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

来源：华东师范大学学报·哲学社会科学版杂志2018年第5期北京时间：

作者：唐海波, 林煜明, 李优

单位：唐海波,男,硕士研究生,研究方向为分布式数据管理.E-mail:jadensshai@foxmail.com.

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

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

基金资助：国家自然科学基金（61562014，U1501252，U1711263）；广西高校中青年教师基础能力提升项目（2017KY0195）；广西自动检测技术与仪器重点实验室研究课题（YQ17111）