算法笔记：kmeans聚类算法简介

关键词：

• 算法笔记：Kmeans聚类算法简介
  • 1. Kmeans算法简介
  • 2. Kmeans算法细节
  • 3. Kmeans算法收敛性证明
  • 4. Kmeans算法的变体
    • 1. cosine距离变体
    • 2. 点积距离版本
  • 5. Kmeans算法实现
    • 1. 基于sklearn的kmeans算法
    • 2. python自实现
  • 6. 参考链接

1. Kmeans算法简介

Kmeans算是非常经典的一个聚类算法了，早已经被写到教科书里面了，不过很不幸的是，最近干活遇到了这个，然后我发现我已经忘得差不多一干二净了……

所以这里就过来挖个坟，考个古，把这玩意拉出来复习一下。

如前所述，Kmeans算法是一个聚类算法，具体来说，我们输入一个包含$N$个点的点集，我们的目的是要将这$N$个点分为$K$个簇，使得每个点到各自的簇的中心距离之和最小。

用公式来表达的话就是：

$$s=\sum _{i=1}^N\underset{j\in 1,...,K}{\min }(d(x_i,u_j))$$

要找到一组$u_j$使得$s$最大。

其中，$d(x,y)$表示$x,y$两点间的距离，一般我们在这里使用欧氏距离。

2. Kmeans算法细节

Kmeans算法的核心思路是迭代。

首先，我们随机从$N$个点当中选出$K$个点作为簇的中心点。

然后，根据全部的$N$个点到这$K$个中心点之间的距离，我们就可以将这全部的$N$个点进行分类，分配到这$K$个簇当中。

而后，我们更新这$K$个簇的中心，具体来说，我们取这$K$个点的均值点作为这$K$个簇的新的中心。

我们不断地重复上述两个步骤，直到达到迭代上限或者簇的中心点不再发生变化即可。

具体的，我们可以给出上述Kmeans算法的算法整理如下：

1. step 1: 从$N$个给定点当中随机$K$个点作为$K$个簇的中心点；
2. step 2: 计算每一个点到这$K$个簇的中心点之间的欧式距离，将其分配到最小的那个簇当中，从而对所有的点进行聚类；
3. step 3: 对于2中得到的每一个簇，更新其中心点为所有点的均值，即$\mathbf{u}=\frac{{\sum }_i{\mathbf{x}}_i}{n}$；
4. step 4: 重复上述2-3两步，直到迭代次数达到上限或者簇的中心不再发生变化。

而Kmeans的算法的优缺点因此也就比较明显：

1. 优点
   • 易实现，易debug
2. 缺点
   • 迭代非常耗时，对于大数据量尤其明显；
   • 较依赖于初始化中心的选择，不同初始化中心点的选择会带来较大的结果差异；

3. Kmeans算法收敛性证明

现在，给出了kmeans聚类算法之后，我们来考察一下kmeans算法的收敛性，也就是说，为什么kmeans算法的迭代是有效的。

我们使用原始的kmeans算法进行说明，即是说，使用欧式距离来对两点间的距离进行描述，此时，前述提到的loss函数就可以表达为：

$$s=\sum _{i=1}^N\underset{j\in 1,...,K}{\min }||x_i,u_j||$$

具体到第$k$次迭代上，即有：

$$s^k=\sum _{i=1}^N\underset{j}{\min }||x_i,u_j^k||$$

显然，$s^k$是一个大于0的数列，因此，我们只需要证明$s^k$递减，那么数列$s^k$必然收敛。

因此，我们只需要证明$s^{k+1}\le s^k$即可。

我们考察第$k$次迭代，它分为两步：

1. 对于上一次分类完成的簇，更新簇的中心从$u^k$到$u^{k+1}$；
   $$s^{{k+1}^{\prime }}=\sum _{i=1}^N||x_i,u_j^{k+1}||$$
2. 使用新的簇中心$u^{k+1}$对所有的点进行更新；
   $$s^{k+1}=\sum _{i=1}^N\underset{j}{\min }||x_i,u_j^{k+1}||$$

其中，对于步骤二，显然有$s^{k+1}\le s^{{k+1}^{\prime }}$。因此，我们只要说明步骤一当中的聚类中心变换之后获得的新的$s^{{k+1}^{\prime }}$小于等于$s^k$即可。

而在这步骤一当中，由于簇的成员都没有发生改变，因此，我们要证明的问题也就是：

