一种基于密度和距离的K-means聚类算法

罗军锋　洪丹丹

摘  要：针对K-means算法中对初始聚类中心和孤立点敏感的缺点，我们通过从密度和距离两个方面的改进，提出新的改进K-means算法。该算法引入特征权重，从近邻密度出发，去除孤立点对算法的影响，同时确定初始聚类中心，在距离计算过程中，引入集成簇内与簇间距离的计算方法，以提升聚类的效果。实验结果表明，该算法比传统聚类算法能够提升10%以上的聚类效果。

关键词：聚类;K-means;特征加权;近邻密度;孤立点

中图分类号：TP311     文献标识码：A

A K-means Clustering Algorithm based on Density and Distance

LUO Junfeng， HONG Dandan

（Network Information Center， Xi'an Jiaotong University， Xi'an 710049， China）

luojf@xjtu.edu.cn; ddhong@xjtu.edu.cn

Abstract： In order to improve the sensitivity of initial clustering centers and outliers of K-means algorithm， an improved K-means algorithm is proposed based on density and distance. In this algorithm， feature weight is introduced to remove the influence of outliers on the algorithm from the neighborhood density. At the same time， the initial clustering center is determined. In the process of distance calculation， the distance calculation method within and between clusters is introduced to improve the clustering effect. The experimental results show that this algorithm improves the clustering effect by more than 10%， compared with the traditional clustering algorithm.

Keywords： clustering; K-means; feature weighting; neighbor density; isolated points

1   引言（Introduction）

K-means[1]算法是數据挖掘算法中一种流行的、简单的、实用的聚类算法，其特点就是思想原理简单、聚类效果较佳。当然，作为算法，传统的K-means聚类算法存在着诸如初始聚类中心随机选择、K值需要事先确定、容易陷入局部最优、对孤立点特别敏感等等缺点或者不足。

长期以来针对这些缺点或不足，许多科研人员提出了不同的改进方法和策略，形成了较完善的聚类策略。文献[2]用在初始聚类中心的选择中，通过引入神经网络算法改进算法，得到了很好的聚类效果;文献[3]则引入了比较新颖的蚁群算法，将蚁群算法的核心思想和K-means算法的核心思想进行融合，同样也达到改进聚类结果质量这一目标。文献[4]首先对聚类对象进行抽样，利用抽样后的数据样本的分布来确定初始聚类中心。文献[5]提出一种基于平均密度优化初始聚类中心的算法。文献[6]中提出的通过使用近似加权核函数优化目标函数。针对孤立点的处理一般都是利用聚类数据点与聚类核心的距离超过目标函数的阈值从而定义为孤立点，文献[7]则通过距离公式的不同定义来将孤立点数据剔除。文献[8]则通过集成簇内与簇间距离的加权算法来改进算法的距离计算公式，以提升聚类的效果。

本文借鉴文献[8]的距离计算方法，提出了一种基于密度和距离的K-means优化算法，该算法首先计算数据对象的局部密度，以此为算法的出发点，首先去除孤立点以减少孤立点对算法结果的影响，再按照距离最远的原则来确定初始聚类中心，随后引入集成簇内与簇间距离的距离计算方法进行聚类，着力提升K-means算法的性能，取得了不错的聚类效果。

2  传统K-means算法（Traditional K-means algorithm）

传统K-means算法的基本思想是：首先从数据对象集D中随机选择k个对象作为初始聚类中心;接着计算每个对象到这些初始聚类中心的距离，并根据最小距离原则进行划分，划给聚类最近的簇;然后重新计算每个聚类簇的均值，直到计算收敛函数，满足函数收敛的要求，算法就终止，否则，重复上述过程。

传统算法中由于初始聚类中心是随机任意选取的，根据选取的初始聚类中心的不同，容易陷入局部最优，最为重要的是孤立点的存在，对平均值会产生很大的影响。本文因此为出发点，先着手解决如何选取初始聚类中心，消除鼓励点，然后才根据新的距离公式进行聚类。

