K-means ++算法

Question

我读了纸k-means ++:Careful Seeding的优点,并不太明白提供的算法是:

"设D(x)表示从数据点x到我们已经选择的最近中心的最短距离.

1A.从X中随机均匀地选择初始中心c1.

1B.选择下一个中心ci,用概率选择ci =x'∈X(D(x')^ 2)/ Sum_of(D(x)^ 2)

1C.重复步骤1b,直到我们选择了总共k个中心.

2-4.继续使用标准k-means算法"

(最好看看上面链接中的算法)

特别是第1b步.它们的意思是"用概率选择ci =x'∈X(D(x')^ 2)/ Sumof(D(x)^ 2)".他们是指选择比例最大的元素吗？如何进行这样的计算可以导致选择最佳质心？

Answer 1

函数D(x)是针对所有点x∈X定义的.

在步骤1b中,我们必须选择一些点作为新的中心.我们将在所有点(不是中心点)之间随机选择.但我们不会给予每一点平等的机会; 我们会在选择之前为不同的点分配不同的概率.这些概率必须加起来为1.

考虑D(x)^ 2.我们可以在每个点对此进行评估,并将值相加:Sum_of(D(x)^ 2).

然后我们可以为每个点x'分配等于D(x')^ 2/Sum_of(D(x)^ 2)的概率.这些概率加起来为1,并且提供了一个更好的机会来远离所有现有的中心.

Answer 2

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.