【Python算法】協同過濾算法——基于物品的協同過濾算法

【Python算法】協同過濾算法——基于物品的協同過濾算法

推薦算法背景：

互聯網的迅猛發展將人類帶入了信息社會和網絡經濟時代，信息化影響到了生活的方方面面。但是隨著互聯網產業的擴大，為用戶提供更多選的同時也帶來了篩選與推薦的難題。于是便提出了推薦算法幫助用戶快速找到自己喜愛的東西。例如京東、淘寶、美團等，在用戶購買物品后，均會給用戶推薦他們可能喜歡的物品，不僅免去了用戶不斷查找類似物品的煩惱，而且也使得用戶可以貨比多家，最終找到自己物美價廉的商品，而相關的網站平臺也可以提升自己的銷量。電影推薦也是比較常見的，例如用戶觀看了阿甘正傳，可能推薦給用戶肖申克的救贖、當幸福來敲門等，推薦相關的應用數不勝數，但其核心就是相關的推薦算法的組合。

目前有關個性化推薦算法主要分為三大類：

1.基于協同過濾的推薦；

2.基于內容過濾的推薦；

3.社會化推薦。

本文主要討論基于協同過濾的推薦，而該算法也可以劃分為兩類：

這里主要介紹基于物品的協同過濾算法（ItemCF）：

內容過濾根據信息資源與用戶興趣的相似性來推薦商品，通過計算用戶興趣模型和商品特征向量之間的向量相似性，主動將相似度高的商品發送給該模型的客戶。由于每個客戶都獨立操作，擁有獨立的特征向量，不需要考慮別的用戶的興趣，不存在評價級別多少的問題，能推薦新的項目或者是冷門的項目。這些優點使得基于內容過濾的推薦系統不受冷啟動和稀疏問題的影響

實驗工具

1.python

Python是一種計算機程序設計語言。是一種動態的、面向對象的腳本語言，最初被設計用于編寫自動化腳本(shell)，隨著版本的不斷更新和語言新功能的添加，越來越多被用于獨立的、大型項目的開發。Python已經成為最受歡迎的程序設計語言之一。自從2004年以后，python的使用率呈線性增長。2011年1月，它被TIOBE編程語言排行榜評為2010年度語言。

由于Python語言的簡潔性、易讀性以及可擴展性，在國外用Python做科學計算的研究機構日益增多，一些知名大學已經采用Python來教授程序設計課程。例如卡耐基梅隆大學的編程基礎、麻省理工學院的計算機科學及編程導論就使用Python語言講授。　　眾多開源的科學計算軟件包都提供了Python的調用接口，例如著名的計算機視覺庫OpenCV、三維可視化庫VTK、醫學圖像處理庫ITK。而Python專用的科學計算擴展庫就更多了，例如如下3個十分經典的科學計算擴展庫：NumPy、SciPy和matplotlib，它們分別為Python提供了快速數組處理、數值運算以及繪圖功能。因此Python語言及其眾多的擴展庫所構成的開發環境十分適合工程技術、科研人員處理實驗數據、制作圖表，甚至開發科學計算應用程序。

jupyter

Jupyter Notebook（此前被稱為 IPython notebook）是一個交互式筆記本，支持運行 40 多種編程語言。

Jupyter Notebook 的本質是一個 Web 應用程序，便于創建和共享文學化程序文檔，支持實時代碼，數學方程，可視化和 markdown。 用途包括：數據清理和轉換，數值模擬，統計建模，機器學習等等

基于物品的推薦算法以及流程

例如前面背景中介紹的，用戶喜歡看阿甘正傳，且給了高評分后，那么系統將會尋找與阿甘正傳類似的電影推薦給用戶。

算法流程

構建用戶–>物品的倒排；

構建物品與物品的同現矩陣；

計算物品之間的相似度，即計算相似矩陣；

根據用戶的歷史記錄，給用戶推薦物品；

構建用戶–>物品的倒排

如下表，行表示用戶，列表示物品，1表示用戶喜歡該物品

