用kmeans算法聚类

① 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、例子、细节

② kmeans聚类算法是什么

K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集。

(2)用kmeans算法聚类扩展阅读：

k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

（1）适当选择c个类的初始中心；

（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；

（3）利用均值等方法更新该类的中心值；

（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。

③ 聚类算法的具体方法

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：
首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；
然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。
改进的算法：k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值，在 K-medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。
步骤：
1，任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。
以下是循环的：
2，将余下的对象分到各个类中去（根据与medoid最相近的原则）；
3，对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。
4，这样循环直到K个medoids固定下来。
这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。 上面提到K-medoids算法不适合于大数据量的计算。Clara算法，这是一种基于采样的方法，它能够处理大量的数据。
Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1, O2 … Oi … Ok），然后在这当中选取E最小的一个作为最终的结果。 Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。
在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。
与上面所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。