協(xié)同過濾推薦算法資料

1、協(xié) 同 過 濾 推 薦 算 法2011年11月17日共二十六頁一：協(xié)同(xitng)過濾算法綜述二：在個性化服務(wù)中的應(yīng)用共二十六頁綜述(zngsh)算法簡介相似性比較方法用戶-項目矩陣(j zhn)稀疏性問題及解決辦法冷啟動問題推薦速度推薦策略評估方法 共二十六頁一 算法(sun f)簡介 隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)資源的激增，用戶很難快速找到需要的信息。為了提供精確而又快速的推薦, 研究者提出了多種推薦算法, 其中協(xié)同過濾推薦算法是應(yīng)用最為成功的一種。 協(xié)同過濾這一概念首次于1992 年由Goldberg、Nicols、Oki及Terry提出,應(yīng)用于Tapestry系統(tǒng), 該系統(tǒng)僅適用較小用戶群

2、(比如, 某一個單位內(nèi)部),而且對用戶有過多要求(比如,要求用戶顯式的給出評價).目前,許多(xdu)電子商務(wù)網(wǎng)站都已經(jīng)使用了推薦系統(tǒng), 如Amazon、CDNow、Drugstore，當(dāng)當(dāng)網(wǎng)上書店和Moviefinder 等。共二十六頁一 算法(sun f)簡介 目前主要有兩類協(xié)同過濾推薦算法: 基于用戶(yngh)的協(xié)同過濾推薦算法和基于項目的協(xié)同過濾推薦算法. 基于用戶的協(xié)同過濾推薦算法基于這樣一個假設(shè), 即如果用戶對一些項目的評分比較相似, 則他們對其他項目的評分也比較相似. 算法根據(jù)目標(biāo)用戶的最近鄰居(最相似的若干用戶)對某個項目的評分逼近目標(biāo)用戶對該項目的評分. 基于項目的協(xié)同過濾

3、推薦算法認(rèn)為, 用戶對不同項目的評分存在相似性, 當(dāng)需要估計用戶對某個項目的評分時, 可以用戶對該項目的若干相似項目的評分進行估計.共二十六頁一 算法(sun f)簡介 存在兩個問題： 稀疏性： 在推薦系統(tǒng)中,每個用戶涉及的信息(xnx)相當(dāng)有限 ,用戶所評價或者購買的產(chǎn)品占產(chǎn)品總數(shù)的比例很小,造成用戶項目偏好矩陣非常稀疏 ,很難找到相似用戶 ,推薦性能可能很差。 擴展性： 是指發(fā)現(xiàn)相似關(guān)系的運算法則通常需要很長的計算時間 ,并且時間會隨著用戶數(shù)目和產(chǎn)品數(shù)目的增加而增加 ,特別是在在線實時推薦中 ,這是一個急需解決的問題?；趨f(xié)同過濾技術(shù)的推薦過程可分為 3個階段: 數(shù)據(jù)表述;發(fā)現(xiàn)最近鄰居;產(chǎn)

4、生推薦數(shù)據(jù)集。共二十六頁二：相似性比較(bjio)方法 相似性計算是協(xié)同過濾推薦算法中最關(guān)鍵的一步，傳統(tǒng)的相似度計算方法有以下幾種：1.余弦相似性 把用戶評分看作n 維項目(xingm)空間上的向量, 用戶間的相似性通過向量間的余弦夾角度量, 設(shè)用戶i和用戶j在n 維項目空間上的評分分別表示為向量, 則用戶i和用戶j之間的相似性為:共二十六頁二：相似性比較(bjio)方法修正的余弦相似性 余弦相似性度量方法中沒有考慮不同用戶的評分尺度問題, 修正的余弦相似性度量方法通過減去用戶對項目(xingm)的平均評分來改善上述缺陷。共二十六頁二：相似性比較(bjio)方法相關(guān)(xinggun)相似性 設(shè)

