推薦算法--基于使用者的協同過濾算法

      基于鄰域的算法分為兩大類，一類是基于使用者的協同過濾算法，另一類是基于物品的協同過濾算法。

我們先來看看基于使用者的協同過濾算法，基于物品的協同過濾算法大體思路和基于使用者的差不多，可以自己參考對比學習。

基于使用者的協同過濾算法

      每年新學期開始，剛進實驗室的師弟總會問師兄相似的問題，比如“我應該買什麼專業書啊”、“我應該看什麼論文啊”等。這個時候，師兄一般會給他們做出一些推薦。這就是現實中個性化推薦的一種例子。在這個例子中，師弟可能會請教很多師兄，然後做出最終的判斷。師弟之是以請教師兄，一方面是因為他們有社會關系，互相認識且信任對方，但更主要的原因是師兄和師弟有共同的研究領域和興趣。那麼，在一個線上個性化推薦系統中，當一個使用者A需要個性化推薦時，可以先找到和他有相似興趣的其他使用者，然後把那些使用者喜歡的、而使用者A沒有聽說過的物品推薦給A。這種方法稱為基于使用者的協同過濾算法。

基于使用者的協同過濾算法主要包括兩個步驟。

(1) 找到和目标使用者興趣相似的使用者集合。

(2) 找到這個集合中的使用者喜歡的，且目标使用者沒有聽說過的物品推薦給目标使用者。

步驟(1)的關鍵就是計算兩個使用者的興趣相似度。這裡，協同過濾算法主要利用行為的相似度計算興趣的相似度。給定使用者u和使用者v，令N(u)表示使用者u曾經有過正回報的物品集合，令N(v)為使用者v曾經有過正回報的物品集合。那麼，我們可以通過如下的Jaccard公式簡單地計算u和v的興趣相似度或者通過餘弦公式：

      jaccard                                                                             餘項公式：

：

這個一個行為記錄                                             我們可以根據餘弦公式計算如下

以餘弦相似度為例，實作該相似度可以利用下面的僞代碼：

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      

     這種方法的時間複雜度是O(|U|*|U|)，這在使用者數很大時非常耗時。事實上，很多使用者互相之間并沒有對同樣的物品産生過行為，即很多時候N(u)^ N(v) = 0。上面的算法将很多時間浪費在了計算這種使用者之間的相似度上。如果換一個思路，我們可以首先計算出N(u)^ N(v) != 0 的使用者對(u,v)，然後再對這種情況除以分母sqrt(N(u)*N(v)) 。

      為此，可以首先建立物品到使用者的倒排表，對于每個物品都儲存對該物品産生過行為的使用者清單。令稀疏矩陣C[u][v]= N(u)^ N(v) 。那麼，假設使用者u和使用者v同時屬于倒排表中K個物品對應的使用者清單，就有C[u][v]=K。進而，可以掃描倒排表中每個物品對應的使用者清單，将使用者清單中的兩兩使用者對應的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的興趣，因為使用的是單一行為的隐回報資料，是以所有的Rvi=1。

如下代碼實作了上面的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。根據UserCF算法，使用者A對物品c、e的興趣是：

使用者相似度計算的改進

    如果兩個使用者都曾經買過《新華字典》，這絲毫不能說明他們興趣相似，因為絕大多數中國人小時候都買過《新華字典》。但如果兩個使用者都買過《資料挖掘導論》，那可以認為他們的興趣比較相似，因為隻有研究資料挖掘的人才會買這本書。換句話說，兩個使用者對冷門物品采取過同樣的行為更能說明他們興趣的相似度。是以，John S. Breese在論文①中提出了如下公式，根據使用者行為計算使用者的興趣相似度：

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