直观理解 K平均算法 (K-means clustering)

Ilingis

聚类又称无监督学习：也就是没有因变量(标签) 情况下，将数据进行合理的分组
聚类评估指标原则

• 簇内(Intra cluster)：簇内的点，互相距离应该很小
  
• 簇间(Inter cluster)：簇间的 距离应该很大
  

Dunn指数：

是评估聚类算法的指标；对于一个好的聚类结果，Dunn指数应该是很大的

也就等于

• ：指的是簇间(Inter cluster)距离
  
• ：指的是簇内(Intra cluster)距离
  

直观几何理解Dunn指数：

• 将  两簇数据的每一个点，互相两两计算距离，为 ; 然后取最小距离： 为 最小簇间距离
  
• 分别在 两簇数据中求出最大两点距离 ,然后 为 最大簇内距离
  

一

扩展：后续再总结其它无监督学习评估指标
K平均算法 (K-means clustering)

几何解释




二

K-means中：K 就是簇数量或组类数量；为超参数

• 初始化：随机任取 K 个类，如K=2
  
• 在数据中随机选取2个点，为质心点(Centroids)
  
• 将所有的点与此两个质心点计算距离，选择最近的质心点，进行分类
  
• 最后，根据分类完成后的 2 簇数据，分别计算簇内距离的平均值，确定为新的质心
  
• 再重复3，4步骤，直到收敛（也就是所有质心点，进行 第4步 后没有太大变化）
  

数学解释与目标函数




三

目标函数：
约束条件： ，
小结：

• ：为质心点
  
• ：为簇群点
  
• ：为簇群的点数
  
• 目标函数：就是优化，簇内各点到质心点 距离最小
  

扩展：上述公式具有指数时间复杂度：优化困难；后续将探讨近似算法求解优化问题
如何初始化:K-Means++

K-Means具有初始化敏感性(initialization sensitivity)：在初始化 K 个质心点时，随机化的点不同，因此最终分类的结果也可能会发生变化；
初始化敏感性几何解释




四

• original points：为原始图
  
• 下面两图，为随机初始化 质心点后，两种不同的模型收敛结果
  

1、第一种初始化质心点后，收敛的结果【想要的结果】



五

1、第二 种初始化质心点后，收敛的结果【错误的结果】



六

K-Means++

1、在初始化时，首先只随机选择一个质心点  
2、然后计算每个点到  质心点  的距离  



七

3、第二个质心点 随机选择的概率，与 步骤 2 中的距离大小成正比；距离越大被选中的概率也就越大
4、选择好了两个质心点  ，那么再次计算所有点到质心点 的距离，然后根据较大距离；大概率地选择 第三个质心点



八

5、重复以上步骤，达到最终收敛效果
小结：在上述步骤中，没有利用距离最大的(绝对的方式)，来进行质心点的选择，而是利用概率(相对的方式)进行质点选择，是因为相对概率，可以降低异常值的影响
K-means的局限性

1、簇的不同大小(different sizes)



九

2、簇的不同密度(different densities)



十

3、非凸形状(non-convex)



十一

扩展：可使用较大的 K 来获得多个簇群，然后将不同的簇群进行合并，但实现比较繁琐，并非较好的方案
K中心点算法(K-medoids)

K-means的质心点可能是不可解释的：
比如在BOW(词袋模型)中，所有点的都是二进制向量 ；而K-means的质心点根据平均值计算出来后的向量可能为 ，那么这样的向量是被新创建出来的，没法解释是哪个点
K中心点算法(K-medoids)：不是给出使用平均值计算的质心，而是一个实际的数据点，具有可解释性；K中心点算法步骤如下：

• 随机选取K个中心点
  
• 计算各个点到中心点的距离 ，然后将点根据最短距离，进行分类，得到K 个簇群
  
• 将K中心点，在各自簇群里，与其它点进行交互；然后计算各点到中心点距离，如果损失减少(也就是求和距离减少)，保持中心点的交换否则撤销交换
  
• 重复2，3，直到收敛
  

K 值选择

K 值为超参数，可以利用网格搜索，选择最小目标函数值的 K值，为最优选择
参考：

• https://en.wikipedia.org/wiki/K-means_clustering
  
• https://cs.wmich.edu/alfuqaha/summer14/cs6530/lectures/ClusteringAnalysis.pdf