数据聚类：

1：先抽几个点，把周围的点聚集起来，然后计算每个类的均值，以计算的结果为分类点，不断重复。直到分类的结果收敛为止。（备注：结果收敛：强条件：质心不再发生变化，稍弱条件：直到仅有1%的点改变簇）

2：R语言中实现：kmeans（x，centers，iter.max，nstart，algorithm=c("Hartigan-Wong", "Lloyd","Forgy", "MacQueen"）） 

centers是初始类的个数或者初始类的中心，

iter.max是最大迭代次数，

nstart是当centers是个数字的时候，随机集合的个数，

algorithm是算法，默认是第一个。其中，"Lloyd","Forgy"为同一种算法。

3：R语言中means算法输出：

    cluster是一个整数向量，用于表示记录所属的聚类。

    centers是一个矩阵，表示每个聚类各个变量的中心点。

    totss表示所生成聚类的总体距离平方和。

    withinss表示各个聚类组内的距离平方和。

    tot.withinss表示聚类组内的距离平方和总量。

    betweenss表示聚类组间的聚类平方和总量。

    size表示每个聚类组中成员的数量。

三种算法说明：

Lloyd算法，是最为经典简单的K-means迭代算法，其步骤如下：

1. 随机选取K个点作为初始的中心点

2. 计算每个点与K个中心点的K个距离(假如有N个点，就有N*K个距离值)

3. 分配剩下的点到距离其最近的中心点的类中

4. 重复步骤2和步骤3

5. 直到达到收敛或者达到某个停止阈值(如最大计算时间)

用公式解释如下：

1. 把所有的点分配到K个类的系数r，属于第k个类的记为1，否则为0

http://img.blog.csdn.net/20170514011023178

2. 由上可知第k个类中的样本数量

http://img.blog.csdn.net/20170514011509930

3. 目标是最小化损失函数J

http://img.blog.csdn.net/20170514011642321

4. 计算每个点到中心点的距离，分配r的系数

http://img.blog.csdn.net/20170514011720165

5. 重新计算每个类的中心点

http://img.blog.csdn.net/20170514011910353

重复4和5指导收敛或者达到某个阈值

Lloyd算法的缺点是，聚类产生的类别经常是不平衡的，就是说不同类中样本的数量差异很大。这点会经常被忽略到，然而很多时候需要我们聚类出来是平衡的，例如对手写数字图像进行聚类的时候，我们有理由相信10个数字出现的频率是一样的，所以希望聚类后每个类中含有样本数量是相同的。像上述的手写数字图像聚类这个例子中 ，为获得更高的分类准确率，则需要平衡的聚类结果。另外，Lloyd算法是一个批量更新算法，因此会学习速度会相对较快。

 

MacQueen算法

MacQueen是一种在线更新的算法，只需要一次迭代，具体步骤如下：

1. 选取头K个点作为K个类的中心点

2. 选取下一个点计算与K个中心点的距离，选取距离最小的分配到该类中

3. 更新该类的中心点

4. 重复2,3直到所有的点分配完毕，达到收敛

MacQueen相对于Lloyd而言，总体的训练时间需要更久。

 

Hartigan-Wong算法

为了改进上述算法的不平衡问题，我们可以考虑用Hartigan-Wong算法，它也是一种在线更新的算法，具体如下：

1. 随机分配所有的点到K个类上，计算K个类的中心

2. 随机选择一个点，把它移出所属类

3. 重新计算有变化的类的中心

4. 把移出的点重新分配到其距离最近的中心点的类上

5. 循环所有的点，重复2,3,4

6. 进行第二次循环，重复2,3,4,5

7. 直到达到收敛或者某个停止阈值

其主要的不同点是在分配到K个类别的过程中，公式如下：

http://img.blog.csdn.net/20170515132857710

值得注意的是因为Hartigan-Wong算法多加了一个乘法项

http://img.blog.csdn.net/20170515133007182

因此算法更倾向于把样本分配给样本数量较少的类。但是这个乘法项并不是为了平衡而设计的，而是在把移除的点加入合适的类中而发生的类大小变化。

Hartigan-Wong算法相对于Lloyd来说是一种在线更新的算法，一般来讲可以获得更低的代价函数值，但是同样地会更慢。Lloyd的批量更新算法速度更快，效率更高。