(57)【要約】【課題】複数台の処理装置を用いて行うデータ分析において、処理装置同士の待ち時間を少なくして、全体の処理効率あげる。【解決手段】通信路０１１０を介して接続された、１台のマスタ０１０１と複数のスレーブ０１０９を用いて、データ分析処理を行う。このデータ分析処理において、マスタ０１０１は、データ分析問題をスレーブ０１０９の台数よりも多い数の部分問題(ジョブ)に分割して、それらのジョブをスレーブに割り当てる。スレーブ０１０９は、マスタ０１０１から割り当てられたジョブを処理して、その処理結果をスレーブ内に保存し、マスタにジョブを要求するという処理を、マスタからのジョブの割り当てが停止するまで繰り返す。最終的に、スレーブ０１０９は、保存中の処理結果をマスタ０１０１に送信する。マスタ０１０１は、全スレーブ０１０９から分析結果を受け取ると、全体の分析結果を出力する。【選択図】図１
2005275440.tif 000002
【特許請求の範囲】
【請求項１】
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて、分析問題のデータ分析を行うデータ分析方法において、
前記第１データ処理装置が、前記分析問題を、前記第２データ処理装置の数よりも多い複数の部分問題に分割し、前記複数の第２データ処理装置のそれぞれに当該部分問題を１ずつ割り当てる処理と、
前記複数の部分問題のすべてがいずれかの第２データ処理装置に割り当て済みとなるまで、前記第１データ処理装置が、前記複数の第２データ処理装置のいずれかの第２データ処理装置が、当該第２データ処理装置に割り当てられた部分問題の処理を終了させるごとに、前記複数の部分問題のうち、未割り当ての部分問題を当該第２データ処理装置に割り当てる処理と、
前記第１データ処理装置が、前記各第２データ処理装置から、当該第２データ処理装置に割り当てられた部分問題の処理結果を受け付ける処理と、
を有することを特徴とするデータ分析方法。
【請求項２】
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて、分析問題のデータ分析を行うデータ分析方法において、
前記第１データ処理装置からの、前記分析問題の部分問題の割り当てが停止するまで、前記各第２データ処理装置が、前記第１データ処理装置から前記分析問題の部分問題が割り当てられるごとに、当該部分問題を処理して、当該処理の結果を保存する処理と、
前記分析問題の部分問題の割り当てが停止した第２データ処理装置が、前記保存している処理結果を前記第１データ処理装置へ送信する処理と、
を有することを特徴とするデータ分析方法。
【請求項３】
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて分析問題の分析を行うデータ分析方法において、
前記各第２データ処理装置は、中断指示を受け付ける入力手段を有し、
当該データ分析方法は、
前記各第２データ処理装置は、前記入力手段が中断指示を受け付けるまで、前記第１データ処理装置から、前記分析問題の部分問題を割り当てられるごとに、当該部分問題を処理して、当該処理の結果を保存する処理と、
前記入力手段が中断指示を受け付けた第２データ処理装置が、前記保存している処理結果を前記第１データ処理装置へ送信する処理と、
を有することを特徴とするデータ分析方法。
【請求項４】
請求項１、2及び３のうちのいずれか１項に記載のデータ分析方法であって、
前記分析問題は、分析対象データからデータの特徴を記述した、ＩＦ〜ＴＨＥＮ…形式の特徴ルールを求めるものであり、
当該データ分析方法は、
前記第１データ処理装置は、前記複数の第２データ処理装置から、それぞれ、当該第２データ処理装置に割り当てた部分問題の処理結果として複数個の特徴ルールおよび該特徴ルールの評価値を受け付け、当該受け取った全特徴ルールのなかから、前記評価値が上位の特徴ルールを選択し、当該選択した特徴ルールを前記分析問題の分析結果として出力する、
ことを特徴とするデータ分析方法。
【請求項５】
請求項１、２、３及び４のうちのいずれか１項に記載のデータ分析方法であって、
前記第１データ処理装置は、前記複数の部分問題の処理に必要な計算量が不均等になるように、前記分析問題を前記複数の部分問題に分割することを特徴とするデータ分析方法。
【請求項６】
請求項５記載のデータ分析方法であって、
前記第１データ処理装置は、前記複数の部分問題を、処理に必要な計算量が大きい順に前記複数の第２データ処理装置に割り当てることを特徴とするデータ分析方法。
【請求項７】
請求項１記載のデータ分析方法であって、
前記第２データ処理装置への、前記部分問題の割り当てを開始した後、前記第１データ処理装置が、未割り当ての１以上の部分問題を、当該未割り当ての部分問題よりも多い数または少ない数の部分問題に再分割する処理を含むことを特徴とするデータ分析方法。
【請求項８】
請求項１〜７のいずれか１項に記載のデータ分析方法において、
前記第１データ処理装置は入出力装置を有し、
当該データ分析方法は、
前記入力手段が、前記複数の第２データ処理装置の数の推定最大値の入力を受け付ける処理と、
前記第１データ処理装置が、前記複数の部分問題の数をカウントし、当該数が、前記入力手段が受け付けた推定最大値よりも小さければ、当該複数の部分問題をさらに分割する分割処理と、
前記複数の部分問題の数が前記推定最大値よりも大きくなるまで、前記第１データ処理装置が前記分割処理を繰り返す処理と、
を有することを特徴とするデータ分析方法。
【請求項９】
コンピュータに請求項１〜８のいずれか１項に記載のデータ分析方法にしたがった処理を実行させるためのプログラム。
【請求項１０】
請求項９記載のプログラムを記録した、コンピュータ読み取り可能な記憶媒体。
【請求項１１】
通信路を介して複数のデータ処理装置に接続され、当該複数のデータ処理装置に分析問題の部分問題を実行させる情報処理装置において、
前記分析問題を、前記複数のデータ処理装置の数よりも多い複数の部分問題に分割し、前記複数のデータ処理装置のそれぞれに当該部分問題を１ずつ割り当てる制御手段と、
前記各データ処理装置から、当該データ処理装置に割り当てられた部分問題の処理結果を、前記通信路を介して受け付ける通信手段と、
を有し、
前記制御手段は、
前記複数の部分問題のすべてが割り当て済みとなるまで、前記複数のデータ処理装置のいずれかのデータ処理装置が、当該データ処理装置に割り当てられた部分問題の処理を終了させるごとに、前記複数の部分問題のうち、未割り当ての部分問題を当該データ処理装置に割り当て、当該データ処理装置に、当該割り当てた部分問題を送信すべく前記通信手段から出力させることを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析方法に係り、特に、複数のデータ処理装置を用いて並列に分析を行うデータ分析方法に関する。
【背景技術】
【０００２】
大量のデータから知識を発見する技術はデータマイニングと呼ばれている。発見される知識の具体例としては、特徴ルール(Characteristic  Rule)が知られている。特徴ルールとその発見法に関しては、特許文献１に記載されている。
【０００３】
特徴ルールは、「ＩＦ  A  ＴＨＥＮ  B」の形式で書き表すことができる。Ａ(条件部と呼ばれる)は、１個以上の条件の組み合わせであり、Ｂ(結論部と呼ばれる)は、単一の条件である。ここで、「条件」は、データの属性とその値の組であり、例えば「年齢＝２０代」のように記述される。特徴ルールには、一般性(ある特徴ルールがどのくらい多くのデータに適用できるかを示す指標)と精度(ある特徴ルールの条件部がどのくらい正確に結論部をあらわしているかを示す指標)とのトレードオフを考えて計算した評価尺度が定義される。この評価尺度は、「ＩＦ  A  ＴＨＥＮ  B」という特徴ルールにおいて、Ｐ(Ａ)とＰ(Ｂ|Ａ)との関数として算出される。ここで、Ｐ(Ａ)及びＰ(Ｂ|Ａ)は、それぞれ、全データのなかで条件Ａを満たすデータの割合、Ｐ(Ｂ|Ａ)は、条件Ａを満たすデータのなかで、さらに条件Bも満たすデータの割合である。特徴ルール生成のアルゴリズムによれば、この評価尺度を用いてルールが評価され、その値の高い順にソートされたランキングの上位が結果として出力される。
【０００４】
また、データマイニングのアルゴリズムは、膨大な量の計算を必要とすることがある。このため、分散環境においてアルゴリズムを実行するための方法が考案されている。
【０００５】
特徴ルールを複数の分析装置を用いて発見する技術については、特許文献２に記載されている。この技術においては、与えられた問題について、考えうる全ての特徴ルールの評価尺度を算出するのに必要な値を計数するカウンタが、複数のデータ分析装置で分割して保持されている。そして、一台のデータ格納装置が全分析装置に対して同時に１レコードづつデータを送信し、全分析装置が、Ｐ(Ａ)、Ｐ(Ｂ|Ａ)の値を算出するために、受信した１レコードのデータについて条件を満たすカウンタをカウントアップする。全分析装置がこの処理を終えると、データ格納装置が次のデータを分析装置に送信する。このような処理が繰り返されることによって全レコードについてデータが処理され、その後、全ての特徴ルールの評価値が算出されて、評価尺度が上位の特徴ルールが結果として出力される。
【０００６】
また、データ分析問題を複数の分析装置を用いて解く技術について、非特許文献１に記載されている。この文献に記載されているSETI@homeによれば、電波望遠鏡から得られる信号データが、固定長のWork  Unit(WU)に分割されて、多数のコンピュータ上で実行されるクライアントプログラムにインターネット経由で分配される。クライアントプログラムは、計算結果をサーバに返し、次のWUを得る。クライアント間ではお互いに一切の関わりを持たない。
【０００７】
【特許文献１】特開平８−７７０１０号公報
【０００８】
【特許文献２】特開２００１−１６７０９８号公報
【非特許文献１】「SETI@home:  An  Experiment  in  Public-Resource  Computing」Communications  of  the  ACM誌、第45巻第11号  pp.56〜61、2002年11月
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところが、上記従来の技術には以下のような課題がある。
【００１０】
特許文献１記載のアルゴリズムは、単一の処理装置を用いてルールを発見することを前提にしている。このため、項目数が増えて探索するルールの数が増加した場合、１台の装置では十分な計算能力が得られず、アルゴリズムが停止するまでに非常に長い時間がかかる。特に、条件部に許される条件の数を増やして特徴ルール発見の探索を行った場合、探索すべきルールの数が爆発的に増加する。このため、探索にかかる時間が膨大になることがある。
【００１１】
また、特許文献２記載の技術においては、全処理装置が、分析対象データ１レコードの処理を終えるまで次のレコードの処理に移らない。このため、分析を行うシステム全体の処理速度が、最も処理の遅い分析装置の処理速度以上にはならない。
【００１２】
また、非特許文献１記載の技術においては、分析すべき問題全体を、クライアントとなるコンピュータの数以上に分割する手段が提供されていない。このため、分析に参加するクライアント数よりも少ない数のジョブに分割するようなケースについては、一台のマシンに少なくとも一つの問題を割り当てることができず、計算機リソースの利用に無駄が生じることがある。
【００１３】
そこで、本発明は、複数のデータ処理装置で実行されるデータ分析処理において、全体の処理効率を向上させることを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて、分析問題のデータ分析を行うデータ分析方法において、
前記第１データ処理装置が、前記分析問題を、前記第２データ処理装置の数よりも多い複数の部分問題に分割し、前記複数の第２データ処理装置のそれぞれに当該部分問題を１ずつ割り当てる処理と、
前記複数の部分問題のすべてがいずれかの第２データ処理装置に割り当て済みとなるまで、前記第１データ処理装置が、前記複数の第２データ処理装置のいずれかが、当該第２データ処理装置に割り当てられた部分問題の処理を終了させるごとに、前記複数の部分問題のうち、未割り当ての部分問題を当該第２データ処理装置に割り当てる処理と、
前記第１データ処理装置が、前記各第２データ処理装置から、当該第２データ処理装置に割り当てられた部分問題の処理結果を受け付ける処理と、
を有することを特徴とするデータ分析方法。
【００１５】
また、本発明は、
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて、分析問題のデータ分析を行うデータ分析方法において、
前記第１データ処理装置からの、前記分析問題の部分問題の割り当てが停止するまで、前記各第２データ処理装置が、前記第１データ処理装置から前記分析問題の部分問題が割り当てられるごとに、当該部分問題を処理して、当該処理の結果を保存する処理と、
前記分析問題の部分問題の割り当てが停止した第２データ処理装置が、前記保存している処理結果を前記第１データ処理装置へ送信する処理と、
を有することを特徴とするデータ分析方法を提供する。
【００１６】
さらに、本発明は、
通信路を介して接続された第１データ処理装置と複数の第２データ処理装置を用いて分析問題の分析を行うデータ分析方法において、
前記各第２データ処理装置は、中断指示を受け付ける入力手段を有し、
当該データ分析方法は、
前記各第２データ処理装置は、前記入力手段が中断指示を受け付けるまで、前記第１データ処理装置から、前記分析問題の部分問題を割り当てられるごとに、当該部分問題を処理して、当該処理の結果を保存する処理と、
前記入力手段が中断指示を受け付けた第２データ処理装置が、前記保存している処理結果を前記第１データ処理装置へ送信する処理と、
を有することを特徴とするデータ分析方法を提供する。
【発明の効果】
【００１７】
本発明によれば、分析問題を、分析に参加するデータ処理装置の数以上のジョブに分割し、各データ処理装置が処理するジョブを送信し、一つのジョブを処理し終えたデータ処理装置に、他のデータ処理装置のジョブの終了を待たずに次のジョブを与えることにより、各データ処理装置の処理能力の差による待ち時間を抑え、情報処理システムの計算機リソースを効率的に利用することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明に係る第１の実施形態について説明する。
【００１９】
図１に、本発明の第１の実施形態に係るデータ分析システムの構成を示す。
【００２０】
本データ分析システムにおいては、第１データ処理装置(マスタ)０１０１、データ記憶装置０１０８及び１以上の第２データ処理装置(スレーブ)０１０９が、バス型の通信路０１１０を介して接続されている。ここで、マスタ０１０１は、分析を管理する管理装置、スレーブは、実際に分析を行う分析装置０１０９である。
【００２１】
マスタ０１０１は、処理装置０１０２、入出力装置０１０５、記憶装置０１０７、これら各装置を互いに接続する通信路０１１１、等を備える。処理装置０１０２は、処理装置０１０２が実行する処理に必要なデータを一時的に格納するメモリ０１０３を備え、メモリ０１０３には、処理装置０１０２が実行する処理が記述されたプログラム０１０４が記憶装置０１０７からロードされる。入出力装置０１０５は、キーボード、ディスプレイ等の入力装置、出力装置を含む入出力機器と、装置の外部との通信を管理する通信装置０１０６とを有する。マスタ０１０１は、この通信装置０１０６を介して通信路０１１０と接続されている。記憶装置０１０７は、大量のデータを記憶する容量を持つ、例えばハードディスク装置のような機器である。本実施の形態において、分析実行装置０１０９とデータ記憶装置０１０８も、同様の処理装置、記憶装置、入出力装置等を備えている。なお、記憶装置０１０７に格納されたプログラムは、ＣＤ―ＲＯＭ等の記憶媒体からインストールされたものであってもよいし、通信回線０１１０を介してインストールされたものであってもよい。
【００２２】
本実施形態では、知識の発見に特徴ルール生成のアルゴリズムを用いる。以下に、特徴ルール生成について詳細を説明する。
【００２３】
まず、分析対象データと、分析結果として出力される特徴ルールとについて説明する。
【００２４】
本実施形態で用いられる分析対象データの例を図２に示す。
【００２５】
分析対象データは、複数の属性項目(以下、簡単に項目と書く場合がある)からなるレコードの集合である。全てのレコードは同じ属性項目を持っている。各属性項目には、それぞれのレコードの、ある属性をあらわす値が格納されている。レコード及び属性項目が具体的に何を表すかは分析対象データに依存する。例えば、ある商店の購買履歴のデータを分析対象とする場合、１つのレコードは、１人の顧客に対応し、各属性項目は、その顧客の顧客ＩＤ、性別、年齢、購買頻度、購入総額等の属性に対応する。
【００２６】
特徴ルール生成では、前処理として、それぞれの属性項目の属性値を少数のカテゴリに変換する場合がある。この処理をカテゴリ化と呼ぶ。例えば、年齢という属性項目は通常１０〜１００程度の属性値を取り得るが、これを、「２５歳以下」、「２６歳から３５歳」、「３６歳以上」等の複数のカテゴリに変換する。この場合、年齢という属性項目を３つのカテゴリに変換したことになる。性別のように、元々「男」「女」の２値の属性値しか取らないものは、属性値をそのままカテゴリとして用いることもある。具体的には、性別は、２つのカテゴリ「男」「女」を持つ属性項目である。図２に示した分析対象データの属性項目は、このようなカテゴリ化の処理が施されたものである。
【００２７】
特徴ルールは、例えば、次のように書き表すことができる。
【００２８】
「ＩＦ  年齢＝２６〜３５  ＡND  購買頻度＝高  ＴＨＥＮ  購入総額＝高」。
【００２９】
すなわち、特徴ルールは、属性項目とそのカテゴリとを組み合わせた節をＩＦ以下の条件部とＴＨＥＮ以下の結論部とに有する、ＩＦ〜ＴＨＥＮルールとして表される。条件部に現れる属性を条件項目、結論部に現れる属性を結論項目、特徴ルールの条件部に現れる条件項目とそのカテゴリとの組を条件節と呼ぶ。
【００３０】
特徴ルールは、そのルールが対象データの特徴をどの程度よく表しているかを定量的に評価する指標となる評価値を有する。特徴ルールを一般的に「ＩＦ  Ａ  ＴＨＥＮ  B」と表す場合、評価値は、次式で定義される。
【００３１】
Ｐ(Ａ)^ａ  *  ｌｏｇ(Ｐ(Ｂ|Ａ)／Ｐ(Ｂ))
ここで、Ｐ(Ａ)、Ｐ(Ｂ)は、それぞれ、分析対象データ全体のうち、条件Ａ、条件Ｂを満足するレコードの割合、Ｐ(Ｂ|Ａ)は、条件Ａを満足するレコードのうち、条件Ａと条件Ｂの両方を満足するレコードの割合である。また、指数ａは、ルールの評価において一般性(あるルールがどのくらい多くのデータに適用できるかを示す指標)と精度(あるルールの条件部がどのくらい正確に結論部を表しているを示す指標)のいずれに重点をおくかを定める正の定数である。この評価値は、分析者によって指定されてもよいし、次式によって定められてもよい。
【００３２】
Ｐ(Ａ)^ａ  *  Ｐ(Ｂ|Ａ)  *  ｌｏｇ(Ｐ(Ｂ|Ａ)/Ｐ(Ｂ))
評価値にいずれの値を用いるにしても、ある特徴ルールに現れる条件部を満たすレコードの数、結論部を満たすレコードの数、条件部と結論部とを満たすレコードの数、および分析対象データ全体のレコード数を知ることによって、評価値を算出することができる。特徴ルール生成では、この評価値によって特徴ルールを評価し、評価値の高い特徴ルールから順にソートしてその上位を結果として出力する。ソートされた特徴ルールの例を図３に示す。
【００３３】
特徴ルール生成とは、上記で定義した評価値に基づき、評価値の大きな特徴ルールを発見するアルゴリズムである。この処理を行うにあたっては、処理を実行する前に分析者によって、発見すべき特徴ルール数の上限、結論項目となる属性項目とそのカテゴリ、条件部に含まれる属性項目の候補となる複数の属性項目(以下、条件項目という)、一つの特徴ルールに含まれる条件項目の数の上限(以下、最大条件節数という)が与えられているものとする。
【００３４】
いま、条件項目Ａ(１)〜Ａ(Ｍ)  (Ｍは条件項目の数)が与えられており、各条件項目はＢ(Ａ(m),１)〜Ｂ(Ａ(m),  N(Ａ(m))にカテゴリ化されているものとする(ここで、N(Ａ(m))は、条件項目Ａ(ｍ)のカテゴリ数、mは１≦m≦Mの整数である)。最大条件節数をC_maxとすると、特徴ルール「ＩＦ  X  ＴＨＥＮ  Y」は、以下のように述べることができる。
【００３５】
条件部Ｘは、条件節Ｃ(ｉ)の論理積「Ｃ(１)  and  …  and  Ｃ(ｋ)」と表すことができる。ここで、ｉは１≦ｉ≦ｋの整数、ｋは１≦ｋ≦C_maxの整数である。条件節Ｃ(ｉ)は、条件項目Ａ(ｍ)とＡ(ｍ)のカテゴリＢ(Ａ(ｍ),ｎ)との組み合わせであり、ルール中、「Ａ(ｍ)＝Ｂ(Ａ(ｍ),ｎ)」と表現される。
【００３６】
ここで、条件節が複数個含まれる特徴ルールは、以下のような性質を持つものとする。k個の条件節からなる条件部Ｃ(１)  and  …  and  Ｃ(ｋ)  (２≦ｋ≦Ｃ_max)において、任意の２個の条件節をＣ(ｉ),Ｃ(ｊ)  (Ｃ(ｉ)はＡ(m)＝Ｂ(Ａ(m),ｎ)、Ｃ(ｊ)はＡ(Ｐ)＝Ｂ(Ａ(Ｐ),ｑ)とする)としたとき、ｉ＜ｊならばm＜Ｐとなる。すなわち、一つのルールにおいて、同じ条件項目は現れず、条件節は条件項目の添え字で昇順に並んでいるものとする。
【００３７】
上記の説明より考え得る特徴ルールは数多く存在するが、それらの関係は図４及び図５に示すような木構造で表わすことができる。特徴ルール生成においては、この木(以下、探索木と呼ぶ)を走査(探索)することによってルールを発見する。
【００３８】
探索木におけるルール間の順序関係を以下の通り定める。
【００３９】
条件項目の順序関係と、各条件項目のカテゴリ間の順序関係とは、予め定められていることとする。例えば、条件項目に適当なインデックス番号を与え、それぞれの条件項目において、含まれるカテゴリにもインデックス番号を与えると、インデックス番号の大小によって順序関係を定めることができる。条件節、カテゴリの順序関係は、それぞれインデックス番号が小さい方の順序が先になる。
【００４０】
条件項目の順序関係とカテゴリの順序関係とに基づき、条件節と条件部との順序関係を定める。条件節の順序関係は、まず条件項目の順序関係によって決定され、条件項目が同じ場合には、カテゴリの順序関係によって決定される。条件部の順序関係は、条件部に含まれる条件節を順序関係の早い順に整列し、これらの順序関係を先頭の条件節から比較することによって定める。
【００４１】
探索木の具体例を図４に示す。この探索木において、ルートノード０４０１を除く全てのノードが一つの特徴ルールに対応する。ルートノード０４０１からあるノードに至るまでの枝の数を深さと呼び、同一の深さにあるノードの集合をレイヤと呼ぶことにすると、破線で囲まれた深さ１のノードの集合０４０４が一つのレイヤを形成している。
【００４２】
レイヤ０４０４には条件項目とそのカテゴリの考え得る全ての組み合わせがノードとして含まれており、それぞれのノードは、１つの条件節を持つルールに対応している。結論部を「購入総額＝高」として特徴ルールを発見する場合を仮定すると、例えばノード０４０２は、「ＩＦ  性別＝男  ＴＨＥＮ  購入総額＝高」というルールに対応する。また、レイヤ０４０４の下位に位置する深さ２のレイヤ０４０５には、２つの条件節を持つ特徴ルールに対応するノードが含まれている。例えば、ノード０４０３は、「ＩＦ  性別＝男性  ＡND  購買頻度＝高  ＴＨＥＮ  購入総額＝高」というルールに対応する。つまり、ノードの深さはルールの条件節数に対応する。
【００４３】
ここで、枝で結ばれた二つのノードのうち、上位にあるノードを親ノード、下位にあるノードを子ノードと呼び、それぞれのノードに対応するルールを親ルール及び子ルールと呼ぶことにする。探索木においては、子ルールが条件部「Ｃ(１)  and  …  and  Ｃ(ｋ−１)  and  Ｃ(ｋ)」を有する場合、その親ルールの条件部は、子ルールの条件部から、最後に現れる条件節Ｃ(ｋ)を取り除いた「Ｃ(１)  and  …  and  Ｃ(ｋ−１)」という条件部を持つ。
【００４４】
探索木の別の例として、探索木の木全体の概要を描いたものを、図５に示す。図５は、５つの条件項目Ａ〜Ｅがそれぞれ５つのカテゴリに分割された、最大条件節数を３として探索を行う場合の探索木の概念図である。
【００４５】
本実施形態に係る特徴ルールの性質を考慮すると、特徴ルール生成における探索木は、N個(Ｎは条件項目数)の項目からＭ個以下(Ｍは最大条件節数)の項目を選ぶときの組み合わせを書き出し、さらに各条件項目がそれぞれカテゴリ化されていることを考慮して、条件項目とカテゴリ値との取り得る組み合わせを、重複なく書き出したものである、ということができる。
【００４６】
探索木において全てのノードを評価する手順として、幅優先探索、深さ優先探索などのアルゴリズムが考えられる。幅優先探索とは、探索木の深さ１のレイヤより、同じレイヤにあるノードをまず評価し、そのレイヤの全てのノードを評価し終えたら、次のレイヤに移るという探索方法である。深さ優先探索とは、ノードの親子関係に着目し、同じレイヤにあるノードより子ノードを優先してノードを巡回する探索方法である。
【００４７】
次に、本実施形態に係る探索木の分割処理について説明する。探索木を部分木に分割する方法の一例を、図６を用いて説明する。なお、図６に示す探索木は、図５と同様のものである
図６において、破線で囲まれたノード群０６０１は、深さ１のレイヤに含まれる全てのノードを表している。同じ条件項目を持つノードを一つのグループとして、ノード群０６０１に含まれるノードをより小さなノード群に分けると、ノード群０６０２〜０６０４となる。同様に深さ２のレイヤに含まれるノード群も、深さ１のレイヤで同じグループになったノードの子ノードが一つのグループとなるようにノード群に分割する。以下、深さ２以上のレイヤに含まれるノード群も同様に分割する。このようにして分割されたそれぞれのノード群を、探索木を探索する際のジョブと呼ぶことにする。
【００４８】
このような分割方法によれば、ジョブがそれぞれのレイヤを基準として独立して切り分けられるので、幅優先探索のアルゴリズムを適用して特徴ルール生成を行うことができる。
【００４９】
また、分割方法の別の例を、図７を用いて説明する。図７に示す木は、特徴ルール生成における探索木であり、図５と同様のものである。
【００５０】
１条件を持つ特徴ルールの集合であるレイヤ０７０１に着目する。このレイヤ０７０１において、同一の条件項目を条件部にもつルールに対応するノードと、それらのノードをルートノードとして持つ部分木の集合とを一つのジョブとみなして、探索木全体を分割する。すなわち、図７においては、部分木０７０２〜０７０４がそれぞれ一つのジョブを表す。このような分割方法によれば、それぞれの部分木に深さ優先探索のアルゴリズムを適用して特徴ルール生成を行うことができる。
【００５１】
本実施形態においては、図６に示した探索木の分割方法を採用し、この分割方法により分割されたジョブを複数のスレーブで処理することによって特徴ルールの生成を行うことを考える。
【００５２】
各ジョブの探索アルゴリズムには幅優先探索を用いる。幅優先探索で特徴ルール生成を行う場合、深さ１のレイヤから順にノードを評価する。各レイヤにおいて特徴ルールの探索を行う際には、その前のレイヤ(深さが１少ないレイヤ)までのルール生成結果を参照し、冗長なルールを排除しつつ特徴ルールの探索を行う必要がある。ここで、冗長ルールとは以下のようなルールのことである。すなわち、ルールＲ_ａ,Ｒ_ｂを含むルールの集合Ｒにおいて、条件部Ｒ_ａが条件部Ｒ_ｂに含まれる条件節のいくつかからなり、かつ、Ｒ_aの評価値がＲ_bと同じかまたは大きいとき、ルール集合Rのなかにおいて、Ｒ_ｂは冗長ルールである。
【００５３】
つまり、幅優先探索では、レイヤｎ(ただし、１≦ｎ≦Ｃ_max-１)のルール探索が完了するまではレイヤn+１の探索に進めないことになる。このため、本実施形態に係るルール生成の手順においては、待ち合わせの処理を行い、マスタがレイヤｎのジョブの分析結果全てをスレーブから受け取るまで、レイヤｎ+１に含まれるジョブの処理を開始しないようになっている。
【００５４】
図８〜図１３を用いて、本実施形態に係る特徴ルール生成の詳細を説明する。
【００５５】
図８は、マスタが分析実行装置(スレーブ)を管理するための処理の詳細なフローチャートである。マスタがスレーブを管理する処理は、ルール生成中と、ルール生成が行われていないときとでは異なる。図８に示したのは、特徴ルール生成の分析が行われていない場合の処理のフローチャートである。
【００５６】
スレーブ管理テーブルの一例を図９に示す。
【００５７】
このスレーブ管理テーブルは、マスタと通信して分析を行うスレーブの情報を管理するためのもので、メモリ０１０３に保持される。このスレーブ管理テーブルには、スレーブごとに、少なくとも、スレーブを一意に識別するためのＩＤ０９０１、スレーブと通信路を用いて通信する際に必要な情報０９０２と、が格納されている。この情報０９０２は、例えばＴＣＰ／ＩＰを用いて通信を行う場合には、スレーブのＩＰアドレス及びポート番号である。
【００５８】
図８において、マスタ０１０１は、スレーブ０１０９を管理する処理Ｓ０８０１〜Ｓ０８０４を実行するのと並行して、パラメータ入力受付処理を実行する。処理Ｓ０８０１〜Ｓ０８０４とパラメータ入力受付処理は、マルチスレッドなど、処理装置内で複数のタスクを同時に実行する機構を用いて並行に処理される。
【００５９】
パラメータ入力受付処理では、分析者が、入出力装置０１０５により、データ記憶装置０１０８に格納されている分析対象データのファイル名を指定し、これをメモリ０１０３に読み込む。ここで、分析対象データは、特徴ルール生成を用いてルール生成を行う対象となるデータであり、例えば、表形式のファイル、データベース内のデータ等の形式で、データ記憶装置０１０８に格納されている。なお、ここでは、データ記憶装置０１０８に分析対象データを格納しているが、マスタ内の記憶装置０１０７に分析対象データを格納し、記憶装置０１０７から分析対象データがメモリ０１０３に読み込まれるようにしてもよい。
【００６０】
分析対象データをメモリ０１０３に格納するに当たって、各属性項目には、それぞれ、項目を一意に特定するためのインデックス番号が割り当てられる。例えば、分析対象データのなかで属性項目が現れる順に属性項目に通し番号を振り、この値をインデックス番号として用いることができる。
【００６１】
分析者は、さらに、分析対象データのカテゴリ化に関する情報、ルール生成に用いる条件項目と結論部、ルール生成パラメータ、分析に参加するスレーブ数の想定最大値を、入出力装置０１０５により入力し、これらをメモリ０１０３に格納する。
【００６２】
分析対象データのカテゴリ化に関する情報は、分析対象データに含まれる各属性項目をカテゴリ化するための情報である。この情報には、それぞれの属性項目のカテゴリ数、属性項目のとる値をカテゴリに変換するための境界値、それぞれのカテゴリに含まれるデータのレコード数が含まれている。それぞれの属性項目において、項目の各カテゴリには、インデックス番号が付与される。
【００６３】
条件項目と結論部とに関する情報は、ルール生成で用いる条件項目と結論項目、および結論部として用いる結論部のカテゴリの情報が含まれる。これらは、マスタ０１０１の内部において、属性項目、カテゴリに付与したインデックス番号で管理される。
【００６４】
ルール生成に用いる条件項目及び結論部は、条件部に現れる属性項目の候補となる項目の組み合わせと、結論部となる属性項目とカテゴリとの組である。
【００６５】
ルール生成パラメータには、発見する特徴ルールの個数Ｒ_max、最大条件節数Ｃ_maxが含まれる。
【００６６】
スレーブ数の想定最大値には、分析に用いるスレーブの数より大きい値が指定される。
【００６７】
パラメータ入力受付処理は、これらの情報の入力後に終了する。
【００６８】
Ｓ０８０１において、マスタ０１０１は、スレーブ０１０９からの信号を受信していないかどうかをチェックする。その結果、スレーブ追加の信号をスレーブから受信したと判断した場合には、マスタ０１０１は、スレーブ追加処理Ｓ０８０２を実行する。また、スレーブ削除の信号をスレーブから受信したと判断した場合には、マスタ０１０１は、スレーブ削除処理Ｓ０８０３を実行する。一方、いずれの信号も受信していないと判断した場合には、マスタ０１０１は、分岐処理Ｓ０８０４を実行する。
【００６９】
スレーブ追加処理Ｓ０８０２において、マスタ０１０１は、Ｓ０８０１で受け取った信号の発信元スレーブに、このスレーブを識別するためのＩＤ番号を割り当て、スレーブのＩＰアドレスとスレーブが通信に用いるポート番号を取得し、これらの値を、スレーブ管理テーブルに格納する。ＩＤ番号は、例えば、信号の発信元スレーブに、マスタにおける信号受信順に通し番号を付与する等によってスレーブに割り当てられる。その後、マスタ０１０１は、処理をＳ０８０１に戻す。
【００７０】
スレーブ削除処理０８０２において、マスタ０１０１は、Ｓ８０１で受け取った中断要求の信号の発信元スレーブを管理テーブルから削除する。
【００７１】
一方、Ｓ０８０４では、マスタ０１０１は、入出力装置０１０５からの入力内容をチェックし、ルール生成実行開始の信号の入力があるか否かを調べる。その結果、ルール生成実行開始の信号の入力があれば、マスタ０１０１は、分析実行開始処理Ｓ０８０５を実行し、そうでなければ、マスタ０１０１は、Ｓ０８０１に処理を戻す。
【００７２】
分析実行開始処理Ｓ０８０５では、マスタ０１０１は、ルール生成を行うための準備((１)分析対象データをスレーブに送信する準備、(２)分析結果のルールを格納する準備、(３)探索木のジョブへの分割、(４)分析の初期条件の設定)を行う。
(１)分析対象データをスレーブに送信する準備
マスタ０１０１は、メモリ０１０３内に格納されている分析対象データの、条件項目、結論部の項目に対応する各属性項目のデータをカテゴリ化する。
(２)分析結果のルールを格納する準備
マスタ０１０１は、メモリ０１０３内に分析結果の特徴ルールを格納するのに十分な領域を確保する。この領域には、分析の途中結果として、分析中のある時点でスレーブから受け取った上位Ｒ_max個のルールが格納される。
(３)探索木のジョブへの分割
マスタ０１０１は、図６で示した方法にしたがって、以下のように探索木をジョブに分割する。
【００７３】
マスタ０１０１は、分析対象データの条件項目に、条件項目メモリ０１０３に格納された順に条件項目Ａ(１)、条件項目Ａ(２)等のインデックス番号を与えて、順序関係を定める。それぞれの条件項目のカテゴリについても、同様にインデックス番号を与え、順序関係を定める。これにより、条件項目とカテゴリとに関して順序関係が定められ、条件部の順序関係を定めることができる。
【００７４】
分割した各ジョブに関する情報は、マスタ０１０１内のジョブ管理テーブルで管理する。ジョブ管理テーブルの一例を図１０に示す。図１０に示すように、ジョブ管理テーブルには、ジョブごとに、少なくとも、ジョブを一意に識別するためのジョブＩＤ１００１、レイヤ番号１００２、ジョブの分析開始ノード１００３、分析終了ノード１００４、そのジョブの分析を担当するスレーブのＩＤを格納する担当スレーブ１００５、分析の状態(例えば、分析中、分析完了等)に関する情報を保持するジョブ状態フラグ１００６が含まれている。このジョブ管理テーブルは、メモリ０１０３に格納されている。
【００７５】
マスタ０１０１は、上記の順序関係に基づいて、ジョブの分析開始ノードと分析終了ノードを特定することにより、各ジョブに含まれるノードを一意に決定することができる。例えば、ジョブ０６０２の分析開始ノードとして条件部「Ａ＝ａ(１)」、ジョブ０６０２の分析終了ノードとして「Ａ＝ａ(５)」を指定することにより、ジョブ０６０２で分析するノードを一意に決定することができる。ノードは、マスタ０１０１、スレーブ０１０９においては、条件項目とカテゴリのインデックス番号の組として表現される。例えば、条件項目Ａのインデックス番号を１、カテゴリａ(１)のインデックス番号を１、カテゴリａ(５)のインデックス番号を５とすれば、ジョブ０６０１の開始ノード及び終了ノードは、それぞれ、(１,１)、(１,５)と表すことができる。条件節が複数ある場合、一つのノードは、複数の条件項目とカテゴリのインデックス番号との組で表現される。なお、以下において、ノードが計算機内で操作されている場合、実際には、このようなインデックス番号が計算機の内部で操作されていることとする。
【００７６】
これを踏まえて、探索木のジョブへの分割は、以下のように実現される。
【００７７】
マスタ０１０１は、レイヤの深さを表す変数Iの初期値＝１、条件項目の番号を表す変数mの初期値＝１として以下の処理を繰り返し実行する。
【００７８】
あるジョブの分析開始ノードに対応する条件節Ｘ_ｓをＣ_ｓ(１)  and  …  and  Ｃ_ｓ(Ｉ)、分析終了ノードに対応する条件節Ｘ_ｅをＣ_ｅ(１)  and  …  and  Ｃ_ｅ(Ｉ)と書くことにする。ここで、Ｃ_ｓ(１)は(ｍ,１)、Ｃ_s(ｉ)(２≦ｉ≦Ｉ)は(ｍ+ｉ-１,１)、C_e(１)は(m,N(Ａ(ｍ)))、Ｃ_ｅ(ｉ)(２≦ｉ≦Ｉ)は(Ｍ-Ｉ+ｉ,Ｎ(Ａ(Ｍ-Ｉ+ｉ)))、Mは条件項目の数である。この方法によって、マスタ０１０１は、分析開始ノードと分析終了ノードの条件項目とカテゴリの組を決定し、この分析開始ノード１００３、分析終了ノード１００４、ジョブを一意に識別するジョブＩＤ１００１、そのジョブが含まれるレイヤ１００２をジョブ管理テーブルに格納する。ここで、ジョブＩＤは、例えばジョブの登録順に通し番号付与することによってジョブに与えられる。また、このジョブの担当スレーブ１００５を「未割り当て」とする。
【００７９】
マスタ０１０１は、この処理を、変数mを１づつ増加させながら、mがＭ-Ｉ+１に等しくなるまで繰り返す。ｍがＭ-Ｉ+１に等しくなったら、マスタ０１０１は、mを初期値「１」に戻してIを１だけ増加させ、Iが最大条件節数C_maxに等しくなるまで同様の処理を繰り返す。
【００８０】
分析に参加するスレーブの数の想定最大値よりも各レイヤに含まれるジョブの数が少ない場合には、マスタ０１０１は、一番多くのルールを含むジョブを２分割する処理を繰り返すことによって、レイヤに含まれるジョブの数をスレーブの数の想定最大値よりも大きくする。この処理は全レイヤについて同様に行う。ここで、ジョブを２分割する処理は、以下のようにして実現する。
【００８１】
ジョブＪをジョブＪ(１)及ジョブＪ(２)に分割する場合、マスタ０１０１は、各条件項目のカテゴリ分割数から、ジョブに含まれるルールの数を算出し、これを２で割る。なお、カテゴリ分割数の情報はメモリ０１０３に格納されている。その後、マスタ０１０１は、ルール数を２で割ることによって得た商の端数を切り捨て、得られた整数をＮとする。マスタ０１０１は、Ｊの開始ノードを、Ｊ(１)の開始ノードとし、Ｊ(１)の開始ノードから、ノードの順序関係に従ってノードを数え、N番目のノードをＪ(１)の終了ノードとする。
【００８２】
また、マスタ０１０１は、Ｊ(１)の終了ノードの次ノードをＪ(２)の開始ノードとし、Ｊの終了ノードをＪ(２)の終了ノードとして、Ｊ(１)及びＪ(２)の情報をジョブ管理テーブルへ格納する。これにより、ジョブ管理テーブル内のジョブＪの情報がＪ(１)の情報で上書きされ、Ｊ(２)の情報が管理テーブルに追加される。
【００８３】
以上により、１つのレイヤに含まれるノードの数がスレーブの想定最大値を下回らない限り、１つのレイヤのルール探索を、スレーブより多くのジョブに分割することができる。
(４)分析の初期条件を設定する処理
マスタ０１０１は、割り当て可能レイヤ番号を格納するためのパラメータを用意し、レイヤ番号１を割り当て可能レイヤ番号に設定する。また、マスタ０１０１は、採用されるルールの最小評価値を格納するためのパラメータを用意し、そのパラメータを初期化する。パラメータの初期化に用いられる値はルールの評価方法によって異なるが、本実施形態に係る評価値を用いる場合には、パラメータに「０」を設定することによって初期化を行う。このパラメータは、スレーブによってルールを評価する際に用いられる。具体的には、ルールの評価値がこのパラメータ値を下回ることがわかった時点で、そのルールに関するそれ以降の評価処理を行わない、というように用いられる。これにより、処理の削減が図られる。なお、これらのパラメータを格納する領域はメモリ０１０３に確保する。
【００８４】
これらの準備処理(１)〜(４)が実行された後、分析実行開始処理Ｓ０８０５において、マスタ０１０１は、図１１に示すスレーブ管理処理と、図１２に示す分析処理とを開始する。これらの処理は、マスタ０１０１内において、図８における処理と並行に実行される。この処理は、マルチスレッドなど、処理装置内で複数のタスクを同時に実行する機構を用いて実現される。なお、図１１に示すスレーブ管理処理は、分析の実行中にスレーブを管理する処理である。
【００８５】
分析実行開始処理Ｓ０８０５が終了すると、分析実行通知処理Ｓ０８０６に進む。
【００８６】
分析実行通知処理Ｓ０８０６は、マスタ０１０１は、スレーブ管理テーブルに登録されている、全てのスレーブに対して、通信路０１１０を介して分析実行通知信号を送信する。分析実行通知処理の完了後、この手順における処理を終了する。
【００８７】
図１１に、分析実行開始処理Ｓ０８０５中に実行されるスレーブ管理処理の詳細なフローチャートを示す。
【００８８】
分岐処理Ｓ１１０１において、マスタ０１０１は、スレーブからのスレーブ管理に関する信号をチェックする。その結果、マスタ０１０１は、その信号がスレーブ追加信号である場合にはスレーブ追加処理１１０２、その信号がスレーブ削除信号である場合にはスレーブ削除処理１１０３を実行する。一方、スレーブ０１０９からそれらの信号を受信していない場合には、マスタ０１０１は、分岐処理Ｓ１１０４を実行する。
【００８９】
スレーブ追加処理Ｓ１１０２において、マスタ０１０１は、図８のスレーブ追加処理０８０２と同様の処理を実行した後、さらに分析実行通知処理Ｓ１１０５を実行する。分析実行通知処理Ｓ１１０５において、マスタ０１０１は、スレーブ追加処理Ｓ１１０２で追加されたスレーブに分析実行通知の信号を送信してから、Ｓ１１０１に処理を戻す。
【００９０】
スレーブ削除処理１１０３において、マスタ０１０１は、図８のスレーブ削除処理０８０３と同様の処理を行い、Ｓ１１０１に処理を戻す。
【００９１】
分岐処理Ｓ１１０４において、マスタ０１０１は、図１２の分析処理が終了しているかどうかをチェックし、終了していれば、図１１の手順における処理を終了し、終了していなければＳ１１０１に処理を戻す。
【００９２】
図１２に、分析実行開始処理Ｓ０８０５中に実行される分析処理の詳細なフローチャートを示す。
【００９３】
分岐処理Ｓ１２０１において、マスタ０１０１は、分析中のスレーブから受信した信号の内容をチェックし、その種類に応じて処理を分岐させる。本実施形態において、スレーブからの受信信号の種類は、データ・パラメータ要求信号、途中経過要求信号、ジョブ要求信号、ジョブ分析完了通知信号及び結果送信信号のいずれかである。
【００９４】
スレーブからの通信内容がデータ・パラメータ要求信号である場合、マスタ０１０１は、データ・パラメータ送信処理１２０２において、その信号の発信元スレーブに分析対象データ及び分析パラメータを送信してから、Ｓ１２０１に処理を戻す。ここで、分析対象データは、分析対象データのカテゴリ化により得られたデータのカテゴリ値のインデックスの列に変換されて送信される。また、この処理で送信される分析パラメータには、発見すべき特徴ルール数の上限R_max、結論項目となる属性項目のインデックス番号とそのカテゴリのインデックス番号、条件項目のインデックス番号、最大条件節数C_maxが含まれている。
【００９５】
スレーブからの通信内容が途中経過要求信号である場合、マスタ０１０１は、途中経過送信処理Ｓ１２０３を実行する。マスタ０１０１は、途中経過送信処理Ｓ１２０３において、メモリ０１０３に格納している分析結果のルール群をスレーブ０１０９に送信してから、Ｓ１２０１に処理を戻す。
【００９６】
スレーブ０１０９からの信号がジョブ要求信号である場合、マスタ０１０１は分岐処理Ｓ１２０４を実行する。分岐処理Ｓ１２０４において、マスタ０１０１は、割り当て可能なジョブがあるか否かチェックする。具体的には、マスタ０１０１は、ジョブ管理テーブルを参照し、割り当て可能レイヤ番号と等しいレイヤ番号１００２を持つジョブのうち、担当スレーブ１００５の項目が「未割り当て」のジョブが存在するかどうかをチェックする。その結果、そのようなジョブが存在すれば、マスタ０１０１は、割り当て可能なジョブがあると判定して、ジョブ割り当て処理Ｓ１２０５を実行する。一方、そのようなジョブが存在しなければ、マスタ０１０１は、割り当て可能なジョブなしと判定して、現在のレイヤにおけるジョブ割り当て終了処理Ｓ１２０６を実行する。
【００９７】
ジョブ割り当て処理Ｓ１２０５において、マスタ０１０１は、担当スレーブの項目が「未割り当て」ジョブのうちの一つをジョブ要求信号の発信元スレーブに割り当て、ジョブ管理テーブルにおいて、該当するジョブのジョブ状態フラグ１００６を「分析中」の状態とし、このスレーブのＩＤを担当スレーブ１００５の項目に格納する。その後、Ｓ１２０１に処理を戻す。この割り当て処理においては、ジョブ管理テーブルに格納されている分析開始ノード１００３及び分析終了ノード１００４の値、マスタ０１０１に格納されている最小評価値の情報が、マスタ０１０１からスレーブ０１０９に送信される。
【００９８】
現在のレイヤにおけるジョブ割当て終了処理Ｓ１２０６において、マスタ０１０１は、現レイヤの分析結果の送信を要求する信号をスレーブ０１０９に送信してから、Ｓ１２０１に処理を戻す。
【００９９】
スレーブ０１０９からの信号がジョブ分析完了通知である場合、マスタ０１０１は、パラメータ更新処理Ｓ１２０７を行う。この信号には、そのスレーブが保持している特徴ルールの最小評価値が含まれている。パラメータ更新処理Ｓ１２０７において、マスタ０１０１は、ジョブ管理テーブルにおける、このスレーブが分析中であったジョブのジョブ状態フラグ１００６を「分析完了」に更新する。また、マスタ０１０１は、スレーブから受け取った最小評価値に関するパラメータ値と、マスタで保存中の最小評価値の値とを比較し、両者のうちの大きな方の値で、マスタで保存中の最小評価値を更新する。その後、Ｓ１２０１に処理を戻す。
【０１００】
スレーブからの信号が結果送信である場合、マスタ０１０１は、途中結果マージ処理Ｓ１２０８を実行する。途中結果マージ処理Ｓ１２０８において、マスタ０１０１は、スレーブ０１０９から、そのスレーブが行った分析の結果を受信し、この分析結果を、メモリ０１０３に格納されている分析結果とマージする。具体的には、マスタ０１０１は、メモリに保存中の特徴ルールとスレーブ０１０９からの受信特徴ルールとを参照し、それらのルールのなかから、評価値が上位のルールR_max個を選択し、マスタが格納している結果ルールを更新する。
【０１０１】
その後、マスタ０１０１は、ジョブ管理テーブルの担当スレーブ１００５の項目を参照し、この項目に格納されているスレーブＩＤが、結果を送信してきたスレーブのＩＤと同一のジョブについて、ジョブ管理テーブルのジョブ状態フラグ１００５を「結果受理」とする。
【０１０２】
その後、分岐処理Ｓ１２０９において、マスタ０１０１は、ジョブ管理テーブルを参照して、現在分析中のレイヤ番号１００２を持つジョブについて、全てのジョブのジョブ状態フラグ１００６が結果受理を示す値になっているかどうかをチェックする。その結果、結果受理であれば、マスタ０１０１は、分岐処理Ｓ１２１０を実行し、そうでなければ、マスタ０１０１は、Ｓ１２０１に処理を戻す。
【０１０３】
Ｓ１２１０において、マスタ０１０１は、現在分析中のレイヤ番号と最大条件節数の値を参照し、現在分析中のレイヤ番号が最大条件節数よりも小さければ、分析続行通知処理Ｓ１２１１を実行し、同じであれば、分析終了通知処理Ｓ１２１２を実行する。
【０１０４】
分析続行通知処理Ｓ１２１１において、マスタ０１０１は、割り当て可能レイヤ番号を１増加させ、スレーブ管理テーブルに登録されている全スレーブに分析続行通知を送信してから、Ｓ１２０１に処理を戻す。
【０１０５】
一方、分析終了通知処理１２１２において、マスタ０１０１は、スレーブ管理テーブルに登録されている全スレーブに分析終了の信号を送信してから、Ｓ１２１３を実行する。結果出力処理Ｓ１２１３において、マスタ０１０１は、現在保持している特徴ルールの集合を、最終的な結果として入出力装置に出力する。これにより、ルール生成の処理を終了する。
【０１０６】
つぎに、図１３により、本実施形態に係るスレーブ処理の詳細を説明する。
【０１０７】
スレーブ０１０９は、分析実行登録処理Ｓ１３０１において、マスタ０１０１にスレーブ追加の信号を送信し、分析実行初期化処理Ｓ１３０２において、マスタ０１０１からの分析実行通知の信号を待つ。スレーブ０１０９は、分析実行通知の信号を受信すると、データ・パラメータ送信要求をマスタ０１０１に送信して、分析対象データ及びルール生成に用いるパラメータをマスタ０１０１から受信する。また、スレーブ０１０９は、分析結果のルール群を格納する領域、および、途中結果のルール群を格納する領域をメモリに確保し、これらの領域を空に初期化する。なお、これらの領域として、R_max個のルールを格納するために十分なメモリ領域が確保されることとする。
【０１０８】
その後、途中結果要求処理Ｓ１３０３において、スレーブ０１０９は、マスタ０１０１に途中結果要求の信号を送信することによって、マスタ０１０１が保持しているルール生成の結果である特徴ルールの集合を含む途中結果をマスタ０１０１から受信する。そして、スレーブ０１０９は、マスタ０１０１から受信した途中結果を、Ｓ１３０２で確保した、途中結果のルール群を格納するためのメモリに格納する。
【０１０９】
その後、スレーブ０１０９は、ジョブ要求処理Ｓ１３０４において、マスタ０１０１にジョブ要求の信号を送信し、分岐処理Ｓ１３０５において、Ｓ１３０４で送信したジョブ要求に対する応答信号を参照し、その応答信号が、新しいジョブの割り当て信号及び分析結果の送信要求信号のいずれであるかをチェックする。その結果、新しいジョブの割り当ての信号であれば、スレーブ０１０９は分析実行処理Ｓ１３０６を実行し、分析結果の送信を要求する信号であれば、スレーブ０１０９は途中結果送信処理Ｓ１３０７を実行する。
【０１１０】
分析実行処理１３０６において、スレーブ０１０９は、マスタ０１０１から受信した最小評価値をメモリに保持し、割り当てられたジョブの分析開始ノード及び分析終了ノードを参照し、以下のように、本実施形態に係るノードの順序関係にしたがってノードを評価する。
【０１１１】
スレーブ０１０９は、分析開始ノードをカレントノードに設定し、このカレントノードに対応するルール(以下、カレントルールと呼ぶ)の評価値を算出する。その後、スレーブ０１０９は、このルールの採用判定を行う。具体的には、スレーブ０１０９は、（１）カレントルールの評価値が、このスレーブにおけるルールの最小評価値よりも大きいこと、（２）Ｓ１３０３で受信した途中結果のルール群において、カレントルールが冗長ルールに当らないこと、の２つの条件がいずれも真であれば、このルールを採用する。
【０１１２】
カレントルールが採用になった場合、スレーブ０１０９は、このカレントルールを、Ｓ１３０２で確保した分析結果格納領域に格納されているルールと、評価値が小さいルールから順に比較し、比較対象のルールの評価値がカレントルールの評価値を下回ったときに比較対象ルールの上位にカレントルールを挿入する。これにより、分析結果格納領域に格納されているルールの数がR_max個を上回った場合には、スレーブ０１０９は、一番評価値の低いルールを削除し、その後、改めて分析結果格納領域に格納されている最下位のルールの評価値を参照し、最小評価値のパラメータをこの値で更新する。その後、スレーブ０１０９は、カレントノードが分析終了ノードと等しいか否かをチェックし、両者が等しければノードの評価を終了し、そうでなければ、現在のカレントノードの次ノードをカレントノードに設定してノードの評価及び採用判定を再度実行する。
【０１１３】
その後、ジョブ分析結果送信処理Ｓ１３０８において、スレーブ０１０９は、格納している分析結果の特徴ルールのうち、最も評価値が低いルールの評価値をマスタ０１０１に送信してから、Ｓ１３０４に処理を戻す。ただし、分析結果のルール群を保持する領域に格納されているルール数がR_max個に満たない場合には、スレーブ０１０９は、評価値として「０」をマスタ０１０１に送信して、Ｓ１３０４に処理を戻す。
【０１１４】
一方、途中結果送信処理Ｓ１３０７においては、スレーブ０１０９は、保持している分析結果の特徴ルールに関する情報をマスタ０１０１に送信する。ここでマスタ０１０１に送信する特徴ルールの情報は、分析結果の特徴ルールの、条件部に含まれる条件項目とカテゴリの組、およびそれぞれの特徴ルールの評価値を含んでいる。その後、分岐処理Ｓ１３０９において、スレーブ０１００は、分析の続行に関する信号をマスタ０１０１から受信するまで待機する。ここで、マスタ０１０１から分析続行通知を受信すれば、スレーブ０１０９はＳ１３０３に処理を戻し、マスタ０１０１から分析終了通知を受信すれば、スレーブ０１０９は分析終了処理Ｓ１３１０を実行する。
【０１１５】
分析終了処理Ｓ１３１０において、スレーブ０１０９は、分析で使用したメモリの開放等の、分析終了のために必要な処理を実行してから、処理を終了する。なお、スレーブ０１０９が、ここで処理を終了せずにＳ１３０２に処理を戻し、次のルール生成問題の開始を待機するようにしてもよい。
【０１１６】
本実施形態に係るスレーブ処理は、スレーブ０１０９が、入出力装置０１０５から分析中断の指示を受け付けるように変更することも可能である。分析中断の指示の有無は、例えば、Ｓ１３０４においてスレーブ０１０９がマスタ０１０１にジョブを要求する前にチェックされればよい。分析中断の指示があった場合には、スレーブ０１０９が、途中結果送信処理Ｓ１３０７及び分析終了処理Ｓ１３０９を行い、スレーブ削除の信号をマスタ０１０１に送信してから、処理を終了するようにすればよい。
【０１１７】
このように、本実施形態によれば、分析問題が分析装置の数以上のジョブに分割されて、一つのジョブを処理し終えた分析装置には、他の分析装置のジョブの終了を待たずに次のジョブが与えられる。このため、分析に参加する処理装置の処理能力の差による待ち時間が抑され、処理装置の計算機リソースを効率的に利用することができる。
【０１１８】
以下、本発明に係る第２の実施形態について説明する。
【０１１９】
本実施形態では、上述の第１の実施形態と同様の処理でスレーブの管理が行われる。その詳細は一部を除き、図８、図１１で説明したものと同様であるが、本実施形態では、分析実行開始処理Ｓ０８０５において、上述の第１の実施形態で説明した処理を行う代わりに、以下の処理が実行される。
【０１２０】
分析実行開始処理Ｓ０８０５では、ルール生成を行うための準備として、分析対象データをスレーブに送信する準備、分析結果のルールを格納する準備、探索木の部分木への分割、分析の初期条件の設定を行う。スレーブに送信する準備、分析結果のルールを格納する準備に関する処理は、第１の実施形態で示した処理と同様である。
【０１２１】
探索木の部分木への分割は、第１の実施形態と異なり、探索木全体を、図７に示すような部分木の集合に分割する。探索木の分割方法の詳細を説明するのに先立って、本実施形態において、マスタ０１０１内でジョブを管理するためのテーブルのデータ構造を図１４に示す。このジョブ管理テーブルには、部分問題ごとに、少なくとも、ジョブを一意に識別するジョブＩＤ(部分問題ＩＤ)１４０１、そのジョブの分析を担当するスレーブのＩＤを格納する担当スレーブ１４０３、それぞれのジョブが分析を担当する条件項目を格納する担当条件項目１４０２、分析の状態(例えば「分析中」や「分析完了」など)に関する情報を保持するジョブ状態フラグ１４０４が含まれている。
【０１２２】
探索木の分割方法の詳細は、以下の通りである。
【０１２３】
探索木の部分木への分割では、ジョブ管理テーブルの担当条件項目１４０２に、条件項目のインデックス番号が１から順に条件項目数まで格納し、担当スレーブ１４０３を「未割り当て」とする。本実施形態においては、深さ１のレイヤにおける条件項目を基準として、それらのノードをルートとする部分木を一つのジョブとして扱う。このため、その条件項目を特定する情報をジョブ管理テーブルに格納しておけば、ジョブに対応する部分木を一意に表すことができる。
【０１２４】
分析実行開始処理Ｓ０８０５では、また、マスタ０１０１は、図１１に示したスレーブ管理処理と、図１５に示した分析処理を開始する。マスタ０１０１は、分析実行開始処理Ｓ０８０５を終了すると、分析実行通知処理Ｓ０８０６を実行する。
【０１２５】
本実施形態に係るマスタ０１０１の処理の詳細を、図１５を用いて説明する。
【０１２６】
マスタ０１０１は、分岐処理Ｓ１５０１において、分析中のスレーブからの通信内容をチェックし、その内容に対応する処理に分岐する。ここで、スレーブ０１０９からの通信内容は、データ・パラメータ要求信号、ジョブ要求信号、ジョブ分析完了通知、結果送信のいずれかである。
【０１２７】
スレーブ０１０９からの通信内容がデータ・パラメータ要求信号である場合には、マスタ０１０１は、データ・パラメータ送信処理として、その信号の送信元スレーブに分析対象データ及び分析パラメータを送信し、分岐処理Ｓ１５０１に戻る。ここで、分析対象データのカテゴリ化により得られたデータのカテゴリ値のインデックスの列に変換されて送信される。この処理で送信するパラメータには、発見すべき特徴ルール数の上限R_max、結論項目となる属性項目のインデックス番号とそのカテゴリのインデックス番号、条件項目のインデックス番号、最大条件節数C_maxが含まれている。
【０１２８】
スレーブ０１０９からの信号がジョブ要求信号である場合には、マスタ０１０１は、分岐処理１５０３において、ジョブ管理テーブルを参照して、担当スレーブの項目１４０３が「未割り当て」となっているジョブがあるかどうかをチェックする。その結果、そのようなジョブがあれば、マスタ０１０１は、ジョブ割り当て処理Ｓ１５０４を実行し、そのようなジョブがなければ、マスタ０１０１は、ジョブ割り当て終了処理Ｓ１５０５を実行する。
【０１２９】
ジョブ割り当て処理Ｓ１５０４においては、マスタ０１０１は、担当スレーブの項目が「未割り当て」であるジョブの一つを、ジョブ要求信号の送信元スレーブに割り当てる。具体的には、マスタ０１０１は、担当条件項目番号と、マスタ０１０１が格納しているルールの最小評価値を含むデータをスレーブ０１０９に送信する。その後、マスタ０１０１は、ジョブ管理テーブルにおける、割り当てたジョブのジョブ状態フラグ１４０４を「分析中」とし、担当スレーブ１４０３の項目に、割り当てたスレーブのＩＤを格納してから、分岐処理Ｓ１５０１に戻る。
【０１３０】
ジョブ割り当て終了処理Ｓ１５０５においては、マスタ０１０１は、分析結果の送信を要求する信号をスレーブ０１０９に送信する。その後、マスタ０１０１は、分岐処理Ｓ１５０１に戻る。
【０１３１】
スレーブからの信号がジョブ分析完了通知の場合、マスタ０１０１は、パラメータ更新処理Ｓ１５０６において、スレーブ０１０９から、そのスレーブにおける生成ルールの最小評価値を含むパラメータを受け取り、その最小評価値を、マスタに格納されている最小評価値の値と比較する。この比較結果、値の大きかった方の評価値を新しい値として、マスタの最小評価値を更新する。そして、マスタ０１０１は、ジョブ管理テーブルの担当スレーブ１４０３とジョブ状態フラグ１４０４の項目を参照し、担当スレーブのＩＤが、信号を送ってきたスレーブと同一であり、ジョブ状態フラグ１４０４が「分析中」であるジョブのジョブ状態フラグ１４０４を「分析完了」とする。その後、分岐処理Ｓ１５０１に戻る。
【０１３２】
スレーブ０１０９からの信号が結果送信である場合、マスタ０１０１は、結果マージ処理Ｓ１５０７において、スレーブ０１０９から、そのスレーブの分析結果を受信する。マスタ０１０１は、この結果を、以下の処理によって、メモリ０１０３に格納している分析結果とマージする。すなわち、マスタは、メモリ０１０３に格納された特徴ルール及びスレーブから受信した特徴ルールの評価値を参照し、それらのルールのなかから、評価値が上位のルールR_max個を選択し、マスタが格納する結果ルールを更新する。
【０１３３】
その後、マスタ０１０１は、ジョブ管理テーブルの担当スレーブ１４０３の項目を参照し、結果を送信してきたスレーブのＩＤと同一のＩＤが格納されているジョブについて、ジョブ状態フラグ１４０４の項目を「結果受理」とする。
【０１３４】
分岐処理Ｓ１５０８において、マスタ０１０１は、ジョブ管理テーブルにおける、全てのジョブのジョブ状態フラグ１４０４が「結果受理」となったか否かをチェックする。その結果、ジョブ管理テーブルにおける全てのジョブのジョブ状態フラグ１４０４が「結果受理」となっていれば、マスタ０１０１は、結果出力処理Ｓ１５０９を実行し、そうでなければ、マスタ０１０１は、分岐処理Ｓ１５０１に戻る。
【０１３５】
結果出力処理Ｓ１５０９において、マスタ０１０１は、現在マスタで保持している特徴ルールの集合を、最終的な結果として入出力装置０１０５に出力する。これにより、分析処理が終了する。
【０１３６】
つぎに、図１６により、本実施形態に係るスレーブ処理の詳細を説明する。
【０１３７】
スレーブ０１０９は、分析実行登録処理Ｓ１６０１において、スレーブ追加の信号をマスタ０１０１に送り、分析実行初期化処理Ｓ１６０２において、マスタ０１０１からの分析実行通知の信号を待つ。スレーブ０１０９は、この信号を受け取ると、データ・パラメータ送信要求の信号をマスタ０１０１に送信して、マスタ０１０１から、分析対象データ及びルール生成に用いるパラメータを受信する。また、スレーブ０１０９は、分析実行初期化処理Ｓ１６０２において、分析結果のルール群を格納する領域をメモリに確保し、これらの領域を空に初期化する。ここでは、R_max個のルールを格納するために十分なメモリ領域が確保されるものとする。
【０１３８】
その後、スレーブ０１０９は、ジョブ要求処理Ｓ１６０３において、ジョブ要求の信号をマスタ０１０１に送信し、分岐処理Ｓ１６０４において、そのジョブ要求に対する応答信号が、新しいジョブの割り当て信号、及び、分析結果の送信を要求する信号のいずれであるかをチェックする。その結果、新しいジョブの割り当ての信号であれば、スレーブ０１０９は、分析実行処理Ｓ１６０５を実行し、分析結果の送信を要求する信号であれば、スレーブ０１０９は、途中結果送信処理Ｓ１６０６を実行する。
【０１３９】
分析実行処理Ｓ１６０５において、スレーブ０１０９は、割り当てられたジョブに対応する部分木を探索し、評価値の高いR_max個のルールを抽出する。ジョブの割り当て処理で伝達された担当項目番号をmとすると、この処理は、具体的には、以下のような手順で実現される。
【０１４０】
スレーブ０１０９は、条件部「Ａ(ｍ)＝Ｂ(Ａ(ｍ),１)」をカレントノードに設定して、カレントノードに対応するルール(カレントルール)の評価値を算出する。そして、スレーブ０１０９は、このスレーブの採用判定を行う。具体的には、スレーブ０１０９は、カレントルールの評価値が、このスレーブにおけるルールの最小評価値よりも大きいとの条件を満たすか否かを判定し、これが真であれば(カレントルールの評価値の方が大きければ)、このルールを採用する。
【０１４１】
スレーブ０１０９は、カレントルールを採用した場合、このカレントルールを、Ｓ１６０２で確保した分析結果テーブルに格納されたルールと、評価値が小さいルールから順番に比較してゆき、比較対象のルールの評価値がカレントルールの評価値を下回った時点で比較対象ルールの上位にカレントルールを挿入する。これにより分析結果テーブルに格納されているルールの数がR_max個を上回った場合には、スレーブ０１０９は、一番評価値の低いルールを削除してから、改めて分析結果テーブルに格納されている最下位のルールの評価値を参照し、最小評価値のパラメータをこの値で更新する。この後、スレーブ０１０９は、次に評価及び採用判定を行うノードの生成を試みる。その結果、ノード生成に成功すれば、スレーブ０１０９は、生成したルールをカレントノードに設定して、ノードの評価及び採用判定を再度実行し、ノード生成に失敗すれば、スレーブ０１０９は、ノードの評価を終了する。
【０１４２】
カレントノードの次のノードの生成は、以下のようにして行われる。
【０１４３】
ここでは、カレントルールの条件部ＸをＣ(１)  and  Ｃ(２)  and  …と表す。
【０１４４】
スレーブ０１０９は、まず、カレントノードの子ルールの生成を試みる。カレントルールの条件節の一番右端にある条件節Ｃ(ｋ)が条件項目Ａ(ｎ)を有する場合、スレーブ０１０９は、カレントルールの条件部にＡ(ｎ+１)＝Ｂ(Ａ(ｎ+１),１)を付け加えた条件部を有するルールを生成する。ただし、カレントルールの条件節数が既に最大条件節数C_maxに達している場合、または、Ｃ(ｋ)が条件節Ａ(Ｍ)  (Mは条件項目の数)を条件項目に持つ場合には、子ルールの生成は失敗する。子ルールの生成が成功した場合には、スレーブ０１０９は、生成したルールを次の評価を行うルールに設定する。一方、子ルールの生成が失敗した場合には、スレーブ０１０９は、次の処理に移る。
【０１４５】
次に、スレーブ０１０９は、「次のルールもカレントルールと同じ親ルールを持つ」という制約条件のもとで次のルールの生成を試みる。ここで、次のルールは、第１の実施形態において述べた条件部の順序関係に基づいて決定される。スレーブ０１０９は、上記の制約条件によって、次のルールを生成摺ることができれば、このルールを、次に評価を行うルールに設定する。一方、上記の制約条件を満たす次のルールが存在しなければ(生成が失敗すれば)、スレーブ０１０９は、カレントルールから親ルールに戻り(具体的には、カレントルールの条件部から一番右の条件節を削除し)、そのレイヤにおいて、上記と同様の制約条件で、次のルールの生成を試みる。ただし、深さ１のレイヤで次のルールの生成を試みる場合、条件節がＡ(m)＝Ｂ(Ａ(m),N(Ａ(m)))の次のルールの生成は失敗するものとする。
【０１４６】
スレーブ０１０９は、このような、同じレイヤにおける次のルールの生成に失敗するたびに親ルールに戻るという処理を繰り返し、ルートノードまで戻ったときには、次に評価するルールの生成が失敗したと判断する。
【０１４７】
このような処理を実行した後、スレーブ０１０９は、ジョブ分析結果送信処理Ｓ１６０７において、スレーブ０１０９が保持している特徴ルールのうち、最も表価値が低いルールの評価値をマスタ０１０１に送信する。その後、スレーブ０１０９は、ジョブ要求処理Ｓ１６０３に戻る。ただし、途中結果のルール群を保持する領域に格納されているルール数がR_max個に満たない場合には、スレーブ０１０９は、Ｓ１６０７で、評価値として「０」をマスタ０１０１に送信してから、Ｓ１６０３に戻る。
【０１４８】
結果送信処理Ｓ１６０６において、スレーブ０１０９は、保持している特徴ルールに関する情報をマスタ０１０１に送信する。このときマスタに送信される特徴ルールの情報には、それぞれの特徴ルールの条件部に含まれる条件項目とカテゴリの組、それぞれの特徴ルールの評価値が含まれている。
【０１４９】
その後、分析終了処理Ｓ１６０８において、スレーブ０１０９は、分析で使用したメモリの開放等、分析終了時に必要な処理を実行してから、処理を終了する。なお、スレーブ０１０９が、ここで処理を終了せずにＳ１６０２に処理を戻し、次のルール生成問題の開始を待機するようにしてもよい。
【０１５０】
また、本実施形態に係るスレーブ処理においては、スレーブ０１０９が、入出力装置０１０５から、分析中断の指示を受け付けるよう変更することも可能である。分析中断の指示の有無は、例えばＳ１６０３において、スレーブ０１０９がマスタ０１０１にジョブを要求する前にチェックされればよい。分析中断の指示があった場合には、スレーブ０１０９が、結果送信処理Ｓ１６０６及び分析終了処理Ｓ１６０８を行って、分析中断の信号をマスタ０１０１に送信してから、処理を終了するようにすればよい。
【０１５１】
以上、本発明に係る２つの実施形態について説明したが、これらの実施形態は、例えば、以下のように変更することが可能である。
【０１５２】
第１に、第１及び第２実施形態における、スレーブへのジョブの割り当ては、ジョブに含まれるノードの数の多い順に割り当てを行うように変更してもよい。
【０１５３】
第２に、第１及び第２実施形態における、スレーブへのジョブの割り当ては、ルール生成の進行状況に応じてジョブの大きさを動的に変更して再分割し、再分割したジョブをスレーブに割り当てるように変更してもよい。例えば、ルール生成において、スレーブへの割り当てを行っていないジョブの数が、分析者が定める一定の数を下回った場合に、一回のルール生成を通して一回だけ、残りのジョブを、分析者が指定する分割方法によって、より小さなジョブに再分割し、これをスレーブに割り当てるように変更することができる。このような分割方法として、例えば、分析が行われていない全ジョブを２等分するなどの方法が考えられる。
【０１５４】
このような第１及び第２の変更例によれば、ルール生成の終盤に近づくにつれてジョブの規模が小さくなり、スレーブがそのジョブを処理するのに要する時間が短縮される。このため、各スレーブにおける処理終了時刻をより高い精度で揃えてルール生成を行うことができ、結果として、全体の処理速度を向上させることができる。
【０１５５】
第３に、第１の実施形態の分析実行開始処理Ｓ０８０５における、探索木のジョブへの分割は、以下のような処理(１)〜(１０)で実現されてもよい。
(１)分割パラメータａ、最小ジョブサイズパラメータｂの値を、あらかじめ決めておく。あるいは、分析者が、あらかじめ入出力装置０１０５より入力しておく。ここで、ａ、ｂは、１以上の整数とする。マスタ０１０１は、スレーブ管理テーブルに登録されているスレーブの数(Ｓとする)を読み取る。
(２)マスタ０１０１は、レイヤ番号Iの初期値を１とする。
(３)マスタ０１０１は、レイヤIに含まれるノードの数(Nとする)を数える。
(４)マスタ０１０１は、Ｎ／(ａ*Ｓ)を計算し、その小数点以下を切り捨てる。これをZとする。ここで、Zは、整数であり、１個のジョブに含まれるノードの数である。
(５)ここでＺ<ｂであれば、マスタ０１０１はZにbを代入する。
(６)マスタ０１０１は、レイヤIの最初のノードをX_sとする。
(７)マスタ０１０１は、レイヤIにおいて、X_sから数えてZ番目のノードをX_eとする。ただし、Z番目まで数える前にレイヤIの最後のノードに達した場合には、マスタ０１０１は、レイヤIの最後のノードをX_eとする。
(８)マスタ０１０１は、X_sを開始ノード、X_eを終了ノードとしてジョブ管理テーブルにジョブを追加する。
(９)X_eがレイヤIの最後のノードであれば、マスタ０１０１は、(１０)へ、そうでなければ、マスタ０１０１は、レイヤIにおいてX_eの次のノードをX_sとして、(７)へ戻る。
(１０)Ｉが最大条件節数に等しければ、マスタ０１０１は、処理を終了させる。そうでなければ、マスタ０１０１は、Iに１を加算してから、(３)に戻る。
【０１５６】
このような第３の変更例によれば、各レイヤをより柔軟にジョブに分割することができるようになり、負荷を柔軟にスレーブに割り当てることができる。
【産業上の利用可能性】
【０１５７】
本発明に係るデータ分析方法は、例えば、購買データの分析、ＤＮＡチップを用いた遺伝子発現解析等の、膨大な探索空間を探索する必要があるデータ分析に使用することができる。
【図面の簡単な説明】
【０１５８】
【図１】本発明の実施形態に係るデータ分析を実行する情報処理システムの概略構成図である。
【図２】本発明の第一実施形態に係る分析対象データのデータ構造を概念的に示した図である。
【図３】本発明の第一実施形態に係る特徴ルールののデータ構造を概念的に示した図である。
【図４】特徴ルールを発見するための探索空間を表す木構造の一例を示した図である。
【図５】特徴ルールを発見するための探索空間を表した木構造の一例を示した図である。
【図６】図５の木構造をジョブに分割する方法を説明するための図である。
【図７】図５の木構造をジョブに分割する方法を説明するための図である。
【図８】本発明の第１の実施形態に係る、マスタが実行する、スレーブを管理するための処理のフローチャートである。
【図９】本発明の実施形態に係るスレーブ管理テーブルのデータ構造を概念的に示した図である。
【図１０】本発明の第１の実施形態に係るジョブ管理テーブルのデータ構造を概念的に示した図である。
【図１１】本発明の実施形態に係る、マスタがＳ０８０５で実行するスレーブ管理処理のフローチャートである。
【図１２】本発明の第１の実施形態に係る、マスタがＳ０８０５で実行する分析管理処理のフローチャートである。
【図１３】本発明の第１の実施形態に係るスレーブ処理のフローチャートである。
【図１４】本発明の第２の実施形態に係るジョブ管理テーブルのデータ構造を概念的に示した図である。
【図１５】本発明の第２の実施形態に係る、マスタが実行する分析処理のフローチャートである。
【図１６】本発明の第２の実施形態に係るスレーブ処理のフローチャートである。
【符号の説明】
【０１５９】
０１０２…処理装置、０１０３…メモリ、０１０４…プログラム、０１０５…入出力装置、０１０６…通信装置、０１０７…記憶装置、０１１０…通信路、０１１１…通信路
【図１】
2005275440.tif 000003
【図２】
2005275440.tif 000004
【図３】
2005275440.tif 000005
【図４】
2005275440.tif 000006
【図５】
2005275440.tif 000007
【図６】
2005275440.tif 000008
【図７】
2005275440.tif 000009
【図８】
2005275440.tif 000010
【図９】
2005275440.tif 000011
【図１０】
2005275440.tif 000012
【図１１】
2005275440.tif 000013
【図１２】
2005275440.tif 000014
【図１３】
2005275440.tif 000015
【図１４】
2005275440.tif 000016
【図１５】
2005275440.tif 000017
【図１６】
2005275440.tif 000018