為什麼歐幾里得距離在高維中不是一個好的度量?
我讀到“歐幾里得距離在高維度上不是一個好的距離”。我想這句話與維度詛咒有關,但究竟是什麼?此外,什麼是“高維度”?我一直在使用具有 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 $ . 他們產生了一些結果,證明這些“分數範數”表現出增加最遠點和最近點之間對比度的特性。這在某些情況下可能很有用,但是有一個警告:這些“分數範數”不是正確的距離度量,因為它們違反了三角不等式。如果三角不等式是你研究中的一個重要品質,那麼分數度量就不會非常有用。