聚类分析概述

聚类分析是一种无监督学习方法，其核心目标是将数据集中的样本按照某种相似性准则划分为若干组（簇），使得同一簇内的样本尽可能相似，而不同簇间的样本尽可能不同。聚类分析在数学建模、数据挖掘、模式识别等领域具有广泛的应用价值。

基本概念

什么是聚类

聚类（Clustering）是指在没有预先定义类别标签的情况下，根据数据本身的内在结构和特征，将样本集合划分为多个子集的过程。每个子集称为一个簇（Cluster），簇内样本具有较高的相似度，簇间样本具有较大的差异性。

设样本集合为 \( X = {x_1, x_2, \ldots, x_n} \)，其中每个样本 \( x_i \in \mathbb{R}^p \) 是一个 \( p \) 维向量。聚类的目标是找到一个划分：

\[ \mathcal{C} = {C_1, C_2, \ldots, C_K} \]

使得：

\[ \bigcup_{k=1}^{K} C_k = X, \quad C_i \cap C_j = \emptyset \quad (i \neq j) \]

聚类与分类的区别

聚类分析的基本要素

聚类分析通常包含以下几个关键要素：

1. 特征选择与提取：选择合适的特征来表示样本
2. 相似性度量：定义样本间的距离或相似度
3. 聚类算法：选择合适的算法进行划分
4. 结果验证：评估聚类结果的质量
5. 结果解释：对聚类结果给出合理的解释

从优化的角度，聚类可以表述为：给定距离函数 \( d \) 和目标准则 \( J \)，寻找最优划分：

\[ \mathcal{C}^* = \arg\min_{\mathcal{C}} J(\mathcal{C}; X, d) \]

距离与相似度度量

基本定义

距离度量（Distance Metric）是聚类分析的基础。一个合法的距离函数 \( d: \mathbb{R}^p \times \mathbb{R}^p \to \mathbb{R} \) 需要满足以下性质：

1. 非负性：\( d(x, y) \geq 0 \)，且 \( d(x, y) = 0 \) 当且仅当 \( x = y \)
2. 对称性：\( d(x, y) = d(y, x) \)
3. 三角不等式：\( d(x, z) \leq d(x, y) + d(y, z) \)

欧氏距离

欧氏距离（Euclidean Distance）是最常用的距离度量。对于 \( p \) 维向量 \( x \) 和 \( y \)：

\[ d_E(x, y) = \sqrt{\sum_{i=1}^{p} (x_i - y_i)^2} = |x - y|_2 = \sqrt{(x - y)^T (x - y)} \]

标准化欧氏距离引入各维度标准差 \( s_i \)，消除量纲影响：

\[ d_{SE}(x, y) = \sqrt{\sum_{i=1}^{p} \frac{(x_i - y_i)^2}{s_i^2}} \]

特点：直观，符合几何距离概念；对量纲敏感，使用前需标准化；适用于连续型数值变量。

曼哈顿距离

曼哈顿距离（Manhattan Distance），又称城市街区距离或 \( L_1 \) 范数距离：

\[ d_M(x, y) = \sum_{i=1}^{p} |x_i - y_i| = |x - y|_1 \]

更一般地，闵可夫斯基距离（Minkowski Distance）统一了多种距离：

\[ d_q(x, y) = \left( \sum_{i=1}^{p} |x_i - y_i|^q \right)^{1/q} \]

当 \( q = 1 \) 时为曼哈顿距离，\( q = 2 \) 时为欧氏距离，\( q \to \infty \) 时为切比雪夫距离：

\[ d_\infty(x, y) = \max_{1 \leq i \leq p} |x_i - y_i| \]

特点：计算简单；对异常值不如欧氏距离敏感；适合高维稀疏数据。

余弦相似度

余弦相似度（Cosine Similarity）衡量两个向量方向上的一致性：

\[ \cos(x, y) = \frac{x^T y}{|x|2 \cdot |y|2} = \frac{\sum{i=1}^{p} x_i y_i}{\sqrt{\sum{i=1}^{p} x_i^2} \cdot \sqrt{\sum_{i=1}^{p} y_i^2}} \]

