数学基础

发布日期: 2020-11-22

更新日期: 2022-08-27

文章字数: 1.6k

阅读时长: 6 分

阅读次数:

基于numpy的实现代码传送门

聚类的评估没有一个统一的标准，不同于有监督学习的理性评估，像聚类这种无监督学习的评估，完全是基于感性的认识。分成多少类，每个类包含多少个样本，各个簇的划分标准是什么，是基于距离还是基于密度，一千个读者就有一千个哈姆雷特，众口难调。不过，一个统一的看法是，好的聚类模型都是簇内相似度高且簇间相似度低。

所以只能介绍几种经验式的评估标准，至于是否能够真实评估系统的结果，建议结合实际业务，每种指标都算一次，横向比较，挑选一个合适的评估方案。

先给出如下假设

假设给定数据集 $D=\{x_1,...,x_N\}$，聚类后，划分得到簇的集合为 $C=\{c_1,...,c_k\}$，各个样本的簇的标签为 $Y=\{y_1,...,y_N\}$，参考模型划分的簇集为 $C'=\{c'_1,...,c'_{k'}\}$，各个样本的簇的标签为 $Y'=\{y'_1,...,y'_N\}$

1. 聚类前的模型评估（数据质量评估）

数据质量评估即聚类趋势评估，是一种评估样本间是否具有明显的界限进行聚类划分的指标，一般使用霍普金斯统计量（Hopkins Statistics）进行量化评估，其评估流程如下：

从 $N$ 个样本中随机抽取 $n$个样本，对每个样本在样本空间中找一个离其最近的向量，计算两者的距离，用集合 $r=\{r_1,...,r_n\}$ 表示
重复一次步骤1，其距离集合用 $r'=\{r'_1,...,r'_n\}$ 表示
按下式计算霍普金斯统计量 \[ H=\frac{\sum_{i=1}^n r'_i}{\sum_{i=1}^n r_i + \sum_{i=1}^n r'_i} \]
如果H为0.5左右，那么整个样本空间趋向于均匀分布，即没有聚类趋势（聚簇不明显）的空间，没有聚类的价值；如果H趋近于1或0，则说明样本空间有聚类趋势（聚簇明显）的空间，有聚类的价值

2. 聚类后的模型评估（模型质量评估）

根据是否具有参考模型，可分为外部指标（既然都有参考模型，为什么不使用分类方法呢？）和内部指标。

2.1. 外部指标

先进行如下定义 \[ a = |SS|=\sum_{i=1}^N \sum_{j=i}^N I(y_i=y_j,y'_i=y'_j) \\ b = |SD|=\sum_{i=1}^N \sum_{j=i}^N I(y_i=y_j,y'_i \neq y'_j) \\ c = |DS|=\sum_{i=1}^N \sum_{j=i}^N I(y_i \neq y_j,y'_i=y'_j) \\ d = |DD|=\sum_{i=1}^N \sum_{j=i}^N I(y_i \neq y_j,y'_i \neq y'_j) \] 其中，a表示所有样本对 $(x_i,x_j)$ 对在 $C$ 中位同一个簇且在 $C'$ 中也位于同一个簇的数量，其他变量如此类推即可。

Jaccard系数（JC） \[ JC=\frac{a}{a+b+c} \]
FM指数（FMI） \[ FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}} \]
Rand指数（RMI） \[ RI=\frac{2(a+b)}{N(N-1)} \]
调整的Rand指数（ARI） \[ ARI = \frac{RI- E[RI]}{\max(RI) - E[RI]} \]

上面指标中ARI的取值范围为 $[-1,1]$，除了ARI外指标的取值范围都为 $[0,1]$，值越大越好

2.2. 内部指标

2.2.1. 整体评估

同样的，先进行如下定义 \[ avg(c)= \frac{2}{|c|(|c|-1)}\sum_{1\leq i<j\leq |c|} dist(x_i, x_j) \\ diam(c) = \max_{1\leq i<j\leq |c|} dist(x_i, x_j) \\ d_{min}(c_i,c_j)=\min_{x_i\in c_i,x_j \in c_j} dist(x_i, x_j) \\ d_{cen}(c_j,c_j) = dist(\mu_i, \mu_j) \] 其中， $dist(x_i, x_j)$ 是 $(x_i, x_j)$ 之间的距离，$= _{1i < |c|} x_i $ 表示 $c$ 的中心点，则 $avg(c)$ 表示 $c$ 内样本间的平均距离，$diam(c)$ 表示 $c$ 内样本间的最远距离，$d_{min}(c_i,c_j)$ 表示 $(c_i,c_j)$ 间的最近距离，$d_{cen}(c_j,c_j)$ 表示 $(c_j,c_j)$ 间的中心点距离

DB指数（DBI） \[ DBI=\frac{1}{k}\sum_{i=1}^k \max_{j\neq x} (\frac{avg(c_i)+avg(c_j)}{d_{cen}(c_i,c_j)}) \]
Dunn指数（DI） \[ DI=\min_{1\leq i \leq k} (\min_{j\neq i}(\frac{d_{min}(c_i,c_j)}{\max_{1\leq l \leq k} diam(c_l)})) \]

DBI的值越小越好，DI则相反

这里还涉及到距离的计算，这个在k近邻算法中已经提及过，这里不再赘述。

2.2.2. 单点评估

轮廓系数（Silhouette Coefficient）是常用对某个点聚类效果的评估

对于样本空间中任意一个样本 $x$ ，计算其到本类簇其他所以点的距离之和的均值 $a(x)$，其到其他类簇的最近距离的均值 $b(x)$，计算轮廓系数 \[ s(x) = \frac{b(x)-a(x)}{\max(a(x),b(x))} \] 其中，$s(x)\in [-1,1]$，该值越接近1，则该点的聚类越好，反之，则越差，特别地，如果该值为负，表示该点到其他类簇的距离比到本类的距离要小，说明该点已经聚类错误了。

2.2.3. 当前簇评估

Calinski-Harabasz（CH）指标 \[ CH(k) = \frac{trB(k)/(k-1)}{trW(k)/(N-k)} \] 其中，$trB(k)$ 表示当前类与其他类的簇间距离（即簇内中心点的距离或簇内的均值的距离）组成的矩阵的迹，$trW(k)$ 表示当前类簇内距离组成的矩阵的迹

3. 簇数确定

簇数k的确定是一个很重要，但又很难解决的问题。目前没有一个直接选取的方案，一般采取启发性的算法。

肘方法（The Elbow Method）选取k值流程如下

从 $k=1$ 开始，尝试对样本空间进行聚类划分，求聚类后各个簇的中心点，计算簇内各个点到该中心点的距离，最后将所有的距离相加，得到该簇数的距离和 $r(k)$
重复n次步骤1，作 $k-r(k)$ 曲线图，其中k为横坐标，$r(k)$ 为纵坐标。
正常情况下，应该是一条不断下降的曲线，曲线从骤降到平滑对应的拐点，其对应的k值即为选取的k值

至于n的确定，一种经验的方法是，一般簇数k都在 $\sqrt{N}$ 左右，所以取 $n=\sqrt{N}+2$ 即可。