一种新的软聚类投票法及其并行化实现

doi:10.3969/j.issn.0253-2778.2016.03.001

中国科学技术大学学报 ›› 2016, Vol. 46 ›› Issue (3): 173-179.DOI: 10.3969/j.issn.0253-2778.2016.03.001

• 论著 •

一种新的软聚类投票法及其并行化实现

张静静，杨燕*，王红军，韩晓涛，邓强

西南交通大学信息科学与技术学院, 成都 611756

收稿日期:2015-08-27 修回日期:2015-09-29 接受日期:2015-09-29 出版日期:2015-09-29 发布日期:2015-09-29
通讯作者: 杨燕
作者简介:张静静，女，1989年生，硕士. 研究方向：数据挖掘、云计算. E-mail: youyouzhangjing@yeah.net.
基金资助:
国家自然科学基金项目(Nos. 61134002，61170111,61572407)资助.

A novel voting method and parallel implementation for soft clustering

ZHANG Jingjing,YANG Yan*,WANG Hongjun, HAN Xiaotao,DENG Qiang

School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756

Received:2015-08-27 Revised:2015-09-29 Accepted:2015-09-29 Online:2015-09-29 Published:2015-09-29

摘要/Abstract

摘要： 聚类集成作为数据挖掘的重要应用工具，得到了广泛的认可和研究.本文在投票法的基础上提出一种新的软聚类投票 (VMSC)算法.算法首先求取平均隶属度矩阵，然后进行迭代优化.该算法能够消除噪声点影响，具有很好的稳定性.Spark云计算平台能够高效处理大数据.为了提出的算法处理大数据，在Spark云计算平台上实现并行的VMSC算法.VMSC算法实验用12组UCI数据集进行验证，并与sCSPA、sMCLA、sHGBF及SVCE等软聚类算法进行对比.结果表明，VMSC算法对软聚类算法具有较好的集成效果.在Spark云计算平台上对VMSC算法并行实现.实验表明，该算法具有较理想的并行效果，能够有效处理大数据.

关键词: 软聚类集成, 投票, 云计算, 大数据

Abstract: As an important tool of Data Mining, clustering ensemble has been widely recognized and studied. This paper proposes a novel voting method for Soft Clustering(VMSC). The ensemble process consists of two steps: calculating the average degree of membership matrix as the input of the second step, and iterative optimization. This method deals well with eliminating the influences of noise and has good stability. The cloud computing platform of Spark handles big data efficiently. The VMSC algorithm was parallelizod to make it suitable for big data on Spark Cloud Computing platform. In the VMSC experiments, 12 UCI datasets were used to test it, and its results were compared with 4 other soft clustering ensemble algorithms: sCSPA, sMCLA, sHGBF and SVCE. The experiments indicate that the VMSC algorithm has a better integration effect. And the parallel experiments show that its parallel implementation manages big data efficiently.

Key words: soft clustering ensemble, voting, cloud computing, big data

中图分类号:

TP301

张静静，杨燕*，王红军，韩晓涛，邓强. 一种新的软聚类投票法及其并行化实现[J]. 中国科学技术大学学报, 2016, 46(3): 173-179.

ZHANG Jingjing,YANG Yan*,WANG Hongjun, HAN Xiaotao,DENG Qiang. A novel voting method and parallel implementation for soft clustering[J]. Journal of University of Science and Technology of China, 2016, 46(3): 173-179.

参考文献

