聚类算法简介

聚类作为无监督学习的重要分支，其目标是将数据集划分为若干个具有相似特征的子集（即簇），使得同一簇内的样本尽可能相近，而不同簇之间的样本差异明显。以下介绍几种主流聚类方法的核心原理与实现方式。

基于划分的聚类方法

K-Means 算法

核心思想：通过最小化簇内平方误差（SSE）将数据划分为 K 个簇，每个簇由其质心（均值）表示。

算法流程：

1. 随机初始化 K 个质心；
2. 将每个数据点分配到距离最近的质心所对应的簇；
3. 重新计算各簇的质心（即该簇所有点的均值）；
4. 重复执行步骤 2 和 3，直至质心不再显著变化或达到最大迭代次数。

局限性：

• 对初始质心的选择敏感；
• 易陷入局部最优解；
• 结果高度依赖于预设的 K 值。

如何确定最佳 K 值？

选择合适的簇数 K 是使用 K-Means 的关键问题之一，常用方法包括肘部法则和轮廓系数法。

1. 肘部图（Elbow Method）
观察不同 K 值下聚类模型的误差平方和（SSE）变化趋势，寻找“拐点”作为理想 K 值。随着 K 增大，SSE 单调递减，但在某个临界点后下降速度明显放缓，形成类似手肘的形状。

SSE 计算公式如下：

SSE = \sum_{i=1}^{k} \sum_{x \in C_i} ||x - \mu_i||^2

其中，\(C_i\) 表示第 i 个簇，\(\mu_i\) 为其质心。

代码示例：

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

sse = []
for k in range(1, 11):
    kmeans = KMeans(n_clusters=k, random_state=42).fit(X)
    sse.append(kmeans.inertia_)

plt.plot(range(1, 11), sse, marker='o')
plt.xlabel('K')
plt.ylabel('SSE')
plt.title('Elbow Method')
plt.show()

2. 轮廓系数（Silhouette Coefficient）
用于衡量样本与其自身簇的紧密程度以及与其他簇的分离程度，取值范围为 [-1, 1]，数值越大表明聚类效果越好。最优 K 值通常对应轮廓系数的最大值。

单一样本 i 的轮廓系数计算公式为：

s(i) = \frac{b(i) - a(i)}{\max\big(a(i), b(i)\big)}

其中：

• \(a(i)\)：样本 i 到其所在簇中其他样本的平均距离，反映簇内紧凑性；
• \(b(i)\)：样本 i 到最近的其他簇中所有样本的平均距离，体现簇间分离度。

K-means++ 改进策略

核心思想：优化初始质心选取过程，降低随机性影响，提升收敛速度与聚类质量。

主要改进：
采用加权概率机制选择初始中心点：首个中心点随机选定；后续每一步中，距离已有中心越远的数据点被选中的概率越高。

若当前已选中心集合为 \(C\)，新中心点 \(x\) 的选择概率为：

P(x) = \frac{D(x)^2}{\sum_{x_i \in X} D(x_i)^2}

其中，\(D(x)\) 表示点 \(x\) 到最近已选中心的距离。

Bisecting K-means（二分 K-means）

核心思想：采用自上而下的分裂策略——从一个包含全部数据的簇开始，每次将一个现有簇用 K-means 分裂成两个子簇（k=2），直到总数达到指定 K 值。通常优先分裂 SSE 最大的簇。

算法步骤：

1. 将所有数据视为一个簇；
2. 当当前簇数量小于 K 时：
   • 对每一个现有簇：
   • 计算其原始 SSE；
   • 对该簇执行 K-means（k=2）得到两个子簇；
   • 计算分裂后两个子簇的总 SSE；
   • 选择能带来最大 SSE 下降（或最小分裂后 SSE 总和）的簇进行实际划分；
3. 重复上述过程直至满足簇数要求。

优势：

• 相比标准 K-Means，对初始中心依赖较小；
• 更适用于存在层次结构的数据场景，如文本文档聚类。

基于密度的聚类方法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

核心思想：根据样本分布的密度来识别簇，能够发现任意形状的聚类，并有效识别噪声点（离群点）。

该方法基于两个关键参数：

