【机器学习】K-Means聚类算法_k-means++算法

K-Means简介

     K-Means算法是一种无监督的聚类算法，由于算法实现相对简单，且聚类效果也不错，因此其被广泛应用于各个领域。此外，K-Means算法还有许多相关的变体算法，本文首先介绍传统的K-Means算法，然后在其基础上讲述K-Means的变体算法，包括K-Means++, K-Modes以及K-Prototype等等，本文将会简单介绍这几种变体算法。
 

K-Means原理

     K-Means算法原理非常简单，对于给定的样本集，分别计算样本与样本之间的距离，根据样本的远近程度将样本集划分为$k$个簇。K-Means算法的核心思想就是令处于同一簇的样本之间的距离都相对较近，此外，还要远离其他簇的样本，即让处于不同簇的样本之间的距离相对较远。
给定样本集 D = { x 1 , x 2 , … , x m } D=\{x_1,x_2,\ldots,x_m\} D={x1​,x2​,…,xm​}，K-Means算法针对聚类所得到的簇划分 C = { C 1 , C 2 , … , C k } C=\{C_1,C_2,\ldots,C_k\} C={C1​,C2​,…,Ck​}最小化平方误差
$$E=\sum _{i=1}^k\sum _{x\in C_i}{\Vert x-{\mu }_i\Vert }_2^2$$其中，${\mu }_i=\frac{1}{|C_i|}{\sum }_{x\in C_i}x$是簇$C_i$ 均值向量。直观来看$E$在一定程度上表示样本围绕簇均值向量的紧密程度，其中$E$的值越小说明簇内样本越紧密。
     为了求出$E$的最小值，需要初始化后迭代更新求解，其具体算法过程见下一节。
 

K-Means算法过程

     在上一节通过对K-Means算法原理的介绍，接下来将介绍其算法实现的过程。传统的K-Means算法过程如下所示：
输入： 样本集 D = { x 1 , x 2 , … , x m } D=\{x_1,x_2,\ldots,x_m\} D={x1​,x2​,…,xm​}
       聚类簇的数目$k$

输出： 簇划分 C = { C 1 , C 2 , … , C k } C=\{C_1,C_2,\ldots,C_k\} C={C1​,C2​,…,Ck​}

过程：

• 从$D$中随机选择$k$个样本作为初始的均值向量 { μ 1 , μ 2 , … , μ k } \{\mu_1,\mu_2,\ldots,\mu_k\} {μ1​,μ2​,…,μk​}
• 对于$n=1,2,\dots ,N$
  • 令$C_t=\varnothing (1\le t\le k)$
  • 对于$i=1,2,\dots ,m$计算样本$x_i$和各个质心向量${\mu }_j(j=1,2,\dots ,k)$的距离$d_{ij}={\Vert x_i-{\mu }_j\Vert }_2$
  • 根据最近的均值向量确定$x_i$簇标记 λ i = arg ⁡ min ⁡ i ∈ { 1 , 2 , … , k } d i j \lambda_i=\arg\min_{i\in\{1,2,\ldots,k\}}d_{ij} λi​=argmini∈{1,2,…,k}​dij​。将样本$x_i$划入对应的簇：$C_{{\lambda }_j}=C_{{\lambda }_j}\cup x_i$
  • 对于$j=1,2,\dots ,k$，对$C_j$中所有的样本点重新计算新的均值向量${\mu }_j=\frac{1}{|C_j|}{\sum }_{x\in C_j}x$
  • 如果所有的$k$个质心向量都没有发生变化，则跳出循环
• 输出簇划分 C = { C 1 , C 2 , … , C k } C=\{C_1,C_2,\ldots,C_k\} C={C1​,C2​,…,Ck​}
   

K-Means的变体算法

  通过K-Means聚类过程可以看到其操作非常简单，但是其也存在一定的局限性。为了可以更好的处理不同形式的聚类，各种变体算法一一被提出。
 

K-Means++

  从K-Means聚类过程可以看到初始化的$k$个均值向量选择对聚类结果和算法迭代次数都会产生很大的影响，因此如果可以设计一种策略来更好地初始化$k$个均值向量，用以代替传统的随机初始化，那么对算法将会有极大的提升。
  K-Means++算法就是对传统K-Means算法中随机初始化均值向量进行了改进优化。K-Means++中初始化均值向量策略具体如下：

1. 对于给定的样本集$D$，从中随机选择一个样本作为第一个聚类中心${\mu }_1$
2. 对于数据集中的每一个点$x_i$，计算$x_i$与已选择的聚类中心中最近的聚类中心的距离$dist(x_i)=\arg \min ||x_i-{\mu }_r|{|}_2^2$
3. 选择一个新的数据点作为新的聚类中心，选择的准则是：对应$dist(x)$较大的点$x$，被选取作为聚类中心的概率较大，其被选中的概率为$P(x)=\frac{dist(x{)}^2}{{\sum }_{x\in D}dist(x{)}^2}$
4. 重复第2步直到选择出$k$个聚类质心
5. 利用这$k$个均值向量作为传统的K-Means算法的初始化聚类中心

  K-Means++算法虽然在初始化聚类中心时消耗了多余的时间，但是其可以加速K-Means的收敛，相对而言，还是降低了总体的计算的时间。
 

