聚类（Clustering）基础知识3

一、聚类的性能评价

1、聚类性能评价

（1）聚类性能评价方法：

聚类性能评价方法主要分为两种：

• 外部评价法 (external criterion)：评估聚类结果与参考结果的相似程度。
• 内部评价法 (internal criterion)：评估聚类的本质特征，无需参考结果。

2、参考模型 (reference model)

（1）数据集：

• 数据集： D = { x 1 , x 2 , . . . , x N } D = \{x_1, x_2, ..., x_N\} D={x1​,x2​,...,xN​}

（2）聚类结果：

• 聚类结果： C = { C 1 , C 2 , . . . , C K } C = \{C_1, C_2, ..., C_K\} C={C1​,C2​,...,CK​}，其中$C_k$表示属于类别$k$的样本的集合。

（3）参考模型：

• 参考模型： C ∗ = { C 1 ∗ , . . . , C K ∗ } C^* = \{C_1^*, ..., C_K^*\} C∗={C1∗​,...,CK∗​}

（4）标记向量：

• $\lambda$ 和 ${\lambda }^{\ast }$ 分别为$C$和 $C^{\ast }$ 的标记向量。

（5）样本对数目计算：

• $a=\#\{(x_i,x_j)|x_i,x_j\in C_k;x_i,x_j\in C_l^{\ast }\}$
  • 在两种聚类结果中，两个样本的所属簇相同。
• $d=\#\{(x_i,x_j)|x_i\in C_{k1},x_j\in C_{k2};x_i\in C_{l1}^{\ast },x_j\in C_{l2}^{\ast }\}$
  • 在两种聚类结果中，两个样本的所属簇不同。
• $b=\#\{(x_i,x_j)|x_i,x_j\in C_k;x_i\in C_{l1}^{\ast },x_j\in C_{l2}^{\ast }\}$
• $c=\#\{(x_i,x_j)|x_i\in C_{k1},x_j\in C_{k2};x_i,x_j\in C_l^{\ast }\}$

（6）外部评价指标：

利用$(a,b,c,d)$定义外部评价指标：

$N(N-1)/2$	参考模型	相同	不同
聚类结果	相同	$a$	$b$
	不同	$c$	$d$

3、外部索引

（1）Jaccard 系数 (JC)

• $JC=\frac{a}{a+b+c}$
• $JC\in [0,1]$，$JC\uparrow$，一致性 $\uparrow$

Fowlkes and Mallows 指数 (FMI)

• $FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$
• $FMI\in [0,1]$，$FMI\uparrow$，一致性 $\uparrow$

（2）Rand 指数 (Rand Index), RI

• $RI=\frac{2(a+d)}{N(N-1)}$
• $RI\in [0,1]$，$RI\uparrow$，一致性 $\uparrow$

4、无参考模型

（1）大部分时候只有聚类结果，没有参考模型，只能用内部评价法评估聚类的性能：

• 簇内相似度越高，聚类质量越好。
• 簇间相似度越低，聚类质量越好。

5、簇内相似度

（1）平均距离：

• $avg(C_k)=\frac{1}{|C_k|(|C_k|-1)}{\sum }_{x_i,x_j\in C_k}dist(x_i,x_j)$
  • 其中$|C_k|$表示簇$C_k$中元素的数目。

（2）最大距离：

• $diam(C_k)={\max }_{x_i,x_j\in C_k}dist(x_i,x_j)$

（3）簇的半径 (diameter)：

• $diam(C_k)=\sqrt{\frac{1}{|C_k|}{\sum }_{x_i\in C_k}(dist(x_i,{\mu }_k){)}^2}$
  • 其中${\mu }_k=\frac{1}{|C_k|}{\sum }_{x_i\in C_k}{x}_i$
    

6、簇间相似度/距离

（1）最小距离：

• $d_{min}(C_k,C_l)={\min }_{x_i\in C_k,x_j\in C_l}dist(x_i,x_j)$
  

（2）类中心之间的距离：

• $d_{cen}(C_k,C_l)=dist({\mu }_k,{\mu }_l)$，
  • 其中${\mu }_k=\frac{1}{|C_k|}{\sum }_{x_i\in C_k}{x}_i$
    

7、内部评价指标

（1）DB 指数 (DBI)

  $DBI=\frac{1}{K}{\sum }_{k=1}^K{\max }_{k\ne l}\frac{avg(C_k)+avg(C_l)}{d_{cen}(C_k,C_l)}$，
  簇内距离/簇间距离
  $DBI\downarrow$，聚类质量 $\uparrow$

