使用kmean算法对颜色进行聚类

❶ kmeans聚类算法是什么

kmeans聚类算法是将样本聚类成k个簇（cluster）。

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。在实际K-Mean算法中，我们一般会多次运行图c和图d，才能达到最终的比较优的类别。

用数据表达式表示

假设簇划分为$(C_1,C_2,...C_k)$，则我们的目标是最小化平方误差E：$$ E = sumlimits_{i=1}^ksumlimits_{x in C_i} ||x-mu_i||_2^2$$。

其中$mu_i$是簇$C_i$的均值向量，有时也称为质心，表达式为：$$mu_i = frac{1}{|C_i|}sumlimits_{x in C_i}x$$。

❷ matlab里的kmeans算法使用案例不理解丘解释

[Idx,C,sumD,D]=Kmeans(data,3,’dist’,’sqEuclidean’,’rep’,4)

等号右边：

kmeans：K-均值聚类

data是你自己的输入数据

3 是你要聚成3类

dist sqEuclidean 这2个参数，表示距离函数为欧式距离。什么是欧式距离自己网络

’rep’,4聚类重复次数4次。因为要反复算直到选出最好的结果，至多反复算4次

等号左边：

Idx 是你聚类的标号

C 是聚类之后质心的位置

sumD是所有点到质心的距离之和

D是每个点与所有质心的距离

比如下面这幅图中，输入数据data就是所有的小点，K-均值聚类输出的结果就是所有的数据被聚为了3类，聚类的标号就是红绿蓝三种颜色，每一类有一个自己的质心（大的点）。

❸ Kmeans聚类算法简介

由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最着名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重心(centroids)，移动到其包含成员的平均位置，然后重新划分其内部成员。k是算法计算出的超参数，表示类的数量；Kmeans可以自动分配样本到不同的类，但是不能决定究竟要分几个类。k必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我将会详细介绍一些方法来估计最优聚类数量。

Kmeans的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，Kmeans参数的最优解也是以成本函数最小化为目标。Kmeans成本函数公式如下：

μiμi是第kk个类的重心位置。成本函数是各个类畸变程度(distortions)之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，Kmeans会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。

2.1 根据问题内容确定

这种方法就不多讲了，文章开篇就举了一个例子。

2.2 肘部法则

如果问题中没有指定kk的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同kk值的成本函数值画出来。随着kk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着kk值继续增大，平均畸变程度的改善效果会不断减低。kk值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kk值就是肘部。为了让读者看的更加明白，下面让我们通过一张图用肘部法则来确定最佳的kk值。下图数据明显可分成两类：

从图中可以看出，k值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显着降低。因此最佳的k是2。

2.3 与层次聚类结合

经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。

2.4 稳定性方法

稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有kk个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明kk个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个kk，找到合适的k值。

2.5 系统演化方法

系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为kk个聚类时称系统处于状态kk。系统由初始状态k=1k=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 kiki ，其所对应的聚类结构决定了最优类数 kiki 。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。

2.6 使用canopy算法进行初始划分

基于Canopy Method的聚类算法将聚类过程分为两个阶段

(1) 聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；

(2) 在各个Canopy内使用传统的聚类方法(如Kmeans)，不属于同一Canopy的对象之间不进行相似性计算。

从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于Kmeans这样的聚类方法是需要人为指出K的值的，通过(1)得到的Canopy个数完全可以作为这个k值，一定程度上减少了选择k的盲目性。

其他方法如贝叶斯信息准则方法(BIC)可参看文献[4]。

选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始中心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE(误差的平方和)的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。

第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取kk个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：(1)样本相对较小，例如数百到数千(层次聚类开销较大)；(2) kk相对于样本大小较小。

第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少(多了就不是离群点了)，它们多半不会在随机样本中出现。计算量也大幅减少。

第四种方法就是上面提到的canopy算法。

常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

因为欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？

从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。

我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数(Silhouette Coefficient)。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：

aa是每一个类中样本彼此距离的均值，bb是一个类中样本与其最近的那个类的所有样本的距离的均值。

输入：聚类个数k，数据集XmxnXmxn。

输出：满足方差最小标准的k个聚类。