例如python構建的數據格式如下 { 'A':?{'a':?'1',?'b':?'1',?'d':?'1'},? 'B':?{'c':?'1',?'b':?'1',?'e':?'1'},? 'C':?{'c':?'1',?'d':?'1'},? 'D':?{'c':?'1',?'b':?'1',?'d':?'1'}, 'E':?{'a':?'1',?'d':?'1'} }

構建物品與物品的同現矩陣

共現矩陣C表示同時喜歡兩個物品的用戶數，是根據用戶物品倒排表計算出來的。如根據上面的用戶物品倒排表可以計算出如下的共現矩陣C：

計算物品之間的相似度，即計算相似矩陣

其中兩個物品之間的相似度如何計算？

設|N(i)|表示喜歡物品i的用戶數，|N(i)?N(j)|表示同時喜歡物品i，j的用戶數，則物品i與物品j的相似度為：

(1)式有一個問題，當物品j是一個很熱門的商品時，人人都喜歡，那么wij就會很接近于1，即(1)式會讓很多物品都和熱門商品有一個很大的相似度，所以可以改進一下公式：

算法流程2中的共現矩陣C其實就是式(2)的分子，矩陣N（用于計算分母）表示喜歡某物品的用戶數（是總的用戶數），則(2)式中的分母便很容易求解出來了。

矩陣N如下所示：

利用式（2）便能計算物品之間的余弦相似矩陣如下：

根據用戶的歷史記錄，給用戶推薦物品；

最終推薦的是什么物品，是由預測興趣度決定的。

物品j預測興趣度=用戶喜歡的物品i的興趣度×物品i和物品j的相似度

例如：A用戶喜歡a，b，d ，興趣度分別為1,1,1

推薦c的預測興趣度=1X0.67+1X0.58=1.25

推薦e的預測興趣度=1X0.58=0.58

python實現算法

數據描述

該數據為用戶，興趣度，物品

#用戶，興趣度，物品 ????uid_score_bid?=?['A,1,a',?'A,1,b',?'A,1,d',?'B,1,b',?'B,1,c',?'B,1,e',?'C,1,c',?'C,1,d',?'D,1,b',?'D,1,c',?'D,1,d', ?????????????????????'E,1,a',?'E,1,d']

2.python實現物品推薦

#?-*-?coding:?UTF-8?-*- ????from?math?import?sqrt ????import?operator ????#?用戶，興趣度，物品 ????uid_score_bid?=?['A,1,a',?'A,1,b',?'A,1,d',?'B,1,b',?'B,1,c',?'B,1,e',?'C,1,c',?'C,1,d',?'D,1,b',?'D,1,c',?'D,1,d', ?????????????????????'E,1,a',?'E,1,d'] ????#?1.構建用戶-->物品的倒排 ????def?loadData(files): ????????data?=?{} ????????for?line?in?files: ????????????user,score,item?=?line.split(",") ????????????data.setdefault(user,{}) ????????????data[user][item]?=?score ????????print("----1.用戶：物品的倒排----") ????????print(data) ????????return?data ????#?2.1?構造物品-->物品的共現矩陣 ????#?2.2?計算物品與物品的相似矩陣 ????def?similarity(data): ????????#?2.1?構造物品：物品的共現矩陣 ????????N?=?{}??#?喜歡物品i的總人數 ????????C?=?{}??#?喜歡物品i也喜歡物品j的人數 ????????for?user,item?in?data.items(): ????????????for?i,score?in?item.items(): ????????????????N.setdefault(i,0) ????????????????N[i]?+=?1 ????????????????C.setdefault(i,{}) ????????????????for?j,scores?in?item.items(): ????????????????????if?j?not?in?i: ????????????????????????C[i].setdefault(j,0) ????????????????????????C[i][j]?+=?1 ????????print("---2.構造的共現矩陣---") ????????print?('N:',N) ????????print?('C',C) ????????#?2.2?計算物品與物品的相似矩陣 ????????W?=?{} ????????for?i,item?in?C.items(): ????????????W.setdefault(i,{}) ????????????for?j,item2?in?item.items(): ????????????????W[i].setdefault(j,0) ????????????????W[i][j]?=?C[i][j]/sqrt(N[i]*N[j]) ????????print("---3.構造的相似矩陣---") ????????print(W) ????????return?W ????#?3.根據用戶的歷史記錄，給用戶推薦物品 ????def?recommandList(data,W,user,k=3,N=10): ????????rank?=?{} ????????for?i,score?in?data[user].items():??#?獲得用戶user歷史記錄，如A用戶的歷史記錄為{'a':?'1',?'b':?'1',?'d':?'1'} ????????????for?j,w?in?sorted(W[i].items(),key=operator.itemgetter(1),reverse=True)[0:k]:??#?獲得與物品i相似的k個物品 ????????????????if?j?not?in?data[user].keys():??#?該相似的物品不在用戶user的記錄里 ????????????????????rank.setdefault(j,0) ????????????????????rank[j]?+=?float(score)?*?w ????????print("---4.推薦----") ????????print(sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N]) ????????return?sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N] ????if?__name__?==?'__main__': ????????#?用戶，興趣度，物品 ????????uid_score_bid?=?['A,1,a',?'A,1,b',?'A,1,d',?'B,1,b',?'B,1,c',?'B,1,e',?'C,1,c',?'C,1,d',?'D,1,b',?'D,1,c',?'D,1,d', ?????????????????????????'E,1,a',?'E,1,d'] ????????data?=?loadData(uid_score_bid)??#?獲得數據 ????????W?=?similarity(data)??#?計算物品相似矩陣 ????????recommandList(data,?W,?'A',?3,?10)??#推薦

