聚类算法总览

聚类算法总览 Clustering

下面我们进入聚类部分。“聚类”算法，从名字来看，和分类有点像。的确，我认为这两者做的本质工作是一样的，只是这两种模型所处理的数据不太一样。分类算法大多是有监督学习(Supervised Learning)，也就是数据集是有标注的。但是聚类算法是一类无监督学习算法(Unsupervised Learning)，也就是数据集是没有类别标签的，而我们聚类模型的任务就是将这些没有类别标记的数据划分开，并且希望划分的结果好。下面给出一个动图为例来展示聚类的大体流程

下面给出数学化的表达：假定样本集为 D = { x 1 , x 2 , … , x m } D={x1,x2,dots,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},dots,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,dots,k} {Cl​∣l=1,2,…,k}。相应的，我们用 λ i ∈ { 1 , 2 , … , k } lambda_{i}in{1,2,dots,k} λi​∈{1,2,…,k}表示包含样本 x i x_i xi​的簇的簇标记，即 x i ∈ C λ i x_iin C_{lambda_{i}} xi​∈Cλi​​。于是，聚类的结果可以用一个簇标记向量来表示，即 λ = ( λ 1 ； λ 2 ； … ； λ k ) lambda=(lambda_1； lambda_2；dots；lambda_k) λ=(λ1​；λ2​；…；λk​)。

Validity Index

根据上面的描述，我们不难发现，如何去度量一个聚类模型的好坏是非常重要的。在分类、回归任务中，我们通常都是找到度量模型性能的指标，然后以这个指标作为目标函数进行优化。那么在聚类模型中，我们的指标从直观上来说就是要“物以类聚，人以群分”。聚类模型有两类指标，一种叫做外部指标，即我们有一个参考模型，然后我们用我们模型的结果与参考模型的结果进行比较；另一种叫做内部指标，即不借助参考模型的指标。

External Index

