概念相違発見手法の高速化の検討
西田研究室　　裏谷　治

1．はじめに

　複数の人間が入力した大規模なデータベースから概念の相違を取り除き，整合性のとれたデータベースとして提供することは，データベースの供給者にとっても，ユーザにとっても重要な課題である． 　我々は従来より，ユーザの知識を決定木で表現するという枠組みにおいて，ID3と遺伝的アルゴリズム（GA）を用いて決定木を生成し，その構造を比較することによって概念の相違を発見する手法に対する研究を進めてきた．
　本研究では，特にGAを用いた手法に焦点を当て，様々な側面からの解析をもとにその有効性と問題点についての検討を行った．その解析結果をもとに，大規模データベースに適用可能とする為に計算量がO(n3) 以下の手法を提供することを目指し，従来のID3とGAの手法を共に取り入れ高速化した新たな手法を提案し，その有効性の検討を行う．

2．システムの概要

　複数の人間の概念の相違を考えるに当たって，まず概念の相違を定義する必要がある．一般的には，概念の相違には種々のレベルが考えられるが，ここでは複数の人間の間に存在する概念の相違として，
のような2つの場合に焦点を絞って取り扱う．
　2人の人間が自分自身の概念に対応するシンボルを用いてクラス・属性・属性値より成る事例を入力すると仮定して，その入力データよりクラス・属性・属性値における概念の相違の検出を行う．

3．高速化アルゴリズム

　従来の手法ではID3よりもGAの方が検出率がよいがGAの計算時間の多さが問題であるということが挙げられているため，GAの手法の高速化を図るためにまずGAを利用した決定木生成部について計算量解析を行った．その結果，GAの手法の計算量と必要な世代数の関係から，現時点ではGAの手法の計算量をO(n3)以下にすることは困難であるという結論に達した．
　そこで計算量を減らす為に，情報量基準に基づいてコンパクトな決定木を生成するID3の特徴を生かし，ID3による決定木をGAの初期世代に用いてGAと同じ操作を10世代だけ繰り返すという新たな高速化アルゴリズム BIC （ Boosting with Information Criterion）を提案し，計算時間の短縮と検出率の向上を図った．

4．プロトタイプによる評価

　UNIX上でC言語を用いてBICを実現するプロトタイプを実装し，従来のID3，GAの手法との比較に対する評価実験を行った．その結果，相違が単独で存在する場合ではBICの手法はID3と同等以上の検出率（全体で　ID3 = 79.3 %，GA = 71.7%，BIC = 79.9%）を得ることを確認した．
　一方異なる相違が2つ存在する場合では，BICの検出率はID3に及ばず，GAと同程度の検出率（全体で　ID3 = 84.2 %，GA = 76.5%，BIC = 77.0%）であり，相違が単独の場合ほど有効ではないことが明らかになった．この理由としては相違が増えて決定木構造が複雑になることによって誤った検出結果が増大したということが考えられる．

5．結論

　本研究では，複数の人間が与えた大規模データベースに存在する概念相違に対して概念相違発見手法を適用するために，従来の手法を基に高速化した新たな手法を提案した．従来の2つの手法との比較による評価実験により，検出能力と計算時間について，高速化した手法の有効性を実証した．
　将来の課題としては，入力の知識事例の背景が異なる場合に対する効果などについても検証，改良を行い，また検出アルゴリズムを更にBICに適したものに改良することによって更なる有効性の向上を目指すことが考えられる．