一种基于滑动窗口的多关系模式频度更新算法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (3): 671-676.

一种基于滑动窗口的多关系模式频度更新算法

侯伟¹, 杨炳儒¹, 吴晨生², 周谆¹

1. 北京科技大学信息工程学院, 北京, 100083;
2. 北京市科学技术情报研究所, 北京, 100037

收稿日期:2008-02-01 修回日期:2008-07-05 出版日期:2009-03-20 发布日期:2010-01-03
作者简介:侯伟(1981- ),男,博士研究生,主要研究方向为数据挖掘.E-mail:dr.houwei@gmail.com
基金资助:
国家自然科学基金资助课题(60675030)

Multi-relational pattern frequency update algorithm based on sliding window

HOU Wei¹, YANG Bing-ru¹, WU Chen-sheng², ZHOU Zhun¹

1. School of Information Engineering, Univ. of Science and Technology Beijing, Beijing 100083, China;
2. Beijing Municipal Inst. of Science and Technology Information, Beijing 100037, China

Received:2008-02-01 Revised:2008-07-05 Online:2009-03-20 Published:2010-01-03

摘要/Abstract

摘要： 面向多个相关数据流的挖掘算法研究尚处于起步阶段。作为多数据流挖掘算法的基础,模式频度更新算法仍然存在计数不准确、性能较低等问题,难以以此构造有效的挖掘算法。通过引入多关系挖掘概念以及目标关系定义,进而限定计数对象,提出了一种基于滑动窗口的多关系模式频度更新算法MRPFU。该算法监视各数据流窗口的更新情况,采用计数传播策略,减少了时间与空间复杂度。理论分析及实验结果证明了所提算法的有效性且具有较高性能。

Abstract: Presently,the study of mining algorithms for multiple correlated data streams is still at a primitive stage.As the basis of mining multiple data streams,the methods of updating the frequencies of patterns,are bearing problems of count deviation,low performances etc.Consequently,efficient mining algorithms are difficult to be built either.The concepts of multi-relational data mining and target relation are introduced firstly,and the count object is defined accordingly.Then an algorithm based on sliding windows for updating frequencies of multi-relational patterns is proposed,which monitors the updates of streams,adopts the strategy of count propagation,and relieves the complexity of runtime and space.The theoretical analysis and experiments prove its effectiveness and performance.

中图分类号:

TP182

侯伟, 杨炳儒, 吴晨生, 周谆. 一种基于滑动窗口的多关系模式频度更新算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(3): 671-676.

HOU Wei, YANG Bing-ru, WU Chen-sheng, ZHOU Zhun. Multi-relational pattern frequency update algorithm based on sliding window[J]. Journal of Systems Engineering and Electronics, 2009, 31(3): 671-676.

参考文献

[1] Han J,Kamber M.Data mining;concepts and techniques[M].San Francisco:Morgan Kaufmann,2000.
[2] Babcock B,Babu S,Datar M,et al.Models and issues in data stream systems[C].Proc.of the 21th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.Wisconsin:Madison,2002:1-16.
[3] Gaber M M,Zaslavsky A,Krishnaswamy S.Mining data streams:A review[J].ACM SIGMOD Record,2005,34(2):18-26.
[4] Garofalakis M N,Gehrke J,Rastogi R.Querying and mining data streams:you only get one look[C].Proc.of the 28th Int.Conf.on Very Large Data Bases,Hong Kong,2002.
[5] Kontaki M,Papadopoulos A N,Manolopoulos Y.Effident incremental subspace clustering in data streams[C].Proc.of Datobase Engineering and Applications Symposium,Delhi,India,2006.
[6] Commnde G,Muthukrishnan S.What's new:Finding significant differences in network data streams[C].Proc.of IEEE INFOCOM,Hang Koag,2004.
[7] Chen R,Sivakumar K,Kargupta H.Distributed web mining using bayesian networks from multiple data streams[C].Proc.of ICDM',San Jose,California,2001.
[8] Xu Y,Wang K,Fu A,et al.Classification spanning correlated data streams[C].Proc.of CIKM',Arlington,Virginia,2006.
[9] Dzeroski S,Lavrac N.Relational data mining[M].Berlin:Springer,2001.
[10] Terry D,Goldberg D,Nichols D,et al.Continuous queries over append-only databases[C].proc.of ICMD,1992:321-330.
[11] Golab L,(o)zsu M T.Processing sliding window multi-joins in continuous queries over data streams[C].Proc.of the 29th VLDB Conf.,Berlin,Germany,2003.
[12] Srivastava U,Widom J.Memory-limited execution of windowed stream joins[C].Proc.of the 30th VLDB Conf.,Toronto,Canada,2004.
[13] Gedik B,Wu K,Yu P S,et al.GRUBJOIN:An adaptive multiway windowed stream join with time correlation-aware CPU load shedding[J].Transactions on Knowledge and Data Engineering,2007,19(10):1363-1380.
[14] 钱江渡,徐宏炳,董逸生,等.基于最小生成树的数据流窗口连接优化算法[J].计算机研究与发展,2007,44(6):1000-1007.
[15] Yin X,Han J,Yang J,et al.CrossMine:efficient classification across multiple database relations[C].Proc.of the 20th International Conference on Data Engineering,Boston,2004.
[16] Atramentov A,Leiva H,Honavar V.A multi-relational decision tree learning algorithm-implementation and experiments[C].Proc.of ILP,Szeged,Hungary,2003.
[17] Sourc forge research data[OL].http://www.nd.edu/～oss/Data/data.html,2002.