基于用戶的協(xié)同過濾算法（UserCF）原理以及代碼實(shí)踐

簡介

協(xié)同過濾（collaborative filtering）是一種在推薦系統(tǒng)中廣泛使用的技術(shù)踢步。該技術(shù)通過分析用戶或者事物之間的相似性，來預(yù)測用戶可能感興趣的內(nèi)容并將此內(nèi)容推薦給用戶。這里的相似性可以是人口特征的相似性雌澄，也可以是歷史瀏覽內(nèi)容的相似性，還可以是個(gè)人通過一定機(jī)制給與某個(gè)事物的回應(yīng)。比如帅刀，A和B是無話不談的好朋友，并且都喜歡看電影远剩，那么協(xié)同過濾會(huì)認(rèn)為A和B的相似度很高扣溺，會(huì)將A喜歡但是B沒有關(guān)注的電影推薦給B，反之亦然瓜晤。

協(xié)同過濾推薦分為3種類型：

基于用戶(user-based)的協(xié)同過濾(UserCF)
基于物品(item-based)的協(xié)同過濾（ItemCF算法)
基于模型(model-based)的協(xié)同過濾 (ModelCF算法)

本文主要講述基于用戶協(xié)同過濾算法的原理以及代碼實(shí)現(xiàn)锥余。

算法原理

UserCF算法主要是考慮用戶與用戶之間的相似度，給用戶推薦和他興趣相似的其他用戶喜歡的物品痢掠。俗話說"物以群分驱犹，人以類聚"嘲恍，人們總是傾向于跟自己志同道合的人交朋友。同理雄驹，你朋友喜歡的東西你大概率也可能會(huì)喜歡佃牛，UserCF算法正是利用了這個(gè)原理。舉個(gè)例子医舆，如果要給一個(gè)用戶A推薦物品俘侠，可以先找到與A最為相似的用戶B，接著獲取用戶B最喜歡的且用戶A沒有聽說過的物品蔬将，并預(yù)測用戶A對這些物品的評分爷速，從中選取評分最高的若干個(gè)物品推薦給用戶A。

從上述描述可以知道娃胆，UserCF算法的主要步驟如下：

找到與目標(biāo)用戶興趣相似的用戶集合
找到這個(gè)集合中的用戶最喜歡的遍希，且目標(biāo)用戶還未接觸過的物品推薦給目標(biāo)用戶

上述是UserCF算法的基本思路等曼，方便讀者形成對UserCF算法的整體印象里烦。也許你看了上述文字依然沒有思路，沒關(guān)系禁谦，且繼續(xù)往下看胁黑。

首先，根據(jù)算法的步驟1州泊，我們自然而然就會(huì)提出一個(gè)問題丧蘸，那就是如何度量兩個(gè)用戶之間的相似度？試想一下遥皂，我們在現(xiàn)實(shí)生活中如何判斷兩個(gè)人是否興趣相似呢力喷？比如你喜歡打LOL，恰巧你室友也喜歡演训，那顯然你們的共同話題會(huì)比較多弟孟，因?yàn)槟銈冇泄餐呐d趣愛好。我們剛好可以利用這一點(diǎn)來計(jì)算用戶之間的相似度样悟。

對于用戶u和用戶v拂募，令N(u)代表用戶u喜歡的物品合集，令N(v)代表用戶v喜歡的物品合集窟她。N(u)∩N(v)代表的是用戶u和用戶v都喜歡的物品陈症，N(u)∪N(v)代表的是用戶u和用戶v喜歡的物品的合集，那么可以利用以下公式來簡單計(jì)算相似度:
$W\mu\nu = \frac {|N(\mu) \bigcap N(\nu)|}{|N(\mu) \bigcup N(\nu)|}$
上述公式叫做Jaccard公式震糖，直觀上理解就是录肯，將用戶u與用戶v都喜歡的物品的數(shù)量除以他們喜歡物品的總和，如果u和v喜歡的物品是一模一樣的吊说，則u和v的相似度為1论咏。

還有另外一種余弦相似度計(jì)算公式:
$W\mu\nu = \frac {|N(\mu) \bigcap N(\nu)|} {\sqrt{|N(\mu) \| N(\nu)}|}$
上述公式的分母部分代表的是u喜歡的物品的數(shù)量與v喜歡的物品的數(shù)量的乘積于样，而不再是他們之間的交集。

