数据挖掘（五）：聚类

聚类是数据挖掘描述任务的一个重要组成部分。数据挖掘任务包括描述性任务和预测性任务两种。描述性任务包括聚类、关联分析、序列、异常检测等，预测性任务包括回归和分类。

聚类：将数据对象划分为若干类，同一类的对象具有较高的相似度，不同类的对象相似度较低。从这个简单的描述中，可以看出聚类的关键是如何度量对象间的相似性。较为常见的用于度量对象的相似度的方法有距离、密度等。

1 基于距离度量对象相似性的思想

凡是满足距离定义四个条件（唯一性、非负性、对称性和三角不等式）的函数都可以作为距离公式。常用的有欧氏距离（Euclid）、曼哈顿距离（Manhattan）、契比雪夫距离（Chebyshev）、马哈拉诺比斯距离（Mahalanobis）等。

基于距离的两类经典聚类算法：划分方法（Partitioning Method）和层次聚类方法（Hierarchical Method）。

1.1 划分方法

该方法的典型代表有k-Means、k-Medoids。

k-Means算法的核心思想是把n个数据对象划分为k个类（这k各类事先未知），使得划分后每个类中的数据点到该类中心的距离最小。即使J最小。

k-means算法流程：

输入：分类个数k，包含n个数据对象的数据集
输出：k个聚类
（1）从n个数据对象中任意选取k个对象作为初始的聚类中心；
（2）分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中；
（3）所有对象分配完成后，重新计算k个聚类的中心；
（4）与前一次计算得到的k个聚类中心比较（检测是否收敛），如果聚类中心发生变化（未收敛），转（2），否则聚类结束。

k-means算法本质上是实现了聚类的基本思想：类内数据点越近越好，类间数据点越远越好。

上述算法大多数情况下会最终求得收敛的最优聚类结果，但也有可能陷入局部最优解。还存在一个问题，上述算法有一个前提，就是指定k的值，即聚类个数。而在实际应用中k值是无法事先给定的，因此k-means算法的另一个重点就是要找出一个合适的k，使平方误差数值达到最小。一般的做法是尝试若干个k，选择使平方误差（距离）最小的k值。

k-Means算法第（3）步中聚类中心是计算当前每个cluster的均值作为新的聚类中心，这正是k-Means算法得名的原因。计算公式为

第（4）步中检测是否收敛的标准并非常用标准，因为要达到完全收敛可能并不现实。因此，较为常见的说法为，直到迭代了最大的步数或者前后的 J 的值相差小于一个阈值为止。

在k-medoids算法中，我们将从当前 cluster 中选取这样一个点——它到其他所有（当前 cluster 中的）点的距离之和最小——作为中心点。也就是说，k-Means算法选择的中心点未必在n个数据点中，而可以是连续空间的任意值；k-Medoids则只能在给样本给定的那些点里面选。也正是因为这样，k-Means对噪声和孤立点数据非常敏感，而k-Medoids则可以有效地消除这种影响。

当结果簇是密集的，而簇与簇之间区别明显时，k-Means算法的效果较好。对于大规模数据集，该算法是相对可扩展的，并且效率较高。仅就k-Means和k-Medoids两者而言，在第（3）步中，k-Means具有O(n)的时间复杂度，而k-Medoids的时间复杂度是O(n^2)。

k-Means的不足：首先，k-Means只有在簇数据点的平均值有定义的情况下才能使用，这可能不适用于某些应用，如离散数据。对k-Means改进后的k-模算法用模代替簇的平均值作为相似性度量，用基于频率的方法来修改聚类的模。k-模算法可用于解决离散问题。k-Means和k-模相结合用来处理有数值类型和分类类型属性的数据，这就是k-原型算法。其次，k-Means和k-Medoids不适用于发现非球状的簇。原因是这类算法使用距离来描述数据间的相似性，但是对于非球状数据集，只用距离来描述是不够的。对于这种情况，要采用密度作为相似性度量。（参见2）

1.2 层次聚类方法

层次聚类方法（Hierarchical Method）按数据分层建立簇，形成一棵以簇为节点的树。该方法的典型代表有凝聚法（Agglomerative）和分裂法（Divisive）。若自底向上进行层次聚集，则称为凝聚的层次聚类；若自顶向下进行层次分解，则称为分裂法的层次聚类。

凝聚的层次聚类首先将每个对象作为一个簇，然后逐渐合并这些簇形成较大的簇，直到所有对象都在同一个簇中，或者满足某个终止条件。分裂与之相反，它首先将所有的对象置于一个簇中，然后逐渐划分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件，例如达到了某个希望的簇数目，或两个最近的簇之间的距离超过了一定的阈值。

层次方法可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。但是，单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作不可修正，这可能导致聚类结果质量很低。另外，由于需要检查和估算大量对象或簇才能决定簇的合并或分裂，所以其可扩展性较差。因此，实际应用中常把层次方法与其他方法结合使用，形成多阶段聚类，改善聚类质量。这类方法包括BIRCH、CURE、ROCK、Chameleon等。

2 基于密度度量对象相似性的思想

对于非球状的聚类问题可采用基于密度的聚类算法。基于密度的聚类算法（Density-based Method）从数据对象的分布密度触发，把密度足够大的区域连接起来，从而可以发现任意形状的簇，而且此类算法还能有效去除噪声。常见的基于密度的算法有DBSCAN、OPTICS、DENCLUE等。

3 其他方法

3.1 视觉聚类算法

视觉聚类算法是基于尺度空间理论建立的。其基本思想是：将数据集看作图像，将数据建模问题看作认知问题，通过模拟认知心理学的格式塔原理与生物视觉原理解决问题。格式塔原理（Gestalt）就是物体的整体是由局部特征组织在一起的认知原则，包含相似率、连续率、闭合率、近邻率、对称率。将这五者作为聚类的基本原则，模拟人的眼睛由近到远观察景物的过程设计算法进行聚类。随着由近到远，观察尺度由小变大，所看到的景物层次会逐渐变化，这就是一个聚类的过程。

视觉聚类的关键是最佳聚类个数的选择。随着尺度σ由小变大，聚类个数逐渐变少，但会出现尺度σ在很大范围内变化而聚类个数稳定不变的情况，这意味着这个聚类个数存活周期最长，它就是最佳聚类个数。这解决了聚类有效性问题。

参考资料：

[1]大话数据挖掘

[2]聚类算法研究．孙吉贵等．Journal of Software

[3]漫谈 Clustering (2): k-medoids．http://blog.pluskid.org/?p=40

[4]数据仓库工具箱：维度建模的完全指南