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

Question

我正在编写一个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矢量？当输出向量中的值取决于该向量中的其他值时，我不知道如何向量化。

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

Answer 1

另一个选择是使用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