舉個(gè)簡單例子來表明如何計(jì)算用戶u和v之間的相似度潘靖，假如用戶u和用戶v喜歡的游戲如下表：

用戶	喜愛的游戲
u	{英雄聯(lián)盟, 王者榮耀穿剖，絕地求生}
v	{英雄聯(lián)盟，和平精英}

利用余弦相似度計(jì)算公式可以得到如下結(jié)果：
$W\mu\nu = \frac {|\{英雄聯(lián)盟,王者榮耀,絕地求生\} \bigcap \{英雄聯(lián)盟,和平精英\}|}{\sqrt{\{英雄聯(lián)盟,王者榮耀,絕地求生\} || \{英雄聯(lián)盟, 和平精英\}}|} = \frac {1}{\sqrt{6}}$
故卦溢，我們可以計(jì)算得到用戶u和用戶v之間的相似度為 $\frac {1}{\sqrt{6}}$ 糊余。

至此，我們已經(jīng)可以計(jì)算任意兩個(gè)用戶之間的相似度了单寂，下一步要做的事情是建立一張用戶相似度表贬芥，此表中保存了任意兩個(gè)用戶之間的相似度，方便后續(xù)挑選出與用戶u最相似的若干個(gè)用戶宣决。

當(dāng)用戶相似度表建立起來了之后蘸劈，UserCF算法就可以給用戶推薦與他興趣最相似的K個(gè)用戶喜歡的物品了。那此時(shí)又會(huì)出現(xiàn)一個(gè)問題尊沸，假如我們要給用戶w進(jìn)行推薦威沫，并且在用戶相似度表中找到了與他最相似的K個(gè)用戶，這K個(gè)用戶喜歡的物品有很多洼专，我們怎么知道要推薦哪些物品給用戶w呢棒掠？此時(shí)就涉及到了用戶對物品的感興趣程度，我們當(dāng)然會(huì)把用戶最感興趣的物品推薦給他屁商。故使用以下公式來度量用戶u對物品i的感興趣程度：

