基于用戶部分特征的協同過濾算法①

李永超, 羅 軍

?

基于用戶部分特征的協同過濾算法①

李永超, 羅 軍

(國防科技大學計算機學院, 長沙 410073)

協同過濾算法作為推薦系統中應用最廣泛的算法之一, 在大數據環境下面臨嚴重的數據稀疏問題, 使得近鄰選擇的效果不佳, 直接影響了算法的推薦性能. 為了解決這一問題, 本文提出了一種基于用戶部分特征的協同過濾算法(UPCF), 該算法首先基于評分偏差和項目流行度進行矩陣缺失值填充, 隨后利用初始聚類中心優化的K-means算法對該填充矩陣進行項目聚類, 并利用用戶在項目分類下的局部特征進行近鄰集合構建, 最終采用基于用戶的協同過濾算法獲得推薦. 我們采用流行的MAE指標對算法在MovieLens數據集上進行評測. 實驗表明, 與目前流行的協同過濾算法相比, 提出的UPCF算法在沒有增加算法復雜性的前提下, 性能有近10%的提升.

項目流行度; 最近鄰選擇; 項目聚類; 協同過濾算法

1 引言

隨著互聯網的興起, 互聯網上的信息呈指數化增長, 人類進入了信息爆炸的大數據時代. 如何從浩瀚的數據信息中獲取自己感興趣的信息, 已成為人類面臨的巨大難題. 于是無需用戶提供明確需求, 僅通過用戶歷史行為主動幫助用戶快速有效篩選信息的推薦系統應運而生[1]. 我們在互聯網網站中看到的“猜你喜歡”, “大家都在看”, “看過的也看”, “你可能會感興趣”等都是推薦技術的實際應用. 據報道, 早在2002 年, 在線購物企業Amazon 總銷售額的20%便源自它的推薦系統. 推薦技術在新聞領域更是產生了“今日頭條”這樣的不生產內容, 僅依靠推薦引擎便擁有3.5 億注冊用戶, 3500 萬活躍用戶的新興科技媒體.

協同過濾作為推薦系統的主流技術之一, 主要包括基于用戶的協同過濾推薦、基于項目的協同過濾推薦和基于矩陣分解的協同過濾推薦[2]. 而其中基于用戶的協同過濾算法是目前在實際應用中最為成功的算法. 該算法首先通過用戶間的共同評分項計算用戶間的相似度, 然后根據用戶間的相似度選擇目標用戶的近鄰集合, 最后根據用戶近鄰集合對目標用戶進行推薦. 最近鄰選擇作為該算法中最關鍵的步驟, 直接決定了推薦的質量. 然而在實際應用中由于數據集中項目的維度巨大, 大多數用戶只會對極少數的項目進行評價, 從而導致用戶評分數據的極端稀疏,不同用戶間的共同評分項極少,用戶間相似性計算的可靠性和準確性難以得到保證, 推薦算法的效果大打折扣.

為了解決稀疏性問題, 多種措施相繼被提出. Ungar LH等[3]首次提出基于用戶聚類的協同過濾算法(UBCF), 通過用戶聚類來降低最近鄰搜索的數據規模, 增加最近鄰可靠性. 黃裕洋等[4]根據評分數據的稀疏性情況, 提出了一種動態計算相似性的方法(HCFR). Xavier Amatriain[5]等提出在提前構建的專家集合中尋找用戶近鄰集合, 以確保用戶的近鄰對待預測項目有過評分記錄. 黃創光等[6]提出了一種不確定近鄰的協同過濾推薦算法(UNCF). 該算法通過不確定近鄰因子及調和參數去計算基于用戶和產品的預測評分并產生推薦. Koren Y[7]通過將矩陣分解和最近鄰算法相結合, 大大提高了算法的推薦性能.