(1) 选择k个初始中心点，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 对于X[0]….X[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；

(3) 对于所有标记为i点，重新计算c[i]={ 所有标记为i的样本的每个特征的均值}；

(4) 重复(2)(3)，直到所有c[i]值的变化小于给定阈值或者达到最大迭代次数。

Kmeans的时间复杂度：O(tkmn)，空间复杂度：O((m+k)n)。其中，t为迭代次数，k为簇的数目，m为样本数，n为特征数。

7.1 优点

(1). 算法原理简单。需要调节的超参数就是一个k。

(2). 由具有出色的速度和良好的可扩展性。

7.2 缺点

(1). 在 Kmeans 算法中 kk 需要事先确定，这个 kk 值的选定有时候是比较难确定。

(2). 在 Kmeans 算法中，首先需要初始k个聚类中心，然后以此来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。

(3). 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。

(4). 对离群点很敏感。

(5). 从数据表示角度来说，在 Kmeans 中,我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster的数据是呈圆形(或者高维球形)或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在 GMM 中，使用了一种更加一般的数据表示，也就是高斯分布。

(6). 从数据先验的角度来说，在 Kmeans 中,我们假设各个 cluster 的先验概率是一样的,但是各个 cluster 的数据量可能是不均匀的。举个例子,cluster A 中包含了10000个样本,cluster B 中只包含了100个。那么对于一个新的样本,在不考虑其与A cluster、 B cluster 相似度的情况,其属于 cluster A 的概率肯定是要大于 cluster B的。

(7). 在 Kmeans 中，通常采用欧氏距离来衡量样本与各个 cluster 的相似度。这种距离实际上假设了数据的各个维度对于相似度的衡量作用是一样的。但在 GMM 中，相似度的衡量使用的是后验概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通过引入协方差矩阵,我们就可以对各维度数据的不同重要性进行建模。

(8). 在 Kmeans 中，各个样本点只属于与其相似度最高的那个 cluster ，这实际上是一种 hard clustering 。

针对Kmeans算法的缺点，很多前辈提出了一些改进的算法。例如 K-modes 算法，实现对离散数据的快速聚类，保留了Kmeans算法的效率同时将Kmeans的应用范围扩大到离散数据。还有K-Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。当然还有其它的一些算法，这里我 就不一一列举了。

Kmeans 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后,再来进行数据的聚类。而 hierarchical clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。

❹ kmeans聚类算法优缺点

优缺点如下：

1、优点

k-平均算法是解决聚类问题的一种经典算法，算法简单、快速。

对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt) O(nkt)O(nkt)，其中n是所有对象的数目，k是簇的数目，t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。

算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。

2、缺点

对K值敏感。也就是说，K的选择会较大程度上影响分类效果。在聚类之前，我们需要预先设定K的大小，但是我们很难确定分成几类是最佳的，比如上面的数据集中，显然分为2类，即K = 2最好，但是当数据量很大时，我们预先无法判断。

对离群点和噪声点敏感。如果在上述数据集中添加一个噪音点，这个噪音点独立成一个类。很显然，如果K=2,其余点是一类，噪音点自成一类，原本可以区分出来的点被噪音点影响，成为了一类了。如果K=3，噪音点也是自成一类，剩下的数据分成两类。这说明噪音点会极大的影响其他点的分类。

聚类分析特点

聚类分析的实质：是建立一种分类方法，它能够将一批样本数据按照他们在性质上的亲密程度在没有先验知识的情况下自动进行分类。这里所说的类就是一个具有相似性的个体的集合，不同类之间具有明显的区别。

层次聚类分析是根据观察值或变量之间的亲疏程度，将最相似的对象结合在 一起，以逐次聚合的方式（Agglomerative Clustering），它将观察值分类，直到最后所有样本都聚成一类。

层次聚类分析有两种形式，一种是对样本（个案）进行分类，称为Q型聚类；另一种是对研究对象的观察变量进行分类，称为R型聚类。

❺ K-means原理、优化、应用

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

    K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

1、随机选择K个聚类的初始中心。

2、对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类。

3、每次迭代过程中，利用均值等方法更新各个聚类的中心点（质心）。

4、对K个聚类中心，利用2、3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束。（画图时，可以对不同的聚类块和聚类中心可选择不同的颜色标注）

1、原理比较简单，实现也是很容易，收敛速度快。 

2、聚类效果较优。 

3、算法的可解释度比较强。 

4、主要需要调参的参数仅仅是簇数k。

1、K值的选取不好把握 

2、对于不是凸的数据集比较难收敛 

3、如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。 

4、 最终结果和初始点的选择有关，容易陷入局部最优。

5、对噪音和异常点比较的敏感。

    解决K-Means算法对 初始簇心 比较敏感的问题，二分K-Means算法是一种弱化初始质心的一种算法。

1、将所有样本数据作为一个簇放到一个队列中。

2、从队列中选择一个簇进行K-Means算法划分，划分为两个子簇，并将子簇添加到队列中。

3、循环迭代步骤2操作，直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)。

4、队列中的簇就是最终的分类簇集合。

从队列中选择划分聚簇的规则一般有两种方式；分别如下：

1、对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种)，选择SSE最大的聚簇进行划分操作(优选这种策略)。

