協(xié)同過濾推薦算法2011年11月17日一：協(xié)同過濾算法綜述二：在個性化服務(wù)中的應(yīng)用綜述算法簡介相似性比較方法用戶-項(xiàng)目矩陣稀疏性問題及解決辦法冷啟動問題推薦速度推薦策略評估方法一算法簡介隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)資源的激增，用戶很難快速找到需要的信息。為了提供精確而又快速的推薦,研究者提出了多種推薦算法,其中協(xié)同過濾推薦算法是應(yīng)用最為成功的一種。協(xié)同過濾這一概念首次于1992年由Goldberg、Nicols、Oki及Terry提出,應(yīng)用于Tapestry系統(tǒng),該系統(tǒng)僅適用較小用戶群(比如,某一個單位內(nèi)部),而且對用戶有過多要求(比如,要求用戶顯式的給出評價(jià)).目前,許多電子商務(wù)網(wǎng)站都已經(jīng)使用了推薦系統(tǒng),如Amazon、CDNow、Drugstore，當(dāng)當(dāng)網(wǎng)上書店和Moviefinder等。一算法簡介目前主要有兩類協(xié)同過濾推薦算法:基于用戶的協(xié)同過濾推薦算法和基于項(xiàng)目的協(xié)同過濾推薦算法.基于用戶的協(xié)同過濾推薦算法基于這樣一個假設(shè),即如果用戶對一些項(xiàng)目的評分比較相似,則他們對其他項(xiàng)目的評分也比較相似.算法根據(jù)目標(biāo)用戶的最近鄰居(最相似的若干用戶)對某個項(xiàng)目的評分逼近目標(biāo)用戶對該項(xiàng)目的評分.基于項(xiàng)目的協(xié)同過濾推薦算法認(rèn)為,用戶對不同項(xiàng)目的評分存在相似性,當(dāng)需要估計(jì)用戶對某個項(xiàng)目的評分時,可以用戶對該項(xiàng)目的若干相似項(xiàng)目的評分進(jìn)行估計(jì).一算法簡介存在兩個問題：稀疏性：在推薦系統(tǒng)中,每個用戶涉及的信息相當(dāng)有限,用戶所評價(jià)或者購買的產(chǎn)品占產(chǎn)品總數(shù)的比例很小,造成用戶—項(xiàng)目偏好矩陣非常稀疏,很難找到相似用戶,推薦性能可能很差。擴(kuò)展性：是指發(fā)現(xiàn)相似關(guān)系的運(yùn)算法則通常需要很長的計(jì)算時間,并且時間會隨著用戶數(shù)目和產(chǎn)品數(shù)目的增加而增加,特別是在在線實(shí)時推薦中,這是一個急需解決的問題?；趨f(xié)同過濾技術(shù)的推薦過程可分為3個階段:數(shù)據(jù)表述;發(fā)現(xiàn)最近鄰居;產(chǎn)生推薦數(shù)據(jù)集。二：相似性比較方法相似性計(jì)算是協(xié)同過濾推薦算法中最關(guān)鍵的一步，傳統(tǒng)的相似度計(jì)算方法有以下幾種：1.余弦相似性

