Question

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

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

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

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

1.1 外部指标

1. 对于数据集 $ MathJax-Element-104 $ ，假定通过聚类给出的簇划分为 $ MathJax-Element-473 $ 。参考模型给出的簇划分为 $ MathJax-Element-46 $ ，其中 $ MathJax-Element-554 $ 和 $ MathJax-Element-48 $ 不一定相等 。

   令 $ MathJax-Element-49 $ 分别表示 $ MathJax-Element-102 $ 的簇标记向量。定义：

   $ a=|SS|,SS=\{(\mathbf {\vec x}_i,\mathbf {\vec x}_j) \mid \lambda_i=\lambda_j,\lambda_i^{*}=\lambda_j^{*}, i \lt j\} \\ b=|SD|,SD=\{(\mathbf {\vec x}_i,\mathbf {\vec x}_j) \mid \lambda_i = \lambda_j,\lambda_i^{*} \ne \lambda_j^{*}, i \lt j\} \\ c=|DS|,DS=\{(\mathbf {\vec x}_i,\mathbf {\vec x}_j) \mid \lambda_i \ne \lambda_j,\lambda_i^{*}=\lambda_j^{*}, i \lt j\} \\ d=|DD|,DD=\{(\mathbf {\vec x}_i,\mathbf {\vec x}_j) \mid \lambda_i\ne\lambda_j,\lambda_i^{*}\ne\lambda_j^{*}, i \lt j\} $

   其中 $ MathJax-Element-51 $ 表示集合的元素的个数。各集合的意义为：

   • $ MathJax-Element-52 $ ：包含了同时隶属于 $ MathJax-Element-102 $ 的样本对。
   • $ MathJax-Element-54 $ ：包含了隶属于 $ MathJax-Element-99 $ ，但是不隶属于 $ MathJax-Element-100 $ 的样本对。
   • $ MathJax-Element-57 $ ：包含了不隶属于 $ MathJax-Element-99 $ ， 但是隶属于 $ MathJax-Element-100 $ 的样本对。
   • $ MathJax-Element-60 $ ：包含了既不隶属于 $ MathJax-Element-99 $ ， 又不隶属于 $ MathJax-Element-100 $ 的样本对。

   由于每个样本对 $ MathJax-Element-63 $ 仅能出现在一个集合中，因此有 $ MathJax-Element-64 $ 。

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

1.1.1 Jaccard系数

1. Jaccard系数Jaccard Coefficient:JC：

   $ JC=\frac {a}{a+b+c} $

   它刻画了：所有的同类的样本对（要么在 $ MathJax-Element-99 $ 中属于同类，要么在 $ MathJax-Element-100 $ 中属于同类）中，同时隶属于 $ MathJax-Element-102 $ 的样本对的比例。

1.1.2 FM指数

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

   $ FMI=\sqrt{\frac {a}{a+b}\cdot \frac{a}{a+c}} $

   它刻画的是：

   • 在 $ MathJax-Element-99 $ 中同类的样本对中，同时隶属于 $ MathJax-Element-100 $ 的样本对的比例为 $ MathJax-Element-70 $ 。
   • 在 $ MathJax-Element-100 $ 中同类的样本对中，同时隶属于 $ MathJax-Element-99 $ 的样本对的比例为 $ MathJax-Element-73 $ 。
   • FMI就是 $ MathJax-Element-74 $ 和 $ MathJax-Element-75 $ 的几何平均。

1.1.3 Rand指数

1. Rand指数Rand Index:RI：

   $ RI=\frac{a+d}{N(N-1)/2} $

   它刻画的是：

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

1.1.4 ARI指数

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

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

2. 定义一致性矩阵为：

   $ \begin{array} {c|crc} & \mathbb C_1^{*} & \mathbb C_2^{*}&\cdots&\mathbb C_{K^\prime}^{*}&\text{sums} \\ \mathbb C_1 & \hline n_{1,1} & n_{1,2} &\cdots & n_{1,K^\prime}& s_1 \\ \mathbb C_2& n_{2,1} & n_{2,2} &\cdots & n_{2,K^\prime}& s_2\\ \vdots &\vdots & \vdots & \ddots&\vdots&\vdots\\ \mathbb C_K& n_{K,1} & n_{K,2} &\cdots & n_{K,K^\prime}& s_K\\ \text{sums} & t_1& t_2 & \cdots&t_K&N \end{array} $

   其中：

   • $ MathJax-Element-79 $ 为属于簇 $ MathJax-Element-84 $ 的样本的数量， $ MathJax-Element-81 $ 为属于簇 $ MathJax-Element-85 $ 的样本的数量。
   • $ MathJax-Element-83 $ 为同时属于簇 $ MathJax-Element-84 $ 和簇 $ MathJax-Element-85 $ 的样本的数量。

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

3. 定义ARI指数Adjusted Rand Index:

   $ ARI=\frac{\sum_i\sum_jC^2_{n_{i,j}}-\left[\sum_iC^2_{s_i}\times \sum_jC^2_{t_j}\right]/C_N^2}{\frac 12\left[\sum_iC^2_{s_i}+\sum_jC^2_{t_j}\right]-\left[\sum_iC^2_{s_i}\times \sum_jC^2_{t_j}\right]/C_N^2} $

   其中：

   • $ MathJax-Element-88 $ ：表示同时隶属于 $ MathJax-Element-102 $ 的样本对。

   • $ MathJax-Element-90 $ ：表示最大的样本对。

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

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

     • 随机挑选一对样本，一共有 $ MathJax-Element-94 $ 种情形。
     • 这对样本隶属于 $ MathJax-Element-99 $ 中的同一个簇，一共有 $ MathJax-Element-96 $ 种可能。
     • 这对样本隶属于 $ MathJax-Element-100 $ 中的同一个簇，一共有 $ MathJax-Element-98 $ 种可能。
     • 这对样本隶属于 $ MathJax-Element-99 $ 中的同一个簇、且属于 $ MathJax-Element-100 $ 中的同一个簇，一共有 $ MathJax-Element-101 $ 种可能。
     • 则在随机划分的情况下，同时隶属于 $ MathJax-Element-102 $ 的样本对的期望（平均样本对）为： $ MathJax-Element-103 $ 。

