上一章：机器学习08——集成学习
下一章：机器学习10——降维与度量学习
机器学习实战项目：【从 0 到 1 落地】机器学习实操项目目录：覆盖入门到进阶，大学生就业 / 竞赛必备

一、聚类任务（无监督学习的核心）

聚类是无监督学习中最核心的任务之一，目标是将无标记样本集划分为若干不相交的“簇”（cluster），以揭示数据内在的分布结构。

（一）形式化描述

• 给定样本集D={x1,x2,...,xm}D = \{x_1, x_2, ..., x_m\}D={x1​,x2​,...,xm​}，每个样本$x_i$为n维特征向量；
• 聚类算法将$D$划分为$k$个簇{C1,C2,...,Ck}\{C_1, C_2, ..., C_k\}{C1​,C2​,...,Ck​}，满足：
  • 簇间不相交：$C_{l^{\prime }}{\cap }_{l^{\prime }\ne l}{C}_l=\varnothing$；
  • 覆盖所有样本：$D={\cup }_{l=1}^k{C}_l$；
• 簇标记向量λ={λ1;λ2;...;λm}\lambda = \{\lambda_1; \lambda_2; ...; \lambda_m\}λ={λ1​;λ2​;...;λm​}表示样本所属簇（λj∈{1,2,...,k}\lambda_j \in \{1, 2, ..., k\}λj​∈{1,2,...,k}，即$x_j\in C_{{\lambda }_j}$）。
  

二、聚类性能度量（有效性指标）

性能度量用于评价聚类结果的优劣，核心是“簇内相似度高、簇间相似度低”，分为外部指标和内部指标。

（一）外部指标（与参考模型比较）

• 定义：将聚类结果与“参考模型”（如人工标注的簇划分）比较，通过样本对的匹配情况计算。
• 关键参数：
  • $a$：同簇且参考模型中同簇的样本对数量；
  • $b$：同簇但参考模型中不同簇的样本对数量；
  • $c$：不同簇但参考模型中同簇的样本对数量；
  • $d$：不同簇且参考模型中不同簇的样本对数量。
• 常用指标：
  • Jaccard系数（JC）：$JC=\frac{a}{a+b+c}$；
  • FM指数（FMI）：$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$；
  • Rand指数（RI）：$RI=\frac{2(a+d)}{m(m-1)}$。

（二）内部指标（直接评价聚类结果）

• 定义：基于聚类结果自身的统计特性（如距离、密度）评价，无需参考模型。
• 关键参数：
  • $avg(C)$：簇$C$内样本平均距离；
  • $diam(C)$：簇$C$内样本最大距离；
  • $d_{min}(C_i,C_j)$：簇$C_i$与$C_j$的最近样本距离；
  • $d_{cen}(C_i,C_j)$：簇$C_i$与$C_j$的中心距离。
• 常用指标：
  • DB指数（DBI）：$DBI=\frac{1}{k}{\sum }_{i=1}^{k}ma{x}_{j\ne i}\left(\frac{avg(C_i)+avg(C_j)}{d_{cen}({\mu }_i,{\mu }_j)}\right)$（值越小越好）；
  • Dunn指数（DI）：$DI=mi{n}_{1\le i\le k}\left\{mi{n}_{j\ne i}\left(\frac{d_{min}(C_i,C_j)}{ma{x}_{1\le l\le k}diam(C_l)}\right)\right\}$（值越大越好）。

三、距离计算（聚类的基础）

距离度量是聚类的核心，需满足非负性、同一性、对称性和直递性，不同属性类型需采用不同度量方式。

（一）常用距离

• 闵可夫斯基距离：$dist(x_i,x_j)={\left({\sum }_{u=1}^n|x_{iu}-x_{ju}{|}^p\right)}^{1/p}$，其中：
  • $p=2$为欧氏距离（最常用）；
  • $p=1$为曼哈顿距离。

（二）属性类型与距离度量

1. 连续属性：直接使用闵可夫斯基距离；
2. 离散属性：
   • 有序属性：可转换为连续值后用闵可夫斯基距离；
   • 无序属性：用VDM距离：
     $$VD{M}_p(a,b)=\sum _{i=1}^k{\left|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}\right|}^p$$
     （$m_{u,a,i}$为第$i$簇中属性$u$取$a$的样本数，$m_{u,a}$为属性$u$取$a$的总样本数）；
