姓名：崔少杰 ? ? ? 學(xué)號(hào)：16040510021

轉(zhuǎn)載自：http://www.reibang.com/p/79d24fa3664f=有修改

【嵌牛導(dǎo)讀】：基于用戶的協(xié)同過濾算法（User-CF）屬于基于領(lǐng)域的算法诽表⌒较Γ基于用戶的協(xié)同過濾算法主要包括兩個(gè)步驟。找到和目標(biāo)用戶興趣相似的用戶集合隔箍。找到這個(gè)集合中的用戶喜歡的寺酪，且目標(biāo)用戶沒有聽說過的物品推薦給目標(biāo)用戶坎背。

【嵌牛鼻子】：協(xié)同過濾算法、皮爾遜相關(guān)度

【嵌牛提問】：如何簡單實(shí)現(xiàn)基于用戶的協(xié)同過濾算法寄雀？

【嵌牛正文】：相似度算法

步驟一的關(guān)鍵就是計(jì)算兩個(gè)用戶之間的相似度得滤，以下列舉兩種比較常見的相似度計(jì)算方法。

給定用戶u和用戶v咙俩，令N(u)表示用戶u曾經(jīng)有過正反饋的物品集合耿戚，令N(v)為用戶v曾經(jīng)有過正反饋的物品集合。

Jaccard公式

Jaccard公式

余弦相似度

余弦相似度

另外還有一種基于向量的相似度算法阿趁，也是在代碼實(shí)現(xiàn)中將使用的相似度計(jì)算方法膜蛔。具體的關(guān)于Pearson相關(guān)系數(shù)的介紹會(huì)在下文中闡述。

Pearson相關(guān)系數(shù)

Pearson相關(guān)系數(shù)

關(guān)于這三種相似度之間的差別和選擇標(biāo)準(zhǔn)脖阵，自己也還沒有仔細(xì)去研究皂股。之后有時(shí)間的話會(huì)補(bǔ)充。

計(jì)算舉例

計(jì)算單獨(dú)的兩個(gè)用戶之間的相似度

下面將簡單介紹利用余弦相似度計(jì)算方法得到兩個(gè)用戶之間的相似度命黔。

計(jì)算舉例

例如呜呐，用戶A對(duì)物品{a,b,d}有過行為，用戶B對(duì)物品{a,c}有過行為悍募，利用余弦相似度公式計(jì)算用戶A和用戶B的興趣相似度為：

A和B之間的相似度

同理蘑辑，我們可以算出用戶A和用戶C、D的相似度：

A和C坠宴、D之間的相似度

計(jì)算用戶兩兩之間的相似度矩陣

對(duì)兩兩用戶都利用余弦相似度計(jì)算相似度洋魂。這種方法的時(shí)間復(fù)雜度是O(N^2)。耗時(shí)很大喜鼓。

因此我們需要建立一張物品到用戶之間的倒排表副砍，這樣就能排除對(duì)根本沒有任何聯(lián)系的用戶之間的相似度計(jì)算。

再根據(jù)倒排表計(jì)算共同評(píng)分過的物品的矩陣庄岖。

如下圖所示

計(jì)算共同評(píng)分過的物品的矩陣

矩陣中的每一個(gè)數(shù)值都是余弦相似度中的分子部分豁翎，然后將分子除以分母可以得到最終的用戶興趣相似度。

即可以將上圖中的共同評(píng)分過的物品的矩陣轉(zhuǎn)換為用戶之間的相似度矩陣隅忿，且只用計(jì)算非0的部分心剥。

例如，計(jì)算A與B的用戶相似度背桐。用戶A和B的矩陣中的值為1刘陶，即他們共同交集的物品為1。A總共評(píng)分過的物品為3牢撼，B總共評(píng)分過的物品為2匙隔。根據(jù)余弦相似度算法，得出相似度為

計(jì)算結(jié)果

篩選出K個(gè)與目標(biāo)用戶最相似的用戶

得到了用戶之間的相似度后熏版，算法會(huì)給用戶推薦和他興趣最相似的K個(gè)用戶喜歡的物品

以下公式度量了算法中用戶u對(duì)物品i的感興趣程度

用戶u對(duì)物品i的感興趣程度

其中纷责，S(u,K)包含和用戶u興趣最相近的K個(gè)用戶，N(i)是對(duì)物品i有過行為的用戶集合撼短，Wuv是用戶u和用戶v的興趣相似度再膳，rvi為1

舉例

