人智导（十六）：聚类效果评价

总述

• 聚类质量的评价是一个困难的问题
• 没有正确结果的反馈（无监督过程）
• 常用的方法：
  • 使用者的观察
    • 了解数据的分布
    • 对于文档的聚类，可以通过阅读同一簇中的文档内容判断分组是否正确
  • 分类的方法

基于数据外在信息的评价方法

• 使用已标记类的数据（如同分类问题）验证算法质量
• 假设：每一个类是一个簇(cluster)
• 算法得到聚类结果后，测算其质量，通过熵(entropy)，纯度(purity)，查准率(precision)，查全率(recall)，F值等等
  • 已知数据集D有k个类$C=(c_1, c_2, \dots ,c_k)$C=(c1​,c2​,…,ck​)，聚类算法生成了k个簇，即划分D为k个不交叠的子集$D_1,D_2,\dots ,D_k$D1​,D2​,…,Dk​

聚类质量度量：熵(Entropy)

熵：对于每个簇(cluster)，度量其熵值为
$entropy(D_i)=-\Sigma^k_{j-1}Pr_i(c_j)log_2Pr_i(c_j)$entropy(Di​)=−Σj−1k​Pri​(cj​)log2​Pri​(cj​)
其中$Pr_i(c_j)$Pri​(cj​)是$c_j$cj​类的数据点在簇$D_i$Di​中的占比
度量聚类效果的总体熵值（计算所有簇的熵）：
$entropy_{total}(D)=\Sigma^k_{i-1}\frac{|D_i|}{D}\times entropy(D_i)$entropytotal​(D)=Σi−1k​D∣Di​∣​×entropy(Di​)

聚类质量度量：纯度(Purity)

纯度：度量一个簇包含一个类中的数据的程度。计算每个簇的纯度值为
$purity(D_i)=max_j(Pr_i(c_j))$purity(Di​)=maxj​(Pri​(cj​))
度量聚类效果的总体纯度值（计算所有簇的纯度）：
$purity_{total}(D)=\Sigma^k_{i=1}\frac{|D_i|}{D}\times purity(D_i)$puritytotal​(D)=Σi=1k​D∣Di​∣​×purity(Di​)

示例

文档数据集D包含了900个文档数据，分为三类：科学(Science)，体育(Sports)，政治(Politics)；每个类300份文档。
每份文档标记为其中一个类，应用算法聚类时不使用类标记，聚类效果如下：

Cluster	Science	Sports	Politics	Entropy	Purity
1	250	20	10	0.589	0.893
2	20	180	80	1.198	0.643
3	30	100	210	1.257	0.617
Total	300	300	300	1.031	0.711

基于数据内在信息的评价方法

• 类内的凝聚度：簇的误差平方和SSE尽可能小 $SSE = \Sigma_i\Sigma_{x\in C_i}(x-m_i)^2$SSE=Σi​Σx∈Ci​​(x−mi​)2
• 聚类间分离度：簇与簇间的差异尽可能的大 $BSS=\Sigma_i|C_i|(m-m_i)^2$BSS=Σi​∣Ci​∣(m−mi​)2 其中$|C_i|$∣Ci​∣是第$i$i个簇的数据点的数目

示意图：

• 凝聚度：
• 分离度：

间接评价的方法

• 在许多应用中，聚类并不是基本任务，而使用其帮助完成其他任务
• 可以通过基本任务执行的结果来比较聚类方法的效果
• 例如亚马逊图书推荐，主要任务是在线推荐给用户感兴趣的图书进行推销