第14章 聚类方法
文档摘要
第14章 聚类方法 习题14.1   试写出分裂聚类算法，自上而下地对数据进行聚类，并给出其算法复杂度。 解答： 解答思路： 给出一般聚类方法概述 给出分裂聚类的定义 给出分裂聚类预先确定的要素 写出分裂聚类算法，并计算复杂度 自编程实现分裂聚类算法 解答步骤： 第1步：一般聚类方法概述   根据书中第14章的聚类方法介绍：   聚类是针对给定的样本，依据它们的特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是给定样本集合的一个子集。直观上，相似的样本聚集在相同的类，不相似的样本分散在不同的类。常用的聚类算法包括层次聚类和$k$均值聚类。层次聚类又分为聚合（自下而上）和分裂（自上而下）两种方法。
第14章 聚类方法
习题14.1
试写出分裂聚类算法，自上而下地对数据进行聚类，并给出其算法复杂度。
解答：
解答思路：
- 给出一般聚类方法概述
- 给出分裂聚类的定义
- 给出分裂聚类预先确定的要素
- 写出分裂聚类算法，并计算复杂度
- 自编程实现分裂聚类算法
解答步骤：
第1步：一般聚类方法概述
根据书中第14章的聚类方法介绍：
聚类是针对给定的样本，依据它们的特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是给定样本集合的一个子集。直观上，相似的样本聚集在相同的类，不相似的样本分散在不同的类。常用的聚类算法包括层次聚类和k均值聚类。层次聚类又分为聚合（自下而上）和分裂（自上而下）两种方法。
第2步：分裂聚类的定义
根据书中第14章的分裂聚类介绍：
分裂法开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。
第3步：分裂聚类预先确定的要素
分裂聚类的具体过程如下：对于给定的样本集合，开始将所有样本分到一个类，然后按照一定分裂方法，例如类中距离最大，将最满足规则条件的样本分到两个新的类；如此反复进行，每次减少剩余未分类的样本，直到满足停止条件，如所有样本都分到了对应的类中。
由此可知，分裂聚类需要预先确定下面三个要素：
（1）选择要分裂的类方法；
（2）分裂类的方法；
（3）停止条件。
根据这些要素的不同组合，就可以构成不同的分裂聚类方法。选择要分裂的类的方法可以是选择最大直径的类、样本最多的类、最大均值的类、最大SSE的类。分裂类的方法可以是使用贪心算法选择新类中心、K-means算法、Ward方法。停止条件可以是每个类包含一个样本、类的个数达到阈值。
第4步：写出分裂聚类算法，并计算复杂度
分裂聚类算法
输入：n个样本组成的样本集合及设定的样本类别数k；
输出：满足设定的样本类别数的样本集合的一个层次化聚类。
（1）构造1个类，该类包含全部样本。
（2）计算n个样本两两之间的欧氏距离\{d_{ij}\}。
（3）分裂类中距离最大的两个样本，将其分到两个类，并设置为各自的类中心。
（4）计算未分裂的样本与目前各个类中心的距离，分裂类中距离最大的样本作为新的类中心，构造一个新类。
（5）如果类的个数满足设定的样本类别数k，则继续执行第（6）步，否则回到第（4）步继续分裂样本。
（6）根据当前的类中心，按照最近邻的原则对整个数据集进行分类。
计算复杂度：
- 时间复杂度为O(k n^2m)：整个算法计算过程中需要计算两两样本之间的复杂度，设m是样本的维度，总体样本为n个，则时间复杂度为O(n^2 m)；设定的样本类别数为k，则需要重复k次，故时间复杂度为O(k n^2 m)。
- 空间复杂度为O(n^2)：需要一个n \times n的矩阵保存两两样本间的距离。
第4步：自编程实现分裂聚类算法
import numpy as np class DivisiveClustering: def __init__(self, num_class): # 聚类类别个数 self.num_class = num_class # 聚类数据集 self.cluster_data = [] if num_class > 1: self.cluster_data = [[] for _ in range(num_class)] def fit(self, data): """ :param data: 数据集 """ num_sample = data.shape[0] if self.num_class == 1: # 如果只设定了一类，将所有数据放入到该类中 for d in data: self.cluster_data.append(d) else: # (1) 构造1个类，该类包含全部样本 # 初始化类中心 class_center = [] # (2) 计算n个样本两两之间的欧氏距离 distance = np.zeros((num_sample, num_sample)) for i in range(num_sample): for j in range(i + 1, num_sample): distance[j, i] = distance[i, j] = np.linalg.norm(data[i, :] - data[j, :], ord=2) # (3) 分裂距离最大的两个样本，并设置为各自的类中心 index = np.where(np.max(distance) == distance) class_1 = index[1][0] class_2 = index[1][1] # 记录已经分裂完成的样本 finished_data = [class_1, class_2] class_center.append(data[class_1, :]) class_center.append(data[class_2, :]) num_class_temp = 2 # (5) 判断类的个数是否满足设定的样本类别数 while num_class_temp != self.num_class: # (4.1) 计算未分裂的样本与目前各个类中心的距离 data2class_distance = np.zeros((num_sample, 1)) for i in range(num_sample): # 计算样本到各类中心的距离总和 data2class_sum = 0 for j, center_data in enumerate(class_center): if i not in finished_data: data2class_sum += np.linalg.norm(data[i, :] - center_data) data2class_distance[i] = data2class_sum # (4.2) 分裂类间距离最大的样本作为新的类中心，构造一个新类 class_new_index = np.argmax(data2class_distance) num_class_temp += 1 finished_data.append(class_new_index) # 添加到类中心集合中 class_center.append(data[class_new_index, :]) # 根据当前的类中心，按照最近邻的原则对整个数据集进行分类 for i in range(num_sample): data2class_distance = [] for j, center_data in enumerate(class_center): # 计算每个样本到类中心的距离 data2class_distance.append(np.linalg.norm(data[i, :] - center_data)) # 将样本划分到最近的中心的类中 label = np.argmin(data2class_distance) self.cluster_data[label].append(data[i, :])
# 使用书中例14.2的样本数据集 dataset = np.array([[0, 2], [0, 0], [1, 0], [5, 0], [5, 2]]) num_class = 2 divi_cluster = DivisiveClustering(num_class=num_class) divi_cluster.fit(dataset) print("分类数:", num_class) for i in range(num_class): print(f"class_{i}:", divi_cluster.cluster_data[i])
分类数: 2 class_0: [array([0, 0]), array([1, 0]), array([5, 0])] class_1: [array([0, 2]), array([5, 2])]
习题14.2
证明类或簇的四个定义中，第一个定义可推出其他三个定义。
解答：
解答思路：
- 给出定义14.5
- 给出定义14.6，并由定义14.5推导定义14.6
- 给出定义14.7，并由定义14.5推导定义14.7
- 给出定义14.8，并由定义14.5推导定义14.8
解答步骤：
第1步：定义14.5
根据书中第14.1.2节的定义14.5：
用G表示类或簇，用x_i,x_j表示类中的样本，N_G表示G中样本的个数，用d_{ij}表示样本x_i与样本x_j之间的距离。
定义14.5 设T为给定的正数，若集合G中任意两个样本x_i, x_j，有
d_{ij} \leqslant T
d_{ij} \leq T
D_G = \max \limits_{x_i, x_j \in G} d_{ij} \leqslant T
d_{ij} \leqslant D_G \leqslant T
\frac{1}{n_G - 1} \sum_{x_j \in G} d_{ij} \leqslant T
\sum_{x_j \in G} d_{ij} \leqslant (n_G - 1) T
\frac{1}{n_G - 1} \sum_{x_j \in G} d_{ij} \leqslant T
\frac{1}{n_G(n_G - 1)}\sum_{x_i \in G}\sum_{x_j \in G} d_{ij} \leqslant T \
d_{ij} \leqslant V
\sum_{x_i \in G} \sum_{x_j \in G} d_{ij} \leqslant n_G(n_G - 1) T
\frac{1}{n_G(n_G - 1)} \sum_{x_i \in G}\sum_{x_j \in G} d_{ij} \leqslant T \
d_{ij} \leqslant V
\begin{aligned}
C^*
&= \arg \min \limits_{C} W(C) \
&= \arg \min \limits_{C} \sum_{l=1}^k \sum_{C(i)=l} | x_i - \bar{x}_l |^2
\end{aligned}
S(n,k) = \frac{1}{k!} \sum_{l=0}^k (-1)^{k-l} \left( \begin{array}{c} k \ l \end{array} \right) l^n \tag{14.21}
T(n, k) = k!S(n, k)
H(x) = \left( x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots \right)^k = (e^x - 1)^k
\begin{aligned}
G(x)
&= P(n, 0) x^0 + P(n, 1) x^1 + P(n, 2) x^2 + \cdots + P(n, n) x^n \
&= \sum_{k=0}^{\infty} \frac{(n-k)!}{n!} x^k
\end{aligned}
C(n, 0) x^0 + C(n, 1) x^1 + C(n, 2) x^2 + \cdots + C(n, n) x^n
P(n, r) = C(n, r)P(r, r) = C(n, r) r!
P(n, 0) \frac{x^0}{0!} + P(n, 1) \frac{x^1}{1!} + P(n, 2) \frac{x^2}{2!} + \cdots + P(n, n) \frac{x^n}{n!} = (1 + x)^n
H(x) = a_0 \frac{x^0}{0!} + a_1 \frac{x^1}{1!} + a_2 \frac{x^2}{2!} + \cdots + a_k \frac{x^k}{k!} = \sum_k a_k \frac{x^k}{k!}
T(n, k) = k!S(n, k)
H(x) = \left( x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots \right)^k = (e^x - 1)^k
H(x) = \sum_{i=0}^k \left( \begin{array}{c} k \ i \end{array} \right) (-1)^i e^{(k-i) x}
\begin{aligned}
H(x)
&= \sum_{i=0}^k \left( \begin{array}{c} k \ i \end{array} \right) (-1)^i \sum_{n=0}^{\infty} \frac{1}{n!} (k-i)^n x^n \
&= \sum_{n=0}^{\infty} \frac{x^n}{n!} \sum_{i=0}^k (-1)^i \left( \begin{array}{c} k \ i \end{array} \right) (k-i)^n
\end{aligned}
T(n, k) = \sum_{i=0}^k (-1)^i \left( \begin{array}{c} k \ i \end{array} \right) (k-i)^n
S(n, k) = \frac{1}{k!} \sum_{i=0}^k (-1)^i \left( \begin{array}{c} k \ i \end{array} \right) (k-i)^n
S(n,k) = \frac{1}{k!} \sum_{l=0}^k (-1)^{k-l} \left( \begin{array}{c} k \ l \end{array} \right) l^n
\min_C \sum_{l=1}^k \sum_{C(i) = l} | x_i - m_l |^2
\min \limits_{m_1,...m_k} \sum_{l=1}^k \sum_{C(i)=l} | x_i - m_l |^2
m_l = \frac{1}{n_l} \sum_{C(i) = l} x_i, \quad l = 1, \cdots, k
P(y|\theta) = \sum_{k=1}^K \alpha_k \phi(y | \theta_k)
\phi(y | \theta_k) = \frac{1}{\sqrt{2 \pi} \sigma_k} \exp \left( - \frac{(y - u_k)^2}{ 2 \sigma_k^2} \right)
P(y|\theta) = \sum_{k=1}^K \alpha_k \phi(y | \theta_k)
\begin{array}{l}
\gamma_{jk} = \left { \begin{array}{ll}
1, & \text{第}j \text{个观测来自第}k \text{个分模型} \
0, & \text{否则}
\end{array} \right. \
j = 1,2,\cdots, N; \quad k = 1,2,\cdots, K
\end{array}
\log P(y, \gamma | \theta) = \sum_{k=1}^K \left { n_k \log \alpha_k + \sum_{j=1}^N \gamma_{jk} \left[ \log \left( \frac{1}{\sqrt{2 \pi}} \right) - \log \sigma_k - \frac{1}{2 \sigma_k^2} (y_j - u_k)^2 \right] \right }
\hat{\gamma}{jk} = \frac{\alpha_k \gamma(y_j | \theta_k)}{\displaystyle \sum{k=1}^K \alpha_k \gamma(y_j | \theta_k)}, \quad j=1,2,\cdots, N; \quad k = 1,2,\cdots, K
\hat{u}k = \frac{\displaystyle \sum{j=1}^N \hat{\gamma}{jk} y_j}{\displaystyle \sum{j=1}^N \hat{\gamma}_{jk}}, \quad k = 1,2,\cdots, K \
\hat{\sigma}^2 = \frac{\displaystyle \sum_{j=1}^N \hat{\gamma}_{jk} (y_j - u_k)^2}{\displaystyle \sum_{j=1}^N \hat{\gamma}_{jk}}， \quad k = 1,2,\cdots, K \
\hat{\alpha}_k = \frac{\displaystyle \sum_{j=1}^N \hat{\gamma}_{jk} }{N}, \quad k = 1,2,\cdots, K