基于知识诱导与无用中心驱动的K-means算法

K-means Algorithm Driven by Knowledge Induction and Useless Center

摘要

K-means 算法是一种广泛应用的高效无监督聚类算法。然而，研究表明，在处理高维或非球状结构的数据集时，K-means算法在确定聚类数目和选择初始质心方面存在显著局限性。为优化K-means算法的初始质心选取机制，解决聚类数目确定问题，文章提出了一种基于知识诱导与无用中心驱动的K-means算法。该算法首先引入高密度知识点的检测机制，通过识别数据集中的高密度知识点，构建候选质心集合，基于高斯混合模型理论推导最优聚类数；随后，采用无用中心筛选策略对候选质心进行优化选择，最终确定最优初始质心集合。在真实数据集上的实验结果表明，所提算法在聚类性能上总体优于其他对比算法。该算法可有效解决非球状数据分布的聚类问题，并在复杂数据结构场景下展现出较为优越的聚类性能。

Abstract

K-means is a widely used and efficient unsupervised clustering algorithm. However, studies have shown that when dealing with high-dimensional or non-spherically distributed datasets, the K-means algorithm has significant limitations in determining the number of clusters and selecting initial centroids. To thoroughly explore and optimize the initial centroid selection mechanism and the problem of determining the number of clusters in the K-means algorithm, a K-means algorithm based on knowledge induction and useless center driven is proposed. This algorithm first introduces a detection mechanism for high-density knowledge points, constructs a candidate centroid set by identifying high-density knowledge points in the dataset; then infers the optimal number of clusters based on Gaussian mixture model theory; subsequently adopts a useless center screening strategy to optimally select the candidate centroids, and finally determines the optimal initial centroid set. Experiments on real datasets show that the proposed optimized algorithm generally outperforms other comparison algorithms in clustering performance. This algorithm effectively solves the clustering problem of non-spherical data distribution and exhibits relatively superior clustering performance in scenarios with complex data structures.

关键词

无监督聚类 / K-means / 高密度知识点 / 高斯混合模型 / 无用中心

Key words

unsupervised clustering / K-means / high-density knowledge points / Gaussian mixture model / useless center

参考文献

[1] 王森, 邢帅杰, 刘琛 . 密度峰值聚类算法研究综述[J]. 华东交通大学学报, 2023, 40(1): 106-116.

[2] WANG S, XING S J, LIU C . Survey of density peak clustering algorithm[J]. Journal of East China Jiaotong University, 2023, 40(1): 106-116.

[3] 周晓东, 董海清, 张昆鹏, 等 . 基于几何的 K—means 初始聚类中心优化算法研究 [J]. 仪表技术, 2025(2): 66-69.

[4] ZHOU X D, DONG H Q, ZHANG K P, et al. Research on optimization algorithm for initial clustering centers of K—means based on geometry [J]. Instrumentation Technology, 2025(2): 66-69.

[5] 姚苏梅, 陆泉 . 数据与知识协同驱动的知识发现: 概念、机理与模型[J]. 情报学报, 2025, 44(3): 282-295.

[6] YAO S M, LU Q . Knowledge—discovery method driven by the collaboration of data and knowledge: concept, mechanism, and model[J]. Journal of the China Society for Scientific and Technical Information, 2025, 44(3): 282-295.

[7] HARTIGAN J A, WONG M A . Algorithm AS 136: a K—means clustering algorithm [J]. Applied Statistics, 1979, 28(1): 100.

[8] SELIM S Z, ISMAIL M A . K—means—type algorithms: a generalized convergence theorem and characterization of local optimality [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6(1): 81-87.

[9] COMANICIU D, MEER P . Mean shift: a robust approach toward feature space analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619.

[10] CHINRUNGRUENG C, SEQUIN C H . Optimal adaptive K—means algorithm with dynamic adjustment of learning rate [J]. IEEE Transactions on Neural Networks, 1995, 6(1): 157-169.

[11] IKOTUN A M, EZUGWU A E, ABUALIGAH L, et al. K—means clustering algorithms: a comprehensive review, variants analysis, and advances in the era of big data [J]. Information Sciences, 2023, 622: 178-210.

[12] 孙林, 刘梦含, 薛占熬 . 结合人工蜂群与 K—means聚类的特征选择 [J]. 计算机科学与探索, 2024, 18(1): 93-110.

[13] SUN L, LIU M H, XUE Z A . Feature selection combining artificial bee colony with K—means clustering [J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(1): 93-110.

[14] TANG Y M, PAN Z F, HU X H, et al. Knowledge—induced multiple kernel fuzzy clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(12): 14838-14855.

[15] 原泽菲, 张正军, 姜国林 . 基于相对邻近度的自适应谱聚类算法[J]. 计算机科学, 2025, 52(10): 79-89.

[16] YUAN Z F, ZHANG Z J, JIANG G L . Adaptive spectral clustering algorithm based on relative proximity[J]. Computer Science, 2025, 52(10): 79-89.

[17] 张清华, 周靖鹏, 代永杨, 等 . 基于代表点与 K近邻的密度峰值聚类算法 [J]. 软件学报, 2023, 34(12): 5629-5648.

[18] ZHANG Q H, ZHOU J P, DAI Y Y, et al. Density peaks clustering algorithm based on representative points and K—nearest neighbors [J]. Journal of Software, 2023, 34(12): 5629-5648.

[19] SARMADI H, ENTEZAMI A, MAGALHÃES F . Unsupervised data normalization for continuous dynamic monitoring by an innovative hybrid feature weighting—selection algorithm and natural nearest neighbor searching[J]. Structural Health Monitoring, 2023, 22(6): 4005-4026.

[20] 何选森, 何帆, 徐丽, 等 . K—means 算法最优聚类数量的确定 [J]. 电子科技大学学报, 2022, 51(6): 904-912.

[21] HE X S, HE F, XU L, et al. Determination of the optimal number of clusters in K—means algorithm [J]. Journal of University of Electronic Science and Technology of China, 2022, 51(6): 904-912.

[22] PATEL E, KUSHWAHA D S . Clustering cloud workloads: K—means vs Gaussian mixture model [J]. Procedia Computer Science, 2020, 171: 158-167.

[23] AHMED M, SERAJ R, ISLAM S M S . The K—means algorithm: a comprehensive survey and performance evaluation [J]. Electronics, 2020, 9(8): 1295.

[24] 周晨曦, 梁循, 齐金山 . 基于约束动态更新的半监督层次聚类算法[J]. 自动化学报, 2015, 41(7): 1253-1263.

[25] ZHOU C X, LIANG X, QI J S . A semi—supervised agglomerative hierarchical clustering method based on dynamically updating constraints[J]. Acta Automatica Sinica, 2015, 41(7): 1253-1263.

基金资助

国家自然科学基金项目(12361004)