对于数据集 D = { x 1 , x 2 , … , x m } D={x1,x2,dots,x_m} D={x1,x2,…,xm​}，假设聚类模型给出的聚类结果为 C = { C 1 , C 2 , … , C k } C={C_1,C_2,dots,C_k} C={C1​,C2​,…,Ck​}，参考模型给出的结果为 C = { C 1 ∗ , C 2 ∗ , … , C k ∗ } C={C_1^*,C_2^*,dots,C_k^* } C={C1∗​,C2∗​,…,Ck∗​}，相应的，我们设 λ lambda λ和 λ ∗ lambda^* λ∗为聚类模型和参考模型给出的簇标记向量，那么得到以下四个量的定义：
a   =   ∣ S S ∣ ,     S S   =   { ( x i , x j ) ∣ λ i = λ j ,    λ i ∗ = λ j ∗ ,    i < j } b   =   ∣ S D ∣ ,     S D   =   { ( x i , x j ) ∣ λ i = λ j ,    λ i ∗ ≠ λ j ∗ ,    i < j } c   =   ∣ D S ∣ ,     D S   =   { ( x i , x j ) ∣ λ i ≠ λ j ,    λ i ∗ = λ j ∗ ,    i < j } d   =   ∣ D D ∣ ,     D D   =   { ( x i , x j ) ∣ λ i ≠ λ j ,    λ i ∗ ≠ λ j ∗ ,    i < j } a = |SS|, SS = {(x_i,x_j)|lambda_i=lambda_j, lambda_i^*=lambda_j^*, ilt j } \ b = |SD|, SD = {(x_i,x_j)|lambda_i=lambda_j, lambda_i^*neqlambda_j^*, ilt j } \ c = |DS|, DS = {(x_i,x_j)|lambda_ineqlambda_j, lambda_i^*=lambda_j^*, ilt j } \ d = |DD|, DD = {(x_i,x_j)|lambda_ineqlambda_j, lambda_i^*neqlambda_j^*, ilt j } a = ∣SS∣,   SS = {(xi​,xj​)∣λi​=λj​,  λi∗​=λj∗​,  i 这四个量的解释为：

a a a：对于任意两个样本 x i , x j x_i,x_j xi​,xj​，它们在聚类模型属于同一簇，并且在参考模型中也属于同一簇 b b b：对于任意两个样本 x i , x j x_i,x_j xi​,xj​，它们在聚类模型属于同一簇，但在参考模型中也不属于同一簇 c c c：对于任意两个样本 x i , x j x_i,x_j xi​,xj​，它们在聚类模型不属于同一簇，但在参考模型中也属于同一簇 d d d：对于任意两个样本 x i , x j x_i,x_j xi​,xj​，它们在聚类模型不属于同一簇，并且在参考模型中也不属于同一簇

那么根据这四个量，我们可以得到以下几个常用的度量聚类模型的外部指标：

Jaccard Coefficient(JC)

J C     =     a a   +   b   +   c JC = frac{a}{a + b + c} JC   =   a + b + ca​

JC系数越大，聚类的效果就越好

Fowlkes and Mallows Index(FMI)

F M I     =     a a   +   b ⋅ a a   +   c FMI = sqrt{frac{a}{a + b}cdot frac{a}{a + c}} FMI   =   a + ba​⋅a + ca​ ​

FMI系数越大，聚类效果越好

Rand Index(RI)

R I     =     2 ( a   +   d ) m ( m   −   1 ) RI = frac{2(a + d)}{m(m - 1)} RI   =   m(m − 1)2(a + d)​

RI系数越大，聚类效果越好

Internal Index

下面来看内部指标，首先还是定义几个量:
a v g ( C )   =   2 ∣ C ∣ ( ∣ C ∣ − 1 ) ∑ 1 ≤ i < j ≤ ∣ C ∣ d i s t ( x i ,   x j ) d m a x ( C )   =   m a x 1 ≤ i < j ≤ ∣ C ∣ d i s t ( x i ,   x j ) 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 ) d c e n ( C i ,   C j )   =   d i s t ( μ i , μ j )            μ 表 示 簇 C 的 中 心 点 avg(C) = frac{2}{|C|(|C|-1)}sum_{1le ilt jle|C|}dist(x_i, x_j) \ d_{max}(C) = max_{1le ilt jle|C|}dist(x_i, x_j) \ d_{min}(C_i, C_j) = min_{x_iin{C_i},x_jin{C_j}} dist(x_i, x_j) \ d_{cen}(C_i, C_j) = dist(mu_i, mu_j) mu表示簇C的中心点 avg(C) = ∣C∣(∣C∣−1)2​1≤i 还是来解释一下这四个量：

a v g avg avg：表示的是簇 C C C内两两样本之间距离之和的平均值 d m a x d_{max} dmax​：表示的是簇 C C C内两两样本之间距离的最大值 d m i n d_{min} dmin​：表示的是簇 C i C_i Ci​和 C j C_j Cj​最近样本之间的距离 d c e n d_{cen} dcen​：表示的是簇 C i C_i Ci​和 C j C_j Cj​中心点之间的距离

根据以上四个量，我们可以得到以下两个常用的内部指标

Davis-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 ( C i ,   C j ) ) DBI = frac{1}{k}sum_{i=1}^{k}max_{jneq i}(frac{avg(C_i) + avg(C_j)}{d_{cen}(C_i, C_j)}) DBI   =   k1​i=1∑k​maxj​=i​(dcen​(Ci​, Cj​)avg(Ci​) + avg(Cj​)​)

DBI系数越小，聚类效果越好

Dunn Index(DI)

D I     =     m i n 1 ≤ i ≤ k { m i n j ≠ i ( d m i n ( C i ,   C j ) m a x 1 ≤ l ≤ k d m a x ( C l ) ) } DI = min_{1le ile k} {min_{jneq i}(frac{d_{min}(C_i, C_j)}{max_{1le l le k} d_{max}(C_l)})} DI   =   min1≤i≤k​{minj​=i​(max1≤l≤k​dmax​(Cl​)dmin​(Ci​, Cj​)​)}

