協同過濾算法

jopen 9年前發布 | 15K 次閱讀算法
協作型過濾

協同過濾是利用集體智慧的一個典型方法。要理解什么是協同過濾 (Collaborative Filtering, 簡稱CF)，首先想一個簡單的問題，如果你現在想看個電影，但你不知道具體看哪部，你會怎么做？大部分的人會問問周圍的朋友，看看最近有什么好看的電影推薦，而我們一般更傾向于從口味比較類似的朋友那里得到推薦。這就是協同過濾的核心思想。
協同過濾一般是在海量的用戶中發掘出一小部分和你品位比較類似的，在協同過濾中，這些用戶成為鄰居，然后根據他們喜歡的其他東西組織成一個排序的目錄推薦給你。
要實現協同過濾，需要以下幾個步驟：
搜集偏好
</li>
尋找相近用戶
</li>
推薦物品
</li> </ul> </div>
搜集偏好

首先，我們要尋找一種表達不同人及其偏好的方法。這里我們用python的嵌套字典來實現。
在本章中所用的數據，是從國外的網站 grouplens 下載的 u.data 。該數據總共四列，共分為用戶ID、電影ID、用戶評分、時間。我們只需根據前三列，生成相應的用戶偏好字典。
#生成用戶偏好字典
def make_data():
    result={}
    f = open('data/u.data', 'r')
    lines = f.readlines()
    for line in lines:

    #按行分割數據
    (userId , itemId , score,time ) = line.strip().split("\t")
    #字典要提前定義
    if not result.has_key( userId ):
        result[userId]={}
    #注意float,不然后續的運算存在類型問題
    result[userId][itemId] = float(score)
return result</pre> <p>另外如果想在字典中顯示展現電影名，方便分析，也可以根據 <a href="/misc/goto?guid=4959647125463645741">u.item</a> 中電影數據，預先生成電影的數據集。 </p>

#將id替換為電影名 構造數據集
def loadMovieLens(path='data'):

# Get movie titles
movies={}
for line in open(path+'/u.item'):
    (id,title)=line.split('|')[0:2]
    movies[id]=title
# Load data
prefs={}
for line in open(path+'/u.data'):
    (user,movieid,rating,ts)=line.split('\t')
    prefs.setdefault(user,{})
    prefs[user][movies[movieid]]=float(rating)
return prefs</pre> <p>根據上面兩個函數中的一種，到此我們的用戶數據集已經構造好了，由于數據量不是非常大，暫時放在內存中即可。由于以上數據集比較抽象，不方便講解，至此我們定義一個簡單的數據集來講解一些例子，一個簡單的嵌套字典： </p>

#用戶：{電影名稱：評分}
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}, 
    'Michael Phillips':{'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,'Superman Returns': 3.5, 'The Night Listener': 4.0},
    'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,'The Night Listener': 4.5, 'Superman Returns': 4.0,'You, Me and Dupree': 2.5},
    'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 2.0}, 
    'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
    'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns':4.0}
}
 尋找相近用戶 

收集完用戶信息后，我們通過一些方法來確定兩個用戶之間品味的相似程度，計算他們的 相似度評價值 。有很多方法可以計算，我們在此介紹兩套常見的方法：歐幾里得距離和皮爾遜相關度。 

歐幾里得距離 

歐幾里得距離（euclidea nmetric）（也稱歐式距離）是一個通常采用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。 


數學定義： 

已知兩點 A = (x_1,x_2,...,x_n)和 B = (y_1,y_2,...,y_n)，則兩點間距離： 

$$|AB|=\sqrt{(x_1 - x_2)^2+(y_1 - y_2)^2+...+(x_n-y_n)^2}$$ 

接下來我們只要把數據集映射為坐標系就可以明顯的比較出相似度，以"Snakes on a Plane"和"You, Me and Dupree"兩部電影距離，有坐標系如下圖： 
 </div>
計算上圖中Toby和Mick LaSalle的相似度： 



from math import sqrt 

sqrt(pow( 4.5-4 , 2 ) + pow( 1 - 2 , 2)) 

1.118033988749895 
</div>
</div>
上面的式子計算出了實際距離值，但在實際應用中，我們希望相似度越大返回的值越大，并且控制在0~1之間的值。為此，我們可以取函數值加1的倒數(加1是為了防止除0的情況)： 


1/(1+sqrt(pow( 4.5-4 , 2 ) + pow( 1 - 2 , 2)))0.4721359549995794 
</div>
接下來我們就可以封裝一個基于歐幾里得距離的相似度評價，具體python實現如下： 

#歐幾里得距離
def sim_distance( prefs,person1,person2 ):
    si={}
    for itemId in prefs[person1]:
        if itemId in prefs[person2]:
            si[itemId] = 1

#no same item
if len(si)==0: return 0
sum_of_squares = 0.0    
#計算距離 
sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) for item in si])
return 1/(1 + sqrt(sum_of_squares) )</pre> <p>基于測試數據集critics，則可以計算兩個人的相似度值為： </p>


sim_distance( critics , 'Toby', 'Mick LaSalle' )0.307692307692 
</div>
皮爾遜相關度 

皮爾遜相關系數是一種度量兩個變量間相關程度的方法。它是一個介于 1 和 -1 之間的值，其中，1 表示變量完全正相關， 0 表示無關，-1 表示完全負相關。 


數學公式 ： 

$$\frac{\sum x_iy_i-\frac{\sum x_i\sum y_i}{n}}{\sqrt{\sum x_i^2-\frac{(\sum x_i)^2}{n}}\sqrt{\sum y_i^2-\frac{(\sum y_i)^2}{n}}}$$ 
</div>

與歐幾里得距離不同，我們根據兩個用戶來建立笛卡爾坐標系，根據用戶對相同電影的評分來建立點，如下圖： 
 在圖上，我們還可以看到一條線，因其繪制的原則是盡可能的接近圖上所有點，故該線也稱為 最佳擬合線 。用皮爾遜方法進行評價時，可以修正“ 夸大值 ”部分，例如某人對電影的要求更為嚴格，給出分數總是偏低。 
</div>
python代碼實現： 

#皮爾遜相關度 
def sim_pearson(prefs,p1,p2):
    si={}
    for item in prefs[p1]: 
      if item in prefs[p2]: si[item]=1
    if len(si)==0: return 0
    n=len(si)

#計算開始
sum1=sum([prefs[p1][it] for it in si])
sum2=sum([prefs[p2][it] for it in si])
sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
sum2Sq=sum([pow(prefs[p2][it],2) for it in si])   
pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
num=pSum-(sum1*sum2/n)
den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
#計算結束
if den==0: return 0
r=num/den
return r</pre> <p>最后根據critics的數據計算Gene Seymour和Lisa Rose的相關度： </p>


recommendations.sim_pearson(recommendations.critics,'Gene Seymour','Lisa Rose') 
</div>
為評論者打分 

到此，我們就可以根據計算出用戶之間的相關度，并根據相關度來生成相關度列表，找出與用戶口味相同的其他用戶。 

#推薦用戶
def topMatches(prefs,person,n=5,similarity=sim_distance):

#python列表推導式
scores=[(similarity(prefs,person,other),other) for other in prefs if other!=person]
scores.sort()
scores.reverse()
return scores[0:n]</pre> <h3>推薦物品 </h3>


對于用戶來說，找出與他具有相似愛好的人并不重要，主要是為他推薦他可能喜歡的物品，所以我們還需要根據用戶間相似度進一步計算。例如為Toby推薦，由于數據不多，我們取得所有推薦者的相似度，再乘以他們對電影的評價，得出該電影對于Toby的推薦值，也可以認為是Toby可能為電影打的分數。如下圖： 
 我們通過計算其他用戶對某個Toby沒看過電影的加權和來得到總權重，最后除以相似度和，是為了防止某一電影被看過的多，總和會更多的影響，也稱“ 歸一化 ”處理。 
