原型聚类

原型聚类称为”基于原型的聚类”(prototype-based clustering)，此类算法假设聚类结构能通过一组原型刻画。
通常，算法先对原型进行初始化，然后对原型进行迭代求解。采用不同的原型表示，不同的求解方式，将产生不同的算法。

k-means算法

算法原理


k均值算法首先假设一组向量作为所有簇的簇均值向量，然后根据假设的簇均值向量给出了数据集D的一个簇划分，再根据这个簇划分来计算真实的簇均值向量。
算法过程

  1. 初始化聚类中心
  2. 将样本点分配到最近的聚类中心
  3. 调整聚类中心为类内样本均值
  4. 重复1.2 直到收敛

终止条件判断

  1. 对所有的 <nobr> k∈1,2,..,K </nobr>，都有 <nobr> μ^k=μk </nobr>则收敛，停止迭代。

坐标下降算法

  1. 分配样本点到最近聚类中心
    <nobr> zi←argminj||uj−xi||22 </nobr>
    调整聚类中心为类内样本均值（平方距离最小等价于求均值）
    <nobr> μjμj=1nj∑i:zi=jxi←argminj||uj−xi||22 </nobr>

    交替最小化

优缺点和改进

优点：
1. 原理简单
2. 实现容易
3. 聚类效果还可以
缺点：
1. 对于离群点和孤立点敏感；
2. k值的选择，（需要预知有几类）;
3. 假设了球对称形状的簇，不能发现非凸形的簇
4. 收敛到局部最优（初始聚类中心的选择；）
5. 需要样本的均值可以计算（限定数据种类）
6. 无法增量计算

复杂度O（NKm），迭代次数可能较多，迭代次数和K较小时退化为O（N）

kmeans++

k-means的初始化算法关系找到的局部最优解的质量
k-means++使用智能的初始化方式

  1. 随机选择第一个聚类中心
  2. 计算各样本点到最近的聚类中心的距离 <nobr> d(x) </nobr>
  3. 以正比于 <nobr> d(x)2 </nobr>的概率选择选择新的聚类中心
  4. 重复2，3直到选出k个中心

优点：后续的k-mean收敛速度更快，结果更好
缺点：初始化比随机代价高，

如何选择聚类中心数

肘部法则

可扩展k-means MR

待补充

参考资料

《机器学习》周志华 第9章