如果你对这篇文章感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) 算法要求数据为向量形式，其通过构建 CF-tree (Clustering Feature Tree) 实现可扩展地高效聚类，具体来说，每个簇存储一个三元组：
C
F
=
(
N
,
LS
,
SS
)
,
CF=(N,\text{LS},\text{SS}),
CF=(N,LS,SS),
其中
N
N
N 表示簇中点的数量，矢量
LS
\text{LS}
LS 表示各点线性求和，标量
SS
\text{SS}
SS 表示各点平方和。假设某簇中有
N
N
N 个
D
D
D 维数据点，则矢量
LS
\text{LS}
LS 是个各点的线性求和：
LS
=
∑
n
=
1
N
x
n
.
\text{LS}=\sum_{n=1}^N \boldsymbol{x}_n.
LS=n=1∑Nxn.
标量
SS
\text{SS}
SS 是各数据点的平方和：
SS
=
∑
n
=
1
N
x
n
T
x
n
.
\text{SS}=\sum_{n=1}^N \boldsymbol{x}_n^T \boldsymbol{x}_n.
SS=n=1∑NxnTxn.
有了 CF 特征后，两个簇合并，新的 CF 特征可以直接相加，即：
CF
1
+
CF
2
=
(
N
1
+
N
2
,
LS
1
+
LS
2
,
SS
1
+
SS
2
)
.
\text{CF}_1+\text{CF}_2=(N_1+N_2,\text{LS}_1+\text{LS}_2,\text{SS}_1+\text{SS}_2).
CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2).
由于 CF 很容易地可以合并，CF-tree 可以实现增量式聚类，不断插入新节点。另外，由于数据为向量形式，得到了各点向量求和后，可以方便地计算「簇质心」、「簇半径」、「簇直径」以及各类簇间距离。详细内容可参考「数据挖掘入门笔记 —— BIRCH 聚类」。
层次聚类中有两种常见形式：
在实际应用中，凝聚式层次聚类由于不用事先指定簇个数，因此更为常见，其通常采用下述方式进行：
可以看出，其主要思路是定义簇间距离
d
i
,
j
d_{i,j}
di,j，每次将簇间距离最小的两个簇
i
,
j
i,j
i,j 合并为一个新的簇
i
+
j
i+j
i+j，并更新其它簇到新簇的距离
d
k
,
i
+
j
d_{k,i+j}
dk,i+j。
由于每次重新计算簇间距离非常低效，因此存在 Lance–Williams equation，其定义了一种每次合并后，递归更新簇间距离的范式，如下所示：
d
k
,
i
+
j
=
α
i
d
k
,
i
+
α
j
d
k
,
j
+
β
d
i
,
j
+
γ
∣
d
k
,
i
−
d
k
,
j
∣
.
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}|.
dk,i+j=αidk,i+αjdk,j+βdi,j+γ∣dk,i−dk,j∣.
满足上式的 merge 准则通常较为高效，此处列举一些常见的方式：
Method
α
i
α
i
β
γ
Single linkage
0.5
0.5
0
−
0.5
Complete linkage
0.5
0.5
0
0.5
Group average
n
i
n
i
+
n
j
n
j
n
i
+
n
j
0
0
Weighted group average
0.5
0.5
0
0
Centroid
n
i
n
i
+
n
j
n
j
n
i
+
n
j
−
n
i
⋅
n
j
(
n
i
+
n
j
)
2
0
Ward
n
i
+
n
k
(
n
i
+
n
j
+
n
k
)
n
j
+
n
k
(
n
i
+
n
j
+
n
k
)
−
n
k
(
n
i
+
n
j
+
n
k
)
0
\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}
Method Single linkage Complete linkage Group average Weighted group average Centroid Ward αi0.50.5ni+njni0.5ni+njni(ni+nj+nk)ni+nkαi0.50.5ni+njnj0.5ni+njnj(ni+nj+nk)nj+nkβ0000(ni+nj)2−ni⋅nj(ni+nj+nk)−nkγ−0.50.50000
[IS22 - Andreas Lang] 该篇文章指出 BIRCH 方法计算不稳定，容易导致一些灾难性结果，例如：
如上图所示，使用 BIRCH 对应 CF-tree 计算方差时，得到了负数，致使标准差无法计算。该篇文章还进一步指出，使用下述距离指导簇合并，容易在计算上发生灾难性结果（因为减法的存在，可能导致结果未负，无法开根）：
为改进上述问题，该篇文章提出了 BETULA 方法，其对原始 BIRCH 中每个簇对应的三元组 C F BIRCH = ( N , L S , S S ) CF_{\text{BIRCH}}=(N,LS,SS) CFBIRCH=(N,LS,SS) 进行了修改，提出 C F BETULA = ( n , μ , S ) CF_{\text{BETULA }}=(n,\mu,S) CFBETULA =(n,μ,S)，其中 n n n 对应簇中所有样本权重之和（此处允许不同样本有不同权重）， μ \mu μ 对应均值向量， S S S 对应簇中所有样本偏离均值之和，即 S = ∑ x n x ( x − μ ) 2 S=\sum_x n_x(x-\mu)^2 S=∑xnx(x−μ)2。
与 BIRCH 方法类似，BETULA 也可以通过
C
F
BETULA
CF_{\text{BETULA }}
CFBETULA 快速合并两个簇，即：
n
A
B
=
n
A
+
n
B
μ
A
B
=
μ
A
+
n
B
n
A
B
(
μ
B
−
μ
A
)
S
A
B
=
S
A
+
S
B
+
n
B
(
μ
B
−
μ
A
)
(
μ
B
−
μ
A
B
)
\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}
nAB=nA+nBμAB=μA+nABnB(μB−μA)SAB=SA+SB+nB(μB−μA)(μB−μAB)
随后文章依旧以上述例子举例，尝试说明 BETULA 的计算更加稳定，不容易产生灾难性结果：
最后，该篇文章列举了多种距离度量方式，其中 BETULA 的计算均不涉及减法，因此计算时更稳定：
D
2
(
A
,
B
)
2
=
1
n
A
n
B
∑
x
∈
A
∑
y
∈
B
∥
x
−
y
∥
2
=
1
n
A
n
B
(
n
B
S
S
A
+
n
A
S
S
B
−
2
L
S
A
T
L
S
B
)
(
BIRCH
)
=
1
n
A
S
A
+
1
n
B
S
B
+
∥
μ
A
−
μ
B
∥
2
(
BETULA
)
D
3
(
A
,
B
)
2
=
1
n
A
B
(
n
A
B
−
1
)
∑
x
,
y
∈
A
B
∥
x
−
y
∥
2
=
2
n
A
+
n
B
−
1
(
S
S
A
+
S
S
B
−
1
n
A
+
n
B
∥
L
S
A
+
L
S
B
∥
2
)
(
BIRCH
)
=
2
n
A
B
(
n
A
B
−
1
)
(
n
A
B
(
S
A
+
S
B
)
+
n
A
n
B
∥
μ
A
−
μ
B
∥
2
)
(
BETULA
)
D
4
(
A
,
B
)
2
=
∑
x
∈
A
B
∥
x
−
μ
A
B
∥
2
−
∑
x
∈
A
∥
x
−
μ
A
∥
2
−
∑
x
∈
B
∥
x
−
μ
B
∥
2
=
1
n
A
∥
L
S
A
∥
2
+
1
n
B
∥
L
S
B
∥
2
−
1
n
A
+
n
B
∥
L
S
A
+
L
S
B
∥
2
(
BIRCH
)
=
n
A
n
B
n
A
B
∥
μ
A
−
μ
B
∥
2
(
BETULA
)
R
(
A
,
B
)
2
=
1
n
A
B
∑
x
∈
A
B
∥
x
−
μ
A
B
∥
2
=
1
n
A
B
(
S
S
A
B
−
1
n
A
B
∥
L
S
A
B
∥
2
)
(
BIRCH
)
=
1
n
A
B
S
A
B
(
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}
D2(A,B)2D3(A,B)2D4(A,B)2R(A,B)2=nAnB1x∈A∑y∈B∑∥x−y∥2=nAnB1(nBSSA+nASSB−2LSATLSB)(BIRCH)=nA1SA+nB1SB+∥μA−μB∥2(BETULA)=nAB(nAB−1)1x,y∈AB∑∥x−y∥2=nA+nB−12(SSA+SSB−nA+nB1∥LSA+LSB∥2)(BIRCH)=nAB(nAB−1)2(nAB(SA+SB)+nAnB∥μA−μB∥2)(BETULA)=x∈AB∑∥x−μAB∥2−x∈A∑∥x−μA∥2−x∈B∑∥x−μB∥2=nA1∥LSA∥2+nB1∥LSB∥2−nA+nB1∥LSA+LSB∥2(BIRCH)=nABnAnB∥μA−μB∥2(BETULA)=nAB1x∈AB∑∥x−μAB∥2=nAB1(SSAB−nAB1∥LSAB∥2)(BIRCH)=nAB1SAB(BETULA)
