层次聚类(Hierarchical Clustering)

Hierarchical Clustering.

层次聚类 (Hierarchical Clustering) 是把数据对象组成一棵聚类树，对数据集进行层次的分解，后面一层生成的簇基于前面一层的结果。根据分解的顺序是自底向上（合并）还是自顶向下（分裂），层次聚类可以分为凝聚 (agglomerate)和分裂 (divisive)。

• 凝聚聚类：又称自底向上（bottom-up）的层次聚类，每一个数据点最开始都是一个簇，每次按一定的准则将最相近的两个簇合并生成一个新的簇，如此往复，直至最终所有数据都属于一个簇。
• 分裂聚类： 又称自顶向下（top-down）的层次聚类，最开始所有数据均属于一个簇，每次按一定的准则将某个簇划分为多个簇，如此往复，直至每个数据点均是一个簇。

层次聚类算法是一种贪心算法（greedy algorithm），因其每一次合并或划分都是基于某种局部最优的选择。层次聚类的局限在于，一旦某次合并或分裂被执行，就不能修改。

层次聚类算法的优点：（1）距离和规则的相似度容易定义，限制少；（2）不需要预先制定聚类数；（3）可以发现类的层次关系；（4）可以聚类成其它形状。

层次聚类算法的缺点：（1）计算复杂度太高；（2）奇异值也能产生很大影响；（3）算法很可能聚类成链状。

1. AGNES算法与Divisive算法

Agglomerative Nesting (AGNES)是一种凝聚的层次聚类算法，步骤如下：

1. 初始化，每个样本当做一个簇；
2. 计算任意两簇距离，找出距离最近的两个簇，合并这两簇；
3. 重复步骤2，直到最远两簇距离超过阈值，或者簇的个数达到指定值，终止算法。

Divisive Analysis (DIANA)是一种分裂的层次聚类算法，步骤如下：

1. 初始化，所有样本集中归为一个簇；
2. 在同一个簇中，计算任意两个样本之间的距离，找到距离最远的两个样本点$a,b$，将$a,b$作为两个簇的中心；
3. 计算原来簇中剩余样本点距离 $a,b$ 的距离，距离哪个中心近，分配到哪个簇中；
4. 重复步骤2、3，直到最远两簇距离不足阈值，或者簇的个数达到指定值，终止算法。

在AGNES算法中，需要计算簇间距离。假设两个簇$C_i$和$C_j$分别有$n_i$和$n_j$个数据，其质心为$m_i$和$m_j$，一些常用的簇间距离度量方法：

