kmeans算法要实现什么

⑴ 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$$。

⑵ Kmeans聚类算法简介（有点枯燥）

1. Kmeans聚类算法简介

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

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

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

2. K值的确定

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]。

3. 初始质心的选取

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

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

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

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

4. 距离的度量

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

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

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

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

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

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

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

5. 聚类效果评估

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

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

6. Kmeans算法流程

输入：聚类个数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. Kmeans算法优缺点

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算法原理

Kmeans是一种无监督的基于距离的聚类算法，其变种还有Kmeans++。

注意，某些聚类中心可能没有被分配到样本，这样的聚类中心就会被淘汰（意味着最终的类数可能会减少）

和其他机器学习算法一样，K-Means 也要评估并且最小化聚类代价，在引入 K-Means 的代价函数之前，先引入如下定义：

引入代价函数：

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

数据呈圆形、凸型、在一起的簇的数据形状近似高斯分布的这些数据是kmeans喜欢的数据。

⑷ k-means聚类算法的实现和可视化

k-means是一个非监督算法，以前我们学的都是监督算法或者半监督算法，例如多元回归，贝叶斯判别，支持向量机，随机森林算法等。而这种距离算法则是非监督算法。

PS：常见的聚类方法有：系统聚类法，k均值聚类法
系统聚类法是计算所有数据之间的距离，根据不同的分类数，迭代，直到全部不能分为止，意思是你想要多少类都能分给你。

聚类算法根据数据之间的相似性或者距离将数据分为几个簇，簇与簇之间不同。

在这个算法中，我们需要提前指定数据可能分成的堆数，每个数据对象在不同的堆里都不同。

两个距离：（距离体现了他们之间的差异性）
个体与个体之间的距离
类与类之间的距离
距离的计算种类：马氏距离，欧氏距离，明氏距离等

每一个簇都有聚类中心，根据数据到聚类中心的距离，把它归为哪一类。

工具：python3.6 sklearn iris

结果不太理想，因为我用的是鸢尾花的数据，该数据适合用来做判别分析。
sklearn里还有很多好用的功能，这倒是一个新发现。

⑸ k means算法如何具体实现呢

1.基本Kmeans算法[1]

[cpp] view plain
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数

时间复杂度：O(tKmn)，其中，t为迭代次数，K为簇的数目，m为记录数，n为维数

空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数

⑹ kmeans算法是什么

K-means算法是一种基于距离的聚类算法，也叫做K均值或K平均，也经常被称为劳埃德(Lloyd)算法。是通过迭代的方式将数据集中的各个点划分到距离它最近的簇内，距离指的是数据点到簇中心的距离。

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

算法流程

1、选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心。

2、对于样本中的数据对象，根据它们与这些聚类中心的欧氏距离，按距离最近的准则将它们分到距离它们最近的聚类中心（最相似）所对应的类。

3、更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值。

4、判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2）。

⑺ 聚类算法之K均值算法(k-means)的Python实现

K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

通常，人们根据样本间的某种距离或者相似性来定义聚类，即把相似的（或距离近的）样本聚为同一类，而把不相似的（或距离远的）样本归在其他类。

所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。

k-means算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

看起来还不错

分析一个公司的客户分类，这样可以对不同的客户使用不同的商业策略，或是电子商务中分析商品相似度，归类商品，从而可以使用一些不同的销售策略，等等。

⑻ kmeans聚类算法是什么

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

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

(8)kmeans算法要实现什么扩展阅读：

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

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

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

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

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

⑼ kmeans算法用Python怎么实现

1、从Kmeans说起

Kmeans是一个非常基础的聚类算法，使用了迭代的思想，关于其原理这里不说了。下面说一下如何在matlab中使用kmeans算法。

创建7个二维的数据点：

复制代码 代码如下:
x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];

使用kmeans函数：

复制代码 代码如下:
class = kmeans(x, 2);

x是数据点，x的每一行代表一个数据；2指定要有2个中心点，也就是聚类结果要有2个簇。 class将是一个具有70个元素的列向量，这些元素依次对应70个数据点，元素值代表着其对应的数据点所处的分类号。某次运行后，class的值是：

复制代码 代码如下:

2
2
2
1
1
1
1

这说明x的前三个数据点属于簇2，而后四个数据点属于簇1。 kmeans函数也可以像下面这样使用：

复制代码 代码如下:

>> [class, C, sumd, D] = kmeans(x, 2)
class =
2
2
2
1
1
1
1

