基于密度标准差优化初始聚类中心的k_means改进算法

黄灵 王云锋 陈光武

摘要： 传统k_means算法采用随机法选择初始聚类中心，易造成聚类结果陷入局部最优解和聚类精度低的问题，而且易受孤立点的影响。为了解决这一问题，提出了一种基于密度标准差优化初始聚类中心的改进算法。该算法先计算数据集样本的平均值和标准差，接着计算每个数据点的密度分布函数值，然后计算样本的平均密度和密度标准差，若小于密度标准差，则划分为孤立点；搜索密度分布函数值数组中的最大值，那么最大值对应的样本点即为初始聚类中心，并将以初始聚类中心为原点，以样本平均值为半径的圆内各点的密度函数值赋值为0，如此重复，直到找到k个初始聚类中心。该算法基于Python语言在PyCharm软件平台实现。实验结果表明，这种基于密度标准差优化初始聚类中心的算法消除了孤立点的影响，具有更高的准确率和更好的聚类结果。

关键词： k_means算法；密度标准差；初始聚类中心；Python

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2019）06-0147-05

1 引言

数据挖掘，又称为数据库知识发现，是从海量的、无规律的、有噪声的数据中，提取出潜在的、对人们有利用价值的信息和知识的过程[1]。数据挖掘是一门多学科交叉的学问，包括：机器学习、统计、数据库、人工智能、信息检索和可视化[2]。数据挖掘分析方法包括：分类，估计，预测，相关性分组或关联规则，聚類，复杂数据类型挖掘（Text，Web，图形图像，视频，音频等）。

聚类分析作为数据挖掘领域中常用的数据分析方法，它是数据之间的相似度作为评判事物类别的依据，将具有足够相似度的数据聚为一类，使得同一类簇内数据的相似度尽量大，不同类簇间的数据相似度尽量小[3]。通过聚类分析，可以发现全部数据对象属性的分布规律，明确数据的整体发展态势。聚类算法[3-4]可以分为：基于划分的方法，基于层次的方法，基于密度的方法，基于网格的方法，基于模型的方法。基于划分方法的聚类算法有k_means算法，k_medoids算法，clarans算法等[3-4]；基于层次的聚类算法有birch算法，cure算法，chameleon算法等[3-4]；基于密度的聚类算法有dbscan算法，optics算法[3-4]；基于网格的聚类算法有sting算法，clique算法，wave_cluster算法[3-4]。不同类型的聚类算法具有不同的应用条件，到目前为止，面对所有数据集，没有哪一种算法能一直保持其优点。为了解决这一问题，一些研究人员提出融合聚类的思想，融合不同的聚类算法，以便取长补短，达到更好的聚类效果。

聚类算法的研究主要集中在以下几个方面：

1）强可伸缩性[5]：强可伸缩性是指聚类算法面对任何规模的数据集都应具有良好的聚类效果。

2）可处理高维数据集[6]：在现实生活中，数据一般都是高维的，使一些常用的相似度评判标准失去意义，导致数据无法聚类。故聚类算法应该具有处理高维数据集的解决方案。

3）对参数依赖性小[7]：在很多聚类算法中，需要指定一些参数来初始化算法，但面对未知的数据集，无法确定参数值，不能得到良好的聚类效果。故应减少参数的设定，提高鲁棒性。

4）可过滤噪声[8]：在现实生活中，数据的质量是不高的，包含大量的孤立点，会严重影响聚类效果。故应过滤掉孤立点，保留有用数据，以便得到更好的聚类效果。

5）可处理任意形状的簇[9]：在现实生活的数据集中，同种类型的数据按照簇状分布，但是簇的形状不一定是规则的。聚类算法不应只能处理某一种形状的数据，应能处理任性形状的簇。

6）可在分布式环境中运行[10]：传统的聚类算法大多是处理集中式数据的，即要聚类的数据存储在同一计算机或同一地点，但是随着信息技术和网络技术的不断发展，大部分应用系统和数据是以分布式存在的。采用传统的聚类算法会消耗大量存储资源，降低聚类效果，故分布式聚类算法由此而生。 传统式聚类算法在分布式环境中运行目前聚类算法的主要研究方向。