• \(\epsilon\)（eps）：邻域半径；
• MinPts：在 \(\epsilon\)-邻域内成为核心点所需的最小点数。

据此定义三类点：

• 核心点：在其 \(\epsilon\)-邻域内至少有 MinPts 个点；
• 边界点：非核心点，但落在某核心点的 \(\epsilon\)-邻域内；
• 噪声点：既不是核心点也不是边界点。

聚类过程通过不断扩展密度可达的点形成簇，天然支持噪声过滤和非凸簇识别。

OPTICS（Ordering Points To Identify the Clustering Structure）

核心思想：是对 DBSCAN 的改进，解决了其对全局参数 \(\epsilon\) 的敏感问题。通过构建“可达性距离”排序，生成一个反映数据密度结构的可视化顺序图，从而支持多密度层次的聚类分析。

相较于 DBSCAN，OPTICS 不直接产生固定簇划分，而是输出一种有序结构，用户可根据此结构提取不同粒度的聚类结果。

层次聚类（Hierarchical Clustering）

该方法通过构建树状结构（称为“树形图” dendrogram）来组织簇，可分为两类：

• 凝聚式（Agglomerative）：自底向上，初始每个点为独立簇，逐步合并最相似的两个簇；
• 分裂式（Divisive）：自顶向下，初始所有点属于同一簇，递归地进行分割。

常用于需要展示数据层级关系的场景，如生物分类、社交网络分析等。

常用距离度量方式

聚类过程中，样本间相似性通常通过距离函数衡量，常见类型包括：

• 欧氏距离（Euclidean Distance）
• 曼哈顿距离（Manhattan Distance）
• 余弦相似度（Cosine Similarity）
• 马氏距离（Mahalanobis Distance）

具体选择应结合数据特性与应用场景。

簇间距离计算方法比较

在层次聚类中，判断两个簇之间的“距离”有多种策略：

• 单链接（Single Linkage）：两簇间最近两点的距离，易产生链式效应；
• 全链接（Complete Linkage）：最远两点距离，倾向于生成紧凑簇；
• 平均链接（Average Linkage）：所有点对间的平均距离，平衡性较好；
• 质心法（Centroid Method）：两簇质心之间的距离；
• Ward 法：最小化合并后的簇内方差增量，适合球形簇。

高斯混合模型（Gaussian Mixture Model, GMM）

GMM 是一种基于概率模型的软聚类方法，假设数据由多个高斯分布混合而成，每个簇对应一个高斯成分。

相比于 K-Means 的硬划分，GMM 提供的是每个样本属于各个簇的概率（隶属度），更具灵活性。

EM 算法（Expectation-Maximization Algorithm）

用于估计 GMM 中的参数（均值、协方差、混合权重），属于迭代优化算法，包含两个步骤：

1. E步（期望步）：给定当前参数，计算每个样本属于各高斯成分的后验概率；
2. M步（最大化步）：利用E步的结果更新模型参数以最大化似然函数。

重复以上两步直至收敛。

GMM 能拟合更复杂的簇形状（如椭圆、倾斜分布），但计算成本较高，且对初值敏感。

基于密度的聚类方法能够有效识别任意形状的簇，并具备噪声点检测能力。该类算法通过设定邻域参数来判断数据点之间的密度关系，进而实现簇的扩展与划分。

算法流程

• 设定两个关键参数：邻域半径（ε）和最小点数（M），用于判断核心点。
• 从满足邻域内点数不少于 M 的核心点出发，逐步扩展其邻域范围，将密度可达的点纳入同一簇中。
• 所有未被归入任何簇的点被视为噪声点。

其中，“密度可达”是指：若某点位于一个核心点的 ε 邻域内，则认为其密度可达。进一步地：

• 若某点自身邻域内的点数 ≥ M，则为核心点；
• 若不是核心点但处于某个核心点的邻域内，则为边界点；
• 否则标记为噪声。

优缺点分析

优点：

• 无需预先指定聚类数量；
• 对异常值或噪声具有较强的鲁棒性。

缺点：

• 需要人为设定 ε 和最小点数 M；
• 对初始参数选择敏感；
• 在处理密度分布不均的数据时效果较差。

