使用Levenshtein距离进行文本聚类

Question

我有一组(2k - 4k)的小字符串(3-6个字符),我想将它们聚类.由于我使用字符串,以前的答案关于如何进行聚类(尤其是字符串聚类)？,告诉我,Levenshtein距离很适合用作弦乐的距离函数.此外,由于我事先并不知道群集的数量,因此分层聚类是要走的路而不是k-means.

虽然我以抽象的形式得到问题,但我不知道实际做什么的简单方法.例如,MATLAB或R是使用自定义函数(Levenshtein距离)实际实现层次聚类的更好选择.对于这两种软件,人们可以很容易地找到Levenshtein距离实现.聚类部分似乎更难.例如,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))

在这个例子中,我们在3组中人工创建了一组30个随机char(5)字符串(以"aa","bb"和"cc"开头).我们使用计算Levenshtein距离矩阵adist(...),并且我们运行heirarchal聚类hclust(...).然后我们将树形图切割成三个簇,cutree(...)并将簇ID附加到原始字符串.