次元の呪い

次元の呪い（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%を占める立方体を探索すればよい）

参考¶

• Curse of Dimensionality - Lecture Notes for Big Data Analytics

• The Math Behind “The Curse of Dimensionality” | by Maxime Wolf | Towards Data Science