k_means聚类算法是1967年由Macqueen提出的，是聚类分析中最常用的一种典型的聚类算法，也是一种应用最广泛的聚类算法[4]。其目标是根据数据某种相似性度量方法进行划分，使每个数据到所属类簇的中心的距离尽可能小，不同类簇间的距离尽可能大。由于该算法具有简单，快速，高效和良好的搜索能力，并且适用于大数据集的优点而被广泛应用。主要缺点有：1）必须给定聚类数目k值[11]，k值不同可能导致不同的聚类结果；2）初始聚类中心[12-13]的选择对聚类结果有很大的影响，易陷入局部最优解；3）只能处理数值型数据，且对噪声和孤立点[12]数据敏感；4）只对球状数据具有良好的聚类效果，不能发现其他形状的数据。

针对k_means算法存在的缺点，已经有许多研究人员提出了一系列的改进方法。有人提出一种改进k_means算法[11]，此算法可以自确定聚类数目和初始聚类中心，改善了聚类结果，但对噪声敏感，此外，该算法对分布较稀疏的数据集的聚类效果不理想。也有人提出了结合初始中心优化和特征加权的K-Means聚类算法[12]，此算法根据样本特征对聚类的贡献程度获得初始特征权重，构建一种加权距离度量，利用提出的初始聚类中心选择方法获得k个初始聚类中心，并结合初始特征权重进行初步聚类。此算法具有较高的聚类准确性，但需指定聚类数目k。有人提出了最小最大K-means聚类算法[13]，该算法通过大量的迭代工作来获取全局最优解。随着现代互联网技术的发展，海量数据以分布式形式存储，传统算法的应用出现障碍，分布式算法应运而生，称为k_means算法的新的研究方向。

目前k_means算法的研究主要集中在以下几个方面：

1）自确定聚类数目k；2）优化初始聚类中心；3）可过滤噪声；4）可处理任意形状的簇；5）可处理高维数据集；6）可在分布式环境中运行。

本文提出了一种基于密度标准差优化初始聚类中心的改进算法，此算法改变了初始聚类中心的选择对聚类结果的影响，大大减少了迭代次数，提高了聚类精度，同时也不再只对球状数据有良好的聚类效果，可发现多种形状的簇，且对噪声不敏感，可处理高维数据。本算法为提升k-means算法聚类结果提供了一种新的研究思路。在大数据和人工智能的时代，只有掌握数据处理的方法，才能在这个竞争激烈的社会下生存。同时此算法也为分布式的k-means算法提供了一種优化初始聚类中心的解决方法。

2 传统k-means算法

K-means算法的思想[14-15]是对给定的一个样本数据的数据集[X=X1，X2，...，Xn]，并且每个Xi是d维的向量（d维向量由样本数据的d个特征组成），在给定分类组数k（[k≤n]）值的条件下，将数据集X划分成k个子集[S=S1，S2，...，Sk]，每个子集代表一个类，这k组子集应满足以下条件：

传统K-means算法步骤如下：

1）从数据集X中随机选取k个数据对象作为初始聚类中心；

2）计算数据集中每个对象到k个聚类中心的距离，将数据划分到与聚类中心距离最短的类中；

3）根据聚类结果，重新计算k个簇的聚类中心，计算方法是取簇中所有元素各自维度的算数平均数；

4）将X中全部元素按照新的中心重新聚类；

5）重复4，直到每个簇的中心基本不再变化；

6）将结果输出。

3 基于密度标准差优化初始聚类中心的k_means改进算法

3.1 基本定义

待聚类的数集[X=X1，X2，...，Xn]，其中[Xi=xi1，xi2，...，xid]，是实数空间[X∈Rd]中的向量，并且d表示数据的属性数目（数据空间的维数）。

3.2 改进k_means算法