運行結果如下圖：

電影推薦應用案例

1.電影數據描述

data?=?{'Lisa?Rose':?{'Lady?in?the?Water':?2.5,?'Snakes?on?a?Plane':?3.5, ??????????????????????????'Just?My?Luck':?3.0,?'Superman?Returns':?3.5,?'You,?Me?and?Dupree':?2.5, ??????????????????????????'The?Night?Listener':?3.0}, ????????????'Gene?Seymour':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?3.5, ?????????????????????????????'Just?My?Luck':?1.5,?'Superman?Returns':?5.0,?'The?Night?Listener':?3.0, ?????????????????????????????'You,?Me?and?Dupree':?3.5}, ????????????'Michael?Phillips':?{'Lady?in?the?Water':?2.5,?'Snakes?on?a?Plane':?3.0, ?????????????????????????????????'Superman?Returns':?3.5,?'The?Night?Listener':?4.0}, ????????????'Claudia?Puig':?{'Snakes?on?a?Plane':?3.5,?'Just?My?Luck':?3.0, ?????????????????????????????'The?Night?Listener':?4.5,?'Superman?Returns':?4.0, ?????????????????????????????'You,?Me?and?Dupree':?2.5}, ????????????'Mick?LaSalle':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?4.0, ?????????????????????????????'Just?My?Luck':?2.0,?'Superman?Returns':?3.0,?'The?Night?Listener':?3.0, ?????????????????????????????'You,?Me?and?Dupree':?2.0}, ????????????'Jack?Matthews':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?4.0, ??????????????????????????????'The?Night?Listener':?3.0,?'Superman?Returns':?5.0,?'You,?Me?and?Dupree':?3.5}, ????????????'Toby':?{'Snakes?on?a?Plane':?4.5,?'You,?Me?and?Dupree':?1.0,?'Superman?Returns':?4.0} ????????????}

2.推薦

推薦過程和上面的代碼過程一樣，僅不用構造倒排數據

demo.py:

