多数決判別関数のBDDによる簡約化

石井 恵  フセイン アルモアリム  秋葉 泰弘  金田 重郎  

誌名
電子情報通信学会論文誌 D   Vol.J78-D2   No.10   pp.1469-1478
発行日: 1995/10/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: 人工知能,自然言語処理,認知科学
キーワード: 
機械学習,  ID3,  決定木,  簡約化,  BDD,  

本文: PDF(731.3KB)>>
論文を購入




あらまし: 
近年,学習性能向上をねらいとして,訓練事例から複数個の決定木を作成し,テスト事例の判別にこれら決定木による判別結果の多数決を用いる,多数決判別手法が提案されている.しかし,多数決判別手法は,複数個の決定木を用いるため,可読性が悪く,知識ベース構築支援には向かない.そこで,本論文では多数決判別手法の知識ベース構築支援への適用をねらいとして,多数決判別関数全体を積和形式に変換する簡約化手法を提案する.本手法の特徴は,変換過程の内部表現として,BDDを用いる点にある.BDDの利用により,高速な簡約化が実現できる.この際,BDDの入力変数順序決定法が課題となる.本論文では決定木の変数順序に基づく入力変数順序決定法を提案する.実際に,(1)Irvine Database,(2)医療診断データ,を用いて簡約化を行った.簡約化後の記述量は,簡約化前の決定木1個の平均1.2~2.7倍であり,簡約化前の多数決判別関数の記述量の1/3以下となった.従って本手法の記述量削減効果は大きく,知識ベース構築支援に利用できると考える.また,本提案の入力変数順序決定法により,Sun SPARC server 10ワークステーションで数秒~十数秒と高速な簡約化が実現できることを確認した.