经典聚类算法研究综述

邓林培

摘 要 文章通过介绍4种经典的聚类算法以加强人们对聚类算法的了解，同时对每一种算法的适用情况和优势劣势进行阐述。聚焦于聚类算法发展所呈现的趋势和应用情景中涉及的领域，感知聚类算法在机器学习甚至人工智能领域的强大生命力。

关键词 人工智能；机器学习；聚类；K-means

中图分类号 TP2 文献标识码 A 文章编号 1674-6708（2019）230-0108-03

从1956年的达特茅斯会议到如今，不过短短60多年的时间，人工智能发展之迅速令人惊叹。人工智能领域十分广泛，神经网络、自然语言处理、遗传算法、深度学习，甚至哲学问题和未来趋势等都是这一大学科中的一部分。对机器来说，所谓智能，实质是由人对它输入算法和数据，机器本身运用算法从数据中进行学习，并由此处理新的实际问题。不光算法，像自然语言处理，哲学问题都可以与机器学习结合。

机器学习中有许多算法。其中聚类算法是一个大的分支。针对不同数据类型，聚类算法中有各种不用运行理念、不同基准的算法可将不同类型的样本数据收聚到较好的结果。聚类算法中经典的算法如K-means算法、均值漂移算法、DBSCAN算法和层次聚类算法在当下仍经久不衰。同时，聚类算法在信息技术和人工智能浪潮的推涌之下，呈现出融合的新态势。

1 经典聚类算法研究

1.1 K-means

K-means算法是一种应用极为广泛的聚类算法[ 1 ]。它的核心思想是用户指定k个初始的质心（随机数）作为聚类的类别，并重复迭代直至算法收敛。

首先，计算所有数据点到这k个初始质心的距离，并以这个计算出的距离作为下一步分类标准，也就是说，各数据点到哪个质心距离最近，便决定它在此次类别的分取中属于哪一类别。那么，初始定义的k个质心就会在迭代中将所有数据分为k个类别也就是k个簇。待对每个样本点进行了距离计算并类别归属之后，再重新计算k个簇中每一个簇对应的质心，即更新质心。每个簇数据明朗，质心实际可求，于是，对所得的每一个簇的所有数据点求新质心，再以此质心替换随机数质心做为新的距离计算標准，重复距离近便成一簇的过程。之后继续重复质心更新和数据分簇过程，直至质心更新时，每簇的质心不再变化或仅有微小变化时，算法停止。最后所得的k个最终质心及它们所在簇包含的样本点，即所期望的聚类结果。

K-means算法中k值也就是聚类的类别数是需要用户自己定义的，当遇到一个复杂的数据结构，可能需要多次尝试才能选取到一个较好的k值，使这个样本数据聚成如此多个类才是最优的。

我们可以发现，因在最初的算法迭代中选取的初始质心为随机定义而来，会致使聚类效果不好，迭代次数增多，可能仅得到局部最优结果。局部最优是K-means算法乃至机器学习算法存在的普遍问题。同时，K-means算法仅适用于数据聚类，并且在噪音数据出现时，由于其算法的原理，以距离平方和为准则，会使一些不合理的极端数据影响聚类结果。

针对它的这些缺陷，K-means算法衍生出的变种k-modes算法和K-prototype算法在一定程度上弥补了K-means算法的不足。

K-modes算法适用于离散型非数值型的集合，如时间、文本、颜色、大小等。它是以属性来度量两样本的相关性D。比较两样本所有属性，若属性不同就给D加1，相同就加0。也就是说，D值越大，两样本就越不相关。这不相关程度越大就相当于k-means中的距离越远。接着以每一簇中出现频率最大的属性值来代表那一簇的属性，不断更新簇，更新代表属性，重复迭代。

K-prototype算法是对K-means算法和K-modes算法的结合，它适用于样本记录里面既有离散型数据又有数值型数据的集合。它结合K-means得到数值属性和结合K-modes得到分类属性，最终通过权重来得出样本混合属性。其更新也是两者结合，并重复迭代得出结果。

当然，K-means算法以其运算迅速，操作简单易行等优势仍在各领域有着广泛的应用。

1.2 均值漂移聚类

与K-means相似，都是基于质心的聚类算法。均值漂移算法[ 2 ]依赖于自定义半径的圆形滑动窗口的移动。窗口会一直向着能使圆内数据点密度增大最快的方向靠近，直至窗口无论再向哪个方向移动，都无法再使更多点被包括进窗口内，即窗口内数据密度不再增加时，窗口才不再滑动。它与K-means的相似之处是它也需要先随机选取窗口中心值和窗口半径，待窗口滑到新的数据区时，中心值便随之更新，即把窗口内所有数据点的平均值作为新的中心点而继续滑动。

