聚类结果评估

一个好的聚类结果要求较高的簇内相似度 (intra-) 和较低的簇间相似度 (inter-) 。根据模型比较的对象不同,聚类结果评估指标可以分为外部指标 (external)内部指标 (internal) 两类:

  • 外部指标:需要参考模型,比较样本在不同模型中的分类情况;
  • 内部指标:基于自己的聚类结果,不借助模型间的比较。

外部指标

外部指标一般基于样本对分类一致性情况导出。

集合表示

$n$ 个样本的集合共有 $\mathrm{C}_n^2$ 个样本对,按照每个样本对在本模型和参考模型中的分类一致性可以将所有样本对分为四类:
$$
a=|SS|, \quad SS = \left\lbrace{
\left({\boldsymbol{x}_i,\boldsymbol{x}_j}\right)\;|\;
\lambda_i = \lambda_j, \; \lambda_i^\ast = \lambda_j^\ast, \; i < j
}\right\rbrace \\
b=|SD|, \quad SD = \left\lbrace{
\left({\boldsymbol{x}_i,\boldsymbol{x}_j}\right)\;|\;
\lambda_i = \lambda_j, \; \lambda_i^\ast \neq \lambda_j^\ast, \; i < j
}\right\rbrace \\
c=|DS|, \quad SD = \left\lbrace{
\left({\boldsymbol{x}_i,\boldsymbol{x}_j}\right)\;|\;
\lambda_i \neq \lambda_j, \; \lambda_i^\ast = \lambda_j^\ast, \; i < j
}\right\rbrace \\
b=|DD|, \quad DD = \left\lbrace{
\left({\boldsymbol{x}_i,\boldsymbol{x}_j}\right)\;|\;
\lambda_i \neq \lambda_j, \; \lambda_i^\ast \neq \lambda_j^\ast, \; i < j
}\right\rbrace
$$
上面的定义中,$\lambda_i$ 表示样本 $i$ 在本模型中的类别,$\lambda_i^\ast$ 表示样本 $i$ 在参考模型中的类别。

因此直观理解上面的定义:

  • $SS$ 是在本模型中属于同一类、在参考模型中也属于同一类的样本对的集合,$a$ 是集合 $SS$ 的元素个数;
  • $SD$ 是在本模型中属于同一类、在参考模型中不属于同一类的样本对的集合,$b$ 是集合 $SD$ 的元素个数;
  • $DS$ 是在本模型中不属于同一类、在参考模型中属于同一类的样本对的集合,$c$ 是集合 $DS$ 的元素个数;
  • $DD$ 是在本模型中不属于同一类、在参考模型中也不属于同一类的样本对的集合,$d$ 是集合 $DD$ 的元素个数

当参考分布是真实分布时,此时参考模型是理想模型,即
$$
SS = TP \; \text{(真阳性); } SD = FP \; \text{(假阳性); }
DS = FN \; \text{(假阴性); } SS = TN \; \text{(真阴性); }
$$
矩阵表示

样本对的分类一致性也可以通过两个矩阵表示
$$
X_{pair}=\left[\begin{matrix}
I(x_1,x_1) & I(x_1,x_2) & \cdots & I(x_1,x_n) \\
I(x_2,x_1) & I(x_2,x_2) & \cdots & I(x_2,x_n) \\
\vdots & \vdots & \ddots & \vdots \\
I(x_n,x_1) & I(x_n,x_2) & \cdots & I(x_n,x_n)
\end{matrix}\right]
$$

$$
Y_{pair}=\left[\begin{matrix}
I^\ast(x_1,x_1) & I^\ast(x_1,x_2) & \cdots & I^\ast(x_1,x_n) \\
I^\ast(x_2,x_1) & I^\ast(x_2,x_2) & \cdots & I^\ast(x_2,x_n) \\
\vdots & \vdots & \ddots & \vdots \\
I^\ast(x_n,x_1) & I^\ast(x_n,x_2) & \cdots & I^\ast(x_n,x_n)
\end{matrix}\right]
$$

$I(x_i,x_j) \in \lbrace 0, \; 1 \rbrace$ :0表示本模型将 $x_i$ 和 $x_j$ 两个样本分为同一类,1表示分为不同类;

$I^\ast(x_i,x_j) \in \lbrace 0, \; 1 \rbrace$ :0表示参考模型将 $x_i$ 和 $x_j$ 两个样本分为同一类,1表示分为不同类;

所以 $X_{pair}(n \times n)$ 和 $Y_{pair}(n \times n)$ 是二值矩阵。

从矩阵可以导出四个集合(矩阵中1对应的样本对属于该集合):
$$
\begin{split}
SS &= 1 - X_{pair} \; | \; Y_{pair} \\
SD &= \frac{Y_{pair} - X_{pair} + 1}2 \\
DS &= \frac{X_{pair} - Y_{pair} + 1}2 \\
DD &= X_{pair} \; \& \; Y_{pair}
\end{split}
$$


Jaccard系数

杰卡德系数 (Jaccard Coefficient, JC) 用于比较 有限 集合$X$和$Y$之间的相似性与差异性。
$$
\mathrm{JC} = \frac{|DD|}{|SD|+|DS|+|DD|} = \frac{|DD|}{1-|SS|} = \frac{X_{pair} \; \& \; Y_{pair}}{X_{pair} \; | \; Y_{pair}}
$$
适用于 稀疏 & 二值 矩阵。

系数 & 多值矩阵可用Tanimoto系数。


Tanimoto系数

Tanimoto系数又叫广义Jaccard系数,用来计算两个稀疏向量间的相似性,向量各分量取值0到1。
$$
\mathrm{EJ}(A,B) = \frac{A \cdot B}{||A|| + ||B|| - A \cdot B}
$$
$\mathrm{EJ}$ 系数常见的计算方式还有另一种

