改进K—Means算法的探讨与分析

曹卫华+乔平安

摘要：随着人类社会的不断进步和发展，K-Means作为聚类中较常用的算法，得到广泛的应用。该文探讨了K-Means和Canopy算法的执行过程，针对K-Means及Canopy的优缺点，提出了改进的K-Means算法。算法中将Canopy作为K-Means的预处理，通过Canopy得到聚类中簇的个数、初始化的聚类中心，同时排除掉“噪声”以及孤立点带来的影响，将Canopy的结果用于K-Means，进一步增强聚类性能，减少计算量。另外，针对K-Means中使用的距离度量公式，提出了改进的余弦距离度量公式，使得簇内数据点间的距离减小，簇间数据点间的距离增大，提高聚类质量。

关键词：聚类；K-Means；Canopy；余弦；距离度量公式；改进

中图分类号：TP319 文献标识码：A 文章编号：1009-3044（2017）06-0200-02

1 概述

聚类分析作为一项重要的人类社会活动，广泛应用于市场研究、模式识别、数据分析和图像处理等诸多领域。在童年时期，我们通过不断改进潜意识聚类方案学习如何区分猫和狗，或动物和植物。通过自动化聚类，可以识别对象空间中的密集和稀疏区域，从而发现数据属性中的总体分布模式和有趣的相关性。在商业活动中，聚类分析可以帮助营销人员在其客户群中发现不同的群体，并基于购买模式来表征客户群。在生物学中，聚类分析可以将植物和动物区分开，将具有相似功能的基因进行分类，并获得对人群内在结构的了解。在未来的工作和生活中，聚类将继续发挥越来越举足轻重的作用，带给我们前所未有的帮助。

2 聚类算法介绍

聚类技術中存在着许多算法，但是难以提供一种清晰的方法分类各种聚类算法，因为这些分类都可能重叠，使得一个聚类方法属于许多类别中。然而，呈现不同聚类方法的相对分类组织却是有用的。一般来说，主要的聚类方法可以分类为分区方法、分层方法、基于密度的方法、基于网格的方法、基于模型的方法等，很多聚类算法的共同点是需要选择度量距离的方法，可以根据向量空间和建模数据的性质采用多种方法测量向量之间的距离。K-Means则是分区方法中较为常见的一种算法，其流程如图1所示。

K-Means算法的主要不足体现在：

1）该算法必须事先确定簇的个数k，即要求用户事先知道数据集中数据的一些特点。但很多时候用户对数据集是不了解的，并不知道数据集应该聚类成多少个簇才最合适。聚类结果对初始聚类个数比较敏感，对于不同的初始值，可能会导致不同的聚类结果。

2）该算法经常以局部最优结束，有时很难达到全局最优。

3）该算法对初始化的聚类中心点较为敏感，对于不同的初始值，其聚类结果也可能有很大的差异。可通过多设置不同的初始值，对比最后的聚类结果，直到所有结果趋于稳定来改进这一不足，但该做法比较耗时，且浪费资源。

4）该算法只能发现球状簇，其他形状的簇较难发现。

5）该算法只有在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。另外，“噪声”和孤立点数据对聚类的结果影响也比较大，因为少量的该类数据可能对平均值产生极大的影响。

Canopy算法常作为K-Means算法的预处理，用于初始化聚类中心。Canopy聚类尝试通过将聚类过程划分为两个子过程来加速维度较高、基数较大的数据集的聚类。首先，通过选择一个简单、快捷的距离度量公式和两个阈值T1和T2，其中T1> T2，将数据集划为多个子集成为“canopy”，各子集之间可能存在重叠部分。然后将所有数据点添加到一个list中，并随机选择list中的一个点。迭代计算list中剩余点与初始化点之间的距离。如果距离在T1内，则该点将添加到该canopy。此外，如果距离在T2内，则将该点从list中移除。该算法重复迭代，直到list为空[1]。其次，通过使用一个精准、严密的距离计算方法来计算出现在第一步中同一个canopy的所有数据向量的距离。

Cnaopy聚类能帮助用户在使用K-Means聚类时估计k值。对T1、T2给定一个合适的阈值，Canopy聚类将会找到合适数量的canopy。如上所述，在K-Means聚类中，这些可用作初始质心。在Canopy聚类中，因为在第一步时将数据集简单地分为多个canopy，从而使得canopy内部的聚类速度明显提高。Canopy算法的优点主要体现在：