5、經(jīng)用戶i和用戶j共同評分的項目集合用Iij表示,則用戶i 和用戶j 之間的相似性sim ( i, j )通過Pearson 相關(guān)系數(shù)度量：共二十六頁二：相似性比較(bjio)方法 余弦相似性度量方法把用戶評分看作一個向量, 用向量的余弦夾角度量用戶間的相似性, 然而沒有包含用戶評分的統(tǒng)計特征; 修正的余弦相似性方法在余弦相似性基礎(chǔ)上, 減去了用戶對項目的平均評分, 然而該方法更多體現(xiàn)(txin)的是用戶之間的相關(guān)性而非相似性, 相關(guān)性和相似性是兩個不同的概念,相似性反映的是聚合特點, 而相關(guān)性反映的是組合特點; 相似相關(guān)性方法, 依據(jù)雙方共同評分的項目進行用戶相似性評價,如果用戶間的所有評分項

6、目均為共同評分項目, 那么相似相關(guān)性和修正的余弦相似性是等同的. 用戶對共同評分項目的評分確實能很好地體現(xiàn)用戶的相似程度, 但由于用戶評分?jǐn)?shù)據(jù)的極端稀疏性, 用戶間共同評分的項目極稀少, 使得相似相關(guān)性評價方法實際不可行. 共二十六頁三： 用戶(yngh)-項目矩陣稀疏性問題及解決辦法矩陣填充技術(shù) 最簡單的填充辦法就是將用戶(yngh)對未評分項目的評分設(shè)為一個固定的缺省值, 或者設(shè)為其他用戶對該項目的平均評分. 然而用戶對未評分項目的評分不可能完全相同,這種辦法不能從根本上解決稀疏性問題. 能夠產(chǎn)生較理想的推薦效果, 矩陣填充技術(shù)主要有以下幾類:1.1 BP 神經(jīng)網(wǎng)絡(luò) BP 神經(jīng)網(wǎng)絡(luò)對復(fù)雜的

7、輸入輸出關(guān)系有比較強大的學(xué)習(xí)和建模能力,能夠有效地處理非完整信息。BP神經(jīng)網(wǎng)絡(luò)是一個3層網(wǎng)絡(luò),分別為輸入層、隱含層和輸出層. 共二十六頁三 ： 用戶-項目(xingm)矩陣稀疏性問題及解決辦法 BP 神經(jīng)網(wǎng)絡(luò)把用戶對各個項目的評分看作訓(xùn)練樣本, 分別輸入到輸入層的各個單元中; 這些單元經(jīng)過加權(quán), 輸出到隱含層的各個單元; 隱含層的加權(quán)輸出再經(jīng)過一次加權(quán)作為輸出層的單元輸入; 最后由輸出層產(chǎn)生給定樣本(yngbn)的預(yù)測值.這種矩陣填充技術(shù)對噪聲數(shù)據(jù)有較強的承受能力, 可以有效降低用戶-項目矩陣的稀疏性, 達到提高推薦精度的目的. 然而,BP 算法的缺點為存在隨著訓(xùn)練時間的增加, 收斂速度有變慢

8、的趨勢,以致會延長最近鄰居的查找時間. 共二十六頁三 ： 用戶(yngh)-項目矩陣稀疏性問題及解決辦法1.2 Naive Bayesian 分類方法 Naive Bayesian 分類方法基于概率模型進行(jnxng)分類,可以使用該方法估算一個實例屬于某一類的概率, 在得到某一個項目所屬的分類之后, 可以利用此分類中其他項目的評分情況來預(yù)測未評分項目的評分, 從而可以填充用戶-項目矩陣, 降低稀疏性.1.3 基于內(nèi)容的預(yù)測 基于內(nèi)容的預(yù)測又稱基于屬性的預(yù)測或基于語義的預(yù)測, 該方法根據(jù)項目的屬性聯(lián)系以及項目所處的地位、相互關(guān)系和項目元信息等內(nèi)容計算項目之間的內(nèi)容相似性, 而不依賴于用戶對項

