如何使用相似的算法

我需要實現以下問題Hadoop的地圖毒害的耐受力工作的鍵：我得到類型的數據如何使用相似的算法

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

我需要寫一個映射精簡工作得到所有唯一鍵，其中每個鍵都有一個（隨機）valueData。對於hadoop來說聽起來很簡單，是的，我知道如何實現這一點。

但真正的問題是，我還需要減少所有「」類似的「鍵。和輸出應符合的dataValue

一個什麼是Hadoop中以implemet最好的辦法（以及如何）的類似關鍵之一？我還想要改變相似性算法的靈活性。

2012-11-02 Julias

感謝您的意見。我只想澄清更基本的問題。當我使用Map/Reduce Reduce時，所有鍵都與數值列表相同。如何「更新」默認映射縮小比例關鍵字，因此只有一個類似的鍵會出現在縮小功能中？我正在尋找簡單的Java Map/Reduce代碼 – Julias

看看MinHashing技術，它被廣泛用於MapReduce這個任務。

相似性度量綁定到Jaccard，不確定是否有其他方法。然而，一旦你計算了密鑰附近，你可以使用另一個度量來度量它們之間的相似度，因爲minhashing大大減少了你的搜索空間。

你可以閱讀更多關於維基百科：http://en.wikipedia.org/wiki/MinHash

亨利馬烏有MinHash聚類算法，你可以去看看那裏。它很容易理解並且具有幾個哈希算法。

2012-11-02 22:07:04

謝謝，這很好，我會看看mahout的使用情況。如果我正在編寫組合鍵並覆蓋方法-equals-和-compareTo-方法，但不覆蓋-hashCode-我的代碼是否能正確工作？ – Julias

你需要矢量化你的密鑰，我假設你的密鑰是文本，所以你可以使用shingling（http：// en。wikipedia.org/wiki/W-shingling）使搜索更加模糊。 Mahout負責矢量化你的文本鍵，然後可以聚集在他們身上。 –

你基本上需要拿出一個功能，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。但是，也許你可以允許這個「足夠好」的性。

然後，你可以讓你的減少步驟的關鍵，這個功能的輸出。

我還會補充一點，還有很多其他複雜的技術可用於特定的相似性度量和特定的聚類方法 - 如果您更詳細地瞭解您所使用的度量類型，我可以指出其中的一種方法希望能夠使用，或者「相似」鍵究竟是什麼。

2012-11-02 21:19:37

回答