[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP3209163B2 - 分類装置 - Google Patents

分類装置

Info

Publication number
JP3209163B2
JP3209163B2 JP27379797A JP27379797A JP3209163B2 JP 3209163 B2 JP3209163 B2 JP 3209163B2 JP 27379797 A JP27379797 A JP 27379797A JP 27379797 A JP27379797 A JP 27379797A JP 3209163 B2 JP3209163 B2 JP 3209163B2
Authority
JP
Japan
Prior art keywords
classification
case data
condition
case
rule
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP27379797A
Other languages
English (en)
Other versions
JPH1196010A (ja
Inventor
和彦 大野
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Priority to JP27379797A priority Critical patent/JP3209163B2/ja
Priority to US09/157,315 priority patent/US6266656B1/en
Publication of JPH1196010A publication Critical patent/JPH1196010A/ja
Application granted granted Critical
Publication of JP3209163B2 publication Critical patent/JP3209163B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computing arrangements using knowledge-based models
    • G06N5/02—Knowledge representation; Symbolic representation
    • G06N5/022—Knowledge engineering; Knowledge acquisition
    • G06N5/025—Extracting rules from data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/35—Clustering; Classification
    • G06F16/353—Clustering; Classification into predefined classes
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/24—Classification techniques
    • G06F18/24765—Rule-based classification

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Evolutionary Computation (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Biology (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Computational Linguistics (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、分類済の事例デー
タを用いて分類ルールを自動生成し、未分類の事例を自
動分類する分類装置に関する。
【０００２】
【従来の技術】分類事例から分類ルールを自動生成し、
これを用いて分類を行う方法としては、統計的な手法、
知識処理的な手法、計算論的学習理論に基づく手法、ニ
ューラルネット的な手法など、多くの方法が提案されて
いる。これらの手法は、各々長所、短所があり、適する
問題領域も変わって来る。
【０００３】統計的な手法は、確率モデルを基礎に事例
データの解析を行う事を主目的にするため、一般的には
事例データに潜在する主要な傾向を見つけ出すために利
用されることが多い。また、ルール生成に必要な計算量
も少い。半面、例外的な分類処理は得意でないことが多
い。代表的手法は、数量化II類やベイズ判別などが知ら
れている。
【０００４】知識処理的な手法、および計算論的学習理
論は、機械学習の実現を目指した研究の過程で提案され
ている手法および理論である。機械学習とは、簡単に言
えば、計算機が自律的に適応的な知識（情報、ルール、
プログラム等）を自動生成することである。自動分類も
この機械学習機能の一部として位置付けることができ
る。統計的手法の主目的は事例データの主要な傾向の発
見であるが、機械学習の場合は、最終目的が計算機の知
能化にあるため、目的が多様化している。研究者（グル
ープ）毎に目的は少しずつ異っており、例えば、事例と
矛盾しない仮説の範囲を求めること、例外的に振舞う事
例データを認識しこれを処理すること、あるいは事例を
生成するプログラムを自動生成することなどが目的にな
る。
【０００５】ニューラルネット的手法は、疑似的な神経
細胞を用いた模擬システムであり、学習やパタン識別に
応用することができる。簡単に使える半面、分類ルール
がブラックボックスとなり人間によるチェックや修正が
難しいという問題点がある。
【０００６】以下では、従来技術として、帰納理論装置
（特公平０７−４３７２２号公報参照）を注目する。上
記特公平０７−４３７２２号公報に記載の帰納推論装置
は、諸条件の組合せによって成立する事象に対する一般
的な知識を、この対象分野の事例から帰納的に求めるこ
とにより、知識処理に必要な知識情報を効果的に得るこ
とを目的としたものである。
【０００７】この帰納推論装置は、事例データの集合を
入力されたのち、各分類結果を成立させる十分条件と必
要条件を自動生成する。これを用いて、未知の条件が与
えられた際、十分条件が満たされていれば当該分類結果
は成立と判定し、必要条件が満たされていなければ当該
分類結果は不成立と判定する。
【０００８】
【発明が解決しようとする課題】この技術の問題点は、
事例データの組が論理的に分類不能な場合に、有効な分
類ルールを生成できないことである。例えば、以下の事
例データが与えられたとしよう。
【０００９】
【表１】
【００１０】上記の事例データから分類ルールが生成さ
れた後、分類結果が未知の事例データ
【００１１】
【表２】
【００１２】を分類する場合を考える。
【００１３】条件“水中生活”は、分類結果“魚”を導
く十分条件でないため、鯉は魚とは分類できない。ま
た、“水中生活”は“魚”の必要条件であるため、鯉が
魚であることは否定できない。つまり、上記の事例デー
タの集合からは、“水中生活”と“魚”に関する積極的
な分類ルールは生成されない。この事情は、“獣”に関
しても同様である。
【００１４】以上は、論理的には当然のことであるが、
現実的な応用の面からは問題点がある。
【００１５】第１の問題点は、現実的な応用問題では論
理的に分類不能な事例データが与えられることが多いこ
とである。
【００１６】第２の問題点は、前記の帰納推論装置は事
例データの情報を十分に活用しているとは言えない点で
ある。例えば、水中生活をするほとんどの事例が“魚”
であり、それらが学習用の事例データとしてシステムに
与えられた場合、“確実ではないが、水中生活をするの
は魚であろう”という分類ルールができることが望まし
い。この際、確実さの程度が定量的にかわることも重要
である。
【００１７】前記の帰納推論装置と対比させた場合、本
発明が解決しようとする課題は、 ・論理的に分類不能な事例データの入力に対して、確実
さの程度を定量的に含む分類ルールを生成し、 ・そのような分類ルールを用いて、未知の事例を確実さ
の定量値付で分類することである。
【００１８】本発明の目的について、より一般的な立場
から述べると、現実的な分類問題に対して、有効な学習
型の自動分類を行う装置を提供することにある。
【００１９】ここで、現実的な分類問題とは、前記のよ
うな論理的には分類不能な事例を含み、かつ、条件や分
類結果の種類が大きな問題のことを意味する。そして、
これを有効に分類するとは、 １．現実的な時間と計算資源内で分類に有効な分類ルー
ルを生成でき、 ２．分類結果を確実さの定量値つきで出力できる、こと
をいう。
【００２０】
【課題を解決するための手段】前記目的を達成するた
め、本発明は、その概略を述べれば、確実さの定量値と
して確率値を分類ルールに導入し、事例を用いて確率値
つきの分類ルールを生成し、この分類ルールを用いて確
率的な分類を行うようにしたものである。。
【００２１】より詳細には、本発明は、分類手がかりと
なる条件部と分類結果の組を事例データとして、該事例
データのなかで分類結果が既知である既知事例データを
用いて分類ルールを自動生成し、分類結果が未知である
未知事例データを、前記分類ルールを用いて自動分類す
る分類装置において、既知事例データおよび未知事例デ
ータを入力する入力手段と、確率的な情報を含む分類ル
ールを蓄える分類ルールデータベースと、前記既知事例
データを条件部の論理関係に基づいてネットワーク化し
て蓄積する事例データベースと、入力された前記既知事
例データおよび前記未知事例データの条件部と前記分類
ルールを用いて分類結果の確率値を推定する確率値推定
手段と、分類ルールの有効性を統計的検定により評価す
ることにより無駄な分類ルールの生成を抑制する分類ル
ール生成手段と、を備えたことを特徴とする。
【００２２】また、本発明は、前記入力手段から入力さ
れた前記既知事例データの分類結果の確率値と、前記確
率値推定手段から出力される分類結果の確率値と、を比
較して、その差が予め定めた値よりも大きな場合に、分
類ルールを生成する、ことを特徴とする。
【００２３】また、本発明は、入力された前記既知事例
データの条件部全部あるいは条件の一部を入力として受
取り、前記事例データベースを探索して否定条件を含む
事例ノードを推定する否定条件探索手段を備え、前記否
定条件探索手段を用いて、否定条件を含む分類ルールを
生成する機能を追加した分類ルール生成手段を備える、
ことを特徴とする。
【００２４】本発明は、第１の手段として、分類ルール
の生成時に、その分類ルールの有効性を判定し、無駄な
分類ルールの生成を防ぐ（請求項１参照）。
【００２５】本発明は、第２の手段として、条件の論理
的関係に基づいてネットワーク化された事例データベー
スを探索することにより否定条件を発見し、否定条件つ
きの分類ルールを生成する（請求項３参照）。
【００２６】本発明によれば、上記第１の手段により、
分類ルールの記憶のために必要な記憶装置の総量を減少
させることができ、分類ルールの利用・操作の処理時間
を短縮させることができる。これは、現実問題を解く際
に有効である。
【００２７】また上記第２の手段により、全事例を探索
するよりも短い処理時間で否定条件の探索を行うことが
でき、否定条件つきの分類ルールを効率的に生成するこ
とができる。否定条件つきの分類ルールは自動分類の精
度向上につながる。
【００２８】［発明の概要］本発明の実施の形態を説明
する前に、本発明の原理について説明する。
【００２９】本発明の特徴は、事例データから分類ルー
ルを自動生成する点にある。この処理の背景にある確率
統計的な考え方を下敷に事例データ、母集団、分類ルー
ル等に付いて説明する。
【００３０】事例データ：まず、事例データを定義す
る。
【００３１】事例データとは、条件部と分類結果の対で
ある。条件部は、一般に、複数個の条件の論理積から構
成される。これらの条件は、該事例データに関して成立
している条件である。また、成立している条件は条件部
に含まれないものとする。以下は条件部の例である。
【００３２】
【数１】
【００３３】但し、記号
【００３４】
【数２】
【００３５】は論理積を表す記号である。上記の例で
は、「水中生活」、「えら呼吸」、「鱗あり」の全ての
条件が満たされている事を示す。
【００３６】分類結果は、離散的な記号である。以下は
分類結果の例である。 魚
【００３７】条件部と分類結果の対により事例データが
構成される。また、本質的ではないが、説明のため事例
名称を追加する場合もある。以下に１件の事例データの
例を示す。
【００３８】
【表３】
【００３９】この事例データは、水中生活を営み、えら
呼吸を行い、鱗があり、魚に分類され、鰯１と呼ばれ
る。
【００４０】＜事例データ集合＞：ある時点までに投入
された事例データの集まりを事例データ集合と呼ぶ。以
下は、事例データ集合の例である。
【００４１】
【表４】
【００４２】＜事例データの観測確率＞：事例データに
はそれが観測される確率が付属していると考える（これ
は仮定である）。この観測確率は、一般に０以上１以下
の実数値を取り、全事例データの観測確率の和は１とな
る。観測確率は「測度」と呼ばれることもある。
【００４３】観測確率も含めた事例データ集合を母集団
と呼ぶ。母集団の例を示す。
【００４４】
【表５】
【００４５】事例データは母集団の観測確率に基づいて
発生すると仮定する。つまり、表１の母集団から事例デ
ータを１件観測した場合、それが
【００４６】
【表６】
【００４７】である確率は０．１である。
【００４８】＜分類結果の条件つき確率＞：事例データ
において、条件Ｃが成立するとは、 １．事例データの条件部に、条件Ｃの肯定条件が全て含
まれ、 ２．事例データの条件部に、条件Ｃの否定条件が全く含
まれないことである。
【００４９】事例データにおいて、条件Ｃのもとで分類
結果Ｒが成立するとは、該事例データにおいて条件Ｃが
成立し、分類結果がＲとなっていることである。
【００５０】母集団が決まれば、その上で条件Ｃのもと
での分類結果Ｒの条件付確率ｐ（Ｒ｜Ｃ）が次式（２）
ように定義される。
【００５１】
【数３】
【００５２】これは、分類結果の条件つき確率とも呼ば
れる。
【００５３】例えば、表５の母集団のもとでは、 ｐ（魚｜水中生活）＝１．０ …（３） である。
【００５４】母集団に存在する全ての条件の組合せのも
とでの分類結果の条件つき確率を全て正しく求める事が
できれば、分類ルールの生成処理は成功裡に完了する
が、これは実際上簡単なことではない。まず、条件付確
率の値を正確に求めるためには多量の事例データが必要
である。つぎに、条件要素がｎ個ある場合、条件の組合
せの総数は２n−１個となり極めて多量の条件付確率を
処理しなければならなくなるからである。
【００５５】そこで、本発明では、統計的に信頼性の高
い条件付確率を優先的に用いて、分類ルールを生成して
いる。
【００５６】本発明では、事例データは１件づつ投入さ
れ、そのたびに事例データベースの更新と分類ルールの
生成・修正が行われる。この分類ルールの生成と修正を
行う処理を「分類ルール生成処理」と呼ぶ事にする。分
類ルール生成処理においては、投入された１件の該事例
データが中心的役割をはたす事になる。そこで、この該
事例データを特に「帰納事例」と呼ぶ。
【００５７】分類ルール生成処理の目的は、与えられた
事例データ集合の条件と分類結果の確率的関係を分類ル
ールとして形式化することである。このため、該帰納事
例に関して、条件部を分類手がかりとして用いて、分類
結果の確率値を高く導き、帰納事例の分類結果に排反す
る分類結果の確率値を低く導くような分類ルールを生成
することが分類ルール生成処理の目標となる。
【００５８】＜事例データの頻度＞：入力された帰納事
例は事例データベースに蓄積されてゆく。既に入力され
た事例データに対応して事例データの頻度が決まる。こ
の頻度は、一般に０以上の実数値を取る。事例データベ
ース上には概念的には以下のような表が作成されてい
る。ただし、実体は表ではなく後述するネットワークで
ある。
【００５９】
【表７】
【００６０】＜分類ルール＞：分類ルールは条件部Ｃ、
分類結果Ｒ、条件部Ｃのもとで分類結果Ｒが成立する条
件つき確率ｐ（Ｒ｜Ｃ）の推定値、および条件部頻度か
らなる。
【００６１】分類ルールの例： 分類ルール：
【００６２】
【表８】
【００６３】分類ルールの２つの数値、条件つき確率の
推定値（例中の確率値）と条件部頻度を説明するために
頻度に関する２つの用語（条件部頻度、ルール成立頻
度）を定義する。
【００６４】＜条件部頻度＞：ある分類ルールｒの条件
部をＣ、事例データの条件部をＤとするとき、Ｄのもと
でＣが成り立つような全ての事例データの頻度の総和を
ｒの条件部頻度と呼ぶ。
【００６５】例： 事例データベース：
【００６６】
【表９】
【００６７】分類ルール：
【００６８】
【表１０】
【００６９】の条件部頻度は５である。なぜならば、水
中生活をする事例が５例あるからである。条件部頻度は
分類結果（上記例では「獣」）には無関係である。
【００７０】＜ルール成立頻度＞：ある分類ルールｒの
条件部をＣ分類結果をＲ、事例データの条件部をＤ、分
類結果をＳとするとき、ＤのもとでＣが成り立ち、 Ｒ＝Ｓ … （４） であるような全ての事例データの頻度の総和をｒのルー
ル成立頻度と呼ぶ。
【００７１】本発明では、条件つき確率の推定値として
次式（５）のラプラスの推定式を用いている。
【００７２】
【数４】
【００７３】ｔ＝１，ｎ＝２やｔ＝０．５，ｎ＝１など
のバリエーションがあるが、特に断らないかぎり、ｔ＝
１，ｎ＝２を用いる。分類ルールの条件つき確率は、式
（２）により定義した母集団により決まる理想的条件付
確率を事例データ集合より推定するものである。
【００７４】事例データを用いて、確率的な分類ルール
を生成し、自動分類の過程で確率値の推定を行うことに
より、分類結果に確実さの定量値として確率値を付与す
ることができる。
【００７５】分類ルールの生成時に否定条件を含む分類
ルールを生成する事が分類精度の向上に有効なことがあ
る。例えば、次のような事例集合が与えられたとしよう
（これまで例として登場した事例集合は無視して、この
事例集合のみが与えられたとする）。
【００７６】
【表１１】
【００７７】但し、
【００７８】
【数５】
【００７９】は論理積を表す記号である。
【００８０】以上の事例から生成されうる分類ルールの
うち、否定条件を含まない分類ルールのみを記述する
と、
【００８１】
【表１２】
【００８２】となる（確率値はラプラスの推定式により
計算）。この分類ルールを用いて、分類問題として条件
＝“水中生活”を解くと、分類結果は、１位“獣”確率
値０．５７、２位“魚”確率値０．４３となる。これ
は、誤っており、１位が“魚”、２位が“獣”となるの
が正しい。
【００８３】ここで、否定条件付の分類ルールも記述す
る。
【００８４】
【表１３】
【００８５】
【数６】
【００８６】は否定を表す記号であり、
【００８７】
【数７】
【００８８】は、“肺呼吸”という条件が無いことを示
している。
【００８９】この分類ルールを用いて、分類問題として
条件＝“水中生活”を解くと、１位“魚”確率値０．６
７、２位“獣”確率値０．３３と正しい順序の分類結果
が得られる。
【００９０】以上のように否定条件つきの分類ルールは
分類精度の向上に有効であるが、その生成は否定条件な
しの分類ルールほど容易ではない。それは、否定条件な
しの分類ルールは帰納事例の条件を組み合わせる事によ
り生成可能であるのに対して、否定条件つきの分類ルー
ルでは、否定条件が帰納事例の条件に含まれておらず過
去の事例集合から探索する必要があるためである。以降
では、まず本発明の全体像を示し、次に否定条件なしの
分類ルールの生成方法を説明し、その後に、否定条件つ
きの分類ルールの生成方法を示す。
【００９１】
【発明の実施の形態】次に、本発明の実施の形態につい
て図面を参照して詳細に説明する。
【００９２】図１及び図２は、本発明の実施の形態に係
る分類装置の構成を示すブロック図である。図１は、請
求項１の発明の実施の形態に対応し、図２は、請求項３
に記載の実施の形態に対応している。以下では、図２を
参照して、分類ルール生成時と分類時の処理手順を説明
する。図１との処理手順の違いは後述する。
【００９３】図１を参照すると、本発明の実施の形態
は、既知事例データおよび未知事例データを入力する入
力装置１０３と、確率的な情報を含む分類ルールを蓄え
る分類ルールデータベース１０６と、前記既知事例デー
タを条件部の論理関係に基づいてネットワーク化して蓄
積する事例データベース１０５と、入力された前記既知
事例データおよび前記未知事例データの条件部と前記分
類ルールを用いて分類結果の確率値を推定する確率値推
定装置１０２と、分類ルールの有効性を統計的検定によ
り評価することにより無駄な分類ルールの生成を抑制す
る分類ルール生成装置１０１と、出力装置１０４と、を
含んで構成されている。
【００９４】また、図２を参照すると、図１の構成に、
更に、否定条件探索装置１０７を備えた構成とされ、否
定条件探索装置１０７は、入力された前記既知事例デー
タの条件部全部あるいは条件の一部を入力として受取
り、前記事例データベースを探索して否定条件を含む事
例ノードを推定し、分類ルール生成装置１０１は否定条
件探索装置１０７を用いて、否定条件を含む分類ルール
を生成する機能を具備している。
【００９５】＜分類ルール生成時の処理手順＞： ステップ１：入力装置から分類結果が既知の事例データ
１個の入力を受け、分類ルール生成装置１０１と確率値
推定装置１０２へ転送する。この事例データは、以降の
処理で他の事例とは異る役割を果たすため、これを特に
「帰納事例」と呼ぶ。
【００９６】ステップ２：分類ルール生成装置１０１
は、事例データベース１０５へ帰納事例の追加を行う。
【００９７】ステップ３：確率値推定装置１０２は、帰
納事例の条件と分類ルールデータベース１０６を用いて
分類結果とその確率値を求める。
【００９８】ステップ４：分類結果が外れていた場合に
は、分類ルールの生成を行うためステップ５へ、分類結
果が正しい場合にはステップ９へ分岐する。
【００９９】ステップ５：分類ルール生成装置１０１
は、まず、否定条件を含まない分類ルールの生成の試み
を行い、生成できればステップ９へ分岐する。
【０１００】ステップ６：分類ルール生成装置１０１
は、否定条件探索装置１０７へ探索条件を送る。
【０１０１】ステップ７：否定条件探索装置１０７は、
事例データベース１０５を探索して、検索条件に適合す
る否定条件を求め、分類ルール生成装置１０１へ転送す
る。
【０１０２】ステップ８：分類ルール生成装置１０１
は、否定条件付の分類ルールを生成して分類ルールデー
タベース１０６へ追加する。
【０１０３】ステップ９：次の事例データがあればステ
ップ１へ戻り、無ければ終了する。
【０１０４】図１に示す分類装置では、否定条件探索装
置１０７が設けられていないため、上記ステップ６，ス
テップ７，ステップ８の処理が省略される。
【０１０５】＜自動分類時の処理手順＞： ステップ１：入力装置１０３から分類結果が未知の事例
データの入力を受け取り、確率値推定装置１０２へ転送
する。
【０１０６】ステップ２：確率値推定装置１０２は該事
例データの条件と分類ルールデータベースを用いて分類
結果とその確率値を求める。
【０１０７】ステップ３：次の事例データがあればステ
ップ１へ、無ければ終了する。
【０１０８】図１の分類装置でも同様である。
【０１０９】＜否定条件なしの分類ルール生成方法＞：
否定条件なしの分類ルールは、原則として事例の条件を
組み合わせる事により生成する事ができる。
【０１１０】例：
【０１１１】
【表１４】
【０１１２】に対しては、以下の分類ルールが生成可能
である。
【０１１３】
【表１５】
【０１１４】ただし、すべての分類ルールを生成すると
総ルール数が爆発的に増大する為、現実的な応用に際し
ては、有益な分類ルールのみを生成するようにコントロ
ールする事が重要である。生成可能な分類ルール数は、
事例の条件数をｎとすると、その組合せの総数２n−１
だけ存在する。例えば、ｎ＝１０のとき、生成可能な分
類ルール数は１０２３となる。ｎが大きくなるにつれて
この数は爆発的に増大するため、有益な分類ルールのみ
を生成するような手段が必要になる。
【０１１５】本発明においては、有益な分類ルールのみ
を生成するため以下の２つの手段を用いている。
【０１１６】１．第１の手段として、統計的検定によっ
て分類ルールの有効性を判定する。これは請求項１に対
応している。
【０１１７】２．第２の手段として、帰納事例がうまく
分類できた場合は、新しい分類ルールは生成しない。こ
れは請求項２に対応している。
【０１１８】以下では、統計的検定による分類ルールの
有効性判定手順を説明する。
【０１１９】＜分類ルールの有効性＞：分類ルールの有
効性は観念的には以下のように定義される。
【０１２０】１．分類ルールｒの分類結果をＲ条件部を
Ｃとするとき、条件つき確率のｐ〜（Ｒ｜Ｃ）が、母集
団から決まる条件つき確率ｐ（Ｒ｜Ｃ）と近い値を取
り、 ２．分類ルールｒを分類ルールベースに追加する前の分
類システムの分類能力と追加した後の分類能力が大きく
異るとき、分類ルールｒを有効とする。
【０１２１】第１の条件は、条件つき確率ｐ（Ｒ｜Ｃ）
の推定にラプラスの推定式（５）を用いる事によりある
程度満足されている。第２の条件の判定方法を以下に述
べる。この判定では、既存の分類ルールベースから追加
しようとする分類ルールが導けるかどうかが焦点とな
る。
【０１２２】＜ルール有効性判定手順＞： ステップ１：帰納事例を事例データベースに追加する。
【０１２３】ステップ２：該事例データベースを用い
て、有効性判定対象の分類ルールの条件部頻度とルール
成立頻度を得る。以下では、有効性判定対象の分類ルー
ルを「当該分類ルール」と呼ぶ。
【０１２４】ステップ３：既存の分類ルールベースを用
いて、当該分類ルールの条件部Ｃを分類手がかりとして
自動分類する（自動分類の１例として、特開平7-200545
号公報に記載の確率的演繹推論装置による分類が用いら
れる）。その結果、当該分類ルールの分類結果Ｒの条件
つき確率の推定値ｐ〜（Ｒ｜Ｃ）が得られる。
【０１２５】ステップ４：該条件つき確率推定値ｐ〜
（Ｒ｜Ｃ）のもとで該条件部頻度と該ルール成立頻度以
上の異常な状態が起こる確率ｑを計算する。
【０１２６】ステップ５：該確率ｑがあらかじめ設定さ
れた危険率以上である場合、当該分類ルールは既存の分
類ルールベースから自然に導けることがわかる。そこ
で、当該分類ルールは有効でないと判定する。
【０１２７】逆に、ｑがあらかじめ設定された危険率未
満である場合、当該分類ルールは既存の分類ルールベー
スから自然に導けるものではなく特殊なものであること
がわかる。そこで、当該分類ルールを有効と判定する。
【０１２８】例：有効性判定対象の分類ルールを、
【０１２９】
【表１６】
【０１３０】とする。
【０１３１】まず、既存の分類ルールベースを用いて、
条件付確率
【０１３２】
【数８】
【０１３３】を推定する。そのため、
【０１３４】
【数９】
【０１３５】のもとで成立する分類ルールの集合を求め
る。
【０１３６】例：
【０１３７】
【表１７】
【０１３８】これらの分類ルールの確率値を用いて、条
件付確率
【０１３９】
【数１０】
【０１４０】を推定する。これには幾つかの推定方法が
あるが、１例として、特開平７−２００５４５号公報に
記載の確率的演繹推論装置をあげる。
【０１４１】詳細は省略するが、既存の分類ルールベー
スと推定手段を用いて分類手がかり
【０１４２】
【数１１】
【０１４３】のもとで分類結果「獣」が出現する確率の
推定値
【０１４４】
【数１２】
【０１４５】が０．２と推定されたとする。
【０１４６】また、事例データベースから得られた当該
分類ルールの頻度は、 条件部頻度 ＝１０， ルール成立頻度＝ ９ であるとする。
【０１４７】このとき、生成しようとする分類ルールの
成立確率をｐと仮定した基で、事例データベースから求
めた頻度以上に異常な状態が起こる確率ｑは、
【０１４８】
【数１３】
【０１４９】と極めて低い。
【０１５０】この確率値があらかじめ設定される危険率
（０．０５，０．１等）を下回った場合、生成しようと
する分類ルールは既存の分類ルールとは異ると判定され
る。これは生成しようとする分類ルールが有効であるこ
とを示しているので、ラプラスの推定式（５）を用いて
確率値を求め、分類ルールベースに追加する。追加され
る分類ルールを以下に示す。
【０１５１】
【表１８】
【０１５２】一方、確率値ｑが危険率を上回る値であっ
た場合は、有効とは判断できないため、分類ルールには
追加されない。なお、危険率は統計的検定に用いられる
閾値であり、帰無仮説を誤って棄却する確率である。分
類ルールの有効性判定においては、無効な分類ルールを
生成してしまう確率である。
【０１５３】以上では概念的な説明のために確率値ｑを
計算して危険率と比較する統計的検定方法を示した。し
かし統計的検定には様々な方法があり、本発明では発明
の請求範囲を上記の確率計算法に限らず、適用可能な全
ての統計的検定方式を用いる。
【０１５４】＜否定条件つき分類ルールの生成手順＞：
前述したように適切な否定条件つき分類ルールは分類精
度を向上させる。以下ではその生成手順を説明するが事
例データベースの探索を無駄無く行うことにより計算時
間の短縮と記憶装置の負担を軽減している。これは請求
項３に対応している。
【０１５５】否定条件つき分類ルールの生成手順では、 ステップ１：追加すべき否定条件を事例データベースか
ら探索し、分類ルールを生成し ステップ２：統計的検定を行い分類ルールの有効性の判
定を行い、 ステップ３：有効と判定されたものを分類ルールベース
に追加する。
【０１５６】否定条件の検索では、事例データベースを
条件の簡単なものから複雑なものへとたどりながら、否
定条件となり得る条件を探索するが、事例データベース
は条件の論理的関係に基いたネットワークを構成してお
り、これが検索時間の短縮を実現している。統計的検定
による分類ルールの有効性判定は否定条件なしの場合と
同様である。
【０１５７】否定条件の検索を説明する前に、事例デー
タベースの構成を説明する。事例データベースの構成要
素を、事例ノードと呼び、図３に示すように、一意番
号、条件、検査マーク、下位事例リスト、事例情報から
構成する。以下にその意味を示す。
【０１５８】一意番号：事例ノードを一意に示す番号。
【０１５９】条件： 事例ノードの条件部を記録する。
【０１６０】検査マーク：否定条件の検索などの処理に
おいて、この事例ノードが既に処理されたかどうかを記
録する。
【０１６１】下位事例リスト： 下位事例ノードを記録
したリスト。“下位事例ノード”の意味は後述する。
【０１６２】事例情報： 事例ノードの条件のもとで、
どのような分類結果が何回現れたかを記録する。
【０１６３】＜下位の事例ノード＞：事例ノードＥの条
件部をＣとするとき、条件部Ｃの条件を全て含む事例ノ
ードの集合をＳとする。Ｓの中で、他の事例の条件を完
全に含むことはない（もっとも簡単な条件部を持つ）事
例ノードをＥの“下位事例ノード”あるいは“下位ノー
ド”と呼ぶ。下位事例ノードは複数あり得る。
【０１６４】例：事例ノードとその条件部が以下の表の
時、Ｅ０の下位事例ノードはＥ１，Ｅ２である。Ｅ４は
Ｅ０の下位事例ノードにはならない。
【０１６５】
【表１９】
【０１６６】事例情報の例：事例の集合、
【０１６７】
【表２０】
【０１６８】は、事例ノード
【０１６９】
【表２１】
【０１７０】に対応する。この事例情報は、条件“水中
生活”に対して分類結果“獣”の事例が３件、“魚”の
事例が２件存在した事を記録している。
【０１７１】同位事例ノード：ある事例ノードは複数の
下位事例ノードを持つことがあるが、これらの下位事例
ノードを互いに“同位事例ノード”あるいは“同位ノー
ド”と呼ぶ。
【０１７２】上位事例ノード：ある事例ノードＥを下位
事例ノードとする事例ノードＦはＥから見て“上位事例
ノード”あるいは“上位ノード”と呼ばれる。
【０１７３】事例データベース１０５は、事例の探索の
速度を効率化するため、個別条件毎に、探索エントリポ
イントという事例ノードのリストを生成する。
【０１７４】探索エントリポイント：探索エントリポイ
ントは１つの条件に対して１個存在しており、その条件
を含む最も簡単な事例ノードのリストで構成される。
【０１７５】事例が多数与えられると、事例ノードは連
結され、ネットワークを形成する。以下の事例が与えら
れた後の事例ノードの連結例を図４に示す。
【０１７６】
【表２２】
【０１７７】事例データの入力とともに上位、下位の連
結を更新しながら事例データベースが形成される。この
事例データベースを用いれば、ある条件と分類結果が与
えられた際に、既知の事例中での条件の成立頻度と分類
結果の成立頻度を効率的に求めることができる。
【０１７８】事例ノードＥを含んでそれ以下の下位の事
例ノードの条件成立頻度の総和をＥの条件総頻度、分類
結果Ｒの総成立頻度を条件ＥにおけるＲの成立総頻度と
呼ぶ。条件総頻度はＥの条件以外は無視した際の事例の
個数であり、Ｒの成立総頻度は同じくＲの成立する事例
の個数である。これらの値は、事例ノードに記憶してお
いてもよい。
【０１７９】＜否定条件の検索手順＞：否定条件は、前
述したように帰納事例（分類ルール生成の手がかりとな
る１件の事例）に含まれていないので、事例データベー
スを検索して発見しなければならない。その具体的な手
順は、図５に示されているが、ここでは概念的に説明す
る。
【０１８０】否定条件の検索では、分類結果Ｒと検索条
件Ｃが当られる。これが、図２に示した分類装置のブロ
ック図において、分類ルール生成装置１０１から否定条
件検索装置１０７へ送られる情報である。
【０１８１】検索条件としては、 １．帰納事例の条件 ２．帰納事例を自動分類する際に利用される既存の分類
ルールの条件 などが与えられる。
【０１８２】２の肯定条件は１の部分集合であり、検索
時間の短縮効果がある。この検索条件を用いて否定条件
の検索を行う。以下の手順は、分類結果Ｒを高い確率で
積極的に導く分類ルールを生成する場合を想定する。分
類結果Ｒを低い確率で否定的に導く分類ルールを生成す
る場合は、確率値や検定の考え方が逆になる。
【０１８３】探索は、検索条件の一部を含み検索条件と
矛盾しないような事例ノードのうち、条件の少い事例ノ
ードから始めて、下位の事例ノードへと進められる。あ
る事例ノードにおいて、以下の条件が満たされた場合、
この事例ノードには否定条件が含まれると推定する。
【０１８４】［否定条件を含む事例ノードの条件］：あ
る事例ノードＥの条件総頻度をｎ，分類結果Ｒの成立総
頻度をｓとし、Ｅの上位事例ノードＦにおける条件総頻
度をｍ分類結果Ｒの成立総頻度をｔとする。あるＦにつ
いて、ｔ／ｍが十分高く、ｓ／ｎが十分低く、ｔ／ｍと
ｓ／ｎの間に有為な差がある場合、事例ノードＥは否定
条件を含むと推定する。
【０１８５】否定条件を含むと推定された事例ノードの
条件Ｄと帰納事例の条件の差分を否定条件とする。
【０１８６】＜ソフトウェア関連発明に関する説明＞：
図８は、請求項４の処理手順記録媒体を含む分類装置の
ブロック図である。図８を参照すると、本発明の分類装
置は、図１に示した構成に加えて、分類ルール生成装置
駆動プログラムを記録した処理手順記憶媒体１０８を備
える。この処理手順記録媒体１０８は磁気ディスク、半
導体メモリその他の記録媒体であってよい。また、分類
ルール生成装置駆動プログラムに係わる分類ルール生成
装置１０１は、請求項４でいうコンピュータにより実現
される。
【０１８７】分類ルール生成装置駆動プログラムには、
既に述べた、分類ルール生成時の処理手順、自動分類時
の処理手順、ルール有効性判定手順が含まれている。こ
れらは、分類装置の初期設定時に、処理手順記録媒体１
０８から分類ルール生成装置１０１をなすコンピュータ
に読み込まれ、実行される。
【０１８８】図９は、請求項５の処理手順記録媒体を含
む分類装置のブロック図である。図９によると、本発明
の分類装置は、図２に示した構成に加えて、装置駆動プ
ログラムを記録した処理手順記憶媒体１０８を備える。
この処理手順記録媒体１０８は、磁気ディスク、半導体
メモリその他の記録媒体であってよい。また、この装置
駆動プログラムに係わる分類ルール生成装置１０１と否
定条件探索装置１０７は、請求項５でいうコンピュータ
により実現される。
【０１８９】この装置駆動プログラムには、既に述べ
た、分類ルール生成時の処理手順、自動分類時の処理手
順、ルール有効性判定手順、否定条件つき分類ルールの
生成手段、否定条件の検索手順が含まれている。これら
のうち、分類ルール生成時の処理手順、自動分類時の処
理手順、ルール有効性判定手順、否定条件つき分類ルー
ルの生成手順は、分類装置の、初期設定時に、処理手順
記録媒体１０８から分類ルール生成装置１０１をなすコ
ンピュータに読み込まれ、既に述べた手順により実行さ
れる。
【０１９０】また、否定条件の検索手順は、分類装置の
初期設定時に、処理手順記録媒体から否定条件探索装置
１０８をなすコンピュータに読み込まれ、既に述べた手
順により実行される。
【０１９１】
【実施例】上記した本発明の実施の形態について更に詳
細に説明すべく、本発明の実施例について以下に説明す
る。
【０１９２】図１は、請求項１の発明の一実施例に係る
分類装置の構成を示すブロック図である。図２は、請求
項３の発明の一実施例に係る分類装置のブロック図であ
る。図１を参照すると、本実施例に係る分類装置は、既
知事例データおよび未知事例データを入力する入力装置
１０３と、確率的な情報を含む分類ルールを蓄える分類
ルールデータベース１０６と、前記既知事例データを条
件部の論理関係に基づいてネットワーク化して蓄積する
事例データベース１０５と、入力された前記既知事例デ
ータおよび前記未知事例データの条件部と前記分類ルー
ルを用いて分類結果の確率値を推定する確率値推定装置
１０２と、分類ルールの有効性を統計的検定により評価
することにより無駄な分類ルールの生成を抑制する分類
ルール生成装置１０１と、出力装置１０４と、を含んで
構成されている。
【０１９３】また図２を参照すると、この分類装置は、
図１の構成に、更に、否定条件探索装置１０７を備えた
構成とされ、否定条件探索装置１０７は、入力された前
記既知事例データの条件部全部あるいは条件の一部を入
力として受取り、前記事例データベースを探索して否定
条件を含む事例ノードを推定し、分類ルール生成装置１
０１は否定条件探索装置１０７を用いて、否定条件を含
む分類ルールを生成する機能を具備している。
【０１９４】これらの分類装置における分類ルールの生
成手順を以下に示す。
【０１９５】＜分類ルールの生成手順＞：図５は、分類
ルールの生成手順の一実施例を示す流れ図である。装置
名称については、図２に示した分類装置のブロック図に
対応している。本実施例は、請求項１，２，３全てに対
応しているが、各請求項に限定する場合は後述する。
【０１９６】ステップ（Ｓｔｅｐ）１：入力装置１０３
から事例データ（帰納事例）１個の入力を受け、分類ル
ール生成装置１０１と確率値推定装置１０２へ転送す
る。
【０１９７】ステップ２：分類ルール生成装置１０１は
事例データベース１０５へ帰納事例の追加を行う。
【０１９８】ステップ３：確率値推定装置１０２を用い
て帰納事例の条件部と分類ルールから分類結果とその確
率値を求める。
【０１９９】ステップ４：各々の分類結果について、推
定した確率値と正解確率値が設定された閾値以上に隔た
っている場合には、分類結果が外れているものと判定す
る。推定が外れた分類結果は全て“推定結果誤りリス
ト”に記録する。
【０２００】ステップ５：推定結果誤りリストが空であ
れば、ステップ１へ移り、そうでなければ、ステップ６
の処理へ進む。
【０２０１】ステップ６：推定結果誤りリストの先頭の
分類結果が、ステップ６からステップ１２までの処理の
対象となる分類ルールの分類結果となる。確率値推定装
置１０２から、ステップ３の分類時に用いた分類ルール
を、分類ルール生成装置１０１に転送する。
【０２０２】ステップ７：帰納事例の条件を各個の条件
単位に分解し追加条件集合Ｓを生成する。
【０２０３】
【数１４】
【０２０４】追加条件集合Ｓ＝水中生活、肺呼吸
【０２０５】ステップ８：該分類ルール各々に該追加条
件集合Ｓの要素である各個の条件を追加して、新しい分
類ルールの条件を生成する。追加すべき条件の個数の上
限値は、装置起動時に外部から与えられる。
【０２０６】ステップ９：ステップ８で生成した新分類
ルールの条件部頻度、ルール成立頻度を事例データベー
スより求め、ステップ３で求めた確率値ｐを用いて、前
記本発明の発明の実施の形態で説明し、た統計的検定に
より該新分類ルールの有効性を判定する。該新分類ルー
ルが有効であればステップ１１へ、無効ならばステップ
１０へ進む。
【０２０７】ステップ１０：生成の対象となる新しい分
類ルールが残っていればステップ８へ、さもなければ、
ステップ１２へ進む。
【０２０８】ステップ１１：該新分類ルールを分類ルー
ルデータベース１０６に追加する。
【０２０９】ステップ１２：否定条件を含む分類ルール
の生成を試みる。
【０２１０】ステップ１３：分類結果誤りリストの先頭
分類結果を除去する。除去された分類結果はステップ６
からステップ１３までの処理で分類ルールの分類結果と
なって来たものである。分類結果誤りリストの要素が残
っていればステップ６へ。
【０２１１】ステップ１４：事例データが残っていれ
ば、ステップ１へ、さもなければ終了する。
【０２１２】なお、請求項１の実施例に限定する場合
は、上記の分類ルールの生成手順に、以下に記載の修正
を行う。また、対応するブロック図は、図に示す構成と
される。
【０２１３】修正： ステップ４：自動分類の結果が誤りであった場合はすべ
ての分類結果を“推定結果誤りリスト”に記録する。
【０２１４】ステップ１２：行わない。
【０２１５】自動分類の結果が誤りであるかどうかの判
定には以下のような方法がある。
【０２１６】・確率値の高い順に自動分類の分類結果を
並べて、その１位が帰納事例の分類結果と一致していな
ければ誤りと判断する。
【０２１７】・確率値の高い順に自動分類の分類結果を
並べて、その１位の確率値があらかじめ設定した閾値を
超え、２位の確率値が別にあらかじめ設定した閾値を下
回る場合、１位が帰納事例の分類結果と一致していなけ
れば誤りと判断する。
【０２１８】・自動分類の結果出力された上位の分類結
果の確率値を総和が１になるように正規化し、１位の確
率値があらかじめ設定した閾値を超えた場合、１位が帰
納事例の分類結果と一致していなければ誤りと判断す
る。
【０２１９】請求項１、２に限定する場合は、上記の分
類ルールの生成手順に以下に記載の修正を行う。また、
対応するブロック図は、図１となる。
【０２２０】修正： ステップ１２：行わない。
【０２２１】＜否定条件を含む分類ルールの生成手順
＞：これは、請求項３の分類ルール生成装置における分
類ルール生成手順である。
【０２２２】図６は、固定条件を含む分類ルールの生成
手順の一実施例である。これは５のステップ１２で利用
される手順の一実施例の流れ図である。
【０２２３】ステップ１：自動分類に用いられた分類ル
ールのうちから望ましくない確率値を持つ分類ルールの
条件をすべて集め条件集合Ｓを生成する。
【０２２４】望ましくない確率値を持つ分類ルールと
は、 １．正しい分類結果を導くべき分類ルールの場合は、確
率値が設定された閾値よりも有意に低いものであり、 ２．誤った分類結果を導くべき分類ルールの場合は、確
率値が設定された閾値よりも有意に高いものである。
【０２２５】ステップ２：該条件集合Ｓを論理的に成立
させるような事例ノードを全て集め、これを事例集合Ｅ
とする。
【０２２６】ステップ３：Ｅの要素である事例ノード各
々について、否定条件を含んでいるかどうかの推定をお
こない、得られた否定条件を否定条件集合Ｎに累積す
る。
【０２２７】この推定方法は、上記発明の実施の形態で
説明されている。
【０２２８】ステップ４：該条件集合Ｓに該否定条件集
合Ｎを追加して新しい分類ルール候補ｈの条件部とす
る。
【０２２９】ステップ５：該分類ルール候補ｈの有効性
を統計的検定により判定する。その際、事例データベー
スからｈの条件成立頻度とルール成立頻度を求める。
【０２３０】ステップ６：有効であれば該分類ルール候
補ｈを分類ルールとして生成する。
【０２３１】図７は、否定条件の探索手順の一実施例の
流れ図である。これは、“否定条件を含む分類ルールの
生成手順”および図６のステップ２で用いられた事例ノ
ード探索手順でもある。
【０２３２】図７において、開始時点では、検索条件と
分類結果が与えられる。また、図７中の用語の意味は以
下の通りである。
【０２３３】ノードスタック：検索対象の事例ノードを
一時格納するスタック。単に“スタック”と呼ぶ場合も
ある。一般にスタックとは、先入れ、後出し式の記憶装
置である。
【０２３４】復帰状態スタック：スタックと連動するス
タックで、ノードスタックの先頭ノードを処理し終えて
次の事例ノードを処理する際にどのステップから始める
かを示す。
【０２３５】回答ノードリスト：探索手順が回答として
返す事例ノードのリスト。
【０２３６】ステップ１：初期設定を行う。検索条件を
個別の条件単位に分解し、各条件のエントリーポイント
の事例ノードを順にノードスタックに積む。最初の事例
ノードを積んだ際に復帰状態スタックに“終了”を積
む。つぎの事例ノードからは１個積むと同時に復帰状態
スタックに“ステップ２”を１個積む。
【０２３７】ステップ２：探索開始。ノードスタックの
先頭事例ノードを探索対象ノードとする。
【０２３８】ステップ３：探索対象ノードは「未検査」
状態か判定し、未検査ならばステップ４へ、検査済なら
ばステップ１２へ進む。
【０２３９】ステップ４：探索対象ノードを「検査済」
とする。
【０２４０】ステップ５：探索対象ノードの基で検索条
件は成立するか判定し、成立するならばステップ６へ、
さもなければステップ８へ進む。
【０２４１】ステップ６：探索対象ノードは否定条件と
なりうるような条件を含んでいるか判定し、含んでいれ
ばステップ７へ、含んでいなければステップ８へ進む。
【０２４２】ステップ７：探索対象ノードを回答ノード
ノストに追加する。
【０２４３】ステップ８：探索対象ノードに同位ノード
は存在するか判定し、存在するならばステップ９へ、存
在しない場合ステップ１０へ進む。
【０２４４】ステップ９：同位ノードをスタック先頭に
積む。さらに復帰状態スタックに“ステップ１０”を積
む。ステップ３へ跳ぶ。
【０２４５】ステップ１０：探索対象ノードの条件総頻
度が設定された閾値を下回っていた場合、下位ノードの
探索は行わない。下位ノードの探索を行う場合ステップ
１１へ、行わない場合ステップ１２へ進む。
【０２４６】ステップ１１：下位ノードをノードスタッ
ク先頭に積む。復帰状態スタックに“ステップ１２”を
積み、ステップ３に跳ぶ。
【０２４７】ステップ１２：スタック先頭ノードを除去
する。その結果２番目の事例ノードがあれば、これがス
タック先頭ノードとなり、同時に探索対象ノードとす
る。
【０２４８】ステップ１３：復帰状態スタックの先頭要
素を復帰変数に退避し、先頭要素を除去する。
【０２４９】ステップ１４：復帰変数＝“ステップ１
０”ならばステップ１０に跳ぶ。
【０２５０】ステップ１５：復帰変数＝“ステップ１
２”ならばステップ１２に跳ぶ。
【０２５１】ステップ１６：復帰変数＝“終了”ならば
終了に跳ぶ。
【０２５２】
【発明の効果】以上に示したように、本発明によれば、
現実的な分類問題に対して有効な自動分類を行うため
に、分類ルールの生成時にそのルールの有効性を判定
し、無駄な分類ルールの生成を防ぐ手段を備え、条件の
論理的関係に基づいてネットワーク化された事例データ
ベースを探索することにより、否定条件を発見し、否定
条件つきの分類ルールを生成する手段を備え、第１の手
段により、分類ルールの記憶のために必要な記憶装置の
総量を減少させることができ、分類ルールの理由・操作
の処理時間を短縮させることができる、という効果を奏
する。これは、現実問題を解く際に有効である。
【０２５３】また、本発明によれば、第２の手段によ
り、全事例を探索するよりも短い処理時間で否定条件の
探索を行うことができ、否定条件つきの分類ルールを効
率的に生成することができるという効果を奏する。否定
条件つきの分類ルールは自動分類の精度向上につなが
る。
【図面の簡単な説明】
【図１】本発明の一実施例の構成を示すブロック図であ
る。
【図２】本発明の別の実施例の構成を示すブロック図で
ある。
【図３】本発明の実施例を説明するための図であり、事
例ノードの概念図である。
【図４】本発明の実施例を説明するための図であり、連
結した事例ノードを示す例を表す図である。
【図５】本発明における分類ルールの生成の手順の一実
施例を示す図である。
【図６】本発明において否定条件を含む分類ルールの生
成の手順の一実施例を示す図である。
【図７】本発明において否定条件を含む事例ノードの探
索手順の一実施例を示す図である。
【図８】本発明の処理手順記録媒体を含む分類装置のブ
ロック図を示す図である。
【図９】本発明の処理手順記録媒体を含む分類装置ブロ
ック図を示す図である。
【符号の説明】
１０１ 分類ルール生成装置 １０２ 確率値推定装置 １０３ 入力装置 １０４ 出力装置 １０５ 事例データベース １０６ 分類ルールデータベース １０７ 否定条件探索装置 １０８ 処理手順記録媒体
フロントページの続き (56)参考文献 特開 平６−44206（ＪＰ，Ａ) 特開 平５−35484（ＪＰ，Ａ) 特開 平７−200545（ＪＰ，Ａ) 斉藤、中野、「ノイズを含む事例から のルール抽出：ＲＦ３アルゴリズム」、 情報処理学会論文誌、Ｖｏｌ．33、Ｎ ｏ．５、社団法人情報処理学会・発行 （1992年）、ｐｐ．636〜644（特許庁Ｃ ＳＤＢ文献番号：ＣＳＮＴ 199800280007) 吉田、山村、小林、「属性の識別能力 の局所性を考慮した確率的決定木の構 築」、人工知能学会誌、Ｖｏｌ．11、Ｎ ｏ．２、社団法人人工知能学会・発行 （1996年３月）、ｐｐ．264〜272（特許 庁ＣＳＤＢ文献番号：ＣＳＮＴ 199800390010) 谷澤、上原、前川、「典型性に基づく 概念学習アルゴリズム」、情報処理学会 研究報告、Ｖｏｌ．93、Ｎｏ．５（93− ＡＩ−86）、社団法人情報処理学会・発 行（1993年）、ｐｐ．33〜40（特許庁Ｃ ＳＤＢ文献番号：ＣＳＮＴ 199800022005) (58)調査した分野(Int.Cl.7，ＤＢ名) G06F 9/44 G06F 17/30 ＪＩＣＳＴファイル（ＪＯＩＳ) ＣＳＤＢ（日本国特許庁)