$p(\mu, i) = \sum_{\nu \in S(\mu, K) \bigcap N(i)} W\mu\nu R\nu i$
乍一看感覺很復(fù)雜烟很，其實(shí)不然。
其中 $S(\mu, K)$ 代表的是與用戶 $\mu$ 最相似的K個(gè)用戶蜡镶，將與用戶 $\mu$ 相似的用戶列表按照相似度進(jìn)行排序就可以得到雾袱。 $N(i)$ 代表的是對喜歡物品i的用戶集合， $W\mu\nu$ 代表的是用戶 $\mu$ 和用戶 $\nu$ 之間的相似度官还，這個(gè)也可以直接從用戶相似度表中得到芹橡。 $R\nu i$ 代表用戶v對物品i的興趣，因?yàn)槭褂玫氖菃我恍袨榈碾[反饋數(shù)據(jù)妻枕，所以所有的 $R\nu i=1$ 僻族。

對于與用戶 $\mu$ 最相似的K個(gè)用戶，我們分別計(jì)算用戶 $\mu$ 與這K個(gè)用戶喜歡的物品集合 $I_n, n \in \{1,2,...,N\}$ 之間的感興趣程度屡谐，得到用戶 $\mu$
對這N個(gè)物品的感興趣程度列表述么，然后將其逆序排序，取前m個(gè)物品推薦給用戶 $\mu$ 愕掏，至此UserCF算法結(jié)束度秘。

算法工作流程

接下來，我們用一個(gè)簡單例子演示一下UserCF的具體工作流程。
下表是我們臆造的原始數(shù)據(jù)剑梳，也稱之為User-Item表唆貌，即用戶-物品列表，記錄了每個(gè)用戶喜愛的物品垢乙，數(shù)據(jù)表格如下：

用戶	喜愛的物品
A	{a,b,d}
B	{a,c,d}
C	{b,e}
D	{c,d,e}

接下來我們需要計(jì)算用戶相似度矩陣锨咙，最直觀的方法就是，對于用戶列表{A,B,C,D},我們對其中兩兩用戶都使用余弦相似度算法計(jì)算相似度追逮。這種算法的時(shí)間復(fù)雜度是O(N^2)酪刀，當(dāng)用戶量很大的時(shí)候，計(jì)算非常耗時(shí),在實(shí)際運(yùn)用中不可取钮孵。觀察一下相似度計(jì)算公式會(huì)發(fā)現(xiàn)骂倘，其實(shí)如果用戶 $\mu$ 和用戶 $\nu$ 沒有共同喜歡的物品（比如表中的用戶B和用戶C），那么他們之間的相似度為0巴席，也就沒有必要計(jì)算了历涝。
也就是說我們沒必要對任意兩個(gè)用戶之間都計(jì)算相似度，我們只需要計(jì)算那些彼此之間有共同喜愛物品的用戶之間的相似度漾唉，故首先可以想到建立倒排表荧库，即Item-User表，具體如下：

物品	喜愛它的用戶
a	{A,B}
b	{A,C}
c	{B,D}
d	{A,B,D}
e	{C,D}

有了這張表之后毡证，相當(dāng)于我們將原先零散的用戶按照他們喜愛的物品給劃分成若干個(gè)小圈子电爹。比如用戶A、B由于都喜歡物品a料睛，所以被分到了一起。同理摇邦，用戶C恤煞、D都喜歡物品e，因此也被分到了一起施籍。
那這么做的目的是什么呢居扒？回顧一下上面說的用戶相似度計(jì)算方法，可以看到無論是哪一種方法都要先求出|N( $\mu$ )∩N( $\nu$ )|丑慎，所以我們的目的就是為了快速地求出任意用戶之間的交集喜喂。
由此可以建立下面的用戶喜愛物品交集矩陣W：

	A	B	C	D
A	0	2	1	1
B	2	0	0	2
C	1	0	0	1
D	1	2	1	0

其中W[u][v]代表的含義是用戶u和用戶v都喜愛的物品個(gè)數(shù)，即|N( $\mu$ )∩N( $\nu$ )|竿裂。比如用戶A玉吁、C都喜歡物品b，所以W[A][C]=1腻异。用戶A进副、B除了喜歡物品a以外，還共同喜歡物品d悔常，因此W[A][B]=2影斑。
由于用戶A给赞、B之間的交集和用戶B、A之間的交集是一樣的矫户，所以此矩陣是一個(gè)對稱矩陣片迅。
其實(shí)這里的W就是相似度計(jì)算公式中的分子部分，而每個(gè)用戶的喜愛列表從之前的User-Item列表中就已經(jīng)可以得到了皆辽，因此我們就可以計(jì)算出用戶相似度矩陣了障涯，結(jié)果如下：

	A	B	C	D
A	0	0.67	0.41	0.33
B	0.67	0	0	0.67
C	0.41	0	0	0.41
D	0.33	0.67	0.41	0

當(dāng)用戶相似度矩陣建立好了之后，我們就可以對用戶進(jìn)行物品推薦了膳汪。
比如要對用戶C進(jìn)行物品推薦唯蝶，通過查表可以知道（上表第四行），用戶A和用戶D是比較相似的兩個(gè)用戶遗嗽。
再通過User-Item表查詢到用戶A喜歡的物品列表{a,b,d}粘我，用戶D喜歡的物品列表{c,d,e}，故用戶A痹换、D喜歡物品的交集是{a,b,c,d,e}征字，其中用戶C喜歡的列表是{b,e}，為了避免重復(fù)推薦用戶已經(jīng)喜歡的物品娇豫，所以要先從物品列表中去掉用戶C已經(jīng)喜歡的物品匙姜，故最終待推薦的物品列表為{a,c,d}。
此時(shí)我們來計(jì)算用戶C對待推薦物品列表中物品的感興趣程度：

p(C,a) = W[C][A] = 0.41
p(C,c) = W[C][D] = 0.41
p(C,d) = W[C][A] + W[C][D] = 0.82

接著按照用戶C對待推薦物品感興趣程度對待推薦列表進(jìn)行逆序排序冯痢，得到最終的推薦列表{d,a,c}氮昧，我們可以將整個(gè)推薦列表或者取前K個(gè)物品推薦給用戶C。
至此浦楣，UserCF算法整體流程結(jié)束袖肥。
可以看到，算法的輸出的最應(yīng)該推薦給用戶C的物品是d振劳，我們不難發(fā)現(xiàn)這是因?yàn)榕c用戶C最相似的用戶A和用戶D都喜歡物品d椎组，因此將d推薦給C是比較合理的選擇。

