目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型，聚类的目的和应用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。聚类分析的实现步骤大致为特征选择、计算相似度、选择聚类算法和验证判定结果。每一步中选择不同的方法，便是区分聚类算法的原则之一。

聚类分析旨在发现紧密相关的观测值组群，使得与属于不同簇的观测值相比，属于同一簇的观测值相互之间尽可能类似。聚类可用来对相关的顾客分组、找出显著影响地球气候的海洋区域以及压缩数据等。仅依据在数据中发现的描述对象及其关系的信息，将数据划分成有意义或有用的组（簇）。目前的聚类算法有很多种，考虑到数据类型，相似度计算公式以计算法结构，各种算法已有很多交集。

5.1.4.1　传统聚类算法

传统的聚类算法分为5类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等。通过扩展这些类别中的各种算法，大量面向数据流应用的聚类算法破茧而出。传统聚类算法多数属于硬聚类，每个元素只能属于一个集合，在元素特征模糊时聚类结果将受到影响。此外，一些传统聚类算法需要输入子集数量的初始值，这使得在处理大数据时聚类效果不佳。但传统聚类是现代聚类发展的理论基础和实践先驱，因此对于传统聚类的介绍和理解具有重要意义。

（1）划分方法

基于划分的聚类算法是在机器学习中应用最多的，在处理聚类个数固定的聚类上有着明显优势。划分法属于硬聚类，指导思想是将给定的数据集初始分裂为k个簇，每个簇至少包含一条数据记录，然后通过反复迭代至每个簇不再改变即得出聚类结果。该算法先对数据样本进行初步分组，再将此划分结果作为初始值进行迭代，在迭代过程中根据样本点到各组的距离反复调整，重新分组，通过一次又一次的重复计算，使得每次的计算结果都要比上一次的效果好，最终分组结果不再发生变化，最终得到一个最优的收敛的目标函数。

给定一个有n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且k≤n。也就是说，它将数据划分为k个簇，同时满足两个要求，每个簇至少包含一个对象以及每个对象必须属于且仅属于一个簇。实际上，后面介绍的在某些模糊划分技术中第二个要求可以根据实际情况给予放宽。给定k，即要构建的划分数目，创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是在同一个类中的对象之间的距离尽可能小，而不同类中的对象之间的距离尽可能大。当然还有许多其他划分质量的评判准则。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。

比较典型的划分方法有K－Means算法、K－Medoid算法及K－Harmonic Means算法等。

①K－Means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K－Means算法是采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。

②K－Medoid中心划分法，它是基于K－Means聚类的算法改进。我们知道，KMeans算法执行过程，首先需要随机选择初始质心，只有第一次随机选择的初始质心才是实际待聚类点集中的点，而后续将非质心点指派到对应的质心点后，重新计算得到的质心并非是待聚类点集中的点。如果某些非质心点是离群点的话，导致重新计算得到的质心可能偏离整个簇，为了解决这个问题，提出了改进的K－Medoid聚类算法（K－中心划分法）。K－Medoid聚类算法不再采用簇中对象的平均值作为参照点，而是选用簇中心位置的对象，即中心点为参照点

PAM（Partitioning Around Medoid，围绕中心点的划分）是聚类分析算法中划分法的一个聚类方法，是最早提出的K—中心划分算法之一。围绕中心点划分（Partitioning Around Medoids，简称PAM）的方法是比较常用的。使用PAM方法进行处理，可以指定一个最大迭代次数的参数，在迭代过程中基于贪心策略来选择使得聚类的质量最高的划分。使用PAM的方法处理，每次交换一个中心点和非中心点，然后执行将非中心点指派到最近的中心点，计算得到的代价函数值SAD越小，则聚类质量越好，如此不断地迭代，直到找到一个最好的划分。

③K－Harmonic Means（K调和均值或KHM算法）算法，是K－Means聚类算法的一种改进算法，通过KHM聚类算法可以得到每个数据点到所有聚类中心的调和平均值，当这些数据点接近任一聚类中心时，调和方法为每个数据点提供了一个较好的分值，K－Harmonic Means聚类算法这种功能类似于K－Means聚类算法的最小距离功能。

（2）层次方法

