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

doi:10.11772/j.issn.1001-9081.2018041338

计算机应用 ›› 2018, Vol. 38 ›› Issue (11): 3132-3138.DOI: 10.11772/j.issn.1001-9081.2018041338

• 第七届中国数据挖掘会议(CCDM 2018) • 上一篇下一篇

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

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

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

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

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).

摘要/Abstract

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

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

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

中图分类号:

TP391.4

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

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[2]	李旭娟, 皮建勇, 黄飞翔, 贾海朋. 基于自生成深度神经网络的4D航迹预测[J]. 计算机应用, 2021, 41(5): 1492-1499.
[3]	张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.
[4]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[5]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[6]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[7]	陈凯, 于彦伟, 赵金东, 宋鹏. 基于城市交通监控大数据的工作位置推理方法[J]. 计算机应用, 2021, 41(1): 177-184.
[8]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[9]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[10]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[11]	蔡豪, 袁正道. 云数据中心基于贪心模式的虚拟机选择算法[J]. 计算机应用, 2020, 40(6): 1707-1713.
[12]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[13]	杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.
[14]	徐周波, 杨健, 刘华东, 黄文文. 基于XGBoost与拓扑结构信息的蛋白质复合物识别算法[J]. 计算机应用, 2020, 40(5): 1510-1514.
[15]	陈曦, 梅广, 张金金, 许维胜. 融合知识图谱和协同过滤的学生成绩预测方法[J]. 计算机应用, 2020, 40(2): 595-601.