K-Means属于聚类算法，是一种无监督学习算法，没有训练集和测试集之分，也没有正确分类的标签与之参照来提升学习效果。
聚类就是把一堆样本根据一些特性分成不同的簇，也就是类。
聚类类型有以下几种：
层次的与划分的：划分聚类就是简单的讲数据集划分成不重叠的子集（簇）；如果簇允许有子簇，就是层次聚类。
互斥的和模糊的：互斥的就是一个样本点只在一个簇中，模糊聚类则是每个样本点以一个0和1之间的权值来表示属于每个簇的概率。
完全的与部分的： 完全聚类将每个对象指派到一个簇，而部分聚类则不是，可能有一些对象不会被指派。
聚类的方法有以下三种：
- 基于原型的聚类，簇的原型通常是质心（聚类中心）。
- 基于图的聚类，以图表示数据，节点事对象，边代表对象之间的联系。
- 基于密度的聚类，以稠密区域和低密度区域来进行区分。
K-Means数据是基于原型的聚类。
K-Means原理
该算法比较简单，首先假定一组数据集，则先选择K个之心，其中K是用户指定的参数（簇的个数），之后把每个点指派到最近的质心。
指派到同一个质心的点成为一个簇。
之后根据同一个簇的点，重新计算质心的位置，更新质心，再重新对所有的点进行指派。
重复指派和更新的步骤，直到簇的中心不发生变化。
通常情况下，如果质心变化的幅度很小，就可以停止该算法了。
样本点的指派
一般来说，采用欧几里得距离来对空间中的点进行指派，作为距离的度量，在文档中用余弦相似性。
当然，也可以用曼哈顿距离替代欧几里得距离，用Jaccard度量替代余弦相似性。
也就是说，确定质心之后，对一个样本点，计算出他到每一个质心的度量，离哪个最近就属于哪个质心的簇。
质心的更新和优化目标
根据上面的步骤，每次把所有的点划分完成之后，都需要更新质心，具体的方法如下：
欧氏空间中的数据（样本点）
可以用误差平方和作为度量聚类质量的目标函数，计算每个数据点的误差-该点到最近质心的欧氏距离，然后计算平方和，之后取该簇所有点误差平方和的均值，即更新后的质心。
例如：三个二维点（1，1）、（2，3）和（6，2）的质心是（(1+2+6)/3,(1+3+2)/3） = (3,2)。
文档型数据
需要最大化簇中文档与质心的相似性，则取簇中每个样本点到质心的余弦相似度和的均值。
几种常用的度量的组合如下：
局限
聚类的初始质心位置需要初始化，如果选用随机初始化的方法，则很可能簇的质量会很差，因为K-Means是局部最优算法，可能每次聚类结果都不一样。
我们可以在选取质心时，随机选择第一个点，或者取所有点的质心作为第一个点，然后对于每个后继初始质心，选择离已经选去过的初始质心最远的点，这样可以保证质心足够分散，但是容易选中离群点。
算法评价指标
聚类算法的评价指标分为三种，内部指标、外部指标、相对指标。
内部指标就是不需要外部信息作为参照的指标，仅使用内部信息，比如簇的凝聚性，分离性等。
外部指标则是设定有一组外部提供的分类标号，可以计算匹配程度，类似于分类算法评价。
相对指标则是比较不同的类和簇，可以用任何一种指标在不同的簇之间进行比较以评估性能。
凝聚度和分离度
K-Means是基于原型的聚类，我们只看这种情况下的凝聚度和分离度。
凝聚度可以定义为关于簇质心的邻近度的和，两个簇之间的分离度可以用两个簇圆形的邻近性度量。
当用欧几里得距离衡量邻近度时，簇之间分离性的传统度量时组平方和（SSB），即簇质心到所有数据点的总均值
的距离的平方和，而
是总均值。
轮廓系数
轮廓系数综合了凝聚度和分离度，计算方法如下：
- 对于第i个对象，计算他到簇中所有其他对象的平均距离，记作
.
- 对于第i个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离。关于所有的簇，找出最小值，记作
。
- 对于第i个对象，轮廓系数为：
从公式中可以看出，轮廓系数在-1和1之间变化，理想情况下，肯定是要大于
的而且越大越好，那么越大轮廓系数就趋近于1。
另外可以取簇中点的轮廓系数的平均值，计算簇的平均轮廓系数，通过计算所有点的平均轮廓系数，可以得到聚类优良性的总度量。
邻近度矩阵
邻近度矩阵类似于混淆矩阵，将相似度矩阵的行和列排序，属于相同簇的对象在一起，则理想的相似度矩阵具有块对角结构。
块越明显，则聚类效果越好。
外部指标
外部指标是存在外部信息的评价度量，可以参考分类算法的评价指标，所以可以有熵、纯度、精准率、召回率、F1-Score等评价指标，这里不再具体说明。
另外针对二元分类，我们还有Rand系数和Jaccard系数作为度量。
假设有相依表如下：
| - | 相同的簇 | 不同的簇 |
|---|---|---|
| 相同的类 | ||
| 不同的类 |
：两个样本点，具有相同的类，也被分进了相同的簇。
：两个样本点，具有相同的类，分到了不同的簇。
：两个不同类的样本点，分到了同一个簇。
：两个不同类的样本点，分到了不同的簇。
所以在聚类算法的外部指标中，相依表中的数不等于所有点的个数。
根据相依表，我们有Rand系数为：
Jaccard系数为：
簇个数的确定
在有些业务中无法确定需要分类个类别个数时，我们可以通过一些手段来估计需要聚类的簇个数。
可以画出簇个数-SSE曲线或者簇个数-轮廓系数曲线来判断选取哪个点比较合适。
如图：
横轴代表簇个数，纵轴代表在该簇个数下聚类之后的SSE/轮廓系数。
我们可以根据肘部法则来判断最优簇个数，左图中时SSE的变化，可以看到在10个簇时，SSE有一个明显的变小拐点，形成了一个肘部。
右图中的轮廓系数（小于1，越大越好），也是在10的时候出现了拐点，那么选取10作为簇个数就是最理想的。
K-Means改进
主要有K-Means++, ISODATA,Kernel K-Means三种改进方式：
K-means++：原始K-means算法最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心：假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉：聚类中心当然是互相离得越远越好。这个改进虽然直观简单，但是却非常得有效。
ISODATA：ISODATA的全称是迭代自组织数据分析法。在K-means中，K的值需要预先人为地确定，并且在整个算法过程中无法更改。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出K的大小。ISODATA就是针对这个问题进行了改进，它的思想也很直观：当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。
Kernel K-means：传统K-means采用欧式距离进行样本间的相似度度量，显然并不是所有的数据集都适用于这种度量方式。参照支持向量机中核函数的思想，将所有样本映射到另外一个特征空间中再进行聚类，就有可能改善聚类效果。
K-Means ++
下面结合一个简单的例子说明K-means++是如何选取初始聚类中心的。数据集中共有8个样本，分布以及对应序号如下图所示：
假设经过图2的步骤一后6号点被选择为第一个初始聚类中心，那在进行步骤二时每个样本的D(x)和被选择为第二个聚类中心的概率如下表所示：
其中的P(x)就是每个样本被选为下一个聚类中心的概率。最后一行的Sum是概率P(x)的累加和，用于轮盘法选择出第二个聚类中心。方法是随机产生出一个0~1之间的随机数，判断它属于哪个区间，那么该区间对应的序号就是被选择出来的第二个聚类中心了。例如1号点的区间为[0,0.2)，2号点的区间为[0.2, 0.525)。
从上表可以直观的看到第二个初始聚类中心是1号，2号，3号，4号中的一个的概率为0.9。而这4个点正好是离第一个初始聚类中心6号点较远的四个点。这也验证了K-means的改进思想：即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。可以看到，该例的K值取2是比较合适的。当K值大于2时，每个样本会有多个距离，需要取最小的那个距离作为D(x)。
ISODATA
ISODATA算法在运行过程中能够根据各个类别的实际情况进行两种操作来调整聚类中心数K：(1)分裂操作，对应着增加聚类中心数；(2)合并操作，对应着减少聚类中心数。
其中涉及到分裂和合并操作，首先来看合并操作：
分裂操作：
另外，根据以上操作，以下四个参数是需要给出的：
预期的聚类中心数目Ko：虽然在ISODATA运行过程中聚类中心数目是可变的，但还是需要由用户指定一个参考标准。事实上，该算法的聚类中心数目变动范围也由Ko决定。具体地，最终输出的聚类中心数目范围是 [Ko/2, 2Ko]。
每个类所要求的最少样本数目Nmin：用于判断当某个类别所包含样本分散程度较大时是否可以进行分裂操作。如果分裂后会导致某个子类别所包含样本数目小于Nmin，就不会对该类别进行分裂操作。
最大方差Sigma：用于衡量某个类别中样本的分散程度。当样本的分散程度超过这个值时，则有可能进行分裂操作（注意同时需要满足[2]中所述的条件）。
两个类别对应聚类中心之间所允许最小距离dmin：如果两个类别靠得非常近（即这两个类别对应聚类中心之间的距离非常小），则需要对这两个类别进行合并操作。是否进行合并的阈值就是由dmin决定。
针对ISODATA算法总结一下：该算法能够在聚类过程中根据各个类所包含样本的实际情况动态调整聚类中心的数目。如果某个类中样本分散程度较大（通过方差进行衡量）并且样本数量较大，则对其进行分裂操作；如果某两个类别靠得比较近（通过聚类中心的距离衡量），则对它们进行合并操作。
可能没有表述清楚的地方是ISODATA-分裂操作的第1步和第2步。同样地以图三所示数据集为例，假设最初1，2，3，4，5，6，8号被分到了同一个类中，执行第1步和第2步结果如下所示：
而在正确分类情况下（即1，2，3，4为一类；5，6，7，8为一类），方差为0.33。因此，目前的方差远大于理想的方差，ISODATA算法就很有可能对其进行分裂操作。
