我对K-Means++算法的理解存在一些困难。我特别想知道最初的k个中心点是如何选择的，也就是初始化部分，因为其余部分与原始的K-Means算法类似。
- 使用的概率函数是基于距离还是高斯分布的？
- 同时，是否选择距离其他中心点最远的点作为新的中心点？
我希望能得到一个逐步的解释和一个例子。维基百科上的解释不够清晰。另外，如果有详细注释的源代码也会很有帮助。如果使用了6个数组，请说明每个数组的用途。
回答：
有趣的问题。感谢你让我注意到这篇论文 – 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]: # 这个事件的概率为0.1 i = 0elif r < cumprobs[1]: # 这个事件的概率为0.2 i = 1elif r < cumprobs[2]: # 这个事件的概率为0.3 i = 2elif r < cumprobs[3]: # 这个事件的概率为0.4 i = 3