【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
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}^*$对应的簇标记向量。我们将样本两两配对考虑，定义：
\[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}\]通常$k\neq s$。
$\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则相反，值越大越好。