相似度算法改進(jìn)

上述算法使用的是余弦相似度計(jì)算公式历恐，但是這個(gè)公式過于粗糙寸癌，原因是余弦相似度只是簡單地計(jì)算了用戶u和用戶v共同喜歡的物品在他們總共喜歡物品中占據(jù)的比例。
比如弱贼，兩個(gè)用戶都購買了時(shí)下熱門物品蒸苇，這并不能說明他們興趣相似，因?yàn)闊衢T物品是絕大多數(shù)人都會(huì)買的東西哮洽。換句話說填渠，兩個(gè)用戶對冷門物品采用過相同的行為更能說明他們興趣的相似度。因此John.S.Breese提出了以下相似度計(jì)算公式：
$W\mu\nu = \frac {\sum_{i \in N(\mu) \bigcap N(\nu) } \frac {1} {log(1+|N(i)|)} }{\sqrt{|N(\mu) \| N(\nu)}|}$
相比余弦相似度公式，這里的分子 $\frac {1} {log(1+|N(i)|)}$ 懲罰了用戶u和用戶v共同喜歡的熱門物品對他們相似度的影響氛什。
在下一節(jié)的代碼實(shí)踐中莺葫，分別實(shí)現(xiàn)了基于這兩種相似度計(jì)算的UserCF算法。

代碼實(shí)踐

上一節(jié)是基于一個(gè)非常簡易的測試數(shù)據(jù)集枪眉，接下來我們將UserCF算法運(yùn)用在推薦系統(tǒng)經(jīng)典數(shù)據(jù)集MovieLens上捺檬。
MovieLens數(shù)據(jù)集介紹以及數(shù)據(jù)處理參見鏈接。

根據(jù)之前的介紹贸铜，可知整個(gè)算法流程分為兩個(gè)階段：

訓(xùn)練階段
推薦階段

對于訓(xùn)練階段堡纬，可分為以下幾步：

數(shù)據(jù)預(yù)處理，建立User-Item表
建立Item-User倒排表
建立用戶物品交集矩陣
建立用戶相似度矩陣

對于推薦階段蒿秦，可分為以下幾步：

尋找與被推薦用戶最相似的K個(gè)用戶
計(jì)算用戶對物品的感興趣列表并逆序排列

訓(xùn)練階段

數(shù)據(jù)預(yù)處理烤镐，建立User-Item表

我們采用MovieLens數(shù)據(jù)集中的ratings.dat文件，因?yàn)檫@里面包含了用戶對電影的評分?jǐn)?shù)據(jù)棍鳖，注意我們忽略掉評分那一欄炮叶，將其簡化成用戶喜歡或者不喜歡。只要用戶有參與過評分的電影渡处，無論分值如何镜悉，我們都認(rèn)為這部電影是用戶喜歡的。

注意医瘫，ratings.dat里面包含了100多萬條評價(jià)數(shù)據(jù)侣肄，為了減少訓(xùn)練時(shí)間，可以只讀取部分?jǐn)?shù)據(jù)醇份，本文讀取了前29415條數(shù)據(jù)稼锅，即前200個(gè)用戶的評價(jià)數(shù)據(jù)。ratings.dat原始數(shù)據(jù)每行包含了4列被芳，本文中只取了’UserID‘缰贝、’MovieID‘這兩列，關(guān)于此數(shù)據(jù)集的詳細(xì)介紹請參見鏈接畔濒。

接下來使用以下代碼來讀取數(shù)據(jù)并建立User-Item表：

import random
import pandas as pd

def LoadMovieLensData(filepath, train_rate):
    ratings = pd.read_table(filepath, sep="::", header=None, names=["UserID", "MovieID", "Rating", "TimeStamp"],\
                            engine='python')
    ratings = ratings[['UserID','MovieID']]
    train = []
    test = []
    random.seed(3)
    for idx, row in ratings.iterrows():
        user = int(row['UserID'])
        item = int(row['MovieID'])
        if random.random() < train_rate:
            train.append([user, item])
        else:
            test.append([user, item])
    return PreProcessData(train), PreProcessData(test)

