為什麼歐幾里得距離在高維中不是一個好的度量？
我讀到“歐幾里得距離在高維度上不是一個好的距離”。我想這句話與維度詛咒有關，但究竟是什麼？此外，什麼是“高維度”？我一直在使用具有 100 個特徵的歐幾里德距離應用層次聚類。使用此指標“安全”的功能最多有多少？
華盛頓大學佩德羅·多明戈斯 (Pedro Domingos) 的“關於機器學習的一些有用的知識”對更高維度的非直觀結果進行了很好的總結：
[O] 來自三維世界的直覺通常不適用於高維世界。在高維中，多元高斯分佈的大部分質量不在均值附近，而是在其周圍越來越遠的“殼”中；而高維橙的大部分體積都在皮，而不是果肉。如果恆定數量的示例均勻分佈在高維超立方體中，則在某些維度之外，大多數示例更靠近超立方體的面，而不是離它們最近的鄰居。如果我們通過將超球體刻在超立方體中來近似超球體，那麼在高維中，幾乎所有超立方體的體積都在超球體之外。這對於機器學習來說是個壞消息，其中一種類型的形狀通常由另一種類型的形狀近似。
這篇文章還充滿了機器學習的許多額外智慧。
除了機器學習之外，另一個應用是最近鄰搜索：給定一個感興趣的觀察值，找到它的最近鄰（從某種意義上說，這些是與查詢點距離最小的點）。但是在高維中，會出現一個奇怪的現象：最近點和最遠點之間的比率接近 1，即這些點之間的距離基本上是一致的。這種現象可以在各種距離度量中觀察到，但對於歐幾里得度量來說，它比曼哈頓距離度量更明顯。最近鄰搜索的前提是“更近”的點比“更遠”的點更相關，但如果所有點之間的距離基本一致，則區分是沒有意義的。
來自 Charu C. Aggarwal、Alexander Hinneburg、Daniel A. Keim，“關於高維空間中距離度量的令人驚訝的行為”：
[在 Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, " When Is ‘Nearest Neighbor’ Meaningful? “] 中已經爭論過，在數據分佈的某些合理假設下，最近鄰和最遠鄰的距離之比對於各種數據分佈和距離函數，對於高維空間中的給定目標幾乎是 1。在這種情況下，最近鄰問題變得不明確，因為到不同數據點的距離之間的對比不存在。在這種情況下，從定性的角度來看，即使是鄰近的概念也可能沒有意義：這個問題甚至比高維算法的性能下降更為根本。
… 許多高維索引結構和算法使用 [E]uclidean 距離度量作為其在二維或三維空間應用中的傳統使用的自然擴展。…在本文中，我們提供了一些令人驚訝的理論和實驗結果來分析 $ L_k $ 值的規範 $ k $ . 更具體地說，我們表明到查詢點的距離的相對對比在很大程度上取決於 $ L_k $ 使用的指標。這提供了相當多的證據表明 $ L_k $ 對於更高的值，隨著維度的增加，規範惡化得更快 $ k $ . 因此，對於具有固定（高）維值的給定問題 $ d $ ，最好使用較低的值 $ k $ . 這意味著 $ L_1 $ 距離度量（Manhattan distance metric）最適合高維應用，其次是歐幾里得度量（ $ L_2 $ ）。…
“令人驚訝的行為”論文的作者然後建議使用 $ L_k $ 規範與 $ k<1 $ . 他們產生了一些結果，證明這些“分數範數”表現出增加最遠點和最近點之間對比度的特性。這在某些情況下可能很有用，但是有一個警告：這些“分數範數”不是正確的距離度量，因為它們違反了三角不等式。如果三角不等式是你研究中的一個重要品質，那麼分數度量就不會非常有用。