1. K-means

作用

把n个对象根据他们的属性分为K个聚类，使得

• 同一个聚类中的对象相似度较高
• 不同聚类中的对象相似度较小

算法过程

一开始是原始数据，杂乱无章，看起来都一样，没有label。

1. 人为指定聚类个数，令K=2；
2. 人为指定初始聚类中心（需要一定的先验知识）：随机在坐标上选K（此处K=2）个点，作为聚类中心；
3. 把每个数据样本划分到最近的中心点那一簇；
4. 划分完后更新每个簇的中心（即把该簇的所有数据点的坐标加起来取平均值），得到新的簇中心后，再次进行操作3，就这样不断“划分——更新——划分——更新”，知道每个簇的中心不再移动为止。

注意

求簇中心的算法：
1. 使用每个点的坐标平均值
2. 
3. 
4. 

算法特点

1. 聚类中心的个数K要事先给定，但在实际中这个K是非常难以估计的，很多时候事先并不知道该分几个类才合适。
2. 需要人为地指定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（这个缺陷可以使用K-means++改进）。

2. K-means++

算法过程

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

注意

如何使D(x)较大的点，被选取作为聚类中心的概率较大
A：
1. 先从数据库中随机挑个随机点当“种子点”
2. 对每个未被选中的点：计算其和最近的“种子点”的距离D(x)保存在一个数组里，然后把这些距离加起来得到Sum(D(x))
3. 再取一个随机值，用权重的方式来取下一个“种子点”：
  1）先取一个能落在Sum(D(x))中的随机值Random
  2）对于未被选中的数据点，如果Random-=D(x)后，Random<=0，则将该数据点选做种子点
4. 重复2和3，直到K个聚类中心被选出来
5. 利用这K个聚类中心运行标准的K-means算法

算法特点

1. 聚类中心的个数K要事先给定，但在实际中这个K是非常难以估计的，很多时候事先并不知道该分几个类才合适。
2. 不需人为地指定初始聚类中心（是对K-means的改进）。

3. KNN

4. KNN和K-means比较

参考文献

Kmeans（K均值）与Kmeans++和KNN（K近邻）算法比较