层次聚类

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

层次聚类

概念

层次聚类(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
2
3
4
5
6
7
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
2
3
4
5
6
7
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个样本集导出距离函数。

打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2019-2022 guoben
  • PV: UV:

微信