由于 DBSCAN 使用统一的 ε 值，在面对多密度场景时存在局限性：

• 当 ε 过小时，稀疏区域中的点难以达到最小点数要求，导致这些区域无法形成有效簇；
• 当 ε 过大时，相邻的高密度簇可能被错误合并为一个簇。

为缓解这一问题，OPTICS（Ordering Points To Identify the Clustering Structure）被提出，旨在解决对输入参数敏感的问题。该方法通过对有限组邻域参数进行聚类分析，获得不同参数下的聚类结构，从而更灵活地揭示数据内在模式。

OPTICS 算法基础概念

核心距离（Core Distance）：
对于给定对象 p 和邻域半径 ε，核心距离表示使 p 成为核心点所需的最小半径 r。数学定义如下：

CD(p, ε) = min{ r | r ≤ ε, |N_r(p)| ≥ MinPts }

其中 N_r(p) 表示以 p 为中心、半径为 r 的邻域中包含的点集，MinPts 为预设阈值。若在 ε 范围内 p 的邻域点数不足 MinPts，则 p 不是核心点，其核心距离无定义，记作 ∞。

可达距离（Reachability Distance）：
对象 q 关于核心点 p 的可达距离定义为：

RD(p, q, ε) = max( CD(p, ε), d(p, q) )

其中 d(p, q) 是 p 与 q 之间的直接距离（如欧氏距离）。若 p 非核心点，则该距离无意义，记为 ∞。

性质说明：

• 可达距离始终大于等于核心距离；
• 利用可达距离可构建“可达性图”（Reachability Plot），直观展示数据点的簇状结构；
• 算法使用优先队列管理可达距离，生成有序输出序列。

核心思想

OPTICS 在 DBSCAN 的基础上进行了优化，引入可达距离排序机制，适用于多密度环境下的聚类任务。它并不直接输出最终簇标签，而是生成一个反映密度结构的排序序列，便于后续按需提取簇。

算法步骤

1. 计算每个点的核心距离与可达距离；
2. 根据可达距离生成排序后的点序列；
3. 结合可视化或设定阈值，从中提取出具体的簇结构。

详细执行过程：

• 初始化：所有点标记为未处理状态，创建空的有序列表和按可达距离排序的优先队列；
• 选取一个未处理的种子点 p，计算其核心距离。若无定义则跳过；否则获取其 ε-邻域内的所有点；
• 将 p 加入有序列表，并为邻域内每个点 q 计算可达距离，更新至优先队列；
• 从队列中取出可达距离最小的点 q，重复上述扩展操作，直至队列为空；
• 最终输出有序点列及其对应的可达距离，形成可达性图，用于分析聚类结构。

该过程能按照局部密度差异自动聚合相似密度的点，而非强制分配类别标签。

以下为 insert_list() 函数的具体定义：

层次聚类（Hierarchical Clustering）

核心思想：
采用树状结构（即树状图）描述数据点间的聚合关系，分为两类主要方式：凝聚式（自底向上）和分裂式（自顶向下）。

凝聚式算法步骤

1. 初始阶段，将每个数据点视为独立的簇；
2. 计算各簇之间的距离（常用单链接、全链接或平均链接）；
3. 合并距离最近的两个簇；
4. 重复第 2 和第 3 步，直到所有点合并为一个簇，或满足停止条件为止。

常用距离度量方式

距离名称	定义	数学表达式（二维空间）	适用场景
欧氏距离	两点之间的直线距离	d = √[(x - x) + (y - y)]	几何空间、聚类分析
曼哈顿距离	两点在各坐标轴上的绝对距离之和	d = |x - x| + |y - y|	网格路径规划、图像处理

在度量空间中，不同的距离度量方法适用于多种数据分析任务。以下是几种常见的距离与相似性度量方式及其应用场景的整理。

切比雪夫距离定义为两点在各个坐标维度上差值的绝对值中的最大值，其公式为：

d = max(|x - x|, |y - y|)

该距离常用于棋盘式移动模拟或图像像素分析等场景，其中移动的最大偏移决定了整体距离。