2、选择样本数据量最多的簇进行划分操作：

    由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此有提出这种算法的改进: K-means++ 。

    其实这个算法也只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是， 初始的聚类中心之间的相互距离要尽可能的远 。

1、随机选取一个样本作为第一个聚类中心 c1；

2、计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离），用 D(x)表示；这个值越大，表示被选取作为聚类中心的概率较大；最后，用轮盘法选出下一个聚类中心。

3、重复步骤2，知道选出 k 个聚类中心。

4、选出初始点（聚类中心），就继续使用标准的 k-means 算法了。

尽管K-Means++在聚类中心的计算上浪费了很多时间，但是在迭代过程中，k-mean 本身能快速收敛，因此算法实际上降低了计算时间。

      解决K-Means++算法缺点而产生的一种算法；主要思路是改变每次遍历时候的取样规则，并非按照K-Means++算法每次遍历只获取一个样本，而是每次获取K个样本，重复该取样操作O(logn)次 (n是样本的个数) ，然后再将这些抽样出来的样本聚类出K个点，最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明：一般5次重复采用就可以保证一个比较好的聚簇中心点。

1、在N个样本中抽K个样本，一共抽logn次，形成一个新的样本集，一共有Klogn个数据。

2、在新数据集中使用K-Means算法，找到K个聚簇中心。

3、把这K个聚簇中心放到最初的样本集中，作为初始聚簇中心。

4、原数据集根据上述初始聚簇中心，再用K-Means算法计算出最终的聚簇。

        Canopy属于一种‘粗’聚类算法，即使用一种简单、快捷的距离计算方法将数据集分为若干可重叠的子集canopy，这种算法不需要指定k值、但精度较低，可以结合K-means算法一起使用：先由Canopy算法进行粗聚类得到k个质心，再使用K-means算法进行聚类。

 1、将原始样本集随机排列成样本列表L=[x1,x2,...,xm]（排列好后不再更改），根据先验知识或交叉验证调参设定初始距离阈值T1、T2，且T1>T2 。

2、从列表L中随机选取一个样本P作为第一个canopy的质心，并将P从列表中删除。

3、从列表L中随机选取一个样本Q，计算Q到所有质心的距离，考察其中最小的距离D：

如果D≤T1，则给Q一个弱标记，表示Q属于该canopy，并将Q加入其中；

如果D≤T2，则给Q一个强标记，表示Q属于该canopy，且和质心非常接近，所以将该canopy的质心设为所有强标记样本的中心位置，并将Q从列表L中删除；

 如果D>T1，则Q形成一个新的聚簇，并将Q从列表L中删除。

4、重复第三步直到列表L中元素个数为零。

1、‘粗’距离计算的选择对canopy的分布非常重要，如选择其中某个属性、其他外部属性、欧式距离等。

2、当T2<D≤T1时，样本不会从列表中被删除，而是继续参与下一轮迭代，直到成为新的质心或者某个canopy的强标记成员。

3、T1、T2的取值影响canopy的重叠率及粒度：当T1过大时，会使样本属于多个canopy，各个canopy间区别不明显；当T2过大时，会减少canopy个数，而当T2过小时，会增加canopy个数，同时增加计算时间。

4、canopy之间可能存在重叠的情况，但是不会存在某个样本不属于任何canopy的情况。

5、Canopy算法可以消除孤立点，即删除包含样本数目较少的canopy，往往这些canopy包含的是孤立点或噪音点。

    由于K-Means算法存在初始聚簇中心点敏感的问题，常用使用Canopy+K-Means算法混合形式进行模型构建。

1、先使用canopy算法进行“粗”聚类得到K个聚类中心点。

2、K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点，进行“细”聚类。

1、执行速度快(先进行了一次聚簇中心点选择的预处理)；

2、不需要给定K值，应用场景多。

3、能够缓解K-Means算法对于初始聚类中心点敏感的问题。

    Mini Batch K-Means算法是K-Means算法的一种优化变种，采用 小规模的数据子集 (每次训练使用的数据集是在训练算法的时候随机抽取的数据子集) 减少计算时间 ，同时试图优化目标函数；Mini Batch K-Means算法可以减少K-Means算法的收敛时间，而且产生的结果效果只是略差于标准K-Means算法。

1、首先抽取部分数据集，使用K-Means算法构建出K个聚簇点的模型。

2、继续抽取训练数据集中的部分数据集样本数据，并将其添加到模型中，分配给距离最近的聚簇中心点。

3、更新聚簇的中心点值。

4、循环迭代第二步和第三步操作，直到中心点稳定或者达到迭代次数，停止计算操作。

https://www.jianshu.com/p/f0727880c9c0

