r - 在 R 中对非常大的数据集进行聚类

Question

我有一个由 70,000 个数值组成的数据集，表示从 0 到 50 的距离，我想对这些数字进行聚类；但是，如果我尝试经典的聚类方法，那么我必须建立一个 70,000X70,000 距离矩阵来表示数据集中每两个数字之间的距离，这不适合内存，所以我想知道是否有有什么聪明的方法可以解决这个问题而不需要进行分层抽样吗？我还尝试了 R 中的大内存和大分析库，但仍然无法将数据装入内存

Answer 1

70000并不算大。它不小，但也不是特别大...问题是面向矩阵的方法的可扩展性有限。

但是有很多聚类算法不使用矩阵，也不需要 O(n^2) (甚至更糟糕，O(n^3) )运行时。

您可能想尝试ELKI ，它具有出色的索引支持(尝试使用 SortTimeRecursive 批量加载的 R* 树)。索引支持使其速度更快。

如果您坚持使用 R，至少尝试一下 kmeans 和 fastcluster 软件包。 K-means 的运行时复杂度O(n*k*i)(其中 k 是参数 k，i 是迭代次数)； fastcluster 具有与 ELKI 中的 SLINK 算法相当的单链接聚类的 O(n) 内存和 O(n^2) 运行时实现。 (R“agnes”层次聚类将使用 O(n^3) 运行时和 O(n^2) 内存)。

实现很重要。通常，R 中的实现并不是最好的(恕我直言)，除了核心 R 之外，它通常至少具有有竞争力的数值精度。但 R 是由统计学家构建的，而不是数据挖掘者构建的。它的重点是统计表达能力，而不是可扩展性。所以作者不应该受到责备。对于大数据来说，这只是错误的工具。

哦，如果您的数据是一维的，则根本不要使用聚类。使用核密度估计。一维数据很特殊:它是有序的。任何将一维数据分解为整数的好算法都应该利用它来对数据进行排序。