基于項目的協同過濾推薦算法的改進

黃　典

?

基于項目的協同過濾推薦算法的改進

黃典

個性化推薦技術是在互聯網迅速發展下應運而生的。協同過濾是各種個性化推薦技術中最受歡迎的，它在取得巨大成功的同時也同樣遭遇到挑戰。目前它所面臨的最緊要問題就是如何解決數據稀疏帶來的難題。本文主要研究協同過濾中的一種，即基于項目的協同過濾推薦算法，提出了一種改進算法：融合差異度和時間函數的協同過濾推薦算法，并通過實驗證明改進的算法對于數據稀疏的問題確有改善作用。

互聯網的飛速發展，使得網絡上數據呈指數性增長。“信息過載”之下，那些希望借由網絡的力量尋找信息的人們，就越來越找不到他們真正想要的信息，變得無所適從。所以，一個互聯網企業如何讓用戶從自己所提供的海量信息中獲得他們感興趣的信息，是擺在這些企業面前最實際的技術難題。在這樣的情況下，個性化推薦技術應運而生。個性化推薦技術的核心是推薦算法，優秀的推薦算法會使得相應的推薦系統成為客戶所依賴的優秀系統。在各種各樣的推薦算法中，協同過濾推薦是目前最為成功也是應用最廣泛的個性化推薦技術。20世紀90年代，Bob Goldberg等人在構建郵件系統Tapestry時提出了協同過濾推薦的概念，并成功地應用于Tapestry，使它在之后成為非常成功的系統。進入21世紀，隨著電子商務的發展，協同過濾開始 被一些大型的電子商務平臺引入，基于協同過濾的個性化推薦系統因其性能的優秀得到了越來越多的重視，因此被廣泛地應用于商業領域。

近年來，我國的電子商務網站發展很快，比如大家所熟悉的以京東，一號店等為代表的很多網站。因此，不僅需要個性化推薦系統，還需要性能高的個性化推薦系統，才能滿足人們日益增長的對差異化商品的需求。然而，我國個性化推薦系統發展相對較晚，相關研究人才也比較缺乏，所以和美國等發達國家相比差距較大。另一方面，互聯網正以難以想象的速度發展，電子商務系統無論是個體還是總量的規模都大得驚人，這使得現有的比較通用的協同過濾推薦算法開始面臨一些難以解決的問題，其中最典型的就是數據稀疏問題。所以，為了進一步推進協同過濾推薦在實際中的應用并讓它們發揮出最大的效果，我們需要對數據稀疏等問題進行深入研究。

基于對現在通常使用的協同過濾推薦算法的深入研究，本文主要著眼于基于項目的協同過濾推薦算法，希望通過采用改進的算法來有效地解決數據稀疏所帶來的問題。和其它的協同過濾推薦算法一樣，基于項目的協同過濾推薦算法的核心同樣也是計算相似性，只是它計算的是項目之間的相似性。現在通常所使用的計算項目相似性的方法只考慮那些具有共同評分的那些用戶的評分值差異，依賴于那些對項目都評過分用戶，這在數據豐富的情況下沒有問題，但是當數據稀疏時，項目間有共同評分的那些值相對于整個評分來說太少太少，這樣就會導致算法“失靈”。針對此問題，本文在協同過濾的兩個步驟中分別引入了差異度和時間函數。差異度從項目間評分方差差異的角度衡量項目間相似性，而時間函數改進了預測評分的方法。兩種方法的引入和結合最終起到了緩解了現在通用的算法在稀疏數據情況下的問題，如相似性的計算不夠準確以及由此產生的推薦質量下降等等。我們將通過實驗結果來驗證這種改進的算法在數據稀疏的情況下，會對推薦的質量有很顯而易見的提高。

基于項目的（Item-based）協同過濾推薦

在基于項目的協同過濾推薦中，我們首先會確定出目標用戶和目標項目，然后找到那些與目標項目的相似度滿足一定條件的項目，即目標項目的相似項目。在共同評分的假設下，這些相似項目也會有目標用戶對其的評分，因此我們可以用這些評分來對目標用戶對目標項目的評分作出合理的預測。我們可以很容易的發現，基于項目的協同過濾推薦是基于這樣一個重要的前提條件：有用戶的共同評分。在此前提條件下，如果該用戶對某個項目喜歡并且選擇了它，那對于和這個項目很相近的項目，他也會有選擇它們的傾向。

