在本章中你將學到：
- 推薦系統是如何工作的？
- 社會化過濾是如何工作的？
- 如何計算物品之間的相似度？
- 曼哈頓距離，歐式距離和閔科夫斯基距離
- 皮爾森相關度
- 余弦相似度
- 實現Python版本的KNN算法
- 附加的數據集
面向程序員的數據挖掘指南: 第二章 從推薦系統開始
作者：佚名
我們將通過對推薦系統的研究來開始數據挖掘的探索之旅。如今推薦系統無處不在。
2.1 我喜歡你喜歡的
我們將通過對推薦系統的研究來開始數據挖掘的探索之旅。如今推薦系統無處不在——從Amazon到last.fm的音樂和演唱會推薦：
在上面的Amazon的例子中，Amazon融合了兩種的信息來進行推薦。***個是我看過的Gene Reeves翻譯的《The Lotus Sutra》；第二個是看過《The Lotus Sutra》翻譯版的人看還過其他的幾個翻譯。
在這章中，我們介紹的推薦方法叫協同過濾。之所以稱為協同，是因為它產生的 推薦是基于其他人的結果——在效果上，其實就是人們一起協作而提出推薦。它是這么工作的：假設我的任務是給你推薦一本書，我在這個網站上搜索跟你在讀書方 面有相似偏好的用戶。一旦發現這樣的用戶我就可以把她喜歡的書推薦給你——有可能是Paolo Bacigalupi的《The Windup Girl》。
2.2 如何找到那些跟你相似的人
因此***步便是那些跟你相似的人。這里有一個簡單的二維空間示例，假設用戶在5***評分系統中對書進行打分——0星意味著這本書很差，5星則是非常 好。因為我們是在簡單二維條件下，我們把評分限制在這兩本書：Neal Stephenson的《Snow Crash》和Steig Larsson的《The Girl with the Dragon Tattoo》。
首先，下列表格列出了三個用戶對這兩本書的評分：
我想要給神秘的X女士推薦一本書，她給《Snow Crash》評了4星，同時給《The Girl with the Dragon Tattoo》評了2星。***個任務是找到與X女士最相似、或者最相近的人。我通過計算距離來實現。
曼哈頓距離
最容易的計算距離的方法叫曼哈頓距離或者出租車距離。在2D的例子中，每個人用點（x, y）來表示。我將為每個x和y添加下標用于標示不同的人，因此（x1, y1）可能是Amy，（x2, y2）可能是難以捉摸的X女士。曼哈頓距離的計算如下：
|x1 - x2| + |y1 - y2|
（即x的差的絕對值加上y的差的絕對值）。所以Amy和X女士的曼哈頓距離是4：
計算出X女士與所有三個人的距離如下：
Amy是最相近的匹配。我們查看她的歷史評分，例如，她給Paolo Bacigalupi的《The Windup Girl》評了5星，我們就可以把這本書推薦給X女士。
#p#
歐式距離
曼哈頓距離的一個優點是計算速度快。如果我們想從Facebook上的一百萬用戶中找出與來自Kalamazoo小Danny最相似的人，速度快是優勢。
勾股定理
你可能從以前的學習中想起勾股定理，這里，我們用直線距離代替曼哈頓距離來計算Amy與X女士的距離（原本是4），直線距離如圖所示：
勾股定理告訴我們如何來計算這種直線距離。
直線c表示的距離稱為歐式距離，公式如下：
回顧一下，x1，x2分別表示用戶1和用戶2對《Dragon Tattoo》的喜好；y1，y2表示是用戶1和用戶2對《Snow Crash》的喜好。
Amy對《Snow Crash》和《Dragon Tattoo》都評了5分；而X女士給《Dragon Tattoo》評了2分，對《Snow Crash》評了4分。因此這兩人之間的歐氏距離為：
計算X女士和所有人的歐式距離如下：
擴展到N維
我們從一開始的兩本書擴展到更復雜一點的情形。假設我們在一家提供在線音樂服務的公司工作，我們想通過樂隊推薦系統來獲得更好的用戶體驗。用戶可以 在我們的1-5星系統中為樂隊評分，他們可以給出半顆星的評分（比如，你可以給一個樂隊評2.5星）。下面的圖表展示了8個用戶對8個樂隊的評分：
表格里的連字符"-"表示對應的用戶沒有給相應的樂隊評分。現在我們需要通過用戶對共同的樂隊的打分來計算他們之間的距離。比如，當我們在計算 Angelica和Bill之間的距離時，用到樂隊有Blues Traveler , Broken Bells , Phoenix, Slightly Stoopid, and Vampire Weekend。所以計算的曼哈頓距離如下：
對于行"Manhattan Distance", ***一列只需要將列"Difference"求和即可:
(1.5+1.5+3+2+1) = 9計算歐式距離的過程類似，我們只用到他們共同評過分的那些樂隊：
更詳細的計算如下：
動手試試
題目1：計算上表中Hailey和Veronica的歐式距離?
題目2：計算上表中Hailey和Jordyn的歐式距離？
答案:
題目1：
題目2：
一個不足
當在使用這些距離的時候我們發現它存在一個不足：當我們計算Hailey和 Veronica之間的距離的時候，我們發現他們只共同給兩個樂隊(Norah Jones 和 The Strokes)評了分；但是，當我們計算Hailey 和 Jordyn的距離時，我們發現他們共同給5個樂隊評了分。這樣看起來似乎使得我們的距離度量方法出現偏斜，因為Hailey和 Veronica的距離是二維空間上計算的，而Hailey 和 Jordyn的距離是在五維空間。當沒有缺失值的情況下，曼哈頓距離和歐氏距離都表現很好。處理空值在學術上是一個熱門的研究方向。在本書的后面章節我們 將討論如何來處理這個問題。現在我們只要意識到這一缺陷即可，我們還得繼續我們的"***探索" —— 構建推薦系統。
推廣/泛化
曼哈頓距離和歐式距離更一般的形式是閔可夫斯基距離(Minkowski Distance):
當:
- r = 1時，上式即為曼哈頓距離
- r = 2時，上式即為歐式距離
- r = 無窮大時，上式為確界距離
很多時候你會發現公式其實并不難理解。現在讓我們來剖析它。當r=1，公式就簡化成曼哈頓距離：
依然以貫穿本章的音樂為例，x和y代表兩個人，d(x,y)表示他們之間的距離。n是x，y都評過分的樂隊的數量。我們在前面已經做過計算：
列"Difference"代表評分差值的絕對值，這些絕對值加起來得到9。
當r=2，我們得到歐氏距離的公式：
需要注意的是：當r值越大，單個維度中，大的difference值對整體的difference值影響越大。
使用Python表示這些數據
Python中表示上述數據的方式很多，在這里我將用Python中的字典表示（也叫做散列表或者哈希表）
- 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}
- }
我們通過如下方式得到某個特定用戶的評分：
- >>> users["Veronica"]
- {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
計算曼哈頓距離的代碼
計算曼哈頓距離的代碼如下：
- def manhattan(rating1, rating2):
- """Computes the Manhattan distance. Both rating1 and rating2 are dictionaries
- of the form {'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
接下來構建一個函數找到最相似的那個人（其實它會返回一個按距離排序好的列表，最相似的人在列表的***個）：
- def computeNearestNeighbor(username, users):
- """creates a sorted list of users based on their distance to username"""
- distances = []
- for user in users:
- if user != username:
- distance = manhattan(users[user], users[username])
- distances.append((distance, user))
- # sort based on distance -- closest first
- 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')]
***，我們將把這些代碼整合在一起成為一個完整的推薦系統。比如我想為Hailey生成推薦結果，我會找到跟他最相似的鄰居——在本例中是 Veronica。接著我會找出Veronica打過分但是Hailey沒有打過分的樂隊，我們會假設Hailey會對該樂隊的評分和Veronica對 該樂隊的評分相同(至少是相似)。比如，Hailey沒有給Phoenix評分，Veronica給Phoenix評了4分，所以我們將猜想Hailey 很有可能也喜歡這個樂隊。下面是生成推薦結果的函數。
- def recommend(username, users):
- """Give list of recommendations"""
- # first find nearest neighbor
- nearest = computeNearestNeighbor(username, users)[0][24]
- recommendations = []
- # now find bands neighbor rated that user didn't
- neighborRatings = users[nearest]
- userRatings = users[username]
- for artist in neighborRatings:
- if not artist in userRatings:
- recommendations.append((artist, neighborRatings[artist]))
- # using the fn sorted for variety - sort is more efficient
- 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)]
這跟我們的期望相符。正如我們上面所示，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來說，返回的空值意味著我們無法對她進行推薦。我們看看問題出在哪里：
- >>> 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，他們的評分表如下：
我們看到Veronica評過的所有樂隊Angelica也都有評過分。我們沒有更新的評分的樂隊了，因此就沒有推薦結果。
我們將提出方法來改善該系統來避免這種情況的出現。
課后作業
- 實現閔可夫斯基距離函數
- 改變computeNearestNeighbor，使用閔可夫斯基作為距離計算函數。
埋怨用戶
讓我們看看用戶評分的細節。我們可以看出當用戶對樂隊進行打分的時候，其打分行為差別很大：
Bill不喜歡走極端，他的評分都在2星到4星之間。Jordyn看起來喜歡所有的東西，他的評分都在4星到5星之間。Hailey的評分很極端，給出的不是1星就是4星.
這種情況下，我們應該如何比較用戶，比如Hailey和Jordan？Hailey的4分相當于Jordyn的4分還是5分？我想應該是更像5分，這種差異會給推薦系統帶來新的問題。
皮爾森相關系數
有一種解決此類問題的方法是使用皮爾森相關系數。首先，從一般性出發，考慮下面的數據(和前面用的數據不同)：
這個例子在數據挖掘領域被稱為“分數通脹”。Clara的***評分是4——她的所有評分都在4到5之間。如果我們將上表中的評分用圖表示：
事實上這條直線暗示著Clara和Robert之間是興趣是高度一致的。他們都覺得Phoenix是***的樂隊，其次是Blues Traveler，接著是Norah Jones。
還不錯的的一致性：
不是太好的一致性：
因此從圖表中可以看出：一條直線表示高度相關。皮爾森相關系數是一種度量兩個變量相關性的方法（在這個例子中，Ckara和Robert的相關 性）。它的取值范圍在-1到1之間。1表明完全相關，-1表明完全負相關。一個比較直觀的感覺：上圖中，直線的皮爾森系數是1，我標著“還不錯的的一致 性”皮爾森系數有0.91，“不是太好的一致性”的系數則為0.81，所以我們可以用這個去發現與我們興趣最相似的人。
皮爾森相關系數的公式是：
除了看起來復雜，這個公式的另外一個問題是需要對數據進行多輪運算。慶幸的是，對我們做算法的人來說，該公式有另外一個近似的形式：
（記住我兩段前說過的，不要跳過公式）這個公式，除了一看是看上去更加復雜，更重要的是，數值的不穩定性意味著小的誤差可能會被近似后的公式放大。 但是這個變形有一個***的好處是我們可以通過對數據一輪的遍歷就能實現它。首先，我們來剖析這個公式，并結合前幾頁講到的例子：
我們先計算：
這是相似度計算公式分子的***部分，這里的x和y分別代表著Clara和Robert。
對于每一個樂隊，我們把Clara和Robert的分數相乘，然后求和：
接著我們計算分子的另外一部分:
因此:
等于Clara所有評分的和，即22.5. 對于Robert，其評分的和為15，他們總共對5個樂隊評分，即：
因此前文中的公式的分子為70 - 67.5=2.5.
現在我們開始計算分母：
首先：
前面我們已經計算過Clara的評分之和等于22.5，平方以后得506.25。然后除以共同評分的樂隊數5，得到101.25。把以上結果整合到一起得到：
接著，按照同樣的方法計算Robert：
把所以的計算整合到一起得到***的結果：
因此1意味著Clara和Robert是完全相關的。
課后作業
在進行下面的計算之前，我們先使用Python實現一下Pearson相似度算法：
- 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 += x**2
- sum_y2 += y**2
- # now compute denominator
- denominator = sqrt(sum_x2 - (sum_x**2) / n) * sqrt(sum_y2 -(sum_y**2) / n)
- if denominator == 0:
- return 0
- else:
- return (sum_xy - (sum_x * sum_y) / n) / denominator
***一個公式 —— 余弦相似度
我接著講***一個公式——余弦相似度，它在文本挖掘中非常流行，同時在協同過濾中也被廣泛采用。要知道我們什么時候會用到這個公式，我們先把我們的例子做一些小小的改
變。我們記錄下每個人播放某首歌曲的次數，并且以此信息來作為我們推薦算法的基礎信息。
肉眼觀察上面的圖表（或者用上面講到的距離公式），在聽音樂的習慣上，Ann要比Ben更像Sally。
問題出現哪里？
我是我iTunes中差不多有四千首歌曲，這里是播放量排名靠前的一些歌曲：
所以我的排名***的是Marcus Miller的Moonlight Sonata，總共播放25次，你有可能一次也沒聽過這首歌。實際上，很有可能這些排名靠前的歌曲你一首也沒聽過。此外，iTunes上面有超過1千5百 萬首歌曲，我只有4000首。所以對某個人來說，他的數據是稀疏的，因為他只聽了所有歌曲中極少的部分，每個人的播放數據是極度稀疏的。當我們在1千5百 萬首歌曲里面對比兩個人的音樂播放次數時，基本上他們都共同的播放的歌曲數為0。但是，當我們計算相似性的時候沒法使到這種共享為0次的播放。
另外一個類似的情形是使用詞計算文本之間的相似度。假設我們都喜歡一本書，比如Carey Rockwell的Tom Corbett Space Cadet：The Space Pioneers，我們想要找到類似的書本。其中一種可能的方法是使用詞頻。屬性是某個詞，屬性的值是該詞在書本中出現的頻率。所以《The Space Pioneers 》中6.13%的詞是the，0.89%是Tom，0.25%是space。我可以用這些詞匯頻率來計算這本書與其他書的相似度。但是，數據稀疏性問題在 這里出現了，這本書中總共有6629個不重復的詞匯，而英文中有超過一百萬個英文單詞。所以如果我們的屬性是英語單詞，在《The Space Pioneers》中或者其他書本中將會有相對少的非零屬性值。問題再次出現，任何相似性度量不應該依賴共有的零值。
余弦相似度忽略了0與0的匹配，其定義如下：
其中"."表示向量x和向量y的內積，"||x||"表示向量x的長度，即：
用一個例子來表示:
兩個向量為：
x=(4.75, 4.5, 5, 4.25, 4) y=(4, 3, 5, 2, 1)因此：
內積為：
x⋅y = (4.75 × 4)+ (4.5 × 3)+ (5 × 5)+ (4.25 × 2)+ (4 ×1) = 70因此，余弦相似度為：
余弦相似度中，1表示完全正相關，-1表示完全負相關，因此0.935表示正相關性很高。
練習:
計算Angelica和Veronica的余弦相似度。
責任編輯：陳四芳
來源：
圖靈社區