對(duì)目標(biāo)用戶A進(jìn)行推薦。選取K=3曲横，用戶A對(duì)物品c喂柒，e沒有過行為不瓶，因此可以把這兩個(gè)物品推薦給用戶A。根據(jù)算法灾杰，用戶A對(duì)物品c蚊丐，e的興趣是

用戶A對(duì)物品c，e的興趣

基于豆瓣圖書評(píng)論數(shù)據(jù)的簡單實(shí)現(xiàn)

評(píng)論數(shù)據(jù)格式介紹

自己對(duì)評(píng)論數(shù)據(jù)作了一個(gè)簡單的清洗艳吠，數(shù)據(jù)格式如下：

圖書名+用戶名+評(píng)分信息+評(píng)分時(shí)間

中間以"\t"作為分隔符

部分圖書數(shù)據(jù)如下圖所示

部分圖書數(shù)據(jù)

使用Pearson相關(guān)系數(shù)計(jì)算用戶相似度

之前介紹的協(xié)同過濾算法并沒有引進(jìn)評(píng)分的概念麦备，引進(jìn)評(píng)分之后，就不能簡單地利用集合去計(jì)算了昭娩，而是應(yīng)該利用向量去計(jì)算凛篙。

Pearson相關(guān)系數(shù)將兩個(gè)用戶共同評(píng)分的n個(gè)項(xiàng)目看做一組向量，計(jì)算兩個(gè)用戶在這n個(gè)項(xiàng)目上評(píng)分的相關(guān)性栏渺，減去用戶平均評(píng)分是基于用戶評(píng)分尺度的考量呛梆，公式如下：

Pearson相關(guān)系數(shù)

其中Iuv是用戶u和v都評(píng)過分的項(xiàng)目的集合，ru是用戶u所有評(píng)分的平均分

計(jì)算用戶u對(duì)物品i評(píng)分的預(yù)測(cè)

得到用戶相似度后磕诊，接下來就是根據(jù)目標(biāo)用戶u的近鄰用戶得到u對(duì)于物品i的評(píng)分預(yù)測(cè)削彬，公式如下：

用戶u對(duì)物品i的評(píng)分預(yù)測(cè)

評(píng)分預(yù)測(cè)越高，目標(biāo)用戶u喜歡該物品的概率也就越高秀仲。

最終按照評(píng)分預(yù)測(cè)的高低可得到最適合推薦給用戶u的物品列表融痛，在這個(gè)實(shí)例里也就是圖書列表。

Python實(shí)現(xiàn)

導(dǎo)入數(shù)據(jù)

導(dǎo)入的原始數(shù)據(jù)為訓(xùn)練集（trainSet）神僵，利用該訓(xùn)練集生成圖書-用戶倒排表（bookUser）雁刷，再利用倒排表生成用戶-用戶共同評(píng)分過的圖書矩陣（u2u）

# encoding=utf-8frommathimportsqrtimportcodecsdefloadData():# 訓(xùn)練集trainSet = {}# 看過該本書的所有用戶集合bookUser = {}# 用戶-用戶共有書籍矩陣u2u = {}? ? TrainFile ='/Users/cjl/Desktop/comments.txt'# 加載訓(xùn)練集# trainset {"userName", {"bookName, rating"}}# bookUser {"bookName", ["username1", "username2", ...]} 即為物品-用戶倒排表forlineincodecs.open(TrainFile,"r","utf-8"):? ? ? ? (bookName, userName, rating, timestamp) = line.strip().split("\t")? ? ? ? trainSet.setdefault(userName, {})? ? ? ? trainSet[userName].setdefault(bookName, float(rating))? ? ? ? bookUser.setdefault(bookName, [])? ? ? ? bookUser[bookName].append(userName.strip())# 生成用戶-用戶共有書籍矩陣forbinbookUser.keys():# 遍歷特定的書籍中所有的用戶foruinbookUser[b]:? ? ? ? ? ? u2u.setdefault(u, {})forninbookUser[b]:ifu != n:? ? ? ? ? ? ? ? ? ? u2u[u].setdefault(n,[])? ? ? ? ? ? ? ? ? ? u2u[u][n].append(b)returntrainSet, u2u

簡單測(cè)試導(dǎo)入的數(shù)據(jù)以及生成的u2u是否正確

測(cè)試導(dǎo)入數(shù)據(jù)

計(jì)算一個(gè)用戶的平均評(píng)分

defgetAverageRating(user, trainSet):average = (sum(trainSet[user].values())*1.0) / len(trainSet[user].keys())returnaverage