为了更准确的找到初始聚类中心，本文利用样本点的标准差作为探寻半径，依据样本点的密度函数值寻找初始聚类中心。本文依据孤立点条件将待聚类的数集X分成两部分，将满足孤立点条件的点放入集合G，其余点放入集合Q，Q对应的密度函数值放入集合D。本文提出计算密度标准差，将大于密度标准差的密度函数值放入集合M，将介于密度标准差和孤立点密度的密度函数值放入集合P。这样就降低了搜索范围，减少了搜索时间，避免了选取到孤立点。改进算法思想如下：

算法 基于密度标准差优化初始聚类中心的k_means算法

输入 待聚类的数集X={X1，X2，…，Xn}，其中xi ={xi1，xi2， …，xid}；k簇的数目

输出 k个初始聚类中心

步骤：

1）根据公式（1）（2）（3）计算数据对象之间的欧式距离，样本的平均距离和样本的标准差。

2）根据公式（4）（5）（6）计算样本点的密度函数值，平均密度和密度标准差。

3）根据公式（7）将满足孤立点条件的点放入集合G，其余点放入集合Q。

4）在Q中执行（2），样本点的密度函数值存入集合D，将大于密度标准差的密度函数值放入集合M。

5）找到M中密度函数最大值MAX在Q中对应的样本点xi即为初始聚类中心。

6）将以初始聚类中心为圆心，样本标准差为半径的圆内所有点的密度函数值赋为0。

7）重复（4）～（6）直到找到k个初始聚类中心。

3.3 孤立点的处理

本文将原始数据集分成两部分，将满足孤立点条件的点放入集合G，其余点放入集合Q；利用新提出的改进算法对集合Q进行聚类，得到各个类的初始聚类中心。孤立点不参与聚类，将归为一类显示。因为孤立点不参与聚类过程中的各种计算，所以不影响聚类中心的值，故本文新提出的改进算法对孤立点不敏感。

为了验证本文改进算法对孤立点不敏感，测试数据有70个数据点，其中孤立点5个，约占总数的7%，用传统k_means算法和本文改进的k_means算法进行测试，结果如下图1和图2所示。

图2中五个黑色三角形的数据点是孤立点，而在图1中可以看到五个点分别聚类到三个类中。图1和图2对比发现，有孤立点的聚类结果和无孤立点的聚类结果是不同的。

4 实验结果分析

本文将传统的k_means算法和基于密度标准差的k_means优化算法进行了实验对比，选择了专用于测试数据挖掘算法的UCI数据库[16]中的Iris数据集、Wine数据集和模拟实验数据集作为本文测试数据集。

本文算法采用Python语言实现，测试环境是：CPU：Intel（R）Core?i5-2520 CPU @2.50 GHz；内存： 4 GB；操作系统：Windows 10 64位；算法调试运行工具：PyCharm。

4.1 模拟实验数据和结果分析

实验使用的两个数据集如图3、图4所示，数据集使用随机数随机生成如表1所示。分别在两个数据集上运行传统k_means算法和改进k_means算法，传统k_means算法运行结果如图5、图6所示，改进k_means算法运行结果如图7、图8所示。

由此实验可见，改进k_means算法不仅具有传统k_means算法的优点，还改善了传统k_means算法对孤立点敏感，随机选择初始聚类中心易陷入局部最优解的缺点。改进后的k_means算法不再只对球状数据有较好的聚类效果，对密度不同的簇也有较好的聚类效果，可以大大改善数据量较大但稀疏的数据对象被分类到相邻的数据量小但密集的簇中的情况，提高了聚类精度。

4.2 UCI实验数据和结果分析

为了验证本文提出的改进k_means算法的性能，本文用UCI数据集进行了测试。UCI数据集的名称、属性个数、数据对象数如表4所示。

因为本文提出的改进k_means算法根据密度标准差得到初始聚类中心，所以初始聚类中心是确定的，如果数据集确定，那么得到的聚类结果也是确定的。故只需进行一次实验即可得到聚类结果。然而传统k_means算法随机生成初始聚类中心，故每次实验结果都是不确定的。本实验运行10次传统k_means算法和一次改进k_means算法进行聚类结果的对比。运行10次传统k_means算法的聚类结果如表5所示，可知，10次实验中聚类精度相同的情况下，迭代次数和运行时间还是不同的。由此可以看出，传统k_means算法是不稳定的，初始聚类中心的选择对聚类结果影响很大，尤其对迭代次数的影响是最大的。如果选择好初始聚类中心，是明显可以减少迭代次数的。