闵可夫斯基距离是多种距离的广义形式，通过调节参数 p 可以退化为不同具体距离：

d = (|x - x| + |y - y|)/

当 p=1 时，变为曼哈顿距离；当 p=2 时，对应欧氏距离。这种灵活性使其适用于需要动态调整距离计算方式的任务。

p

余弦相似度衡量的是两个向量之间的方向夹角余弦值，表达式如下：

cosθ = (xx + yy) / [√(x + y) × √(x + y)]

尽管它并非严格意义上的距离度量，但广泛应用于文本分类和推荐系统中，用以评估内容间的语义相似性。可通过 1 - cosθ 的转换形式作为距离使用。

1 - cosθ

马氏距离是一种考虑数据分布结构的距离度量，其计算涉及协方差矩阵 Σ 的逆：

d = √[(x - x) Σ (x - x)]

由于对变量间的相关性和尺度差异进行了标准化处理，因此特别适合多元统计分析和异常检测任务，尤其在非独立同分布数据中表现优异。

汉明距离用于比较两个等长字符串，在相同位置上不同字符的数量即为该距离：

d = Σ δ(x ≠ y)

其中 δ 为指示函数，表示是否发生字符差异。此距离在编码理论、DNA序列比对等领域具有重要应用。

杰卡德距离由集合运算得出，定义为 1 减去杰卡德相似系数：

d = 1 - |A ∩ B| / |A ∪ B|

用于衡量两个集合之间的差异程度，常见于集合相似性分析及推荐系统中。

簇间距离计算方法对比

在聚类分析中，常用的簇间距离计算策略包括单链接、全链接和平均链接，各自特性如下表所示：

方法	计算公式	优点	缺点	适用场景
单链接	D(A,B) = min∈, b∈B d(a,b)	能够识别细长或不规则形状的簇；对噪声相对鲁棒	容易产生链式效应（Chaining Effect）	适用于非球形簇结构
全链接	D(A,B) = max∈, b∈B d(a,b)	生成更紧凑的簇，避免链式延伸	对离群点和噪声敏感	适用于球形或密集分布的数据簇
平均链接	D(A,B) = (1 / |A|×|B|) Σ∈ Σ_b∈B d(a,b)	综合单链接与全链接的优点，效果较为均衡	计算开销较大，复杂度较高	通用性强，适用于中等规模数据集

高斯混合模型（GMM）

核心思想：假设观测数据是由多个高斯分布线性组合而成，利用EM算法迭代估计各成分的参数（均值、协方差、权重）。

算法流程：

1. 初始化每个高斯成分的参数。
2. E步：基于当前参数，计算每个样本点属于各高斯分布的后验概率。
3. M步：根据E步结果，重新估计参数以最大化联合似然函数。
4. 重复执行E步与M步，直至参数收敛。

EM算法（期望-最大化）

问题背景：在无监督学习中，观测数据 X 常伴随隐变量 Z，导致直接求解极大似然困难，因需对隐变量积分或求和。

算法框架：EM算法通过交替进行以下两步实现参数优化：

• E步（Expectation）：固定当前参数 θ，计算隐变量的后验分布 p(Z|X, θ)，并求出对数似然关于该分布的条件期望：

Q(θ|θ) = _{Z|X,θ} [log p(X,Z|θ)]

• M步（Maximization）：寻找新参数 θ，使 Q 函数最大化，即 θ = argmax Q(θ|θ)。

通过反复迭代，逐步逼近最优参数估计。

M 步（Maximization）：通过最大化期望函数，得到下一轮迭代的参数估计值：

θ^(t+1) = arg max_θ Q(θ | θ^(t))。

该迭代过程确保对数似然函数在每一步都不减少，最终收敛至局部极大值。

适用范围

EM 算法适用于存在以下情况的模型：

• 模型中包含缺失数据或隐变量，例如聚类中的类别标签、混合模型中的成分指示变量、隐马尔可夫模型中的状态序列等；
• 需要进行极大似然估计（MLE） 或 最大后验估计（MAP） 的生成式模型。

高斯混合模型（Gaussian Mixture Model, GMM）

在 GMM 中，观测数据被认为是由 K 个多元正态分布线性组合生成的结果，其概率密度函数表示为：

