回答思路

k-means算法，也被称为k-均值算法，是最基本也是应用最广泛的聚类算法。该算法的核心思想是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点。

迭代过程

输入：簇的数目k和包含n个对象的数据库。

算法步骤：

为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。

将样本集中的样本按照最小距离原则分配到最邻近聚类

使用每个聚类中的样本均值作为新的聚类中心。

重复步骤2.3直到聚类中心不再变化。

伪代码

复杂度分析

1、时间复杂度

O(tnkm)，其中，t为迭代次数，k为簇的数目，n为样本点数，m为样本点维度。

2、空间复杂度

O(m(n+k))，其中，k为簇的数目，m为样本点维度，n为样本点数。

k-means迭代过程可视化

https://hckr.pl/k-means-visualization/

对kmeans算法不熟悉的同学可以从该网站里面，直观地了解kmeans迭代的每个过程

簇心随机不好，怎么才能更稳定

K-Means算法试图找到使平方误差准则函数最小的簇，当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想，但对于其他场景效果则不一定很好。

而且该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。

举个例子，典型的月牙形数据

from sklearn.datasets import make_moons X, y = make_moons(200, noise=.05, random_state=0) labels = KMeans(2, random_state=0).fit_predict(X) plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')

解决这种场景的思路可以借鉴支持向量机的核函数（使用核函数转换来将数据投影成到更高维度），在聚类中，可以考虑谱聚类，即Spectral clustering。

from sklearn.cluster import SpectralClustering model = SpectralClustering(n_clusters=2, affinity='nearest_neighbors', assign_labels='kmeans') labels = model.fit_predict(X) plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')

总结来说，主要有三种方法，解决簇心随机不好的问题，使聚类更稳定

多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE（误差的平方和）的簇集。这种策略简单，但是效果可能不好（本质还是随机选取）。

取一个样本，并使用谱聚类或者层次聚类技术对它聚类。比如从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。

取所有点的质心作为第一个点，然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。（典型的改进是kmeans++）