运行10次传统k_means算法的聚类结果和运行1次改进k_means算法的聚类结果对比如表6所示。通过表6可知，改进k_means算法提高了聚类精度，且运行1次即可达到传统k_means算法最好的聚类效果，改进算法的迭代次数小于传统算法的迭代次数的平均值，虽然改进算法比传统算法用时要多，但是改进算法运行1次即可达到最好的聚类效果。改进k_means算法用时较多的原因是寻找初始聚类中心时，对数据集进行了大量的运算，如求样本均值、样本标准差密度函数值、平均密度、密度标准差。

5 结束语

本文提出的基于密度标准差优化初始聚类中心的改进k_means算法更好的确定了初始聚类中心，避免了随机选取聚类中心，提高了聚类精度，减少了迭代次数，有效避免了传统k_means算法易陷入局部最优解的情况，减少了孤立点对初始聚类中心的影响。本文的目的是提供一种优化初始聚类中心的方法，为聚类算法添砖加瓦，以便得到更准确的聚类结果。本改进算法的缺点是：1）需指定k值。2）耗时较多，由于此改进算法需进行大量的计算，故花费的时间较多一些。3）随着需要聚类的数据量的不断增大，计算机的计算性能要更好。下一步要做的工作是寻找确定k值的方法，并改善数据存储的方式以降低时间的消耗。

参考文献：

[1] Han J and Kimber M.数据挖掘概念与技术[M]. 范明，孟小峰，等.译.北京：机械工业出版社，2001.

[2] Bing Liu著.余勇，薛贵荣等译.Web数据挖掘[M].2版.北京：清华大学出版社，2013.

[3] 李硕.聚类算法的研究与改进[D].北京：北京邮电大学，2017.

[4] 李荟娆. K-means聚类方法的改进及其应用[D].黑龙江哈尔滨：东北农业大学，2014.

[5] Chaudhuri D， Chaudhuri B. A novel multispeed nonhierarchical data clustering technique [J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics a Publication of the IEEE Systems Man & Cybernetics Society， 1997，27（5）：71-876.

[6] Faber V. Clustering and the continuous K-means algorithm[J].Los Alamos Science， 1994（22）：138-144.

[7] Dan P， Moore A. Accelerating Exact k-means Algorithms with Geometric Reasoning [A]. // ACM SIGKDD International Conference on Knowledge Discovery & Data Mining [C]， New York： ACM Press， 1999：277-281.

[8] Wu X， Yao C. Application of improved K-means clustering algorithm in transit data collection [A]. // International Conference on Biomedical Engineering and Informatics[C]， New York： IEEE， 2010：3028-3030.

[9] 王莉.數据挖掘中聚类方法的研究[D].天津：天津大学，2004.

[10] 毛锐.基于密度的分布式聚类算法的研究[D].吉林长春：吉林大学，2012.

[11] 贾瑞玉，李玉功. 类簇数目和初始中心点自确定的K_means算法[J]. 计算机工程与应用，2018，54（7） ：152-158.

[12] 王宏杰，师彦文. 结合初始中心优化和特征加权的K-Means聚类算法[J]. 计算机科学，2017，44（11） ：457-459.

[13] Zhu M， Wang W， Huang J. Improved initial cluster center selection in K-means clustering[J].Engineering Computations，2014，31（8）：1661一1667.

[14] Tzortzis G， Likas A. The Min Max K-means clustering algorithm [J].Pattern Recognition， 2014， 47 （7）： 2505-2516.

[15] Lai J Z C， Huang T J. Fast global k-means clustering using cluster membership and inequality [J].Pattern Recognition， 2010， 43（5）：1954-1963.

[16] Asuncion A，Newman D J.UCI machine learning repository [EB/OL]. [2018-3-23]. http：//archive.ics.uci.edu/ml/index.php

【通联编辑：唐一东】