• 对一系列点${\mathbf{x}}_1,...,{\mathbf{x}}_{n_i}$，$s=\sum _{j=1}^{n_i}||{\mathbf{x}}_j-\mu ||$在 μ = 1 n i ∑ j = 1 n i x j \\bold\\mu = \\frac1n_i\\sum\\limits_j=1^n_i \\boldx_j μ=n查看详情

  机器学习笔记之kmeans算法(代码片段)

  Kmeans算法：优点：容易实现缺点：可能收敛到局部最小值，在大规模数据集上的收敛速度较慢。适用数据类型：数值型数据算法原理：k-means算法接受参数k；然后将事先输入的n个数据对象划分为k个聚类... 查看详情

  机器学习sklearn19.0聚类算法——kmeans算法

  一、关于聚类及相似度、距离的知识点 二、k-means算法思想与流程三、sklearn中对于kmeans算法的参数四、代码示例以及应用的知识点简介（1）make_blobs：聚类数据生成器 sklearn.datasets.make_blobs(n_samples=100,n_features=2,centers=3,cluste... 查看详情

  机器学习笔记之kmeans算法(代码片段)

  Kmeans算法：优点：容易实现缺点：可能收敛到局部最小值，在大规模数据集上的收敛速度较慢。适用数据类型：数值型数据算法原理：k-means算法接受参数k；然后将事先输入的n个数据对象划分为k个聚类... 查看详情

  聚类-kmeans算法（图解算法原理）(代码片段)

  文章目录简介算法原理sklearn库调用K的取值简介k均值聚类算法（k-meansclusteringalgorithm）是一种迭代求解的聚类分析算法，也就是将数据分成K个簇的算法，其中K是用户指定的。比如将下图中数据分为3簇，不同颜... 查看详情

  聚类-kmeans算法（图解算法原理）(代码片段)

  文章目录简介算法原理sklearn库调用K的取值简介k均值聚类算法（k-meansclusteringalgorithm）是一种迭代求解的聚类分析算法，也就是将数据分成K个簇的算法，其中K是用户指定的。比如将下图中数据分为3簇，不同颜... 查看详情

  kmeans聚类算法

  frompyspark.ml.clusteringimportKMeans,KMeansModelfrompysparkimportSparkContextfrompyspark.sqlimportSparkSession,Rowfrompyspark.ml.linalgimportVector,Vectorssc=SparkContext(‘local‘,‘KMeans聚类算法‘)spark=S 查看详情

  机器学习-kmeans算法（图解算法原理）(代码片段)

  文章目录简介算法原理sklearn库调用K的取值前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。简介k均值聚类算法（k-meansclusteringalgorithm）是一种迭代... 查看详情

  转：机器学习sklearn19.0聚类算法——kmeans算法

  https://blog.csdn.net/loveliuzz/article/details/78783773机器学习sklearn19.0聚类算法——Kmeans算法  查看详情

  聚类算法——kmeans算法

  聚类概念　　无监督问题：我们手里没有标签　　聚类：相似的东西分到一组　　难点：如何评估，如何调参　　　　基本概念　　要得到簇的个数，需要指定K值　　质心：均值，即向量各维取平均即可　　距离的度量：常用... 查看详情

  聚类算法-kmeans算法的简单实现

  1.聚类与分类的区别：  首先要来了解的一个概念就是聚类，简单地说就是把相似的东西分到一组，同Classification(分类)不同，对于一个classifier，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，... 查看详情

  从零开始实现kmeans聚类算法

  ...;需要源代码的小伙伴可以去我的Githubfork！1.Kmeans聚类算法简介由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最著名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重... 查看详情

  机器学习--kmeans聚类算法

  1.1概述K-means算法是集简单和经典于一身的基于距离的聚类算法采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终... 查看详情

  机器学习-聚类kmeans(代码片段)

  图解K-Means算法本文中介绍的是一种常见的无监督学习算法，名字叫做K均值算法：K-Means算法。K-Means算法在无监督学习，尤其是聚类算法中是最为基础和重要的一个算法。它实现起来非常简单。聚类效果也很不错的ÿ... 查看详情

  为基于 KMeans 的聚类算法创建条形图的问题

  】为基于KMeans的聚类算法创建条形图的问题【英文标题】：ProblemwithcreatingbarplotsforKMeans-basedclusteringalgorithm【发布时间】：2021-12-0313:00:28【问题描述】：我正在努力为基于KMeans的聚类算法绘制条形图。问题是我想以这样的方式演... 查看详情

  使用二叉树结构的 KMeans 算法中的数据聚类

  】使用二叉树结构的KMeans算法中的数据聚类【英文标题】：DataclusteringinKMeansAlgorithmusingbinarytreestructure【发布时间】：2012-02-0623:02:12【问题描述】：我在为Java中的KMeans集群生成代码时遇到问题。我已经知道该算法，但是很难用java... 查看详情

  基于matlab的kmeans聚类算法的仿真与分析(代码片段)

  ...二、核心程序三、测试结果一、理论基础    K-means聚类算法是硬聚类算法，是典型的基于原型的目标函数聚类分析算法点到原型——簇中心的某种距离和作为优化的目标函数，采用函数求极值的方法得到迭代运算的调... 查看详情

  r-kmeans聚类算法

  　　　　在数据挖掘中，K-Means算法是一种clusteranalysis的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。问题K-Means算法主要解决的问题如下图所示。我们可以看到，在图的左边有一些点，我... 查看详情