Claims (5)

    (57)【特許請求の範囲】
  1. 【請求項１】分類手がかりとなる条件部と分類結果の組
    を事例データとして、該事例データのなかで分類結果が
    既知である既知事例データを用いて分類ルールを自動生
    成し、分類結果が未知である未知事例データを、前記分
    類ルールを用いて自動分類する分類装置において、 既知事例データおよび未知事例データを入力する入力手
    段と、 確率的な情報を含む分類ルールを蓄える分類ルールデー
    タベースと、 前記既知事例データを条件部の論理関係に基づいてネッ
    トワーク化して蓄積する事例データベースと、 入力された前記既知事例データおよび前記未知事例デー
    タの条件部と前記分類ルールを用いて分類結果の確率値
    を推定する確率値推定手段と、 分類ルールの有効性を統計的検定により評価することに
    より無駄な分類ルールの生成を抑制する分類ルール生成
    手段と、 を備え、 前記分類ルール生成手段が、前記入力手段から入力され
    た前記既知事例データの分類結果の確率値と、前記確率
    値推定手段から出力される分類結果の確率値と、を比較
    して、分類ルールを生成するか抑制するかを判定する、
    ことを特徴とする分類装置。
  2. 【請求項２】分類手がかりとなる条件部と分類結果の組
    を事例データとして、該事例データのなかで分類結果が
    既知である既知事例データを用いて分類ルールを自動生
    成し、分類結果が未知である未知事例データを、前記分
    類ルールを用いて自動分類する分類装置において、 既知事例データおよび未知事例データを入力する入力手
    段と、 確率的な情報を含む分類ルールを蓄える分類ルールデー
    タベースと、 前記既知事例データを条件部の論理関係に基づいてネッ
    トワーク化して蓄積する事例データベースと、 入力された前記既知事例データおよび前記未知事例デー
    タの条件部と前記分類 ルールを用いて分類結果の確率値
    を推定する確率値推定手段と、 分類ルールの有効性を統計的検定により評価することに
    より無駄な分類ルールの生成を抑制する分類ルール生成
    手段と、 入力された前記既知事例データの条件部全部あるいは条
    件の一部を入力として受取り、前記事例データベースを
    探索して否定条件を含む事例ノードを推定する否定条件
    探索手段を備え、 前記否定条件探索手段を用いて、否定条件を含む分類ル
    ールを生成する機能を追加した分類ルール生成手段を備
    える、ことを特徴とする分類装置。
  3. 【請求項３】分類手がかりとなる条件部と分類結果の組
    を事例データとして、該事例データのなかで分類結果が
    既知である既知事例データを用いて分類ルールを自動生
    成し、分類結果が未知である未知事例データを、前記分
    類ルールを用いて自動分類する処理を、コンピュータで
    実行させるプログラムを記録した記録媒体において、 前記コンピュータは、既知事例データおよび未知事例デ
    ータを入力する入力手段と、 確率的な情報を含む分類ルールを蓄える分類ルールデー
    タベースと、 前記既知事例データを条件部の論理関係に基づいてネッ
    トワーク化して蓄積する事例データベースと、を備え、 入力された前記既知事例データについて前記分類ルール
    データベースから新しい分類ルールを生成する処理と、 分類ルールの有効性を統計的検定により評価して無駄な
    ルールの生成を抑制するルール有効性判定処理と、入力された前記既知事例データの条件部あるいは条件の
    一部を用いて前記事例データベースを探索して否定条件
    を含む事例ノードを推定する否定条件の検索処理と、 該否定条件の検索手順で推定された否定条件を含む分類
    ルールを生成する否定条件つき分類ルールの生成処理
    と、 を前記コンピュータに実行させるためのプログラムを記
    録した記録媒体。
  4. 【請求項４】分類手がかりとなる条件部と分類結果の組
    を事例データとして、該事例データのなかで分類結果が
    既知である既知事例データを用いて分類ルールを自動生
    成し、分類結果が未知である未知事例データを前記分類
    ルールを用いて自動分類する処理を、コンピュータで実
    行させるプログラムを記録した記録媒体において、 前記コンピュータは、 既知事例データおよび未知事例データを入力する入力装
    置と、 確率的な情報を含む分類ルールを蓄える分類ルールデー
    タベースと、 前記既知事例データを条件部の論理関係に基づいてネッ
    トワーク化して蓄積する事例データベースと、を含み、 （ａ）前記入力装置から入力された前記既知事例データ
    および前記未知事例データの条件部と前記分類ルールを
    用いて分類結果の確率値を推定する確率値推定手段、及
    び、 （ｂ）分類ルールの有効性を統計的検定により評価する
    ことにより無駄な分類ルールの生成を抑制する分類ルー
    ル生成手段であって、前記入力装置から入力された前記
    既知事例データの分類結果の確率値と、前記確率値推定
    手段から出力される分類結果の確率値と、を比較して、
    分類ルールを生成するか抑制するかを判定する分類ルー
    ル生成手段、 の上記（ａ）、（ｂ）の各手段を前記コンピュータ上で
    機能させるためのプログラムを記録した記録媒体。
  5. 【請求項５】分類手がかりとなる条件部と分類結果の組
    を事例データとして、該事例データのなかで分類結果が
    既知である既知事例データを用いて分類ルールを自動生
    成し、分類結果が未知である未知事例データを前記分類
    ルールを用いて自動分類する処理を、コンピュータで実
    行させるプログラムを記録した記録媒体において、 前記コンピュータは、 既知事例データおよび未知事例データを入力する入力装
    置と、 確率的な情報を含む分類ルールを蓄える分類ルールデー
    タベースと、 前記既知事例データを条件部の論理関係に基づいてネッ
    トワーク化して蓄積する事例データベースと、を含み、 （ａ）前記入力装置から入力された前記既知事例データ
    および前記未知事例データの条件部と前記分類ルールを
    用いて分類結果の確率値を推定する手段、 （ｂ）入力された前記既知事例データの条件部全部ある
    いは条件の一部を入力として受取り、前記事例データベ
    ースを探索して否定条件を含む事例ノードを推定する否
    定条件探索手段、及び、 （ｃ）分類ルールの有効性を統計的検定により評価する
    ことにより無駄な分類ルールの生成を抑制する手段であ
    って、前記否定条件探索手段を用いて、否定条件を含む
    分類ルールを生成する機能を備えた分類ルール生成手
    段、 の上記（ａ）〜（ｃ）の各手段を前記コンピュータ上で
    機能させるためのプログラムを記録した記録媒体。