一般大家習慣于將基于項目的協同過濾推薦算法看作以下三個步驟：第一步，對各個項目之間的相似度進行計算，這是利用已有的（用戶，項目）評分記錄來進行的，這里有很多種方法，常見的包括余弦及修正的余弦法，還有Pearson法等，本文中也將提出一種改進的方法；第二步，找到目標項目的最近鄰居集，這是非常關鍵和重要的一步。找到目標項目的最近鄰居集的過程是先將第一步算出的相似度按照從大到小來進行排列，然后依照一定規則選出那些與目標項目相似度高的項目（最常用的方法有Top-N法和閾值法），最后把這些選擇出來的項目作為最近鄰居集中的元素放入，便得到了最近鄰居集以供預測評分；第三步，在第二步中所得到的最近鄰居集中的項目，得到它們各自的由目標用戶給出的評分，并用這些評分來預測目標項目的評分，最后把那些預測評分較高的項目推薦給用戶。

數據稀疏問題及推薦算法的改進

如前一節所講，基于項目的協同過濾的重要前提條件是有用戶的共同評分，而在數據稀疏的情況下，有用戶的共同評分的項目的相對數量是極少的，因此數據稀疏問題是最普遍也是最難克服的問題，也是推薦質量下降的“元兇”。在數據稀疏的情況下，計算相似性的那些通用方法如余弦法存在很多不足之處，紛紛表現不佳：與實際情況相比，通過計算得到的項目之間的相似性往往差別很大，甚至出現完全相反的情況；在極端情況下，比如兩個項目如果沒有任何一個用戶對它們都評過分（在數據稀疏的情況下這并不少見），則我們根本沒有辦法來計算它們的相似性，推薦算法也就因此“失效”。

電子商務如今正以一種難以想象的速度在飛快的發展著，而隨著這種發展，數據稀疏問題也越來越成為在其中所應用的算法的瓶頸。因為具有離線可計算性以及好的穩定性，基于項目的協同過濾推薦算法一直是受到電子商務網站青睞的代表性算法，如Amazon等大型電子商務網站都是使用的它來進行推薦。所以現在也有越來越的研究致力于解決如何有效改善數據稀疏的問題，采用的方法和途徑主要有兩種：第一種是采用各種方法試圖達到減小數據的稀疏程度的目標，另一部分則不減小數據的稀疏程度，而是著眼于對相似性計算方法的改進，在稀疏度不變的情況下，通過改進算法來提高其準確性。實驗和應用中的結果都證明，這些算法在一定程度上有效，對數據稀疏帶來的問題進行了改善或者緩解，但都不夠完善，各自還是仍然存在很多問題和一定缺陷。怎么想辦法以來在數據稀疏情況下，提高協同過濾推薦算法的準確性并產生令人滿意的效果，是目前擺在很多研究人員面前的最實際問題，同時也是本文所努力嘗試探索的問題。

在計算項目間的相似度大小的時候，余弦法等傳統的計算方法只考慮項目間有共同用戶評分的那些評分值，這在普通情況下具有很好的效果，但在數據稀疏的情況下卻很不理想，甚至在評分數據極端稀疏性的情況下會“失效”，因為可能會出現無法找到目標項目的最近鄰居集的結果。本文考慮每個項目的所有評分，對于缺乏共同評分甚至沒有共同評分的情況，提出了差異度的概念，并且把它作為重要參考因素來尋找項目的最近鄰居集中的相似項目，以期望實現在數據稀疏的情況下提升推薦質量的效果。由于在數據稀疏的情況下，有共同評分的項目相對數量極少，所以傳統的計算方法會效果變差甚至“失效”，而差異度是用來描述項目之間的評分方差差異，可以在共同評分數據很少的情況下也能進行計算，甚至不需要項目之間有共同評分，即使兩個項目之間完全沒有共同評分，也可以通過計算各自的方差來得到它們的差異度。因此，在計算項目間相似度時，我們將差異度引入其中，使其與余弦法或者Pearson法等計算方法相結合，這樣可以十分有效地解決極端稀疏情況下計算相似性的方法效果變差的問題。

即使是很稀疏的系統，用戶都仍然會對很多項目有評分，只是這些評分的數量相對于整個系統來講太少了，而這其中共同評分的項目就更少。但是，用戶評過分的項目都能計算得到一個評分方差。通過計算某個項目的所有評分所得到的方差越大，表示用戶對該項目的評價越不統一，有著很大分歧，而如果得到的方差越小，則表示對用戶對該項目的評價越趨于相近。因此，項目和間的差異度大小可以表示為：

另外，一直以來我們一般假設用戶具有穩定的興趣，即一個用戶現在喜歡什么，對一個項目的評價如何，他就會一直喜歡什么，對一個項目的評價也會一直和之前一樣。但很容易看出來，這是與事實不符合的。在現實生活中很容易觀察到，用戶的興趣或者說偏好是經常發生改變的，尤其是在長期當中，基本上都會隨著時間而產生變化。以前喜歡的項目可能之后就不喜歡了，以前不喜歡的反面變得喜歡；以前給予很高的評價的項目，可能現在只會給予很低的評價，而反而以前給予很低評價的項目現在則給予高的評價。由此可見，對于推薦算法的效果來說，時間也是一個不可忽視的非常重要的因素。因此，本文在計算預測評分的步驟中，引入了時間函數，把它作為評分的權重，以使得推薦算法更符合實際情況。在設計時間函數的時候，考慮到人們的興趣變化是有快有慢的，即有的時候會產生很大的變化，有的時候卻會很長一段時間中趨于穩定，所以呈現的規律是一種非線性的變化，因此本文設計的用作權重的時間函數也是一個非線性的函數，公式如下：