def PreProcessData(originData):
    """
    建立User-Item表，結(jié)構(gòu)如下：
        {"User1": {MovieID1, MoveID2, MoveID3,...}
         "User2": {MovieID12, MoveID5, MoveID8,...}
         ...
        }
    """
    trainData = dict()
    for user, item in originData:
        trainData.setdefault(user, set())
        trainData[user].add(item)
    return trainData

建立Item-User倒排表

這里使用了python的dict里面嵌套set來實(shí)現(xiàn)倒排表锣咒，偽代碼如下：

def UserItemTable(userItemTab):
    """
    建立User-Item倒排表
    :param userItemTab: user-item表
    :return:
    """
    item_user = dict()
    for user, items in userItemTab.items():
        for item in items:
            item_user.setdefault(item, set())
            item_user[item].add(user)

建立用戶物品交集矩陣

同理侵状，保存用戶物品交集的矩陣采用了雙重dict來實(shí)現(xiàn)。

def UserInterSection(item_user):
    """
    建立用戶物品交集矩陣W, 其中C[u][v]代表的含義是用戶u和用戶v之間共同喜歡的物品數(shù)
    :param item_user: item_user 倒排表
    """
    userInterSection = dict()
    for item, users in item_user.items():
        for u in users:
            for v in users:
                if u == v:
                    continue
                userInterSection.setdefault(u, defaultdict(int))
                userInterSection[u][v] += 1  # 將用戶u和用戶v共同喜歡的物品數(shù)量加一

建立用戶相似度矩陣

用戶相似度矩陣只需要在用戶物品交集矩陣的基礎(chǔ)上除以用戶u和用戶v各自喜愛物品列表數(shù)量的乘積毅整。

def UserSimMatrix(userItemTab, userInterSection):
    """
    建立用戶相似度矩陣
    :param userItemTab: User-Item表
    :param userInterSection: 用戶物品交集矩陣
    :return: 
    """
    userSimMatrix = dict() #用戶相似度矩陣
    for u, related_user in userInterSection.items():
        for v, cuv in related_user.items():
            nu = len(userItemTab[u])
            nv = len(userItemTab[v])
            userSimMatrix[u][v] = cuv / math.sqrt(nu * nv)

完整代碼

下面的代碼實(shí)現(xiàn)了完整的功能捍壤，修改“ratings.dat"文件的路徑之后，可以直接運(yùn)行鞍爱。


import math
import random
import pandas as pd
from Utils import modelsave
from collections import defaultdict
from operator import itemgetter

def LoadMovieLensData(filepath, train_rate):
    ratings = pd.read_table(filepath, sep="::", header=None, names=["UserID", "MovieID", "Rating", "TimeStamp"],\
                            engine='python')
    ratings = ratings[['UserID','MovieID']]

    train = []
    test = []
    random.seed(3)
    for idx, row in ratings.iterrows():
        user = int(row['UserID'])
        item = int(row['MovieID'])
        if random.random() < train_rate:
            train.append([user, item])
        else:
            test.append([user, item])
    return PreProcessData(train), PreProcessData(test)

def PreProcessData(originData):
    """
    建立User-Item表鹃觉，結(jié)構(gòu)如下：
        {"User1": {MovieID1, MoveID2, MoveID3,...}
         "User2": {MovieID12, MoveID5, MoveID8,...}
         ...
        }
    """
    trainData = dict()
    for user, item in originData:
        trainData.setdefault(user, set())
        trainData[user].add(item)
    return trainData

