K-Means 的工作原理

基于向量距离来做聚类

  • 选取 K 个点作为初始的类中心点，这些点一般都是从数据集中随机抽取的；

  • 将每个点分配到最近的类中心点，这样就形成了 K 个类，然后重新计算每个类的中心点；

  • 重复第二步，直到类不发生变化，或者你也可以设置最大迭代次数，这样即使类中心点发生变化，但是只要达到最大迭代次数就会结束。

Notes:

  • 需要指定类簇的数量
  • 给定初始的类中心

聚类距离计算方法：

  • 欧氏距离

  • 曼哈顿距离

  • 切比雪夫距离

  • 余弦距离

聚类簇的确定

经验法

对于n个样本空间，簇数p为6. K-Means - 图1，每个簇大约有6. K-Means - 图2个点

肘方法

评价K值好坏的标准是SSE（sum of the squared errors）

6. K-Means - 图3

  • 6. K-Means - 图4代表第i个簇
  • p是簇6. K-Means - 图5里的样本点
  • 6. K-Means - 图6是簇的质心

随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于最佳聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达最佳聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的最佳聚类数。这也是该方法被称为手肘法的原因。

sklearn的实现

  1. from sklearn.cluster import KMeans

我们看下 K-Means 如何创建：

KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')

我们能看到在 K-Means 类创建的过程中，有一些主要的参数：

  • n_clusters: 即 K 值，一般需要多试一些 K 值来保证更好的聚类效果。你可以随机设置一些 K 值，然后选择聚类效果最好的作为最终的 K 值；

  • max_iter： 最大迭代次数，如果聚类很难收敛的话，设置最大迭代次数可以让我们及时得到反馈结果，否则程序运行时间会非常长；

  • n_init：初始化中心点的运算次数，默认是 10。程序是否能快速收敛和中心点的选择关系非常大，所以在中心点选择上多花一些时间，来争取整体时间上的快速收敛还是非常值得的。由于每一次中心点都是随机生成的，这样得到的结果就有好有坏，非常不确定，所以要运行 n_init 次, 取其中最好的作为初始的中心点。如果 K 值比较大的时候，你可以适当增大 n_init 这个值；

  • init： 即初始值选择的方式，默认是采用优化过的 k-means++ 方式，你也可以自己指定中心点，或者采用 random 完全随机的方式。自己设置中心点一般是对于个性化的数据进行设置，很少采用。random 的方式则是完全随机的方式，一般推荐采用优化过的 k-means++ 方式；

  • algorithm：k-means 的实现算法，有“auto” “full”“elkan”三种。一般来说建议直接用默认的”auto”。简单说下这三个取值的区别，如果你选择”full”采用的是传统的 K-Means 算法，“auto”会根据数据的特点自动选择是选择“full”还是“elkan”。我们一般选择默认的取值，即“auto” 。