k-means ++究竟是如何工作的？

Question

我无法完全理解k-means ++算法.我很感兴趣的是如何挑选出第一个k质心(剩下的就像在原始的k-means中).

1. 概率函数是基于距离还是高斯？
2. 在同一时间,最长的远点(来自其他质心)被挑选出来用于新的质心.

我将欣赏一步一步的解释和一个例子.维基百科中的那个还不够清楚.一个评论很好的源代码也会有所帮助.如果您使用的是6个阵列,那么请告诉我们哪个阵列是为了什么.

Answer 1

有趣的问题.感谢您提醒我这篇论文.PDF链接原始论文.

简单来说,最初从输入观察向量集中随机选择聚类中心,其中x如果x不接近任何先前选择的中心,则选择向量的概率很高.

这是一个一维的例子.我们的观察结果是[0,1,2,3,4].设第一个中心c1为0.下一个聚类中心c2x 的概率与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

Answer 2

一线。

假设我们需要选择2个聚类中心，而不是像随机选择所有聚类中心一样（我们以简单的k均值进行选择），我们将随机选择第一个聚类中心，然后找到距离第一个中心最远的点{这些点很可能会不属于第一个聚类中心，因为它们离它很远}，并在这些远点附近分配第二个聚类中心。