Map-reduce-algorithm

MapReduce-アルゴリズム

MapReduceアルゴリズムには、MapとReduceという2つの重要なタスクが含まれています。

• マップタスクは、マッパークラスによって実行されます。
• 削減タスクは、Reducerクラスによって実行されます。

マッパークラスは入力を受け取り、トークン化し、マッピングし、並べ替えます。 Mapperクラスの出力は、Reducerクラスの入力として使用されます。Reducerクラスは、一致するペアを順番に検索してそれらを削減します。

マッパーリデューサークラス

MapReduceはさまざまな数学アルゴリズムを実装して、タスクを小さな部分に分割し、それらを複数のシステムに割り当てます。 技術的には、MapReduceアルゴリズムは、Map＆Reduceタスクをクラスター内の適切なサーバーに送信するのに役立ちます。

これらの数学的アルゴリズムには次のものが含まれます-

• ソート
• 検索中
• 索引付け
• TF-IDF

ソート

ソートは、データを処理および分析するための基本的なMapReduceアルゴリズムの1つです。 MapReduceは、キーによってマッパーからの出力キーと値のペアを自動的にソートするソートアルゴリズムを実装しています。

• 並べ替えメソッドは、マッパークラス自体に実装されます。
• シャッフルおよびソートフェーズでは、マッパークラスの値をトークン化した後、 Context クラス（ユーザー定義クラス）は、一致する値のキーをコレクションとして収集します。
• 同様のキーと値のペア（中間キー）を収集するために、Mapperクラスは RawComparator クラスの助けを借りてキーと値のペアをソートします。
• 特定のレデューサーの中間キーと値のペアのセットは、Reduceに提示される前に、Hadoopによってキー値（K2、\ {V2、V2、…}）を自動的にソートされます。

検索中

検索は、MapReduceアルゴリズムで重要な役割を果たします。 これは、コンバイナーフェーズ（オプション）およびレデューサーフェーズで役立ちます。 例の助けを借りて、検索がどのように機能するかを理解してみましょう。

例

次の例は、MapReduceが検索アルゴリズムを使用して、特定の従業員データセットで最高の給与を引き出している従業員の詳細を見つける方法を示しています。

• A、B、C、Dの4つの異なるファイルに従業員データがあると仮定します。 また、すべてのデータベーステーブルから従業員データを繰り返しインポートするため、4つのファイルすべてに従業員レコードが重複していると仮定します。 次の図を参照してください。

Map Reduce Illustration

• *マップフェーズ*では、各入力ファイルを処理し、従業員データをキーと値のペア（<k、v>：<emp name、salary>）で提供します。 次の図を参照してください。

Map Reduce Illustration

• コンバイナーフェーズ（検索手法）は、マップフェーズからの入力を従業員名と給与のキーと値のペアとして受け入れます。 検索手法を使用して、コンバイナはすべての従業員の給与をチェックして、各ファイルで最高の給与を受け取る従業員を見つけます。 次のスニペットを参照してください。

<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary

if(v(second employee).salary > Max){
   Max = v(salary);
}

else{
   Continue checking;
}

期待される結果は次のとおりです-

a|

<satish, 26000>

| a|

<gopal, 50000>

| a|

<kiran, 45000>

| a|

<manisha, 45000>

|

• リデューサーフェーズ-各ファイルを作成すると、最高給の従業員が見つかります。 冗長性を回避するには、すべての<k、v>ペアを確認し、重複するエントリがあれば削除します。 4つの入力ファイルからの4つの<k、v>ペアの間でも同じアルゴリズムが使用されます。 最終的な出力は次のようになります-

<gopal, 50000>

索引付け

通常、インデックスは特定のデータとそのアドレスを指すために使用されます。 特定のマッパーの入力ファイルに対してバッチインデックス作成を実行します。

MapReduceで通常使用されるインデックス作成手法は、*反転インデックス*と呼ばれます。GoogleやBingなどの検索エンジンは、反転インデックス作成手法を使用します。 簡単な例を使用して、インデックス作成がどのように機能するかを理解してみましょう。

例

次のテキストは、逆索引付けの入力です。 ここで、T [0]、T [1]、およびt [2]はファイル名であり、その内容は二重引用符で囲まれています。

T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"

インデックスアルゴリズムを適用した後、次の出力が得られます-

"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}

ここで「a」：\ {2}は、「a」という用語がT [2]ファイルに現れることを意味します。 同様に、「is」：\ {0、1、2}は、ファイルT [0]、T [1]、およびT [2]に「is」という用語が含まれることを意味します。

TF-IDF

TF-IDFはテキスト処理アルゴリズムで、Term Frequency-Inverse Document Frequencyの略です。 これは、一般的なWeb分析アルゴリズムの1つです。 ここで、「頻度」という用語は、ドキュメント内で用語が出現する回数を指します。

期間頻度（TF）

ドキュメント内で特定の用語が出現する頻度を測定します。 これは、ドキュメント内の単語の出現回数をそのドキュメント内の単語の総数で割って計算されます。

TF(the) = (Number of times term the ‘the’ appears in a document)/(Total number of terms in the document)

逆ドキュメント頻度（IDF）

用語の重要性を測定します。 テキストデータベース内のドキュメントの数を特定の用語が出現するドキュメントの数で割って計算されます。

TFの計算中、すべての用語は等しく重要であると見なされます。 つまり、TFは、「is」、「a」、「what」などの通常の単語の用語頻度をカウントします。 したがって、以下を計算することにより、まれな用語をスケールアップしながら頻繁な用語を知る必要があります-

IDF(the) = log_e(Total number of documents/Number of documents with term ‘the’ in it).

このアルゴリズムは、小さな例を使用して以下に説明されています。

例

単語 hive が50回出現する、1000個の単語を含むドキュメントを考えます。 hive のTFは（50/1000）= 0.05です。

ここで、1,000万のドキュメントがあり、これらの1000個に hive という単語が表示されているとします。 次に、IDFはlog（10,000,000/1,000）= 4として計算されます。

TF-IDF重量は、これらの量の積-0.05×4 = 0.20です。