BIRCH 聚类
BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) 算法要求数据为向量形式，其通过构建 CF-tree (Clustering Feature Tree) 实现可扩展地高效聚类，具体来说，每个簇存储一个三元组：
$$
CF=(N,\text{LS},\text{SS}),
$$
其中 $N$ 表示簇中点的数量，矢量 $\text{LS}$ 表示各点线性求和，标量 $\text{SS}$ 表示各点平方和。假设某簇中有 $N$ 个 $D$ 维数据点，则矢量 $\text{LS}$ 是个各点的线性求和：
$$
\text{LS}=\sum_{n=1}^N \boldsymbol{x}_n.
$$
标量 $\text{SS}$ 是各数据点的平方和：
$$
\text{SS}=\sum_{n=1}^N \boldsymbol{x}_n^T \boldsymbol{x}_n.
$$
有了 CF 特征后，两个簇合并，新的 CF 特征可以直接相加，即：
$$
\text{CF}_1+\text{CF}_2=(N_1+N_2,\text{LS}_1+\text{LS}_2,\text{SS}_1+\text{SS}_2).
$$
由于 CF 很容易地可以合并，CF-tree 可以实现增量式聚类，不断插入新节点。另外，由于数据为向量形式，得到了各点向量求和后，可以方便地计算「簇质心」、「簇半径」、「簇直径」以及各类簇间距离。详细内容可参考「数据挖掘入门笔记 —— BIRCH 聚类」。
Lance–Williams equation
层次聚类中有两种常见形式：
在实际应用中，凝聚式层次聚类由于不用事先指定簇个数，因此更为常见，其通常采用下述方式进行：
可以看出，其主要思路是定义簇间距离 $d_{i,j}$，每次将簇间距离最小的两个簇 $i,j$ 合并为一个新的簇 $i+j$，并更新其它簇到新簇的距离 $d_{k,i+j}$。
由于每次重新计算簇间距离非常低效，因此存在 Lance–Williams equation，其定义了一种每次合并后，递归更新簇间距离的范式，如下所示：
$$
d_{k,i+j}=\alpha_i d_{k,i}+\alpha_j d_{k,j}+\beta d_{i,j}+\gamma|d_{k,i}-d_{k,j}|.
$$
满足上式的 merge 准则通常较为高效，此处列举一些常见的方式：
$$
\begin{array}{|l|c|c|c|c|} \hline \text { Method } & \alpha_i & \alpha_i & \beta & \gamma \\ \hline \text { Single linkage } & 0.5 & 0.5 & 0 & -0.5 \\ \text { Complete linkage } & 0.5 & 0.5 & 0 & 0.5 \\ \text { Group average } & \frac{n_i}{n_i+n_j} & \frac{n_j}{n_i+n_j} & 0 & 0 \\ \text { Weighted group average } & 0.5 & 0.5 & 0 & 0 \\ \text { Centroid } & \frac{n_i}{n_i+n_j} & \frac{n_j}{n_i+n_j} & \frac{-n_i \cdot n_j}{\left(n_i+n_j\right)^2} & 0 \\ \text { Ward } & \frac{n_i+n_k}{\left(n_i+n_j+n_k\right)} & \frac{n_j+n_k}{\left(n_i+n_j+n_k\right)} & \frac{-n_k}{\left(n_i+n_j+n_k\right)} & 0 \\ \hline \end{array}
$$
BETULA 聚类
[IS22 - Andreas Lang] 该篇文章指出 BIRCH 方法计算不稳定，容易导致一些灾难性结果，例如：
如上图所示，使用 BIRCH 对应 CF-tree 计算方差时，得到了负数，致使标准差无法计算。该篇文章还进一步指出，使用下述距离指导簇合并，容易在计算上发生灾难性结果（因为减法的存在，可能导致结果未负，无法开根）：
为改进上述问题，该篇文章提出了 BETULA 方法，其对原始 BIRCH 中每个簇对应的三元组 $CF_{\text{BIRCH}}=(N,LS,SS)$ 进行了修改，提出 $CF_{\text{BETULA }}=(n,\mu,S)$，其中 $n$ 对应簇中所有样本权重之和（此处允许不同样本有不同权重），$\mu$ 对应均值向量，$S$ 对应簇中所有样本偏离均值之和，即 $S=\sum_x n_x(x-\mu)^2$。
与 BIRCH 方法类似，BETULA 也可以通过 $CF_{\text{BETULA }}$ 快速合并两个簇，即：
$$
\begin{aligned} & n_{A B}=n_A+n_B \\ & \mu_{A B}=\mu_A+\frac{n_B}{n_{A B}}\left(\mu_B-\mu_A\right) \\ & S_{A B}=S_A+S_B+n_B\left(\mu_B-\mu_A\right)\left(\mu_B-\mu_{A B}\right) \end{aligned}
$$
随后文章依旧以上述例子举例，尝试说明 BETULA 的计算更加稳定，不容易产生灾难性结果：
最后，该篇文章列举了多种距离度量方式，其中 BETULA 的计算均不涉及减法，因此计算时更稳定：
$$
\begin{aligned} \mathrm{D} 2(A, B)^2 &= \frac{1}{n_A n_B} \sum_{x \in A} \sum_{y \in B}\|x-y\|^2 \\ &=\frac{1}{n_A n_B}\left(n_B S S_A+n_A S S_B-2 L S_A^T L S_B\right) \quad (\text{BIRCH}) \\ &=\frac{1}{n_A} S_A+\frac{1}{n_B} S_B+\left\|\mu_A-\mu_B\right\|^2 \quad (\text{BETULA}) \\ \\ \mathrm{D} 3(A, B)^2&=\frac{1}{n_{A B}\left(n_{A B}-1\right)} \sum_{x, y \in A B}\|x-y\|^2 \\ &=\frac{2}{n_A+n_B-1}\left(S S_A+S S_B-\frac{1}{n_A+n_B}\left\|L S_A+L S_B\right\|^2\right) \quad (\text{BIRCH}) \\ &=\frac{2}{n_{A B}\left(n_{A B}-1\right)}\left(n_{A B}\left(S_A+S_B\right)+n_A n_B\left\|\mu_A-\mu_B\right\|^2\right) \quad (\text{BETULA}) \\ \\ \mathrm{D} 4(A, B)^2&=\sum_{x \in A B}\left\|x-\mu_{A B}\right\|^2-\sum_{x \in A}\left\|x-\mu_A\right\|^2-\sum_{x \in B}\left\|x-\mu_B\right\|^2 \\ &=\frac{1}{n_A}\left\|L S_A\right\|^2+\frac{1}{n_B}\left\|L S_B\right\|^2-\frac{1}{n_A+n_B}\left\|L S_A+L S_B\right\|^2 \quad (\text{BIRCH}) \\ &=\frac{n_A n_B}{n_{A B}}\left\|\mu_A-\mu_B\right\|^2 \quad (\text{BETULA}) \\ \\ \mathrm{R}(A, B)^2&=\frac{1}{n_{A B}} \sum_{x \in A B}\left\|x-\mu_{A B}\right\|^2 \\ &=\frac{1}{n_{A B}}\left(S S_{A B}-\frac{1}{n_{A B}}\left\|L S_{A B}\right\|^2\right) \quad (\text{BIRCH}) \\ &=\frac{1}{n_{A B}} S_{A B} \quad (\text{BETULA}) \end{aligned}
$$
参考资料