MapReduce の制限事項
定義上、ペアごとのユーザーの類似性はMapReduce では表現できません。
何をするかを思い出すと、それは1 つのキーと値のペアをmap読み取ることです。2 つのキーと値のペアを読み取っていません。
の定義により、ペアワイズ比較mapを計算することはできません。
mapとreduceが線形プロセスであることを認識していれば、これは明らかです。また、ペアワイズ類似度は 2 次タスクです。動作しません。
つまり、mapreduce を悪用しない限りです。データ空間を 2 次サイズに拡張できます。最初にすべての n*n ペアを生成すると、これらのペアを MapReduce で再度処理できます。しかし、それは悪い悪用です (一部の人々は正確にそうしているようですが)。
(悪用) MapReduce の代替
まず第一に、データを反転するなどして、問題を実際に線形になるように書き直すことができる場合があります。または、実際には2次ですが、実際のデータでは通常線形のままになるように巧妙な剪定を行うことによって(生成中または生成前に理論的に2次データの多くを削除できるため)。
次に、Mahout は Hadoop プラットフォーム上に構築されていますが、MapReduce だけですべてが解決されるわけではないことに注意してください。Hadoop の多くは、「map+reduce」だけでは実行できません。たとえば TeraSort - 並べ替えは線形の問題ではないため (要素の比較も含まれます)、MapReduce では解決できません。ただし、Hadoop を TeraSort に使用することはできます。それには、一般化されたメジアン オブ メジアン アプローチを使用して分位数を推定する分散ソートを作成し、これらの分位数に従ってデータを分散してからO(n log n)、個々のノードで個々のバケット ( を参照) をソートします。複雑さは超線形のままですが、実行時間は単一ノードよりもはるかに短くなります。
Hadoop には、MapReduce 以外にもいくつかのオプションが用意されていると確信しています。このような非線形の問題を解決するために Mahout が何をするかを詳しく調べたいと思うかもしれません。すべてを MapReduce しようとしたり、ふりをしたりしません。「一括同期処理」として知られる一般化を使用して MapReduce を超える Apache Hama もあります。一般に、Hadoop (および Yarn) はそのようなことを許可します。しかし、API は明らかに従来の Mapper および Reducer API よりもはるかに困難です。
MapReduce の単純な悪用
または、悪用の道に進みます (これはおそらくMahout が行うことではありません) 。map reduce を悪用するのは実際にはかなり簡単です。出力サイズに制限がないためです。したがって、メモリを気にしない場合は、次のことができます。
たとえば、キーには 1 から n までの番号が付けられているため、すべてのキーを知っていると仮定します。次に、使用できます
map(K, V) -> [ (1, (K, V)), (2, (K, V)), (3, (K, V)), ..., (n, (K, V)) ]
(これは明らかに 2 次サイズのデータ セットを作成します!) そしてレデューサーでは、すべてのキーにデータ セットの完全なコピーと 1 つの ID が含まれるようになりました。
したがって、各オブジェクトのリデューサーは、完全なデータセットを再度読み取り、 n 個の類似度を計算して出力します。
ブーム、あなたは問題をマップ縮小しました。それは愚かで非効率的ですが、機能し、実行されています。
補助データによるよりスマートな悪用
これのよりスマートなバージョンは、いわゆる「補助データ」としてデータセットをシステムに直接ロードします。したがって、次のようになります。
map (K,V) -> [ (K_1, sim(V, aux_obj1)), (K_2, sim(V, aux_obj2)),
(K_3, sim(V, aux_obj3)), ... (K_n, sim(V, aux_objn)) ]
これは、MapReduce の悪用としてはそれほど悪くはありません (2 次結果行列の並列計算の標準的な方法にすぎません)。これは、大規模な補助データを使用することについて少なくとも正直であるためです。補助データがワーカーメモリに収まる限り、それも機能します。また、関数のパラメーター化として実際には見ることができない補助データを使用するため、適切な mapreduce ではなくなりました。
どうやらデータを (Python でも) メモリにロードできることを考えると、この最後のオプションがおそらく最も簡単な方法です。補助メモリをチャンクに分割し、データベースのこれらのスライスを個別のジョブとして計算することもできます。
それでも、MapReduce ではありません。これは二次問題であり、定義により MapReduce にはなりません。これらの問題は Hadoop (Mahout を参照) で解決できますが、そのためには MapReduce 以上のものが必要です。
実際のタスクに対する最後のコメント
まず、あなたが本当にやりたいことをもっと共有してください。より速くなるための重要なアイデアは、より少なくすることです。計算を節約できれば、常に高速になります。
10 万人のユーザーと 5 つの属性 (2 倍の価値がある?) はそれほど多くありません。したがって、Python の実装が非効率的すぎる可能性があります。コンパイルされて最適化された言語は、おそらく 1 ～ 2 桁速くなります。私は 10 分間で 8 つの属性を持つ 110,000 個のオブジェクトでペアごとの類似性を調べました。あなたの問題もこの頃に解決できるはずです。10 万人のユーザーと 5 つの属性は、まだ実際には「hadoop サイズのビッグ データ」ではありません。高速な低レベルの実装とは対照的に、Hadoop のオーバーヘッドに対して、得られるよりも多くの費用を支払うことになる可能性があります。
ピアソン相関の最適化: ここでできることがいくつかあります。標準偏差などを再計算する方法に注意してください。データを前処理し、平均が 0 で標準偏差が 1 になるようにすべてのレコードを標準化すると、ピアソン相関は共分散に単純化されます (stddev が 1 であるため)。また、平均が 0 であるため、共分散はちょうど になりE(x*y) = 1/5 \sum x_i * y_iます。この関数は、たとえば上位 10 個の類似オブジェクトのみに関心がある場合は、おそらく空間インデックスを使用して高速化できます。これをELKIに簡単に追加して、そこで空間インデックス構造を使用できると思います。これにより、通常、実行時間がさらに桁違いに短縮されます。つまり、単一の CPU で 1 分の処理時間になるはずです。