数据挖掘与分析课程笔记（Chapter 14）

数据挖掘与分析课程笔记

• 参考教材：Data Mining and Analysis : MOHAMMED J.ZAKI, WAGNER MEIRA JR.

文章目录

0. 数据挖掘与分析课程笔记（目录）
1. 数据挖掘与分析课程笔记（Chapter 1）
2. 数据挖掘与分析课程笔记（Chapter 2）
3. 数据挖掘与分析课程笔记（Chapter 5）
4. 数据挖掘与分析课程笔记（Chapter 7）
5. 数据挖掘与分析课程笔记（Chapter 14）
6. 数据挖掘与分析课程笔记（Chapter 15）
7. 数据挖掘与分析课程笔记（Chapter 20）
8. 数据挖掘与分析课程笔记（Chapter 21）

---

---

Chapter 14：Hierarchical Clustering 分层聚类

14.1 预备

Def.1 给定数据集 D = { x 1 , x 2 , ⋯   , x n } , ( x i ∈ R d ) \mathbf{D}=\{ \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\},(\mathbf{x}_i\in \mathbb{R}^d) D={x1​,x2​,⋯,xn​},(xi​∈Rd)，$\mathbf{D}$ 的一个聚类是指 $\mathbf{D}$ 的划分 C = { C 1 , C 2 , ⋯   , C k } \mathcal{C}=\{C_1,C_2,\cdots,C_k \} C={C1​,C2​,⋯,Ck​} s.t. $C_i\subseteq \mathbf{D},C_i\cap C_j=\varnothing ,{\cup }_{i=1}^k{C}_i=\mathbf{D}$；

称聚类 A = { A 1 , ⋯   , A r } \mathcal{A}=\{A_1,\cdots,A_r\} A={A1​,⋯,Ar​} 是聚类 B = { B 1 , ⋯   , B s } \mathcal{B}=\{B_1,\cdots,B_s\} B={B1​,⋯,Bs​} 的嵌套，如果 $r>s$，且对于 $\forall A_i\in \mathcal{A}$ ，存在 $B_j\in \mathcal{B}$ 使得 $A_i\subseteq B_j$

$\mathbf{D}$ 的分层聚类是指一个嵌套聚类序列 ${\mathcal{C}}_1,\cdots ,{\mathcal{C}}_n$，其中 C 1 = { { x 1 } , { x 2 } , ⋯   , { x n } } , ⋯   , C n = { { x 1 , x 2 , ⋯   , x n } } \mathcal{C}_1=\{ \{\mathbf{x}_1\},\{\mathbf{x}_2\},\cdots,\{\mathbf{x}_n\}\},\cdots,\mathcal{C}_n=\{\{ \mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\} \} C1​={{x1​},{x2​},⋯,{xn​}},⋯,Cn​={{x1​,x2​,⋯,xn​}}，且 ${\mathcal{C}}_t$ 是 ${\mathcal{C}}_{t+1}$ 的嵌套。

Def.2 分层聚类示图的顶点集是指所有在 ${\mathcal{C}}_1,\cdots ,{\mathcal{C}}_n$ 中出现的元，如果 $C_i\in {\mathcal{C}}_t$ 且 $C_j\in {\mathcal{C}}_{t+1}$ 满足，则 $C_i$ 与 $C_j$ 之间有一条边。

事实：

1. 分层聚类示图是一棵二叉树（不一定，作为假设，假设每层只聚两类），分层聚类与其示图一一对应。
2. 设（即数据点数为 $n$），则所有可能的分层聚类示图数目为 $(2n-3)!!$ （跃乘 $1\times 3\times 5\times \cdots$）

14.2 团聚分层聚类

算法14.1 ：

输入： $\mathbf{D},k$

输出：$\mathcal{C}$