（2）Dunn 指数 (DI)

  $DI={\min }_{1\le k<l\le K}\frac{d_{min}(C_k,C_l)}{{\max }_{1\le k\le K}diam(C_k)}$，
  最小簇间距离/最大簇的半径
  $DI\uparrow$，聚类质量 $\uparrow$

8、Calinski-Harabaz Index (CHI)

  $CHI=\frac{tr(B)}{tr(W)}\times \frac{N-K}{K-1}$，
  $CHI\uparrow$，聚类质量 $\uparrow$   计算快

  其中$W$为簇内散度矩阵：$W={\sum }_{k=1}^K{\sum }_{x_i\in C_k}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^{\top }$
  其中簇中心${\mu }_k=\frac{1}{|C_k|}{\sum }_{x_i\in C_k}{x}_i$
  $tr(W)={\sum }_{k=1}^K{\sum }_{x_i\in C_k}dist(x_i,{\mu }_k)$，为矩阵$W$的迹

  $B$为簇间散度矩阵：$B={\sum }_{k=1}^K|C_k|({\mu }_k-\mu )({\mu }_k-\mu {)}^{\top }$
  其中$\mu =\frac{1}{N}{\sum }_{i=1}^N{x}_i$
  $tr(B)={\sum }_{k=1}^K|C_k|dist({\mu }_k,\mu )$

9、轮廓指数 (Silhouette Index)

  对于其中的一个样本点$i$，记：
  - $a(i)$：样本点$i$到与其所属簇中其它点的平均距离
  - $\overline{d(i,C_k)}$：样本点$i$到其他簇$C_k(x_i\notin C_k)$内所有点的平均距离
  - $b(i)$：所有$\overline{d(i,C_k)}$的最小值
  则样本点$i$的轮廓宽度为：$s(i)=\frac{b(i)-a(i)}{\max (a(i),b(i))}$
  $s(i)\in [-1,1]$
  $SI\uparrow$，聚类质量 $\uparrow$
  平均轮廓值为：$SI=\frac{1}{N}{\sum }_{i=1}^{N}s(i)$

（1）例：轮廓指数

  SI值小的点为边缘点

（2）例：根据SI选择聚类数目

  2个簇轮廓分数高，但2个簇的大小不均衡
  4个簇轮廓分数高，且每个簇的轮廓大小比较均衡
  3个簇和5个簇比较糟糕：因为存在低于平均轮廓分数的聚类，轮廓图的大小波动很大

10、聚类小结

  聚类与应用高度相关
  聚类很难评估，但实际应用中很有用
  聚类方法

• 基于中心的模型：如K均值聚类
• 基于连接性的模型：如层次聚类（BIRCH、CURE、CHAMELEON、GRIN）
• 基于分布的模型：基于数据点的产生分布确定模型，如高斯混合模型
• 基于密度的模型：如DBSCAN、OPTICS、DENCLUE、Mean-shift
• 基于图模型的聚类：谱聚类
• 基于网格的聚类：STING、CLIQUE
• 基于模型的聚类：SOM、基于神经网络的聚类

两个通用工具

• EM
• 图及其拉普拉斯矩阵

11、Scikit-Learn中的聚类算法

（1）Classes sklearn.cluster

Classes	Description
cluster.AffinityPropagation(…)	Perform Affinity Propagation Clustering of data.
cluster.AgglomerativeClustering(…)	Agglomerative Clustering.
cluster.Birch(…)	Implements the BIRCH clustering algorithm.
cluster.DBSCAN(…)	Perform DBSCAN clustering from vector array or distance matrix.
cluster.FeatureAgglomeration(…)	Agglomerate features.
cluster.KMeans(…)	K-Means clustering.
cluster.MiniBatchKMeans(…)	Mini-Batch K-Means clustering.
cluster.MeanShift(…)	Mean shift clustering using a flat kernel.
cluster.OPTICS(…)	Estimate clustering structure from vector array.
cluster.SpectralClustering(…)	Apply clustering to a projection of the normalized Laplacian.
cluster.SpectralBiclustering(…)	Spectral biclustering (Kluger, 2003).
cluster.SpectralCoClustering(…)	Spectral Co-Clustering algorithm (Dhillon, 2001).

Scikit-Learn 官方文档

12、Scikit-Learn中的聚类算法示例

13、采用Scikit-Learn进行聚类算法的实例

• Python Data Science Handbook
• Neptune.ai 聚类算法博客