聚类（上）

聚类任务

对于训练样本的标记信息是未知的情况下，我们的目标就会变成通过对无标记训练样本的学习来揭示数据的内在性质及规律，我们把这样的学习方法称之为“无监督学习”，而在此类学习任务中，研究最多应用最广的就是“聚类”。

在聚类算法中，我们试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个“簇”。而对于样本来说，我们并不知道其内部存在的类别，所以我们分出的这些“簇”就可能对应着一些潜在的概念（类别），与分类算法的区别就在于，这些潜在的概念在之前我们是完全未知的。

一般的聚类结果展示如下图所示：

基于不同的学习策略，人们设计出多种类型的聚类算法，在学习算法之前，我们先来了解一下性能度量和距离运算。

性能度量

我们在之前的文章中了解过了分类算法的评估方式，对于聚类来说，我们有一些特殊的性能度量方式，让我们来了解一下。

对于聚类来说，我们把每个类别分成了相应的“簇”，直观上看我们希望“物以类聚”，而想要把很多“簇”聚的好，我们就希望“簇内的相似度”高且”簇间的相似度“低。

聚类的性能度量大致分类两类，一类是将聚类结果与某个”参考模型“进行比较，称为”外部指标“；另一类是直接考察聚类结果而不利用任何参考模型，称为”内部指标“。

对于数据集$D={x_1,x_2,...,x_m}$D=x1​,x2​,...,xm​，假定通过聚类给出的簇划分为$C=\{C_1,C_2,...,C_k\}$C={C1​,C2​,...,Ck​}，参考模型给出的簇划分为$C^*=\{C_1^*,C_2^*,...,C_k^*\}$C∗={C1∗​,C2∗​,...,Ck∗​}，相应的我们用$\lambda$λ和$\lambda^*$λ∗分别表示$C$C和$C^*$C∗对应的簇标记向量，我们将样本两两配对考虑，定义如下的内容：

$a = |SS|,SS=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}$a=∣SS∣,SS={(xi​,xj​)∣λi​=λj​,λi∗​=λj∗​,i<j}

$b = |SD|,SD=\{(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j\}$b=∣SD∣,SD={(xi​,xj​)∣λi​=λj​,λi∗​​=λj∗​,i<j}

$c = |DS|,DS=\{(x_i,x_j)|\lambda_i\neq\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}$c=∣DS∣,DS={(xi​,xj​)∣λi​​=λj​,λi∗​=λj∗​,i<j}

$d = |DD|,DD=\{(x_i,x_j)|\lambda_i\neq\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}$d=∣DD∣,DD={(xi​,xj​)∣λi​​=λj​,λi∗​=λj∗​,i<j}

其中集合SS包含了在$C$C中隶属于相同簇且在$C^*$C∗中也隶属于相同簇的样本对，其他集合同理，由于每个样本对仅能出现在一个集合中，因此我们有$a+b+c+d=\frac{m(m-1)}{2}$a+b+c+d=2m(m−1)​成立。

根据上面的式子，我们可以得到下面这些常用的外部指标：

Jaccard系数

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

FM指数

$FMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}}$FMI=a+ba​⋅a+ca​​

Rand指数

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

很显然，对于上面的性能度量结果来说，结果值都在[0,1]之间，并且值越大越好。

考虑聚类结果的簇划分$C={C_1,C_2,...C_k}$C=C1​,C2​,...Ck​，定义：

$avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leqslant i<j\leqslant|C|}dist(x_i,x_j)$avg(C)=∣C∣(∣C∣−1)2​∑1⩽i<j⩽∣C∣​dist(xi​,xj​)

$diam(C)=max_{1\leqslant i<j\leqslant|C|}dist(x_i,x_j)$diam(C)=max1⩽i<j⩽∣C∣​dist(xi​,xj​)

$d_{min}(C_i,C_j)=min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)$dmin​(Ci​,Cj​)=minxi​∈Ci​,xj​∈Cj​​dist(xi​,xj​)

$d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)$dcen​(Ci​,Cj​)=dist(μi​,μj​)

