對相似性算法的了解起源于最近在做使用協(xié)同過濾原理的推薦系統(tǒng)中，基于鄰域的推薦算法（User-Based CF和 和 Item-Based CF）需要估算不同樣本之間的相似性度量(Similarity Measurement)，這也是機器學(xué)習(xí)中在做分類的時候的一個常見場景。
而相似度通常采用的方法就是計算樣本間的“距離”(Distance)。采用什么樣的方法計算距離是很講究，甚至關(guān)系到分類的正確與否。
本文的目的在于對當(dāng)下常見的相似度度量方法的原理，實現(xiàn)，優(yōu)缺點，改進版本，適用場景等幾個方面做一個總結(jié)
一、歐氏距離(EuclideanDistance)
歐氏距離是歐幾里得距離的簡稱，是最易于理解的一種距離計算方法，其實就是空間中兩點間的距離公式。
-
二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離（拓展到n維同理）
-
兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離
-
向量運算的形式：
-
就其意義而言，歐氏距離越小，兩個用戶相似度就越大，歐氏距離越大，兩個用戶相似度就越小。而在日常使用中，一般習(xí)慣于將相似度與1類比，對越相似的人給出越大的值，相似度在數(shù)值上反映為0<=sim_distance(x,y)<=1，越接近1，相似度越高。所以我們需要進行歸一化處理，可以通過將其函數(shù)值加1(避免除以0)，并取其倒數(shù)的方法來構(gòu)造歐幾里得相似度函數(shù)：
用 python實現(xiàn)計算歐幾里得距離，并構(gòu)造相似度函數(shù)：
# @Author : XZP
# @Email : pcxzp@live.com
# @File : EuclideanDistanceSimilarity.py
from 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
- 缺點：當(dāng)數(shù)據(jù)集出現(xiàn)異常值（即數(shù)據(jù)不是很規(guī)范）的時候，歐幾里德距離表現(xiàn)不"穩(wěn)定"，另除了異常值外，當(dāng)這種情況：例如A、B明明都喜歡這個電影，品味相似，但是B對電影的評分向來比較苛刻（評分都不太高），所以導(dǎo)致這時候用歐氏距離得出二者不相似的結(jié)論，這顯然不是我們所期望的結(jié)果。
二、標(biāo)準(zhǔn)化歐氏距離
三、曼哈頓距離
四、切比雪夫距離
五、 夾角余弦距離
如果高中正常畢業(yè), 參加過高考, 那么肯定會這么一個公式
cos<a, b> = a ? b / |a|?|b|
假設(shè)
a = (3, 1, 0),
b = (2, -1, 2)
分子是a,b兩個向量的內(nèi)積, (3, 1, 0) ? (2, -1, 2) = 3?2 + 1?(-1) + 0?2 = 5
分母是兩個向量模(模指的是向量的長度)的乘積.
總之這個cos的計算不要太簡單
余弦距離(余弦相似度), 計算的是兩個向量在空間中的夾角大小, 值域為[-1, 1]:
1代表夾角為0°, 完全重疊/完全相似;
-1代表夾角為180°, 完全相反方向/毫不相似.
余弦相似度的問題是: 其計算嚴(yán)格要求"兩個向量必須所有維度上都有數(shù)值", 比如:
v1 = (1, 2, 4),
v2 = (3, -1, null),
那么這兩個向量由于v2中第三個維度有null, 無法進行計算.
然而, 實際我們做數(shù)據(jù)挖掘的過程中, 向量在某個維度的值常常是缺失的, 比如
v2=(3, -1, null)
v2數(shù)據(jù)采集或者保存中缺少一個維度的信息, 只有兩個維度.
那么, 我們一個很樸素的想法就是, 我們在這個地方填充一個值, 不就滿足了"兩個向量必須所有維度上都有數(shù)值"的嚴(yán)格要求了嗎?
在填充值的時候, 一般我們用這個向量已有數(shù)據(jù)的平均值， 所以v2填充后變成
v2=(3, -1, 2),
接下來我們就可以計算cos<v1, v2>了.（由此引出皮爾遜距離）
七、皮爾遜相關(guān)系數(shù)
皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）是余弦相似度在維度值缺失情況下的一種改進
-
首先我們來看皮爾森相似度的公式：
假設(shè)有兩個變量X、Y，那么兩變量間的皮爾遜相關(guān)系數(shù)可通過以下公式計算：
公式一：
公式二：
公式三：
公式四：
以上列出的四個公式等價，其中E是數(shù)學(xué)期望，cov表示協(xié)方差，N表示變量取值的個數(shù)。
- 再來看皮爾遜相關(guān)系數(shù)的思路：皮爾遜是比歐幾里德距離更加復(fù)雜的可以判斷人們興趣相似度的一種方法。該相關(guān)系數(shù)通過將兩組數(shù)據(jù)與某一直線擬合的思想來求值，該值實際上就為該直線的斜率。其斜率的區(qū)間在[-1,1]之間，其絕對值的大小反映了兩者相似度大小，斜率越大，相似度越大，當(dāng)相似度為1時，該直線為一條對角線。
也被稱為“最佳擬合線”
再從余弦相似度的層面來理解皮爾遜相關(guān)系數(shù)，我把這些
null的維度都填上0, 然后讓所有其他維度減去這個向量各維度的平均值, 這樣的操作叫作中心化。中心化之后所有維度的平均值就是0了(妙哇！), 也滿足進行余弦計算的要求. 然后再進行我們的余弦計算得到結(jié)果. 這樣先中心化再余弦計得到的相關(guān)系數(shù)叫作皮爾遜相關(guān)系數(shù).由此再看計算皮爾遜相關(guān)系數(shù)的公式就明了了。用 python實現(xiàn)計算皮爾森相似度:
# @Author : XZP
# @Email : pcxzp@live.com
# @File : PersonSimilarity.py
from 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])
# 計算系數(shù)
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
總結(jié): 皮爾遜系數(shù)就是cos計算之前兩個向量都先進行中心化(centered)，余弦計算和皮爾遜相關(guān)系數(shù)計算就是一個東西兩個名字啊
- 優(yōu)點：
- 它在數(shù)據(jù)不是很規(guī)范的時候，會傾向于給出更好的結(jié)果。
- 修正了“夸大分值”的情況：二者有相對近似的偏好，但某人一般傾向于給出更高的分值，而二者的分值之差又始終保持一致，則他們依然可能會存在很好的相關(guān)性（單純的用歐幾里得距離，相似度會偏低，得出不相關(guān)的結(jié)論，這顯然不是我們所期望的。）
八、漢明距離
pass
九、總結(jié)
其實你會發(fā)現(xiàn)，選擇不同的相似性度量方法，對結(jié)果的影響是微乎其微的。 ——《集體智慧編程》