层次方法的指导思想是对给定待聚类数据集合进行层次化分解。此算法又称为数据类算法，此算法根据一定的链接规则将数据以层次架构分裂或聚合，最终形成聚类结果。根据层次的分解如何形成，层次的方法可以被分为凝聚的、分裂的方法。分裂聚类初始将所有待聚类项看成同一类，然后找出其中与该类中其他项最不相似的类分裂出去形成两类。如此反复执行直到所有项自成一类。聚合聚类初始将所有待聚类项都视为独立的一类，通过连接规则，包括单连接、全连接、类间平均连接以及采用欧氏距离作为相似度计算的算法，将相似度最高的两个类合并成一个类。如此反复执行直到所有项并入同一个类。

BIRCH算法是层次算法中的典型代表算法，其核心是CF（Cluster Feature）和CF Tree。CF是一个存储了聚类信息的三元组，其中包含了n（待聚类项个数），LS（n个数据点的线性和），SS（n个数据点的平方和）。LS和SS分别反映了聚类的质心和聚类的直径大小。CF Tree有两个参数：分支因子B（每个非叶子节点的子节点的最大样本数目）和阈值T（限定叶节点的最大半径或直径）。

（3）基于密度的方法（Density－Based Methods）

划分方法和层次方法的两类算法，其聚类的划分都以距离为基础，容易产生类圆形的凸聚类。而密度算法很好地克服了这一缺点。密度算法的指导思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪”数据并发现任意形状的簇。

DBSCAN算法是基于密度聚类的经典算法。它将簇定义为密度相连的点的最大集合，将足够高密度的区域划分为簇。这样的算法对噪声具有健壮性，并且可以发现任意形状的聚簇。DBSCAN的基本算法流程为，从任意对象x开始，根据阈值和参数通过广度优先搜索提取从x点密度可达的所有对象，得到一个聚类。若x是核心对象，则可以一次标记相应对象为当前类并以此为基础进行扩展。得到一个完整的聚类后，在选择一个新的对象重复上述过程。若x是边界对象，则将其标记为噪声并舍弃。

尽管DBSCAN算法改进完善了上述两种算法的一些缺陷，但此算法也存在不足。如聚类的结果与参数关系较大，阈值过大容易将同一聚类分割，阈值过小容易将不同聚类合并。此外固定的阈值参数对于稀疏程度不同的数据不具适应性，密度小的区域同一聚类易被分割，密度大的区域不同聚类易被合并。

（4）基于网格的方法

基于网格的方法，把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。

基于网格方法的代表性例子如STING，它采用基于网格的多分辨率聚类技术，将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构，即高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储，这些统计变量可以方便后续的查询处理。尽管该技术有快速的处理速度，但发现簇的质量和精确性难以得到保证。

（5）其他算法

除了上述四种聚类算法，较常用的传统聚类算法的还有基于模型的方法、回归分析法等。

基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳匹配，这样的方法经常是基于这样的假设，数据是根据潜在的概率分布生成的。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据和孤立点，从而产生健壮的聚类方法。基于模型的聚类方法主要有两类，一个是统计学方法，一个是神经网络方法。

回归分析的方法在预先假设数据元素具有局部线性的前提下，利用数学函数来进行一个多变量分析。回归分析方法分为初始化和合并两个步骤。此外，它的初始簇集是通过数学函数构建的，而不像基于K－Means算法那样近似地得到。

5.1.4.2　数据挖掘领域中聚类方法研究的发展趋势

由于每一种方法都有缺陷，再加上实际问题的复杂性和数据的多样性，使得无论哪一种方法都只能解决某一类问题。近年来，随着人工智能、机器学习、模式识别和数据挖掘等领域中传统方法的不断发展以及各种新方法和新技术的涌现，数据挖掘中的聚类分析方法得到了长足的发展。整体来看，主要围绕样本的相似性度量、样本归属关系、样本数据的前期处理、高维样本聚类、增量样本聚类等几个方面展开研究。

（1）基于样本归属关系的聚类

①基于粒度的聚类算法。

从表面上看，聚类和分类有很大的差异——聚类是无导师或无监督学习，而分类是有导师或有监督学习。更进一步地说，聚类的目的是发现样本点之间最本质的抱团性质的一种客观反映；分类在这一点上却不大相同，分类需要一个训练样本集，由领域专家指明哪些样本属于一类，哪些样本数据属于另一类，但是分类的这种先验知识却常常是纯粹主观的。如果从信息粒度的角度来看的话，就会发现聚类和分类有很大的相通之处：聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行计算的，所以说在粒度原理下，聚类和分类是相通的，很多分类的方法也可以用在聚类方法中。

②不确定聚类算法(www.daowen.com)

