基于有序复合策略的数据流最大频繁项集挖掘  

Maximal Frequent Itemsets in Data Stream Mining Based on Orderly-Compound Policy

作　　者：琚春华[1,2] 许翀寰[2,3] 

机构地区：[1]浙江工商大学现代商贸中心,杭州310018 [2]浙江工商大学计算机与信息工程学院,杭州310018 [3]浙江工商大学工商管理学院,杭州310018

出　　处：《情报学报》2010年第5期864-871,共8页Journal of the China Society for Scientific and Technical Information

基　　金：国家自然科学基金（编号：70671094 71071141）; 浙江省自然科学基金重点项目（编号：Z1091224）

摘　　要：挖掘最大频繁项集的优势在于得到的项目数量较少。相比频繁项集和频繁闭合项集挖掘算法,此类算法具有较高的时间和空间效率。根据数据流的特点,结合滑动窗口,提出一种基于有序复合策略的数据流最大频繁项集挖掘算法（E-FPMFI）。当数据流流过时,以基本窗口为单位,更新获取数据流片段信息,单遍扫描片段信息得到频繁项目并存储于频繁项目列表内。算法的核心思想：构建有序FP-tree,采用混合子集剪枝技术削减搜索空间,合并同一分支中支持数相等的邻接结点,压缩生成有序复合FP-tree,挖掘最大频繁项集时避免超集检验。经实验验证,E-FPMFI算法具有较好的时空效率和良好的可扩展性。Mining maximal frequent itemsets get the advantage of a relatively small number of itemsets.Compared to mining frequent itemsets and mining frequent closed itemsets,such algorithm has higher time and space efficiency.According to the features of data streams and combined sliding window,a new algorithm E-FPMFI which is based on orderly-compound policy for mining maximal frequent itemsets in data stream is proposed.The algorithm based on basic window updates information from data stream flow fragment and scans the stream o uly once to gain and store it in frequent itemsets list.The algorithm construct FP-tree, then compress orderly FP-tree by merging nodes which has equal minsup in same branch,also uses subset mix pruning technique, avoid superset checking.The experimental results show the algorithm has higher time,space efficiency and good scalability.

关 键 词：数据流 最大频繁项集 滑动窗口 有序复合FP-tree 

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