-2

假设我有以下用户/项目集，其中项目也可以为每个用户复制（如 user1） 

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

我想找到一个 map-reduce 算法来计算每对用户之间的共同项目的数量，就像这样

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

它基本上找到每对项目集的交集，并将复制视为新项目。我是 mapreduce 的新手，我该如何为此做一个 map-reduce？

4

3 回答 3

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"] }

并且在该 reducer 中，会在每个值中发出每个用户的排列，例如：

{ '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'] }
于 2012-12-18T00:53:02.923 回答
3

对于这些类型的问题，您需要了解某些算法的扩展性比其他算法更好，并且任何一种算法的性能都取决于数据的“形状”和大小。

将每个用户的项目集与每个其他用户进行比较可能适用于小型域数据集（比如 1000 个或用户，甚至可能是 10,000 个，具有相似数量的项目），但这是一个“n 平方”问题（或订单至少可以说，我的大 O 生锈了！）：

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

因此，100,000 个用户域将产生 4,999,950,000 组比较。

解决此问题的另一种方法是反转关系，因此运行 Map Reduce 作业以生成用户的项目映射：

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

从那里您可以迭代每个项目的用户并输出用户对（计数为 1）：

'a' would produce: [ 'u1_u2' : 1, 'u1_u3' : 1, 'u2_u3' : 1 ]
'f' would produce: [ 'u2_u3' : 1 ]

然后最终产生每个用户配对的总和：

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

这不会产生您感兴趣的行为（u1 和 u3 项目集中的双 a），但会详细说明初始实现。

如果您知道您的域集通常包含没有共同项目的用户、每个用户的少量项目或具有大量不同值的项目域，那么此算法将更有效（之前您正在比较每个用户到另一个用户，两组之间的交叉概率很低）。我相信数学家可以为你证明这一点，但我不是！

这也有与以前相同的潜在扩展问题——如果你有一个所有 100,000 个用户都共有的项目，你仍然需要生成 40 亿个用户对。这就是为什么在盲目地对数据应用算法之前了解数据很重要的原因。

于 2012-12-18T01:08:30.157 回答
0

这对你有用吗？

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])
    )

这是输出：

u1 和 u2 的共同项目：1
u1 和 u3 的常见项目：2
u2 和 u3 的共同项目：1
于 2012-12-17T23:18:57.030 回答