3. 混合属性：结合闵可夫斯基距离和VDM：
   $$MinkovD{M}_p(x_i,x_j)={\left(\sum _{连续属性}|x_{iu}-x_{ju}{|}^p+\sum _{无序属性}VD{M}_p(x_{iu},x_{ju})\right)}^{1/p}$$

四、原型聚类（基于原型的聚类）

原型聚类假设聚类结构可通过“原型”（如中心、概率分布）刻画，通过迭代优化原型实现聚类。

（一）k均值算法（k-means）

• 核心思想：最小化簇内平方误差$E={\sum }_{i=1}^k{\sum }_{x\in C_i}\Vert x-{\mu }_i{\Vert }_2^2$（${\mu }_i$为簇$C_i$的均值向量）。
• 算法步骤：
  1. 随机选择$k$个样本作为初始均值向量{μ1,μ2,...,μk}\{\mu_1, \mu_2, ..., \mu_k\}{μ1​,μ2​,...,μk​}；
  2. 迭代：
     • 簇划分：将每个样本划入距离最近的均值向量对应的簇；
     • 更新均值：计算每个簇的新均值向量${\mu }_i=\frac{1}{|C_i|}{\sum }_{x\in C_i}x$；
  3. 终止：均值向量不再更新时停止。
• 特点：高效易实现，但对初始中心敏感，适用于凸形分布数据。
  

• 模型定义：混合分布$p_M(x)={\sum }_{i=1}^k{\alpha }_{i}p(x|{\mu }_i,{\Sigma }_i)$，其中${\alpha }_i$为混合系数（$\sum {\alpha }_i=1$），$p(x|{\mu }_i,{\Sigma }_i)$为第$i$个高斯分布（均值${\mu }_i$，协方差${\Sigma }_i$）。
• 求解方法（EM算法）：
  1. 初始化参数{αi,μi,Σi}\{\alpha_i, \mu_i, \Sigma_i\}{αi​,μi​,Σi​}；
  2. 迭代（E步→M步）：
     • E步：计算样本$x_j$属于第$i$个成分的后验概率${\gamma }_{ji}=\frac{{\alpha }_{i}p(x_j|{\mu }_i,{\Sigma }_i)}{{\sum }_{l=1}^k{\alpha }_{l}p(x_j|{\mu }_l,{\Sigma }_l)}$；
     • M步：更新参数${\alpha }_i=\frac{1}{m}{\sum }_j{\gamma }_{ji}$，${\mu }_i=\frac{{\sum }_j{\gamma }_{ji}{x}_j}{{\sum }_j{\gamma }_{ji}}$，${\Sigma }_i=\frac{{\sum }_j{\gamma }_{ji}(x_j-{\mu }_i)(x_j-{\mu }_i{)}^T}{{\sum }_j{\gamma }_{ji}}$；
  3. 终止：似然函数收敛。
• 特点：灵活拟合复杂分布，可输出样本属于各簇的概率，但计算复杂度高。

五、层次聚类（树形结构聚类）

层次聚类通过逐层合并或拆分簇，形成树形聚类结构，分为自底向上（聚合）和自顶向下（分拆）策略。

（一）AGNES算法（自底向上聚合）

• 核心思想：初始将每个样本视为一个簇，迭代合并距离最近的两个簇，直至达到预设簇数$k$。
• 簇距离度量：
  • 最小距离：$d_{min}(C_i,C_j)=mi{n}_{x\in C_i,z\in C_j}dist(x,z)$；
  • 最大距离：$d_{max}(C_i,C_j)=ma{x}_{x\in C_i,z\in C_j}dist(x,z)$；
  • 平均距离：$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}{\sum }_{x\in C_i}{\sum }_{z\in C_j}dist(x,z)$。
• 特点：生成层次化簇结构，便于可视化，但计算复杂度高（$O(m^{2}logm)$），对噪声敏感。

总结

聚类通过无监督方式揭示数据内在结构，性能可通过外部或内部指标评价。距离计算需根据属性类型选择（如连续属性用欧氏距离，无序属性用VDM）。原型聚类（k均值、高斯混合）高效且适用于大规模数据；层次聚类（AGNES）生成树形结构，适合探索数据层次关系。实际应用中需根据数据分布和任务需求选择算法。

上一章：机器学习08——集成学习
下一章：机器学习10——降维与度量学习
机器学习实战项目：【从 0 到 1 落地】机器学习实操项目目录：覆盖入门到进阶，大学生就业 / 竞赛必备