取值范围 \( [-1, 1] \)，值越接近 1 表示方向越一致。由此导出余弦距离：

\[ d_{\cos}(x, y) = 1 - \cos(x, y) \]

特点：对向量尺度不敏感，只关注方向；广泛应用于文本挖掘和信息检索；适合高维稀疏数据。

相关系数

皮尔逊相关系数（Pearson Correlation Coefficient）衡量线性相关程度：

\[ r(x, y) = \frac{\sum_{i=1}^{p} (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_{i=1}^{p} (x_i - \bar{x})^2} \cdot \sqrt{\sum_{i=1}^{p} (y_i - \bar{y})^2}} \]

其中 \( \bar{x} = \frac{1}{p}\sum_{i=1}^{p} x_i \)，由相关系数导出的距离为 \( d_r(x, y) = 1 - r(x, y) \)。

特点：消除量纲和均值影响；本质上是中心化后的余弦相似度；适合衡量线性趋势一致性。

其他距离度量

马氏距离（Mahalanobis Distance）考虑变量间相关性：

\[ d_{Mah}(x, y) = \sqrt{(x - y)^T \Sigma^{-1} (x - y)} \]

其中 \( \Sigma \) 为协方差矩阵，当 \( \Sigma = I \) 时退化为欧氏距离。

汉明距离（Hamming Distance）适用于离散型变量，表示对应位置不同字符的个数。

杰卡德距离（Jaccard Distance）适用于集合数据：\( d_J(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|} \)。

聚类方法分类

层次聚类

层次聚类（Hierarchical Clustering）通过逐步合并或分裂来构建嵌套的簇结构，结果用树状图（Dendrogram）表示。

凝聚型层次聚类

凝聚型（Agglomerative）自底向上：初始每个样本为独立簇，逐步合并距离最近的簇对。簇间距离的链接准则：

最短距离法（Single Linkage）：

\[ d(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y) \]

最长距离法（Complete Linkage）：

\[ d(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x, y) \]

平均距离法（Average Linkage）：

\[ d(C_i, C_j) = \frac{1}{|C_i| \cdot |C_j|} \sum_{x \in C_i} \sum_{y \in C_j} d(x, y) \]

Ward 方法：最小化合并后簇内平方和的增量：

\[ \Delta(C_i, C_j) = \frac{|C_i| \cdot |C_j|}{|C_i| + |C_j|} |\bar{x}_i - \bar{x}_j|^2 \]

优缺点：无需预先指定聚类数目，可通过树状图直观展示；但计算复杂度高（\( O(n^2 \log n) \) 至 \( O(n^3) \)），合并操作不可逆。

划分聚类

划分聚类（Partitional Clustering）将数据集直接划分为 \( K \) 个不重叠的簇。

K-Means 算法

目标是最小化簇内平方和（WCSS）：

\[ J = \sum_{k=1}^{K} \sum_{x_i \in C_k} |x_i - \mu_k|^2 \]

其中 \( \mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i \) 为质心。算法交替执行：

1. 分配：\( C_k = {x_i : |x_i - \mu_k| \leq |x_i - \mu_j|, \forall j \neq k} \)
2. 更新：\( \mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i \)

K-Means++ 改善初始化：以概率 \( \frac{D(x_i)^2}{\sum_j D(x_j)^2} \) 逐步选取远离已选质心的样本。

K-Medoids（PAM 算法）使用实际数据点作为簇中心，对异常值更鲁棒。

性质：时间复杂度 \( O(nKpt) \)；收敛到局部最优；适用于球形簇；对异常值敏感。

密度聚类

密度聚类（Density-Based Clustering）基于样本分布密度识别簇，能发现任意形状的簇。

DBSCAN 算法

核心概念：

• \( \varepsilon \)-邻域：\( N_\varepsilon(x) = {y \in X : d(x, y) \leq \varepsilon} \)
• 核心点：\( |N_\varepsilon(x)| \geq \text{MinPts} \)
• 密度可达：通过核心点链式传递
• 密度相连：存在公共核心点使两点均密度可达

