基于Levenshtein距离的文本聚类

Question

我有一组(2k - 4k)的小字符串(3-6个字符)，我想对它们进行集群。由于我使用字符串，以前在集群(特别是字符串集群)是如何工作的？上的答案告诉我，Levenshtein距离很适合用作字符串的距离函数。而且，由于我事先不知道集群的数量，所以层次聚类是要走的路，而不是k-方法。

虽然我得到了抽象形式的问题，但我不知道如何才能真正做到这一点。例如，MATLAB或R是使用自定义函数(Levenshtein距离)实现分层聚类的更好的选择。对于这两个软件，都可以很容易地找到Levenshtein远程实现。聚类部分似乎更难。例如，MATLAB中的聚类文本计算所有字符串的距离数组，但我无法理解如何使用距离数组实际获得集群。你们中的任何一位专家能告诉我如何用自定义函数在MATLAB或R中实现分层聚类吗？

Answer 1

这可能有点简单，但这里有一个代码示例，它使用基于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个组(以"aa“、"bb”和“cc”开始)创建一个由30个随机字符(5)组成的字符串集。利用adist(...)计算了Levenshtein距离矩阵，并利用hclust(...)进行了传递性聚类。然后，我们用cutree(...)将树状图分成三个簇，并将簇id附加到原始字符串中。

Answer 2

埃尔基包括Levenshtein距离，并提供了多种高级聚类算法，例如光学聚类。

作为其工作的一部分，Felix Stahlberg提供了文本聚类支持：

Stahlberg，F.，Schlippe，T. 通过跨语言的字对音素对齐分词。。 口语技术讲习班，2012年IEEE。IEEE，2012年。

我们当然希望得到更多的捐助。

Answer 3

虽然答案在一定程度上取决于字符串的意义，但一般来说，您的问题是通过序列分析系列技术来解决的。更具体地说，最优匹配分析(OMA)。

大多数情况下，OMA分三个步骤进行。首先，你定义你的序列。从您的描述中，我可以假设每个字母都是一个单独的“状态”，这是一个序列中的构建块。其次，您将使用几种算法中的一种来计算数据集中所有序列之间的距离，从而获得距离矩阵。最后，您将将该距离矩阵输入到一个聚类算法中，例如分层聚类或围绕Medoids (PAM)进行分区，由于有关集群质量的附加信息，该算法似乎越来越受欢迎。后者指导您选择集群的数量，这是序列分析中的几个主观步骤之一。

在R中，功能丰富的最方便的软件包是TraMineR，网站可以找到这里。它的用户指南是非常容易访问的，而且开发人员在这方面也或多或少地很活跃。

您可能会发现，集群并不是最困难的部分，只是决定集群的数量。TraMineR指南显示，语法非常直观，而且基于视觉序列图的结果很容易解释。下面是用户指南中的一个示例：

clusterward1 <- agnes(dist.om1, diss = TRUE, method = "ward")

dist.om1是OMA获得的距离矩阵，聚类隶属度包含在clusterward1对象中，可以任意绘制、作为变量进行编码。diss=TRUE选项表示数据对象是不同的(或距离)矩阵。别紧张，嗯？最困难的选择(不是语法上的，而是方法上的)是选择适合您特定应用的正确的距离算法。一旦你有了它，能够证明你的选择是正确的，剩下的就很容易了。祝好运!