1）K-Means算法中孤立点和“噪声”点对聚类结果有很大的影响。而在Canopy算法中，经过第一步将所有的数据点划分到一个或多个canopy中，可通过直接去掉数据点较少的canopy来排除孤立点或“噪声”带来的干扰。

2）Canopy算法通过第一步的粗糙距离计算方法把数据划入不同的可重叠的子集中，接着只对同一个重叠子集中的样本数据向量进行计算，大大减少了需要计算距离的样本数量，提高聚类效率。

3 改进K-Means算法

综上所述，可以将Canopy算法作为K-Means算法的预处理，通过Canopy算法的第一阶段得到若干个canopy，将canopy的个数作为K-Means算法中初始化簇的个数，再将每个canopy的中心点作为K-Means算法的初始化聚类中心，并通过去掉含有极少数据点的canopy来排除可能存在的“噪声”或孤立点。既可以保证算法的准确性，又可以增加计算效率，减少计算时间。

在K-Means算法中主要通过距离度量公式计算簇的质心与数据向量之间的距离将各个数据点划分到距离最近的簇中，从而实现聚类。因此，距离度量公式的选择在聚类中起着举足轻重的作用，直接影响着聚类的质量。在距离度量的各种公式中，欧式距离、平方欧式距离、余弦距离、曼哈顿距离以及Jaccard距离等较为常用。实验证明在K-Means算法中采用Jaccard距离度量公式可取得较好的结果[2]，特别是针对高维数据集使用欧氏距离可使聚类的性能提高10～20倍[3]。相对于欧式距离，在K-Means中使用余弦计算公式可取得更好的效果[4]。在本文中提出另一种改进的余弦距离计算公式，该公式可使得同一簇内各个数据点之间的距离尽可能达到最小，不同簇内各个数据点之间的距离达到最大，提高聚类的精确度。

余弦相似性是通过计算两个向量之间夹角的余弦值来表示的。夹角为0°的余弦值为1，夹角为90°的余弦值为0，因此两个向量之间相似度取值为-1～1。具有相同方向夹角为0°的两个向量余弦相似度为1，夹角为90°的两个向量之间的相似度为0，具有相反方向夹角为180°的两个向量余弦相似度为-1。余弦值計算取决于向量之间的方向与向量之间夹角的大小无关[4]。余弦相似性计算经常被用于真实的向量空间，它的取值范围为[-1，1]。通过观察两个向量之间夹角的方向而不是夹角的大小来计算向量之间的余弦相似度，给定向量空间中的两个向量，它们之间的余弦相似性表示如下：

根据上述公式，余弦相似性的取值范围为[-1，1]。以同样的方式，采用上述公式计算余弦相似性。在本文中向量之间的余弦值就是向量之间的距离测量标准，所以余弦值的范围[-1，1]也是距离D的变化范围。

在采用标准的余弦距离度量公式得到向量之间的距离后，为使同一簇中数据点间的距离更小，不同簇中数据点间的距离更大，当距离D取值为0～0.5时，通过对距离平方减小同一簇中数据点之间的距离，当距离D取值大于0.5时，通过对距离开平方增大不同簇数据点之间的距离。采用改进的余弦距离度量公式后，可使得簇内数据点间距离减小，簇间数据点间距离增加，从而达到改善簇的质量，提高聚类准确性的目的。

参考文献：

[1] Mccallum A， Nigam K， Ungar L H. Efficient clustering of high-dimensional data sets with application to reference matching[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2000：169-178.

[2] Shameem M U S， Ferdous R. An efficient k-means algorithm integrated with Jaccard distance measure for document clustering[C]// Asian Himalayas International Conference on Internet， 2009. Ah-Ici. IEEE， 2009：1-6.

[3] Kanungo T， Mount D M， Netanyahu N S， et al. An efficient k-means clustering algorithm： analysis and implementation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2002， 24（7）：881-892.

[4] Strehl E， Ghosh J， Mooney R. Impact of Similarity Measures on Web-page Clustering[C]// 2001：58-64.