大量データのための2次パーソナルコネクションマイニングアルゴリズム（Hadoop実装）

私は最近、Sina Weibo の「あなたに興味があるかもしれない人々」の間接的なフォローアップ推奨のように、2 次接続の関係をいくつか見つけ出す必要のあるプロジェクトに取り組みました。簡単な説明は次のとおりです。フォローしている N 人の人が XXX もフォローしています。

プログラムの実装で実際に探しているのは、User1 が 10 人のユーザー {User3、User4、User5、...、User12} をフォローしていて、セット UF1 として記録されている場合、UF1 のこれらのユーザーもフォローセットを持ち、UF3 (User3 がフォローしているユーザー)、UF4、UF5、...、UF12 として記録されます。また、これらのセットの間には共通部分があり、ほとんどのセットの共通部分によって生成される共通部分こそが、探しているもの、つまり関心のある人々です。

2 次接続アルゴリズムの実装に関する情報をオンラインで検索しました。そのほとんどは、幅検索アルゴリズムを検索するだけで、ためらいの深さは 2 以内であると判断されています。このアルゴリズムは実際には非常に簡単です。最初のステップは、フォローしている人を見つけることです。2 番目のステップは、これらの人がフォローしている人を見つけることです。最後に、2 番目のステップの結果で最も頻繁に表示される 1 人以上の人を見つければ完了です。

しかし、他のユーザーがいる場合、計算中にこれらのユーザーのフォロー関係が必ずメモリに格納され、計算中に順番に検索されます。まず、明確な診断比較がなく、その効果はHadoopに基づくものほど良くないことを説明する必要があります。私はHadoopを使用して実装したいだけで、最近も学習しています。不備があれば、指摘してください。

まず、初期データはファイルであり、各行は ida+'\t'+idb という関係に従います。つまり、ida は idb に従います。次に、2 つの Map/Reduce タスクが使用されました。

Map/Reduce 1:任意のユーザーのフォローセットとフォローセットを検索します。図に示すように:

コードは次のとおりです。

マップタスク: 出力キー: 間接アクターAのID、値: フォロワーまたはフォローされている人のID

公共  void map(テキストキー、IntWritable値、コンテキストコンテキスト)はIOException、InterruptedExceptionをスローします{ 
        戻り値: 
         // 2つのユーザーIDを分割する 
        文字列[] _key = Separator.CONNECTORS_Pattern.split(key.toString()); 
         _key.length == 2 の場合{ 
             // 「f」プレフィックスはフォローを意味し、「b」プレフィックスはフォローを意味します 
            context.write(新しいテキスト(_key[ 0 ])、新しいテキスト( "f" + _key[ 1 ]));
            context.write(新しいテキスト(_key[ 1 ])、新しいテキスト( "b" + _key[ 0 ])); 
              
              
        }
    }

削減タスク: 出力キー: 間接アクター A の ID、値は 2 つの文字列で、最初の文字列はフォローしているすべての人々 (区切り文字で区切られています)、2 番目の文字列はフォローしている人々 (これも区切られています)

 &nbsp;&nbsp;&nbsp;&nbsp;保護されています  void Reduce(テキストキー、Iterable<TextPair> ペア、コンテキストコンテキスト) 
      IOException、InterruptedExceptionをスローします{
        StringBuilder の first_follow =新しいStringBuilder();
        StringBuilderのsecond_befollow =新しいStringBuilder(); 
          
         ( TextPair ペア: ペア){
            文字列 id = pair.getFirst().toString();
            文字列値 = pair.getSecond().toString(); 
             id.startsWith( "f" )の場合{
                first_follow.append(id.substring( 1 )).append(Separator.TABLE_String);
            }それ以外  id.startsWith( "b" )の場合
                second_befollow.append(id.substring( 1 )).append(Separator.TABLE_String);
            }
        } 
          
        context.write(キー、新しいTextPair(first_follow.toString()、second_befollow.toString()));
 &nbsp;&nbsp;&nbsp;&nbsp;}

Separator.TABLE_String はカスタムセパレーターです。TextPair はカスタムの Writable クラスであり、キーを 2 つの値に対応させ、2 つの値を区別できるようにします。

Map/Reduce 2:前のステップで、B が A に続き、A が T に続く場合、T は B の 2 次接続であり、間接的な人物は A であると結論付けることができるので、同じ 2 次接続の異なる間接的な人物を見つけます。図に示すように:

コードは次のとおりです。

マップタスク: 出力時に、キーは2つの文字列レコードのIDで表される2次関係であり、値はこの2次関係によって生成された間接的な人物のIDです。

公共  void map(テキストキー、テキストペア値、コンテキストコンテキスト)はIOException、InterruptedExceptionをスローします{
        Map<String, String> first_follow = new HashMap<String, String>();
        Map<String, String> second_befollow = new HashMap<String, String>();
        文字列 _key = key.toString();
        String[] follow = values.getFirst().toString().split(Separator.TABLE_String); 
          
        文字列[] 秒 = values.getSecond().toString().split(Separator.TABLE_String); 
          
         for (文字列 sf : follow){ 
              
            first_follow.put(sf、_key); 
              
        } 
          
         (文字列 ss : 秒){ 
              
            second_befollow.put(ss, _key); 
              
        } 
          
         ( Entry <String, String> f : first_follow.entrySet()){ 
             ( Entry<String, String> b : second_befollow.entrySet()){
                context.write(新しいTextPair(f.getKey() 、b.getKey())、新しいText(key));
            }
        }
 &nbsp;&nbsp;&nbsp;&nbsp;}

削減タスク: 出力時、キーは引き続き 2 次関係であり、値はカンマで区切られたすべての間接的な人の ID です。

保護された  void Reduce(TextPair キー、Iterable<Text> 値、Context コンテキスト) 
     IOException、InterruptedExceptionをスローします{ 
      
    StringBuilder 結果 = new StringBuilder(); 
     for (テキストテキスト:値){
        結果.append(text.toString()).append( "," );
    } 
      
    context.write(キー、新しいテキスト(resutl.toString()));
 }