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

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

BP神經網絡對復雜的輸入輸出關系有比較強大的學習和建模能力,能夠有效地處理非完整信息。BP神經網絡是一個3層網絡,分別為輸入層、隱含層和輸出層.

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

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

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

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

以項目聚類為例,k-means聚類算法通過用戶對項目評分的相似性對項目進行聚類并生成相應的聚類中心,然后計算目標項目與各聚類中心的相似度,選出與目標項目相似度最高的k個聚類中心對應的聚類,在這k個聚類中搜索目標項目的最近鄰居,從而達到在盡量少的項目空間中找到目標項目的大部分最近鄰居.K-means聚類算法的優點在于不同聚類中的項目之間有較明顯的區別,而且算法的擴展性相對較好.缺點是聚類數目k需要事先給定而且不同的應用中k值是不同的,難于選取;另外初始聚類中心是隨機選取的,對于同一組數據,可能因為初始聚類中心的不同而產生不同的聚類結果.五：推薦速度GibbsSampling方法

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

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

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