一种基于信息熵和密度的K-means算法的改进

谷玉荣

摘要：影响K-means聚类算法的因素主要有聚类个数、初始聚类中心、异常点、相似性度量和聚类评价准则五个方面。本文通过利用信息熵确定属性的权重，从而对欧氏距离进行加权处理，将孤立点从数据集中取出，从而更好得选出聚类中心，然后利用加权欧氏距离公式对数据集进行相应的聚类。实验结果表明，基于信息熵和密度的K-means聚类算法聚类结果更精确。

关键词：信息熵;加权欧氏距离;基于信息熵和密度的K-means聚类算法

中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2018）12-0107-03

0 引言

K-means聚类算法是在1967年由J.B.Mac Queen提出的一种基于欧氏距离和误差平方和函数SSE（Sum of the Squared Error）的划分聚类算法。它的主要目的是通过选取聚类中心和聚类个数，利用欧氏距离公式将剩余数据划分到距离最近的聚类中心的簇中。这个聚类划分的过程需要反复迭代，直到新选出的聚类中心与上一次的差距不大为止。其算法的具体过程如图1所示。

K-means聚类算法尽管具备计算复杂度简单、可扩展性好、收敛速度快和效率高四大优点，但也有缺点。它的缺点主要包括：（1）由于聚类数目是人为决定的且聚类中心是随机选择，因此不同的聚类中心和聚类数目会导致不同聚类结果（2）数据集中会出现所谓的“噪声”和孤立点数据，而这些数据在聚类的过程中会对聚类中心产生影响，从而形成局部最优解。（3）当数据集中的数据属性维度较大时，不仅会产生冗余信息从而使得算法运行的时间较长，而且利用的欧氏距离公式对待每一个属性的重要性是一致的，导致聚类中心选择有问题，聚类精度不精确。

针对K-means聚类算法现存的缺点，大多数研究者采用密度优化的方法对聚类中心进行适当选取。文献[1]中采用了密度指针函数选取了初始化聚类中心;文献[2]中采用最优划分方法对数据集进行划分，从而了解数据点的分布情况，依据数据点的分布情况进行初始聚类中心的选取;文献[3]中利用距离、平均距离、密度参数、平均密度四个参数对每个数据的密度值进行相应的排序，并从中将密度值大的数据点选为聚类中心;文献[4]中通过研究数据集的分布特征，在数据高密度分布的区域，取出距离最远的一些点为聚类中心;文献[5]中通过了解数据的分布情况，从高密度的数据分布中选取第一个初始化聚类中心，剩下聚类中心利用最大最小距离原则进行选取;文献[6]中通过利用局部密度和高密距离参数，划分出孤立点，并对其余的数据点进行排序，选出合适的聚类中心，避免陷入局部最优解;文献[7]中利用平均密度计算公式、数据点的密度参数公式和孤立点排除公式将数据集中的孤立点划分出来，通过不断迭代的过程在大于平均密度的密度参数集中选择合适的聚類中心，并对剩余数据进行划分后再对孤立点进行聚类，很好地避免孤立点对聚类中心选择的影响，且提高了聚类精度和反应时间。

由此可以看出，虽然大部分的利用密度进行聚类优化的方式对数据整体的分布情况反映良好，且在对数据进行聚类时可不受“噪声”和孤立点数据的影响，导致选取的聚类中心更为合适，但在利用距离公式进行数据划分时，认为每一个属性的重要程度都是一样的，造成聚类结果不精确，而且算法过程较为复杂，算法运行的时间较长。

1 相关基本理论

对于具有m个属性值的n个数据值的数据集S={x1，x2，....xn}来说：

（1）任意两个数据点之间的距离：

（1）

其中，指n个数值中第i个数据的第p个属性值。

（2）所有数据点之间的平均距离：

（2）

其中，是从n个数据中任取两个数据点的个数之和。

（3）任意一个点的密度参数：

（3）

即以数据集S中任一点为圆心，平均距离Mean Dist（S） 为半径，圆内数据的个数即为的密度参数。其中，当时，;当时，。

（4）所有数据点密度的平均值：

（4）

（5）孤立点的确定：

（5）

（6）信息熵：

（6）

其中，为出现的概率。

2 基于信息熵和密度的K-means聚类算法的改进

在利用算法解决实际问题的过程中，会遇到数据的属性值种类多且重要性不一致的问题，而基于密度的K-means聚类算法并不能很好处理这种缺点，因此，需将“信息熵”的概念引入到基于密度改进的K-means聚类算法中，从而客观的确定属性的权重，对欧式距离公式进行相应的加权处理，用来确定合适的聚类中心且对数据集进行聚类。

2.1 运用信息熵确定属性权重[8]

（1）利用公式（7）计算j维属性对应的第i个数据点出现的概率。

（7）

（2）利用公式（6）计算j维属性的信息熵。

（3）利用公式（8）计算j维属性的差异性系数。

（8）

其中，越小，越大，属性越重要。

