我有这个问题。我有一个非常大的键值对集合（以百万为单位），其中一个唯一的id作为键，一个字符串作为值（两个或多个键的字符串可能完全相似）。我必须将这些键值对分组在一起，因为组1包含一些id字符串对组2包含一些其他对等。分组需要在字符串之间的相似性上完成，这些字符串实际上是对的值。我已经实现了这些字符串之间的levenshtein距离，并将距离小于阈值距离的对分组在一起。我用传统的（非常糟糕的）方法实现了它：将每个字符串相互比较。
我需要一些如何优化这个技巧。我真的可以在hadoop中使用map reduce将键值对分组在一起吗？我认为map和reduce函数的输入是独立的，因此不能“分组”在一起。这是一个k-均值聚类问题吗？你能推荐一些其他更快更有效的方法吗？谢谢。
1条答案
按热度按时间km0tfn4u1#
拼写检查器使用burkhard-keller树（bk-tree），这里有一个例子https://github.com/mkarlesky/csharp-bk-tree. 这在根据现有列表测试新词时非常快，但也给出了一个“距离”度量，该度量基于将字符串更改为下一个字符串所需的操作数。与简单的“contains”测试不同，它提供了一种组织可用选项的方法。您可以在此处阅读更多信息：http://blog.notdot.net/2007/4/damn-cool-algorithms-part-1-bk-trees. 我怀疑你可以利用距离来帮助聚类。
我想关于bk树的主要事情是你可以继续使用levenshtein距离。但也许你已经用过了？这种技术不适合像k-means那样挑选任意数量的聚类。但我确实看到了一篇有趣的文章，内容是在k-means的上下文中利用一些新的并行处理，这可能会帮助您在c中加快速度：
http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40
这个例子没有使用字符串，但是我想asparallel的概念可能有助于提高您已有的解决方案的性能？