java - 如何对hadoop map resuce作业的键使用相似度算法

Question

我需要实现以下问题：我正在获取类型的数据

public class Data{   
  private String key;
  private String valueData;
}

我需要编写一个 map reduce 作业来获取所有唯一键，每个键都有一个（随机）valueData。hadoop 听起来很简单，是的，我知道如何实现这一点。

但真正的问题是，我还需要减少所有“相似”键。并且输出应该是与dataValue之一相似的键之一

在 hadoop 中实现这一点的最佳方法（以及如何）是什么？我还希望能够灵活地更改相似度算法。

score 1 · Accepted Answer

看看这项MinHashing技术，它与 MapReduce 一起广泛用于此任务。

相似性度量是绑定的Jaccard，不确定是否有其他方法。但是，一旦您计算了近键，您就可以使用另一个指标来衡量它们之间的相似性，因为 minhashing 大大减少了您的搜索空间。

您可以在维基百科上阅读更多信息：http ://en.wikipedia.org/wiki/MinHash

Mahout 有一个MinHash聚类算法，你可以看看那里。它很容易理解，并具有多种散列算法。

score 0 · Accepted Answer

您基本上需要想出一个函数，f，这样，尽可能地：

f(A) = f(B) if and only if A and B are "similar"

现在，您能够遵守的严格程度完全取决于这些值的确切域是什么，以及您的相似性指标是什么，但这是目标。

例如，如果键是实数，那么我可能会选择f(x) = round(x). 对于非常接近的 x 值，很可能f(x)相同，但也可能不同，例如 2.45 和 2.55。但也许你可以允许这种“足够好”。

然后，您可以将减少步骤的关键作为此函数的输出。

我还要补充一点，对于特定的相似性指标和特定的聚类方法，还有许多其他复杂的技术——如果你提供更多关于你希望使用的指标类型的详细信息，也许我可以为你指出其中之一，或者“相似”键到底是什么。

2 回答 2