学习笔记【机器学习重点与实战】——8 聚类基础(评价指标/距离/相似度)

1 基本概念

在”无监督学习” (unsupervised learning) 中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。

聚类（clustering）就是一种研究最多、应用最广的无监督学习。对于大量未知标注的数据集，按照数据的内在相似性将数据集划分为多个类别，将相似的对象归到同一个簇中，使得簇内的数据相似度较大，而簇间的数据相似度较小。即有点像全自动分类，簇内的对象越相似，聚类的效果越好。

2 评价指标

2.1 样本无标签

（1）Silhouette Coefficient - 轮廓系数

较高的 Silhouette Coefficient 得分与具有更好定义的聚类的模型相关。Silhouette Coefficient 是为每个样本定义的，由两个得分组成:

• a: 样本与同一类别中所有其他点之间的平均距离。
• b: 样本与 下一个距离最近的簇 中的所有其他点之间的平均距离。

然后将单个样本的 Silhouette 系数 s 给出为:

s=b−amax(a,b) $$s=\frac{b-a}{max(a,b)}$$

给定一组样本的 Silhouette 系数作为每个样本的 Silhouette 系数的平均值。

实现代码如下：

from sklearn.metrics.cluster import silhouette_score
silhouette_score(X, labels, metric='euclidean')

（2）Calinski-Harabaz

较高的 Calinski-Harabaz 的得分与具有更好定义的聚类的模型相关。类别内部数据的协方差越小越好，类别之间的协方差越大越好，这样的Calinski-Harabasz分数会高。 最大的优势是比轮廓系数快很多。

对于 k 簇，Calinski-Harabaz 得分 s 是作为 between-clusters dispersion mean （簇间色散平均值）与 within-cluster dispersion（群内色散之间）的比值给出的:

s(k)=Tr(Bk)Tr(Wk) $$s(k)=\frac{\mathrm{T}\mathrm{r}(B_k)}{\mathrm{T}\mathrm{r}(W_k)}$$

其中 BK $B_K$ 是 between group dispersion matrix （组间色散矩阵）， WK $W_K$ 是由以下定义的 within-cluster dispersion matrix （群内色散矩阵）:

Wk=∑q=1k∑x∈Cq(x−cq)(x−cq)T $$W_k=\underset{q=1}{\overset{k}{\sum }}\underset{x\in C_q}{\sum }(x-c_q)(x-c_q{)}^T$$

Bk=∑qnq(cq−c)(cq−c)T $$B_k=\underset{q}{\sum }{n}_q(c_q-c)(c_q-c{)}^T$$

N 为数据中的点数，C_q为 cluster （簇） q 中的点集， C_q 为 cluster（簇） 的 q 中心，c 为 E 的中心，n_q为 cluster（簇） 中的 q 点数。

实现代码如下：

from sklearn.metrics.cluster import calinski_harabaz_score
calinski_harabaz_score(X, labels)

（3）Compactness - 紧密性 CP

CP计算每一个类各点到聚类中心的平均距离。CP越低意味着类内聚类距离越近。但没有考虑类间效果。

（4）Separation - 间隔性 SP

SP计算各聚类中心两两之间平均距离。SP越高意味类间聚类距离越远。但没有考虑类内效果。

（5）Davies-Bouldin Index - DBI

DB计算任意两类别的类内距离平均距离(CP)之和除以两聚类中心距离，求最大值。DB越小意味着类内距离越小，同时类间距离越大。但因使用欧式距离，所以对于环状分布，聚类评测很差。

（6）Dunn Validity Index - DVI

DVI计算任意两个簇元素的最短距离(类间)除以任意簇中的最大距离(类内)。DVI越大意味着类间距离越大，同时类内距离越小。但对离散点的聚类测评很高、对环状分布测评效果差。

2.2 样本有标签

（1）Homogeneity - 均一性

每个簇只包含一个类的成员。

实现代码如下：

from sklearn.metrics.cluster import homogeneity_score
homogeneity_score(labels_true, labels_pred)

若labels_true = [0, 0, 1, 1]，labels_pred = [1, 1, 0, 0]；homogeneity_score = 1.0。

（2）Completeness - 完整性

给定类的所有成员都分配给同一个簇。

实现代码如下：

from sklearn.metrics.cluster import completeness_score
completeness_score(labels_true, labels_pred)

若labels_true = [0, 0, 1, 1]，labels_pred = [0, 1, 0, 1]；completeness_score = 0.0。

（3）V-measure

均一性和完整性的加权平均。

实现代码如下：

from sklearn.metrics.cluster import v_measure_score
v_measure_score(labels_true, labels_pred)

若labels_true = [0, 0, 1, 2]，labels_pred = [0, 0, 1, 1]；v_measure_score = 0.8。

（4）Rand index - 兰德指数 RI 、Adjusted Rand index - 调整兰德指数 ARI

RI=2(a+d)m(m−1) $$RI=\frac{2(a+d)}{m(m-1)}$$

RI取值范围为[0,1]，越大表示聚类效果准确性越高，同时每个类内的纯度越高。

为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：

ARI=RI−E|RI|max(RI)−E|RI| $$ARI=\frac{RI-E|RI|}{max(RI)-E|RI|}$$

