k近邻推荐用到的各种距离
1 kkk-近鄰推薦原理
2 各種距離
2.1 歐幾里得距離
d12=(x1?x2)2+(y1?y2)2d_{12} = \sqrt{(x_{1} - x_{2})^2 + (y_{1} - y_{2})^2}d12?=(x1??x2?)2+(y1??y2?)2?
缺點:歐式距離是一種常用的距離度量,但它并不是尺度不變的,這意味著所計算的距離可能會根據特征的單位發生傾斜。通常,在使用歐式距離度量之前,需要對數據進行歸一化處理。
此外,隨著數據維數的增加,歐氏距離的作用也就越小。這與維數災難(curse of dimensionality)有關。
用例:當數據的維度比較低,歐式距離的效果非常好。如果在低維數據上使用歐式距離,則如 kkk-NN 和 HDBSCAN 之類的方法可達到開箱即用的效果。
2.2 曼哈頓距離
在曼哈頓街區要從一個十字路口開車到另一個十字路口,駕駛距離顯然不是兩點間的直線距離。這個實際駕駛距離就是曼哈頓距離。 曼哈頓距離也稱為“城市街區距離”(City Block distance)。
d12=∣x1?x2∣+∣y1?y2∣d_{12} = \left|x_{1} - x_{2}\right| + \left|y_{1} - y_{2}\right|d12?=∣x1??x2?∣+∣y1??y2?∣
缺點:盡管曼哈頓距離在高維數據中可以工作,但它比歐式距離直觀性差。此外,由于它可能不是最短路徑,有可能比歐氏距離給出一個更高的距離值。
用例:當數據集具有離散或二進制屬性時,曼哈頓距離似乎工作得很好,因為它考慮了在這些屬性值中實際可以采用的路徑。以歐式距離為例,它會在兩個向量之間形成一條直線,但實際上這是不可能的。
2.3 切比雪夫距離 (Chebyshev Distance)
切比雪夫距離定義為兩個向量在任意坐標維度上的最大差值。換句話說,它就是沿著一個軸的最大距離。切比雪夫距離通常被稱為棋盤距離,因為國際象棋的國王從一個方格到另一個方格的最小步數等于切比雪夫距離。
d12=max?(∣x1?x2∣,∣y1?y2∣)d_{12} = \max(\left|x_{1} - x_{2}\right|, \left|y_{1} - y_{2}\right|)d12?=max(∣x1??x2?∣,∣y1??y2?∣)
缺點:切比雪夫距離通常用于特定的用例,這使得它很難像歐氏距離或余弦相似度那樣作為通用的距離度量。因此,在確定適合用例時才使用它。
用例:切比雪夫距離用于提取從一個方塊移動到另一個方塊所需的最小移動次數。此外,在允許無限制八向移動的游戲中,這可能是有用的方法。在實踐中,切比雪夫距離經常用于倉庫物流,因為它非常類似于起重機移動一個物體的時間。
2.4 余弦距離
d12=x1x2+y1y2x12+y12x22+y22d_{12} = \frac{x_{1}x_{2} + y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}d12?=x12?+y12??x22?+y22??x1?x2?+y1?y2??
缺點:余弦相似度的一個主要缺點是沒有考慮向量的大小,而只考慮它們的方向。以推薦系統為例,余弦相似度就沒有考慮到不同用戶之間評分尺度的差異。
用例:當我們對高維數據向量的大小不關注時,可以使用余弦相似度。對于文本分析,當數據以單詞計數表示時,經常使用此度量。例如,當一個單詞在一個文檔中比另一個單詞更頻繁出現時,這并不一定意味著文檔與該單詞更相關。可能是文件長度不均勻或者計數的重要性不太重要。我們最好使用忽略幅度的余弦相似度。
2.5 閔氏距離(Minkowski)
d12=[(x1?x2)p+(y1?y2)p]1pd_{12} =[(x_1 - x_2) ^p+ (y_1 - y_2)^p]^{\frac{1}{p}}d12?=[(x1??x2?)p+(y1??y2?)p]p1?
最有趣的一點是,我們可以使用參數 ppp 來操縱距離度量,使其與其他度量非常相似。常見的 ppp 值有:
- p=1p=1p=1:曼哈頓距離
- p=2p=2p=2:歐氏距離
- p=∞p=\inftyp=∞:切比雪夫距離
缺點:閔氏距離與它們所代表的距離度量有相同的缺點,因此,對曼哈頓距離、歐幾里得距離和切比雪夫距離等度量標準有個好的理解非常重要。此外,參數ppp 的使用可能很麻煩,因為根據用例,查找正確的 ppp 值在計算上效率低。
用例:ppp的積極一面是可迭代,并找到最適合用例的距離度量。它允許在距離度量上有很大的靈活性,如果你非常熟悉 ppp和許多距離度量,將會獲益多多。
2.6 雅卡爾指數(Jaccard Index)
雅卡爾指數(交并比)是用于比較樣本集相似性與多樣性的統計量。雅卡爾系數能夠量度有限樣本集合的相似度,其定義為兩個集合交集大小與并集大小之間的比例。
dAB=1?∣A∩B∣∣A∪B∣d_{AB} =1 - \frac{|A \cap B|}{|A \cup B|}dAB?=1?∣A∪B∣∣A∩B∣?
缺點:雅卡爾指數的一個主要缺點是它受數據大小的影響很大。大數據集對指數有很大影響,因為它可以顯著增加并集,同時保持交集相似。
用例:雅卡爾指數通常用于使用二進制或二進制數據的應用程序中。當你有一個深度學習模型來預測圖像分割時,比如一輛汽車,雅卡爾指數可以用來計算給定真實標簽的預測分割的準確度。
類似地,它可以用于文本相似性分析,以測量文檔之間有多少詞語重疊。因此,它可以用來比較模式集合。
2.7 漢明距離(Hamming Distance)
漢明距離是兩個向量之間不同值的個數。它通常用于比較兩個相同長度的二進制字符串。它還可以用于字符串,通過計算不同字符的數量來比較它們之間的相似程度。
缺點:當兩個向量長度不相等時,漢明距離使用起來很麻煩。當幅度是重要指標時,建議不要使用此距離指標。
用例:典型的用例包括數據通過計算機網絡傳輸時的錯誤糾正 / 檢測。它可以用來確定二進制字中失真的數目,作為估計誤差的一種方法。此外,你還可以使用漢明距離來度量分類變量之間的距離。
2.8 半正矢(Haversine)
半正矢距離是指球面上的兩點在給定經緯度條件下的距離。它與歐幾里得距離非常相似,因為它可以計算兩點之間的最短連線。主要區別在于半正矢距離不可能有直線,因為這里的假設是兩個點都在一個球面上。
d=2rarcsin??(sin?2(φ2?φ12)+cos?(φ1)cos?(φ2)sin?2(λ2?λ12))d=2 \operatorname{r\arcsin}\left(\sqrt{\sin ^{2}\left(\frac{\varphi_{2}-\varphi_{1}}{2}\right)+\cos \left(\varphi_{1}\right) \cos \left(\varphi_{2}\right) \sin ^{2}\left(\frac{\lambda_{2}-\lambda_{1}}{2}\right)}\right)d=2rarcsin(sin2(2φ2??φ1??)+cos(φ1?)cos(φ2?)sin2(2λ2??λ1??)?)
符號說明:
ddd:兩點之間的距離;
rrr:球的半徑;
φ1,φ2\varphi_1,\varphi_2φ1?,φ2?:點1和點2的緯度,以弧度制度量;
λ1,λ2\lambda_1, \lambda_2λ1?,λ2?:點1和點2的經度,以弧度制度量。
缺點:這種距離測量的一個缺點是,假定這些點位于一個球體上。實際上,這種情況很少出現,例如,地球不是完美的圓形,在某些情況下可能使計算變得困難。相反,如果假定是橢球,使用 Vincenty 距離比較好。
用例:半正矢距離通常用于導航。例如,你可以使用它來計算兩個國家之間的飛行距離。請注意,如果距離本身不那么大,則不太適合。
2.9 S?rensen-Dice 系數
S?rensen-Dice 系數與雅卡爾指數非常相似,都是度量樣本集的相似性和多樣性。盡管它們的計算方法相似,但是 S?rensen-Dice 系數更直觀一些,因為它可以被視為兩個集合之間重疊的百分比,這個值在 0 到 1 之間:
D(A,B)=2∣A∩B∣∣A∣+∣B∣D(A, B)=\frac{2|A \cap B|}{|A|+|B|}D(A,B)=∣A∣+∣B∣2∣A∩B∣?
缺點:正如雅卡爾指數,S?rensen-Dice 系數也夸大了很少或沒有真值的集合的重要性,因此,它可以控制多集合的平均得分,還可以控制多組平均得分并按相關集合的大小成反比地加權每個項目,而不是平等對待它們。
用例:用例與雅卡爾指數相似,它通常用于圖像分割任務或文本相似性分析。
2.10 M-Distance
Mei Zheng, Fan Min, Heng-Ru Zhang, Wen-Bin Chen, Fast recommendations with the M-distance, IEEE Access 4 (2016) 1464–1468.
2.11 MCFV
Heng-Ru Zhang, Fan Min, Zhi-Heng Zhang, Song Wang, Efficient collaborative filtering recommendations with multi-channel feature vectors. International Journal of Machine Learning & Cybernetics. (2019)1165–1172.
2.12 三角距離Triangle
Triangle?(ij,iq)=Triangle?(OA→,OB→)=1?∣AB∣∣OA∣+∣OB∣Triangle?(ij,iq)=1?∑u∈Cij,iq(ru,j?ru,q)2∑u∈Ci,i,qru,j2+∑u∈Ci,i,qru,q2\operatorname{Triangle}\left(i_{j}, i_{q}\right)=\operatorname{Triangle}(\overrightarrow{O A}, \overrightarrow{O B})=1-\frac{|A B|}{|O A|+|O B|} \\ \operatorname{Triangle}\left(i_{j}, i_{q}\right)=1-\frac{\sqrt{\sum_{u \in C_{i j, i_{q}}}\left(r_{u, j}-r_{u, q}\right)^{2}}}{\sqrt{\sum_{u \in C_{i, i, q}} r_{u, j}^{2}}+\sqrt{\sum_{u \in C_{i, i, q}} r_{u, q}^{2}}} Triangle(ij?,iq?)=Triangle(OA,OB)=1?∣OA∣+∣OB∣∣AB∣?Triangle(ij?,iq?)=1?∑u∈Ci,i,q??ru,j2??+∑u∈Ci,i,q??ru,q2??∑u∈Cij,iq???(ru,j??ru,q?)2??
where OA→\overrightarrow{O A}OA is the rating vector of iji_{j}ij?, OB→\overrightarrow{O B}OB is the rating vector of iqi_{q}iq?.
Triangle considers both the length of vectors and the angle between them, so it is more reasonable than the angle based Cosine measure. For example, given the two vectors A = (5, 5, 5) and B = (1, 1, 1), the Cosine similarity is 1, which is contrary to common sense. In contrast, the Triangle similarity between them is 0.33, more in line with expectations.
三角距離既考慮了向量的長度,也考慮了它們之間的夾角,因此比基于角度的余弦測度更合理。 例如,給定兩個向量 A = (5, 5, 5) 和 B = (1, 1, 1),則余弦相似度為 1,這與常識相反。 相比之下,它們之間的三角形相似度為0.33,更符合預期。
Shuang-Bo Sun, Zhi-Heng Zhang, Xin-Ling Dong, Heng-Ru Zhang, Tong-Jun Li, Lin Zhang, Fan Min, Integrating Triangle and Jaccard similarities for recommendation, PLOS ONE 12 (8) (2017) 1–16.
總結
以上是生活随笔為你收集整理的k近邻推荐用到的各种距离的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python读取json格式的超参数
- 下一篇: 巴克沙里手稿——历史性的突破可能比内容本