K-Modes

  传统的K-Means算法往往只能适用于对数值型属性的样本集进行聚类，但是如果样本集中的样本属性是分类型的，那么原本K-Means算法中计算簇的均值向量以及样本之间的欧式距离就无法有效地实现。于是，变种算法K-Modes诞生了，其可以适用于分类型属性的样本集。
  给定一个样本集$D$，其中 D = { x 1 , x 2 , … , x n } D=\{x_1,x_2,\ldots,x_n\} D={x1​,x2​,…,xn​}，对于任一样本$x_t$，都有$m$个离散属性，即$x_t=[x_t^1,x_t^2,\dots ,x_t^m]$。

1. 随机确定$k$个聚类中心$C_1,C_2,\dots ,C_k$
2. 对于样本$x_i(i=1,2,\dots ,N)$，分别计算其与$k$个聚类中心的距离 （这里的距离表示两个样本中，其中不同属性值的个数。例如，$x_i=[1,0,2,3]$，$C_1=[1,1,2,9]$，其第二、第四属性不同，即$x_i$到$C_1$的距离为2）
3. 将$x_i$划分到与聚类中心距离最小的簇，在全部的样本都被划分完毕之后，重新确定簇中心，与传统K-Means不同的是，聚类中心$C_i$中对应每一个属性都更新为所在簇中样本对应属性的众数。
4. 重复步骤2和3，直到总距离（各个簇中样本与对应的聚类中心的距离和）不再降低，返回最后的聚类结果

  K-Modes算法与K-Means算法总体上是类似的，其算法也是相对比较简单，容易实现，只是在样本间距离的计算和聚类中心的更新这两方面有着一定的差别。
 

K-Prototype

  K-Means算法只能应用于全是数值型属性的样本集，而K-Modes算法只能应用于全是分类型属性的样本集，然而在实际问题中，我们的样本集中的样本往往是既存在数值型属性，又存在分类型属性。
  为了处理混合属性聚类的样本集，研究人员提出了K-Prototype，其结合了K-Means算法和K-Modes算法两者的思想，并且针对混合属性提出了描述样本簇的原型和混合属性样本之间的相异度。
  对于K-Prototype，需要对样本集的定义稍作修改：

   D = { x 1 , x 2 , … , x n } D=\{x_1,x_2,\ldots,x_n\} D={x1​,x2​,…,xn​}，其中包含$n$个样本
  对于$x_i$的$m$个属性，有$x_i=[x_{i,1}^r,x_{i,2}^r,\dots ,x_{i,p}^r,x_{i,p+1}^c,x_{i,p+2}^c,\dots ,x_{i,m}^c]$。

其中$r$代表数值型属性，$c$代表类别型属性，并且定义前$p$个属性为数值型属性，后$m-p$个属性为分类型属性。
  K-Prototype算法提出了混合属性簇的原型，我们可以理解原型就是数值属性聚类的聚类中心。混合属性中存在数值型属性和分类型属性，其中对于数值型属性使用属性对应取值的均值，对于分类型属性是在分类型属性中选取属性值众数。
  K-Prototype的相异度: 数值型属性选用欧氏距离，分类型属性选用汉明距离，两者分别计算再相加，就是K-Prototype的相异度距离。汉明距离是指两个相同维度的向量中对应属性值不同的个数。例如，$[1,1,1,1]$和$[1,0,0,1]$这两者的汉明距离是2。
  综上可以计算样本与原型（聚类中心）的相异度距离为：
$$d(x_i,Q_c)=\sum _{j=1}^p(x_{ij}^r-q_{cj}^r{)}^2+{\mu }_l\sum _{j=p+1}^m\delta (x_{ij}^c-q_{cj}^c)$$其中，在等号右侧部分，左边部分表示数值型属性的距离计算，右边部分表示分类型属性的距离计算。$Q_c$表示某一簇的原型（聚类中心），$q_{cj}$表示对应的原型中第$j$个属性，${\mu }_l$表示分类属性的权重因子，$\delta (\cdot )$代表汉明距离的计算。
  同时K-Prototype还定义了一个目标函数，随着算法不断迭代，直到目标函数值不变。
$$E=\sum _{c=1}^k\sum _{i=1}^n{y}_{ic}d(x_i,Q_c)$$其中$y_{ic}$表示在簇$c$中有没有这个样本，如果有的话，$y_{ic}=1$，没有的话，$y_{ic}=0$。
  有了目标函数后，就可以得出K-Prototype算法的算法过程。算法的步骤是：

1. 对于给定的样本集$D$，从中随机选取$k$个样本作为初始的$k$个簇的原型
2. 对于数据集中的每一个样本$x_i$，计算$x_i$与$k$个簇原型的相异度距离
3. 将该样本分配到相异度距离最小的对应簇中，分配完毕后，更新簇的原型
4. 重复步骤2和步骤3，直到目标函数直到目标函数值不再变化，聚类结束

 
 
如有错误，欢迎批评指出，谢谢！