其中，dist()用于计算两个样本之间的距离；$\mu$μ代表簇C的中心点$\mu=\frac{1}{|C|}\sum_{1\leqslant i\leqslant|C|}x_i$μ=∣C∣1​∑1⩽i⩽∣C∣​xi​，显然$avg(C)$avg(C)对应于簇$C$C内样本间的平均距离，$diam(C)$diam(C)对应于簇$C$C内样本间的最远距离，$d_{min}$dmin​对应于簇$C_i$Ci​与簇$C_j$Cj​最近样本间的距离，$d_{cen}(C_i,C_j)$dcen​(Ci​,Cj​)对应于簇$C_i$Ci​与簇$C_j$Cj​中心点间的距离。

根据上面的式子，我们可以得到下面这些常用的内部指标：

DB指数

$DBI=\frac{1}{k}\sum_{i=1}^k\underset{j\neq i}{max}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})$DBI=k1​∑i=1k​j​=imax​(dcen​(μi​,μj​)avg(Ci​)+avg(Cj​)​)

Dunn指数

$DI=\underset{1\leqslant i\leqslant k}{min}\{\underset{j\neq i}{min}(\frac{d_{min}(C_i,C_j)}{\underset{1\leqslant l \leqslant k}{max}diam(C_l)})\}$DI=1⩽i⩽kmin​{j​=imin​(1⩽l⩽kmax​diam(Cl​)dmin​(Ci​,Cj​)​)}

很显然，DBI的值越小越好，DI的值越大越好。

距离度量

对于函数$dist()$dist()，如果他表示一个距离的度量，我们就要满足一些基本性质：

• 非负性

$dist(x_i,x_j)\geqslant0$dist(xi​,xj​)⩾0

• 同一性（当且仅当$x_i=x_j$xi​=xj​）

$dist(x_i,x_j)=0$dist(xi​,xj​)=0

• 对称性

$dist(x_i,x_j)=dist(x_j,x_i)$dist(xi​,xj​)=dist(xj​,xi​)

• 直递性(三角不等式)

$dist(x_i,x_j)\leqslant dist(x_i,x_k)+dist(x_k,x_j)$dist(xi​,xj​)⩽dist(xi​,xk​)+dist(xk​,xj​)

给定样本$x_i=(x_{i1};x_{i2};...;{x_{in}})$xi​=(xi1​;xi2​;...;xin​)与$x_j=(x_{j1};x_{j2};...;x_{jn})$xj​=(xj1​;xj2​;...;xjn​)，最常用的是“闵可夫斯基距离”：

$dist_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}$distmk​(xi​,xj​)=(∑u=1n​∣xiu​−xju​∣p)p1​

当闵可夫斯基距离中的p=1时，我们称之为曼哈顿距离：

$dist_{man}(x_i,x_j)=\sum_{u=1}^{n}|x_{iu}-x_{ju}|$distman​(xi​,xj​)=∑u=1n​∣xiu​−xju​∣

当闵可夫斯基距离中的p=2时，我们称之为欧几里得距离（欧式距离）：

$dist_{ed}(x_i,x_j)=\sqrt{\sum_{u=1}^{n}|x_{iu}-x_{ju}|^2}$disted​(xi​,xj​)=∑u=1n​∣xiu​−xju​∣2​

很显然我们的闵可夫斯基以及相关的距离度量方式只能够对数值型属性进行度量，例如集合{1,2,3}；但是当我们遇到类别型数据的时候，就无法进行计算了，例如集合{苹果，西瓜，橘子}，对应着我们有下面的计算方法：

VDM

令$m_{u,a}$mu,a​表示在属性u上取值为a的样本数，$m_{u,a,i}$mu,a,i​表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a与b之间的VDM距离为：

$VDM_p(a,b)=\sum_{i=1}^{k}|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$VDMp​(a,b)=∑i=1k​∣mu,a​mu,a,i​​−mu,b​mu,b,i​​∣p

有了VDM之后，我们将闵可夫斯基距离和VDM进行结合去处理混合属性：

$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^nVDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$MinkovDMp​(xi​,xj​)=(∑u=1nc​​∣xiu​−xju​∣p+∑u=nc​+1n​VDMp​(xiu​,xju​))p1​

注：当我们遇到的不同属性的重要性不同的时候，我们也可以对特征进行加权。

K-Means聚类

聚类算法中，最典型最常用的算法就是K-Means（K均值）算法，让我们来了解一下K-Means的原理及流程。