［1］
孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1): 48-61.
SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1): 48-61.
[2] CADES I V, SMYTH P, MANNILA H. Probabilistic modeling of transaction data with applications to profiling, visualization, and prediction [C]// Proceedings of the 7th ACM SIGKDD. San Francisco, USA: ACM Press, 2001: 37-46.
[3] JAIN A K, MURTY M N, FLYNN P J. Data clustering: A review[J]. ACM Computing Surveys, 1999, 31(3): 264-323.
[4] WOLPERT D H, MACREADY W G. No free lunch theorems for search[R]. Santa Fe: Santa Fe Institute, Technical Report: SFI-TR-95-02-010, 1996.
[5] STREHL A, GHOSH J. Cluster ensembles--a knowledge reuse framework for combining multiple partitions[J]. The Journal of Machine Learning Research, 2003, 3(1): 583-617.
[6] DIMITRIADOU E, WEINGESSEL A, HORNIK K. A combination scheme for fuzzy clustering[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2002, 16(7): 901-912.
[7] FERN X Z, BRODLEY C E. Solving cluster ensemble problems by bipartite graph partitioning[C]//Proceedings of the 21st International Conference on Machine Learning. Banff , Canada: ACM Press, 2004: 36.
[8] TOPCHY A, JAIN A K, PUNCH W. A mixture model for clustering ensembles[C]//Proceedings of the SIAM International Conference on Data Mining. Baltimore, USA: SIAM Press, 2004: 379.
[9] FRED A L N, JAIN A K. Combining multiple clusterings using evidence accumulation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(6): 835-850.
[10] ZHOU Z H, TANG W. Clusterer ensemble[J]. Knowledge-Based Systems, 2006, 19(1):77-83.
[11] NGUYEN N, CARUANA R. Consensus clusterings[C]//Proceedings of the 7th International Conference on Data Mining. Omaha, USA: IEEE Press, 2007: 607-612.
[12] TUMER K, AGOGINO A K. Ensemble clustering with voting active clusters [J]. Pattern Recognition Letters, 2008, 29(14):1947-1953.
[13] WANG H, YANG Y, WANG H, et al. Soft-Voting Clustering Ensemble [A]// Lecture Notes in Computer Science, 2013, 7872: 307-318.
[14] REN Y, DOMENICONI C, ZHANG G, et al. Weighted-object ensemble clustering[C]// Proceeding of the 13th International Conference on Data Mining. IEEE Press, 2013: 627-636.
[15] CHAKERI A, HALL L O. Dominant sets as a framework for cluster ensembles: An evolutionary game theory approach[C]//Proceeding of 22nd International Conference on Pattern Recognition. Stockholm, Sweden: IEEE Press, 2014: 3457-3462.
[16] DUMONCEAUX F, RASCHIA G, GELGON M. An algebraic approach to ensemble clustering[C]//Proceeding of 22nd International Conference on Pattern Recognition Stockholm, Sweden: IEEE Press, 2014: 1301-1306.
[17] SU P, SHANG C, SHEN Q. Link-based pairwise similarity matrix approach for fuzzy c-means clustering ensemble[C]//Proceeding of 22nd International Conference on Fuzzy Systems. IEEE Press, 2014: 1538-1544.
[18] HAO Z F, WANG L J, CAI R C, et al. An improved clustering ensemble method based link analysis[J]. World Wide Web, 2015, 18(2): 185-195.
[19] ZHONG C, YUE X, ZHANG Z, et al. A clustering ensemble: Two-level-refined co-association matrix with path-based transformation[J]. Pattern Recognition, 2015, 48(8): 2699-2709.
[20] DEAN J, GHEM A S. MapReduce: Simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.
[21] STEPENOSKY N, GREEN D, KOUNIOS J, et al. Majority vote and decision template based ensemble classifiers trained on event related potentials for early diagnosis of Alzheimer's disease[C]//Proceeding of the International Conference on Acoustics, Speech and Signal Processing. Toulouse, France: IEEE Press, 2006: 1935-1941.
[22] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]// Proceeding NSDI'12 Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. San Jose, USA: IEEE Press, 2012, 70(2): 141-146.
[23] DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters[J]. Journal of Cybernetics, 1974, 3(3): 32-57.
[24] SHENTAL N, BAR-HILLEL A, WEINSHALL D. Computing Gaussian Mixture Models with EM Using Side-Information[A]// Advances in Neural Information Processing Systems, International Conference on Machine Learning. MIT Press, 2003.
[25] KUSHARY D. The EM algorithm and extensions[J]. Biometrics, 20088, 15(1): 154-156.
[26] TOPCHY A P, LAW M H C, JAIN A K, et al. Analysis of consensus partition in cluster ensemble[C]//Proceeding of the 4th IEEE International Conference on Data Mining. Brighton, UK: ACM Press, 2004: 225-232.
[27] PUNERA K, GHOSH J. Consensus-based ensembles of soft clusterings[J]. Applied Artificial Intelligence, 2008, 22(7-8): 780-810.
[28] RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical Association, 1971, 66(336):846-850.

()
()

[1]	邱镇，王琪媛，刘迪，孟洪民. 一种基于可伸缩模式的潜在语义挖掘方法[J]. 中国科学技术大学学报, 2019, 49(7): 524-532.
[2]	陈锋，张智，李琴剑，陈宇强，陈国良. FCD大数据并行处理的动态任务调度算法[J]. 中国科学技术大学学报, 2018, 48(9): 718-722.
[3]	陈志注，王宏志，熊风，张义策，高宏，李建中. 大数据拍卖的定价策略与方法[J]. 中国科学技术大学学报, 2018, 48(6): 486-494.
[4]	徐华，李京. 面向带宽保障的云中虚拟集群调度算法[J]. 中国科学技术大学学报, 2018, 48(6): 495-503.
[5]	王佳玉，张振宇，褚征，吴晓红. 一种基于轨迹数据密度分区的分布式并行聚类方法[J]. 中国科学技术大学学报, 2018, 48(1): 47-56.
[6]	徐子伟，王鹏，陈宗海. 一种基于Fisher比率和预测风险准则的电信客户流失预测分步特征选择方法[J]. 中国科学技术大学学报, 2017, 47(8): 686-694.
[7]	陈振国，田立勤，林闯. 基于感知源信任评价的物联网数据可靠保障模型[J]. 中国科学技术大学学报, 2017, 47(4): 297-303.
[8]	卜尧，吴斌，陈玉峰，白德盟. BDAP——一个基于Spark的数据挖掘工具平台[J]. 中国科学技术大学学报, 2017, 47(4): 358-368.
[9]	王亚玲，刘越，洪建光，崔蔚，李彦虎，苏伊鹏，黄高攀，张明明，刘万涛. 基于Spark/Shark的电力用采大数据OLAP分析系统[J]. 中国科学技术大学学报, 2016, 46(1): 66-75.
[10]	黄冬梅，孙乐，赵丹枫. 基于ADMD融合策略的海洋大数据索引技术研究[J]. 中国科学技术大学学报, 2015, 45(10): 813-821.

一种新的软聚类投票法及其并行化实现

A novel voting method and parallel implementation for soft clustering

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价