algorithm - K均值++算法

Question

我读了论文 k-means++: The Advantages of Careful Seeding并且不太理解所提供的算法是:

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

1a.随机均匀选择一个初始中心c1来自 X.

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”是什么意思？他们的意思是选择比例最大的元素吗？执行此类计算如何才能选择最佳质心？

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，并且更有可能指向远离所有现有中心的点。