不确定数据流最大频繁项集挖掘算法研究  

Mining maximum frequent itemsets over uncertain data streams

作　　者：刘慧婷[1] 候明利 赵鹏[1] 姚晟[1] LIU Huiting;HOU Mingli;ZHAO Peng;YAO Sheng(School of Computer Science and Technology, Anhui University, Hefei 230601, China)

机构地区：[1]安徽大学计算机科学与技术学院,合肥230601

出　　处：《计算机工程与应用》2016年第19期72-77,93,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61202227);安徽省自然科学基金(No.1408085MF122)

摘　　要：对于大型数据,频繁项集挖掘显得庞大而冗余,挖掘最大频繁项集可以减少挖出的频繁项集的个数。可是对于不确定性数据流,传统判断项集是否频繁的方法已不能准确表达项集的频繁性,而且目前还没有在不确定数据流上挖掘最大频繁项集的相关研究。因此,针对上述不足,提出了一种基于衰减模型的不确定性数据流最大频繁项集挖掘算法TUFSMax。该算法采用标记树结点的方法,使得算法不需要超集检测就可挖掘出所有的最大频繁项集,节约了超集检测时间。实验证明了提出的算法在时间和空间上具有高效性。For large data bases, the number of frequent itemsets is huge and redundancy, and mining maximum frequentitemsets is more suitable because the scale of the output is much smaller. But traditional mining maximum frequent itemsetsalgorithm assumes the availability of precise data. Mining frequent itemsets from uncertain data streams is muchmore complicated than precise streams, and there is no research on mining maximum frequent itemsets over uncertaindata streams until now. Therefore, aiming at the shortcoming, the paper proposes a maximum frequent itemsets miningalgorithm TUFSMax. The algorithm adopts a decay window model to find frequent itemsets through calculating expectedsupports, and it uses a new method, called marking the tree nodes. By using the new method, algorithm TUFSMax canavoid super detection in the course of mining all of the maximum frequent itemsets, to save the detection time. Experimentalresults show that the proposed algorithm is efficient in time and space.

关 键 词：不确定性数据流 最大频繁项集 超集检测 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]