聚类

Clustering

性能度量

Target：聚类结果的“簇内相似度”（Intra-Cluster Similarity）高且“簇间相似度”（Inter-Cluster Similarity）低

• 外部指标（External Index）

  将聚类结果与某个“参考模型”（Reference Model）比较

  $$\begin{array}{ll}a=|SS|,& SS=\left\{\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\mid {\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\right)\}\\ b=|SD|,& SD=\left\{\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\mid {\lambda }_i={\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\right)\}\\ c=|DS|,& DS=\left\{\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\mid {\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }={\lambda }_j^{\ast },i<j\right)\}\\ d=|DD|,& DD=\left\{\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\mid {\lambda }_i\ne {\lambda }_j,{\lambda }_i^{\ast }\ne {\lambda }_j^{\ast },i<j\right)\}\end{array}$$
  $\ast$表示参考模型，下述外部指标值越大越好

  • Jaccard系数

    Jaccard Coefficient，JC

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

  • FM指数

    Fowlkes and Mallows Index，FMI

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

  • Rand指数

    Rand Index，RI

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

• 内部指标（Internal Index）

  直接考察聚类结果而不利用任何参考模型

  $$\begin{array}{rl}& \mathrm{avg}(C)=\frac{2}{|C|(|C|-1)}\sum _{1⩽i<j⩽|C|}\mathrm{dist}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\\ & \mathrm{diam}(C)=\underset{1⩽i<j⩽|C|}{\max }\mathrm{dist}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\\ & d_{\min }\left(C_i,C_j\right)=\underset{{\mathbf{x}}_i\in C_i,{\mathbf{x}}_j\in C_j}{\min }\mathrm{dist}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\\ & d_{\mathrm{cen}}\left(C_i,C_j\right)=\mathrm{dist}\left({\mathbf{\mu }}_i,{\mathbf{\mu }}_j\right)\end{array}$$
  $avg(C)$表示簇C内样本间的平均距离，$diam(C)$表示簇C内样本间的最远距离，$d_{min}(C_i,C_j)$两簇最近样本间的距离，$d_{cen}(C_i,C_j)$两簇中心点的距离

  • DB指数

    Davies-Bouldin Index，DBI

    $$\mathrm{DBI}=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }\left(\frac{\mathrm{avg}\left(C_i\right)+\mathrm{avg}\left(C_j\right)}{d_{\mathrm{cen}}\left({\mathbf{\mu }}_i,{\mathbf{\mu }}_j\right)}\right)$$
    越小越好

  • Dunn指数

    Dunn Index，DI

    $$\mathrm{DI}=\underset{1⩽i⩽k}{\min }\left\{\underset{j\ne i}{\min }\left(\frac{d_{\min }\left(C_i,C_j\right)}{{\max }_{1⩽l⩽k}\mathrm{diam}\left(C_l\right)}\right)\right\}$$
    越大越好

距离计算

dist(·,·)

非负性、同一性、对称性、直递性

• 闵可夫斯基距离

  Minkowski Distance

  适用于有序属性（Ordinal Attribute）

  $$dis{t}_{mk}\left(x_i,x_j\right)={\left(\sum _{u=1}^n{\left|x_{iu}-x_{ju}\right|}^p\right)}^{\frac{1}{2}},p\ge 1$$
  即$L_P$范数

• VDM

  Value Difference Metric

  适用于无序属性（Non-ordinal Attribute）

  $$VD{M}_p(a,b)=\sum _{i=1}^k\mid \frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{{m_{u,b}|}^p}$$
  $m_{u,a}$表示在属性u上取值为a的样本数，$m_{u,a,i}$表示在第i个样本簇中在属性u上取值为a的样本数，$k$为样本簇数

• 可将上述两种距离度量结合起来处理混合属性，假定有$n_c$个有序属性，$n-n_c$个无序属性，则

  $$\mathrm{Minkov}D{M}_p\left(x_i,x_j\right)={\left(\sum _{u=1}^{n_c}{\left|x_{iu}-x_{ju}\right|}^p+\sum _{u=n_c+1}^{n}VD{M}_p\left(x_{iu},x_{ju}\right)\right)}^{\frac{1}{p}}$$

• 当样本空间中不同属性的重要性不同时，可使用“加权距离”，如

  $$dis{t}_{wmk}(x_i,x_j)=(w_1\cdot |x_{i1}-x_{j1}{|}^p+...+w_n\cdot |w_{in}-w_{jn}{|}^p{)}^{\frac{1}{p}}$$
  其中权重$w_i>=0$，表征不同属性的重要性

• 非度量距离

  Non-metric Distance

  • 可通过距离度量学习（Distance Metric Learning）来实现