把用戶評分看作n維項(xiàng)目空間上的向量,用戶間的相似性通過向量間的余弦夾角度量,設(shè)用戶i和用戶j在n維項(xiàng)目空間上的評分分別表示為向量,則用戶i和用戶j之間的相似性為:二：相似性比較方法修正的余弦相似性余弦相似性度量方法中沒有考慮不同用戶的評分尺度問題,修正的余弦相似性度量方法通過減去用戶對項(xiàng)目的平均評分來改善上述缺陷。二：相似性比較方法相關(guān)相似性設(shè)經(jīng)用戶i和用戶j共同評分的項(xiàng)目集合用Iij表示,則用戶i和用戶j之間的相似性sim(i,j)通過Pearson相關(guān)系數(shù)度量：二：相似性比較方法余弦相似性度量方法把用戶評分看作一個向量,用向量的余弦夾角度量用戶間的相似性,然而沒有包含用戶評分的統(tǒng)計(jì)特征;修正的余弦相似性方法在余弦相似性基礎(chǔ)上,減去了用戶對項(xiàng)目的平均評分,然而該方法更多體現(xiàn)的是用戶之間的相關(guān)性而非相似性,相關(guān)性和相似性是兩個不同的概念,相似性反映的是聚合特點(diǎn),而相關(guān)性反映的是組合特點(diǎn);相似相關(guān)性方法,依據(jù)雙方共同評分的項(xiàng)目進(jìn)行用戶相似性評價(jià),如果用戶間的所有評分項(xiàng)目均為共同評分項(xiàng)目,那么相似相關(guān)性和修正的余弦相似性是等同的.用戶對共同評分項(xiàng)目的評分確實(shí)能很好地體現(xiàn)用戶的相似程度,但由于用戶評分?jǐn)?shù)據(jù)的極端稀疏性,用戶間共同評分的項(xiàng)目極稀少,使得相似相關(guān)性評價(jià)方法實(shí)際不可行.三：用戶-項(xiàng)目矩陣稀疏性問題及解決辦法矩陣填充技術(shù)最簡單的填充辦法就是將用戶對未評分項(xiàng)目的評分設(shè)為一個固定的缺省值,或者設(shè)為其他用戶對該項(xiàng)目的平均評分.然而用戶對未評分項(xiàng)目的評分不可能完全相同,這種辦法不能從根本上解決稀疏性問題.能夠產(chǎn)生較理想的推薦效果,矩陣填充技術(shù)主要有以下幾類:1.1BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)對復(fù)雜的輸入輸出關(guān)系有比較強(qiáng)大的學(xué)習(xí)和建模能力,能夠有效地處理非完整信息。BP神經(jīng)網(wǎng)絡(luò)是一個3層網(wǎng)絡(luò),分別為輸入層、隱含層和輸出層.

三：用戶-項(xiàng)目矩陣稀疏性問題及解決辦法BP神經(jīng)網(wǎng)絡(luò)把用戶對各個項(xiàng)目的評分看作訓(xùn)練樣本,分別輸入到輸入層的各個單元中;這些單元經(jīng)過加權(quán),輸出到隱含層的各個單元;隱含層的加權(quán)輸出再經(jīng)過一次加權(quán)作為輸出層的單元輸入;最后由輸出層產(chǎn)生給定樣本的預(yù)測值.這種矩陣填充技術(shù)對噪聲數(shù)據(jù)有較強(qiáng)的承受能力,可以有效降低用戶-項(xiàng)目矩陣的稀疏性,達(dá)到提高推薦精度的目的.然而,BP算法的缺點(diǎn)為存在隨著訓(xùn)練時間的增加,收斂速度有變慢的趨勢,以致會延長最近鄰居的查找時間.三：用戶-項(xiàng)目矩陣稀疏性問題及解決辦法1.2NaiveBayesian分類方法

NaiveBayesian分類方法基于概率模型進(jìn)行分類,可以使用該方法估算一個實(shí)例屬于某一類的概率,在得到某一個項(xiàng)目所屬的分類之后,可以利用此分類中其他項(xiàng)目的評分情況來預(yù)測未評分項(xiàng)目的評分,從而可以填充用戶-項(xiàng)目矩陣,降低稀疏性.1.3基于內(nèi)容的預(yù)測基于內(nèi)容的預(yù)測又稱基于屬性的預(yù)測或基于語義的預(yù)測,該方法根據(jù)項(xiàng)目的屬性聯(lián)系以及項(xiàng)目所處的地位、相互關(guān)系和項(xiàng)目元信息等內(nèi)容計(jì)算項(xiàng)目之間的內(nèi)容相似性,而不依賴于用戶對項(xiàng)目的評分.三用戶-項(xiàng)目矩陣稀疏性問題及解決辦法

