近傍に基づく類似事例検索の理論的解析

概要

論文の詳細を見る
近年, 事例ベース推論や例に基づく学習に代表されるように, 類似事例検索に基づく推論/学習の研究が活発に行なわれている。これらの枠組では, 現在の問題に類似した過去の事例を検索し, 検索された類似事例を直接利用することで, 問題に対する解を導出する。ここで, 解の妥当性は検索される類似事例に強く依存するため, 類似事例をどのように定義するかが大きな問題となる。最も一般的な類似事例の定義では, 類似事例の数(k)を固定し, 現在の問題に最も近いk個の過去の事例を, 問題に対する類似事例と定義する。この定義を用いた学習手法は, k-Nearest Neighbor Method(k-NN)と呼ばれている。また, 問題からの距離dを固定し, 問題からの距離がd以内の事例を類似事例と定義することも出来る。本論文では, この定義を用いた学習手法を, d-Nearest Neighborhood Method (d-NNh)と呼ぶことにする。図1は, 2次元空間において, k-NNとd-NNhが形成する, 現在の問題に対する近傍を示しており(k=5, d=0.3), 近傍内の事例が類似事例として検索され, 現在の問題に対する解の導出に利用される。本論文では, 分類問題に対するk-NNとd-NNhの平均的解析を行なう。平均的解析とは, 事例空間上の確率分布を固定することで, 目標概念に対して学習アルゴリズムが正しい答を出力する確率(正答率)を導出し, アルゴリズムの平均的な挙動を解析する理論的枠組である。我々は, 3種類のノイズ(関連属性ノイズ, 非関連属性ノイズ, クラスノイズ)が扱えるように, 平均的解析の枠組を拡張してきた。ここでは, この拡張された平均的解析の枠組を用いて, ノイズを含む問題領域におけるk-NNとd-NNhの挙動を理論的に比較する。
一般社団法人情報処理学会の論文
1997-09-24

近傍に基づく類似事例検索の理論的解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク