在线挖掘数据流滑动窗口中频繁闭项集

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (5): 1235-1240.

在线挖掘数据流滑动窗口中频繁闭项集

敖富江¹, 杜静², 颜跃进², 黄柯棣¹

1. 国防科学技术大学机电工程与自动化学院, 湖南, 长沙, 410073;
2. 国防科学技术大学计算机学院, 湖南, 长沙, 410073

收稿日期:2008-01-17 修回日期:2008-06-24 出版日期:2009-05-20 发布日期:2010-01-03
作者简介:敖富江(1975- ),男,博士研究生,主要研究方向为数据仓库,数据挖掘和复杂大系统仿真.E-mail:fjao@nudt.edu.cn
基金资助:
国家自然科学基金资助课题(60704038)

Online mining closed frequent itemsets over a stream sliding window

AO Fu-jiang¹, DU Jing², YAN Yue-jin², HUANG Ke-di¹

1. Coll. of Mechanical Engineering and Automation, National Univ. of Defense Technology, Changsha 410073, China;
2. School of Computer Science, National Univ. of Defense Technology, Changsha 410073, China

Received:2008-01-17 Revised:2008-06-24 Online:2009-05-20 Published:2010-01-03

摘要/Abstract

摘要： 在线挖掘滑动窗口中的频繁闭项集是一类重要的数据流挖掘问题.提出了一种新的频繁闭项集挖掘算法FPCFI-DS.该算法能够在有限的存储空间中高速挖掘数据流滑动窗口中的频繁闭项集,并且能够在任意时刻维护当前窗口中精确的频繁闭项集.对于第一个窗口中的数据,FPCFI-DS算法采用单遍过程FPCFI进行挖掘,挖掘结果被保存于一棵全局闭项集树GCT中.当窗口向前滑动时,FPCFI-DS算法采用更新挖掘方式快速挖掘出当前窗口中的频繁闭项集.实验结果表明,FPCFI-DS算法的空间效率和时间效率都显著优于同类经典算法Moment.

Abstract: Online mining closed frequent itemsets in sliding window is one of the most important issues for mining data streams.A novel algorithm,FPCFI-DS,is proposed,which can efficiently mine closed frequent itemsets over a stream sliding window with limited memory space,and maintain exact closed frequent itemsets in current window at any time.For data in the first window,the algorithm FPCFI-DS mines closed frequent itemsets using single-pass procedure,denoted as FPCFI.The resulting closed frequent itemsets are stored in a global closed frequent itemsets tree(GCT).When the window slides forward,the FPCFI-DS quickly updates closed frequent itemsets in current window using the updating-mining method.The experimental results show that FPCFI-DS is superior to that of state-of-the-art algorithm Moment in terms of time and space efficiency.

中图分类号:

TP311