（4）利用公式（9）计算出j维属性的权重。

（9）

从而得到加权的欧式距离公式为：

（10）

2.2 基于密度的K-means聚类算法的改进

本文通过利用信息熵对欧氏距离公式进行相应的加权处理，对文献[7]中的基于密度的K-means聚类算法进行相应的改进，从而选取合适聚类中心并进行相应聚类。具体的实现过程如下：

（1）从包含有m个属性值的n个数据集合s中，利用公式（10）、（2）、（3）、（4）计算出所有数据点之间的距离、平均距离、密度及平均密度。

（2）利用公式（5）将数据集s划分成孤立点Q集合和剩余点P集合。

（3）将P集合按照公式（3）、（4），将大于平均密度的密度参数放入到集合U中。

（4）在集合U中找出最大的密度参数值和其个数N。

（5）if N=1，在集合P中找出密度参数值所对应的数据点即为聚类中心。利用公式（10）、（2）将与聚类中心的距离小于平均距离的数据点的密度参数从集合U中删除。

（6）else在集合P中找出密度参数值为的所有数据点，利用公式（11）计算出最小的，此时最小的所对应的数据点即为聚类中心。再利用公式（10）、（2）将与聚类中心的距离小于平均距离的数据点的密度参数从集合W中删除。

（11）

其中，。

（7）重復步骤（4）—（6），直到选出K个聚类中心。

（8）利用加权的欧式距离公式（10）计算出数据集P中的数据点与k个聚类中心的距离，根据“类内距离最小化”的原则将其聚类到不同的簇中。

（9）用公式（12）重新计算这k个聚类簇的聚类中心，并对数据集P进行重新划分，直到满足误差平方和公式（13）收敛为止。

（12）

其中，代表的是聚类中心，代表的是聚类的簇，代表的是聚类簇中的数据点的个数，。

（13）

其中，代表的是所有对象的均方差和。

（10）利用加权的欧式距离公式（10）计算出数据集Q中的数据点与k个聚类中心的距离，根据“类内距离最小化”的原则将其聚类到不同的簇中。因此，这种基于信息熵和密度的改进K-means聚类算法的流程图如下图2所示。

3 实验结果及分析

本文通过选取UCI上的Iris数据集为例子，利用基于信息熵和密度的改进的K-means聚类算法进行聚类分析并和文献[7]中基于密度的K-means聚类算法进行相应的比较，聚成3种结果，对应的聚类结果如图3和图4所示。

通过两者算法的比较，可以得出基于密度的K-means聚类算法的聚类中心为第96，131，89数据，分别对应的密度参数值为119，79，119;基于信息熵和密度的改进的K-means聚类算法的聚类中心为第80，133，99数据，分别对应的密度参数值为97，93，81。两种算法的4种属性值所对应的聚类中心如下表1所示。通过图3和图4的对比，可以得出，利用加权的欧式距离公式进行聚类划分，使得权重大的属性值在聚类的过程中作用放大，权重小的属性值在聚类的过程中作用缩小，使得聚类的分界线明显，取得得聚类中心更合适，进一步提高了聚类的精度，更符合实际过程中的应用。

参考文献

[1]牛琨，张舒博，陈俊亮.融合网格密度的聚类中心初始化方案[J].北京邮电大学学报，2007（2）：6-10.

[2]崔斌，卢阳.基于不确定数据的查询处理综述[J].计算机应用，2008（11）：2729-2731+2744.

[3]韩凌波，王强，蒋正峰，等.一种改进的k-means 初始聚类中心选取算法[J].计算机工程与应用，2010（17）：150-152.

[4]孙士保，秦克云.改进的k-平均聚类算法研究[J].计算机工程，2007（13）：200-201+209.

[5]左进，陈泽茂.基于改进K 均值聚类的异常检测算法[J].计算机科学，2016（8）：258-261.

[6]刘闯，陈桂芬.基于密度最大值的K-means初始聚类中心点算法改进[J].数字技术与应用，2017（11）：118-119.

[7]邢长征，谷浩.基于平均密度优化初始聚类中心的K-means算法[J].计算机工程与应用，2014（20）：135-138.

[8]杨玉梅.基于信息熵改进的K-means动态聚类算法[J].重庆邮电大学学报（自然科学版），2016（2）：254-259.

An Improvement of K-means Algorithm Based on Information Entropy and Density

GU Yu-rong

（North Automatic Control Technology Institute， Taiyuan Shanxi 030006）

Abstract：The factors affecting the K-means clustering algorithm mainly include five aspects： cluster number， initial cluster center， outlier， similarity measure and cluster evaluation criteria. This paper uses the information entropy to determine the weight of the attribute， thus the Euclidean distance is weighted， and the isolated points are taken out from the data set， so that the cluster center is better selected. Then， the data set is clustered by the weighted Euclidean distance formula. The experimental results show that the K-means clustering algorithm based on information entropy and density is more accurate.

Key words：information entropy; weighted Euclidean distance; K-means clustering algorithm based on information entropy and density