基于協(xié)同過(guò)濾算法的推薦系統(tǒng)設(shè)計(jì)

基于協(xié)同過(guò)濾算法的推薦系統(tǒng)設(shè)計(jì)緒論：長(zhǎng)尾理論。協(xié)同過(guò)濾算法的定義：（一）預(yù)定義：要實(shí)現(xiàn)協(xié)同過(guò)濾算法，需要做以下的預(yù)定義：鄰域：給定集合X，映射U：X→P(P(X))（其中P(P(X))是X的冪集的冪集），U將X中的點(diǎn)x映射到X的子集族U(x)），稱(chēng)U(x)是X的鄰域系以及U(x)中的元素（即X的子集）為點(diǎn)x的鄰域，當(dāng)且僅當(dāng)U滿足以下的鄰域公理：U1：若集合A∈U(x)，則x∈A。U2：若集合A，B∈U(x)，則A∩B∈U(x)。U3：若集合A∈U(x)，且A?B?X，則B∈U(x)。U4：若集合A∈U(x)，則存在集合B∈U(x)，使B?A，且?y∈B，B∈U(y)。皮爾遜相關(guān)系數(shù)：皮爾遜相關(guān)系數(shù)是一種度量?jī)蓚€(gè)變量相似程度的一種方法，若變量X和變量Y線性相關(guān)，則其皮爾遜系數(shù)的z值域?yàn)閇-1,1]。系數(shù)值為1表示完全正相關(guān)；系數(shù)值為-1表示完全負(fù)相關(guān)。曼哈頓距離：歐幾里得距離：余弦相似度：Jaccard相似度：（二）基于用戶的協(xié)同過(guò)濾算法：在實(shí)際應(yīng)用中，如果一個(gè)用戶C需要得到個(gè)性化的推薦，那么根據(jù)這個(gè)用戶過(guò)去喜歡過(guò)的物品，計(jì)算出與這個(gè)顧客有著相似偏好的用戶，繼而把這些相似的用戶所喜歡的、且C沒(méi)有喜好過(guò)的物品推薦給用戶C，這就是基于用戶的協(xié)同過(guò)濾算法的主要思路。該方法主要包括兩個(gè)步驟：尋找和查詢用戶具有相似偏好的用戶群體。找到這些用戶所喜歡的物品集合，選取其中用戶最為感興趣的子集推薦給查詢用戶。在步驟1中，我們使用相似度來(lái)度量?jī)蓚€(gè)用戶之間的相似度。相似度的計(jì)算方法可以調(diào)用預(yù)定義中的皮爾遜相似度、余弦相似度、曼哈頓距離、歐幾里得距離和jaccard相似度。記用戶A和用戶B之間的相似度為sim在得到用戶的相似度之后，我們需要給查詢用戶返回根據(jù)其興趣度的TopK結(jié)果，我們用如下公式衡量用戶的興趣度：公式其中S(u,K)代表相似用戶集中的前K個(gè)用戶，N(i)代表喜歡物品i的用戶集合。R代表用戶u對(duì)物品i的感興趣程度。下圖代表基于用戶協(xié)同過(guò)濾算法的主要流程：（三）基于物品的協(xié)同過(guò)濾算法：在基于用戶的協(xié)同過(guò)濾算法的基礎(chǔ)上，又發(fā)展出了基于物品的協(xié)同過(guò)濾算法。這主要是因?yàn)樵谝话愕木W(wǎng)站應(yīng)用中，用戶的數(shù)量往往遠(yuǎn)遠(yuǎn)大于物品的數(shù)量，這就造成了計(jì)算用戶之間的相似度成為一件非常耗時(shí)的工作：以余弦相似度為例。設(shè)一個(gè)網(wǎng)站中的用戶數(shù)為N，那么就需要維護(hù)一張N*N的矩陣，因而遍歷矩陣計(jì)算相似度的時(shí)間復(fù)雜度為O（N*N），這在用戶基數(shù)較大時(shí)其計(jì)算時(shí)間會(huì)明顯增加?；谖锲返膮f(xié)同推薦算法的工作方式是先找到和用戶歷史上喜好過(guò)的物品相似的物品，然后返回這些物品中用戶興趣度最高的前K個(gè)物品?；谖锲返膮f(xié)同過(guò)濾算法也分為兩步：計(jì)算物品之間的相似度。根據(jù)物品的相似度和用戶的歷史行為返回給用戶的推薦列表。在步驟1中，與基于用戶的推薦算法相似，也使用皮爾遜相關(guān)系數(shù)、歐幾里得距離等預(yù)定義中的相似度計(jì)算方法來(lái)計(jì)算物品之間的相似度。記物品A和物品B之間的相似度為sim。在得到物品間的相似度之后，通過(guò)以下公式計(jì)算對(duì)用戶u來(lái)說(shuō)，每個(gè)物品的感興趣程度。公式這里N（u）代表某個(gè)用戶的物品喜好集合，s（j，K）代表相似物品集合中相似度最高的前K個(gè)物品組成的子集。SVD推薦算法：1、矩陣分解和baseline預(yù)測(cè)matrixfactorizationmodel

