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

Question

我有一个包含70,000个数字值的数据集，表示距离从0到50，我想对这些数字进行聚类。然而，如果我尝试使用传统的聚类方法，那么我将不得不建立一个70,000X70,000的距离矩阵，表示数据集中每两个数字之间的距离，这将无法在内存中完成，因此我想知道是否有任何聪明的方法来解决这个问题，而不需要进行分层抽样？我还尝试了R中的bigmemory和big analytics库，但仍无法将数据装入内存。

- DOSMarter

---

这个编程解决方案（使用cluster::clara）是否相关/有用？ - jbaums

不是真的，因为问题在于距离矩阵太大了，无法适应任何内存。 - DOSMarter

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是由统计学家构建的，而不是由数据挖掘者构建的。它的重点在于统计表达性，而不在于可扩展性。因此，作者并不需要受到责备。这只是用于大数据的错误工具。

哦，如果您的数据是1维的，请根本不要使用聚类。使用核密度估计。1维数据很特殊：它是有序的。将1维数据分成间隔的任何好算法都应利用您可以对数据进行排序的事实。

- Has QUIT--Anony-Mousse

Answer 2

您可以使用 kmeans 来计算大量数据的中心（1000、2000 等），并在这些中心的坐标上执行分层聚类方法。这样，距离矩阵将更小，通常适用于此类数据。

## Example
# Data
x <- rbind(matrix(rnorm(70000, sd = 0.3), ncol = 2),
           matrix(rnorm(70000, mean = 1, sd = 0.3), ncol = 2))
colnames(x) <- c("x", "y")

# CAH without kmeans : dont work necessarily
library(FactoMineR)
cah.test <- HCPC(x, graph=FALSE, nb.clust=-1)

# CAH with kmeans : work quickly
cl <- kmeans(x, 1000, iter.max=20)
cah <- HCPC(cl$centers, graph=FALSE, nb.clust=-1)
plot.HCPC(cah, choice="tree")

- Victorp

---

使用您的方法并运行cah <- HCPC(cl$centers, graph=FALSE, nb.clust=-1)后，我得到了这个错误：Error in catdes(data.clust, ncol(data.clust), proba = proba, row.w = res.sauv$call$row.w.init) : object 'data.clust' not found。 - Pie-ton

Answer 3

另一个非矩阵导向的方法，至少用于可视化大数据中的聚类，是唐等人（2016年）提出的largeVis算法。不幸的是，由于缺乏包维护，largeVis R软件包已经在CRAN上被弃用，但是可以通过其gitHub存储库编译一个（维护的？）版本（需要安装Rtools）。

library(devtools)     
install_github(repo = "elbamos/largeVis")

该软件包也有Python版本。底层算法使用分割树和邻域细化来查找每个观测值的K个最相似实例，然后将结果邻域网络投影到dim较低的维度中。它已经在C++中实现，并使用OpenMP（如果编译时支持）进行多处理；因此，它已经足够快地对我测试过的任何较大数据集进行聚类。

- martin