基于聚类划分的高效用模式并行挖掘算法

doi:10.11772/j.issn.1001-9081.2016.08.2202

计算机应用 ›› 2016, Vol. 36 ›› Issue (8): 2202-2206.DOI: 10.11772/j.issn.1001-9081.2016.08.2202

基于聚类划分的高效用模式并行挖掘算法

邢淑凝^1,2, 刘方爱^1,2, 赵晓晖^1,2

1. 山东师范大学信息科学与工程学院, 济南 250014;
2. 山东省分布式计算机软件新技术重点实验室(山东师范大学), 济南 250014

收稿日期:2016-01-11 修回日期:2016-02-27 出版日期:2016-08-10 发布日期:2016-08-10
通讯作者: 刘方爱
作者简介:邢淑凝(1992-),女,山东青岛人,硕士研究生,CCF会员,主要研究方向:数据挖掘、大数据分析;刘方爱(1962-),男,山东青岛人,教授,博士生导师,博士,主要研究方向:并行计算模型、分布式网络、数据挖掘;赵晓晖(1981-),女,河南范县人,讲师,博士研究生,主要研究方向:复杂网络、数据挖掘。
基金资助:
国家自然科学基金资助项目（90612003,61572301）。

Parallel high utility pattern mining algorithm based on cluster partition

XING Shuning^1,2, LIU Fang'ai^1,2, ZHAO Xiaohui^1,2

1. College of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250014, China;
2. Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology(Shandong Normal University), Jinan Shandong 250014, China

Received:2016-01-11 Revised:2016-02-27 Online:2016-08-10 Published:2016-08-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (90612003, 61572301).

摘要/Abstract

摘要： 针对在大规模数据库中挖掘高效用模式产生大量基于内存的效用模式树，从而导致内存空间占用较大以及丢失一些高效用项集的问题，提出在Hadoop分布式计算平台下的基于聚类划分的高效用模式并行挖掘算法PUCP。首先，采用聚类的方法把数据库中相似的事务划分为若干数据子集；然后，把若干划分好的数据子集分配到Hadoop平台的各个节点中构造效用模式树；最后，把各个节点中相同项的条件模式基分配到同一个节点中进行挖掘，以减少各个节点交叉操作的次数。通过实验结果和理论分析表明：PUCP算法在不影响挖掘结果可靠性的前提下，与主流串行高效用模式挖掘——效用模式增长挖掘算法（UP-Growth）和现有的并行高效用模式挖掘算法PHUI-Growth相比，挖掘效率分别提高了61.2%和16.6%；并且使用了Hadoop计算平台，能有效缓解挖掘大规模数据的内存压力。

关键词: 大数据, 高效用模式挖掘, 聚类, 并行计算, Hadoop

Abstract: The exiting algorithms generate a lot of utility pattern trees based on memory when mining high utility patterns in large-scale database, leading to occupying more memory spaces and losing some high utility itemsets. Using Hadoop platform, a parallel high utility pattern mining algorithm, named PUCP, based on cluster partition was proposed. Firstly, the clustering method was introduced to divide the transaction database into several sub-datasets. Secondly, sub-datasets were allocated to each node of Hadoop to construct utility pattern tree. Finally, the conditional pattern bases of the same item which generated from utility pattern trees were allocated to the same node, reducing the crossover operation times of each node. The theoretical analysis and experimental results show that, compared with the mainstream serial high utility pattern mining algorithm named UP-Growth (Utility Pattern Growth) and parallel high utility pattern mining algorithm named HUI-Growth (Parallel mining High Utility Itemsets by pattern-Growth), the mining efficiency of PUCP is increased by 61.2% and 16.6% respectively without affecting the reliability of the mining results; and the memory pressure of large data mining can be effectively relieved by using Hadoop platform.

Key words: big data, high utility pattern mining, clustering, parallel computing, Hadoop

中图分类号:

TP301.6

邢淑凝, 刘方爱, 赵晓晖. 基于聚类划分的高效用模式并行挖掘算法[J]. 计算机应用, 2016, 36(8): 2202-2206.

XING Shuning, LIU Fang'ai, ZHAO Xiaohui. Parallel high utility pattern mining algorithm based on cluster partition[J]. Journal of Computer Applications, 2016, 36(8): 2202-2206.

参考文献

