10. 聚类分析

# 简介

聚类分析是一种无监督学习技术，旨在根据相似性将数据点分组到不同的簇中。本笔记系统梳理了聚类分析中的关键概念、方法及其优缺点。

# 距离度量

在聚类分析中，距离度量是定义数据点或簇之间“相似性”或“不相似性”的核心。

# 点与点之间的距离

• 欧氏距离 (Euclidean Distance)：最常见的距离度量，基于点在多维空间中的直线距离。
• 相关系数 (Correlation Coefficient)：衡量两个变量之间的线性相关性，常用于高维数据。
• Jaccard 距离 (Jaccard Distance)：主要用于度量两个集合之间的不相似性。
• 汉明距离 (Hamming Distance)：用于度量两个等长字符串或二进制数据之间的差异，即对应位置上不同字符的数量。

# 簇与簇之间的距离

不同的聚类方法在合并或拆分簇时会采用不同的距离计算方式，这通常被称为“链接 (Linkage)”。

• 单链接法 / 最小距离 (Single Linkage / MIN)：

  • 定义：两个簇之间最近的两个点之间的距离。
  • 优点：能自然地处理非球形或不规则形状的簇。
  • 缺点：对异常值和噪声高度敏感，可能导致“链式效应”。

• 全链接法 / 最大距离 (Complete Linkage / MAX)：

  • 定义：两个簇之间最远的两个点之间的距离。
  • 优点：对噪声和异常值的敏感性较低。
  • 缺点：倾向于形成紧凑的球形簇，但可能违反“紧密度”原则（即，簇内某些点可能比其所属簇中的某些点更接近于相邻簇中的点）。

• 平均链接法 / 组均值 (Group Average)：

  • 定义：两个簇中所有点对之间距离的平均值。
  • 优点：是单链接法和全链接法的折衷方案，具有全链接法形成球形簇的特性，且对噪声的敏感性低于单链接法。

• 质心距离法 (Distance Between Centroids)：

  • 定义：两个簇的质心（均值点）之间的距离。
  • 优点：与组均值法类似。

• Ward 链接法 (Ward’s Linkage)：

  • 定义：基于簇内平方误差和（Sum of Squared Error, SSE），选择合并后 SSE 增量最小的两个簇。
  • 优点：类似于 K 均值法的分层模拟，常用于初始化 K 均值算法。如果点之间的不相似度是距离的平方，则与平均链接法有相似的特性。

---

# 层次聚类 (Hierarchical Clustering)

层次聚类通过构建一个嵌套的簇结构来组织数据，生成一个树状图。

# 自底向上法 (Agglomerative)

• 初始化：将每个数据点视为一个单独的簇。
• 迭代：重复合并距离最近的两个簇。
• 终止：所有点最终合并成一个包含所有点的单一簇。

# 自顶向下法 (Divisive)

• 初始化：所有数据点组成一个单一簇。
• 迭代：重复将距离最远的点或子集拆分。
• 终止：每个数据点都成为一个单独的簇。

# 层次聚类的可视化与特点

# 树状图 (Dendrogram)

树状图是一种可视化层次聚类结果的工具。

• 横坐标：表示数据点。
• 纵坐标：表示簇合并时的距离。
• 结构：每个合并点代表一个簇，其高度表示该簇合并的两个子簇之间的距离。

# 优势

• 无需预设簇的数量：可以通过在树状图上“切割”来获得任意数量的簇。
• 直观：能清晰地展示数据点和簇之间的关系。

# 局限性

• 计算复杂度高：通常需要 $O(n^3)$ 的时间复杂度，不适合大规模数据集。
• 不可逆：一旦合并两个簇，就无法撤销。
• 缺乏客观函数：没有直接优化的目标函数。
• 特定方法的问题：不同链接方法对噪声、异常值、非凸形状或不同大小的簇可能存在敏感性。

# 层次聚类的延伸算法

• BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)：使用聚类特征树 (CF-tree) 逐步调整子簇，时间复杂度为 $O(n)$，适用于大规模数据集。
• CHAMELEON：通过动态建模进行层次聚类，能够处理不同形状的簇。

---

# 分区聚类 (Partitioning Clustering)

分区聚类将数据点划分为预定数量（K）的不重叠的簇。

# K 均值算法 (K-Means)

• 核心思想：通过最小化簇内平方误差和（SSE）来寻找最优分区。
• 初始化：随机或通过其他方法选择 K 个初始质心 (centroids)。
• 迭代：
  1. 分配 (Assignment)：将每个数据点分配到最近的质心所在的簇。
  2. 更新 (Update)：重新计算每个簇的质心（即簇内所有点的均值）。
