k近傍法

k近傍法︵ケイきんぼうほう、英: k-nearest neighbor algorithm, k-NN︶は、入力との類似度が高い上位k個の学習データで多数決/平均するアルゴリズムである。

パターン認識︵分類・回帰︶でよく使われる。最近傍探索問題の一つ。k近傍法は、インスタンスに基づく学習の一種であり、怠惰学習 の一種である。その関数は局所的な近似に過ぎず、全ての計算は分類時まで後回しにされる。また、回帰分析にも使われる。

概要

k近傍法は以下の手順からなる‥

(一)入力と全学習データとの類似度︵距離︶測定

(二)類似度上位k個の選出

(三)選出されたデータの多数決あるいは平均

すなわち﹁入力とよく似たk個のデータで多数決/平均する﹂単純なアルゴリズムである。

例えば環境︵気温/湿度/風速︶から天気︵雨/曇り/晴れ︶を予測する分類問題を考える。k=5 のk近傍分類では、過去100日の環境-天気ペアを学習データとし、今日の環境類似度が高い上位 k=5 日をピックアップ、その5日の天気が雨/雨/晴れ/雨/雨であれば多数決で雨と予測する。

言い換えれば、あるオブジェクトの分類は、その近傍のオブジェクト群の投票によって決定される︵すなわち、k 個の最近傍のオブジェクト群で最も一般的なクラスをそのオブジェクトに割り当てる︶。k は正の整数で、一般に小さい。k = 1 なら、最近傍のオブジェクトと同じクラスに分類されるだけである。二項分類の場合、k を奇数にすると同票数で分類できなくなる問題を避けることができる。

同じ手法は回帰分析に使われる。この場合、オブジェクトの属性値を k個の最近傍のオブジェクト群の属性値の平均値とする。より近いオブジェクトに大きく重み付けすることもできる。

近傍のオブジェクトは、正しい分類が判っているもの︵あるいは回帰分析の場合、属性値が判っているもの︶から選ばれる。これをアルゴリズムの訓練例と考えることもできるが、明確な訓練段階は不要である。近傍を選ぶにあたって、各オブジェクトは多次元の特徴空間における位置ベクトルで表される。通常、ユークリッド距離を使うが、マンハッタン距離などの他の距離も原理的には使うことができる。k近傍法は、データの局所的構造に左右されやすい。

アルゴリズム

k近傍法の例。標本︵緑の丸︶は、第一のクラス︵青の四角︶と第二のクラス︵赤の三角︶のいずれかに分類される。k = 3 なら、内側の円内にあるオブジェクトが近傍となるので、第二のクラスに分類される︵赤の三角の方が多い︶。しかし、k = 5 なら、それが逆転する。

訓練例は、多次元の特徴空間におけるベクトルである。空間は、訓練例のラベルと位置によって領域に分割されている。空間内のある点には、その k個の最近傍の訓練例に最も多く付けられているクラスラベル cが割り当てられる。このとき、一般にユークリッド距離が使われる。

アルゴリズムの訓練段階では、訓練例の特徴ベクトルとクラスラベルだけを保持している。実際の分類段階では、クラスが未知である標本の特徴空間におけるベクトルが与えられる。この新たなベクトルと既存のベクトル群との距離を計算し、k 個の最近傍の標本が選択される。新たなベクトルを特定のクラスに分類する方法はいくつかある。最も一般的な手法は、k 個の最近傍のオブジェクトの中で最も一般的なクラスに分類する方法である。この技法による分類の問題点は、全訓練例で個体数が最も多いクラスに分類される可能性が高くなる点である。この対策として、k 個の最近傍のオブジェクトの間で、新たなベクトルとの距離の大小を考慮して︵重み付けして︶クラスを決定する方法がある。

パラメータ選択

k をどのように決定するかは、データに依存する。一般に kが大きければ、分類にあたってのノイズの影響を低減できるが、クラス間の境界が明確にならない傾向がある。k の選択には様々なヒューリスティックスが用いられる︵例えば、交差検証︶。k = 1 のときの k近傍法を、最近傍法と呼び、最も近傍にある訓練例のクラスを採用する。

k近傍法の正確さは、ノイズ的な特徴や不適切な特徴によって著しく損なわれることがある。あるいは、特徴尺度がその重要性と対応していない場合も、同様である。このあたりに関しては、特徴選択︵feature selection︶として研究されている。特徴尺度を最適化するための特によく使われる手法として、進化的アルゴリズムの利用がある。また、訓練データと訓練クラスとの相互情報量によって特徴の尺度を決定する方法もよく使われる。

特徴

このアルゴリズムの単純なバージョンは、単に標本と既存のベクトルとの距離を計算すればよいが、データが増えれば計算量も膨大となる。様々な最近傍探索アルゴリズムが提案されており、一般に実際に距離を計算する回数を削減する。特徴空間のパーティショニングによる最適化や、特定の値が近いものだけ距離を計算する最適化などがある。その他の最近傍探索アルゴリズムとしては、次のようなものがある。

●kd木

●Metric tree

●Locality sensitive hashing (LSH)

最近傍法は、強い一致性を示す。データ量が無限に近づくにつれて、このアルゴリズムの誤り率はベイズ誤り率︵達成可能な最小誤り率︶の2倍以下となる。k近傍法は k︵近傍とするデータ個数︶を増やすことでベイズ誤り率に近づく。

k近傍法は、連続値をとる変数についても適用可能である。そのような実装の例として、距離の逆数で重み付けした k近傍法がある。このアルゴリズムは次のように動作する。

1. 対象データと他のデータのユークリッド距離かマハラノビス距離を計算する。
2. 計算された距離の順にデータをソートする。
3. ヒューリスティックによって決めた最適な k 個の近傍を選ぶ（根二乗平均誤差など）
4. それらについて、距離の逆数で重み付けした平均を求める。

関連項目

• サポートベクターマシン
• データマイニング
• パターン認識
• カーネル密度推定
• 機械学習
• 最近傍探索
• 人工知能
• 統計学
• K平均法
• 予測分析

参考文献

• Belur V. Dasarathy, editor（1991）Nearest Neighbor（NN）Norms: NN Pattern Classification Techniques, ISBN 0-8186-8930-7
• Nearest-Neighbor Methods in Learning and Vision, edited by Shakhnarovish, Darrell, and Indyk, The MIT Press, 2005, ISBN 0-262-19547-X
• Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data. Forest Ecology and Management, Volume 196, Issues 2-3, 26 July 2004, Pages 245-255. Helena Mäkelä and Anssi Pekkarinen
• Estimation and mapping of forest stand density, volume, and cover type using the k-nearest neighbors method. Remote Sensing of Environment, Volume 77, Issue 3, September 2001, Pages 251-274. Hector Franco-Lopez, Alan R. Ek and Marvin E. Bauer

外部リンク

• k-nearest neighbor algorithm in Visual Basic （ソースコードと実行ファイルあり）
• k-nearest neighbor tutorial using MS Excel
• Agglomerative-Nearest-Neighbor Algorithm, by Michael J. Radwin
• Weighted distance learning for nearest neighbor error minimization by R. Paredes and E. Vidal
• K-Nearest Neighbor （英語） - スカラーペディア百科事典「K近傍法」の項目。