以上方法雖然從一定程度上減弱了數據稀疏對近鄰選擇帶來的影響, 提高了協同過濾的推薦質量和效率, 但在最近鄰計算的過程中, 對用戶的相似性計算仍基于全局相似性, 沒有充分考慮用戶在不同項目類別下的興趣差異. 正如世上沒有完全相同的兩片樹葉一樣, 在各個方面興趣都相似的用戶也難以尋找. 大多用戶可能只在某個領域內興趣相仿, 在其他領域內可能興趣完全相悖. 因此本文提出了一種基于用戶部分特征的協同過濾算法UPCF, 該算法首先對填充矩陣進行項目聚類, 然后僅根據用戶在該項目分類下的所有評價進行相似度矩陣構建, 降低數據維度的同時提升了最近鄰計算的可靠性, 最后根據相似性矩陣進行近鄰集合構建, 從而最終得到推薦結果.

2 問題定義及基本方法

基于用戶的協同過濾算法基于以下假設: 如果用戶之間對一些項目的評分比較相似, 則他們對其它項目的評分也將會比較相似. 協同過濾推薦系統首先搜索目標用戶的若干近鄰, 然后根據最近鄰對項目的評分去預測目標用戶對項目的評分, 從而產生推薦列表. 作為算法的輸入, 數據源=(,,), 其中={u,u,···,u}是基本用戶的集合,;{i,i,···,i}是項目集合,.階矩陣是用戶對各項目的評分矩陣, 其中的元素r表示中第個用戶對中第個項目的評分. 基于用戶的協同過濾算法主要包括以下三個步驟.

2.1 評分矩陣預處理

由于在實際應用中, 項目集的維數很大, 用戶只能對極少數項目進行評價, 因此評分矩陣十分稀疏, 這對后面的相似性計算提出了很大的挑戰. 合理的矩陣缺失值預測填充可以從一定程度上緩解稀疏性問題.

目前常用的缺失值預測方法包括評分中值、眾數、用戶評分均值、項目評分均值、采用奇異值分解填補近鄰評分缺失值[7]以及基于近似項目預測評分值[8]等.

2.2 用戶近鄰集合構建

接下來, 我們在預處理過的用戶評分矩陣上采用相似度計算方法, 計算用戶之間的相似度, 形成用戶的相似度矩陣. 協同過濾算法研究中最常用的相似度計算方法是相關相似度、余弦相似度和修正的余弦相似度, 它們的計算公式分別如下:

相關相似度:

余弦相似度:

修正的余弦相似度:

各公式中表示用戶、.r表示用戶對項目的評分,表示用戶的平均評分,I、I表示用戶已經評價過的項目集合,I表示用戶和用戶的共同評分項目集合.

相似矩陣構建結束后, 便可根據用戶指定的最近鄰篩選規則構建近鄰集合, 常用的篩選規則包括指定近鄰數量和設置相似度閾值.

2.3 物品推薦

利用上一步計算得到的近鄰集合, 找到這個集合中的用戶喜歡且目標用戶沒有聽說過的物品推薦給用戶. 具體而言, 我們利用公式(4)計算用戶對指定項目的預測評分.

其中N為用戶的最近鄰集合, sim()為用戶、的相似度, 其余符號與前面定義一致. 最終便得到了用戶關于項目i的預測評分.

3 基于用戶部分特征的協同過濾算法(UPCF)

傳統的基于用戶的協同過濾算法在計算最近鄰的過程中使用了用戶的所有評分記錄, 考察了用戶的全局相似性. 然而在全部項目集上興趣都相似的用戶并不常見, 大多用戶可能只在某一主題下興趣相似, 而在其余項目分類中喜好完全不同. 因此傳統的近鄰集合構建往往選擇了全局相對相似而舍棄了在某些領域內興趣高度契合的用戶. 為了解決這個問題, 本文提出了一種基于用戶部分特征的協同過濾算法, 使得在最近鄰選擇時所需的相似度僅根據用戶在該項目所在類內的評價信息計算獲得. 算法詳細流程如下所示.

3.1 未評分項目預測填充

