6

我正在尝试将层次聚类应用于我的数据集，该数据集由 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 时我才会收到错误。任何想法为什么？

4

2 回答 2

5

您可能真的用完了 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-11T23:55:01.127 回答
5

好吧，层次聚类对于大型数据集没有多大意义。在我看来，这实际上是一个教科书的例子。层次聚类的问题在于它并没有真正构建合理的集群。它构建了一个树状图，但是对于 14000 个对象，树状图变得几乎无法使用。并且很少有层次聚类的实现具有从树状图中提取合理聚类的非平凡方法。另外，在一般情况下，层次聚类非常复杂O(n^3)，这使得它很难扩展到大型数据集。

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

任何真正好的 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，那可能是一个不错的选择。

于 2012-04-12T05:34:53.130 回答