结合密度参数与中心替换的改进K-means算法及新聚类有效性指标研究  

Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index

作　　者：张亚迪 孙悦 刘锋[1] 朱二周[1] ZHANG Ya-di;SUN Yue;LIU Feng;ZHU Er-zhou(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

机构地区：[1]安徽大学计算机科学与技术学院,合肥230601

出　　处：《计算机科学》2022年第1期121-132,共12页Computer Science

基　　金：安徽省自然科学基金(面上项目)(2008085MF188)。

摘　　要：聚类是一种经典的数据挖掘技术,它在模式识别、机器学习、人工智能等多个领域得到了广泛的应用。通过聚类分析,目标数据集的深层次结构可以被有效地发掘出来。作为一种常用的划分聚类算法,K-means具有实现简单、能够处理大型数据等优点。然而,受收敛规则的影响,K-means算法仍然存在着对初始类簇中心的选取非常敏感、不能很好地处理非凸型分布和有离群值的数据集等问题。文中提出了一种基于密度参数和中心替换的改进K-means算法DC-Kmeans。该算法采用数据对象的密度参数来逐步确定初始类簇中心,使用中心替换方法更新偏离实际位置的初始中心,因而比传统聚的类算法更加精确。为了获得最佳聚类效果,文中同时提出了一个能够对聚类结果进行有效评价的新聚类有效性指标SCVI和一个能够快速获得目标数据集最佳类簇数的新算法OCNS。实验结果表明,所提聚类方法对各种类型的数据集都是有效的。As a classical data mining technique,clustering is widely used in fields as pattern recognition,machine learning,artificial intelligence,and so on.By effective clustering analysis,the underlying structures of datasets can be identified.As a commonly used partitional clustering algorithm,K-means is simple of implementation and efficient on classifying large scale datasets.However,due to the influence of the convergence rule,the traditional K-means is still suffering problems as sensitive to the initial clustering centers,cannot properly process non-convex distributed datasets and datasets with outliers.This paper proposes the DC-Kmeans(density parameter and center replacement K-means),an improved K-means algorithm based on the density parameter and center replacement.Due to the gradually selecting of initial clustering centers and continuously update imprecision old centers,the DC-Kmeans is more accurate than the traditional K-means.Two novel methods are also proposed for optimally clustering:1)a novel clustering validity index (CVI),SCVI(Sum of the inner-cluster compactness and the inter-cluster separateness based CVI),is proposed to evaluate the results of the DC-Kmeans;2)a new algorithm,OCNS(optimal clustering number determination based on SCVI),is designed to determine the optimal clustering numbers for different datasets.Experimental results demonstrate that the proposed clustering method is effective for many kinds of datasets.

关 键 词：聚类算法 聚类有效性指标 最佳类簇数 类簇中心 数据挖掘 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]