9、目的評分.共二十六頁三 用戶(yngh)-項目矩陣稀疏性問題及解決辦法 得到項目之間的內(nèi)容相似性后, 選擇與目標(biāo)項目相似性最大的若干個項目進行評分預(yù)測, 用預(yù)測評分填充用戶-項目矩陣(j zhn)中的空項, 降低其稀疏性. 由于不同類別的項目之間在屬性描述上有較大差別, 因此基于語義的方法無法計算跨類別的項目之間的相似性, 也就無法進行跨類別的評分預(yù)測.另外基于語義的相似性計算需要提取項目的屬性特征,涉及到領(lǐng)域知識, 應(yīng)用面較窄.矩陣降維技術(shù)-奇異值分解 通過降低用戶-項目矩陣的維數(shù)解決矩陣的稀疏性問題, 奇異值分解(Singular Value Decompo sition, SVD)是一種

10、矩陣分解技術(shù), 它深刻揭露了矩陣的內(nèi)部結(jié)構(gòu), 它可以將一個mn (假設(shè)m n)的矩陣R分解為三個矩陣U,S,V,大小分別為mm,mn,nn .共二十六頁三 用戶-項目(xingm)矩陣稀疏性問題及解決辦法 協(xié)同過濾推薦系統(tǒng)中SVD 的優(yōu)勢主要體現(xiàn)在: 用戶-項目矩陣稀疏性問題得到很好的解決;對用戶-項目矩陣降維后, 運算復(fù)雜度大大降低, 系統(tǒng)的擴展性得到提升; 用戶間和項目間的潛在關(guān)系(gun x)將得到更好的發(fā)掘, 有利于提高推薦精度.SVD 方法的缺點為: 降維會導(dǎo)致用戶-項目矩陣中的信息丟失,有的情況下會影響推薦精度, 通過選取合適的保留維數(shù)k,可以在一定程度上減小這種影響. 總的來說,

11、 SVD 方法不僅能夠解決矩陣稀疏性問題, 而且對于系統(tǒng)的擴展性和推薦精度的提高也有作用.共二十六頁四：冷啟動問題(wnt)1) 在U ser-based 系統(tǒng)中, 對于一個新的用戶來說, 系統(tǒng)中沒有該用戶的任何購買(gumi)信息記錄, 因此無法找到其最近鄰居, 從而無法進行推薦.2) 在 Item - based 系統(tǒng)中, 當(dāng)系統(tǒng)中加入一個新的項目時, 該項目沒有評分記錄, 無法找出其最近鄰居并進行推薦或評分預(yù)測. 協(xié)同過濾推薦系統(tǒng)中存在的這種問題被稱為冷啟動問題. 為了解決冷啟動問題, 普遍采用基于內(nèi)容的最近鄰居查找技術(shù), 其基本思想是:1) 利用聚類技術(shù)將用戶按照屬性相似性聚類, 從項

12、目屬性的角度找到新項目的最近鄰居;2) 用新項目k的所有最近鄰居的平均評分來代替已有評分的平均值.例如：先對項目進行聚類，得到項目在屬性特征上的相似關(guān)系群，然后與用戶-項目評分矩陣中的協(xié)同相似關(guān)系群組合。共二十六頁五：推薦(tujin)速度 電子商務(wù)系統(tǒng)中, 由于項目在一定時期內(nèi)通常是相對穩(wěn)定的, 項目相似性的計算可以離線進行,這就使得與基于用戶的協(xié)同過濾推薦系統(tǒng)相比, 基于項目的協(xié)同過濾推薦系統(tǒng)的運行效率較高. 隨著用戶數(shù)和項目數(shù)的增多, 協(xié)同過濾推薦算法的計算量也不斷增大. 通常采用聚類技術(shù)提高推薦速度(sd), 因為使用聚類技術(shù)可以大大縮小用戶或項目的最近鄰居搜索范圍, 從而提高推薦的實

13、時性.共二十六頁五：推薦(tujin)速度EM (Expectation-Maximization)算法 EM算法通過估計用戶(yngh)或項目屬于某一類的概率對用戶(yngh)或項目進行聚類. 在實際的聚類中, 不同的用戶可能會喜歡同一個項目,根據(jù) EM 算法, 這樣的項目可能會同時出現(xiàn)在兩個不同的聚類中. 如果要求每個用戶或項目只能屬于一個用戶分類或項目分類, EM 算法就不再適用.共二十六頁五：推薦(tujin)速度k-means聚類算法 以項目聚類為例, k-means 聚類算法通過用戶對項目評分的相似性對項目進行聚類并生成相應(yīng)的聚類中心, 然后計算目標(biāo)項目與各聚類中心的相似度, 選出

