一种基于K-Means的平衡约束聚类算法

doi:10.3969/j.issn.1000-5641.2018.05.014

华东师范大学学报(自然科学版) ›› 2018, Vol. 2018 ›› Issue (5): 164-171.doi: 10.3969/j.issn.1000-5641.2018.05.014

一种基于K-Means的平衡约束聚类算法

唐海波¹, 林煜明¹, 李优²

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

收稿日期:2018-07-04 出版日期:2018-09-25 发布日期:2018-09-26
通讯作者: 林煜明,男,副研究员,硕士生导师,研究方向为海量数据管理和观点挖掘.E-mail:ymlin@guet.edu.cn. E-mail:ymlin@guet.edu.cn
作者简介:唐海波,男,硕士研究生,研究方向为分布式数据管理.E-mail:jadensshai@foxmail.com.
基金资助:
国家自然科学基金（61562014，U1501252，U1711263）；广西高校中青年教师基础能力提升项目（2017KY0195）；广西自动检测技术与仪器重点实验室研究课题（YQ17111）

A K-Means based clustering algorithm with balanced constraints

TANG Hai-bo¹, LIN Yu-ming¹, LI You²

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

Received:2018-07-04 Online:2018-09-25 Published:2018-09-26

摘要/Abstract

摘要： 聚类是一种重要数据分析技术，在众多领域中得到广泛地应用.然而，由于数据分布的内在特点，传统的聚类算法并不能保证聚类结果具有平衡性，这与很多现实的需求不一致.本文提出了一种基于K-Means的平衡约束聚类算法，该算法对K-Means算法每次迭代中数据点的分配策略进行修改，达到对每个簇可包含的数据点数目上限进行约束的目的.同时，算法支持用户自定义簇可包含的数据点数目上限，满足不同的平衡约束聚类需求.另外，本算法参数少，只需设置目标簇数目及其可包含的数据点数目上限，时间复杂度低，具有简单、快速的特点.在6个UCI（University of CaliforniaIrvine）真实数据集上进行的实验结果表明，文中提出的平衡约束聚类算法相比其他平衡约束聚类算法具有更佳的聚类效果和时间性能.

关键词: 平衡约束, 聚类, 贪心算法, 数据管理

Abstract: Clustering is a type of core data processing technology, which has been applied widely in various applications. Traditional clustering algorithms, however, cannot guarantee the balance of clustering results, which is inconsistent with the needs of real-world applications. To address this problem, this paper proposes a K-Means based clustering algorithm with balanced constraints. The proposed clustering algorithm changes the data point assignment process, in each iteration, to achieve balanced data blocks. The maximum cluster size threshold can be customized to meet different division requirements. The algorithm is simple and efficient-only two parameters need to be specified:the number of clusters and the threshold for the maximum cluster size. A series of experiments carried on six real UCI (University of California Irvine) datasets show that the algorithm proposed in this paper has better clustering performance and efficiency compared to other balanced clustering algorithms.

Key words: balanced constraints, clustering, greedy algorithm, data management

中图分类号:

TP391.4

