c++ - 改进的 K-means 聚类(Ward 准则)速度改进

Question

我使用带有随机初始化的 k 均值聚类来进行聚类识别。算法适用于良好的数据。但是，如果我处理带有很多噪声的数据，那么我的 k-means 算法就会失去其稳健性，并且会为同一数据集上的每次运行提供不同的解决方案。

所以我决定改进我的 k-means 聚类以最小化 Ward 标准:

1. 进行标准的 k-means 聚类
2. 遍历点和所有聚类并找到点 P 和聚类 A 和 B，就好像我将点 P 从聚类 A 移到聚类 B，那么该聚类的 ward 标准将是最小的
3. 如果找到这样的点，将其从 A 移动到 B，更新聚类中心并继续 2

我用 C++ 写了这个算法 here .然而，问题是，这种方法非常慢，我正在处理每个大约有 20 000 个点的集群。

你能建议我一个更好的解决方案，或者你能帮我加快这个算法吗？

Answer 1

我终于找到了解决方案。我意识到:

• 我对 Ward 的方法真的没用
• PCA 对我来说无法使用，因为我只使用一维簇。
• 在我实现 k-means++ 之后，正如 Micka 所说，k-means 的可靠性得到了提高。然而，偶尔它仍然给出不好的解决方案。 (实验性地，同一数据的 5 个聚类中有 1 个是错误的)

对我绝对有帮助的是 Mean normalization .我做了 5x k-means，计算了每次迭代的聚类中心的平均值。最后使用计算出的均值作为初始解运行 k-means。