從上面的公式中可以看到，每一個評分項都有一個唯一的時間權重，距離現在越近的評分項權重越大，而距離現在越久的評分項則權重也越小，這符合實際的興趣變化的規律，因此能夠更好地對評分進行預測，使得推薦算法更符合實際，在應用中取得更好的效果。

實驗結果分析

為了分析將差異度和時間函數引入算法后，融合了差異度和時間函數的新算法在數據稀疏情況下的性能，我們用以下三種方法來進行計算并對比各自的結果；

①Pearson：傳統的Pearson方法計算相似度

②Pearson+ICS：傳統的Pearson方法與差異度（ICS）結合計算相似度；

③Pearson+ICS+時間函數：傳統的Pearson方法與差異度（ICS）結合計算相似度，預測評分時加入時間函數。

③即是本文所提出的新的算法。

本文用作實驗的數據集分別是完整的MovieLens數據，采樣密度為50%的MovieLens數據，以及采樣密度為25%的MovieLens數據，的最優值分別是=0.5（完整的MovieLens數據）、=0.6（采樣密度為50%）和=0.7（采樣密度為25%）。

上圖是方法①②③在 MovieLens 未處理過的數據集下的對比結果，其中進行預測評分采用的是MAE方法。從圖中可以看出，在使用原始數據的情況下，數據有著較低的稀疏度，本文的改進算法與通常所采用的算法相比，效果并不明顯。這也符合大家所知道的實際情況，通常所采用的這些算法已經具有了很好的性能，所以在數據豐富的情況下，它們基本上已經能夠比較準確地計算出相似性，從而得出比較準確的預測，這種時候再加入改進的方法雖然也有所助益，但是效果并不是那么明顯。

上圖是方法①②③在 MovieLens數據集經過50%稀疏采樣后的對比結果，其中進行預測評分采用的是MAE方法。從圖中可以看出，在使用這樣的數據集的時候，本文的算法對推薦效果的提升作用已經很明顯了。正如我們所分析的那樣，數據稀疏會使得依賴于共同評分的那些相似性計算方法效果變差，從而使得得出不準確的結果，而算法的性能也隨之下降，而本文提出的改進方法，因為引進了差異度，可以在共同評分少的情況下增大差異度的權重，這樣就計算出了更為準確的相似性，有效改善了推薦的效果。另外對比是否引入時間函數的兩種結果，也能很明顯的看出時間函數對推薦效果的改善起到的作用。

上圖是方法①②③在 MovieLens數據集經過25%稀疏采樣后的對比結果，其中進行預測評分采用的是MAE方法。在25%稀疏采樣后的數據集下，本文的算法與通常的計算方法相比，可以很明顯的看出，其推薦的效果有了更為很明顯的改變。我們因此可以得出，如果數據越稀疏，通常使用的算法的效果會越差，甚至在極端的情況下出現“失效”的結果，而本文提出的融合差異度和時間函數的協同過濾推薦算法比通常的算法效果提升的幅度就會越大，因為本來更多的就是要解決數據稀疏下沒有共同評分的情況。另外還值得注意的是時間函數對算法的效果的提升也很明顯，有沒有加入時間函數的算法之間的對比也是非常顯而易見的。

結語

通過以上的實驗可以看出，本文提出的差異度和時間函數的協同過濾推薦算法在數據稀疏情況下具有良好的效果，使得推薦系的性能得到了明顯的提升。因為該算法在計算項目相似性時，既考慮了項目間具有共同評分的那些值，還能在缺乏共同評分甚至是沒有共同評分的極端情況下，通過考慮項目間的方差差異性，來進行項目相似性的計算。而這樣的方法很符合數據稀疏的情況，因為數據稀疏就是缺少共同評分，因此能夠計算出更為準確的相似度，緩解數據稀疏所導致的問題。另一方面，在預測評分階段引入了時間函數概念，使得算法更符合人們的興趣會隨時間變化這一客觀現實，對于用戶在不同時間段對項目的評分給予不同的權重，這種有效的改進也對推薦效果產生了很好的改進作用。

數據稀疏問題一直是協同過濾推薦算法研究中的熱點和難點，差異度和時間函數都是其中值得進一步研究的問題，也是在以后的研究中會繼續深入探尋的問題。

黃 典

北京郵電大學理學院

黃典，男，碩士研究生，北京郵電大學理學院應用數學專業。

10.3969/j.issn.1001-8972.2016.01.020