1. K-means
作用
把n个对象根据他们的属性分为K个聚类，使得
- 同一个聚类中的对象相似度较高
- 不同聚类中的对象相似度较小
算法过程
一开始是原始数据，杂乱无章，看起来都一样，没有label。
- 人为指定聚类个数，令K=2；
- 人为指定初始聚类中心（需要一定的先验知识）：随机在坐标上选K（此处K=2）个点，作为聚类中心；
- 把每个数据样本划分到最近的中心点那一簇；
- 划分完后更新每个簇的中心（即把该簇的所有数据点的坐标加起来取平均值），得到新的簇中心后，再次进行操作3，就这样不断“划分——更新——划分——更新”，知道每个簇的中心不再移动为止。
注意
求簇中心的算法：
1. 使用每个点的坐标平均值
2.
3.
4.
算法特点
- 聚类中心的个数K要事先给定，但在实际中这个K是非常难以估计的，很多时候事先并不知道该分几个类才合适。
- 需要人为地指定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（这个缺陷可以使用K-means++改进）。
2. K-means++
算法过程
- 从输入的数据点集合中随机选择一个点作为第一个聚类中心
- 对于数据集中的每一个点x，计算它与最近聚类中心（指已选择的聚类中心）的距离D(x)
- 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
- 重复2和3直到K个聚类中心被选出来
- 利用这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算法
算法特点
- 聚类中心的个数K要事先给定，但在实际中这个K是非常难以估计的，很多时候事先并不知道该分几个类才合适。
- 不需人为地指定初始聚类中心（是对K-means的改进）。
3. KNN
4. KNN和K-means比较
| KNN | K-means |
|---|---|
| 分类算法 | 聚类算法 |
| 监督学习 | 无监督学习 |
| 喂给它的数据集是带label的数据 | 喂给它的数据集是无label的 |
| 没有明显的前期训练过程，属于memory-based learning | 有明显的前期训练过程 |
| K的含义：…… | K是人工固定好的数字，假设数据集可以分为K个簇，由于是依靠人工定好，需要一点先验知识 |
