K-Means聚类算法原理是怎么样的？

1. K-Means聚类算法原理是怎么样的？

一，K-Means聚类算法原理
        k-means 算法接受参数 k 
；然后将事先输入的n个数据对象划分为 
k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对
象”（引力中心）来进行计算的。
　　K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
　　假设要把样本集分为c个类别，算法描述如下：
　　（1）适当选择c个类的初始中心；
　　（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
　　（3）利用均值等方法更新该类的中心值；
　　（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
　　该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

2. 关于k-means算法的聚类分析

3. K-Means聚类算法

        所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图所示：
                                          
         根据样本之间的距离或者说是相似性（亲疏性），把越相似、差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
  
  相关概念： 
  
  K值 ：要得到的簇的个数
  
  质心 ：每个簇的均值向量，即向量各维取平均即可
  
  距离量度 ：常用欧几里得距离和余弦相似度（先标准化）
                                          
  算法流程： 
  
 1、首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。
  
 2、从数据集中随机选择k个数据点作为质心。
  
 3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。
  
 4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。
  
 5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。
  
 6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。
                                          
 K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述:
                                          
         上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。
  
 坐标系中有六个点：
                                          
 1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
  
 2、通过勾股定理计算剩余点分别到这两个点的距离：
                                          
 3、第一次分组后结果：
  
         组A：P1
  
         组B：P2、P3、P4、P5、P6
  
 4、分别计算A组和B组的质心：
  
         A组质心还是P1=（0，0）
  
         B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
  
 5、再次计算每个点到质心的距离：
                                          
 6、第二次分组结果：
  
         组A：P1、P2、P3
  
         组B：P4、P5、P6
  
 7、再次计算质心：
  
         P哥1=（1.33，1） 
  
         P哥2=（9，8.33）
  
 8、再次计算每个点到质心的距离：
                                          
 9、第三次分组结果：
  
         组A：P1、P2、P3
  
         组B：P4、P5、P6
  
 可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
  
  优点： 
  
 1、原理比较简单，实现也是很容易，收敛速度快。
  
 2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
  
 3、主要需要调参的参数仅仅是簇数k。
  
  缺点： 
  
 1、K值需要预先给定，很多情况下K值的估计是非常困难的。
  
 2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
  
 3、对噪音和异常点比较的敏感。用来检测异常值。
  
 4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
  
  1、K值怎么定？ 
  
         答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
  
  2、初始的K个质心怎么选？ 
  
         答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。       当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
  
  3、关于离群值？ 
  
         答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
  
 4、单位要一致！
  
         答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
  
 5、标准化
  
         答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。
  
 
  
  
 
  
  
 参考文章： 聚类、K-Means、例子、细节

4. K-Means 聚类算法

问题导入
  
     假如有这样一种情况，在一天你想去某个城市旅游，这个城市里你想去的有70个地方，现在你只有每一个地方的地址，这个地址列表很长，有70个位置。事先肯定要做好攻略，你要把一些比较接近的地方放在一起组成一组，这样就可以安排交通工具抵达这些组的“某个地址”，然后步行到每个组内的地址。那么，如何确定这些组，如何确定这些组的“某个地址”？答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。
  
 一，聚类思想
  
         所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图：
                                          
         根据样本之间的距离或者说相似性，把越相似，差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
  
 二，K-Means聚类分析算法
  
         K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。
  
 相关概念：
  
         K值：要得到的簇的个数
  
         质心：每个簇的均值向量，即向量各维取品军即可
  
         距离度量：常用欧几里得距离和余弦相似度(先标准化)
  
         两点之间的距离：
                                          
 算法流程：
  
         1    首先确定一个K值，即我们希望将数据集经过聚类得到 K个集合；
  
         2    从数据集中随机选择K个数据点作为质心；
  
         3    对数据集中每一个点，计算其与每个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合
  
         4    把所有数据归好集合，一共有K个集合，然后重新计算每个集合的质心；
  
         5    如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。
  
         6    如果新质心和原质心距离变化大，需要迭代3-5步骤
  
 K-means实现过程
  
 K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。
  
  算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
  
  1.数据分配： 
  
 每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
                                          
 其中 dist（·）是标准（L2）欧氏距离。让指向第 i 个集群质心的数据点集合定为 Si 。
  
  2. 质心更新： 
  
 在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
                                          
 K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
  
 K 值的选择
  
 上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
  
  Elbow point 拐点方法 
  
 通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
                                          
  DBI（Davies-Bouldin Index） 
  
 DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
  
 还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
  
 
  
  
 三，数学原理
                                          
 K-Means采用的启发式很简单，可以用下面一组图来形象的描述：
                                          
 上述a表达了初始的数据集，假设 k=2 。在图b中，我们随机选择了两个 k 类所对应的类别质点，即图中的红色质点和蓝色质点，然后分别求样本中所有点到这两个质心的距离，并标记每个样本类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心大热位置已经发生了变化。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求出新的质心。最终我们得到的两个类别如图f.
  
 四，实例
  
 坐标系中有六个点：
                                          
 1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
  
 2、通过勾股定理计算剩余点分别到这两个点的距离：
                                          
 3、第一次分组后结果：
  
         组A：P1
  
         组B：P2、P3、P4、P5、P6
  
 4、分别计算A组和B组的质心：
  
         A组质心还是P1=（0，0）
  
         B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
  
 5、再次计算每个点到质心的距离：
                                          
 6、第二次分组结果：
  
         组A：P1、P2、P3
  
         组B：P4、P5、P6
  
 7、再次计算质心：
  
         P哥1=（1.33，1） 
  
         P哥2=（9，8.33）
  
 8、再次计算每个点到质心的距离：
                                          
 9、第三次分组结果：
  
         组A：P1、P2、P3
  
         组B：P4、P5、P6
  
 可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
  
 五、K-Means的优缺点
  
  优点： 
  
 1、原理比较简单，实现也是很容易，收敛速度快。
  
 2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
  
 3、主要需要调参的参数仅仅是簇数k。
  
  缺点： 
  
 1、K值需要预先给定，很多情况下K值的估计是非常困难的。
  
 2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
  
 3、对噪音和异常点比较的敏感。用来检测异常值。
  
 4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
  
  六、细节问题 
  
  1、K值怎么定？ 
  
 答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
  
  2、初始的K个质心怎么选？ 
  
         答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。       当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
  
  3、关于离群值？ 
  
         答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
  
 4、单位要一致！
  
         答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
  
 5、标准化
  
         答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。