JP27379797A 1997-09-19 1997-09-19 分類装置 Expired - Lifetime JP3209163B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP27379797A JP3209163B2 (ja) 1997-09-19 1997-09-19 分類装置
US09/157,315 US6266656B1 (en) 1997-09-19 1998-09-21 Classification apparatus

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP27379797A JP3209163B2 (ja) 1997-09-19 1997-09-19 分類装置

Publications (2)

Publication Number Publication Date
JPH1196010A JPH1196010A (ja) 1999-04-09
JP3209163B2 true JP3209163B2 (ja) 2001-09-17

Family

ID=17532726

Family Applications (1)

Application Number Title Priority Date Filing Date
JP27379797A Expired - Lifetime JP3209163B2 (ja) 1997-09-19 1997-09-19 分類装置

Country Status (2)

Country Link
US (1) US6266656B1 (ja)
JP (1) JP3209163B2 (ja)

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020128858A1 (en) * 2001-01-06 2002-09-12 Fuller Douglas Neal Method and system for population classification
US20030018486A1 (en) * 2001-06-25 2003-01-23 Jacob Feldman Consistency validation for complex classification rules
US7035877B2 (en) 2001-12-28 2006-04-25 Kimberly-Clark Worldwide, Inc. Quality management and intelligent manufacturing with labels and smart tags in event-based product manufacturing
US7380213B2 (en) 2001-12-28 2008-05-27 Kimberly-Clark Worldwide, Inc. User interface for reporting event-based production information in product manufacturing
US8799113B2 (en) 2001-12-28 2014-08-05 Binforma Group Limited Liability Company Quality management by validating a bill of materials in event-based product manufacturing
US7357298B2 (en) * 2001-12-28 2008-04-15 Kimberly-Clark Worldwide, Inc. Integrating event-based production information with financial and purchasing systems in product manufacturing
US7032816B2 (en) * 2001-12-28 2006-04-25 Kimberly-Clark Worldwide, Inc. Communication between machines and feed-forward control in event-based product manufacturing
US6968250B2 (en) * 2001-12-28 2005-11-22 Kimberly-Clark Worldwide, Inc. Intelligent agent system and method for evaluating data integrity in process information databases
US7447641B2 (en) 2002-06-27 2008-11-04 International Business Machines Corporation User interface and algorithm to handle “unknown” data in card-sorting exercise and cluster analysis
US7350187B1 (en) 2003-04-30 2008-03-25 Google Inc. System and methods for automatically creating lists
JP2006277185A (ja) * 2005-03-29 2006-10-12 Osaka Gas Co Ltd 故障予測診断支援システム
JP4429236B2 (ja) * 2005-08-19 2010-03-10 富士通株式会社 分類ルール作成支援方法
WO2007050646A2 (en) * 2005-10-24 2007-05-03 Capsilon Fsg, Inc. A business method using the automated processing of paper and unstructured electronic documents
US8176004B2 (en) * 2005-10-24 2012-05-08 Capsilon Corporation Systems and methods for intelligent paperless document management
US20100274750A1 (en) * 2009-04-22 2010-10-28 Microsoft Corporation Data Classification Pipeline Including Automatic Classification Rules
US9578060B1 (en) 2012-06-11 2017-02-21 Dell Software Inc. System and method for data loss prevention across heterogeneous communications platforms
US9779260B1 (en) 2012-06-11 2017-10-03 Dell Software Inc. Aggregation and classification of secure data
US9501744B1 (en) 2012-06-11 2016-11-22 Dell Software Inc. System and method for classifying data
US9390240B1 (en) * 2012-06-11 2016-07-12 Dell Software Inc. System and method for querying data
US9349016B1 (en) 2014-06-06 2016-05-24 Dell Software Inc. System and method for user-context-based data loss prevention
US10326748B1 (en) 2015-02-25 2019-06-18 Quest Software Inc. Systems and methods for event-based authentication
US10417613B1 (en) 2015-03-17 2019-09-17 Quest Software Inc. Systems and methods of patternizing logged user-initiated events for scheduling functions
US9990506B1 (en) 2015-03-30 2018-06-05 Quest Software Inc. Systems and methods of securing network-accessible peripheral devices
US9842220B1 (en) 2015-04-10 2017-12-12 Dell Software Inc. Systems and methods of secure self-service access to content
US9563782B1 (en) 2015-04-10 2017-02-07 Dell Software Inc. Systems and methods of secure self-service access to content
US9641555B1 (en) 2015-04-10 2017-05-02 Dell Software Inc. Systems and methods of tracking content-exposure events
US9569626B1 (en) 2015-04-10 2017-02-14 Dell Software Inc. Systems and methods of reporting content-exposure events
US9842218B1 (en) 2015-04-10 2017-12-12 Dell Software Inc. Systems and methods of secure self-service access to content
US10536352B1 (en) 2015-08-05 2020-01-14 Quest Software Inc. Systems and methods for tuning cross-platform data collection
US10218588B1 (en) 2015-10-05 2019-02-26 Quest Software Inc. Systems and methods for multi-stream performance patternization and optimization of virtual meetings
US10157358B1 (en) 2015-10-05 2018-12-18 Quest Software Inc. Systems and methods for multi-stream performance patternization and interval-based prediction
US10142391B1 (en) 2016-03-25 2018-11-27 Quest Software Inc. Systems and methods of diagnosing down-layer performance problems via multi-stream performance patternization
US20210350260A1 (en) * 2018-09-21 2021-11-11 Nec Corporation Decision list learning device, decision list learning method, and decision list learning program
US11455321B2 (en) 2020-03-19 2022-09-27 International Business Machines Corporation Deep data classification using governance and machine learning

