度量和距离计算"/>
聚类的性能度量和距离计算
聚类也许是机器学习中"新算法"出现最多,最快的领域,一个重要原因是聚类不存在客观标准;给定数据集 ，总能从某个角度找到以往算法未覆盖的某种标准从而设计出新算法，相对于机器学习其他分支来说，聚类的知识还不够系统化，但是聚类技术本身在现实任务中非常重要。
文章目录
- 一，聚类任务
- 二、性能度量（*）
- 三，距离计算（*）
如果基本了解聚类的概念就可以直接看性能度量和距离计算了，
一，聚类任务
聚类是一类“无监督学习”(unsupervised learning),常见的无监督学习任务还有密度估计（density estimation）,异常检测（anomaly detection）等，无监督学习就是对训练样本的标记信息是未知的，目标是通过对无标记样本的学习来揭示数据的内在性质及规律，为了进一步的数据分析提供基础，此类学习任务中研究最多，应用最广的是“聚类任务”（clustering）。
聚类试图将数据集中的样本划分为若干个通常是互不相交的子集，每个子集叫做一个“簇”（cluster），通过这样的划分，每个簇可能都有一些潜在的概念（类别），比如对于西瓜来说像瓜的颜色，大小，本地瓜或者外地瓜。但是这些东西在聚类操作前我们是不知道的，聚类过程只能自动的形成簇结构，簇所代表的属性还要我们来定义。
形式化的说，假定样本集 D = { x 1 , x 2 . . . , x m } D=\{x_1,x_2...,x_m\} D={x1,x2...,xm}包含 m m m个无标记样本，每个样本 x i = { x i 1 , x i 2 . . . , x i n } x_i=\{x_{i1},x_{i2}...,x_{in}\} xi={xi1,xi2...,xin}是一个 n n n为特征向量，则聚类算法将样本 D D D划分为 k k k个不相交的簇 { C l ∣ l = 1 , 2 , ⋯ , k } \{C_l|l=1,2,\cdots,k\} {Cl∣l=1,2,⋯,k}，其中
C l ′ ⋂ l ′ ≠ l C l = ∅ C_{l'}\bigcap_{l'\neq l}C_l= \emptyset Cl′⋂l′=lCl=∅且 D = ⋃ l = 1 k C l D=\bigcup^k_{l=1}C_l D=⋃l=1kCl.相应的，我们用 λ i ∈ { 1 , 2 , ⋯ , k } \lambda_i\in\{1,2,\cdots,k\} λi∈{1,2,⋯,k} 表示样本 x j x_j xj的“簇标记”（cluster label），即 x j ∈ C λ j x_j\in C_{\lambda j} xj∈Cλj.于是，聚类的结果可用包含 m m m个元素的簇标记向量
λ i = { λ 1 ; λ 2 , ⋯ , λ k } \lambda_i=\{\lambda_1;\lambda_2,\cdots,\lambda_k\} λi={λ1;λ2,⋯,λk}表示。
聚类既能作为一个单独过程，用于寻找数据内在的分布结构，也可以作为分类等其他学习任务的前驱过程。例如，在一些商业中需对新用户的类型进行判别，但定义“用户类型”对商家来说可能不太容易，此时往往可以先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用于判别新用户的类型。
基于不同的学习策略，人们设计出多种类型的聚类算法。我们就先对两个基本问题进行讨论——性能度量和距离计算。
二、性能度量（*）
聚类性能度量亦称聚类“有效性指标”（validity index），与监督学习中的性能度量非常相似，对聚类结果，我们需通过某种性能度量来评估其好坏；另一方面，若明确了最终将要使用的性能度量，则可以直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
聚类是样本集 D D D划分为若干个互不相交的子集，即样本簇。那么，什么样的聚类结果比较好呢？直观上看，我们希望“物以类聚”,即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同，换言之，聚类结果的“簇内相似度”（intra-cluster simliarity）高且“簇间相似度”(inter-cluster simliarity)低。
聚类性能度量大致有两种，一类是将聚类结果于某个“参考模型”（reference mode）进行比较，称为“外部指标”（external index）；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”（internal index）.
对数据集 D = { x 1 , x 2 . . . , x m } D=\{x_1,x_2...,x_m\} D={x1,x2...,xm}，假定通过聚类给出的簇划分为 C = { C 1 , C 2 . . . , C k } C=\{C_1,C_2...,C_k\} C={C1,C2...,Ck},参考模型给出的簇划分为 C ∗ = { C 1 ∗ , C 2 ∗ . . . , C s ∗ } C^*=\{C^*_1,C^*_2...,C^*_s\} C∗={C1∗,C2∗...,Cs∗},相应地，令 λ \lambda λ与 λ ∗ \lambda^* λ∗分别表示 C C C 和 C ∗ C^* C∗对应的簇标记向量，我们将样本两两配对考虑，定义
a = ∣ S S ∣ , S S = { ( x i , x j ) ∣ λ i = λ j , λ i ∗ = λ j ∗ , i < j } , ( 1 ) a=|SS|,SS=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda^*_i=\lambda^*_j,i<j\},(1) a=∣SS∣,SS={(xi,xj)∣λi=λj,λi∗=λj∗,i<j},(1)
b = ∣ S D ∣ , S D = { ( x i , x j ) ∣ λ i = λ j , λ i ∗ ≠ λ j ∗ , i < j } , ( 2 ) b=|SD|,SD=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda^*_i\neq\lambda^*_j,i<j\},(2) b=∣SD∣,SD={(xi,xj)∣λi=λj,λi∗=λj∗,i<j},(2)
c = ∣ D S ∣ , D S = { ( x i , x j ) ∣ λ i ≠ λ j , λ i ∗ = λ j ∗ , i < j } , ( 3 ) c=|DS|,DS=\{(x_i,x_j)|\lambda_i\neq\lambda_j,\lambda^*_i=\lambda^*_j,i<j\},(3) c=∣DS∣,DS={(xi,xj)∣λi=λj,λi∗=λj∗,i<j},(3)
d = ∣ D D ∣ , D D = { ( x i , x j ) ∣ λ i ≠ λ j , λ i ∗ ≠ λ j ∗ , i < j } , ( 4 ) d=|DD|,DD=\{(x_i,x_j)|\lambda_i\neq\lambda_j,\lambda^*_i\neq\lambda^*_j,i<j\},(4) d=∣DD∣,DD={(xi,xj)∣λi=λj,λi∗=λj∗,i<j},(4)
其中集合 S S SS SS 包含了在 C C C 中隶属于相同簇且在 C ∗ C^* C∗ 中也隶属于相同簇的样本对，集合 S D SD SD 包含了在 C C C 中隶属于相同簇但在 C ∗ C^* C∗ 中隶属于不同簇的样本对,…由于每个样本对对 ( x i , x j ) ( i < j ) (x_i,x_j)(i<j) (xi,xj)(i<j)仅能出现在一个集合中，因此有 a + b + c + d = m ( m − 1 ) / 2 a+b+c+d=m(m-1)/2 a+b+c+d=m(m−1)/2成立。
基于等式1到4可以导出下面这些常用的聚类性能度量外部指标：
- Jaccard系数（Jaccard Coeffcient,简称JC）
J C = a a + b + c . ( 5 ) JC=\frac{a}{a+b+c}.(5) JC=a+b+ca.(5) - FM指数（Fowlkes and Mallows Index,FMI）
F M I = a a + b ⋅ a a + c ( 6 ) FMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}} (6) FMI=a+ba⋅a+ca (6) - Rand指数（Rand index,RI）
R I = 2 ( a + b ) m ( m − 1 ) . ( 7 ) RI=\frac{2(a+b)}{m(m-1)}.(7) RI=m(m−1)2(a+b).(7)
显然，上述性能度量的结果值均在区间[0,1]，值越大越好。
考虑聚类结果的簇划分 C = { C 1 , C 2 . . . , C k } C=\{C_1,C_2...,C_k\} C={C1,C2...,Ck}，定义
a v g ( C ) = 2 ∣ C ∣ ( ∣ C ∣ − 1 ) ∑ 1 ≤ i < j ≤ ∣ C ∣ d i s t ( x i , x j ) , ( 8 ) avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leq i<j\leq|C|}dist(x_i,x_j), \ (8) avg(C)=∣C∣(∣C∣−1)21≤i<j≤∣C∣∑dist(xi,xj), (8)
d i a m ( C ) = m a x 1 ≤ i < j ≤ ∣ C ∣ d i s t ( x i , x j ) , ( 9 ) diam(C)=max_{1\leq i<j\leq|C|}\ dist(x_i,x_j), (9) diam(C)=max1≤i<j≤∣C∣ dist(xi,xj),(9)
d m i n ( C i , C j ) = m i n x i ∈ C i , x j ∈ C j d i s t ( x i , x j ) , ( 10 ) d_{min}(C_i,C_j)=min_{x_i\in C_i,x_j\in C_j} \ dist(x_i,x_j), (10) dmin(Ci,Cj)=minxi∈Ci,xj∈Cj dist(xi,xj),(10)
d c e n ( C i , C j ) = d i s t ( μ i , μ j ) , ( 11 ) d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j), (11) dcen(Ci,Cj)=dist(μi,μj),(11)
其中， d i s t ( ⋅ , ⋅ ) dist(\cdot,\cdot) dist(⋅,⋅)用于计算两个样本之间的距离(距离越大则样本的相似度越低)； μ \mu μ 代表簇 C C C 的中心点 μ = 1 ∣ C ∣ ∑ 1 ≤ i ≤ ∣ C ∣ x i \mu=\frac{1}{|C|}\sum_{1\leq i\leq|C|}x_i μ=∣C∣1∑1≤i≤∣C∣xi，显然， a v g ( C ) avg(C) avg(C)对应于簇 C C C内样本间的平均距离， d i a m ( C ) diam(C) diam(C)对应于簇 C C C内样本间的最远距离， d m i n ( C i , C j ) d_{min}(C_i,C_j) dmin(Ci,Cj)对应于簇 C i C_i Ci与簇 C j C_j Cj最近样本间的距离， d c e n ( C i , C j ) d_{cen}(C_i,C_j) dcen(Ci,Cj)对应于簇 C i C_i Ci与簇 C j C_j Cj中心点的距离。
基于8~11可以导出下面这些常用的性能度量内部指标：
- DB指数（Davies-Bouldin Index，DBI）
D B I = 1 k ∑ i = 1 k m a x j ≠ i ( a v g ( C i ) + a v g ( C j ) d c e n ( μ i , μ j ) ) ( 12 ) DBI=\frac{1}{k}\sum^{k}_{i=1}max_{j\neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})(12) DBI=k1i=1∑kmaxj=i(dcen(μi,μj)avg(Ci)+avg(Cj))(12) - Duun指数（Duun ）
D I = m i n 1 ≤ i ≤ k { m i n j ≠ i ( d m i n ( μ i , μ j ) m a x 1 ≤ i ≤ k d i a m ( C l ) ） } ( 13 ) DI=min_{1\leq i\leq k}\{min_{j\neq i}(\frac{d_{min}(\mu_i,\mu_j)}{max_{1\leq i\leq k}diam(C_l)}）\}(13) DI=min1≤i≤k{minj=i(max1≤i≤kdiam(Cl)dmin(μi,μj)）}(13)
显然，DBI的值越小越好，而DI则相反，值越大越好。
三，距离计算（*）
对函数 d i s t ( ⋅ , ⋅ ) dist(\cdot,\cdot) dist(⋅,⋅)，若它是一个“距离度量”（distance measure），则需满足一些基本性质：
非 负 性 ： d i s t ( x i , x j ) ≥ 0 ( 14 ) 非负性：dist(x_i,x_j)\geq0 (14) 非负性：dist(xi,xj)≥0(14)
同 一 性 ： d i s t ( x i , x j ) = 0 当 且 仅 当 x i = x j ( 15 ) 同一性：dist(x_i,x_j)=0 当且仅当x_i=x_j (15) 同一性：dist(xi,xj)=0当且仅当xi=xj(15)
对 称 性 ： d i s t ( x i , x j ) = d i s t ( x j , x i ) ( 16 ) 对称性：dist(x_i,x_j)=dist(x_j,x_i) (16) 对称性：dist(xi,xj)=dist(xj,xi)(16)
直 递 性 ( 三 角 不 等 式 ) ： d i s t ( x i , x j ) ≤ d i s t ( x i , x k ) + d i s t ( x k , x j ) ( 17 ) 直递性(三角不等式)：dist(x_i,x_j)\leq dist(x_i,x_k)+dist(x_k,x_j) (17) 直递性(三角不等式)：dist(xi,xj)≤dist(xi,xk)+dist(xk,xj)(17)
给定样本 x i = { x i 1 , x i 2 . . . , x i n } x_i=\{x_{i1},x_{i2}...,x_{in}\} xi={xi1,xi2...,xin}与$x_j={x_{j1},x_ji2}…,x_{jn}},最常用的是“闵可夫斯基距离”（Minkowski distance）
d i s t m k ( x i , x j ) = ( ∑ u = 1 n ∣ x i u − x j u ∣ p ) 1 p ( 18 ) dist_mk(x_i,x_j)=(\sum^n_{u=1}|x_{iu}-x_{ju}|^p)^\frac{1}{p}(18) distmk(xi,xj)=(u=1∑n∣xiu−xju∣p)p1(18)
对于 p p p大于等于1，式（18）显然满足（14~17）d的距离度量基本性质，
p = 2 p=2 p=2时，闵可夫斯基距离即欧式距离（Euclidean distance）
d i s t e d ( x i , x j ) = ∣ ∣ x i , x j ∣ ∣ 2 = ( ∑ u = 1 n ∣ x i u − x j u ∣ 2 ) dist_{ed}(x_i,x_j)=||x_i,x_j||_2=\sqrt{(\sum^n_{u=1}|x_{iu}-x_{ju}|^2)} disted(xi,xj)=∣∣xi,xj∣∣2=(u=1∑n∣xiu−xju∣2)
p = 1 p=1 p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）也称街区距离（city block distance）
d i s t m a n ( x i , x j ) = ∣ ∣ x i , x j ∣ ∣ 1 = ∑ u = 1 n ∣ x i u − x j u ∣ dist_{man}(x_i,x_j)=||x_i,x_j||_1=\sum^n_{u=1}|x_{iu}-x_{ju}| distman(xi,xj)=∣∣xi,xj∣∣1=u=1∑n∣xiu−xju∣
p p p接近于 ∞ \infin ∞时，闵可夫斯基距离是切比雪夫距离。
我们常将属性划分为“连续属性”(continuous attribute)和“离散属性”（categorical attribute）,前者在定义域上有无穷多个取值，后者在定义域上是有限个取值，然而，在讨论距离计算时，属性是否定义了”序“关系更为重要，例如定义域为{1，2，3}的离散属性与连续属性的性质更接近一些，能够直接在属性上面计算距离，这样的属性通常我们称为有序，而{飞机，火车，巴士}这种我们称为无序，而闵可夫斯基距离适用于有序属性。
对于无序属性可以采用VDM(Value difference metric)，令 m u , a m_{u,a} mu,a表示属性 u u u上取值为 a a a的样本数， m u , a ， i m_{u,a，i} mu,a，i表示在第 i i i个样本簇中属性 u u u上取值为 a a a的样本数， k k k为样本簇数，则属性 u u u上两个离散值 a a a与 b b b之间的VDM距离为
于是，将闵可夫斯基距离和VDM结合即可处理混合属性，假定有 n c n_c nc个有序属性， n − n c n-n_{c} n−nc个无序属性，不失一般性，令有序属性排列在无序属性之前，则有
当样本空间中不同属性的重要性不同时，可使用”加权距离“（weighted distance）以加权闵可夫斯基距离为例：
其中权重 w i ≥ 0 ( i = 0 , 1 , ⋯ , n ) w_i\geq0(i=0,1,\cdots,n) wi≥0(i=0,1,⋯,n)表征不同属性的重要性，通常 ∑ i = 1 n w i = 1 \sum^n_{i=1}w_i=1 ∑i=1nwi=1.
需要注意的是，通常我们是基于某种形式的距离来定义”相似度度量“（similarity measure），距离越大，相似度越小。然而，用于相似度度量的距离未必一定要满足距离度量的所有基本性质，尤其是直递性。例如：
这样的距离叫做”非度量距离“（non-metric distance）。本篇介绍的距离计算式都是事先定义好的，但在不少现实任务中给，有必要基于数据样本来确定核时的距离计算式，这可以通过”距离度量学习“（distance metric learning）来实现。
后面的原型聚类，密度聚类，层次聚类下篇再更了
更多推荐
聚类的性能度量和距离计算
发布评论