计算scipy中成对距离时的内存错误

我正在尝试将层次聚类应用于由14039个用户组成的数据集。每个矢量具有10个特征，其中每个特征基本上是由该用户标记的标签的频率。我使用Scipy API进行聚类。现在我需要计算这14039个用户之间的成对距离，并将距离矩阵传递给联动函数。计算scipy中成对距离时的内存错误

import scipy.cluster.hierarchy as sch 
    Y = sch.distance.pdist(allUserVector,'cosine') 
    set_printoptions(threshold='nan') 
    print Y

但我的程序给我的MemoryError在计算距离矩阵本身

File "/usr/lib/pymodules/python2.7/numpy/core/numeric.py", line 1424, in array_str 
    return array2string(a, max_line_width, precision, suppress_small, ' ', "", str) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 306, in array2string 
    separator, prefix) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 210, in _array2string 
    format_function = FloatFormat(data, precision, suppress_small) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 392, in __init__ 
    self.fillFormat(data) 
    File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 399, in fillFormat 
    non_zero = absolute(data.compress(not_equal(data, 0) & ~special)) 
MemoryError

任何想法如何解决这一问题？我的数据集是否太大？但我猜集群14K用户不应该太多，它应该导致内存错误。我在i3和4 Gb Ram上运行它。我也需要应用DBScan集群，但也需要距离矩阵作为输入。

任何建议表示赞赏。

编辑：只有当我打印Y时才会出错。任何想法为什么？

来源

2012-04-11 Maxwell

好吧，层次聚类对于大型数据集并没有多大意义。在我看来，它实际上大多是一本教科书的例子。层次聚类的问题是它并不真正构建明智的聚类。它构建树状图，但有14000个树状图变得几乎不可用。很少有层次聚类的实现方法从树形图中提取可感知的聚类有不平凡的方法。另外，在一般情况下，层次聚类的复杂性为O(n^3)，这使得它对于大型数据集来说真的很糟糕。

DBSCAN在技术上确实是而不是需要一个距离矩阵。实际上，当你使用距离矩阵时，将会是slow，因为计算距离矩阵已经是O(n^2)。即使如此，您仍然可以通过计算动态距离来计算DBSCAN的内存开销，代价是每次计算两次距离。 DBSCAN每访问一次，所以除了对称增益之外，使用距离矩阵几乎没有任何好处。从技术上讲，你可以做一些简洁的缓存技巧，甚至可以减少这种技巧，因为DBSCAN也只需要知道哪些对象低于epsilon阈值。当合理选择epsilon时，在计算距离矩阵的相同CPU成本下，即时管理邻居组将使用比O(n^2)少得多的内存。但是应该支持索引结构，然后运行在O(n log n)运行环境中.DBSCAN的任何一个非常好的实现（它是拼写全部大写，顺便说一句，因为它是一个缩写，而不是扫描）。

在http://elki.dbs.ifi.lmu.de/wiki/Benchmarking上，他们在110250对象数据集和8维上运行DBSCAN，非索引变量需要1446秒，索引只有219，这比索引编译快了大约7倍。（然而，这不是python）类似地，OPTICS的索引速度是它的5倍。他们在我的实验中的kmeans实现比WEKA kmeans快6倍，并且使用的内存少得多。他们的单链接层次聚类也是一个优化的实现。其实我目前看到的唯一一个并不是天真的O(n^3)矩阵编辑方法。如果你愿意超越python，那可能是一个不错的选择。

来源

2012-04-12 05:34:53

这可能是你真的用完了RAM。找出N个对象之间的成对距离意味着存储N^2个距离。在你的情况下，N^2将会是14039^2 = 1.97 * 10^8。如果我们假设每个距离只需要4个字节（这几乎肯定不是这种情况，因为它们必须保存在某种可能具有非恒定开销的数据结构中），这可以达到800兆字节。对于口译员来说，这是很多记忆。 32位体系结构只允许高达2 GB的进程内存，而您的原始数据占用了大约50％。随着数据结构的开销，你可能会看到比这更高的用法 - 我不能说多少，因为我不知道SciPy/numpy背后的内存模型。

我会尝试打破你的数据集成更小的集合，或不构建全距离矩阵。你可以把它分解成更易于管理的块（比如说，包含大约1000个元素的14个子集），并且在每个块和所有向量之间做最近邻居 - 然后你可以在任何时候将内存加载到内存中一次（14000 * 1000,14次而不是14000 * 14000次）。

编辑： agf在这两方面都是完全正确的：我错过了你的编辑，当它试图构建代表矩阵的巨型字符串时，问题可能就出现了。如果它正在打印浮点值，并且我们假设每个元素打印了10个字符，并且每个字符存储了一个字节的字符串，那么您仅仅为字符串查找了2 GB的内存使用情况。

来源

2012-04-11 23:55:01

我想你错过了他的编辑。只有在尝试打印整个距离矩阵时才会出错。它正在构建耗尽他的记忆的巨大弦乐。 – agf 2012-04-12 00:09:24

我做到了。答案更新以反映编辑。谢谢！ – 2012-04-12 04:38:08

预先编辑的答案对于相关问题确实很有帮助。请保留这个答案，以便我可以将其他问题链接到它。 – ximiki 2018-01-23 16:36:29

计算scipy中成对距离时的内存错误

回答

相关问题