(57)【要約】【課題】複数の計算機を利用してデータ分析を行う際、データ処理時間を短縮する。【解決手段】マスタ１０１と複数台のスレーブ１０９を用いてデータの分析を行うデータ分析方法において、マスタ１０１は、複数の分析問題を有するデータをレイヤに分割し、それぞれのレイヤを少なくとも１つの分析問題を含むジョブに分割する。またマスタ１０１は、評価を省略することのできる分析問題について示したフラグのリストを保持し、一つのレイヤの処理を開始する前にこのリストを全てのスレーブ１０９に送信する。スレーブ１０９は、マスタ１０１より受信したリストの情報を参照して分析問題の評価を選択的に実行し、処理の結果を用いてこのリストを更新し、更新したリストをマスタ１０１に送信する。また、マスタ１０１はスレーブ１０９より受信したリストの値を参照してマスタが内部に保持しているリストの値を更新する。【選択図】図1
2006107129.tif 000002
【特許請求の範囲】
【請求項１】
マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムが行なうデータ分析方法であって、
前記マスタ計算機は、
複数の分析問題が含まれている分析データの入力を受付けるステップと、
前記受付けた分析データを複数の階層グループ（以下「レイヤ」という）に分類するステップと、
上位のレイヤから順番に分析処理を行うレイヤを特定するステップと、
予め定めた規則にしたがい、前記特定されたレイヤに分類された分析データに含まれる分析問題毎に分析処理を行なうか否かを対応付けた条件リストを作成し、該作成した条件リストを保持する条件リスト生成ステップと、
前記保持している条件リストおよび前記分析データを前記スレーブ計算機に送信するステップと、
前記特定されたレイヤに分類された分析データを少なくとも１の分析問題が含まれるジョブに分割するステップと、
前記分割したジョブを前記スレーブ計算機に割り当てるステップと、を行い、
前記複数のスレーブ計算機は、各々、
前記マスタ計算機が送信した条件リストおよび前記分析データを受信するステップと、
前記マスタ計算機から割り当てられたジョブを受付けるステップと、
前記受信した条件リストを用いて、前記受付けたジョブに含まれる分析問題の中から、分析処理を行なうことが対応付けられている分析問題を選択するステップと、
前記選択した分析問題に対する分析処理を実行するステップと、
前記受信した分析データを用いて、前記割り当てられたジョブが属するレイヤの下位のレイヤに含まれる分析問題について、評価処理の必要性を判定するステップと、
前記判定結果を用いて、前記受信した条件リストを更新し、該更新した条件リストを前記マスタ計算機に送信するステップと、を実行し、
前記条件リスト生成ステップは、
前記スレーブ計算機が更新した条件リストを送信した場合、該送信された条件リストを受信して、該受信した条件リストを用いて、自身が保持する条件リストを更新すること
特徴とするデータ分析方法。
【請求項２】
マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムが行なうデータ分析方法であって、
前記マスタ計算機は、
分析対象のデータ、および、分析対象データの属性をカテゴリで分類した属性条件の入力を受付けるステップと、
前記受付けた属性条件を１以上組合せたルールを複数集めたルール生成問題を作成するステップと、
前記作成したルール生成問題を複数の階層グループ（以下「レイヤ」という）に分類するステップと、
一のレイヤを分析対象のレイヤに特定するステップと、
予め定めた規則にしたがい、前記特定したレイヤに分類された前記ルール生成問題に含まれているルールに、評価を行なうか否かを示す情報を対応付けた条件リストを作成し、該作成した条件リストを保持するステップと、
前記保持している条件リスト、前記ルール生成問題、および前記分析対象データを前記スレーブ計算機に送信するステップと、
前記特定したレイヤを少なくとも１のルールが含まれるジョブに分割するステップと、
前記分割したジョブを前記スレーブ計算機に割り当てるステップと、を実行し、
前記複数のスレーブ計算機は、各々、
前記マスタ計算機が送信した前記条件リスト、前記ルール生成問題、および前記分析対象データを受信するステップと、
前記マスタ計算機から割り当てられたジョブを受付けるステップと、
前記受信した条件リストを用いて、前記受付けたジョブに含まれるルールの中から評価を行なうことが対応付けられているルールを選択するステップと、
前記受信した分析対象データを用いて、前記選択したルールに対する評価を実行するステップと、
前記受信したルール生成問題を用いて、前記割り当てられたジョブが属するレイヤと別のレイヤに分類されたルールについて、分析処理の必要性を判定するステップと、
前記判定の結果を用いて、前記受信した条件リストを更新して、該更新した条件リストを前記マスタ計算機に送信するステップと、を実行し、
前記条件リストを保持するステップは、
前記スレーブ計算機が更新した条件リストを送信した場合、該送信された条件リストを受信し、該受信した条件リストを用いて、自身が保持する条件リストを更新すること
特徴とするデータ分析方法。
【請求項３】
請求項２に記載のデータ分析方法であって、
前記スレーブ計算機が行う評価の必要性を判定するステップは、
前記割り当てられたジョブが属するレイヤに含まれる全てのルールの評価が終了した後に、当該レイヤの下位のレイヤに含まれるルールについて、評価の必要性の有無の判定を行うこと
を特徴とするデータ分析方法。
【請求項４】
請求項２〜３のいずれか一項に記載のデータ分析方法であって、
前記ルールは、分析対象データの特徴をＩＦ〜ＴＨＥＮ〜形式のルールで示したものであること
を特徴とするデータ分析方法。
【請求項５】
請求項２〜４のいずれか一項に記載のデータ分析方法であって、
前記分析対象データは、複数の属性項目からなるレコードの集合であって、
前記選択したルールに対する評価を実行するステップは、
前記選択した一のルールの評価を行なう際、当該ルールを構成する属性条件を満たす分析対象データのレコードを識別するインデックスを作成するステップと、
前記一のルールの評価を実行した後で、当該一のルールと異なる他のルールの評価を行う場合に、前記一のルールを構成する属性条件と、前記他のルールを構成する属性条件とを比較し、前記比較の結果、前記他のルールに前記一のルールと同じ構成の属性条件が含まれている場合、前記作成したインデックスにより識別されレコードだけを用いて、当該他のルールの評価を行なうステップと、を有すること
を特徴とするデータ分析方法。
【請求項６】
請求項３〜５のいずれか一項に記載のデータ分析方法であって、
前記スレーブ計算機は、
所定に基準にしたがい前記マスタ計算機に前記ルールの評価結果を送信する評価結果送信ステップを行い、
前記マスタ計算機は、
前記スレーブ計算機が送信したルールの評価結果を受信して、該受信した評価結果を集計したルールリストを作成し、該ルールリストを保持するステップと、
一つのレイヤに含まれるジョブをスレーブ計算機に割り当てる前に、該スレーブ計算機に、自身が保持しているルールリストを送信するステップと、を行い、
前記評価結果送信ステップは、
前記レイヤに含まれる全てのジョブの処理が終了した後に、前記マスタ計算機から送信されたルールリストに含まれないルールの評価結果を前記マスタ計算機に送信すること
を特徴とするデータ分析方法。
【請求項７】
請求項１〜６のいずれか一項に記載のデータ分析方法であって、
前記スレーブ計算機には出力装置が接続されていて、
前記スレーブ計算機は、
前記評価したルールの処理量を示す情報を前記出力装置に出力するステップを行うこと
を特徴とするデータ分析方法。
【請求項８】
請求項７に記載のデータ分析法方であって、
前記マスタ計算機には出力装置が接続されていて、
前記スレーブ計算機は、前記評価したルールの処理量を示す情報をマスタ計算機に送信するステップを行ない、
前記マスタ計算機は、
前記スレーブ計算機が送信した前記処理量を受信して、該受信した処理量を自身に接続された前記出力装置に出力すること
を特徴とするデータ分析方法。
【請求項９】
マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムであって、
前記マスタ計算機は、
複数の分析問題が含まれている分析データの入力を受付ける手段と、
前記受付けた分析データを複数の階層グループ（以下「レイヤ」という）に分類する手段と、
上位のレイヤから順番に分析処理を行うレイヤを特定する手段と、
予め定めた規則にしたがい、前記特定されたレイヤに分類された分析データに含まれる分析問題毎に分析処理を行なうか否かを対応付けた条件リストを作成し、該作成した条件リストを保持する条件リスト生成手段と、
前記保持している条件リストおよび前記分析データを前記スレーブ計算機に送信する手段と、
前記特定されたレイヤに分類された分析データを少なくとも１の分析問題が含まれるジョブに分割する手段と、
前記分割したジョブを前記スレーブ計算機に割り当てる手段と、を有し、
前記複数のスレーブ計算機は、各々、
前記マスタ計算機が送信した条件リストおよび前記分析データを受信する手段と、
前記マスタ計算機から割り当てられたジョブを受付ける手段と、
前記受信した条件リストを用いて、前記受付けたジョブに含まれる分析問題の中から、分析処理を行なうことが対応付けられている分析問題を選択する手段と、
前記選択した分析問題に対する分析処理を実行する手段と、
前記受信した分析データを用いて、前記割り当てられたジョブが属するレイヤの下位のレイヤに含まれる分析問題について、分析処理の必要性を判定する手段と、
前記判定結果を用いて、前記受信した条件リストを更新し、該更新した条件リストを前記マスタ計算機に送信する手段と、を有し、
前記条件リスト生成手段は、
前記スレーブ計算機が更新した条件リストを送信した場合、該送信された条件リストを受信して、該受信した条件リストを用いて、自身が保持する条件リストを更新すること
特徴とするデータ分析システム。
【請求項１０】
マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムにおいて、前記マスタ計算機にデータ分析に関する処理を実行させるプログラムであって、
前記プログラムは、
複数の分析問題が含まれている分析データの入力を受付けるステップと、
前記受付けた分析データを複数の階層グループ（以下「レイヤ」という）に分類するステップと、
上位のレイヤから順番に分析処理を行うレイヤを特定するステップと、
予め定めた規則にしたがい、前記特定されたレイヤに分類された分析データに含まれる分析問題毎に分析処理を行なうか否かを対応付けた条件リストを作成し、該作成した条件リストを保持する条件リスト生成ステップと、
前記保持している条件リストおよび前記分析データを前記スレーブ計算機に送信するステップと、
前記特定されたレイヤに分類された分析データを少なくとも１の分析問題が含まれるジョブに分割するステップと、
前記分割したジョブを前記スレーブ計算機に割り当てるステップと、を前記マスタ計算機に実行させて、
前記条件リスト生成ステップは、
前記スレーブ計算機が前記割り当てられたジョブが属するレイヤの下位のレイヤに含まれる分析問題について、分析処理の必要性を判定して、当該判定結果を前記マスタ計算機に送信した場合に、前記判定結果を受信して、該受信した判定結果を用いて、前記保持する条件リストを更新するステップを有すること
を特徴とするプログラム。
【請求項１１】
マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムにおいて、前記スレーブ計算機にデータ分析に関する処理を実行させるプログラムであって、
前記マスタ計算機は、
複数の分析問題が含まれている分析データの入力を受付けるステップと、
前記受付けた分析データを複数の階層グループ（以下「レイヤ」という）に分類するステップと、
上位のレイヤから順番に分析処理を行うレイヤを特定するステップと、
予め定めた規則にしたがい、前記特定されたレイヤに分類された分析データに含まれる分析問題毎に分析処理を行なうか否かを対応付けた条件リストを作成し、該作成した条件リストを保持する条件リスト生成ステップと、
前記保持している条件リストおよび前記分析データを前記スレーブ計算機に送信するステップと、
前記特定されたレイヤに分類された分析データを少なくとも１の分析問題が含まれるジョブに分割するステップと、
前記分割したジョブを前記スレーブ計算機に割り当てるステップと、を行なうものであって、
前記プログラムは、
前記マスタ計算機が送信した条件リストおよび前記分析データを受信するステップと、
前記マスタ計算機から割り当てられたジョブを受付けるステップと、
前記受信した条件リストを用いて、前記受付けたジョブに含まれる分析問題の中から、分析処理を行なうことが対応付けられている分析問題を選択するステップと、
前記選択した分析問題に対する分析処理を実行するステップと、
前記受信した分析データを用いて、前記割り当てられたジョブが属するレイヤの下位のレイヤに含まれる分析問題について、分析処理の必要性を判定するステップと、
前記判定結果を用いて、前記受信した条件リストを更新し、該更新した条件リストを前記マスタ計算機に送信するステップと、を前記スレーブ計算機に実行させること
を特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ分析方法に係り、特に複数の計算機を用いて並列に分析処理を行うデータ分析の技術に関する。
【背景技術】
【０００２】
大量のデータから知識を発見する技術は、データマイニングと呼ばれている。発見される知識の具体例としては特徴ルール(Characteristic Rule)が知られている。特徴ルールを用いて大量のデータから知識を発見する技術は、特許文献１に記載されている。特許文献１は、分析処理全体の中から分析が必要な処理と不要な処理を判定して、分析が必要な処理だけを行うようにしている。
【０００３】
また、データ分析の処理時間を短縮させるための技術が特許文献２に記載されている。特許文献２では、膨大な量の計算を必要とするアルゴリズムを実行するために、データ分析を分散環境にて実行する方法が考案されている。
【０００４】
【特許文献１】特開平８−７７０１０号公報
【特許文献２】特開２０００−２４２６１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１では、１台の計算機でデータの分析処理を行なうようにしている。そのため、たとえ、データ処理量を低減したとしても、分析対象のデータが大規模になると、結果的に処理が終了するまでに非常に時間がかかるという問題が発生してしまう。また、特許文献１では、データ処理量を低減する手段を複数の装置を利用して行なうことについて何ら考慮されていない。
【０００６】
特許文献２では、並列実行による処理時間短縮の効果はあるが、この手法は、処理を分割して複数台の計算機に分配するだけであり、処理量自体が削減されるわけではない。なお、特許文献２では、データ処理全体の処理量を低減させるための考慮は何らなされていない。
【０００７】
そこで、本発明の目的は、複数の計算機を利用してデータ分析を行う際に、データ分析の処理量を削減し、データ処理時間を短縮することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本発明の一態様は、マスタ計算機と、前記マスタ計算機に通信路を介して接続されている複数台のスレーブ計算機とを有するデータ分析システムに適用される。
【０００９】
そして、前記マスタ計算機は、複数の分析問題が含まれている分析データの入力を受付けるステップと、前記受付けた分析データを複数の階層グループ（以下「レイヤ」という）に分類するステップと、上位のレイヤから順番に分析処理を行うレイヤを特定するステップと、予め定めた規則にしたがい、前記特定されたレイヤに分類された分析データに含まれる分析問題毎に分析処理を行なうか否かを対応付けた条件リストを作成し、該作成した条件リストを保持する条件リスト生成ステップと、前記保持している条件リストおよび前記分析データを前記スレーブ計算機に送信するステップと、前記特定されたレイヤに分類された分析データを少なくとも１の分析問題が含まれるジョブに分割するステップと、前記分割したジョブを前記スレーブ計算機に割り当てるステップと、を行い、前記複数のスレーブ計算機は、各々、前記マスタ計算機が送信した条件リストおよび前記分析データを受信するステップと、前記マスタ計算機から割り当てられたジョブを受付けるステップと、前記受信した条件リストを用いて、前記受付けたジョブに含まれる分析問題の中から、分析処理を行なうことが対応付けられている分析問題を選択するステップと、前記選択した分析問題に対する分析処理を実行するステップと、前記受信した分析データを用いて、前記割り当てられたジョブが属するレイヤの下位のレイヤに含まれる分析問題について、分析処理の必要性を判定するステップと、前記判定結果を用いて、前記受信した条件リストを更新し、該更新した条件リストを前記マスタ計算機に送信するステップと、を実行し、前記条件リスト生成ステップは、前記スレーブ計算機が更新した条件リストを送信した場合、該送信された条件リストを受信して、該受信した条件リストを用いて、自身が保持する条件リストを更新する。
【発明の効果】
【００１０】
このように本発明によれば、データ分析の処理を複数の処理に分割し、複数の計算機を用いて並列に実行している。また、マスタ計算機および複数のスレーブ計算機のそれぞれに、ジョブに含まれる分析問題毎に分析処理を行なうか否かを対応付けたパラメータを保持させるようにしている。そして、スレーブ計算機は、そのパラメータを用いて、割り当てられたジョブの中から、分析処理を行なうことが対応付けられている分析問題選択して分析するようにしている。また、スレーブ計算機は、割り当てられたジョブと別のレイヤに含まれる分析問題について、分析処理の必要性を判定して、マスタ計算機が保持するパラメータを更新するようにしている。
【００１１】
そのため、本発明によれば、複数の計算機を利用してデータ分析を行う際に、データ分析の処理量を削減でき、結果的に、データ処理時間を短縮することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施形態を、図面を用いて説明する。
〈第１実施形態〉
先ず、本発明の第１実施形態について説明する。なお、本実施形態では、データ分析処理として、表形式の分析対象データからそのデータの特徴を表す特徴ルールと呼ばれる「ＩＦ〜ＴＨＥＮ…」形式のルールを生成する処理を行なう場合を例に説明する。また、本実施形態は、この分析問題を解くために分析処理の全体を管理するための計算機(以下、「マスタ」と呼ぶ)と、実際に分析を行う複数台の計算機(以下、「スレーブ」と呼ぶ)とを有するシステムを用いる。また、特徴ルールを単にルールと記述することもある。
【００１３】
図１は、本発明の第１実施形態のデータ分析システムの全体構成を説明するための図である。
【００１４】
図示するように、データ分析システムは、マスタ１０１と、１台以上のスレーブ１０９ａ〜ｎ（以下、単に「スレーブ１０９」という）と、データ記憶装置１０８とを有する。マスタ１０１、１台以上のスレーブ１０９、およびデータ記憶装置１０８は、バス型の通信路１１０を介して相互に接続されている。
【００１５】
マスタ１０１は、データ分析処理の全体を管理する計算機である。マスタ１０１は、１つのデータ分析処理を複数のジョブ（ジョブの構成については後述する）に分割して、分割した複数のジョブをそれぞれのスレーブ１０９に振分けて割り当てる。マスタ１０１は、ジョブを割り当てたスレーブ１０９に対して、その割り当てたジョブを実行させる。また、マスタ１０１は、スレーブ１０９が行なったジョブの実行結果を集めて集計する。
【００１６】
具体的には、マスタ１０１は、処理装置１０２、入出力装置１０５、および記憶装置１０７を有する。処理装置１０２、入出力装置１０５、および記憶装置１０７は、通信路１１１を介して相互に接続されている。
【００１７】
処理装置１３０は、各種の処理を実行するためのＣＰＵ（中央演算装置）１２０と、ＣＰＵ１２０が実行するプログラム１０４やＣＰＵ１２０が実行する処理に必要なデータ（図示しない）を一時的に格納するメモリ１０３とを有する。なお、後段で説明するマスタ１０１が行なう処理は、ＣＰＵ１２０がメモリ１０３に格納されているプログラム１０４を実行することにより実現されるものである。
【００１８】
入出力装置１０５は、利用者が入力する各種の情報や操作命令等を受付ける入力器（図示しない）と、マスタ１０１が行なった分析結果等を出力する出力器（図示しない）と、外部の装置との間で行う通信を管理する通信装置１０６とを有する。なお、入力器には、例えば、キーボードやマウス等を用いることができる。出力器には、分析結果の表示画面や各種の設定画面を表示する液晶表示装置やＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）等のディスプレイ装置を用いることができる。また、マスタ１０１は、この通信装置１０６を介して通信路１１０と接続されている。記憶装置１０７は、大量のデータを記憶する容量を持つ、例えばハードディスク装置のような機器である。
【００１９】
スレーブ１０９は、マスタ１０１から割り当てられたジョブを実行して、その結果をマスタ１０１に送信する。具体的には、スレーブ１０９は、マスタ１０１と同様、処理装置１１２、入出力装置１１５、および記憶装置１１７を有する。処理装置１１２、入出力装置１１５、および記憶装置１１７は、通信路１１８を介して相互に接続されている。
【００２０】
処理装置１３０は、各種の処理を実行するＣＰＵ（中央演算装置）１３０と、ＣＰＵ１３０が実行するプログラム１１４やＣＰＵ１２０が実行する処理に必要なデータ（図示しない）を一時的に格納するメモリ１１３とを有する。なお、後段で説明するスレーブ１０９が行なう処理は、ＣＰＵ１３０がメモリ１１３に格納されているプログラム１１４を実行することにより実現されるものである。入出力装置１１５および記憶装置１１７の構成は、上述したマスタ１０１が有する入出力装置１０５および記憶装置１０７の構成と同様である。
【００２１】
データ記憶装置１０８は、分析対象のデータを格納するための装置であり、マスタと同様の構成（処理装置、入出力装置、および記憶装置）を有する。なお、データ記憶装置１０８が行なう処理は、従来技術により実現されるため説明は省略する。
【００２２】
続いて、本実施形態のデータ分析システムが行なう特徴ルール生成処理のアルゴリズムの概要を説明する。
【００２３】
まず始めに、特徴ルールを生成するための入力データである分析対象データ、および、分析結果として出力される特徴ルールについて図２〜３を用いて説明する。
【００２４】
図２は、本実施形態で用いられる分析対象データのデータ構成を模擬的に示した図である。
【００２５】
分析対象データ２００は、複数の属性項目(以下、簡単に項目とも記述する)２０１〜２０４からなるレコードの集合であり、全てのレコードは同じ項目を有する。項目にはそれぞれのレコードのある属性をあらわす値が格納されている。レコードや項目が具体的に何を表すかは分析対象のデータに依存するが、図２では、ある商店の購買履歴のデータを分析対象とする場合の例を示している。図示する例では、分析対象データ２００は、顧客を識別する顧客ＩＤを格納するための項目２０１と、その顧客の性別を格納するための項目２０２と、その顧客の年齢を格納するための項目２０３と、その顧客の購入総額を格納するための項目２０４とを備えて１つのレコードが構成されている。なお、１つのレコードは、一人の顧客に対応している。
【００２６】
また、本実施形態の特徴ルール生成では、前処理としてそれぞれの項目の属性値を少数のカテゴリに変換する場合がある。この処理をカテゴリ化と呼ぶ。例えば、年齢は、通常１０〜１００歳程度の属性値を取り得るが、これを「２５歳以下」、「２６歳から３５歳」、「３６歳以上」のようにカテゴリに変換する。この場合は、年齢という属性項目を３つのカテゴリに変換したことになる。性別のように元々「男」「女」の２値しか値を取らないものは、このままカテゴリとして用いることもある。この場合、性別は、２つのカテゴリを持つ属性項目である。図２に示す分析対象データ２００に含まれる値は、このようなカテゴリ化の処理を施したものである。
【００２７】
続いて、特徴ルール生成処理により出力される特徴ルールを説明する。
【００２８】
特徴ルールは、例えば、以下の（式１）のように表すことができる。
IF 年齢=26〜35 AND 購買頻度=高 THEN 購入総額=高…（式１）
すなわち、特徴ルールとは、属性項目とそのカテゴリを組み合わせた節をIF以下の条件部とTHEN以下の結論部に持つ、IF〜THEN…形式のルールである。なお、条件部に現れる属性を条件項目、結論部に現れる属性を結論項目と呼ぶ。また、特徴ルールの条件部に現れる条件項目とそのカテゴリの組を条件節と呼ぶ。
【００２９】
また、特徴ルールは、そのルールが対象データの特徴をどの程度よく表しているかを定量的に評価する指標となる評価値を持つ。この評価値は、特徴ルールを「IF X THEN Y」と表す場合、以下の（式２）で定義することができる。
P(X)^a * log(P(Y|X)/P(Y)) …（式２）
ここでP(X)、P(Y)は、それぞれ、分析対象データ全体のうちで、条件X、条件Yを満足するレコードの割合である。P(Y|X)は、条件Xを満足するレコードのうち条件Xと条件Yの両方を満足するレコードの割合である。また、指数aは、ルールの評価において一般性(あるルールがどのくらい多くのデータに適用できるかを示す指標)と精度(あるルールの条件部がどのくらい正確に結論部をあらわしているかを示す指標)とのどちらに重点をおくかを定める正の定数であり、分析者によって指定される。
【００３０】
なお、本実施形態では、評価値の定義について特に限定しない。例えば、評価値の別の定義として、以下の（式３）を用いるようにしてもよい。
P(X)^a * P(Y|X) * log(P(Y|X)/P(Y))…（式３）
そして、評価値の定義に上記のいずれを用いるにしても、ある特徴ルールに現れる条件部を満たすレコードの数、結論部を満たすレコードの数、条件部と結論部を満たすレコードの数、および分析対象データ全体のレコードの数を知ることによって、評価値を算出することができる。
【００３１】
次に、特徴ルール生成のアルゴリズムの概要を説明する。特徴ルール生成とは、上記で定義した評価値に基づき、この値の大きな特徴ルールを発見するアルゴリズムである。特徴ルール生成の出力としては、評価値の大きい順にルールをソートし、その上位を出力する。このような出力の例を図３に示す。
【００３２】
図３は、本実施形態の特徴ルール生成処理により出力されるデータを例示した図である。図示するように、特徴ルール生成処理の結果出力されるデータは、評価値の大きさの順位毎に作成された特徴ルールとその評価値とが対応付けられている。
【００３３】
次に、特徴ルール生成処理を実行する際の前準備について説明する。
【００３４】
特徴ルール生成処理を行うにあたって、分析者は、処理を実行する前に以下の処理を行い、データ分析システムに各種の条件を設定する。
【００３５】
具体的には、分析者は、分析対象データの属性項目より、条件節に含まれる項目の候補となる複数の項目を選択する。これは前述の属性項目である。データ分析システムは、分析者が選択した項目の入力を受付ける。
【００３６】
また、分析者は、条件項目についてカテゴリ化の処理を行なう。データ分析システムは、分析者がカテゴリ化した情報の入力を受付ける。さらに、分析者は、結果として出力する特徴ルール数の上限、結論項目となる分析対象データの属性項目とそのカテゴリ、一つの特徴ルールに含まれる条件項目の数の上限(以下、最大条件節数という)をデータ分析システムに指定する。データ分析システムは、上記の指定されたデータを受付ける。
【００３７】
次に、特徴ルール生成処理における、特徴ルールの探索について説明する。特徴ルールの探索とは、多数のルールから、評価値の高いルールを探し出す処理のことである。特徴ルール生成では与えられた条件より考え得る特徴ルールを木構造にみなして、この木構造を探索することにより評価値の高いルールを探し出す。以下ではこの木構造について説明するが、それに先立ち、特徴ルールの一般的な表記方法、特徴ルール間の順序関係について説明し、この説明を踏まえて上記の木構造について説明する。
【００３８】
以下に特徴ルールの一般的な表記方法について説明する。
【００３９】
まず、特徴ルール生成する処理において、分析者は、与えられた条件項目に条件項目番号を条件項目によって重複しないように与える。そして、データ分析システムは、条件項目毎に与えられた条件項目番号をテーブル形式のデータとして保持する。ここで、条件項目番号と条件項目を対応付けるテーブルの例を図４に示す。
【００４０】
図４は、条件項目番号と条件項目を示す項目名称とを対応付けるテーブルの一例を示す図である。図示するように、条件項目番号と条件項目を対応付けるテーブル（以下、「条件項目番号テーブル４００」という）は、「項目番号」を格納するためのエントリ４０１とエントリ４０１に格納された「項目番号」に対応付けた「項目名称」を格納するためのエントリ４０２とを有する。図示する例では、１からの連番を条件項目に与えている場合の例を示している。
【００４１】
分析者は、上記の条件番号を与える処理と同様に、条件項目のそれぞれのカテゴリにカテゴリ番号を与える。この場合、分析者は、それぞれの条件項目の中でカテゴリ番号が重複しないようにする。データ分析システムは、与えたれたカテゴリとカテゴリ番号とをテーブル形式のデータとして保持する。ここで、カテゴリ番号とカテゴリ名称を格納するテーブルの例を図５に示す。
【００４２】
図５は、カテゴリ番号とカテゴリ名称とを対応付けるテーブルの一例を示す図である。図示するように、カテゴリ番号とカテゴリ名称とを対応付けるテーブル（以下、「カテゴリ番号テーブル５００」という）は、「カテゴリ番号」を格納するためのエントリ５０１とエントリ５０１に格納された「カテゴリ番号」に対応付けた「カテゴリ名称」を格納するためのエントリ５０２とを有する。図５では「性別」という属性項目について「男性」、「女性」のカテゴリに分け、それぞれに１、２のカテゴリ番号を与えている場合を示している。
【００４３】
続いて、本実施形態の特徴ルール生成処理において用いる数式を説明する。以下では、Ｍ個の条件項目が与えられており、各条件項目は、カテゴリ化されている場合を例にする。また、条件項目番号がｎの条件項目をａ（n）で表し、ａ(n)のカテゴリ番号がｍのカテゴリをｖ(m，n)で表す。また、最大条件節数を「Ｃ_ｍａｘ」と表すことにする。そして、このような場合、特徴ルール「ＩＦ Ｘ ＴＨＥＮ Ｙ」は以下のように述べることができる。すなわち、条件部「Ｘ」は、条件節Ｃ(ｉ)の論理積として「Ｃ（１） ａｎｄ … ａｎｄ Ｃ（ｋ）」と書き表すことができる。ここで、「ｉ」は、「1≦ｉ≦k」を満たすものとする。また、「k」は、「1≦k≦Ｃ_ｍａｘ」の整数であるものとする。
【００４４】
条件節Ｃ(ｉ)は、条件項目a(m)と、a(m)のカテゴリｖ(m，n)との組み合わせであり、特徴ルールの中では「ａ（m） ＝ ｖ（m， n）」と表現される。
【００４５】
ここで、条件節が複数個含まれる特徴ルールは、以下のような性質を持つものとする。ｋ個の条件節からなる条件部「Ｃ（１） and … and Ｃ（ｋ） (２≦ｋ≦Ｃ_ｍａｘ)」において、任意の２個の条件節を「Ｃ（ｉ）、Ｃ（ｊ） (C(i)はa(m) = v(m, n)として、C(j)はa(p) = v(p, q)とする)」とした場合、「ｉ＜ｊ」ならば「ｍ＜ｐ」となる。すなわち、一つのルールにおいて、同じ条件項目は現れず、条件節は、条件項目の番号で昇順に並んでいるものとする。
【００４６】
次に、上記のように表される任意の２つの特徴ルールの間に、以下のような順序関係を与える。
【００４７】
まず、条件項目の順序関係を条件項目番号、各条件項目のカテゴリ間の順序関係をカテゴリ番号によって定める。そして、条件項目の順序関係とカテゴリの順序関係に基づき、条件節と条件部の順序関係を定める。条件節の順序関係は、まず条件項目の順序関係によって決定し、条件項目が同じ場合はカテゴリの順序関係によって決定する。条件部の順序関係は、条件部に含まれる条件節を順序関係の早い順に整列し、これらの順序関係を先頭の条件節から比較する事によって定める。
【００４８】
特徴ルールの順序関係は、同じ結論部を持つルールについて定義する。特徴ルールの条件部の順序関係が特徴ルールの順序関係となる。結論部が異なる特徴ルールの間に順序関係は定義しない。
【００４９】
続いて、上述した説明を踏まえて、特徴ルール生成の問題において、特徴ルールの集合を木構造に対応付ける処理を説明する。
【００５０】
さて、上記より考え得る特徴ルールは数多く存在するが、それらの関係は図６で述べるような木構造であらわすことができる。特徴ルール生成においては、この木を走査(探索)することによって、特徴ルールを発見するのでこの木を探索木と呼ぶことにする。以下、探索木について図６を用いて説明する。
【００５１】
図６は、特徴ルール生成における探索木の一例を示す図である。
【００５２】
探索木は、１つのルートノード６００と、条件節Ｃ(ｉ)を示す複数のノード（６００−１〜６００−ｎ）と、ルートノード６００とノード（６００−１〜６００−ｎ）との間を繋ぐ枝と、各ノード（６００−１〜６００−ｎ）間を繋ぐ枝と、を有する。
【００５３】
図示する例では、ルートノード６００を除く全てのノード（６００−１〜６００−ｎ）は、一つの特徴ルールに対応している。ルートノード６００からあるノードに至るまでの枝の数を深さと呼び、同一の深さにあるノードの集合をレイヤと呼ぶこととする。また、深さがｎのレイヤをレイヤｎと呼ぶことにすると、レイヤｎに含まれるルールはｎの条件節を持つ。
【００５４】
レイヤ１には、1条件節を持つルールを、ルールの順序関係に従って、より順序の小さいルールより順に配置する。また、枝で結ばれる二つのノードは、以下に説明する親ルール、子ルールの関係が成立する。枝で結ばれた二つのノードのうち、浅いレイヤにあるノードを親ノード、深いレイヤにあるノードを子ノードとよび、それぞれのノードに対応するルールを親ルール、子ルールと呼ぶことにする。この場合、子ルールが「C(1) and … and C(k-1) and C(k)」のような条件部を持つ場合、その親ルールの条件部は子ルールの条件部から最後に現れる条件節C(k)を取り除いた「C(1) and … and C(k-1)」という条件部を持つ。また、一つの親ルールに属する子ルール同士については、ルールの順序関係に従って、より順序の小さいルールより順に配置する。
【００５５】
そして、上述のように、特徴ルール生成では探索木のノードを順に評価していくことによって、評価値が上位のルールを発見する。この評価の手順についてはいくつかのアルゴリズムが考えられるが、本実施形態では幅優先探索を用いる。
【００５６】
幅優先探索とは、探索木の深さ1のレイヤより、同じレイヤにあるノードをまず評価し、そのレイヤの全てのノードを評価し終えたら、次のレイヤに移るという探索方法である。例えば図６の探索木を幅優先探索のアルゴリズムで探索する場合、その手順は以下のようになる。まず、深さ１のレイヤに含まれる特徴ルールについて、その順序関係に従って全てのルールの評価を行い、これが完了すると深さ２の探索に移る。これをあらかじめ設定した最大条件節の深さのレイヤまでくり返す。
【００５７】
本実施形態のデータ分析システムは、幅優先探索を用いて各レイヤにおいて特徴ルールの探索を行う際、その前のレイヤ(深さが１少ないレイヤ)までのルール生成結果を参照し、冗長なルールを排除しつつ探索を行う。
【００５８】
ここで、冗長ルールとは、例えば以下のようなルールのことである。「ルールＲ＿ａ」および「ルールＲ＿ｂ」を含むルールの集合Ｒにおいて、「Ｒ＿ａ」の条件部が「Ｒ＿ｂ」の条件部に含まれる条件節のいくつかからなり、かつ「Ｒ＿ａ」の評価値が「Ｒ＿ｂ」と同じかもしくは大きいものとする。この場合、ルール集合Ｒの中において「Ｒ＿ｂ」は、冗長ルールである。
【００５９】
また、木構造の探索を行う場合、枝刈りと呼ばれる処理を行って、全体の探索時間を短縮することができる。ここで、枝刈りとは、全体の処理を木構造に表現できる場合において、所定の規則にしたがい処理の一部を省く処理のことをいう。以下、探索木の探索アルゴリズムにおける枝刈り処理について説明する。
【００６０】
特徴ルール生成の結果として出力するルール数の上限をＲ＿ｍａｘ個とする。探索木において、あるルールを評価する場合、そのルールの子孫ルールの評価値の最大値を推定し、その値がその時点で判明しているＲ＿ｍａｘ番目の評価値を持つルールの評価値よりも小さい場合、これらの子孫ルールは結果として出力され得ないため、探索を省き、処理時間を短縮する。上記の子孫ルールの最大値の推定方法については、特許文献1に記載の技術により実現することができる。
【００６１】
例えば、あるルールの評価値を、上述の（式２）により算出した場合、この評価値をμとする。そして、このルールの子孫ルールの評価値の最大値は、以下に示す（式４）により推定することができる。
max [μ, (N_xy / N)^a * log(N / N_y)]…（式４）
ここでmax[n, m]は、nとmの大きい方の数を返す関数である。「N_xy」は、分析対象データにおいて条件Xと条件Yの両方を満たすレコードの数、「N_y」は、分析対象データにおいて条件Yを満たすレコードの数、Nは分析対象データ含まれるレコードの数である。
【００６２】
以下に、本実施形態において採用する、幅優先探索で枝刈りを行う一手法について説明する。
【００６３】
本実施形態における枝刈り手法では、レイヤｎにおいてルールを探索する際、評価の対象となっているルールの子孫ルールの評価値の最大値を推定し、そこで枝刈りが発生しているかどうかを記録しておき、レイヤｎ＋１の探索の際にこの記録に基づいて枝刈りを行う。
【００６４】
本実施形態のデータ分析システムでは、条件項目a(m)とそれぞれの条件項目の取るカテゴリv(m, n)の全ての組み合わせについて、枝刈りが発生しているかどうかを判定するフラグを保持するようにする。このフラグのリストを枝刈り条件節リストと呼ぶ。枝刈り条件節リストの例を図７に示す。
【００６５】
図７は、本実施形態の枝刈り条件節リストの一例を示す図である。図示するように、枝刈り条件節リスト７００は、条件項目a(m)とそれぞれの条件項目の取るカテゴリv(m, n)の全ての組み合わせについて、枝刈りが発生しているか否かを判定するフラグを格納するエントリが設けられている。なお、本実施形態では、枝刈りが発生した場合のフラグを「１」として、枝刈りが発生しなかった場合のフラグを「０」とする。また、枝刈り条件節リスト７００においては、それぞれの条件項目が同じ数のカテゴリに分割されるとは限らないため、カテゴリ番号の何番までフラグが格納されているかは、条件項目によって異なる。
【００６６】
本実施形態における枝刈りの手順の概要は以下のとおりである。本実施形態のデータ分析システムは、レイヤｎの探索においてルールの評価を開始する前に、枝刈り条件節リスト７００のフラグを「枝刈りが発生した」ことを意味する「１」で初期化しておく。特徴ルールを評価する際には、評価対象とするルールの子孫ルールの評価値の最大値を推定し、そのルールにおける枝刈りの有無を判定し、枝刈りが発生しなかった場合、枝刈り条件節リストの、そのルールに含まれるそれぞれの条件節に対応するフラグを「枝刈りが発生していない」ことを意味する「０」で更新する。
【００６７】
このようにしてレイヤｎにおける枝刈り条件節リストを作成し、レイヤｎ＋1の探索の際にはこの枝刈り条件節リストに基づいて枝刈りを行う。
【００６８】
データ分析システムは、レイヤｎ＋1において枝刈りの判定は以下のようにして行う。評価対象のルールが、レイヤｎで作成した枝刈り条件節リストで「枝刈りが発生した」となっている条件節を含む場合、そのルールの探索は行わない。以上が本実施形態で採用する特徴ルール生成の概要である。
【００６９】
そして、本実施形態では、特徴ルール生成を複数のスレーブ１０９を用いて実行する。その手法として、上記の探索木（図６）を複数の部分木に分割し、各スレーブ１０９が分割された木について特徴ルールの探索を行う、という方法を採用する。
【００７０】
続いて、本実施形態における探索木の分割処理の概要を説明する。探索木から部分木に分割する方法の一例を、図８を用いて説明する。
【００７１】
図８は、本実施形態のデータ分析システムが行なう探索木を分割する処理の一例を説明するための図である。なお、図８では、図６に示した探索木を分割する場合を例示している。
【００７２】
図示する破線で囲まれたノード群８０１は、深さ１のレイヤに含まれる全てのノードを表している。ノード群８０１に含まれるノードを、同じ条件項目を持つノードを一つのグループとして、より小さなノード群に分けると、ノード群８０２〜８０４となる。同様に深さ２のレイヤに含まれるノード群も、深さ１のレイヤで同じグループになったノードの子ノードを一つのグループとしてノード群に分割する。以下深さ２以上のレイヤに含まれるノードについても同様に分割する。このようにして分割されたそれぞれのノード群を、探索木を探索する際のジョブと呼ぶことにする。
【００７３】
続いて、本実施形態において、複数台のスレーブ１０９で特徴ルール生成を行うアルゴリズムの概要について図９を用いて説明する。
【００７４】
図９は、本実施形態のデータ分析システムが行なう特徴ルール生成処理のアルゴリズムの概要を示すフローチャートである。
【００７５】
最初にマスタ１０１は、ジョブ生成処理を行なう（Ｓ９０１）。ジョブ生成処理とは、分析者が入力するパラメータを受付けて、受付けたパラメータを用いてジョブを生成する処理である。具体的には、マスタ１０１は、分析者が入力するパラメータの入力を受付ける。分析者が入力するパラメータとは、分析者により選択された条件項目、その条件項目をカテゴリ化した情報、探索を行う最大条件節の数、特徴ルール生成の結果として採用するルール数の上限Ｒ＿ｍａｘの値を含むデータのことをいう。マスタ１０１は、受付けたパラメータを用いて、探索木を作成する。そして、マスタ１０１は、探索木を分割して、ジョブを生成する（Ｓ９０１）。なお、第１レイヤを分析対象のレイヤとする。
【００７６】
また、マスタ１０１は、本ステップにおいて枝刈り条件節リスト７００（図７参照）を準備する。これは前のレイヤにおける枝刈り判定結果を保持するリストである。但し、第１レイヤの探索を行う際には、前のレイヤの結果は存在しない。そのため、マスタ１０１は、条件節リスト７００の各エントリの全ての値を「枝刈りが発生していない」ことを意味する「０」に初期化する。また、マスタ１０１は、ここで採用ルールの途中結果を保持するルールリスト（図示しない）を用意し、これを空に初期化する。
【００７７】
続いて、マスタ１０１は、データ・パラメータ配信処理を行い（Ｓ９０２）、Ｓ９０３の処理に進む。データ・パラメータ配信処理とは、スレーブ１０９に分析対象データと分析に使用するパラメータを送信する処理である。
【００７８】
Ｓ９０３において、マスタ１０１は、途中結果配信処理を行なう。途中結果配信処理とは、前のレイヤまでのルール生成の途中結果であるルールリストをスレーブに送信する処理である。ただし、分析対象レイヤが１の場合は、前のレイヤまでのルール生成結果は存在しないため、ルール生成の途中結果に関しては何も送信しない。また、マスタ１０１は、枝刈り条件節リストをスレーブ１０９に送信する。その後、マスタ１０１は、後述するスレーブ１０９からのジョブ要求を受付けるまで待機する。
【００７９】
一方、スレーブ１０９は、マスタ１０１が送信したルールリストを受信して、スレーブ１０９内部で保持する。また、スレーブ１０９では、枝刈り条件節リストＡおよび枝刈り条件節リストＢの２つのリストを用意する。リストＡは、前のレイヤの枝刈り判定結果を保持するものであり、マスタ１０１から送信された枝刈り条件節リストの内容をコピーしたものである。リストＢは、分析対象となっているレイヤにおいて、枝刈り有無の判定結果を書き込んでいくものであり、その値全てを「枝刈りが発生した」を意味する「１」で初期化する。スレーブ１０９は、上記の処理を行なった後、ジョブ要求処理を行う（Ｓ９０４）。具体的には、各スレーブ１０９は、マスタ１０１に、現在、処理の対象となっているレイヤに含まれるジョブを要求する。
【００８０】
マスタ１０１は、スレーブ１０９からのジョブ要求を受付ける。マスタ１０１は、現在処理中のレイヤに含まれるジョブの状態をチェックし、まだスレーブ１０９に割り当てられていないジョブがある場合、Ｓ９０６の処理に進む。一方、マスタ１０１は、現在処理中のレイヤの中にスレーブ１０９に割り当てられていないジョブがない場合、分析結果の送信を要求する信号をスレーブ１０９に送信して（図１５のＳ１５０６で説明する）、Ｓ９０８の処理に進む（Ｓ９０５）。
【００８１】
Ｓ９０６では、マスタ１０１は、ジョブ要求を行ったスレーブ１０９に対して、まだ割り当ての行われていないジョブの一つを割り当てる。
【００８２】
スレーブ１０９は、Ｓ９０６においてマスタ１０１からジョブを割り当てられた場合、その割り当てられたジョブについてルール生成を実行する（Ｓ９０７）。具体的には、スレーブ１０９は、ジョブに含まれるルールのそれぞれを評価対象として、以下の処理を行う。
【００８３】
ルール生成処理では、スレーブ１０９は、枝刈り条件節リストＡを参照し、評価対象のルールの親ルールで枝刈りが発生しているかどうかをチェックし、発生していなければ、ルールの評価を行う。
【００８４】
スレーブ１０９は、ルールの評価を行う場合、そのルールの評価値を計算し、そのルールの採用、或いは不採用を決定する。採用の判定は、「このルールの評価値がこのスレーブで保持しているルールの評価値の最小値よりも大きいこと（要件１）」、および、「途中結果のルールリストを参照し、このルールが冗長ルールには当らないこと（要件２）」の２つの要件をチェックし、要件１および２の両者とも真であればこのルールを採用する。この場合、スレーブ１０９で保持しているルールリストにこのルールを加え、リストに含まれるルールの数がＲ＿ｍａｘ個を越える場合は、その評価値の上位Ｒ＿ｍａｘ個を新たなルールリストとする。
【００８５】
また、スレーブ１０９は、ルールの評価を行う場合、さらにそのルールの子孫ルールの枝刈り判定を行い、枝刈り条件節リストＢを更新する。このルールにおいて枝刈りが発生していない場合、リストＢのこのルールに含まれる条件節に対応するフラグを「枝刈りが発生していない」ことを意味する「０」で上書きする。
【００８６】
スレーブ１０９は、Ｓ９０７において、１つのジョブの処理が終了した場合、Ｓ９０４の処理に戻る。
【００８７】
続いて、Ｓ９０５において、マスタ１０１が現在処理中のレイヤの中にスレーブ１０９に割り当てられていないジョブがないと判断した場合に進むＳ９０８の処理を説明する。
【００８８】
Ｓ９０８において、各スレーブ１０９は、処理中のレイヤに含まれるジョブの処理が全て終了した後、ルールリストと枝刈り条件節リストＢをマスタ１０１に送信する。
【００８９】
マスタ１０１では、自身が保持する採用ルールリストにスレーブから送信されたルールリストの特徴ルールを加え、その中から評価値の上位Ｒ＿ｍａｘ個のルールを新たな採用ルールリストとして保持する。また、マスタ１０１は、それぞれのスレーブ１０９から送信された枝刈り条件節リストＢをマージし、新たな枝刈り条件節リストとする。このマージ処理は、以下のように行う。
【００９０】
スレーブ１０９から送られてきた全ての枝刈り条件節リストＢにおいて値が「１(枝刈りが発生した)」となっている条件節については、マスタの枝刈り条件節リストの対応する値を「１」とし、それ以外の条件節ではその値を「０(枝刈りが発生していない)」とする。
【００９１】
続いて、マスタ１０１は、現在分析中のレイヤがユーザの指定した最大条件節数より小さい場合、次のレイヤを処理するため、分析対象レイヤの条件節数を１増やして、Ｓ９０３の処理に戻る。一方、マスタ１０１は、現在分析中のレイヤがユーザの指定した最大条件節数より大きい場合、Ｓ９１０に進む。
【００９２】
Ｓ９１０では、マスタ１０１は、マスタ１０１内のルールリストに蓄積されている特徴ルールをデータ分析結果として出力して、ルール生成を終了する。
【００９３】
続いて、本実施形態のスレーブ１０９が行なう幅優先探索において、１つのジョブに含まれる特徴ルールを評価する手順を、図１０を用いて説明する。
【００９４】
図１０は、本実施形態のスレーブが行なう１つのジョブに含まれるルールを探索する処理を説明するためのフローチャートである。以下の各処理ステップは、スレーブ１０９がマスタ１０１からジョブを割り当てられた場合に実行する処理である。なお、以下の説明では、現在探索の対象となっているレイヤをｎとする。
【００９５】
最初に、スレーブ１０９は、与えられたジョブにおける、分析開始ノードの親ノードを処理対象のノード(以下カレントルールと呼ぶ)に特定して（Ｓ１００１）、Ｓ１０１２の処理に進む。
【００９６】
Ｓ１０１２では、スレーブ１０９は、現在の分析対象レイヤが第１レイヤか否かをチェックする。そして、スレーブ１０９は、現在の分析対象レイヤが第１レイヤの場合にＳ１００９の処理に進み、現在の分析対象レイヤが第１レイヤではない場合にＳ１００２の処理に進む。
【００９７】
Ｓ１００２では、スレーブ１０９は、Ｓ１００１で特定したカレントルールが「カレントルールの階層<ｎであること」、「カレントルールには子ルールが存在していること」、および「カレントルールで枝刈りは発生していないこと」の３つの条件を全て満たすか否かを判断する。スレーブ１０９は、上記の３つの条件を全て満たすと判断した場合にＳ１００６に進み、それ以外の場合（すなわち、上記の３つの条件の１つでも満たさない場合）、Ｓ１０１３の処理に進む。
【００９８】
Ｓ１０１３では、スレーブ１０９は、「カレントルールにおいて枝刈りが発生していること」、および「分析終了ノードがカレントルールの子孫ルールに含まれること」の２つの条件を全て満たすか否かを判断する。そして、スレーブ１０９は、上記の２つの条件を全て満たすと判断した場合、すなわち「カレントルールにおいて枝刈りが発生していて、かつ分析終了ノードがカレントルールの子孫ルールに含まれる」と判断した場合に処理を終了する。一方、スレーブ１０９は、上記の２つの条件を満たさないと判断した場合、すなわち、上記の２つの条件の１つでも満たさないものがある場合、Ｓ１００３の処理に進む。
【００９９】
Ｓ１００３では、スレーブ１０９は、「カレントルールの次の兄弟ルールが存在するか否か」を判断する。そして、スレーブ１０９は、「カレントルールの次の兄弟ルールが存在する」と判断した場合にＳ１００７の処理に進む。一方、スレーブ１０９は、「カレントルールの次の兄弟ルールが存在しない」と判断した場合にＳ１００４の処理に進む。ここで次の兄弟ルールの「次」とは、ルール間に定めた順序関係によって決定する。
【０１００】
Ｓ１００４では、スレーブ１０９は、「カレントルールの親ルールはルートノードではあるか否か」を判断する。そして、スレーブ１０９は、「カレントルールの親ルールはルートノードではないと」判断した場合、Ｓ１００５の処理に進む。一方、スレーブ１０９は、「カレントルールの親ルールはルートノードである」判断した場合、処理を終了する。
【０１０１】
Ｓ１００５では、スレーブ１０９は、カレントルールの親ルールを新しいカレントルールとして、上述したＳ１００３の処理に戻る。
【０１０２】
続いて、Ｓ１００２において、３つの条件を全て満たすと判断した場合に進むＳ１００６の処理を説明する。Ｓ１００６では、スレーブ１０９は、カレントルールの子ルールのうち、ルール間に定めた順序関係において最初のルールをカレントルールに設定する。ただし、子ルールの中に、分析開始ノードの親ノードがある場合はこのルールをカレントルールに設定する。スレーブ１０９は、この処理の後、Ｓ１００８の処理に移る。
【０１０３】
続いて、Ｓ１００３において、「カレントルールの次の兄弟ルールが存在する」と判断した場合に進むＳ１００７の処理を説明する。Ｓ１００７では、スレーブ１０９は、予めルール間に定めた順序関係において、カレントルールの次の兄弟ルールをカレントルールに特定して、Ｓ１００８の処理に進む。
【０１０４】
Ｓ１００８では、スレーブ１０９は、カレントルールが属しているレイヤの番号をチェックし、それが現在探索対象のレイヤであれば、Ｓ１００９の処理に進み、そうでなければＳ１００２の処理に戻る。
【０１０５】
Ｓ１００９では、スレーブ１０９は、カレントルールの採用判定処理を行い、Ｓ１０１０の処理に進む。なお、この採用判定処理は、後述する図１７に示すＳ１７０６の分析実行処理の説明において、詳細に述べる。
【０１０６】
Ｓ１０１０では、スレーブ１０９は、カレントルールにおいて枝刈りの判定を行い、上述した図７に示した枝刈り条件節リストを更新して、Ｓ１０１１の処理に進む。
【０１０７】
Ｓ１０１１では、スレーブ１０９は、カレントルールが分析終了ノードか否かをチェックし、分析終了ノードであれば処理を終了し、そうでなければＳ１００２の処理に戻る。
【０１０８】
続いて、本実施形態のデータ分析システムが行なう特徴ルール生成処理について、図１１〜図１９を用いて詳細に説明する。
【０１０９】
図１１は、本実施形態のマスタが行なう特徴ルール生成処理を説明するためのフローチャートである。
【０１１０】
マスタ１０１は、図示する各処理ステップを行なうために、分析処理を行うスレーブ１０９についての情報を管理するテーブル（以下、「スレーブ管理テーブル１２００」という）を保持している。スレーブ管理テーブル１２００は、マスタ１０１が有する処理装置１０２のメモリ１０３の所定の領域に格納されるものとする。ここで、スレーブ管理テーブル１２００の一例を図１２に示す。
【０１１１】
図１２は、本実施形態のマスタが保持するスレーブ管理テーブルの一例を模擬的に示した図である。スレーブ管理テーブル１２００は、少なくとも、それぞれのスレーブを一意に識別するためのＩＤと、そのＩＤにより識別されるスレーブ１０９と通信路を用いて通信する際に必要な情報とが含まれるように構成される。「通信する際に必要な情報」は、例えばＴＣＰ／ＩＰを用いて通信を行う場合には、スレーブのＩＰアドレスおよびポート番号である。図示するスレーブ管理テーブル１２００は、ＴＣＰ／ＩＰを用いて通信を行う場合を例にしている。そのため、スレーブ管理テーブル１２００は、スレーブを一意に識別するためのＩＤを格納するためのエントリ１２０１と、エントリ１２０１に格納されたＩＤに対応付けて、そのＩＤにより識別されるスレーブ１０９のＩＰアドレスおよびポート番号を格納するためのエントリ１２０２〜１２０３とを有する。
【０１１２】
図１１に戻り、説明を続ける。最初に、マスタ１０１は、パラメータ入力受付処理を実行する（Ｓ１１０１）。具体的には、分析者が入出力装置１０５を用いてデータ記憶装置１０８に格納されている分析対象データのファイル名を指定する情報をマスタ１０１に入力する。マスタ１０１は、入力されたファイル名を指定する情報を受付けて、そのファイル名のファイルをデータ記憶装置１０８からメモリ１０３に読み込む。分析者は、さらに、ルール生成に用いる条件項目と結論部、条件項目のカテゴリ化に関する情報、ルール生成パラメータ、分析に参加するスレーブ数の想定最大値を入出力装置１０５を用いてマスタ１０１に入力する。これらの情報はメモリ１０３の所定の領域に格納される。
【０１１３】
分析対象データとは、特徴ルールの生成を行う対象データであり、例えば、表形式のファイルや、データベース内のデータなどの形式でデータ記憶装置１０８に格納されている。なお、分析対象データをデータ記憶装置１０８に格納する代わりに、記憶装置１０７に格納しておいても良い。この場合、メモリ１０３へのデータの読み込みは記憶装置１０７から行われる。
【０１１４】
また、分析対象データのカテゴリ化に関する情報は、分析対象データに含まれる各属性項目をカテゴリ化するための情報である。この情報には、それぞれの属性項目のカテゴリ数、属性項目のとる値をカテゴリに変換するための境界値、それぞれのカテゴリに含まれるデータのレコード数が含まれている。カテゴリのデータは、図５で示したようにカテゴリ番号に対応付けられている。
【０１１５】
ルール生成に用いる条件項目と結論部は、条件部に現れる属性項目の候補となる項目の組み合わせと、結論部となる属性項目とカテゴリの組である。条件項目と結論部に関する情報は、ルール生成で用いる条件項目と結論項目、および結論部として用いる結論部のカテゴリの情報が含まれる。条件項目は図４で示したとおり、項目番号と対応付ける。これらはマスタ１０１の内部に保持される。
【０１１６】
ルール生成パラメータには、発見する特徴ルールの個数Ｒ＿ｍａｘ、最大条件節数Ｃ＿ｍａｘが含まれる。また、スレーブ数の想定最大値には分析に用いるスレーブの数より大きい値を指定する。Ｓ１１０１の処理は、これらの情報の入力後に終了して、Ｓ１１０２の処理に移行する。
【０１１７】
Ｓ１１０２では、マスタ１０１は、入出力装置１０５より分析実行開始の指示が入力されたかどうかをチェックする。そして、マスタ１０１は、分析実行開始の指示が入力されていた場合、現在分析実行中であることを表すフラグをメモリ１０３の所定領域に格納してＳ１１０５に進む。そうでない場合、すなわち、分析実行開始の指示が入力されていない場合、マスタ１０１は、Ｓ１１０３の処理に進む。
【０１１８】
Ｓ１１０３では、マスタ１０１は、スレーブから分析処理への参加もしくは撤退を通知する信号を受信していないかどうかをチェックする。そして、マスタ１０１は、スレーブ１０９からの「分析処理への参加信号」を受信した場合にＳ１１０７の処理に進み、スレーブ１０９からの「分析処理からの撤退信号」を受信した場合にＳ１１０８の処理に進む。また、マスタ１０１は、「分析処理への参加信号」および「分析処理からの撤退信号」のいずれの信号も受信しなかった場合、Ｓ１１０４の処理に進む。
【０１１９】
Ｓ１１０４では、マスタ１０１は、スレーブ１０９からの「ルール生成のコマンド」を受信したかどうかをチェックする。そして、マスタ１０１は、「ルール生成のコマンド」を受信していた場合、後述するコマンド判定処理（図１５のＳ１５０１）に進む。一方、マスタ１０１は、「ルール生成のコマンド」を受信しない場合、Ｓ１１０２の処理に戻る。
【０１２０】
続いて、Ｓ１１０２において、分析実行開始の指示が入力されていた場合に進むＳ１１０５の処理を説明する。Ｓ１１０５では、マスタ１０１は、ルール生成を行うための準備として、「分析対象データをスレーブに送信する準備」、「分析結果のルールを格納する準備」、「探索木のジョブへの分割」、「枝刈り条件節リストの初期化」、および「分析の初期条件の設定」を行う。以下、「分析対象データをスレーブに送信する準備」、「分析結果のルールを格納する準備」、「探索木のジョブへの分割」、「枝刈り条件節リストの初期化」、および「分析の初期条件の設定」を順番に説明する。
【０１２１】
最初に「分析対象データをスレーブに送信する準備」について説明する。「分析対象データをスレーブに送信する準備」とは、マスタ１０１がメモリ１０３内に格納した分析対象データの、条件項目、結論部の項目に対応する各属性項目のデータをカテゴリ化する処理である。具体的には、メモリ１０３内に格納された分析対象データについて、分析に使用するレコードにレコード番号と呼ばれるインデックス番号を振り、それぞれのレコードについてカテゴリ化後の値をカテゴリ番号で表した「カテゴリ化した分析対象データ」を作成する。「カテゴリ化した分析対象データ」を表形式で記述した例を図１３に示す。
【０１２２】
図1３は、本実施形態のマスタ１０１が分析対象データをカテゴリ化したあとに格納するテーブルの一例を示す図である。図示するように、分析対象データをカテゴリ化したあとに格納するテーブルでは、分析に使用するレコードを識別するレコード番号１３０１、および条件項目番号１３０２の両者にカテゴリ番号が対応付けられている。マスタ１０１は、スレーブ１０９に分析対象データを送信する際、図１３のように記述されたデータを送信する。
【０１２３】
図１１に戻り説明を続ける。「分析結果のルールを格納する準備」では、マスタ１０１は、メモリ１０３内に分析結果の特徴ルールを格納するのに十分な領域を確保する。この領域には分析の途中結果として、分析中のある段階において、スレーブ１０９から受け取った上位Ｒ＿ｍａx個のルールが格納される。
【０１２４】
また、マスタ１０１は、「探索木のジョブへの分割」を上述の図８で示した方法を用いて行う。そして、分割した各ジョブに関する情報は、マスタ１０１内のジョブ管理テーブルで管理する。ここで、ジョブ管理テーブルの一例を図１４に示す。
【０１２５】
図１４は、本実施形態のマスタにおいてジョブを管理するテーブルの一例を模擬的に示した図である。ジョブ管理テーブル１４００は、少なくとも、それぞれのジョブを一意に識別する「ジョブＩＤ」を格納するための項目１４０１と、項目１４０１に格納された「ジョブＩＤ」により識別されるジョブの「レイヤ番号」を格納するための項目１４０２と、そのジョブの「分析開始ノード」を格納するための項目１４０３と、そのジョブの「分析終了ノード」を格納するための項目１４０４と、そのジョブの分析を担当する「担当スレーブのＩＤ」を格納する項目１４０５と、分析の状態(例えば「分析中」や「分析完了」など)に関する情報を示すジョブ状態フラグを格納するための項目と、を有する。このジョブ管理テーブル１４００は、メモリ１０３の所定の領域に格納されている。
【０１２６】
また、図８の説明で示した分割方法では、ルール同士の順序関係に基づいて、ジョブの分析開始ノードと分析終了ノードを特定することにより、各ジョブに含まれるノードを一意に決定することができる。例えば、図８に示すジョブ８０２において、条件項目ａ（１）が５つのカテゴリに分割されているとする。この場合、分析開始ノードとして条件部ａ（１）＝ｖ（１，１）、分析終了ノードとしてａ（１）＝ｖ（１，５）を指定することにより、ジョブ８０２で分析するノードを一意に決定することができる。ノードは、マスタ１０１、スレーブ１０９の中では、条件項目とカテゴリのインデックス番号の組として表現される。例えば、ジョブ８０２は、開始ノードを（１，１)、終了ノードを（１，５）と表すことができる。条件節が複数ある場合、一つのノードは、複数の条件項目とカテゴリのインデックス番号の組で表現される。
【０１２７】
これを踏まえて、ステップ１００５における探索木のジョブへの分割は、以下の処理を行うことによって実現される。レイヤの深さを表す「変数Ｉ」の初期値を１、条件項目の番号を表す変数ｍの初期値を１として以下の処理を繰り返す。
【０１２８】
具体的には、あるジョブの分析開始ノードに対応する条件節「X_s」を「C_s(1) and … and C_s(I)」とし、分析終了ノードに対応する条件節「X_e」を「C_e(1) and … and C_e(I)」と書くこととする。この場合、「C_s(1)」は、「a(m) = v(m, 1)である。「C_s(i)(2≦i≦I)」は、「a(m+i-1 ) = v(m+i-1, 1)」である。「C_e(1)」は、「a(m) = v(m, N(m))」である。「C_e(i)(2≦i≦I)」は、「a(M-I+i) = v(M-I+i, N(M-I+i))」である。ここでMは条件項目の数、N(m)は条件項目mのカテゴリの数である。この方法によって、分析開始ノードと分析終了ノードの条件項目とカテゴリの組を決定し、この分析開始ノード、分析終了ノード、ジョブを一意に識別するジョブＩＤ、そのジョブが含まれるレイヤをジョブ管理テーブルに格納する。ここで、ジョブＩＤは、例えばジョブが登録される順に通し番号付与する、などの方法で与える。また、このジョブの担当スレーブを「未割り当て」とする。
【０１２９】
マスタ１０１は、この処理を変数mを1づつ増加させながらmがM-I+1に等しくなるまで行う。マスタ１０１は、mがM-I+1に等しくなったら、mを1に戻してIを1増加させ、同様の処理をIが最大条件節数C_maxに等しくなるまで行う。
【０１３０】
次に、マスタ１０１は、分析に参加するスレーブの数の想定最大値よりも各レイヤに含まれるジョブの数が少ない場合、一番多くのルールを含むジョブを２分割する処理を繰り返す。この処理によって、レイヤに含まれるジョブの数がスレーブの数の想定最大値よりも大きくなるようにする。この処理は全てのレイヤについて同様に行う。
【０１３１】
なお、上記の処理の中で、ジョブを２分割する処理は、以下のようにして実現する。いま、ジョブＪをジョブＪ（１）、ジョブＪ（２）に分割することとする。この場合、マスタ１０１は、各条件項目のカテゴリ分割数よりジョブに含まれるルールの数を算出し、これを２で割る。このカテゴリ分割数の情報はメモリ１０３に格納されている。なお、端数を切り捨て、この整数をＮとする。まず、マスタ１０１は、Ｊの開始ノードをＪ（１）の開始ノードとする。Ｊ（１）の開始ノードからノードの順序関係に従ってノードを数え、Ｎ番目のノードをＪ（１）の終了ノードとする。また、Ｊ（１）の終了ノードの次のノードをＪ（２）の開始ノードとし、Ｊの終了ノードをＪ（２）の終了ノードとする。Ｊ（１）、Ｊ（２）のジョブ管理テーブルへの格納は、ジョブＪの情報をＪ(１)の情報で上書きし、Ｊ（２）を管理テーブルに追加することで行う。なお、マスタ１０１は、このジョブを分割する処理を行った後、ジョブを、ジョブの含むルール数の大きい順に並べなおして、ジョブ番号を改めて振りなおしても良い。
【０１３２】
次に、Ｓ１１０５における「枝刈り条件節リスト初期化」の処理を説明する。マスタ１０１は、以下の手順により「枝刈り条件節リストの初期化」を行うマスタ１０１では、２つの枝刈りリストを保持する。すなわち、マスタ１０１は、メモリ１０３に記憶領域を確保して、２つの枝刈りリストを保持する。１つ目のリストは、分析対象レイヤの枝刈り条件節リストであり、これはリストの各値を「枝刈りが発生していない」ことを意味する「０」に設定することで初期化する。もう１つのリストは次のレイヤの枝刈り条件節リストであり、これはリストの各値を「枝刈りが発生している」ことを意味する「１」で初期化する。
【０１３３】
続いて、Ｓ１１０５における「分析の初期条件を設定する処理」を説明する。「分析の初期条件を設定する処理」では、マスタ１０１は、割り当て可能レイヤ番号を格納するパラメータを用意し、レイヤ番号1を割り当て可能レイヤ番号に設定する。また、マスタ１０１は、採用されるルールの最小評価値を格納するパラメータを用意し、「０」に初期化する。マスタ１０１は、これらのパラメータを格納する領域をメモリ１０３に確保する。マスタ１０１は、Ｓ１１０５において、以上の処理を行った後Ｓ１００６の処理に進む。
【０１３４】
Ｓ１１０６では、マスタ１０１は、分析実行通知処理を行う。具体的には、マスタ１０１は、スレーブ管理テーブル１２００（図１２参照）に登録されている、全てのスレーブに対して、通信路１１０を介して分析実行通知信号を送信する。マスタ１０１は、分析実行通知処理の完了後、Ｓ１１０２の処理に戻る。
【０１３５】
続いて、Ｓ１１０３において、スレーブ１０９からの「分析処理への参加信号」を受信した場合に進むＳ１１０７のスレーブ追加処理を説明する。
【０１３６】
Ｓ１１０７では、マスタ１０１は、Ｓ１１０３で受け取った信号の発信元であるスレーブ１０９について、このスレーブを識別するＩＤ番号を与え、スレーブのＩＰアドレスとスレーブが通信に用いるポート番号を取得し、これらの値をスレーブ管理テーブル１２００に格納する。ＩＤ番号は、例えば信号を受け取ったスレーブ１０９に、信号を受け取った順に通し番号を付与するなどの方法で与える。この処理の完了後、Ｓ１１０９の処理に進む。
【０１３７】
Ｓ１１０９では、マスタ１０１は、この処理を実行する時点でルール生成を実行中であるかどうかをチェックし、実行中であればＳ１１１０の分析実行通知処理に分岐し、そうでなければＳ１１０２に分岐する。
【０１３８】
Ｓ１１１０では、マスタ１０１は、この処理を実行する前にＳ１１０７で追加したスレーブに対して、通信路１１０を介して分析実行通知信号を送信し、Ｓ１１０２の処理に戻る。
【０１３９】
続いて、Ｓ１１０３において、スレーブ１０９からの「分析処理からの撤退信号」を受信した場合に進むＳ１１０８のスレーブ削除処理を説明する。
【０１４０】
Ｓ１１０８では、Ｓ１１０３で受け取った中断要求の信号の発信元であるスレーブ１０９にルール生成の途中経過と枝刈り条件節リストを送信する信号を送信する。また、マスタ１０１は、スレーブ１０９からの途中結果と枝刈り条件節リストを受信した後、そのスレーブ１０９を管理テーブルから削除する。スレーブ１０９からの途中経過と枝刈り条件節リストの送信については、後述する図１７に示すＳ１７０７およびＳ１７０９にて詳細を説明する。
【０１４１】
次に、マスタ１０１がスレーブ１０９からルール生成コマンドを受け取った場合に行なう処理について図１５を用いて説明する。
【０１４２】
図１５は、本実施形態のマスタがスレーブからルール生成に関するコマンドを受信した場合に行なう処理を説明するためのフローチャートである。マスタ１０１は、スレーブ１０９が送信するルール生成コマンドを受信した場合に図示する各処理ステップを開始する。
【０１４３】
最初に、マスタ１０１は、分析中のスレーブから受信した信号の内容をチェックし、その種類によって対応する処理を決定して（Ｓ１５０１）、対応する処理ステップに移行する。スレーブ１０９からの信号の種類には、「データ・パラメータ要求信号」、「途中経過要求信号」、「ジョブ要求信号」、「ジョブ分析完了通知信号」、「結果送信信号」、および「枝刈りリスト送信信号」がある。
【０１４４】
まず、Ｓ１５０１で受信したスレーブ１０９からの信号が「データ・パラメータ要求信号」である場合を説明する。マスタ１０１は、スレーブ１０９からの通信内容が「データ・パラメータ要求信号」の場合は、Ｓ１５０２に進む。Ｓ１５０２では、マスタ１０１は、その信号の発信元であるスレーブ１０９に分析対象データと分析パラメータを送信して、再び図１１のＳ１１０２に戻る。なお、分析対象データの送信処理とは、カテゴリ化を行った後のデータをそのカテゴリ番号の列に変換して、その変換したデータ（図１３参照）をスレーブ１０９に送信する処理である。また、この処理で送信するパラメータには、発見すべき特徴ルール数の上限Ｒ＿ｍａｘ、結論項目となる属性項目のインデックス番号とそのカテゴリのインデックス番号、条件項目のインデックス番号、最大条件節数Ｃ＿ｍａｘが含まれる。
【０１４５】
続いて、Ｓ１５０１で受信したスレーブ１０９からの信号が「途中経過要求信号」である場合を説明する。この場合、マスタ１０１は、Ｓ１５０２の途中経過送信処理に進む。Ｓ１５０２の途中経過送信処理では、マスタ１０１は、メモリ１０３内に格納している分析結果のルール群と、分析対象レイヤの枝刈り条件節リストをスレーブ１０９に送信する。そして、マスタ１０１は、Ｓ１５０２の処理が終了すると、再び図１１のＳ１１０２に戻る。
【０１４６】
次に、Ｓ１５０１で受信したスレーブ１０９からの信号が「ジョブ要求信号」である場合を説明する。この場合、マスタ１０１は、Ｓ１５０４の処理に進む。Ｓ１５０４では、マスタ１０１は、割り当て可能なジョブが在るか否かをチェックし、割り当て可能なジョブが在る場合は、Ｓ１５０５に進みジョブ割り当て処理を実行する。一方、Ｓ１５０４において、割り当て可能なジョブが無い場合には、マスタ１０１は、Ｓ１５０６の処理に進み、現在のレイヤにおけるジョブ割り当ての終了処理を実行する。
【０１４７】
ここで、割り当て可能なジョブのチェックは以下のようにして実行される。具体的には、マスタ１０１は、ジョブ管理テーブル１４００（図１４参照）を参照し、割り当て可能レイヤ番号と等しいレイヤ番号を持つジョブのうち、「担当スレーブ」を格納する項目１４０５に「未割り当て」が格納されているジョブが存在するかどうかをチェックする。そのようなジョブが存在すれば割り当て可能なジョブがあると判定し、なければ割り当て可能なジョブが無いと判定する。Ｓ１５０５のジョブ割り当て処理においては、担当スレーブの項目１４０５が「未割り当て」ジョブの中の一つをジョブ要求信号の発信元であるスレーブに割り当て、ジョブ管理テーブル１４００における該当するジョブのジョブ状態フラグを「分析中」の状態とし、担当スレーブの項目にこのスレーブのＩＤを格納し、図１１の分岐１１０２に戻る。
【０１４８】
この割り当てにおいては、マスタ１０１からスレーブ１０９に、ジョブ管理テーブル１４００に格納されている、分析開始ノード、分析終了ノードの値、マスタ１０１に格納している最小評価値の情報が送信される。
【０１４９】
Ｓ１５０６の現レイヤにおけるジョブ割り当ての終了処理では、マスタ１０１は、スレーブ１０９に現レイヤの分析結果の送信を要求する信号を送信し、図１１のＳ１１０２に戻る。
【０１５０】
次に、Ｓ１５０１で受信したスレーブ１０９からの信号が「ジョブ分析完了通知」である場合を説明する。この場合、マスタ１０１は、Ｓ１５０７のパラメータ更新処理に進む。この信号には、そのスレーブが保持している特徴ルールの最小評価値が含まれている。Ｓ１５０７のパラメータ更新処理では、マスタ１０１は、ジョブ管理テーブル１４００内におけるこのスレーブが分析中であったジョブのジョブ状態フラグを「分析完了」とする。また、マスタ１０１は、スレーブ１０９から受け取った最小評価値に関するパラメータを参照し、この値をマスタで格納してある最小評価値の値と比較し、両者のうち値の大きな方を新しい値として、マスタの最小評価値を更新する。マスタ１０１は、Ｓ１５０７の完了後、図１１のＳ１１０２に戻る。
【０１５１】
続いて、Ｓ１５０１で受信したスレーブ１０９からの信号が「結果送信」である場合を説明する。この場合、マスタ１０１は、Ｓ１５０８の途中結果マージ処理に進む。Ｓ１５０８の途中結果マージ処理では、マスタ１０１は、スレーブ１０９から、そのスレーブ１０９が行った分析の結果を受信する。マスタ１０１は、受信した分析の結果をマスタ１０１内のメモリ１０３に格納している分析結果とマージする。この分析結果のマージ処理は以下のようにして実現される。具体的には、マスタ１０１で格納してある特徴ルールと本ステップでスレーブ１０９から受信した特徴ルールの評価値を参照し、それらのルールの中から評価値が上位のルールＲ＿ｍａｘ個を選択し、メモリ１０３に格納する結果ルールを更新する。
【０１５２】
Ｓ１５０８において、マスタ１０１は、結果ルールを更新した後、ジョブ管理テーブル１４００を更新する処理を行なう。具体的には、マスタ１０１は、ジョブ管理テーブル１４００の担当スレーブの項目を参照し、この項目に格納されているスレーブＩＤが結果を送信してきたスレーブのＩＤと同一であるジョブについて、ジョブ管理テーブルのジョブ状態フラグを「結果受理」とする。マスタは、Ｓ１５０８の処理が完了後、Ｓ１５０９に進む。
【０１５３】
Ｓ１５０９では、マスタ１０１は、ジョブ管理テーブル１４００を参照して、現在分析中のレイヤ番号を持つジョブについて、全てのジョブのジョブ状態フラグが結果受理を示す値になっているかどうかをチェックする。そして、マスタ１０１は、全てのジョブのジョブ状態フラグが結果受理を示す値になっている場合、保持している採用ルールの最小評価値の値をこの段階でマスタ１０１のルールリストに保持されているルールの最小の評価値で更新して、Ｓ１５１０の処理に進む。一方、マスタ１０１は、全てのジョブのジョブ状態フラグが結果受理を示す値になっていない場合、図１１のＳ１１０２に戻る。
【０１５４】
Ｓ１５１０では、マスタ１０１は、接続されている全てのスレーブに枝刈りリスト送信通知を送信し、図１１のＳ１１０２に戻る。
【０１５５】
続いて、Ｓ１５０１で受信したスレーブ１０９からの信号が「枝刈りリスト送信」である場合を説明する。この場合、マスタ１０１は、Ｓ１５１１の枝刈りリストのマージ処理に進む。Ｓ１５１１では、マスタ１０１は、スレーブ１０９から、そのスレーブ１０９が保持している枝刈り条件節リストを受取り、マスタ１０１が保持している次のレイヤの枝刈りリストとマージする。このマージは、スレーブ１０９から送信してきた枝刈りリストの各項目について、項目の値が「枝刈りが発生していない」ことを意味する「０」であれば次のレイヤの枝刈り条件節リストの対応する項目の値を「０」に設定する。
【０１５６】
Ｓ１５１１において、マスタ１０１は、次のレイヤの枝刈りリストとマージ処理した後、ジョブ管理テーブル１４００の担当スレーブの項目を参照し、この項目に格納されているスレーブＩＤが結果を送信してきたスレーブのＩＤと同一であるジョブについて、ジョブ管理テーブル１４００のジョブ状態フラグを「枝刈りリスト受理」とする。マスタ１０１は、Ｓ１５１１の完了後、Ｓ１５１２の処理に進む。
【０１５７】
Ｓ１５１２では、マスタ１０１は、ジョブ管理テーブル１４００を参照して現在分析中のレイヤ番号を持つジョブについて、全てのジョブのジョブ状態フラグが「枝刈りリスト受理」になっているかどうかをチェックし、枝刈りリスト受理になっていればＳ１５１３の処理に進む。一方、マスタ１０１は、全てのジョブのジョブ状態フラグが「枝刈りリスト受理」になっていない場合、図１１のＳ１１０２に戻る。
【０１５８】
Ｓ１５１３では、マスタ１０１は、この段階での分析対象のレイヤ番号と最大条件節数の値を参照し、現在分析中のレイヤ番号が最大条件節数よりも小さければ、Ｓ１５１４の分析続行通知処理に進み、同じならばＳ１５１５の分析終了通知処理に進む。すなわち、本ステップでは、現在分析中のレイヤの次のレイヤが在るか否かを判定し、次のレイヤがあればＳ１５１４に分岐して、次のレイヤがなければＳ１５１５に分岐する処理を行なう。
【０１５９】
Ｓ１５１４では、マスタ１０１は、分析対象とするレイヤ番号を１増やし、スレーブ管理テーブル１４００に登録されている全てのスレーブに分析続行通知を送信し、図１１のＳ１１０２に戻る。
【０１６０】
Ｓ１５１５では、マスタ１０１は、スレーブ管理テーブル１４００に登録されている全てのスレーブ１０９に分析終了の信号を送信し、Ｓ１５１６に移る。Ｓ１５１６では、マスタ１０１は、現在保持している特徴ルールの集合を最終的な結果として入出力装置１０５に出力し、ルール生成の処理を終了する。以上が、第１実施形態のマスタ１０１が行なう処理の詳細である。
【０１６１】
次に、入出力装置１０５に出力される、マスタ１０１の画面の例を図１６に挙げる。
【０１６２】
図１６は、本実施形態のマスタが有する入出力装置に出力される分析結果表示画面の一例を示した図である。
【０１６３】
図示するマスタ画面１６００には、それぞれのスレーブが評価したルールの数と、それらの評価ルールの合計数が表示されている。それぞれのスレーブの評価ルール数は、後述する図１７のＳ１７０８に示す結果送信処理においてスレーブ１０９からマスタ１０１への通信によって通知され、マスタ１０１のメモリ１０３内に格納されている。
【０１６４】
続いて、本実施形態のスレーブ１０９側で行なわれる処理の詳細について説明する。
【０１６５】
図１７は、本実施形態のスレーブが行なう処理を説明するためのフローチャートである。
【０１６６】
さて、最初にスレーブ１０９は、分析実行登録処理を行う（Ｓ１７０１）。具体的には、スレーブ１０８は、マスタ１０１にスレーブ追加の信号を送り、Ｓ１７０２の分析実行初期化処理に移る。
【０１６７】
Ｓ１７０２では、スレーブ１０９は、マスタ１０１からの分析実行通知の信号を待つ。スレーブ１０９は、マスタ１０１が送信した分析実行通知の信号を受信した場合、マスタ１０１にデータ・パラメータ送信要求の信号を送信する。そして、スレーブ１０９は、マスタ１０１が送信した分析対象データおよびルール生成に用いるパラメータを受信する。また、Ｓ１７０２では、さらに、以下の処理を行う。
【０１６８】
具体的には、スレーブ１０９は、分析の途中結果のルール群であるルールリストを格納する領域をスレーブ内部のメモリ１１３に確保し、この領域を空に初期化する。この領域は、Ｒ＿ｍａｘ個のルールを格納するために十分な領域とする。また、スレーブ１０９は、枝刈り条件節リストを格納する領域をメモリ１１３に確保する。これらの領域は、以下、それぞれ枝刈り条件節リストＡ、Ｂと呼ぶことにする。枝刈り条件節リストＡは、前のレイヤまでの枝刈り判定結果を保持する領域であり、枝刈り条件節リストＢは、分析対象となっているレイヤにおいて判定した枝刈り条件節の情報を書き込んでいく領域である。スレーブ１０９は、この処理の完了後、Ｓ１７０３の途中結果要求処理に移る。
【０１６９】
Ｓ１７０３では、スレーブ１０９は、マスタ１０１に途中結果要求の信号を送信する。マスタ１０１は、スレーブ１０９からの途中結果要求の信号を受付けて、自身が保持する途中結果のルールリストおよび枝刈り条件節リストをスレーブ１０９に送信する。そして、スレーブ１０９は、マスタ１０１が送信する途中結果のルールリストおよび枝刈り条件節リストを受信する。スレーブ１０９は、受信した途中結果のルール（特徴ルール）をスレーブ内のルールリストに格納する。また、スレーブ１０９は、受信した枝刈り条件節リストを枝刈り条件節リストＡに格納する。さらに、スレーブ１０９は、枝刈り条件節リストＢのフラグを「枝刈りが発生している」ことを意味する「１」で初期化する。スレーブ１０９は、これらの処理が完了するとＳ１７０４のジョブ要求処理に進む。
【０１７０】
Ｓ１７０４では、スレーブ１０９は、マスタ１０１にジョブ要求の信号を送信して、Ｓ１７０５の処理に進む。Ｓ１７０５では、スレーブ１０９は、Ｓ１７０４のジョブ要求の信号への応答の信号を参照し、新しいジョブの割り当ての信号であればＳ１７０６の分析実行処理に進み、分析結果の送信を要求する信号であればＳ１７０７の途中結果送信処理に進む。
【０１７１】
Ｓ１７０６では、スレーブ１０９は、マスタ１０１から受信した最小評価値をメモリに保持し、割り当てられたジョブのルール探索の処理を図１０に示した手順で行う。具体的には、スレーブ１０９は、Ｓ１７０６において、図１０のＳ１００９で示した採用判定処理と、Ｓ１０１０で示した枝刈りチェック処理と、を行なう。ここで、図１０に示した採用判定処理について図１８を用いて詳細に説明する。
【０１７２】
図１８は、本実施形態のスレーブが行なうカレントルールの採用判定処理を説明するためのフローチャートである。なお、評価対象となっているルールのことをカレントルールと呼ぶことにする。
【０１７３】
カレントルールの採用判定処理では、スレーブ１０９は、最初に、分析対象データのレコードをスキャンしてルールの条件部を満たすレコード数、ルールの結論部を満たすルール数、条件部と結論部を満たすルール数を計数して、カレントルールの評価値を算出して（Ｓ１８０１）、Ｓ１８０２の処理に進む。なおルールの結論部は一回の分析を通して変わらないので、一回計数すれば再度計数する必要はない。
【０１７４】
Ｓ１８０２では、スレーブ１０９は、メモリ１１３に保持した最小評価値を参照し、カレントルールの評価値よりも最小評価値が大きければ、カレントルールを不採用として採用判定処理を終了する。一方、スレーブ１０９は、カレントルールの評価値が最小評価値よりも大きい場合、Ｓ１８０３に進む。
【０１７５】
Ｓ１８０３では、スレーブ１０９は、予め保持する変数「ｉ」に１を代入する処理を行い、Ｓ１８０４に進む。なお、変数「ｉ」とは、スレーブ１０９のルールリストにアクセスするための変数である。
【０１７６】
Ｓ１８０４では、スレーブ１０９は、ルールリストのｉ番目の評価値とカレントルールの評価値を比較し、カレントルールの評価値のほうが大きければカレントルールを採用して、Ｓ１８０８の処理に進む。また、スレーブ１０９は、ｉ番目のルールが存在しない場合も、カレントルールを採用してＳ１８０８の処理に進む。一方、比較の結果、スレーブ１０９は、ルールリストのｉ番目の評価値の方がカレントルールの評価値より大きい場合、Ｓ１８０５の処理に進む。
【０１７７】
Ｓ１８０５では、スレーブ１０９は、カレントルールがルールリストのｉ番目のルールの子ルールであるか否かをチェックし、子ルールであればカレントルールを不採用として採用判定処理を終了する。そうでない場合は、Ｓ１８０６の処理に進む。
【０１７８】
Ｓ１８０６では、スレーブ１０９は、ｉ番目のルールがルールリストの最後のルールか否かをチェックする。具体的には、スレーブ１０９は、ｉ番目のルールがルールリストの最後のルールであり、かつ「ｉ」が出力すべきルールの最大数Ｒ＿ｍａｘより小さいならばＳ１８０７の処理に進む。ルールリストの末尾であり、「ｉ ＝ Ｒ＿ｍａｘ」であれば、カレントルールは不採用として、採用判定の処理を終了する。
【０１７９】
Ｓ１８０７では、スレーブ１０９は、変数「ｉ」に「ｉ＋１」を代入する処理を行い、Ｓ１８０４の処理に戻る。
【０１８０】
続いて、Ｓ１８０４において、カレントルールを採用した場合に進むＳ１８０８の処理を説明する。Ｓ１８０８では、スレーブ１０９は、ルールリストのｉ番目のルールとして、カレントルールをリストに挿入、あるいは追加する処理を行い、Ｓ１８０９に進む。スレーブ１０９は、ルールを挿入した結果、リストのルールがＲ＿ｍａｘ個以上になった場合は、ルールリストの末尾のルールをリストから削除する。
【０１８１】
Ｓ１８０９では、スレーブ１０９は、ルールリストにＲ＿ｍａｘ個のルールが含まれ、かつ、ルールリストの末尾のルールの評価値が、メモリ１１３に保持した最小評価値よりも大きい場合、これを新たな最小評価値として保持し、採用判定処理を終了する。以上が、Ｓ１７０６の内部で行われる、ルールの採用判定処理の詳細である。
【０１８２】
次に、図１０のＳ１０１０の枝刈りチェック処理について図１９を用いてその詳細を説明する。
【０１８３】
図１９は、本実施形態のスレーブが行なう枝刈りチェック処理の詳細を説明するためのフローチャートである。
【０１８４】
最初にスレーブ１０９は、枝刈り基準値推定処理を行なう（Ｓ１９０１）。枝刈り推定処理では、スレーブ１０９は、カレントルールの子孫ルールが取り得る評価値の最大値を推定し、Ｓ１９０２の処理に進む。
【０１８５】
Ｓ１９０２では、スレーブ１０９は、Ｓ１９０１で求めた推定値を、最小評価値と比較する。スレーブ１０９は、比較の結果、推定値が最小評価値よりも小さい場合に「カレントルールにおいて枝刈りが発生した」と判断して、処理を終了する。スレーブ１０９は、推定値が最小評価値以上の場合に「カレントルールにおいて枝刈りが発生していない」と判断して、Ｓ１９０３の処理に進む。
【０１８６】
Ｓ１９０３では、スレーブ１０９は、変数「ｉ」に1を代入して、Ｓ１９０４の処理に進む。なお、「ｉ」は、カレントルールが持つ複数の条件節のうちの一つを指すインデックスとして使用される。
【０１８７】
Ｓ１９０４では、スレーブ１０９は、カレントルールの条件節数と「ｉ」を比較し、「ｉ」の方が大きければ処理を終了する。そうでなければＳ１９０５のリスト更新処理に移る。
【０１８８】
Ｓ１９０５では、スレーブ１０９は、探索条件節リストＢのカレントルールの「ｉ」番目の条件節に対応するフラグを「枝刈りが発生しない」ことを意味する「０」で上書きし、Ｓ１９０６の処理に移る。
【０１８９】
Ｓ１９０６では、スレーブ１０９は、「ｉ」に「ｉ＋１」を代入して、Ｓ１９０４の処理に戻る。以上が図１０のＳ１０１０の枝刈りチェックで行われる処理の詳細である。
【０１９０】
図１７に戻り、説明を続ける。スレーブ１０９は、図１８に示した採用判定処理、および図１９に示した枝刈りチェック処理を終了した後、ステップ１７０８の分析結果送信処理に進む。
【０１９１】
Ｓ１７０８では、スレーブ１０９は、自身のメモリ１１３に格納している最小評価値をマスタに送信し、Ｓ１７０４の処理に戻る。
【０１９２】
続いて、Ｓ１７０５において、マスタ１０１からの信号が分析結果の送信を要求する信号であると判断した場合に進むＳ１７０７の以降の処理を説明する。Ｓ１７０７では、スレーブ１０９は、ルールリストをマスタに送信し、Ｓ１７０９の処理に移る。ここでマスタに送信する特徴ルールの情報は、分析結果の特徴ルールの、条件部に含まれる条件項目とカテゴリの組、およびそれぞれの特徴ルールの評価値を含んでいる。なお、Ｓ１７０７では、スレーブ１０９は、分析対象のレイヤを探索中に、ルールリストに追加されたルールのみを抜き出して、マスタに送信しても良い。
【０１９３】
Ｓ１７０９では、スレーブ１０９は、マスタ１０１から枝刈りリスト送信の信号を受信するのを待機し、この信号を受信すると、マスタ１０１に枝刈り条件節リストＢを送信する。
【０１９４】
次に、スレーブ１０９は、分析の続行に関する信号を受信するまで待機し、マスタ１０１より分析続行通知を受信した場合はＳ１７０３の処理に戻る。一方、スレーブ１０９は、マスタ１０１より分析終了通知を受け取った場合はＳ１７１１の分析終了処理に進む（Ｓ１７１０）。Ｓ１７１１では、スレーブ１０９は、分析で使用したメモリの解放など、分析終了時に必要な処理を行い、処理を終了する。
【０１９５】
なお、図１７のスレーブ１０９の処理においては、入出力装置１０５より分析中断の指示を受け付けるように変更することも可能である。分析中断の指示は、Ｓ１７０４において、スレーブ１０９からマスタ１０１にジョブを要求する前にチェックする。分析中断の指示がある場合、Ｓ１７０７の途中結果送信処理、Ｓ１７０９の枝刈りリスト送信処理、およびＳ１７１１の分析終了処理を行って、マスタ１０１にスレーブ削除の信号を送信して、このスレーブ１０９における処理を終了する。以上が、第1実施形態におけるスレーブ１０９の処理の詳細である。
【０１９６】
次に、スレーブ１０９が入出力装置１１５に出力するスレーブの画面の例を図２０を用いて説明する。
【０１９７】
図２０は、本実施形態のスレーブの入出力装置に出力される分析結果表示画面の一例を示した図である。
【０１９８】
スレーブ画面２０００には、そのスレーブ１０９において評価したルールの数が表示されている。この評価ルール数は、図１０に示したＳ１００９の採用判定が行われるたびにカウントされ、スレーブ１０９のメモリ１１３に格納されている。この評価ルール数は、図１７に示したＳ１７０８の結果送信処理におけるスレーブ１０９からマスタ１０１への通信によってマスタ１０１に通知される。
【０１９９】
以上が本発明における第１実施形態であるが、これは以下のように変更して実施することも可能である。
<第２実施形態>
続いて、本発明の第１実施形態の変形例である第２実施形態について説明する。第２実施形態は、枝刈りの判定を行うタイミングを第１実施形態のものから変更したものである。なお、第２実施形態の説明において、第１実施形態と同様の構成については、同様の符号を用いることとする。また、第２実施形態の説明は、第１実施形態と異なる部分を中心に説明する。
【０２００】
さて、第２実施形態では、上述したマスタ１０１が行なう図１５のＳ１５１０の処理を変更するようにしている。第２実施形態では、マスタ１０１は、上述したＳ１５１０の処理に代えて、「接続されている全てのスレーブに枝刈りリスト送信通知と、マスタで保持している途中結果のルールリストにおける採用ルールの評価値の最小値を送信し、図１１のＳ１１０２に戻る」ようにする。
【０２０１】
また、第２実施形態のスレーブ１０９は、上述した図１７のＳ１７０３の途中結果要求処理を変更する。第２実施形態のスレーブ１０９は、上述したＳ１７０３の処理に加えて、さらに、以下の処理を行な。具体的には、スレーブ１０９は、枝刈り判定値リストを格納する領域をメモリ１１３に確保する。この確保した枝刈り判定値リストは、分析対象レイヤの処理を行う際に、枝刈りの基準値となる評価値を記録する領域である。枝刈り条件節の判定値リストは「０」で初期化する。ここで変形実施形態の枝刈り判定値リストの例を図２１に示す。
【０２０２】
図２１は、本発明の変形実施形態における枝刈り判定値リストの一例を模擬的に示す図である。
【０２０３】
さらに、第２実施形態のスレーブ１０９は、上述したＳ１７０６の分析実行処理において、枝刈り判定を行うところを以下のように変更して実施する。
【０２０４】
すなわち、第２実施形態のスレーブ１０９は、カレントルールの子孫ルールが取り得る評価値の最大値を推定し、上記推定値と、枝刈り判定値リストのカレントルールの条件節に対応する判定値とを比較し、判定値の方が値が小さかった場合、前記の推定値で、判定値を上書きする。なお、カレントルールに条件節が複数含まれる場合は、ルールに対応する枝刈り条件節リストの判定値も複数存在する。
【０２０５】
また、第２実施形態では、上述したＳ１７０９の枝刈りリスト送信処理を以下のように変更して実施する。
【０２０６】
具体的には、第２実施形態では、Ｓ１７０９において、スレーブ１０９は、マスタ１０１から枝刈りリスト送信の信号を受信するまで待機する。スレーブ１０９は、枝刈りリスト送信の信号を受信すると、この信号に含まれている採用ルールの最小評価値を読み込み、これを枝刈り条件節リストＢに保持されている「枝刈り判定値」と比較する。そして、スレーブ１０９は、判定値の方が小さい条件節の枝刈りフラグを「枝刈りが発生している」ことを意味する「１」に設定する。スレーブ１０９は、判定値の方が小さい条件節以外の枝刈りフラグを「枝刈りが発生していない」ことを意味する「０」に設定する。このようにして、スレーブ１０９は、次のレイヤの枝刈り条件節リストの値を定め、枝刈りフラグのみをマスタ１０１に送信する。
【０２０７】
この第２実施形態では、分析対象レイヤにおけるルールの評価が全て終わってから、ルールリストより採用ルールの最小評価値を取得し、この値を元に枝刈りの有無を決定する。第1実施形態では、ルール生成を行いながら枝刈りの判定を行うが、第２実施形態では、全ての条件節について、ルール生成を行いながら枝刈り判定を行うときの判定値よりも同じか大きい値で枝刈りの判定を行うことになるので、枝刈りの機会が増えることが期待できる。
【０２０８】
したがって、この第２実施形態によれば、より効率的に枝刈り処理を行うことにより、評価するルール数を減らし、高速でルール生成を行うことが可能である。
【０２０９】
<第３実施形態>
続いて、第１実施形態の他の変形例である第３実施形態について説明する。第３実施形態は、第１実施形態のスレーブ１０９が行なう図１７に示したＳ１７０６の初期化処理、およびＳ１７０６で説明した分析実行処理においてルール生成を行う際のレコードの走査を変更したものである。なお、第３実施形態の説明において、第１実施形態と同様の構成については、同様の符号を用いることとする。また、第３実施形態の説明は、第１実施形態と異なる部分を中心に説明する。
【０２１０】
第３実施形態では、親子のルールについて、「特徴ルール生成の探索木では、子ルールは親ルールの条件部に別の条件節を追加した条件部を持つので、親ルールの条件部を満たさなかったレコードが、子ルールの条件部も満たすことはない」という性質を利用し、「親ルールを満たさなかったレコードは、子ルールでは走査しない」という方針を採用することによって走査するレコードの数を削減し、処理の高速化を図るようにしている。以下、第３実施形態の詳細を以下に述べる。
【０２１１】
第３実施形態では、あるルールを評価する際に走査する必要のあるレコードのレコード番号を記録する「レコードインデックス」をメモリに保持する。レコードインデックスは、分析処理の際に使用される全てのレコードのレコード番号を記録しておくのに十分な大きさを持つメモリ上の記憶領域である。
【０２１２】
スレーブ１０９は、上述した図１７のＳ１７０２の処理に加えて、さらに、以下の処理を行なう。
【０２１３】
具体的には、スレーブ１０９は、最大条件節数をＣ＿ｍａｘとして、Ｃ＿ｍａｘ個のレコードインデックスをメモリに確保する。レコードインデックスには、「０」から「Ｃ＿ｍａｘ-１」のインデックス番号を与える。例えば、レコードインデックス０、レコードインデックスｎなどと記すことにする。また、レコードインデックスｋのj番目の要素を「ｘ（ｋ， Ｊ）」と表すこととする。
また、以下ではレコード番号がaのレコードをレコードaと示す。スレーブ１０９は、これらのレコードインデックスを空で初期化する。レコードインデックス０には、分析に用いるレコードのレコード番号を１から順に全て記録する。また、ルールの結論部を満たすレコードの数をカウントし、その値をｃ３とする。
【０２１４】
第３実施形態では、上述したＳ１７０６の処理において、レコードの走査を以下のように行う。なお、以下では、スレーブ１０９が分析開始後ｍ番目に評価するルールＲ（ｍ）の条件部を「ｃ（ｍ， １） ａｎｄ ｃ（ｍ， ２） and … ａｎｄ ｃ（ｍ， ｎ）」と記すことにする。つまりｃ（ｍ， ｎ）は、ルールＲ（ｍ）の先頭からn番目の条件節である。
【０２１５】
また、スレーブ１０９において、Ｒ（ｍ-１）の評価まで完了しており、Ｓ１７０６を実行する時点でＲ（ｍ）の評価を行おうとしているものとする。Ｒ（ｍ）はレイヤ「Ｎ」に含まれているものとする。レコード走査処理の流れを図２２を用いて説明する。
【０２１６】
図２２は、第３実施形態のレコードの走査を行う処理の詳細を示すフローチャートである。
【０２１７】
スレーブ１０９は、最初に差分チェック処理を行なう（Ｓ２２０１）。差分チェック処理では、スレーブ１０９は、Ｒ（ｍ-１）とＲ（ｍ）との条件部を比較し、以下の条件を満たすように値「ｋ」を定める。具体的には、スレーブ１０９は、Ｒ（ｍ-１）とＲ（ｍ)との条件部を比較して、ｋ番目の条件節までが同じであり、ｋ+１番目の条件節以降が異なっている」ことを満たす値「ｋ」を求める。ただし、「ｍ=１」の場合は、ｋ=０とする。また、全ての条件節が異なっている場合、「ｋ=０」とする。
【０２１８】
スレーブ１０９は、レコードインデックスｋ+１以降を空に初期化する。スレーブ１０９は、さらに、各種の代入処理を行なう（Ｓ２２０２）。具体的には、スレーブ１０９は、「ｊ」に対して「１」を代入して、「ａ」に対して「X(k, j)」を代入する。スレーブ１０９は、「ｎ」に対して「ｋ+１」を代入して、「ｃ１」に「０」を代入して、「ｃ２」に「０」を代入する。ここで、「ｊ」は、レコードインデックスの要素にアクセスするための変数、「a」には走査の対象となるレコードのレコード番号、「ｎ」は、条件節の番号、「ｃ１」はルールＲ（ｍ）の条件部を満たすレコード数、「ｃ２」は、ルールＲ（ｍ）の条件部と結論部を同時に満たすレコード数が記録される。
【０２１９】
続いて、Ｓ２２０３において、スレーブ１０９は、レコードａが条件ｃ（ｍ， ｎ）を満たすかどうかをチェックする。条件を満たす場合、Ｓ２２０５の処理に進み、条件を満たさない場合、Ｓ２２０７の処理に進む。
【０２２０】
Ｓ２２０５では、スレーブ１０９は、「ｎ」と「Ｎ」とを比較して、「ｎ≠Ｎ」の場合Ｓ２２０４に進む。Ｓ２２０４では、スレーブ１０９は、レコードインデックスｎに、現在走査しているレコードのインデックス番号であるａを追加し、Ｓ２２０６の処理に進む。Ｓ２２０６では、スレーブ１０９は、「ｎ」に「ｎ+１」を代入して、Ｓ２２０３の処理に戻る。
【０２２１】
一方、Ｓ２２０５において、「ｎ＝Ｎ」の場合、レコードａはルールＲ（ｍ）の条件部を満たすことが確認されたことになる。この場合、スレーブ１０９は、これをフラグなどで記録し、Ｓ２２１０の処理に進む。
【０２２２】
Ｓ２２１０では、スレーブ１０９は、レコードaが、ルールＲ（ｍ）の結論部を満たすかどうかをチェックする。これまでの処理において、レコードａがＲ（ｍ）の条件部を満たすかどうかも解っているので、この結果より、レコード数と計数するカウンタｃ１、ｃ２を増加させる。
【０２２３】
Ｓ２２０７では、スレーブ１０９は、ｘ（ｋ， ｊ）がレコードインデックスｋに含まれる最後のレコードであれば、Ｓ２２０９に進み、そうでなければＳ２２０８において「ｊ←ｊ＋１」、「ａ←ｘ（ｋ， ｊ）」とし、Ｓ２２０３の処理に戻る。
【０２２４】
Ｓ２２０９では、スレーブ１０９は、c１、c２、c３より、ルールＲ（ｍ）の評価値を計算し、処理を終了する。
【０２２５】
このように、第３実施形態によれば、ルールの評価の際に走査するレコードの数を減らすことが可能であり、結果として高速に処理を行うことが可能である。
【０２２６】
このように、本発明の上述した第１〜３実施形態によれば、例えば、図２に示すような購買データの分析や、ＤＮＡチップを用いた遺伝子発現解析など、非常に多くの項目を持つデータを分析対象としたデータ分析処理を高速に行なうことができる。
【０２２７】
なお、本発明は、以上で説明した実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形が可能である。
【図面の簡単な説明】
【０２２８】
【図１】本発明の実施形態のデータ分析システムの全体構成を説明するための図である。
【図２】本発明の実施形態で用いられる分析対象データのデータ構成を模擬的に示した図である。
【図３】本発明の実施形態の特徴ルール生成処理により出力されるデータを例示した図である。
【図４】本発明の実施形態の条件項目番号と条件項目を示す項目名称とを対応付けるテーブルの一例を示す図である。
【図５】本発明の実施形態のカテゴリ番号とカテゴリ名称とを対応付けるテーブルの一例を示す図である。
【図６】特徴ルール生成における探索木の一例を示す図である。
【図７】本発明の実施形態の枝刈り条件節リストの一例を示す図である。
【図８】本発明の実施形態のデータ分析システムが行なう探索木をジョブに分割する処理の一例を説明するための図である。
【図９】本発明の実施形態のデータ分析システムが行なう特徴ルール生成処理のアルゴリズムの概要を示すフローチャートである。
【図１０】本発明の実施形態のスレーブが行なう１つのジョブに含まれるルールを探索する処理を説明するためのフローチャートである。
【図１１】本発明の実施形態のマスタが行なう特徴ルール生成処理を説明するためのフローチャートである。
【図１２】本発明の実施形態のマスタが保持するスレーブ管理テーブルの一例を模擬的に示した図である。
【図１３】本発明の実施形態のマスタが分析対象データをカテゴリ化したあとに格納するテーブルの一例を示す図である。
【図１４】本発明の実施形態のマスタが保持するジョブを管理するためのテーブルの一例を模擬的に示した図である。
【図１５】本発明の本実施形態のマスタがスレーブからルール生成に関するコマンドを受信した場合に行なう処理を説明するためのフローチャートである。
【図１６】本発明の実施形態のマスタが有する入出力装置に出力される分析結果表示画面の一例を示した図である。
【図１７】本発明の実施形態のスレーブが行なう処理を説明するためのフローチャートである。
【図１８】本発明の実施形態のスレーブが行なうカレントルールの採用判定処理の詳細を説明するためのフローチャートである。
【図１９】本発明の実施形態のスレーブが行なう枝刈りチェック処理の詳細を説明するためのフローチャートである。
【図２０】本発明の実施形態のスレーブの入出力装置に出力される分析結果表示画面の一例を示した図である。
【図２１】本発明の第２実施形態における枝刈り判定値リストの一例を模擬的に示す図である。
【図２２】本発明の第３実施形態のレコードの走査を行う処理の詳細を示すフローチャートである。
【符号の説明】
【０２２９】
１０１…マスタ、１０２…処理装置、１０３…メモリ、１０４…プログラム、１０５…入出力装置、１０６…通信装置、１０７…記憶装置、１０８…データ記憶装置、１０９ａ〜ｎ…スレーブ、１１０…通信路、１１１…通信路、１１２…処理装置、１１３…メモリ、１１４…プログラム、１１５…入出力装置、１１６…通信装置、１１８…通信路
【図１】
2006107129.tif 000003
【図２】
2006107129.tif 000004
【図３】
2006107129.tif 000005
【図４】
2006107129.tif 000006
【図５】
2006107129.tif 000007
【図６】
2006107129.tif 000008
【図７】
2006107129.tif 000009
【図８】
2006107129.tif 000010
【図９】
2006107129.tif 000011
【図１０】
2006107129.tif 000012
【図１１】
2006107129.tif 000013
【図１２】
2006107129.tif 000014
【図１３】
2006107129.tif 000015
【図１４】
2006107129.tif 000016
【図１５】
2006107129.tif 000017
【図１６】
2006107129.tif 000018
【図１７】
2006107129.tif 000019
【図１８】
2006107129.tif 000020
【図１９】
2006107129.tif 000021
【図２０】
2006107129.tif 000022
【図２１】
2006107129.tif 000023
【図２２】
2006107129.tif 000024