class UserCF(object):
    """ User based Collaborative Filtering Algorithm Implementation"""
    def __init__(self, trainData, similarity="cosine"):
        self._trainData = trainData
        self._similarity = similarity
        self._userSimMatrix = dict() # 用戶相似度矩陣

    def similarity(self):
        # 建立User-Item倒排表
        item_user = dict()
        for user, items in self._trainData.items():
            for item in items:
                item_user.setdefault(item, set())
                item_user[item].add(user)

        # 建立用戶物品交集矩陣W, 其中C[u][v]代表的含義是用戶u和用戶v之間共同喜歡的物品數(shù)
        for item, users in item_user.items():
            for u in users:
                for v in users:
                    if u == v:
                        continue
                    self._userSimMatrix.setdefault(u, defaultdict(int))
                    if self._similarity == "cosine":
                        self._userSimMatrix[u][v] += 1 #將用戶u和用戶v共同喜歡的物品數(shù)量加一
                    elif self._similarity == "iif":
                        self._userSimMatrix[u][v] += 1. / math.log(1 + len(users))

        # 建立用戶相似度矩陣
        for u, related_user in self._userSimMatrix.items():
            # 相似度公式為 |N[u]∩N[v]|/sqrt(N[u]||N[v])
            for v, cuv in related_user.items():
                nu = len(self._trainData[u])
                nv = len(self._trainData[v])
                self._userSimMatrix[u][v] = cuv / math.sqrt(nu * nv)

    def recommend(self, user, N, K):
        """
        用戶u對物品i的感興趣程度：
            p(u,i) = ∑WuvRvi
            其中Wuv代表的是u和v之間的相似度， Rvi代表的是用戶v對物品i的感興趣程度睹逃，因?yàn)椴捎脝我恍袨榈碾[反饋數(shù)據(jù)盗扇，所以Rvi=1。
            所以這個(gè)表達(dá)式的含義是唯卖，要計(jì)算用戶u對物品i的感興趣程度粱玲，則要找到與用戶u最相似的K個(gè)用戶，對于這k個(gè)用戶喜歡的物品且用戶u
            沒有反饋的物品拜轨，都累加用戶u與用戶v之間的相似度抽减。
        :param user: 被推薦的用戶user
        :param N: 推薦的商品個(gè)數(shù)
        :param K: 查找的最相似的用戶個(gè)數(shù)
        :return: 按照user對推薦物品的感興趣程度排序的N個(gè)商品
        """
        recommends = dict()
        # 先獲取user具有正反饋的item數(shù)組
        related_items = self._trainData[user]
        # 將其他用戶與user按照相似度逆序排序之后取前K個(gè)
        for v, sim in sorted(self._userSimMatrix[user].items(), key=itemgetter(1), reverse=True)[:K]:
            # 從與user相似的用戶的喜愛列表中尋找可能的物品進(jìn)行推薦
            for item in self._trainData[v]:
                # 如果與user相似的用戶喜愛的物品與user喜歡的物品重復(fù)了，直接跳過
                if item in related_items:
                    continue
                recommends.setdefault(item, 0.)
                recommends[item] += sim
        # 根據(jù)被推薦物品的相似度逆序排列橄碾，然后推薦前N個(gè)物品給到用戶
        return dict(sorted(recommends.items(), key=itemgetter(1), reverse=True)[:N])

    def train(self):
        self.similarity()


if __name__ == "__main__":
    train, test = LoadMovieLensData("../Data/ml-1m/ratings.dat", 0.8)
    print("train data size: %d, test data size: %d" % (len(train), len(test)))
    UserCF = UserCF(train)
    UserCF.train()

    # 分別對測試集中的前4個(gè)用戶進(jìn)行電影推薦
    print(UserCF.recommend(list(test.keys())[0], 5, 80))
    print(UserCF.recommend(list(test.keys())[1], 5, 80))
    print(UserCF.recommend(list(test.keys())[2], 5, 80))
    print(UserCF.recommend(list(test.keys())[3], 5, 80))

上述代碼對測試集中前4個(gè)用戶進(jìn)行了電影推薦卵沉，對每個(gè)用戶而言，從與他們相似的80個(gè)用戶喜歡的電影中挑選出5部推薦法牲。輸出結(jié)果是一個(gè)dict史汗，里面包含了給用戶推薦的電影以及用戶對每部電影的感興趣程度，按照逆序排列拒垃。

運(yùn)行結(jié)果如下：

參考

協(xié)同過濾--維基百科
《推薦系統(tǒng)實(shí)戰(zhàn)》-- 項(xiàng)亮
http://www.reibang.com/p/a59ff0dc22a3