reduce 関数の作成

MapReduce における reduce 関数の役割

mapreduce は、データのブロックを受け取って中間結果を出力する入力 map 関数と、中間結果を読み取って最終結果を生成する入力 reduce 関数の両方を必要とします。したがって、map 関数および reduce 関数が独立して実行できるように、計算を 2 つの関係する部分に分割するのは自然なことです。たとえば、データ セット内の最大値を求めるために、map 関数は入力データの各ブロック内の最大値を求めることができ、次に、reduce 関数はすべての中間最大値の中から単一の最大値を求めることができます。

次の図に、mapreduce アルゴリズムの Reduce フェーズを示します。

mapreduce アルゴリズムの Reduce フェーズには次のステップがあります。

1. mapreduce アルゴリズムの Map フェーズの結果は、map 関数で追加されたすべてのキーと値のペアを含む中間 KeyValueStore オブジェクトです。mapreduce は、reduce 関数を呼び出す前に、中間 KeyValueStore オブジェクト内の値を一意なキーでグループ化します。中間 KeyValueStore オブジェクト内の一意なキーごとに、reduce 関数が一度呼び出されます。

2. mapreduce は、各キーに対して、そのキーに関連付けられる値をすべて含む ValueIterator オブジェクトを作成します。

3. reduce 関数は、関数 hasnext および getnext を使用して、ValueIterator オブジェクトからの値をスクロールします。これは通常、while ループの中で使用されます。

4. 要約の計算の実行後、reduce 関数は、関数 add および addmulti を使用して、1 つ以上のキーと値のペアを最終 KeyValueStore オブジェクトに追加します。

mapreduce アルゴリズムの Reduce フェーズは、reduce 関数が一意な中間キーとそれに関連付けられた値をすべて処理した時に完了します。mapreduce アルゴリズムのこのフェーズは、(Map フェーズと同様に) reduce 関数によって追加されたすべてのキーと値のペアを含む KeyValueStore オブジェクトです。Reduce フェーズの後、mapreduce はキーと値のペアを KeyValueStore から引き出して、データストア (既定では KeyValueDatastore オブジェクト) に返します。出力データストア内のキーと値のペアは、並べ替えられた順序になっていません。reduce 関数が追加した順序のままで表示されます。

reduce 関数の要件

mapreduce は、中間の KeyValueStore オブジェクト内の一意なキーごとに reduce 関数を自動的に呼び出すため、reduce 関数はこの自動呼出しの際に適切に実行できるように、特定の基本的な要件を満たさなければなりません。これらの要件は、mapreduce アルゴリズムの Reduce フェーズ中にデータが適切に移動することを集合的に保証します。

reduce 関数への入力は、intermKey、intermValIter および outKVStore です。

• intermKey は、map 関数によって追加された一意なキーの 1 つです。mapreduce が reduce 関数を呼び出すたびに、中間の KeyValueStore オブジェクトのキーから新しい一意のキーが指定されます。

• intermValIter は、アクティブなキー intermKey に関連付けられた ValueIterator オブジェクトです。この ValueIterator オブジェクトには、アクティブなキーに関連付けられたすべての値が含まれます。関数 hasnext とgetnext を使用して値をスクロールします。

• outKVStore は、reduce 関数によってキーと値のペアを追加する必要のある最終的な KeyValueStore オブジェクトの名前です。関数 add および関数 addmulti は、このオブジェクト名を使用して出力にキーと値のペアを追加します。mapreduce は outKVStore から出力のキーと値のペアを取り、出力データストア (既定は KeyValueDatastore オブジェクト) に返します。reduce 関数が outKVStore にキーと値のペアをまったく追加しなかった場合は、mapreduce は空のデータストアを返します。

reduce 関数に関するこれらの基本要件に加えて、reduce 関数によって追加されるキーと値のペアも、以下の条件を満たさなければなりません。

1. キーは数値スカラー、文字ベクトル、または string でなければなりません。数値キーを NaN、論理値、複素数、スパースにすることはできません。

2. reduce 関数によって追加されるすべてのキーは同じクラスでなければなりませんが、そのクラスは map 関数によって追加されたキーのクラスとは異なっていてもかまいません。

