內容導讀
對相似性算法的了解起源於最近在做 使用協同過濾原理 的推薦系統中， 基於鄰域的推薦算法 （User-Based CF和 和 Item-Based CF）需要估算不同樣本之間的 相似性度量(Similarity Measurement) ，這也是機器學習中在做 分類 的時候的一個常見場景。而 相似度 通常採用的方法就是計算樣本間的 「距離」(Distance) 。採用什麼樣的方法計算距離是很講究，甚至關係到分類的正確與否。缺點： 當數據集出現異常值（即數據不是很規範）的時候，歐幾裡德距離表現不"穩定" ，另除了異常值外，當這種情況：例如A、B明明都喜歡這個電影，品味相似，但是B對電影的評分向來比較苛刻（評分都不太高），所以導致這時候用歐氏距離得出二者不相似的結論，這顯然不是我們所期望的結果。修正了 「誇大分值」 的情況：二者有相對近似的偏好，但某人一般傾向於給出更高的分值，而二者的分值之差又始終保持一致，則他們依然可能會存在很好的相關性（單純的用歐幾裡得距離，相似度會偏低，得出不相關的結論，這顯然不是我們所期望的。其實你會發現，選擇不同的相似性度量方法，對結果的影響是微乎其微的。
對相似性算法的了解起源於最近在做使用協同過濾原理的推薦系統中，基於鄰域的推薦算法（User-Based CF和 和 Item-Based CF）需要估算不同樣本之間的相似性度量(Similarity Measurement)，這也是機器學習中在做分類的時候的一個常見場景。
而相似度通常採用的方法就是計算樣本間的「距離」(Distance)。採用什麼樣的方法計算距離是很講究，甚至關係到分類的正確與否。
本文的目的在於對當下常見的相似度度量方法的原理，實現，優缺點，改進版本，適用場景等幾個方面做一個總結
一、歐氏距離(EuclideanDistance)
歐氏距離是歐幾裡得距離的簡稱，是最易於理解的一種距離計算方法，其實就是空間中兩點間的距離公式。
二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離（拓展到n維同理）
兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離
向量運算的形式：
就其意義而言，歐氏距離越小，兩個用戶相似度就越大，歐氏距離越大，兩個用戶相似度就越小。而在日常使用中，一般習慣於將相似度與1類比，對越相似的人給出越大的值，相似度在數值上反映為0
用 python實現計算歐幾裡得距離，並構造相似度函數：
# @Author : XZP# @Email : pcxzp@live.com# @File : EuclideanDistanceSimilarity.pyfrom math import sqrt# 找到二者相同評分項def get_same_Item(prefs, person1, person2): si = {} for item in prefs[person1]: if item in prefs[person2]: si[item] = 1 return si# 歐幾裡得相似度算法def sim_euclid(prefs, p1, p2): si = get_same_Item(prefs, p1, p2) if len(si) == 0: return 0 sum_of_squares = sum([pow(prefs[p1][item] - prefs[p2][item], 2) for item in si]) return 1 / (1 + sqrt(sum_of_squares))if __name__ == '__main__': critics = {'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5, 'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 3.5}} print(sim_euclid(critics, 'Lisa Rose', 'Gene Seymour')) # 0.29429805508554946
缺點：當數據集出現異常值（即數據不是很規範）的時候，歐幾裡德距離表現不"穩定"，另除了異常值外，當這種情況：例如A、B明明都喜歡這個電影，品味相似，但是B對電影的評分向來比較苛刻（評分都不太高），所以導致這時候用歐氏距離得出二者不相似的結論，這顯然不是我們所期望的結果。
二、標準化歐氏距離
三、曼哈頓距離
四、切比雪夫距離
五、 夾角餘弦距離
如果高中正常畢業, 參加過高考, 那麼肯定會這麼一個公式
cos = a b / |a||b|
假設
a = (3, 1, 0),b = (2, -1, 2)
分子是a,b兩個向量的內積, (3, 1, 0) (2, -1, 2) = 32 + 1(-1) + 02 = 5分母是兩個向量模(模指的是向量的長度)的乘積.
總之這個cos的計算不要太簡單
餘弦距離(餘弦相似度), 計算的是兩個向量在空間中的夾角大小, 值域為[-1, 1]:1代表夾角為0°, 完全重疊/完全相似;-1代表夾角為180°, 完全相反方向/毫不相似.
餘弦相似度的問題是: 其計算嚴格要求"兩個向量必須所有維度上都有數值", 比如:
v1 = (1, 2, 4), v2 = (3, -1, null),
那麼這兩個向量由於v2中第三個維度有null, 無法進行計算.
然而, 實際我們做數據挖掘的過程中, 向量在某個維度的值常常是缺失的, 比如
v2=(3, -1, null)
v2數據採集或者保存中缺少一個維度的信息, 只有兩個維度.
那麼, 我們一個很樸素的想法就是, 我們在這個地方填充一個值, 不就滿足了"兩個向量必須所有維度上都有數值"的嚴格要求了嗎?
在填充值的時候, 一般我們用這個向量已有數據的平均值， 所以v2填充後變成
v2=(3, -1, 2),
接下來我們就可以計算cos了.（由此引出皮爾遜距離）
七、皮爾遜相關係數
皮爾遜相關係數（Pearson Correlation Coefficient）是餘弦相似度在維度值缺失情況下的一種改進
首先我們來看皮爾森相似度的公式：假設有兩個變量X、Y，那麼兩變量間的皮爾遜相關係數可通過以下公式計算：公式一：
公式二：
公式三：
公式四：
以上列出的四個公式等價，其中E是數學期望，cov表示協方差，N表示變量取值的個數。
再來看皮爾遜相關係數的思路：皮爾遜是比歐幾裡德距離更加複雜的可以判斷人們興趣相似度的一種方法。該相關係數通過將兩組數據與某一直線擬合的思想來求值，該值實際上就為該直線的斜率。其斜率的區間在[-1,1]之間，其絕對值的大小反映了兩者相似度大小，斜率越大，相似度越大，當相似度為1時，該直線為一條對角線。
也被稱為「最佳擬合線」
再從餘弦相似度的層面來理解皮爾遜相關係數，我把這些null的維度都填上0, 然後讓所有其他維度減去這個向量各維度的平均值, 這樣的操作叫作中心化。中心化之後所有維度的平均值就是0了(妙哇！), 也滿足進行餘弦計算的要求. 然後再進行我們的餘弦計算得到結果. 這樣先中心化再餘弦計得到的相關係數叫作皮爾遜相關係數.由此再看計算皮爾遜相關係數的公式就明了了。
用 python實現計算皮爾森相似度:
# @Author : XZP# @Email : pcxzp@live.com# @File : PersonSimilarity.pyfrom math import sqrt def sim_pearson(prefs, p1, p2): # Get the list of mutually rated items si = get_same_Item(prefs, p1, p2) n = len(si) # if they are no ratings in common, return 0 if n == 0: return 0 # Sums of all the preferences sum_x = sum([prefs[p1][it] for it in si]) sum_y = sum([prefs[p2][it] for it in si]) sum_x2 = sum([pow(prefs[p1][it], 2) for it in si]) sum_y2 = sum([pow(prefs[p2][it], 2) for it in si]) sum_xy = sum([prefs[p1][it] * prefs[p2][it] for it in si]) # 計算係數 num = sum_xy - (sum_x * sum_y / n) den = sqrt((sum_x2 - pow(sum_x, 2) / n) * (sum_y2 - pow(sum_y, 2) / n)) if den == 0: return 0 r = num / den return r
總結: 皮爾遜係數就是cos計算之前兩個向量都先進行中心化(centered)，餘弦計算和皮爾遜相關係數計算就是一個東西兩個名字啊
優點：
它在數據不是很規範的時候，會傾向於給出更好的結果。
修正了「誇大分值」的情況：二者有相對近似的偏好，但某人一般傾向於給出更高的分值，而二者的分值之差又始終保持一致，則他們依然可能會存在很好的相關性（單純的用歐幾裡得距離，相似度會偏低，得出不相關的結論，這顯然不是我們所期望的。）
八、漢明距離
pass
九、總結
其實你會發現，選擇不同的相似性度量方法，對結果的影響是微乎其微的。 ——《集體智慧編程》