在Python中对大约100,000个短字符串进行聚类

Question

我想用Python把大约100,000个短字符串进行聚类，方法可以是q-gram距离、简单的“袋子距离”或者Levenshtein距离。我原本打算先计算一个距离矩阵（也就是100,000个字符串两两比较），然后用pyCluster进行层次聚类。但是在开始之前，我就遇到了一些内存问题。比如说，这个距离矩阵对numpy来说太大了。

aa = numpy.zeros((100000, 100000))
ValueError: array is too big.

这样做听起来合理吗？还是说我在这个任务中注定会遇到内存问题？谢谢你的帮助。

Answer 1

你需要用到矩阵吗？我猜你是想用矩阵来提高速度吧？

我有一个k-means聚类算法（而不是层次聚类算法），这个算法会根据需要计算节点之间的距离。不过，这个方法可能只适合快速计算距离的情况。而且你手上的数据比我多，但你也受限于内存的大小。

Answer 2

一百亿个元素可真是太多了。我对q-grams不太了解，但如果那个矩阵是稀疏的，也就是说大部分地方都是空的，那么你可以用大约20万个元素的字典来处理。

Answer 3

100,000 * 100,000 * 32位 = 40GB，这可是个很大的内存需求，所以你确实需要找其他方法。即使你能把这些数据放进内存，计算起来也会太慢。

一个常见且简单的解决办法是先从数据中随机抽取一小部分，进行聚类分析。找到这部分数据的聚类后，再把剩下的数据点放到最合适的聚类里。