Kmeans

kmeans, 或k-均值聚类是一个不断重复迭代的算法，试图将样本分到k样本不交叉的簇中，划分的过程中，需要尽量的做到“同一个类内的样本离的越近越好，不同类间的样本离得越远越好”。
划分的过程使得类样本的平方和最小（WCSS within-cluster sum of squares），其需要满足目标：

其中，\(\mu_i\)是\(S_i\)中所有点的均值，上式叫做L2规数/欧几里得距离，算法的步骤为：

1. 指定聚类数量k
2. 随机初始化k个样本作为初始聚类中心
3. 不断计算每个样本与聚类中心的距离，将样本分配给最近的中心
4. 所有样本计算结束后，重新计算各自类簇内的聚类中心，计算方式为平均类内的所有样本
5. 重复 3 4 步直到聚类中心不再变化或者达到迭代次数为止

kmeans存在的问题

• 因为涉及到距离，如果采用欧式距离等只能适合于对连续型数据
• 计算时间复杂度太高，基本就是\(O(n^2)\)
• 由于是随机初始化的聚类中心，因次每次聚类的结果都不会稳定，而且效果不好
• 容易收到异常值的影响

kmeans++

因为kmeans随机初始化聚类中心而导致的聚类结果不稳定的问题，kmeans++主要针对这个问题做了改进。核心就是在初始化聚类中心的时候，选择离已选的聚类中心最远的点作为初始化的依据
计算方式为：

1. 随机选取中心点\(c_1\)
2. 计算每个未被选择的样本与已有聚类中心的最短距离\(D(x)\)
3. 计算每个样本被选为下一个聚类中心的概率：\(\frac{D(x)^2}{\sum_{x\in X} D(x)^2}\), 那么，谁离几个聚类中心最远，就更有可能被选择为聚类中心。
4. 重复 2、3步直到选择到k个聚类中心
   5 选出后遵循kmeans的4 5 步

聚类算法总结

原文：https://www.cnblogs.com/zhouyc/p/15145298.html