对于数据集中的每一个数据，按照距离𝐾个中心点的距离，将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。
计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。
重复步骤，直至中心点不再变化。
Repeat {
for i = 1 to m
c(i) := index (form 1 to K) of cluster centroid closest to x(i)
for k = 1 to K
μk := average (mean) of points assigned to cluster k
}
https://camo.githubusercontent.com/7934ba50374f3316d8f1b8a3dcd210cc6d9d2607c6fa640c0ba0e8883c116c43/687474703a2f2f7778332e73696e61696d672e636e2f6d773639302f30303633304465666c79316735623734367a776a676a33306668306337676e6a2e6a7067img,[object Object]
https://camo.githubusercontent.com/8fabb926634ad9f39b44abb9027b7759d7e0064b6726a3c32b40ac78cade6632/687474703a2f2f7778322e73696e61696d672e636e2f6d773639302f303036333044656667793167356275397766776f746a33306a703031747132762e6a7067img,[object Object]
算法分为两个步骤，第一个 for 循环是赋值步骤，即：对于每一个样例𝑖，计算其应该属于的类。第二个 for 循环是聚类中心的移动，即：对于每一个类𝐾，重新计算该类的质心。
K-均值算法也可以很便利地用于将数据分为许多不同组，即使在没有非常明显区分的组群的情况下也可以。下图所示的数据集包含身高和体重两项特征构成的，利用 K-均值算法将数据分为三类，用于帮助确定将要生产的 T-恤衫的三种尺寸。
K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此 K-均值的代价函数（又称畸变函数 Distortion function）为：
在运行 K-均值算法的之前，我们首先要随机初始化所有的聚类中心点，下面介绍怎样做：
我们应该选择𝐾 < 𝑚，即聚类中心点的个数要小于所有训练集实例的数量。
随机选择𝐾个训练实例，然后令𝐾个聚类中心分别与这𝐾个训练实例相等K-均值的一个问题在于，它有可能会停留在一个局部最小值处，而这取决于初始化的情况。
https://camo.githubusercontent.com/2a1aa5980b6f918d6111f680fbb258057cd365778c05e2aa9d0b195452c31f02/687474703a2f2f7778322e73696e61696d672e636e2f6d773639302f30303633304465666c7931673562377062616561766a3330716f3063777463392e6a7067img,[object Object]
为了解决这个问题，我们通常需要多次运行 K-均值算法，每一次都重新进行随机初始化，最后再比较多次运行 K-均值的结果，选择代价函数最小的结果。这种方法在𝐾较小的时候（2--10）还是可行的，
没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选择的时候思考我们运用 K-均值算法聚类的动机是什么。有一个可能会谈及的方法叫作
我们可能会得到一条类似于这样的曲线。像一个人的肘部。这就是“肘部法则”所做的，让我们来看这样一个图，看起来就好像有一个很清楚的肘在那儿。你会发现这种模式，它的畸变值会迅速下降，从 1 到 2，从 2 到 3 之后，你会在 3 的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用 3 个聚类来进行聚类是正确的，
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。
| KNN | K-Means |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| 1.KNN是分类算法 2.属于监督学习 3.训练数据集是带label的数据 | 1.K-Means是聚类算法 2.属于非监督学习 3.训练数据集是无label的数据，是杂乱无章的，经过聚类后变得有序，先无序，后有序。 |
| 没有明显的前期训练过程，属于memory based learning | 有明显的前期训练过程 |
| K的含义：一个样本x，对它进行分类，就从训练数据集中，在x附近找离它最近的K个数据点，这K个数据点，类别c占的个数最多，就把x的label设为c。 | K的含义：K是人工固定好的数字，假设数据集合可以分为K个蔟，那么就利用训练数据来训练出这K个分类。 |
都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法思想。
k-means：在大数据的条件下，会耗费大量的时间和内存。 优化k-means的建议：
减少聚类的数目K。因为，每个样本都要跟类中心计算距离。
减少样本的特征维度。比如说，通过PCA等进行降维。
考察其他的聚类算法，通过选取toy数据，去测试不同聚类算法的性能。
hadoop集群，K-means算法是很容易进行并行计算的。
算法可能找到局部最优的聚类，而不是全局最优的聚类。使用改进的二分k-means算法。
二分k-means算法：首先将整个数据集看成一个簇，然后进行一次k-means（k=2）算法将该簇一分为二，并计算每个簇的误差平方和，选择平方和最大的簇迭代上述过程再次一分为二，直至簇数达到用户指定的k为止，此时可以达到的全局最优。
由于数据以及需求的多样性，没有一种算法能够适用于所有的数据类型、数 据簇或应用场景，似乎每种情况都可能需要一种不同的评估方法或度量标准。例 如，K均值聚类可以用误差平方和来评估，但是基于密度的数据簇可能不是球形， 误差平方和则会失效。在许多情况下，判断聚类算法结果的好坏强烈依赖于主观 解释。尽管如此，聚类算法的评估还是必需的，它是聚类分析中十分重要的部分之一。
聚类评估的任务是估计在数据集上进行聚类的可行性，以及聚类方法产生结 果的质量。这一过程又分为三个子任务。
这一步骤是检测数据分布中是否存在非随机的簇结构。如果数据是基本随机 的，那么聚类的结果也是毫无意义的。我们可以观察聚类误差是否随聚类类别数 量的增加而单调变化，如果数据是基本随机的，即不存在非随机簇结构，那么聚 类误差随聚类类别数量增加而变化的幅度应该较不显著，并且也找不到一个合适 的K对应数据的真实簇数。
确定聚类趋势之后，我们需要找到与真实数据分布最为吻合的簇数，据此判定聚类结果的质量。数据簇数的判定方法有很多，例如手肘法和Gap Statistic方 法。需要说明的是，用于评估的最佳数据簇数可能与程序输出的簇数是不同的。 例如，有些聚类算法可以自动地确定数据的簇数，但可能与我们通过其他方法确 定的最优数据簇数有所差别。
在无监督的情况下，我们可以通过考察簇的分离情况和簇的紧 凑情况来评估聚类的效果。定义评估指标可以展现面试者实际解决和分析问题的 能力。事实上测量指标可以有很多种，以下列出了几种常用的度量指标，更多的 指标可以阅读相关文献。
轮廓系数、均方根标准偏差、R方（R-Square）、改进的HubertΓ统计。
首先选择𝐾个随机的点，称为聚类中心（cluster centroids）；
U676683698
U774568524
