K-Means是一种迭代聚类方法，它随机分配初始质心并移动它们以最小化平方和。一个问题是，由于质心最初是随机的，因此错误的起始位置可能会导致算法收敛于局部最优值。

K-Means++旨在解决这个问题 - 它使用加权方法选择初始质心，这使得更远的点更有可能被选为初始质心。这个想法是，虽然初始化更复杂并且需要更长的时间，但质心会更准确，因此需要更少的迭代，因此它将减少总时间。（来源）

事实上，设计 K-Means++ 的人测试了它对数据进行聚类的速度，发现它的速度是原来的两倍。（来源）

然而，R 中的一些基本测试表明，K-Means++ 需要比 K-Means 更少的迭代次数并不能弥补初始化所花费的额外时间，即使对于正常大小的数据集也是如此。

考试：

我用大小从 100 到几千点的数据集对其进行了测试。数据在代码中被命名为“comp”。如果你想测试它，你可以使用任何你想要的数据集。

K-均值

首先，我们进行聚类：

k <- kmeans(comp, 2, nstart=1, iter.max=100, algorithm = "Lloyd")

接下来，可以将平方和添加到列表中

results <- k$withinss

现在，如果我们将聚类放在一个循环中，每次循环时都会添加到“结果”列表中，我们可以看到它在一定时间内循环了多少次

repeat {
k <- kmeans(comp, 2, nstart=1, iter.max=10, algorithm = "Lloyd")

results <- c(results, k$withinss)
}

（我以这种低效的方式做到了，因为我最初使用此代码来测试准确性，即哪种方法具有平均总平方和）

如果我们让循环运行 60 秒，我们会发现列表有 132,482 个对象。（它循环了 66241 次，因为每次都将两个对象添加到列表中）。

K-Means++

现在将其与 ++ 初始化进行比较。

#Set-up
library(LICORS)
k <- kmeanspp(comp, k = 2, start = "random", iter.max = 100, nstart = 1)

results <- k$withinss

#Loop
repeat {
k <- kmeanspp(comp, k = 2, start = "random", iter.max = 100, nstart = 1)

results <- c(results, k$withinss)
}

“结果”列表最终有 22712 个对象（循环了 11356 次）。

K-Means比 K-Means++ 快5 倍以上，因此这显然不仅仅是测量误差。比率会根据我用于测试的数据集而变化，但我已经尝试了所有数据集，直到具有数千个点的数据集，结果始终表明 K-Means++ 速度较慢。

我的第一个想法是我使用的包（LICORS）可能在执行 K-Means 时代码效率低下，但后来我看到 LICORS 在 ++ 初始化后实际上使用了默认的 kmeans 函数。换句话说：除了初始化的方法，一切都一样，而且++更慢。（另一个名为 flexclust 的 K-Means++ 包使用不同的代码甚至更慢！）

也许数据集需要有数万个点才能使 K-Means++ 更快？在这种情况下，对于我见过的每个来源都说 K-Means++ 更快是非常误导的。也许我误解了什么，或者测试有问题？

这里的任何专家（例如 Tim，他在这里声称 K-Means++ 更快）可以解释这些结果吗？