键值对聚类

slhcrj9b  于 2021-06-03  发布在  Hadoop
关注(0)|答案(1)|浏览(347)

我有这个问题。我有一个非常大的键值对集合(以百万为单位),其中一个唯一的id作为键,一个字符串作为值(两个或多个键的字符串可能完全相似)。我必须将这些键值对分组在一起,因为组1包含一些id字符串对组2包含一些其他对等。分组需要在字符串之间的相似性上完成,这些字符串实际上是对的值。我已经实现了这些字符串之间的levenshtein距离,并将距离小于阈值距离的对分组在一起。我用传统的(非常糟糕的)方法实现了它:将每个字符串相互比较。
我需要一些如何优化这个技巧。我真的可以在hadoop中使用map reduce将键值对分组在一起吗?我认为map和reduce函数的输入是独立的,因此不能“分组”在一起。这是一个k-均值聚类问题吗?你能推荐一些其他更快更有效的方法吗?谢谢。

km0tfn4u

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的概念可能有助于提高您已有的解决方案的性能?

相关问题