次元の呪い#
次元の呪い（curse of dimensionality） はデータの次元に対してデータ数が少ないときに生じる問題のこと。
高次元における「近傍」の増加#
最近傍探索の基礎的な方法は入力空間を格子状（grid）に分割したセルの集合として扱うよう前処理すること。
クエリ（検索・予測のための入力）\(q\)を含むセルと隣接するセルを「近傍」のセルとする。 もし1次元なら、\(q\)を含むセルとその両隣で3つのセルが「近傍」のセルになる。 2次元の場合、\(3^2 = 9\)個のセルが「近傍」になる。 3次元なら\(3^3 = 27\)となり、一般に\(m\)次元に対して\(3^m\)のセルが「近傍」になる。
別の説明#
データセット\(X\)における\(n\)個の点が一様にランダムに\([0,1]^m\)（m-cube）から選び出されたとする。
クエリの点\(q\)について、\(q\)の周囲の超立方体を\(f\)分位点（\(k=fn\)）まで拡張するとする。 このとき、この立方体（\(q\)のための探索空間）は入力空間全体のほとんどを占めるような巨大なものとなる。
探索空間の立方体の辺の長さの期待値は\(E_m(f) = f^{1/m}\)
例：
5000個の点が\([0,1]^m\)から無作為抽出されたとする。\(q=\boldsymbol{0}\)（原点）とする。
1次元の場合、5個の近傍点をえるために平均で\(5/5000 = 0.001\)の距離を探索する必要がある。（言い換えると、5つの点を獲るために入力空間の立方体のうち0.1%を占める立方体を探索すればよい）
10**(1/10)
1.2589254117941673