C =
4.0629 4.0845
-0.1341 0.1201

sumd =
1.2017
0.2939

D =
34.3727 0.0184
29.5644 0.1858
36.3511 0.0898
0.1247 37.4801
0.7537 24.0659
0.1979 36.7666
0.1256 36.2149

class依旧代表着每个数据点的分类;C包含最终的中心点，一行代表一个中心点；sumd代表着每个中心点与所属簇内各个数据点的距离之和；D的
每一行也对应一个数据点，行中的数值依次是该数据点与各个中心点之间的距离，Kmeans默认使用的距离是欧几里得距离（参考资料[3]）的平方值。
kmeans函数使用的距离，也可以是曼哈顿距离（L1-距离），以及其他类型的距离，可以通过添加参数指定。

kmeans有几个缺点（这在很多资料上都有说明）：

1、最终簇的类别数目（即中心点或者说种子点的数目）k并不一定能事先知道，所以如何选一个合适的k的值是一个问题。
2、最开始的种子点的选择的好坏会影响到聚类结果。
3、对噪声和离群点敏感。
4、等等。

2、kmeans++算法的基本思路

kmeans++算法的主要工作体现在种子点的选择上，基本原则是使得各个种子点之间的距离尽可能的大，但是又得排除噪声的影响。 以下为基本思路：

1、从输入的数据点集合（要求有k个聚类）中随机选择一个点作为第一个聚类中心
2、对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3、选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
4、重复2和3直到k个聚类中心被选出来
5、利用这k个初始的聚类中心来运行标准的k-means算法

假定数据点集合X有n个数据点，依次用X(1)、X(2)、……、X(n)表示，那么，在第2步中依次计算每个数据点与最近的种子点（聚类中心）的
距离，依次得到D(1)、D(2)、……、D(n)构成的集合D。在D中，为了避免噪声，不能直接选取值最大的元素，应该选择值较大的元素，然后将其对应
的数据点作为种子点。

如何选择值较大的元素呢，下面是一种思路（暂未找到最初的来源，在资料[2]等地方均有提及，笔者换了一种让自己更好理解的说法）：
把集合D中的每个元素D(x)想象为一根线L(x)，线的长度就是元素的值。将这些线依次按照L(1)、L(2)、……、L(n)的顺序连接起来，组成长
线L。L(1)、L(2)、……、L(n)称为L的子线。根据概率的相关知识，如果我们在L上随机选择一个点，那么这个点所在的子线很有可能是比较长的子
线，而这个子线对应的数据点就可以作为种子点。下文中kmeans++的两种实现均是这个原理。

3、python版本的kmeans++

在http://rosettacode.org/wiki/K-means%2B%2B_clustering 中能找到多种编程语言版本的Kmeans++实现。下面的内容是基于python的实现（中文注释是笔者添加的）：

复制代码 代码如下:

from math import pi, sin, cos
from collections import namedtuple
from random import random, choice
from import
try:
import psyco
psyco.full()
except ImportError:
pass

FLOAT_MAX = 1e100

class Point:
__slots__ = ["x", "y", "group"]
def __init__(self, x=0.0, y=0.0, group=0):
self.x, self.y, self.group = x, y, group

def generate_points(npoints, radius):
points = [Point() for _ in xrange(npoints)]

# note: this is not a uniform 2-d distribution
for p in points:
r = random() * radius
ang = random() * 2 * pi
p.x = r * cos(ang)
p.y = r * sin(ang)

return points

def nearest_cluster_center(point, cluster_centers):
"""Distance and index of the closest cluster center"""
def sqr_distance_2D(a, b):
return (a.x - b.x) ** 2 + (a.y - b.y) ** 2

min_index = point.group
min_dist = FLOAT_MAX

for i, cc in enumerate(cluster_centers):
d = sqr_distance_2D(cc, point)
if min_dist > d:
min_dist = d
min_index = i

return (min_index, min_dist)

'''
points是数据点，nclusters是给定的簇类数目
cluster_centers包含初始化的nclusters个中心点，开始都是对象->(0,0,0)
'''

def kpp(points, cluster_centers):
cluster_centers[0] = (choice(points)) #随机选取第一个中心点
d = [0.0 for _ in xrange(len(points))] #列表，长度为len(points)，保存每个点离最近的中心点的距离

