2013年2月14日木曜日

K-近傍法

k-近傍法は、テストデータとの距離が短い順にk個の判定用データを取り出し、
多数決によってテストデータが所属するカテゴリーを推定する方法です。


例えば、以下の図を見てください。
(図は、Wikipediaの「k近傍法」の解説にあったsvgをpngに変換したものです)

 


青四角や赤三角は判定用データで、
緑丸はテストデータです。

この例では、緑丸の属するカテゴリが、
青四角が属するカテゴリなのか、

赤三角が属するカテゴリなのか、を調べます。



カテゴリの調べ方としては、

  1. 緑丸と青四角or赤三角との距離を全て求める。
     
  2. 距離の短い順に青四角or赤三角をk個抽出する。
     
  3. 抽出した青四角と赤三角の個数をそれぞれ求め、
    多い方を緑丸の属するカテゴリとする。

という手順で求めます。


k=1ならば、最も距離が短い記事に該当するカテゴリがそのまま推定結果になります。
この図だと、緑丸に最も近いのは赤三角です。
よって、

  緑丸が属するカテゴリは、赤三角が属するカテゴリ

という推定結果を得ます。


k=3の場合は、上位3つの記事が、青四角が1つ、赤三角が2つとなります。
このため、

  緑丸が属するカテゴリは、赤三角が属するカテゴリ

という推定結果を得ます。


しかし、k=5になると、上位5つは、青四角が3つ、赤三角が2つとなります。
このため、

  緑丸が属するカテゴリは、青四角が属するカテゴリ

と推定されます。



このk近傍法で気になる点は2つあります。

1つ目は、判定用データの数が膨大になったり、
判定用データに使われる独立変数が増大すると、
距離計算にかかる演算量が増えてしまう点です。

2つ目は、1部の例外的な塊が誤った推定結果を促してしまう
という懸念がある点です。



1つ目の対策としては、距離計算に使われる判定用データの数を
極力減らすことが考えれます。

例えば、各判定用データは、他のどの判定用データに近いのか、
というデータ(周辺データと呼ぶことにします)も持つようにします。
そして、次の手順を繰り返しながら距離計算に使う判定用データを
決めていきます。

  1. 最初に距離計算に使う判定用データを適当に1つ決め、ポインタを当てる。
     
  2. 決めた判定用データと周辺データとの距離を求め、その中で最小になった判定用データに
    ポインタを移す。
     
  3. 2. の作業を、判定用データそのものが最小になるまでひたすら繰り返す。

こんな感じで距離計算していけば、距離が異常に長くなるような判定用データとの
距離計算を回避することが可能になるので、演算量削減が期待できます。


2つ目の対策については、データクレンジングをきっちり行うことが挙げられます。
データクレンジングとは、一般的なカテゴリの特徴とかけ離れたデータを
取り去る作業のことを言います。
ただ、この作業をひたすら行うことは、学習をしなくても良いというメリットを損なう気もします。
だから、クレンジングしまくらなくてはならないカテゴリについては、
k近傍法ではなく、カテゴリの代表的な特徴を求める手法を使う方が良いようにも思います。

他には、アンサンブル学習を適用するのもアリかと思います。
アンサンブル学習については、後にまた改めて書くつもりなので、
今回は説明をサボります。。。(笑)


そもそも、「カテゴリに分類できる問題じゃねぇじゃん!」という話もありますが・・・。


次回の記事では、Rを使ってk近傍法を試してみたいと思います。


0 件のコメント:

コメントを投稿