Clustering ensemble algorithms based on improved genetic algorithm in cloud computing

doi:10.11772/j.issn.1001-9081.2017071749

Abstract

Abstract: Considering the problem that unsupervised clustering lacks priori information about data classification, the accuracy of base clustering is affected by clustering algorithm and general clustering ensemble algorithm has high space complexity, a Clustering Ensemble algorithm based on Improved Genetic Algorithm (CEIGA) was proposed. Focusing on the issue that traditional clustering ensemble algorithms can not meet the time requirement of large scale data processing, a Parallel Clustering Ensemble algorithm based on Improved Genetic Algorithm (PCEIGA) using Hadoop for cloud computing was also proposed. Firstly, the base clustering partitions produced by base clustering generation mechanism were encoded as the initial population of the improved Genetic Algorithm (GA) after changing cluster labels. Secondly, the diversity of base clustering was ensured by improving the selection operator of GA. According to the improved selection operator, crossover operation and mutation operation were adopted on chromosomes and the next generation population was gotten by elitist strategy to ensure the accuracy of base clustering. By this way, the final results of clustering ensemble reached global optimum and the accuracy of the algorithm was improved. To improve the efficiency of the proposed algorithms, two MapReduce processes were designed and one Combine process was added to reduce the communication among nodes. Finally, CEIGA, PCEIGA and four advanced clustering ensemble algorithms were compared on UCI data sets. The experimental results show that CEIGA performs better than other advanced clustering ensemble algorithms, and PCEIGA can significantly reduce running time and improve algorithm efficiency without decreasing the accuracy of clustering results.

Key words: cloud computing, Genetic Algorithm (GA), clustering ensemble, selection operator, parallel

摘要： 针对无监督聚类缺少数据分类等先验信息、基聚类的准确性受聚类算法影响以及一般聚类融合算法空间复杂度高的问题，提出一种基于改进遗传算法的聚类融合算法（CEIGA）；同时针对传统聚类融合算法已经不能满足大规模数据处理对于时间的要求的问题，提出一种云计算下使用Hadoop平台的基于改进遗传算法的并行聚类融合算法（PCEIGA）。首先，基聚类生成机制产生的基聚类划分在完成簇标签转化后进行基因编码作为遗传算法的初始种群。其次，通过改进遗传算法的选择算子，保证基聚类的多样性；再根据改进的选择算子对染色体进行交叉和变异操作并使用精英策略得到下一代种群，保证基聚类的准确性。如此循环，使聚类融合最终结果达到全局最优，提高算法准确度。通过设计两个MapReduce过程并加入Combine过程减少节点通信，提高算法运行效率。最后，在UCI数据集上比较了CEIGA、PCEIGA和四个先进的聚类融合算法。实验结果表明，与先进的聚类融合算法相比，CEIGA性能最好；而PCEIGA能在不影响聚类结果准确度的前提下明显降低算法运行时间，提高算法效率。

关键词: 云计算, 遗传算法, 聚类融合, 选择算子, 并行

CLC Number:

TP18
TP301.6

XU Zhanyang, ZHENG Kezhang. Clustering ensemble algorithms based on improved genetic algorithm in cloud computing[J]. Journal of Computer Applications, 2018, 38(2): 458-463.

徐占洋, 郑克长. 云计算下基于改进遗传算法的聚类融合算法[J]. 计算机应用, 2018, 38(2): 458-463.

References

[1] STREHL A, GHOSH J. Cluster ensembles:a knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2003, 3(3):583-617.
[2] TURING A M. Computing machinery and intelligence[J]. Mind, 1950, 59(236):433-460.
[3] WANG D X, LI L, YU Z W, et al. AP2CE:double affinity propagation based cluster ensemble[C]//Proceedings of the 2013 International Conference on Machine Learning and Cybernetics. Piscataway, NJ:IEEE, 2013:16-23.
[4] YU Z W, HAN G Q, LI L, et al. Adaptive noise immune cluster ensemble using affinity propagation[C]//ICDE 2016:Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Piscataway, NJ:IEEE, 2016:1454-1455.
[5] KAO L J, HUANG Y P. Ejecting outliers to enhance robustness of fuzzy cluster ensemble[C]//Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ:IEEE, 2013:3790-3795.
[6] IAM-ON N, BOONGOEN T, GARRETT S, et al. A link-based approach to the cluster ensemble problem[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2011, 33(12):2396-2409.
[7] ZHONG C M, YUE X D, ZHANG Z H, et al. A clustering ensemble:two-level-refined co-association matrix with path-based transformation[J]. Pattern Recognition, 2015, 48(8):2699-2709.
[8] WANG L, ZHANG G Y. Cluster ensemble based image segmentation algorithm[C]//ICICSE 2015:Proceedings of the 2015 Eighth International Conference on Internet Computing for Science and Engineering. Piscataway, NJ:IEEE, 2015:68-73.
[9] YU Z W, LUO P N, YOU J, et al. Incremental semi-supervised clustering ensemble for high dimensional data clustering[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(3):701-714.
[10] ZHANG S H, YANG L, XIE D Q. Unsupervised evaluation of cluster ensemble solutions[C]//ICACI 2015:Proceedings of the 2015 Seventh International Conference on Advanced Computational Intelligence. Piscataway, NJ:IEEE, 2015:101-106.
[11] BANERJEE B, BOVOLO F, BHATTACHARYA A, et al. A new self-training-based unsupervised satellite image classification technique using cluster ensemble strategy[J]. IEEE Geoscience & Remote Sensing Letters, 2015, 12(4):741-745.
[12] YU Z W, CHEN H T, YOU J, et al. Hybrid fuzzy cluster ensemble framework for tumor clustering from biomolecular data[J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics, 2013, 10(3):657-670.
[13] GOSWAMI J P, MAHANTA A K. A genetic algorithm based ensemble approach for categorical data clustering[C]//INDICON 2015:Proceedings of the 2015 Annual IEEE India Conference. Piscataway, NJ:IEEE, 2015:1-6.
[14] ALFRED R, CHIYE G J, OBIT J H, et al. A genetic algorithm based clustering ensemble approach to learning relational databases[J]. Advanced Science Letters, 2015, 21(10):3313-3317.
[15] 刘朋欢.基于生成模型的聚类融合算法[D].青岛:中国海洋大学,2014. (LIU P H. Generative approaches for ensemble clustering[D]. Qingdao:Ocean University of China, 2014.)
[16] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. Berkeley, CA:USENIX Association, 2008:10-10.
[17] 吴晓璇,倪志伟,倪丽萍.云计算环境下基于分形的聚类融合算法研究[J].计算机工程与应用,2015,51(14):1-6. (WU X X, NI Z W, NI L P. Research on fractal clustering ensemble algorithm based on cloud computing environment[J]. Computer Engineering and Applications, 2015, 51(14):1-6.)
[18] BENMOUNAH Z, BATOUCHE M. A parallel distributed system for gene expression profiling based on clustering ensemble and distributed optimization[C]//ICA3PP 2013:Proceedings of the 13th International Conference on Algorithms and Architectures for Parallel Processing, LNCS 8285. Cham:Springer, 2013:176-185.
[19] IAM-ON N, BOONGOEN T. Comparative study of matrix refinement approaches for ensemble clustering[J]. Machine Learning, 2015, 98(1/2):269-300.
[20] LI F J, QIAN Y H, WANG J T, et al. Multigranulation information fusion:a Dempster-Shafer evidence theory based clustering ensemble method[C]//Proceedings of the 2015 IEEE International Conference on Machine Learning and Cybernetics. Piscataway, NJ:IEEE, 2015:58-63.