for i in xrange(1, len(cluster_centers)): # i=1...len(c_c)-1
sum = 0
for j, p in enumerate(points):
d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j个数据点p与各个中心点距离的最小值
sum += d[j]

sum *= random()

for j, di in enumerate(d):
sum -= di
if sum > 0:
continue
cluster_centers[i] = (points[j])
break

for p in points:
p.group = nearest_cluster_center(p, cluster_centers)[0]

'''
points是数据点，nclusters是给定的簇类数目
'''
def lloyd(points, nclusters):
cluster_centers = [Point() for _ in xrange(nclusters)] #根据指定的中心点个数，初始化中心点，均为(0,0,0)

# call k++ init
kpp(points, cluster_centers) #选择初始种子点

# 下面是kmeans
lenpts10 = len(points) >> 10

changed = 0
while True:
# group element for centroids are used as counters
for cc in cluster_centers:
cc.x = 0
cc.y = 0
cc.group = 0

for p in points:
cluster_centers[p.group].group += 1 #与该种子点在同一簇的数据点的个数
cluster_centers[p.group].x += p.x
cluster_centers[p.group].y += p.y

for cc in cluster_centers: #生成新的中心点
cc.x /= cc.group
cc.y /= cc.group

# find closest centroid of each PointPtr
changed = 0 #记录所属簇发生变化的数据点的个数
for p in points:
min_i = nearest_cluster_center(p, cluster_centers)[0]
if min_i != p.group:
changed += 1
p.group = min_i

# stop when 99.9% of points are good
if changed <= lenpts10:
break

for i, cc in enumerate(cluster_centers):
cc.group = i

return cluster_centers

def print_eps(points, cluster_centers, W=400, H=400):
Color = namedtuple("Color", "r g b");

colors = []
for i in xrange(len(cluster_centers)):
colors.append(Color((3 * (i + 1) % 11) / 11.0,
(7 * i % 11) / 11.0,
(9 * i % 11) / 11.0))

max_x = max_y = -FLOAT_MAX
min_x = min_y = FLOAT_MAX

for p in points:
if max_x < p.x: max_x = p.x
if min_x > p.x: min_x = p.x
if max_y < p.y: max_y = p.y
if min_y > p.y: min_y = p.y

scale = min(W / (max_x - min_x),
H / (max_y - min_y))
cx = (max_x + min_x) / 2
cy = (max_y + min_y) / 2

print "%%!PS-Adobe-3.0\n%%%%BoundingBox: -5 -5 %d %d" % (W + 10, H + 10)

print ("/l {rlineto} def /m {rmoveto} def\n" +
"/c { .25 sub exch .25 sub exch .5 0 360 arc fill } def\n" +
"/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath " +
" gsave 1 setgray fill grestore gsave 3 setlinewidth" +
" 1 setgray stroke grestore 0 setgray stroke }def")

for i, cc in enumerate(cluster_centers):
print ("%g %g %g setrgbcolor" %
(colors[i].r, colors[i].g, colors[i].b))

for p in points:
if p.group != i:
continue
print ("%.3f %.3f c" % ((p.x - cx) * scale + W / 2,
(p.y - cy) * scale + H / 2))

print ("\n0 setgray %g %g s" % ((cc.x - cx) * scale + W / 2,
(cc.y - cy) * scale + H / 2))

print "\n%%%%EOF"

def main():
npoints = 30000
k = 7 # # clusters

points = generate_points(npoints, 10)
cluster_centers = lloyd(points, k)
print_eps(points, cluster_centers)

main()

上述代码实现的算法是针对二维数据的，所以Point对象有三个属性，分别是在x轴上的值、在y轴上的值、以及所属的簇的标识。函数lloyd是
kmeans++算法的整体实现，其先是通过kpp函数选取合适的种子点，然后对数据集实行kmeans算法进行聚类。kpp函数的实现完全符合上述
kmeans++的基本思路的2、3、4步。

⑽ k-means算法解决了什么问题

k-means
算法属于聚类分析方法中一种基本的且应用最广泛的划分算法，它是一种已知聚类类别数的聚类算法。指定类别数为k，对样本集合进行聚类，聚类的结果由k
个聚类中心来表达，基于给定的聚类目标函数（或者说是聚类效果判别准则），算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减小的方向进行，最终的聚类结果使目标函数值取得极小值，达到较优的聚类效果。使用平均误差准则函数e作为聚类结果好坏的衡量标准之一，保证了算法运行结果的可靠性和有效性。