基础的层次聚类算法

引入

层次聚类算法分为两种:

• 凝聚方法, agglomerative, 即自下而上法(bottom-up)

  • 从点作为个体簇开始, 每一步合并两个最近距离的簇. 需要定义簇的邻近性概念

• 分裂算法, divisive, 即自上而下法(top-down)

  • 从一个簇包含所有点开始, 每一步分裂一个簇, 直到只剩下单点簇. 在每一步, 需要确定分裂那个簇, 以及如何分裂

两种方法本质上没有优劣之分, 只是在实际应用的时候要根据数据特点以及想要的类的数量, 来考虑是自上而下更快还是自下而上更快, 然后进行选择.

因此以下只关注凝聚方法的层次聚类. 使用凝聚方法, 首先需要计算两个簇之间的邻近度.

簇的邻近度

MIN/单链(single link)

MIN/单链将簇的邻近度定义为两个簇的最近点之间的邻近度, 以点的邻近度, 作为簇的邻近度. 关于点的邻近度的定义可以参考两点之间的相似性度量方法.

单链擅长:

• 处理非凸集/非椭圆形状的簇

但缺点也很显著:

• 对噪声和离群点很敏感

MAX/全链(complete link)

MAX/全链去两个簇中两个最远的点之间的邻近度作为簇的邻近度.

全链擅长:

• 对噪声和离群点不敏感

但也有以下的缺点:

• 偏好形成球形, 对非凸集样本集不友好

• 可能使得很大的簇破裂

组平均(group average)

对两个簇中的所有点之间组成点对, 对所有点对的邻近度(距离)取平均值, 因此需要遍历所有点.

Ward

Ward将两个簇的邻近度定义为两个簇合并时导致的平方误差的增量. 即首先分别计算两个簇的平方误差, 然后再假设这两个簇聚合在一起, 计算聚合后的新簇的平方误差. 再将合并后平方误差减去合并前的, 就得到了合并后的平方误差的增量. 这个值肯定的大于0的, 在聚类算法中, 应选择平方误差增加最小的两个簇进行合并.

至于平方误差, 公式为:

$\sum\limits_{i=1}^{n}x_i^2-\frac{1}{n}(\sum\limits_{i=1}^{n}x_i)^2$

本质相当于方差$\times n$. 当然Ward属于一种思想, 任何可以衡量簇内部离散程度的指标都可以使用.

在使用平方误差的Ward方法时, 层次聚类算法可以从数学上证明, 与K-Means算法十分相似. 因此具有K-Means聚类算法的性质.

质心方法

计算每个簇的质心, 使用质心点之间的邻近度作为两个簇之间的邻近度.

质心方法有个独特的缺点: 本次迭代合并的两个簇, 可能比上一次迭代合并的两个簇更为相似, 从而出现倒置的可能性. 使用其他簇的邻近度评价方法不会出现这个现象, 簇之间的距离随着层次聚类的进行而单调增加.

Lance-Williams公式

上面的所有计算簇的邻近度的方法, 都能够用Lance-Williams公式的形式表示, 不同方法之间, 只是公式中参数值设定的不同.

Lance-Williams公式是一种衡量簇之间邻近度的通用且重要的公式.

确定好要使用的簇的邻近度之后, 开始对簇进行合并, 这一步被称为linkage. 如使用ward方法的这个过程就被称为ward linkage method.

linkage过程中会记录每次合并的两个簇的序号, 并给定这个新生成的簇一个新的独特序号(序号递增), 然后会记录这两个被合并簇之间的邻近度.

scipy.cluster.hirarchy.linkage函数中可以选择上述的任意一种方法, 进行linkage, 记录并返回整个合并过程. 使用返回的linkage matrix可以画树状图(dendrogram)进行可视化, 而包装好的聚类方法中, 也使用到了这个函数, 对函数的返回结果进行解析和组装, 返回聚类结果.

使用方法

对于层次聚类, 在sklearn和scipy中都有对应的模型类或函数进行实践.

sklearn中有一个专门做凝聚方式的聚类的类: AgglomerativeClustering, 具体的使用方法可以参考对应的文档. 需要注意的是层次聚类因为是从完全单点的簇聚合成一个簇, 所以需要指定簇的数量, 才能返回对应的结果. 重要的参数如下:

• n_clusters: int, default=2

  • 要发现的簇的数量

• affinity: string or callable, default: “euclidean”

  • 计算点之间的相似度的方法, 可以快捷的使用字符串指定, 接受“euclidean”, “l1”, “l2”, “manhattan”, “cosine”, or “precomputed”, 对于ward方法, 只接受euclidean

• linkage: {“ward”, “complete”, “average”, “single”}, optional (default=”ward”)

  • 簇之间合并的方法, 如上面介绍

scipy中, 可以使用scipy.cluster.hierarchy.fclusterdata函数进行聚类. 具体的使用方法可以参考对应的文档. 原理可参考Hierarchical clustering (scipy.cluster.hierarchy).

层次聚类特性

优点:

• 层次聚类的算法往往能够得到高质量的聚类

• 不同的linkage方法的选择, 可以适用于多种数据集情况

缺点:

• 计算量以及存储量十分复杂, 层次聚类算法是很昂贵的

• 对于高维数据或噪声的存在也可能产生问题

一种解决方案是, 在使用层次聚类之前, 使用如K-Means之类的其他聚类算法进行初步聚类(即使用其他算法聚出来很多类, 其他算法在使用时指定较多的簇数量), 然后再使用层次聚类算法, 即层次聚类算法的起点是从小簇开始的, 不再是从单个点开始. 使用这种方法, 上面的两个缺点, 在一定程度上都能得到解决(速度等).