p(x) = ∑_k=1^K π_k·(x | μ_k, Σ_k)，

其中，π_k 表示第 k 个高斯分量的混合权重，满足 ∑_k π_k = 1；μ_k 和 Σ_k 分别是第 k 个高斯分布的均值向量与协方差矩阵。

参数估计流程（基于 EM 算法）

由于每个样本所属的具体高斯分量无法直接观测，因此采用 EM 算法进行参数学习。

E 步（Expectation）：计算每个样本 xi 属于第 k 个分量的后验概率，即“软分配”结果：

γ_ik = p(z_i = k | x_i, θ^(t)) = [π_k^(t)·(x_i | μ_k^(t), Σ_k^(t))] / [∑_j=1^K π_j^(t)·(x_i | μ_j^(t), Σ_j^(t))]。

M 步（Maximization）：根据 E 步提供的软分配权重，更新模型参数：

• π_k^(t+1) = (1/N) ∑_i γ_ik，
• μ_k^(t+1) = (∑_i γ_ikx_i) / (∑_i γ_ik)，
• Σ_k^(t+1) = [∑_i γ_ik(x_i - μ_k^(t+1))(x_i - μ_k^(t+1))] / (∑_i γ_ik)。

重复执行 E 步与 M 步，直到对数似然的变化趋于稳定，算法收敛。

软聚类特性

不同于 K-Means 这类硬聚类方法，GMM 提供的是概率形式的聚类归属，即每个样本属于各个簇的概率。这种机制使其能够有效识别非球形、椭圆状分布的簇结构，特别适合处理高维空间中复杂分布的数据。

典型应用场景

应用场景	常用算法	说明
聚类分析	GMM + EM	适用于簇间存在重叠、形状大小不一的情形，如图像分割、用户行为分群等任务
密度估计	GMM	用于构建生成模型、异常检测或概率预测等场景
HMM 参数学习	EM（Baum-Welch 算法）	隐状态不可见时，利用 EM 框架迭代估计转移概率和发射概率
其他生成模型	EM	包括混合朴素贝叶斯、因子分析等，均属于含隐变量的建模范畴，EM 可作为通用求解工具
文本主题建模	变分 EM / 采样 EM	LDA 中的主题为潜在变量，通常借助 EM 类方法进行近似推断

优点

• 通用性强：只要能写出完整数据的似然函数，即可应用 EM 框架，广泛适用于混合模型、HMM、因子分析等多种模型。
• 软分配机制：在 GMM 中提供样本归属的概率输出，有助于表达不确定性，提升聚类结果的解释性与鲁棒性。
• 单调收敛性：每次迭代都保证对数似然不下降，数值稳定性良好。
• 理论基础扎实：基于 Jensen 不等式的数学推导，具有严谨的统计学依据。

缺点与局限性

• 易陷入局部最优：EM 算法仅能保证收敛到局部极大值，在多峰似然函数下容易陷入次优解，常需配合多次随机初始化或模型选择策略以缓解此问题。
• 计算开销较大：每轮迭代需计算所有样本对所有分量的后验概率，时间复杂度约为 O(NKD)，其中 D 为特征维度，因此在大规模或高维数据上效率较低。
• 对初始值敏感：初始参数的选择显著影响最终结果，不当的初值可能导致收敛缓慢或结果偏差。

模型选择具有挑战性：混合分量数 K 需要人为设定，若选择不当容易引发欠拟合或过拟合问题。为缓解这一难题，通常采用 BIC/AIC 准则、交叉验证方法，或引入非参数贝叶斯技术（例如基于狄利克雷过程的 GMM）来进行辅助判断。

对噪声与离群点较为敏感：异常数据会显著干扰均值与协方差的估计结果，进而降低聚类效果。对此，可通过使用对角协方差结构、稀疏协方差形式，或改用鲁棒性的混合模型来提升模型的抗干扰能力。

初始参数影响显著：不同的初始均值、协方差矩阵或混合权重设置可能导致算法收敛至不同结果。因此，在实际应用中，常结合 K-Means 或层次聚类等方法进行预初始化，以提高收敛稳定性与聚类质量。