3  基于密度和距离的K-means算法（K-means algorithm based on density and distance）

针对传统K-means的缺点，本算法改进包括：首先，引入近邻密度，目的有两个：其一，剔除聚类过程中的初始孤立点，因为孤立点对聚类的结果影响很大;其二，是用近邻密度选择高密度对象，并从中选择初始聚类中心，以解决传统K-means算法初始聚类中心选择随机造成的问题。然后利用文献[8]的聚类方法和思想进行聚类，这样处理的原因就是大大减轻了孤立点对聚类结果的影响，由于初始聚类中心不是随机形成的，大大提升了文献[8]算法的效率和效果。下面从算法的基本概念、思想、步骤等分别加以描述。

3.1   近邻密度的概念

定义1  k距离

在数据集D中，数据对象o距离数据对象p之间的距离，我们记为：d（p，o）。对于任意一个正整数k，我们将数据对象p 的k距离记作k-dist（p）。

当以下两个条件同时满足时，我们认为k-dist（p）=d（p，o）：

（1）至多存在k-1个数据对象满足：      。

（2）至少存在k个数据对象满足：;

定义2  k近邻邻居

首先，根据定义1中得到数据对象p的k距离，那么对象p的k近邻邻居为这样一个集合，其中满足：数据集中所有数据对象到p的距离小于等于k的数据对象。具体记为：。

定义3 近邻距离

不失一般性，d（p，o）表示数据对象d和数据对象o之间的距离，那么对象p关于对象o的近邻距离为数据对象p的k距离与数据对象o之间距离的最大值，表示为：

定义4 近邻密度

给定任意数据集合D，数据对象p的近邻密度定义为：

在定义4中，首先计算数据集中所考察对象p的k近邻所有邻居对象到对象p的近邻距离之和。如果数据对象近邻密度取值小，就说明它的k近邻邻居所涵盖的范围就非常小，这个区域就是个高密度区域。

3.2   算法目标函数

设为一个包含n个数据对象的数据集合，其中第i个数据对象表示为，m为数据对象属性的数目。由D生成的k近邻密度矩阵为

，依据公式（1）进行计算。数据对象分配矩阵U是的0-1矩阵，=1表示第i个属性被分到第P个簇。为k个簇中心向量，其中为第p个簇中心。为k个权重向量，其中代表第p个簇的特征权重，为第p个簇中第j个特征的权重。通过结合簇间距离与簇内距离的信息，本算法目标函数为：

其中：

文献[8]已经证明了如何计算，，，这里就不在多做叙述。

3.3   算法步骤与描述

针对文献[8]改进后的新算法分三大步骤：

首先，根据预先设定的特定权重W来计算各个对象的k近邻密度矩阵;预先设定一个阈值，这个值的设定关系到聚类的效果，其主要目的是用来剔除孤立点，然后将剩余的所有数据对象重新组合成新的数据对象，重新对新的数据对象集进行聚类，构造新的k近邻密度矩阵和特征权重W。

然后，对构造出来的进行从小到大的排序，将排在前列的2k个数据对象选择出来，将作为初始的聚类中心候选集。在这个候选集中首选选取前两个数据对象作为初始聚类中心，在候选集中剩余的数据对象中选取距离这两个初始聚类中心最远的一个数据对象加入初始聚类中心集中，以此类推，直到最终k个数据中心Z形成。

最后，根据文献[8]中的算法进行聚类。

算法详细描述如下：

输入：d维数据集D、预先设定的特征权重W、k近邻离群阈值

输出：满足准则函数最小的k个族类

（1）用设定的特征权重W和距离公式来计算各个数据对象之间的加权距离，得到各数据对象的K-dist近邻矩阵，并一并形成构造K-dist近邻邻居矩阵和近邻密度NND矩阵。

（2）根据近邻密度矩阵，判断所有对象的NND是否大于离群阈值，如果是大于，则将该数据对象作为孤立点去除;如果不是，则保留该数据对象;同时选择NND最小的2k个对象作为准初始聚类中心集待用。

