聚类中的性能度量

聚类

在无监督学习中，训练样本的标记是没有指定的，通过对无标记样本的训练来探索数据之间的规律。其中应用最广的便是聚类，聚类试图把一群未标记数据划分为一堆不相交的子集，每个子集叫做”簇“，每个簇可能对应于一个类别标签，但值得注意的是，这个标签仅仅是我们人为指定强加的，并不是数据本身就存在这样的标签。例如音乐软件对音乐的曲分或者流派进行聚类，可以划分为伤感，轻快等一系列标签，但是这个曲分只是人为加上的，音乐本身并不知道自己被分为了什么曲分。

那聚类该如何做性能度量呢？在机器学习中我们都需要对任务进行评价以便于进行下一步的优化。分类和回归都有自己的评估准则，包括准确率，精确度，召回率等，聚类中的性能度量也同样有这样的指标来评价聚类的性能。

考虑聚类的任务的目的，容易想到就是”物以类聚“，即达到”簇内相似度高“，”簇间相似度低“的性能效果。具体的性能度量有两类，一类是外部指标，与某个专家给定的参考模型进行比对，另一类是内部指标，只考虑自己聚类之后的结果。

外部指标

外部指标需要一个参考模型，这个参考模型通常是由专家给定的，或者是公认的参考模型比如公开数据集。对于聚类的结果所形成的簇集合（这里叫做簇C），对于参考模型的簇集合（这里叫做D），对这两个模型结果的样本进行两两配对比较，可得到如下显而易见的数据。

a = 在C中属于相同簇且在D中属于相同簇的样本对的数量。
b = 在C中属于相同簇且在D中属于不同簇的样本对的数量。
c = 在C中属于不同簇且在D中属于相同簇的样本对的数量。
d = 在C中属于不同簇且在D中属于不同簇的样本对的数量。

对这里的abcd，不考虑一个样本属于多个簇的情况，因此每个样本都只能出现在一个集合中，所以a+b+c+d=m(m-1)/2。（m为样本总数)

由此可以导出几个常见的外部性能指标，Jaccard系数，FM指数，Rand指数。

Jaccard指数（简称JC）常用来表示集合之间的相似性和差异性，常常被定义为集合交集大小与集合并集大小的比值，因此也常被叫做并交比。其公式为

Jaccard index

FM指数（简称FMI）

FMI

Rand指数（Rand Index，简称RI）

RI和Jaccard系数十分相似，只是所比较的范围不同而已。这里每个指标的值均在0-1之间，显然值越大说明聚类效果越好。

内部指标

内部指标则只考虑聚类之后这些簇之间的效果，通常用距离来度量。

avg(C):簇C样本间的平均距离
diam(C):簇C样本间的最远距离
dmin(ci,cj):簇间最近样本间的距离
dcen(ci,jc)：簇间中心点之间的距离

使用这些簇间的距离指标也可以导出几个常见的性能度量内部指标，DB指数，Dunn指数。

DB指数（简称DBI）

DBI

Dunn指数（简称DI）

Dunn指数

显然，DBI的值越小越好，而DI的值越大越好。

距离度量

计算簇之间的相似性和差异性时常常要使用距离来进行度量，内部指标也都是以距离度量为基础的。

距离常常分为度量距离和非度量距离，其中度量距离满足非负性，对称性，直递性（三角不等式），而非度量距离往往不满足直递性。举个例子，人马和人很像，人马也和马和像，但是人和马的差距非常大，即不满足三角不等式，所以这个距离为非距离度量。

而对于属性可以分为连续属性和离散属性，但这个分类法对距离度量没有多大意义。在考虑距离的时候，属性更多的是考虑有序性，例如高，中，矮是有序的，即高>中>矮。但是金鱼，鲤鱼，草鱼这些便是没有顺序的，无法对这些鱼的品种来比较顺序。

对于有序属性，我们最常使用的是闵科夫斯基距离

闵科夫斯基距离

而当p取不同值的时候，便可得到实际使用的距离度量。
当p=1时，为曼哈顿距离

曼哈顿距离

当p=2时，为欧式距离

欧式距离

当p=无穷大时，为切比雪夫距离

切比雪夫距离

对于无序属性，使用VDM(Value Difference Metric)来表示，令 $m_{u,a}$ 表示在属性u上取值为a的样本数， $m_{u,a,i}$ 表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a,b的VDN距离为：
$VDM_{p}=\sum_{i=1}^{k}\left | \frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}} \right |$