我阅读了论文k-means++：小心播种的优势，并不太了解所提供的算法：
“让 D(x) 表示从数据点 x 到我们已经选择的最近中心的最短距离。
1a。从 X 中均匀随机选择一个初始中心 c1。
1b。选择下一个中心 ci，以概率 (D(x')^2) / Sum_of(D(x)^2) 选择 ci = x' ∈ X
1c。重复步骤 1b，直到我们选择了总共 k 个中心。
2-4。与标准 k-means 算法一样进行"
（最好看看上面链接中的算法）
特别是步骤 1b。“以概率 (D(x')^2) / Sumof(D(x)^2) 选择 ci = x' ∈ X”是什么意思。他们的意思是选择比例最大的元素吗？以及如何执行这样的计算才能选择最佳质心？
函数D(x)是为所有点 x ∈ X 定义的。
在步骤 1b 中，我们必须选择某个点作为新中心。我们将在所有点（还不是中心）之间随机选择。但我们不会对每一点都给予平等的机会；在我们选择之前，我们会为不同的点分配不同的概率。这些概率加起来必须为 1。
考虑 D(x)^2。我们可以在每一点上评估它，并将这些值相加：Sum_of(D(x)^2)。
然后我们可以为每个点 x' 分配一个等于 D(x')^2 / Sum_of(D(x)^2) 的概率。这些概率加起来为 1，并为远离所有现有中心的点提供了更好的机会。
http://en.wikipedia.org/wiki/K-means%2B%2B
1. Choose one center uniformly at random from among the data points.
2. For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen.
3. Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to D(x)2.
4. Repeat Steps 2 and 3 until k centers have been chosen.
5. Now that the initial centers have been chosen, proceed using standard k-means clustering.
K-Means 和 K-Means++ 之间最大的区别在于初始中心的选择方式。K-means 随机选择初始中心。在选择初始中心之前，K-Menas++ 计算点与第一个中心之间的所有距离，以使所有将被选择的中心彼此远离。如果选择一个中心靠近其他中心，则分配给相应中心的点需要迭代多次以分离集群。但是，如果两个中心的距离足够远，它们属于一个簇的概率很小，并且很容易将簇分开。