使用Levenshtein距离进行文本聚类

Question

使用Levenshtein距离进行文本聚类

rmatlabcluster-analysislevenshtein-distancehierarchical-clustering

37

我有一组（2k - 4k）小字符串（3-6个字符），想要对它们进行聚类。由于使用了字符串，之前在如何进行聚类（特别是字符串聚类）中的答案告诉我，Levenshtein距离是用作字符串距离函数的好方法。而且，由于我事先不知道聚类的数量，层次聚类是正确的选择，而不是k-means。

尽管我理解了这个问题的抽象形式，但我不知道实际操作起来最简单的方法是什么。例如，MATLAB或R哪个更适合使用自定义函数（Levenshtein距离）实现分层聚类。对于这两种软件，人们可以很容易地找到Levenshtein距离的实现。但聚类部分似乎更难。例如，在MATLAB中聚类文本计算所有字符串的距离数组，但我不知道如何使用距离数组来实际获得聚类结果。你们任何一位专家能否向我展示如何在MATLAB或R中使用自定义函数实现分层聚类呢？

- Alexandros

2

这取决于您使用的分层聚类类型。单链接和完全链接 HC可以仅使用距离矩阵执行，因此一旦您通过任何方法获得了该矩阵，则常规聚类函数（例如hclust）应该可以正常工作。另一方面，平均链接或Ward方法需要在每个步骤重新计算距离，因此它们将更加复杂。 - gung - Reinstate Monica

那么在MATLAB中，Z = linkage(Y,method) 将会使用预先计算的距离矩阵和完全方法，是吗？ - Alexandros

我只能猜测答案是“是”。我很久没有使用MATLAB了，而且我从未使用过它进行任何聚类。 - gung - Reinstate Monica

4个回答

4

ELKI 包含 Levenshtein 距离，并提供了广泛的高级聚类算法，例如 OPTICS 聚类。

文本聚类支持由 Felix Stahlberg 贡献，作为他在以下工作中的一部分：

Stahlberg, F., Schlippe, T., Vogel, S., & Schultz, T.
通过跨语言单词到音素的对齐进行单词分割。
2012 年 IEEE 口语技术研讨会 (SLT)。IEEE，2012年。

我们当然欢迎额外的贡献。

- Erich Schubert

4

我听说过ELKI，我的许多同事都在使用它。如果你想要投入必要的时间，ELKI是一个有效的选择。但是，在ELKI中，我需要重载许多Java类才能初步查看结果，而R代码只有10行。即使基于非最优算法，快速查看初始结果也比浪费15-30天来学习一个框架，只是为了看到我的方法是否正确更好。因此，现在使用R是可以的。以后，ELKI可能是一个更好的解决方案。 - Alexandros

1

ELKI需要一个脚本API，我一直在考虑添加Groovy，但还没有时间去做。对于R，由于性能问题，我并不是太满意。任何不是矩阵的东西都很慢，而且矩阵操作的规模为O(n^2)或更差。如果我想快速尝试一些东西，我通常发现scipy是最好的脚本语言，而且往往由于Cython代码的缘故，它的速度令人惊讶。 - Erich Schubert

3

虽然答案在一定程度上取决于字符串的含义，但通常您的问题可以通过序列分析技术家族来解决。更具体地说，是最优匹配分析（OMA）。

通常，OMA分为三个步骤。首先，您需要定义序列。根据您的描述，我可以假设每个字母都是一个单独的“状态”，也就是序列中的构建块。其次，您将使用多种算法之一来计算数据集中所有序列之间的距离，从而获得距离矩阵。最后，您将把该距离矩阵输入到聚类算法中，例如分层聚类或分区回路中心（PAM），后者由于提供有关群集质量的附加信息而越来越受欢迎。后者指导您选择群集数量，在序列分析中的几个主观步骤之一。

在R中，最方便的软件包是TraMineR，它具有大量功能，网站可以在此处找到here。其用户指南非常易于访问，并且开发人员在SO上也更活跃。

你可能会发现，聚类并不是最困难的部分，除了决定聚类数量。 TraMineR 的指南显示其语法非常简单直观，并且基于可视化序列图易于解释结果。以下是用户指南中的示例：

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

dist.om1是通过OMA获得的距离矩阵，聚类成员包含在clusterward1对象中，您可以进行任何操作：绘图、重新编码为变量等。选项diss=TRUE表示数据对象是不相似性（或距离）矩阵。简单吧？最困难的选择（不是语法上的，而是方法论上的）是选择适合您特定应用的正确距离算法。一旦您做出了这个选择并能够证明其正确性，其他事情就很容易了。祝好运！

- Maxim.K

我已经研究了序列模式匹配，但定义字母表似乎有些过度，因为distance(abc,abd) = distance(abc,abf)。所以为什么要定义一个字典呢？因为我们只检查不等式f!=c是否成立，这与e!=c是相同的。尽管如此，还是要为你的努力加上一分。 - Alexandros

1

字母表是自动定义的，会对所有可能的状态进行取样。当然你可以对它进行修改。普通的OM算法会在(abc,abd)和(abc,abf)之间分配完全相同的距离。这个距离基于两种情况下的一个替换操作，其成本是相同的，假设你没有给这些特定的字母分配差异化的成本。当然，如果你的问题和另一种解决方案一样简单，那就没问题。你也可以使用PAM代替HC。 - Maxim.K

2

如果您想要清晰地了解如何使用分区聚类（这肯定会更快）来解决您的问题，请查看这篇论文：《使用聚类算法进行有效的拼写检查方法》。

作者解释了如何使用修改版（类似于PAM的）iK-Means对字典进行聚类。

祝你好运！

- TheVoiceInMyHead

那么，R是否实现了这个修改版（类似于PAM的）iK-Means？这种方法是否自动提取聚类数？如果没有，即使它真的是最先进的技术，我也无法自己实现聚类算法。此外，慢的部分必须是距离矩阵而不是聚类。 - Alexandros

... 仍然对您的贡献加一 - Alexandros

是的，它会自动获取聚类数量。据我所知，目前还没有R版本，不过实现起来应该不难（在Matlab中只需大约80行代码）。 - TheVoiceInMyHead

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jlhoward · Accepted Answer

这里有一个使用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组由5个随机字符组成的字符串，并将它们分成三组（以“aa”、“bb”和“cc”开头）。我们使用adist(...)计算Levenshtein距离矩阵，使用hclust(...)运行层次聚类。然后，我们使用cutree(...)将树形图切成三个簇，并将簇id附加到原始字符串上。