Clustering

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

下面给出数学化的表达：假定样本集为 D = { x 1 , x 2 , … , x m } D=\{x1,x2,\dots,x_m\} D={x1,x2,…,xm​}包含$m$个无标记样本，每个样本$x_i=(x_{i1},x_{i2},\dots ,x_{in})$是一个$n$维的特征向量，则聚类算法将样本集$D$划分为$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\in C_{{\lambda }_i}$。于是，聚类的结果可以用一个簇标记向量来表示，即$\lambda =({\lambda }_1；{\lambda }_2；\dots ；{\lambda }_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 }^{\ast }$为聚类模型和参考模型给出的簇标记向量，那么得到以下四个量的定义：
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^*, \ \ i\lt j \} \\ b \ = \ |SD|, \ \ \ SD \ = \ \{(x_i,x_j)|\lambda_i=\lambda_j, \ \ \lambda_i^*\neq\lambda_j^*, \ \ i\lt j \} \\ c \ = \ |DS|, \ \ \ DS \ = \ \{(x_i,x_j)|\lambda_i\neq\lambda_j, \ \ \lambda_i^*=\lambda_j^*, \ \ i\lt j \} \\ d \ = \ |DD|, \ \ \ DD \ = \ \{(x_i,x_j)|\lambda_i\neq\lambda_j, \ \ \lambda_i^*\neq\lambda_j^*, \ \ i\lt j \} a = ∣SS∣,   SS = {(xi​,xj​)∣λi​=λj​,  λi∗​=λj∗​,  i<j}b = ∣SD∣,   SD = {(xi​,xj​)∣λi​=λj​,  λi∗​​=λj∗​,  i<j}c = ∣DS∣,   DS = {(xi​,xj​)∣λi​​=λj​,  λi∗​=λj∗​,  i<j}d = ∣DD∣,   DD = {(xi​,xj​)∣λi​​=λj​,  λi∗​​=λj∗​,  i<j}
这四个量的解释为：

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

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

Jaccard Coefficient(JC)

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

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

Fowlkes and Mallows Index(FMI)

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

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

Rand Index(RI)

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

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

Internal Index

下面来看内部指标，首先还是定义几个量:
$$\begin{gathered} avg(C)=\frac{2}{|C|(|C|-1)}\sum _{1\le i<j\le |C|}dist(x_i,x_j) \\ {d}_{max}(C)=ma{x}_{1\le i<j\le |C|}dist(x_i,x_j) \\ {d}_{min}(C_i,C_j)=mi{n}_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j) \\ {d}_{cen}(C_i,C_j)=dist({\mu }_i,{\mu }_j)\mu 表示簇C的中心点 \end{gathered}$$
还是来解释一下这四个量：

• $avg$：表示的是簇$C$内两两样本之间距离之和的平均值
• $d_{max}$：表示的是簇$C$内两两样本之间距离的最大值
• $d_{min}$：表示的是簇$C_i$和$C_j$最近样本之间的距离
• $d_{cen}$：表示的是簇$C_i$和$C_j$中心点之间的距离

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

Davis-Bouldin Index(DBI)

$$DBI=\frac{1}{k}\sum _{i=1}^{k}ma{x}_{j\ne i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)})$$

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_{1\le i\le k} \{min_{j\neq i}(\frac{d_{min}(C_i,\ C_j)}{max_{1\le 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$维实向量空间$R^n$，$x_i,x_j\in R^n$，$x_i=(x_i^{(1)},x_i^{(2)},\dots ,x_i^{(n)})$，$x_j=(x_j^{(1)},x_j^{(2)},\dots ,x_j^{(n)})$，那么$L_p$距离定义为：
$$L_P(x_i,x_j)=(\sum _{k=1}^n|x_i^{(k)}-x_j^{(k)}{|}^p{)}^{\frac{1}{p}}$$
特别的，当$p=1$时，就是曼哈顿距离；当$p=2$时，就是欧氏距离。

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

有了以上两种针对不同类别属性的距离计算公式以后，我们就可以将这两者结合起来，其中$n_c$表示数据集中连续属性的个数：
$$dist(x_i,x_j)=(\sum _{k=1}^{n_c}|x_{ik}-x_{jk}{|}^p+\sum _{k=n_c+1}^{n}VD{M}_p(x_{ik},x_{jk}){)}^{\frac{1}{p}}$$