Ⅰ.模糊聚类。在实践中大多数对象没有严格的属性，它们的类属和形态存在着中介性，适合软划分。由于模糊聚类分析具有描述样本类属中间性的优点，能客观地反映现实世界，成为当今聚类分析研究的主流。1969年，Ruspini首次将模糊集理论应用到聚类分析中，提出了模糊聚类算法是基于模糊数学理论的一种非监督学习方法。模糊聚类一经提出，就得到了学术界极大关注，模糊聚类是一个很大的聚类“家族”，关于模糊聚类的研究十分活跃，从目标函数、隶属度函数和聚类准则函数等三个方面进行了研究。

Ⅱ.粗糙聚类。不确定聚类另外一种就是粗糙聚类，从粗糙集与聚类算法的耦合来看，可以把粗糙聚类分为两类：强耦合粗糙聚类和弱耦合粗糙聚类。所谓弱耦合粗糙聚类，就是粗糙集扮演着数据预处理等角色，最主要的应用就是用粗糙集的属性简约理论对进行聚类的样本数据进行降维；所谓的强耦合是指利用粗糙集的上、下近似理论对聚类算法上、下近似处理。

Ⅲ.基于熵的聚类。在物理学中，熵用来描述原子分布的无序程度。当某一系统越有序、越确定时，该系统的热熵越小。在信息论中，信息熵是一个信源发出某一消息所含信息量的度量，当某一信源发出的消息越确定时，该信源的信息熵越小；数据点的分布类似于原子的分布，当聚类的划分越合理，数据点在某一聚类上的归属越确定时，该聚类的信息熵值越小。在聚类分析中，由于在分组前数据点对某一聚类的归属在主观划分上是依赖于用户所选取的算法，当用户采取不同的算法时，数据点的归属性就不同，而客观上来讲，数据点对某一聚类的归属又是确定的。因此，如果在主观上找到尽可能确定的数据点归属，即求得信息熵值最小的聚类结果，那么聚类的目的就达到了，这就是基于熵的聚类算法。

（2）基于样本相似性度量的聚类

①谱聚类算法。

谱聚类算法是建立在谱图理论基础之上，并利用数据的相似矩阵的特征向量进行聚类，使得算法与数据点的维数无关，而仅与数据点的个数有关，因而统称为谱聚类方法。谱聚类算法是一种基于两点间相似关系的方法，这使得该方法适用于非测度空间。与其他方法相比，该方法不仅思想简单、易于实现、不易陷入局部最优解，而且具有识别非凸分布的聚类能力，非常适合于许多实际应用问题。

②仿射聚类。

仿射聚类是2007年Science报道的一个全新聚类算法，其优势体现在处理类数很多的情况时运算速度快。仿射聚类算法通过一个迭代循环，不断进行证据的收集和传递（亦称为消息传递）以产生m个高质量的类代表和对应的聚类，同时聚类的能量函数也得到了最小化，将各数据点分配给最近的类代表所属的类，则找到的m个聚类即是聚类结果。

③混合属性聚类。

在实际数据聚类中，需要处理的数据除数值型属性外，还包括文本、图像等符号型属性的混合型数据。这些算法在进行不同属性的数据处理时，都要进行相关转换，或者全部转换成数值型数据，或者全部转换成符号型数据进行处理，数据聚类精度在进行转换时受到影响。面向混合型数据的聚类方法就是解决这类聚类问题的。CBL（Clustering Based on Lattice）算法是以格论为基础，利用格论中简单元组和超级元组的概念，对数据进行格的划分，以非距离的格关系作为聚类相似度的衡量方法，同时也产生了基于CBL的改进算法，利用格论中简单元组及超级元组将对象属性转化为格模型，以对象间格覆盖数来衡量类间相似度，根据高覆盖高相似度的原则选择聚类中心进行聚类。

（3）基于样本更新策略的聚类

增量聚类的研究主要有两个思路：一个是将所有的数据进行迭代，即从第一个数据到最后一个数据进行迭代运算，其优点是精度高，不足之处是不能利用前一次聚类的结果，浪费资源。另一个是利用上一次聚类的结果，每次将一个数据点划分到已有簇中，即新增的数据点被划入中心离它最近的簇中并将中心移向新增的数据点，优点是不需要每次对所有数据进行重新聚类，缺点是泛化能力弱，监测不出孤立点。

①数据流增量聚类

数据流的聚类问题是典型的增量聚类问题，这些数据具有实时性、连续性、顺序性的动态流式数据。数据流聚类的基本任务就是对当前数据进行聚类的同时，随着新数据的不断流入，动态调整和更新聚类结果以真实反映数据流的聚类形态。目前主要是把一些传统的聚类算法应用到数据流聚类问题当中来。

