基于鄰域的算法是推薦系統(tǒng)中最基本的算法，該算法不僅在學(xué)術(shù)界得到了深入研究，而且在業(yè)界得到了廣泛應(yīng)用。基于鄰域的算法分為兩大類，一類是基于用戶的協(xié)同過濾算法，另一類是基于物品的協(xié)同過濾算法。

我們先來看看基于用戶的協(xié)同過濾算法，基于物品的協(xié)同過濾算法大體思路和基于用戶的差不多，可以自己參考對比學(xué)習(xí)。

基于用戶的協(xié)同過濾算法

每年新學(xué)期開始，剛進(jìn)實(shí)驗(yàn)室的師弟總會問師兄相似的問題，比如“我應(yīng)該買什么專業(yè)書啊”、“我應(yīng)該看什么論文啊”等。這個時候，師兄一般會給他們做出一些推薦。這就是現(xiàn)實(shí)中個性化推薦的一種例子。在這個例子中，師弟可能會請教很多師兄，然后做出最終的判斷。師弟之所以請教師兄，一方面是因?yàn)樗麄冇猩鐣P(guān)系，互相認(rèn)識且信任對方，但更主要的原因是師兄和師弟有共同的研究領(lǐng)域和興趣。那么，在一個在線個性化推薦系統(tǒng)中，當(dāng)一個用戶A需要個性化推薦時，可以先找到和他有相似興趣的其他用戶，然后把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。這種方法稱為基于用戶的協(xié)同過濾算法。

基于用戶的協(xié)同過濾算法主要包括兩個步驟。

(1) 找到和目標(biāo)用戶興趣相似的用戶集合。

(2) 找到這個集合中的用戶喜歡的，且目標(biāo)用戶沒有聽說過的物品推薦給目標(biāo)用戶。

步驟(1)的關(guān)鍵就是計(jì)算兩個用戶的興趣相似度。這里，協(xié)同過濾算法主要利用行為的相似度計(jì)算興趣的相似度。給定用戶u和用戶v，令N(u)表示用戶u曾經(jīng)有過正反饋的物品集合，令N(v)為用戶v曾經(jīng)有過正反饋的物品集合。那么，我們可以通過如下的Jaccard公式簡單地計(jì)算u和v的興趣相似度或者通過余弦公式：

      jaccard                                                                             余項(xiàng)公式：

：                         

這個一個行為記錄                                             我們可以根據(jù)余弦公式計(jì)算如下

以余弦相似度為例，實(shí)現(xiàn)該相似度可以利用下面的偽代碼：

def UserSimilarity(train):    W = dict()    for u in train.keys():        for v in train.keys():            if u == v:                continue            W[u][v] = len(train[u] & train[v])            W[u][v] = /= math.sqrt(len(train[u]) * len(train[v]) * 1.0)    return W

這種方法的時間復(fù)雜度是O(|U|*|U|)，這在用戶數(shù)很大時非常耗時。事實(shí)上，很多用戶相互之間并沒有對同樣的物品產(chǎn)生過行為，即很多時候N(u)^ N(v) = 0。上面的算法將很多時間浪費(fèi)在了計(jì)算這種用戶之間的相似度上。如果換一個思路，我們可以首先計(jì)算出N(u)^ N(v) != 0 的用戶對(u,v)，然后再對這種情況除以分母sqrt(N(u)*N(v)) 。

為此，可以首先建立物品到用戶的倒排表，對于每個物品都保存對該物品產(chǎn)生過行為的用戶列表。令稀疏矩陣C[u][v]= N(u)^ N(v) 。那么，假設(shè)用戶u和用戶v同時屬于倒排表中K個物品對應(yīng)的用戶列表，就有C[u][v]=K。從而，可以掃描倒排表中每個物品對應(yīng)的用戶列表，將用戶列表中的兩兩用戶對應(yīng)的C[u][v]加1，最終就可以得到所有用戶之間不為0的C[u][v]

def UserSimilarity(train):    # build inverse table for item_users    item_users = dict()    for u, items in train.items():        for i in items.keys():            if i not in item_users:                item_users[i] = set()            item_users[i].add(u)    #calculate co-rated items between users    C = dict()    N = dict()    for i, users in item_users.items():        for u in users:            N[u] += 1            for v in users:                if u == v:                    continue                C[u][v] += 1    #calculate finial similarity matrix W    W = dict()    for u, related_users in C.items():        for v, cuv in related_users.items():            W[u][v] = cuv / math.sqrt(N[u] * N[v])    return W

下面是按照想法建立的稀疏矩陣，對于物品a，將W[A][B]和W[B][A]加1，對于物品b，將W[A][C]和W[C][A]加1，以此類推，掃描完所有物品后，我們可以得到最終的W矩陣，這里的W是余弦相似度中的分子部分，然后將W除以分母可以得到最終的用戶興趣相似度

得到用戶之間的興趣相似度后，UserCF算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。上面右邊公式度量了UserCF算法中用戶u對物品i的感興趣程度：其中，S(u, K)包含和用戶u興趣最接近的K個用戶，N(i)是對物品i有過行為的用戶集合，Wuv是用戶u和用戶v的興趣相似度，Rvi代表用戶v對物品i的興趣，因?yàn)槭褂玫氖菃我恍袨榈碾[反饋數(shù)據(jù)，所以所有的Rvi=1。

如下代碼實(shí)現(xiàn)了上面的UserCF推薦算法：

def Recommend(user, train, W):    rank = dict()    interacted_items = train[user]    for v, wuv in sorted(W[u].items, key=itemgetter(1), reverse=True)[0:K]:        for i, rvi in train[v].items:        if i in interacted_items:            #we should filter items user interacted before            continue        rank[i] += wuv * rvi    return rank

選取K=3，用戶A對物品c、e沒有過行為，因此可以把這兩個物品推薦給用戶A。根據(jù)UserCF算法，用戶A對物品c、e的興趣是：

用戶相似度計(jì)算的改進(jìn)

如果兩個用戶都曾經(jīng)買過《新華字典》，這絲毫不能說明他們興趣相似，因?yàn)榻^大多數(shù)中國人小時候都買過《新華字典》。但如果兩個用戶都買過《數(shù)據(jù)挖掘?qū)д摗罚强梢哉J(rèn)為他們的興趣比較相似，因?yàn)橹挥醒芯繑?shù)據(jù)挖掘的人才會買這本書。換句話說，兩個用戶對冷門物品采取過同樣的行為更能說明他們興趣的相似度。因此，John S. Breese在論文①中提出了如下公式，根據(jù)用戶行為計(jì)算用戶的興趣相似度：

分子中的倒數(shù)懲罰了用戶u和用戶v共同興趣列表中熱門物品對他們相似度的影響。N(i)是對物品i有過行為的用戶集合，越熱門，N(i)越大

def UserSimilarity(train):    # build inverse table for item_users    item_users = dict()    for u, items in train.items():        for i in items.keys():            if i not in item_users:                item_users[i] = set()            item_users[i].add(u)    #calculate co-rated items between users    C = dict()    N = dict()    for i, users in item_users.items():        for u in users:            N[u] += 1            for v in users:                if u == v:                    continue            C[u][v] += 1 / math.log(1 + len(users))    #calculate finial similarity matrix W    W = dict()    for u, related_users in C.items():        for v, cuv in related_users.items():            W[u][v] = cuv / math.sqrt(N[u] * N[v])    return W