开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Evaluation of Clustering】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15652
Evaluation of Clustering
内容介绍：
一、聚类评估主要内容
二、聚类质量的评估
三、聚类的结果评估
四、聚类的趋势评估
本课程继续开始学习数据仓库与数据挖掘。主要介绍聚类的评估。在聚类的评估中，主要要介绍三个方面的内容，第一个就是聚类质量的评估，第二个是聚类稳定性的评估，第三个是聚类趋势的评估。
一、聚类评估主要内容
在聚类质量的评估中，主要是评估蔟的质量。在聚类稳定性的评估中，主要是要评估聚类算法，它所得到的聚类结果是否对参数敏感。在聚类趋势的评估中，主要是评估数据集分布，它是否具有内在的组团结构。
二、聚类质量的评估
首先来看一下数据结果的评估。对于聚类结果的评估，主要有两种方式，一种是外部方法，一种是内部方法。
1. 概念
（1）、外部方法
对于外部方法来说，它是一种基于有监督的评估方法，需要使用到一些外部知识，经常使用的是一些数据对象的类标签。通过比较数据对象的蔟标签和数据对象的类标签来判断聚类质量。
（2）、内部的方法
基于，内部的方法主要是根据数据的分布特性，去设计一些评估指标来评估聚类质量。
（3）、 聚类质量
这些聚类质量主要体现在两个方面，一种是蔟类的凝聚性，也就是蔟类的对象是否尽可能的相似，另外一种就是蔟的分离性，就是蔟和蔟之间尽可能的不相似。
2. 外部评价方法
首先来看一下外部评价方法。假设使用的外部评价知识为 T，得到的聚类结果为C，用 Q( C,T) 来代表对聚类结果的评估。
如果聚类结果评估质量比较好，那么它必须要满足以下一些要求，第一个就是蔟的同质性。也就是在蔟中的所有数据对象要求尽可能的序属于同一个类，那么蔟的纯度越高，聚类的质量就越好。第二个要求就是蔟的完整性。所谓蔟的完整性，就是一个类的数据对象尽可能的被分到同一个蔟中去。
第三个要求就是把它称之为叫做碎布袋。所谓的碎布袋就是把一些零散的异质的数据对象放到一个蔟中，这样得到的聚类，结果它的质量会比把这些零碎异质的数据对象每一个对象作为一个蔟得到的聚类结果要好。第四个要求是小蔟的保留性，如果一个聚类方法将一个小类划分成为若干个小蔟，而另外一种聚类方法将一个大类划分为若干个小蹙，那么可以说第一种聚类质量会要比第二种距离质量要差一些。
3. 外部评估方法的度量指标
（1）、纯度
第一个度指标就是纯度。所谓的纯度，就是一个蔟中某一类别的数据所占的比例。对于一个聚类结果 c，它的某一个蔟 c 的程度可以用下图的公式去计算，其中 ni 代表的是这个蔟 Ci 的数据对象的数目。而 nij 指的是在这个蔟中出现频率最高的类别的数据对象的数目。比如图上的这样的一个聚类结果为例，是有三个蔟，那么每一行代表的是一个蔟中数据对象的分布状态。对于第一个蔟 c1 来说，它有50个数据对象，其中20个属于 t2 类，30个属于 t3 类，那么也就是出现频率比较高的类别是t3 类，t3 类的数据，个数是30个，所以它的纯度就是30/50。
那么，计算得到每一个出的程度之后，可以把每一个蔟的纯度加权取平均得到这个聚类结果 c 的纯度，这个是聚类结果 c 的程度的计算方法，经过化简之后，相当于它的程度是可以用 1/n，然后 Σmax{nij} 来计算。比如对于蔟 c1，它的纯度是30/50，那么蔟 c2 它的纯度应该是20，除以25，那么第三这个蔟的纯度应该就是25除以25，那么把它的这三个纯度加权取平均就是30+20+25除以总共的数目100，这个就是使用纯度来评估聚类效果。
（2）、精度
和纯度的计算方法非常类似的就是精度，精度的计算方法和纯度的计算方法是一样的，就不再介绍。
（3）、召回率
除了精度和纯度之外，还可以计算每一个簇的召回率，蔟的召回率的公式在下图中，对于一个结果 c，它的一个蔟，ci 的召回率是等于 ni j 的数目除以 |Tji| ，那么它的含义指的是在这个蔟中出现频率最高类别的数目占它类别的比率，依然是以蔟C1 为例，在蔟 C1 中出现频率最高的是第三类，第三类出现的数目是三十，那么所有的 t3 类的总共的数目是三十五，所以说对于蔟 C1 来说，它的召回率就是三十除以三十五，计算了每一个蔟的召回率之后，可以对所有的蔟取平均，然后得到聚类结果的召回率。
（4）、F-Measure 的计算方法
那么除了有召回率，还有这样的一个 F-Measure 的计算方法，下图计算 F1 score的值公式，关于 F1 score 的计算方法，在讲分类评估的时候介绍过，对于 F1 score 来说它是精度和召回率的一种平衡，对于每一个蔟依然可以计算每一个蔟的精度，和每一个蔟的召回率，然后在此基础上，计算每一个蔟的 F1 score，然后再加每一个蔟的 F1 score 取平均就可以得到了整个聚类结果的 F1 score 方法，那么这些外部评估的指标。
（5）、NMI
除了之前介绍的外部评估指标之外，还有一个外部评估指标是叫做 N MI，那么它是基于互信息的，首先看一下对于一个聚类结果 c 来说，它的互信息指数是怎么算的？那么下图是它的一个计算公式，其中r指的是所有的蔟的数目，而k指的是类别的数目，pij指的是蔟 ci 中的数据对象属于类tj的概率。
那么在计算了这样一个互信息之后，可以对它进行一些规范化，那么就是用 ci 类别的熵和蔟的熵进行规范化之后，就可以得到 NMI这 样的一个指数。
那么对于 NMI 指数来说，它的取值范围是0到1之间，那么当它接近一的时候，就也就是它比较大的时候，就意味着聚类质量是比较好的。
4. 内部评估方法指标
（1）、sse
那么在介绍完。外部评估方法的指标之后，再介绍一下内部评估方法的一些指标，那么，第一个就是 sse，那么 sse 的含义，之前介绍过，它主要是用来评估这个蔟的凝聚性，也就是蔟，如果在一个蔟中数据对象很相似，那么它的 sse 是比较小的，聚类结果是比较好的。
（2）、ssb
那么，除了评估蔟的凝聚性，再进行蔟评估的时候，还要考虑它的一个分离性，所谓出的分离性，就是希望蔟和蔟之间的距离尽可能的大，蔟闲的数据对象尽可能的不相似，一般的使用 ssb 去计算。下图是 ssb 的计算公式，那么其中 ci 就指的是蔟的数目，m 是所有数据对象的均值，而MI是某一个蔟的中心点，那么对于 ssb 来说它越大就说明出的分离性越好。
（3）、sse+ssb
通过分析，会发现对于一个数据集合分布来说，它的 ssb 和 sse 的值相加是一个常量，如下图所示，有四个数据对象，那么假设把它分成一个类别，也就是成一个蔟，那么它的 sse，ssB 的和是10，那当k值取二的时候，再进行计算，会发现它的值依然是十，也就是说，因为 ssb 和 sse 的和是一个常量，那最小化 sse，其实也就意味着最大化 ssb 。
所以说如果一个聚类结果它的 sse 最小，也就意味着它的 ssb 越大，因此在使用 ss e 进行评估的时候，不仅评估了它的凝聚性，其实也评估了它的蔟的分离性。这个是关于 sse 的介绍。
（4）、轮廓指数
再来看一下轮廓指数。之前讲过在评估蔟的证的时候，需要综合的去考虑它的蔟的凝聚性和蔟的分割性，对于轮廓指数来说，它也是顾及了这两点的一个内部指标，要计算轮廓指数，首先要计算两个变量 a 和 b。对于变量 a 来说，它指的是一个数据对象到它同蔟的数据对象的距离的平均值，而对于 b，它指的是一个数据对象i到它非同蔟的某一个蔟中所有数据对象的平均值，计算所有非同蔟的这个平均值之后，从中选一个最小的就是b的值。然后轮廓系数的值，计算方式就是（b-a）÷max（a，b）。
那么对于轮廓系数来说，它的取值范围是-1到1之间的，那么当轮廓系数小于零，它意味着 b 的值比 a 的值大，那么这个距离效果是比较差的。因为 b 代表的是一个数据对象，到它一个非同蔟的数据对象的距离，而 a 指的是它的数据对象到它所在蔟的一个数据对象的距离，所以肯定希望 b 的值是要大于零的值。那么当轮廓系数是位于0和1之间的，就是相当于是一个比较正常的聚类效果，那么当这个聚类的轮廓系数接近一的时候，那么就表明聚类效果是比较好的，这个就是关于 sse 这样的一个指标。
以上就是关于轮廓指数的计算方式。
三、聚类的结果评估
再介绍一下如何通过相关系数来对聚类的结果进行评估，相关系数主要是计算两个矩阵的相关系数，一个矩阵就是数据对象数据对象之间近邻性的矩阵，那么另外一个矩阵的就是理想的相似性矩阵。
1.两矩阵概念
对于近邻性取证来说它的每一个矩阵中的元素代表的是任意两个数据对象的相似度或者是近邻度。而理想的相似度矩阵指的是构造一个矩阵，如果两个数据对象属于同一个蔟，那么这两个数据对象所对应的矩阵元素为一否则为零。
通过计算这两个矩阵的相关性，会发现如果聚类质量比较好的数据对象，它的这个相似度矩阵跟理想的相似度矩阵之间的相关信息比较高的，反之比较低。
2.矩阵相关的
比如下图展示的两种聚类，结果很明显，图左边的聚类结果是要优于这张图右边的聚类结果，通过相关计算，发现左图计算的两个矩阵的相关度是0.9，而右图的相关度只有0.5，所以聚类结果比较好的，这两个矩阵的相关度是比较高的。
3.矩阵可视化
基于以上考虑，可以直接通过数据对象之间的相似度矩阵来可视化聚类结果。可以根据聚类得到的结果，将蔟的数据对象进行排序，将属于同一个蔟的数据对象尽可能的排列在一起。那么对于下图的一个相似度矩阵用每一个方格代表的是两个数据对象之间的相似度相似度越高颜色就是暖色系越深，可以看到对于这样的一个聚类结果，很明显的，在它的对角线上出现了三个聚集性非常强的这样的一个色块，就显示了它的聚类效果是比较好的。
如果这个聚类结果比较差，可以看到对于这样的一个聚类结果，如果用相似度矩阵进行可视化的时候，那么它的这个对角线上面的凝聚性就是比较差的。
所以通过这个分析，可以通过一些相似度矩阵来对聚类结果进行可视化，从而评估聚类结果。
四、聚类的趋势评估
最后，介绍一下聚类的趋势评估。趋势评估主要就是评估数据集集合，它是否具有潜在的内在组团结构，如果一个数据吉它是均匀分布的，那么它是没有这种聚集趋势，是不需要对它进行聚类分析的。但是对于聚类的趋势评估是比较困难的，因为在之前介绍过关于蔟的定义是有多种方式的，所以说如何对于数据集的聚集趋势进行评估，也是很难做。
主要介绍一个常用的方法，就是霍普金斯统计量。那么下图是霍普金斯统计量的计算公式，假设有一个数据集 D，从这个数据集 D 中去抽取 p 的数学对象组成一个数据集 w，那么依然再从这个数据集 D，中抽取几个数据对象组成一个数据集 u，Wi 含义就是集合 W 中，任意一个数据对象到它最近邻的数据对象的距离的和，那么 ui 指的是 Ui 中的任何一个数据对象 i 到集合地点 u，这样的一个集合中，离它最近的一个数据对象之间的距离的和，如果是数据分布是均匀的，那么这个 ΣWI 的值和 ΣUI 的值是尽可能的接近的，所以霍普金斯的分布的值大概是0.5左右，但是如果数据分布式比倾斜的，比如说有一部分数据分布式非常不均衡的，那么有可能这样的一个 UI 的值就会非常大，所以当霍布金斯统计量的值等于零或者是等于一的时候，那么就意味着数据它的分布式高度倾斜的是具有聚类曲是的。
以上就是关于聚类评估的一些知识的介绍。
