Balanced clustering based on simulated annealing and greedy strategy

doi:10.11772/j.issn.1001-9081.2018041338

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (11): 3132-3138.DOI: 10.11772/j.issn.1001-9081.2018041338

Previous Articles Next Articles

Balanced clustering based on simulated annealing and greedy strategy

TANG Haibo¹, LIN Yuming¹, LI You², CAI Guoyong¹

1. Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology), Guilin Gunangxi 541004, China;
2. Guangxi Key Laboratory of Automatic Testing and Instrument(Guilin University of Electronic Technology), Guilin Gunangxi 541004, China

Received:2018-04-29 Revised:2018-06-21 Online:2018-11-10 Published:2018-11-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61562014, 61763007, U1711263), the Natural Science Foundation of Guangxi (2015GXNSFAA139303), the Project of Guangxi Key Laboratory of Trusted Software, the Director Fund Project of Guangxi Key Laboratory of Automatic Testing and Instrument (YQ17111).

基于模拟退火与贪心策略的平衡聚类算法

唐海波¹, 林煜明¹, 李优², 蔡国永¹

1. 广西可信软件重点实验室(桂林电子科技大学), 广西桂林 541004;
2. 广西自动检测技术与仪器重点实验室(桂林电子科技大学), 广西桂林 541004

通讯作者: 林煜明
作者简介:唐海波(1993-),男,江苏淮安人,硕士研究生,主要研究方向:分布式数据管理;林煜明(1978-),男,广西合浦人,副研究员,博士,CCF会员,主要研究方向:观点挖掘、海量数据管理;李优(1980-),女,安徽亳州人,副教授,硕士,主要研究方向:文本挖掘;蔡国永(1971-),男,广西河池人,教授,博士,CCF高级会员,主要研究方向:社会媒体挖掘、机器学习、可信软件。
基金资助:
国家自然科学基金资助项目（61562014，61763007，U1711263）；广西自然科学基金资助项目（2015GXNSFAA139303）；广西可信软件重点实验室研究课题；广西自动检测技术与仪器重点实验室主任基金立项项目（YQ17111）。

Abstract

Abstract: Concerning the problem that clustering results are usually required to be balanced in practical applications, a Balanced Clustering algorithm based on Simulated annealing and Greedy strategy (BCSG) was proposed. The algorithm includes two steps:Simulated Annealing Clustering Initialization (SACI) and Balanced Clustering based on Greedy Strategy (BCGS) to improve clustering effectiveness with less time cost. First of all, K suitable data points of data set were located based on simulated annealing as the initial point of balanced clustering, and the nearest data points to each center point were added into the cluster where it belongs in stages greedily until the cluster size reach the upper limit. A series of experiments carried on six UCI real datasets and two public image datasets show that the balance degree can be increased by more than 50 percentage points compared with Fuzzy C-Means when the number of clusters is large, and the accuracy of clustering result is increased by 8 percentage points compared with Balanced K-Means and BCLS (Balanced Clustering with Least Square regression) which have good balanced clustering performance. Meanwhile, the time complexity of the BCSG is also lower, the running time is decreased by nearly 40 percentage points on large datasets compared with Balanced K-Means. BCSG has better clustering effectiveness with less time cost than other balanced clustering algorithms.

Key words: balanced clustering, greedy algorithm, simulated annealing, approximate algorithm, data mining

摘要： 针对现实应用通常要求聚类的结果相对平衡的问题，提出了一种基于模拟退火与贪心策略的平衡聚类算法（BCSG），该算法包括基于模拟退火的初始点选择算法（SACI）与基于贪心策略的平衡聚类算法（BCGS）2个步骤，以提高平衡聚类算法的聚类效果与时间性能。首先基于模拟退火在数据集中快速定位出K个合适的数据点作为平衡聚类初始点，然后每个中心点分阶段贪婪地将距离其最近的数据点加入簇中直至达到簇规模上限。在6个UCI真实数据集与2个公开图像数据集上进行的聚类对比实验结果表明：在簇数目较大时相比Fuzzy C-Means聚类结果平衡度最高提升了50%以上；聚类结果的准确率相比Balanced K-Means、BCLS两个表现较好的算法平均提高了8个百分点；算法时间复杂度也更低，在较大规模的数据集上运行时间比Balanced K-Means最高减少了近40%。实验结果表明BCSG具有更佳的聚类效果和时间性能。

关键词: 平衡聚类, 贪心算法, 模拟退火, 近似算法, 数据挖掘

CLC Number:

TP391.4

TANG Haibo, LIN Yuming, LI You, CAI Guoyong. Balanced clustering based on simulated annealing and greedy strategy[J]. Journal of Computer Applications, 2018, 38(11): 3132-3138.

唐海波, 林煜明, 李优, 蔡国永. 基于模拟退火与贪心策略的平衡聚类算法[J]. 计算机应用, 2018, 38(11): 3132-3138.

References