把我們的用戶評(píng)分想象成一個(gè)表:

每一行代表一個(gè)用戶,每一列代表一個(gè)物品,這其實(shí)就是一個(gè)矩形,只是我們擁有的這個(gè)矩形可能是非常稀疏的,也就是我們知道的評(píng)分占總量很少,,但現(xiàn)在我們知道它是一個(gè)矩形,一個(gè)矩形自然可以表示為另兩個(gè)矩形的乘積:

這也就是matrixfactorizationmodel的原理了,我們需要做的就是通過(guò)已有數(shù)據(jù)來(lái)學(xué)習(xí)右邊的兩個(gè)矩形,更intuitive的你可以把總的矩形里的每個(gè)評(píng)分看成是該用戶的特征向量與物品特征向量的內(nèi)積:(這里符號(hào)變得有些多,你理解了意思就成)

2.BaselinePredictors

BaselinePredictors就簡(jiǎn)單多了，我們?cè)O(shè)定μ是平均值，然后分別用bi和bu來(lái)代表具體用戶和物品的“偏好”，也就是

這兩個(gè)參數(shù)我們當(dāng)然可以當(dāng)成一個(gè)優(yōu)化任務(wù)來(lái)計(jì)算，比如最小二乘：

也可以用比較快的方法來(lái)，因?yàn)閷?shí)際上這就是經(jīng)驗(yàn)似然：

1、SVD算法的原理SVD(SingularValueDecomposition)的想法是根據(jù)已有的評(píng)分情況，分析出評(píng)分者對(duì)各個(gè)因子的喜好程度以及電影包含各個(gè)因子的程度，最后再反過(guò)來(lái)根據(jù)分析結(jié)果預(yù)測(cè)評(píng)分。電影中的因子可以理解成這些東西：電影的搞笑程度，電影的恐怖程度，等等。根據(jù)這些因子，將N*M的評(píng)分矩陣（R[u][i]代表用戶u對(duì)電影i的評(píng)分）分解成一個(gè)N行F列的用戶因子矩陣P（P[u][k]表示用戶u對(duì)因子k的喜好程度）和一個(gè)M行F列的物品因子矩陣Q（Q[i][k]表示第i個(gè)物品的因子k，具體見(jiàn)下述公式：公式下面是將評(píng)分矩陣R分解成用戶因子矩陣P與物品因子矩陣Q的一個(gè)例子。R的元素?cái)?shù)值越大，表示用戶越喜歡這部電影。P的元素?cái)?shù)值越大，表示用戶越喜歡對(duì)應(yīng)的因子。Q的元素?cái)?shù)值越大，表示物品對(duì)應(yīng)的因子程度越高。分解完后，就能利用P，Q來(lái)預(yù)測(cè)用戶A對(duì)《等風(fēng)來(lái)》的評(píng)分了。按照這個(gè)例子來(lái)看，用戶A應(yīng)該會(huì)給《等風(fēng)來(lái)》較低的分?jǐn)?shù)。因?yàn)樗幌矚g幽默片。表1評(píng)分矩陣R《阿甘正傳》《美麗人生》《等風(fēng)來(lái)》用戶A53 ？用戶B24 5表2用戶因子矩陣P勵(lì)志幽默用戶A10.1用戶B0.21表3物品因子矩陣Q勵(lì)志幽默《阿甘正傳》50《美麗人生》33《等風(fēng)來(lái)》05