②基于群体智能的增量聚类

研究者从生物的智能行为中受到启发，建立了各种模型，用来求解复杂的科学问题，目前主流的一些群体智能算法及其在增量聚类中的应用情况：基于遗传算法的增量聚类、基于PSO算法的增量聚类、基于蚁群算法的增量聚类、基于人工免疫系统的增量聚类等。

（4）基于样本高维性的聚类

由于高维数据存在的普遍性，使得对高维数据的聚类已经成为近几年研究的一个热点。高维数据聚类的特点是：①随着维数增长，聚类的时间和空间复杂度迅速上升从而导致算法的性能下降；②高维数据集中存在大量无关的属性，并且在这些不相关的维上十分稀疏，这就使得在所有维中存在簇的可能性几乎为零，所以传统的聚类算法不适合对高维数据进行聚类；③距离函数难于定义，聚类操作的基础是数据对象之间相似性的度量，相似度高的对象归为一类，但在高维情况下距离函数失效，因此必须通过重新定义合适的距离函数或相似性度量函数以避开“维度效应”的影响。

对于高维数据而言，针对高维数据的稀疏性、空间和维灾等特征，目前主要有两个研究思路：一个是通过选维、降维技术去除与数据簇不相关的维，然后再使用聚类算法对转换后的数据进行聚类。另一个是子空间聚类，该类算法从数据集中找不同子空间中的簇。

（5）与其他学科的融合聚类

①量子聚类算法。量子力学是一门研究粒子在能量场中分布的科学，聚类是研究样本在尺度空间中的分布情况。可见，量子力学研究的粒子在空间中的分布，同聚类研究样本在尺度空间中的分布情况是等价的。对于样本分布已知时的聚类，对于量子力学而言，描述粒子分布的波函数是已知的，聚类过程相当于：在波函数已知时，采用薛定锷方程求解势能函数，而这个势能函数将最终决定粒子的分布。

②聚类集成。聚类集成是基于集成思想的一种新的聚类算法，利用（经过选择的）多个聚类结果找到一个新的数据（或对象）划分，这个划分在最大程度上共享了所有输入的聚类结果对数据（或对象）集的聚类信息。聚类集成可以分为两个阶段：聚类成员个体生成阶段和对聚类成员个体结果进行集成阶段。

③球壳聚类。球壳聚类其实是模糊聚类的衍生，模糊聚类的原型由点逐步扩展到线、面、球壳、椭圆壳、矩形壳和多边形壳。其中球壳聚类是其中研究最为活跃的一种。所谓球壳聚类就是样本数据的分布呈球壳状的聚类问题，可以采用球壳作为聚类原型，定义目标函数，并推导出球壳聚类的迭代算法。模糊壳聚类方法依赖于人脑事先给出确定的聚类壳数，并且对原型初始化要求较高。

5.1.4.3　应用领域

聚类分析具有广泛的应用领域。对于网络流量的监控和数据挖掘，可以实现舆情分析，获知前所未有的热点事件。聚类分析作为一种基本的数据挖掘方法已经广泛地应用于相似搜索、顾客划分、模式识别、趋势分析、金融投资、地理信息系统、卫星图像和医疗卫生等领域，并取得了一定成效。比较有代表性的应用实例如：

（1）在交易数据库中，对顾客一次购买商品的情况进行聚类分析，根据聚类结果来布置商品摆放位置，从而提高销售利润。

（2）类似地，在电子商务中，每天的日常业务会产生大量数据，用聚类算法分析这些数据信息能帮助销售商确定相对固定的顾客群，便于商家有针对性的制订销售方案、开展有效的促销活动，以保证在赢得更大利润的同时又发展了新顾客群、保留住了旧顾客群。

（3）在信息检索领域中，聚类分析对文档进行分类，改善信息检索的效率，从而提高人们的工作效率。

（4）在气象预测中，通过对由传感器传来的空气的温度、湿度、可见度等信息进行聚类，可以预测未来几天气候的变化。

（5）在医疗分析中，通过对一组新型疾病聚类，得到每类疾病的特征描述，就可以对这些疾病进行识别，提高治疗的功效。聚类还能帮助医生发现不正常类别的特殊病例，例如识别组织结构的病变细胞。

聚类还用于发现空间趋势，即空间数据库中一个或多个非空间属性的变化模式。在天文学上，研究人员利用聚类分析宇宙仿真系统得到的数据，更好地理解黑洞形成和进化的物理过程等。