高維距離集中的數學論證
我知道在高維空間中，幾乎所有點對之間的距離具有幾乎相同的值（“距離集中度”）。參見Aggarwal 等人。2001，關於高維空間中距離度量的驚人行為。
有數學方法來觀察這種現象嗎？
有一個簡單的數學思想實驗可以闡明這一現象，儘管它似乎不能立即適用。因此，我將簡要描述這個實驗，並在一個單獨的部分中通過對具體情況的計算機分析來跟進。
思想實驗
一個古老的製圖栗子是地圖的大部分區域位於其邊緣附近。同樣，比薩餅的大部分——比你想像的還要多——由它的外殼組成。更重要的是，厚皮水果（如葡萄柚或西瓜）的大部分體積都在其表皮中。
這個披薩有一半以上位於陰影區域之外的邊緣附近。然而，這個“地殼”的寬度只有 $ 18% $ 餅的直徑。
地圖、比薩餅和葡萄柚沒有共同的形狀，但有一個共同的潛在解釋。我們可以通過假設其基本形狀——矩形、圓形、球體或其他任何東西——被某種因素均勻地縮小來模擬地圖的邊界、比薩餅的外殼或水果的皮 $ \alpha $ 並且“外殼”或“外皮”由位於這兩個同心相似形狀之間的東西組成。
在 $ n $ 尺寸（示例涉及 $ n=2 $ 或者 $ n=3 $ ）， 這 $ n $ 因此，內部的維體積將是 $ \alpha^n $ 乘以原始形狀的體積。（這個體積縮放定律有時用於定義空間的維數。）因此，相對於原始體積的外皮體積為
$$ 1 - \alpha^n. $$
作為一個函數 $ \alpha $ 它的增長率是
$$ \mathrm{d}(1 - \alpha^n) = -n,\alpha^{n-1},\mathrm{d}\alpha. $$
從沒有收縮開始（ $ \alpha=1 $ ) 並註意到 $ \alpha $ 正在減少（ $ \mathrm{d}\alpha $ 是負數），我們發現外皮的初始增長率等於 $ n. $
這表明外皮的體積最初增長得更快—— $ n $ 比對象縮小的速度快幾倍。的因素 $ n $ 暗示
在更高的維度上，距離的相對微小的變化會轉化為體積的更大變化。
我們稱之為**“地圖邊緣原則”。**
現在考慮一個表格數據集，由以下觀察組成 $ n $ 數值特徵。我們可以將每個觀察視為一個點 $ \mathbb{R}^n $ 並且（至少在我們的想像中）也可能假設這個點集合包含在某種緊湊區域內 $ \mathcal D $ 具有相對簡單的邊界。
如果我們選擇使用歐幾里得距離來比較這些點（以及其他點） $ \mathcal D $ ) 並考慮任意觀察 $ x, $ 地圖邊緣原則意味著大部分房間在 $ \mathcal D $ 幾乎是盡可能遠 $ x. $ （軟糖術語“幾乎”需要解釋在邊界周圍發生的事情 $ \mathcal D. $ )
另一個觸及問題核心的含義是製圖師困惑的概括：如果我們的觀察有點“分散”在 $ \mathcal D, $ 那麼製圖師的問題是“這個數據集在邊界附近的比例是多少？” 為了以定量的方式表達這一點，讓我們倒過來：我們問，我們應該縮小多少 $ \mathcal D $ 比如說，讓它只有原來的一半？讓我們稱之為“半長” $ \mathcal D, $ 類似於放射性衰變的半衰期。
如果半長是 $ \alpha, $ 我們只需要解方程
$$ \alpha^n = \frac{1}{2};\quad \alpha = 2^{-1/n} = e^{-(\log 2)/n} \approx 1 - \frac{\log 2}{n} \approx 1 - \frac{0.7}{n}. $$
在二維中，半長是 $ 1 - 0.35. $ 由於一半的收縮發生在地圖或披薩的一側，另一半發生在另一側（參見上圖），因此地圖的一半面積（ $ n=2 $ ) 位於（大約）範圍內 $ 35/2=18% $ 它的直徑從邊界。
在三個維度上，半長是 $ 1 - 0.23: $ 現在，*一半的水果體積在裡面 $ 12% $ 它的直徑從它的邊界。*果皮只有整個水果寬度的八分之一的水果是一半以上的果皮。
儘管有外觀，但這種葡萄柚的大約一半體積是果皮。 （來源：FreeDigitalPhotos.net。）
在非常大的尺寸中，半長非常接近 $ 1. $ 在 $ n=350 $ 尺寸大於 $ 98%, $ 百分之二以內 $ 1. $ 因此，期望任何一半 $ 350 $ 位於其中的維數據集 $ 1% $ 它的直徑從它的邊界。除非數據是強聚類的，否則這種概括將是準確的。
表達這些結果的另一種方式是：
缺乏強聚類，在更高維度 $ n $ 我們可以預期數據集中觀測值之間的大多數歐幾里得距離非常接近相同，並且非常接近它們所在區域的直徑。“非常接近”是指大約 $ 1/n. $
**這個分析的幾個部分實際上只是揮手和近似，**由於模糊性 $ \mathcal D $ 以及關於數據集的非常一般的假設。怎麼 $ \mathcal D $ 無論如何定義？在某些應用中，它是由固有限制決定的；例如，當所有特徵都是比例時。在許多應用程序中，特徵被任意縮放以位於固定間隔（“標準化”）內，我們經常採用 $ \mathcal D $ 為對應的超立方體。但這只是一種技巧，它對任何外圍數據值都非常敏感。這篇文章的其餘部分探討了一種替代方案，其中邊界在結果中的作用不那麼重要。得出了類似的結論。
封閉歐幾里得空間中的距離分析
我發現論文的設置相當隨意，因為它正在探索單位立方體內的距離。距離分佈很大程度上取決於這些立方體邊界的形狀。
有一種方法可以避免邊界效應。在一維中，“立方”只是單位區間， $ [0,1]. $
因為這個區間有兩端，所以有些點離其餘的點很遠；其他人（靠近中間）往往接近所有點。 這是不對稱的。 要消除不對稱性，請將間隔滾動成一個循環，其中起點 $ 0 $ 到達終點 $ 1: $
在幾何上，它的所有點都是等價的。
我們可以通過將每個坐標分別滾動到一個循環中來在更高維度上做同樣的事情。維度上的結果 $ d $ 是個 $ d $ -環面。它沒有邊界，所有點在幾何上都是等價的。但是，它不像球體那樣完全對稱：與（歐幾里德）球體不同，其幾何形狀由於其曲率而不再是歐幾里得，這些 $ d $ -tori 是*平坦的，*沒有曲率。它們可以讓我們深入了解歐幾里得距離，而無需處理邊界的複雜性。
圓環中距離的分析研究很複雜，至少對於大於 $ 1. $ 讓我們通過從 a 上的均勻分佈生成隨機點來研究這些距離 $ d $ -環面併計算它們所有的相互距離（除了每個點與其自身之間的必然距離為零）。對於以下數字，我在八個獨立維度中的每個維度中生成了 500 個點，從而在每個數據集中產生了超過 100,000 個距離。 這些距離如何分佈以及這些分佈如何隨維度變化 $ d $ ?
這是這些距離的直方圖數組，每個維度一個。
用數學方法證明眼睛已經看到的東西並不難：隨著維度的增加，分佈趨於高斯或“正常”形狀。
還有另一個顯著的規律： 這些直方圖的分佈幾乎是恆定的。 在每個下方，我都打印了距離的標準偏差 (SD)。它幾乎沒有改變 $ 1 $ 通過 $ 128 $ 方面。從這個意義上說，根本沒有高維度的距離“集中”！
為了便於比較，以下是在公共圖上顯示的相同數字：
顏色的含義與以前相同，表明平均距離隨著尺寸的增加而增加。 他們大致使用平方根定律：平均距離約為維度平方根的四分之一。（那些熟悉高維勾股定理的人會立刻明白為什麼。） $ d $ -環面是由坐標都不同的點對實現的 $ 1/2 $ （因為你不能比沿著循環更遠）；這個距離顯然是 $ \sqrt{d}/2. $
因此，比較每個維度的相對距離是有意義的。在這裡，我們再繪製一張相同數據集的圖，現在距離全部除以 $ \sqrt{d}/2: $
這種歸一化使直方圖居中 $ 0.58, $ 無關維度。 在這裡，我們正在研究“距離集中度”的最清晰表現：儘管每個維度中的相對距離通常是相同的，但隨著維度的增加，距離會更緊密地集中在中心值周圍。 從發布的標準偏差中可以看出，它們也享有平方根反定律：相對距離的分佈約為 $ 1/(4\sqrt{d}). $
換句話說，在高維環面上的任何給定點周圍（所有點在幾何上都是相同的，所以哪個點都沒有關係），環面上幾乎所有其他點的距離幾乎相同！ 如果你是一個高維平坦歐幾里得空間的居民，儘管這個空間沒有邊界，但該空間的大部分似乎都靠近你周圍的一個球殼。 在 $ d $ = 一百萬維，例如，最大可能距離為 $ 500, $ 平均距離大約是 $ 288.7, $ 幾乎所有的距離都在 $ 0.5 $ 那個值。
所有這些關於歐幾里得距離的形狀、典型值和擴展的一般結論在其他域形狀中都成立，但細節有所不同。然而，一般的結果是，在合理緊湊的高維域中隨機選擇的點往往不會明顯聚集。 這對基於聚類和最近鄰分析的統計（和機器學習）方法具有明顯的意義。