算法从核心点出发扩展簇，将所有密度相连的点归入同一簇，不可达点标记为噪声。

优缺点：无需指定聚类数；能发现任意形状簇和噪声点；但对参数敏感，对密度不均匀数据效果有限。

OPTICS 通过核心距离和可达距离生成有序排列，可在不同密度阈值下提取聚类。

基于模型的聚类

高斯混合模型

假设数据由 \( K \) 个高斯分布混合生成：

\[ p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x | \mu_k, \Sigma_k) \]

使用 EM 算法迭代求解。E 步计算责任度：

\[ \gamma_{ik} = \frac{\pi_k \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(x_i | \mu_j, \Sigma_j)} \]

M 步更新参数：

\[ \mu_k = \frac{\sum_{i=1}^{n} \gamma_{ik} x_i}{\sum_{i=1}^{n} \gamma_{ik}}, \quad \Sigma_k = \frac{\sum_{i=1}^{n} \gamma_{ik} (x_i - \mu_k)(x_i - \mu_k)^T}{\sum_{i=1}^{n} \gamma_{ik}}, \quad \pi_k = \frac{1}{n} \sum_{i=1}^{n} \gamma_{ik} \]

使用 BIC 选择分量数：\( \text{BIC} = -2 \ln L + m \ln n \)。

优缺点：提供软聚类和概率解释；能拟合椭球形簇；但对初始值敏感，高维时协方差估计不稳定。

模糊聚类

模糊 C 均值算法

模糊 C 均值（FCM）允许样本以隶属度属于多个簇，目标函数：

\[ J_m = \sum_{i=1}^{n} \sum_{k=1}^{K} u_{ik}^m |x_i - \mu_k|^2 \]

其中 \( u_{ik} \in [0,1] \) 满足 \( \sum_k u_{ik} = 1 \)，\( m > 1 \) 为模糊化指数。更新公式：

\[ u_{ik} = \frac{1}{\sum_{j=1}^{K} \left(\frac{|x_i - \mu_k|}{|x_i - \mu_j|}\right)^{\frac{2}{m-1}}}, \quad \mu_k = \frac{\sum_{i=1}^{n} u_{ik}^m x_i}{\sum_{i=1}^{n} u_{ik}^m} \]

特点：提供柔性分配；\( m \to 1 \) 时退化为 K-Means；适用于边界模糊的情况。

聚类评价指标

聚类评价分为外部指标（需参考真实标签）和内部指标（仅基于数据本身）。

轮廓系数

轮廓系数（Silhouette Coefficient）综合考虑紧凑性和分离性。对样本 \( x_i \)：

• \( a(i) \)：与同簇其他样本的平均距离（簇内凝聚度）

\[ a(i) = \frac{1}{|C_{k_i}| - 1} \sum_{x_j \in C_{k_i}, j \neq i} d(x_i, x_j) \]

• \( b(i) \)：与最近邻簇所有样本的平均距离（簇间分离度）

\[ b(i) = \min_{k \neq k_i} \frac{1}{|C_k|} \sum_{x_j \in C_k} d(x_i, x_j) \]

轮廓系数定义为：

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

取值范围 \( [-1, 1] \)：接近 1 表示聚类合理，接近 0 表示在簇边界，接近 -1 表示可能错误分配。整体轮廓系数：

\[ \bar{s} = \frac{1}{n} \sum_{i=1}^{n} s(i) \]

Calinski-Harabasz 指数

CH 指数（方差比准则）定义为簇间离散度与簇内离散度的比值：

\[ \text{CH} = \frac{B_K / (K - 1)}{W_K / (n - K)} \]

其中 \( B_K = \sum_{k=1}^{K} |C_k| |\mu_k - \bar{x}|^2 \)，\( W_K = \sum_{k=1}^{K} \sum_{x_i \in C_k} |x_i - \mu_k|^2 \)。

CH 指数越大越好，计算效率高，适合确定最优聚类数。

Davies-Bouldin 指数

DB 指数衡量各簇间的相似程度：