14、與目標(biāo)項目相似度最高的k 個聚類中心對應(yīng)的聚類, 在這k 個聚類中搜索目標(biāo)項目的最近鄰居, 從而達到在盡量少的項目空間中找到目標(biāo)項目的大部分最近鄰居. K-means 聚類算法的優(yōu)點在于不同聚類中的項目之間有較明顯的區(qū)別, 而且算法的擴展性相對較好. 缺點是聚類數(shù)目k 需要事先給定而且不同的應(yīng)用中k 值是不同的, 難于選取; 另外初始聚類中心是隨機選取的, 對于同一組數(shù)據(jù), 可能因為初始聚類中心的不同而產(chǎn)生(chnshng)不同的聚類結(jié)果.共二十六頁五：推薦(tujin)速度Gibbs Sampling 方法 Gibbs Sampling 方法與EM 算法類似, 不同的是Gibbs Sampl

15、ing方法基于Bayesian 模型. Gibbs Samp ling 算法有較好的聚類效果和很強的擴展性, 但是其算法復(fù)雜度較大. 聚類過程相對(xingdu)比較耗時, 但是可以離線進行， 而且目標(biāo)項目的最近鄰居搜索范圍縮小到幾個聚類中, 遠遠小于整個項目空間共二十六頁五：推薦(tujin)速度模糊聚類 模糊聚類與聚類的區(qū)別在于前者不需要預(yù)先給定聚類的數(shù)目, 而是通過一定的閾值來確定對象的相似類別. 模糊聚類利用模糊等價關(guān)系將給定的對象分為一些等價類, 并由此得到與關(guān)系對應(yīng)的模糊相似矩陣, 該模糊相似矩陣滿足傳遞性.根據(jù)相似矩陣求出其傳遞關(guān)系的閉包, 然后在傳遞關(guān)系的閉包上實現(xiàn)分類: 模糊

16、聚類過程可以離線進行,不會給推薦系統(tǒng)的實時性帶來負擔(dān). 同時(tngsh)模糊聚類對于解決數(shù)據(jù)稀疏性帶來的冷啟動問題也有很好的效果.共二十六頁六：推薦(tujin)策略平均加權(quán)策略 目前大多數(shù)協(xié)同過濾推薦系統(tǒng)都采用平均加權(quán)策略產(chǎn)生推薦,平均加權(quán)策略在產(chǎn)生推薦的時候綜合考慮(kol)了用戶對所有項目的評分情況. 在用戶評價過的項目數(shù)較多時, 這種方法是合理的而且實驗證明有較好的推薦效果, 當(dāng)用戶評價過的項目數(shù)較少時, 個別項目的評分就會對平均評分產(chǎn)生較大影響, 這種情況下平均評分無法反映用戶對大多數(shù)項目的評分情況.共二十六頁六：推薦(tujin)策略基于評分頻度的推薦策略 電子商務(wù)中用戶評分通常

17、(tngchng)為離散值, 比如1, 2, 3, 4, 5,基于評分頻度的推薦策略首先用統(tǒng)計的方法計算最近鄰居集中用戶給出的各種評分的出現(xiàn)頻率, 然后將評分頻率最高的那個分值作為目標(biāo)用戶的預(yù)測評分. 該推薦策略用戶對大多數(shù)鄰居的評分情況, 實驗證明, 在最近鄰居數(shù)較少時, 推薦效果優(yōu)于平均加權(quán)策略共二十六頁七：評估(pn )方法. 推薦質(zhì)量的評價標(biāo)準(zhǔn)主要(zhyo)有統(tǒng)計精度度量和決策支持精度度量方法兩類. 統(tǒng)計精度度量方法中常用的是平均絕對偏差MAE(Mean Absolute Error) ;決策支持精度度量方法中主要有召回率 (Recall)、準(zhǔn)確率(Precision)及ROC(Receiver Operating Characteristic)等三種方法.共二十六頁 謝 謝共二十六頁內(nèi)容摘要協(xié) 同 過 濾 推 薦 算 法。隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)資源的激增，用戶很難快速找到需要。為了提供精確