敖富江, 杜静, 颜跃进, 黄柯棣. 在线挖掘数据流滑动窗口中频繁闭项集[J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1235-1240.

AO Fu-jiang, DU Jing, YAN Yue-jin, HUANG Ke-di. Online mining closed frequent itemsets over a stream sliding window[J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1235-1240.

参考文献

[1] Chi Y,Wang H,Yu PS,et al.Moment:maintaining closed frequent itemsets over a stream sliding window[C]//Proc,of ICDM,2004:59-66.
[2] Li HF,Ho CC,Kuo FF,et al.A new algorithm for maintaining closed frequent itemsets in data streams by incremental updates[C]//Proc.of IWMESD,Hong Kong,2006.
[3] Nan J,Gruenwald L.CFl-stream:mining closed frequent itemsets in data streams[C]//Proc,of KDD,2006,592-597.
[4] 刘旭,毛国君,等.数据流中频繁闭项集的近似挖掘算法[J].电子学报,2007,35(5):900-905.
[5] 刘学军,徐宏炳,等.基于滑动窗口的数据流闭合频繁模式的挖掘[J].计算机研究与发展,2006,43(10):1738-1743.
[6] Li HF,Lee S,Shah M.Online mining (Recently)maximal frequent itemsets over data streams[C]//Proc,of RIDE-SDMA,Tokyo,Japan:IEEE Press,2005:11-18.
[7] Chang J,Lee WS.Finding recent frequent itemsets adaptively over online data streams[C]//Proc,of KDD'03,Washington,USA:ACM Press,2003:487-492.
[8] Ao FJ,Yah YJ,et al.Mining maximal frequent itemsets in data streams based on FP-Tree[C]//Proc.of the 5th Int.Conf.on Machine Learning and Data Mining,Leipzig,German,July,2007:479-489.
[9] Zhu Y,Shasha D.Statstream:statistical monitoring of thousands of data streams in real time[C]//Proc.of VLDB'2002.Hong Kong:Morgan Kau fmann,2002:358-369.
[10] Grahne G,Zhu JF.Efficiently using prefix-trees in mining frequent itemsets[C]//Proc.of FIMI,2003.
[11] Pei J,Han J,Mao R.CLOSET:an efficient algorithm for mining frequent closed itemsets[C]//Proc,of DMKD' 00,2000.
[12] Yan YJ,Li ZJ,Chen HW.Fast mining maximal frequent itemsets based on FP-trea[C]//Proc.of the 17th Australian Computer Society (ACS)Australian Joint Conference on Artificial Intelligence,Cairns Australia,December,2004:475-487.
[13] Goethals B.The FIMI repository[EB],http://fimi,cs.helsinki,fi,2003.
[14] Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proc.of VLDB,Santiago,Chile,Sept,1994:487-499.

[1]	刘延钊, 黄志球, 沈国华, 王金永, 徐恒. 基于决策树和BN的自动驾驶车辆行为决策方法[J]. 系统工程与电子技术, 2022, 44(10): 3143-3154.
[2]	陈江美, 张文德. 基于灰关联分析和时空偏好特征的兴趣点推荐算法[J]. 系统工程与电子技术, 2022, 44(6): 1934-1941.
[3]	任耀军, 袁修久, 黄林. q阶三角犹豫模糊BM算子及其多属性决策应用[J]. 系统工程与电子技术, 2022, 44(1): 181-191.
[4]	陈云翔, 饶益, 蔡忠义, 王泽洲. 基于改进相似性的装备部件剩余寿命预测及经济性储备策略[J]. 系统工程与电子技术, 2021, 43(9): 2688-2696.
[5]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[6]	孙雪, 黄志球, 沈国华, 王金永, 徐恒. 基于本体和BN的无人车行为决策方法[J]. 系统工程与电子技术, 2021, 43(2): 452-465.
[7]	张磊, 马春光, 印桂生. 匿名区域层级扩张的位置隐私保护方法[J]. 系统工程与电子技术, 2021, 43(2): 561-566.
[8]	龚丹, 王甜甜, 苏小红, 董美含. 基于软件历史仓库和抽象语法树的相似缺陷识别方法[J]. 系统工程与电子技术, 2020, 42(10): 2399-2408.
[9]	周海岩. 建立频繁项目集向量的极大频繁项目集挖掘[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2497-2500.
[10]	侯东风, 陆昌辉, 刘青宝, 张维明. 流式数据多维模型 [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 2003-2007.
[11]	吴彩华, 朱小冬, 刘俊涛, 王毅刚. 一种新的软件可靠性增长模型 [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 2024-2028.
[12]	刘波, 杨路明, 邓云龙. 一种自适应的XML数据流质量预测策略[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1485-1491.
[13]	李海峰, 陆民燕, 王学成. 考虑右删失数据的改进Jelinski-Moranda软件可靠性模型[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1496-1499.
[14]	杜荣华. 一种促进PSO全局收敛的参数调整策略[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1454-1457.
[15]	孙梦璘, 甘志强. 航天型号软件代码质量度量评估实现[J]. Journal of Systems Engineering and Electronics, 2009, 31(4): 956-959.