层次聚类

本文主要为了了解聚类的分裂与合并。

层次聚类

概念

层次聚类（Hierarchical Clustering）考虑把n个样本聚成c类的情况。首先把所有样本分成n类，每类正好含有一个样本。其次，我们将样本分为n-1类，接着是n-2类，这样下去知道所有样本被分为一类。我们成聚类数目$c=n-k+1$对应层次结构的第k层，因此第1层对应n个类而第n层对应一个类别。对层次结构的任意一层及其该层中的任意n个样本，如果该层中属于同一类，而且在更高的层次一直属于同一类，那么这样的序列称为层次聚类。

层次聚类的表达方式

1. 树图
2. 集合图
   1. 纯文本集合：${x_1,{x_2,x_3},{x_4,x_5}}$
   2. 维恩图

其中，纯文本集合不能定量的体现相似性

实现方法

层次聚类方法主要通过两种途径进行实现：合并和分裂。

合并是自底向上，先使得所有样本归入一类，然后通过后续分裂，来增加类别的数目。

一 合并

自底向上，先使得样本各成一类，然后通过合并不同的类，来减少类别数目。

基于合并的聚类算法

一开始一共有c类

1 begin intialize: c,\hat{c} <- n, D_i <- {x_i}, i = 1,...,n
2 		do \hat{c}<-\hat{c}-1
3 			求最接近的聚类，如D_i和D_j
4			合并D_i和D_j
5 		until c = \hat{c}
6		return c个聚类
7 end

对合并方法来说，从一个层次到另一个层次所需的计算比较简单。但是如果样本过多而期望的类别样本数目又很少，这种计算会被反复多次地执行。

不同类别之间的相似性的度量：
$$
d_\min(D_i,D_j) = \min_{x\in D_i\x’D_j}||x-x’||\
d_\max(D_i,D_j) = \max_{x\in D_i\x’D_j}||x-x’||\
d_{avg}(D_i,D_j) = \frac{1}{n_in_j}\sum_{x\in D_i}\sum_{x\in D_j}||x-x’||\
d_{mean}(D_i,D_j) = ||m_i-m_j||
$$
在上述的这些距离度量中，最近距离度量$d_\min(.,.)$和$d_\max(.,.)$ 代表了类与类之间距离的两个极端。就像所有利用最大值或最小值的算法，它们对噪声和孤立点非常敏感。用平静值代替它们可以改善这些问题。

二 分裂

先将样本都归入一类，然后通过后续分裂，来增加类别数目。

基于优化的层次聚类

任选一种距离度量来表示类与类之间的距离时，没有考虑到是否能使聚类准则函数取极值。

因此可以稍作修改，获得一个极值化准则函数的“逐步优化的层次聚类”的算法。

1 begin intialize: c,\hat{c} <- n, D_i <- {x_i}, i = 1,...,n
2 		do \hat{c}<-\hat{c}-1
3 			寻找其合并类，将准则函数改变为最小的聚类，例如D_i和D_j
4			合并D_i和D_j
5 		until c = \hat{c}
6		return c个聚类
7 end

可以看出，基于$d_\max(.,.)$的聚类方法使得划分半径增长最慢，可以看作是一种逐步求精的例子。

还有一种基于误差平方和的准则函数$J_e$的方法，如果我们找到两个类，若它们的合并类造成$J_e$的增加凉最少，就要求距离
$$
d_e(D_i,D_j) = \sqrt{\frac{n_in_j}{n_i+n_j}}||m_i-m_j||
$$
最小，当挑选用来合并的聚类的时候，这个准则除了考虑了类与类之间的距离，还考虑了类中所含样本的个数。一般来说，基于$d_e(.,.)$的算法倾向于将孤立点或较小的类与较大的类合并。虽然最后的结果不一定能最小化$J_e$，但这个结果可以向进一步的迭代优化提供非常好的初始点。

层次聚类和导出度量

假定可以衡量数据集中的任意两个样本之间的相异程度，$\delta(x,x’)$。而且$\delta(x,x’)\geq 0 $，等号当且仅当$x=x’$时成立。那么合并聚类算法还是可以使用，只要理解两个最近的聚类就是最不相异的类。

如果定义两个聚类的相异度为：
$$
\delta_\min(D_i,D_j) = \min_{x\in D_i\x’\in D_j} \delta(x,x’)\
\delta_\max(D_i,D_j) = \max_{x\in D_i\x’\in D_j} \delta(x,x’)
$$
层次聚类算法就可以对给定的n个样本集导出距离函数。

打赏