1. C ← { C i = { x i } ∣ x i ∈ D } \mathcal{C} \leftarrow \{C_i=\{\mathbf{x}_i\}|\mathbf{x}_i \in \mathbf{D} \} C←{Ci​={xi​}∣xi​∈D}
2. Δ ← { δ ( x i , x j ) : x i , x j ∈ D } \Delta \leftarrow \{\delta(\mathbf{x}_i,\mathbf{x}_j):\mathbf{x}_i,\mathbf{x}_j \in \mathbf{D} \} Δ←{δ(xi​,xj​):xi​,xj​∈D}
3. repeat
4. ​ 寻找最近的对 $C_i,C_j\in \mathcal{C}$
5. ​ $C_{ij}\leftarrow C_i\cup C_j$
6. ​ C ← ( C ∣ { C i , C j } ) ∪ C i j \mathcal{C}\leftarrow (\mathcal{C} | \{C_i,C_j \}) \cup {C_{ij}} C←(C∣{Ci​,Cj​})∪Cij​
7. ​ 根据 $\mathcal{C}$ 更新距离矩阵 $\Delta$
8. Until $|\mathcal{C}|=k$

问题：如何定义/计算 $C_i,C_j$ 的距离，即 $\delta (C_i,C_j)$ ?

$\delta (C_i,C_j)$ 有以下五种不同方式：

1. 简单连接： δ ( C i , C j ) : = min ⁡ { δ ( x , y ) ∣ x ∈ C i , y ∈ C j } \delta(C_i,C_j):= \min \{\delta(\mathbf{x},\mathbf{y}) | \mathbf{x} \in C_i, \mathbf{y} \in C_j\} δ(Ci​,Cj​):=min{δ(x,y)∣x∈Ci​,y∈Cj​}

2. 完全连接： δ ( C i , C j ) : = max ⁡ { δ ( x , y ) ∣ x ∈ C i , y ∈ C j } \delta(C_i,C_j):= \max \{\delta(\mathbf{x},\mathbf{y}) | \mathbf{x} \in C_i, \mathbf{y} \in C_j\} δ(Ci​,Cj​):=max{δ(x,y)∣x∈Ci​,y∈Cj​}

3. 组群平均：$\delta (C_i,C_j):=\frac{\sum _{\mathbf{x}\in C_i}\sum _{\mathbf{y}\in C_j}\delta (\mathbf{x},\mathbf{y})}{n_i\cdot n_j},n_i=|C_i|,n_j=|C_j|$

4. 均值距离：$\delta (C_i,C_j):=||{\mathbf{\mu }}_i-{\mathbf{\mu }}_j|{|}^2,{\mathbf{\mu }}_i=\frac{1}{n}\sum _{\mathbf{x}\in C_i}\mathbf{x},{\mathbf{\mu }}_j=\frac{1}{n}\sum _{\mathbf{y}\in C_j}\mathbf{y}$

5. 极小方差：对任意 $C_i$，定义平方误差和 $SS{E}_i=\sum _{\mathbf{x}\in C_i}||\mathbf{x}-{\mathbf{\mu }}_i|{|}^2$

   对 $C_i,C_j,SS{E}_{ij}:=\sum _{\mathbf{x}\in C_i\cup C_j}||\mathbf{x}-{\mathbf{\mu }}_{ij}|{|}^2$，其中 ${\mathbf{\mu }}_{ij}:=\frac{1}{n_i+n_j}\sum _{\mathbf{x}\in C_i\cup C_j}\mathbf{x}$

   $\delta (C_i,C_j):=SS{E}_{ij}-SS{E}_i-SS{E}_j$

证明：$\delta (C_i,C_j)=\frac{n_i{n}_j}{n_i+n_j}||{\mathbf{\mu }}_i-{\mathbf{\mu }}_j|{|}^2$

简记：$C_{ij}:=C_i\cup C_j,n_{ij}:=n_i+n_j$

注意：$C_i\cap C_j=\varnothing$，故 $|C_{ij}|=n_i+n_j$
δ ( C i , C j ) = ∑ z ∈ C i j ∥ z − μ i j ∥ 2 − ∑ x ∈ C i ∥ x − μ i ∥ 2 − ∑ y ∈ C j ∥ y − μ j ∥ 2 = ∑ z ∈ C i j z T z − n i j μ i j T μ i j − ∑ x ∈ C i x T x + n i μ i T μ i − ∑ y ∈ C j y T y + n j μ j T μ j = n i μ i T μ i + n j μ j T μ j − ( n i + n j ) μ i j T μ i j

