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

• 新型互联网应用技术 • 上一篇    下一篇

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

唐海波1, 林煜明1, 李优2   

  1. 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-bo1, LIN Yu-ming1, LI You2   

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

摘要: 聚类是一种重要数据分析技术,在众多领域中得到广泛地应用.然而,由于数据分布的内在特点,传统的聚类算法并不能保证聚类结果具有平衡性,这与很多现实的需求不一致.本文提出了一种基于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

中图分类号: