title: 經(jīng)典推薦算法之 Slope one
date: 2017/5/16 15:29:24
tags:
- 推薦系統(tǒng)
- Machine Learning
categories: 推薦系統(tǒng)
Slope One 是一系列應(yīng)用于協(xié)同過濾的算法的統(tǒng)稱换怖。由 Daniel Lemire和Anna Maclachlan于2005年發(fā)表的論文中提出放刨。 有爭議的是葵袭，該算法堪稱基于項(xiàng)目評價的non-trivial 協(xié)同過濾算法最簡潔的形式。該系列算法的簡潔特性使它們的實(shí)現(xiàn)簡單而高效个初，而且其精確度與其它復(fù)雜費(fèi)時的算法相比也不相上下乖寒。 該系列算法也被用來改進(jìn)其它算法。
協(xié)同過濾簡介及其主要優(yōu)缺點(diǎn)
協(xié)同過濾推薦（Collaborative Filtering recommendation）在信息過濾和信息系統(tǒng)中正迅速成為一項(xiàng)很受歡迎的技術(shù)院溺。與傳統(tǒng)的基于內(nèi)容過濾直接分析內(nèi)容進(jìn)行推薦不同宵统，協(xié)同過濾分析用戶興趣，在用戶群中找到指定用戶的相似（興趣）用戶，綜合這些相似用戶對某一信息的評價马澈，形成系統(tǒng)對該指定用戶對此信息的喜好程度預(yù)測。 與傳統(tǒng)文本過濾相比弄息，協(xié)同過濾有下列優(yōu)點(diǎn):
- 能夠過濾難以進(jìn)行機(jī)器自動基于內(nèi)容分析的信息。如藝術(shù)品摹量、音樂涤伐。
- 能夠基于一些復(fù)雜的，難以表達(dá)的概念（信息質(zhì)量缨称、品位)進(jìn)行過濾凝果。
- 推薦的新穎性。
盡管協(xié)同過濾技術(shù)在個性化推薦系統(tǒng)中獲得了極大的成功睦尽，但隨著站點(diǎn)結(jié)構(gòu)器净、內(nèi)容的復(fù)雜度和用戶人數(shù)的不斷增加，協(xié)同過濾技術(shù)的一些缺點(diǎn)逐漸暴露出來当凡。 主要有以下三點(diǎn): - 稀疏性(sparsity)：在許多推薦系統(tǒng)中山害，每個用戶涉及的信息量相當(dāng)有限，在一些大的系統(tǒng)如亞馬遜網(wǎng)站中沿量，用戶最多不過就評估了上百萬本書的1%~2%浪慌。造成評估矩陣數(shù)據(jù)相當(dāng)稀疏，難以找到相似用戶集朴则，導(dǎo)致推薦效果大大降低权纤。
- 擴(kuò)展性(scalability)：“最近鄰居”算法的計算量隨著用戶和項(xiàng)的增加而大大增加，對于上百萬之巨的數(shù)目乌妒，通常的算法將遭遇到嚴(yán)重的擴(kuò)展性問題汹想。
- 精確性(accuracy)：通過尋找相近用戶來產(chǎn)生推薦集，在數(shù)量較大的情況下芥被，推薦的可信度隨之降低欧宜。
Item-based協(xié)同過濾 和 過擬合
當(dāng)可以對一些項(xiàng)目評分的時候，比如人們可以對一些東西給出1到5星的評價的時候拴魄，協(xié)同過濾意圖基于一個個體過去對某些項(xiàng)目的評分和（龐大的）由其他用戶的評價構(gòu)成的數(shù)據(jù)庫冗茸，來預(yù)測該用戶對未評價項(xiàng)目的評分。 例如: 如果一個人給披頭士的評分為5（總分5）的話匹中，我們能否預(yù)測他對席琳狄翁新專輯的評分呢夏漱？
這種情形下, item-based 協(xié)同過濾系統(tǒng)根據(jù)其它項(xiàng)目的評分來預(yù)測某項(xiàng)目的分值，一般方法為 線性回歸 (
另外一種更好的方法是使用更簡單一些的式子践付，比如
實(shí)驗(yàn)證明當(dāng)使用一半的回歸量的時候秦士，該式子（稱為Slope One）的表現(xiàn)有時優(yōu)于線性回歸方程。該簡化方法也不需要那么多存儲空間和延遲永高。
Item-based 協(xié)同過濾只是協(xié)同過濾的一種形式.其它還有像 user-based 協(xié)同過濾一樣研究用戶間的聯(lián)系的過濾系統(tǒng)隧土。但是，考慮到其他用戶數(shù)量龐大命爬，item-based協(xié)同過濾更可行一些曹傀。
電子商務(wù)中的Item-based協(xié)同過濾
人們并不總是能給出評分，當(dāng)用戶只提供二進(jìn)制數(shù)據(jù)（購買與否）的時候饲宛，就無法應(yīng)用Slope One 和其它基于評分的算法皆愉。 二進(jìn)制 item-based協(xié)同過濾應(yīng)用的例子之一就是Amazon的 item-to-item 專利算法，該算法中用二進(jìn)制向量表示用戶-項(xiàng)目購買關(guān)系的矩陣落萎，并計算二進(jìn)制向量間的cosine相關(guān)系數(shù)亥啦。
有人認(rèn)為Item-to-Item 算法甚至比Slope One 還簡單，例如：
在本例當(dāng)中练链，項(xiàng)目1和項(xiàng)目2間的cosine相關(guān)系數(shù)為：
項(xiàng)目1和項(xiàng)目3間的cosine相關(guān)系數(shù)為：
而項(xiàng)目2和項(xiàng)目3的cosine相關(guān)系數(shù)為：
于是翔脱，瀏覽項(xiàng)目1的顧客會被推薦買項(xiàng)目3(兩者相關(guān)系數(shù)最大),而瀏覽項(xiàng)目2的顧客會被推薦買項(xiàng)目3,瀏覽了項(xiàng)目3的會首先被推薦買項(xiàng)目1（再然后是項(xiàng)目2,因?yàn)?和3的相關(guān)系數(shù)小于1和3）。該模型只使用了每對項(xiàng)目間的一個參數(shù)（cosine相關(guān)系數(shù)）來產(chǎn)生推薦媒鼓。因此届吁，如果有n個項(xiàng)目，則需要計算和存儲 n（n-1）/2 個cosine相關(guān)系數(shù)绿鸣。
Slope One 協(xié)同過濾
為了大大減少過適(過擬合)的發(fā)生疚沐，提升算法簡化實(shí)現(xiàn)， Slope One 系列易實(shí)現(xiàn)的Item-based協(xié)同過濾算法被提了出來潮模。本質(zhì)上亮蛔，該方法運(yùn)用更簡單形式的回歸表達(dá)式
例:
- User A 對 Item I 評分為1 對Item J.評分為1.5
- User B 對 Item I 評分為2.
- 你認(rèn)為 User B 會給 Item J 打幾分?
- Slope One 的答案是：2.5 (1.5-1+2=2.5).
舉個更實(shí)際的例子，考慮下表：
在本例中厘惦，項(xiàng)目2和1之間的平均評分差值為 (2+(-1))/2=0.5. 因此偷仿，item1的評分平均比item2高0.5。同樣的，項(xiàng)目3和1之間的平均評分差值為3酝静。因此节榜，如果我們試圖根據(jù)Lucy 對項(xiàng)目2的評分來預(yù)測她對項(xiàng)目1的評分的時候，我們可以得到 2+0.5 = 2.5别智。同樣全跨，如果我們想要根據(jù)她對項(xiàng)目3的評分來預(yù)測她對項(xiàng)目1的評分的話，我們得到 5+3=8.
如果一個用戶已經(jīng)評價了一些項(xiàng)目亿遂，可以這樣做出預(yù)測：簡單地把各個項(xiàng)目的預(yù)測通過加權(quán)平均值結(jié)合起來。當(dāng)用戶兩個項(xiàng)目都評價過的時候渺杉，權(quán)值就高蛇数。在上面的例子中，項(xiàng)目1和項(xiàng)目2都評價了的用戶數(shù)為2,項(xiàng)目1和項(xiàng)目3 都評價了的用戶數(shù)為1,因此權(quán)重分別為2和1. 我們可以這樣預(yù)測Lucy對項(xiàng)目1的評價：
于是是越，對“n”個項(xiàng)目耳舅，想要實(shí)現(xiàn) Slope One，只需要計算并存儲“n”對評分間的平均差值和評價數(shù)目即可倚评。
步驟
計算物品之間的評分差的均值浦徊，記為物品間的評分偏差(兩物品同時被評分)
根據(jù)物品間的評分偏差和用戶的歷史評分，預(yù)測用戶對未評分的物品的評分天梧。
將預(yù)測評分排序盔性，取topN對應(yīng)的物品推薦給用戶。
舉例
假設(shè)有100個人對物品A和物品B打分了呢岗，R(AB)表示這100個人對A和B打分的平均偏差;有1000個人對物品B和物品C打分了冕香， R(CB)表示這1000個人對C和B打分的平均偏差；
應(yīng)用Slope One的推薦系統(tǒng)
● hitflip DVD推薦系統(tǒng)
● How Happy
● inDiscover MP3推薦系統(tǒng)
● RACOFI Composer
● Value Investing News 股票新聞網(wǎng)站
● AllTheBests 購物推薦引擎
Python 實(shí)現(xiàn)
def loadData():
items={'A':{1:5,2:3},
'B':{1:3,2:4,3:2},
'C':{1:2,3:5}}
users={1:{'A':5,'B':3,'C':2},
2:{'A':3,'B':4},
3:{'B':2,'C':5}}
return items,users
#***計算物品之間的評分差
#items:從物品角度后豫，考慮評分
#users:從用戶角度悉尾，考慮評分
def buildAverageDiffs(items,users,averages):
#遍歷每條物品-用戶評分?jǐn)?shù)據(jù)
for itemId in items:
for otherItemId in items:
average=0.0 #物品間的評分偏差均值
userRatingPairCount=0 #兩件物品均評過分的用戶數(shù)
if itemId!=otherItemId: #若無不同的物品項(xiàng)
for userId in users: #遍歷用戶-物品評分?jǐn)?shù)
userRatings=users[userId] #每條數(shù)據(jù)為用戶對物品的評分
#當(dāng)前物品項(xiàng)在用戶的評分?jǐn)?shù)據(jù)中，且用戶也對其他物品由評分
if itemId in userRatings and otherItemId in userRatings:
#兩件物品均評過分的用戶數(shù)加1
userRatingPairCount+=1
#評分偏差為每項(xiàng)當(dāng)前物品評分-其他物品評分求和
average+=(userRatings[otherItemId]-userRatings[itemId])
averages[(itemId,otherItemId)]=average/userRatingPairCount
#***預(yù)測評分
#users:用戶對物品的評分?jǐn)?shù)據(jù)
#items：物品由哪些用戶評分的數(shù)據(jù)
#averages：計算的評分偏差
#targetUserId：被推薦的用戶
#targetItemId：被推薦的物品
def suggestedRating(users,items,averages,targetUserId,targetItemId):
runningRatingCount=0 #預(yù)測評分的分母
weightedRatingTotal=0.0 #分子
for i in users[targetUserId]:
#物品i和物品targetItemId共同評分的用戶數(shù)
ratingCount=userWhoRatedBoth(users,i,targetItemId)
#分子
weightedRatingTotal+=(users[targetUserId][i]-averages[(targetItemId,i)])\
*ratingCount
#分母
runningRatingCount+=ratingCount
#返回預(yù)測評分
return weightedRatingTotal/runningRatingCount
# 物品itemId1與itemId2共同有多少用戶評分
def userWhoRatedBoth(users,itemId1,itemId2):
count=0
#用戶-物品評分?jǐn)?shù)據(jù)
for userId in users:
#用戶對物品itemId1與itemId2都評過分則計數(shù)加1
if itemId1 in users[userId] and itemId2 in users[userId]:
count+=1
return count
if __name__=='__main__':
items,users=loadData()
averages={}
#計算物品之間的評分差
buildAverageDiffs(items,users,averages)
#預(yù)測評分:用戶2對物品C的評分
predictRating=suggestedRating(users,items,averages,2,'C')
print 'Guess the user will rate the score :',predictRating
結(jié)果：用戶2對物品C的預(yù)測分值為
Guess the user will rate the score : 3.33333333333
Slop one 增量更新
主要方法在于根據(jù)新的評分項(xiàng)挫酿，更新偏差表與共同評分項(xiàng)個數(shù)
維基百科
推薦算法之 slope one 算法
黃明波. 基于Slope One算法的增量音樂推薦系統(tǒng)的設(shè)計與實(shí)現(xiàn)[D].重慶大學(xué),2016