均值漂移算法的优点在于不需要我们事先确定类别数目，当初始的中心点数目足够，它会自发收敛到密度最高的几个区域。

此算法对密度分布差异较大的数据聚类效果好且受均值影响较小。但对分布均匀的数据来说，均值漂移算法收敛效果较差。

1.3 DBSCAN算法

DBSCAN是一种基于密度的聚类算法[ 3 ]，它的聚类思想是以密度可达关系导出可得的最大密度相连样本集合，此即为聚类出的一个簇。

6）另取核心对象重复上两步步骤。DBSCAN适用于任意稠密数据，对数据里的噪声数据不敏感，聚类结果相对受其他因素干扰较少，可避免出现K-means受初始值影响大的情况。但正是由于其基于密度的算法特性，如果样本密度不均，会导致出现聚类质量低的情况。且如果样本数据多，DBSCAN聚类收敛耗时会较长，并不理想。

1.4 層次聚类算法

层次聚类包括自下而上的凝聚聚类和自上而下的分裂聚类方法[ 4 ]。

其中凝聚聚类要求我们首先得把每个数据点视为一个单一的簇，再将距离最近的两个簇合并。这里就需要我们选定一个距离度量标准。例如我们可以使用簇间距离，即第一个簇中的数据点与第二个簇中的数据点之间的平均距离作为标准来进行合并。合并后重新计算各簇间距离，重复合并步骤，直到聚类成一簇或达到预设条件方可结束算法。

而分裂聚类与凝聚聚类恰好相反，它意在将一个大的数据集分裂成许多小簇。先将所有对象置于一个类中，然后逐渐分出小簇，使总数据集变为越来越小但个数越来越多的簇，直到每个对象独自成簇或满足了一定的终止条件。例如达到了我们希望的聚类簇数目，结束算法。

层次聚类不需要我们提前知道需要合成或分割所得的簇的数目，同时它可以使用多种距离计算方法来计算簇间距离，但也正是距离计算量大，层次聚类并不迅速，效率低。

2 聚类算法的发展趋势与应用前景

2.1 发展趋势

正如人类认识社会，需要区别不同事物，联系相同相似事物一样，数据的挖掘、处理也离不开聚类分析。在这个数据爆炸的时代，聚类算法大有用武之地。公司对目标顾客的分析，市场销售的调研等等都与聚类算法有着密切联系。不难发现，聚类算法中不同类型的算法有着不同适用领域，但每个算法都并不完美。各个算法之间存在一种相互弥补相互结合的关系，正与现代社会发展，领域不断更新，各领域数据变得更庞大更多元更复杂的趋势相适应。这无疑对算法提出了更高的要求，孤立的算法已经并不完全适用于这个时代。

2.2 应用前景

聚类算法可应用于图像分割、机器视觉、数据压缩和信息检索，它功能强大，譬如检索时可以使检索时间缩短并且拥有更高的精确度。它还应用于一些生活中常用的软件，如知识管理系统里的知识共享、知识推荐功能，学生成绩统计分析软件对成绩的深度挖掘功能。

聚类算法可应用于建立数据库，其中的文本聚类算法还被用来建立词义网（Word Net）。随着时代的发展，聚类算法的应用领域已从商业金融拓展到了教育互联网等行业，同时对生物学、心理学、考古学、地质学的研究也都有重要作用。

3 结论与展望

聚类算法的发展已经到了一个融合互补的时期，它所包含的孤立的经典算法虽仍然能得到较为广泛的应用但终会逐渐追逐不上时代日新月异的复杂变化。时代发展要求数据结构向着更复杂更灵活的方向发展。聚类算法要想继续能将机器学习进行得正确而高速，势必要在原本的经典算法的基础之上，做出符合时代数据特征的创新。

在笔者看来，完美倒不是一件幸事，只有在对不完美的修正与创新中，才能擦出新的思维火花，在成果不断更新被淘汰更新再换代的过程中，人类的智慧才得以更大可能的激发，社会才得以不断进步。正因如此，聚类算法的未来，是互相融合互相补充的未来，是不断改进与简化的未来，至少以后的一段时期内，它的未来前景不可小觑。

参考文献

[1]杨善林，李永森，胡笑旋，等.K-means算法中的K值优化问题研究[J].系统工程理论与实践，2006，26（2）：97-101.

[2]周芳芳，樊晓平，叶榛.均值漂移算法的研究与应用[J].控制与决策，2007，22（8）：841-847.

[3]荣秋生，颜君彪，郭国强.基于DBSCAN聚类算法的研究与实现[J].计算机应用，2004，24（4）：45-46.

[4]史变霞，张明新.一种改进的层次聚类算法[J].微电子学与计算机，2010，27（12）：55-56.