张晋逢 孙忠林

摘 要：Kmeans算法存在两个主要缺陷，导致聚类结果准确率较低。为改善聚类效果，提出一种DGK-Kmeans算法。该算法选用核密度估计处理数据，得到备选聚类中心，依据平均类间相似度动态增加初始聚类中心个数，直至平均类间相似度大于前次计算值时，选取平均类内相似度最小时对应的聚类中心为初始聚类中心，进行Kmeans聚类计算。采用UCI标准数据集进行实验，证明改进后的DGK-Kmeans算法在聚类准确率和稳定性方面有很大提高。

关键词：Kmeans算法;高斯核函数;动态聚类中心

DOI：10. 11907/rjdk. 182140

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）002-0042-03

Abstract：There are two main defects in the Kmeans algorithm which lead to lower accuracy of clustering results.In order to improve the clustering effect， a DGK-Kmeans algorithm is proposed.The algorithm uses the kernel density estimation to process the data to obtain the candidate cluster center， and dynamically increases the number of initial cluster centers according to the average inter-class similarity until the average inter-class similarity is greater than the previous calculated value， and the average intra-class similarity is selected. The cluster center corresponding to the minimum degree is Kmeans clustering calculation for the initial cluster center.The experiment uses the UCI standard data set to verify that the improved DGK-Kmeans algorithm and greatly improves the accuracy and stability of clustering.

Key Words：Kmeans clustering;Gaussian kernel function;dynamic clustering center

0 引言

Kmeans算法是一種适用于大规模数据集[1]的简单聚类算法，但算法迭代次数受初始聚类中心和实际聚类中心偏差的影响很大，所以选择合适的初始聚类中心是很有必要的[2]。Kmeans算法有两个主要缺点：一是需要人工输入聚类K值;二是随机选择K个初始中心[3]。

为提高Kmeans算法的性能，许多学者从不同方面对算法进行改进[4]。ALSABTI[5]选择利用K-D树结构对Kmeans算法进行改进。赖玉霞等[6]根据聚类对象分布密度，从K个处于高密度区域的点中选取相互距离值最远的样本点作为初始聚类中心。王玲等[7]提出一种基于密度敏感的相似度度量方法。程艳云等[8]提出通过定义的平均类间最大相似度指标值确定最佳K值，进而动态分配聚类中心的聚类算法。韩凌波等[9]提出按照密度大小选择K个聚类中心的算法。马帅等[10]选择根据密度和参考点提高聚类算法，基本满足聚类以适应数据集分布的特征。袁方等[11]提出一种基于样本距离相似度及通过合适的权值初始化聚类的方法，对特定的数据集选择合适权值进行聚类，达到了良好的效果。周涓等[12]提出基于距离大小的算法，初始聚类中心选择的是相互之间距离最远的K个样本点。周世兵等[13]从样本几何结构的角度定义样本聚类距离和样本聚类离差距离，设计一种新的聚类有效指标，从而提出一种自动确定最佳聚类数量的方法。刘凤芹等[14]提出一种基于最大距离实现K值自动生成的算法。翟东海等[15]提出基于最大距离选取初始簇中心的算法。

以上研究通过密度、权值及距离对算法进行改进，但都存在聚类精度不高、时间复杂度高等情况。因此本文提出一种基于高斯核密度、动态确定初始聚类中心的DGK-Kmeans算法（Gaussian Kernel Kmeans Algorithm）。通过实验证明，本文算法在UCI数据集中的聚类精度高于传统K-means算法，并且在误差平方和方面也有很大优势。

1 高斯核密度估计

核密度估计方法对于数据分布特征的研究从数据样本集合本身出发，不需要利用数据分布的先验知识或对数据样本服从何种分布作出任何假设[16]。核函数的作用是在高维空间对输入的空间进行特征映射后，直接在高维数据空间进行数据处理。核函数映射是非线性变换的，可确保映射出各种不同的高维特征空间[17]。

使用高斯核函数作为核平滑函数的密度估计，是一种用来估计概率密度函数的非参数方法，假定[x1，x2，？，xn]为独立分布[F]的[n]个数据点，数据点服从的分布密度函数为[f]，函数定义为：

本文采用高斯核函数为核平滑函数，公式为：

[h]的取值公式为：

2 DGK-Kmeans算法

由于Kmeans算法聚类数需事先确定，且初始聚类中心的选取具有随机性，因此本文提出基于高斯核密度的动态确定初始聚类中心的算法（DGK-Kmeans算法）。