时间戳

首页 > 解决方案 > 如何在R中向量化贪心算法？

r - 如何在R中向量化贪心算法？

问题描述

我正在编写一个 R 脚本，它实现了一个贪心算法来优化一个函数。作为一个简单的例子，假设我有一个正数向量要分布在 3 个集群中。我想最小化每个集群中的总集群内距离。我使用贪心算法，一次分配一个数字，并将每个数字放在该数字与集群中已有数字之间距离总和最小的集群中。这是实现该算法的 R 脚本：

n <- 100
set.seed(0)
x <- rnorm(n)
cluster <- integer(n)

total_distance <- function(c, x, cluster){
  if(!any(cluster == c)){
    total_dist <- 0
  } else{
    total_dist <- sum(abs(x[cluster == c] - x[which.min(cluster > 0)]))
  }
  return(total_dist)
}

for(i in 1:n){
  within_cluster_distances <- mapply(total_distance, 1:3,
                                     MoreArgs = list(x = x, cluster = cluster))
  cluster[i] <- which.min(within_cluster_distances)
}

> cluster
  [1] 1 2 3 1 2 3 2 2 2 1 1 3 3 2 2 2 2 3 1 3 2 1 2 1 2 1 1 3 3 2 2 3 2 3 1 1 1 2 1 2 1 1 2 3 3 3 3 1 1 2 2 2 1 3 2 2 1 2 3 3 2 2 3 2 3 2 3
 [68] 1 2 2 2 2 3 2 1 1 2 2 3 3 3 1 1 2 2 2 1 2 1 1 1 3 2 3 1 2 2 1 2 1

是否有可能（甚至可取）对循环进行矢量化以获得cluster矢量？当输出向量中的值依赖于该向量中的其他值时，我不知道如何向量化。

编辑：我意识到上面概述的贪心算法不是一种有效的聚类方法。上面描述的问题并不是我真正想要解决的问题。我的问题是关于在我的代码示例中对循环进行矢量化是否可行和有益。

标签： ralgorithmvectorizationgreedy

解决方案

另一种选择是使用stats::kmeans：

kmeans(x, 3)$cluster

检查哪个更紧密：

cldist <- function(v) sum(abs(outer(v, v, `-`)))

tapply(x, cluster, FUN=cldist)
#       1        2        3 
#1086.007 1132.614 1019.575 

tapply(x, kmeans(x, 3)$cluster, FUN=cldist)
#       1        2        3 
#234.8734 722.5750 374.7199

推荐阅读