[1] JAGRAW R,SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann,1994:487-499.
[2] HAN J W,KAMBER M.数据挖掘:概念与技术[M].范明,孟小峰,译.2版.北京:机械工业出版社,2007:206-228.(HAN J W,KAMBER M.Data Mining:Concepts and Techniques[M].FAN M,MENG X F,translated.2nd ed.Beijing:China Machine Press,2007:206-228.)
[3] ZIHAYAT M,AN A.Mining top-k high utility patterns over data streams[J].Information Sciences,2014,285:138-161.
[4] YUN U,RYANG H.Incremental high utility pattern mining with static and dynamic databases[J].Applied Intelligence,2015,42(2):323-352.
[5] YUN U,RYANG H,RYU K H.High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates[J].Expert Systems with Applications,2014,41(8):3861-3878.
[6] SONG W,LIU Y,LI J.Mining high utility itemsets by dynamically pruning the tree structure[J].Applied Intelligence,2014,40(1):29-43.
[7] SHIE B-E,HSIAO H-F,TSENG V S.Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments[J].Knowledge and Information Systems,2013,37(2):363-387.
[8] LEE D,PARK S-H,MOON S.Utility-based association rule mining:a marketing solution for cross-selling[J].Expert Systems with Applications,2013,40(7):2715-2725.
[9] LIU Y,LIAO W-K,CHOUDHARY A.A two-phase algorithm for fast discovery of high utility itemsets[M]//PAKDD'05:Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Berlin:Springer-Verlag,2005:689-695.
[10] TSENG V S,WU C-W,SHIE B-E,et al.UP-Growth:an efficient algorithm for high utility itemset mining[C]//KDD'10:Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2010:253-262.
[11] SHIE B-E,HSIAO H-F,TSENG V S.Efficient algorithms for discovering high utility user behavior patterns in mobile commerce environments[J].Knowledge and Information Systems,2013,37(2):363-387.
[12] LIN Y C,WU C-W,TSENG V S.Mining high utility itemsets in big data[C]//PAKDD 2015:Proceedings of the 19th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,LNCS 9078.Berlin:Springer-Verlag,2015:649-661.
[13] LIU Y,LIAO W-K,CHOUDHARY A.A fast high utility itemsets mining algorithm[C]//UBDM'05:Proceedings of the 1st International Workshop on Utility-based Data Mining.New York:ACM,2005:90-99.
[14] JAIN A K,DUBES R C.Algorithms for clustering data[M]//Algorithms for Clustering Data.Upper Saddle River,NJ:Prentice Hall,1988:227-229.
[15] Frequent itemset mining implementations repository[EB/OL].[2015-12-22].http://fimi.cs.Helsinki.fi.

基于聚类划分的高效用模式并行挖掘算法

Parallel high utility pattern mining algorithm based on cluster partition

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	曾祥银, 郑伯川, 刘丹. 基于深度卷积神经网络和聚类的左右轨道线检测[J]. 计算机应用, 2021, 41(8): 2324-2329.
[3]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[4]	戴嫣然, 戴国庆, 袁玉波. 基于肤色学习的多人脸前景抽取方法[J]. 计算机应用, 2021, 41(6): 1659-1666.
[5]	马建红, 曹文斌, 刘元刚, 夏爽. 基于功效特征的专利聚类方法[J]. 计算机应用, 2021, 41(5): 1361-1366.
[6]	李国荣, 冶继民, 甄远婷. 基于新的鲁棒相似性度量的时间序列聚类[J]. 计算机应用, 2021, 41(5): 1343-1347.
[7]	王治和, 常筱卿, 杜辉. 基于万有引力的自适应近邻传播聚类算法[J]. 计算机应用, 2021, 41(5): 1337-1342.
[8]	龙超奇, 蒋瑜, 谢雨. 基于峰值网格改进的小波聚类算法[J]. 计算机应用, 2021, 41(4): 1122-1127.
[9]	李杏峰, 黄玉清, 任珍文, 李毅红. 基于自适应邻域的鲁棒多视图聚类算法[J]. 计算机应用, 2021, 41(4): 1093-1099.
[10]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[11]	郭佳, 韩李涛, 孙宪龙, 周丽娟. 自动确定聚类中心的比较密度峰值聚类算法[J]. 计算机应用, 2021, 41(3): 738-744.
[12]	吕佳, 鲜焱. 结合改进密度峰值聚类和共享子空间的协同训练算法[J]. 计算机应用, 2021, 41(3): 686-693.
[13]	邹志文, 秦程. 基于k-means++的动态构建空间主题R树方法[J]. 计算机应用, 2021, 41(3): 733-737.
[14]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[15]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.