(57)【特許請求の範囲】
【請求項１】
１つのキーと値の組から一つ以上のキーと値の組を生成するマップ（Map）手段と、キーが同じ複数のキーと値の組から１つないしは複数のキーと値の組を生成するリデュース（Reduce）手段、及び、与えられた教師データを格納する分散ファイル記憶手段を有し、大規模なデータを並列分散処理するためのデータ分析・機械学習装置であって、
前記マップ手段及び前記リデュース手段は、
入力されたデータの処理中に、該マップ手段及び該リデュース手段で利用するパラメータに関する情報として、該データからパラメータの値、利用位置、利用元関数を検出し、前記分散ファイル記憶手段に格納する検出手段を有し、
ジョブに与えられたパラメータを参照し、前記分散ファイル記憶手段に格納されている前記パラメータに関する情報と照合し、所定の条件を満たす場合に、中間データをキャッシュとして該分散ファイル記憶手段、または、ローカルの記憶手段に格納する中間データ格納手段と、
ジョブに与えられたパラメータを参照し、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、前記リデュース手段のみを実行させるスキップ処理手段と、
を有し、
前記リデュース手段は、
前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、該分散ファイル記憶手段、または、該ローカルの記憶手段から該中間データを読み込んで処理を行う手段を含み、
前記中間データ格納手段は、
前記マップ手段の処理がパラメータに依存しない、または、該パラメータの利用頻度が所定の閾値を超えている、または、ユーザにより保存することが指定されている場合に、前記中間データをキャッシュとして格納する手段を含む
ことを特徴とするデータ分析・機械学習装置。
【請求項２】
前記検出手段は、
前記マップ手段及び前記リデュース手段のクラス名、予め与えられているパラメータ名と値の該マップ手段及び該リデュース手段の処理中における利用順序、利用される関数を検出する手段を含む
請求項１記載のデータ分析・機械学習装置。
【請求項３】
１つのキーと値の組から一つ以上のキーと値の組を生成するマップ（Map）手段と、キーが同じ複数のキーと値の組から１つないしは複数のキーと値の組を生成するリデュース（Reduce）手段、及び、与えられた教師データを格納する分散ファイル記憶手段を有し、大規模なデータを並列分散処理する装置におけるデータ分析・機械学習方法であって、
前記マップ手段及び前記リデュース手段が、入力されたデータの処理中に、該マップ手段及び該リデュース手段で利用するパラメータに関する情報として、該データからパラメータの値、利用位置、利用元関数を検出し、前記分散ファイル記憶手段に格納する検出ステップと、
中間データ格納手段が、ジョブに与えられたパラメータを参照し、前記分散ファイル記憶手段に格納されている前記パラメータに関する情報と照合し、所定の条件を満たす場合に、中間データをキャッシュとして該分散ファイル記憶手段、または、ローカルの記憶手段に格納する中間データ格納ステップと、
スキップ処理手段が、ジョブに与えられたパラメータを参照し、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、前記リデュース手段のみを実行させるスキップ処理ステップと、
前記リデュース手段が、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、該分散ファイル記憶手段、または、該ローカルの記憶手段から該中間データを読み込んで処理を行うステップと、
を行い、
前記中間データ格納ステップにおいて、
前記マップ手段の処理がパラメータに依存しない、または、該パラメータの利用頻度が所定の閾値を超えている、または、ユーザにより保存することが指定されている場合に、前記中間データをキャッシュとして格納する
ことを特徴とするデータ分析・機械学習方法。
【請求項４】
前記検出ステップにおいて、
前記マップ手段及び前記リデュース手段のクラス名、予め与えられているパラメータ名と値の該マップ手段及び該リデュース手段の処理中における利用順序、利用される関数を検出する
請求項３記載のデータ分析・機械学習方法。
【請求項５】
請求項１または２に記載のデータ分析・機械学習装置を構成する各手段としてコンピュータを機能させるためのデータ分析・機械学習プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析及び機械学習処理装置及び方法及びプログラムに係り、特に、大規模なデータの分析処理のための機械学習処理の効率化を図るためのデータ分析及び機械学習処理装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
大規模データの分析処理のための技術として"MapReduce"がある（例えば、非特許文献１参照）。
【０００３】
図２３は、マップリデュース（MapReduce）処理の流れを示す。MapReduceはネットワークによって相互に接続された複数のコンピュータを用いる。MapReduceは図２３に示すような流れで処理が行われる分散処理フレームワークである。
【０００４】
MapReduce処理が開始されると、まずは各コンピュータにおいて、ユーザが任意に定義した"Mapper"が起動され、予め分散ファイルシステム（HDFS）に格納されていた分散データを各々のコンピュータが読み込み、マップ（Map）処理が行われる。
【０００５】
Map処理では、各コンピュータが自らに割り当てられた分散データを先頭から順に１行に対して１回、ユーザが定義したMap関数が適用される。Map関数において、処理の結果として複数のキー・値（Key-Value）形式のレコードの集合を中間データとして出力する。なお、Key・Valueそれぞれの型は一定制約下でユーザが任意に定義するものとする。
【０００６】
次に、各コンピュータにおいて各ユーザが任意に定義したReducerが起動され、中間データのKey部が同じレコードが１台のコンピュータに集められるように、ネットワークを介して中間データを相互に移動させる。これを"Shuffle処理"と呼ぶ。
【０００７】
同じKeyを持つ中間データのレコードは最終的にソートされた状態で、Valueはイテレータとしてユーザが定義したリデュース（Reduce）関数に与えられる。Reduce関数において、処理の結果として複数のKey-Value形式のレコードの集合が出力される。
【０００８】
図２４にMapReduceを利用した一般的なアプリケーションの処理フローを示す。
【０００９】
ステップ１００）  初期設定ファイルを入力し、MapReduceを開始するためにジョブを生成する。
【００１０】
ステップ１１０）  生成されたジョブに対して利用するマッパー（Mapper）・リデューサー（Reducer）やReducerの数、その他のMapReduce処理そのものに必要な設定や、ユーザが定義するMapper・Reducer等の内部で利用するパラメータ、コマンドライン引数などの解析により実行時に変更可能なパラメータをMapReduceジョブに与える。
【００１１】
ステップ１２０）  MapReduce処理を行う。詳細は図２５で述べる。
【００１２】
ステップ１３０）  MapReduce処理によって出力された結果に対して何らかの処理（ユーザが定義した処理）を行う。
【００１３】
次に、図２４のステップ１２０のMapReduce処理について説明する。MapReduce処理は複数のノード（コンピュータ）をネットワークで相互に接続したクラスタ上で行う分散処理フレームワークである。
【００１４】
図２５は、一般的なMapReduce処理のフローを示す。
【００１５】
ステップ２００）  MapReduce処理が開始されると、まずは、各ノードにおいてユーザが任意に定義したMapperが起動され、予め分散ファイルシステムに格納されていた分散データを各々のノードが読み込み、Map処理が行われる。このとき、ユーが定義した任意のMap処理を行う。各ノードが自らに割り当てた分散データを先頭から順に１行に対して１回、ユーザが定義したMap関数が適用され、Key-Value形式の任意の中間データを出力する。
【００１６】
ステップ２１０）  ユーザがコンバイン（Combine）に利用するクラスを明示的に指定している場合のみ、各ノードにおいてMap処理が終わり次第、次にコンバイナー（Combiner）が起動され、それぞれのMap処理によって出力された中間データを対象として、キーが共通である中間データを一つにまとめるCombine処理（ローカルでのReduce）が行われ、Key・Valueリストの形をとった任意の複数の中間データが出力される。
【００１７】
ステップ２２０）  各ノードにおいてユーザが任意に定義したReducerが起動され、中間データのキー部が同じレコードが１台のノードに集められるように、ネットワークを介して中間データを相互に移動させるシャッフル（Shuffle）処理が行われる。Shuffleの際、中間データはKey部を元にしてソートされ、１つのKeyに対して複数のValueの形式のリストが出力される。
【００１８】
ステップ２３０）  Shuffleされた中間データそれぞれに対してReduce処理が行われる。
【００１９】
上記の技術は、同じデータを入力として、複数のMapReduce処理（Grep処理）を行うものであり、中間データのキーへのタグの付与、中間データの削減処理（ジョブの事前統合と複数ジョブの同時実行）を行う(例えば、非特許文献２参照)。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】MRShare: Sharing Across Multiple Queries in MapReduce [Tomasz Nykiel, Michalis Potamias, Chaitanya Mishra, George Kollios, Nick Koudas, VLDB2010,2010年9月]
【非特許文献２】MapReduce: Simple_ed Data Processing on Large Clusters [Jeffrey Dean, Sanjay Ghemawat, OSDI2004] http://static.googleusercontent.com/external content/untrusted dlcp/labs.google.com/ja//papers/mapreduce-osdi04.pdf
【発明の概要】
【発明が解決しようとする課題】
【００２１】
機械学習処理は、事前に機械学習アルゴリズムに与える設定値次第で得られる処理結果の精度が大きく異なる場合があるため、設定値を調整しながら処理を複数回繰り返さなければ最良の結果を得ることができない。特に、MapReduceを利用して大規模なデータを対象とした処理を行う際に、例えば、機械学習ライブラリである"Mahout"では設定値の調整があまり考慮されないため、良い結果を得るために長時間に及ぶ処理を複数回行うことになり、非常に効率が悪い。
【００２２】
上記の非特許文献１の技術は、複数回の処理において、各処理のデータ読み込み部分の共有化により、中間データ削減によるShuffleコストは削減できるが、以前の処理の中間データを再利用することによる大幅な処理量の削減ができないという問題がある。
【００２３】
本発明は、上記の点に鑑みなされたもので、過去の処理において利用した中間データを再利用できないという問題を解決し、大幅な処理量の削減が可能なデータ分析及び機械学習処理装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２４】
上記の課題を解決するために、本発明（請求項１）は、１つのキーと値の組から一つ以上のキーと値の組を生成するマップ（Map）手段と、キーが同じ複数のキーと値の組から１つないしは複数のキーと値の組を生成するリデュース（Reduce）手段、及び、与えられた教師データを格納する分散ファイル記憶手段を有し、大規模なデータを並列分散処理するためのデータ分析・機械学習装置であって、
前記マップ手段及び前記リデュース手段は、
入力されたデータの処理中に、該マップ手段及び該リデュース手段で利用するパラメータに関する情報として、該データからパラメータの値、利用位置、利用元関数を検出し、前記分散ファイル記憶手段に格納する検出手段を有し、
ジョブに与えられたパラメータを参照し、前記分散ファイル記憶手段に格納されている前記パラメータに関する情報と照合し、所定の条件を満たす場合に、中間データをキャッシュとして該分散ファイル記憶手段、または、ローカルの記憶手段に格納する中間データ格納手段と、
ジョブに与えられたパラメータを参照し、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、前記リデュース手段のみを実行させるスキップ処理手段と、
を有し、
前記リデュース手段は、
前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、該分散ファイル記憶手段、または、該ローカルの記憶手段から該中間データを読み込んで処理を行う手段を含み、
前記中間データ格納手段は、
前記マップ手段の処理がパラメータに依存しない、または、該パラメータの利用頻度が所定の閾値を超えている、または、ユーザにより保存することが指定されている場合に、前記中間データをキャッシュとして格納する手段を含む。
【００２５】
また、本発明（請求項２）は、請求項１の前記検出手段に、
前記マップ手段及び前記リデュース手段のクラス名、予め与えられているパラメータ名と値の該マップ手段及び該リデュース手段の処理中における利用順序、利用される関数を検出する手段を含む。
【００２７】
本発明（請求項３）は、１つのキーと値の組から一つ以上のキーと値の組を生成するマップ（Map）手段と、キーが同じ複数のキーと値の組から１つないしは複数のキーと値の組を生成するリデュース（Reduce）手段、及び、与えられた教師データを格納する分散ファイル記憶手段を有し、大規模なデータを並列分散処理する装置におけるデータ分析・機械学習方法であって、
前記マップ手段及び前記リデュース手段が、入力されたデータの処理中に、該マップ手段及び該リデュース手段で利用するパラメータに関する情報として、該データからパラメータの値、利用位置、利用元関数を検出し、前記分散ファイル記憶手段に格納する検出ステップと、
中間データ格納手段が、ジョブに与えられたパラメータを参照し、前記分散ファイル記憶手段に格納されている前記パラメータに関する情報と照合し、所定の条件を満たす場合に、中間データをキャッシュとして該分散ファイル記憶手段、または、ローカルの記憶手段に格納する中間データ格納ステップと、
スキップ処理手段が、ジョブに与えられたパラメータを参照し、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、前記リデュース手段のみを実行させるスキップ処理ステップと、
前記リデュース手段が、前記中間データが前記分散ファイル記憶手段、または、前記ローカルの記憶手段に格納されている場合には、該分散ファイル記憶手段、または、該ローカルの記憶手段から該中間データを読み込んで処理を行うステップと、を行い、
前記中間データ格納ステップにおいて、
前記マップ手段の処理がパラメータに依存しない、または、該パラメータの利用頻度が所定の閾値を超えている、または、ユーザにより保存することが指定されている場合に、前記中間データをキャッシュとして格納する。
【００２８】
また、本発明（請求項４）は、請求項３の前記検出ステップにおいて、
前記マップ手段及び前記リデュース手段のクラス名、予め与えられているパラメータ名と値の該マップ手段及び該リデュース手段の処理中における利用順序、利用される関数を検出する。
【００３０】
本発明（請求項５）は、請求項１または２に記載のデータ分析・機械学習装置を構成する各手段としてコンピュータを機能させるためのデータ分析・機械学習プログラムである。
【発明の効果】
【００３１】
上記のように、本発明では、MapReduce処理中に、パラメータの利用順序、利用関数を検知し、その情報を活用して中間データをキャッシュとして残すかを判定し、所定の条件を満たした場合には中間データを分散ファイルシステムに格納しておき、以降の処理においてキャッシュした中間データを再利用することで、マップ（Map）処理、及び、シャッフル（Shuffle）処理をスキップして、リデュース(Reduce）処理のみを開始することにより、処理量を削減することができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の第１の実施の形態におけるシステム構成図である。
【図２】本発明の第１の実施の形態における全体動作のフローチャートである。
【図３】本発明の第１の実施の形態における中間データを保存するMapReduceを利用した処理のフローチャート（S310）である。
【図４】本発明の第１の実施の形態における中間データ保存判定の処理のフローチャート（S620）である。
【図５】本発明の第１の実施の形態における中間データを再利用するMapReduceを利用した処理のフローチャート（S320）である。
【図６】本発明の第１の実施の形態における中間データ再利用判定処理のフローチャート（S920）である。
【図７】本発明の第２の実施の形態におけるパラメータ情報を検知するMapReduceを利用した処理のフローチャート（S300）である。
【図８】本発明の第２の実施の形態におけるパラメータ情報を検知するMapReduce処理のフローチャート（S420）である。
【図９】本発明の第２の実施の形態におけるパラメータ情報検知のイメージである。
【図１０】本発明の第３の実施の形態における中間データを保存するMapReduce処理のフローチャート（S630）である。
【図１１】本発明の第３の実施の形態における中間データを再利用したMapReduce処理のフローチャート（S930）である。
【図１２】本発明の一実施例のHadoopによるMapReduce処理開始時の各ノードの動きを示す図である。
【図１３】クライアントノードの一般的な処理のフローチャートである。
【図１４】ジョブ追加時の処理のフローチャート（S1450）である。
【図１５】本発明の一実施例のジョブ追加時の処理のフローチャート（S1450）である。
【図１６】本発明の一実施例のジョブスケジューラの処理のフローチャートである。
【図１７】本発明の一実施例のTaskTrackerのタスク取得ループの処理のフローチャートである。
【図１８】本発明の一実施例のタスク開始時の処理のフローチャート（S1821,S1831）である。
【図１９】本発明の一実施例のパラメータ検知用Mapperの処理のフローチャート（S1920）である。
【図２０】本発明の一実施例の検知用Configurationクラスのパラメータ呼出時の処理のフローチャートである。
【図２１】本発明の一実施例の検知用Reducerの処理のフローチャート（S1920）である。
【図２２】本発明の一実施例のスキップ用Mapperの処理のフローチャート（S1920）である。
【図２３】MapReduce処理の流れである。
【図２４】MapReduceを利用した一般的なアプリケーション処理のフローチャートである。
【図２５】一般的なMapReducerの処理のフローチャートである。
【発明を実施するための形態】
【００３３】
以下図面と共に、本発明の実施の形態を説明する。
【００３４】
［第1の実施の形態］
図１は、本発明の第1の実施の形態におけるシステム構成を示す。
【００３５】
本発明の構成は、図２３と同様に、ネットワークによって相互に接続された複数のコンピュータを用い、図２３と同様の流れを処理が行われる分散処理フレームワークを行うシステムである。
【００３６】
本実施の形態では、MapReduce処理において、集計用データ作成部（Mapper）２０、集計部（Reducer）４０においてパラメータに関する情報を検知し、保存する。それ以後、制御部（Controller）５０において、MapReduce処理の開始時に処理に利用するMapper・Reducer・パラメータと、保存した情報とを比較して、中間データをキャッシュとして分散ファイルシステム１０に保存するか否かを、ユーザの指定等により判定する。さらに、それ以降の処理において、分散ファイルシステム１０に保存されたキャッシュを利用するか否かを判定し、中間データを再利用することで、Map・Shuffle処理をスキップする。
【００３７】
以下に、動作の詳細を説明する。
【００３８】
図２は、本発明の第1の実施の形態における全体動作のフローチャートである。
【００３９】
ステップ３００）  本ステップでは、図２４と同様のMapReduce処理を行うが、その過程でMapper２０やReducer40が利用するパラメータの値、利用位置、利用元関数を検知し、分散ファイルシステム１０に保存する。
【００４０】
ステップ３１０）  図２４に示すMapReduce処理の過程において、制御部(Controller)５０が、ジョブに与えられたパラメータを参照し、ステップ３００で得られたパラメータに関する情報と照合することで、中間データをキャッシュとして保存するべきか判定し、保存する場合は、中間データを分散ファイルシステム１０またはローカルに保存する。
【００４１】
ステップ３２０）  図２４に示すMapReduce処理の過程において、Controller５０は、ジョブに与えられたパラメータを参照し、ステップ３１０で得られた中間データのキャッシュを再利用可能かどうかを判定して、可能な場合はキャッシュを再利用することによってMap処理とShuffle処理をスキップし、Reducer４０のReduce処理のみを行う。
【００４２】
次に、上記のステップ３１０の詳細な動作を説明する。
【００４３】
図３は、本発明の第1の実施の形態における中間データを保存するMapReduceを利用した処理のフローチャートである。
【００４４】
ステップ６００）  図２４と同様に、MapReduceジョブを生成する。
【００４５】
ステップ６１０）  図２４と同様に、ジョブにパラメータを与える。
【００４６】
ステップ６２０）  Controller５０は、ステップ６１０の出力であるジョブが保持するパラメータを元に、ステップ３００の出力である分散ファイルシステム１０に格納されたパラメータに関する情報を参照し、当該ジョブにおいて中間データをキャッシュとして保存するか否かを判定し、保存する場合は保存フラグ「真」を示すパラメータを新たに追加する。
【００４７】
ステップ６３０）  MapReduce処理の過程で、Reduce処理を行う直前に、中間データをキャッシュとして分散ファイルシステム１０に保存する。
【００４８】
ステップ６４０）  図２４のステップ１３０と同様の処理を行う。
【００４９】
次に、上記のステップ６２０の処理について詳細に説明する。
【００５０】
図４は、本発明の第１の実施の形態における中間データ保存判定の処理フローチャートである。
【００５１】
ステップ７００）  Controller５０は、Mapperクラス名、パラメータに関する情報が与えられると、Mapperクラス名を元に、パラメータに関する情報を参照し、Mapper２０の処理内においてパラメータ呼び出しがない場合は『真』を、そうでない場合は『偽』を出力する。
ステップ７１０）  Controller５０は、Map処理で利用するパラメータの全てにおいて、同じ値が設定される頻度がユーザが指定した閾値を超えているかを判定する。詳しくは、Mapperクラス名に基づいて、与えられたパラメータに関する情報を参照し、Mapper２０の処理内において利用されるパラメータのうち、全てがユーザにより設定された閾値を超える頻度で同じ値が設定される場合は『真』を、そうでない場合は『偽』を出力する。
【００５２】
ステップ７２０）  controller５０は、パラメータの集合を取得して、当該集合中に中間データ記憶部３０への保存を明示的に有効化するものがあるかを確認し、ある場合は『真』を、ない場合は『偽』を出力する。
【００５３】
ステップ７３０）  上記のステップ７００，７１０，７２０のいずれにおいて、『真』である場合は、Controller５０は、MapReduceジョブが保持するパラメータに対して中間データを有効化するフラグと、中間データを保存する場所を付与する。
【００５４】
次に、図２のステップ３２０の処理について詳細に説明する。
【００５５】
図５は、本発明の第１の実施の形態における中間データを再利用するMapReduceを利用した処理のフローチャートである。
【００５６】
ステップ９００）  Controller５０は、図２４のステップ１００と同様にMapReduceジョブを生成する。
【００５７】
ステップ９１０）  図２４のステップ１１０と同様に生成されたジョブにパラメータを与える。
【００５８】
ステップ９２０）  ステップ９１０の出力であるジョブが保持するパラメータを元に、当該ジョブにおいて利用可能な中間データがキャッシュとして分散ファイルシステム１０に保存されているか否かを判定し、利用可能な場合はキャッシュ利用フラグが『真』を示すパラメータを新たにジョブに追加する。
【００５９】
ステップ９３０）  Reducer４０は、キャッシュとして中間データ記憶部３０に保存されている中間データを利用して、Map処理及びShuffle処理をスキップしてReduce処理のみのMapReduce処理を行う。
【００６０】
ステップ９４０）  図２４のステップ１３０と同様の処理を行う。
【００６１】
次に、上記の５のステップ９２０の処理を説明する。
【００６２】
図６は、本発明の第１の実施の形態における中間データ再利用判定処理のフローチャートである。
【００６３】
ステップ１０００）  ジョブが保持するパラメータを元に、分散ファイルシステム１０内に利用できるキャッシュ（同じ入力データ、同じパラメータを利用して処理したときの中間データ）があるかどうかを判定する。
【００６４】
ステップ１０１０）  ある場合は、ジョブに対して利用するキャッシュ保存場所を含めたキャッシュ利用フラグを付与する。
【００６５】
［第２の実施の形態］
本実施の形態は、第１の実施の形態の図２のステップ３００の処理において、MapReduce処理に使われるMapperクラス・Reduceクラスの名前、事前に与えるパラメータ名と値、それがMapReduce処理中のどのような順序で、どの関数内で利用されるかを検出し、その情報を分散ファイルシステム１０に保存することで、以後の処理において利用できるようにするものである。
【００６６】
本実施の形態におけるシステム構成は第１の実施の形態と同様である。
【００６７】
図７は、本発明の第２の実施の形態におけるパラメータ情報を検知するMapReduceを利用した処理のフローチャートである。
【００６８】
以下の処理は、第１の実施の形態の図２のステップ３００の処理に対応する。
【００６９】
ステップ４００）  図２４のステップ１００と同様である。
【００７０】
ステップ４１０）  図２４のステップ１１０と同様である。
【００７１】
ステップ４２０）  Mapper２０及びReducer４０は、入力された任意のデータから、内部で利用されるパラメータの値、利用位置、利用元関数を検知し、分散ファイルシステム１０に保存しながらMapReduce処理を行う。
【００７２】
ステップ４３０）  図２４のステップ１３０と同様である。
【００７３】
次に、上記のステップ４２０の処理について詳細に説明する。
【００７４】
図８は、本発明の第２の実施の形態におけるパラメータ情報を検知するMapReduce処理のフローチャートである。
【００７５】
ステップ５００）  各ノードに割り当てられたデータが入力されると、Mapper２０は、ユーザが定義した任意のMap処理を行う。各ノードが自らに割り当てた分散データを先頭から順に１行に対して１回、ユーザが定義したMap関数が適用される。その間パラメータが利用される際に、利用したMapperクラス名、関数、パラメータ名、パラメータ値を分散ファイルシステム１０に保存する。
【００７６】
ステップ５１０）  ステップ５００で生成されたKey-Value形式のデータが入力されると、キーが共通のものを集め（キー１つにリスト状の値となる）、ユーザが定義した任意のCombine処理を行う。その間、パラメータが利用される際に、利用したCombinerクラス名、関数、パラメータ名、パラメータ値を分散ファイルシステム１０に格納する。
【００７７】
ステップ５２０）  Reducer４０において、図２５のステップ２２０と同様の処理を行う。
【００７８】
ステップ５３０）  Reducer４０は、入力に対してユーザが定義した任意のReduce処理を行う。その間パラメータが利用される際に、利用したReducerクラス名、関数、パラメータ名、パラメータ値を分散ファイルシステム１０に保存する。
【００７９】
図９に実装時の処理イメージを示す。オープンソフトウェアであるMapReduceは、「Hadoop」を利用することにより容易に実現可能である。Hadoopにおいて、ジョブに予め与える全てのパラメータは"Configuration"という名のクラスで管理されており、MapReduce処理の過程でMapperやReducerはController(制御部５０または、JobTracker(後述する図１２))からこのConfigurationがファイルとして保存された場所を受け取り、そのファイルを読み込んで利用する。Configurationには、Mapper及びReducerが利用する(例えば、機械学習アルゴリズムに関する)パラメータの他、JobTrackerが利用するパラメータなども含む全てのパラメータが格納される。Configurationはパラメータをname/valueの組で管理しており、nameが問い合わせられたら対応するvalueを返すという形で利用される。本発明では、同図下段に示すように、これを検知用のものに入れ替えることで、パラメータ情報の検知を実現する。具体的には、パラメータ利用のために、Configurationにnameが送られたとき、単純にvalueを返答するだけでなく、同時に問い合わせ元のクラス名・関数名・パラメータ値などの情報を取得して別途HDFSに保存する。
【００８０】
［第３の実施の形態］
本実施の形態は、第２の実施の形態によって得られた情報を利用して、Map処理がパラメータに依存しない場合、統計的に同じパラメータが頻繁に利用される場合、ユーザが指定する場合に、Map処理の結果である中間データをキャッシュとして分散ファイルシステム１０に保存する。以降の処理において、保存した中間データをキャッシュとして利用可能な場合は、それを読み込んで、Reduce処理のみを行い、Map処理及びShuffle処理は行わない。
【００８１】
本実施の形態におけるシステム構成は第１の実施の形態と同様である。
【００８２】
図１０は、本発明の第３の実施の形態における中間データを保存するMapReduce処理のフローチャートである。同図に示す処理は、第１の実施の形態の図３のステップ６３０の処理に対応する。
【００８３】
ステップ８００）  図２５のステップ２００と同様にMap処理を行う。
【００８４】
ステップ８１０）  図２５のステップ２１０と同様にCombine処理を行う。
【００８５】
ステップ８２０）  図２５のステップ２２０と同様に、Shuffle処理を行う。
【００８６】
ステップ８３０）  上記の処理による中間データをキャッシュとして分散ファイルシステム１０に出力する。
【００８７】
ステップ８４０）  図２５のステップ２３０と同様の処理を行う。但し、Reducer４０に対して中間データ記憶部３０に保存されているShuffle済みの中間データを直接流し込むことで、Map処理及びShuffle処理をスキップする。
【００８８】
次に、上記の図５のステップ９３０の処理を説明する。
【００８９】
図１１は、本発明の第３の実施の形態における中間データを再利用したMapReduce処理のフローチャートである。
【００９０】
ステップ１１００）  Reducer４０は、キャッシュとして分散ファイルシステム１０に保存されている中間データを取得する。
【００９１】
ステップ１１１０）  Reducer４０は、取得した中間データを用いて、図２５のステップ２３０と同様の処理を行う。
【００９２】
以上、本発明の実施の形態を説明したが、本発明では、ユーザが中間データのキャッシュを陽に指定しない限り（自動的にキャッシュを行う場合）、最低３回のMapReduceを行う。１回目はパラメータ情報の検知、２回目で１回目の情報を利用した中間データのキャッシュ判定及びキャッシュ、３回目で２回目においてキャッシュした中間データを利用する処理量を削減する。
【実施例】
【００９３】
以下、本発明をオープンソース分散システムの「Hadoop」に適用した例を示す。
【００９４】
以下では、Hadoopにおいて、「パラメータ」は具体的にはConfigurationクラスを指す。Configurationクラスは、Hadoopによる一連のMapReduce処理の流れの中で、Hadoopそのもののパラメータ、ユーザが定義したMapper、Reducerを指定するパラメータ、MapperやReducer等で利用される変数等のパラメータなど、あらゆるパラメータを区別なく格納、管理するためのクラスであり、MapReduceに関わる様々なクラスがConfigurationクラスを継承あるいはConfigurationクラスを保持する形で利用する。パラメータは、「名前：値」の形でConfigurationクラスに格納され、必要とする型に応じたメソッドにパラメータの名前を与えると、その型の値が応答される。HDFSやローカルファイルに出力するために、XML形式に変換するメソッドを持つ。
【００９５】
「ジョブ（jobまたはJobConf）」は、Hadoopにおいて、具体的にはJobクラス、もしくは、JobConfクラスを指す。HadoopによるMapReduce処理を開始する際、ジョブを生成し、ジョブが提供する各種メソッドを用いて処理に利用するMapperクラスやReduceクラスなどを与え、開始メソッドによってMapReduce処理を開始することができる。Configurationクラスを内包し、与えられたパラメータは基本的に全てそちらに格納する。
【００９６】
なお、後述する「JobTracker」は前述の実施の形態における「制御部（Controller）５０」に対応する。
【００９７】
図１２は、HadoopによるMapReduce処理開始時の各ノードの動作を示す。
【００９８】
同図に示すシステムは、JobClient１３０２、MapReduceアプリケーション１３０１を有するクライアントノード１３００、JobTracker１３１１を有するJobTrackerノード１３１０、TaskTracker１３２１、Map or Reduceタスク１３２２を有するTrack Trackerノード１３２０から構成される。
【００９９】
まず、一般的なクライアントノード１３００の動作を説明する。
【０１００】
図１３は、クライアントノードの一般的な処理のフローチャートである。
【０１０１】
ステップ１４００）  クライアントノード１３００のJobClient１３０２は、Hadoopに含まれるJobクラスのインスタンスの生成時に、XML形式の初期パラメータが読み込まれ、Configurationクラスとしてジョブに与えられる。
【０１０２】
ステップ１４１０）  Mapper・Reducer・Key・ValueクラスなどのHadoopが必要とするパラメータや、処理の途中に利用する変数の初期値などのパラメータをジョブに与え（ジョブが保持するconfigurationにパラメータを与える）、固定のパラメータが与えられたジョブインスタンスを出力する。
【０１０３】
ステップ１４２０）  入力データの場所や実行時にユーザが変更可能なパラメータをコマンドライン引数の解析などによって取得し、ジョブに与える（ジョブが保持する    Configurationにパラメータを与える）。
【０１０４】
ステップ１４３０）  JobClient１３０２を利用してJobTrackerが動作しているサーバから新規のジョブのIDを取得し、ジョブに与える。
【０１０５】
ステップ１４４０）  ステップ１４３０で取得したジョブIDを元にした分散ファイルシステム１３３０上の所定の場所（パス）に、ステップ１４００、１４１０、１４２０によって生成、設置付与がなされたジョブをXMLとして出力する（また、入力データを示すファイルも所定の場所に出力する）。
【０１０６】
ステップ１４５０）  JobClient１３０２を利用して新しいジョブの追加をJobTracker１３１１に通知する。詳細について後述する。
【０１０７】
ステップ１４６０）  JobTracker１３１１において追加されたジョブが実行中ジョブとなり、キューに蓄積される。適宜キューを元にMapReduce処理が実行され、処理のログを標準出力に表示しながら終了まで待機する（Task Trackerノード１３２０のMap or Reduceタスク１３２２が全て終了まで待機する）。
【０１０８】
ステップ１４６０）  ステップ１４６０の処理が終了し、MapReduce処理のログ情報をMapReduce処理の結果として取得し、ユーザが定義した任意の処理を行う。
【０１０９】
図１４は、ジョブ追加時の処理のフローチャートであり、上記のステップ１４５０の詳細を示す。
【０１１０】
ステップ１５００）  入力されたジョブIDを元にしてジョブの初期化を行い、実行ジョブ(JobInProgress)を生成する。
【０１１１】
ステップ１５１０）  実行ジョブをキューに追加する。
【０１１２】
上記に示した処理は一般的な処理であるが、本発明では、図１４の処理の代わりに、図１５に示す処理を行う。
【０１１３】
図１５は、本発明の一実施例のジョブ追加時の処理のフローチャートである。
【０１１４】
ステップ１６００）  クライアントノード１３００のJobClient１３０２において、図２５のステップ２００と同様に、実行ジョブを生成する。
【０１１５】
ステップ１６１０）  ジョブが保持するConfigurationを参照し、パラメータ検知設定が有効か判定する。有効である場合はステップ１６２０に移行し、有効でない場合は、ステップ１６１１に移行する。
【０１１６】
ステップ１６１１）  Mapper・Reducerクラス名、入力データ名、パラメータを用いて分散ファイルシステム１３３０上のディレクトリを検索し、再利用可能な中間データのキャッシュがあるかどうか判定する。ある場合はステップ１６１２に移行し、ない場合は、ステップ１６４０に移行する。
【０１１７】
ステップ１６１２）  ジョブのConfigurationに対してReducerの処理が無しになるように操作し、Mapperクラスをスキップ用のものに入れ替え、ステップ１６４０に移行する。
【０１１８】
ステップ１６２０）  設定済みのMapper、Reducerは別の設定名として退避し、パラメータ検知用のMapper、Reducerに入れ替える。また、入れ替え済みのConfigurationの内容を分散ファイルシステム１３３０上に保存されているXMLにも反映する。
【０１１９】
ステップ１６３０）  ユーザによる明示的なキャッシュ有効指定がある場合には、常に『真』を、また、Mapper・Reducerクラスタ名、入力データ名、パラメータ名を用いて分散ファイルシステム１３３０上に蓄積されたパラメータの利用クラス・関数の情報を検索し、Mapperがパラメータに依存しない場合や、依存していても同じパラメータ値をユーザが指定する回数以上利用している場合に『真』を出力する。それ以外は『偽』を出力してステップ１６４０に移行する。
【０１２０】
ステップ１６３１）  ステップ１６３０において、『真』である場合には、実行ジョブのConfigurationに対して、中間データをキャッシュするためのフラグを付与する。
【０１２１】
ステップ１６４０）  図１４のステップ１５１０と同様に、実行ジョブをキューに格納する。
【０１２２】
次に、図１３のJobTrackerノード１３１０のJobTracker１３１１のジョブスケジューラの処理について説明する。
【０１２３】
図１６は、本発明の一実施例のジョブスケジューラの処理のフローチャートである。
【０１２４】
ステップ１７００）  JobTracker1311は、キューの中に実行ジョブがあるかどうかを判定し、ある場合は、ステップ１７１０に移行し、ない場合にはキュー待ちする。
【０１２５】
ステップ１７１０）  キューから実行ジョブを取得する。
【０１２６】
ステップ１７２０）  実行ジョブを元にして分散ファイルシステム１３３０の適切な場所からジョブのリソースを取得し、必要な数のMapタスク、Reduceタスクを生成する。
【０１２７】
ステップ１７３０）  終了判定として、終了フラグがあるかを判定する。終了フラグがある場合は当該処理を終了し、ない場合はステップ１７００に移行する。
【０１２８】
次に、TaskTrackerノード１３２０のTaskTracker１３２１のタスク取得処理について説明する。
【０１２９】
図１７は、本発明の一実施例のTaskTrackerのタスク取得ループの処理のフローチャートである。
【０１３０】
ステップ１８００）  TaskTrackerノード１３２０のTaskTracker１３２１は、JobTrackerノード１３１０のJobTracker１３１１に対して、自らの生存を確認させるためにハートビート（Heat Beat）を送出し、JobTracker１３１１からそれに対する応答を受け取る。
【０１３１】
ステップ１８１０）  TaskTracker１３２１は、JobTracker１３１１からの応答にタスクが含まれているかどうかを判定し、含まれている場合はステップ１８２０に移行し、含まれていない場合はステップ１８００に移行する。
【０１３２】
ステップ１８２０）  TaskTracker１３２１は、タスクがMapタスクであるかどうかを判定する。Mapタスクである場合はステップ１８２１に移行し、そうでない場合はステップ１８３０に移行する。
【０１３３】
ステップ１８２１）  TaskTracker１３２１は、与えられたMapタスクを実行し、ステップ１８００に移行する。詳細については図１８で後述する。
【０１３４】
ステップ１８３０）  タスクがReduceタスクであるかを判定する。Reduceタスクである場合はステップ１８３１に移行し、そうでない場合はステップ１８４０に移行する。
【０１３５】
ステップ１８３１）  与えられたReduceタスクを実行し、ステップ１８００に移行する。詳細は図１８で後述する。
【０１３６】
ステップ１８４０）  終了フラグがあれば、処理を終了し、なければステップ１８００に移行する。
【０１３７】
次に、上記のステップ１８２１，１８３１のタスク（Mapタスク、Reduceタスク）の開始の処理について説明する。
【０１３８】
図１８は、本発明の一実施例のタスク開始時の処理のフローチャートである。
【０１３９】
ステップ１９００）  TaskTracker１３２１は、パラメータ（Configuration）、ジョブの進捗状況（Status）、入出力などを含むContextクラスをタスクに応じて生成する。
【０１４０】
ステップ１９１０）  与えられたタスクに応じたクラス（MapperクラスまたはReducerクラス）を生成する。
【０１４１】
ステップ１９２０）  生成したContextクラスをMapperクラスまたはReducerクラスに与え、実行する。Mapperクラスの場合は、図１９の処理、Reducerクラスの場合は図２０の処理を実行する。
【０１４２】
上記のステップ１９１０でMapperクラスが生成された場合には、以下の処理を行う。
【０１４３】
図１９は、本発明の一実施例のMapperクラスが生成された場合の処理のフローチャートである。
【０１４４】
ステップ２２００）  Contextクラス（設定、タスクID、データの入出力、ジョブステータス、カウンタ等を持つクラス）、Mapperとして利用しているクラスが入力されると、Contextクラスが保持するConfigurationクラスを取り出し、それをパラメータが利用されたクラス・関数・順序を検知するためのConfigurationに入れ替える。
【０１４５】
ステップ２２１０）  Mapperクラスの名前をConfigurationから取り出し、通常のMapperクラスを生成する。
【０１４６】
ステップ２２２０）  ユーザの定義した任意の事前処理のみを行う。ここでは、MapperやReducerの中の関数名をそれぞれMapper内、Reducer内のものであることが明示的にわかるような関数名（検知が容易な関数名）にしておくことで、Mapper・Reducerどちらからパラメータが利用されたかを容易に判定できるようになる。
【０１４７】
ステップ２２３０）  割り当てられた入力データの一部及びContextクラスが入力されると、入力の次の１行に対して、検知が容易な関数名を用いてユーザの定義した任意のMap処理のみを行う。
【０１４８】
ステップ２２４０）  ステップ２２３０で読み込んだ行がデータの最終行であるかどうかを判断する。
【０１４９】
ステップ２２５０）  検知が容易な関数名を用いてユーザの定義した任意の終了処理のみを行う。
【０１５０】
次に、上記の図１９のステップ２２００で生成された検知用コンテキストに対してパラメータを要求するときの処理を説明する。
【０１５１】
図２０は、本発明の一実施例の検知用Configurationクラスのパラメータ呼び出し時の処理のフローチャートである。
【０１５２】
ステップ２３００）  Java（登録商標）の機能であるStack Traceを用いて、当該関数を呼び出した関数を辿り、呼び出し元のMapperクラス名と関数名を検知する。
【０１５３】
ステップ２３１０）  分散ファイルシステム１３３０上に、ステップ２３００の出力を呼び出し元クラス名、順序（数値）、関数名、パラメータ名をディレクトリ名、値をファイル名、頻度を内容としてファイルを生成し、分散ファイルシステム１３３０に出力する。
【０１５４】
ステップ２３２０）  保持しているプロパティクラスから、パラメータ名をキーとして値を取得し、呼び出したメソッドに適切な型に変換する。
【０１５５】
次に、図１８のステップ１９２０において、検知用Reducerを実行する場合の処理について説明する。
【０１５６】
図２１は、本発明の一実施例の検知用Reducerの処理のフローチャートである。
【０１５７】
ステップ２５００）  Contextクラス（設定、タスクID,）データの入出力、ジョブステータス、カウンタ等を持つクラス）、Reducerとして利用しているクラスの名前が入力されると、Contextクラスが保持するConfigurationクラスを取り出し、それをパラメータが利用されたクラス、関数、順序を検知するためのConfigurationに入れ替える。
【０１５８】
ステップ２５１０）  Reducerクラスの名前をConfigurationから取得し、通常のReducerクラスを生成する。
【０１５９】
ステップ２５２０）  検知が容易な関数名を用いて、ユーザの定義した任意の事前処理のみを行う。
【０１６０】
ステップ２５３０）  Contextクラス内のConfigurationにキャッシュ保存フラグがあるかを判定する。ある場合は、ステップ２５４０に移行し、ない場合はステップ２５５０に移行する。
【０１６１】
ステップ２５４０）  分散ファイルシステム１３３０内の所定の場所に、Mapperクラス名、Reduceクラス名、入力データ名、Keyをディレクトリとし、Valueイテレータの内容を全てそのディレクトリ内に出力する。
【０１６２】
ステップ２５５０）  割り当てられた中間データ（Key，Value）に対して、検知が容易な関数を用いてReduce処理を行う。
【０１６３】
ステップ２５６０）  ユーザが定義した任意の終了処理のみを行う。
【０１６４】
次に、図１８のステップ１９２０において、スキップ用Mapperを実行する場合の処理について説明する。
【０１６５】
図２２は、本発明の一実施例のスキップ用Mapperの処理のフローチャートである。
【０１６６】
ステップ２６００）  Reducerクラスの名前をConfigurationから取得し、通常のReducerクラスを生成する。
【０１６７】
ステップ２６１０）  ユーザの定義した任意の事前処理のみを行う。
【０１６８】
ステップ２６２０）  予め保存していた分散ファイルシステム１３３０上の中間データのキャッシュを読み込み、Key、Valueイテレータの形で取得する。
【０１６９】
ステップ２６３０）  割り当てられた中間データ（Key、Value）に対してReduce処理を行う。
【０１７０】
ステップ２６４０）  ユーザの定義した任意の終了処理のみを行う。
【０１７１】
なお、上記の図１に示す構成要素の動作をプログラムとして構築し、データ分析・機械学習装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１７２】
また、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１７３】
１０  分散ファイルシステム（HDFS）
２０  集計用データ作成部（Mapper）
３０  中間データ記憶部
４０  集計部（Reducer）
５０  制御部（Controller）
６０  結合部（Combiner）
７０  シャッフル部（Shuffle）
１３００  クライアントノード
１３０１  MapReduceアプリケーション
１３０２  ジョブクライアント（JobClient）
１３１０  ジョブトラッカ（JobTracker）ノード
１３１１  ジョブトラッカ（JobTracker）
１３２０  タスクトラッカ（TaskTracker）ノード
１３２１  タスクトラッカ（Task Tracker）
１３２２  Map or Reduceタスク
１３３０  分散ファイルシステム（HDFS）
【図１】
0005552449.tif 000002
【図２】
0005552449.tif 000003
【図３】
0005552449.tif 000004
【図４】
0005552449.tif 000005
【図５】
0005552449.tif 000006
【図６】
0005552449.tif 000007
【図７】
0005552449.tif 000008
【図８】
0005552449.tif 000009
【図９】
0005552449.tif 000010
【図１０】
0005552449.tif 000011
【図１１】
0005552449.tif 000012
【図１２】
0005552449.tif 000013
【図１３】
0005552449.tif 000014
【図１４】
0005552449.tif 000015
【図１５】
0005552449.tif 000016
【図１６】
0005552449.tif 000017
【図１７】
0005552449.tif 000018
【図１８】
0005552449.tif 000019
【図１９】
0005552449.tif 000020
【図２０】
0005552449.tif 000021
【図２１】
0005552449.tif 000022
【図２２】
0005552449.tif 000023
【図２３】
0005552449.tif 000024
【図２４】
0005552449.tif 000025
【図２５】
0005552449.tif 000026