并行挖掘频繁项目集新算法——MREclat

doi:10.11772/j.issn.1001-9081.2014.08.2175

计算机应用 ›› 2014, Vol. 34 ›› Issue (8): 2175-2178.DOI: 10.11772/j.issn.1001-9081.2014.08.2175

• 第五届中国数据挖掘会议(CCDM 2014)论文 • 上一篇下一篇

并行挖掘频繁项目集新算法——MREclat

章志刚,吉根林,唐梦梦

南京师范大学计算机科学与技术学院，南京210023

收稿日期:2014-04-30 修回日期:2014-05-10 出版日期:2014-08-01 发布日期:2014-08-10
通讯作者: 吉根林
作者简介:章志刚(1988-)，男，江苏海安人，硕士研究生，主要研究方向：云计算、数据挖掘；吉根林(1964-)，男，江苏海安人，教授，博士生导师，博士，CCF高级会员，主要研究方向：数据挖掘；唐梦梦(1990-)，女，江苏连云港人，硕士研究生，主要研究方向:空间轨迹挖掘。
基金资助:
江苏省自然科学基金资助项目

MREclat: new algorithm for parallel mining frequent itemsets

ZHANG Zhigang,JI Genlin,TANG Mengmeng

School of Computer Science and Technology, Nanjing Normal University, Nanjing Jiangsu 210023, China

Received:2014-04-30 Revised:2014-05-10 Online:2014-08-01 Published:2014-08-10
Contact: JI Genlin

摘要/Abstract

摘要：

针对Eclat算法在挖掘海量数据中的频繁项目集时存在的内存和计算资源不足等问题，提出了基于Map/Reduce计算模型的并行挖掘算法——MREclat。首先，将水平型数据库转换成垂直型数据库；然后，将转换后的数据按2-项集的前缀分发到各个计算节点上，且在分发数据时引入了均衡策略；接着，在各个计算节点上求出以某一前缀开头的所有频繁项目集；最后，合并各个节点的结果得到所有频繁项目集。介绍了MREclat的设计思想，研究了算法的运行性能。实验结果表明，MREclat算法效率大约是PEclat算法的2倍，加速比性能比PEclat算法提高了64%。

Abstract:

Aiming at the problem that the memory and computational capability is insufficient while using Eclat algorithm to mine frequent itemsets from massive dataset, a parallel mining algorithm based on Map/Reduce framework, called MREclat(MapReduce Eclat), was proposed. Firstly, MREclat algorithm converted the horizontal database into a vertical one. Secondly, it redistributed the converted dataset according to the first item of each frequent 2-itemset and load-balance was taken into consideration while distributing datasets. Then, all the frequent itemsets prefixed by the same item were computed in each computing node. Finally, MREclat algorithm collected the result of each computing node and generated the whole frequent itemsets. In this paper, the idea of MREclat was introduced and the performance of the algorithm was studied. The experimental results show that MREclat algorithm is twice as efficient as PEclat algorithm, and the speedup performance of MREclat algorithm is 64% higher than that of PEclat.

中图分类号:

TP311.13

章志刚吉根林唐梦梦. 并行挖掘频繁项目集新算法——MREclat[J]. 计算机应用, 2014, 34(8): 2175-2178.

ZHANG Zhigang JI Genlin TANG Mengmeng. MREclat: new algorithm for parallel mining frequent itemsets[J]. Journal of Computer Applications, 2014, 34(8): 2175-2178.

参考文献

