この項目では、パターン認識の最も基本的な手法であるk近傍法と、その中核をなす「距離(類似度)の測り方」、そして近傍探索を高速化するデータ構造・アルゴリズムを学びます。距離の定義は検索・推薦・距離学習など現代の応用にも直結する基礎です。
📖 概要
パターン認識とは、観測データを特徴ベクトルとして表し、あらかじめ定めたクラスのどれに属するかを判別する処理です。その代表的な手法がk近傍法(k-NN)で、「未知のデータに特徴空間上で最も近い k 個の訓練データを探し、多数決でクラスを決める」というシンプルな原理で動きます。訓練時にはデータを保存するだけで、予測時に計算を行う「怠惰学習」に分類され、kは挙動を左右するハイパーパラメータです(kが小さいと決定境界が複雑になりノイズに敏感、大きいと滑らかになります)。
k近傍法の性能は「近さ」をどう定義するかに依存します。そこで、ユークリッド距離・マンハッタン距離とその一般化であるLp距離、方向の類似度に基づくコサイン距離、データの分布(共分散)を考慮するマハラノビス距離といった距離・類似度の使い分けが重要になります。
もうひとつの課題は計算量です。素朴に全訓練データとの距離を計算すると、データ数に比例した時間がかかります。これを改善するために、空間を分割して探索を絞り込むkd-treeや、厳密さを少し犠牲にして大規模データでも高速に検索する近似最近傍探索が使われます。
🔍 キーワード解説
k近傍法と最近傍法
最近傍法は、未知データに最も近い訓練データ1個のクラスをそのまま出力する方法です。k近傍法はこれを一般化し、近い順に k 個を選んで多数決(回帰なら平均)します。境界が複雑な問題にも対応できる一方、予測のたびに距離計算が必要で、特徴量のスケールの影響を受けやすいため正規化が重要です。また高次元では距離の差が付きにくくなる「次元の呪い」の影響を受けます。
ユークリッド距離・マンハッタン距離・Lp距離
ユークリッド距離は2点間の直線距離で、差の2乗和の平方根 (Σ |xi - yi|^2)^(1/2) です(L2距離)。マンハッタン距離は座標ごとの差の絶対値の和 Σ |xi - yi| で、碁盤目状の道を進む距離に例えられます(L1距離)。これらを一般化したのがLp距離(ミンコフスキー距離) (Σ |xi - yi|^p)^(1/p) で、p=1 でマンハッタン距離、p=2 でユークリッド距離になり、p→∞ の極限は座標差の最大値(チェビシェフ距離)に対応します。pが小さいほど各次元の差を均等に扱い、大きいほど最大の差が支配的になります。
コサイン距離
コサイン類似度は、2つのベクトルのなす角のコサイン cos θ = (x・y) / (||x|| ||y||) で、ベクトルの長さによらず「向きの近さ」を測ります。値は-1から1の範囲を取り、コサイン距離は 1 - コサイン類似度 として定義されます。文書の単語頻度ベクトルや埋め込み表現のように、大きさよりも成分の比率・方向が意味を持つデータの類似度計算で広く使われます。
マハラノビス距離
マハラノビス距離は、データの共分散行列 Σ を使って ((x - y)^T Σ^(-1) (x - y))^(1/2) と定義される距離です。特徴量ごとの分散の違いと特徴量間の相関を打ち消して測るため、「分布の広がりを考慮した距離」といえます。共分散行列が単位行列のときはユークリッド距離に一致します。分布の中心からの離れ具合を測れるため、外れ値検出・異常検知にもよく用いられます。
kd-tree
kd-treeは、k次元空間の点集合を、座標軸に垂直な超平面で再帰的に分割して構築する二分木のデータ構造です。最近傍探索では、木をたどって候補を見つけたあと、「現在の最近傍までの距離より近い可能性のある領域」だけを遡って調べることで、多くの場合に全探索より大幅に距離計算を削減できます。ただし次元が高くなると枝刈りが効きにくくなり、全探索と変わらない性能に劣化しやすいことが知られています。低〜中次元のデータに向いた手法です。
近似最近傍
近似最近傍(ANN)探索は、「厳密な最近傍」ではなく「十分近い点」を高速に見つけることを狙うアプローチです。厳密性を緩める代わりに、高次元・大規模データでも実用的な速度で検索できます。代表的な考え方に、似た点が同じバケットに入りやすいハッシュ関数を使う局所性鋭敏ハッシュ(LSH)や、点同士を近傍グラフでつないで探索する方法などがあります。埋め込みベクトルによる類似画像検索・文書検索・推薦システムなど、深層学習の実応用を支える基盤技術です。
📝 試験でのポイント
- 具体的な2点の座標からユークリッド距離・マンハッタン距離・コサイン類似度を計算させる問題が典型です
- Lp距離の式で p=1, p=2, p→∞ がそれぞれ何になるかの対応は頻出です
- マハラノビス距離は「共分散を考慮する」「単位行列ならユークリッド距離に一致」という特徴を押さえましょう
- k近傍法の k の大小と決定境界の複雑さ・過剰適合の関係は選択肢問題で問われやすい内容です
- kd-treeは厳密探索の高速化(高次元で劣化)、近似最近傍は精度を緩めた大規模高速検索、という役割の違いを区別しましょう
📚 まとめ
k近傍法は「近い訓練データの多数決」というシンプルな原理のパターン認識手法で、距離の定義が性能を左右します。 ユークリッド距離・マンハッタン距離はLp距離の特殊ケースで、コサイン距離は方向の類似度、マハラノビス距離は分布を考慮した距離です。 探索の計算量はkd-treeによる厳密な絞り込みや、近似最近傍探索による大規模高速化で対処します。 距離計算は手を動かして解けるように、各距離の式と使いどころを整理しておきましょう。
