摘要：協(xié)作型過(guò)濾協(xié)同過(guò)濾是利用集體智慧的一個(gè)典型方法。這就是協(xié)同過(guò)濾的核心思想。要實(shí)現(xiàn)協(xié)同過(guò)濾，需要以下幾個(gè)步驟搜集偏好尋找相近用戶推薦物品搜集偏好首先，我們要尋找一種表達(dá)不同人及其偏好的方法。

協(xié)同過(guò)濾是利用集體智慧的一個(gè)典型方法。要理解什么是協(xié)同過(guò)濾 (Collaborative Filtering, 簡(jiǎn)稱CF)，首先想一個(gè)簡(jiǎn)單的問(wèn)題，如果你現(xiàn)在想看個(gè)電影，但你不知道具體看哪部，你會(huì)怎么做？大部分的人會(huì)問(wèn)問(wèn)周圍的朋友，看看最近有什么好看的電影推薦，而我們一般更傾向于從口味比較類似的朋友那里得到推薦。這就是協(xié)同過(guò)濾的核心思想。

協(xié)同過(guò)濾一般是在海量的用戶中發(fā)掘出一小部分和你品位比較類似的，在協(xié)同過(guò)濾中，這些用戶成為鄰居，然后根據(jù)他們喜歡的其他東西組織成一個(gè)排序的目錄推薦給你。

要實(shí)現(xiàn)協(xié)同過(guò)濾，需要以下幾個(gè)步驟：

搜集偏好

尋找相近用戶

推薦物品

首先，我們要尋找一種表達(dá)不同人及其偏好的方法。這里我們用python的嵌套字典來(lái)實(shí)現(xiàn)。

在本章中所用的數(shù)據(jù)，是從國(guó)外的網(wǎng)站grouplens下載的u.data。該數(shù)據(jù)總共四列，共分為用戶ID、電影ID、用戶評(píng)分、時(shí)間。我們只需根據(jù)前三列，生成相應(yīng)的用戶偏好字典。

#生成用戶偏好字典
def make_data():
    result={}
    f = open("data/u.data", "r")
    lines = f.readlines()
    for line in lines:
        #按行分割數(shù)據(jù)
        (userId , itemId , score,time ) = line.strip().split("	")
        #字典要提前定義
        if not result.has_key( userId ):
            result[userId]={}
        #注意float,不然后續(xù)的運(yùn)算存在類型問(wèn)題
        result[userId][itemId] = float(score)
    return result

另外如果想在字典中顯示展現(xiàn)電影名，方便分析，也可以根據(jù)u.item中電影數(shù)據(jù)，預(yù)先生成電影的數(shù)據(jù)集。

#將id替換為電影名 構(gòu)造數(shù)據(jù)集
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("	")
        prefs.setdefault(user,{})
        prefs[user][movies[movieid]]=float(rating)
    return prefs

根據(jù)上面兩個(gè)函數(shù)中的一種，到此我們的用戶數(shù)據(jù)集已經(jīng)構(gòu)造好了，由于數(shù)據(jù)量不是非常大，暫時(shí)放在內(nèi)存中即可。
由于以上數(shù)據(jù)集比較抽象，不方便講解，至此我們定義一個(gè)簡(jiǎn)單的數(shù)據(jù)集來(lái)講解一些例子，一個(gè)簡(jiǎn)單的嵌套字典：

#用戶：{電影名稱：評(píng)分}
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}
}

收集完用戶信息后，我們通過(guò)一些方法來(lái)確定兩個(gè)用戶之間品味的相似程度，計(jì)算他們的相似度評(píng)價(jià)值。有很多方法可以計(jì)算，我們?cè)诖私榻B兩套常見(jiàn)的方法：歐幾里得距離和皮爾遜相關(guān)度。

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

數(shù)學(xué)定義：
已知兩點(diǎn) A = (x_1,x_2,...,x_n)和B = (y_1,y_2,...,y_n)，則兩點(diǎn)間距離：
$$|AB|=sqrt{(x_1 - x_2)^2+(y_1 - y_2)^2+...+(x_n-y_n)^2}$$
接下來(lái)我們只要把數(shù)據(jù)集映射為坐標(biāo)系就可以明顯的比較出相似度，以"Snakes on a Plane"和"You, Me and Dupree"兩部電影距離，有坐標(biāo)系如下圖：

計(jì)算上圖中Toby和Mick LaSalle的相似度：

from math import sqrt
sqrt(pow( 4.5-4 , 2 ) + pow( 1 - 2 , 2))
1.118033988749895

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

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

