1 概要
最近傍法は、入力に対して最も近い既知の事例を参照し、その属性を手がかりに分類や推定を行う機械学習の基本手法である。訓練時に複雑なモデルを強く学習させるというより、データ同士の近さを活用して判断する点に特徴がある。分類だけでなく、連続値の予測や検索、異常の発見にも応用される。
1.1 基本的な考え方
この方法では、新しい対象を特徴量の組として表し、既知のデータ群との距離を比較する。もっとも近い事例、または近い複数の事例の情報を使って出力を決めるため、発想は単純である。近接したものは性質も似ているという仮定に基づく。
1.2 近傍の定義
近傍は、ある対象の周囲にあるデータ集合を指すが、その範囲は距離尺度や近傍数の設定によって変わる。最も近い1件を取る場合もあれば、上位数件をまとめて扱う場合もある。半径で区切って近傍を定める方式も広く使われる。
1.3 代表的な用途
代表例は分類であり、ラベル付きデータから新規入力の所属先を推定する。回帰では、近い事例の数値を参照して値を予測する。さらに、検索システムで類似文書を探したり、通常と異なる振る舞いを見つけたりする場面でも利用される。
2 理論的背景
最近傍法は、対象間の距離を測る枠組みの上に成り立つ。したがって、どの空間で比較するか、どの尺度を使うか、どのように決定するかが結果に大きく影響する。理論面では、これらの選択が性能と解釈の両方を左右する。
2.1 距離空間
距離空間とは、任意の2点の隔たりを数値化できる数学的構造である。最近傍法では、この距離が小さいほど似ていると見なす。距離が適切でないと、近さの意味が崩れ、判断も不安定になりやすい。
2.1.1 ユークリッド距離
ユークリッド距離は、各特徴量の差を二乗して足し合わせ、その平方根を取る尺度である。幾何学的な直感に沿っており、最もよく知られた方法の一つである。数値の大きさに影響されやすいため、前処理との相性が重要になる。
2.1.2 マンハッタン距離
マンハッタン距離は、各成分の差の絶対値を合計して求める。格子状の移動に似た性質を持ち、外れた値の影響をやや抑えやすい。データの分布や特徴の意味によっては、ユークリッド距離より扱いやすいことがある。
2.1.3 その他の距離尺度
用途に応じて、コサイン類似度、ハミング距離、マハラノビス距離などが使われる。文書や高次元ベクトルでは角度に基づく尺度が有効な場合があり、カテゴリデータでは一致・不一致を数える方法が合う。データの性質に応じた選択が欠かせない。
2.2 特徴空間
特徴空間とは、各データを座標点として表すための空間である。ここでは各軸が一つの特徴に対応し、点同士の位置関係が比較の基礎となる。近傍法では、表現の仕方がそのまま判断基準に結びつく。
2.2.1 次元と尺度
特徴量の数が増えると空間は高次元化し、点同士の距離感が見えにくくなる。さらに、ある特徴だけ数値の範囲が大きいと、その軸が距離計算を支配しやすい。各次元の意味づけとスケールの整合が必要である。
2.2.2 標準化と正規化
標準化は平均と分散をそろえる処理であり、正規化は値を一定範囲に収める操作である。これらにより、異なる単位や桁の特徴量を比較しやすくなる。近傍の判定を安定させるうえで、実務上きわめて重要である。
2.3 決定規則
近い事例を集めた後は、それらから最終的な答えを導く必要がある。分類ならラベル、回帰なら数値を決める。決定規則は単純な場合もあれば、距離に応じて重みを変える場合もある。
2.3.1 多数決
多数決では、近傍に含まれる事例のラベルを数え、最も多いものを採用する。最も直感的な規則であり、分類問題で広く利用される。複数の事例が同程度に近い場合でも、扱い方を定めやすい。
2.3.2 加重投票
加重投票では、近い事例ほど大きな影響を与えるように重みを付ける。距離の逆数や指数関数を用いて、遠い点の寄与を弱めることが多い。局所的な情報を強調できるため、単純な多数決より柔軟である。
3 最近傍法の種類
最近傍法には、採用する近傍の数や範囲によっていくつかの形がある。1件だけを見る方法は最も単純で、複数件をまとめる方法は安定性を高めやすい。半径を用いる方式は、近さそのものを直接条件にする。
3.1 近傍数が一つの場合
1件だけを基準にする方式は、最も近い既知データの属性をそのまま引き継ぐ。実装は非常に簡潔だが、外れ値の影響を受けやすい。局所的な変化を強く反映するため、境界が細かく揺れやすい。
3.2 複数近傍を用いる場合
複数の近傍を参照すると、単独の例に左右されにくくなる。近い複数件の傾向をまとめることで、予測のばらつきを抑えやすい。分類と回帰のどちらにも応用しやすい構成である。
3.2.1 最近傍分類
最近傍分類は、近接した事例のラベルをもとにクラスを決める手法である。k個の近傍を使う形式が代表的で、各ラベルの票数で判定する。境界が非線形な問題でも扱いやすい。
3.2.2 近傍回帰
近傍回帰では、周囲の事例の目的変数を平均化し、未知の値を推定する。単純平均のほか、距離に応じた重み付き平均が使われる。滑らかな予測が得られやすい一方、局所的な極値は平滑化されやすい。
3.3 半径を基準にする方法
半径方式では、あらかじめ定めた距離以内にある事例を近傍とみなす。対象ごとに近傍数が変動するため、密な領域と疎な領域を自然に区別できる。半径の設定が結果を大きく左右する。
4 アルゴリズム
最近傍法の処理は、学習段階と推論段階に分けて考えると理解しやすい。学習では主にデータを保持し、推論では新しい入力との比較を行う。計算の中心は距離算出と候補選択である。
4.1 学習段階
この手法の学習は、厳密にはモデルのパラメータを推定するというより、参照用データを保存する段階に近い。入力例とそのラベル、あるいは目的値を蓄えておく。処理自体は軽いが、保存容量はデータ量に依存する。
4.2 推論段階
推論では、新規入力と保存済みデータの関係を調べ、近いものを抽出して結果を求める。実際の負荷はここに集中しやすい。候補の選び方と決定方法が、最終出力を決める核心となる。
4.2.1 距離計算
まず、入力と各保存例との距離を計算する。特徴量の種類や尺度に応じて、適切な距離関数を適用する。多数のデータがある場合、この部分が計算時間の主因となる。
4.2.2 近傍探索
距離を求めた後、条件に合う近傍を探す。全件を比較して小さい順に並べる方法が基本だが、効率化のために索引構造を使うこともある。データ規模が増えるほど、探索手法の差が大きくなる。
4.2.3 結果の決定
選ばれた近傍から、分類なら最多ラベル、回帰なら平均や加重平均を計算する。半径方式では、条件内の全事例をまとめて用いる。ここでの規則が、手法の挙動をかなり左右する。
4.3 計算量
最近傍法は、学習は軽い一方で推論時の負担が大きくなりやすい。特に大量データでは、距離計算の回数が増えるため、応答速度に影響する。計算量の見積もりは実用性の評価に不可欠である。
4.3.1 全探索
全探索では、保存済み全データに対して距離を計算する。実装は単純だが、データ数が増えると線形にコストが膨らむ。小規模なら十分でも、大規模用途では限界が現れやすい。
4.3.2 高速化手法
高速化には、kd木、ボール木、局所性に基づく近似探索などがある。これらは候補を絞り込み、不要な比較を減らす。高次元では効果が薄れる場合もあるが、実務上は重要な選択肢である。
5 応用
最近傍法は、入力と既知事例の対応関係を直接使えるため、さまざまな場面で利用される。規則が明快で、データの意味が比較的保たれている領域と相性がよい。以下に代表的な用途を示す。
5.1 分類問題
分類では、画像、音声、文書、センサーデータなどを既存クラスに振り分ける。境界が複雑でも、局所的な分布を反映しやすい点が利点である。教師データが十分なら、直感的な基準として有効である。
5.2 回帰問題
回帰では、気温、需要、価格、評価点などの連続値を予測する。似た条件の事例を参照するため、ルールを人が理解しやすい。急激な変化がある領域では、近傍の取り方が結果に強く影響する。
5.3 情報検索
検索分野では、クエリと近い文書や項目を探す用途に使われる。ベクトル表現された文書同士の近さを比較し、関連候補を並べる。推薦や類似検索の基礎としても扱われる。
5.4 異常検知
通常データから大きく離れた点を異常候補とみなす方法がある。近傍が極端に少ない、あるいは距離が目立って大きい場合に注意を促す。ルールが単純なため、監視用途で使いやすい。
6 長所と短所
最近傍法は理解しやすく、用途も広いが、万能ではない。長所は透明性と実装容易性にあり、短所は計算負荷と尺度依存性にある。データの特徴に応じた調整が必要である。
6.1 長所
6.1.1 実装の容易さ
基本は距離を測って近いものを選ぶだけなので、仕組みを組み立てやすい。複雑な訓練工程を要しないため、試作段階でも扱いやすい。小規模な問題では導入の負担が少ない。
6.1.2 解釈のしやすさ
どの事例を根拠にしたかを示しやすく、判断の理由が追跡しやすい。専門家が確認したい場面では、説明可能性の高さが利点になる。近い実例を参照する構造は、直感的な納得感を与えやすい。
6.2 短所
6.2.1 計算コスト
新しい入力ごとに多くの比較が必要となり、データが増えるほど重くなる。保存量も大きくなりやすく、応答速度の確保が課題になる。大規模システムでは工夫が不可欠である。
6.2.2 ノイズへの感度
誤ったラベルや例外的な点が近くにあると、判断が乱されやすい。とくに1件だけを使う方式では、その影響が顕著である。データの品質管理が性能に直結する。
6.2.3 次元の呪い
特徴量が増えると、空間が希薄になり、近さの差が分かりにくくなる。多くの点が互いに似た距離になるため、近傍の意味が弱まる。高次元データでは、特徴選択や次元削減が重要になる。
7 関連手法
最近傍法は、他の学習法と比べることで性質が明確になる。決定木のように明示的な規則を作る手法とは異なり、局所的な参照に重きを置く。拡張版では、重み付けや探索の工夫が加えられる。
7.1 決定木との比較
決定木は、特徴量に基づく分岐を通じて規則を構築する。これに対し、最近傍法は事例を直接参照する点が異なる。木構造は解釈しやすい一方、近傍法は局所的な柔軟性に優れる。
7.2 支持ベクトル機械との比較
支持ベクトル機械は、境界面を学習してクラスを分ける。最近傍法は境界を明示的に最適化せず、周囲のデータ配置から判断する。前者は学習で計算を集中させ、後者は推論時に比較を行う。
7.3 近傍法の拡張
基本形を補うため、近傍の扱いに工夫を加えた方法が多い。重みを変えたり、探索を効率化したりすることで、精度や速度を改善する。用途に応じて柔軟に発展してきた分野である。
7.3.1 重み付き最近傍法
重み付き最近傍法は、距離に応じて近い事例の影響を強める。単純な票数では表せない局所情報を反映しやすい。境界付近での判断を細かく調整したいときに有効である。
7.3.2 近傍探索の高速化
近傍探索の高速化は、データ構造や近似計算を用いて候補探索を短縮する。大規模データでは、精度と速度の両立が課題となる。実運用では、完全な厳密性より応答性を優先することもある。
8 歴史
最近傍法の発想は古く、初期のパターン認識や統計的分類と深く関わる。単純な考え方でありながら、計算機の発展とともに再評価されてきた。今日では、理論と実装の両面で重要な位置を占める。
8.1 研究の発展
初期には、記憶された事例との比較によって分類する方法として整備された。のちに統計的な解析や効率的な探索法が加わり、実用性が高まった。機械学習の基礎として、教育現場でも広く紹介されている。
8.2 統計的学習理論との関係
最近傍法は、局所的な近さを使うため、統計的学習理論の文脈でも研究されてきた。一般化性能や誤り率の挙動を考えるうえで、重要な比較対象になる。単純な規則でありながら、理論的な検討余地が大きい。
9 実装上の注意
実際に適用する際は、距離の取り方だけでなく、前処理や探索方法も含めて設計する必要がある。細部の選択が結果に強く影響するため、試行錯誤が欠かせない。以下の点は特に重要である。
9.1 特徴量の前処理
欠損値の処理、外れ値の扱い、尺度の調整を整えてから使うことが望ましい。前処理が不十分だと、距離計算が偏りやすい。意味の異なる特徴量を同列に扱う場合は、変換の設計が重要になる。
9.2 距離尺度の選択
距離尺度は、データの種類と目的に合わせて選ぶ必要がある。数値型、カテゴリ型、テキスト型では適した尺度が異なる。誤った選択は、近傍の解釈そのものを不適切にする。
9.3 近傍数の調整
近傍数が少ないと細かな変動に敏感になり、多すぎると平滑化が進みすぎる。最適値はデータごとに異なるため、検証を通じて決めることが多い。汎化性能と安定性のバランスが要点である。
9.4 データ構造の選択
高速な探索には、用途に応じたデータ構造が役立つ。単純な配列で十分な場合もあるが、件数が多ければ索引の導入が有効である。保存形式と検索効率の両面を見て設計することが求められる。