如何减少Prado用于R中大数据的k-means框架中的内存使用？

Question

我试图验证普拉多用于聚类交易策略的k-means框架，该框架基于his paper中的回报相关矩阵，使用R表示大量策略，比如1000。

他试图在所有可能的k和多个初始化上使用两个for循环找到k-means的最优k和最优初始化，即k从2变为N-1，其中N是策略的数量。

问题是运行k-means意味着很多次，尤其是那么多群集是内存穷举的，而我的计算机m3medium我使用的AWS实例都能够完成这项工作。 （4 GB RAM，尽管在AWS上有较少的后台RAM消耗过程。）

所以，非常高兴，任何想法如何处理这个内存问题？或者至少如何估算所需的记忆量作为所用策略数量的函数？

我已经尝试了包biganalytics及其bigkmeans功能，但这还不够。我也知道有更高的RAM AWS实例，但我想确保我的代码在切换到这样的实例之前是最佳的。我也试图限制使用的集群数量，这确认它是主要的内存消耗问题，但我不想坚持这样的解决方案（也不与更好的AWS实例结合）。

在AWS上正确执行的最高策略数量约为500。

内存优化代码的主要部分如下：

D <- nrow(dist)
seq.inits <- rep(1:nr.inits,D-2)
seq.centers <- rep(2:(D-1),each = nr.inits)
KM <- mapply(function(x,y){
  set.seed(x+333)
  kmeans(dist, y)
},seq.inits,seq.centers)

dist是策略'返回'相关 - 距离矩阵（即列数等于行数，以及其他属性），nr.inits是初始化的数量。两者都是输入变量。之后，使用轮廓分数确定最佳聚类，并且如果需要可能重新聚类。

我知道距离矩阵不适合k-means的输入，而且我也知道数据挖掘问题，所以请不要解决这些问题。

我上面提到的问题是：

1. 是否有可能减少内存使用量，以便我能够在m3.medium AWS实例上运行1000个策略？
2. 是否有可能至少根据使用的数字策略估算内存使用量？ （假设我尝试2:(N-1)集群。）

实际上，第二个问题，最好是在优化之后，对我来说更重要。因为我想尝试甚至比“仅”1000更多的策略。

预先感谢您的回答！

Answer 1

即使您没有使用R，也不会同时存储所有结果。此外，我认为您没有正确使用kmeans，因为它需要您的输入数据，而不是跨距矩阵。同样，您不需要分配所有seq.centers。你提到了剪影索引，它可以用cluster::silhouette计算，所以：

library(cluster)
data(ruspini) # sample data included in the cluster package

由于您的数据没有变化，您可以预先计算跨距矩阵：

dm <- dist(ruspini)

您所需工作流程的一次“迭代”将是：

km <- kmeans(ruspini, 2) # try 2 clusters
score <- mean(cluster::silhouette(km$cluster, dist = dm)[,3L])

你想要相同的k集群的几个随机开始：

num_starts <- 2L
scores <- sapply(seq_len(num_starts), function(ignored) {
  km <- kmeans(ruspini, 2)
  mean(cluster::silhouette(km$cluster, dist = dm)[,3L])
})

请注意，仅保存分数，而不显示群集结果。您还需要不同的k值：

max_k <- 3L
num_starts <- 2L
scores <- sapply(2L:max_k, function(k) {
  repetitions <- sapply(seq_len(num_starts), function(ignored) {
    km <- kmeans(ruspini, k)
    mean(cluster::silhouette(km$cluster, dist = dm)[,3L])
  })

  max(repetitions)
})

对于k的每个值，我们只返回所有重复的最大分数（同样，通过不存储所有内容来节省空间）。

为了使一切都可以重现，你可以在顶部使用set.seed;使用它一次就足以进行顺序计算。也许你想利用并行化，但是你可能需要更多的RAM（很难说多少，因为有很多因素在起作用），你需要注意重现性。如果您想尝试一下，最终的脚本可能如下所示：

library(doParallel)
library(cluster)

data(ruspini)
dm <- dist(ruspini)

max_k <- 3L
num_starts <- 2L

# get random seeds for each execution
RNGkind("L'Ecuyer")
set.seed(333L)
current_seed <- .Random.seed # initialize
seeds <- lapply(2L:max_k, function(ignored) {
  lapply(seq_len(num_starts), function(also_ignored) {
    seed <- current_seed
    current_seed <<- parallel::nextRNGStream(current_seed)
    # return
    seed
  })
})

workers <- makeCluster(detectCores())
registerDoParallel(workers)

scores <- foreach(k = 2L:max_k, k_seeds = seeds, .combine = c, .packages = "cluster") %dopar% {
  repetitions <- sapply(seq_len(num_starts), function(i) {
    set.seed(k_seeds[[i]])
    km <- kmeans(ruspini, k)
    mean(cluster::silhouette(km$cluster, dist = dm)[,3L])
  })

  max(repetitions)
}

stopCluster(workers); registerDoSEQ(); rm(workers)

names(scores) <- paste0("k_", 2L:max_k)