并行挖掘频繁项目集新算法——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-10 出版日期:2014-08-01
通讯作者: 吉根林
作者简介:章志刚(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-10 Published:2014-08-01
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]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[3]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[4]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[5]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[6]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	蒋辉, 闫秋艳, 姜竹郡. 面向多元时间序列异常检测的对称正定自编码器方法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3294-3299.
[9]	宋洪涛, 于江生, 韩启龙. 工业多元时序数据质量评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1743-1750.
[10]	孟玉飞, 武优西, 王珍, 李艳. 对比保序模式挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3740-3746.
[11]	王佳鑫, 颜嘉麒, 毛谦昂. 加密数字货币监管技术研究综述[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 2983-2995.
[12]	黄硕, 李艳辉, 曹建秋. 本地化差分隐私下的频繁序列模式挖掘算法PrivSPM[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2057-2064.
[13]	金泳, 高扬华, 潘晓华, 沈诗婧, 朱心洲. 采用数据血缘的数据热度预测方法[J]. 《计算机应用》唯一官方网站, 2023, 43(S1): 119-125.
[14]	马志峰, 于俊洋, 王龙葛. 多样性表示的深度子空间聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 407-412.
[15]	王旭, 申玉民, 熊晓芸, 李鹏, 王金龙. 基于哈希图的建筑物联网数据管理方法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2471-2480.

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

MREclat: new algorithm for parallel mining frequent itemsets

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics