在 GPU 支持下更快地对高维数据进行 Kmeans 聚类
Faster Kmeans Clustering on High-dimensional Data with GPU Support
我们一直在使用 Kmeans 对我们的日志进行聚类。
一个典型的数据集有 10 mill。具有 100k+ 特征的样本。
为了找到最优的 k - 我们 运行 并行多个 Kmeans 并选择轮廓分数最好的那个。在 90% 的情况下，我们最终得到的 k 在 2 到 100 之间。
目前，我们正在使用 scikit-learn Kmeans。
对于这样的数据集，在具有 32 个内核和 244 个 RAM 的 ec2 实例上进行集群大约需要 24 小时。
我目前一直在研究更快的解决方案。
我已经测试过的：
Kmeans + Mean Shift Combination - 好一点（对于 k=1024 --> ~13h）但仍然很慢。
Kmcuda 库 - 不支持稀疏矩阵表示。需要 ~3TB RAM 才能将该数据集表示为内存中的密集矩阵。
Tensorflow (tf.contrib.factorization.python.ops.KmeansClustering()) - 今天才开始调查，但要么我做错了什么，要么我不知道怎么做煮它。在我使用 20k 样本和 500 个特征进行的第一次测试中，单个 GPU 上的聚类比 1 线程中的 CPU 慢。
Facebook FAISS - 不支持稀疏表示。
我列表中的下一个是 PySpark MlLib Kmeans。但它在 1 个节点上有意义吗？
它会在多个 GPU 上更快地训练我的用例吗？例如，带有 8 个 Tesla V-100 的 TensorFlow？
有什么我没听说过的魔法图书馆吗？
或者只是简单地垂直缩放？
明智地选择算法。 kmeans 有聪明的算法，也有愚蠢的算法。 Lloyd's 很愚蠢，但到目前为止，您在 GPU 中只能找到它。它通过不必要的计算浪费了大量资源。因为 GPU 和 "big data" 人们不关心资源效率......
好的算法包括 Elkan、Hamerly、Ying-Yang、Exponion、Annulus 等 - 这些算法比 Lloyd 的快。
Sklearn 是这里比较好的工具之一，因为它至少包括 Elkan 的算法。但如果我没记错的话，它可能会反复制作你的数据的密集副本。也许成块，所以你不会注意到它。当我将 sklearn 的 k-means 与 Python 中我自己的球形 k-means 进行比较时，我的实现速度快了很多倍。当 sklearn 版本执行密集操作时，我只能使用稀疏优化来解释这一点。但也许这已经有所改进。
实施质量很重要。有一篇关于基准测试 k-means 的有趣论文。让我Google吧：
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.
它们展示了同一个算法如何可能具有 f 数量级的 运行 时间差异，具体取决于实施差异。 Spark 在那里表现不佳...它的开销太高，算法太慢。
您不需要所有数据。
K 均值适用于平均值。随着您添加更多数据，均值的质量会非常缓慢地提高。因此，使用您拥有的所有数据几乎没有用处。只要使用足够大的样本，结果应该具有几乎相同的质量。您也可以利用它进行播种。 运行 先在较小的集合上，然后添加更多数据进行优化。
因为您的数据稀疏，所以 k-means 很有可能不是正确的工具。您是否测试过结果的质量？您如何确保属性得到适当缩放？结果有多少仅由向量为 0 的位置决定，而不是由实际的非零值决定？经常使用 re运行ning k-means 真的能改善结果吗？如果您不再使用 re运行 k-means 怎么办？如果你只是 运行 它在 3) 中讨论的样本上怎么办？如果您只选择 k 个随机中心并执行 0 次 k-means 迭代怎么办？你最好的剪影是什么？很可能您无法衡量差异，只是在白白浪费时间和资源！那么，您如何确保结果的可靠性？
感谢@desertnaut 对 RAPIDS cuml 库的建议。
后续可以找到here.
我们一直在使用 Kmeans 对我们的日志进行聚类。 一个典型的数据集有 10 mill。具有 100k+ 特征的样本。
为了找到最优的 k - 我们 运行 并行多个 Kmeans 并选择轮廓分数最好的那个。在 90% 的情况下，我们最终得到的 k 在 2 到 100 之间。 目前，我们正在使用 scikit-learn Kmeans。 对于这样的数据集，在具有 32 个内核和 244 个 RAM 的 ec2 实例上进行集群大约需要 24 小时。
我目前一直在研究更快的解决方案。
我已经测试过的：
Kmeans + Mean Shift Combination - 好一点（对于 k=1024 --> ~13h）但仍然很慢。
Kmcuda 库 - 不支持稀疏矩阵表示。需要 ~3TB RAM 才能将该数据集表示为内存中的密集矩阵。
Tensorflow (tf.contrib.factorization.python.ops.KmeansClustering()) - 今天才开始调查，但要么我做错了什么，要么我不知道怎么做煮它。在我使用 20k 样本和 500 个特征进行的第一次测试中，单个 GPU 上的聚类比 1 线程中的 CPU 慢。
Facebook FAISS - 不支持稀疏表示。
我列表中的下一个是 PySpark MlLib Kmeans。但它在 1 个节点上有意义吗？
它会在多个 GPU 上更快地训练我的用例吗？例如，带有 8 个 Tesla V-100 的 TensorFlow？
有什么我没听说过的魔法图书馆吗？
或者只是简单地垂直缩放？
明智地选择算法。 kmeans 有聪明的算法，也有愚蠢的算法。 Lloyd's 很愚蠢，但到目前为止，您在 GPU 中只能找到它。它通过不必要的计算浪费了大量资源。因为 GPU 和 "big data" 人们不关心资源效率...... 好的算法包括 Elkan、Hamerly、Ying-Yang、Exponion、Annulus 等 - 这些算法比 Lloyd 的快。
Sklearn 是这里比较好的工具之一，因为它至少包括 Elkan 的算法。但如果我没记错的话，它可能会反复制作你的数据的密集副本。也许成块，所以你不会注意到它。当我将 sklearn 的 k-means 与 Python 中我自己的球形 k-means 进行比较时，我的实现速度快了很多倍。当 sklearn 版本执行密集操作时，我只能使用稀疏优化来解释这一点。但也许这已经有所改进。
实施质量很重要。有一篇关于基准测试 k-means 的有趣论文。让我Google吧：
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.
它们展示了同一个算法如何可能具有 f 数量级的 运行 时间差异，具体取决于实施差异。 Spark 在那里表现不佳...它的开销太高，算法太慢。
您不需要所有数据。
K 均值适用于平均值。随着您添加更多数据，均值的质量会非常缓慢地提高。因此，使用您拥有的所有数据几乎没有用处。只要使用足够大的样本，结果应该具有几乎相同的质量。您也可以利用它进行播种。 运行 先在较小的集合上，然后添加更多数据进行优化。
因为您的数据稀疏，所以 k-means 很有可能不是正确的工具。您是否测试过结果的质量？您如何确保属性得到适当缩放？结果有多少仅由向量为 0 的位置决定，而不是由实际的非零值决定？经常使用 re运行ning k-means 真的能改善结果吗？如果您不再使用 re运行 k-means 怎么办？如果你只是 运行 它在 3) 中讨论的样本上怎么办？如果您只选择 k 个随机中心并执行 0 次 k-means 迭代怎么办？你最好的剪影是什么？很可能您无法衡量差异，只是在白白浪费时间和资源！那么，您如何确保结果的可靠性？
感谢@desertnaut 对 RAPIDS cuml 库的建议。
后续可以找到here.