ARI取值范围为[−1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。

实现代码如下：

from sklearn.metrics.cluster import adjusted_rand_score
adjusted_rand_score(labels_true, labels_pred)

若labels_true = [0, 0, 1, 2]，labels_pred = [0, 0, 1, 1]；v_measure_score = 0.57。

（5）Normalized Mutual Information - 标准互信息NMI、Mutual Information - 互信息MI、Adjusted Mutual Information - 调整互信息MI

利用基于互信息的方法来衡量聚类效果需要实际类别信息，NIM是用熵做分母将MI值调整到0与1之间。NMI与MI取值范围为[0,1]，AMI取值范围为[−1,1]，值越大意味着聚类结果与真实情况越吻合。

实现代码如下：

from sklearn.metrics.cluster import adjusted_mutual_info_score
adjusted_mutual_info_score(labels_true, labels_pred)

若labels_true = [0, 0, 0, 0]，labels_pred = [0, 1, 2, 3]；v_measure_score = 0.0。

3 距离/相似度计算

“距离度量” (distance measure) ，则需满足一些基本性质：

非负性同一性对称性直递性：dist(xi,xj)≥0：di的xi,xj)=0当且仅当xi=xj：dist(xi,xj)=dist(xj,xi)：dist(xi,xj)≤dist(xi,xk)+dist(xk,xj)(3)(4)(5)(6) $$\begin{array}{}\text{(3)}& 非负性& ：dist(x_i,x_j)\ge 0\text{(4)}& 同一性& ：di的x_i,x_j)=0当且仅当x_i=x_j\text{(5)}& 对称性& ：dist(x_i,x_j)=dist(x_j,x_i)\text{(6)}& 直递性& ：dist(x_i,x_j)\le dist(x_i,x_k)+dist(x_k,x_j)\end{array}$$

（1）Euclidean Distance - 欧式距离

以古希腊数学家欧几里得命名的距离；也就是我们直观的两点之间直线最短的直线距离。

d=∑i=1n(xi−yi)2−−−−−−−−−−√ $$d=\sqrt{\underset{i=1}{\overset{n}{\sum }}(x_i-y_i{)}^2}$$

（2）Manhattan Distance - 曼哈顿距离

是由十九世纪的赫尔曼·闵可夫斯基所创词汇；是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和；也就是和象棋中的“車”一样横平竖直的走过的距离；曼哈顿距离是超凸度量。

d=∑i=1n|xi−yi| $$d=\underset{i=1}{\overset{n}{\sum }}|x_i-y_i|$$

（3）Minkowski Distance - 闵氏距离

以俄罗斯数学家闵可夫斯基命名的距离；是欧式距离的推广，p=2时等价于欧氏距离，和p-范数等值。

d=∑i=1n(xi−yi)p−−−−−−−−−−√p $$d=\sqrt[p]{\underset{i=1}{\overset{n}{\sum }}(x_i-y_i{)}^p}$$

（4）Jaccard Coefficient - 杰卡德相似系数

越大越相似；分子是A和B的交集大小，分母是A和B的并集大小。

J(A,B)=|A⋂B||A⋃B| $$J(A,B)=\frac{|A\bigcap B|}{|A\bigcup B|}$$

（5）Cosine Similarity - 余弦相似度

S=x⋅y|x||y| $$S=\frac{x\cdot y}{|x||y|}$$

（6）Pearson Correlation - 皮亚逊相关系数

分子是两个集合的交集大小，分母是两个集合大小的几何平均值。是余弦相似性的一种形式。

r=∑ni=1(Xi−x¯¯¯)(yi−y¯¯¯)∑ni=1(Xi−x¯¯¯)2−−−−−−−−−−−−√∑ni=1(yi−y¯¯¯)2−−−−−−−−−−−√ $$r=\frac{\underset{i=1}{\overset{n}{\sum }}(X_i-\bar{x})(y_i-\bar{y})}{\sqrt{\underset{i=1}{\overset{n}{\sum }}(X_i-\bar{x}{)}^2}\sqrt{\underset{i=1}{\overset{n}{\sum }}(y_i-\bar{y}{)}^2}}$$

（7）Kullback-Leibler Divergence - K-L散度

即相对熵；是衡量两个分布(P、Q)之间的距离；越小越相似。

D(P||Q)=∑i=1nP(i)logP(i)Q(i) $$D(P||Q)=\underset{i=1}{\overset{n}{\sum }}P(i)log\frac{P(i)}{Q(i)}$$

4 参考

1. 机器学习升级版视频 - 邹博
2. 《机器学习 - 周志华》第9章 聚类
3. 《机器学习实战》第10章 利用K-均值聚类算法对未标注数据分组
4. 18种和“距离(distance)”、“相似度(similarity)”相关的量的小结

---

===========文档信息============
学习笔记由博主整理编辑，供非商用学习交流用
如本文涉及侵权，请随时留言博主，必妥善处置
版权声明：非商用*转载-保持署名-注明出处
署名(BY) ：dkjkls（dkj卡洛斯）
文章出处：http://blog.csdn.net/dkjkls