Scipy中计算两两距离时的记忆错误

Question

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

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

但是我的程序在计算距离矩阵的时候给了我记忆错误

  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和4gb内存上运行它。 我也需要应用DBScan聚类，但这也需要距离矩阵作为输入。

任何建议都很感激。

编辑：我只有在打印Y时才会出错。有什么想法吗？

Answer 1

好吧，层次聚类对于大型数据集来说没什么意义。在我看来，这实际上是一个教科书式的例子。层次化集群的问题是它并没有真正构建合理的集群。它建立了一个树状图，但是有14000个对象，树状图变得几乎不可用。层次聚类的实现很少有非平凡的方法从树状图中提取敏感的聚类。另外，在一般情况下，层次聚类是复杂的O(n^3)，这使得它对大型数据集的伸缩性非常差。

DBSCAN技术上不需要距离矩阵。事实上，当使用距离矩阵时，它将变慢，因为计算距离矩阵已经是O(n^2)。即使这样，您也可以通过计算动态距离来保证DBSCAN的内存开销，而每次计算两次距离。DBSCAN可以访问每个点一次，因此除了对称增益外，使用距离矩阵几乎没有任何好处。从技术上讲，您可以使用一些简洁的缓存技巧来减少这种情况，因为DBSCAN还需要知道哪些对象低于epsilon阈值。当epsilon被合理地选择时，在计算距离矩阵的CPU开销相同的情况下，动态地管理邻居集将使用比O(n^2)少得多的内存。

任何真正好的DBSCAN实现（它的拼写都是大写，顺便说一句，因为它是缩写，而不是扫描）都应该支持索引结构，然后在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，那可能是个不错的选择。