❻ 聚类算法--KMeans

    与分类、序列标注等任务不同，聚类是在事先并不知道任何样本标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低(即增大类内聚，减少类间距)。    

    聚类属于非监督学习，K均值聚类是最基础常用的聚类算法。它的基本思想是，通过迭代寻找K个簇(Cluster)的一种划分方案，使得聚类结果对应的损失函数最小。其中，损失函数可以定义为各个样本距离所属簇中心点的误差平方和。

其中 代表第i个样本， 是 所属的簇，  代表簇对应的中心点，M是样本总数。

相关概念：

    K值： 要得到的簇的个数。

    质心： 每个簇的均值向量。即向量各维取平均即可。

    距离量度： 常用欧几里得距离和余弦相似度(先标准化)。

    KMeans的主要思想是：在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。

    KMeans的核心目标是将给定的数据集划分成K个簇(K是超餐)，并给出每个样本数据对应的中心点。具体步骤非常简单：

    （1）首先确定一个K值，即我们希望将数据集经过聚类得到k个集合。

    （2）从数据集中随机选择K个数据点作为质心。

    （3）对数据集中每一个点，计算其与每一个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合。

    （4）把所有数据归好集合后，一共有K个集合。然后重新计算每个集合的质心。

    （5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。

    （6）如果新质心和原质心距离变化很大，需要迭代3-5步骤。

KMeans最核心的部分是先固定中心点，调整每个样本所属的类别来减少J；再固定每个样本的类别，调整中心点继续减小J。两个过程交替循环，J单调递减直到极小值，中心点和样本划分的类别同时收敛。

KMeans的优点 ：

 高效可伸缩，计算复杂度为O(NKt)接近于线性(N是数据量，K是聚类总数，t是迭代轮数)。

 收敛速度快，原理相对通俗易懂，可解释性强。

当结果簇是密集的，而簇与簇之间区别是明显时，他的效果较好。主要需要调参的参数仅仅是簇数K。

缺点 ：

 受初始值和异常点影响，聚类结果可能不是全局最优而是局部最优。K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同，对结果影响很大。

 K是超参数，一般需要按经验选择。

 对噪音和异常点比较的敏感，用来检测异常值。

 只能发现球状的簇。在K-Means中，我们用单个点对cluster进行建模，这实际上假设各个cluster的数据是呈高维球型分布的，但是在生活中出现这种情况的概率并不算高。例如，每一个cluster是一个一个的长条状的，K-Means的则根本识别不出来这种类别( 这种情况可以用GMM )。实际上，K-Means是在做凸优化，因此处理不了非凸的分布。

根据以上特点，我们可以从下面几个角度对算法做调优。

（1）数据预处理：归一化和异常点过滤

    KMeans本质是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响 。所以在聚类前对数据( 具体的说是每一个维度的特征 )做归一化和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致 中心偏移 ，这些噪声点最好能提前过滤。

（2）合理选择K值

    K值的选择一般基于实验和多次实验结果。例如采用 手肘法 ，尝试不同K值并将对应的损失函数画成折线。手肘法认为图上的 拐点就是K的最佳值 (k=3)。

为了将寻找最佳K值的过程自动化，研究人员提出了Gap Statistic方法。不需要人们用肉眼判断，只需要找到最大的Gap Statistic对应的K即可。

       损失函数记为  ，当分为K类时，Gap Statistic定义为：  。 是 的期望 ，一般由蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做KMeans，得到一个 ，重复多次就可以计算出 的近似值。

       的物理含义是随机样本的损失与实际样本的损失之差。Gap越大说明聚类的效果越好 。一种极端情况是，随着K的变化 几乎维持一条直线保持不变。说明这些样本间没有明显的类别关系，数据分布几乎和均匀分布一致，近似随机。此时做聚类没有意义。

（3）改进初始值的选择

    之前我们采用随机选择K个中心的做法，可能导致不同的中心点距离很近，就需要更多的迭代次数才能收敛。如果在选择初始中心点时能 让不同的中心尽可能远离 ，效果往往更好。这类算法中，以K-Means++算法最具影响力。

（4）采用核函数

    主要思想是通过一个非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的空间进行聚类。非线性映射增加了数据点线性可分的概率(与SVM中使用核函数思想类似)对于非凸的数据分布可以达到更为准确的聚类结果。

 (1）初始的K个质心怎么选？

    最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更合理，就用哪个结果。当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果，从结果中每个分类选一个点

（2）关于离群值？

    离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些"极大""极小"之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离散值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。

（3）单位要一致！

（4）标准化

    数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里得距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化(normalization)，即将数据按比例缩放，使之落入一个小的特定区间。

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