#?-*-?coding:?UTF-8?-*- ????from?math?import?sqrt ????import?operator ????data?=?{'Lisa?Rose':?{'Lady?in?the?Water':?2.5,?'Snakes?on?a?Plane':?3.5, ??????????????????????????????'Just?My?Luck':?3.0,?'Superman?Returns':?3.5,?'You,?Me?and?Dupree':?2.5, ??????????????????????????????'The?Night?Listener':?3.0}, ????????????????'Gene?Seymour':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?3.5, ?????????????????????????????????'Just?My?Luck':?1.5,?'Superman?Returns':?5.0,?'The?Night?Listener':?3.0, ?????????????????????????????????'You,?Me?and?Dupree':?3.5}, ????????????????'Michael?Phillips':?{'Lady?in?the?Water':?2.5,?'Snakes?on?a?Plane':?3.0, ?????????????????????????????????????'Superman?Returns':?3.5,?'The?Night?Listener':?4.0}, ????????????????'Claudia?Puig':?{'Snakes?on?a?Plane':?3.5,?'Just?My?Luck':?3.0, ?????????????????????????????????'The?Night?Listener':?4.5,?'Superman?Returns':?4.0, ?????????????????????????????????'You,?Me?and?Dupree':?2.5}, ????????????????'Mick?LaSalle':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?4.0, ?????????????????????????????????'Just?My?Luck':?2.0,?'Superman?Returns':?3.0,?'The?Night?Listener':?3.0, ?????????????????????????????????'You,?Me?and?Dupree':?2.0}, ????????????????'Jack?Matthews':?{'Lady?in?the?Water':?3.0,?'Snakes?on?a?Plane':?4.0, ??????????????????????????????????'The?Night?Listener':?3.0,?'Superman?Returns':?5.0,?'You,?Me?and?Dupree':?3.5}, ????????????????'Toby':?{'Snakes?on?a?Plane':?4.5,?'You,?Me?and?Dupree':?1.0,?'Superman?Returns':?4.0} ????????????????} ????#?1.構建用戶-->物品的倒排（此推薦無需使用） ????def?loadData(files): ????????data?=?{} ????????for?line?in?files: ????????????user,score,item?=?line.split(",") ????????????data.setdefault(user,{}) ????????????data[user][item]?=?score ????????print("----1.用戶：物品的倒排----") ????????print(data) ????????return?data ????#?2.1?構造物品-->物品的共現矩陣 ????#?2.2?計算物品與物品的相似矩陣 ????def?similarity(data): ????????#?2.1?構造物品：物品的共現矩陣 ????????N?=?{}??#?喜歡物品i的總人數 ????????C?=?{}??#?喜歡物品i也喜歡物品j的人數 ????????for?user,item?in?data.items(): ????????????for?i,score?in?item.items(): ????????????????N.setdefault(i,0) ????????????????N[i]?+=?1 ????????????????C.setdefault(i,{}) ????????????????for?j,scores?in?item.items(): ????????????????????if?j?not?in?i: ????????????????????????C[i].setdefault(j,0) ????????????????????????C[i][j]?+=?1 ????????print("---2.構造的共現矩陣---") ????????print?('N:',N) ????????print?('C',C) ????????#?2.2?計算物品與物品的相似矩陣 ????????W?=?{} ????????for?i,item?in?C.items(): ????????????W.setdefault(i,{}) ????????????for?j,item2?in?item.items(): ????????????????W[i].setdefault(j,0) ????????????????W[i][j]?=?C[i][j]/sqrt(N[i]*N[j]) ????????print("---3.計算的相似矩陣---") ????????print(W) ????????return?W ????#?3.根據用戶的歷史記錄，給用戶推薦物品 ????def?recommandList(data,W,user,k=3,N=10): ????????rank?=?{} ????????for?i,score?in?data[user].items():??#?獲得用戶user歷史記錄，如A用戶的歷史記錄為{'a':?'1',?'b':?'1',?'d':?'1'} ????????????for?j,w?in?sorted(W[i].items(),key=operator.itemgetter(1),reverse=True)[0:k]:??#?獲得與物品i相似的k個物品 ????????????????if?j?not?in?data[user].keys():??#?該相似的物品不在用戶user的記錄里 ????????????????????rank.setdefault(j,0) ????????????????????rank[j]?+=?float(score)?*?w ????????print("---3.推薦----") ????????print(sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N]) ????????return?sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N] ????if?__name__?==?'__main__': ????????print("---1.構造數據---") ????????W?=?similarity(data)??#?計算物品相似矩陣 ????????recommandList(data,?W,?'Toby',?10,?10)??#推薦

推薦結果如下圖所示：

Python

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。