簡單測(cè)試

簡單測(cè)試

計(jì)算用戶相似度

遍歷u2u，利用皮爾遜相關(guān)系數(shù)的計(jì)算保礼，將共同評(píng)分過的書籍矩陣轉(zhuǎn)換為兩個(gè)用戶之間的相似度矩陣

# 計(jì)算用戶相似度defgetUserSim(u2u, trainSet):userSim = {}# 計(jì)算用戶相似度# 對(duì)每個(gè)用戶uforuinu2u.keys():ifu !='':# 將用戶u加入userSim中設(shè)為key沛励，該用戶對(duì)應(yīng)一個(gè)字典userSim.setdefault(u, {})# 獲取用戶u對(duì)電影的平均評(píng)分average_u_rate = getAverageRating(u, trainSet)# 對(duì)與用戶u相關(guān)的每個(gè)用戶nforninu2u[u].keys():ifn !='':# 將用戶n加到用戶u的字典中userSim[u].setdefault(n,0)# 獲取用戶n對(duì)電影的平均評(píng)分average_n_rate = getAverageRating(n, trainSet)# 皮爾遜相關(guān)系數(shù)的分子部分part1 =0# 皮爾遜相關(guān)系數(shù)的分母的一部分part2 =0# 皮爾遜相關(guān)系數(shù)的分母的一部分part3 =0# 對(duì)用戶u和用戶n的共有的每個(gè)電影forminu2u[u][n]:? ? ? ? ? ? ? ? ? ? ? ? part1 += (trainSet[u][m] - average_u_rate) * (trainSet[n][m] - average_n_rate) *1.0part2 += pow(trainSet[u][m] - average_u_rate,2) *1.0part3 += pow(trainSet[n][m] - average_n_rate,2) *1.0part2 = sqrt(part2)? ? ? ? ? ? ? ? ? ? part3 = sqrt(part3)# 若分母為0，相似度為0ifpart2 ==0orpart3 ==0:? ? ? ? ? ? ? ? ? ? ? ? userSim[u][n] =0else:? ? ? ? ? ? ? ? ? ? ? ? userSim[u][n] = part1 / (part2 * part3)returnuserSim

簡單測(cè)試

輸出相似用戶

尋找最近鄰用戶并生成推薦結(jié)果

遍歷trainSet中的所有用戶炮障，生成一個(gè)評(píng)分預(yù)測(cè)pred

# 尋找用戶最近鄰并生成推薦結(jié)果defgetRecommendations(N, trainSet, userSim):pred = {}# 對(duì)每個(gè)用戶foruserintrainSet.keys():# 生成空預(yù)測(cè)表pred.setdefault(user, {})# 獲取該用戶評(píng)過分的書籍interacted_items = trainSet[user].keys()# 獲取該用戶的平均評(píng)分average_u_rate = getAverageRating(user, trainSet)? ? ? ? userSimSum =0# 選取N個(gè)最相似的用戶# lambda x:x[1] 根據(jù)用戶相似度進(jìn)行比較ifuser.strip() !='':? ? ? ? ? ? simUser = sorted(userSim[user.strip()].items(), key=lambdax: x[1], reverse=True)[0:N]# 遍歷相似用戶的用戶名和相似度forn, siminsimUser:# 得到該近鄰用戶的平均評(píng)分average_n_rate = getAverageRating(n, trainSet)# 對(duì)該用戶所有近鄰用戶相似度求和userSimSum += sim# 遍歷該近鄰用戶的所有評(píng)分書籍和具體評(píng)分form, nratingintrainSet[n].items():# 如果這本書該用戶已經(jīng)看過目派，則跳過ifmininteracted_items:continue# 否則將這本書以及這本書的推薦指數(shù)加到這名用戶的推薦列表中else:? ? ? ? ? ? ? ? ? ? ? ? pred[user].setdefault(m,0)? ? ? ? ? ? ? ? ? ? ? ? pred[user][m] += (sim * (nrating - average_n_rate))# 遍歷這名用戶推薦列表中的所有書籍，更新評(píng)分預(yù)測(cè)forminpred[user].keys():ifuserSimSum ==0:? ? ? ? ? ? ? ? ? ? pred[user][m] = average_u_rateelse:? ? ? ? ? ? ? ? ? ? pred[user][m] = average_u_rate + (pred[user][m] *1.0) / userSimSumreturnpred

簡單測(cè)試

輸出推薦書籍