-2

次のユーザー/アイテム セットがあり、アイテムが各ユーザー (user1 など) に対して複製される可能性があるとします。 

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

そのようなユーザーの各ペア間の共通アイテムの数を計算するマップ削減アルゴリズムを見つけたい

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

そして、そのレデューサーでは、次のように、各値の各ユーザーの順列を発行します。

{ '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 乗」の問題 (または順序) です。そのあたりで、私の Big O は控えめに言っても錆びています!):

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

したがって、ユーザー ドメインが 100,000 の場合、4,999,950,000 セットの比較が行われます。

この問題に対するもう 1 つのアプローチは、関係を逆にすることです。そのため、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) を生成しませんが、初期実装について詳しく説明します。

通常、ドメイン セットに共通のアイテムを持たないユーザー、ユーザーごとのアイテムの数が少ない、または多数の異なる値を持つアイテム ドメインが含まれていることがわかっている場合、このアルゴリズムはより効率的です (以前は比較していました)。 2 つのセットが交差する可能性は低い)。私は数学者があなたのためにこれを証明できると確信していますが、私はそうではありません!

これには、以前と同じ潜在的なスケーリングの問題もあります。つまり、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 に答える