键值对的聚类
我有这个问题。我有一个非常大的键值对集(以百万为单位)，其中一个唯一的id作为键，一个字符串作为值(对于2个或更多的键，字符串可能完全相似)。我必须将这些键值对分组在一起，因为组1包含一些id-string对，组2包含一些其他对，等等。分组需要根据字符串之间的相似性进行，这些字符串实际上是这些对的值。我已经实现了这些字符串之间的Levenshtein距离，并将距离小于阈值距离的对组合在一起。我以传统的(非常糟糕的)方式实现了它:将每个字符串相互比较。
我需要一些关于如何优化这方面的技巧。我可以在Hadoop中使用Map-Reduce将键值对分组在一起吗？我认为map和reduce函数的输入是独立的，因此不能“组合”在一起。这是一个k-means聚类问题吗？你能推荐一些其他更快更有效的技术吗？谢谢。
回答 1
Stack Overflow用户
发布于 2013-07-17 02:41:32
拼写检查器使用伯克哈德-凯勒树(BK-树)在这里找到一个例子https://github.com/mkarlesky/csharp-bk-tree。这在根据现有列表测试新词时非常快，但也给出了一个“距离”度量，该度量基于将字符串更改为下一个字符串所需的操作数量。与提供布尔值的简单“包含”测试不同，它为您提供了一种组织可用选项的方法。你可以在这里阅读更多关于它的内容：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的概念会对您已经拥有的解决方案的性能有所帮助。
https://stackoverflow.com/questions/17684347
复制相似问题
腾讯云开发者
