KMean算法精讲

本文目录

  KMeas算法是一种聚类算法，同时也是一种无监督的算法，即在训练模型时并不需要标签，其主要目的是通过循环迭代，将样本数据分成

    K
   
  
  
   K
  
 
K类。

基本训练步骤

• Step1：初始化 K K K个聚类中心（不必是真是的样本）
• Step2：分别计算所有样本点到这 K K K个聚类中心的距离，并把样本点划分至距离最近的group
• Step3：针对于每个group，计算其组内的平均点作为新的聚类中心（例如用户有年龄、性别两个特征，针对于年龄特征直接求平均值即可，对于性别特征使用onehot编码，每个纬度都求其平均值即可）
• Step4：重复步骤2和3直到满足终止条件

其基本过程如下图所示：

关于KMeans的几个问题

KMeans算法的目标函数是什么？

  已知观测集

    (
   
   
    
     x
    
    
     1
    
   
   
    ,
   
   
    
     x
    
    
     2
    
   
   
    ,
   
   
    .
   
   
    .
   
   
    .
   
   
    ,
   
   
    
     x
    
    
     n
    
   
   
    )
   
  
  
   (x_1,x_2,...,x_n)
  
 
(x1​,x2​,...,xn​)，其中每个观测都是一个d维实向量，k平均聚类要把这

 
  
   
    n
   
  
  
   n
  
 
n个观测划分到

 
  
   
    K
   
  
  
   K
  
 
K个集合中

 
  
   
    (
   
   
    K
   
   
    ≤
   
   
    n
   
   
    )
   
  
  
   (K≤n)
  
 
(K≤n),使得组内平方和最小。换句话说，它的目标是找到使得下式满足的聚类

 
  
   
    
     S
    
    
     i
    
   
  
  
   S_i
  
 
Si​：

 
  
   
    
     
      
       arg min
      
      
       ⁡
      
     
     
      S
     
    
    
     
      ∑
     
     
      
       i
      
      
       =
      
      
       1
      
     
     
      K
     
    
    
     
      ∑
     
     
      
       x
      
      
       ∈
      
      
       
        S
       
       
        i
       
      
     
    
    
     ∣
    
    
     ∣
    
    
     
      x
     
     
      i
     
    
    
     −
    
    
     
      μ
     
     
      i
     
    
    
     ∣
    
    
     
      ∣
     
     
      2
     
    
   
   
    \argmin_S\sum\limits_{i=1}^K\sum\limits_{x\in S_i}||x_i-\mu_i||^2
   
  
 Sargmin​i=1∑K​x∈Si​∑​∣∣xi​−μi​∣∣2

其中

     u
    
    
     i
    
   
  
  
   u_i
  
 
ui​是

 
  
   
    
     S
    
    
     i
    
   
  
  
   S_i
  
 
Si​中所有点的均值

KMeans算法是否一定会收敛？

  将

    n
   
  
  
   n
  
 
n个数据分为

 
  
   
    K
   
  
  
   K
  
 
K个聚类，最多有

 
  
   
    
     n
    
    
     K
    
   
  
  
   n^K
  
 
nK种分类可能，这是一个很大但有限的数字。对于算法每次迭代，我们仅基于旧的聚类产生一个新的聚类。算法的性质如下：

• (1)如果旧的聚类与新的聚类相同，则下一次迭代的结果将再次相同。
• (2)如果新的聚类与旧的聚类不同，则更新的群集的目标函数值较低

  因此，KMeans算法的迭代过程总是在朝着目标函数减小的方向进行，进行优先次迭代之后，其目标值一定可以收敛。

不同的初始化是否带来不⼀样的结果？

不同的初始化显然会带来不同的结果，下面图片就可以表示：

K值如何进行选择？

  显然不同的K值也会导致最终的结果不同，那么我们该如何对K值进行选择？

  在这里我们定义一个概念Inertia：样本集中所有点离其所属cluster中心的距离的总和。

  因此我们可以使用交叉验证的方法，对不同的K值计算其Inertia，当

    K
   
  
  
   K
  
 
K趋近于

 
  
   
    n
   
  
  
   n
  
 
n时，Inertia的值一定是越来越小并且趋近于0，但其总会存在一个拐点，即Inertia下降的速度由快变为慢，我们一般取这个拐点的K值：

KMeans++

  所谓Kmeans++，即在Kmeans的基础上做了一些改进，主要是针对于初始点选择进行了优化，其初始点的选择过程如下：

• 1.从数据点中随机选择一个中心。
• 2.对于每个数据点 x x x，计算 D ( x ) D(x) D(x)，即 x x x与已经选择的最接近中心之间的距离。
• 3.使用加权概率分布随机选择一个新的数据点作为新的中心，其中选择点 x x x 的概率与 D ( x ) 2 D(x)^2 D(x)2成正比。
• 4.重复步骤2和3，直到选择了 K K K个中心。

其余训练过程与KMeans一致。

KMeans的优缺点

优点：

• 容易理解，容易实现
• 容易解释结果
• 计算复杂度比较低

缺点:

• 当数据的分布密度不均匀情况下，效果不理想
• 即使真实的聚类情况下不同聚类的个体数量非常不同，K-Means-也倾向让不同聚类包含的个体数据比较平均
• K-Means前提假设数据特征之间的联合分布是椭圆形的。这个条件在真实世界很难满足。
• K-Means无法处理环套环，缠绕S形的聚类
• 对异常值比较敏感
• 对初始化比较敏感

个人有关KMeans的奇思妙想

  上面有提到过，KMeans无法处理环套环，缠绕S形的聚类，也可以理解为对于分类问题，无法处理线性不可分的情况，但是我们在计算距离时如果有使用内积，比如余弦距离，那么我们就可以使用kernel trick，但缺点是对于核函数的选择我们往往需要采用交叉验证，这就需要我们使用带标签的数据来进行训练，而且现实中的意义可能不大。