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

在如今資訊量呈爆炸式增長的時代，谷歌百度等搜尋引擎為人們查找資訊提供了便利，幫助使用者快速查找有價值的資訊。然而此類查詢方式是大衆化的，無法根據個人興趣為使用者展示相關的資訊，此外搜尋引擎要求使用者給出明确的資訊需求或者是關鍵字。推薦系統則用于提供個性化的資訊，可通過分析使用者行為或社交關系在使用者需求不明确的情況下為使用者提供資訊。傳統的推薦算法包括基于内容的推薦算法和基于協同過濾的推薦算法以及混合推薦。這篇部落客要是對協同過濾算法進行介紹，進一步的，協同過濾又可分為基于使用者和基于物品兩類。

基于使用者的協同過濾推薦算法代碼借鑒于Danni_hgc的電影推薦算法執行個體代碼

基于物品的推薦算法代碼主要借鑒于海天一樹X

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

基本思想

基于使用者的協同過濾推薦算法的基本思想就是根據使用者朋友的興趣愛好來推測使用者的興趣愛好，在日常生活中，當你的朋友看了某部電影時，往往會将這部電影分享給你，而你去觀看這部電影的機率也會高于陌生人為你推薦這部電影（除電影本來就有很高的熱度以外）。簡而言之，可以說相似的使用者具有相同的興趣。基于使用者的協同過濾方法可分為兩個步驟：

1.計算使用者與目标使用者之間的相似度。

2.将與目标使用者興趣相似的使用者喜歡且目标使用者未接觸的物品推薦給目标使用者。

可以通過計算餘弦相似度，或者是傑卡德相似系數等方式來計算使用者之間的相似度，設 N(u) 為使用者 u 喜歡的物品集合，N(v) 為使用者 v 喜歡的物品集合，Wuv表示使用者u和使用者v之間的相似度：

1）餘弦相似度

2）傑卡德相似系數

計算餘弦相似度的代碼：

def calcCosDistSpe(user1,user2):
    avg_x=0.0
    avg_y=0.0
    for key in user1:
        avg_x+=key[1]
    avg_x=avg_x/len(user1)

    for key in user2:
        avg_y+=key[1]
    avg_y=avg_y/len(user2)

    u1_u2=0.0
    for key1 in user1:
        for key2 in user2:
            if key1[1] > avg_x and key2[1]>avg_y and key1[0]==key2[0]:
                u1_u2+=1
    u1u2=len(user1)*len(user2)*1.0
    sx_sy=u1_u2/math.sqrt(u1u2)
    return sx_sy
           

推薦物品，計算出使用者相似度之後，需要找出與使用者最相似的k個鄰居，并将k個鄰居看過且使用者感興趣程度較高的電影（除開使用者看過的電影）推薦給使用者。

尋找使用者最相似的k個鄰居代碼如下:

def calcNearestNeighbor(userid,users_dic,item_dic):
    neighbors=[]
    #neighbors.append(userid)
    for item in users_dic[userid]:
        for neighbor in item_dic[item[0]]:
            if neighbor != userid and neighbor not in neighbors:
                neighbors.append(neighbor)

    neighbors_dist=[]
    for neighbor in neighbors:
        dist=calcCosDistSpe(users_dic[userid],users_dic[neighbor])
        neighbors_dist.append([dist,neighbor])
    neighbors_dist.sort(reverse=True)
    return  neighbors_dist
           

算法實作

資料介紹

資料：mk-100k

u.data内容

user id movie id 評分 其他

196 242 3 881250949

186 302 3 891717742

22 377 1 878887116

244 51 2 880606923

166 346 1 886397596

u.item内容

movie_id movie_name release

1|Toy Story (1995)|01-Jan-1995|

2|GoldenEye (1995)|01-Jan-1995|

3|Four Rooms (1995)|01-Jan-1995|

完整代碼

# -*- coding=utf-8 -*-

import math
from texttable import Texttable

#   讀取檔案
def readFile(file_name):
    contents_lines=[]
    f=open(file_name,"r",encoding='ISO-8859-1')#The encoding was "ISO-8859-1"
    contents_lines=f.readlines()
    f.close()
    return contents_lines