為了緩解在項目聚類時矩陣的稀疏問題, 我們首先對評分矩陣進行缺失值預測填充. 考慮到熱門項目對用戶特征貢獻度不大, 以及相對冷門項目而言, 用戶接觸到熱門項目的概率大得多, 而如果用戶未對熱門項目進行反饋評價, 很可能是因為用戶對該項目并不感興趣. 而在推薦系統中, 項目流行度是衡量項目熱門程度的主要指標, 它是指項目被用戶反饋的總次數, 被反饋的次數越多代表項目流行度越高. 因此為了能夠從一定程度上合理懲罰未評分熱門項目, 我們引入了項目流行度權重系數,在此次試驗中, 我們采用以下公式計算項目流行度, 其中()表示項目已被評分的總次數.

項目被評分總次數()越大則對應權重越小, 預測評分則會相應降低.最終我們采用如下方法進行缺失值預測填充.

3.2 項目聚類

缺失數據處理過后, 我們便可對項目進行聚類, 本次我們采用聚類算法中最經典的K-means算法進行項目聚類. 而傳統的K-means算法對初始聚類中心非常敏感, 聚類結果隨不同的初始輸入而有較大波動. 為消除這種敏感性, 本文采用袁方等提出的優化初始聚類中心的改進K-means算法[9]進行聚類計算. 與傳統聚類算法不同的是, 該算法在選取初始聚類中心時計算每個數據對象所在區域的密度, 選擇相互距離最遠的個處于高密度區域的點作為初始聚類中心. 實驗表明改進后的K-means算法能產生質量較高的聚類結果, 并且消除了對初始輸入的敏感性.

過程1. 基于項目的kmeans聚類 輸入: 聚類數目k, 最大迭代次數iter_num和用戶評分數據填充矩陣R輸出: k個聚類 1) 計算以項目集I中每個項目ij為中心, 包含常數Minpts個數據對象的半徑, 記為ij的密度參數. 越大, 說明數據對象所處區域的數據密度越低. 反之則說明數據對象所處區域的數據密度越高. 選取滿足的點ij為高密度區域D. 取D中處于最高密度區域的點作為第1個聚類中心rl; 取D中距離rl最遠的點作第2個聚類中心r2; 計算D中各數據對象ij到rl, r2的距離d(ij, r1), d(ij, r2), r3為滿足max(min(d(ij, r1), d(ij, r2)),j=1,2···n的數據對象ij; rm為滿足max(min(d(ij, r1), d(ij, r2)...d(ij, rm-1)),j=1,2···n的數據對象ij,ij∈D. 依此得到k個初始聚類中心. 記為集合centerold={r1, ···, rk}; 2) k個聚類簇cluster1, ···clusterk均初始化為空, 記為集合Cluster=(cluster1, ···clusterk)3) REPEATFOR each item i in I:FOR each center rjin centerold : 計算項目i和聚類中心rj的相似性; sim(i,rm)=max(sim(i,r1),sim(i,r2),···,sim(i,rk))EndforFor each clusterm in Cluster: 計算clusterm的均值, 生成新的聚類中心cnewm. Centernew={cnew1,cnew2,···, cnewk}EndforUTILCenterold=(c1, ···ck)和Centernew=(c1, ···ck)相同或達到最大迭代次數iter_num.4) 返回Cluster.

3.3 推薦生成

為了保證預測的精確性, 避免提前引入誤差, 我們在評分預測階段采用原始用戶評價矩陣而非填充矩陣. 并使用公式(1)計算待推薦用戶在待推薦項目所在類內與其余用戶的相似度, 構建用戶相似性矩陣. 查找與用戶相似度最大的個最近鄰. 使用公式(4)計算用戶預測評分, 得到最終評分預測值, 算法過程如下.