Family Cites Families (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0743722B2 (ja) 1985-08-02 1995-05-15 株式会社東芝 帰納推論装置
US5140670A (en) * 1989-10-05 1992-08-18 Regents Of The University Of California Cellular neural network
JP3182169B2 (ja) 1991-07-26 2001-07-03 株式会社リコー 故障診断方法
US5361379A (en) * 1991-10-03 1994-11-01 Rockwell International Corporation Soft-decision classifier
US5325445A (en) 1992-05-29 1994-06-28 Eastman Kodak Company Feature classification using supervised statistical pattern recognition
JPH0644206A (ja) 1992-07-24 1994-02-18 Meidensha Corp 帰納的学習システムにおける分岐属性の決定方法
JPH0743722A (ja) 1993-07-28 1995-02-14 Canon Inc 液晶素子
US5720009A (en) * 1993-08-06 1998-02-17 Digital Equipment Corporation Method of rule execution in an expert system using equivalence classes to group database objects
JPH0877010A (ja) 1994-09-07 1996-03-22 Hitachi Ltd データ分析方法および装置
DE4436408C1 (de) 1994-10-12 1995-12-07 Daimler Benz Ag Mustererkennungsverfahren
US5649070A (en) * 1995-02-17 1997-07-15 International Business Machines Corporation Learning system with prototype replacement
US5729452A (en) 1995-03-31 1998-03-17 Envirotest Acquisition Co. Method and system for diagnosing and reporting failure of a vehicle emission test
US5719692A (en) * 1995-07-07 1998-02-17 Lucent Technologies Inc. Rule induction on large noisy data sets
US5809499A (en) 1995-10-20 1998-09-15 Pattern Discovery Software Systems, Ltd. Computational method for discovering patterns in data sets
US5727199A (en) 1995-11-13 1998-03-10 International Business Machines Corporation Database mining using multi-predicate classifiers
US5819007A (en) * 1996-03-15 1998-10-06 Siemens Medical Systems, Inc. Feature-based expert system classifier
US6092059A (en) * 1996-12-27 2000-07-18 Cognex Corporation Automatic classifier for real time inspection and classification

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
吉田、山村、小林、「属性の識別能力の局所性を考慮した確率的決定木の構築」、人工知能学会誌、Ｖｏｌ．１１、Ｎｏ．２、社団法人人工知能学会・発行（１９９６年３月）、ｐｐ．２６４〜２７２（特許庁ＣＳＤＢ文献番号：ＣＳＮＴ１９９８００３９００１０）
斉藤、中野、「ノイズを含む事例からのルール抽出：ＲＦ３アルゴリズム」、情報処理学会論文誌、Ｖｏｌ．３３、Ｎｏ．５、社団法人情報処理学会・発行（１９９２年）、ｐｐ．６３６〜６４４（特許庁ＣＳＤＢ文献番号：ＣＳＮＴ１９９８００２８０００７）
谷澤、上原、前川、「典型性に基づく概念学習アルゴリズム」、情報処理学会研究報告、Ｖｏｌ．９３、Ｎｏ．５（９３−ＡＩ−８６）、社団法人情報処理学会・発行（１９９３年）、ｐｐ．３３〜４０（特許庁ＣＳＤＢ文献番号：ＣＳＮＴ１９９８０００２２００５）

Also Published As

Publication number Publication date
US6266656B1 (en) 2001-07-24
JPH1196010A (ja) 1999-04-09

Similar Documents

Publication Publication Date Title
JP3209163B2 (ja) 分類装置
US6542881B1 (en) System and method for revealing necessary and sufficient conditions for database analysis
US20200089650A1 (en) Techniques for automated data cleansing for machine learning algorithms
CN109033200B (zh) 事件抽取的方法、装置、设备及计算机可读介质
CN111612041A (zh) 异常用户识别方法及装置、存储介质、电子设备
Zheng et al. Feature grouping and selection: A graph-based approach
US20230195851A1 (en) Data classification system, data classification method, and recording medium
CN112685324B (zh) 一种生成测试方案的方法及系统
CN107168995A (zh) 一种数据处理方法及服务器
CN112784054A (zh) 概念图处理装置、概念图处理方法和计算机可读介质
CN112732690B (zh) 一种用于慢病检测及风险评估的稳定系统及方法
KR101965276B1 (ko) 그래프 기반의 데이터 분석 시스템 및 방법과, 이를 위한 컴퓨터 프로그램
Mahanipour et al. Using fuzzy-rough set feature selection for feature construction based on genetic programming
CN116756327A (zh) 基于知识推断的威胁情报关系抽取方法、装置和电子设备
CN118468061B (zh) 一种算法自动匹配及参数优化方法及系统
CN110716761A (zh) 信息处理平台上软件应用的执行参数的自动和自优化确定
CN113362920B (zh) 基于临床数据的特征选择方法及装置
Montañés et al. A wrapper approach with support vector machines for text categorization
CN114610576A (zh) 一种日志生成监控方法和装置
CN113704422A (zh) 一种文本推荐方法、装置、计算机设备和存储介质
CN115393659B (zh) 基于多级决策树的个性化分类流程优化方法和装置
US20230281275A1 (en) Identification method and information processing device
CN110457455A (zh) 一种三值逻辑问答咨询优化方法、系统、介质和设备
Pan The Construction and Application of Library Intelligent Acquisition Decision Model Based on Decision Tree Algorithm.
CN114625880B (zh) 人物关系抽取方法、装置、终端及存储介质

Legal Events

Date Code Title Description
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20010612

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20070713

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20080713

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090713

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100713

Year of fee payment: 9