在Python中聚集~100000个短字符串

Question

我想用q-gram距离或简单的“bag-distance”或者Python中的Levenshtein距离来聚类大约100000个短字符串。我计划填写一个距离矩阵（100000个选择2比较），然后用pyCluster进行分层聚类。但我在出发前就遇到了一些记忆问题。例如，距离矩阵对于numpy来说太大了。在

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

这样做似乎是合理的吗？还是我注定要在这项任务中出现记忆问题？谢谢你的帮助。在

Answer 1

你需要矩阵吗？我想你想用矩阵来计算速度？在

我有一个k-means聚类算法（而不是层次聚类算法），它根据需要计算节点距离。不过，可能只适用于快速距离测量。你的数据比我多，但你受内存限制。在

Answer 2

100000*100000*32bit=40GB，这相当于RAM的一大部分，所以是的，你需要找到另一种方法。（即使您可以将这些数据放入内存，计算也会花费太长时间。）

一个常见且简单的快捷方式是对数据的一个随机子集进行聚类，在找到该子集的簇之后，只需将其余的点放入最适合它们的簇中。在

Answer 3

100亿个元素是非常多的。我不知道q-grams，但是如果矩阵是稀疏的，你可以使用200000的元素dict