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

Question

我正在尝试将分层聚类应用于我的数据集,该数据集由14039个用户向量组成.每个向量具有10个特征,其中每个特征基本上是由该用户标记的标签的频率.我正在使用Scipy api进行聚类.现在我需要计算这些14039用户之间的成对距离,并将tis距离矩阵传递给连接函数.

  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时才会收到错误.有什么想法吗？

Answer 1

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

我会尝试将您的数据集分成更小的集合,或者不构建完整的距离矩阵.您可以将其分解为更易于管理的块(例如,大约1000个元素的14个子集),并在每个块和所有向量之间进行最近邻居 - 然后您正在考虑在任何内存中加载一个数量级的内存.一次(14000*1000,14次而不是14000*14000一次).

编辑: agf在两个方面完全正确:我错过了你的编辑,当它试图构建代表你的矩阵的巨大字符串时,可能会出现问题.如果它正在打印浮点值,并且我们假设每个元素打印10个字符,并且字符串每个字符存储一个字节,那么您只需查看字符串的2 GB内存使用量.

Answer 2

好吧，对于大型数据集而言，分层聚类没有太大意义。我认为这实际上主要是教科书示例。分层集群的问题在于它实际上并没有构建合理的集群。它建立了树状图，但是有了14000个对象，树状图就变得非常不可用。很少有分层聚类的实现具有非平凡的方法来从树状图中提取出明智的聚类。另外，在一般情况下，层次聚类非常复杂O(n^3)，这使其对大型数据集的扩展确实不利。

DBSCAN技术上并没有需要的距离矩阵。实际上，当您使用距离矩阵时，它会很慢，因为计算距离矩阵已经是O(n^2)。即便如此，您也可以O(n^2)通过动态计算距离而以每次两次计算距离为代价来保证DBSCAN 的内存成本。DBSCAN访问每个点一次，因此使用距离矩阵几乎没有好处，除了对称增益。从技术上讲，您可以做一些巧妙的缓存技巧来减少这种情况，因为DBSCAN还只需要知道哪些对象低于epsilon阈值。当合理选择epsilon时，与O(n^2)以相同的CPU成本计算距离矩阵相比，即时管理邻居集将使用更少的内存。

DBSCAN的任何真正好的实现（由于是缩写，所以都是大写，btw，因为不是扫描），但是应该支持索引结构，然后在O(n log n)运行时运行。

在http://elki.dbs.ifi.lmu.de/wiki/Benchmarking上，他们在110250个对象数据集和8个维度上运行DBSCAN，而未索引的变体需要1446秒，而索引的变体仅需219秒。大约快7倍，包括索引建立。（但是，它不是python）类似地，使用索引的OPTICS快5倍。在我的实验中，它们的kmeans实现比WEKA kmeans快6倍左右，并且使用的内存更少。他们的单链接层次集群也是一种优化的O(n^2)实现。实际上，到目前为止，我所看到的唯一的方法不是天真的O(n^3)矩阵编辑方法。如果您愿意超越python，那可能是一个不错的选择。