1. 最小距离：两个类中距离最近的两个样本的距离；\(d_{min}(C_i,C_j)=min_{(p \in C_i,p' \in C_j)}\mid p-p' \mid\)
2. 最大距离：两个类中距离最远的两个样本的距离；\(d_{max}(C_i,C_j)=max_{(p \in C_i,p' \in C_j)}\mid p-p' \mid\)
3. 平均距离：两个簇的平均值作为中心点之间的距离；\(d_{avg}(C_i,C_j)=\frac{1}{n_in_j} \sum_{p \in C_i}^{} {\sum_{p' \in C_j}^{} {\mid p-p' \mid}}\)
4. （类）均值距离：两个簇任意两点距离加总后，取平均值；\(d_{mean}(C_i,C_j)= \mid m_i-m_j \mid\)
5. 中间距离：介于最短距离和最长距离之间，相当于三角形的中线；\(d_{mid}(C_i,C_j)= \sqrt{\frac{1}{2}d_{lp}^2+\frac{1}{2}d_{lq}^2-\frac{1}{4}d_{pq}^2}\)
6. 重心距离：将每类中包含的样本数考虑进去。\(d_{gravity}(C_i,C_j)= \frac{n_i}{n_i+n_j}d_{i\cdot}^2+\frac{n_j}{n_i+n_j}d_{j\cdot}^2-\frac{n_in_j}{(n_i+n_j)^2}d_{ij}^2\)

最小和最大度量代表了簇间距离度量的两个极端，它们趋向对离群点或噪声数据过分敏感。当算法选择“最小距离”作为簇间距离时，称之为最近邻聚类算法。并且当最近两个簇之间的距离超过阈值时，算法终止，则称其为单连接算法；当算法选择“最大距离”作为簇间距离时，称之为最远邻聚类算法。并且当最近两个簇之间的最大距离超过阈值时，算法终止，则称其为全连接算法。

使用均值距离和平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。尽管均值距离计算简单，但是平均距离也有它的优势，因为它既能处理数值数据又能处理分类数据。

2. BIRCH算法

Balanced Iterative Reducing and Clustering Using Hierarchies (BIRCH) 使用聚类特征树（CF-tree）来进行快速聚类。算法的主要流程为：

1. 扫描数据库，建立一棵存放于内存的CF-Tree，它可以被看作数据的多层压缩，试图保留数据的内在聚类结构；
2. 采用某个选定的聚类算法（如K-means或者凝聚算法），对CF树的叶节点进行聚类，把稀疏的簇当作离群点删除，而把更稠密的簇合并为更大的簇。

（1）构造CF-Tree

聚类特征CF用一个三元组$(N,LS,SS)$概括描述各簇的信息。

• $N$是簇中数据点的数量；
• $LS$是各点的线性求和；\(\sum_n x_n\)
• $SS$是各点的平方和。\(\sum_n \mid\mid x_n \mid\mid^2\)

CF具有可加性:

CF结构概括了簇的基本信息，并且是高度压缩的，它存储了小于实际数据点的聚类信息。通过CF可以计算簇的信息：

• 簇质心：\(x_0 = \frac{LS}{N}\)
• 簇半径：簇中点到质心的平均距离；\(R = \sqrt{\frac{\sum_n (x_n-x_0)^2}{N}} = \sqrt{\frac{NSS-LS^2}{N^2}}\)
• 簇直径：簇中两两数据点的平均距离；\(D = \sqrt{\frac{\sum_{i,j} (x_i-x_j)^2}{N(N-1)}} = \sqrt{\frac{2NSS-2LS^2}{N(N-1)}}\)

通过CF还可以计算簇间距离：

• 中心点欧基里得距离（centroid Euclidian distance）：\(\sqrt{(\frac{LS_1}{N_1}-\frac{LS_2}{N_2})^2}\)
• 中心点曼哈顿距离（centroid Manhattan distance）：\(\mid \frac{LS_1}{N_1}-\frac{LS_2}{N_2}\mid\)
• 簇连通平均距离（average inter-cluster distance）：\(\sqrt{\frac{SS_1}{N_1}-2\frac{LS_1^\top}{N_1}\frac{LS_2}{N_2}+\frac{SS_2}{N_2}}\)
• 全连通平均距离（average intra-cluster distance）：\(\sqrt{\frac{2(N_1+N_2)(SS_1+SS_2)-2(LS_1+LS_2)^2}{(N_1+N_2)(N_1+N_2-1)}}\)
• 散布恶化距离（variance increase distance）：\(\sqrt{\frac{(N_1+N_2)(SS_1+SS_2)-(LS_1+LS_2)^2}{(N_1+N_2)^2}}-\sqrt{\frac{N_1SS_1-LS_1^2}{N_1^2}}-\sqrt{\frac{N_2SS_2-LS_2^2}{N_2^2}}\)

定义CF Tree的重要参数：

• 枝平衡因子$β$：表示枝节点最大的分支数，所有内部节点的分支不得多于 $β$ 个；
• 叶平衡因子$λ$：表示叶节点允许包含的最大CF数；
• 空间阈值$τ$：表示叶节点每个CF的最大样本半径或直径，所有类簇的半径不得大于$τ$。

CF Tree的建立过程如下：

• 初始化枝平衡因子$β$，叶平衡因子$λ$和空间阈值$τ$；
• 在数据库中逐个选取数据点，将数据点插入到CF Tree上：
  1. 引入一个新数据，从根节点向下寻找距离最近的叶节点和叶节点里最近的CF节点；
  2. 判断新数据是否属于该CF（满足空间阈值$τ$和叶平衡因子$λ$约束），若满足则更新路径上所有的CF；
  3. 否则判断新数据是否可以构造一个新的CF（满足枝平衡因子$β$约束），若满足则将新的CF节点放入这个叶节点，并更新路径上所有的CF；
  4. 否则将当前叶节点划分为两个新叶节点，选择旧叶节点中所有CF里距离最远的两个CF，作为两个新叶节点的第一个CF节点。将其他元组和新样本元组按照距离远近原则放入对应的叶节点。依次向上检查父节点是否也要分裂，如果需要按和叶节点分裂方式相同。

（2）Birch算法流程

Birch算法的完整流程：

1. 将所有的样本依次读入，在内存中建立一棵CF Tree。
2. （可选）CF Tree瘦身：将CF Tree进行筛选，去除一些异常CF节点，对于一些距离非常近的元组进行合并。
3. （可选）二度聚类：利用其它聚类算法（比如K-Means）对所有的CF元组进行聚类，得到一棵比较好的CF Tree。这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点CF个数限制导致的树结构分裂。
4. （可选）聚类精修：利用CF Tree的所有CF节点的质心作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

3. CURE算法

Clustering Using Representative (CURE) 算法是一种凝聚层次聚类，首先把每个数据点看成一个簇，然后将距离最近的簇结合，一直到簇的个数达到要求为止。

不同于质心或者单个点来代表一个类，CURE算法中每个簇有多个代表点，这使得 CURE 算法可以适应非球形的几何形状。代表点的选取：首先选择簇中距离质心最远的点做为第一个点，然后依次选择距离已选到的点最远的点，直到选到$c$个点为止，这些点尽量分散，捕获了簇的形状和大小。

CURE算法还通过“收缩因子”减少离群点对聚类效果的影响。将选取到的代表点根据固定的参数$0≤α≤1$向该簇的质心收缩，距离质心越远的点（例如离群点）的收缩程度越大，因此CURE对离群点不太敏感，这种方法可以有效的降低离群点带来的不利影响。当 $α$ 趋于 $0$ 时，所有的“代表点”都汇聚到质心，算法退化为基于“质心”的聚类(K-means)；当 $α$ 趋于 $1$ 时，“代表点”完全没有收缩，算法退化为基于“全连接”的聚类。在得到收缩后的代表点后，两个簇之间的距离就可以定义为这两个簇中距离最近的两个代表点之间的距离。

4. ROCK算法

ROCK (RObust Clustering using linKs) 属于凝聚型的层次聚类算法，初始状态时每一个样本都是一个簇。在合并两个簇的时候，遵循的原则是簇之间的链接数量最小，而簇内的链接数量最大；优先合并相似度最大的两个簇。

两个点之间的链接 (link)是指两个点具有共同邻居；如果两个样本点的相似度超过阀值$\theta$，则这两个样本点就是邻居。相似度的计算可以选择Jaccard系数或余弦相似度。

ROCK定义的两个簇之间的相似度指标Goodness Measure计算为：

一般取$f(\theta) = \frac{1-\theta}{1+\theta}$。

5. Chameleon算法

Chameleon 算法的思想是首先使用图划分算法将$k$临近图划分为大量相对较小的子簇；然后使用凝聚层次聚类算法基于子簇的相似度反复合并子簇。

合并子簇时，Chameleon 算法同时考虑两个簇之间的距离和簇内各元素之间的距离。如果两个簇的边界距离和各簇内部元素之间的距离大致相同，就考虑将他们合并在一起。

簇的互联性可以用相对互联度（RI）来衡量：

其中$WS(C_i,C_j)$表示将簇$C$划分为两个子簇$C_i,C_j$割边（需要截断的边）的权重和，$WS(C_i)$表示将$C_i$划分为大致相等的两部分的割边的权重和。

簇的邻近性可以用相对近似度（RC）来衡量：

其中$MW(C_i,C_j)$表示将簇$C$划分为两个子簇$C_i,C_j$割边（需要截断的边）的平均权重，$MW(C_i)$表示将$C_i$划分为大致相等的两部分的割边的平均权重。

在反复合并子簇的过程中，RI 和 RC都要满足大于用户指定阈值。若满足条件，则进行合并；若满足条件的子簇有多个，则选择RI最高的子簇进行合并，重复这一过程，直到没有满足条件的子簇为止。