唐海波, 林煜明, 李优. 一种基于K-Means的平衡约束聚类算法[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 164-171.

TANG Hai-bo, LIN Yu-ming, LI You. A K-Means based clustering algorithm with balanced constraints[J]. Journal of East China Normal University(Natural Sc, 2018, 2018(5): 164-171.

参考文献

[1] AGGARWAL C C, REDDY C K. Data Clustering:Algorithms and Applications[M]. Raton:Chapman & Hall/CRC, 2013.
[2] VISWANATH P, PINKESH R. l-DBSCAN:A fast hybrid density based clustering method[C]//Proceedings of the 18th International Conference on Pattern Recognition. NJ:IEEE, 2006:912-915.
[3] PEIZHUANG W. Pattern recognition with fuzzy objective function algorithms (James C. Bezdek)[J]. SIAM Review, 1983, 25(3):442-442.
[4] MALINEN M I, FRÄNTI P. Balanced k-means for clustering[C]//Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Berlin:Springer, 2014:32-41.
[5] LIU H, HAN J, NIE F, et al. Balanced clustering with least square regression[C]//Proceedings of the 31th AAAI Conference on Artificial Intelligence. CA:AAAI, 2017:2231-2237.
[6] BRADLEY P S, BENNETT K P, DEMIRIZ A. Constrained k-means clustering[J]. Microsoft Research Redmond, 2000, 59(1):1-34.
[7] KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics, 2005, 52(1):7-21.
[8] WU B, ZHOU Y, YUAN P, et al. Semstore:A semantic-preserving distributed rdf triple store[C]//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. NY:ACM, 2014:509-518.
[9] BANERJEE A, GHOSH J. On scaling up balanced clustering algorithms[C]//Proceedings of the 2002 SIAM International Conference on Data Mining. PA:Society for Industrial and Applied Mathematics, 2002:333-349.
[10] BANERJEE A, GHOSH J. Frequency-sensitive competitive learning for scalable balanced clustering on highdimensional hyperspheres[J]. IEEE Transactions on Neural Networks, 2004, 15(3):702-719.
[11] NG A Y, JORDAN M I, WEISS Y. On spectral clustering:Analysis and an algorithm[C]//Proceedings of the neural information processing systems. Massachusetts:MIT Press, 2002:849-856.
[12] 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.
[13] STREHL A, CHOSH J. Knowledge reuse framework for combining multiple partitions[J]. Journal of Machine learning Research, 2002, 33(3):583-617.

[1]	彭曼, 邵一平, 裴蓓, 杨梦杰, 李根, 文婉若, 杨凯. 长三角一体化示范区生态系统服务供需格局演变及区域调控探讨[J]. 华东师范大学学报（自然科学版）, 2023, 2023(6): 145-157.
[2]	郑新俊, 田国良, 黄飞虎. 基于Data Fabric的多模数据管理方法[J]. 华东师范大学学报（自然科学版）, 2023, 2023(5): 164-181.
[3]	刘丹琪, 蔡鹏. 存算分离架构下Part元数据的单独管理策略[J]. 华东师范大学学报（自然科学版）, 2023, 2023(5): 40-50.
[4]	高歌, 胡卉芪. FeaDB: 基于内存的多版本在线特征存储[J]. 华东师范大学学报（自然科学版）, 2023, 2023(5): 65-76.
[5]	唐倩雯, 李清韵, 刘涛, 陈丹. 上海乡村植物景观中多年生草本应用现状分析[J]. 华东师范大学学报（自然科学版）, 2023, 2023(3): 53-63.
[6]	洪语晨, 郁毅明, 王晔, 董启文. 多源数据辅助材料研发的数据应用系统[J]. 华东师范大学学报（自然科学版）, 2022, 2022(5): 14-25.
[7]	黄冬晴, 俞黎阳, 陈珏, 魏同权. 面向移动边缘计算的联合计算卸载和资源分配策略研究[J]. 华东师范大学学报（自然科学版）, 2021, 2021(6): 88-99.
[8]	邓思佳, 佟兴, 唐海波, 张召, 金澈清. 面向区块链的数据管理中间件[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 60-73.
[9]	吴蕊, 张安勤, 田秀霞, 张挺. 基于改进K-means的电力数据异常检测算法[J]. 华东师范大学学报（自然科学版）, 2020, 2020(4): 79-87.
[10]	申航杰, 琚生根, 孙界平. 基于模糊聚类和支持向量回归的成绩预测[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 66-73,84.
[11]	马明海, 刘善文, 黄民生, 冷培恩. 上海市河道水环境与蚊幼孳生关系分析[J]. 华东师范大学学报(自然科学版), 2017, 2017(6): 156-163.
[12]	闫密巧, 过仲阳, 任浙豪. 基于聚类关联规则的公交扒窃犯罪时空分析[J]. 华东师范大学学报(自然科学版), 2017, (3): 145-152.
[13]	肖冰, 郭进伟, 钱卫宁. 可扩展数据管理系统中的网络请求服务机制[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 165-172.
[14]	周子闵, 周坚华. FCM聚类的软划分:以遥感图像城镇下垫面聚类为例[J]. 华东师范大学学报(自然科学版), 2016, 2016(4): 150-157.
[15]	陈杰, 孙霄龙, 莫玮. 空间绳牵引并联机器人多目标优化设计[J]. 华东师范大学学报(自然科学版), 2015, 2015(1): 142-150.

一种基于K-Means的平衡约束聚类算法

A K-Means based clustering algorithm with balanced constraints

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价