得到項(xiàng)目之間的內(nèi)容相似性后,選擇與目標(biāo)項(xiàng)目相似性最大的若干個項(xiàng)目進(jìn)行評分預(yù)測,用預(yù)測評分填充用戶-項(xiàng)目矩陣中的空項(xiàng),降低其稀疏性.由于不同類別的項(xiàng)目之間在屬性描述上有較大差別,因此基于語義的方法無法計(jì)算跨類別的項(xiàng)目之間的相似性,也就無法進(jìn)行跨類別的評分預(yù)測.另外基于語義的相似性計(jì)算需要提取項(xiàng)目的屬性特征,涉及到領(lǐng)域知識,應(yīng)用面較窄.矩陣降維技術(shù)-奇異值分解通過降低用戶-項(xiàng)目矩陣的維數(shù)解決矩陣的稀疏性問題,奇異值分解(SingularValueDecomposition,SVD)是一種矩陣分解技術(shù),它深刻揭露了矩陣的內(nèi)部結(jié)構(gòu),它可以將一個m×n(假設(shè)m≥n)的矩陣R分解為三個矩陣U,S,V,大小分別為m×m,m×n,n×n.三用戶-項(xiàng)目矩陣稀疏性問題及解決辦法協(xié)同過濾推薦系統(tǒng)中SVD的優(yōu)勢主要體現(xiàn)在:用戶-項(xiàng)目矩陣稀疏性問題得到很好的解決;對用戶-項(xiàng)目矩陣降維后,運(yùn)算復(fù)雜度大大降低,系統(tǒng)的擴(kuò)展性得到提升;用戶間和項(xiàng)目間的潛在關(guān)系將得到更好的發(fā)掘,有利于提高推薦精度.SVD方法的缺點(diǎn)為:降維會導(dǎo)致用戶-項(xiàng)目矩陣中的信息丟失,有的情況下會影響推薦精度,通過選取合適的保留維數(shù)k,可以在一定程度上減小這種影響.總的來說,SVD方法不僅能夠解決矩陣稀疏性問題,而且對于系統(tǒng)的擴(kuò)展性和推薦精度的提高也有作用.四：冷啟動問題1)在User-based系統(tǒng)中,對于一個新的用戶來說,系統(tǒng)中沒有該用戶的任何購買信息記錄,因此無法找到其最近鄰居,從而無法進(jìn)行推薦.2)在Item-based系統(tǒng)中,當(dāng)系統(tǒng)中加入一個新的項(xiàng)目時,該項(xiàng)目沒有評分記錄,無法找出其最近鄰居并進(jìn)行推薦或評分預(yù)測.協(xié)同過濾推薦系統(tǒng)中存在的這種問題被稱為冷啟動問題.為了解決冷啟動問題,普遍采用基于內(nèi)容的最近鄰居查找技術(shù),其基本思想是:1)利用聚類技術(shù)將用戶按照屬性相似性聚類,從項(xiàng)目屬性的角度找到新項(xiàng)目的最近鄰居;2)用新項(xiàng)目k的所有最近鄰居的平均評分來代替已有評分的平均值.例如：先對項(xiàng)目進(jìn)行聚類，得到項(xiàng)目在屬性特征上的相似關(guān)系群，然后與用戶-項(xiàng)目評分矩陣中的協(xié)同相似關(guān)系群組合。五：推薦速度

電子商務(wù)系統(tǒng)中,由于項(xiàng)目在一定時期內(nèi)通常是相對穩(wěn)定的,項(xiàng)目相似性的計(jì)算可以離線進(jìn)行,這就使得與基于用戶的協(xié)同過濾推薦系統(tǒng)相比,基于項(xiàng)目的協(xié)同過濾推薦系統(tǒng)的運(yùn)行效率較高.隨著用戶數(shù)和項(xiàng)目數(shù)的增多,協(xié)同過濾推薦算法的計(jì)算量也不斷增大.通常采用聚類技術(shù)提高推薦速度,因?yàn)槭褂镁垲惣夹g(shù)可以大大縮小用戶或項(xiàng)目的最近鄰居搜索范圍,從而提高推薦的實(shí)時性.五：推薦速度EM(Expectation-Maximization)算法EM算法通過估計(jì)用戶或項(xiàng)目屬于某一類的概率對用戶或項(xiàng)目進(jìn)行聚類.在實(shí)際的聚類中,不同的用戶可能會喜歡同一個項(xiàng)目,根據(jù)EM算法,這樣的項(xiàng)目可能會同時出現(xiàn)在兩個不同的聚類中.如果要求每個用戶或項(xiàng)目只能屬于一個用戶分類或項(xiàng)目分類,EM算法就不再適用.五：推薦速度k-means聚類算法