#
#   解壓rating資訊，格式：使用者id\t電影id\t使用者rating\t時間
#   輸入：資料集合
#   輸出:已經解壓的排名資訊
#
def getRatingInformation(ratings):
    rates=[]
    for line in ratings:
        rate=line.split("\t")
        rates.append([int(rate[0]),int(rate[1]),int(rate[2])])
    return rates
#
#   生成使用者評分的資料結構
#
#   輸入:所有資料 [[2,1,5],[2,4,2]...]
#   輸出:1.使用者打分字典 2.電影字典
#   使用字典，key是使用者id，value是使用者對電影的評價，
#   rate_dic[2]=[(1,5),(4,2)].... 表示使用者2對電影1的評分是5，對電影4的評分是2
#
def createUserRankDic(rates):
    user_rate_dic={}
    item_to_user={}
    for i in rates:
        user_rank=(i[1],i[2])#電影id和評分
        if i[0] in user_rate_dic:
            user_rate_dic[i[0]].append(user_rank)
        else:
            user_rate_dic[i[0]]=[user_rank]

        if i[1] in item_to_user:
            item_to_user[i[1]].append(i[0])
        else:
            item_to_user[i[1]]=[i[0]]

    return user_rate_dic,item_to_user
#   使用UserFC進行推薦
#   輸入：檔案名,使用者ID,鄰居數量
#   輸出：推薦的電影ID,輸入使用者的電影清單,電影對應使用者的反序表，鄰居清單
#
def recommendByUserFC(file_name,userid,k=5):

    #讀取檔案資料
    test_contents=readFile(file_name)

    #檔案資料格式化成二維數組 List[[使用者id,電影id,電影評分]...]
    test_rates=getRatingInformation(test_contents)

    #格式化成字典資料
    #    1.使用者字典：dic[使用者id]=[(電影id,電影評分)...]
    #    2.電影字典：dic[電影id]=[使用者id1,使用者id2...]
    test_dic,test_item_to_user=createUserRankDic(test_rates)

    #尋找鄰居
    neighbors=calcNearestNeighbor(userid,test_dic,test_item_to_user)[:k]

    recommend_dic={}
    for neighbor in neighbors:
        neighbor_user_id=neighbor[1]
        movies=test_dic[neighbor_user_id]
        for movie in movies:
            #print movie
            if movie[0] not in recommend_dic:
                recommend_dic[movie[0]]=neighbor[0]
            else:
                recommend_dic[movie[0]]+=neighbor[0]
    #print len(recommend_dic)

    #建立推薦清單
    recommend_list=[]
    for key in recommend_dic:
        #print key
        recommend_list.append([recommend_dic[key],key])


    recommend_list.sort(reverse=True)
    #print recommend_list
    user_movies = [ i[0] for i in test_dic[userid]]

    return [i[1] for i in recommend_list],user_movies,test_item_to_user,neighbors
#   擷取電影的清單
def getMoviesList(file_name):
    #print sys.getdefaultencoding()
    movies_contents=readFile(file_name)
    movies_info={}
    for movie in movies_contents:
        movie_info=movie.split("|")
        movies_info[int(movie_info[0])]=movie_info[1:]
    return movies_info
#主程式
#輸入 ： 測試資料集合
if __name__ == '__main__':
    movies=getMoviesList("D:/PycharmProject/recomender system/data/ml-100k/u.item")
    recommend_list,user_movie,items_movie,neighbors=recommendByUserFC("D:/PycharmProject/recomender system/data/ml-100k/u.data",305,80)
    # 推薦清單（電影，使用者相似度），使用者看的所有電影，看某電影的所有使用者，使用者鄰居（相似度，鄰居id）
    neighbors_id=[ i[1] for i in neighbors]
    table = Texttable()
    table.set_deco(Texttable.HEADER)
    table.set_cols_dtype(['t',  # text
                          't',  # float (decimal)
                          't']) # automatic
    table.set_cols_align(["l", "l", "l"])
    rows=[]
    rows.append([u"movie name",u"release", u"from userid"])
    for movie_id in recommend_list[:20]:#尋找與推薦項目相關的鄰居使用者
        from_user=[]
        for user_id in items_movie[movie_id]:
            if user_id in neighbors_id:
                from_user.append(user_id)
        rows.append([movies[movie_id][0],movies[movie_id][1],from_user[0:5]])#隻顯示與推薦結果相關的5個鄰居使用者
    table.add_rows(rows)
    print (table.draw())
           

運作結果

