An Improved K-Means Algorithm with Auto-Determined Clustering Number by Using Gravity

doi:10.7652/xjtuxb201410018

您当前的位置：

首页 >

文章列表页 >

An Improved K-Means Algorithm with Auto-Determined Clustering Number by Using Gravity

更新时间：2025-07-09

- An Improved K-Means Algorithm with Auto-Determined Clustering Number by Using Gravity
- Vol. 48, Issue 10, Pages: 115-119(2014)
- 作者机构：
  
  1. 西安电子科技大学计算机学院,西安,710071
  2. 西北师范大学计算机科学与工程学院,兰州,730070
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201410018
  CLC： TP301.6
- Online First：10 October 2014，
  
  Published：2014
- 稿件说明：
移动端阅览
An Improved K-Means Algorithm with Auto-Determined Clustering Number by Using Gravity[J]. 2014, 48(10): 115-119.
DOI：

An Improved K-Means Algorithm with Auto-Determined Clustering Number by Using Gravity[J]. 2014, 48(10): 115-119. DOI： 10.7652/xjtuxb201410018.

摘要

针对传统K均值算法需要提前指定聚类数目且易陷入局部最优的问题

提出了一种采用万有引力定律自动确定类数的K均值算法(Gravity K均值算法

GK均值算法)。所提算法利用正交设计方法在数据空间均匀投放若干探测器

探测器根据万有引力定律移动

当两个探测器的距离小于给定阈值时合并为一个

当探测器处于稳定状态时

探测器的个数就是聚类的数目。将得到的探测器作为K均值算法的初始中心点

有效地避免了K均值算法陷入局部最优。实验结果表明:相比传统K均值算法

本文提出的方法可以自动确定聚类数目

并给出较好的初始中心

算法的迭代次数至少减少了25%

聚类正确率平均提高了14%

DB(Davies and Bouldin)聚类评价指标平均降低了0.19。

Abstract

An improved K-means algorithm to auto-determine the clustering number by using gravity is proposed to solve the problems that one needs to specify the number of clusters in the traditional K-means algorithm and it is easy to fall into local optimum. The orthogonal design method is used to uniformly place several detectors into the data space

and then these detectors are moved according to the law of universal gravitation. When two detectors's distance less than the given threshold

they are merged. The number of detectors is just the number of the clusters when the algorithm converges. Then the resulting detectors are used as the initial center points to avoid the local optimum. Experimental results and comparisons with the traditional K-means algorithm show that the proposed method can automatically determine the number of clusters and gives the better initial centers

and that the iteration number of the algorithm is reduced by at least 25% and clustering accuracy is increased by an average of 14% and the performance evaluation DB(Davies and Bouldin)index is reduced by an average of 0.19.

关键词

Keywords

references

PENA J M, LOZANO J A, LARRANAGA P. An empirical comparison of four initialization methods for the K-means algorithm[J]. Pattern Recognition Letters, 1999, 20(10): 1027-1040.

MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]∥Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, USA: University of California Press, 1967: 281-297.

ESTIVILL C V, YANG Jianhua. Fast and robust general purpose clustering algorithms[J]. Data Mining and Knowledge Discovery, 2004, 8(2): 127-150.

SU Muchun, CHOU Chienhsing. A modified version of the K-means algorithm with a distance based on cluster symmetry[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(6): 674-680.

LIKAS A, VLASSIS M, VERBEEK J. The global K-means clustering algorithm[J]. Pattern Recognition, 2003, 36(2): 451-461.

D'URSO P, GIORDANI P. A robust fuzzy K-means clustering model for interval valued data[J]. Computational Statistics, 2006, 21(2): 251-269.

HUA Chunsheng, CHEN Qian, WU Haiyuan, et al. RK-means clustering: K-means with reliability[J]. IEICE Transactions on Information and Systems, 2008, E91-D(1): 96-104.

TIMMERMAN M E, CEULEMANS E, DE R, et al. Subspace K-means clustering[J]. Behavior Research Methods, 2013, 45(4): 1011-1023.

PELLEG D, MOORE A. X-means: extending K-means with efficient estimation of the number of clusters[C]∥Proceedings of the 17th International Conference on Machine Learning. New York, USA: ACM, 2000: 727-734.

HAMERLY G, ELKAN C. Learning the k in K-means[C]∥Proceedings of the 17th Annual Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT Press, 2003: 281-288.

KALOGERATOS A, LIKAS A. Dip-means: an incremental clustering method for estimating the number of clusters[C]∥Proceedings of the 6th Annual Conference on Neural Information Processing Systems. Cambridge, MA, USA: MIT Press, 2012: 2402-2410.

BAGIROV A M, UGON J, WEBB D. Fast modified global k-means algorithm for incremental cluster construction[J]. Pattern Recognition, 2011, 44(4): 866-876.

TZORTZIS G, LIKAS A. The minmax k-means clustering algorithm[J]. Pattern Recognition, 2014, 47(7): 2505-2516.

LEUNG Yiuwing, WANG Yuping. An orthogonal genetic algorithm with quantization for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2001, 5(1): 41-53.

DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227.

董哲,伊鹏.采用链路聚类的动态网络社团发现算法.2014,48(8):73-79.[doi:10.7652/xjtuxb201408013]

张永斌,陆寅,张艳宁.域名请求行为特征与构成特征相结合的域名变换检测.2013,47(8):54-60.[doi:10.7652/xjtuxb 201308010]

许亚美,卢朝阳,李静,等.手写维文字符分割中的多信息融合路径寻优方法.2013,47(8):68-73.[doi:10.7652/xjtuxb 201308012]

王学恩,韩德强,韩崇昭.采用不确定性度量的粗糙模糊C均值聚类参数获取方法.2013,47(6):55-60.[doi:10.7652/xjtuxb201306010]

夏虎,庄健,于德弘.面向高维特征故障数据的进化软子空间聚类算法.2013,47(5):115-120.[doi:10.7652/xjtuxb2013 05021]

华莉琴,许维,王拓,等.采用改进的尺度不变特征转换及多视角模型对车型识别.2013,47(4):92-99.[doi:10.7652/xjtuxb201304016]

李清华,康海燕,苑晓姣,等.个性化搜索中用户兴趣模型匿名化研究.2013,47(4):131-136.[doi:10.7652/xjtuxb2013 04022]

杨攀,桂小林,田丰,等.一种高效的用于话题检测的关键词元聚类方法.2012,46(10):24-28.[doi:10.7652/xjtuxb2012 10005]

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Energy Efficiency Optimization of the Cryogenic Air Separation Process for Electronic-Grade Ultra Pure Nitrogen

Study on the Thermodynamic Properties in the Anomalous Region of Supercritical Water

Numerical Simulation of Heat-Moisture Barrier Performance of a Horizontal Air Curtain in Cold Storage

Related Author

No data

Related Institution

No data

⁰