【机器学习基础】第三十三课:聚类之性能度量

外部指标,内部指标,Jaccard系数,FM指数,Rand指数,DB指数,Dunn指数

Posted by x-jeff on January 25, 2022

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.性能度量

聚类性能度量亦称聚类“有效性指标”(validity index),对聚类结果,我们需通过某种性能度量来评估其好坏;另一方面,若明确了最终将要使用的性能度量,则可直接将其作为聚类过程的优化目标,从而更好地得到符合要求的聚类结果。

聚类是将样本集$D$划分为若干互不相交的子集,即样本簇。那么,什么样的聚类结果比较好呢?直观上看,我们希望“物以类聚”,即同一簇的样本尽可能彼此相似,不同簇的样本尽可能不同。换言之,聚类结果的“簇内相似度”(intra-cluster similarity)高且“簇间相似度”(inter-cluster similarity)低。

聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型”(reference model,例如将领域专家给出的划分结果作为参考模型)进行比较,称为“外部指标”(external index);另一类是直接考察聚类结果而不利用任何参考模型,称为“内部指标”(internal index)。

对数据集$D=\{ \mathbf{x}_1 , \mathbf{x}_2 , … , \mathbf{x}_m \}$,假定通过聚类给出的簇划分为$\mathcal{C}=\{C_1,C_2,…,C_k \}$,参考模型给出的簇划分为$\mathcal{C}^*=\{C_1^*,C_2^*,…,C_s^* \}$。相应地,令$\mathbf{\lambda}$与$\mathbf{\lambda}^*$分别表示与$\mathcal{C}$和$\mathcal{C}^*$对应的簇标记向量。我们将样本两两配对考虑,定义:

通常$k\neq s$。

\[a=\lvert SS \rvert, \ SS=\{ (\mathbf{x}_i,\mathbf{x}_j) \mid \lambda_i = \lambda_j, \lambda_i^* = \lambda_j^*,i<j \} \tag{1}\] \[b=\lvert SD \rvert, \ SD=\{ (\mathbf{x}_i,\mathbf{x}_j) \mid \lambda_i = \lambda_j, \lambda_i^* \neq \lambda_j^*,i<j \} \tag{2}\] \[c=\lvert DS \rvert, \ DS=\{ (\mathbf{x}_i,\mathbf{x}_j) \mid \lambda_i \neq \lambda_j, \lambda_i^* = \lambda_j^*,i<j \} \tag{3}\] \[d=\lvert DD \rvert, \ DD=\{ (\mathbf{x}_i,\mathbf{x}_j) \mid \lambda_i \neq \lambda_j, \lambda_i^* \neq \lambda_j^*,i<j \} \tag{4}\]

$\lambda_i$表示样本$\mathbf{x}_i$在$\mathcal{C}$中所属的簇。$\lambda_i^*$表示样本$\mathbf{x}_i$在$\mathcal{C}^*$中所属的簇。

其中集合$SS$包含了在$\mathcal{C}$中隶属于相同簇且在$\mathcal{C}^*$中也隶属于相同簇的样本对,集合$SD$包含了在$\mathcal{C}$中隶属于相同簇但在$\mathcal{C}^*$中隶属于不同簇的样本对。由于每个样本对$(\mathbf{x}_i,\mathbf{x}_j)(i<j)$仅能出现在一个集合中,因此有$a+b+c+d=m(m-1)/2$成立。

基于式(1)~式(4)可导出下面这些常用的聚类性能度量外部指标:

👉Jaccard系数(Jaccard Coefficient,简称JC):

\[JC=\frac{a}{a+b+c} \tag{5}\]

👉FM指数(Fowlkes and Mallows Index,简称FMI):

\[FMI=\sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c} } \tag{6}\]

👉Rand指数(Rand Index,简称RI):

\[RI=\frac{2(a+d)}{m(m-1)} \tag{7}\]

显然,上述性能度量的结果值均为$[0,1]$区间,值越大越好。

考虑聚类结果的簇划分$\mathcal{C}=\{C_1,C_2,…,C_k \}$,定义:

\[avg(C)=\frac{2}{\lvert C \rvert (\lvert C \rvert -1)} \sum_{1 \leqslant i <j \leqslant \lvert C \rvert} dist (\mathbf{x}_i,\mathbf{x}_j) \tag{8}\] \[diam(C)=\max _{1 \leqslant i <j \leqslant \lvert C \rvert} dist (\mathbf{x}_i,\mathbf{x}_j) \tag{9}\] \[d_{min}(C_i,C_j) = \min_{\mathbf{x}_i \in C_i , \mathbf{x}_j \in C_j} dist (\mathbf{x}_i,\mathbf{x}_j) \tag{10}\] \[d_{cen} (C_i,C_j)=dist(\mathbf{\mu}_i,\mathbf{\mu}_j) \tag{11}\]

其中,$dist(\cdot,\cdot)$用于计算两个样本之间的距离(距离越大则样本的相似度越低);$\mathbf{\mu}$代表簇$C$的中心点$\mathbf{\mu}=\frac{1}{\lvert C \rvert} \sum_{1 \leqslant i \leqslant \lvert C \rvert} \mathbf{x}_i$。显然,$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$中心点间的距离。

基于式(8)~(11)可导出下面这些常用的聚类性能度量内部指标:

👉DB指数(Davies-Bouldin Index,简称DBI):

\[DBI=\frac{1}{k} \sum^k_{i=1} \max_{j\neq i} (\frac{avg(C_i) + avg(C_j)}{d_{cen}(\mathbf{\mu}_i,\mathbf{\mu}_j)}) \tag{12}\]

👉Dunn指数(Dunn Index,简称DI):

\[DI=\min_{1 \leqslant i \leqslant k} \{ \min_{j\neq i} (\frac{d_{min} (C_i,C_j)}{\max_{1\leqslant l \leqslant k} diam(C_l)}) \} \tag{13}\]

显然,DBI的值越小越好,而DI则相反,值越大越好。