r - 我自己的 R 中的 K-means 算法

Question

我是 R 编程的初学者，我在 R 中做这个练习作为编程的介绍。我已经在 R 中实现了自己的 K 均值实现，但在一个点上停留了一段时间:我需要达成共识，算法会迭代，直到找到每个簇的最优中心。

这是没有迭代的原始算法。它只是从整个数据中随机取一个数据点作为中心，这个数由k定义。

Centroid_test=data[sample(nrow(data), k), ]
x = Centroid_test
y = data
m=apply(data,1,function(data)   (apply(Centroid_test,1,function(Centroid_test,y)
dist(rbind(Centroid_test,data)),data)))
colnames(m)=rownames(y)
minByCol <- apply(m, MARGIN=2, FUN=which.min)
minByColdf=as.data.frame(minByCol)
MasterDataframe=data.frame(data,minByColdf)
Sort_Master=MasterDataframe[ order(MasterDataframe[,3], MasterDataframe[,3]), ]
res=data.frame(Sort_Master)
cen=Centroid_test
rownames(cen)=1:k
res
cen

因此，我有一些聚类中心和每个聚类伴随的数据点，但它不是最佳中心。我怎样才能找到好的中心？

我的尝试如下。我知道我必须迭代上面的代码，让我们说 kmax 次，直到它满足停止迭代的条件，从而给出适合数据的最佳集群:

for (n in 1:kmax){

  if (condition)
    break;
}

但是我该如何定义条件呢？在阅读了一些关于 k 均值的知识之后，一个想法是找到一个值最接近其组均值的中心。我写了这段代码:

kn=1
group=subset(res, res[,3] == 1)
mean(group$x)
mean(group$y)
cen[kn,]$x
cen[kn,]$y

但我不知道如何在代码中写出“越相似的意思”。我发现的另一个想法是找到距离最小的集群从每个点。我想不出我怎么能成功地将它写入代码。

如果您能告诉我如何操作或分享想法，那将非常有帮助!

提前致谢!

编辑:

澄清一下:

所以，我想要做的是做某种算法，根据每个簇的中心和点之间的距离找到最优的簇中心。在阅读了有关 k-means 算法的更多信息后，我发现有 Forgy/Lloyd 算法、MacQueen 算法和 Hartigan & Wong 算法。每个人都试图用不同的方法找到最佳中心。

上面的代码分配随机点作为中心，然后计算每个点到每个中心的距离，并且与一个点的距离最小的点被分配到该点簇。 cen 包含每个簇的中心，res 给出分配给每个簇的所有点(这就是第三列的用途)。

我的想法是先计算出分组后每个点到中心的距离，然后保存到dataframe或者其他什么的。下一步将是重新做一遍:找到新的随机中心，再次为每个中心分配点，形成聚类，最后计算点和中心之间的距离，再次保存它们。最后会有一个数据框或矩阵有很多(例如在 100 次迭代之后)，距离然后我们可以找到每个点和聚类中心之间距离最小的中心。这些与其他点距离最小的点是簇的最佳中心。

虚拟数据:

y=rnorm(500,1.65)
x=rnorm(500,1.15)

data=cbind(x,y)

运行完上面的代码后，运行plot来查看集群的中心:

plot(data)
points(cen, pch=21,bg=23)

Answer 1

计算欧氏距离的函数:

euclid <- function(points1, points2) {
  distanceMatrix <- matrix(NA, nrow=dim(points1)[1], ncol=dim(points2)[1])
  for(i in 1:nrow(points2)) {
    distanceMatrix[,i] <- sqrt(rowSums(t(t(points1)-points2[i,])^2))
  }
  distanceMatrix
}

K均值算法使用上面的欧氏距离:

K_means <- function(x, centers, distFun, nItter) {
  clusterHistory <- vector(nItter, mode="list")
  centerHistory <- vector(nItter, mode="list")

  for(i in 1:nItter) {
    distsToCenters <- distFun(x, centers)
    clusters <- apply(distsToCenters, 1, which.min)
    centers <- apply(x, 2, tapply, clusters, mean)
    # Saving history
    clusterHistory[[i]] <- clusters
    centerHistory[[i]] <- centers
  }

  list(clusters=clusterHistory, centers=centerHistory)
}

准备数据:

test=data # A data.frame
ktest=as.matrix(test) # Turn into a matrix
centers <- ktest[sample(nrow(ktest), 5),] # Sample some centers, 5 for example

结果

res <- K_means(ktest, centers, euclid, 10)