一、性能度量

1. 聚类的性能度量也称作聚类的有效性指标validity index 。

2. 直观上看，希望同一簇的样本尽可能彼此相似，不同簇的样本之间尽可能不同。即：簇内相似度intra-cluster similarity高，且簇间相似度inter-cluster similarity低。

3. 聚类的性能度量分两类：

   • 聚类结果与某个参考模型reference model进行比较，称作外部指标external index 。
   • 直接考察聚类结果而不利用任何参考模型，称作内部指标internal index 。

1.1 外部指标

1. 对于数据集 ，假定通过聚类给出的簇划分为 。参考模型给出的簇划分为 ，其中 和 不一定相等 。

   令 分别表示 的簇标记向量。定义：

   

   其中 表示集合的元素的个数。各集合的意义为：

   • ：包含了同时隶属于 的样本对。
   • ：包含了隶属于 ，但是不隶属于 的样本对。
   • ：包含了不隶属于 ， 但是隶属于 的样本对。
   • ：包含了既不隶属于 ， 又不隶属于 的样本对。

   由于每个样本对 仅能出现在一个集合中，因此有 。

2. 下述性能度量的结果都在 [0,1]之间。这些值越大，说明聚类的性能越好。

1.1.1 Jaccard系数

1. Jaccard系数Jaccard Coefficient:JC：

   

   它刻画了：所有的同类的样本对（要么在 中属于同类，要么在 中属于同类）中，同时隶属于 的样本对的比例。

1.1.2 FM指数

1. FM指数Fowlkes and Mallows Index:FMI：

   

   它刻画的是：

   • 在 中同类的样本对中，同时隶属于 的样本对的比例为 。
   • 在 中同类的样本对中，同时隶属于 的样本对的比例为 。
   • FMI就是 和 的几何平均。

1.1.3 Rand指数

1. Rand指数Rand Index:RI：

   

   它刻画的是：

   • 同时隶属于 的同类样本对（这种样本对属于同一个簇的概率最大）与既不隶属于 、 又不隶属于 的非同类样本对（这种样本对不是同一个簇的概率最大）之和，占所有样本对的比例。
   • 这个比例其实就是聚类的可靠程度的度量。

1.1.4 ARI指数

1. 使用RI有个问题：对于随机聚类，RI指数不保证接近0（可能还很大）。

   ARI指数就通过利用随机聚类来解决这个问题。

2. 定义一致性矩阵为：

   

   其中：

   • 为属于簇 的样本的数量， 为属于簇 的样本的数量。
   • 为同时属于簇 和簇 的样本的数量。

   则根据定义有： ，其中 表示组合数。数字2 是因为需要提取两个样本组成样本对。

3. 定义ARI指数Adjusted Rand Index:

   

   其中：

   • ：表示同时隶属于 的样本对。

   • ：表示最大的样本对。

     即：无论如何聚类，同时隶属于 的样本对不会超过该数值。

   • ：表示在随机划分的情况下，同时隶属于 的样本对的期望。

     • 随机挑选一对样本，一共有 种情形。
     • 这对样本隶属于 中的同一个簇，一共有 种可能。
     • 这对样本隶属于 中的同一个簇，一共有 种可能。
     • 这对样本隶属于 中的同一个簇、且属于 中的同一个簇，一共有 种可能。
     • 则在随机划分的情况下，同时隶属于 的样本对的期望（平均样本对）为： 。

1.2 内部指标

1. 对于数据集 ，假定通过聚类给出的簇划分为 。

   定义：

   

   其中： 表示两点 之间的距离； 表示簇 的中心点， 表示簇 的中心点， 表示簇 的中心点之间的距离。

   上述定义的意义为：

   • ： 簇 中每对样本之间的平均距离。
   • ：簇 中距离最远的两个点的距离。
   • ：簇 之间最近的距离。
   • ：簇 中心点之间的距离。

1.2.1 DB指数

1. DB指数Davies-Bouldin Index:DBI：

   

   其物理意义为：

   • 给定两个簇，每个簇样本距离均值之和比上两个簇的中心点之间的距离作为度量。

     该度量越小越好。

   • 给定一个簇 ，遍历其它的簇，寻找该度量的最大值。

   • 对所有的簇，取其最大度量的均值。

2. 显然 越小越好。

   • 如果每个簇样本距离均值越小（即簇内样本距离都很近），则 越小。
   • 如果簇间中心点的距离越大（即簇间样本距离相互都很远），则 越小。

1.2.2 Dunn指数

1. Dunn指数Dunn Index:DI：

   

   其物理意义为：任意两个簇之间最近的距离的最小值，除以任意一个簇内距离最远的两个点的距离的最大值。

2. 显然 越大越好。

   • 如果任意两个簇之间最近的距离的最小值越大（即簇间样本距离相互都很远），则 越大。
   • 如果任意一个簇内距离最远的两个点的距离的最大值越小（即簇内样本距离都很近），则 越大。

1.3 距离度量

1. 距离函数 常用的有以下距离：

   • 闵可夫斯基距离Minkowski distance：

     给定样本 ，则闵可夫斯基距离定义为：

     

     • 当 时，闵可夫斯基距离就是欧式距离Euclidean distance：

       

     • 当 时，闵可夫斯基距离就是曼哈顿距离Manhattan distance：

       

   • VDM距离Value Difference Metric：

     考虑非数值类属性（如属性取值为：中国，印度，美国，英国），令 表示 的样本数； 表示 且位于簇 中的样本的数量。则在属性 上的两个取值 之间的 VDM距离为：

     

     该距离刻画的是：属性取值在各簇上的频率分布之间的差异。

2. 当样本的属性为数值属性与非数值属性混合时，可以将闵可夫斯基距离与 VDM 距离混合使用。

   假设属性 为数值属性， 属性 为非数值属性。则：

   

3. 当样本空间中不同属性的重要性不同时，可以采用加权距离。

   以加权闵可夫斯基距离为例：

   

4. 这里的距离函数都是事先定义好的。在有些实际任务中，有必要基于数据样本来确定合适的距离函数。这可以通过距离度量学习distance metric learning来实现。

5. 这里的距离度量满足三角不等式： 。

   在某些任务中，根据数据的特点可能需要放松这一性质。如：美人鱼和人距离很近，美人鱼和鱼距离很近，但是人和鱼的距离很远。这样的距离称作非度量距离non-metric distance。