第二章：推薦系統(tǒng)入門
原文：http://guidetodatamining.com/chapter-2/
內(nèi)容：
- 推薦系統(tǒng)工作原理
- 社會化協(xié)同過濾工作原理
- 如何找到相似物品
- 曼哈頓距離
- 歐幾里得距離
- 閔可夫斯基距離
- 皮爾遜相關(guān)系數(shù)
- 余弦相似度
- 使用Python實現(xiàn)K最鄰近算法
- 圖書漂流站（BookCrossing）數(shù)據(jù)集
你喜歡的東西我也喜歡
我們將從推薦系統(tǒng)開始，開啟數(shù)據(jù)挖掘之旅戚绕。推薦系統(tǒng)無處不在仪缸，如亞馬遜網(wǎng)站的“看過這件商品的顧客還購買過”板塊：
last.fm上對音樂和演唱會的推薦（相似歌手）：
在亞馬遜的例子里，它用了兩個元素來進(jìn)行推薦：一是我瀏覽了里維斯翻譯的《法華經(jīng)》一書列肢；二是其他瀏覽過該書的顧客還瀏覽過的譯作。
本章我們講述的推薦方法稱為協(xié)同過濾宾茂。顧名思義瓷马，這個方法是利用他人的喜好來進(jìn)行推薦，也就是說跨晴，是大家一起產(chǎn)生的推薦欧聘。他的工作原理是這樣的：如果要推薦一本書給你，我會在網(wǎng)站上查找一個和你類似的用戶端盆，然后將他喜歡的書籍推薦給你——比如巴奇加盧比的《發(fā)條女孩》怀骤。
如何找到相似的用戶费封？
所以首先要做的工作是找到相似的用戶。這里用最簡單的二維模型來描述蒋伦。假設(shè)用戶會在網(wǎng)站用五顆星來評價一本書——沒有星表示書寫得很糟弓摘，五顆星表示很好。因為我們用的是二維模型痕届，所以僅對兩本書進(jìn)行評價：史蒂芬森的《雪崩》（縱軸）和拉爾森的《龍紋身的女孩》（橫軸）韧献。
首先，下表顯示有三位用戶對這兩本書做了評價：
現(xiàn)在我想為神秘的X先生推薦一本書研叫，他給《雪崩》打了四星锤窑，《龍紋身的女孩》兩星。第一個任務(wù)是找出哪個用戶和他最為相似嚷炉。我們用距離來表示渊啰。
曼哈頓距離
最簡單的距離計算方式是曼哈頓距離。在二維模型中申屹，每個人都可以用(x, y)的點(diǎn)來表示绘证，這里我用下標(biāo)來表示不同的人，(x1, y1)表示艾米独柑，(x2, y2)表示那位神秘的X先生迈窟，那么他們之間的曼哈頓距離就是：
也就是x之差的絕對值加上y之差的絕對值，這樣他們的距離就是4忌栅。
完整的計算結(jié)果如下：
艾米的距離最近车酣，在她的瀏覽歷史中可以看到她曾給巴奇加盧比的《發(fā)條女孩》打過五星，于是我們就可以把這本書推薦給X先生索绪。
歐幾里得距離
曼哈頓距離的優(yōu)點(diǎn)之一是計算速度快湖员，對于Facebook這樣需要計算百萬用戶之間的相似度時就非常有利。
勾股定理
也許你還隱約記得勾股定理瑞驱。另一種計算距離的方式就是看兩點(diǎn)之間的直線距離：
利用勾股定理娘摔，我們可以如下計算距離：
這條斜線就是歐幾里得距離，公式是：
回顧一下唤反，這里的x1表示用戶1喜歡《龍紋身》的程度凳寺，x2是用戶2喜歡這本書的程度；y1則是用戶1喜歡《雪崩》的程度彤侍，y2是用戶2喜歡這本書的程度肠缨。
艾米給《龍紋身》和《雪崩》都打了五顆星，神秘的X先生分別打了兩星和四星盏阶，這樣他們之間的歐幾里得距離就是：
以下是全部用戶的計算結(jié)果：
N維模型
剛才我們僅僅對兩本書進(jìn)行評價（二維模型）晒奕，下面讓我們擴(kuò)展一下，嘗試更復(fù)雜的模型。假設(shè)我們現(xiàn)在要為一個在線音樂網(wǎng)站的用戶推薦樂隊脑慧。用戶可以用1至5星來評價一個樂隊魄眉，其中包含半星（如2.5星）。下表展示了8位用戶對8支樂隊的評價：
表中的短橫表示這位用戶沒有給這支樂隊打分闷袒。我們在計算兩個用戶的距離時豁护，只采用他們都評價過的樂隊奏篙，比如要計算Angelica和Bill的距離港华，我們只會用到5支樂隊刻蟹。這兩個用戶的曼哈頓距離為：
最后距離即是上方數(shù)據(jù)的加和：(1.5 + 1.5 + 3 + 2 + 1)。
計算歐幾里得距離的方法也是類似的淘捡，我們也只取雙方都評價過的樂隊藕各。
用公式來描述即：
掌握了嗎？ 那就試試計算其他幾個用戶之間的距離吧焦除。
有個瑕疵
當(dāng)我們計算Hailey和Veronica的距離時會發(fā)現(xiàn)一個問題：他們共同評價的樂隊只有兩支（Norah Jones和The Strokes）激况，而Hailey和Jordyn共同評價了五支樂隊，這似乎會影響我們的計算結(jié)果膘魄，因為Hailey和Veronica之間是二維的乌逐，而Haily和Veronica之間是五維的。曼哈頓距離和歐幾里得距離在數(shù)據(jù)完整的情況下效果最好创葡。如何處理缺失數(shù)據(jù)浙踢，這在研究領(lǐng)域仍是一個活躍的話題。本書的后續(xù)內(nèi)容會進(jìn)行一些討論灿渴，這里先不展開÷宀ǎ現(xiàn)在，讓我們開始構(gòu)建一個推薦系統(tǒng)吧骚露。
推廣：閔可夫斯基距離
我們可以將曼哈頓距離和歐幾里得距離歸納成一個公式蹬挤，這個公式稱為閔可夫斯基距離：
其中：
-
r = 1該公式即曼哈頓距離 -
r = 2該公式即歐幾里得距離 -
r = ∞極大距離
當(dāng)你在書中看到這些數(shù)學(xué)公式，你可以選擇快速略過它棘幸，繼續(xù)讀下面的文字焰扳，過去我就是這樣；你也可以停下來误续，好好分析一下這些公式吨悍，會發(fā)現(xiàn)其實它們并不難理解。比如上面的公式蹋嵌，當(dāng)r = 1時育瓜，可以簡化成如下形式：
仍用上文的音樂站點(diǎn)為例，x和y分別表示兩個用戶欣尼，d(x, y)表示他們之間的距離，n表示他們共同評價過的樂隊數(shù)量，我們之前已經(jīng)做過計算：
其中Difference一欄表示兩者評分之差的絕對值愕鼓，加起來等于9钙态，也就是他們之間的距離。
當(dāng)r = 2時菇晃，我們得到歐幾里得距離的計算公式：
提前預(yù)告一下：r值越大册倒，單個維度的差值大小會對整體距離有更大的影響。
使用Python代碼來表示數(shù)據(jù)（終于要開始編程了）
在Python中磺送，我們可以用多種方式來描述上表中的數(shù)據(jù)驻子，這里我選擇Python的字典類型（或者稱為關(guān)聯(lián)數(shù)組、哈希表）估灿。
注：本書的所有代碼可以在這里找到崇呵。
users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
"Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
"Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
"Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
"Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
"Jordyn": {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
"Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
"Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
}
我們可以用以下方式來獲取某個用戶的評分：
>>> user["Veronica"]
{"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
>>>
計算曼哈頓距離
def manhattan(rating1, rating2):
"""計算曼哈頓距離。rating1和rating2參數(shù)中存儲的數(shù)據(jù)格式均為
{'The Strokes': 3.0, 'Slightly Stoopid': 2.5}"""
distance = 0
for key in rating1:
if key in rating2:
distance += abs(rating1[key] - rating2[key])
return distance
我們可以做一下測試：
>>> manhattan(users['Hailey'], users['Veronica'])
2.0
>>> manhattan(users['Hailey'], users['Jordyn'])
7.5
>>>
下面我們編寫一個函數(shù)來找出距離最近的用戶（其實該函數(shù)會返回一個用戶列表馅袁，按距離排序）：
def computeNearestNeighbor(username, users):
"""計算所有用戶至username用戶的距離域慷，倒序排列并返回結(jié)果列表"""
distances = []
for user in users:
if user != username:
distance = manhattan(users[user], users[username])
distances.append((distance, user))
# 按距離排序——距離近的排在前面
distances.sort()
return distances
簡單測試一下：
>>> computeNearestNeighbor("Hailey", users)
[(2.0, 'Veronica'), (4.0, 'Chan'), (4.0, 'Sam'), (4.5, 'Dan'), (5.0, 'Angelica'), (5.5, 'Bill'), (7.5, 'Jordyn')]
最后，我們結(jié)合以上內(nèi)容來進(jìn)行推薦汗销。假設(shè)我想為Hailey做推薦犹褒，這里我找到了離他距離最近的用戶Veronica。然后弛针，我會找到出Veronica評價過但Hailey沒有評價的樂隊叠骑，并假設(shè)Hailey對這些陌生樂隊的評價會和Veronica相近。比如削茁，Hailey沒有評價過Phoenix樂隊宙枷，而Veronica對這個樂隊打出了4分，所以我們認(rèn)為Hailey也會喜歡這支樂隊付材。下面的函數(shù)就實現(xiàn)了這一邏輯：
def recommend(username, users):
"""返回推薦結(jié)果列表"""
# 找到距離最近的用戶
nearest = computeNearestNeighbor(username, users)[0][1]
recommendations = []
# 找出這位用戶評價過朦拖、但自己未曾評價的樂隊
neighborRatings = users[nearest]
userRatings = users[username]
for artist in neighborRatings:
if not artist in userRatings:
recommendations.append((artist, neighborRatings[artist]))
# 按照評分進(jìn)行排序
return sorted(recommendations, key=lambda artistTuple: artistTuple[1], reverse = True)
下面我們就可以用它來為Hailey做推薦了：
>>> recommend('Hailey', users)
[('Phoenix', 4.0), ('Blues Traveler', 3.0), ('Slightly Stoopid', 2.5)]
運(yùn)行結(jié)果和我們的預(yù)期相符。我們看可以看到厌衔，和Hailey距離最近的用戶是Veronica璧帝，Veronica對Phoenix樂隊打了4分。我們再試試其他人：
>>> recommend('Chan', users)
[('The Strokes', 4.0), ('Vampire Weekend', 1.0)]
>>> recommend('Sam', users)
[('Deadmau5', 1.0)]
我們可以猜想Chan會喜歡The Strokes樂隊富寿，而Sam不會太欣賞Deadmau5睬隶。
>>> recommend('Angelica', users)
[]
對于Angelica，我們得到了空的返回值页徐，也就是說我們無法對其進(jìn)行推薦苏潜。讓我們看看是哪里有問題：
>>> computeNearestNeighbor('Angelica', users)
[(3.5, 'Veronica'), (4.5, 'Chan'), (5.0, 'Hailey'), (8.0, 'Sam'), (9.0, 'Bill'), (9.0, 'Dan'), (9.5, 'Jordyn')]
Angelica最相似的用戶是Veronica，讓我們回頭看看數(shù)據(jù)：
我們可以看到变勇，Veronica評價過的樂隊恤左，Angelica也都評價過了贴唇，所以我們沒有推薦。
之后飞袋，我們會討論如何解決這一問題戳气。
作業(yè)：實現(xiàn)一個計算閔可夫斯基距離的函數(shù)，并在計算用戶距離時使用它巧鸭。
def minkowski(rating1, rating2, r):
distance = 0
for key in rating1:
if key in rating2:
distance += pow(abs(rating1[key] - rating2[key]), r)
return pow(distance, 1.0 / r)
# 修改computeNearestNeighbor函數(shù)中的一行
distance = minkowski(users[user], users[username], 2)
# 這里2表示使用歐幾里得距離
用戶的問題
讓我們仔細(xì)看看用戶對樂隊的評分瓶您，可以發(fā)現(xiàn)每個用戶的打分標(biāo)準(zhǔn)非常不同：
- Bill沒有打出極端的分?jǐn)?shù)，都在2至4分之間纲仍；
- Jordyn似乎喜歡所有的樂隊呀袱，打分都在4至5之間；
- Hailey是一個有趣的人郑叠，他的分?jǐn)?shù)不是1就是4夜赵。
那么，如何比較這些用戶呢锻拘？比如Hailey的4分相當(dāng)于Jordan的4分還是5分呢油吭？我覺得更接近5分。這樣一來就會影響到推薦系統(tǒng)的準(zhǔn)確性了署拟。
- 左：我非常喜歡Broken Bells樂隊婉宰，所以我給他們打4分！
- 右：Broken Bells樂隊還可以推穷，我打4分心包。
皮爾遜相關(guān)系數(shù)
解決方法之一是使用皮爾遜相關(guān)系數(shù)。簡單起見馒铃，我們先看下面的數(shù)據(jù)（和之前的數(shù)據(jù)不同）：
這種現(xiàn)象在數(shù)據(jù)挖掘領(lǐng)域稱為“分?jǐn)?shù)膨脹”蟹腾。Clara最低給了4分——她所有的打分都在4至5分之間。我們將它繪制成圖表：
一條直線——完全吻合Ｇ睢Ｍ拗场！
直線即表示Clara和Robert的偏好完全一致议谷。他們都認(rèn)為Phoenix是最好的樂隊炉爆，然后是Blues Traveler、Norah Jones卧晓。如果Clara和Robert的意見不一致芬首，那么落在直線上的點(diǎn)就越少。
意見基本一致的情形
意見不太一致的情形
所以從圖表上理解逼裆，意見相一致表現(xiàn)為一條直線郁稍。皮爾遜相關(guān)系數(shù)用于衡量兩個變量之間的相關(guān)性（這里的兩個變量指的是Clara和Robert），它的值在-1至1之間胜宇，1表示完全吻合耀怜，-1表示完全相悖恢着。從直觀上理解，最開始的那條直線皮爾遜相關(guān)系數(shù)為1财破，第二張是0.91然评，第三張是0.81。因此我們利用這一點(diǎn)來找到相似的用戶狈究。
皮爾遜相關(guān)系數(shù)的計算公式是：
這里我說說自己的經(jīng)歷。我大學(xué)讀的是現(xiàn)代音樂藝術(shù)盏求，課程包括芭蕾抖锥、現(xiàn)代舞、服裝設(shè)計等碎罚，沒有任何數(shù)學(xué)課程磅废。我高中讀的是男子學(xué)校，學(xué)習(xí)了管道工程和汽車維修荆烈，只懂得很基礎(chǔ)的數(shù)學(xué)知識拯勉。不知是因為我的學(xué)科背景，還是習(xí)慣于用直覺來思考憔购，當(dāng)我遇到這樣的數(shù)學(xué)公式時會習(xí)慣性地跳過宫峦，繼續(xù)讀下面的文字。如果你和我一樣玫鸟，我強(qiáng)烈建議你與這種惰性抗?fàn)幍急粒囍ダ斫膺@些公式。它們雖然看起來很復(fù)雜屎飘，但還是能夠被常人所理解的妥曲。
上面的公式除了看起來比較復(fù)雜，另一個問題是要獲得計算結(jié)果必須對數(shù)據(jù)做多次遍歷钦购。好在我們有另外一個公式檐盟，能夠計算皮爾遜相關(guān)系數(shù)的近似值：
這個公式雖然看起來更加復(fù)雜，而且其計算結(jié)果會不太穩(wěn)定押桃，有一定誤差存在葵萎，但它最大的優(yōu)點(diǎn)是，用代碼實現(xiàn)的時候可以只遍歷一次數(shù)據(jù)怨规，我們會在下文看到陌宿。首先，我們將這個公式做一個分解波丰，計算下面這個表達(dá)式的值：
對于Clara和Robert壳坪，我們可以得到：
很簡單把？下面我們計算這個公式：
Clara的總評分是22.5掰烟， Robert是15爽蝴，他們評價了5支樂隊沐批，因此：
所以，那個巨型公式的分子就是70 - 67.5 = 2.5蝎亚。
下面我們來看分母：
首先：
我們已經(jīng)計算過Clara的總評分是22.5九孩，它的平方是506.25，除以樂隊的數(shù)量5发框，得到101.25躺彬。綜合得到：
對于Robert，我們用同樣的方法計算：
最后得到：
因此梅惯，1表示Clara和Robert的偏好完全吻合宪拥。
先休息一下吧
計算皮爾遜相關(guān)系數(shù)的代碼
from math import sqrt
def pearson(rating1, rating2):
sum_xy = 0
sum_x = 0
sum_y = 0
sum_x2 = 0
sum_y2 = 0
n = 0
for key in rating1:
if key in rating2:
n += 1
x = rating1[key]
y = rating2[key]
sum_xy += x * y
sum_x += x
sum_y += y
sum_x2 += pow(x, 2)
sum_y2 += pow(y, 2)
# 計算分母
denominator = sqrt(sum_x2 - pow(sum_x, 2) / n) * sqrt(sum_y2 - pow(sum_y, 2) / n)
if denominator == 0:
return 0
else:
return (sum_xy - (sum_x * sum_y) / n) / denominator
測試一下：
>>> pearson(users['Angelica'], users['Bill'])
-0.9040534990682699
>>> pearson(users['Angelica'], users['Hailey'])
0.42008402520840293
>>> pearson(users['Angelica'], users['Jordyn'])
0.7639748605475432
最后一個公式：余弦相似度
這里我將奉上最后一個公式：余弦相似度。它在文本挖掘中應(yīng)用得較多铣减，在協(xié)同過濾中也會使用到她君。為了演示如何使用該公式，我們換一個示例葫哗。這里記錄了每個用戶播放歌曲的次數(shù)缔刹，我們用這些數(shù)據(jù)進(jìn)行推薦：
簡單掃一眼上面的數(shù)據(jù)（或者用之前講過的距離計算公式），我們可以發(fā)現(xiàn)Ann的偏好和Sally更為相似劣针。
問題在哪兒校镐？
我在iTunes上有大約4000首歌曲，下面是我最常聽的音樂：
可以看到捺典，Moonlight Sonata這首歌我播放了25次灭翔，但很有可能你一次都沒有聽過。事實上辣苏，上面列出的這些歌曲可能你一首都沒聽過肝箱。此外，iTunes上有1500萬首音樂稀蟋，而我只聽過4000首煌张。所以說單個用戶的數(shù)據(jù)是 稀疏 的，因為非零值較總體要少得多退客。當(dāng)我們用1500萬首歌曲來比較兩個用戶時骏融，很有可能他們之間沒有任何交集，這樣一來就無從計算他們之間的距離了萌狂。
類似的情況是在計算兩篇文章的相似度時档玻。比如說我們想找一本和《The Space Pioneers》相類似的書，方法之一是利用單詞出現(xiàn)的頻率茫藏，即統(tǒng)計每個單詞在書中出現(xiàn)的次數(shù)占全書單詞的比例误趴，如“the”出現(xiàn)頻率為6.13%，“Tom” 0.89%务傲，“space” 0.25%凉当。我們可以用這些數(shù)據(jù)來尋找一本相近的書枣申。但是，這里同樣有數(shù)據(jù)的稀疏性問題看杭≈姨伲《The Space Pioneers》中有6629個不同的單詞，但英語語言中有超過100萬個單詞楼雹，這樣一來非零值就很稀少了模孩，也就不能計算兩本書之間的距離。
余弦相似度的計算中會略過這些非零值贮缅。它的計算公式是：
其中瓜贾，“·”號表示數(shù)量積⌒酰“||x||”表示向量x的模，計算公式是：
我們用上文中“偏好完全一致”的示例：
所以兩個向量為：
它們的模是：
數(shù)量積的計算：
因此余弦相似度是：
余弦相似度的范圍從1到-1筷笨，1表示完全匹配憔鬼，-1表示完全相悖。所以0.935表示匹配度很高胃夏。
作業(yè)：嘗試計算Angelica和Veronica的余弦相似度
應(yīng)該使用哪種相似度轴或？
我們整本書都會探索這個問題，以下是一些提示：
- 如果數(shù)據(jù)存在“分?jǐn)?shù)膨脹”問題仰禀，就使用皮爾遜相關(guān)系數(shù)照雁。
- 如果數(shù)據(jù)比較“密集”，變量之間基本都存在公有值答恶，且這些距離數(shù)據(jù)是非常重要的饺蚊，那就使用歐幾里得或曼哈頓距離。
- 如果數(shù)據(jù)是稀疏的悬嗓，則使用余弦相似度污呼。
所以，如果數(shù)據(jù)是密集的包竹，曼哈頓距離和歐幾里得距離都是適用的燕酷。那么稀疏的數(shù)據(jù)可以使用嗎？我們來看一個也和音樂有關(guān)的示例：假設(shè)有三個人周瞎，每人都給100首音樂評過分苗缩。
- Jake（左）：鄉(xiāng)村音樂的忠實聽眾。
- Linda和Eric（右）：我們愛六十年代的搖滾樂声诸！
Linda和Eric喜歡相同的音樂酱讶，他們的評分列表中有20首相同的的歌曲，且評分均值相差不到0.5彼乌！所以他們之間的曼哈頓距離為20 x 0.5 = 10浴麻，歐幾里得距離則為：
Linda和Jake只共同評分了一首歌曲：Chris Cagle的 What a Beautiful Day 得问。Linda打了3分，Jake打了5分软免，所以他們之間的曼哈頓距離為2宫纬，歐幾里得距離為：
所以不管是曼哈頓距離還是歐幾里得距離，Jake都要比Eric離Linda近膏萧，這不符合實際情況漓骚。
嘿，我想到一個辦法榛泛。人們給音樂打分是從1到5分蝌蹂，那些沒有打分的音樂就統(tǒng)一給0分好了，這樣就能解決數(shù)據(jù)稀疏的問題了曹锨！
想法不錯孤个，但是這樣做也不行。為了解釋這一問題沛简，我們再引入兩個人到例子里來：Cooper和Kelsey齐鲤。他們和Jake都有著非常相似的音樂偏好，其中Jake在我們網(wǎng)站上評價了25首歌曲椒楣。
Cooper評價了26首歌曲给郊，其中25首和Jake是一樣的。他們對每首歌曲的評價差值只有0.25捧灰！
Kelsey在我們網(wǎng)站上評價了150首歌曲淆九，其中25首和Jake相同。和Cooper一樣毛俏，她和Jake之間的評價差值也只有0.25炭庙！
所以我們從直覺上看Cooper和Keylsey離Jake的距離應(yīng)該相似。但是煌寇，當(dāng)我們計算他們之間的曼哈頓距離和歐幾里得距離時（代入0值）煤搜，會發(fā)現(xiàn)Cooper要比Keylsey離Jake近得多。
為什么呢唧席？
我們來看下面的數(shù)據(jù)：
從4擦盾、5、6這三首歌來看淌哟，兩人離Jake的距離是相同的迹卢，但計算出的曼哈頓距離卻不這么顯示：
問題就在于數(shù)據(jù)中的0值對結(jié)果的影響很大，所以用0代替空值的方法并不比原來的方程好徒仓。還有一種變通的方式是計算“平均值”——將兩人共同評價過的歌曲分?jǐn)?shù)除以歌曲數(shù)量腐碱。
總之，曼哈頓距離和歐幾里得距離在數(shù)據(jù)完整的情況下會運(yùn)作得非常好，如果數(shù)據(jù)比較稀疏症见，則要考慮使用余弦距離喂走。
古怪的現(xiàn)象
假設(shè)我們要為Amy推薦樂隊，她喜歡Phoenix谋作、Passion Pit芋肠、以及Vampire Weekend。和她最相似的用戶是Bob遵蚜，他也喜歡這三支樂隊帖池。他的父親為Walter Ostanek樂隊演奏手風(fēng)琴，所以受此影響吭净，他給了這支樂隊5星評價睡汹。按照我們現(xiàn)在的推薦邏輯，我們會將這支樂隊推薦給Amy寂殉，但有可能她并不喜歡囚巴。
或者試想一下，Billy Bob Olivera教授喜歡閱讀數(shù)據(jù)挖掘方面的書籍以及科幻小說友扰，他最鄰近的用戶是我彤叉，因為我也喜歡這兩種書。然而焕檬，我又是一個貴賓犬的愛好者，所以給《貴賓犬的隱秘生活》這本書打了很高的分澳泵。這樣一來实愚，現(xiàn)有的推薦方法會將這本書介紹給Olivera教授。
問題就在于我們只依靠最相似的 一個 用戶來做推薦兔辅，如果這個用戶有些特殊的偏好腊敲，就會直接反映在推薦內(nèi)容里。解決方法之一是找尋多個相似的用戶维苔，這里就要用到K最鄰近算法了碰辅。
K最鄰近算法
在協(xié)同過濾中可以使用K最鄰近算法來找出K個最相似的用戶，以此作為推薦的基礎(chǔ)介时。不同的應(yīng)用有不同的K值没宾，需要做一些實驗來得出。以下給到讀者一個基本的思路沸柔。
假設(shè)我要為Ann做推薦循衰，并令K=3。使用皮爾遜相關(guān)系數(shù)得到的結(jié)果是：
這三個人都會對推薦結(jié)果有所貢獻(xiàn)褐澎，問題在于我們?nèi)绾未_定他們的比重呢会钝？我們直接用相關(guān)系數(shù)的比重來描述，Sally的比重是0.8/2=40%工三，Eric是0.7/2=35%迁酸，Amanda則是25%：
假設(shè)他們?nèi)藢rey Wardens的評分以及加權(quán)后的結(jié)果如下：
最后計算得到的分?jǐn)?shù)為：
Python推薦模塊
我將本章學(xué)到的內(nèi)容都匯集成了一個Python類先鱼，雖然代碼有些長，我還是貼在了這里：
import codecs
from math import sqrt
users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0,
"Norah Jones": 4.5, "Phoenix": 5.0,
"Slightly Stoopid": 1.5,
"The Strokes": 2.5, "Vampire Weekend": 2.0},
"Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5,
"Deadmau5": 4.0, "Phoenix": 2.0,
"Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
"Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0,
"Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5,
"Slightly Stoopid": 1.0},
"Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0,
"Deadmau5": 4.5, "Phoenix": 3.0,
"Slightly Stoopid": 4.5, "The Strokes": 4.0,
"Vampire Weekend": 2.0},
"Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0,
"Norah Jones": 4.0, "The Strokes": 4.0,
"Vampire Weekend": 1.0},
"Jordyn": {"Broken Bells": 4.5, "Deadmau5": 4.0,
"Norah Jones": 5.0, "Phoenix": 5.0,
"Slightly Stoopid": 4.5, "The Strokes": 4.0,
"Vampire Weekend": 4.0},
"Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0,
"Norah Jones": 3.0, "Phoenix": 5.0,
"Slightly Stoopid": 4.0, "The Strokes": 5.0},
"Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0,
"Phoenix": 4.0, "Slightly Stoopid": 2.5,
"The Strokes": 3.0}
}
class recommender:
def __init__(self, data, k=1, metric='pearson', n=5):
""" 初始化推薦模塊
data 訓(xùn)練數(shù)據(jù)
k K鄰近算法中的值
metric 使用何種距離計算方式
n 推薦結(jié)果的數(shù)量
"""
self.k = k
self.n = n
self.username2id = {}
self.userid2name = {}
self.productid2name = {}
# 將距離計算方式保存下來
self.metric = metric
if self.metric == 'pearson':
self.fn = self.pearson
#
# 如果data是一個字典類型奸鬓，則保存下來焙畔，否則忽略
#
if type(data).__name__ == 'dict':
self.data = data
def convertProductID2name(self, id):
"""通過產(chǎn)品ID獲取名稱"""
if id in self.productid2name:
return self.productid2name[id]
else:
return id
def userRatings(self, id, n):
"""返回該用戶評分最高的物品"""
print ("Ratings for " + self.userid2name[id])
ratings = self.data[id]
print(len(ratings))
ratings = list(ratings.items())
ratings = [(self.convertProductID2name(k), v)
for (k, v) in ratings]
# 排序并返回結(jié)果
ratings.sort(key=lambda artistTuple: artistTuple[1],
reverse = True)
ratings = ratings[:n]
for rating in ratings:
print("%s\t%i" % (rating[0], rating[1]))
def loadBookDB(self, path=''):
"""加載BX數(shù)據(jù)集，path是數(shù)據(jù)文件位置"""
self.data = {}
i = 0
#
# 將書籍評分?jǐn)?shù)據(jù)放入self.data
#
f = codecs.open(path + "BX-Book-Ratings.csv", 'r', 'utf8')
for line in f:
i += 1
#separate line into fields
fields = line.split(';')
user = fields[0].strip('"')
book = fields[1].strip('"')
rating = int(fields[2].strip().strip('"'))
if user in self.data:
currentRatings = self.data[user]
else:
currentRatings = {}
currentRatings[book] = rating
self.data[user] = currentRatings
f.close()
#
# 將書籍信息存入self.productid2name
# 包括isbn號全蝶、書名闹蒜、作者等
#
f = codecs.open(path + "BX-Books.csv", 'r', 'utf8')
for line in f:
i += 1
#separate line into fields
fields = line.split(';')
isbn = fields[0].strip('"')
title = fields[1].strip('"')
author = fields[2].strip().strip('"')
title = title + ' by ' + author
self.productid2name[isbn] = title
f.close()
#
# 將用戶信息存入self.userid2name和self.username2id
#
f = codecs.open(path + "BX-Users.csv", 'r', 'utf8')
for line in f:
i += 1
#print(line)
#separate line into fields
fields = line.split(';')
userid = fields[0].strip('"')
location = fields[1].strip('"')
if len(fields) > 3:
age = fields[2].strip().strip('"')
else:
age = 'NULL'
if age != 'NULL':
value = location + ' (age: ' + age + ')'
else:
value = location
self.userid2name[userid] = value
self.username2id[location] = userid
f.close()
print(i)
def pearson(self, rating1, rating2):
sum_xy = 0
sum_x = 0
sum_y = 0
sum_x2 = 0
sum_y2 = 0
n = 0
for key in rating1:
if key in rating2:
n += 1
x = rating1[key]
y = rating2[key]
sum_xy += x * y
sum_x += x
sum_y += y
sum_x2 += pow(x, 2)
sum_y2 += pow(y, 2)
if n == 0:
return 0
# 計算分母
denominator = (sqrt(sum_x2 - pow(sum_x, 2) / n)
* sqrt(sum_y2 - pow(sum_y, 2) / n))
if denominator == 0:
return 0
else:
return (sum_xy - (sum_x * sum_y) / n) / denominator
def computeNearestNeighbor(self, username):
"""獲取鄰近用戶"""
distances = []
for instance in self.data:
if instance != username:
distance = self.fn(self.data[username],
self.data[instance])
distances.append((instance, distance))
# 按距離排序，距離近的排在前面
distances.sort(key=lambda artistTuple: artistTuple[1],
reverse=True)
return distances
def recommend(self, user):
"""返回推薦列表"""
recommendations = {}
# 首先抑淫，獲取鄰近用戶
nearest = self.computeNearestNeighbor(user)
#
# 獲取用戶評價過的商品
#
userRatings = self.data[user]
#
# 計算總距離
totalDistance = 0.0
for i in range(self.k):
totalDistance += nearest[i][1]
# 匯總K鄰近用戶的評分
for i in range(self.k):
# 計算餅圖的每個分片
weight = nearest[i][1] / totalDistance
# 獲取用戶名稱
name = nearest[i][0]
# 獲取用戶評分
neighborRatings = self.data[name]
# 獲得沒有評價過的商品
for artist in neighborRatings:
if not artist in userRatings:
if artist not in recommendations:
recommendations[artist] = (neighborRatings[artist]
* weight)
else:
recommendations[artist] = (recommendations[artist]
+ neighborRatings[artist]
* weight)
# 開始推薦
recommendations = list(recommendations.items())
recommendations = [(self.convertProductID2name(k), v)
for (k, v) in recommendations]
# 排序并返回
recommendations.sort(key=lambda artistTuple: artistTuple[1],
reverse = True)
# 返回前n個結(jié)果
return recommendations[:self.n]
運(yùn)行示例
首先構(gòu)建一個推薦類绷落，然后獲取推薦結(jié)果：
>>> r = recommender(users)
>>> r.recommend('Jordyn')
[('Blues Traveler', 5.0)]
>>> r.recommend('Hailey')
[('Phoenix', 5.0), ('Slightly Stoopid', 4.5)]
新的數(shù)據(jù)集
現(xiàn)在讓我們使用一個更為真實的數(shù)據(jù)集。Cai-Nicolas Zeigler從圖書漂流站收集了超過100萬條評價數(shù)據(jù)——278,858位用戶為271,379本書打了分始苇。這份數(shù)據(jù)（匿名）可以從這個地址獲得砌烁，有SQL和CSV兩種格式。由于特殊符號的關(guān)系催式，這些數(shù)據(jù)無法直接加載到Python里函喉。我做了一些清洗，可以從這里下載荣月。
CSV文件包含了三張表：
- 用戶表管呵，包括用戶ID、位置哺窄、年齡等信息捐下。其中用戶的姓名已經(jīng)隱去；
- 書籍表萌业，包括ISBN號坷襟、標(biāo)題、作者生年、出版日期婴程、出版社等；
- 評分表抱婉，包括用戶ID档叔、書籍ISBN號、以及評分（0-10分）蒸绩。
上文Python代碼中的loadBookDB方法可以加載這些數(shù)據(jù)蹲蒲，用法如下：
>>> r.loadBookDB('/Users/raz/Downloads/BX-Dump/')
1700018
>>> r.recommend('171118')
注意 由于數(shù)據(jù)集比較大，大約需要幾十秒的時間加載和查詢侵贵。
項目實踐
只有運(yùn)行調(diào)試過書中的代碼后才能真正掌握這些方法届搁，以下是一些實踐建議：
- 實現(xiàn)一個計算曼哈頓距離和歐幾里得距離的方法；
- 本書的網(wǎng)站上有一個包含25部電影評價的數(shù)據(jù)集，實現(xiàn)一個推薦算法卡睦。
