树型数据流中内置无序闭子树挖掘算法

摘要

随着信息技术的发展，流数据挖掘是数据挖掘中具有挑战性的问题之一。实时应用中通常会形成大量的数据流，比如传感网络中的传感数据，web中的web记录等等。传统“先存储后处理”的数据挖掘技术不能解决流数据速度快，不能重复扫描，数据量大等特性，对于数据流数据挖掘已经越来越力不从心。而树型数据流是数据流中应用最广的领域之一，因此在树型数据流中挖掘频繁的子树是非常有用的。候选子树数目和支持度计算效率一直是影响树型数据流中频繁子树挖掘的主要因素。
　　 本文首先从理论上提出线性扩展策略，该策略可以简单确定待插入结点的位置和新候选子树的二项编码；然后提出数据结构全属向导LTPS，基于该数据结构提出广度线性扩展算法DFLinApri，该算法可枚举树型数据流中内置无序闭子树，并可有效计算候选子树的支持度，但该算法产生冗余闭子树；最后提出基于数据结构部属向导LTD的算法深度线性扩展算法BFLinApri，算法BFLinApri对算法DFLinApri进行改进，消除冗余。本文实验分别采用合成数据集F5、D10和真实数据集cslogs。实验结果表明本文的两个算法在F5和D10这两个不同规模的数据集上时间效率比PrefixTreeISpan和TreeMine都有明显提高，产生的闭子树数目比PrefixTreeISpan产生的频繁子树数目明显减少。在数据集cslogs上BFLinApri的耗时是TreeMiner的1/2。