次元の呪い (Curse of dimensionality) とは何なのか

データサイエンスの本や、ブログなどを見ているとよく目にする、次元の呪いとはなんなのか、と疑問に思ったので、調べてまとめてみました。

Wikipedia より

高次元ユークリッド空間の広大さを示す別の例として、単位球と単位立方体の大きさを次元を上げながら比較してみればよい。次元が高くなると、単位球は単位立方体に比較して小さくなっていく。したがってある意味では、ほとんど全ての高次元空間は中心から遠く、言い換えれば、高次元単位空間はほとんど超立方体の角で構成されており、「中間」がない。このことは、カイ二乗分布を理解する上で重要である。

と、ちょっと日本語が正しく使われていないようなので、頑張って初心者言語に翻訳していきたいと思います。

この回のポイント↓

まぁ、次元の呪いを機械学習をする上で簡単に言うと、
"扱う特徴量(次元)が多すぎて、機械学習モデルが効率よく回帰または分類ができないこと"
を言います。

特徴量とは、例えば'花'で言うと、花弁、茎、葉、根などのことです。
回帰や分類の違いは、前回まとめたので、こちらを参照

たとえ話

Stackflow の fcop さんのコメントがわかりやすかったので、要約して翻訳してみます。

質問は、子供でもわかるように次元の呪いを説明してくださいとの質問に対して、fcopさんはこう答えていました。

例えば、様々な種類のクッキーが入ったトラックがあるとして、その中から子供が自分の好きなクッキーを選ぶ時に、'味'という特徴量だけ考えると、[甘い,辛い,すっぱい,苦い]の4種類しかないとします。この特徴量だけを考慮すれば、子供は簡単に好きなクッキーを選べますよね。きっと、甘いに属するクッキーでしょうね。しかし、これに新しい特徴量'色'[赤、青、黄、緑]が入ってくると、4種類×4種類で16通りが考えられますね。さらに、5種類の'形'という特徴量が加わると、4×4×5=80通りになってしまいます。これを、繰り返していくと指数関数的に種類が増えていき、なにがなんだかわかんなくなってしまいますよね。これが、次元の呪い、the curse of dimensionality です。

次元の呪い (Curse of Dimensionality) の2つの解決策

• 特徴選択 (Feature selection)

必要不可欠な特徴量（次元）、とくに必要ではない特徴量を見極めて、後者を消去（削減）します。このことを特徴選択といいます。 特徴選択には、filter法とwrapper法とEmbedded法があるようです。これは、また改めて新しいページにまとめますので、気になる方はこのページをストックするなり、フォローするなりしておいてください、そのうちここにリンク貼ります。もしくは、英語で読める方は、こちらを参考にどうぞ。これ

• 特徴作成(Feature creation)

これは、２つ以上の特徴量を組み合わせて、1つの特徴にまとめてしまおうというものです。
Kaggle の Titanic survival prediction のコンペで使われているデータには、Parch と SibSp という、親子と兄弟、配偶者の数を示す特徴量がありました。それを、多くの人が、Family Size というParch と SibSp を足し合わせた特徴量にまとめていました。これが、特徴作成です。