tensorflow - 在 GPU 支持下对高维数据进行更快的 Kmeans 聚类

Question

我们一直在使用 Kmeans 来对日志进行聚类。典型的数据集有 10 mill。具有 100k+ 特征的样本。

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

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

我已经测试过的内容:

1. Kmeans + 均值平移 Combination - 好一点(对于 k=1024 --> ~13h)，但仍然很慢。

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

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

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

我的列表中的下一个是 PySpark MlLib Kmeans。但它在 1 个节点上有意义吗？

在多个 GPU 上更快地训练我的用例吗？例如，带有 8 Tesla V-100 的 TensorFlow？

还有什么我没听说过的神奇图书馆吗？

或者只是简单地垂直缩放？

Answer 1

1. 明智地选择算法。 kmeans 有聪明的算法，也有愚蠢的算法。劳合社(Lloyd's)很愚蠢，但却是迄今为止您在 GPU 中能找到的唯一一个。它通过不必要的计算浪费了大量资源。因为GPU和“大数据”人们并不关心资源效率......好的算法包括 Elkan's、Hamerly's、Ying-Yang、Exponion、Annulus 等 - 这些算法比 Lloyd's 快得多。

   Sklearn 是这里更好的工具之一，因为它至少包含 Elkan 的算法。但如果我没记错的话，它可能会重复地复制你的数据。也许是成 block 的，所以你不会注意到它。当我将 sklearn 中的 k 均值与我自己在 Python 中的球形 k 均值进行比较时，我的实现速度快了很多倍。我只能使用稀疏优化来解释这一点，而 sklearn 版本则执行密集操作。但也许从那以后这已经得到了改进。

2. 实现质量很重要。有一篇关于 k 均值基准测试的有趣论文。让我用谷歌搜索一下:

   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 均值很可能不是正确的工具。您测试过结果的质量吗？如何确保属性得到适当缩放？结果有多少是简单地由向量为 0 的位置决定的，而不是由实际的非零值决定的？如此频繁地重新运行 k 均值，结果真的会有所改善吗？如果您不再重新运行 k 均值怎么办？如果您只是在 3) 中讨论的示例上运行它会怎么样？如果您只选择 k 个随机中心并进行 0 次 k 均值迭代会怎样？你最好的剪影是什么？您很可能无法衡量差异，只是白白浪费时间和资源!那么，您如何确保结果的可靠性呢？