［1］LIBEN-NOWELL D, KLEINBERG J. The link prediction problem for social networks ［J］. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.
［2］HUANG Z, LI X, CHEN H. Link prediction approach to collaborative filtering ［C］// JCDL'05: Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries. Piscataway: IEEE Press, 2005: 141-142.
［3］BISCHOFF K, FIRAN C, GEORGESCU M. Social knowledge-driv-en music hit prediction ［C］// ADMA 2009: Proceedings of the 5th International Conference on Advanced Data Mining and Applications. Berlin: Springer, 2009: 43-54.
［4］PAVLOV M, ICHISE R. Finding experts by link prediction in co-authorship networks ［EB/OL］. ［2014-01-15］. http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-290/paper04.pdf.
［5］JEH G, WIDOM J, SIMRAN K. A measure of structural context similarity ［C］// Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, ACM Press, 2002: 538-543.
［6］BLONDEL V D, GAJARDO A, HEYMANS M, et al. A measure of similarity between graph vertices: applications to synonym extraction and Web searching ［J］. SIAM Review, 2004, 46(4): 647-666.
［7］SARUKKAI R R. Link prediction and path analysis using Markov chains ［J］. Computer Networks, 2003, 33(6): 377-386.
［8］FRIEDMAN N, GETOOR L, KOLLER D, et al. Learning probabilistic relational models ［C］// IJCAI'99: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers, 1999: 1300-1309.
［9］HECKERMAN D, MEEK C, KOLLER D. Probabilistic entity-relationship models, PRMs, and plate models ［C］// Proceedings of the ICML-2004 Workshop on Statistical Relational Learning and its Connections to Other Fields. Banff: ［s.n.］, 2004: 55-60.
［10］ZHOU T, L L, ZHANG Y C. Predicting missing links via local information ［J］. The European Physical Journal B, 2009, 71(4): 623-630.
［11］DONG Y, KE Q, WU B. Link prediction based on node similarity ［J］. Computer Science, 2011, 38(7): 162-199.(东昱晓,柯庆,吴斌.基于节点相似性的链接预测［J］.计算机科学,2011,38(7):162-199.)
［12］L L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks ［J］. Physical Review E, 2009, 80(4): 046122.
［13］KATZ L. A new status index derived from sociometric analysis ［J］. Psychometrika, 1953, 18(1): 39-43.
［14］SHEN Y. Link prediction in complex networks ［D］. Guangzhou: South China University of Technology, 2011.(沈勇明.复杂网络链接预测［D］.广州：华南理工大学,2011.)
［15］TENG Z. Research on link prediction for dynamic networks ［D］. Jinan: Shandong University, 2012.(滕兆明.动态多维社会网络链接预测研究［D］.济南：山东大学,2012.)
［16］YIN H. Research on link prediction for social networks ［D］. Changchun: Jilin University, 2012.(殷涵.社会网络链接预测研究［D］.长春：吉林大学,2012.)
［17］ZHAO C. Link prediction for social networks ［D］. Harbin: Harbin Institute of Technology, 2012.(赵婵媛.社会网络链接算法研究［D］.哈尔滨：哈尔滨工业大学,2012.)
［18］GAO S, DENOYER L, GALLINARI P. Temporal link prediction by integrating content and structure information ［C］// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM Press, 2011: 1169-1174.
［19］CUI A, FU Y, SHANG M, et al. The local structure of complex networks sprung up: common neighbor drive network evolution ［J］. Acta Physica Sinica, 2011, 60(3): 803-808.(崔爱香,傅彦,尚明生,等.复杂网络局部结构的涌现:共同邻居驱动网络演化［J］.物理学报,2011,60(3):803-808.)
［20］ADAMIC L A, ADAR E. Friends and neighbors on the Web ［J］. Social Networks, 2003, 25(3): 211-230.
［21］SUN H. Research on link prediction based on transactional information ［D］. Qinhuangdao: Yanshan University, 2010.(孙浩.基于事物信息的链接预测算法研究［D］.秦皇岛：燕山大学，2010.)
［22］LI Y, XIAO H, LI D, et al. Research of dynamic link prediction method based on link importance ［J］. Journal of Computer Research and Development, 2011,48(z2): 40-46.(李玉华,肖海岭,李栋才,等.基于链接重要性的动态链接预测方法研究［J］.计算机研究与发展,2011,48(z2):40-46.)
［23］MURATA T, SAKIKO M. Link prediction of social networks based on weighted proximity measures ［C］// Proceedings of the 2007 IEEE/WIC/ACM International Conference on Web Intelligence. Washington, DC: IEEE Computer Society, 2007: 86-88.
［24］GRANOVETTER M S. The strength of weak ties ［J］. Journal of American Sociology, 1973, 78(6): 1368-1178.
［25］WATTS D. Network dynamics between order and disorder ［M］. CHEN Y, translate. Beijing: China Renmin University Press, 2006: 14-17.(WATTS D.有序与无序之间的网络动力学［M］.陈禹,译.北京:中国人民大学出版社，2006:14-17.)
［26］TAN C, TANG J, SUN J, et al. Social action tracking via noise tolerant time-varying factor graphs ［C］// KDD'10: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2010: 1049-1058.

[1]	赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.
[2]	冯钧王秉发陆佳民. 分布式资源描述框架数据管理系统查询性能评价[J]. 计算机应用, 0, (): 0-0.
[3]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[4]	林定康颜嘉麒巴·楠登符朕皓姜皓晨. 门罗币匿名及追踪技术综述[J]. 计算机应用, 0, (): 0-0.
[5]	沈忱, 邰凌翔, 彭煜玮. 面向自动参数调优的动态负载匹配方法[J]. 计算机应用, 2021, 41(3): 657-661.
[6]	杨程, 陆佳民, 冯钧. 分布式环境下大规模资源描述框架数据划分方法综述[J]. 计算机应用, 2020, 40(11): 3184-3191.
[7]	兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 计算机应用, 2020, 40(2): 410-415.
[8]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[9]	万静, 郑龙君, 何云斌, 李松. 高维不确定数据的子空间聚类算法[J]. 计算机应用, 2019, 39(11): 3280-3287.
[10]	李博, 张晓, 颜靖艺, 李可威, 李恒, 凌玉龙, 张勇. 基于值差度量和聚类优化的K最近邻算法在银行客户行为预测中的应用[J]. 计算机应用, 2019, 39(9): 2784-2788.
[11]	李耘书, 滕飞, 李天瑞. 基于微操作的Hadoop参数自动调优方法[J]. 计算机应用, 2019, 39(6): 1589-1594.
[12]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[13]	朱跃龙, 朱晓晓, 王继民. 基于子序列全连接和最大团的时间序列模体发现算法[J]. 计算机应用, 2019, 39(2): 414-420.
[14]	尹远, 张昌, 文凯, 郑云俊. 基于DiffNodeset结构的最大频繁项集挖掘算法[J]. 计算机应用, 2018, 38(12): 3438-3443.
[15]	曲立平, 吴家喜. 基于评分可靠性的跨域个性化推荐方法[J]. 计算机应用, 2018, 38(11): 3081-3083.

并行挖掘频繁项目集新算法——MREclat

MREclat: new algorithm for parallel mining frequent itemsets

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics