第八章 聚类

1 聚类概要

基本概念

聚类：基于特定的距离或相似度度量，将数据集划分为$k$个子集合$C_k$，又称为簇

簇有质心和半径两个描述指标

• 质心$m$：簇内样本的平均值
  $$m_i=\frac{1}{n_i}\sum _{x_i\in C_i}{x}_i$$

• 半径$r$：半径为簇内所有样本到质心距离的均方差的平方根
  $$r_i=\sqrt{\frac{{\sum }_{x_i\in C_i}{(x_i-m_i)}^2}{n_i}}$$

分类

根据内在机制

• 基于划分：K-means、K-medoids
• 基于层次：AGNES、DIANA、BIRCH
• 基于密度：DBSCAN、OPTICS、Mean-Shift
• 基于网络：STING、CLIQUE
• 基于模型：高斯混合聚类、贝叶斯高斯混合聚类
• 基于图：谱聚类、Louvain、Girvan-Newman

根据聚类结果是否允许簇内存在重叠

• 硬聚类（每个数据只能属于一个簇）：K-means
• 软聚类（赋予数据每个簇的隶属度得分）：模糊C-均值算法、高斯混合聚类

评价指标

当数据集具有真实的类别标签时（外部指标）

• 列联矩阵：二维矩阵，行代表真实类别标签，列代表聚类结果的簇标签，矩阵中的每个值为对应的统计频数

  from sklearn.metrics.cluster import contingency_matrix

• 成对混淆矩阵

  from sklearn.metrics.cluster import pair_confusion_matrix

  TN和TP越大，FN和FP越接近0，聚类结果越好

  $$\left[\begin{array}{cc}TN& FP\\ FN& TP\end{array}\right]$$

  TN：实际中属于不同类别，聚类结果中被划分到了不同簇中的样本对数量

  TP：实际中属于同一类别，聚类结果中被划分在了相同簇中的样本对数量

  FP：实际中属于不同类别，聚类结果中被划分在了相同簇中的样本对数量

  FN：实际中属于同一类别，聚类结果中被划分到了不同簇中的样本对数量

• Fowlkes-Mallows指数FM

  from sklearn.metrics import fowlkes_mallows_score

  取值范围：[0，1]，越大越好

  计算正确聚类的样本对比例
  $$FM=\frac{TP}{\sqrt{(TP+FP)(TP+FN)}}$$

• 兰德系数RI

  from sklearn.metrics import rand_score

  取值范围：[0，1]，越大越好

  计算属于同一类别的样本对比例
  $$RI=\frac{2(TP+TN)}{n(n-1)}$$
  **调整兰德系数ARI：**由于兰德系数存在对数据集类别进行随机取值时，数值不会接近于0的缺陷，使用调整兰德系数

  from sklearn.metrics import adjusted_mutual_info_score

  取值范围：[-1，1]，越大越好，1表示完全一致，-1表示完全不一致

  $$ARI=\frac{2(TP\times TN-FN\times FP)}{(TP+FN)(FN+TN)+(TP+FP)(FP+TN)}$$

• 互信息MI

  from sklearn.metrics import mutual_info_score

  度量真实标签和聚类标签一致性的指标

  **调整互信息AMI：**由于互信息可能受到聚类数量的影响，例如增加聚类数量可能会提高互信息，使用调整互信息

  from sklearn.metrics import adjusted_mutual_info_score

  取值范围：[0，1]，越大越好

• 同质性，完整性和V-measure

  同质性：from sklearn.metrics import homogeneity_score

  完整性：from sklearn.metrics import completeness_score

  V-measure：from sklearn.metrics import v_measure_score

  基于聚类结果和真实标签之间的相似度进行聚类评估的指标

  **同质性：**衡量一个簇是否仅包含来自同一类别的样本。如果簇满足这个条件，则该簇是完全同质的，同质性得分为1

  **完整性：**衡量属于同一类别的所有样本是否被划分到同一个簇中。如果满足这一条件，则完整性得分为1

  **V-measure：**同质性和完整性的调和平均，是综合的衡量聚类性能的指标。当V-measure值为1时，说明聚类结果既完全同质又完全完整

当数据集没有真实的类别标签时（内部指标）

• 轮廓系数SC

  from sklearn.metrics import silhouette_score

  取值范围：[-1，1]，越大越好

  计算数据的簇内平均距离和簇间平均距离进行聚类效果评估的指标

  样本$i$的轮廓系数为
  $$\begin{gathered} S{C}_i=\frac{b_i-a_i}{\max (a_i,b_i)} \\ SC=\frac{1}{n}\sum _{i=1}^{n}S{C}_i \end{gathered}$$
  其中，

  内聚度$a$：同一簇中，样本$i$到其他样本之间的平均距离

  分离度$b$：样本$i$到下一个最近簇中所有样本的平均距离

• Calinski-Harabasz指数CH

  from sklearn.metrics import calinski_harabasz_score

  越大越好

  计算簇内的方差和簇间的方差进行聚类效果评估的指标
  KaTeX parse error: Undefined control sequence: \tr at position 14: CH=\cfrac{\̲t̲r̲(B)}{\tr(W)}\ti…
  其中，$k$为聚类数

  簇内散度矩阵$W={\sum }_{q=1}^k{\sum }_{x\in C_q}(x-m_q)(x-m_q{)}^T$，$m_q$为簇的质心

  簇间散度矩阵$B={\sum }_{q=1}^k{n}_q(m_q-m)(m_q-m{)}^T$，$m$为数据集的质心

• Davies-Bouldin指数DB

  from sklearn.metrics import davies_bouldin_score

  越小越好

  计算簇内样本到质心平均距离和最近簇质心之间的距离
  $$\begin{gathered} DB=\frac{1}{k}\sum _{i,j=1}^k\max R_{ij} \\ {R}_{ij}=\frac{r_i+r_j}{d_{ij}} \end{gathered}$$
  其中，$k$为聚类数，$r_i$为簇$C_i$中所有数据到质心距离的平均值，$d_{ij}$为簇$C_i$和$C_j$质心的距离

簇数量的确定

• 经验取值法
  $$k\approx \sqrt{n/2}$$

• 肘部法则

  寻找簇内距离平均和SSE下降率显著变化的点确定最佳聚类数
  $$SSE=\sum _{i=1}^k\sum _{x\in C_i}d(x,m_i{)}^2$$

• 内部指标

  通过选择不同的簇值多次运行聚类算法，使内部指标达到最优值时的簇值为最佳聚类值

---

2 层次聚类

from sklearn.cluster import AgglomerativeClustering

可视化展示层次聚类树状图：from scipy.cluster.hierarchy import dendrogram

分裂型和凝聚型

• 自上而下的分裂型层次聚类算法
• 自下而上的凝聚型层次聚类算法（计算复杂度更低）

凝聚型链接方式

根据样本之间距离计算方式不同，分类

• 单链接方式：将两个簇中距离最近的样本之间的距离作为簇整体的距离

• 全链接方式：将两个簇中距离最远的样本之间的距离作为簇整体的距离

• 平均链接方式：将两个簇中所有样本之间的距离均值作为簇整体的距离

• Ward链接方式：两个簇以内部方差增加量作为整体的距离，每次聚合使得合并后簇内方差增加的量最小
  $$\Delta (Var)=\sum _{j=1}^n\frac{|C_i||C_j|}{|C_i|+|C_j|}\parallel m_i-m_j{\parallel }^2$$

算法评价

占用大规模的计算时间和空间资源，适用于小规模数据集分析

---

3 K-means聚类

from sklearn.cluster import KMeans

质心初始化

• 随机选择
• 随机分区
• K-means++

算法评价

适用于簇大小相近且分布均匀的数据集

对噪声数据和异常数据比较敏感，噪声数据会影响最终簇的分布结果

---

4 高斯混合聚类

from sklearn.mixture import GaussianMixture

一种基于模型的软聚类算法

高斯混合聚类将数据集视作多个高斯分布混合叠加的分布，通过估计高斯混合模型中的单个高斯分布的均值和协方差，拟合数据集中不同聚类的数据分布

算法步骤

