Java教程
聚类算法指标整理
文章目录
- 前言
- 纯度(purity)
- 纯度的计算Python代码
- 标准互信息(NMI)
- 熵
- 互信息
- 标准互信息
- MI 和 NMI的计算实现 Python 版
- 调整互信息(AMI)
- 示例代码
- 兰德系数(Rand Index)
- 示例代码
- 调整兰德系数(Adjusted Rand index)
- 示例代码
前言
本文主要介绍聚类算法的一些常见评测指标。
假设某一种算法得到聚类结果为:
A = [ 1 2 1 1 1 1 1 2 2 2 2 3 1 1 3 3 3 ] \mathrm{A}=\left[\begin{array}{lllllllll} 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 1 & 1 & 3 & 3 & 3 \end{array}\right] A=[12111112222311333]
标准的聚类结果为：
B
=
[
1
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
]
\mathrm{B}=\left[\begin{array}{llllllll} 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 \end{array}\right]
B=[11111122222233333]
那么如何评价该算法的聚类效果？
纯度(purity)
把每个簇中最多的类作为这个簇所代表的类，然后计算正确分配的类的数量，然后除以总数：
纯度计算如下：
purity = ( cluster A + cluster B + cluster C ) total = ( 4 + 5 + 4 ) 18 = 0.722 \text { purity }=\frac{(\text { cluster } A+\text { cluster } B+\text { cluster } C)}{\text { total }}=\frac{(4+5+4)}{18}=0.722 purity = total ( cluster A+ cluster B+ cluster C)=18(4+5+4)=0.722
一般而言，纯度随着clusters数量的增加而增加。例如，将每个样本结果分为一个单独的簇，此时纯度为1。鉴于此，不能简单用纯度来衡量聚类质量与聚类数量之间的关系。
纯度的计算Python代码
def purity(result, label):
# 计算纯度
total_num = len(label)
cluster_counter = collections.Counter(result)
original_counter = collections.Counter(label)
t = []
for k in cluster_counter:
p_k = []
for j in original_counter:
count = 0
for i in range(len(result)):
if result[i] == k and label[i] == j: # 求交集
count += 1
p_k.append(count)
temp_t = max(p_k)
t.append(temp_t)
return sum(t)/total_num
标准互信息(NMI)
熵
标准互信息(Normalized mutual information, NMI)这个指标源自信息论，所以需要先了解熵(entropy)的概念。熵这个概念是用于量化不确定性，熵的定义如下：
H
(
p
)
=
−
∑
i
p
i
log
2
(
p
i
)
H(p)=-\sum_{i} p_{i} \log _{2}\left(p_{i}\right)
H(p)=−i∑pilog2(pi)
其中
P
i
P_i
Pi表示label为
i
i
i的概率。延续上述示例，可以计算其熵。
class A ： 6 / 18
class B ：7 / 18
class C ：5 / 18
entropy
=
−
(
(
6
18
)
⋅
log
(
6
18
)
)
−
(
(
7
18
)
⋅
log
(
7
18
)
)
−
(
(
5
18
)
⋅
log
(
5
18
)
)
\text { entropy}=-\left(\left(\frac{6}{18}\right) \cdot \log \left(\frac{6}{18}\right)\right)-\left(\left(\frac{7}{18}\right) \cdot \log \left(\frac{7}{18}\right)\right)-\left(\left(\frac{5}{18}\right) \cdot \log \left(\frac{5}{18}\right)\right)
entropy=−((186)⋅log(186))−((187)⋅log(187))−((185)⋅log(185))
其值为 1.089。需要注意的是：当类别或标签分布均匀时，熵值比较高。
熵随着不确定性的减小而减小。假设我们有两个类，其中类A中有9个数据点，类B中有1个数据点。在这种情况下，如果我们要预测一个随机选择的数据点的类别，我们会比之前的情况更确定。这是因为此时熵计算如下，结果值为0.325：
entropy
=
−
(
(
9
10
)
⋅
log
(
9
10
)
)
−
(
(
1
10
)
⋅
log
(
1
10
)
)
\text { entropy }=-\left(\left(\frac{9}{10}\right) \cdot \log \left(\frac{9}{10}\right)\right)-\left(\left(\frac{1}{10}\right) \cdot \log \left(\frac{1}{10}\right)\right)
entropy =−((109)⋅log(109))−((101)⋅log(101))
以上即为熵的概念。
互信息
互信息是用以衡量数据分布之间的相关性。互信息越高，相关性也越高。两个离散随机变量 X X X 和 Y Y Y的互信息定义如下：
M I ( X , Y ) = ∑ x = 1 ∣ X ∣ ∑ y = 1 ∣ Y ∣ P ( x , y ) log ( P ( x , y ) P ( x ) P ( y ) ) M I(X, Y)=\sum_{x=1}^{|X|} \sum_{y=1}^{|Y|} P(x, y) \log \left(\frac{P(x, y)}{P(x) P(y)}\right) MI(X,Y)=x=1∑∣X∣y=1∑∣Y∣P(x,y)log(P(x)P(y)P(x,y))
其中 p ( x , y ) p(x,y) p(x,y) 是 X X X 和 Y Y Y 的联合概率分布函数，而 p ( x ) p(x) p(x)和 p ( y ) p(y) p(y)分别是 X X X 和 Y Y Y 的边缘概率分布函数。 ∣ X ∣ 和 ∣ Y ∣ |X|和|Y| ∣X∣和∣Y∣ 分别表示两个变量的取值集合范围。
以决策树为例，特征A对训练数据集D的信息增益，定义为集合D的经验熵 H ( D ) H(D) H(D)与特征A给定条件下D的经验条件熵 H ( D ∣ A ) H(D|A) H(D∣A)之差，这2者的差值即为互信息。换句话说，熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
以背景问题为例，可以进行如下计算。
首先计算上式分子中联合概率分布 P ( i , j ) = ∣ X i ∩ Y j ∣ N P(i, j)=\frac{\left|X_{i} \cap Y_{j}\right|}{N} P(i,j)=N∣Xi∩Yj∣。PS: X i X_i Xi等同于 x x x, Y j Y_j Yj等同于 y y y。
其中红色线框表示 P ( 1 , 1 ) P(1,1) P(1,1)，即预测结果为类别1，标准为类别1。依次类推，可以得到全部的 P ( i , j ) P(i,j) P(i,j)值。
P ( 1 , 1 ) = 5 / 17 , P ( 1 , 2 ) = 1 / 17 , P ( 1 , 3 ) = 2 / 17 P ( 2 , 1 ) = 1 / 17 , P ( 2 , 2 ) = 4 / 17 , P ( 2 , 3 ) = 0 P ( 3 , 1 ) = 0 , P ( 3 , 2 ) = 1 / 17 , P ( 3 , 3 ) = 3 / 17 \begin{aligned} &P(1,1)=5 / 17, P(1,2)=1 / 17, P(1,3)=2 / 17 \\ &P(2,1)=1 / 17, P(2,2)=4 / 17, P(2,3)=0 \\ &P(3,1)=0, P(3,2)=1 / 17, P(3,3)=3 / 17 \end{aligned} P(1,1)=5/17,P(1,2)=1/17,P(1,3)=2/17P(2,1)=1/17,P(2,2)=4/17,P(2,3)=0P(3,1)=0,P(3,2)=1/17,P(3,3)=3/17
再计算分母中概率函数 P ( i ) = X i / N , P ( i ) P(i)=X_{i} / N, P(i) P(i)=Xi/N,P(i) 为 i i i 的概率分布函数, P ( j ) P(j) P(j) 为 j j j 的概率分布函数：
对于
P
(
i
)
P(i)
P(i) ：
P
(
1
)
=
8
/
17
,
P
(
2
)
=
5
/
17
,
p
(
3
)
=
4
/
17
P(1)=8 / 17, P(2)=5 / 17, p(3)=4 / 17
P(1)=8/17,P(2)=5/17,p(3)=4/17
即统计算法预测结果中，各个类别的占比。
对于
P
(
j
)
:
P(j):
P(j):
P
(
1
)
=
6
/
17
,
P
(
2
)
=
6
/
17
,
P
(
3
)
=
5
/
17
P(1)=6 / 17, P(2)=6 / 17, P(3)=5 / 17
P(1)=6/17,P(2)=6/17,P(3)=5/17
即统计标准结果中，各个类别的占比。
据此，可以计算得到互信息 MI = 0.5654
M
I
=
P
(
1
,
1
)
∗
log
P
(
1
,
1
)
P
(
i
=
1
)
P
(
j
=
1
)
+
P
(
1
,
2
)
∗
log
P
(
1
,
2
)
P
(
i
=
1
)
P
(
j
=
2
)
+
P
(
1
,
3
)
∗
log
P
(
1
,
3
)
P
(
i
=
1
)
P
(
j
=
3
)
+
P
(
2
,
1
)
∗
log
P
(
2
,
1
)
P
(
i
=
2
)
P
(
j
=
1
)
+
P
(
2
,
2
)
∗
log
P
(
2
,
2
)
P
(
i
=
2
)
P
(
j
=
2
)
+
P
(
2
,
3
)
∗
log
P
(
2
,
3
)
P
(
i
=
2
)
P
(
j
=
3
)
+
P
(
3
,
1
)
∗
log
P
(
3
,
1
)
P
(
i
=
3
)
P
(
j
=
1
)
+
P
(
3
,
2
)
∗
log
P
(
3
,
2
)
P
(
i
=
3
)
P
(
j
=
2
)
+
P
(
3
,
3
)
∗
log
P
(
3
,
3
)
P
(
i
=
3
)
P
(
j
=
3
)
MI = P(1,1)*\log \frac{P(1, 1)}{P(i=1)P(j=1)} + P(1,2)*\log \frac{P(1, 2)}{P(i=1)P(j=2)} + P(1,3)*\log \frac{P(1, 3)}{P(i=1)P(j=3)} + \\ P(2,1)*\log \frac{P(2, 1)}{P(i=2)P(j=1)} + P(2,2)*\log \frac{P(2, 2)}{P(i=2)P(j=2)} + P(2,3)*\log \frac{P(2, 3)}{P(i=2)P(j=3)} + \\ P(3,1)*\log \frac{P(3, 1)}{P(i=3)P(j=1)} + P(3,2)*\log \frac{P(3, 2)}{P(i=3)P(j=2)} + P(3,3)*\log \frac{P(3, 3)}{P(i=3)P(j=3)}
MI=P(1,1)∗logP(i=1)P(j=1)P(1,1)+P(1,2)∗logP(i=1)P(j=2)P(1,2)+P(1,3)∗logP(i=1)P(j=3)P(1,3)+P(2,1)∗logP(i=2)P(j=1)P(2,1)+P(2,2)∗logP(i=2)P(j=2)P(2,2)+P(2,3)∗logP(i=2)P(j=3)P(2,3)+P(3,1)∗logP(i=3)P(j=1)P(3,1)+P(3,2)∗logP(i=3)P(j=2)P(3,2)+P(3,3)∗logP(i=3)P(j=3)P(3,3)
PS: 以下证明了互信息和熵之间的关系
I
(
X
;
Y
)
=
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
p
(
x
)
p
(
y
)
=
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
p
(
x
)
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
y
)
=
∑
x
,
y
p
(
x
)
p
(
y
∣
x
)
log
p
(
y
∣
x
)
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
y
)
=
∑
x
p
(
x
)
(
∑
y
p
(
y
∣
x
)
log
p
(
y
∣
x
)
)
−
∑
y
log
p
(
y
)
(
∑
x
p
(
x
,
y
)
)
=
−
∑
x
p
(
x
)
H
(
Y
∣
X
=
x
)
−
∑
y
log
p
(
y
)
p
(
y
)
=
−
H
(
Y
∣
X
)
+
H
(
Y
)
=
H
(
Y
)
−
H
(
Y
∣
X
)
\begin{aligned} I(X ; Y) &=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)} \\ &=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)}-\sum_{x, y} p(x, y) \log p(y) \\ &=\sum_{x, y} p(x) p(y \mid x) \log p(y \mid x)-\sum_{x, y} p(x, y) \log p(y) \\ &=\sum_{x} p(x)\left(\sum_{y} p(y \mid x) \log p(y \mid x)\right)-\sum_{y} \log p(y)\left(\sum_{x} p(x, y)\right) \\ &=-\sum_{x} p(x) H(Y \mid X=x)-\sum_{y} \log p(y) p(y) \\ &=-H(Y \mid X)+H(Y) \\ &=H(Y)-H(Y \mid X) \end{aligned}
I(X;Y)=x,y∑p(x,y)logp(x)p(y)p(x,y)=x,y∑p(x,y)logp(x)p(x,y)−x,y∑p(x,y)logp(y)=x,y∑p(x)p(y∣x)logp(y∣x)−x,y∑p(x,y)logp(y)=x∑p(x)(y∑p(y∣x)logp(y∣x))−y∑logp(y)(x∑p(x,y))=−x∑p(x)H(Y∣X=x)−y∑logp(y)p(y)=−H(Y∣X)+H(Y)=H(Y)−H(Y∣X)
关系如下图所示：
标准互信息
互信息 I ( X ; Y ) I(X ; Y) I(X;Y)用于衡量当得知算法聚类结果是什么时(Y)，关于分类的已知知识(X)会增加的信息量。如果聚类相对于已知的分类是无关的，那么 I ( X ; Y ) I(X ; Y) I(X;Y)的最小值为0。此时，知道文本在特定的簇中不会给我们提供关于它类别的新信息。当聚类数量=样本数量，即每个文本都在一个类中时，会达到最大互信息值。所以，互信息有着和纯度同样的问题：不惩罚聚类的细分聚类结果。为此，需要引入其他条件相同的时候，簇越少越好。为更好的比较不同聚类结果，提出了标准化互信息(Normalized mutual information，NMI) 的概念， 标准化互信息有几个不同的版本，大体思想都是相同的，都是用熵做分母将MI值调整到0与1之间，一个比较常见的实现如下所示：
N M I ( X , Y ) = M I ( X , Y ) ( H ( X ) + H ( Y ) ) / 2 N M I(X, Y)=\frac{M I(X, Y)}{(H(X)+H(Y))/2} NMI(X,Y)=(H(X)+H(Y))/2MI(X,Y)
上式分母 ( H ( X ) + H ( Y ) ) / 2 (H(X)+H(Y))/2 (H(X)+H(Y))/2通过标准化解决了这个问题。为何分母要选择这种特殊的形式，原因是 ( H ( X ) + H ( Y ) ) / 2 (H(X)+H(Y))/2 (H(X)+H(Y))/2是 M I ( X , Y ) M I(X, Y) MI(X,Y)的一个紧上界。同时这可以确保NMI的值始终介于0与1之间。
N M I ( X , Y ) = 2 M I ( X , Y ) H ( X ) + H ( Y ) N M I(X, Y)=\frac{2 M I(X, Y)}{H(X)+H(Y)} NMI(X,Y)=H(X)+H(Y)2MI(X,Y)
对上面的背景示例计算各自的熵如下：
H ( X ) = P ( 1 ) log 2 ( P ( 1 ) ) + P ( 2 ) log 2 ( P ( 2 ) ) + P ( 3 ) log 2 ( P ( 3 ) ) H ( Y ) = P ′ ( 1 ) log 2 ( P ′ ( 1 ) ) + P ′ ( 2 ) log 2 ( P ′ ( 2 ) ) + P ′ ( 3 ) log 2 ( P ′ ( 3 ) ) \begin{aligned} &H(X)=P(1) \log _{2}(P(1))+P(2) \log _{2}(P(2))+P(3) \log _{2}(P(3)) \\ &H(Y)=P^{\prime}(1) \log _{2}\left(P^{\prime}(1)\right)+P^{\prime}(2) \log _{2}\left(P^{\prime}(2)\right)+P^{\prime}(3) \log _{2}\left(P^{\prime}(3)\right) \end{aligned} H(X)=P(1)log2(P(1))+P(2)log2(P(2))+P(3)log2(P(3))H(Y)=P′(1)log2(P′(1))+P′(2)log2(P′(2))+P′(3)log2(P′(3))
PS: 这里为了区分2个变量的概率分布分别用 P P P 和 P ′ P^{\prime} P′ 来表示。
综上，即可计算NMI的值。
MI 和 NMI的计算实现 Python 版
import math
import numpy as np
from sklearn import metrics
def NMI(A, B):
# 样本点数
total = len(A)
A_ids = set(A)
B_ids = set(B)
# 互信息计算
MI = 0
eps = 1.4e-45
for idA in A_ids:
for idB in B_ids:
idAOccur = np.where(A == idA) # 输出满足条件的元素的下标
idBOccur = np.where(B == idB)
idABOccur = np.intersect1d(idAOccur, idBOccur) # Find the intersection of two arrays.
px = 1.0 * len(idAOccur[0]) / total
py = 1.0 * len(idBOccur[0]) / total
pxy = 1.0 * len(idABOccur) / total
MI = MI + pxy * math.log(pxy / (px * py) + eps, 2)
print("MI=", MI)
# 标准化互信息
Hx = 0
for idA in A_ids:
idAOccurCount = 1.0 * len(np.where(A == idA)[0])
Hx = Hx - (idAOccurCount / total) * math.log(idAOccurCount / total + eps, 2)
Hy = 0
for idB in B_ids:
idBOccurCount = 1.0 * len(np.where(B == idB)[0])
Hy = Hy - (idBOccurCount / total) * math.log(idBOccurCount / total + eps, 2)
NMI = 2.0 * MI / (Hx + Hy) # 标准化互信息
print("NMI=", NMI)
# return NMI
if __name__ == '__main__':
A = np.array([1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3])
B = np.array([1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 3, 3, 3])
NMI(A, B)
print("metrics.normalized_mutual_info_score=", metrics.normalized_mutual_info_score(A, B))
运行结果如下：
MI= 0.565445018842856 NMI= 0.3645617718571898 metrics.normalized_mutual_info_score= 0.36456177185718985
调整互信息(AMI)
上述的NMI对于随机的分类结果，并不会给出一个近似0的得分，为此提出 调整互信息(Adjusted mutual information，AMI)。AMI对于随机的聚类结果会给出接近于0的得分。
A M I = M I − E [ M I ] mean ( H ( Y ) , H ( X ) ) − E [ M I ] \mathrm{AMI}=\frac{\mathrm{MI}-E[\mathrm{MI}]}{\operatorname{mean}(H(Y), H(X))-E[\mathrm{MI}]} AMI=mean(H(Y),H(X))−E[MI]MI−E[MI]
互信息(MI)和标准互信息(NMI)的值都会受到聚类的类别数K的影响，而AMI则不会受到干扰，取值范围为-1到1，数值越大，两种聚类结果越接近。更多关于定义的细节可以参考scikit中AMI的计算
示例代码
>>> from sklearn.metrics.cluster import adjusted_mutual_info_score >>> adjusted_mutual_info_score([0, 0, 1, 1], [0, 0, 1, 1]) ... 1.0 >>> adjusted_mutual_info_score([0, 0, 1, 1], [1, 1, 0, 0]) ... 1.0 >>> adjusted_mutual_info_score([0, 0, 0, 0], [0, 1, 2, 3]) ... 0.0
兰德系数(Rand Index)
理想情况下，当且仅当两个文本相似时，将这两者分在同一个簇里。真实的划分存在以下4种情况：
Positive:
- TP： 将两篇相似文本归入一个簇 (同 – 同)
- TN： 将两篇不相似的文本归入不同的簇 (不同 – 不同)
Negative:
- FP： 将两篇不相似的文本归入同一簇 (不同 – 同)
- FN： 将两篇相似的文本归入不同簇 (同- 不同)
小结下：
- 真阳性（TP）：将两个相似的文本分配在同一个簇中
- 真阴性（TN）：将两个不相似的文本分配在不同的簇中
- 假阳性（FP）：将两个不相似的文本分配在同一个簇中
- 假阴性（FN）：将两个相似的文本分配在不同的簇中
兰德系数（Rand Index，RI）衡量在这些决策中，正确决策的百分比，即准确度（accuracy）。RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。RI的定义如下：
R I = (number of agreeing pairs) / (number of pairs) R I = T P + T N T P + F P + T F + F N = T P + T N C N 2 RI = \text{(number of agreeing pairs)} / \text{(number of pairs)} \\ R I=\frac{T P+T N}{T P+F P+T F+F N}=\frac{T P+T N}{C_{N}^{2}} RI=(number of agreeing pairs)/(number of pairs)RI=TP+FP+TF+FNTP+TN=CN2TP+TN
示例代码
>>> from sklearn.metrics.cluster import rand_score >>> rand_score([0, 0, 1, 1], [1, 1, 0, 0]) 1.0 >>> rand_score([0, 0, 1, 2], [0, 0, 1, 1]) 0.83...
调整兰德系数(Adjusted Rand index)
对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：
ARI = (RI - Expected_RI) / (max(RI) - Expected_RI)
ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。
示例代码
from sklearn.metrics.cluster import adjusted_rand_score print(adjusted_rand_score([0, 0, 1, 1], [0, 0, 1, 1])) # 1.0 print(adjusted_rand_score([0, 0, 1, 1], [1, 1, 0, 0])) # 1.0 print(adjusted_rand_score([0, 0, 1, 2], [0, 0, 1, 1])) # 0.57 print(adjusted_rand_score([0, 0, 0, 0], [0, 1, 2, 3])) # 0, 当聚类结果各自独立
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