以項(xiàng)目聚類為例,k-means聚類算法通過用戶對項(xiàng)目評分的相似性對項(xiàng)目進(jìn)行聚類并生成相應(yīng)的聚類中心,然后計(jì)算目標(biāo)項(xiàng)目與各聚類中心的相似度,選出與目標(biāo)項(xiàng)目相似度最高的k個聚類中心對應(yīng)的聚類,在這k個聚類中搜索目標(biāo)項(xiàng)目的最近鄰居,從而達(dá)到在盡量少的項(xiàng)目空間中找到目標(biāo)項(xiàng)目的大部分最近鄰居.K-means聚類算法的優(yōu)點(diǎn)在于不同聚類中的項(xiàng)目之間有較明顯的區(qū)別,而且算法的擴(kuò)展性相對較好.缺點(diǎn)是聚類數(shù)目k需要事先給定而且不同的應(yīng)用中k值是不同的,難于選取;另外初始聚類中心是隨機(jī)選取的,對于同一組數(shù)據(jù),可能因?yàn)槌跏季垲愔行牡牟煌a(chǎn)生不同的聚類結(jié)果.五：推薦速度GibbsSampling方法

GibbsSampling方法與EM算法類似,不同的是GibbsSampling方法基于Bayesian模型.GibbsSampling算法有較好的聚類效果和很強(qiáng)的擴(kuò)展性,但是其算法復(fù)雜度較大.聚類過程相對比較耗時,但是可以離線進(jìn)行，

而且目標(biāo)項(xiàng)目的最近鄰居搜索范圍縮小到幾個聚類中,遠(yuǎn)遠(yuǎn)小于整個項(xiàng)目空間五：推薦速度模糊聚類模糊聚類與聚類的區(qū)別在于前者不需要預(yù)先給定聚類的數(shù)目,而是通過一定的閾值來確定對象的相似類別.模糊聚類利用模糊等價(jià)關(guān)系將給定的對象分為一些等價(jià)類,并由此得到與關(guān)系對應(yīng)的模糊相似矩陣,該模糊相似矩陣滿足傳遞性.根據(jù)相似矩陣求出其傳遞關(guān)系的閉包,然后在傳遞關(guān)系的閉包上實(shí)現(xiàn)分類:模糊聚類過程可以離線進(jìn)行,不會給推薦系統(tǒng)的實(shí)時性帶來負(fù)擔(dān).同時模糊聚類對于解決數(shù)據(jù)稀疏性帶來的冷啟動問題也有很好的效果.六：推薦策略平均加權(quán)策略目前大多數(shù)協(xié)同過濾推薦系統(tǒng)都采用平均加權(quán)策略產(chǎn)生推薦,平均加權(quán)策略在產(chǎn)生推薦的時候綜合考慮了用戶對所有項(xiàng)目的評分情況.在用戶評價(jià)過的項(xiàng)目數(shù)較多時,這種方法是合理的而且實(shí)驗(yàn)證明有較好的推薦效果,當(dāng)用戶評價(jià)過的項(xiàng)目數(shù)較少時,個別項(xiàng)目的評分就會對平均評分產(chǎn)生較大影響,這種情況下平均評分無法反映用戶對大多數(shù)項(xiàng)目的評分情況.六：推薦策略基于評分頻度的推薦策略

電子商務(wù)中用戶評分通常為離散值,比如{1,2,3,4,5},基于評分頻度的推薦策略首先用統(tǒng)計(jì)的方法計(jì)算最近鄰居集中用戶給出的各種評分的出現(xiàn)頻率,然后將評分頻率最