algorithm - 如何实现 K-Means++ 算法？

Question

我无法完全理解 K-Means++ algorithm .我很感兴趣的是第一个 k 质心是如何被挑选出来的，即初始化，因为其余的就像在原始 K-Means algorithm 中一样。 .

1. 使用的概率函数是基于距离还是高斯？
2. 同时，最远的点(从其他质心)被选为新的质心。

我会很感激一步一步的解释和例子。 Wikipedia中的那个不够清楚。另外，注释得很好的源代码也会有所帮助。如果您使用 6 个阵列，请告诉我们哪一个用于什么。

Answer 1

有趣的问题。感谢您让我注意到这篇论文 - K-Means++: The Advantages of Careful Seeding

简单来说，聚类中心最初是从一组输入观察向量中随机选择的，如果 x 不在附近，则选择向量 x 的概率很高任何先前选择的中心。

这是一个一维的例子。我们的观察结果是 [0, 1, 2, 3, 4]。令第一个中心c1为0。下一个聚类中心c2为x的概率与||c1-x||^成正比2。所以，P(c2 = 1) = 1a，P(c2 = 2) = 4a，P(c2 = 3) = 9a，P(c2 = 4) = 16a，其中 a = 1/(1+4+9+ 16).

假设 c2=4。然后，P(c3 = 1) = 1a，P(c3 = 2) = 4a，P(c3 = 3) = 1a，其中 a = 1/(1+4+1)。

我已经用 Python 编写了初始化程序；不知道对你有没有帮助。

def initialize(X, K):
    C = [X[0]]
    for k in range(1, K):
        D2 = scipy.array([min([scipy.inner(c-x,c-x) for c in C]) for x in X])
        probs = D2/D2.sum()
        cumprobs = probs.cumsum()
        r = scipy.rand()
        for j,p in enumerate(cumprobs):
            if r < p:
                i = j
                break
        C.append(X[i])
    return C

编辑并澄清:cumsum 的输出为我们提供了划分区间 [0,1] 的边界。这些分区的长度等于相应点被选为中心的概率。那么，由于 r 是在 [0,1] 之间统一选择的，它将正好落入这些区间之一(因为 break)。 for 循环检查 r 位于哪个分区。

示例:

probs = [0.1, 0.2, 0.3, 0.4]
cumprobs = [0.1, 0.3, 0.6, 1.0]
if r < cumprobs[0]:
    # this event has probability 0.1
    i = 0
elif r < cumprobs[1]:
    # this event has probability 0.2
    i = 1
elif r < cumprobs[2]:
    # this event has probability 0.3
    i = 2
elif r < cumprobs[3]:
    # this event has probability 0.4
    i = 3