5. k mean聚类算法可以干什么

一，K-Means聚类算法原理
k-means 算法接受参数 k 
；然后将事先输入的n个数据对象划分为 
k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对
象”（引力中心）来进行计算的。
K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
假设要把样本集分为c个类别，算法描述如下：
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

6. k-means算法是聚类算法还是分类算法

一,k-means聚类算法原理
k-means
算法接受参数
k
；然后将事先输入的n个数据对象划分为
k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小.聚类相似度是利用各聚类中对象的均值所获得一个“中心对
象”（引力中心）来进行计算的.
　　k-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一.k-means算法的基本思想是：以空间中k个点为中心进行聚类,对最靠近他们的对象归类.通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果.
　　假设要把样本集分为c个类别,算法描述如下：
　　（1）适当选择c个类的初始中心；
　　（2）在第k次迭代中,对任意一个样本,求其到c个中心的距离,将该样本归到距离最短的中心所在的类；
　　（3）利用均值等方法更新该类的中心值；
　　（4）对于所有的c个聚类中心,如果利用（2）（3）的迭代法更新后,值保持不变,则迭代结束,否则继续迭代.
　　该算法的最大优势在于简洁和快速.算法的关键在于初始中心的选择和距离公式.

7. K-Means 聚类原理

K-Means 是聚类算法中的最常用的一种，算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。
  
 假设有一些点分散在直线上，现在需要对这些点进行聚类分析。
                                          
 第一步，想一下我们希望最终将这些点聚为多少类？
  
 假设我们希望聚为3类
  
 第二步，在这些点中随机选择3个点，作为初始簇(initial cluster)
                                          
 第三步，计算第一个点f分别到这3个initial cluster的距离
                                          
 第四步，将第一个点归属为距离最近的那个cluster
                                          
 重复第三/四步
                                          
 一一判断所有点的归属
                                          
 第五步，计算每一个cluster的均值
                                          
 然后像之前一样，通过计算每个点到这些均值的距离，重新判断每个点归属于哪个cluster
                                          
 判断完每个点的归属之后，重新计算均值……判断归属……计算均值……判断归属……直到聚出来的cluster不再变化
                                          
 很明显，上面的聚类效果很差，还不如我们肉眼聚类出来的效果。是否有办法判断不同聚类结果的好坏呢？
                                          
 第一步，计算每一个cluster的总变差(total variation)
                                          
 第二步，重新选择3个initial cluster，并且多次迭代判断cluster，计算total variation
                                          
 第三步，多次重复上一步的内容，选择total variation最小的聚类结果
                                          
 在本文的案例中，我们通过肉眼可以判断出K选择3比较好。但是如果我们自己无法判断时，如何处理？
  
 一种方法是直接尝试不同的K值进行聚类
  
 K=1是最差的一种结果，total variation此时最大
                                          
 K=2的效果会稍微好些
                                          
 随着K值增大，total variation也逐渐减小；当K=N(样本数)时，total variation降至0。
  
 绘制total variation随K值变化的elbow plot
                                          
 可以看出，K>3时，variation的降低速率明显降低。所以K=3是较好的选择。
  
 二维平面上的点，可以通过欧式距离来判断聚类
                                          
 然后同之前一般，计算平面上同一cluster的中心，重新判断点的归属，寻找中心……判断归属……
                                          
 对于热图相关数据，也可以通过欧式距离来判断样本的聚类
                                          
  https://blog.csdn.net/huangfei711/article/details/78480078 
  
  https://www.biaodianfu.com/k-means-choose-k.html 
  
  https://www.youtube.com/watch?v=4b5d3muPQmA&feature=youtu.be

8. 哪些因素影响k-means算法聚类性能

K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
k个初始类聚类中心点的选取对聚类结果具有较大的
公式
影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。
算法过程如下：
1）从N个文档随机选取K个文档作为质心
2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类
3）重新计算已经得到的各个类的质心
4）迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束
具体如下：
输入：k, data[n];
（1） 选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1]；
（2） 对于data[0]….data[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；
（3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数；
（4） 重复(2)(3)，直到所有c[i]值的变化小于给定阈值。
工作原理
K-MEANS算法的工作原理及流程
K-MEANS算法

输入：聚类个数k，以及包含 n个数据对象的数据库。
输出：满足方差最小标准的k个聚类。
处理流程
（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；
（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（3） 重新计算每个（有变化）聚类的均值（中心对象）
（4） 循环（2）到（3）直到每个聚类不再发生变化为止
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
工作过程k-means 算法的工作过程
说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。