過程2. 評分預測 輸入: 原始用戶評價矩陣R, 最近鄰個數n, 待預測評分用戶u, 項目i, 項目i所在聚類簇clusterj=[il,ij,···,ip]. 輸出: 評分預測值 1) simDict={}2) For user v in U: IF v!=u: simDict[v]=sim(u,v) Endif Endfor3) Nu=sort(simDict)[:n]4)

其中, 此處,的特征向量為=(,,···,),= (,, ··· ,). sim(,)我們采用公式(1)所提供的相關相似性計算. 算法的復雜度為. 至此, 我們便可獲得指定用戶對指定項目的評分預測值, 為隨后的推薦提供支持.

4 實驗結果及分析

本次實驗的硬件平臺是配置Intel pentium E58003.2 GHz CPU, 4G RAM, 操作系統為ubuntu 14.04的個人計算機, 所有程序均由python實現.

4.1 數據集

本文采用的實驗數據集是目前衡量推薦算法質量常用的著名電影評分數據集MovieLens中的100k數據集(http://grouplens.org/datasets/movielens), 該數據集由美國明尼蘇達大學GroupLens研究小組創建并維護. 該實驗數據集共包含930個用戶對1682部電影的100000條評價信息, 其中每個用戶至少對20部電影進行了評分, 每個電影也都收到了用戶評論. 該數據集的稀疏性為1-100000/(943*1682) = 0.937. 數據集中用戶評分范圍是1-5, 數值越大代表用戶對該電影的興趣越大. 本次實驗按照80%和20%的比例隨機的將數據集劃分成為訓練集和測試集, 隨后進行5-折交叉實驗, 取五次試驗的平均值作為最終結果.

4.2 評價標準

平均絕對誤差MAE(mean absolute error)是目前學術研究中應用廣泛的推薦系統推薦質量評價標準. 其主要通過公式(7)計算測試集中用戶實際評分和推薦算法根據訓練集的訓練預測值的差的絕對值均值, 平均絕對誤差MAE越小, 推薦算法的質量越高. 其中表示測試集的數據個數,p為預測評分值,r為測試集中的實際評分值.

4.3 實驗結果分析

我們首先研究聚類個數對本文算法性能的影響. 實驗結果如圖1所示, 其中橫坐標表示聚類個數, 縱坐標表示MAE值, 最近鄰個數統一取=30.

圖1 聚類個數對MAE值的影響

通過圖1我們可以清晰看到剛開始, 隨著聚類族數的增多, 算法性能不斷提升, 當項目聚類個數為50時, 算法取得了最好的性能, 此后聚類族數的增多反而引起算法性能的下降. 接下來, 我們通過將本文所提出算法UPCF與傳統的基于用戶聚類的協同過濾算法(UBCF)[3]、綜合用戶和項目因素的協同過濾推薦算法(HCFR)[4]、基與不確定近鄰的協同過濾算法(UNCF)[6]的平均絕對誤差MAE進行對比觀測試驗性能. 為了縮短算法的運行時間, 聚類個數均設置為20.

圖2 算法性能比較

由圖2可以看出, 本文算法與其他算法在MAE值上有了10%左右的提高, 特別是當近鄰個數比較少的時候, 本文算法體現了非常好的推薦效果, 性能優勢明顯更好, 這充分說明本文提出算法最近鄰選擇的高效合理性. 我們也可以觀察到, 當最近鄰個數達到一定數量后, 所有算法的MAE性能趨于平穩, 這也反映出當近鄰相似度不斷減小時, 該近鄰對算法的性能提升沒有顯著的影響.

此外, 本文算法在提高推薦質量的同時并沒有帶來算法復雜性的提升. 數據的預填充和項目聚類均可提前離線完成, 僅需根據需求隔一段時間更新. 而評分預測由于不再依賴用戶全局特征, 單個評分預測的復雜性由變為, 其中表示用戶總個數,表示項目總個數,表示項目聚類個數. 用戶還可根據實際需求, 并行的在各個項目類內進行用戶評分預測.

5 總結

針對傳統協同過濾算法中最近鄰計算時所面臨的稀疏性和準確性挑戰, 本文提出了一種基于用戶部分特征的協同過濾算法. 該算法采用基于評分偏差與項目流行度的思想進行缺失值填充, 并在最近鄰構建時僅考慮用戶在該項目分類下的特征, 動態的根據待預測項目篩選用戶最近鄰, 從而提高了推薦的質量. 此外, 由于僅需考慮用戶類內特征, 該算法實現了一定程度的降維, 降低了算法的復雜性. 并可根據需要, 分布并發的計算各個類內用戶的預測評分值, 一定程度上提高了算法的實時性.

但算法中項目分類以及用戶最近鄰選擇時特征選擇的準確性仍需要進一步研究改良, 所使用的聚類算法K-means的聚類效果仍不是十分理想. 此外, 在此次研究前期對推薦算法的了解中, 我們發現目前針對各種推薦算法模型的融合以及算法并行化的研究也成為業界的新熱點. 而能夠更好地反應用戶興趣的用戶社交關系的引入[10,11]大大提高了協同過濾算法的近鄰可靠性和準確性, 為算法的改良提供了新的方向. 如何將用戶社交關系引入本文提出的算法, 進一步改善本文算法的性能, 將是下一階段研究的重點.

1 Park DH, Kim HK, Choi IY, Kim JK. A literature review and classification of recommender systems research. Expert Systems with Applications, 2012, 39(11): 10059–10072.

2 Bobadilla J, Ortega F, Hernando A, Gutiérrez A. Recommender system survey. Knowledge-Based Systems. 2013, 46: 109–132.

3 Ungar LH, Foster DP. Clustering methods for collaborative filtering. AAAI Workshop on Recommendation Systems, 1998, 1: 114–129.

4黃裕洋,金遠平.一種綜合用戶和項目因素的協同過濾推薦算法.東南大學學報(自然科學版),2010,40(5):917–921.

5 Amatriain X, Lathia N, Pujol JM, Kwak H, Oliver N. The wisdom of the few: A collaborative filtering approach based on expert opinions from the web. Proc. of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM. 2009. 532–539.

6 黃創光,印鑒,汪靜,劉玉葆,王甲海.不確定近鄰的協同過濾推薦算法.計算機學報,2010,33(8):1369–1377.

7 Koren Y. Factorization meets the neighborhood: A multifaceted collaborative filtering model. Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008. 426–434.

8 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法.軟件學報,2003,14(9):1621–1628.

9袁方,周志勇,宋鑫.初始聚類中心優化的K-means算法.計算機工程,2007,33(3):65–66.

10 Daly EM, Geyer W. Effective event discovery: Using cation and social information for scoping event recommendations. Proc. of the 5th ACM Conference on Recommender Systems. ACM. 2011. 277–280.

11 Guy I. Social recommender systems. Recommender Systems Handbook. Springer US, 2015: 511–543.

Collaborative Filtering Algorithm Based on User Partial Feature

LI Yong-Chao, LUO Jun

(Department of Computer Science, National University of Defense Technology, Changsha 410073, China)

As one of the most widely used algorithms in recommender system, the traditional collaborative filtering algorithm faces serious data sparseness problem in the big data trend, which leads to the ineffective in nearest neighbor selection, and restricts the performance of the algorithm. To address this problem, this paper proposes a collaborative filtering algorithm based on user partial feature(UPCF). In our method, it first rates the missing values based on rating bias and item popularity; and then clusters the items in the filled matrix with a K-means clustering algorithm of meliorated initial center. At last, it uses the user-based collaborative filtering algorithm with the user feature in item class to get the recommendations. The MAE measures on the MovieLens dataset shows that compared with the current popular algorithms, the performance of our UPCF algorithm improves about 10% without any increase of algorithm complexity.

item popularity; nearest neighbor selection; item clustering; collaborative filtering algorithm

2016-07-01;

2016-08-31

[10.15888/j.cnki.csa.005704]