[人工智能]数据挖掘与分析课程笔记（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?\mathbf{D},C_i\cap C_j=?,{\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$，且对于 $?A_i\in \mathcal{A}$ ，存在 $B_j\in \mathcal{B}$ 使得 $A_i?B_j$

$\mathbf{D}$ 的分层聚类是指一个嵌套聚类序列 ${\mathcal{C}}_1,?,{\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,?,{\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 ?$）

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?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=?$，故 $|C_{ij}|=n_i+n_j$
$$\begin{array}{rl}\delta \left(C_i,C_j\right)& =\sum _{\mathbf{z}\in C_{ij}}{\Vert \mathbf{z}?{\mathbf{\mu }}_{ij}\Vert }^2?\sum _{\mathbf{x}\in C_i}{\Vert \mathbf{x}?{\mathbf{\mu }}_i\Vert }^2?\sum _{\mathbf{y}\in C_j}{\Vert \mathbf{y}?{\mathbf{\mu }}_j\Vert }^2\\ & =\sum _{\mathbf{z}\in C_{ij}}{\mathbf{z}}^T\mathbf{z}?n_{ij}{\mathbf{\mu }}_{ij}^T{\mathbf{\mu }}_{ij}?\sum _{\mathbf{x}\in C_i}{\mathbf{x}}^T\mathbf{x}+n_i{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i?\sum _{\mathbf{y}\in C_j}{\mathbf{y}}^T\mathbf{y}+n_j{\mathbf{\mu }}_j^T{\mathbf{\mu }}_j\\ & =n_i{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i+n_j{\mathbf{\mu }}_j^T{\mathbf{\mu }}_j?\left(n_i+n_j\right){\mathbf{\mu }}_{ij}^T{\mathbf{\mu }}_{ij}\end{array}$$
注意到：${\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)$
$$\begin{array}{rl}\delta \left(C_i,C_j\right)& =n_i{\mathbf{\mu }}_i^T{\mathbf{\mu }}_i+n_j{\mu }_j^T{\mathbf{\mu }}_j?\frac{1}{\left(n_i+n_j\right)}\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)\\ & =\frac{n_i\left(n_i+n_j\right){\mathbf{\mu }}_i^T{\mathbf{\mu }}_i+n_j\left(n_i+n_j\right){\mathbf{\mu }}_j^T{\mathbf{\mu }}_j?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}{n_i+n_j}\\ & =\frac{n_i{n}_j\left({\mathbf{\mu }}_i^T{\mathbf{\mu }}_i?2{\mathbf{\mu }}_i^T{\mathbf{\mu }}_j+{\mathbf{\mu }}_j^T{\mathbf{\mu }}_j\right)}{n_i+n_j}\\ & =\left(\frac{n_i{n}_j}{n_i+n_j}\right){\Vert {\mathbf{\mu }}_i?{\mathbf{\mu }}_j\Vert }^2\end{array}$$
问题：如何快速计算算法14.1 第7步：更新矩阵？

☆ Lance–Williams formula
$$\begin{array}{r}\delta \left(C_{ij},C_r\right)={\alpha }_i?\delta \left(C_i,C_r\right)+{\alpha }_j?\delta \left(C_j,C_r\right)+\\ \beta ?\delta \left(C_i,C_j\right)+\gamma ?\left|\delta \left(C_i,C_r\right)?\delta \left(C_j,C_r\right)\right|\end{array}$$

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 \begin{aligned} \delta\left(C_{i j}, 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{aligned}\\ 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. 组群平均
   $$\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)?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)?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)?n_r}\\ & =\frac{n_i\delta (C_i,C_r)+n_j\delta (C_j,C_r)}{(n_i+n_j)}\end{array}$$

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)$