接下來(lái)我們就可以封裝一個(gè)基于歐幾里得距離的相似度評(píng)價(jià)，具體python實(shí)現(xiàn)如下：

#歐幾里得距離
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    
    
    #計(jì)算距離 
    sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) for item in si])
    return 1/(1 + sqrt(sum_of_squares) )

基于測(cè)試數(shù)據(jù)集critics，則可以計(jì)算兩個(gè)人的相似度值為：

sim_distance( critics , "Toby", "Mick LaSalle" )
0.307692307692

皮爾遜相關(guān)系數(shù)是一種度量?jī)蓚€(gè)變量間相關(guān)程度的方法。它是一個(gè)介于 1 和 -1 之間的值，其中，1 表示變量完全正相關(guān)， 0 表示無(wú)關(guān)，-1 表示完全負(fù)相關(guān)。

數(shù)學(xué)公式：
$$frac{sum x_iy_i-frac{sum x_isum 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}}}$$

與歐幾里得距離不同，我們根據(jù)兩個(gè)用戶來(lái)建立笛卡爾坐標(biāo)系，根據(jù)用戶對(duì)相同電影的評(píng)分來(lái)建立點(diǎn)，如下圖：

在圖上，我們還可以看到一條線，因其繪制的原則是盡可能的接近圖上所有點(diǎn)，故該線也稱為最佳擬合線。用皮爾遜方法進(jìn)行評(píng)價(jià)時(shí)，可以修正“夸大值”部分，例如某人對(duì)電影的要求更為嚴(yán)格，給出分?jǐn)?shù)總是偏低。

python代碼實(shí)現(xiàn)：

#皮爾遜相關(guān)度 
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)
    
    #計(jì)算開(kāi)始
    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))
    #計(jì)算結(jié)束

    if den==0: return 0
    
    r=num/den
    
    return r

最后根據(jù)critics的數(shù)據(jù)計(jì)算Gene Seymour和Lisa Rose的相關(guān)度：

recommendations.sim_pearson(recommendations.critics,"Gene Seymour","Lisa Rose")

到此，我們就可以根據(jù)計(jì)算出用戶之間的相關(guān)度，并根據(jù)相關(guān)度來(lái)生成相關(guān)度列表，找出與用戶口味相同的其他用戶。

#推薦用戶
def topMatches(prefs,person,n=5,similarity=sim_distance):
    #python列表推導(dǎo)式
    scores=[(similarity(prefs,person,other),other) for other in prefs if other!=person]
    scores.sort()
    scores.reverse()
    return scores[0:n]

對(duì)于用戶來(lái)說(shuō)，找出與他具有相似愛(ài)好的人并不重要，主要是為他推薦他可能喜歡的物品，所以我們還需要根據(jù)用戶間相似度進(jìn)一步計(jì)算。例如為Toby推薦，由于數(shù)據(jù)不多，我們?nèi)〉盟型扑]者的相似度，再乘以他們對(duì)電影的評(píng)價(jià)，得出該電影對(duì)于Toby的推薦值，也可以認(rèn)為是Toby可能為電影打的分?jǐn)?shù)。如下圖：

我們通過(guò)計(jì)算其他用戶對(duì)某個(gè)Toby沒(méi)看過(guò)電影的加權(quán)和來(lái)得到總權(quán)重，最后除以相似度和，是為了防止某一電影被看過(guò)的多，總和會(huì)更多的影響，也稱“歸一化”處理。

#基于用戶推薦物品
def getRecommendations(prefs,person,similarity=sim_pearson):
    
    totals={}
    simSums={}

    for other in prefs:
        #不和自己做比較
        if other == person: 
            continue
        sim = similarity( prefs,person,other )
        #去除負(fù)相關(guān)的用戶
        if sim<=0: continue
        for item in prefs[other]:
            #只對(duì)自己沒(méi)看過(guò)的電影做評(píng)價(jià)
            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

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

同樣，先構(gòu)造數(shù)據(jù)集，即以物品為key的字典，格式為{電影:{用戶:評(píng)分,用戶:評(píng)分}}

#基于物品的列表
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

計(jì)算物品間的相似度，物品間相似的變化不會(huì)像人那么頻繁，所以我們可以構(gòu)造物品間相似的集合，存成文件重復(fù)利用：

#構(gòu)建基于物品相似度數(shù)據(jù)集
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

基于物品的推薦值計(jì)算，通過(guò)Toby已看影片的評(píng)分，乘以未看影片之間的相似度，來(lái)獲取權(quán)重。最后歸一化處理如下圖：

#基于物品的推薦
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    

源碼

UserCF和ItemCF的比較

歸一化處理的更合適方法

與頻繁模式挖掘的區(qū)別