3. mapreduce の引数 OutputType が 'Binary' (既定) の場合は、reduce 関数で、有効な MATLAB^® データ型を含む任意の MATLAB オブジェクトを追加できます。

4. mapreduce の引数 OutputType が 'TabularText' の場合は、reduce 関数で数値スカラー、文字ベクトル、または string を追加できます。この場合、値に NaN、複素数、論理値、スパースは使用できません。

メモ

上記のキーと値のペアの要件は、mapreduce を使用する製品によって異なる場合があります。使用する製品のドキュメンテーションで、キーと値のペアに関する製品固有の要件を確認してください。

reduce 関数の例

以下は、mapreduce の例で使用されているいくつかの分かりやすい reduce 関数です。

単純な reduce 関数

リデューサーの最も単純な例の 1 つに maxArrivalDelayReducer があります。これは、例MapReduce を使用した最大値の検索のリデューサーです。この例の map 関数は、入力データの各チャンクの最大到着遅延時間を検索します。次に、reduce 関数が、すべての中間値の最大値から単一の最大値を見つけることによってタスクを終了します。最大値を見つけるために、リデューサーは ValueIterator オブジェクト内の値を順次確認し、各値を現在の最大値と比較します。マッパーは単一の一意なキーを中間 KeyValueStore オブジェクトに追加するため、mapreduce はこのリデューサー関数を一度だけ呼び出します。reduce 関数は、出力にキーと値のペアを 1 つ追加します。

function maxArrivalDelayReducer(intermKey, intermValIter, outKVStore)
  % intermKey is 'PartialMaxArrivalDelay'. intermValIter is an iterator of
  % all values that has the key 'PartialMaxArrivalDelay'.
  maxVal = -Inf;
  while hasnext(intermValIter)
    maxVal = max(getnext(intermValIter), maxVal);
  end
  % The key-value pair added to outKVStore will become the output of mapreduce 
  add(outKVStore,'MaxArrivalDelay',maxVal);
end

高度な reduce 関数

より高度なリデューサーの例には statsByGroupReducer があります。これは、例MapReduce を使用してグループごとの要約統計量を計算するのリデューサーです。この例の map 関数は、追加のパラメーター (航空会社、月など) を使用して各入力のデータをグループ化し、データのグループごとにいくつかの統計量を計算します。reduce 関数は、統計量を取得してそれらを長いベクトルに連結し、そのベクトルを使用してカウント、平均、分散、傾斜、尖度の最終的な統計量を計算し、タスクを完了します。リデューサーはこれらの値を構造体のフィールドとして格納するため、それぞれの一意のキーは出力に統計量の構造体をもちます。

function statsByGroupReducer(intermKey, intermValIter, outKVStore)
% Reducer function for the StatisticsByGroupMapReduceExample.

% Copyright 2014 The MathWorks, Inc.

n = [];
m = [];
v = [];
s = [];
k = [];

% get all sets of intermediate statistics
while hasnext(intermValIter)
    value = getnext(intermValIter);
    n = [n; value(1)];
    m = [m; value(2)];
    v = [v; value(3)];
    s = [s; value(4)];
    k = [k; value(5)];
end
% Note that this approach assumes the concatenated intermediate values fit
% in memory. Refer to the reducer function, covarianceReducer,  of the
% CovarianceMapReduceExample for an alternative pairwise reduction approach

% combine the intermediate results
count = sum(n);
meanVal = sum(n.*m)/count;
d = m - meanVal;
variance = (sum(n.*v) + sum(n.*d.^2))/count;
skewnessVal = (sum(n.*s) + sum(n.*d.*(3*v + d.^2)))./(count*variance^(1.5));
kurtosisVal = (sum(n.*k) + sum(n.*d.*(4*s + 6.*v.*d +d.^3)))./(count*variance^2);

outValue = struct('Count',count, 'Mean',meanVal, 'Variance',variance,...
                 'Skewness',skewnessVal, 'Kurtosis',kurtosisVal);

% add results to the output datastore
add(outKVStore,intermKey,outValue);

参考

mapreduce | tabularTextDatastore | add | addmulti | hasnext | getnext | KeyValueStore | ValueIterator

関連するトピック

• map 関数の作成
• MapReduce 入門