</div>
#基于用戶推薦物品
def getRecommendations(prefs,person,similarity=sim_pearson):
    totals={}
    simSums={}
    for other in prefs:

    #不和自己做比較
    if other == person: 
        continue
    sim = similarity( prefs,person,other )
    #去除負相關的用戶
    if sim<=0: continue
    for item in prefs[other]:
        #只對自己沒看過的電影做評價
        if item in prefs[person]:continue
        totals.setdefault( item ,0 )
        totals[item] += sim*prefs[other][item]
        simSums.setdefault(item,0)
        simSums[item] += sim
#歸一化處理生成推薦列表
rankings=[(totals[item]/simSums[item],item) for item in totals]
#rankings=[(total/simSums[item],item) for item,total in totals.items()]
rankings.sort()
rankings.reverse()
return rankings</pre> <h3>基于物品的協同過濾 </h3>

以上所講的都是基于用戶間相似的推薦，下面我們看看基于物品的推薦。 

同樣，先構造數據集，即以物品為key的字典，格式為{電影:{用戶:評分,用戶:評分}} 

#基于物品的列表
def transformPrefs(prefs):
    itemList ={}
    for person in prefs:
        for item in prefs[person]:
            if not itemList.has_key( item ):
                itemList[item]={}

            #result.setdefault(item,{})
        itemList[item][person]=prefs[person][item]
return itemList</pre> <p>計算物品間的相似度，物品間相似的變化不會像人那么頻繁，所以我們可以構造物品間相似的集合，存成文件重復利用： </p>

#構建基于物品相似度數據集
def calculateSimilarItems(prefs,n=10):
    result={}
    itemPrefs=transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        c += 1
        if c%10==0: print "%d / %d" % (c,len(itemPrefs))
        scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
        result[item]=scores
    return result
 
基于物品的推薦值計算，通過Toby已看影片的評分，乘以未看影片之間的相似度，來獲取權重。最后歸一化處理如下圖： 
 </div>
#基于物品的推薦
def getRecommendedItems(prefs,itemMatch,user):
    userRatings=prefs[user]
    scores={}
    totalSim={}
Loop over items rated by this user

for (item,rating) in userRatings.items( ):
  # Loop over items similar to this one
  for (similarity,item2) in itemMatch[item]:
# Ignore if this user has already rated this item
if item2 in userRatings: continue
# Weighted sum of rating times similarity
scores.setdefault(item2,0)
scores[item2]+=similarity*rating
# Sum of all the similarities
totalSim.setdefault(item2,0)
totalSim[item2]+=similarity

Divide each total score by total weighting to get an average

rankings=[(score/totalSim[item],item) for item,score in scores.items( )]

Return the rankings from highest to lowest

rankings.sort( )
rankings.reverse( )
return rankings</pre> <p><a href="/misc/goto?guid=4959647125623561067">源碼</a> </p>

思考 



UserCF和ItemCF的比較 


歸一化處理的更合適方法 


與頻繁模式挖掘的區別



原文  http://segmentfault.com/a/1190000004022134 


                    
                    
                         本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
                         轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
                         本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
                         本文地址：http://www.baiduhome.net/lib/view/open1448085556666.html
                         算法
                    

                
                
                    
                        相關經驗
                        
  協同過濾算法
   基于用戶的協同過濾算法
   基于用戶的協同過濾推薦算法
   基于綜合興趣度的協同過濾推薦算法
   Python 基于協同過濾的推薦
                         
                    
                    
                        相關資訊
                        
  用Go開發協同工具Qortex
   Myriad項目: Mesos和YARN 協同工作
   最懂您的協同管理工具——然之協同發布2.0版本!
   PHP的HTML內容過濾，htmLawed 1.1.12 發布
   Ubuntu 12.04將加入seccomp過濾器
                         
                    
                    
                        相關文檔
                        
   基于物品的協同過濾
    協同過濾--理論研究
    GPS漂移過濾算法
    基于協同過濾的商品推薦引擎
    基于生物序列模式提取技術的郵件過濾算法
    微宏協同項目管理
                         
                    

                    目錄