\[ \text{DB} = \frac{1}{K} \sum_{k=1}^{K} \max_{j \neq k} \left( \frac{S_k + S_j}{d(\mu_k, \mu_j)} \right) \]

其中 \( S_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} |x_i - \mu_k| \)。DB 指数越小越好。

其他评价指标

Dunn 指数：\( \text{Dunn} = \frac{\min_{i \neq j} d(C_i, C_j)}{\max_k \text{diam}(C_k)} \)，越大越好。

肘部法则：绘制 \( \text{SSE}(K) = \sum_{k=1}^{K} \sum_{x_i \in C_k} |x_i - \mu_k|^2 \) 关于 \( K \) 的曲线，选择拐点。

Gap Statistic：\( \text{Gap}(K) = E^*[\ln W_K] - \ln W_K \)，选择使其最大的 \( K \)。

指标对比

应用领域

市场细分与客户分析

通过对客户的购买行为、消费偏好、人口统计特征等进行聚类，实现精准客户细分。典型应用包括 RFM 模型聚类、用户生命周期分析、推荐系统用户分群。

图像处理与计算机视觉

• 图像分割：将像素按照颜色、纹理等特征聚类，分离前景与背景
• 图像压缩：通过 K-Means 对颜色空间量化，减少存储空间
• 目标检测：在特征空间中聚类以识别和定位物体

生物信息学

• 基因表达分析：对基因表达谱数据进行聚类，发现共表达基因模块
• 蛋白质结构分类：根据空间结构特征对蛋白质进行分组
• 物种分类：基于遗传距离进行系统发育分析

社会网络分析

• 社区发现：在社交网络中识别紧密连接的群体
• 异常检测：识别网络中的异常行为模式
• 信息传播分析：研究信息在不同社群间的传播规律

地理信息与城市规划

• 热点区域识别：基于空间位置数据聚类识别高频活动区域
• 交通流量分析：对交通模式进行时空聚类
• 城市功能区划分：根据土地利用和活动特征划分功能区

数学建模竞赛中的应用

1. 数据预处理：通过聚类发现数据的内在结构，为后续建模提供依据
2. 分类评价问题：对研究对象进行类型划分
3. 特征工程：利用聚类结果作为新特征输入后续模型
4. 异常检测：识别偏离正常模式的异常样本
5. 降维与可视化：结合 PCA 等方法展示高维数据的聚类结构

方法选择建议

聚类方法的选择应综合考虑数据规模、特征维度、簇的形状、噪声水平等因素。

在数学建模中，建议先使用 K-Means 进行初步探索，再根据数据特点选择更合适的方法，并结合多种评价指标验证聚类结果的稳定性和合理性。

小结

聚类分析作为无监督学习的核心方法，其本质在于通过合理的距离度量和算法设计，揭示数据中隐含的群组结构。理解各种聚类方法的数学原理、适用条件和局限性，是在数学建模中正确运用聚类分析的关键。选择合适的距离度量、聚类算法和评价指标，三者缺一不可，共同决定了聚类分析的质量。

补充说明

数据预处理对聚类的影响

在进行聚类分析之前，数据预处理至关重要：

• 标准化/归一化：当各特征量纲不同时，应先进行 Z-score 标准化或 Min-Max 归一化，否则量纲较大的特征会主导距离计算
• 缺失值处理：删除、均值/中位数填充或基于模型的插补
• 异常值处理：异常值会严重影响 K-Means 等基于均值的方法
• 特征选择：去除无关或冗余特征，降低维数灾难的影响

高维数据的聚类挑战

当特征维度 \( p \) 很高时，会出现所谓的“维数灾难“：

• 高维空间中样本间的距离趋于均匀化，距离度量失效
• 噪声特征会淹没有用信息
• 解决方案包括：PCA 降维后聚类、子空间聚类、谱聚类等

聚类结果的稳定性验证

为确保聚类结果的可靠性，应进行稳定性验证：

• 多次随机初始化，比较结果的一致性
• Bootstrap 重采样，评估簇分配的稳定性
• 使用不同距离度量和算法，交叉验证结果
• 结合领域知识判断聚类结果的合理性