δ(Ci​,Cj​)​=z∈Cij​∑​∥ ∥​z−μij​∥ ∥​2−x∈Ci​∑​∥x−μi​∥2−y∈Cj​∑​∥ ∥​y−μj​∥ ∥​2=z∈Cij​∑​zTz−nij​μijT​μij​−x∈Ci​∑​xTx+ni​μiT​μi​−y∈Cj​∑​yTy+nj​μjT​μj​=ni​μiT​μi​+nj​μjT​μj​−(ni​+nj​)μijT​μij​​
注意到：${\mathbf{\mu }}_{ij}=\frac{1}{n_{ij}}\sum _{\mathbf{z}\in C_{ij}}\mathbf{z}=\frac{1}{n_i+n_j}(\sum _{\mathbf{x}\in C_i}\mathbf{x}+\sum _{\mathbf{y}\in C_j}\mathbf{y})=\frac{1}{n_i+n_j}(n_i{\mathbf{\mu }}_i+n_j{\mathbf{\mu }}_j)$

故：${\mathbf{\mu }}_{ij}^T{\mathbf{\mu }}_{ij}=\frac{1}{{\left(n_i+n_j\right)}^2}\left(n_i^2{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i+2n_i{n}_j{\mathbf{\mu }}_i^T{\mathbf{\mu }}_j+n_j^2{\mathbf{\mu }}_j^T{\mathbf{\mu }}_j\right)$
δ ( C i , C j ) = n i μ i T μ i + n j μ j T μ j − 1 ( n i + n j ) ( n i 2 μ i T μ i + 2 n i n j μ i T μ j + n j 2 μ j T μ j ) = n i ( n i + n j ) μ i T μ i + n j ( n i + n j ) μ j T μ j − n i 2 μ i T μ i − 2 n i n j μ i T μ j − n j 2 μ j T μ j n i + n j = n i n j ( μ i T μ i − 2 μ i T μ j + μ j T μ j ) n i + n j = ( n i n j n i + n j ) ∥ μ i − μ j ∥ 2

δ(Ci​,Cj​)​=ni​μiT​μi​+nj​μjT​μj​−(ni​+nj​)1​(ni2​μiT​μi​+2ni​nj​μiT​μj​+nj2​μjT​μj​)=ni​+nj​ni​(ni​+nj​)μiT​μi​+nj​(ni​+nj​)μjT​μj​−ni2​μiT​μi​−2ni​nj​μiT​μj​−nj2​μjT​μj​​=ni​+nj​ni​nj​(μiT​μi​−2μiT​μj​+μjT​μj​)​=(ni​+nj​ni​nj​​)∥ ∥​μi​−μj​∥ ∥​2​
问题：如何快速计算算法14.1 第7步：更新矩阵？

☆ Lance–Williams formula
δ ( C i j , C r ) = α i ⋅ δ ( C i , C r ) + α j ⋅ δ ( C j , C r ) + β ⋅ δ ( C i , C j ) + γ ⋅ ∣ δ ( C i , C r ) − δ ( C j , C r ) ∣

δ(Cij​,Cr​)=αi​⋅δ(Ci​,Cr​)+αj​⋅δ(Cj​,Cr​)+β⋅δ(Ci​,Cj​)+γ⋅∣δ(Ci​,Cr​)−δ(Cj​,Cr​)∣​

Proof:

1. 简单连接
   δ ( C i j , C r ) = min ⁡ { δ ( x , y ) ∣ x ∈ C i j , y ∈ C r } = min ⁡ { δ ( C i , C r ) , δ ( C j , C r ) } a = a + b − ∣ a − b ∣ 2 , b = a + b + ∣ a − b ∣ 2

   δ(Cij,Cr)=min{δ(x,y)|x∈Cij,y∈Cr}=min{δ(Ci,Cr),δ(Cj,Cr)}" role="presentation">δ(Cij,Cr)=min{δ(x,y)|x∈Cij,y∈Cr}=min{δ(Ci,Cr),δ(Cj,Cr)}$$\begin{array}{rl}\delta \left(C_{ij},C_r\right)& =min\{\delta (\mathbf{x},\mathbf{y})|\mathbf{x}\in C_{ij},\mathbf{y}\in C_r\}\\ & =min\{\delta (C_i,C_r),\delta (C_j,C_r)\}\end{array}$$
   \\ a=\frac{a+b-|a-b|}{2},b=\frac{a+b+|a-b|}{2} δ(Cij​,Cr​)​=min{δ(x,y)∣x∈Cij​,y∈Cr​}=min{δ(Ci​,Cr​),δ(Cj​,Cr​)}​a=2a+b−∣a−b∣​,b=2a+b+∣a−b∣​
   

2. 完全连接

   见上图

3. 组群平均
   δ ( C i j , C r ) = ∑ x ∈ C i ∪ C j ∑ y ∈ C r δ ( x , y ) ( n i + n j ) ⋅ n r = ∑ x ∈ C i ∑ y ∈ C r δ ( x , y ) + ∑ x ∈ C j ∑ y ∈ C r δ ( x , y ) ( n i + n j ) ⋅ n r = n i n r δ ( C i , C r ) + n j n r δ ( C j , C r ) ( n i + n j ) ⋅ n r = n i δ ( C i , C r ) + n j δ ( C j , C r ) ( n i + n j )

   δ(Cij,Cr)=∑x∈Ci∪Cj∑y∈Crδ(x,y)(ni+nj)⋅nr=∑x∈Ci∑y∈Crδ(x,y)+∑x∈Cj∑y∈Crδ(x,y)(ni+nj)⋅nr=ninrδ(Ci,Cr)+njnrδ(Cj,Cr)(ni+nj)⋅nr=niδ(Ci,Cr)+njδ(Cj,Cr)(ni+nj)" role="presentation">δ(Cij,Cr)=∑x∈Ci∪Cj∑y∈Crδ(x,y)(ni+nj)⋅nr=∑x∈Ci∑y∈Crδ(x,y)+∑x∈Cj∑y∈Crδ(x,y)(ni+nj)⋅nr=ninrδ(Ci,Cr)+njnrδ(Cj,Cr)(ni+nj)⋅nr=niδ(Ci,Cr)+njδ(Cj,Cr)(ni+nj)$$\begin{array}{rl}\delta \left(C_{ij},C_r\right)& =\frac{\sum _{\mathbf{x}\in C_i\cup C_j}\sum _{\mathbf{y}\in C_r}\delta (\mathbf{x},\mathbf{y})}{(n_i+n_j)\cdot n_r}\\ & =\frac{\sum _{\mathbf{x}\in C_i}\sum _{\mathbf{y}\in C_r}\delta (\mathbf{x},\mathbf{y})+\sum _{\mathbf{x}\in C_j}\sum _{\mathbf{y}\in C_r}\delta (\mathbf{x},\mathbf{y})}{(n_i+n_j)\cdot n_r}\\ & =\frac{n_i{n}_r\delta (C_i,C_r)+n_j{n}_r\delta (C_j,C_r)}{(n_i+n_j)\cdot n_r}\\ & =\frac{n_i\delta (C_i,C_r)+n_j\delta (C_j,C_r)}{(n_i+n_j)}\end{array}$$
   δ(Cij​,Cr​)​=(ni​+nj​)⋅nr​x∈Ci​∪Cj​∑​y∈Cr​∑​δ(x,y)​=(ni​+nj​)⋅nr​x∈Ci​∑​y∈Cr​∑​δ(x,y)+x∈Cj​∑​y∈Cr​∑​δ(x,y)​=(ni​+nj​)⋅nr​ni​nr​δ(Ci​,Cr​)+nj​nr​δ(Cj​,Cr​)​=(ni​+nj​)ni​δ(Ci​,Cr​)+nj​δ(Cj​,Cr​)​​

4. 均值距离：作业

5. 极小方差

   基于均值距离的结论再代入 $\delta (C_i,C_j)=\frac{n_i{n}_j}{n_i+n_j}||{\mathbf{\mu }}_i-{\mathbf{\mu }}_j|{|}^2$

事实：算法14.1 的复杂度为 $O(n^2\log n)$