我在某處看到，當我們擁有多維和稀疏數據時，經典距離（如歐幾里得距離）變得難以區分。為什麼？您是否有兩個稀疏數據向量的示例，其中歐幾里得距離的效果不好？在這種情況下，我們應該使用哪種相似性？
我相信這不是稀疏，而是高維度，通常與稀疏數據相關。但是，當數據非常稀疏時，情況可能更糟。因為這時任何兩個對象的距離很可能是其長度的二次均值，即$$ \ lim_ {dim \ rightarrow \ infty} d（x，y）= || x-y || \ rightarrow_p \ sqrt {|| x || ^ 2 + || y || ^ 2} $$
如果$ \ forall_i x_i = 0 \ vee y_i = 0 $，則該等式成立。如果您將維數和稀疏度增加到足以容納幾乎所有屬性的程度，則差異將很小。
更糟糕的是：如果將向量標準化為長度為$ || x || = 1 $ ，那麼任意兩個對象的歐幾里得距離都將是$ \ sqrt {2} $。
因此，根據經驗，歐幾里德距離是 usable （我並不是說有用或有意義的）對像在$ 3/4 $的屬性中應該不為零。那麼應該有合理數量的屬性，其中$ | y_i | \ neq | x_i-y_i | \ neq | x_i | $，因此向量差變得有用。這也適用於任何其他規範引起的差異。因為在高於$ | x-y |的情況下\ rightarrow_p | x + y | $
我認為這不是使距離函數在很大程度上獨立於實際差或絕對差收斂到絕對總和的理想行為！
一個常見的解決方案是使用諸如餘弦距離之類的距離。在某些數據上，它們工作得很好。粗略地說，它們只查看兩個向量都不為零的屬性。在下面的參考中討論了一種有趣的方法（他們沒有發明它，但是我喜歡他們對屬性的實驗評估）是使用共享的最近鄰居。因此，即使向量x和y沒有共同的屬性，它們也可能具有一些共同的鄰居。計算連接兩個對象的對像數與圖形距離密切相關。
關於距離函數的討論很多：
，如果您不喜歡科學文章，也可以在Wikipedia上進行：維度維度 a>
I'd suggest starting withCosine distance,not Euclidean, for any data with most vectors nearly orthogonal,$x \cdot y \approx$ 0.
To see why, look at$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$.
If $x \cdot y \approx$ 0, this reduces to$|x|^2 + |y|^2$: a crummy measure of distance, as Anony-Mousse points out.
Cosine distance amounts to using $x / |x|$,or projecting the data onto the surface of the unit sphere, so all $|x|$ = 1.Then $|x - y|^2 = 2 - 2\ x \cdot y$
a quite different and usually better metric than plain Euclidean.$ x \cdot y$ may be small, but it's not masked by noisy $|x|^2 + |y|^2$.
$x \cdot y$ is mostly near 0 for sparse data.For example, if $x$ and $y$ each have 100 terms non-zero and 900 zeros,they'll both be non-zero in only about 10 terms (if the non-zero terms scatter randomly).
Normalizing $x$ /= $|x|$ may be slow for sparse data; it's fast inscikit-learn.
Summary: start with cosine distance, but don't expect wonders on any old data.
Successful metrics require evaluation, tuning, domain knowledge.
啟發式。這裡的關鍵問題是，歐幾里得準則對任何方向都具有相同的重要性。這構成了缺乏先驗的情況，而且正如您肯定在高維度上知道的那樣，這裡沒有免費的午餐（即，如果您對要搜索的內容一無所知，那麼就沒有理由為什麼有些雜音不會像您想要的那樣搜索，這就是重言式...）。
我想說的是，對於任何問題，找到噪聲以外的東西都需要一定的信息。此限制以某種方式與您嘗試探索的“噪音”級別（即，非信息內容的級別）的“大小”相關。
在高維中，如果先驗信號是稀疏的，則可以使用度量來刪除（即懲罰）非稀疏矢量，該度量將用稀疏矢量填充空間或使用閾值技術。
框架假設$ \ xi $是一個高斯矢量，其均值$ \ nu $和對角協方差$ \ sigma Id $（$ \ sigma $是已知的），並且您想要檢驗簡單的假設
$$ H_0：\; \ nu = 0，\; VS \; H _ {\ theta}：\; \ nu = \ theta $$（對於給定的$ \ theta \ mathbb {R} ^ n $），不一定事先知道$ \ theta $。
能量統計測試。您的直覺當然是，評估您的標準/能量$ \ mathcal {E} _n = \ frac {1} {n} \ sum_ {i = 1} ^ n \ xi_i ^ 2 $是個好主意觀察$ \ xi $以建立檢驗統計量。實際上，您可以構建能量$ T_n = \ frac {\ sum_i \ xi_i ^ 2- \ sigma ^ 2} {\ sqrt {2n \ sigma ^ 4}} $的標準化居中（低於$ H_0 $）版本$ T_n $ 。這樣就為選擇好的$ v_ {1- \ alpha} $
形成了$ \ {T_n \ geq v_ {1- \ alpha} \} $形式的$ \ alpha $臨界區域。檢驗的力量和維度。在這種情況下，很容易就可以顯示出以下公式來檢驗您的檢驗的力量：
$$ P _ {\ theta}（T \ leq v_ {1- \ alpha}）= P \ left（Z \ leq \ frac {v_ {1- \ alpha}} {\ sqrt {1 + 2 \ | \\ theta \ | _2 ^ 2 /（n \ sigma ^ 2）}}-\ frac {\ | \ theta \ | ^ 2_2} {\ sqrt {2n \ sigma ^ 4 + 2 \ sigma ^ 2 \ | \ theta \ | _2 ^ 2 / （n \ sigma ^ 2）}} \ right} $$和$ Z $的總和$ n $ iid個隨機變量，其中$ \ mathbb {E} [Z] = 0 $和$ Var（Z）= 1 $。
這意味著測試的功效會因信號$ \ | \ theta \ | ^ 2_2 $的能量而增加，而減少$ n $。實際上，這就是說，如果您增加問題的大小$ n $如果同時沒有增加信號的強度，那麼您正在向觀察中添加無信息的信息（或者您正在減少有用信息的比例）您所擁有的信息）：這就像增加噪音並降低測試的功效（即，您更有可能說什麼也沒發現，而實際上卻有東西）。
使用閾值統計量進行測試。如果信號中沒有太多能量，但是您知道線性變換可以幫助您將能量集中在一個信號的一小部分，則可以建立一個測試統計量，該統計量將僅評估信號的一小部分的能量。如果您事先知道它集中的位置（例如，您知道信號中不可能有高頻），那麼您可以在前面的測試中獲得一個功率，用小數字和$ \ | \ theta \ |代替$ n $。 ^ 2_2 $幾乎相同...如果您不事先知道，則必須對其進行估算，這將導致眾所周知的閾值測試。
請注意，該論點正是許多論文的根本，例如
維數詛咒的一部分是數據開始從中心散開。即使多元分量法線是IID（球面法線），也是如此。但是，如果數據具有相關結構，即使在低維空間中也要嚴格講歐幾里德距離，歐幾里德距離不是合適的指標。如果我們假設數據是帶有一些非零協方差的多元正態，並且出於爭論的目的，假設協方差矩陣是已知的。那麼馬氏距離是合適的距離量度，它與歐氏距離不同，歐氏距離只有在協方差矩陣與恆等矩陣成比例的情況下才會減小。
我認為這與維度/度量集中度的詛咒有關，但是我再也找不到找到激發這一觀點的討論了。我相信metaoptimize上有一個線程，但我沒能在Google上找到它。文檔（包含多個單詞）可以共享相同的主題，因此與共享大量常用單詞的簡短文檔非常相似。在特定情況下，丟棄向量的範數會有所幫助。
對稀疏性的公理度量是所謂的 $ \ ell_0 $ span>計數，該計數對向量中非零項的（有限）數量進行計數。使用此度量，向量 $（1,0,0,0）$ span>和 $（0,21,0,0 ）$ span>具有相同的稀疏性。而且絕對不是相同的 $ \ ell_2 $ span>規範。並且 $（1,0,0,0）$ span>（非常稀疏）具有相同的 $ \ ell_2 $ span >規範為 $ \ left（\ frac {1} {4}，\ frac {1} {4}，\ frac {1} {4}，\ frac {1} { 4} \ right）$ span>，這是一個非常平坦的非稀疏向量。並且絕對不相同的 $ \ ell_0 $ span>計數。
此函數（既不是范數也不是擬三角函數）是非光滑且非凸的。根據域的不同，它的名稱也有不同的名稱，例如：基數函數，數字度量或僅是簡約或稀疏。由於使用它會導致NP困難問題，因此通常出於實用目的被認為不實用。
同時使用標準距離或標準（例如 $ \ ell_2 $ span>歐幾里得距離）更容易處理，其問題之一是它們的 $ 1 $ span>-均勻性： $$ \ | a.x \ | = | a | \ | x \ | $$ span>表示 $ a \ neq 0 $ span>。這可能被認為是非直覺的，因為標量積不會更改數據中空條目的比例（ $ \ ell_0 $ span>為 $ 0 $ span> -homogeneous）。
因此，在實踐中，有些重新組合為 $ \ ell_p（x）$ span>術語（ $ p \ ge1 $ span>），例如套索，山脊或彈性網正則化。 $ \ ell_1 $ span>範數（曼哈頓或出租車的距離）或其平滑化身特別有用。由於E.Candès和其他人的作品，所以可以解釋為什麼 $ \ ell_1 $ span>是 $的好近似\ ell_0 $ span>：幾何解釋。其他人則以 $ p < 1 $ span>為 $ \ ell_p（x）$ span>的價格，凸性問題。
另一個有趣的途徑是重新公理稀疏性的概念。 N. Hurley等人的稀疏性比較方法是近期最著名的著作之一，涉及分佈的稀疏性。從六個公理（具有有趣的名字，如Robin Hood，Scaling，Rise Tide，Clone，BillGates和Babies）中，出現了幾個稀疏指數：一個基於基尼係數，另一個基於規範比率，尤其是二比一。 $ \ frac {\ ell_1} {\ ell_2} $ span>規範比率，如下所示：
儘管不是凸面的，但出租車中的歐幾里得：平滑的稀疏盲反捲積 $ \ frac {\ ell _1} {\ ell_2} $ span>正則化。 用於稀疏信號恢復的SPOQℓp-Over-Spaq正則化中提供了一些偽範數/範數比 $ \ ell_p / \ ell_q $ span> / a>。
論文關於高維空間中距離度量的驚人行為討論了高維空間中距離度量的行為。
它們遵循$ L_k $範數和提出曼哈頓$ L_1 $範數在高維空間中最有效用於聚類。他們還引入了分數範數 $ L_f $，類似於$ L_k $範數，但具有$ f \ in（0..1）$。
簡而言之，他們表明對於高維空間，使用歐幾里得範數作為默認值可能不是一個好主意；我們通常在這樣的空間中幾乎沒有直覺，並且由於維數而導致的指數爆炸很難用歐幾里得距離來考慮。