• 终止：质心位置不再变化，或达到最大迭代次数。

# K-Means 的变种

• K 众数算法 (K-Modes)：使用众数 (mode) 代替均值作为簇的中心，适用于处理分类数据。
• K 中心点算法 (K-Medoids)：使用簇内最中心的点（中心点, medoids）代替质心，对异常值不敏感。

# 分区聚类的特点

# K 值的选取

• 手肘法 (Elbow Method)：通过绘制不同 K 值下的 SSE 曲线，选择 SSE 下降速率显著放缓的“拐点”作为最优 K 值。
• 经验法：如 $k\approx \sqrt{n/2}$。
• 交叉验证法 (Cross-Validation)。

# 优势

• 高效：时间复杂度通常为 $O(tkn)$，其中 t 为迭代次数，n 为样本数，k 为簇数。在大多数情况下，该算法比层次聚类更高效。

# 局限性

• 对异常值敏感。
• 受簇形状影响：难以处理不同大小、不同密度或非凸形状的簇。

---

# 基于模型的聚类 (Model-Based Clustering)

基于模型的聚类假定数据是由 K 个概率分布的混合模型生成的。

# 核心思想

• 模型假设：每个簇对应一个概率分布（如多元正态分布），数据点是根据这些分布随机生成的。
• 高斯混合模型 (Gaussian Mixture Model, GMM)：通常采用多元正态分布作为每个簇的概率分布。

$$Y \sim \text{Multinomial}(1, \pi) \\ X \mid Y = l \sim \mathcal{N}(\mu_l, \Sigma_l)\\ \Gamma_{n \times k} = (\gamma_{il}), \quad \gamma_{il} = P(Y_i = l \mid X_i = x_i)$$

其中，$\pi$ 是簇的先验概率，$\mu_l$ 和 $\Sigma_l$ 分别是第 $l$ 个簇的正态分布均值和协方差矩阵，$\gamma_{il}$ 是第 $i$ 个数据点属于第 $l$ 个簇的后验概率。

# 聚类过程：EM 算法

基于模型的聚类通常使用期望最大化（Expectation-Maximization, EM）算法来估计模型参数。

• 初始化：随机初始化模型参数 $\mu, \Sigma, \pi$。
• 期望步 (Expectation Step)：
  • 利用当前参数估计值，计算每个数据点属于每个簇的后验概率 $\hat{\gamma}_{il}$。

  • $$\hat{\gamma}_{il}^{(t+1)} = \frac{\hat{\pi}_l^{(t)} \phi_{\hat{\mu}_l^{(t)}, \hat{\Sigma}_l^{(t)}}(x_i)}{\sum_{j=1}^{k} \hat{\pi}_j^{(t)} \phi_{\hat{\mu}_j^{(t)}, \hat{\Sigma}_j^{(t)}}(x_i)}$$

• 最大化步 (Maximization Step)：
  • 利用后验概率 $\hat{\gamma}_{il}$ 更新模型参数，以最大化似然函数。

  • $$\hat{\pi}_l^{(t+1)} = \frac{\sum_{i=1}^{n} \hat{\gamma}_{il}^{(t+1)}}{n} \\ \hat{\mu}_l^{(t+1)} = \frac{\sum_{i=1}^{n} \hat{\gamma}_{il}^{(t+1)} \cdot x_i}{\sum_{i=1}^{n} \hat{\gamma}_{il}^{(t+1)}} \\ \hat{\Sigma}_l^{(t+1)} = \frac{\sum_{i=1}^{n} \hat{\gamma}_{il}^{(t+1)} \cdot (x_i - \hat{\mu}_l^{(t+1)})(x_i - \hat{\mu}_l^{(t+1)})'}{\sum_{i=1}^{n} \hat{\gamma}_{il}^{(t+1)}}$$

---

# 基于模型的聚类与 LDA 的比较

特性	基于模型的聚类（EM）	线性判别分析（LDA）
任务	无监督聚类：从数据中发现潜在的簇	有监督分类：基于已知类别标签对新数据进行预测
权重	使用后验概率 $\hat{\gamma}_{il}$ 作为软分配权重	使用指示函数 $I(Y_i=l)$ 作为硬分配权重
应用	适用于没有标签的聚类问题	适用于有标签的分类问题

---

注：EM 算法的完整过程（略）。