(57)【要約】【課題】従来の遺伝的プログラミングのルール抽出方式では、ルール抽出対象のデータベースからただ１つのルールを抽出する。データベース中に異なるルールを満たすような事例が混在し、単一のルールでは事例集合全体を説明できないようなデータベースからは、その複数のルールを抽出することができない。【解決手段】本発明の遺伝的プログラミングによるデータベース解析の方法およびその装置は、進化的最適化により事例集合を適切に分割し、その各部分事例集合からルールを抽出することで、データベース中の事例の入出力関係として複数のIF_THENルールを抽出することができる。また抽出された各々のルールにはそのルールに一致する事例がデータベース中に存在する割合やIF_THENルールを用いた推論結果に基づいて決定された優先度が付与される。その結果として、従来手法より分類精度が高い、事例の分類システムを構築することが可能である。【選択図】  図１
2005242739.tif 000002
【特許請求の範囲】
【請求項１】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、事例を構成する各入力信号とその信号が取り得る値を表す終端ノードおよびそれらの値の大小関係や論理積を表す関数ノードを組み合わせた木構造により、同一の分類結果を持つ事例の入出力関係をIF_THENルールで表現する手段と、データベースに存在する任意の１つの分類結果を持つ事例の集合を同一の入出力関係を満たす複数の部分事例集合に自動で分割する手段と、複数個生成された木構造に対して事例の分類精度を示す適応度に基づいた選択と木構造における部分木の交換やノードの変更を行い新たな木構造集団を生成するという操作を繰り返す処理を用いることによって、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段を備えたデータベース解析装置。
【請求項２】
請求項１記載の、事例集合を同一の入出力関係を満たす複数の部分事例集合に分割する手段と、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段において、同一の分類結果を持つ事例集合中の任意の部分集合の事例が満たすIF_THENルールを持ち、そのルールに応じて出力を返す機能を持つプログラムをエージェントとし、同一のIF_THENルールを持つエージェントの集合をグループとして、複数のエージェントによりある１つの分類結果を持つ事例集合全体をいずれかのエージェントが持つルールで表現できるように、複数のエージェントが構成するグループ数と各グループに所属するエージェント数、および各エージェントの持つIF_THENルールを自動で探索する最適化手法を用いるデータベース解析の方法。
【請求項３】
請求項１記載の各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段において、同じIF_THENルールを持つ請求項２記載のエージェントの数がそのルールの優先度を表し、任意の１つの分類結果を持つ事例集合に対するIF_THENルールがその分類結果に属する事例集合中の事例に一致する割合が大きいほどそのIF_THENルールの優先度が上がり、そのIF_THENルールが他の分類結果に属する事例に対しても成立してしまう割合が大きいほどそのIF_THENルールの優先度が下がるように適応度を設定することにより優先度を付与するデータベース解析の方法。
【請求項４】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、同一の分類結果を持つ事例の集合をクラスとし、任意の１つのクラスを同一の入出力関係を満たす複数の部分事例集合に自動で分割する手段と、複数個生成された木構造に対して事例の分類精度を示す適応度に基づいた選択と木構造における部分木の交換やノードの変更を行い新たな木構造集団を生成するという操作を繰り返す処理を用いることによって、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段を用いて、対象としたクラスだけが満たすIF_THENルールを自動で獲得する操作を、データベース中に存在する全てのクラスに対して繰り返し履行することにより、データベースに存在する全てのクラスに対するIF_THENルールを抽出する手段を備えた請求項１記載のデータベース解析装置。
【請求項５】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、請求項４記載の手段によって獲得された全てのクラスに対するIF_THENルール集合を用いて、データベース中の事例やデータベース中には存在しない同一フォーマットを持つ事例に対して、その事例がどのクラスに対するIF_THENルールに一致するかに応じて事例を分類する手段と、事例に対して異なるクラスの特徴を示す複数のルールが成立し分類候補が複数存在した場合に、成立したルールの中で最大の優先度を持つルールが示すクラスに分類する手段を備えたデータベース解析装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造プログラムを進化的に最適化する手法である遺伝的プログラミングを用いてデータベース中の事例が満たす複数のIF_THENルール及びそのルールの優先度を獲得する知識獲得手法と、その優先度が付与されたルールを用いて出力が未知である事例に対して出力を予測するシステムを構築する方式に関係する。
【背景技術】
【０００２】
データベース中の事例の入出力関係を表すルールを抽出する手法の１つとして遺伝的プログラミングがある。遺伝的プログラミングは、生物の進化から着想された最適化アルゴリズムである進化的計算法の一種であり、Kozaにより提案された（非特許文献１参照）。
【０００３】
遺伝的プログラミングは木構造プログラムの最適化手法である。遺伝的プログラミングでは、まず問題の解を木構造プログラムで表現できるように、木構造プログラムにおける木の節の要素となる関数記号と、木の葉の要素となる終端記号を設定する。例えば、入出力関係を数式で表現したい場合は、関数記号として四則演算子、終端記号として変数や定数を用いれば良い。図２は関数記号として｛＋，−，×｝、終端記号として｛ｘ，1｝を用いた場合の木構造プログラムの例であり、この木構造プログラムは数式(1+x)(x-1)を表している。問題の解を表す木構造プログラムを遺伝的プログラミングにおける個体と呼ぶ。
【０００４】
遺伝的プログラミングは個体を複数個生成し、生物の適者生存の原理に従って個体群を進化させる。この最適化の流れを図３に示す。まずはじめに、関数記号と終端記号をランダムに組み合わせることにより、複数の木構造プログラムを生成する（３１）。これを初期世代（第1世代）の個体集団とする。次に各個体が表す解を問題に適用しその性能を評価する（３２）。各個体には問題の解としてどの程度優れているかを表す評価値が与えられる。これを適応度と呼ぶ。この適応度に基づいて次世代の個体集団の親となる個体を選択する（３３）。適応度が高い個体ほど選択されやすい。このようにして選択した親個体集合において、２個ずつの組を作成し、各組に対して交叉率と呼ばれる確率に基づいて木構造プログラムの一部を個体間で交換する（３４）。この操作を交叉と呼ぶ。交叉では、図４のように、２つの個体においてそれぞれランダムに１つのノードを選択し、そのノード以下の部分木を交換する。さらに、各個体に対して、突然変異率と呼ばれる確率に基づいて木構造プログラム中のある記号を強制的に別の記号に変更する（３５）。この操作を突然変異と呼ぶ。また、適応度に基づく選択、交叉、突然変異を遺伝操作と呼ぶ。
【０００５】
上記の操作によって次世代の個体集合が生成される。そして再度、各個体の適応度評価を行う（３６）。集団中の最も適応度の高い個体（最良個体）の適応度があらかじめ設定した終了基準を超えるまで、（３３）から（３６）の操作を繰り返す。これにより、木構造プログラムの集合を進化させ、問題により適した解を得ることができる。
【０００６】
入力信号と出力信号の関係が未知のシステムにおいて、その入出力関係を表すルールを木構造で表現できるように終端記号と関数記号を設定し、既知の事例を訓練事例として遺伝的プログラミングを適用すれば、最適化の結果得られた最良個体の木構造プログラムが表すルールは事例の入出力関係を適切に表しており、また獲得したルールを出力が未知の事例に適用することによりその事例の出力を予測することができる。ここで、既知の事例は遺伝的プログラミングの個体への入力となる特徴量ベクトルと、それに対する出力信号の組によって表現される。
【０００７】
特開２００３−３１７０８３では、入力の特徴量ベクトルX=(X1，X2，・・・，Xn)があらかじめ定められたm種類の分類結果Y1，Y2，・・・，Ymのいずれかに分類されている特徴を持つ訓練事例の集合から、その分類を実現するルールを遺伝的プログラミングにより抽出するシステムが記載されている。なお以下では、あらかじめ定められた複数種類に分類され同一の分類結果を持つ事例集合をクラスと呼ぶこととする。従来発明では、ある事例がクラスYiに属するかどうかを判定するルールを抽出するために、クラスYiに分類された事例のみが正の値１を返し、クラスYi以外に分類された事例は負の値−１を返すよう教示信号を設定し、全訓練事例におけるルールの出力値と教示信号の誤差の２乗の和を適応度の評価式としてこの値を小さくするように遺伝的プログラムを適用している。この遺伝的プログラミングによる最適化をi=1，・・・，mまで各クラスを対象として独立してm回行い、各クラスの事例のみが満たすルールを抽出する。その結果得られたm個のルールを用いて、出力が未知の事例に対する分類システムを構築している。出力が未知の事例の分類を行う場合は、その事例の特徴ベクトルを各クラス用のルールに適用し、１に最も近い値を返したルールが示すクラスに分類する。
【０００８】
上記発明の実施例では、具体例として、３種類のクラスα、β、γの分類問題を扱っている。ここで、図５に示すように、α、β、γの各クラスと各クラスの事例のみが満たすルールＡ、Ｂ、Ｃを求めるための教示信号との関係が定められ、教師データ（入力となる特徴量ベクトルと教示信号との組み合わせ）が準備される。遺伝的プログラミングによるルールの抽出は対象とするクラスごとに独立に行われ、最終的に各クラスに対して１つのルール（合計３つのルールＡ〜Ｃ）が決定される。
【０００９】
以上のようにして最終決定された３つのルールＡ〜Ｃを用いることにより分類処理が可能となる。図６に示すように、ルールＡの出力値が最大であればクラスα、ルールＢの出力値が最大であればクラスβ、ルールＣの出力値が最大であればクラスγと判定される。
【００１０】
以上で述べた従来法の問題点は、あるクラスの事例が満たすルールとして単一のルールしか抽出できないことである。同一のクラスに分類されるものであっても、そのクラスの事例の典型的なルールを満たさない例外的な事例が存在する場合もあるため、そのクラスの全ての事例に対して有効なルールは単一のルールで記述できるとは限らない。このような状況では、事例の分類を行う際に、ある１つのクラス用に複数のルールを用意し、そのうちのいずれかが成立した場合に、そのクラスであると判断しなければならない。上記の従来発明の方法では、この処理は不可能であるため、分類能力の精度が低くなってしまう。
【００１１】
【特許文献１】特開２００３−３１７０８３
【非特許文献１】Koza, J., Genetic Programming: On the Programming of Computers by means of Natural Selection, MIT press, 1992
【発明の開示】
【発明が解決しようとする課題】
【００１２】
遺伝的プログラミングを用いたデータベースからのルール抽出に関する従来手法は、全訓練事例に対する誤差の総和を最小化するただ1つのルールの抽出を行うものであった。そのルールにあてはまらない事例は、ノイズや例外データとして無視される。しかし、事例の大部分にあてはまる一般的なルールだけではなく例外的な少数の事例のために利用できるルールを獲得することも重要である。また、複数のルールを獲得した場合には、各ルールがそのクラスの事例に対してどの程度一般的なルールであるかという指標も重要となる。そこで本発明では、データベース中の事例が満たす複数のルールおよび各ルールの優先度を抽出することを目的とする。また、このような複数のルールを利用して精度の高い分類システムを構築することを目的とする。
【課題を解決するための手段】
【００１３】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、事例を構成する各入力信号とその信号が取り得る値を表す終端ノードおよびそれらの値の大小関係や論理積を表す関数ノードを組み合わせた木構造により、同一の分類結果を持つ事例の入出力関係をIF_THENルールで表現する手段と、データベースに存在する任意の１つの分類結果を持つ事例の集合を同一の入出力関係を満たす複数の部分事例集合に自動で分割する手段と、複数個生成された木構造に対して事例の分類精度を示す適応度に基づいた選択と木構造における部分木の交換やノードの変更を行い新たな木構造集団を生成するという操作を繰り返す処理を用いることによって、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段を備えたデータベース解析装置を有する。
【００１４】
請求項１記載の、事例集合を同一の入出力関係を満たす複数の部分事例集合に分割する手段と、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段において、同一の分類結果を持つ事例集合中の任意の部分集合の事例が満たすIF_THENルールを持ち、そのルールに応じて出力を返す機能を持つプログラムをエージェントとし、同一のIF_THENルールを持つエージェントの集合をグループとして、複数のエージェントによりある１つの分類結果を持つ事例集合全体をいずれかのエージェントが持つルールで表現できるように、複数のエージェントが構成するグループ数と各グループに所属するエージェント数、および各エージェントの持つIF_THENルールを自動で探索する最適化手法を用いるデータベース解析の方法を有する。
【００１５】
請求項１記載の各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段において、同じIF_THENルールを持つ請求項２記載のエージェントの数がそのルールの優先度を表し、任意の１つの分類結果を持つ事例集合に対するIF_THENルールがその分類結果に属する事例集合中の事例に一致する割合が大きいほどそのIF_THENルールの優先度が上がり、そのIF_THENルールが他の分類結果に属する事例に対しても成立してしまう割合が大きいほどそのIF_THENルールの優先度が下がるように適応度を設定することにより優先度を付与するデータベース解析の方法を有する。
【００１６】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、同一の分類結果を持つ事例の集合をクラスとし、任意の１つのクラスを同一の入出力関係を満たす複数の部分事例集合に自動で分割する手段と、複数個生成された木構造に対して事例の分類精度を示す適応度に基づいた選択と木構造における部分木の交換やノードの変更を行い新たな木構造集団を生成するという操作を繰り返す処理を用いることによって、各部分事例集合が満たす入出力関係を適切に表現するIF_THENルールを抽出する手段と、各部分集合から抽出されたIF_THENルールの複数が成立した際にいずれのIF_THENルールを採用するかを判断するための優先度を付与する手段を用いて、対象としたクラスだけが満たすIF_THENルールを自動で獲得する操作を、データベース中に存在する全てのクラスに対して繰り返し履行することにより、データベースに存在する全てのクラスに対するIF_THENルールを抽出する手段を備えた請求項１記載のデータベース解析装置を有する。
【００１７】
あらかじめ用意された複数の分類候補の1つもしくは重複を許して2つ以上に、出力信号に応じて分類されている特徴を持つ事例を格納したデータベースにおいて、請求項４記載の手段によって獲得された全てのクラスに対するIF_THENルール集合を用いて、データベース中の事例やデータベース中には存在しない同一フォーマットを持つ事例に対して、その事例がどのクラスに対するIF_THENルールに一致するかに応じて事例を分類する手段と、事例に対して異なるクラスの特徴を示す複数のルールが成立し分類候補が複数存在した場合に、成立したルールの中で最大の優先度を持つルールが示すクラスに分類する手段を備えたデータベース解析装置を有する。
【発明の効果】
【００１８】
上述のように、本発明の遺伝的プログラミングによるルール抽出手段では、データベース中に異なるルールを満たすような事例が混在する場合に、必要な数だけの複数のIF_THENルールを自動的に抽出することができる。そのため、単一ルールの抽出を目的とした従来の遺伝的プログラミングによるルール抽出手法では不可能であった、データベース中に含まれる少数の例外的データに対するルールを抽出することが可能となる。
【００１９】
抽出される複数のルールの各々には、データベース中の事例に対してそのIF_THENルールが成立する頻度やそのIF_THENルールを用いた推論結果に基づいて決定される優先度が自動的に割り当てられる。この優先度の値から、それぞれのルールが一般的なものであるか、例外的なものであるかという知識が得られる。また一般的ルールと例外的ルールが明示的に分離されていることから、ルールの理解が容易となる。
【００２０】
未知の事例に対して、異なるクラスのための複数のIF_THENルールが成立する場合、その優先度に応じた分類結果の判定が可能であり、その結果として精度の高い分類が可能となる。
【発明を実施するための最良の形態】
【００２１】
本発明の遺伝的プログラミングによるデータベース解析の方法およびその装置は、図１に示すように、進化的最適化により事例集合を適切に分割し、その各部分事例集合からルールを抽出することで、データベース中の事例の入出力関係を表す複数のIF_THENルールを抽出することができる。また抽出された各々のルールにはそのルールに一致する事例がデータベース中に存在する割合やIF_THENルールを用いた推論結果に基づいて決定された優先度が付与される。その結果として、従来手法より分類精度が高い、事例の分類システムを構築することが可能である。以下でその詳細および実施例を示す。
【００２２】
全訓練事例集合において、任意の部分集合の事例が満たす入出力関係のルールを表す木構造プログラムを持つものをここではエージェントと呼ぶ。データベースから複数のルールを抽出するために、このエージェントが複数存在するシステム（マルチエージェントシステムと呼ぶ）を用いる。訓練事例集合は複数の部分集合に分割され、複数のエージェントが別々の部分集合からルールを抽出することで、訓練事例中に含まれる複数のルールを抽出することができる。
【００２３】
上記のマルチエージェントシステムによる複数のルール抽出処理を実現するにあたり、訓練事例集合をいくつの部分集合へどのように分割してルールを抽出するかを決定する必要がある。本発明では、全訓練事例の入出力関係を表すのに必要なルール数および木構造プログラムで表されたルールを、1個体の表現方法や遺伝操作の方法を変更した遺伝的プログラミングを用いて獲得する。
【００２４】
複数のエージェントが同一の事例部分集合からルール抽出を行う場合、それらのエージェントは同一の木構造プログラムを持つ。このように同一の木構造プログラムを持つエージェントの集合をグループと呼ぶ。あらかじめ用意したエージェントは、どれか１つのグループに所属することになる。本発明で用いる遺伝的プログラミングは、エージェントがいくつのグループに分かれそしてどのエージェントが同じグループに所属しているかというグループ構造と、各グループが持つ木構造プログラムを進化の過程で共に探索する最適化手法である。この最適化手法をルール抽出処理に応用すれば、訓練事例の入出力関係を表現するのに適切な数だけ異なるルールを生成することができる。また獲得されたグループ構造を解析することにより、事例の入出力関係の表現に必要なルール数、そして各ルールを満たす事例の出現頻度およびルールを用いた推論結果に基づいた各ルールの優先度に関する知識を獲得できる。
【００２５】
本発明では各エージェントのグループが持つ木構造プログラムの集合を、遺伝的プログラミングにおける1個体としてみなす。すなわち、遺伝的プログラミングの各個体は、マルチエージェントシステムを表す。図７は４つのエージェントをルール抽出に用いた場合における遺伝的プログラミングの１個体の例を示している。この図では、エージェント１とエージェント２が１つのグループ（７１）であり、またエージェント３とエージェント４が別のグループ（７２）を形成している。その結果として、この個体は各グループ用に２つの木構造プログラム（７３、７４）を持つ。すなわち、この個体は２つのルールを持っていることになる。
【００２６】
以下で、本発明で用いる遺伝的プログラミングの具体的な処理手順について述べる。図８は本発明による最適化の流れである。はじめに、初期個体集団を生成する（８１）。図９はある１つの初期個体の生成手順を示したものであり、また図１０は本発明における個体集団の概念図である。図９に示した処理を行うことにより、初期個体におけるグループの分割数および各グループへのエージェントの配分はランダムに決定される。図９の処理を初期世代に用いる個体数だけ繰り返すことにより個体集団を作成する。その結果、個体集団は図１０のような多様なグループ構造を持つ。なお、図１０における個体（１０１）は、図７で示した個体を簡略化して描いたものである。
【００２７】
本発明で用いる遺伝的プログラミングの遺伝操作において、選択（８３）、突然変異（８６）は通常の遺伝的プログラミングにおける処理と同様であるが、交叉（８５）が大きく異なる。また新たな遺伝操作としてグループ突然変異（８４）が追加される。
【００２８】
まずは交叉方法の説明を行う。ある２つの個体を交叉する際の具体的な処理手順を以下のステップ１からステップ３に示す。
【００２９】
ステップ１：交叉を行う2つの個体に対して、1つのエージェントを任意に選択する。各個体において、そのエージェントが参照する木をそれぞれTとT'とする。これらの木が交叉に使用される。
【００３０】
ステップ２：各親個体において、選択された木T、T'を参照するエージェント集合A(T)、A(T')をそれぞれ求める。これらの集合の関係は次の3つのケースが考えられる。
【００３１】
ケース１  A(T)＝A(T')のとき：  もし集合の関係がA(T)＝A(T')ならば、各個体のグループ構造は変化しない。ステップ３へ移る。
【００３２】
ケース２  A(T)⊃A(T')またはA(T)⊂A(T')のとき：  集合の関係がA(T)⊃A(T')またはA(T)⊂A(T')ならば、以下の処理を行う。もし集合の関係がA(T)⊃A(T')ならば、Tを持つ個体において、Tと同一の木構造プログラムを新たに生成し、集合A(T)∩A(T')の要素であるエージェントをその木構造プログラムを参照するグループに移す。このようにして新たに生成した木構造プログラムをあらためてTとする。T'を持つ個体のグループ構造は変化しない。逆に、もし集合の関係がA(T)⊂A(T')ならば、T'を持つ個体において、T'と同一の木構造プログラムを新たに生成し、集合A(T)∩A(T')の要素であるエージェントをその木構造プログラムを参照するグループに移す。このようにして新たに生成した木構造プログラムを改めてT'とする。Tを持つ個体のグループ構造は変化しない。このように、２つの集合A(T)、A(T')の共通部分集合の要素であるエージェントが参照する木構造プログラムだけが交叉に使用されるように、一方の個体でグループの分割が発生する。図１１は２つの親個体（１１１と１１２）において、エージェント２が参照する木同士で交叉した場合を表している。ステップ３へ移る。
【００３３】
ケース３  A(T)、A(T')において一方が他方を含む関係に互いにないとき  （ケース１、ケース２のどちらにも該当しない場合）：  A(T)、A(T')の補集合を各々A(T)~、A(T')~とする。もし集合の関係が、A(T)⊃A(T')でない、かつA(T)⊂A(T')でないならば、木Tを持つ個体において集合A(T)~∩A(T')の要素であるエージェントを木Tを持つグループへ移し、木T'持つ個体においては集合A(T')~∩A(T)の要素であるエージェントを木T'を持つグループへ移す。このとき、所属エージェントがなくなったグループおよびそのグループが持つ木構造は削除される。結果として、両方の個体で、A(T)∪A(T')の要素であるエージェントが同一の木を参照するように、エージェントの移動が起こる。図１２は２つの親個体（１２１と１２２）において、エージェント１が参照する木同士で交叉した場合を表している。ステップ3へ移る
【００３４】
ステップ３：木TとT'において、それぞれの木のノードの中から1点がランダムに選択し、そのノード以下の部分木を2個体で交換し、交叉が完了する。
【００３５】
以上のように、交叉は任意の同じエージェントが参照する木構造プログラム同士で行われる。そして交叉に使用される木を参照するエージェント集合の関係に応じてグループ構造を変更する。
【００３６】
またグループ突然変異（８６）は、個体集団がただ１つのグループ構造へ収束することを防ぐために用いる。グループ突然変異では、1個体を構成する各エージェントに対してグループ突然変異率と呼ばれる生起確率に基づいて、あるエージェントを任意に選択されたグループへ移す操作を行う。この操作は交叉によるグループ構造の変化を促進するものとして働くため、交叉の前に行われる。
【００３７】
上記の操作を用いて世代交代を繰り返すことにより、個体集団はグループ構造を徐々に好ましいものに近づけながら解の探索を行う。
【００３８】
図１３は本発明の一実施例の構成図である。この図は、優先度が付与されたIF_THENルールを抽出するシステム（システム１）と、このシステムを複数回用いて抽出した各クラスの事例が満たすIF_THENルールを全て用いて作成した分類システム（システム２）を示している。システム１では、事例を格納したデータベース（１３１）に対して、遺伝的プログラミングを用いたルール抽出処理（１３２）を適用する。進化させた個体集団中の最良個体が持つ複数のルール（１３３）を事例がクラスYiであるかどうかを判定するためのIF_THENルールとする。また本発明を用いることにより、獲得された複数のルールには、そのルールが成立する頻度やそのルールを用いた推論結果に基づいた優先度が付与される。各々のクラスの事例が満たすIF_THENルールを抽出するため、ルール抽出対象のクラスYiをi=1，・・・，mと変更して、システム１を実行する。
【００３９】
データベース（１３１）には、入力の特徴量ベクトルX=(X1，X2，・・・，Xn)がm個のクラスY1，Y2，・・・，Ymのいずれかに分類された事例が格納されている。
【００４０】
ある入力ベクトルが与えられたときに、それがどのクラスに分類されるかを判定するためには、各Yi (i=1，・・・，m)の事例のみが満たすべき論理式を求めなければならない。この論理式は、ある項目とそれが取りうる値の組をAND結合した式であり、例えば次の式数1ように表される。
【数１】
2005242739.tif 000003
【００４１】
この場合、クラスYkの事例に対しては論理式が真（True）を返し、クラスYk以外の事例に対しては論理式が偽（False）を返さなければならない。よってこの式は、論理式が成立するならばその事例はクラスYkに分類されることを示すIF_THENルールとなっている。このIF_THENルールの前件部にあたる論理式は図１４のような木構造プログラムで表現される。
【００４２】
上で述べたクラスYkの事例のみが満たすIF_THENルールの抽出方法について述べる。図１５は各個体の適応度の評価方法を、図１６はその概念図を表している。本発明で用いる遺伝的プログラミングの個体における複数の木は、各々論理式を表している。ｍ種類のクラスが混在する訓練事例集合から各事例をシステムに入力する（１５２）。その入力データに対して、適応度の評価対象の個体が持つ各木の論理式が成立するかどうかを計算する（１５６）。図１６のデータ2に示すように１個体が持つ複数の論理式の内で１つでも真（T）となれば、その入力データの分類結果はYkであるとみなされる。また、図１６のデータ1のように１個体が持つ複数の論理式が全て偽（F）を返せば、その入力データの分類結果はYkではないとみなす。Ykに分類されるべき事例に対しては、個体中の複数の木の中の少なくともいずれか一つが真を出力し、それ以外のクラスの事例には全ての木が偽を返すように最適化を行う。
【００４３】
ルール抽出対象ではない他のクラスの事例に対して、論理式が誤って真を返してしまうような場合、そのルールを持つエージェントの数に応じてペナルティとしてその個体の適応度を減じることとする。これにより誤認する頻度が高いグループへのエージェントの配分は抑制される。
【００４４】
また、各エージェントがルール抽出のために担当する事例の数という観点では、各エージェントの負荷という概念が生じる。これは各グループが持つルールの採用回数および各グループに所属するエージェント数から計算される。各ルールの採用回数は、ルール抽出対象のクラスの事例に対して、そのルールが正しく真を返した場合にカウントされる（１６０）。採用回数のカウントの際は、図１６のデータ3のように、複数の木が真を出力した場合は、その中で最もエージェント数の多いグループのルールを採用することとする。このとき、あるエージェントaがグループgに属しているとすると、このエージェントの負荷Waは次の式数２のように計算される。
【数２】
2005242739.tif 000004
【００４５】
このように計算される各エージェントの負荷を均一化することで、採用回数が多いルールを持つグループには多くのエージェントが配分されるようになり、採用回数が少ないルールを持つグループのエージェント数は少ないものとなる。各ルールを参照しているエージェントの数を見れば、抽出された各々のルールが使用される頻度、すなわち各ルールがそのクラスの事例の性質を表すルールとしてどの程度一般的なものかという重要な知識が得られる。このように各ルールを参照するエージェントの数は、そのルールに一致する事例がデータベース中に存在する割合とルールを用いた推論結果に基づいて決定され、各ルールの優先度を表すことになる。
【００４６】
上記の要求を満たすため、適応度は以下の式数３で計算される。この適応度が増加するように個体集団を進化させることによって、クラスYkの事例のみが満たすIF_THENルールを抽出する。
【数３】
2005242739.tif 000005
【００４７】
ここでmiss_target_dataはルール抽出対象であるクラスYkの事例に対して全てのルールが偽を返した数である（１５８、１６１、１６２）。misrecognitionは、他のクラスの事例に対して真と出力して誤認識してしまった事例数である（１５８、１６１、１６３）。fault_agentは他のクラスの事例に対してあるルールが真を出力して誤認した際に、そのルールを持つグループに所属するエージェント数を表す（１６４）。そのため、式数３の第３項は他のクラスの事例を誤って真と判定してしまう際にそれを支持してしまう平均エージェント数を表している。また、Vwは全エージェントに関する負荷の分散である（１６６）。これらをα、β、δで重み付けした和を適応度とする（１６７）。また冗長なグループの分割を抑制するために、個体が持つグループ数Gの増加に応じてペナルティ係数γ（ただしγ＞１）の（G-1）乗が適応度に乗算される。
【００４８】
上記の適応度を用いた最適化により、Ykに分類されるべき事例に対しては、いずれかの木が真を返し、その他のクラスに分類されるべき事例には偽を返すようになる。また、そのルールが抽出対象のクラスの事例に真を返す頻度が高い程多くのエージェントが配分される。誤認する頻度が高いグループへのエージェントの配分は抑制される。そのため、所属エージェント数が多い程、よく使用される典型的な判定ルールであり、少数のエージェントしか所属していないルールは稀に現れる例外的データに対する判定ルールであることが分かる。他のクラス用のルールも同様の処理により抽出する。
【００４９】
次に各クラス用に獲得されたルールを全て用いて、クラスが未知の事例に対する分類システムを構築する。分類処理の流れを図１７に、その概念図を図１８に示す。クラスが未知の事例の分類を行う際は、その事例を全てのクラスに対するルール集合に適用する。その結果、あるクラスに対して抽出された全てのルールが偽を返す場合は、そのクラスでないことが分かる。抽出したルールのうち、１つでも真を返すものがある場合は、そのルールが示すクラスとなる。例えば、図１８のData 1は、クラスY2と分類される場合を示している。
【００５０】
ある種の事例に対しては、異なるクラスを対象とした複数のルールが真を返す場合が生じる。この場合は、各ルールを持つグループに所属するエージェント数が重要な役割を果たす。最適化の結果として、それぞれのルールを持つグループに所属するエージェント数は、そのルールに一致する事例がデータベースに存在する割合の大きさ、およびルールの予測精度の高さを表すと考えられるため、所属エージェントの多い方のクラスがもっともらしい解と考えられる。ただし、可能性は少ないながらも他方のクラスの可能性もあるとの認識が可能である。図１８のData 2では、クラスY2とクラスYm用のルールが共に真を出力している。この場合は、各ルールを支持するエージェントの多いクラスY2に分類される。ただし、クラスYmの事例の可能性もあることを認識することができる。このようなわずかな可能性も認識できることは本システムを利用する利点の1つである。
【００５１】
実施例として、本発明を医療分野における肝胆嚢データベースからの知識獲得に適用した。このデータベースは、入力項目として９つの検査結果と、出力として４つの疾患（Alcoholic liver damage、 Primary hepatoma、 Liver cirrhosis、 Cholelithiasis）への分類結果を持つ。図１９にこのデータベースにおける各疾患の事例の例を示す。使用するデータベースは536の事例により構成され、そのうち322例を訓練事例として、残りの214事例を学習結果の評価のためのテスト事例として用いた。事例における各検査項目ｘは、図２０に示す閾値を用いて、式数４により４段階に離散化しておく。
【数４】
2005242739.tif 000006
【００５２】
遺伝的プログラミングの記号としては、図２１に示す終端・関数記号を用いた。ただし、記号の使用には次のような制約を設ける。and記号の引数に直接終端記号がくることはなく、また、eq、 gt、 ltの第１引数arg0にはGOTなどの検査項目が、第２引数arg1には離散値0、1、2、3のいずれかが入るとする。これを満たさないような交叉、突然変異は行わないとした。
【００５３】
ここでは、遺伝的プログラミングの１個体を構成するエージェント数を５０として実験を行った。４つの疾患Alcoholic liver damage、 Primary hepatoma、 Liver cirrhosis、 Cholelithiasisの各事例集合のみが満たすように最適化したルールを、それぞれ順に図２２、図２３、図２４、図２５に示す。ある1つの疾患を判定するために複数のルールが抽出されていることが分かる。例えば、Primary Hepatomaの事例のみが満たすルールである図２３では、獲得された最良個体における５０エージェントは、１１のグループに分割されており、所属エージェントの多いルール程、採用回数が多い傾向を持つ。例えば、Primary hepatoma用のRule1は対象のPrimary hepatomaの事例の32％に真を返す典型的なルールであり、Rule11は対象のPrimary hepatomaの事例の2％に真を返すルールであった。出現頻度の少ない例外的な事例に対するルールも抽出できていることが分かる。
【００５４】
獲得されたルールを統合して作成した分類システムを、学習に使用した322個の事例に適用し分類性能を検証した。その結果、80.4％の分類に成功した。実際の分類の様子を観ると、例えば９つの検査項目の値が各々、0、0、0、1、2、1、1、0、1であるデータは、訓練事例中にAlcoholic liver damageとCholelithiasisの2つの診断結果を持つ事例である。この事例に対しては、Alcoholic liver damageのルール２とCholelithiasisのルール６が共に真を返した。この２つのルールを参照しているエージェント数を見るとそれぞれ８、３となる。エージェント数が示す優先度から、この事例はAlcoholic liver damageに分類される。しかしCholelithiasisの可能性についても注意を促すことに成功している。
【００５５】
また、この分類システムを未学習の214個の事例に適用したところ、157例の認識に成功し、認識率は73.4％であった。ただし、ここで認識に失敗とした事例のうち、30例は正解の疾患の可能性について言及しており、かつその大部分に当たる25例は誤って採用した疾患の他に競合するものが正解の疾患だけという精度の高いものであった。可能性の検出と言う観点から見ると、87.4％の事例の認識に成功できていることが分かる。使用した症例データには、もともと誤って分類された事例も含むため、これは高い認識率と言える。
【産業上の利用可能性】
【００５６】
本発明は、データの計測やその計測結果に基づいた分類の判定にノイズや人間の判断・嗜好を伴うような事例が蓄えられたデータベースに有効である。このようなデータは、同一の入力であっても異なる分類結果を持つ事例が存在することや、逆に、同一の分類結果を示す複数の事例が単一のルールで表現できないといった特徴を持つ。
【００５７】
本発明の応用例としては、医療分野における疾患の診断システム、販売事業における顧客の購買履歴からの知識獲得、気象データの時系列変動に基づく気象予測、株価変動予測などが挙げられる。
【００５８】
例えば、医療分野では、患者の診断結果がデータベースに蓄えられている。その大量の事例から有効な診断規則を発見することは、医療の支援や科学的根拠に基づく医療の実現に向けて重要である。しかし、データベースに蓄えられた計測値や検査値などの実測値はノイズを含み、また診断結果は医師の経験によるところが大きくあいまいなものであるため、診断規則は単一のルールで表現できるとは限らない。医療分野では、一般的なケースとは異なる患者を見落とすこと無く治療できるかどうかが、質の高い医療の実現への鍵となる。例外的な少数の患者のための知識も獲得できる本発明は、医療データベースからの診断規則の抽出に有効である。具体的には、実施例としても挙げたように、過去の患者の診断結果データベースから疾患ごとに優先度付きルールを抽出しておき、新たな患者に対してどのクラスのルールが成立するかによって診断する。異なる疾患のための複数のルールが成立した場合は、それらの疾患のどちらにも該当する可能性があり、その可能性はそれらのルールが持つ優先度の比によって認識できる。また、全てのルールが該当しない場合は、いずれの疾患でもない正常な状態とみなすことができる。
【図面の簡単な説明】
【００５９】
【図１】本発明の概念図
【図２】木構造プログラムの例
【図３】遺伝的プログラミングの処理の流れ
【図４】遺伝的プログラミングにおける交叉の例
【図５】従来発明における事例と教示信号の例
【図６】従来発明における未知事例の分類の様子
【図７】本発明における遺伝的プログラミングの１個体の概念図
【図８】本発明における遺伝的プログラミングの処理の流れ
【図９】本発明における遺伝的プログラミングの初期個体の生成方法
【図１０】本発明における遺伝的プログラミングの個体集団の概念図
【図１１】本発明における遺伝的プログラミングの交叉（グループの分割が発生する例）
【図１２】本発明における遺伝的プログラミングの交叉（グループの統合が発生する例）
【図１３】本発明の実施例の構成図
【図１４】IF_THENルールの前件部となる論理式の例
【図１５】クラスYkの事例が満たすIF_THENルールを抽出する際の各個体の適応度の評価方法
【図１６】各事例がクラスYiに属するかどうかの判定方法の概念図
【図１７】クラスが未知の事例に対する分類処理の流れ
【図１８】クラスが未知の事例の分類の概念図
【図１９】肝胆嚢疾患データの例
【図２０】各検査項目の離散化のための閾値
【図２１】肝胆嚢疾患に対するIF_THENルール作成のための終端・関数記号
【図２２】Alcoholic liver damage  の事例のみが満たすように抽出されたルール
【図２３】Primary  hepatoma  の事例のみが満たすように抽出されたルール
【図２４】Liver cirrhosis  の事例のみが満たすように抽出されたルール
【図２５】Cholelithiasis  の事例のみが満たすように抽出されたルール
【符号の説明】
【００６０】
７１  エージェント１と２からなるグループ
７２  エージェント３と４からなるグループ
７３  グループ７１が参照する木構造プログラム
７４  グループ７２が参照する木構造プログラム
１０１  本発明における遺伝的プログラミングの１個体（図７の個体を簡略化したもの）
１１１  交叉に用いる親個体の１つ
１１２  符号１１１が指す個体と交叉するもう一方の親個体
１２１  交叉に用いる親個体の１つ
１２２  符号１２１が指す個体と交叉するもう一方の親個体
１３１  ｍ種類の分類結果のいずれかに分類された事例を格納したデータベース
１３２  ある1つのクラスの事例のみが満たすIF_THENルールを抽出する処理装置
１３３  クラスYiの事例のみが満たすルールの集合
【図２】
2005242739.tif 000007
【図３】
2005242739.tif 000008
【図４】
2005242739.tif 000009
【図５】
2005242739.tif 000010
【図６】
2005242739.tif 000011
【図７】
2005242739.tif 000012
【図８】
2005242739.tif 000013
【図１０】
2005242739.tif 000014
【図１１】
2005242739.tif 000015
【図１２】
2005242739.tif 000016
【図１４】
2005242739.tif 000017
【図１６】
2005242739.tif 000018
【図１８】
2005242739.tif 000019
【図１】
2005242739.tif 000020
【図９】
2005242739.tif 000021
【図１３】
2005242739.tif 000022
【図１５】
2005242739.tif 000023
【図１７】
2005242739.tif 000024
【図１９】
2005242739.tif 000025
【図２０】
2005242739.tif 000026
【図２１】
2005242739.tif 000027
【図２２】
2005242739.tif 000028
【図２３】
2005242739.tif 000029
【図２４】
2005242739.tif 000030
【図２５】
2005242739.tif 000031