K-Means算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。K-Means算法的流程如下：

输入是样本集$D={x_1,x_2,...,x_m}$D=x1​,x2​,...,xm​,聚类的簇树k,最大迭代次数N;

输出是簇划分$C=\{C_1,C_2,...,C_k\}$C={C1​,C2​,...,Ck​}

（1）给定一个k值（适当即可），意味着我们希望数据样本经过聚类后会聚成k个簇（k类）；

（2）从数据集中随机选择k课数据点作为质心（Centroid）$\{\mu_1,\mu_2,...,\mu_k\}${μ1​,μ2​,...,μk​};

（3）计算数据集中每一个样本到每个质心的距离（一般适用欧式距离），离哪个质心的距离近，就把该样本分到哪个质心中，数据集此时被分为k个簇；

（4）对于这k个簇，重新计算每个簇的质心，（计算的方法会在下面说明）；

（5）如果新的质心和之前的质心之间的距离小于某一个设定的阈值，可以认为我们的聚类已经达到了期望的结果，算法终止；

（6）迭代N次如果新的质心和之前的质心差别较大，则重新进行（3）（4）（5）的过程；

（7）最终输出划分。

在流程中提到的质心的计算方法如下：

$\mu_j=\frac{1}{C_j}\sum_{x\in C_j}x$μj​=Cj​1​∑x∈Cj​​x

K-Means++（初始化优化）

K-Means++（初始化优化）

根据K-Means算法的原理我们不难发现，最初的质心选择对聚类的结果和运行时间有着很大的影响，因此我们需要选择合适的K个质心，K-Means++就使用了更优化的方法来初始化质心，让我们来看一下K-Means++的优化策略：

（1）从输入的数据点集合中随机选择一个点作为第一个聚类中心$\mu_1$μ1​；

（2）对于数据集中的每一个点$x_i$xi​，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)；

（3）选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大；

（4）重复（2）（3）步骤直到选择出k个聚类质心；

（5）利用这k个质心来作为初始化质心去运行标准的K-Means算法。

过程中提到的D(x)计算方法如下：

$D(x_i)=argmin||x_i-\mu_r||_2^2，r=1,2,...,k$D(xi​)=argmin∣∣xi​−μr​∣∣22​，r=1,2,...,k

elkan K-Means（距离计算优化）

elkan K-Means（距离计算优化）

在传统的K-means算法中，我们每次迭代都需要计算所有样本到所有质心的距离，这样做会大大浪费我们的时间，elkan K-Means算法就是从距离的优化，去减少一些不必要的距离计算，来看一下它的原理。

elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质，来减少距离的计算。

（1）对于一个样本点x和两个质心$\mu_{j1},\mu_{j2}$μj1​,μj2​。如果我们预先计算出了这两个质心之间的距离$D(j_1,j_2)$D(j1​,j2​)，如果计算发现$2D(x,j_1)\leq D(j_1,j_2)$2D(x,j1​)≤D(j1​,j2​)，我们立即就可以知道$D(x,j_1)\leq D(x,j_2)$D(x,j1​)≤D(x,j2​)，此时我们也就不需要再去计算$D(x,j_2)$D(x,j2​)，也就是说我们少算了一个距离。

（2）对于一个样本点x和两个质心$\mu_{j1},\mu_{j2}$μj1​,μj2​，我们可以得到$D(x,j_2)\geq max\{0,D(x,j_1)-D(j_1,j_2)\}$D(x,j2​)≥max{0,D(x,j1​)−D(j1​,j2​)}。根据三角形的性质我们很容易得到这样的结果。

利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法。

Mini Batch K-Means（大样本优化）

Mini Batch K-Means（大样本优化）

在传统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。

顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。这batch size个样本般是通过无放回的随机采样得到的。

为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。

K-means小结

K-Means的主要优点有：

• 原理比较简单，实现也是很容易，收敛速度快；

• 聚类效果较优；

• 算法的可解释度比较强；

• 主要需要调参的参数仅仅是簇数k。

K-Means的主要缺点有：

• K值的选取不好把握；

• 对于不是凸的数据集比较难收敛；

• 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳；

• 采用迭代方法，得到的结果只是局部最优；

• 对噪音和异常点比较的敏感。