協(xié)同過(guò)濾推薦算法

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

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

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

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

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

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

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

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

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

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

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