K近傍法

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習（英語版） 半教師あり学習（英語版） 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

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

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

概要

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

1. 入力と全学習データとの類似度（距離）測定
2. 類似度上位 k 個の選出
3. 選出されたデータの多数決あるいは平均

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

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

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

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

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

アルゴリズム

訓練例は、多次元の特徴空間におけるベクトルである。空間は、訓練例のラベルと位置によって領域に分割されている。空間内のある点には、その 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近傍法」の項目。

表 話 編 歴 統計学
標本調査	標本 母集団 無作為抽出 層化抽出法
要約統計量	連続確率分布 位置 平均 算術 幾何 調和 中央値 分位数 順序統計量 最頻値 階級値 分散 範囲 偏差 偏差値 標準偏差 標準誤差 変動係数 決定係数 相関係数 自己相関 共分散 自己共分散 分散共分散行列 百分率 統計的ばらつき モーメント 分散 歪度 尖度 カテゴリデータ 頻度 分割表
推計統計学	仮説検定 パラメトリック t検定 ウェルチのt検定 F検定 Z検定 二項検定 ジャック-ベラ検定 シャピロ–ウィルク検定 分散分析 共分散分析 ノンパラメトリック ウィルコクソンの符号順位検定 マン・ホイットニーのU検定 カイ二乗検定 イェイツのカイ二乗検定 累積カイ二乗検定 フィッシャーの正確確率検定 尤度比検定 G検定 アンダーソン–ダーリング検定 コルモゴロフ–スミルノフ検定 カイパー検定 マンテル検定 コクラン・マンテル・ヘンツェルの統計量 その他 帰無仮説 対立仮説 有意 棄却 区間推定 信頼区間 予測区間 モデル選択基準 AIC BIC WAIC MDL その他 偏り 偏りと分散 過剰適合 推定量 点推定 最尤推定 尤度関数 尤度方程式 最小距離推定 メタアナリシス ブートストラップ法
ベイズ統計学	確率 主観確率 ベイズ確率 事前確率 事後確率 最大事後確率 その他 ベイズ推定 ベイズ因子
相関	交絡 ピアソンの積率相関係数 順位相関（スピアマンの順位相関係数 ・ケンドールの順位相関係数 ）
モデル	一般線形モデル 一般化線形モデル 混合モデル 一般化線形混合モデル
回帰	線形 リッジ回帰 ラッソ回帰 エラスティックネット 非線形 k近傍法 決定木 ランダムフォレスト ニューラルネットワーク サポートベクターマシン 射影追跡回帰 時系列 自己回帰モデル 自己回帰移動平均モデル ARCHモデル 対移動平均比率法 トレンド定常 傾向推定 共和分 構造変化
分類	線形 線形判別分析 ロジスティック回帰 <! -- 名前に回帰とついていますが確率を回帰する分類手法です --> 単純ベイズ分類器 単純パーセプトロン 線形サポートベクターマシン 二次 二次判別分析 非線形 k近傍法 決定木 ランダムフォレスト ニューラルネットワーク サポートベクターマシン ベイジアンネットワーク 隠れマルコフモデル その他 二項分類 多クラス分類 第一種過誤と第二種過誤
教師なし学習	クラスタリング k平均法 （k-means++法 ） DBSCAN 密度推定（英語版） カーネル密度推定 （ カーネル ） その他 主成分分析 独立成分分析 自己組織化写像
統計図表	棒グラフ バイプロット（英語版） 箱ひげ図 管理図 フォレストプロット ヒストグラム 円グラフ Q-Qプロット ランチャート 散布図 幹葉表示 バイオリン図 ドットプロット ヒートマップ 階級区分図
生存分析	生存関数 カプラン＝マイヤー推定量 ログランク検定 故障率 比例ハザードモデル
歴史	統計学の創始者 確率論と統計学の歩み
応用	社会統計学 疫学 生物統計学 系統学 統計力学 計量経済学 機械学習 実験計画法
出版物	統計学に関する学術誌一覧 重要な出版物
全般	統計 頻度主義統計学 統計学および機械学習の評価指標
その他	方向統計学 S言語 R言語 統計検定 社会調査士 JDLA Deep Learning For GENERAL JDLA Deep Learning for ENGINEER 実用数学技能検定 品質管理検定
カテゴリ