（3）在步骤2中形成的矩阵中选取最下的2k个数据对象作为候选初始聚类中心，然后首先从中选取距离最远的两个数据对象和，将其作为初始的2个聚类中心，同时在候选初始聚类中心集中删除这两个对象，依次类推，直到找到k个初始聚类中心。

（4）从上个步骤中得到的这k个初始聚类中心为聚类中心，利用文献[8]的算法KICIC循环反复，直到P（W，U，Z）收敛或U不再改变。

3.4   性能分析

根据上面的算法描述可以看出，改进后的聚类算法（简称NKICIC）的时间复杂度与传统K-means聚类算法的区别主要体现在形成初始聚类中心的时候，本算法在形成初始聚类中心的时间复杂度为：

由于算法在计算每一个数据对象的距离矩阵后也会将其自身的距离矩阵保存起来以方便后续使用。这里，通过以空间换时间，算法的时间复杂度会大大降低，当然，其空间开销也会很巨大，经过测算，增加的空间规模为的空间开销。实验表面，这种方法至少提高10倍以上的时间效率。

4   实验及结果分析（Experiments and results analysis）

为了便于和文献[8]的算法KICIC进行对比，我们同样从网站上下载了六个数据集，算法所用的几个参数采用了文献[8]的结果，以同样的评价指标主要分析了传统K-means、KICIC算法与改进后的NKICIC算法。

实验结果：根据表1的结果分析，NKICIC总体上优于原KICIC算法，远优于传统K-means算法。主要原因是由于原算法KICIC中没有消除孤立点，加上对初始聚类中心的敏感原因导致聚类结果不稳定。

根据表1中的数据可以得出，从各项指标来看，改进后的K-means算法的综合聚类效果提高了不少。

算法的时间性能方面，实验结果如图1所示。

从图1中可以看到，改进后的算法虽然增加了三个矩阵的计算时间消耗，但由于三个矩阵为后期删除了孤立点、确定了初始聚类中心，大大减少了后期聚类算法的收敛时间，两者抵消，所以总的时间消耗没有增加太多。

5   結论（Conclusion）

本文在传统距离公式中加入特征属性的权重，并据此计算每个数据对象的近邻矩阵，通过定义一定的距离阈值来减轻数据孤立点对聚类算法执行结果的影响，同时有针对行的选择形成初始聚类中心，随后根据集成族内与族间的距离来进行聚类。实验结果显示，新的聚类算法在性能基本没有损耗的情况下提升了原算法的准确度和聚类效果。

参考文献（References）

[1] James MacQueen. Some methods for classification and analysis of multivariate observations[C]. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability， University of California Press， 1967： 281-297.

[2] Wang Huai-bin， Yang Hong-liang， Xu Zhi-jian. A clustering algorithm use SOM and K-Means in Intrusion Detection[C]. 2010 International Conference on E-Business and E-Government， Guangzhou， 2010： 1281-1284.

[3] 莫锦萍，陈琴，马琳，等.一种新的K-Means蚁群聚类算法[J].广西科学院学报，2008，24（4）：284-286.

[4] 曹志宇，张忠林，李元韬.快速查找初始聚类中心的k-means算法[J].兰州交通大学学报，2009，28（6）：15-18.

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

[6] Jia H，Ding S，Du M，et al.Approximate normalized cuts without eigen-decomposition[J].Information Sciences，2016（374）：135-150.

[7] 张建民.一种改进的K-means聚类算法[J].微计算机信息，2010（9）：233-234.

[8] 黄晓辉，王成，熊李艳，等.一种集成簇内和簇间距离的加权k-means聚类方法[J].计算机学报，2019，59（42）：1-15.

作者简介：

罗军锋（1976-），男，硕士，高级工程师.研究领域：数据挖掘，区块链.

洪丹丹（1981-），女，硕士，高级工程师.研究领域：主數据工程，高校信息化.