使用MapReduce的找到用戶之間的共同項目

Question

假設我有以下的用戶/項目集合，其中的項目也可能是

{ "u1", "item" : [ "a", "a", "c","h" ] } 
{ "u2", "item" : [ "b", "a", "f" ] } 
{ "u3", "item" : [ "a", "a", "f" ] } 

我想找到一個MapReduce的算法爲每個用戶重複（如用戶1），其將計算一些這樣

{ "u1_u2", "common_items" : 1 } 
{ "u1_u3", "common_items" : 2 } 
{ "u2_u3", "common_items" : 2 } 

它基本上發現項集的每對的交叉點，並認爲作爲重複的新項目的每一對用戶之間的共同項目的數目。我是mapreduce的新手，我該怎麼做map-reduce呢？

Answer 1

有了這些各種各樣的問題，你需要明白，一些算法會比其他算法更好，任何一種算法的性能都取決於數據的「形狀」和大小。

將每個用戶的項目集與其他每個用戶進行比較可能適用於小型域數據集（例如1000或用戶，甚至是10,000，具有相似數量的項目），但這是一個'n平方'問題（或左右的訂單，我的大O是生鏽的，至少可以說！）：

Users Comparisons 
----- ----------- 
    2  1 
    3  3 
    4  6 
    5  10 
    6  15 
    n (n^2 - n)/2 

所以10萬用戶域將產生4999950000個一套比較。

另一種方法解決這個問題，將是反的關係，所以運行一個Map Reduce作業生成地圖項目的用戶：

'a' : [ 'u1', 'u2', 'u3' ], 
'b' : [ 'u2' ], 
'c' : [ 'u1' ], 
'f' : [ 'u2', 'u3' ], 
'h' : [ 'u1' ], 

從那裏你可以遍歷用戶對於每個項目，輸出用戶對（具有一個的計數）：

然後終於產生每個用戶配對的總和：

[ 'u1_u2' : 1, 'u1_u3' : 1, 'u2_u3' : 2 ] 

這不會產生你有興趣（雙A的兩個U1和U3項目集）的行爲，但細節的初步實現。

如果您知道您的域集通常包含不具有共同項目的用戶，每個用戶有少量項目或具有大量不同值的項目域，則此算法將更有效（先前你比較每一個用戶到另一個，與相交的兩個集合之間的低概率）。我確信一位數學家可以證明這一點，但我不是！

這也有同樣的潛在結垢問題依舊 - 因爲如果你有一個項目，所有的10萬個用戶都有一個共同點，你仍然需要生成4個十億用戶對。這就是爲什麼瞭解你的數據，盲目地將算法應用於它之前是很重要的。

Answer 2

這是否適合您？

from itertools import combinations 

user_sets = [ 
    { 'u1': [ 'a', 'a', 'c', 'h' ] }, 
    { 'u2': [ 'b', 'a', 'f' ] }, 
    { 'u3': [ 'a', 'a', 'f' ] }, 
] 

def compare_sets(set1, set2): 
    sum = 0 
    for n, item in enumerate(set1): 
     if item in set2: 
      sum += 1 
      del set2[set2.index(item)] 
    return sum 

for set in combinations(user_sets, 2): 
    comp1, comp2 = set[0], set[1] 
    print 'Common items bwteen %s and %s: %s' % (
     comp1.keys()[0], comp2.keys()[0], 
     compare_sets(comp1.values()[0], comp2.values()[0]) 
    ) 

下面是輸出：

 
Common items bwteen u1 and u2: 1 
Common items bwteen u1 and u3: 2 
Common items bwteen u2 and u3: 1 

Answer 3

你想發出所有的用戶，喜歡的東西了一步：

：

{ 'a': "u1" } 
{ 'a': "u1" } 
{ 'c': "u1" } 
{ 'h': "u1" } 
{ 'b': "u2" } 
{ 'a': "u2" } 
{ 'f': "u2" } 
{ 'a': "u1" } 
{ 'a': "u3" } 
{ 'f': "u3" } 

然後通過像鍵減少他們

{ 'a': ["u1", "u1", "u2", "u3"] } 
{ 'b': ["u2"] } 
{ 'c': ["u1"] } 
{ 'f': ["u2", "u3"] } 
{ 'h': ["u1"] } 

並且在該減速器中發出每個用戶的排列中的每個值，如：

{ 'u1_u2': 'a' } 
{ 'u2_u3': 'a' } 
{ 'u1_u3': 'a' } 
{ 'u2_u3': 'f' } 

注意，你要確保像k1_k2的關鍵是k1 < k2讓他們在任何進一步的MapReduce的步驟相匹配。

然後，如果你需要他們的所有分組喜歡你的例子，其他的MapReduce階段將它們的鍵組合，他們會落得像：

{ 'u1_u2': ['a'] } 
{ 'u1_u3': ['a'] } 
{ 'u2_u3': ['a', 'f'] } 
{ 'u2_u3': ['f'] }