同现模式挖掘是交通防控以及舆情事件挖掘的常用技术,而当前的技术不能直接应用于此类应用场景的多数据流同现模式挖掘,因此提出一种面向多数据流的同现模式快速挖掘方法FMCOPS(fast mining co-occurrence patterns).该方法利用基于内存的COP-tree对多数据流中的候选同现模式进行压缩存储和索引;采用最大共同模式搜索算法对候选同现模式集进行剪枝,并获取相关候选同现模式的最大共同模式集;为了提高同现模式挖掘的速度,采用启发式分析方法对最大共同模式集进行单遍分析,以快速发现同现模式.实验结果证明FMCOPS具有很好的准确性、可伸缩性和可用性.
Co-occurrence pattern mining is a popular technique from traffic control to event discovery in social media.However,existing methods for mining co-occurrence from multiple data streams cannot be directly applied to such applications.In this paper,we propose an efficient algorithm for mining co-occurrence patterns from multiple data streams in such application scenario,called FMCOPS.In this algorithm,an in-memory data structure called COP-tree is used to compress and index the data,and large common pattern searching algorithm is utilized to prune the set of candidate co-occurrence pattern and obtain the large common patterns.To boost the speed of mining co-occurrence patterns,we develop a one-pass algorithm that uses the heuristic analysis method to discovery co-occurrence patterns from the set of large common patterns.Our results demonstrate that the proposed approach is better in accuracy,scalability and utility.
[1] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[Z].The 10th Very Large Data Bases,Santiago 1994.
[2] HUANG Y,XIONG H,SHEKHAR S,et al.Mining confident colocation rules without a support threshold[Z].The 2003 ACM Symposium on Applied Computing,New York,2003.DOI:10.1145/952532.952630.
[3] XIAO X,XIE X,LUO Q,et al.Density based co-location pattern discovery[Z].The 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,New York,2008.DOI:10.1145/1463434.1463471.
[4] 邓超,罗泽,阎保平.基于布朗桥模型的重要同现模式挖掘[J].计算机工程,2014,40(12):63-67.DOI:10.3969/j.issn.1000-3428.2014.12.011. DENG Chao,LUO Ze,YAN Baoping.Important Co-occurrence pattern mining based on brown bridge model[J].Computer Engineering,2014,40(12):63-67.DOI:10.3969/j.issn.1000-3428.2014.12.011.
[5] 田晶,王一恒,颜芬,等.一种网络空间现象同位模式挖掘的新方法[J].武汉大学学报:信息科学版,2015,40(5):652-660.DOI:10.13203/j.whugis20130448. TIAN Jing,WANG Yiheng,YAN Fen,et al.A new method for mining co-location patterns between network spatial phenomena[J].Geomatics and Information Science of Wuhan University,2015,40(5):652-660.DOI:10.13203/j.whugis20130448.
[6] CELTIC M.Discovering partial spatio-temporal co-occurrence patterns[Z].2011 IEEE International Conference on Spatidl Oata Mining and Geographical Knowledge Senices, Fuzhou,2011.DOI:10.1109/ICSDM.2011.5969016
[7] CELIK M,AZGINOGLU N,TERZI R.Mining periodic spatio-temporal co-occurrence patterns:A summary of results[Z].Innovations in Intelligent Systems and Applications,Trabzon,2012.DOI:10.1109/INISTA.2012.6247044
[8] 许强,罗泽,魏颖.一种检测时空数据中重要同现模式的快速算法[J].科研信息化技术与应用,2013,4(3):23-31. XU Qiang,LUO Ze,WEI Ying.A fast method for detection of the important co-occurrence cases from spatio-temporal dataset[J].E-science Technology & Application,2013,4(3):23-31.
[9] PILLAI K G,ANGRYK R A,BANDA J M,et al.Spatiotemporal co-occurrence rules [M].Switzerland:Springer International Publishing,2014.DOI:10.1007/978-3-319-01863-8_3.
[10] MOZAFARI B,THAKKAR H.Verifying and mining frequent patterns from large windows over data streams[Z].IEEE 24th International conference on Data Engineeing Cancun,2008.DOI:10.1109/ICDE.2008.4497426.
[11] CHANG J H,LEE W S.Finding recent frequent itemsets adaptively over online data streams[Z].9th ACM SIGKDD international conference on knowledge discovery and data mining,New York,2003.DOI:10.1145/956750.956807.
[12] LEUNG C S,KHAN Q I.Dstree:a tree structure for the mining of frequent sets from data streams[Z].6th Internatianal Confevence on Data Mining,Hongkong,2006.DOI:10.1109/ICDM.2006.62.
[13] GUO J,ZHANG P,TAN J,et al.Mining frequent patterns across multiple data streams[Z].The 20th ACM International Conference on Information and Knowledge Management,New York,2011:2325-2328.DOI:10.1145/2063576.2063957.