from userid表示這些使用者都看過這些電影，為了結果的美觀，隻列印了五個使用者id。

上述計算使用者相似度時僅僅考慮到使用者與項目之間的關系，而忽略了外在因素。比如最近新上映了兩部大導演制作的電影，該導演具有很高的知名度且作品宣傳力度大，是以很多使用者都會選擇去看這兩部電影，此時根據使用者A和使用者B都觀看了電影，就簡單的認為兩個使用者相似比較局限。

基于物品的協同過濾推薦算法

基本思想

基于物品的推薦算法主要是根據使用者的曆史行為資訊來推測使用者未來的興趣，将基于物品的協同過濾推薦算法應用于電影推薦中，最基本的思想就是為使用者推薦最近看過的電影清單中相似的電影。該方法也可分為計算物品相似度和物品推薦兩個步驟，計算物品相似度的方法與計算使用者相似度的方法類似。

算法實作

基于物品的協同過濾算法使用的資料集同上，不再作詳細的介紹。

1.擷取電影的清單

def getMoviesList(file_name):
    #print sys.getdefaultencoding()
    movies_contents=readFile(file_name)
    movies_info={}
    for movie in movies_contents:
        movie_info=movie.split("|")
        movies_info[int(movie_info[0])]=movie_info[1:]
    return movies_info
           

2.讀取資料

def readData(self):
        # 讀取檔案，并生成使用者-物品的評分表和測試集
        self.train = dict()
        # 使用者-物品的評分表
        for line in open(self.train_file):
            user, item, score,other = line.strip().split("\t")
            self.train.setdefault(user, {})
            self.train[user][item] = int(float(score))
           

3.3.計算物品相似度

def ItemSimilarity(self):
        # 建立物品-物品的共現矩陣
        cooccur = dict()  # 物品-物品的共現矩陣
        buy = dict()  # 物品被多少個不同使用者購買N
        for user, items in self.train.items():
            for i in items.keys():
                buy.setdefault(i, 0)
                buy[i] += 1
                cooccur.setdefault(i, {})
                for j in items.keys():
                    if i == j: continue
                    cooccur[i].setdefault(j, 0)
                    cooccur[i][j] += 1
        # 計算相似度矩陣
        self.similar = dict()
        for i, related_items in cooccur.items():
            self.similar.setdefault(i, {})
            for j, cij in related_items.items():
                self.similar[i][j] = cij / (math.sqrt(buy[i] * buy[j]))
        return self.similar
           

4.給使用者做推薦

給使用者user推薦，前K個相關使用者，前N個物品
    def Recommend(self, user, K=3, N=10):
        rank = dict()
        action_item = self.train[user]
        # 使用者user産生過行為的item和評分
        for item, score in action_item.items():
            sortedItems = sorted(self.similar[item].items(), key=lambda x: x[1], reverse=True)[0:K]
            for j, wj in sortedItems:
                if j in action_item.keys():
                    continue
                rank.setdefault(j, 0)
                rank[j] += score * wj
        return dict(sorted(rank.items(), key=lambda x: x[1], reverse=True)[0:N])
           

5.建立表格，顯示推薦結果

table = Texttable()
table.set_deco(Texttable.HEADER)
table.set_cols_dtype(['t',  # text
                      't']) # automatic
table.set_cols_align(["l", "l"])
rows=[]
rows.append([u"movie name",u"release"])
           

6.main()函數

movies=getMoviesList("D:/PycharmProject/recomender system/data/ml-100k/u.item")#得到電影Item的資訊
item = ItemBasedCF("D:/PycharmProject/recomender system/data/ml-100k/u.data")
item.ItemSimilarity()
recommedDict = item.Recommend("166")
for movieid in recommedDict:
    movieid=int(movieid)
    rows.append([movies[movieid][0], movies[movieid][1]])
table.add_rows(rows)
print(table.draw())
           

結果展示

結論

基于物品的推薦算法可以預先計算所有物品之間的相似度，對于線上實驗來說，基于物品的協同過濾推薦算法優于基于使用者的協同過濾算法，但二者都面臨着資料稀疏性和冷啟動問題。此外，傳統的這兩類算法的推薦覆寫率和多樣性低，難以解決長尾問題。長尾理論中的頭部代表的是絕大部分使用者的日常需求，尾部則代表少數使用者的個性化需求。