(57)【要約】【課題】従来の遺伝的プログラミングのルール抽出方式では、自由書式のような未整形の事例から構成されたデータベースからルールを抽出することは出来ず、また、教師信号の情報を含む訓練事例が用意されていないデータベースからのルール抽出を行うことは出来ない。【解決手段】本発明の遺伝的プログラミングによるデータベース解析装置は、任意の二空間の差異をもとにした例外事例を自動的に例外事例集合とし、またその例外事例集合を進化的に最適化することにより適切に分割し、その各部分事例集合からルールを抽出することで、データベース中の事例の入出力関係として複数のIF-THENルールを抽出することができる。従来手法とは異なり、教師信号の情報を含む訓練事例をあらかじめ準備する必要がないため、従来手法よりコストが低くかつ様々な事象に適用可能な事例分類システムを構築することが可能である。【選択図】  図１
2008059234.tif 000002
【特許請求の範囲】
【請求項１】
既存の事例集合からなるデータベースまたは既存の事例集合に時間の経過とともに新たな事例が付加されるデータベースであり、かつデータベース中のある特定の部分空間のみに出現するという特徴を持つ事例であるか否かについて分類する情報を持たない未分類のデータベースにおいて、データベース中の空間全体に一様に出現するという特徴を持つ事例を通常事例とし、データベース中のある特定の部分空間のみに出現するという特徴を持つ事例を例外事例とするとき、通常事例のみが存在し例外事例は存在しないという条件の下で事例検出の基準となるあらかじめ与えられた部分空間と、着目する部分空間のみに出現するという特徴を持つ例外事例の検出対象の部分空間の二空間を当該データベース中に任意に定義し、事例を構成する各信号とその信号が取り得る数値および文字列を表す終端節点およびそれらの数値および文字の包含関係や論理積を表す関数を内部節点として組み合わせ連結したグラフ理論における木構造を示すルールを用いて、事例の信号が持つ特徴を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ルールを自動で探索する手法を用いるデータベース解析の機能を備えたデータベース装置。
【請求項３】
請求項１記載の抽出されたIF-THENルールの複数が成立した際にいずれのIF-THENルールを採用するかを判断するための優先度を付与する手段において、請求項２記載の同一のIF-THENルールを参照するエージェントの数がそのルールの優先度を表し、IF-THENルールが例外事例の検出対象の部分空間の事例に対して成立する頻度が高いほどそのIF-THENルールの優先度が上がり、IF-THENルールが例外事例検出の基準となる部分空間の事例に対して成立する頻度が高いほどそのIF-THENルールの優先度が下がるように設定された評価値の計算式を用いることにより優先度を付与するデータベース解析の機能を備えたデータベース装置。
【請求項４】
請求項１記載のデータベース中のある特定の部分空間のみに出現するという特徴を持つ事例であるか否かの分類に関する情報を持たない未分類のデータベースを構築するための手段として、事例を構成する数値および文字の並びに含まれる信号の内容に応じて分類された種類の一部または全部が未知である事例の集合が与えられその事例を信号の内容に応じて分類された種類ごとに取り扱うことが不可能である場合に、自動で各信号の種類を抽出し各事例を信号の種類ごとに解析可能な事例へと変換するための変換ルールを蓄積する特徴付与データベース機能と、その変換ルールに基づいて各信号の取りうる範囲に応じて分割点を求め各信号を分割することにより各事例を信号の種類ごとに取り扱うことが可能な事例に変換処理するための変換機能からなるデータベース装置。
【請求項５】
請求項１記載の例外事例の検出対象の部分空間のみに出現する事例集合を分割した各部分事例集合が満たす信号の特徴を前件部とするIF-THENルールを抽出する手段によって獲得された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個のルールを用いて、出力が未知の事例に対する分類システムを構築している。出力が未知の事例の分類を行う場合は、その事例の特徴ベクトルを各クラス用のルールに適用し、１に最も近い値を返したルールが示すクラスに分類する。
【０００８】
上記発明の実施例では、具体例として、３種類のクラスα、β、γの分類問題を扱っている。ここで、図５に示すように、α、β、γの各クラスと各クラスの事例のみが満たすルールＡ、Ｂ、Ｃを求めるための教示信号との関係が定められ、教師データ（入力となる特徴量ベクトルと教示信号との組み合わせ）が準備される。遺伝的プログラミングによるルールの抽出は対象とするクラスごとに独立に行われ、最終的に各クラスに対して１つのルール（合計３つのルールＡ〜Ｃ）が決定される。
【０００９】
以上のようにして最終決定された３つのルールＡ〜Ｃを用いることにより分類処理が可能となる。すなわち、個々のルールによる出力を計算し、ルールＡの出力値が最大であればクラスα、ルールＢの出力値が最大であればクラスβ、ルールＣの出力値が最大であればクラスγと判定される。
【００１０】
以上で述べた従来法の問題点は、あるクラスの事例が満たすルールとして単一のルールしか抽出できないことである。同一のクラスに分類されるものであっても、そのクラスの事例の典型的なルールを満たさない例外的な事例が存在する場合もあるため、そのクラスの全ての事例に対して有効なルールは単一のルールで記述できるとは限らない。このような状況では、事例の分類を行う際に、ある１つのクラス用に複数のルールを用意し、そのうちのいずれかが成立した場合に、そのクラスであると判断しなければならない。上記の従来発明の方法では、この処理は不可能であるため、分類能力の精度が低くなる。
【００１１】
上記の問題点の解消を提案した特開２００５−２４２７３９により、全訓練事例中の多くの事例に対する典型的なただ1つのルールの抽出を行うだけでなく、その典型的なルールにあてはまらない例外的な少数の事例のために利用できる複数のルールを獲得することが既に可能となっており、また上記の問題点を解消することにより複数のルールを獲得した場合において、各ルールがそのクラスの事例に対してどの程度一般的なルールであるかという指標についても同様に獲得されており、このような複数のルールを利用した精度の高い分類システムが既に構築されている。
【００１２】
従来手法の問題点は、複数のルールを獲得するために教師信号の情報を含む訓練事例が必要となることであり、ルール獲得のために用意されたデータベース中のすべての事例が、あらかじめ何らかの方法により定められたm種類の分類結果Y1、Y2、・・・、Ymのいずれかに分類されたデータであるという条件を満たしていなければならないことである。すなわち、特開２００３−３１７０８３に挙げられた図５のような事例においてはデータがあらかじめ３種類の分類結果（α・β・γ）に整形されて出力されている。しかしながら、このようなデータベースの構築は一部の事象に対しては以下に挙げる２つの理由により困難となる。１つめは対象となるデータベースが巨大な場合であり、このような場合、データベース中のすべての事例に対し過誤のない正確な分類を行うことは、人間が行う分類に対する正誤判断のコストの問題から容易ではない。２つめは分類の対象となる事例を絶対的な基準により分類することが困難な対象である場合である。例えば、コンピュータログを解析する際には、特開２００１−０５６７６８が扱うハードウェア障害等のように、単一の事象から明確に障害・非障害分類が可能になる事象を対象として、あらかじめアプリケーションプログラムが表示するメッセージを収集し、そのメッセージ内容に応じて分岐処理を行うような場面が想定されるだけではなく、コンピュータの不正利用に代表されるように特定のユーザの使用頻度あるいはその使用用途から逸脱した事象の特定等の用途においては、こうした事象は絶対的な基準だけでは明確には分類できず、ユーザの履歴、使用パターン等の複数の事例からの共起および差異を考慮した分類処理が必要となる。すなわち、データベース中の空間全体に一様に出現するという特徴を持つ事例を通常事例とし、データベース中のある特定の部分空間のみに出現するという特徴を持つ事例を例外事例とするとき、その通常事例と例外事例とを分類する処理である。
【００１３】
【非特許文献１】Koza, J., Genetic Programming: On the Programming of Computers by means of Natural Selection, MIT press, 1992
【特許文献１】特開２００３−３１７０８３
【特許文献２】特開２００５−２４２７３９
【特許文献３】特開２００１−０５６７６８
【００１４】
さらに従来発明においては、図５に示したように分類の対象となるデータベース中の事例が整形された入力形式、すなわち事例を構成する数値および文字の並びに含まれる信号の内容に応じて分類された形式で構築されていることが前提となっており、コンピュータログあるいは自由記述書類のように様々な未整形の入力形式を扱うことが出来ないという問題がある。この点については、特開２００１−０５６７６８においても同様に問題となる。すなわち、あらかじめアプリケーションプログラムが表示するメッセージを収集し、そのメッセージ内容に応じて分岐処理を行う特開２００１−０５６７６８の手法においては、そのメッセージ内容があらかじめ収集されていないときには障害に応じた処理が出来ないという問題である。したがって、多数のアプリケーションに対して、あるいは対象を拡張して人が生成する何らかの入力のようにメッセージ内容が限定されない対象のことは考慮されていないため、従来手法は限られた事例に対してのみに適用できる手法であると言える。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
遺伝的プログラミングを用いたデータベースからのルール抽出を行う手法は、複数のルールを獲得するための分類済みの訓練事例をあらかじめ何らかの方法により定めておく必要があった。しかしながら、対象となるデータベースが巨大な場合にはデータベース中のすべての事例に対し過誤のない正確な分類を行うことは困難であり、また、分類の対象となるデータが絶対的な判断基準だけでは明確に分類を行うことが困難な対象である場合にも、同様に分類課題を行った上、訓練事例とすることは容易ではない。そこで本発明は、データベース中の空間全体に一様に出現するという特徴を持つ事例を通常事例とし、データベース中のある特定の部分空間のみに出現するという特徴を持つ事例を例外事例とするとき、通常事例のみが存在し例外事例は存在しないという条件の下で事例検出の基準となるあらかじめ与えられた部分空間と、着目する部分空間のみに出現するという特徴を持つ例外事例の検出対象の部分空間の二空間を当該データベース中に任意に定義し、事例を構成する各信号とその信号が取り得る数値および文字列を表す終端節点およびそれらの数値および文字の包含関係や論理積を表す関数を内部節点として組み合わせ連結したグラフ理論における木構造を示すルールを用いることにより、訓練事例を用意することなく精度の高い分類システムを構築することを目的とする。さらに未整形の入力、すなわち事例を構成する数値および文字の並びに含まれる信号の内容に応じて分類された種類の一部または全部が未知である事例の集合が与えられその事例を信号の内容に応じて分類された種類ごとに取り扱うことが不可能である入力にも対処できるよう、遺伝的プログラミングを用いた入力データの整形処理を行うことを目的とする。
【課題を解決するための手段】
【００１６】
既存の事例集合からなるデータベースまたは既存の事例集合に時間の経過とともに新たな事例が付加されるデータベースであり、かつデータベース中のある特定の部分空間のみに出現するという特徴を持つ事例であるか否かについて分類する情報を持たない未分類のデータベースにおいて、データベース中の空間全体に一様に出現するという特徴を持つ事例を通常事例とし、データベース中のある特定の部分空間のみに出現するという特徴を持つ事例を例外事例とするとき、通常事例のみが存在し例外事例は存在しないという条件の下で事例検出の基準となるあらかじめ与えられた部分空間と、着目する部分空間のみに出現するという特徴を持つ例外事例の検出対象の部分空間の二空間を当該データベース中に任意に定義し、事例を構成する各信号とその信号が取り得る数値および文字列を表す終端節点およびそれらの数値および文字の包含関係や論理積を表す関数を内部節点として組み合わせ連結したグラフ理論における木構造を示すルールを用いて、事例の信号が持つ特徴を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ルールを自動で探索する手法を用いるデータベース解析の機能を備えたデータベース装置を有する。
【００１８】
請求項１記載の抽出された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ルールを用いた推論結果の精度に基づいて決定された優先度が付与される。その結果として、検出精度およびルールの可読性の高い、事例の例外判定装置を有する検出システムを構築することが可能である。以下でその詳細および実施例を示す。
【００２５】
本発明においては、データベース中の空間全体に一様に出現するという特徴を持つ事例を通常事例と呼び、データベース中のある特定の部分空間のみに出現するという特徴を持つ事例を例外事例と呼ぶこととする。例外事例は人間が手動で分類を行うのではなく、通常事例のみが存在し例外事例は存在しないという条件の下で事例検出の基準となるあらかじめ与えられた部分空間と、着目する部分空間のみに出現するという特徴を持つ例外事例の検出対象の部分空間の二空間を当該データベース中に任意に定義し、その二空間の特徴の差異をもとに例外事例を判定する。例えば、二空間の例としてシステムの運用例を挙げる。図６に示したように、システムの運用開始時には設定ミス等が生じるため、システムは不安定状態にあることが多い。しかし、時間の経過とともに設定ミス等は減少していき、安定状態となる。さらに運用を続けていくと、ハードウェア障害や不正アクセスが起こるため、再び不安定状態となる。すなわち、システムはこれらの２つの状態を繰り返すため、これらの状態を二空間として例外事例検出のための基準となる部分空間および検査対象となる部分空間と定義し、その差異に着目することにより、ハードウェア障害または不正アクセスに代表される例外事例を発見することが可能となる。例えば、図６では、「Successfully Booted.」というメッセージはすべての空間に出現しているため差異を検出することは出来ないが、「Can not access」というメッセージは不安定状態を示す部分空間だけに出現しているため、安定状態を示す部分空間との比較により差異を検出し、例外事例だと判断することができる。
【００２６】
上記の例外判断を遂行するためには、例外事例検出のための基準となるデータベースおよび検査対象となるデータベースに含まれる各事例が複数の属性を持つ必要がある。ここでは、例外事例検出のための基準となるデータベースおよび検査対象となるデータベースに含まれる全事例集合において、任意の部分集合の事例が満たす属性の関係のルールを表す木構造プログラムを持つものをエージェントと呼ぶ。データベースから複数のルールを抽出するために、このエージェントが複数存在するシステム（マルチエージェントシステムと呼ぶ）を用いる。全事例集合から、複数の、同一の特徴を有する部分集合が選択され、複数のエージェントが別々の部分集合からルールを抽出することで、事例集合中に含まれる複数のルール、すなわち上記の例ではハードウェア障害検出等のためのルールを抽出することができる。
【００２７】
上記のマルチエージェントシステムによる複数のルール抽出処理を実現するにあたり、事例集合をいくつの部分集合へどのように分割してルールを抽出するかを決定する必要がある。本発明では、抽出すべき全例外事例の属性関係を表すのに必要なルール数および木構造プログラムで表されたルールを、１個体の表現方法や遺伝操作の方法を変更した遺伝的プログラミングを用いて獲得する。
【００２８】
複数のエージェントが同一の事例部分集合からルール抽出を行う場合、それらのエージェントは同一の木構造プログラムを持つ。このように同一の木構造プログラムを持つエージェントの集合をグループと呼ぶ。あらかじめ用意したエージェントは、どれか１つのグループに所属することになる。本発明で用いる遺伝的プログラミングは、エージェントがいくつのグループに分かれそしてどのエージェントが同じグループに所属しているかというグループ構造と、各グループが持つ木構造プログラムを進化の過程で共に探索する最適化手法である。この最適化手法をルール抽出処理に応用すれば、抽出すべき全例外事例の属性関係を表現するのに適切な数だけ異なるルールを生成することができる。また獲得されたグループ構造を解析することにより、例外事例の属性関係の表現に必要なルール数、そして各ルールを満たす事例の出現頻度およびルールを用いた推論結果の精度に基づいた各ルールの優先度に関する知識を獲得できる。
【００２９】
本発明では各エージェントのグループが持つ木構造プログラムの集合を、遺伝的プログラミングにおける１個体としてみなす。すなわち、遺伝的プログラミングの各個体は、マルチエージェントシステムを表す。図７は４つのエージェントをルール抽出に用いた場合における遺伝的プログラミングの１個体の例を示している。この図では、エージェント１とエージェント２が１つのグループ（７１）であり、またエージェント３とエージェント４が別のグループ（７２）を形成している。その結果として、この個体は各グループ用に２つの木構造プログラム（７３、７４）を持つ。すなわち、この個体は２つのルールを持っていることになる。
【００３０】
以下で、本発明で用いる遺伝的プログラミングの具体的な処理手順について述べる。図８は本発明による最適化の流れである。はじめに、初期個体集団を生成する（８１）。図９はある１つの初期個体の生成手順を示したものであり、また図１０は本発明における個体集団の概念図である。図９に示した処理を行うことにより、初期個体におけるグループの分割数および各グループへのエージェントの配分はランダムに決定される。図９の処理を初期世代に用いる個体数だけ繰り返すことにより個体集団を作成する。その結果、個体集団は図１０のような多様なグループ構造を持つ。なお、図１０における個体（１０１）は、図７で示した個体を簡略化して描いたものである。
【００３１】
本発明で用いる遺伝的プログラミングの遺伝操作において、選択（８３）、突然変異（８６）は通常の遺伝的プログラミングにおける処理と同様であるが、交叉（８５）が大きく異なる。また新たな遺伝操作としてグループ突然変異（８４）が追加される。
【００３２】
まずは交叉方法の説明を行う。ある２つの個体を交叉する際の具体的な処理手順を以下のステップ１からステップ３に示す。
【００３３】
ステップ１：交叉を行う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')の要素であるエージェントが同一の木を参照するように、エージェントの移動が起こる。図１２は２つの親個体（１２１と１２２）において、エージェント１が参照する木同士で交叉した場合を表している。ステップ３へ移る
【００３８】
ステップ３：木TとT'において、それぞれの木のノードの中から1点がランダムに選択し、そのノード以下の部分木を２個体で交換し、交叉が完了する。
【００３９】
以上のように、交叉は任意の同じエージェントが参照する木構造プログラム同士で行われる。そして交叉に使用される木を参照するエージェント集合の関係に応じてグループ構造を変更する。
【００４０】
またグループ突然変異（８４）は、個体集団がただ１つのグループ構造へ収束することを防ぐために用いる。グループ突然変異では、1個体を構成する各エージェントに対してグループ突然変異率と呼ばれる生起確率に基づいて、あるエージェントを任意に選択されたグループへ移す操作を行う。この操作は交叉によるグループ構造の変化を促進するものとして働くため、交叉の前に行われる。
【００４１】
上記の操作を用いて世代交代を繰り返すことにより、個体集団はグループ構造を徐々に好ましいものに近づけながら解の探索を行う。
【００４２】
図１３、図１４、図１５は本発明の一実施例の構成図である。これらの図は、入力となるデータの各事例に対して、ルールによる特徴表現が可能となるように前処理を行い、信号の持つ特徴に応じてタグ付けされた事例に変形するシステム（システム１：図１３）と、前処理により得られた情報を用いて、例外事例だけを検出可能なルールを抽出するシステム（システム２：図１４）と、抽出されたルールにより例外事例を判定するシステムを示している（システム３：図１５）。システム１およびシステム３については後述する。
【００４３】
システム２では、前処理によりタグ付けされた全事例集合に対して、遺伝的プログラミングを用いたルール抽出処理を適用する。進化させた個体集団中の最良個体が持つ複数のルールを事例が例外事例に該当するかどうかを判定するためのIF-THENルールとする。また本発明を用いることにより、獲得された複数のルールには、そのルールが成立する頻度やそのルールを用いた推論結果の精度に基づいた優先度が付与される。
【００４４】
まず、例外事例検出の基準となるデータベースおよび検査対象となるデータベースに含まれる各事例は、事例の特徴を表す最大n個の属性（X1、X2、・・・、Xn）を明確に与えられているものとする。また例外事例検出の基準となるデータベースの各事例は、全て例外事例ではない。また検査対象となるデータベースは、検出すべき例外事例と例外ではない通常の事例が混在している。また、検査対象となるデータベースにおいて各事例が例外事例に該当するかどうかの知識は事前に与えられない。
【００４５】
ある入力事例が与えられたときに、その事例が例外事例であるか否かを判定するためには、例外事例のみが満たすべき論理式を求めなければならない。この論理式は、ある属性項目とその項目に設定された情報の組をAND結合した式であり、例えば次の式数1ように表される。この式は、属性X1に情報A、属性X2に情報B、属性X3に情報Cが設定されている事例は例外事例とみなす、ということを示している。
【数１】
2008059234.tif 000003
【００４６】
この場合、例外事例に対しては論理式が真（True）を返し、通常事例に対しては論理式が偽（False）を返さなければならない。よってこの式は、論理式が成立するならばその事例は例外に分類されることを示すIF-THENルールとなっている。このIF-THENルールの前件部にあたる論理式は図１６のような木構造プログラムで表現される。
【００４７】
上で述べた例外事例のみが満たすIF-THENルールの抽出方法について述べる。図１７は各個体の適応度の評価方法を、図１８はその概念図を表している。本発明で用いる遺伝的プログラミングの個体における複数の木（Ｔ１、Ｔ２、・・・、ＴＧ：Ｇはグループ数を示す）は、各々論理式を表している。例外事例と例外でない通常の事例が混在する事例集合から各事例をシステムに入力する。その入力データに対して、適応度の評価対象の個体が持つ各木の論理式が成立するかどうかを計算する。その各木の計算結果をＯ１、Ｏ２、・・・、ＯＧとする。図１８のデータ２に示すように１個体が持つ複数の論理式の内で１つでも真（T）となれば、その入力データの例外事例であるとみなされる。また、図１８のデータ１のように１個体が持つ複数の論理式が全て偽（F）を返せば、その入力データの分類結果は例外事例ではないとみなす。検査対象のデータベースからできるだけ多くの例外事例を検出することが目標となるため、例外事例検出の基準となるデータベースの各事例に対しては全ての木が偽を返し、検査対象のデータベースに対してはできるだけ多くの事例に、個体中の複数の木の中の少なくともいずれか１つが真を出力するように最適化を行う。
【００４８】
ルール抽出対象ではない、例外事例検出のための基準となるデータベース中の通常事例に対して、論理式が誤って真を返す場合、そのルールを持つエージェントの数に応じてペナルティとしてその個体の適応度を減じることとする。これにより通常の事例を例外と誤認する頻度が高いグループへのエージェントの配分は抑制される。
【００４９】
また、各エージェントがルール抽出のために担当する例外事例の数という観点では、各エージェントの負荷という概念が生じる。これは各グループが持つルールの採用回数および各グループに所属するエージェント数から計算される。各ルールの採用回数は、検査対象となるデータベースの事例に対して、そのルールが真を返した場合にカウントされる。採用回数のカウントの際は、図１８のデータ３のように、複数の木が真を出力した場合は、その中で最もエージェント数の多いグループのルールを採用することとする。このとき、あるエージェントaがグループgに属しているとすると、このエージェントの負荷Waは、グループgの採用回数Cgとグループgに所属するエージェント数Ngを用いて次の式数２のように計算される。
【数２】
2008059234.tif 000004
【００５０】
このように計算される各エージェントの負荷を均一化することで、採用回数が多いルールを持つグループには多くのエージェントが配分されるようになり、採用回数が少ないルールを持つグループのエージェント数は少ないものとなる。各ルールを参照しているエージェントの数を見れば、抽出された各々のルールが使用される頻度、すなわち各ルールが例外事例の性質を表すルールとしてどの程度一般的なものかという重要な知識が得られる。このように各ルールを参照するエージェントの数は、そのルールに一致する事例がデータベース中に存在する割合とルールを用いた推論結果の精度に基づいて決定され、各ルールの優先度を表すことになる。
【００５１】
上記の要求を満たすため、適応度は以下の式数３で計算される。この適応度が増加するように個体集団を進化させることによって、例外事例のみが満たすIF-THENルールを抽出する。
【数３】
2008059234.tif 000005
【００５２】
ここでNnorm、Nerrはそれぞれ、例外事例検出のための基準となるデータベースに含まれる事例数、検査対象となるデータベースに含まれる事例数を表す。またHnormは例外事例検出のための基準となるデータベースの全事例のうち個体の持つルールのいずれかが真を返した事例数であり、Herrは検査対象となるデータベースの全事例のうち個体の持つルールのいずれかが真を返した事例数である。fault_agentは例外事例検出の基準となるデータベース中の事例に対してあるルールが真を出力して誤認した際に、そのルールを持つグループに所属するエージェント数を表す。そのため、式数３の第２項は例外でない事例に対して誤って真と判定する際にそれを支持する平均エージェント数を表している。また、Vwは全エージェントに関する負荷の分散である。これらをβ、δで重み付けした和を適応度とする。また冗長なグループの分割を抑制するために、個体が持つグループ数Gの増加に応じてペナルティ係数γ（ただしγ＞１）の（G-1）乗が適応度に乗算される。
【００５３】
上記の適応度を用いた最適化により、例外事例に対してはいずれかの木が真を返し、通常の事例には偽を返すようになる。また、そのルールが検査対象となるデータベース中の事例に真を返す頻度が高い程多くのエージェントが配分される。例外事例検出の基準となるデータベースに対して誤認する頻度が高いグループへのエージェントの配分は抑制される。そのため、IF-THENルールを参照するエージェントの数がそのルールの優先度を表し、IF-THENルールが例外事例の検出対象の部分空間の事例に対して成立する頻度が高いほどそのIF-THENルールの優先度が上がり、IF-THENルールが例外事例検出の基準となる部分空間の事例に対して成立する頻度が高いほどそのIF-THENルールの優先度が下がることになる。このことは、所属エージェント数が多い程よく使用され、かつ精度の高い典型的な判定ルールであり、少数のエージェントしか所属していないルールは稀に現れる例外的データに対する判定ルールであることを示している。
【００５４】
例外事例の検出用に獲得されたルールは、それ以降、例外事例であるか否かの分類に関する情報を持たない未分類の事例に対する例外事例検出システムに利用する（システム３：図１５）。例外事例であるか否かの分類に関する情報を持たない未分類の事例に対して判定を行う際は、図１８と同様に、これまでに抽出した例外判定ルールを適用する。その結果、判定対象の事例に対して抽出された全てのルールが偽を返す場合は、その例外事例でないことが分かる。抽出したルールのうち、１つでも真を返すものがある場合は、例外事例とみなす。
【００５５】
続いて、例外事例検出の基準となるデータベースおよび検査対象となるデータベースに含まれる各事例を構成する数値および文字の並びに含まれる信号の内容に応じて分類された種類の一部または全部が未知である事例であり、事例の特徴を表す最大n個の属性（X1、X2、・・・、Xn）を明確に与えられていない対象に対して、本発明の対象を拡張する。この拡張はシステム１によって行われる（システム１：図１３）。
【００５６】
各事例を構成する数値および文字の並びに含まれる信号の内容に応じて分類された種類の一部または全部が未知である事例であり、事例の特徴を表す最大n個の属性（X1、X2、・・・、Xn）を明確に与えられていないデータによってデータベースが構成される例として、コンピュータログのサンプルを挙げる（図１９）。遺伝的プログラミングによるルール抽出処理では、各個体が持つ木構造プログラムはルールを表す。データベース中の各事例は、事例中に出現する特徴量やその出現箇所により何らかの種類に分類可能なデータ構造を表現しているため、ルール表現にこれらの構造を有効に利用することが望ましい。しかし、このようなデータ構造の種類の一部または全部が未知である事例をそのままの形式で用いると、データ構造を利用したルール表現が行えないため、適切なルール表現が困難である。また、データ構造を利用することができれば、木構造を表現するために必要な終端記号を効率的に設計できると考えられる。したがって、データ構造の種類の一部または全部が未知である事例を解析し、データの種類を示すタグにより構造化する前処理を行う。まず初期のデータ解析のための特徴付与データベースを最低限与えることとする。ただし、この初期の特徴付与データベースを与える理由は解析時間短縮のためであり、空の状態から実行することも可能である。この特徴付与データベースは、図１９の例においては区切り記号が「コンマ」であり、８個のフィールドに分割されていることに着目して与えられる。ここで、第２フィールドに記された文字列「2005/11/13」は、『１バイトの数字の４個の繰り返し、記号（スラッシュ）、１バイトの数字の２個の繰り返し、記号（スラッシュ）、１バイトの数字の２個の繰り返しによる区切り』という表現が可能である。そして、この表現を特徴付与データベースに登録し、入力信号中に同種の文字列、例えば「2006/08/08」のような類似表現が出現した際には、例えばXML表現を用いて、「<TAG2>2006/08/08</TAG2>」という変換出力を行うことにより事例の変換を行う。なお、“TAG2”というタグの命名法については、必ずしも“DATE”のようにデータの内容に依存して命名することも可能であるが、命名に人間の手が必要になると管理が複雑になる可能性があるため、本発明においては単に番号として命名を行う。
【００５７】
こうした表現は単一の入力形式にしか対応できないため、文字列「2005-11-13」という別の入力形式を有する事例には対処できないため、本研究においては遺伝的プログラミングによる突然変異を用いて変換表現の変更を行い、『１バイトの数字の４個の繰り返し、記号（ハイフン）、１バイトの数字の２個の繰り返し、記号（ハイフン）、１バイトの数字の２個の繰り返しによる区切り』という新たな変換表現を得ることにより、多様な入力への自動適応を可能にする。さらに、こうした変換表現を正規表現を用いて表現することにより、より多様な入力への自動対応を可能にする。単純に上記２つの表現を正規表現化した場合には、「(d){4}(/|-){1}(d){2}(/|-){1}(d){2}(/|-)」と表現されるが、さらにこの表現に遺伝子操作が行われることにより、例えば「(d){4}.{1}(d){2}.{1}(d){2}.*」と進化することも可能であり、同一の正規表現により、「2005年11月13日」という新たな入力書式にも同様に対処することができる。
【００５８】
ただし、各入力信号を適切に分割するように進化を行うことが必要となる。例えば、「(d)+(/|-){1}(d)+(/|-){1}(d)+」のように進化が行われると、図１９中の第１フィールド（この例では日付）と第２フィールド（この例では時刻）の内容を同時に指定することになるため表現力が低下する。したがって、このような正規表現は進化の過程では現れる可能性があるが最終的な世代では残らないようにする。以上のような手続きにより、本発明は、適応的な知識に基づいた動的な解析処理を行うことを可能とする。
【００５９】
しかしながら、この手法では英文字の繰り返しが入力信号として現れるときに、フィールドを分割することが困難になり、収束に至るまでに相当の時間を要するという問題がある。例えば、「[a-z]+」という正規表現は「localhost」というホストに関連する名前と「error」のようなメッセージに関連する英単語を区別できないため、同一の入力特徴と判断され、相当数の遺伝子操作が繰り返されることになる。そこで本発明ではホスト名に関するデータベース等の検索手段を“ifconfig”といったコマンド等によってあらかじめ用意し、大規模なデータベースを用いた照合過程を置くことにより遺伝子操作を減らす。
【００６０】
実施例として、本発明を計算機管理分野におけるログファイルからの機器障害検出およびセキュリティ監視のための知識獲得に適用した。実験のために用意されたログは、１台のサーバから集められた複数のログファイルであった。図２０にこのログファイルに記載された、事例としてのメッセージの例を示す。また、ログファイルに記載された各メッセージは、前処理によりタグ付けされている。図２１に、図２０に記載したメッセージにタグ付けした例を示す。なお、実際のタグは前述のように番号で表されているにすぎないが、ここではわかりやすくするため、時刻、ホスト名、説明といったラベルを用いて表示している。任意の二空間として、より定常状態に近いと考えられる通常運用時のファイル（３２２個。４８２６９行）と、様々な不具合が含まれていると考えられる運用に至るまでの試行期間のファイル（３２２個。１７８０４行）を用意した。遺伝的プログラミングの記号としては、図２２に示す終端・関数記号を用いた。ただし、記号の使用には次のような制約を設ける。and記号の引数に直接終端記号がくることはなく、また、includeの第１引数arg0には時刻、ホスト名などの属性項目が、第２引数arg1には前処理により作成した各単語リストの要素数の最大値をNとして、離散値０、１、２、・・・、N-1のいずれかが入るとする。この条件を満たさないような交叉、突然変異は行わないとした。遺伝的プログラミングの個体は３００個用意し、各個体は５０エージェントから構成されるように実験を行った。
【００６１】
実験の結果、エージェントは１６グループに分割され、１６の判定規則を獲得した。また最良個体は、エラーが含まれていると考えられる試行期間のログから３７２行のメッセージを同定した。しかし反対に、運用状態のログからは何も同定しなかった。図２３に獲得されたルールの一例を示す。これらの規則は、優先度を意味する支持エージェントの個数によって並び替えられている。なお、規則中に現れるタグは実験により２５個獲得され、その名前については遺伝的プログラミングの処理においては不要ではあるが、実験結果としてルールを直感的にわかりやすく説明するという理由で、命名を処理後に行った。例えば、この図で２番目のルールは『何らかの説明が書かれた<EXP>と名付けられたタグ付けが行われており、そのタグの中に文字列「hostthere.ne.jp/A/IN」を含んでいる』ルールである。このルールの記述だけでは何を意味するかわかりづらいが、実際のログファイル中から当該文字列を検索した結果（図２４）を見れば明らかなように、実際のログでは非常に重要なDNS関連のメッセージ、すなわち、「unexpected RCODE(SERVFAIL)」を含んでおり、障害検出に成功していることがわかる。ここで重要な点は、本発明においてはあらかじめ障害分類を行っておらず、障害に関する知識なしに上記の障害検出に成功したことである。したがって本発明の実施の際には、高度に訓練されたエキスパートでなくとも運用が可能であることを示している。
【００６２】
次に、試行期間のログから抽出した３７２個のメッセージデータに対し、どのルールがどれだけ採用されたか調べた。その結果、獲得した１６のルールのそれぞれで、１５２、 ７２、 １３、 ４０、 ３、 ３２、 １０、 ９、 ４、 ２、 １６、 ９、 ３、 ３、 ３、 １のメッセージを同定可能であった。例えば、図２４の最初のログは、図２３の２番目のルールに関連した出力であり、そのメッセージ数が７２個、すなわち試行期間のログ中に７２回出現することになる。このことから、多くのエージェントに支持されるルールが、試行期間のログ中により多く出現しており、適切に上位ランクルールとして抽出が行われ、またそのルールを用いてログ中から重要箇所を検出可能であることがわかる。
【産業上の利用可能性】
【００６３】
本発明は、データの計測やその計測結果に基づいた分類の判定にノイズや人間の判断・嗜好を伴うような事例が蓄えられたデータベースに有効であるだけでなく、事例数が膨大等の理由により教師信号を人手により付与することが容易でないデータベースに対しても有効である。このようなデータベースは、同一の入力であっても異なる分類結果を持つ事例が存在することや、逆に、同一の分類結果を示す複数の事例が単一のルールで表現できない、絶対的な判断基準を用いた分類処理が行えないといった特徴を有している。
【００６４】
本発明の応用例としては、医療分野における疾患の診断システム、販売事業における顧客の購買履歴からの知識獲得、気象データの時系列変動に基づく気象予測、株価変動予測、コンピュータログ解析・自動障害検出システムなどといった入力形式が比較的容易に決定できる例から、症例入力・自動分類システム、症例自動判定システム、医療ミス指摘システムといった自由入力に対応する例が挙げられる。
【００６５】
例えば医療分野では、患者の診断結果がカルテに記されている。しかしながら、その記述形式については医師によって変動があり、決定的ではない。そのため、カルテのどの部分が症状であり、どの部分が検査結果であるか決定することが重要であり、症例入力・自動分類システムによって入力形式を整形することが必要となる。また、このような入力形式が一致するデータを用いることにより機械学習が可能となるが、診断結果は医師の経験によるあいまいさが含まれるデータでもあり、診断規則は単一のルールで表現できるとは限らず、また、複数の病状を発症していることもあり、単一のルールだけですべてが表現されているか疑問である。本発明においては、複数のルールが獲得できるため、症例自動判定システムに適用が容易である。さらに、本発明においては任意の二空間を対象としその相違から例外事象を判定することが可能であるため、新たな診断の際に含まれる可能性の有る医療ミスの指摘を行うことも可能である。医療分野においては多数の患者が訪れることにより医療関係者が多忙を極めており、投薬の指示ミス等が生じやすくなっている。本発明においては、任意の二空間の一方をこれまでに蓄積した全データ、もう一方を現在の患者データと設定することにより、差異があるかないかを判定する。もし投薬指示ミス等によりこれまでと違う薬が指定された場合には二空間の差異により新たなルールが抽出され、ミスを指摘することが可能である。また任意の二空間を同一患者の過去データと現在のデータと定義することにより、平熱の高い人とそうでない人によって診断内容を変えることもできるし、同一患者で投薬内容が大きく変わった場合等にはその内容を指摘することもできる。本発明においては、訓練事例に対し正解となるデータを与えていないため、このような弾力のある運用が可能であり、様々な用途に適用することができる。
【図面の簡単な説明】
【００６６】
【図１】本発明の概念図
【図２】木構造プログラムの例
【図３】遺伝的プログラミングの処理の流れ
【図４】遺伝的プログラミングにおける交叉の例
【図５】従来発明における事例と教示信号の例
【図６】例外事例検出のための基準となるデータベースと検査対象となるデータベースシステムを区別するための運用パターンの例
【図７】本発明における遺伝的プログラミングの１個体の概念図
【図８】本発明における遺伝的プログラミングの処理の流れ
【図９】本発明における遺伝的プログラミングの初期個体の生成方法
【図１０】本発明における遺伝的プログラミングの個体集団の概念図
【図１１】本発明における遺伝的プログラミングの交叉（グループの分割が発生する例）
【図１２】本発明における遺伝的プログラミングの交叉（グループの統合が発生する例）
【図１３】本発明の実施例の構成図１：システム１：変換機能
【図１４】本発明の実施例の構成図２：システム２：抽出機能
【図１５】本発明の実施例の構成図３：システム３：判定機能
【図１６】IF_THENルールの前件部となる論理式の例
【図１７】例外事例が満たすIF_THENルールを抽出する際の各個体の適応度の評価方法
【図１８】各事例が例外事例に該当するかどうかの判定方法の概念図
【図１９】ログデータの例１
【図２０】ログデータの例２
【図２１】タグ付けされた事例の例
【図２２】ログファイル中の例外事例を検出するためのIF_THENルールを構成する終端・関数記号
【図２３】ログファイル中の例外事例の検出ルール
【図２４】ルールにより検出された例外事例の例
【符号の説明】
【００６７】
７１  エージェント１と２からなるグループ
７２  エージェント３と４からなるグループ
７３  グループ７１が参照する木構造プログラム
７４  グループ７２が参照する木構造プログラム
１０１  本発明における遺伝的プログラミングの１個体（図７の個体を簡略化したもの）
１１１  交叉に用いる親個体の１つ
１１２  符号１１１が指す個体と交叉するもう一方の親個体
１２１  交叉に用いる親個体の１つ
１２２  符号１２１が指す個体と交叉するもう一方の親個体
【図２】
2008059234.tif 000006
【図３】
2008059234.tif 000007
【図４】
2008059234.tif 000008
【図５】
2008059234.tif 000009
【図７】
2008059234.tif 000010
【図８】
2008059234.tif 000011
【図１０】
2008059234.tif 000012
【図１１】
2008059234.tif 000013
【図１２】
2008059234.tif 000014
【図１６】
2008059234.tif 000015
【図１７】
2008059234.tif 000016
【図１８】
2008059234.tif 000017
【図２２】
2008059234.tif 000018
【図１】
2008059234.tif 000019
【図６】
2008059234.tif 000020
【図９】
2008059234.tif 000021
【図１３】
2008059234.tif 000022
【図１４】
2008059234.tif 000023
【図１５】
2008059234.tif 000024
【図１９】
2008059234.tif 000025
【図２０】
2008059234.tif 000026
【図２１】
2008059234.tif 000027
【図２３】
2008059234.tif 000028
【図２４】
2008059234.tif 000029