时间戳

首页 > 解决方案 > R levenshtein 距离中的聚类

r - R levenshtein 距离中的聚类

问题描述

我正在尝试使用 levenshtein 距离使用 kmeans 聚类。我很难解释结果。

   # courtesy: code is borrowed from the other thread listed below with some additions of k-means clustering 
      set.seed(1)
  rstr <- function(n,k){   # vector of n random char(k) strings
 sapply(1:n,function(i){do.call(paste0,as.list(sample(letters,k,replace=T)))})
  }

str<- c(paste0("aa",rstr(10,3)),paste0("bb",rstr(10,3)),paste0("cc",rstr(10,3)))
    # Levenshtein Distance
  d  <- adist(str)
rownames(d) <- str
hc <- hclust(as.dist(d))
plot(hc)

# to normalize the distances when there are unequal length sequences 
max<- max(d)
data<- d/max

k.means.fit <- kmeans(data, 3)
library(cluster)
clusplot(d, k.means.fit$cluster, main='Clustering',
     color=TRUE, shade=TRUE,
     labels=5, lines=0, col.p = "dark green")

那么，集群图是什么，我该如何解释它？我提到了他们讨论的其他线程，这些线程集中在两个主要组件上。 https://stats.stackexchange.com/questions/274754/how-to-interpret-the-clusplot-in-r

但不清楚如何解释这个数字以及为什么这些点在那个椭圆/集群中？有任何想法吗？谢谢！！

标签： rcluster-analysisk-meanslevenshtein-distanceunsupervised-learning

解决方案

这很简单。您将字符串构造为三组。您有十个以“aa”开头的字符串，十个以“bb”开头的字符串和十个以“cc”开头的字符串。在这些开始之后，字符串的其余部分是随机的。使用 Levenshtein 距离，您会期望这些以相同的前两个字母开头的字符串彼此靠近。当您查看层次聚类图时，很容易看到由字符串的前两个字母定义的三个主要组。当您使用 k=3 的 kmeans 时，您会得到相同的集群。您可以通过检查集群看到这一点

 k.means.fit$cluster
aagjo aaxfx aayrq aabfe aarju aamsz aajuy aafqd aagka aajwi bbmpm bbevr bbucs 
    1     1     1     1     1     1     1     1     1     1     3     3     3 
bbkvq bbuon bbuam bbtsm bbwlg bbbci bbnrk ccxhl cciqg ccmtc ccwiv ccjim ccxwk 
    3     3     3     3     3     3     3     2     2     2     2     2     2 
ccuyl ccski cctfs ccdgd 
    2     2     2     2

集群 1 是以“aa”开头的字符串，集群 2 以“cc”开头，集群 3 以“bb”开头。

推荐阅读