[1] RAJARAMAN A, ULLMAN J D. 大数据:互联网大规模数据挖掘与分布式处理[M]. 王斌,译. 北京:人民邮电出版社, 2012:176-191.(RAJARAMAN A, ULLMAN J D. Big Data:Internet Large-scale Data Mining and Distributed Processing[M]. WANG B, translated. Beijing:Posts & Telecom Press, 2012:176-191.)
[2] VISWANATH P, PINKESH R. l-DBSCAN:a fast hybrid density based clustering method[C]//Proceedings of the 18th International Conference on Pattern Recognition. Piscataway, NJ:IEEE, 2006:912-915.
[3] BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. Berlin:Springer Science & Business Media, 2013:80-86.
[4] NG A Y, JORDAN M I, WEISS Y. On spectral clustering:Analysis and an algorithm[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic. Cambridge, MA:MIT Press, 2002:849-856.
[5] 丁祥武, 郭涛, 王梅,等. 一种大规模分类数据聚类算法及其并行实现[J]. 计算机研究与发展, 2016, 53(5):1063-1071.(DING X W, GUO T, WANG M, et al. A clustering algorithm for large-scale categorical data and its parallel implementation[J]. Journal of Computer Research and Development, 2016, 53(5):1063-1071.)
[6] 姜火文, 曾国荪, 马海英. 面向表数据发布隐私保护的贪心聚类匿名方法[J]. 软件学报, 2017, 28(2):341-351.(JIANG H W, ZENG G S, MA H Y. Greedy clustering-anonymity method for privacy preservation of table data-publishing[J]. Journal of Software, 2017, 28(2):341-351.)
[7] SHIRKHORSHIDI A S, AGHABOZORGI S, WAH T Y, et al. Big data clustering:a review[C]//Proceedings of the 2014 International Conference on Computational Science and Its Applications. Berlin:Springer, 2014:707-720.
[8] ALTHOFF T, ULGES A, DENGEL A. Balanced clustering for content-based image browsing[J]. Series of the Gesellschaft fur Informatik, 2011(1):27-30.
[9] DU Z, LIU Y, QIAN D. An energy-efficient balanced clustering algorithm for wireless sensor networks[C]//Proceedings of the 2009 Wireless Communications, Networking and Mobile Computing. Piscataway, NJ:IEEE, 2009:1-4.
[10] ALOISE D, DESHPANDE A, HANSEN P, et al. NP-hardness of Euclidean sum-of-squares clustering[J]. Machine Learning, 2009, 75(2):245-248.
[11] MALINEN M I, FRÄNTI P. Balanced k-means for clustering[C]//Proceedings of the 2014 Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Berlin:Springer, 2014:32-41.
[12] LIU H, HAN J, NIE F, ET AL. Balanced clustering with least square regression[C]//Proceedings of the 31th AAAI Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2017:2231-2237.
[13] BRADLEY P S, BENNETT K P, DEMIRIZ A. Constrained k-means clustering[EB/OL].[2018-03-01]. http://machinelearning102.pbworks.com/f/ConstrainedKMeanstr-2000-65.pdf.
[14] KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics, 2005, 52(1):7-21.
[15] BANERJEE A, GHOSH J. On scaling up balanced clustering algorithms[C]//Proceedings of the 2002 SIAM International Conference on Data Mining. Columbus, Ohio:SIAM, 2002:333-349.
[16] HAJEK B. Cooling schedules for optimal annealing[J]. Mathematics of Operations Research, 1988, 13(2):311-329.
[17] CAI D, HE X, HAN J. Document clustering using locality preserving indexing[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(12):1624-1637.
[18] STREHL A, CHOSH J. Knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2002, 33(3):583-617.

Balanced clustering based on simulated annealing and greedy strategy

基于模拟退火与贪心策略的平衡聚类算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LIU Shize, QIN Yanjun, WANG Chenxing, SU Lin, KE Qixue, LUO Haiyong, SUN Yi, WANG Baohui. Traffic flow prediction algorithm based on deep residual long short-term memory network [J]. Journal of Computer Applications, 2021, 41(6): 1566-1572.
[2]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[3]	ZHANG Shuyao, LI Yonghua, FAN Jiajia. Bulk storage assignment algorithm in bulk port based on game theory [J]. Journal of Computer Applications, 2021, 41(3): 867-874.
[4]	FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582.
[5]	Yongpeng SHI, Junjie ZHANG, Yujie XIA, Ya GAO, Shangwei ZHANG. Computation offloading and resource allocation strategy in NOMA-based 5G ultra-dense network [J]. Journal of Computer Applications, 2021, 41(11): 3319-3324.
[6]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[7]	CHEN Kai, YU Yanwei, ZHAO Jindong, SONG Peng. Work location inference method with big data of urban traffic surveillance [J]. Journal of Computer Applications, 2021, 41(1): 177-184.
[8]	QI Xuanxuan, HUANG Jiajun, CAO Jian'an. Path planning for unmanned vehicle based on improved A^* algorithm [J]. Journal of Computer Applications, 2020, 40(7): 2021-2027.
[9]	ZENG Minghua, QUAN Ke. Improved hybrid cuckoo search-based quantum-behaved particle swarm optimization algorithm for bi-level programming [J]. Journal of Computer Applications, 2020, 40(7): 1908-1912.
[10]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[11]	CAI Hao, YUAN Zhengdao. Greedy algorithm optimization based virtual machine selection strategy in cloud data center [J]. Journal of Computer Applications, 2020, 40(6): 1707-1713.
[12]	YANG Yan, LIU Shengjian, ZHOU Yongquan. Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem [J]. Journal of Computer Applications, 2020, 40(5): 1291-1294.
[13]	DU Xusheng, YU Jiong, YE Lele, CHEN Jiaying. Outlier detection algorithm based on graph random walk [J]. Journal of Computer Applications, 2020, 40(5): 1322-1328.
[14]	XU Zhoubo, YANG Jian, LIU Huadong, HUANG Wenwen. Protein complex identification algorithm based on XGboost and topological structural information [J]. Journal of Computer Applications, 2020, 40(5): 1510-1514.
[15]	CHEN Xi, MEI Guang, ZHANG Jinjin, XU Weisheng. Student grade prediction method based on knowledge graph and collaborative filtering [J]. Journal of Computer Applications, 2020, 40(2): 595-601.