(57)【要約】【課題】複数の処理装置を用いてデータ分析を行い、処理速度の遅い装置に影響されることなく、効率的にデータ分析を行う。【解決手段】分析管理装置と複数の分析実行装置を用いて、分析対象のデータからデータの特徴を記述したルールを求めるデータ分析方法において、分析管理装置は、データ分析問題を複数の部分問題に分割し、それぞれの部分問題を解くために必要な計算量を算出する部分問題調査処理と、部分問題の一部を解くために必要な計算量と、部分問題の一部を分析実行装置が解くのに要した時間より、該分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出し、推定値を基準として分析実行装置が次に解くべき部分問題を決定し、次に解くべき部分問題を分析実行装置に割り当てる問題割り当て処理を行い、分析実行装置は、該分析実行装置で解いた部分問題の計算量を分析管理装置に通知し、分析管理装置は、分析実行装置から通知された部分問題の規模より、分析実行装置が一定の時間で分析できる問題量を推定する処理を行う。【選択図】図１
2005107621.tif 000002
【特許請求の範囲】
【請求項１】
通信路を介して接続された分析管理装置と複数の分析実行装置を用いて、分析対象のデータからデータの特徴を記述したルールを求めるデータ分析方法において、
該分析管理装置は、データ分析問題を複数の部分問題に分割し、それぞれの部分問題を解くために必要な計算量を算出する部分問題調査処理と、部分問題の一部を解くために必要な計算量と、部分問題の一部を該分析実行装置が解くのに要する時間より、該分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出し、該推定値を基準として該分析実行装置が次に解くべき部分問題を決定し、次に解くべき部分問題を該分析実行装置に割り当てる問題割り当て処理を行い、
該分析実行装置は、該分析実行装置で解いた部分問題の計算量を分析管理装置に通知し、
該分析管理装置は、該分析実行装置から通知された部分問題の規模より、該分析実行装置が一定の時間で分析できる問題量を推定する処理を行うことを特徴とするデータ分析方法。
【請求項２】
前記問題割り当て処理は、データ分析問題に関する部分問題で該分析実行装置が解いた部分問題の履歴より、該分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出することを特徴とする請求項１に記載のデータ分析方法。
【請求項３】
該分析管理装置における部分問題の割り当て処理は、部分問題調査処理において分割された部分問題より1つ以上の部分問題を選択し、選択した部分問題を該分析実行装置に割り当てることを特徴とする請求項１に記載のデータ分析方法。
【請求項４】
該分析管理装置は、部分問題に関する情報を管理するテーブルをメモリに保持し、該テーブルに登録される、部分問題を一意に識別することができるＩＤ、部分問題の規模、部分問題の分析を担当する分析実行装置のＩＤ、部分問題の分析が完了したことを示すフラグ、部分問題の分析にかかった時間を参照して、分析実行装置を選定し、該選定された分析実行装置に対して次に解くべき部分問題を割り当てることを特徴とする請求項１記載のデータ分析方法。
【請求項５】
通信路に接続された複数のデータ処理装置にデータを分散して分析を行い、データの特徴を記述したルールを求めるデータ分析処理システムにおいて、
分析対象のデータを格納するデータ記憶装置と、
該データ記憶装置から送られるデータを分析の対象として部分問題を解く複数の第二のデータ処理装置と、
該複数の第二のデータ処理装置におけるデータの分析処理を管理する第一のデータ処理装置を有し、
該第一のデータ処理装置は、データ分析問題を複数の部分問題に分割して、それぞれの部分問題の規模を算出し、該第二のデータ処理装置で解いた部分問題の規模とその部分問題を解いた時間に従って、該第二のデータ処理装置が一定の時間で分析できる問題の規模を推定し、その推定値に近い規模を持つ部分問題を該第二のデータ処理装置に割り当て、
該第二のデータ処理装置は、自ら解いた部分問題の問題の規模を該第一のデータ処理装置に送信し、
該第一のデータ処理装置は、該第二のデータ処理装置から送られた問題の規模を含む情報を用いて該第二のデータ処理装置がデータの分析処理できる問題の規模を推定することを特徴とするデータ分析処理システム。
【請求項６】
前記第一のデータ処理装置は、部分問題を一意に識別することができるＩＤ、部分問題の規模、部分問題の分析を担当する分析実行装置のＩＤ、部分問題の分析が完了したことを示すフラグ、部分問題の分析にかかった時間を登録するテーブルを保持するメモリを有し、該テーブルを参照して、第二のデータ処理装置を選定し、選定された第二のデータ処理装置に対して次に解くべき部分問題を割り当てることすることを特徴とする請求項５記載のデータ分析処理システム。
【請求項７】
分析管理装置と、複数の分析実行装置を用いて、分析対象のデータからデータの特徴を記述したルールを求めるデータ分析方法において、
データ分析問題を複数の部分問題に分割し、それぞれの部分問題を解くために必要な計算量を算出するステップと、
部分問題の一部を解くために必要な計算量と、部分問題の一部を分析実行装置が解くのに要する時間より、該分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出し、該推定値を基準として該分析実行装置が次に解くべき部分問題を決定し、次に解くべき部分問題を分析実行装置に割り当てるステップと、
該分析実行装置で解いた部分問題の計算量を該分析管理装置に通知するステップと、
該分析実行装置から通知された部分問題の規模より、該分析実行装置が一定の時間で分析できる問題量を推定する処理を行うステップと、
を有することを特徴とするデータ分析方法。
【請求項８】
前記分析管理措置は、分析実行装置から問題の割当て要求に関する信号の受信をチェックし、該信号の受信が最も早い分析実行装置に対して、次に解くべき部分問題を割当てることを特徴とする請求項７記載のデータ分析方法。
【請求項９】
前記分析管理装置が有する処理装置により下記の式を実行して前記推定値を算出することを特徴とする請求項７又は８記載のデータ分析方法。
R_next = R_prev × (T_exp / T_prev)
ただし、R_prevは対象の分析装置が一つ前に割り当てられた部分問題の規模、T_prevはその部分問題を解くのにかかった応答時間、T_expは期待応答時間。
【請求項１０】
特徴ルールの探索空間を探索木で表し、該探索木の探索空間全体を分割することにより複数の部分問題に分割することを特徴とする請求項７又は８記載のデータ分析方法。
【請求項１１】
分析管理装置と、複数の分析実行装置を用いて、分析対象のデータからデータの特徴を記述したルールを求めるデータ分析を行うためのプログラムにおいて、
データ分析問題を複数の部分問題に分割し、それぞれの部分問題を解くために必要な計算量を算出する手段と、
部分問題の一部を解くために必要な計算量と、部分問題の一部を分析実行装置が解くのに要する時間より、該分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出し、該推定値を基準として該分析実行装置が次に解くべき部分問題を決定し、次に解くべき部分問題を分析実行装置に割り当てる手段と、
該分析実行装置から通知された部分問題の規模より、該分析実行装置が一定の時間で分析できる問題量を推定する処理を行う手段と、
を有することを特徴とするデータ分析用のプログラム。
【請求項１２】
請求項１１に記載のプログラムを格納する記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ分析方法に係り、特に複数の処理装置を利用して大量のデータを並列に処理するデータ分析方法に関する。
【背景技術】
【０００２】
大量のデータから知識を発見する技術はデータマイニングと呼ばれており、このデータマイニングを使用してデータの特徴を表現する特徴ルール(Characteristic Rule)を生成する方法が知られている。
特徴ルール及びその発見の方法については、例えば特開平８−７７０１０公報（特許文献１）に開示されているものがある。
【０００３】
これによれば、特徴ルールは「IF A THEN B」の形式で書き表すことができる。A(条件部と呼ばれる)は1個以上の条件の組み合わせ、B(結論部と呼ばれる)は単一の条件である。ここで「条件」とは、データの属性とその値の組であり、例えば「年齢=20代」のように記述される。
【０００４】
特徴ルールには、一般性(ある特徴ルールがどのくらい多くのデータに適用できるかを示す指標)と精度(ある特徴ルールの条件部がどのくらい正確に結論部を表しているかを示す指標)のトレードオフを考えて計算した評価尺度が定義される。この評価尺度は、「IF A THEN B」という特徴ルールにおいて、P(A)とP(B|A)の関数として算出される。ここでP(A)、P(B|A)はそれぞれ、全データの中で条件Aを満たすデータの割合、P(B|A)は条件Aを満たすデータの中で、さらに条件Bも満たすデータの割合である。特徴ルール生成のアルゴリズムはこの評価尺度を用いてルールを評価し、その値の高い順にソートしたランキングの上位が結果として出力される。
【０００５】
さらに、データマイニングのアルゴリズムは膨大な量のデータを計算する必要があるため、分散環境においてアルゴリズムを実行するための方法が提案されている。例えば、特開２００１−１６７０９８公報（特許文献２）には、複数の分析装置を用いて特徴ルールを発見する手法について開示されている。
この方法によれば、与えられた問題において、考えうる全ての特徴ルールの評価尺度を算出するのに必要な値を計数するカウンタを、複数のデータ分析装置で分割して保持している。この方法においては、一台のデータ格納装置が複数全ての分析装置に対して同時に、1レコードづつデータを送信し、全ての分析装置はP(A)、P(B|A)の値を算出するために、受信した1レコードのデータについて条件を満たすカウンタをカウントアップする。全ての分析装置がこの処理を終えた後、データ格納装置は次のデータを分析装置に送信する。これを繰り返して、全レコードについてデータを処理し、その後、全ての特徴ルールの評価値を算出し、評価尺度が上位の特徴ルールを結果として出力する。
【０００６】
【特許文献１】特開平８−７７０１０公報
【０００７】
【特許文献２】特開２００１−１６７０９８公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記の従来の技術には以下のような課題がある。
特許文献１に開示されているアルゴリズムは、単一の処理装置を用いてルールを発見することを前提にしているため、項目数が増えて探索するルールの数が増加した場合に1台の装置では十分な計算能力が得られず、アルゴリズムが停止するまでに非常に長い時間がかかるという問題がある。特に、条件部に許される条件の数を増やして特徴ルール発見の探索を行った場合、探索すべきルールの数は爆発的に増加するため、この探索に要する時間も膨大になる。
【０００９】
また、特許文献２に述べられている方法は、分析対象データ1レコードの処理ごとに、全ての処理装置が処理を終えるまで次のレコードの処理に移らないので、分析を行うシステム全体の処理速度は、最も処理の遅い分析装置に合わせられ、その処理速度以上にはならない。またこの方法は、1レコードの処理をするごとにデータをメモリに保持せずに捨ててしまっているため、特徴ルールを生成する場合、全ての考えうるルールについてのカウンタを保持しなければならない。このため、探索するルールの条件節が増えた場合に考えうる特徴ルールの数が爆発的に増加し、それにあわせて膨大な量のメモリが必要になるという問題が生ずる。例えば、レコード数が少なく項目数が非常に多いデータから多くの条件の組み合わせを含む特徴ルールを生成したい場合などには、カウンタを分散して保持しても、必要なメモリ量の爆発的な増加に対応できない可能性がある。
【００１０】
本発明の目的は、複数の処理装置にデータを分散してデータ分析を行うことにあり、とりわけ処理速度の遅い装置に影響されることなく、効率的にデータの分析を行う方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明は、通信路に接続された複数のデータ処理装置にデータを分散して分析を行い、データの特徴を記述したルールを求めるデータ分析処理システムにおいて、分析対象のデータを格納するデータ記憶装置と、該データ記憶装置から送られるデータを分析の対象として部分問題を解く複数の第二のデータ処理装置（分析実行装置）と、複数の第二のデータ処理装置におけるデータの分析処理を管理する第一のデータ処理装置（分析管理装置）を有し、第一のデータ処理装置は、データ分析問題を複数の部分問題に分割して、それぞれの部分問題の規模を算出し、第二のデータ処理装置で解いた部分問題の規模とその部分問題を解いた時間に従って、第二のデータ処理装置が一定の時間で分析できる問題の規模を推定し、その推定値に近い規模を持つ部分問題を第二のデータ処理装置に割り当て、
第二のデータ処理装置は、自ら解いた部分問題の問題の規模を該第一のデータ処理装置に送信し、第一のデータ処理装置は、第二のデータ処理装置から送られた問題の規模を含む情報を用いて第二のデータ処理装置がデータの分析処理できる問題の規模を推定する。
【００１２】
好ましい例では、第一のデータ処理装置は、部分問題を一意に識別することができるＩＤ、部分問題の規模、部分問題の分析を担当する分析実行装置のＩＤ、部分問題の分析が完了したことを示すフラグ、部分問題の分析にかかった時間を登録するテーブルを保持するメモリを有し、このテーブルを参照して、第二のデータ処理装置を選定し、選定された第二のデータ処理装置に対して次に解くべき部分問題を割り当てる。
【００１３】
また本発明は、分析管理装置と、複数の分析実行装置を用いて、分析対象のデータからデータの特徴を記述したルールを求めるデータ分析方法として把握される。このデータ分析方法は、データ分析問題を複数の部分問題に分割し、それぞれの部分問題を解くために必要な計算量を算出するステップと、部分問題の一部を解くために必要な計算量と、部分問題の一部を分析実行装置が解くのに要する時間より、分析実行装置が一定の時間で分析できる部分問題の規模の推定値を算出し、推定値を基準として分析実行装置が次に解くべき部分問題を決定し、次に解くべき部分問題を分析実行装置に割り当てるステップと、分析実行装置で解いた部分問題の計算量を分析管理装置に通知するステップと、分析実行装置から通知された部分問題の規模より、分析実行装置が一定の時間で分析できる問題量を推定する処理を行うステップと
を有する。
【００１４】
好ましい例では、前記分析管理措置は、分析実行装置から問題の割当て要求に関する信号の受信をチェックし、該信号の受信が最も早い分析実行装置に対して、次に解くべき部分問題を割り当てる。
また、分析管理装置は処理装置を備え、下記の式を実行して上記推定値を算出する。
R_next = R_prev × (T_exp / T_prev)
ここで、R_prevは対象の分析装置が一つ前に割り当てられた部分問題の規模、T_prevはその部分問題を解くのにかかった応答時間、T_expは期待応答時間。
更に好ましい例では、特徴ルールの探索空間を探索木で表し、該探索木の探索空間全体を分割することにより複数の部分問題に分割する。
【００１５】
本発明は、また上記処理と行うプログラムおよびそれを格納する記憶媒体として把握される。
【発明の効果】
【００１６】
本発明によれば、特徴ルール生成のための分析問題を複数の部分問題に分け、一回の部分問題の分析が期待応答時間程度で終わるように分析実行装置に与える部分問題の規模を調整することにより、処理速度の遅い分析実行装置の処理に影響されることなく、効率的にデータ分析を行える。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態について説明する。
図１は本実施形態によるデータ分析処理システムの構成を示す。
この処理システムにおいて、分析管理装置101、データ記憶装置108、複数の分析実行装置109が、バス型の通信路110を介して接続して構成される。分析管理装置101は、処理装置102、入出力装置105、記憶装置107を備え、これらの装置は内部バスのような通信路111を介して接続されている。また処理装置102はメモリ103を備え、そのメモリ103には処理装置の処理に必要なデータを一時的に格納すると共に、処理の実行を行うプログラム104を格納する。入出力装置105は、キーボードのような入力器や表示器を含む入出力機器を有し、また装置の外部とのデータ通信を管理する通信装置106を有する。分析管理装置101はこの通信装置106を介して通信路110と接続される。記憶装置107は大量のデータを記憶する容量を持つ例えばハードディスク装置である。
データ記憶装置108は例えばハードディスク装置であり、分析の対象となる大量のデータを記憶すると共に分析結果のデータを記憶する。分析データを記憶するためにデータベースＤＢを有する。
【００１８】
ここで図１の、分析実行装置109の内部の詳細なハードウェアの構成については示してないが、分析管理装置101及び分析実行装置109は、データ処理処置であり、これらは実質的に同様の構成を成す、処理装置、記憶装置、入出力装置を備えている。例えば、これら分析管理装置101及び分析実行装置109、更にはデータ記憶装置108も含めて、同様の処理装置、記憶装置、入出力装置、記憶装置を備えたパーソナルコンピュータで構成することもできる。
【００１９】
本実施形態では、知識の発見ために特徴ルールを生成するアルゴリズムを用いる。以下に、特徴ルール生成について詳細を説明する。まず始めに、分析対象データと分析結果の特徴ルールについて述べる。
【００２０】
図２は、本実施形態で使用される分析対象データの例を示す。
分析対象データは複数の属性項目(以下、単に項目と言う)からなるレコードの集合であり、全てのレコードは同じ項目を持っている。項目にはそれぞれのレコードのある属性を表す値が格納されている。レコードや項目が具体的に何を表すかは分析対象のデータに依存する。例えば、ある商店の購買履歴のデータを分析対象とする場合、1つのレコードは１人の顧客に対応し、１レコードの各項目はその顧客毎の顧客ＩＤ、性別、年齢、購買頻度、購入総額などの属性を表す。
【００２１】
特徴ルール生成では、前処理としてそれぞれの項目の属性値を少数のカテゴリに変換する場合がある。この処理をカテゴリ化と呼ぶ。例えば、年齢は通常10〜100程度の属性値を取り得るが、これを「25歳以下」、「26歳から35歳」、「36歳以上」のようにカテゴリに変換する。この場合は年齢という属性項目を3つのカテゴリに変換したことになる。性別のように元々「男」「女」の２値しか値を取らないものは、そのままカテゴリとして用いることもある。この場合、性別は２つのカテゴリを持つ属性項目である。図２の分析対象データは、このようなカテゴリ化の処理を施したものである。
【００２２】
特徴ルールは、例えば次のように書き表すことができる。
「IF 年齢=26〜35 AND 購買頻度=高 THEN 購入総額=高」。
すなわち特徴ルールは、属性項目とそのカテゴリを組み合わせた節をIF以下の条件部とTHEN以下の結論部に持つ、IF〜THENルールである。条件部に現れる属性を条件項目、結論部に現れる属性を結論項目と呼ぶ。また、特徴ルールの条件部に現れる条件項目とそのカテゴリの組を指して、条件節と呼ぶ。
【００２３】
特徴ルールはそのルールがどの程度対象データの特徴を表しているかを定量的に評価する指標となる評価値を持つ。特徴ルールを一般的に「IF A THEN B」と表す場合、評価値は次の式で定義される。
【００２４】
P(A)^a * log(P(B|A)/P(B))
ここでP(A)、P(B)はそれぞれ、分析対象データ全体のうちで、条件A、条件Bを満足するレコードの割合であり、P(B|A)は条件Aを満足するレコードのうち条件Aと条件Bの両方を満足するレコードの割合である。また、指数aはルールの評価において一般性(あるルールがどのくらい多くのデータに適用できるかを示す指標)と精度(あるルールの条件部がどのくらい正確に結論部をあらわしているかを示す指標)のどちらに重点をおくかを定める正の定数であり分析者によって指定される。この評価値の別の定義としては、次の式を用いて評価値を定める場合もある。
【００２５】
P(A)^a * P(B|A) * log(P(B|A)/P(B))
評価値にいずれの値を用いるにしても、ある特徴ルールに現れる条件節を満たすレコード、および分析対象データ全体のレコードの数を知ることによって、評価値を算出することができる。特徴ルール生成ではこの評価値によって特徴ルールを評価し、評価値の高い特徴ルールから順にソートしてその上位を結果として出力する。
ソートされた特徴ルールの例を図３に示す。
【００２６】
特徴的ルール生成とは、上記で定義した評価値に基づき、評価値の大きな特徴ルールを発見するアルゴリズムである。この処理を行うにあたっては、処理を実行する前に分析者によって、発見すべき特徴ルール数の上限、結論項目となる項目とそのカテゴリ、条件部に含まれる項目の候補となる複数の項目(以下、条件候補項目という)、一つの特徴ルールに含まれる条件項目の数の上限(以下、最大条件節数という)が与えられているものとする。
【００２７】
生成され得る特徴ルールの全ての組み合わせは、図４に例示する木構造のように書き表すことができる。
この例では結論部を「購入総額=高」として特徴ルールを発見しようとしている場合を仮定している。この木構造において、ルートノード401を除く全てのノードは一つの特徴ルールに対応する。例えば、破線で囲まれた階層404には条件候補項目とそのカテゴリの考え得る全ての組み合わせがノードとして含まれており、それぞれのノードは1つの条件項目を持つルールに対応している。ノード402は「IF 性別=男 THEN 購入総額=高」というルールに対応している。また階層404の全てのノードの下には、上位のノードに現れる条件候補項目を除く全ての条件候補項目とそのカテゴリの全組み合わせがノードとして含まれている。ただし、IF A AND B THEN Xと、IF B AND A THEN Xは同じルールを表しているので、このような重複がある場合は、同じルールとなるノードは一つを残して省かれている。また一般に、あるノードの下には、ルートノードからそのノードに至るパスに現れた条件候補項目を除く全ての条件候補項目とそのカテゴリの全組み合わせから、さらに前記の重複を除いた組み合わせが、ノードとして含まれている。
このようにして構成される木構造の階層405は、2つの条件項目をもつルールと対応する。例えばノード403は、「IF 性別=男性 AND 購買頻度=高 THEN 購入総額=高」というルールに対応する。
【００２８】
別の例として、A、B、C、D、Eの５つの項目(各項目はカテゴリ化されている)を条件候補項目として特徴ルールを生成する場合の探索木を図５、図６に示す。ここでは最大条件節数は３としている。この値は、ルートノードを除いた木の高さに対応する。
図５の例では、木の高さは３である。一つの特徴ルールに同じ条件項目が重複して現れることはなく、また、特徴ルールでは条件項目の組み合わせのみを考慮すればよいので、その探索木は図５のようになる。例えば前述したように、「IF A=a1 and B=b1」と「IF B=b1 and A=a1」という条件部は同じものである。つまり、条件項目の出現順序は考慮する必要が無い。ここでa1は項目Aの、b1は項目Bのカテゴリである。ただし、図５は探索木全体を簡略化して描いたものであり、(A)など、条件候補項目の名称を括弧でくくったノードは「A=a1」「A=a2」…(a1、a2…は属性項目Aをカテゴリ化したときのカテゴリ名)という複数のノードを代表して示したものである。特徴ルールの探索木では、同じ階層に存在する、同じ属性項目のノードであれば(つまり、階層・属性項目が同じで、カテゴリのみが異なる場合)、そのノードより下位に存在する部分木の形は同じになるので、たとえば部分木504に含まれているルートノード以下(C)−(D)−(E)という枝は実際には図６のような木構造をしていることになる。ただし、ここでは項目Cがc1、c2という二つのカテゴリ、項目Dがd1、d2という二つのカテゴリ、項目Eがe1、e2、e3という3つのカテゴリにカテゴリ化されているものとする。
【００２９】
特徴ルール生成においてルールを発見するアルゴリズムの考え方は、このような木構造において各ノード(ルール)を評価し、評価値の高いルールを選び出すということと同等であると考えるられる。
【００３０】
本実施例では、この探索木の探索空間全体を分割することにより、問題の全体を部分問題に分割することを考える。この部分問題の切り出し方の一例を、図５を用いて説明する。
図５は、特徴ルールの探索空間を探索木として表したものである。ここでは1条件を持つ特徴ルールの集合である501の階層に着目し、この階層の、ある条件候補項目を条件節にもつルールに対応するノードとそのノードをルートノードとして持つ部分木の全体をひとつの部分問題とみなす。すなわち部分木502〜部分木506はそれぞれ部分問題に対応している。
【００３１】
また、それぞれの部分問題で評価する必要のあるルール数は以下のように計算することができる。条件候補項目がA、B、C、…、Xとあり、Aから順に組み合わせの探索を開始する時、最後に探索される条件候補項目Xの番号を1として、探索される順序とは逆に条件候補項目に2、3、…、Mと項目番号を振る(Mは条件候補項目の数)。また、探索木において、あるノードが存在する階層は対応する特徴ルールの条件節の数に相当するが、最大の条件節数を持つルールに対応する階層の番号を1とし、階層が深い順に2、3、…、Nと番号を振る(Nは最大条件節数になる)。すると階層nに存在する項目番号mのノードについて、そのノードをルートとする部分木において評価するべき特徴ルールの総数R(m, n)は以下の漸化式によって算出される。
【００３２】
R(m, n) = C(m-1) × R(m-1, n-1) + R(m-1, n)
ここで、R(m, 1) = R(1, n) = 1とする。また、C(m)は項目番号mの条件項目のカテゴリ数である。図５におけるそれぞれの部分問題で評価する必要のあるルール数は、その条件候補項目の項目番号をmとすると、R(m, N)×C(m)として算出することができる。
【００３３】
次に、図７を参照して本実施例におけるデータ分析の処理の詳細について説明する。
図７は、分析管理装置101におけるデータ分析管理の処理フローを示す。この処理はメモリ103に格納されたプログラム104の実行により行われる。
【００３４】
初期化処理701において、データ分析を行うための準備として、分析対象のデータを分析実行装置109に送信する処理、分析結果のルールを格納する処理、分析の初期条件の設定処理が行なわれる。
【００３５】
即ち、当初データ記憶装置108のＤＢに格納される図２に示す分析対象データは、分析の処理に当たってデータ記憶装置108から通信路110を介して各分析実行装置109に送られ、各分析実行装置の記憶装置に格納される。
【００３６】
分析の初期条件には、発見すべき特徴ルール数の上限R_max、結論項目となる属性項目とそのカテゴリ、条件候補項目、一つの特徴ルールに含まれる条件項目の数の上限である最大条件節数C_max、分析実行装置に割り当てる部分問題の規模の初期値R_ini、分析実行装置が1回で割り当てられた部分問題を解くのに期待される応答時間である期待応答時間T_expが含まれる。これらの値は,入出力装置105から分析者により入力される。初期化処理701が終了すると、ステップ0702に進む。
【００３７】
部分問題調査処理702では、図５により説明した方法で、特徴ルールの探索木を部分木、即ち部分問題に切り分け、上記の漸化式によってそれぞれの部分問題の規模を算出し、部分問題の情報を管理するテーブルに格納し、ステップ703に進む。
【００３８】
図８に部分問題を管理するテーブルの一例を示す。このテーブルにはメモリ103に格納されており、全ての部分問題について、部分問題を一意に識別することができるＩＤ番号、部分問題の規模、部分問題の分析を担当する分析実行装置のID、部分問題の分析が完了した場合にそのことを示すフラグ、その部分問題の分析にかかった時間が登録される。ここで、メモリには、分析対象データを格納する領域、分析のための条件を格納する領域、上位R_max個のルールを格納する領域、部分問題の規模を格納する領域が確保され、使用される。また、この分析条件には上記の初期条件で設定した各条件に加え、枝刈りのためのパラメータや、分析実行装置を管理するためのテーブルが含まれている。
【００３９】
図９は、図７のフローチャートにおける分析実行装置の管理処理703の詳細を示す。
ステップ901では分析の実行を許可する信号が分析実行装置109から送られてきているかどうかをチェックする。ある分析実行装置からの許可信号を受信すればステップ902に進む。一方、許可信号が受信されなければステップ903に進む。
【００４０】
分析実行装置追加処理902では、ステップ901で受け取った信号の発信元である装置のひとつについて、分析実行装置を管理するテーブルに、発信元の装置を登録し、この装置にデータ記憶装置108から分析対象データを取得するよう指示する信号を送信した後、ステップ901に戻る。分析実行装置の管理テーブルは、メモリ103に形成され、データの分析実行が許可された装置を順次登録する。テーブルに登録される内容としては、少なくとも分析実行装置を識別するためのＩＤと、この分析実行装置と通信路を用いて通信する際に必要な情報を含む。この情報は、例えばTCP/IPを用いて通信を行う場合では、分析実行装置のIPアドレスとポート番号である。このテーブルの一例を図10に示す。
【００４１】
ステップ903では、分析実行の中断を要求する信号が分析実行装置から送られて、受信されたか否かをチェックする。もし、ある分析実行装置から送られた中断要求信号が受信されればステップ904に進む。そのような信号が受信されなければ、分析実行装置管理処理703の処理を終了し、ステップ704に進む。分析実行装置削除処理904では、ステップ903で受け取った中断要求の信号の発信元である分析実行装置のＩＤを管理テーブルから削除する。この結果、その装置は分析実行の対象から外される。
【００４２】
図１１は、図７のフローチャートにおける問題割り当て処理のステップ704の詳細を示す。
ステップ1101では、分析実行装置から問題の割り当て要求の信号を受信しているかどうかをチェックする。もし割り当ての要求の信号を受信しているとステップ1102に進み、受信しなければ問題割り当て処理を終了し、ステップ705に進む。
【００４３】
分析装置選択処理1102では、ステップ1101で受け取った割り当て要求の信号の発信元である分析装置から、分析管理装置で信号の受信が最も早かった分析装置を、問題を割り当てる対象として選択する。問題生成処理1103では、対象の分析装置が初期化処理701以降に問題の割り当てを受けたことがあるかどうかを図８のテーブルの担当分析装置を参照してチェックする。もし、問題の割り当てを受けていなければ、まだ割り当てを行っていない部分問題の中から、問題規模初期値R_iniに最も近い規模の部分問題を、その分析実行装置が解くべき部分問題として割り当てる。この割り当ては図８のテーブルの、割り当てる部分問題に対応する担当分析装置の項目に、分析装置のIDを記録することにより行う。部分問題の割り当てを受けたことがあれば、直前に割り当てを行った部分問題を解くのにかかった時間をチェックし、次の式より算出される問題規模R_next（推定値）に最も近い規模を持つ部分問題を、その分析実行装置が解くべき部分問題として割り当てる。
【００４４】
R_next = R_prev × (T_exp / T_prev)
ただし、ここでR_prevは対象の分析装置が一つ前に割り当てられた部分問題の規模、T_prevはその部分問題を解くのにかかった応答時間、T_expは期待応答時間である。なお、問題を割り当てる時点で全ての部分問題について割り当てが終わっていれば、問題の割り当ては行わない。問題割り当て実行処理1104では、ステップ1103で割り当てた分析処理装置が実行すべき問題と、枝刈りのパラメータを含む分析のための条件を、分析実行装置に送信する。もし、全ての部分問題の割り当てが完了しており、ステップ1103で部分問題の割り当てが行われなかった場合には、もう割り当てるべき部分問題が無いという情報を分析実行装置に通知する。
【００４５】
ここで、部分問題の割り当てを実際に行うために対象の分析実行装置が解くべき部分問題を送信する方法は、分析実行装置が分析を行う部分木が分析実行装置に正確に伝わるような方法であれば任意だが、例えば図５を用いて説明した探索木を考える場合には、分析実行装置が探索するべき部分木のルートノードの情報を分析実行装置に送信すればよい。
【００４６】
結果登録処理705では、結果登録の要求が来ているかどうかをチェックする。もし結果登録要求が来ていれば、結果登録要求の発信元である分析実行装置より、結果としてR_max個の候補ルールと分析にかかった時間を受け取り、分析管理装置の中で保持している候補ルールとあわせて評価尺度の順にルールをソートし、上位R_max個の候補ルールを更新する。部分問題の分析実行にかかった時間は、図８のテーブルの分析時間の欄に記録する。
【００４７】
ステップ706では図8のテーブルより全ての部分問題について分析が終了したかどうかをチェックする。もし分析が終了していればステップ707に進み、終了していなければステップ703の前に戻る。ステップ707では、分析管理装置の中で保持されている候補ルールを最終的な結果として出力し、分析を終了する。
以上が分析管理装置における処理の詳細である。
【００４８】
次に、分析実行装置109における処理の詳細について述べる。分析実行装置109における処理の詳細を図１２に示す。
分析装置登録処理1201では、分析の実行を許可する信号を分析管理装置101に送信する。その後、分析管理装置のテーブルに登録が終了したら、データ記憶装置より分析対象データを取得する。
【００４９】
問題割り当て要求処理1202では、分析管理装置に問題の割り当てを要求し、分析実行装置が実行すべき問題と枝刈りのパラメータを含む、分析のための条件を受信する。受信する問題の具体的な形式については、分析実行装置が分析を行う部分木が正確に伝わるような方法であれば任意であるが、例えば図５の木構造を仮定するような場合には、分析実行装置が探索するべき部分木のルートノードを分析管理装置101から受信すればよい。
【００５０】
ステップ1203ではステップ1202の受信の内容をチェックする。もし、割り当てる問題が無い旨を受信したならばステップ1207に進む。一方、問題の割り当てがあった場合はステップ1204に進む。分析実行処理1204では、割り当てられた部分問題に対応する部分木を分析し、分析結果の候補となる評価値の高いR_max個の特徴ルールを発見する。またこの時、探索にかかった時間を計測する。
【００５１】
結果送信処理1205では、ステップ1204で発見した特徴ルールに関する情報と分析にかかった時間を分析管理装置101に送信する。ここで分析管理装置に送信する特徴ルールの情報は、それぞれの特徴ルールの条件部に含まれる条件項目とカテゴリの組、それぞれの特徴ルールの評価値を含んでいる。
【００５２】
また、このステップ1201からステップ1205を実行している装置では同時に中断受付処理1208が実行されており、分析実行装置内の入力装置から中止の指示を受信した場合には分析を中断させるフラグを立てる。
【００５３】
ステップ1206では、分析中断フラグが立っているかどうかをチェックする。もし、分析中断のフラグが立っていれば、ステップ1207の分析終了処理に進む。フラグが立っていなければステップ1202に戻る。
分析終了処理1207では、ステップ1201で格納したデータなどの領域を解放し、分析管理装置に分析の実行を中断する信号を送信するなど、分析の後処理を行って、分析実行装置における処理を終了する。
【００５４】
以上、一実施例について説明したが、上記実施例をさらに以下のように変形して実施することができる。
【００５５】
例えば、図１１に示す問題生成処理1103において、対象の分析実行装置に次に割り当てる問題の規模を算出する際に、直前に解いた問題の規模と解くのにかかった時間のみから算出するのではなく、初期化処理701以降に解いた全ての部分問題について、上記実施例と同じ計算を行い、この算術平均を取ることにより対象の分析実行装置に次に割り当てる問題の規模を算出することもできる。この例によって、対象の分析実行装置が期待応答時間で解ける問題の規模をより正確に推定することができる。
【００５６】
また他の例として、問題生成処理1103において、対象の分析実行装置への部分問題の割り当ては、一つの部分問題のみを割り当てるのではなく、いくつかの部分問題の組み合わせを対象の分析実行装置に割り当てるように変更して実施することが可能である。
R_nextを算出し、一つの部分問題を割り当てた時点で、その部分問題の規模とR_nextを比較する。R_nextの方が大きい場合には、対象の分析実行装置は期待応答時間内にまだ別の部分問題を解くことができると考えられるので、R_nextと分析実行装置に割り当てられた部分問題の規模の総和の差に最も近い規模を持ち、かつ初期化処理0701以降まだ割り当てが行われていない部分問題をこの分析実行装置に割り当てる。このようにして、分析実行装置に割り当てられた部分問題の規模の総和が、R_nextを越えるまで割り当てを繰り返す。この処理によって部分問題の集合を、対象の分析実行装置への割り当てとする。
この例によれば、分析管理装置と分析実行装置間の通信量、通信回数を減らすことができ、通信のための処理の量を削減することができる。
【００５７】
また、他の例として、図１２に示す結果送信処理1205において、分析実行装置が分析管理装置に送信する結果の情報に、実際に評価した特徴ルールの数を付加し、この値を分析実行装置の部分問題を管理するテーブルに格納するように変更して実施することもできる。
特徴ルール生成では、ルールを評価する際に一定値より高い評価値の特徴ルールが存在しないことが事前にわかっている探索空間については探索を省く場合がある。この処理は枝刈りと呼ばれる。この変形例によれば、分析実行装置で実際に評価したルールの数と、分析管理装置が前もって算出した部分問題の規模が異なるような分析を行った場合でも、分析実行装置が期待応答時間で解ける部分問題の規模を正確に把握できる。
【００５８】
この実施例によるデータ分析方法は、図２に示すような購買データの分析や、例えばＤＮＡチップを用いた遺伝子発現解析などの、膨大なデータの分析に使用され得る。
【００５９】
以上説明したようにいくつかの実施例によれば、複数の分析実行装置に分析データを分散して、処理速度の遅い装置に影響されることなく、効率的にデータ分析を行うことができる。
【００６０】
また、各分析実行装置が分析対象データを保持して分析を行うので、条件候補項目数、最大条件節数をいくつに定めるかによらず、各分析実行装置は、考え得る全ての特徴ルールに対応するカウンタを持つ必要なく分析を行うことができ、分析対象データ自体はそれほど大きく無いが多くの条件の組み合わせを含む特徴ルールを生成したいような場合に、分析実行装置に必要なメモリの量を少なく抑えた上で分析を行うことができる。
【図面の簡単な説明】
【００６１】
【図１】一実施形態によるデータ分析を行うための処理システムを示す図である。
【図２】一実施形態における分析対象となるデータの一例を示す図である。
【図３】特徴ルールの一例を示す図である。
【図４】特徴ルールを発見するための探索空間を木構造で表した例を示す図である。
【図５】特徴ルールを発見するための探索空間を木構造で表した別の例を示す図である。
【図６】図５の木構造の一部分を詳細に示した図である。
【図７】一実施形態による分析管理装置における処理の詳細を示すフローチャートである。
【図８】部分問題に関する情報を格納するテーブルの一例を示す図である。
【図９】図７のフローチャートにおける分析実行装置管理処理７０３の詳細を示すフローチャートである。
【図１０】分析実行装置の管理テーブルの一例を示す図である。
【図１１】図７のフローチャートにおける問題割り当て処理７０４の詳細を示すフローチャートである。
【図１２】一実施形態による分析実行装置109の実行アルゴリズムの全体を示すフローチャートである。
【符号の説明】
【００６２】
１０２…処理装置、              １０３…メモリ、
１０４…プログラム、            １０５…入出力装置、
１０６…通信装置、              １０７…記憶装置、
１１０…通信路、                １１１…通信路
【図１】
2005107621.tif 000003
【図２】
2005107621.tif 000004
【図３】
2005107621.tif 000005
【図４】
2005107621.tif 000006
【図５】
2005107621.tif 000007
【図６】
2005107621.tif 000008
【図７】
2005107621.tif 000009
【図８】
2005107621.tif 000010
【図９】
2005107621.tif 000011
【図１０】
2005107621.tif 000012
【図１１】
2005107621.tif 000013
【図１２】
2005107621.tif 000014