DI系数越大，聚类效果越好

Distance

在聚类任务中，另一个重要的环节就是距离的计算，这个部分其实和KNN中距离的计算类似，我们依然可以使用闵可夫斯基距离进行计算。

设 n n n维实向量空间 R n R^n Rn， x i , x j ∈ R n x_i,x_jin{R^n} xi​,xj​∈Rn， x i = ( x i ( 1 ) , x i ( 2 ) , … , x i ( n ) ) x_i=(x_{i}^{(1)}, x_{i}^{(2)},dots,x_{i}^{(n)}) xi​=(xi(1)​,xi(2)​,…,xi(n)​)， x j = ( x j ( 1 ) , x j ( 2 ) , … , x j ( n ) ) x_j=(x_{j}^{(1)},x_{j}^{(2)},dots,x_{j}^{(n)}) xj​=(xj(1)​,xj(2)​,…,xj(n)​)，那么 L p L_p Lp​距离定义为：
L P ( x i , x j ) = ( ∑ k = 1 n ∣ x i ( k ) − x j ( k ) ∣ p ) 1 p L_P(x_i, x_j) = (sum_{k=1}^n|x_i^{(k)} - x_j^{(k)}|^p)^{frac{1}{p}} LP​(xi​,xj​)=(k=1∑n​∣xi(k)​−xj(k)​∣p)p1​
特别的，当 p = 1 p=1 p=1时，就是曼哈顿距离；当 p = 2 p=2 p=2时，就是欧氏距离。

对于连续的属性，我们可以直接使用 L p L_p Lp​进行计算，但是对于离散的属性，比如说颜色有10种，取值 0 ∼ 9 0sim 9 0∼9，这时候就不能用欧氏距离或者曼哈顿距离来计算了。用数学语言来说，就是要看这个属性是否定义了“序”关系，如果没有定义的话，那就是不可比的。对于这种“无序”属性，有一种计算“距离”的方法，叫做Value Difference Metric(VDM)，计算公式如下：
V D M p ( a ,   b )   =   ∑ i = 1 k ∣ m u , a , i m u , a   −   m u , b , i m u , b ∣ VDM_{p}(a, b) = sum_{i=1}^k|frac{m_{u,a,i}}{m_{u,a}} - frac{m_{u,b,i}}{m_{u,b}}| VDMp​(a, b) = i=1∑k​∣mu,a​mu,a,i​​ − mu,b​mu,b,i​​∣
其中， u u u是某个属性， a , b a,b a,b是属性 u u u的两种取值， m u , a , i , m u , b , i m_{u,a,i},m_{u,b,i} mu,a,i​,mu,b,i​表示第 i i i个样本簇中属性 u u u取值分别为 a a a和 b b b的样本数， m u , a m_{u,a} mu,a​和 m u , b m_{u,b} mu,b​表示数据集中属性 u u u取值为 a a a或 b b b的样本数。

有了以上两种针对不同类别属性的距离计算公式以后，我们就可以将这两者结合起来，其中 n c n_c nc​表示数据集中连续属性的个数：
d i s t ( x i ,   x j ) = ( ∑ k = 1 n c ∣ x i k   −   x j k ∣ p   +   ∑ k = n c + 1 n V D M p ( x i k ,   x j k ) ) 1 p dist(x_i, x_j) = (sum_{k=1}^{n_c}|x_{ik} - x_{jk}|^{p} + sum_{k=n_c+1}^{n}VDM_p(x_{ik}, x_{jk}))^{frac{1}{p}} dist(xi​, xj​)=(k=1∑nc​​∣xik​ − xjk​∣p + k=nc​+1∑n​VDMp​(xik​, xjk​))p1​