1.2 内部指标

1. 对于数据集 $ MathJax-Element-104 $ ，假定通过聚类给出的簇划分为 $ MathJax-Element-473 $ 。

   定义：

   $ \text{avg}(\mathbb C_k)=\frac{2}{|\mathbb C_k|(|\mathbb C_k|-1)}\sum_{\mathbf {\vec x}_i,\mathbf {\vec x}_j \in \mathbb C_k,i\ne j}\text{distance}(\mathbf {\vec x}_i,\mathbf {\vec x}_j),\quad k=1,2,\cdots,K\\ \text{diam}(\mathbb C_k)=\max_{\mathbf {\vec x}_i,\mathbf {\vec x}_j \in \mathbb C_k,i\ne j}\text{distance}(\mathbf {\vec x}_i,\mathbf {\vec x}_j),\quad k=1,2,\cdots,K\\ d_{min}(\mathbb C_k,\mathbb C_l)=\min_{\mathbf {\vec x}_i \in \mathbb C_k,\mathbf {\vec x}_j \in \mathbb C_l}\text{distance}(\mathbf {\vec x}_i,\mathbf {\vec x}_j),\quad k,l=1,2,\cdots,K;k\ne l\\ d_{cen}(\mathbb C_k,\mathbb C_l)=\text{distance}( \vec \mu _k, \vec \mu _l),\quad k,l=1,2,\cdots,K;k\ne l \ $

   其中： $ MathJax-Element-106 $ 表示两点 $ MathJax-Element-107 $ 之间的距离； $ MathJax-Element-108 $ 表示簇 $ MathJax-Element-330 $ 的中心点， $ MathJax-Element-110 $ 表示簇 $ MathJax-Element-111 $ 的中心点， $ MathJax-Element-112 $ 表示簇 $ MathJax-Element-121 $ 的中心点之间的距离。

   上述定义的意义为：

   • $ MathJax-Element-114 $ ： 簇 $ MathJax-Element-330 $ 中每对样本之间的平均距离。
   • $ MathJax-Element-116 $ ：簇 $ MathJax-Element-330 $ 中距离最远的两个点的距离。
   • $ MathJax-Element-118 $ ：簇 $ MathJax-Element-121 $ 之间最近的距离。
   • $ MathJax-Element-120 $ ：簇 $ MathJax-Element-121 $ 中心点之间的距离。

1.2.1 DB指数

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

   $ DBI=\frac 1K \sum_{k=1}^{K}\max_{k\ne l}\left(\frac{\text{avg}(\mathbb C_k)+\text{avg}(\mathbb C_l)}{d_{cen}(\mathbb C_k,\mathbb C_l)}\right) $

   其物理意义为：

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

     该度量越小越好。

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

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

2. 显然 $ MathJax-Element-125 $ 越小越好。

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

1.2.2 Dunn指数

1. Dunn指数Dunn Index:DI：

   $ DI= \frac{\min_{k\ne l} d_{min}(\mathbb C_k,\mathbb C_l)}{\max_{i}\text{diam}(\mathbb C_i)} $

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

2. 显然 $ MathJax-Element-128 $ 越大越好。

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

1.3 距离度量

1. 距离函数 $ MathJax-Element-129 $ 常用的有以下距离：

   • 闵可夫斯基距离Minkowski distance：

     给定样本 $ MathJax-Element-130 $ ，则闵可夫斯基距离定义为：

     $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=\left(\sum_{d=1}^{n}|x_{i,d}-x_{j,d}|^{p}\right)^{1/p} $

     • 当 $ MathJax-Element-131 $ 时，闵可夫斯基距离就是欧式距离Euclidean distance：

       $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=||\mathbf {\vec x}_i-\mathbf {\vec x}_j||_{2}=\sqrt {\sum_{d=1}^{n}|x_{i,d}-x_{j,d}|^{2}} $

     • 当 $ MathJax-Element-132 $ 时，闵可夫斯基距离就是曼哈顿距离Manhattan distance：

       $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=||\mathbf {\vec x}_i-\mathbf {\vec x}_j||_{1}= \sum_{d=1}^{n}|x_{i,d}-x_{j,d}| $

   • VDM距离Value Difference Metric：

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

     $ VDM_p(a,b)=\left(\sum_{k=1}^{K}\left|\frac {m_{d,a,k}}{m_{d,a}}-\frac {m_{d,b,k}}{m_{d,b}}\right|^{p}\right)^{1/p} $

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

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

   假设属性 $ MathJax-Element-140 $ 为数值属性， 属性 $ MathJax-Element-141 $ 为非数值属性。则：

   $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=\left (\sum_{d=1}^{n_c}|x_{i,d}-x_{j,d}|^{p}+\sum_{d=n_c+1}^{n}VDM_p(x_{i,d},x_{j,d})^p\right)^{1/p} $

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

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

   $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=\left(\sum_{d=1}^{n}w_d\times|x_{i,d}-x_{j,d}|^{p}\right)^{1/p}\\ w_d \ge 0,d=1,2,\cdots,n;\quad \sum_{d=1}^{n}w_d=1 $

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

5. 这里的距离度量满足三角不等式： $ MathJax-Element-142 $ 。

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