使用GPU支持实现高维数据的更快Kmeans聚类

Question

我们一直在使用Kmeans对日志进行聚类。 一个典型的数据集有100k+特征和1000万个样本。

为了找到最佳的k值，我们并行运行多个Kmeans，并选择具有最佳轮廓分数的一个。在90%的情况下，我们得到的k值在2到100之间。 目前，我们正在使用scikit-learn Kmeans。 对于这样的数据集，聚类需要在具有32个内核和244 RAM的ec2实例上花费大约24小时。

我目前正在研究更快的解决方案。

我已经测试过的内容：

1. Kmeans + Mean Shift Combination - 稍微好一些 (对于k=1024，需要 ~13h)，但仍然很慢。

2. Kmcuda 库 - 不支持稀疏矩阵表示。将该数据集表示为内存中的密集矩阵需要 ~3TB RAM。

3. Tensorflow (tf.contrib.factorization.python.ops.KmeansClustering()) - 今天才开始调查，但我可能做错了什么，或者不知道如何操作。在我的第一个测试中，使用单个GPU进行聚类，20k个样本和500个特征，比在1个线程的CPU上慢。

4. Facebook FAISS - 不支持稀疏表示。

接下来是PySpark MlLib Kmeans。但是，在一个节点上使用它有意义吗？

如果我使用多个GPU，比如使用8个Tesla V-100，会加速我的用例的训练吗？

是否有我没有听说过的神奇库？

还是简单地垂直扩展？

- t_sologub

---

在单节点上使用Pyspark确实没有意义；请查看RAPIDS cuML。 - desertnaut

@desertnaut 非常感谢。我认为这就是我一直在寻找的东西。 - t_sologub

@desertnaut，你有使用这个库的经验吗？玩了几天后，似乎数据集必须转换为cudf.Dataframe（GPU对象）。对吧？我无法想象这样的数据集如何适应GPU内存。 - t_sologub

抱歉，我还没有。 - desertnaut

Answer 1

1. 明智地选择算法。有聪明的和愚蠢的kmeans算法。劳埃德算法是愚蠢的，但是目前在GPU上找到的唯一算法。它浪费了大量资源进行不必要的计算。因为GPU和“大数据”人士并不关心资源效率……

   好的算法包括Elkan's、Hamerly's、Ying-Yang、Exponion、Annulus等——这些比Lloyd's快得多。

   Sklearn是其中较好的工具之一，因为它至少包含了Elkan's算法。但如果我没有记错，它可能会重复制作您的数据的密集副本。也许是分块的，所以你注意不到。当我将sklearn中的k-means与我自己在Python中实现的球形k-means进行比较时，我的实现速度要快得多。我只能解释为我使用了稀疏优化，而sklearn版本执行了密集操作。但也许这已经有所改进。

2. 实现质量很重要。有一篇有关基准测试k-means的有趣论文。让我谷歌一下：

   Kriegel, H. P., Schubert, E., & Zimek, A. (2017). The (black) art of runtime evaluation: Are we comparing algorithms or implementations?. Knowledge and Information Systems, 52(2), 341-378.

   他们展示了同样的算法根据实现差异可能具有数量级的运行时间差异。Spark在这方面表现不佳……它的开销太高，算法太慢。

3. 你不需要所有的数据。

   K-means使用平均值。随着你添加更多数据，平均值的质量会缓慢提高。所以使用所有可用数据几乎没有用处。只需使用足够大的样本，结果应该是几乎相同的质量。您还可以利用这一点进行种子设置。先在较小的集合上运行，然后再添加更多数据进行优化。

4. 因为你的数据是稀疏的，所以很有可能k-means并不是正确的工具。您测试了结果的质量吗？您如何确保属性被适当地缩放？结果到底是由向量为0的位置决定的还是由实际非零值决定的？经常重新运行k-means结果真的会得到改善吗？如果您永远不重新运行k-means会怎样？如果您仅在样本上运行它，如第3点所述？如果您只选择k个随机中心并且不执行任何k-means迭代会怎样？你最好的轮廓系数（Silhouette）是什么？很有可能您无法测量差异，只是在浪费时间和资源！那么您要如何确保结果的可靠性呢？

- Has QUIT--Anony-Mousse

Answer 2

感谢 @desertnaut 推荐使用 RAPIDS cuml 库。

后续内容可以在 这里 找到。

- t_sologub

---

你是否将结果（质量和运行时间）与单个CPU、Greg Hamerly的C++实现 https://github.com/ghamerly/fast-kmeans 和一个轻松适合主内存的示例进行了比较？ - Has QUIT--Anony-Mousse

@HasQUIT--Anony-Mousse 没有，我之前没有看到过那个代码库。很奇怪，因为我在网上搜索了很多次。但是我们最终通过使用更多的线程来加速聚类。 - t_sologub

它支持colab，https://rapids.ai/，这个库看起来不错，为我节省了很多时间。 - DevX