1. 随机初始化$k$个多元高斯分布的均值向量$\mu$，协方差矩阵$\Sigma$，高斯混合分布的权重系数$\alpha$
2. 计算每个样本由$k$个分布生成的后验概率$\gamma$
3. 基于步骤2得到的后验概率，更新$\mu ,\Sigma ,\alpha$
4. 重复步骤2和3，直到似然函数的增加值小于收敛阈值，或者达到最大迭代次数
5. 计算每个样本属于$k$个簇的后验概率，依次将样本划分到后验概率最大的簇中

算法评价

通常用于在簇结构不清晰或需要估计数据不确定性的场景

---

5 DBSCAN算法

from sklearn.cluster import DBSCAN

核心概念

• $\epsilon$-邻域
• 核心对象（计数时包括数据点本身）
• 边界对象（计数时包括数据点本身）
• 直接密度可达（$x_i$对$x_j$成立时，$x_j$对$x_i$不一定成立）
• 密度可达
• 密度相连（满足对称性）：$x_i$与$x_j$都由$x_k$密度可达，则$x_i$与$x_j$密度相连

算法评价

适用于识别复杂形状的簇，能够有效识别和处理异常点

聚类结果依赖参数$\epsilon$和数$MinPts$的取值，不合适的参数设置可能产生过多的噪点或簇的合并

---

6 OPTICS算法

from sklearn.cluster import OPTICS

由DBSCAN算法改进而来

核心概念

• 核心距离：使$x_i$成为核心点的最小邻域半径
  $$cd(x)=\{\begin{array}{cc}notDefine,& |N_{\epsilon }(x)|<MinPts\\ d(x,N_{\epsilon }^{MinPts}(x)),& |N_{\epsilon }(x)|\ge MinPts\end{array}$$

• 可达距离：在$\epsilon$和$MinPts$确定的情况下，$x_j$对$x_i$的可达距离定义为
  rd(xj,xi)={notDefine,∣Nε(x)∣<MinPtsmax⁡{cd(xj),d(xi,xj)},∣Nε(x)∣≥MinPts rd(x_j,x_i)=\left\{\begin{matrix} notDefine, & |N_\varepsilon (x)| < MinPts \\ \max\{cd(x_j),d(x_i,x_j)\}, & |N_\varepsilon (x)| \ge MinPts \end{matrix}\right. rd(xj​,xi​)={notDefine,max{cd(xj​),d(xi​,xj​)},​∣Nε​(x)∣<MinPts∣Nε​(x)∣≥MinPts​

算法评价

与DBSCAN相比，OPTICS减少了对参数设置的依赖性，仅需确定参数$MinPts$

算法需要额外计算可达性图和样本的顺序，对计算性能和存储的需求更高

---

7 谱聚类算法

from sklearn.cluster import spectral_clustering

通过最小化不同子图间边的权重总和，同时最大化各子图内部边的权重总和

算法步骤

1. 利用选定的相似度度量方法，构建数据集的相似性矩阵$S$

   相似性矩阵的构建方法：

   • $\epsilon$-近邻法

   • K-近邻法（需要进行相似性矩阵的对称化）

   • 全连接法（最常用）

     边权重通常采用核函数确定：$w_{ij}=e^{\frac{\parallel x_i-x_j{\parallel }^2}{{\sigma }^2}}$

2. 基于步骤1得到的相似性矩阵，进一步构造邻接矩阵$A$和度矩阵$D$

3. 通过邻接矩阵$A$和度矩阵$D$，计算得到拉普拉斯矩阵$L=D-A$

4. 对拉普拉斯矩阵进行标准化处理$D^{-1/2}L{D}^{1/2}$

5. 计算$D^{-1/2}L{D}^{1/2}$的前$k$个最小特征值所对应的特征向量$f$

6. 将步骤5得到的特征向量进行标准化处理，组成$n\times k$维的特征矩阵$F$

7. 将$F$中的每一行作为$k$维的样本，然后应用K-means聚类算法对样本进行聚类

8. 根据K-means聚类结果，得到原数据集的聚类划分

算法评价

能够收敛到全局最优解

尤其适合解决传统聚类算法难以处理的非凸形状簇的场景

对参数的选择比较敏感