15

我想通过 q​​-gram 距离或简单的“袋子距离”或 Python 中的 Levenshtein 距离来聚集约 100,000 个短字符串。我打算填写一个距离矩阵（100,000 选择 2 个比较），然后使用pyCluster进行层次聚类。但我什至在起步之前就遇到了一些记忆问题。例如，距离矩阵对于 numpy 来说太大了。

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

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

4

4 回答 4

8

100,000 * 100,000 * 32bits = 40 GBytes，这将是很多RAM，所以是的，你需要找到另一种方法。（即使您可以将这些数据放入内存中，计算也会花费太长时间。）

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

于 2010-11-22T02:35:31.663 回答
3

100 亿个元素是非常多的。我不知道 q-gram，但如果该矩阵是稀疏的，您可以使用 200,000-ish 元素字典。

于 2010-11-22T02:38:28.693 回答
2

你需要矩阵吗？我假设您想使用矩阵来提高速度？

我有一个 k-means 聚类算法（而不是分层聚类算法），它可以根据需要计算节点距离。不过，可能仅适用于快速距离指标。而且您拥有的数据比我多——但您受到内存限制的限制。

于 2010-11-23T18:20:46.283 回答
2

  1. 机器学习中有一种叫做 Embedding 的方法，它原则上可以使用O (n+m) 内存而不是O (n*m) (n=10^5 items, m=10^ ) 来搜索这个问题的解决方案5个特点）。不幸的是，我不知道在 O(m+n) 中实现的可用源代码。看：

    共现数据的欧几里得嵌入。Amir Globerson、Gal Chechik、Fernando Pereira 和 Naftali Tishby。机器学习研究杂志, JMLR, 8 (Oct), 2007. pdf / Matlab 代码

  2. 可能还有其他解决方案。我认为你应该在机器学习人士的论坛上问这个问题，例如https://stats.stackexchange.com/，或者更具体的语言处理： http: //metaoptimize.com/qa/。

于 2011-10-09T18:18:34.607 回答