K-Means聚类
2021-9-30
| 2023-8-6
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
Property

原理

K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。K-Means算法有大量的优化变体方法，包括初始化优化K-Means++ ，距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。
 

传统K-Means原理

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
如果用数据表达式表示，假设簇划分为 ，则目标是最小化平方误差：
是簇的均值向量，有时也称为质心，表达式为：
想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述。
notion image
上图a表达了初始的数据集，假设k=2。在图b中，随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，得到了所有样本点的第一轮迭代后的类别。此时对当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终得到的两个类别如图f。
当然在实际K-Mean算法中，一般会多次运行图c和图d，才能达到最终的比较优的类别
 

传统K-Means流程

K-Means算法的一些要点：
  • 对于K-Means算法，首先要注意的是值的选择，一般来说，可以根据对数据的先验经验选择一个合适的值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的值
  • 在确定了的个数后，需要选择个初始化的质心，就像上图b中的随机质心。由于是启发式方法，个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的个质心，最好这些质心不能太近
 
传统的K-Means算法流程：
输入是样本集，聚类的簇数，最大迭代次数
输出是簇划分
  1. 从数据集中随机选择个样本作为初始的 个质心向量：
  1. 对于
      • 将簇划分初始化为
      • 对于，计算样本和各个质心向量的距离： ，将标记最小的为所对应的类别此时更新
      • 对于，对 中所有的样本点重新计算新的质心
      • 如果所有的个质心向量都没有发生变化，则转到步骤3）
  1. 输出簇划分
 

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

个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。
K-Means++的对于初始化质心的优化策略也很简单，如下：
a) 从输入的数据点集合中随机选择一个点作为第一个聚类中心 b) 对于数据集中的每一个点，计算它与已选择的聚类中心中最近聚类中心的距离
c) 选择一个新的数据点作为新的聚类中心，选择的原则是： 较大的点，被选取作为聚类中心的概率较大 d) 重复b和c直到选择出个聚类质心 e) 利用这个质心来作为初始化质心去运行标准的K-Means算法
 

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

传统的K-Means算法在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢？
elkan K-Means利用了两边之和大于等于第三边，以及两边之差小于第三边的三角形性质，来减少距离的计算。
第一种规律是对于一个样本点 和两个质心 。如果预先计算出了这两个质心之间的距离，则如果计算发现 ，立即就可以知道 。此时不需要再计算 也就是说省了一步距离计算。
第二种规律是对于一个样本点和两个质心。可以得到。这个从三角形的性质也很容易得到。
利用上边的两个规律，elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果样本的特征是稀疏的，有缺失值的话，这个方法就不使用了，此时某些距离无法计算，则不能使用该算法
 

大样本优化Mini Batch K-Means

传统的K-Means算法要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的算法非常的耗时，就算加上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与KNN

K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

K-Means小结

K-Means的主要优点有：
  • 原理比较简单，实现也是很容易，收敛速度快
  • 聚类效果较优
  • 算法的可解释度比较强
  • 主要需要调参的参数仅仅是簇数k
K-Means的主要缺点有：
  • K值的选取不好把握
  • 对于不是凸的数据集比较难收敛
      • 实际应用中大部分时候是不知道数据是否是凸的，可以尝试去用Kmeans求解。如果发现效果很不好，怀疑数据严重非凸，那么此时可以考虑用其它不在意数据非凸的算法比如DBSCAN
  • 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳
  • 采用迭代方法，得到的结果只是局部最优
  • 对噪音和异常点比较的敏感
 
 

代码

在scikit-learn中，包括两个K-Means的算法，一个是传统的K-Means算法，对应的类是KMeans。另一个是基于采样的Mini Batch K-Means算法，对应的类是MiniBatchKMeans
KMeans类的主要参数有：
  • n_clusters:：k值，一般需要多试一些值以获得较好的聚类效果
  • max_iter：最大的迭代次数，一般如果是凸数据集的话可以不管这个值，如果数据集不是凸的，可能很难收敛，此时可以指定最大的迭代次数让算法可以及时退出循环
  • n_init：用不同的初始化质心运行算法的次数。由于K-Means是结果受初始值影响的局部最优的迭代算法，因此需要多跑几次以选择一个较好的聚类效果，默认是10，一般不需要改。如果k值较大，可以适当增大这个值。
  • init： 初始值选择的方式，可以为完全随机选择'random'，优化过的'k-means++'或者自己指定初始化的k个质心。一般建议使用默认的'k-means++'。
  • algorithm：有“auto”, “full” or “elkan”三种选择。"full"就是传统的K-Means算法， “elkan”是elkan K-Means算法。默认的"auto"则会根据数据值是否是稀疏的，来决定如何选择"full"和“elkan”。一般数据是稠密的，那么就是 “elkan”，否则就是"full"。一般来说建议直接用默认的"auto"
 
MiniBatchKMeans类的主要参数比KMeans类稍多，主要有：
  • n_clusters
  • max_iter
  • n_init：用不同的初始化质心运行算法的次数。这里和KMeans类意义稍有不同，KMeans类里的n_init是用同样的训练集数据来跑不同的初始化质心从而运行算法。而MiniBatchKMeans类的n_init则是每次用不一样的采样数据集来跑不同的初始化质心运行算法。
  • batch_size：用来跑Mini Batch KMeans算法的采样集的大小，默认是100，如果发现数据集的类别较多或者噪音点较多，需要增加这个值以达到较好的聚类效果。
  • init
  • init_size: 用来做质心初始值候选的样本个数，默认是batch_size的3倍，一般用默认值就可以了。
  • reassignment_ratio: 某个类别质心被重新赋值的最大次数比例，这个和max_iter一样是为了控制算法运行时间的。这个比例是占样本总数的比例，乘以样本总数就得到了每个类别质心可以重新赋值的次数。如果取值较高的话算法收敛时间可能会增加，尤其是那些暂时拥有样本数较少的质心。默认是0.01。如果数据量不是超大的话，比如1w以下，建议使用默认值。如果数据量超过1w，类别又比较多，可能需要适当减少这个比例值。具体要根据训练集来决定。
  • max_no_improvement：连续多少个Mini Batch没有改善聚类效果的话，就停止算法， 和reassignment_ratio， max_iter一样是为了控制算法运行时间的。默认是10，一般用默认值就足够了
 
K值的评估标准
不像监督学习的分类问题和回归问题，无监督聚类没有样本输出，也就没有比较直接的聚类评估方法。但是可以从簇内的稠密程度和簇间的离散程度来评估聚类的效果。常见的方法有轮廓系数Silhouette Coefficient和Calinski-Harabasz Index。
Calinski-Harabasz分数值 的数学计算公式是：
为样本数， 为类别数，为类别之间的协方差矩阵，为类别内部数据的协方差矩阵
类别内部数据的协方差越小越好，类别之间的协方差越大越好，这样的Calinski-Harabasz分数会高。在scikit-learn中， Calinski-Harabasz Index对应的方法是metrics.calinski_harabasz_score
 
notion image
相关文章 :
数据分析
  • Scikit-Learn
    • 层次聚类高斯混合模型GMM
    目录