r - 使用 Levenshtein 距离进行文本聚类

Question

我有一组 (2k - 4k) 小字符串(3-6 个字符)，我想将它们聚类。由于我使用字符串，以前的答案在 How does clustering (especially String clustering) work? , 告诉我 Levenshtein distance很适合用作字符串的距离函数。另外，由于我事先不知道集群的数量，hierarchical clustering是要走的路，而不是 k-means。

虽然我以抽象的形式得到了问题，但我不知道实际做这件事的简单方法是什么。例如，MATLAB 或 R 是使用自定义函数(Levenshtein 距离)实际实现层次聚类的更好选择。对于这两种软件，可以很容易地找到 Levenshtein 距离实现。聚类部分似乎更难。例如Clustering text in MATLAB计算所有字符串的距离数组，但我不明白如何使用距离数组来实际获得聚类。你们中的任何一位大师能否告诉我如何使用自定义函数在 MATLAB 或 R 中实现层次聚类？

Answer 1

这可能有点简单，但这里有一个代码示例，它在 R 中使用基于 Levenshtein 距离的层次聚类。

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)
rect.hclust(hc,k=3)
df <- data.frame(str,cutree(hc,k=3))

在这个例子中，我们人为地创建了一组 30 个随机 char(5) 字符串，分为 3 组(以“aa”、“bb”和“cc”开头)。我们使用 adist(...) 计算 Levenshtein 距离矩阵，并使用 hclust(...) 运行层次聚类。然后我们使用 cutree(...) 将树状图切割成三个簇，并将簇 ID 附加到原始字符串。