實(shí)際上，我們給一部電影評(píng)分時(shí)，除了考慮電影是否合自己口味外，還會(huì)受到自己是否是一個(gè)嚴(yán)格的評(píng)分者和這部電影已有的評(píng)分狀況影響。例如：一個(gè)嚴(yán)格評(píng)分者給的分大多數(shù)情況下都比一個(gè)寬松評(píng)分者的低。你看到這部電影的評(píng)分大部分較高時(shí)，可能也傾向于給較高的分。在SVD中，口味問(wèn)題已經(jīng)有因子來(lái)表示了，但是剩下兩個(gè)還沒(méi)有相關(guān)的式子表示。因此有必要加上相關(guān)的部分，提高模型的精準(zhǔn)度。改進(jìn)后的SVD的公式如下：R=OverallMean+biasU+biasI+P*T(Q)（1）其中OverallMean表示所有電影的平均分，biasU表示用戶評(píng)分偏離OverallMean的程度，biasI表示電影評(píng)分偏離OverallMean的程度，P，Q意思不變。特別注意，這里除了OverallMean之后，其它幾個(gè)都是矩陣。

分解完后，即（1）式中的五個(gè)參數(shù)都有了正確的數(shù)值后，就可以用來(lái)預(yù)測(cè)分?jǐn)?shù)了。假設(shè)我們要預(yù)測(cè)用戶u對(duì)電影i的評(píng)分：bu表示第u個(gè)用戶的偏離程度，bi表示第i部電影的偏離程度，pu表示第u個(gè)用戶的因子愛(ài)好程度，qi表示第i部電影的因子程度。2、參數(shù)學(xué)習(xí)：為了得到用戶因子P和物品因子Q，需要通過(guò)學(xué)習(xí)來(lái)得到矩陣的參數(shù)。SVD使用隨機(jī)梯度下降(stochasticgradientdescent)學(xué)習(xí)（1）式中除了OverallMean之外的參數(shù)。學(xué)習(xí)過(guò)程可以概括成這樣：先給各個(gè)參數(shù)一個(gè)初值，然后利用這些參數(shù)進(jìn)行預(yù)測(cè)，并將預(yù)測(cè)結(jié)果與已知評(píng)分進(jìn)行對(duì)比，最后根據(jù)對(duì)比結(jié)果修正各個(gè)參數(shù)。更準(zhǔn)確點(diǎn)的說(shuō)法是調(diào)整參數(shù)的值，使得以下式子能取到最小值：ALPHA表示所有訓(xùn)練樣本。被第一個(gè)圓括號(hào)括著的部分表示當(dāng)前的預(yù)測(cè)結(jié)果與實(shí)際值的偏差。被第二個(gè)圓括號(hào)括著的部分是為了防止過(guò)擬合(overfitting)?；贛ovieLens數(shù)據(jù)集的推薦系統(tǒng)設(shè)計(jì)選取數(shù)據(jù)集：為了實(shí)現(xiàn)協(xié)同過(guò)濾算法和SVD算法，需要選取一個(gè)合適的數(shù)據(jù)集來(lái)分析。本文研究了以下數(shù)據(jù)集：1、BookCrossing：這個(gè)數(shù)據(jù)集是網(wǎng)上的Book-Crossing圖書(shū)社區(qū)的278858個(gè)用戶對(duì)271379本書(shū)進(jìn)行的評(píng)分，包括顯式和隱式的評(píng)分。這些用戶的年齡等人口統(tǒng)計(jì)學(xué)屬性(demographicfeature)都以匿名的形式保存并供分析。這個(gè)數(shù)據(jù)集是由Cai-NicolasZiegler使用爬蟲(chóng)程序在2004年從Book-Crossing圖書(shū)社區(qū)上采集的。2、JesterJoke：JesterJoke是一個(gè)網(wǎng)上推薦和分享笑話的網(wǎng)站。這個(gè)數(shù)據(jù)集有73496個(gè)用戶對(duì)100個(gè)笑話作的410萬(wàn)次評(píng)分。評(píng)分范圍是-10~10的連續(xù)實(shí)數(shù)。這些數(shù)據(jù)是由加州大學(xué)伯克利分校的KenGoldberg公布的。3、Netflix：這個(gè)數(shù)據(jù)集來(lái)自于電影租賃網(wǎng)址Netflix的數(shù)據(jù)庫(kù)。Netflix于2005年底公布此數(shù)據(jù)集并設(shè)立百萬(wàn)美元的獎(jiǎng)金(netflixprize)，征集能夠使其推薦系統(tǒng)性能上升10％的推薦算法和架構(gòu)。這個(gè)數(shù)據(jù)集包含了480189個(gè)匿名用戶對(duì)大約17770部電影作的大約lO億次評(píng)分。4、UsenetNewsgroups：這個(gè)數(shù)據(jù)集包括20個(gè)新聞組的用戶瀏覽數(shù)據(jù)。最新的應(yīng)用是在KDD2007上的論文。新聞組的內(nèi)容和討論的話題包括計(jì)算機(jī)技術(shù)、摩托車(chē)、籃球、政治等。用戶們對(duì)這些話題進(jìn)行評(píng)價(jià)和反饋。5、MovieLens：MovieLens數(shù)據(jù)集中，用戶對(duì)自己看過(guò)的電影進(jìn)行評(píng)分，分值為1～5。MovieLens包括兩個(gè)不同大小的庫(kù)，適用于不同規(guī)模的算法．小規(guī)模的庫(kù)是943個(gè)獨(dú)立用戶對(duì)1682部電影作的100000次評(píng)分的數(shù)據(jù)；大規(guī)模的庫(kù)是6040個(gè)獨(dú)立用戶對(duì)3900部電影作的大約100萬(wàn)次評(píng)分。在分析、比較各數(shù)據(jù)集的特性之后，發(fā)現(xiàn)MovieLens的數(shù)據(jù)集所涉及的主題—電影較為貼近我們的日常生活，因而具有較大的實(shí)用價(jià)值，且該數(shù)據(jù)庫(kù)數(shù)據(jù)較為規(guī)范、不存在空值等需要進(jìn)行數(shù)據(jù)清洗的情況，因而選擇MovieLens作為分析實(shí)用的數(shù)據(jù)集。在MovieLens中，有大、中、小三個(gè)不同大小的數(shù)據(jù)集，因?yàn)楸卷?xiàng)目是個(gè)人開(kāi)發(fā)，所以選擇規(guī)模最小的“MovieLens-100K”數(shù)據(jù)集，其中包含了943個(gè)獨(dú)立用戶對(duì)1682部電影作的100000次評(píng)分的數(shù)據(jù)。數(shù)學(xué)建模：在數(shù)據(jù)集“MovieLens-100k”中，需要用到三個(gè)數(shù)據(jù)文件，分別是“u.data”、“u.item”、“u.user”。“user.data”中包含943個(gè)獨(dú)立用戶對(duì)1682部電影作的100000次評(píng)分的數(shù)據(jù)。每個(gè)用戶都至少對(duì)20部進(jìn)行了打分。我們將其分為用戶編號(hào)、電影編號(hào)、打分分值、打分之間等4個(gè)屬性，以下述的形式存入數(shù)組：userid|itemid|rating|timestamp.其中timestamp為用戶評(píng)分的時(shí)間戳?！皍.item”保存了電影的信息，我們講其分為電影編號(hào)、電影標(biāo)題、上映時(shí)間、視頻發(fā)行時(shí)間、IMDB鏈接、類(lèi)別等屬性，表示為下述的數(shù)組：movieid|movietitle|releasedate|videoreleasedate|IMDbURL|category|“u.user”保存了評(píng)分人的信息，將其分類(lèi)為用戶編號(hào)、年齡、性別、職業(yè)、解壓密碼等屬性，以下述數(shù)組的形式儲(chǔ)存：userid|age|gender|occupation|zipcode將u.data按7：1分為訓(xùn)練集和測(cè)試集，具體方法見(jiàn)下述偽代碼：defdataSplit(data,M,k,seed)test=emptytrain=emptyforuser,itemindata:ifrandom(0,M)==k:test.append(user,item)elsetrain.append(user,item)returntest,train算法實(shí)現(xiàn)：對(duì)于數(shù)據(jù)集“MovieLens-100k”調(diào)用載第二章所屬的基于用戶協(xié)同過(guò)濾算法、基于物品的協(xié)同過(guò)濾算法和SVD算法，其中相似度的計(jì)算方法調(diào)用預(yù)定義中的皮爾遜相關(guān)系數(shù)等6中方法。下面給出個(gè)算法的偽代碼：基于用戶的協(xié)同過(guò)濾算法：defUserSimilarity(train):item_user=dict()foru,itemsintrain.items:foriinitem.keys()ifiinitem.keys():item_user[i].add(u)C=emptyN=emptyfori,usersinitem_users.items():foruinusers:N(u)+=1forvinusers:ifu==v:continueC[u][v]+=1W=emptyforu.related_usersinC.items():forv.cuvinrelated_users.items():W[u][v]=cuv/math.sqrt(N(u)*N(v))returnWdefRecommand(user,train,W):rank=emptydictinteracted_items=train[user]forv,wuvinsorted(W[u].items,key=itemgetter(1),\reverse=true)forirviintrain[v].item():ifiininteracted_items[v].items():continuerank[i]+=wuv*rvireturnrank基于物品的協(xié)同過(guò)濾算法：defUserSimilarity(train):item_user=dict()foru,itemsintrain.items:foriinitem.keys()ifiinitem.keys():item_user[i].add(u)C=emptyN=emptyfori,usersinitem_users.items():foruinusers:N(u)+=1forvinusers:ifu==v:continueC[u][v]+=1W=emptyforu.related_usersinC.items():forv.cuvinrelated_users.items():W[u][v]=cuv/math.sqrt(N(u)*N(v))returnWdefRecommand(user,train,W):rank=emptydictinteracted_items=train[user]forv,wuvinsorted(W[u].items,key=itemgetter(1),\reverse=flase)forirviintrain[v].item():ifiininteracted_items[v].items():continuerank[i]+=wuv*rvireturnrankSVD算法：from__future__importdivisionimportnumpyasnpimportscipyasspfromnumpy.randomimportrandomclassSVD_C: def__init__(self,X,k=20): ''' kisthelengthofvector ''' self.X=np.array(X) self.k=k self.ave=np.mean(self.X[:,2]) print"theinputdatasizeis",self.X.shape self.bi={} self.bu={} self.qi={} self.pu={} self.movie_user={} self.user_movie={} foriinrange(self.X.shape[0]): uid=self.X[i][0] mid=self.X[i][1] rat=self.X[i][2] self.movie_user.setdefault(mid,{}) self.user_movie.setdefault(uid,{}) self.movie_user[mid][uid]=rat self.user_movie[uid][mid]=rat self.bi.setdefault(mid,0) self.bu.setdefault(uid,0) self.qi.setdefault(mid,random((self.k,1))/10*(np.sqrt(self.k))) self.pu.setdefault(uid,random((self.k,1))/10*(np.sqrt(self.k))) defpred(self,uid,mid): self.bi.setdefault(mid,0) self.bu.setdefault(uid,0) self.qi.setdefault(mid,np.zeros((self.k,1))) self.pu.setdefault(uid,np.zeros((self.k,1))) if(self.qi[mid]==None): self.qi[mid]=np.zeros((self.k,1)) if(self.pu[uid]==None): self.pu[uid]=np.zeros((self.k,1)) ans=self.ave+self.bi[mid]+self.bu[uid]+np.sum(self.qi[mid]*self.pu[uid]) ifans>5: return5 elifans<1: return1 returnans deftrain(self,steps=20,gamma=0.04,Lambda=0.15): forstepinrange(steps): print'the',step,'-thstepisrunning' rmse_sum=0.0 kk=np.random.permutation(self.X.shape[0]) forjinrange(self.X.shape[0]): i=kk[j] uid=self.X[i][0] mid=self.X[i][1] rat=self.X[i][2] eui=rat-self.pred(uid,mid) rmse_sum+=eui**2 self.bu[uid]+=gamma*(eui-Lambda*self.bu[uid]) self.bi[mid]+=gamma*(eui-Lambda*self.bi[mid]) temp=self.qi[mid] self.qi[mid]+=gamma*(eui*self.pu[uid]-Lambda*self.qi[mid]) self.pu[uid]+=gamma*(eui*temp-Lambda*self.pu[uid]) gamma=gamma*0.93 print"thermseofthisstepontraindatais",np.sqrt(rmse_sum/self.X.shape[0]) #self.test(test_data) deftest(self,test_X): output=[] sums=0 test_X=np.array(test