1. Main Steps
K-Means可以说是最简单实用的聚类算法了，流程如下
- 输入：n个数据点，目标簇个数k
- 初始化k个数据点作为簇的中心点
- 迭代至收敛
- 对每个数据点计算其最近的中心点，并将其归到该簇
- 计算每个簇新的中心点（取均值）
2. 中心点的初始化
比较容易想到的是随机初始化，也就是从n个数据点中随机选取k个点作为中心点
实际上，除了随机初始化，业界还经常使用Canopy进行中心点的初始化
Canopy需要设置两个阈值
称为loose distance
称为tight distance
流程如下
- 将所有数据点作为一个集合
- 迭代至集合为空
- 从集合中随机选取一个点作为第一个簇的中心
- 对剩余的每个数据点，如果其与某个簇的距离小于，归到该簇中
- 此外如果其与该簇的距离小于，从集合中删除这个点
3. K值的确定
为了找到较好的K值，可以设定一个聚类结果评估指标（平均半径等）
如果设定的K值小于真实簇数量，随着K的增加，指标会迅速提升
而如果设定的K值大于真实簇数量，随着K的增加，指标提升会变缓
由此可以找到一个较好的K值
4. 并行方法
K-Means的并行可以说是比较容易想到的
- Map：对每个数据点计算其最近的中心点
- Reduce：计算新的中心点