(57)【要約】【課題】大規模、多様データ、ノイズや、不完全なデータからもルールの発見が可能であり、実世界の問題に対して有効なデータマイニング手法を提供することが目的である。【解決手段】一般化分布表（ＧＤＴ）とラフ集合（ＲＳ）理論の組み合わせからなり、ロジック、集合、確率の理論の全てにまたがる手法にかかる。ＧＤＴは、データの不完全性・曖昧性と発見されたルールの強さを評価する確率基準を作るために用いられ、ラフ集合理論は、ルールの抽出や、強いルールの中からすべての実例をカバーする最小ルール集合を絞り出すために用いられる。【選択図】図６
2004213463.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の条件属性のそれぞれに対応するｎ個の条件属性値の組み合わせと、前記組み合わせに関連づけられた１個以上の決定属性にかかる決定属性値とを有する複数の実例から、一の決定属性値と相当因果関係を有するｍ個（ｎ＞ｍ）の条件属性値の組み合わせとしてのルールを発見するためのデータ処理方法であって、
決定属性値が異なる二つの前記実例について、前記条件属性値の異なる前記条件属性を抽出するステップと、
抽出された前記条件属性に関して論理演算を行い、ルールを導出するステップと、
を含む、データ処理方法。
【請求項２】
ｍ個の条件属性値の組み合わせを満たしうる可能な実例の数と実際にデータ処理に使用した実処理実例の数とを比較した第一の指標により、前記ルールの強さを評価するステップを含む、請求項１のデータ処理方法。
【請求項３】
前記一の決定属性値と関連付けられるｍ個（ｎ＞ｍ）の条件属性値の組み合わせを具備する実処理実例の数と、前記一の決定属性値以外の決定属性値と関連付けられるｍ個（ｎ＞ｍ）の条件属性値の組み合わせを具備する実処理実例の数とを比較した第二の指標により、前記ルールの強さを評価するステップを含む、請求項１または請求項２のデータ処理方法。
【請求項４】
それぞれの条件属性値について予め定められた順序を設定するステップと、
それぞれの前記条件属性値を比較し、前記順序との整合性に関連付けて指標化するステップと、
を具備する処理を行ったデータを前記実例として用いる、請求項１ないし請求項３のデータ処理方法。
【請求項５】
ｐ個（ｎ＞ｐ）の前記条件属性値を特定し、ｎ−ｐ個の前記条件属性値を一般化した前記条件属性値の組み合わせを設定し、前記一般化した前記条件属性値の組み合わせに該当しうるｎ個の前記条件属性値の組み合わせの数ｑを導出し、設定された一般化した条件属性値の組み合わせに該当する特定の前記ｎ個の前記条件属性値の組み合わせが現れる確率を１／ｑとして扱う、請求項１ないし請求項４のデータ処理方法。
【請求項６】
実世界に存在する背景情報を参酌して、前記確率を修正するステップと、
をさらに含む、請求項５のデータ処理方法。
【請求項７】
請求項１ないし請求項６のデータ処理方法にかかるステップを有する、データ処理プログラム。
【請求項８】
請求項１ないし請求項６のデータ処理方法にかかるステップを有するプログラムを格納したデータ処理プログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、実世界の大規模、複雑、不完全で曖昧なデータからルールや因果関係などの知識発見を可能にするデータマイニングにかかる技術に属する。
【０００２】
【従来の技術】
コンピュータの計算速度の飛躍的向上と記憶容量の大規模化並びにネットワーク環境の整備により、大量のデータの蓄積、大規模な情報（知識とデータ）の共有や再利用が可能となった。データベースに対するニーズが増加するにつれ、それらに蓄積されているデータを有効に活用し、データ群の背後にある法則や因果関係を分析／抽出する必要性が高まっている。
【０００３】
実世界のデータからｉｆ−ｔｈｅｎルールを発見する帰納学習に関する研究がこの二十年間行われ、代表的なボトムアップ法：バージョン空間（ｖｅｒｓｉｏｎ−ｓｐａｃｅ）［Ｍｉｔｃｈｅｌｌ−７７］  （非特許文献１）や  Ｂａｃｋ−ｐｒｏｐａｇａｔｉｏｎ［Ｒｕｍｅｌｈａｒｔ−８６］（非特許文献２）から、トップダウン法：Ｃ４．５［Ｑｕｉｎｌａｎ−９３］  （非特許文献３）及びラフ集合の方法［Ｐａｗｌａｋ−９１］  （非特許文献４）などまで色々提案された。
【０００４】
【非特許文献１】
［Ｍｉｔｃｈｅｌｌ−７７］  Ｍｉｔｃｈｅｌｌ，  Ｔ．Ｍ．
”Ｖｅｒｓｉｏｎ  Ｓｐａｃｅｓ：  Ａ  Ｃａｎｄｉｄａｔｅ  Ｅｌｉｍｉｎａｔｉｏｎ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｒｕｌｅ  Ｌｅａｒｎｉｎｇ”，
Ｐｒｏｃ．  ５ｔｈ  Ｉｎｔ．  Ｊｏｉｎｔ  Ｃｏｎｆ．  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，  （１９７７）  ３０５−３１０．
【０００５】
【非特許文献２】
［Ｒｕｍｅｌｈａｒｔ−８６］  Ｒｕｍｅｌｈａｒｔ，  Ｄ．Ｅ．，  Ｈｉｎｔｏｎ，  Ｇ．Ｅ．，  ａｎｄ  Ｗｉｌｌｉａｍｓ，  Ｒ．Ｊ．
”Ｌｅａｒｎｉｎｇ  Ｉｎｔｅｒｎａｌ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｂｙ  Ｂａｃｋ−Ｐｒｏｐａｇａｔｉｏｎ  Ｅｒｒｏｒｓ”．
Ｎａｔｕｒｅ  Ｖｏｌ．３２３  （１９８６）  ５３３−５３６．
【０００６】
【非特許文献３】
［Ｑｕｉｎｌａｎ−９３］  Ｑｕｉｎｌａｎ，  Ｊ．Ｒ．
”Ｃ４．５：  Ｐｒｏｇｒａｍｓ  ｆｏｒ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ｝”，
Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  （１９９３）．
【０００７】
【非特許文献４】
［Ｐａｗｌａｋ−９１］  Ｐａｗｌａｋ，  Ｚ．
”Ｒｏｕｇｈ  Ｓｅｔｓ，  Ｔｈｅｏｒｅｔｉｃａｌ  Ａｓｐｅｃｔｓ  ｏｆ  Ｒｅａｓｏｎｉｎｇ  ａｂｏｕｔ  Ｄａｔａ”，
Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ  （１９９１）．
【０００８】
表１を例に、基本的概念を示す。ｕ１，ｕ２，…ｕ６が示す各行を実例と呼ぶ。頭痛、体温、筋肉痛とインフルエンザは属性と呼ばれる。表１においては、頭痛、体温、筋肉痛の有無などに応じて、インフルエンザか否かを判断するものである。判断結果にかかる属性（インフルエンザ）のことを決定属性といい、決定属性に条件を与える属性（頭痛／体温／筋肉痛）のことを条件属性という。各欄に現れるもの（例えば、頭痛については、ｙｅｓ／ｎｏ、体温については  ｎｏｒｍａｌ／ｈｉｇｈ／ｖｅｒｙ−ｈｉｇｈ）をそれぞれの属性の値という。
【０００９】
【表１】
2004213463.tif 000003
【００１０】
「ボトムアップ法」
ボトムアップ法は遂次（ｉｎｃｒｅｍｅｎｔａｌ）学習法である。すなわち、実例が同時に入力される時だけでなく一つずつ与えられる時も概念の学習は可能である。ボトムアップ法は、効果的にデータ変更を取り扱うことができる、しかし、計算時間が長くなる。
ボトムアップ法では、各学習サイクルで１つの新しい実例をとって、その実例を使って学習された概念を修正する。全ての実例の処理が終るまで繰り返す。
代表的なボトムアップ法の一つは、離散的方法としてＭｉｔｃｈｅｌｌによって提案されたバージョン空間（ｖｅｒｓｉｏｎ−ｓｐａｃｅ）法である。バージョン空間法は状態空間の構造に依存した探索手法である。新たに正実例（インフルエンザの値がｙｅｓの実例）が与えられると、それから得られる概念、あるいはそれよりも一般的な概念が、求める概念になりうる。負実例（インフルエンザの値がｎｏの実例）が与えられると、それに対応する概念よりも特殊な要素だけが、求める概念になりうる。与えられた実例集合に対する概念はたくさんありうる。これらの概念のうち、目標とする構造のものを見出すには、問題解決における発見的探索を用いることができる。正実例から求められた一般的な概念と、負実例から求められた特殊な概念からそれぞれ出発して、遂次呈示された正、負実例により、可能な探索領域を狭めていく。求められた一般的な概念をルールと呼ぶ。
【００１１】
表１のインフルエンザの例を使って、バージョン空間法を説明する。
いま、ある対象ｕの属性を表す四つの述語
頭痛（Ｕ，  Ｘ），  Ｘ  ∈｛ｙｅｓ，  ｎｏ｝  
体温（Ｕ，  Ｙ），  Ｙ  ∈｛ｎｏｒｍａｌ，  ｈｉｇｈ，  ｖｅｒｙ−ｈｉｇｈ｝  
筋肉痛（Ｕ，  Ｚ），  Ｚ  ∈｛ｙｅｓ，  ｎｏ｝  
インフルエンザ（Ｕ，  Ｄ），  Ｄ  ｛ｙｅｓ，  ｎｏ｝  
がある。
【００１２】
これらの述語の集合で表される概念
ｕ１＝｛頭痛（Ｕ，  ｙｅｓ），  体温（Ｕ，  ｎｏｒｍａｌ），  筋肉痛（Ｕ，  ｙｅｓ），  インフルエンザ（Ｕ，ｎｏ）｝
ｕ２＝｛頭痛（Ｕ，  ｙｅｓ），  体温（Ｕ，  ｈｉｇｈ），  筋肉痛（Ｕ，  ｙｅｓ），  インフルエンザ（Ｕ，ｙｅｓ）｝
ｕ３＝｛頭痛（Ｕ，  ｙｅｓ），  体温（Ｕ，  ｖｅｒｙ−ｈｉｇｈ），  筋肉痛（Ｕ，  ｙｅｓ），  インフルエンザ（Ｕ，ｙｅｓ）｝
ｕ４＝｛頭痛（Ｕ，  ｎｏ），  体温（Ｕ，  ｎｏｒｍａｌ），  筋肉痛（Ｕ，  ｙｅｓ），  インフルエンザ（Ｕ，ｎｏ）｝
ｕ５＝｛頭痛（Ｕ，  ｎｏ），  体温（Ｕ，  ｈｉｇｈ），  筋肉痛（Ｕ，  ｎｏ），  インフルエンザ（Ｕ，ｎｏ）｝
ｕ６＝｛頭痛（Ｕ，  ｎｏ），  体温（Ｕ，  ｖｅｒｙ−ｈｉｇｈ），  筋肉痛（Ｕ，  ｙｅｓ），  インフルエンザ（Ｕ，ｙｅｓ）｝
を考える。
【００１３】
ここで、インフルエンザという属性の値がｙｅｓ，  ｎｏ  となるルールを求めるので、このインフルエンザを決定属性と呼ぶ。このとき、（頭痛、体温、筋肉痛）により構成されたバージョン空間は図１のようなグラフで表すことができる。グラフの枝は代入操作を表し、一番上の節点は最も「特殊な」概念、一番下の節点は最も「一般的な」概念を表している。  
実例ｕ１よりもっと一般的な概念は、図１の下線つきの節点である。ｕ１とｕ２は、「頭痛」、「筋肉痛」という二つの属性で値が一致しているので、これらの共通的な一般化は（ｙｅｓ，Ｙ，ｙｅｓ）である。ここのＹは変数で、｛ｎｏｒｍａｌ，  ｈｉｇｈ，  ｖｅｒｙ−ｈｉｇｈ｝のなかのどの値でもよい。ｕ１とｕ２の決定属性（インフルエンザ）にかかる値は、ｕ１がｎｏであり、ｕ２がｙｅｓであるという点で異なっているので、（ｙｅｓ，Ｙ，ｙｅｓ）はルールとして使えないということである。
【００１４】
同様に、実例ｕ３とｕ６とについて、共通の一般化を行うと、（Ｘ，ｖｅｒｙ−ｈｉｇｈ，ｙｅｓ）となる。ｕ３とｕ６の決定属性の値（決定クラス）はどちらもｙｅｓであり、同じである。従って、（Ｘ，ｖｅｒｙ−ｈｉｇｈ，ｙｅｓ）という一般化概念は、インフルエンザ＝ｙｅｓを導くルールとして、一つの候補になる。すべての実例を学習し終わった時点で、矛盾が発生しなければ、この一般化概念はルールとして抽出される。
【００１５】
「トップダウン法  （あるいは  バッチ学習）」
トップダウン法では、一度、全てのデータを分析し、データに基づく概念を求めようとする。Ｃ４．５とラフ集合は典型的なものである。
Ｃ４．５は上から下へ、いわゆる、トップダウン・モードで決定木を構成して、枝を切り取るにより、ルールを発見する。木の構成は、ルート節点の選択から始まる。各属性を一つずつ、木のルート節点に当てはめてみる、選出された最も適切な属性を、ルート節点として扱う。一旦ルート節点が決めたら、実例は、この節点によって分類される。分類された各グループをサブ木として、上述の操作を繰り返す。
【００１６】
前述のインフルエンザの例を使って、Ｃ４．５の木の構造を図２により説明する。まず、３つの属性の評価で、「体温」は最も適切な属性と評価され、ルート節点となる。体温に基づく分類は体温＝｛ｎｏｒｍａｌ｝と体温＝｛ｈｉｇｈ，ｖｅｒｙ−ｈｉｇｈ｝の二つのグループ分けるのが適当で、実例が二つのグループに分けられる。次に、体温＝｛ｈｉｇｈ，ｖｅｒｙ−ｈｉｇｈ｝のグループに着目すると、「筋肉痛」は最も適切な属性と評価され、結果として、以下のルールが発見される：
体温（ｎｏｒｍａｌ）  →  インフルエンザ（ｎｏ）
体温（ｈｉｇｈ，  ｖｅｒｙ−ｈｉｇｈ）∧筋肉痛（ｙｅｓ）  →  インフルエンザ（ｙｅｓ）
体温（ｈｉｇｈ，  ｖｅｒｙ−ｈｉｇｈ）∧筋肉痛（ｎｏ）  →  インフルエンザ（ｎｏ）
【００１７】
もう一つのトップダウン法はラフ集合を用いるである。ラフ集合を最初に提案したのは、ポーランドの計算機科学者  Ｚｄｚｉｓｌａｗ  Ｐａｗｌａｋ［Ｐａｗｌａｋ−８２］である。
【非特許文献５】
［Ｐａｗｌａｋ−８２］  Ｐａｗｌａｋ，  Ｚ．
”Ｒｏｕｇｈ  Ｓｅｔｓ，
Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅｓ，  Ｖｏｌ．１１  （１９８２）３４１−３５６．
ラフ集合は集合理論が、曖昧（ｕｎｃｅｒｔａｉｎ）で不完全なデータにも対応出来るように拡張したものである［Ｐａｗｌａｋ−９１，Ｓｋｏｗｒｏｎ−９２］。ある概念があった時、人間によって測定できる知識では、その概念の範囲を上下の近似でしか把握できない。ラフ集合とはそのような近似の方法を理論的に研究したものである。
【非特許文献６】
［Ｓｋｏｗｒｏｎ−９２］  Ｓｋｏｗｒｏｎ，  Ａ．  ａｎｄ  Ｒａｕｓｚｅｒ，  Ｃ．
Ｔｈｅ  ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ  ｍａｔｒｉｘｅｓ  ａｎｄ  ｆｕｎｃｔｉｏｎｓ  ｉｎ  ｉｎｆｏｒｍａｔｉｏｎ  ｓｙｓｔｅｍｓ，
Ｒ．  Ｓｌｏｗｉｎｓｋｉ  （ｅｄ．）  Ｉｎｔｅｌｌｉｇｅｎｔ  Ｄｅｃｉｓｉｏｎ  Ｓｕｐｐｏｒｔ，  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ  （１９９２）３３１−３６２．
ラフ集合で提唱された概念は大きく分けて、（１）データベースにおけるデータ集合の近似的表現および（２）その近似的表現に必要な最小限の属性の集合である縮約を求める方法、の二つである。
【００１８】
データから、ルールを発見するためのラフ集合の方法論では、データベースが決定表として
Ｔ＝（Ｕ，Ａｔ，｛Ｖａ｜  ａ∈Ａｔ  ｝，  ｛Ｉａ  ｜  ａ∈Ａｔ｝，  Ｃ，  Ｄ）
と定義される。ここで、Ｕは実例の有限集合、Ａｔはすべての属性の有限集合、Ｖａは各ａ∈Ａｔに対する値の集合、ＩａはＵｘＡｔから｛Ｖａ｜  ａ∈Ａｔ｝への写像である。ＣとＤはＡｔの二つの部分集合で、Ｃを条件属性の集合とよぶ、Ｄは決定属性の集合である。Ｃ∪Ｄ＝ＡｔとＣ∩Ｄ＝空集合である。Ｃに含まれる属性の値がすべて等しい実例の集合まとめることにより、Ｕはこれらのいくつかの集合に分類される。これをＣによる同値クラスという、Ｕ／Ｃで表す。Ｕ／Ｄも同様である。Ｕ／Ｃ，Ｕ／Ｄをそれぞれ条件クラス、決定クラスと呼ぶ。
【００１９】
決定表の行は、有限集合中の一つの実例を表す。列は、属性の集合を表す。そして、各セルは実例の対応する属性の値を表す。例えば、上記のインフルエンザデータに対しては以下のようになる。
実例の集合Ｕ＝｛ｕ１，  ｕ２，  ｕ３，  ｕ４，  ｕ５，  ｕ６｝
属性の集合Ａｔ＝｛頭痛，  筋肉痛，  インフルエンザ｝
Ｖ頭痛＝｛ｙｅｓ，  ｎｏ｝、Ｖ体温＝｛ｎｏｒｍａｌ，  ｈｉｇｈ，  ｖｅｒｙ＿ｈｉｇｈ｝、Ｖ筋肉痛＝｛ｙｅｓ，  ｎｏ｝、Ｖインフルエンザ＝｛ｙｅｓ，  ｎｏ｝
Ｉｕ１，頭痛＝ｙｅｓ、Ｉｕ１，筋肉痛＝ｙｅｓ、…、Ｉｕ６，インフルエンザ＝ｙｅｓ
条件属性Ｃ＝｛頭痛，  筋肉痛｝
決定属性Ｄ＝｛インフルエンザ｝
【００２０】
上近似と下近似はラフ集合の近似概念の重要な部分である。下近似集合ＲＸは関係Ｒを用いてＸの要素として確実に分類される集合を表す。上近似集合Ｒ＾Ｘは関係Ｒを用いてＸの要素として分類される可能性がある集合を表す。ルール発見は、下近似を探すということになる。
上近似と下近似を説明するため、表２のとおり、頭痛と筋肉痛により構成されたデータを着目する：
【００２１】
【表２】
2004213463.tif 000004
【００２２】
関係Ｒ＝｛頭痛，  筋肉痛｝
Ｒによる分類Ｕ／Ｒ  ＝  ｛｛ｕ５｝，  ｛ｕ１，ｕ２，ｕ３｝，  ｛ｕ４，ｕ６｝｝
決定属性インフルエンザ（’ｎｏ’）  の集合Ｘ１＝  ｛ｕ１，ｕ４，ｕ５｝
関係Ｒを用いてＸ１の要素として確実に分類される集合、下近似集合ＲＸ１＝｛ｕ５｝。
関係Ｒを用いてＸ１の要素として分類される可能性がある集合、Ｘ１の上近似集合Ｒ＾Ｘ１＝｛ｕ１，ｕ２，ｕ３，ｕ４，ｕ５，ｕ６｝
【００２３】
この関係は図３で表せる。関係Ｒについては、ｕ５のみが正しく分類できる。
縮約とは、決定クラスに分類することができる最小限の属性を集合させたものをいう。インフルエンザの例で属性頭痛を削除しても、表３のように、各実例は前とおりに分類される。
【００２４】
【表３】
2004213463.tif 000005
【００２５】
ここで、体温と筋肉痛は削除できない属性である。なぜならば、例えば、ｕ２とｕ４に注目すると、体温のみの値からは決定属性にかかるインフルエンザの値を一意に決定できない。筋肉痛についても同様である。よって、体温と筋肉痛が縮約になる。
縮約１＝  ｛筋肉痛，  体温｝。
同様に、表４のように、筋肉痛の属性を削除しても分類に影響はない。
【００２６】
【表４】
2004213463.tif 000006
【００２７】
しかし、表４から、さらに頭痛または体温の属性を削除したら、決定属性であるインフルエンザを一意的に決定できなくなるので、
縮約２＝｛頭痛，  体温｝。
全ての縮約に含まれる属性はＣＯＲＥと呼ばれる。この例では、
ＣＯＲＥ＝｛頭痛，  体温｝  ∧｛体温，  筋肉痛｝  ＝｛体温｝
Ｓｋｏｗｒｏｎ氏が提案した識別行列［Ｓｋｏｗｒｏｎ−９２，Ｐａｗｌａｋ−９１］を利用すると、決定表の縮約を簡単に導出できる。Ｕ＝｛ｕ１，  ｕ２，  ｕ３，…，ｕｎ｝とすると、識別行列Ｍ（Ｔ）はｎ  ｘ  ｎの行列で、その成分ｍｉｊは実例ｕｉとｕｊを異なった決定クラスに分類するための必要な属性の集合である。Ｍ（Ｔ）が対角行列、かつｍｉｉ＝空集合なので、Ｍ（Ｔ）は下三角行列、即ち、ｍｉｊ：１≦ｉ＜ｊ≦ｎで表すことができる。ｃ  ∈ｍｉｊのときの全ての属性値ｃの論理和を∨ｍｉｊで表す。すべてのｕｉ∈Ｕに関して、縮約は識別関数ｆＴ（数１）により生成される：
【００２８】
【数１】
2004213463.tif 000007
ただし、ｍｉｊ＝  空集合ならば、∨ｍｉｊ＝Ｆａｌｓｅ。
【００２９】
ｆＴの簡約化された論理和標準形中の各論理積は縮約と呼ばれる。
上記のインフルエンザの例で、識別行列を利用して、表５に示すように、縮約を求める過程を説明する。
【００３０】
【表５】
2004213463.tif 000008
【００３１】
まず、ｕ１と他の実例を区別するため、どの属性が重要なのかを分析する。ｕ１とｕ２は体温属性のみ値が異なっているので、ｕ１とｕ２を区別できるのは体温属性である。ｕ１とｕ３を区別するのも、体温属性である。ｕ１とｕ４，  ｕ１とｕ５は同じ決定クラスに属しているので区別する必要はない。ｕ１とｕ６を区別するのは頭痛と体温属性である。このプロセスは、以下の二つのステップからなる。
▲１▼  決定クラス（インフルエンザ）が異なる二つの実例に着目する
▲２▼  二つの実例中、属性値が異なる属性を抽出する。
ｕ２からｕ６は同様にすると、表６にかかる識別行列ができる：
【００３２】
【表６】
2004213463.tif 000009
【００３３】
各要素の論理積をとると、
ｆＴ＝体温∧（頭痛∨体温）∧（頭痛∨筋肉痛）∧（頭痛∨体温∨筋肉痛）∧（体温∨筋肉痛）  ＝  （体温∧頭痛）∨（体温∧筋肉痛）．
二つの縮約｛体温，頭痛｝と｛体温，筋肉痛｝が求められた。
データベースからルールや因果関係などからの知識発見／データマイニング（Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ、ＫＤＤと略記）に関する研究は開始されてから日が浅く、以上で述べた方法は理想的な実験データにたいしては，完璧な結果が得られるが、実世界のデータに対しては、対応できない。
実世界のデータは以下の特徴をもつ。
１．  大規模性
２．  不完全性（欠損データ、不完全データ）
３．  曖昧性（ノイズデータ）
４．  動的性（データの増減）
５．  多様性（連続値データと離散データの混在）
６．  背景知識の利用
従来の方法では、実世界データの問題に対しては、表７で示すように部分的にしか対応できない。
【００３４】
【表７】
2004213463.tif 000010
【００３５】
バージョン空間（ｖｅｒｓｉｏｎ−ｓｐａｃｅ）法の主な問題点は：
１．  ある程度以上の規模の問題では、計算量が多くなってしまう
２．  ノイズデータ、つまり誤りや欠損データに対しては、うまくはたらかない
上の節のバージョン空間の図を見れば分かる、属性の数と各属性に異なった値の数がバージョン空間の大きさの決め手である。属性の数、または各属性の属性値の数が増えると、下の式（数２）に従ってバージョン空間の大きさが増し、計算量が多くなる。
【数２】
2004213463.tif 000011
（ｍは属性の数、ｎｉは属性ｉに含まれる異なった値の数）
【００３６】
従来の  ｂａｃｋ−ｐｒｏｐａｇａｔｉｏｎも、以下のような問題点を持つ：
１．  解かれる問題に関する意味が明確でないので、与えられた決定または出力が達されたプロセスは理解できる形式で、説明するのが難しい
２．  背景知識は、ネットワークに組み込まれない
３．  満足な結果を得るための、トレーニング時間が長い。これは、このようなネットワーク学習方法が、基本的に、トレーニング・データセットを繰り返し使用するからである
それゆえに、ネットワークで知識をどのようにコード化（ｅｎｃｏｄｅ）、または、明示的に表示するか、訓練されたネットワークからどのようにルールを抽出するかがこの方法の問題点である。
【００３７】
ラフ集合の方法は速度が速いが、実例が遂次呈示される場合では、概念学習ができない。データ集合が無矛盾であることはまれである。ラフ集合の方法では、このような矛盾を取り除いて、縮約を求めることを行っている。これは現実のデータベースが多くの確率的な要素を含んでいることを考えれば、非現実的な取り扱いである。
この方法の大きな問題点は、属性の数を増やすと、識別行列が大きくなる。各実例を識別するための属性の組み合わせパターンが多くなり、縮約も多くなる。どの縮約がもっとも適切かを評価する基準はない。
【００３８】
ラフ集合理論の誕生は多くの研究者に非常な大きな興味を与え、ラフ集合に基づく分類学習アルゴリズムは、開発され続けている。しかし、実世界の分類問題がラフ集合の基本的な概念を越えているので、確率統計技術などが加味されなければいけない。
通常、ボトムアップ法は実例が同時呈示される場合だけでなく、遂次呈示の場合でも、概念学習が可能である。しかし、速度が遅い。トップダウン法は速い学習能力と少ない計算時間という特徴を持つ。しかし、実例が遂次呈示された場合、あるいは、データの変更があった場合、概念学習ができない、学習過程でバックグラウンドの知識が使えない、さらに、並列−分散型モードで実行できないという問題点も持つ。
上述のどの方法でも、実世界の応用、例えばノイズ処理、探索過程を管制するための偏差調整及び背景知識の利用等において満足な解決方法は見つけられていない。
【００３９】
【発明が解決しようとする課題】
本発明は、ロジック、集合と確率を結合して、従来技術の問題点を解決し、実世界のデータに対して適用可能な、確率的ラフ集合帰納学習システムを開発することが目的である。
本発明は、大規模、多様データ、ノイズや、不完全なデータからもルールの発見が可能であり、実世界の問題に対して有効なデータマイニング手法を提供することが目的である。
【００４０】
【課題を解決するための手段】
今までの知識発見の方法は、ロジック、集合、または、確率の理論のいずれかのひとつに基づいて開発されており、適応範囲が限られていた。
本発明に関わる手法（ＧＤＴ−ＲＳメソッド）、及び、これを実現したシステム（ＧＤＴ−ＲＳ）は、図４に示すように、一般化分布表（ＧＤＴ）とラフ集合（ＲＳ）理論の組み合わせからなり、ロジック、集合、確率の理論の全てにまたがるものである。ＧＤＴは、データの不完全性・曖昧性と発見されたルールの強さを評価する確率基準を作るために用いられ、ラフ集合理論は、ルールの抽出や、強いルールの中からすべての実例をカバーする最小ルール集合を絞り出すために用いられる。
ＧＤＴ−ＲＳメソッドで発見されたルールの強さには、ノイズや未知（未観察）データの影響が明示的に表される。また、ＧＤＴ−ＲＳメソッドは、学習のためのバイアス調整に対する柔軟性を持ち、背景知識の利用ができる。ＧＤＴ−ＲＳメソッド  を利用して、実例の順位付け問題も解決できるため、本発明は順序情報表も提案した。
【００４１】
１．ＧＤＴ−ＲＳメソッドの概要
ＧＤＴ−ＲＳメソッドはノイズデータや、不完全性なデータからルール発見することを目的とする。ＧＤＴ−ＲＳメソッドは一般化分布表（ＧＤＴ）とラフ集合（ＲＳ）の理論からなる。以下の節で、ＧＤＴ−ＲＳメソッドを理解するために必要な概念である、一般化分布表（ＧＤＴ）、順序情報表等の基本的な概念を紹介した上で、ＧＤＴ−ＲＳメソッドの特徴を示す。なお、もう一つの基本的な概念であるラフ集合理論については、すでに述べた。
【００４２】
２．  一般化分布表（ＧＤＴ）
ＧＤＴ−ＲＳメソッドの中心は変形した遷移マトリクス、いわゆる一般化分布表ＧＤＴ（Ｇｅｎｅｒａｌｉｚａｔｉｏｎ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｔａｂｌｅ）であり、データの不完全性・曖昧性と発見されたルールの強さを評価する確率基準を提供する。
ＧＤＴは実例と概念の確率関係を表している。ＧＤＴは三つの要素からなる：「可能な実例」、「可能な一般化」及び可能な実例と可能な一般化の間の関係を示す「確率関係」。表８から得られるＧＤＴの例を表９で示す。
【００４３】
【表８】
2004213463.tif 000012
【００４４】
【表９】
2004213463.tif 000013
【００４５】
ここで、最上段の行のａ０ｂ０ｃ０、ａ０ｂ０ｃ１、…は全ての属性値の可能な組み合わせを表している。ここでは、属性ａ，ｃが２とおり、属性ｂが３とおりあるので、組み合わせは２ｘ３ｘ２＝１２とおりとなる。一番左の列の  ｛＊ｂ０ｃ０｝、｛＊ｂ０ｃ１｝、…を可能な一般化という。｛＊ｂ０ｃ０｝は、ａに関しては一般化を行い（＊で示す）、ｂ０ｃ０を有する実例の集合｛ａ０ｂ０ｃ０，ａ１ｂ０ｃ０｝を示している。確率関係は、可能な一般化の中で、各々の可能な実例がとりうる確率を示す。
表８で、ＧＤＴの各要素Ｇｉｊは対応する可能な実例と可能な一般化間の関係の強さを示す「確率関係」を表している。背景知識が利用されない場合、事前分布は一様分布で、Ｇｉｊは式１により定義される。  
【００４６】
【数３】
2004213463.tif 000014
【００４７】
ここでのＰＩｊはｊ列目の可能な実例、ＰＧｉはｉ行目の可能な一般化、Ｎｐｇｉはｉ行目の一般化に含まれる可能な実例の数を表している。
ここで、ｉ行目の確率の和は次式で表される。
【数４】
2004213463.tif 000015
ＧＤＴを作成する時は、条件属性のみを使用する。条件属性によって構成された一般化はルールの条件部として扱う。決定属性はルールの概念部として扱う。
【００４８】
３．  背景知識による事前分布の調節
本発明の重要な特徴の一つはルール発見過程を制御するために、バイアスの選択と利用が出来ることである。ここでは、背景知識をバイアスとして利用することにより、ＧＤＴの作成とルール発見過程をどの様に制御するかについて説明する。背景知識がバイアスとして利用されない場合、ディフォルトでは、一つの一般化に対して、関連する全ての可能な実例の発生する確率は等しく、式１に示されるように事前分布は一様分布である。しかし、背景知識の利用により、事前分布を調整することが出来る。この場合、事前分布は一様分布ではなくなる。
一般的に背景知識は下記の形式で定義される：
ａｉ１ｊ１⇒ａｉ２ｊ２，  Ｑ
ここでのａｉ１ｊ１は属性ｉ１のｊ１番目の値で、ａｉ２ｊ２は属性ｉ２のｊ２番目の値である。ａｉ１ｊ１、ａｉ２ｊ２、Ｑをそれぞれ背景知識の「前提」、「結論」、「強さ」と呼ぶ。背景知識の意味は、ａｉ１ｊ１の条件下でａｉ２ｊ２の発生する確率はＱである、ということである。Ｑ＝０は”ａｉ１ｊ１とａｉ２ｊ２は同時に発生することはない”、Ｑ＝１は”ａｉ１ｊ１とａｉ２ｊ２はいつも同時に発生する”、という意味である。Ｑ＝１／ｎｉ２の時は背景知識が利用されない場合のａｉ２ｊ２の発生する確率と同じである。ここで、ｎａｉ２は属性ｉ２の値の数を表している。背景知識”ａｉ１ｊ１⇒ａｉ２ｊ２，  Ｑ”により、属性値ａｉ１ｊ１が発生した時のａｉ２ｊ２の発生する確率が、一様分布の１／ｎｉ２からＱに変更されるので、属性ｉ２のほかの値に対して、発生する確率は（１−Ｑ）／（ｎｉ２−１）となる。
【００４９】
例えば：背景知識
”ａ０＝＞ｃ１，  １００％”
すなわち、”ａ０が発生したら、ｃ１は必ず発生する”という背景知識を導入することにより、表９は以下の表１０のように変更される。変化した確率には￣を付けた。
【００５０】
【表１０】
2004213463.tif 000016
一般化ａ０ｂ０＊のうち、ａ０ｂ０ｃ０は背景知識を利用しない均等分布の場合は１／２だったのに対し、上記背景知識によれば起こりえないので確率は０となる。他方、ａ０ｂ０ｃ１は、上記背景知識によれば必ず起こるので確率は１となる。
【００５１】
４．  ルールの強さと未知データ
本件発明により発見されたルールを以下のように表す。
Ｘ→Ｙ  ｗｉｔｈ  Ｓ，
すなわち、”ＸならばＹで、強さがＳ”である。ここで、Ｘは概念が満足しなければいけない条件（一般化された条件属性の組み合わせ）、ＹはＸにより決定される概念（決定属性の値）、Ｓはルールの強さを示している。言い換えれば、Ｘは｛ａ０ｂ０＊｝，｛ａ０＊ｃ０｝，…等の条件属性値の組合せであり、Ｙは決定属性値またはその組合せである。Ｘ、Ｙ、Ｓをそれぞれルールの条件、結論、強さと呼ぶ。
ルール  Ｘ→Ｙの強さＳは以下のように定義されている：
Ｓ（Ｘ→Ｙ）＝ｓ（Ｘ）ｘ（１−ｒ（Ｘ→Ｙ））                    式  ２
式２はｓ（Ｘ）という要素と、（１−ｒ（Ｘ→Ｙ））という要素との積で成り立っている。
前者ｓ（Ｘ）はルールの安定性を表す指標である。例えば、｛ａ０＊ｃ０｝という条件のときに、決定クラスｄ１となるというルール｛ａ０＊ｃ０｝→ｄ１が発見されたとする。そのときに、一般化指標｛ａ０＊ｃ０｝を満たすべき全ての組み合わせのうち、２０％の実例しか得られていないデータの母集団と、９０％の実例を得たデータの母集団によって得られたルールとは自ずから安定性が異なる。前者の場合、残りの８０％のデータ如何によってそのルール自体が覆される可能性があるからである。そこで、ある一般化指標に該当する可能な実例のうち、未収集データ（実例）の割合は、ルールの安定性を示す指標となりうる。
【００５２】
後者（１−ｒ（Ｘ→Ｙ））は、ルールの信頼性を示す指標である。例えば、｛ａ０＊ｃ０＊｝という条件のときに、決定クラスｄ１となるというルール｛ａ０＊ｃ０｝→ｄ１が発見されたとする。そのときに、一般化指標｛ａ０＊ｃ０｝を満たすべき全ての組み合わせのうち、１００％の実例がｄ１になっている場合と、８０％はｄ１であるが、２０％はｄ２という決定クラスが得られている場合とは自ずからルールの信頼性が異なる。そこで、後述するように、ノイズ率ｒ（Ｘ→Ｙ）という概念を定立し、８０％はｄ１であるが、２０％はｄ２という決定クラスが得られている場合においては、ノイズ率を２０％とした。
ｓ（Ｘ）という要素と、（１−ｒ（Ｘ→Ｙ））という要素との定性的な概念は説明したとおりであるが、ここでは、数式を用いて、これらの概念をより詳しく説明する。
ｓ（Ｘ）は一般化Ｘ（ルールの条件部）の強さを表す。Ｘ＝ＰＧｉとすると、一般化ＰＧｉの強さｓ（ＰＧｉ）はＰＧｉに含まれるデータベースに存在する実例の確率の和で定義される：
【数５】
2004213463.tif 000017
ここで、Ｇｉｊはデータベースから得られる実例ＰＩｊの一般化ＰＧｉの確率、Ｎｉｎｓ−ｒｅｌ（ＰＧｉ）はデータベースに収集され、一般化ＰＧｉに含まれる実例の数である。ｓ（ＰＧｉ）の値は実データの入力により変化する。ＰＧｉに含まれる全て可能な実例がデータベースに存在すれば、ＰＧｉの強さが最大値の１になる。
【００５３】
一般化の強さが未知データの影響を反映している。未知データとはデータベースに収集されていないデータのことである。一般に、データベースでは、全ての可能な実例を収集しているわけではない。中には、全く発生する可能性のない実例があるし、データ採集の範囲や時間にも制限があるからである。未知データを無視してルール発見を行うと、信頼度の低いルールが発見される恐れがある。ＧＤＴ−ＲＳメソッドでは一般化分布表ＧＤＴに基づき、未知データの影響を評価する方法を提供し、ルールの強さを明記的に示すようにした。未知データが少ないとき、ルールの強さの値は大となり、そうでないときは、小さくなる。
【００５４】
ｒ（Ｘ→Ｙ）はルールＸ→Ｙのノイズ率を表す。これは、未知データとノイズデータの影響によるルールの不完全性と不確定性を示している。ノイズ率ｒは以下のように定義される：
【数６】
2004213463.tif 000018
ここで、Ｎｉｎｓ−ｒｅｌ（Ｘ）は一般化Ｘに属する実例の数、Ｎｉｎｓ−ｃｌａｓｓ（Ｘ，Ｙ）はその実例の中で、決定クラスＹに属している実例の数である。ｒ（Ｘ→Ｙ）は分類の正確率を示す。つまり、一般化Ｘに属する実例がクラスＹに属する確率を示している。
なお、ＧＤＴ−ＲＳメソッドを実現したソフトウエアでは、ユーザーの許すノイズ率を閾値として指定できる。ルールのノイズ率が閾値より高いものは自動的に削除される。
【００５５】
５．  順序情報表
実世界のデータに対して、直面する多くの問題は単なる分類問題ではない。実例の順位付けはそのようなタイプの問題の１つである。例えば、商品の売上ランクと保証期間、値段との関係を求める問題はそのような順序問題である。このような問題に対しては、順位付けルール、”実例ｘのある属性ａの値が実例ｙの同じ属性の値より前に位置付けられるならば、実例ｘは実例ｙより前に位置付けられる”という関係を、発見することが目的になる。
属性値による実例の順位付けが、必ずしも実例の全体的な順位付けと同じものであるとは限らない。どの属性が全体的な順位付けを決定するうえでより重要な役割を演ずるか、そして、どの属性が全体的な順位付けに貢献しないか知ることは大切である。
決定表では、各属性の異なった属性値の間の意味関係を考慮していない。しかし、順位付けルールを発見するためには、データの意味を表す「順位情報」が必要である。そのため、意味情報を取り入れることによって、順序化決定表が作成される。順序化決定表は決定表に意味関係が付加されたものと見ることができる。
【００５６】
順位付けされた属性値は、ＧＤＴ−ＲＳメソッドによるデータマイニング処理の一ステップを構成するものではない。むしろ、ＧＤＴ−ＲＳメソッドを適用するにあたって、順位付けされた属性値を用いて情報を前処理する場面で必要なものである。
この前処理がＧＤＴ−ＲＳに対してどのように適用されるかという点については、後述する。ここでは、順序化決定表の概念のみを説明する。
定義１．＞が、集合Ｕの上の二項関係であるとき、関係＞が以下の２つの性質を満たすならば、「弱い順序」という。
【数７】
2004213463.tif 000019
ただし、’は命題の否定を示す。「弱い順序」により、以下の同値関係が定義される：
【数８】
2004213463.tif 000020
２つの要素ｘ，  ｙに対して、ｘ〜ｙならばｘとｙは、＞によって識別できないと言う。同値関係〜は、Ｕの分類Ｕ／〜を誘導する、Ｕ／〜の上の順序関係＞＊は以下のように定義される：
【数９】
2004213463.tif 000021
ここで、［ｘ］〜はｘを含む同値類である。さらに、＞＊は線形順序である。Ｕ／〜のどんな２つの異なる同値類も比較することができる。
【００５７】
定義２．順序決定表は、決定表に順序関係を加味したものである。
属性ａの値の順序は、自然に実例の順序を誘導する、すなわち、Ｕの要素ｘ，  ｙに対して、次のように定義する：
【数１０】
2004213463.tif 000022
ここで、＞｛ａ｝  は、属性ａによって誘導されるＵの上の順序関係を示す。実例ｘの属性ａの値が実例ｙの同じ属性の値より前に配列される場合に限り、ｘはｙより前に配列される。関係＞｛ａ｝は＞ａと全く同じプロパティを持つ。属性Ａｔの部分集合Ａについて、以下の定義がある：
【数１１】
2004213463.tif 000023
すなわち、ｘがＡで全ての属性によってｙより前に配列される場合に限り、ｘはｙより前に配列される。
多くの実世界アプリケーションでは、特別な属性、いわゆる、決定属性を必要とする。決定属性による実例の順位付けは、’＞’によって示されて、実例の全体的な順位付けと呼ばれている。
【００５８】
例：表１１は、５つのメーカによって生産される製品の順序決定表を示す。ａ、ｂ、ｃ、ｄとｏは、それぞれ、製品のサイズ、保証期間、価格、重みと全体的な順位付けを表す。＞ａ、＞ｂ、＞ｃ、＞ｄと＞ｏ  はそれぞれ属性の順位情報を示す。
【００５９】
【表１１】
2004213463.tif 000024
【００６０】
属性値の順位情報に基づいて、以下のような製品の順位情報を得る：
＞＊｛ａ｝：［ｐ３，ｐ４，ｐ５］  ＞＊｛ａ｝  ［ｐ１］  ＞＊｛ａ｝  ［ｐ２］，
＞＊｛ｂ｝：［ｐ１，ｐ２，ｐ３，ｐ４］  ＞＊｛ｂ｝  ［ｐ５］  ，
＞＊｛ｃ｝：［ｐ１，ｐ５］  ＞＊｛ｃ｝  ［ｐ４］  ＞＊｛ｃ｝  ［ｐ２，ｐ３］，
＞＊｛ｄ｝：［ｐ４，ｐ５］  ＞＊｛ｄ｝  ［ｐ３］  ＞＊｛ｄ｝  ［ｐ１］＞＊｛ｄ｝  ［ｐ２］，
＞＊｛ｏ｝：［ｐ１］  ＞＊｛ｏ｝  ［ｐ４］＞＊｛ｏ｝  ［ｐ２，ｐ３，ｐ５］
｛ａ，  ｂ｝と｛ｃ，ｄ｝について、以下の順位を得る：
＞｛ａ，ｂ｝：  空集合
＞｛ｃ，ｄ｝：  ｐ１＞｛ｃ，ｄ｝ｐ２，  ｐ４  ＞｛ｃ，ｄ｝ｐ２，  ｐ５＞｛ｃ，ｄ｝ｐ２，  ｐ４＞｛ｃ，ｄ｝ｐ３，  ｐ５＞｛ｃ，ｄ｝ｐ３．
属性ａとｂを結合することによって、全ての実例は、同じクラスに入れられる。この例では：＞｛ｃ，ｄ｝は弱い順序ではない。すなわち、２つの弱い順序の結合は、弱い順序を生成しないことがある。これは、順序ｘ＞Ａｙを用いて、有効なルールが求められないことを示唆している。
【００６１】
本発明は以上の知見及びラフ集合理論を組み合わせたものであり、具体的には、複数の実例から、一の決定属性値と相当因果関係を有するｍ個の条件属性値の組み合わせとしてのルールを発見するためのデータ処理方法であって、決定属性値が異なる二つの前記実例について、前記条件属性値の異なる前記条件属性を抽出するステップと、抽出された前記条件属性に関して論理演算を行い、ルールを導出するステップとを含む、データ処理方法にかかるものである。ここで、「実例」は、ｎ個の条件属性のそれぞれに対応するｎ個の条件属性値の組み合わせと、この組み合わせに関連づけられた１個以上の決定属性にかかる決定属性値とを有する情報の単位である。なお、ここで、ｎ＞ｍという関係を具備する。
【００６２】
本発明にかかるデータ処理方法は、上記に加えて、ｍ個の条件属性値の組み合わせを満たしうる可能な実例の数と実際にデータ処理に使用した実処理実例の数とを比較した第一の指標により、前記ルールの強さを評価するステップを含むことが好ましい。
本発明にかかるデータ処理方法は、上記に加えて、一の決定属性値と関連付けられるｍ個（ｎ＞ｍ）の条件属性値の組み合わせを具備する実処理実例の数と、前記一の決定属性値以外の決定属性値と関連付けられるｍ個（ｎ＞ｍ）の条件属性値の組み合わせを具備する実処理実例の数とを比較した第二の指標により、前記ルールの強さを評価するステップを含むことが望ましい。
【００６３】
本発明は、ユーザにより設定された順序との関連で各条件属性値を比較し、どのよう条件属性が特定の決定属性に相関があるのかどうかを発見することができる。この場合、本発明は、それぞれの条件属性値について予め定められた順序を設定するステップと、それぞれの前記条件属性値を比較し、この順序との整合性に関連付けて指標化するステップと、を具備する処理を行ったデータを実例として用いることが望ましい。
本発明は、ＧＤＴ手法として、ｐ個（ｎ＞ｐ）の条件属性値を特定し、ｎ−ｐ個の条件属性値を一般化した前記条件属性値の組み合わせを設定し、この一般化した条件属性値の組み合わせに該当しうるｎ個の条件属性値の組み合わせの数ｑを導出し、設定された一般化した条件属性値の組み合わせに該当する特定のｎ個の前記条件属性値の組み合わせが現れる確率を１／ｑとして扱うことが望ましい。本発明によれば、この確率は、実世界に存在する背景情報を参酌して修正することができる。
なお、本発明にかかるＧＤＴ−ＲＳメソッドを実現するプログラム、またはこれを格納した記録媒体（ＧＤＴ−ＲＳシステム）も本発明の射程内である。
【００６４】
【作用】
本発明では、ＧＤＴが一般的な概念と特殊な要素の間の確率関係を用いるという特徴を利用して、データの不完全性・曖昧性と発見されたルールの強さを評価する確率、及びルール選択の基準を得ることができる。本発明によるＧＤＴ−ＲＳメソッドは、下記の実世界の問題を解決する。
【００６５】
１．  大規模データに対して
ラフ集合では、全ての実例を識別できるための識別行列を作ることにより、縮約が求まる。ＧＤＴ−ＲＳメソッドでは、各実例に対して、その実例を識別できる識別ベクトル（識別行列の中の一行）を作成することにより、実例に関するルールを求める。全ての実例を処理終わったら、最小ルール集合を求める。これにより、膨大な識別行列の作成をさけ、直接ルール（縮約ではない）を発見できる。
ＧＤＴ−ＲＳメソッドは、ＧＤＴとラフ集合理論の組み合わせにより、すべての実例をカバーするより強いルールの最小集合を抽出することができるが、更に大規模なデータベースにも対応できるように二つのＧＤＴ−ＲＳメソッドの実現アルゴリズムを提案している。一つは、最適解を求める方法であり、属性の数が少ない小規模なデータベースに適している。もう一つは、貪欲法と呼ばれる方法を利用して、短時間で大規模なデータベースから有用なルールを発見する、近似解を求める方法である。
【００６６】
２．  連続データに対して
ＧＤＴ−ＲＳメソッドは離散データの処理に適する。連続データは、離散化して用いる。そのため、前処理機能として、連続値の離散化の機能を持たせた。
【００６７】
３．  ノイズと未観察データに対して：
ルールの強さには、ノイズの影響が明示的に表されるので、ユーザーは許される範囲でノイズ率を自由に調整し、満足できるルールを求めることができる。
【００６８】
４．  不完全データに対して：
ルールの強さには、未知（未観察）データの影響が明示的に表されるので、未知データの存在を考慮したルールが抽出される。
【００６９】
５．  データ変更に対して：
ＧＤＴ−ＲＳメソッドでは一つの実例に対して、その実例に関するルールを発見できるので、実例の追加については簡単に対応できる。
【００７０】
６．  背景知識の利用
既知の事実を背景知識として利用することにより、より有効な分布表が作成でき、より有意義なルールを発見できる。
【００７１】
【表１２】
2004213463.tif 000025
表１２の例を使って、本発明にかかるＧＤＴ−ＲＳメソッドがどのように動作するかを説明する。
Ｓｔｅｐ１．  同じ条件属性の実例をまとめる
【００７２】
【表１３】
2004213463.tif 000026
−は矛盾を意味する。
【００７３】
Ｓｔｅｐ２．  各々の実例に対して決定属性の値が異なる各実例に対して、識別ベクトルを作成
例：ｕ２の識別ベクトルの作成する。決定属性の値がｕ２のそれと等しいものについて作成する。
ｍ２，ｊを実例ｕ２とｕｊ  における値が異なる属性の集合とすると、
ｍ２，１＝｛ｂ｝
ｍ２，２＝空集合
ｍ２，４＝｛ａ，ｃ｝
ｍ２，６＝｛ｂ｝
ｍ２，７＝ｕ２とｕ７は同じ決定クラスなので、識別する必要はない。
識別ベクトルは表１４のようになる。
【００７４】
【表１４】
2004213463.tif 000027
【００７５】
Ｓｔｅｐ３．  識別ベクトルから識別関数ｆＴを作成  
【数１２】
2004213463.tif 000028
Ｓｔｅｐ４．  識別関数からルールの生成と選択
【数１３】
2004213463.tif 000029
上記（数１３）にｕ２の対応する属性値を代入すると、二つのルールが生成される：
【数１４】
2004213463.tif 000030
この二つのルールの強さはＧＤＴ−ＲＳメソッドにより以下のように算出される：
【数１５】
2004213463.tif 000031
一般化｛ａ０，ｂ１｝（＝｛ａ０ｂ１＊｝）に含まれる可能な実例はａ０ｂ１ｃ０とａ０ｂ１ｃ１である。そのうち、ａ０ｂ１ｃ１のみがデータセットに存在する。ａ０ｂ１ｃ０は観察されない実例である。そのため、一般化｛ａ０，ｂ１｝の強さは０．５である。一般化｛ａ０，ｂ１｝に含まれる実際の実例はすべて決定クラスｄ（ｙ）に属しているので、ノイズ率は０である。
【数１６】
2004213463.tif 000032
一般化｛ｂ１，ｃ１，＊｝  に含まれる可能な実例はａ０ｂ１ｃ１とａ１ｂ１ｃ１である。二つともデータベースに存在するので、一般化｛＊，ｂ１，ｃ１｝の強さは２×１／２＝１である。一般化｛＊，ｂ１，ｃ１｝に含まれる実際の実例はすべて決定クラスｄ（ｙ）に属するので、ノイズ率は０である。
【数１７】
2004213463.tif 000033
二つのルールの強さを比較すると、ｒ２．｛ｂ１ｃ１｝→ｄ（ｙ）の方が大きいので、ｒ２が選択される。
同様にｕ４，  ｕ６，  ｕ７  の実例に対して、Ｓｔｅｐ２からＳｔｅｐ４を実行して、以下のルールが生成される：
【数１８】
2004213463.tif 000034
【００７６】
Ｓｔｅｐ５．  全ての実例をカバーするルールの最小集合を選択
ＧＤＴ−ＲＳメソッドのルール選択規則は以下のように定められている：
１．  含まれる実例の数が最も多いルールが優先的に選択される
２．  含まれる属性の数が少ない方が優先的に選択される
３．  同じ実例を含むものについては、強さがもっとも大きいルールが優先的に選択される
クラスｄ（ｙ）に関係するルールとルールに含まれる実例を表１５に示す：
【００７７】
【表１５】
2004213463.tif 000035
ルール｛ｂ１ｃ１｝→ｄ（ｙ）が含む実例の数は２で、他のルールより多いので、優先的に選択される。そして、｛ａ１ｃ１｝→ｄ（ｙ）と｛ａ０ｂ１｝→ｄ（ｙ）が含む実例は、｛ｂ１ｃ１｝→ｄ（ｙ）にも含まれるので、クラスｄ（ｙ）の最小ルール集合は｛ｂ１ｃ１｝→ｄ（ｙ）のみである。
クラスｄ（ｎ）に関係するルールとルールに含まれる実例を表１６に示す：
【００７８】
【表１６】
2004213463.tif 000036
【００７９】
二つのルールは異なった実例を含むので、両方のルールが採用される。
結果として、以下のようなルール集合を発見した：
｛ｂ１ｃ１｝→ｄ（ｙ）  Ｓ＝１
｛ｂ２｝→ｄ（ｎ）  Ｓ＝１／４
｛ｃ０｝→ｄ（ｎ）  Ｓ＝１／６
次に、順序付け問題について、ＧＤＴ−ＲＳメソッドでの処理方法を商品販売順位の問題について、表１７を使って説明する。
【００８０】
【表１７】
2004213463.tif 000037
【００８１】
ここで表１７の＞ａ：  ｓｍａｌｌ  ＞ａ  ｍｉｄｄｌｅ  ＞ａ  ｌａｒｇｅ等の部分はユーザが設定する。例えば、この例においては、携帯用の電気製品を対象としている。携帯用であるから、サイズについては小さいものがもっとも好ましく、大きいものは好ましくないと考えられるので、＞ａ：  ｓｍａｌｌ  ＞ａ  ｍｉｄｄｌｅ  ＞ａ  ｌａｒｇｅという設定になる。同様に、保証期間は長い方が好ましいので、＞ｂ：  ３ｙｅａｒｓ  ＞ｂ  ２ｙｅａｒｓとなる。属性ｃは価格、属性ｄは重量である。
属性ｏは順序づけを示している（ｏｒｄｅｒの頭文字である）。この例では、実例ｐ１がｏ＝１となっており、最も売れ行きがいいことを示す。売れ行きに関しては、その次がｐ４であり、ｐ２，ｐ３，ｐ５は売れ行きがよくない。
【００８２】
これらの情報をもとに、ａないしｄのどの属性において、売れ行きとの相関が認められるかどうかという点について分析を行うために、この順序化情報表に基づくデータの前処理を行い、ＧＤＴ−ＲＳメソッドを適用する。
Ｓｔｅｐ１．  バイナリ情報表を作成
下の式に基づいて、順序決定表（表１８）からバイナリ情報表を作成する。
【数１９】
2004213463.tif 000038
【００８３】
【表１８】
2004213463.tif 000039
【００８４】
例えば、（１，２）の欄の１，０，１，１，１は、Ｉａ，  Ｉｂ，  Ｉｃ，  Ｉｄ，  Ｉｏにより、ｐ１とｐ２を比較した結果である。属性ａによれば、実例ｐ１はｍｉｄｄｌｅであり、実例ｐ２はｌａｒｇｅであるから、ｐ１とｐ２を比較すると、ユーザの設定した順序に整合する。よって、上式に基づいて、指標として”１”が選択される。他方、属性ｂについては、ｐ１，ｐ２ともに３ｙｅａｒｓで同じであるから、ユーザの設定した順序に整合しない（値が同じ場合は「整合しない」とみなす）。よって、上式に基づいて、指標として、”０”が選択される。
このように、各属性ごと順番にｐ１，ｐ２の属性値をユーザの設定した順序との関係で比較し、”０”または”１”を記入したのが表１８である。
【００８５】
Ｓｔｅｐ２．  ＧＤＴ−ＲＳメソッド  を利用して、ルール発見を行う。
順序化情報表を用いない場合は、各実例の生データによって、ＧＤＴ−ＲＳメソッドを適用した。しかし、順序化情報表を用いる場合は、上記のとおり、各実例の生データを順序化情報表及び設定されたルールに基づいて表１７のように指標化を行い、これに対して、ＧＤＴ−ＲＳメソッドを適用する。
この結果、決定属性に相関する条件属性を見いだすことができる。この場合でいうと、属性「サイズ」「保証期間」「価格」「重量」のうち、どの要因が売上げに最も影響するのか、という分析結果を得ることが可能となる。
【００８６】
【発明の実施の形態】
本発明にかかる手法を実施するための前処理のフローを図５に示す。図５に示すように、本発明を適用してルールを発見するに先だち、データに対しては以下の前処理を行う。
１）順序関係情報（表１１参照）を利用するかどうかを判断する（ステップ５１）。順序関係情報を用いるときは、順序決定表からバイナリ情報表を作成する（ステップ５３，表１２参照）。
２）属性選択をすべきかどうかを判断する（ステップ５５）。
３）連続値属性に対して離散化するかどうかを判断する（ステップ５７）。
これらの前処理を経たデータを本発明による手法で分析する（ステップ５９）。また、本発明にかかるＧＤＴ−ＲＳメソッドの処理ルーチンを図６に示す。
本発明にかかる手法によれば、まず、同じ条件属性（例えば、ａ０ｂ０ｃ１）の組み合わせを有する実例を一つの集合にまとめる（ステップ１１）。この結果、同じ条件属性を持つものの中で、結果属性の値が異なるものが混在する場合は、その条件属性はルールを発見する上で役に立たない。そこで、条件属性の組み合わせが同じで、決定属性が異なる実例については削除を行う（ステップ１５）。ただし、このステップは任意であり、ユーザがこのようなノイズについて寛容な場合は、この限りではない（ステップ１３）。
【００８７】
次に、すでに説明した手法により、決定属性が異なる各実例について、識別ベクトルを作成する（ステップ１７）。識別ベクトルが得られれば、そこから識別関数を作成し（ステップ１９）、識別関数からさらにルールを導出する（ステップ２１）。
ここで、ユーザには、背景知識を利用するかどうかのオプションが与えられる（ステップ２３）。これにより、背景知識による調整を加えた分布を採用したり（ステップ２５）、調整を加えていない一様分布を採用する（ステップ２７）。
導出されたルールがユーザの許容するノイズ率を超える場合（ステップ２９）は、ルールを削除する（ステップ３１）。全ての実例が処理されたことを確認後（ステップ３３）、全ての実例をカバーするルールの最終集合を選択する（ステップ３５）。このようにして、ルールが決められる（ステップ３７）。
【００８８】
【実施例】
以下の説明においては、実世界のデータ三例を用いてＧＤＴ−ＲＳメソッドの効果を示す。
一番目は髄膜炎の例で、背景知識を利用する場合と利用しない場合の結果を比較し、背景知識の利用により、良い結果が得られることを示す。二番目は、細菌培養検査という大規模データベースを用いて、データの前処理、つまり、連続データの離散化、背景知識の利用での属性選択あるいは自動属性選択から、ルール生成するまでのプロセスを説明し、大規模性／複雑問題への有効性を示す。三番目は、胃癌データの例で、ラフ集合論に基づく順位情報を利用して、順位付けルールの生成法を説明し、有用性を示す。
実施例１．髄膜脳炎データベースからの知識発見
まず、髄膜炎の例で、背景知識を用いる場合と、用いない場合の結果を比較し、背景知識の利用の効果を示す。
共通データとして与えられた髄膜炎のデータベースは、１４０人の患者のデータからなっている。属性の数が３８であり、比較的小規模のデータである［Ｔｓｕｍｏｔｏ−９８］Ｔｓｕｍｏｔｏ，  Ｓ．  Ｃｏｍｐａｒｉｓｉｏｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ＫＤＤ  Ｍｅｔｈｏｄｓ  ｗｉｔｈ  Ｃｏｍｍｏｎ  Ｄａｔａｓｅｔｓ，  （Ｓｐｅｃｉａｌ  Ｐａｎｅｌ  Ｄｉｓｃｕｓｓｉｏｎ  Ｓｅｓｓｉｏｎ  ｏｎ  Ｋｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ｆｒｏｍ  ａ  Ｍｅｎｉｎｇｉｔｉｓ  Ｄａｔａｂａｓｅ）  Ｐｒｏｃ．  ｔｈｅ  １２ｔｈ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｆ  ＪＳＡＩ（１９９８）７２−７３。
下記の各因子に関するルールを生成するのが目的である。
・診断に重要な因子（ＤＩＡＧ，  ＤＩＡＧ２に重要な因子）
・原因菌探索に重要な因子（ＣＵＬＴ＿ＦＩＮＤ，  ＣＵＬＴＵＲＥに重要な因子）
・後遺症の有無に関して重要な因子（Ｃ＿ＣＯＵＲＳＥ，  ＣＯＵＲＳＥ（Ｇｒｏｕｐｅｄ）に重要な因子）
この実験では、六つの属性（ＤＩＡＧ，  ＤＩＡＧ２，  ＣＵＬＴ＿ＦＩＮＤ，
ＣＵＬＴＵＲＥ，Ｃ＿ＣＯＵＲＳＥ，ＣＯＵＲＳＥ（Ｇｒｏｕｐｅｄ））
をそれぞれ決定クラスとし、背景知識を利用する場合と利用しない場合についてＧＤＴ−ＲＳメソッドを実行し、対応する因子に関するルール生成を行った。
【００８９】
背景知識
医師の経験を背景知識として利用する。背景知識の一例は以下のとおりである。
・脳波所見（ＥＥＧ＿ＷＡＶＥ）が正常ならば、脳波の局所以上の有無（ＥＥＧ＿ＦＯＣＵＳ）が異常になることはない；
・白血球数（ＷＢＣ）が高ければ、炎症性蛋白（ＣＲＰ）も高い。
【００９０】
以下のリストは、医師から提供された背景知識の一覧である。三組に分けられている：
・同時に発生しないもの
ＥＥＧ＿ＷＡＶＥ（ｎｏｒｍａｌ）  とＥＥＧ＿ＦＯＣＵＳ（＋）
ＣＳＦ＿ＣＥＬＬ（ｌｏｗ）  と  Ｃｅｌｌ＿Ｐｏｌｙ（ｈｉｇｈ）
ＣＳＦ＿ＣＥＬＬ（ｌｏｗ）  と  Ｃｅｌｌ＿Ｍｏｎｏ（ｈｉｇｈ）
・発生する可能性が低いもの
ＷＢＣ（ｌｏｗ）  のとき  ＣＲＰ（ｈｉｇｈ）  は発生する可能性が低い
ＷＢＣ（ｌｏｗ）  のとき  ＥＳＲ（ｈｉｇｈ）  は発生する可能性が低い
ＷＢＣ（ｌｏｗ）  のとき  ＣＳＦ＿ＣＥＬＬ（ｈｉｇｈ）  は発生する可能性が低い
ＷＢＣ（ｌｏｗ）  のとき  Ｃｅｌｌ＿Ｐｏｌｙ（ｈｉｇｈ）  は発生する可能性が低い
ＷＢＣ（ｌｏｗ）  のとき  Ｃｅｌｌ＿Ｍｏｎｏ（ｈｉｇｈ）  は発生する可能性が低い
ＢＴ（ｌｏｗ）  のとき  ＳＴＩＦＦ（ｈｉｇｈ）  は発生する可能性が低い
ＢＴ（ｌｏｗ）  のとき  ＬＡＳＥＧＵＥ（ｈｉｇｈ）  は発生する可能性が低い
ＢＴ（ｌｏｗ）  のとき  ＫＥＲＮＩＧ（ｈｉｇｈ）  は発生する可能性が低い
・同時に発生する可能性が高いもの
ＷＢＣ（ｈｉｇｈ）  と  ＣＲＰ（ｈｉｇｈ）
ＷＢＣ（ｈｉｇｈ）  と  ＥＳＲ（ｈｉｇｈ）
ＷＢＣ（ｈｉｇｈ）  と  ＣＳＦ＿ＣＥＬＬ（ｈｉｇｈ）  
ＷＢＣ（ｈｉｇｈ）  と  Ｃｅｌｌ＿Ｐｏｌｙ（ｈｉｇｈ）
ＷＢＣ（ｈｉｇｈ）  と  Ｃｅｌｌ＿Ｍｏｎｏ（ｈｉｇｈ）
ＢＴ（ｈｉｇｈ）  と  ＳＴＩＦＦ（ｈｉｇｈ）
ＢＴ（ｈｉｇｈ）  と  ＬＡＳＥＧＵＥ（ｈｉｇｈ）
ＢＴ（ｈｉｇｈ）  と  ＫＥＲＮＩＧ（ｈｉｇｈ）
ＢＴ（ｈｉｇｈ）  と  ＣＲＰ（ｈｉｇｈ）
ＢＴ（ｈｉｇｈ）  と  ＥＳＲ（ｈｉｇｈ）  
…  
ＥＥＧ＿ＦＯＣＵＳ（＋）  と  ＦＯＣＡＬ（＋）
ＥＥＧ＿ＷＡＶＥ（＋）  と  ＥＥＧ＿ＦＯＣＵＳ（＋）
ＣＲＰ（ｈｉｇｈ）    と  ＣＳＦ＿ＧＬＵ（ｌｏｗ）
ＣＲＰ（ｈｉｇｈ）    と  ＣＳＦ＿ＰＲＯ（ｌｏｗ）
【００９１】
括弧中の”ｈｉｇｈ”と”ｌｏｗ”は曖昧な範囲なので、以下のように処理した：
１．  医学知識によるデータを離散化する場合：
”ｈｉｇｈ”は正常値の上限より高い値、
”ｌｏｗ”は正常値の下限より小さい値として扱う。
２．  連続値を離散化する場合：
離散化された属性値は有限個の数に分類にされるが、ここで、最大値に分類されたものは”ｈｉｇｈ”、最小値に分類されたものを”ｌｏｗ”とする。それ以外のものは”ｈｉｇｈ”とも”ｌｏｗ”ともしない。
本稿に示される結果は、自動離散化の方法により連続値属性を離散化して得られた結果である。
ＧＤＴ−ＲＳメソッドで利用する背景知識では、発生する確率Ｑは”高い”や”低”などではなく、０以上１以下の数を指定しなければならない。しかし、医師からの知識はそうではないため、適切なＱの値の設定が必要である。今回の実験では、背景知識”ａｉ１ｊ１⇒ｉ２ｊ２の発生する確率が高い”に対して、Ｑを１とし、背景知識”ａｉ１ｊ１⇒ａｉ２ｊ２  の発生する確率が低い”に対して、Ｑを０としている。
【００９２】
結果の比較
背景知識を用いる場合と、用いない場合では得られたルールの一部に違いが見られた。背景知識の利用により、以下の影響が表されている：
背景知識が用いられない場合には強さが低いという理由で得られなかったルールが選択された。例えば、背景知識を用いたときには、下記のｒｕｌｅ１の強さは、背景知識を用いない場合の４倍となった。
ｒｕｌｅ１：  ＯＮＳＥＴ（ａｃｕｔｅ）∧ＥＳＲ（≦５）∧ＣＳＦ＿ＣＥＬＬ（＜１０）∧ＣＵＬＴＵＲＥ（−）→ＶＩＲＵＳ（Ｅ）
この理由を説明する。背景知識が利用されない場合、ｒｕｌｅ１の強さは３０×（３８４／Ｅ）である。但し、３０はルールの条件部が満足する実例の数、３８４／Ｅは条件部（一般化）の強さである。この場合は背景知識に、ｒｕｌｅ１に影響する知識、つまり背景知識の前提部がｒｕｌｅ１の条件部に含まれ、背景知識の結論部がｒｕｌｅ１の条件部に含まれないような背景知識は以下の二つである。
ＣＳＦ＿ＣＥＬＬ（ｌｏｗ）とＣｅｌｌ＿Ｐｏｌｙ（ｈｉｇｈ）は同時に発生しない
ＣＳＦ＿ＣＥＬＬ（ｌｏｗ）とＣｅｌｌ＿Ｍｏｎｏ（ｈｉｇｈ）は同時に発生しない
【００９３】
Ｃｅｌｌ＿ＰｏｌｙとＣｅｌｌ＿Ｍｏｎｏは連続値属性で、離散化により、どちらもｌｏｗとｈｉｇｈに分割されていて、その以外のものはない。ＣＳＦ＿ＣＥＬＬが低い（ｌｏｗ）時、Ｃｅｌｌ＿ＰｏｌｙやＣｅｌｌ＿Ｍｏｎｏが高く（ｈｉｇｈ）なることがないという背景知識により、低いＣＳＦ＿ＣＥＬＬが発生したら、Ｃｅｌｌ＿ＰｏｌｙやＣｅｌｌ＿Ｍｏｎｏの属性値がｌｏｗの一つしか発生しない。よって、Ｃｅｌｌ＿ＰｏｌｙとＣｅｌｌ＿Ｍｏｎｏの属性値の数が１減り、元の２から１になる。そのため、全て属性の属性値の数の積ＥがＥ×１／２×１／２＝Ｅ／４に変わり、ルールの強さＳは３０×（３８４／Ｅ）×４に変更される。  
【００９４】
また、背景知識の利用により、一部のルールが他のルールに置き換えられた。例えば、ルール
ｒｕｌｅ２：  ＤＩＡＧ（ＶＩＲＵＳ（Ｅ））∧ＬＯＣ［４，  ７］→ＥＥＧ＿ａｂｎｏｒｍａｌ，    Ｓ  ＝  ３０／Ｅ
は背景知識が利用されない場合は発見されたが、背景知識を利用したときは、これに代わり下の  ｒｕｌｅ２’が得られた。
ｒｕｌｅ２’：  ＥＥＧ＿ＦＯＣＵＳ（＋）∧ＬＯＣ［４，  ７］→ＥＥＧ＿ａｂｎｏｒｍａｌ，    Ｓ  ＝  （１０／Ｅ）×４
これは、背景知識を利用したことにより、ｒｕｌｅ２’の強さがｒｕｌｅ２の強さを上まったものになったからである。
この結果に対する医師のコメントは「ｒｕｌｅ２とｒｕｌｅ２’は両方とも合理的だが、ｒｕｌｅ２’のほうがより合理的である」というものであった。
【００９５】
実施例２．細菌培養検出データベースからの知識発見
ここで使用したのは共通データとして与えられている細菌培養検出データベースである。
実例の数が２０，０００で、属性の数が４９である。このデータベースは実世界のデータの集まりで、前処理も行っていない。そのため、いくつかの特徴を持っている：
１．  属性の値が欠けている欠損データが存在する
２．  「病名」と「検出菌」は属性値の数が多い
３．  時系列データを含んでいる。即ち、同じ患者の異なった時間での検査データが収集されている
また、幾つかの属性が複数個の子属性からなる。例えば、病名属性は三つの病名を含み、目的菌属性は二種類の目的菌を含んでいる。子属性も計算すると、属性の数が６０にのぼる。そのため、属性選択が必要になる。
【００９６】
このデータベースに対して、主な目的は二つある：
１．  検出菌と他の属性との関係を見つけ出す
ここで、検出菌がある場合（＋）とない場合（−）の二つの決定クラスに分け、各クラスに対して、  ｉｆ−ｔｈｅｎルールを探す。
２．  検出菌がある場合、抗生物質の感受性と他の属性との関係を見つけ出す
抗生物質の感受性は四種類（Ｒ、Ｓ、Ｉ、空）あるが、  今回はｒｅｓｉｓｔａｎｔ（Ｒ）とｓｅｎｓｉｂｉｌｉｔｙ（Ｓ）だけに対してｉｆ−ｔｈｅｎルールを探す。
今回の医療データでは、得られるルールに含まれる実例の数が少ないので、正確率が１００％すなわちノイズがないルールがあっても、十分な信頼性があるといえない。そこで、ＧＤＴ−ＲＳメソッドでは、ユーザーの指定する正確率の範囲でルール発見を行っている。
【００９７】
実行手順：
１．  高正確率でルール発見を行う
２．  実例数が少ない（例えば、３以下）ルールに含まれる実例に対して、低正確率でもう一度ルール発見を行う。
以下では、目的毎の実験結果を示す。
【００９８】
目的１．検出菌と属性の関係
まず、欠損データについては、”？”を代入して、属性の値の一つとして扱う。そして、属性の数を減らすために、明らかに検出菌に無関係な属性、例えば、治療手段、材料、病棟などを削除し、さらに、属性選択方法により重要ではない属性「尿硝酸塩」あるいは「尿蛋白」などを削除した。実験は検出菌を決定クラス、以下の属性を条件属性として行った。
性別、生年月日（十代、二十代、…  に変更）、発熱、気切、白血球、病名１、尿ＷＢＣ、尿蛋白、尿潜血、尿定量、βａｌａｃｔａｍｅｓｅ
表１９と表２０は検出菌がある（＋）とない（−）に関するルールを示している。発見されたルールが多いので、ここでは含む実例の数が多く、正確率が高い一部のルールしか表していない。表のｇｅｎは条件に含まれる一般化の数、ｓｔｒｇ．は一般化の事前分布、「実例数」の中の（＋）と（−）はそれぞれデータベースに存在し、各ルールに含まれる検出菌（＋）あるいは（−）に属している実例の数である。
【００９９】
【表１９】
2004213463.tif 000040
【０１００】
【表２０】
2004213463.tif 000041
【０１０１】
目的２．抗生物質と属性の関係
抗生物質の種類は以下のとおりである：
ＰＣＧ，  ＰＣｓ，  Ａｕｇ，  ＰＣｓ−緑，  ＣＥＰｓ−１，  ＣＥＰｓ−２，  ＣＥＰｓ−３，  ＣＥＰｓ−４，  ＣＥＰｓ−緑，  ＡＧｓ，  ＭＬｓ，  ＴＣｓ，  ＬＣＭｓ，  ＣＰｓ，  ＣＢＰｓ，  ＶＣＭ，  ＲＦＰ／ＦＯＭ
これらの属性を決定属性として、ルール発見を行う。
前例と同じく、重要でない属性を除いて、以下の属性を得た。
性別、年齢（何十代）、発熱、カテーテル１、気切、挿管、ドレナージ１、白血球、投薬１、ステロイド、抗癌剤、放射線、病名１、尿ＷＢＣ、尿硝酸塩、尿蛋白、尿潜血、尿定量、総菌数、検出菌、βａｌａｃｔａｍｅｓｅ
ここで、抗生物質｛Ａｕｇ、ＣＥＰｓ−１、ＰＣＧ、ＰＣｓ｝に対する、ＧＤＴ−ＲＳメソッドの実行結果を示す。ＧＤＴ−ＲＳメソッドは全ての実例を含むルールの集合を探すので、発見されたルールの数が多い。表２１の結果には医師の評価で、価値があると認められたもののみ列挙されている。
【０１０２】
【表２１】
2004213463.tif 000042
【０１０３】
Ｃ４．５  との比較
同じデータに対して、Ｃ４．５によるルール発見を行った。一部の結果はＧＤＴ−ＲＳメソッドと同じである。例えば：
βａｌａｃｔａｍｅｓｅ（３＋）→検出菌（＋）
白血球（不明）∧病名１（腫瘍）∧尿定量（１０４）→検出菌（＋）
尿定量（＜１０３）→検出菌（−）
しかし、一部のルール、例えば、医師によると、意味のあるルール：
病名１（肺炎）→検出菌（−）
はＧＤＴ−ＲＳメソッドで発見されたが、Ｃ４．５では発見されなかった。
Ｃ４．５で発見され、ＧＤＴ−ＲＳメソッドで発見されなかったルールもある。例えば次の二つである：
βａｌａｃｔａｍｅｓｅ（１＋）→検出菌（＋）
発熱（３９℃）→検出菌（−）
その原因はＧＤＴ−ＲＳメソッドでは、より低い閾値（ノイズ率４０％）でルール発見を行ったためである。そのため、Ｃ４．５を用いたときより意義のある一般的なルールが発見された。Ｃ４．５では、βａｌａｃｔａｍｅｓｅ（１＋）あるいは発熱（３９℃）を含む、もっと特殊なルールが発見された（表２２参照）。
【０１０４】
【表２２】
2004213463.tif 000043
【０１０５】
実施例３．胃癌データベースからの知識発見
最後の例は、国立がんセンターで集められる胃癌データベースである。患者の症状、例えば、ガンの種類、ｓｅｒｏｓａｌな侵入の有無、腹膜転移の有無、肝臓転移の有無、ガン組織の最大直径、手術前合併症など、およそ２７の属性がある。解析の目的は、手術後９０日以内に死亡した患者に働いた主要な因子を見つけることである。この例で、順位情報を利用して、ＧＤＴ−ＲＳメソッドに基づく、順位付けルールの生成を説明する。
胃癌データベースは、典型的に不平衝なものである。すなわち、手術後９０日以内に死亡した患者人数２０７に対して、生存した患者の人数は５９６３である。また、生存した患者の中にも死亡した患者と似たような症状を持つ例が多く見られる。
詳しい説明の前に、国立がんセンターの胃癌データの主な属性、そして、その属性値に関する順序情報を示す（表２３を参照）。
【０１０６】
【表２３】
2004213463.tif 000044
「注」”．”や”．．”は、特に説明がなかった場合、欠損値という意味である。
【０１０７】
順序決定表から順位付けルールを見つけるために、まず、順序決定表をバイナリ情報に変える。これよりＧＤＴ−ＲＳシステムを直ちに適用することができる。
本発明にかかるＧＤＴ−ＲＳメソッドで、発見されたルールの品質は、正確度とカバー率を含むいくつかの観点から評価される。正確度は、ルールに含まれるすべての属性を含む実例の数とルールの条件部に含まれるすべての属性を含む実例の比である。ユーザーは、閾値として許された範囲で正確度レベルを指定することができる。胃癌データの例では、閾値は０．６に設定される。一方、カバー率は単にルールに含まれる正実例と負実例の量で示す。
バイナリ情報表で、実例のペア（ｘ，ｙ）∈Ｕ×Ｕを考える。情報関数は、以下のように定義される：
【数２０】
2004213463.tif 000045
例えば、ｘ＞｛ａ｝ｙならＩａ（ｘ，ｙ）＝１である。（ｘ，ｘ）のような実列ペアは扱わない。
表２４で示される結果から、以下のことが分かった。２２個のルールのうち、１７個が属性ｌｉｖｅｒ＿ｍｅｔａ  （肝臓転移）を含んでいる、１１個が属性ｐｅｒｉｔｏｎｅａｌ−ｍａｔｅ（腹膜の転移）を含んでいる、その中の５個はｌｉｖｅｒ＿ｍｅｔａを含む。この結果は、肝臓転移や腹膜の転移が手術後９０日以内に死亡の主要な原因であるということを示す。
【０１０８】
【表２４】
2004213463.tif 000046
【０１０９】
国立がんセンターのスタッフによるこの結果の評価は「発見された順位付けルールは、合理的で面白い」というものであった。彼らは受容性と新規性に基づく、各ルールを評価した。表２５は胃癌データから発見されたルール及び各ルールに対する彼らの評価を示している。納得性と新規性の評価値は、１が最低、５が最高である。表に示されたように、多くのルールが受容されたが、その一部には新規性があるという評価を得た。
【０１１０】
【表２５】
2004213463.tif 000047
【０１１１】
【発明の効果】
本発明にかかるＧＤＴ−ＲＳメソッドは、バイアス調整に対する柔軟性、背景知識の利用可能性、ノイズデータ、欠損データに対する処理の有効性、未観測な情報の予測性などについて、優れている。
本発明によれば、以下の効果が認められる。
１．  背景知識をバイアスとして利用することにより、より合理的なルールが発見される。
２．  未観測なデータを予測し、ルールの強さを決めるので、より意味あるルールが発見される。
【図面の簡単な説明】
【図１】従来技術によるバージョン空間の例を示す。
【図２】従来技術によるＣ４．５の木構造の例を示す。
【図３】従来技術によるラフ集合による分析結果の例を示す。
【図４】本発明にかかる解決手段の概念図を示す。
【図５】本発明によるデータ処理の前処理のフロー図を示す。
【図６】本発明によるデータ処理のフロー図を示す。
【図１】
2004213463.tif 000048
【図２】
2004213463.tif 000049
【図３】
2004213463.tif 000050
【図４】
2004213463.tif 000051
【図５】
2004213463.tif 000052
【図６】
2004213463.tif 000053