假设 $k$ 个特征,即 $A=(a_1,\;a_2,\;\cdots,\;a_k)$,$B=(b_1,\;b_2,\;\cdots,\;b_k)$
$$
\mathrm{EJ}(A,B) = \frac{\sum_{i=1}^k \min{(a_i,b_i)}}{\sum_{i=1}^k \max{(a_i,b_i)}}
$$
连续情况定义如下
$$
\mathrm{EJ}(f,g) = \frac{\int \min(f,g)dx}{\int \max(f,g)dx}
$$


FM指数

FM指数 (Fowlkes and Mallows lndex,FMI) 多用于衡量两个层次聚类间或者与基准参考聚类模型间的相似度。

与基准聚类模型比较

$$
\mathrm{FMI}=\sqrt{\frac{|TP|}{|TP|+|FP|} \times \frac{|TP|}{|TP|+|FN|}}
$$

层次聚类模型比较


RI 和 ARI

给定 $n$ 个样本的集合 $S$,$X={X_1,X_2,{\cdots},X_r}$ 和 $Y={Y_1,Y_2,{\cdots},Y_s}$ 是关于 $S$ 的两个的划分。因为聚类的过程就是再对数据集进行划分,所以一个划分就等效于一个聚类模型。X和Y同时也意味着两个聚类模型 (clustering)。

RI

定义兰德指数 (Rand Index, RI)
$$RI = \frac{|SS|+|DD|}{|SS|+|SD|+|DS|+|DD|} = \frac{||SS|+|DD|}{C_n^2}$$
直观上理解,分子是X和Y认可一致的配对,分母是所有可能的配对。当Y是基准划分时,RI表示真阳性数据和真阴性数据所占的比重。

ARI

为了实现“在聚类结果随机产生的情况下,指标应该接近零”提出了 调整兰德指数 (Adjusted Rand Index, ARI)

构建列联表 (contingency table):

其中 $n_{ij}$ 表示X的第i簇与Y的第j簇共有的元素,即 $n_{ij}=|X_i{\cap}Y_j|$。

ARI 定义如下:
$$
\mathrm{ARI} = \frac { \mathrm{RI} - E[\mathrm{RI}] } { \max {(\mathrm{RI})} - E[\mathrm{RI}] }
= \frac
{
\overbrace{
\sum_{ij}{C_{n_{ij}}^2}
}^{\text{Index}} -
\overbrace{
\frac{\sum_i C_{a_i}^2\sum_j C_{b_i}^2}{C_n^2}
}^{\text{Expected Index}}
}{
\underbrace{
\frac{\sum_i C_{a_i}^2+\sum_j C_{b_i}^2}2
}_{\text{Max Index}} -
\underbrace{
\frac{\sum_i C_{a_i}^2\sum_j C_{b_i}^2}{C_n^2}
}_{\text{Expected Index}}
}
$$
ARI 的取值范围扩展到了[-1, 1],起到了衡量 两组数据分布的吻合程度 的作用。


MI 和 NMI

互信息 (Mutual Information, MI)
$$
MI(X,Y)=\sum_{x,y}{ p(x,y)\log{ \frac{p(x,y)}{p(x)p(y)} } }
$$

标准互信息 (Normalized Mutual Information, NMI)
$$
U(X,Y)=2R=2\frac{I(X;Y)}{H(X)+H(Y)}
$$

$$
H(X)= \sum_{i=1}^{n}{p(x_i)I(x_i)}
= \sum_{i=1}^{n}{p(x_i)\log_b{\frac1{p(x_i)}}}
= -\sum_{i=1}^{n}{p(x_i)\log_b{p(x_i)}}
$$


内部指标

所谓的内部指标就是基于本模型的聚类结果进行计算。

为了衡量样本之间的相似性和差异性,我们需要先定义一个距离公式 dist(a, b) ,距离的定义需要满足下面四个基本性质:

  1. $dist(a, b) {\ge} 0$ 恒成立
  2. 当且仅当 a = b 时 $dist(a, b) = 0$
  3. 对称:$dist(a, b) = dist(b, a)$
  4. 三角不等式: $dist(a, b) {\le} dist(a, c) + dist(c, b)$

当然也可以使用经典距离,例如欧式距离、余弦距离、Hamming距离等等。基于距离,我们定义以下量:

  1. $avg(C)$:簇内两点间的平均距离
  2. $diam(C)$:簇内样本间的最大距离
  3. $d_{min}(C_i,C_j)$:两个簇最近样本间的距离
  4. $d_{cen}(C_i,C_j)$:两个簇中心点(簇的重心)间的距离

Davies-Bouldin Index

戴维森堡丁指数 (Davies-Bouldin Index, DBI)
$$
\mathrm{DB} = \frac1k \sum_{i=1}^k \max \limits_{j \neq i}
\left ( \frac
{ \overline{C_i} + \overline{C_j} }
{ || w_i - w_j ||_2 }
\right )
$$


邓恩指数

邓恩指数 (Dunn Validity Index, DVI) 对环状等奇葩分布效果很差
$$
\mathrm{DVI} = \frac
{\min \limits_{0<m \neq n<K}
\left\lbrace
\min \limits_{\forall x_i \in \Omega_m \\ \forall x_j \in \Omega_n }
\left\lbrace || x_i - x_j || \right\rbrace
\right\rbrace}
{\max \limits_{0<m \le K} \max \limits_{\forall x_i,x_j \in \Omega_m}
\left\lbrace ||x_i - x_j|| \right\rbrace}
$$

轮廓系数 (Silhouette coefficient)

----- For reprint please indicate the source -----
0%