孫 紅,韓 震
(上海理工大學,上海 200093) (上?,F代光學系統重點實驗室,上海 200093) E-mail :1114580685@qq.com
隨著信息與互聯網技術的不斷發展,過去信息閉塞與匱乏的時代已經一去不復返,相反,人們進入了一個信息過載的時代.在這個時代當中,無論是消費者還是生產者,都會遇到一個棘手的問題:對于爆炸式增長的信息量,如何從大量信息中快速、準確獲取自己需要的信息[1].在這種背景下,為了解決信息過載的問題,推薦系統應運而生.推薦系統不需要用戶提供明確的需求,而是通過收集和分析用戶的歷史行為對用戶進行興趣建模,之后根據建立好的興趣模型主動給用戶推薦所需的信息.推薦系統應用于多個領域,在電影視頻推薦領域,Netflix比賽是標志性的視頻推薦系統比賽,旨在提高視頻推薦系統的推薦效果[2],另外尤其是在電子商務平臺領域中,例如eBay,亞馬遜,天貓,京東等等,推薦系統的推薦效果好壞對電子商務的發展有著巨大的影響[3].由此可見推薦系統的重要性,推薦系統的性能好壞最主要取決于推薦算法的優劣.傳統的推薦算法有基于內容的推薦、基于標簽的推薦、協同過濾推薦和混合推薦等等[4,5].隨著互聯網技術的發展,數據結構變得多樣化和復雜化,對傳統的推薦算法構成了一定的挑戰,傳統算法的不足之處也越來越明顯.例如,基于內容的推薦算法原理是提取用戶購買過的物品的特征,根據這些特征尋找具有相似性的物品推薦給用戶,但這導致算法無法處理具有非結構性特征的數據,而且無法將數據量化,這就對算法的使用領域產生了約束[6].協同過濾算法通過相似度計算,為目標用戶發現具有相同興趣的近鄰用戶,并對近鄰用戶進行分析,將近鄰用戶感興趣的物品推薦給目標用戶,幫助挖掘目標用戶的潛在興趣,彌補了基于內容的推薦算法的不足.但協同過濾算法仍有一定的缺陷,例如需要解決數據稀疏問題,用戶之間相似度的計算是基于共同評價過的物品,如果共同評價過的物品太少,則相似度計算結果就不是很準確[7].針對這一問題,近年來國內外的學者提出了各種改進的推薦算法,文獻[8]通過分析用戶之間的信任與親密度來建立信任模型,很好的解決了新注冊用戶的冷啟動問題;文獻[9]考慮物品熱門程度來改進用戶之間相似度的計算方法,一定程度上提高了推薦的準確度,但熱門程度只考慮了物品評價次數的絕對頻數,沒有考慮到相對頻率,無法消除數據集規模大小給相似度計算帶來的影響;文獻[10]基于Jaccard相似度公式引入了物品流行度來改進相似度計算,達到了挖掘冷門項目,提高推薦結果的覆蓋范圍的優化目的,但其將評分記錄數據轉換成隱性反饋數據,注重用戶對物品是否反饋,忽略了用戶反饋物品的興趣量化程度,丟失了評分數據的量化特征,對推薦的精確性有一定的影響;文獻[11]提出了基于熱門物品懲罰和用戶興趣變化的協同過濾算法,引入熱門物品懲罰項來優化相似度計算,引入用戶興趣變化來優化預測評分計算模型;文獻[12]通過分析物品熱門程度的影響,利用啟發式算法對用戶相似性度量方法進行優化,解決冷啟動問題;文獻[13]定量研究物品的熱門度與推薦精度之間的權衡,并以此改進傳統協同過濾算法,處理推薦系統中的長尾數據;文獻[14]通過先對物品項目進行聚類分析,然后再進行推薦處理,提高了推薦系統的準確性,并且降低了改進算法的時間復雜度,但沒有解決數據稀疏的問題.
針對基于皮爾遜相似度的傳統協同過濾算法,本文考慮到物品熱門程度對用戶相似性的影響,對皮爾遜相關系數進行優化達到性能提升的目的.本文首先描述傳統協同過濾算法原理及評價指標,之后提出了一種基于物品熱門因子優化相似度計算的改進算法,利用海量的MovieLens數據集在spark大數據分布式處理平臺進行實驗并得到實驗結果.
協同過濾(Collaborative Filtering,簡稱CF),簡單來說是利用某個興趣相投、擁有共同經驗之近鄰用戶的喜好來推薦感興趣的資訊給目標用戶,個人透過合作的機制給予資訊相當程度的回應(如評分)并記錄下來以達到過濾的目的,進而幫助別人篩選資訊,回應不一定局限于特別感興趣的,特別不感興趣資訊的紀錄也相當重要.傳統協同過濾算法可以分為基于用戶的協同過濾(User-CF)和基于物品的協同過濾(Item-CF).User-CF基本思想是將目標用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度,找到 K個近鄰用戶后,根據近鄰用戶的相似度權重以及他們對物品的偏好,預測目標用戶沒有偏好的未涉及物品,計算得到一個排序的物品列表作為推薦.Item-CF的原理和User-CF 類似,只是在計算近鄰時采用物品本身,而不是從用戶的角度,因此本文從User-CF角度進行改進.
通過User-CF算法產生推薦結果主要經過三個步驟:相似度計算、選擇近鄰用戶、評分預測.通過相似度計算得到目標用戶與其他用戶的相似度,選擇相似度最高的K個用戶作為近鄰用戶,分析近鄰用戶對物品的評價與評分來對目標用戶未涉及的物品進行預測評分,根據預測評分將物品進行排序作為推薦結果[15].
根據相似度主要計算出目標用戶的近鄰用戶,根據近鄰用戶的興趣來挖掘目標用戶的潛在偏好,因此相似度計算方法十分重要.用戶對物品的評分數據可用一個m×n的矩陣表示,其中,m為用戶的數量,n為物品的數量,第j行第k列的元素Rj,k表示用戶 j對物品 k 的評分.用戶—物品評分矩陣可由表1所示.用戶i和用戶j的相似度通過兩用戶共同評價過的物品的評價差異來衡量.主要的計算方法有歐氏距離和皮爾遜相關系數等.

表1 用戶—物品評分矩陣Table 1 User-Item rating matrix
用戶i和用戶j的相似度記作sim(i,j).文獻[9]說明了皮爾遜相似性在應用中要優于歐氏距離,這主要是由于歐氏距離在計算相似性時沒有反映用戶間的相關性.而皮爾遜相關系數用于度量兩個變量X和Y之間的線性相關,利用皮爾遜相關系數作為用戶相似度度量,優勢在于:用戶只要對物品的評分在整體上趨于一致,就認為用戶之間有較強的相似性,更為合理地體現實際應用中用戶之間存在的相似性.因此,本文也是在皮爾遜相似度基礎之上提出了一種改進算法的方法.
皮爾遜相似度計算公式如式(1):
(1)


(2)

預測準確度.平均絕對誤差(MAE)是最常用也是最有效的評價指標,其反映的是系統正確預測用戶對物品偏好的能力,MAE的值越小,則表明系統推薦的準確率就越高.假設測試集中對用戶i的物品推薦列表為Ti,則計算公式如下式(3)所示:
(3)
式中,|Ti|表示為用i戶推薦列表中物品的數量.
分類準確率.分類任務目的就是給目標用戶推薦最相關的n個物品.準確率和召回率是衡量分類效果的重要標準,可以很好的評測推薦算法的精度,準確率和召回率的值越高,表示推薦質量越好.設Ni為用戶i喜歡的物品集合,則準確率計算如下公式(4)所示:
(4)
準確率描述的是推薦列表中有多少比例的推薦物品發生在測試集里的用戶—物品評分記錄中.
召回率表示有多少比例的測試集里的用戶—物品評分記錄包含在推薦列表中.計算公式如下式(5)所示:
(5)
傳統的協同過濾算法通過比較用戶共同評分過的物品交集,根據物品的評分差值進行用戶相似度計算.這種相似度計算模型沒有考慮到物品熱門程度或者物品必需程度對相似度的影響.對于這些大眾性的熱門物品或者生活必需物品,絕大多數用戶都會購買或者評價,這些熱門物品無法體現或者較少地體現用戶的“個性”和潛在的興趣愛好,也就無法表現出用戶間的強相似性,這時應該減弱它們對用戶相似度度量的影響和貢獻.例如,兩個用戶都買過《新華字典》,但這不能說明兩個用戶具有相似性,因為絕大多數人都買過《新華字典》,無法體現用戶的興趣特征;反之,若兩個用戶都買過冷門的《推薦系統實踐》,則可以反映用戶擁有相似的興趣愛好,說明用戶比較相似.因此,冷門物品更能反映用戶之間的相似性,若用戶對同一件冷門物品進行過購買或者評價一致等行為,說明用戶具有相似性,冷門程度越高,則相似性越強.考慮到物品熱門程度,本文對相似性度量方法進行改進來提高算法性能.
基于3.1節分析內容,需要引入一個物品熱門因子來量化物品熱門程度對用戶相似性度量的影響或貢獻.文獻[9]總結得出了皮爾遜相關系數在度量用戶相似度時要優于歐氏距離和余弦相似度,因此本文在皮爾遜相關系數基礎上融合物品熱門因子來改進相似度計算方法.
3.2.1 物品熱門程度
物品熱門程度使用物品的評分頻率來衡量,即所有用戶中有多少比例的用戶對物品進行了評價行為.計算公式如下式(6)所示:
(6)
式中,fc表示物品c的熱門程度,|M|表示用戶的總數量,|mc|表示對物品c進行了評價的用戶數量,很明顯,fc取值介于0和1之間,fc值越接近1,則表明物品c越熱門.同時,采用評分頻率fc而不是評分次數|mc|來衡量熱門程度,這就避免了評分次數|mc|的絕對性,比如物品c的評分次數很大,但用戶基數總量更大,這就說明物品c不是很熱門,盡管|mc|的值很大.
3.2.2 物品熱門因子
物品熱門因子pf衡量物品熱門程度f對用戶相似性度量的貢獻.物品熱門程度f值越小,則其對用戶相似度的貢獻應該越大,即熱門因子pf值越大.物品熱門因子pf與熱門程度f成反比,計算公式如式(7)所示:
(7)
公式(7)其中,pfc稱為物品c的熱門因子,代表物品c熱門程度對用戶相似度的貢獻.α參數稱之為平衡參數,其取值范圍為α>0,表示物品的熱門程度對熱門因子的影響因數.熱門因子與熱門程度的函數關系可由圖1表現出來.

圖1 熱門因子與熱門程度Fig.1 Popular factors and frequency
分別對α取0.3、0.4、0.5、0.6、0.7等值,從圖1中可以看出熱門因子pf的取值范圍均為(1,+∞),表明對不同熱門程度的物品都獎勵了其對用戶相似度的貢獻,但獎勵程度不同,f越小,表明物品越冷門,pf值越大,對相似度貢獻就越大;f越大,表明物品越熱門,pf值接近為1,對相似度基本上沒有貢獻,與冷門物品相比相當于懲罰了熱門物品對相似度的貢獻,pf與f成反比關系.同時,平衡參數α越大,pf整體向上移動,對相似度的貢獻就越大.
3.2.3 皮爾遜相似度改進
本文在皮爾遜相似度基礎上融合物品熱門因子來進行改進,改進后的皮爾遜相似度sim(i,j)′計算方法如下公式(8):
(8)
在公式(8)中增加了物品熱門因子pf來達到用戶相似度改進的目的.對公式(8)與公式(1)進行對比發現,在計算改進的用戶相似度sim(i,j)′時融入了用戶共同評價過的每一個物品的熱門因子.若用戶i和j共同評價過的物品里有冷門物品,則相應的熱門因子pf大于1,sim(i,j)′>sim(i,j),表明用戶i和j具有更強的相似性;若用戶i和j共同評價過的物品基本上都是熱門物品,則相應的熱門因子pf接近為1,sim(i,j)′≈sim(i,j),表明用戶i和j的相似性沒有得到加強,熱門物品的熱門程度對用戶相似性沒有多大貢獻.因此,改進后的用戶相似度計算模型能夠更為合理和更為準確的描述用戶之間相似性.
通過分析物品熱門程度對用戶相似性的影響,融入物品熱門因子來改進皮爾遜相似度計算方法,挖掘出與目標用戶更加相似的近鄰用戶,根據更加相似的近鄰用戶可以向目標用戶推薦更為準確的物品,從而達到改進協同過濾算法的目的.融合物品熱門因子的協同過濾改進算法的基本步驟如下:

算法:融合物品熱門因子的協同過濾改進算法輸入:用戶物品評分矩陣R,目標用戶v,近鄰用戶數為K,物品推薦數目為H,平衡參數α.輸出:目標用戶v的推薦列表Tv,包含H個推薦物品步驟1. 根據平衡參數α利用式(6)和式(7)計算每個物品的熱門因子步驟2. 利用式(8)計算目標用戶v和其他用戶i之間的相似度sim(v,i)'步驟3. 對sim(v,i)'從大到小進行排序,取前K個用戶組成近鄰用戶集合Uv步驟4. 利用式(2)對每個鄰近用戶i∈Uv計算目標用戶v對物品的預測評分步驟5. 對得到的預測評分進行從大到小排序,取前H個預測評分對應的物品組成目標用戶v的推薦列表Tv,返回給目標用戶v
本文數據采用的是MovieLens電影評分的三個版本數據集,數據集中包含user-id,movie-id,rating等本文需要的信息.數據集規模詳細信息見表2所示,將改進后的算法應用到電影推薦中.

表2 MovieLens數據集介紹Table 2 Introduction of MovieLens datasets
數據集評分記錄規模按指數增長,所有數據集中的每個用戶都至少對20部電影進行了評分,評分最高分為5分,最低分為1分.分數越高表示用戶對電影越喜歡.
由于待處理的數據量比較大,評分記錄最高達到了1000萬條記錄,因此本文采用spark大數據處理平臺.Spark是開源的、基于內存的計算框架,適合進行spark Streaming數據流處理、spark SQL數據庫互動、MLlib機器學習等,因此spark可成為下一代用途廣泛的大數據運算平臺.使用spark大數據技術可以極大的提高計算效率和節約時間.
本文搭建了具有4節點的spark分布式計算平臺作為實驗環境.spark集群的環境配置信息與圖2所示.
實驗一共進行兩次,隨機選取數據集中的80%數據作為訓練集,剩下的20%數據作為測試集,選定近鄰用戶數目K為10,電影推薦數目H選定為25部.第一次實驗利用MAE指標來驗證改進算法的性能提升,并描述平衡參數對改進算法性能的影響,找出最優平衡參數;第二次實驗利用大小規模不同的數據集,對傳統算法、文獻[9]改進算法、本文改進算法進行性能比較,從準確率和召回率上驗證本文改進算法在不同規模的數據集中性能依然良好.

圖2 spark集群環境Fig.2 Environment of spark cluster
當α=0時,熱門因子pf=1,對衡量用戶相似度沒有任何貢獻,sim(i,j)′=sim(i,j),此時,算法為傳統的基于皮爾遜相似度的協同過濾算法.因此,平衡參數從0開始取值到1,步長為0.1,采用評分記錄為10萬條的數據集1進行實驗,選定近鄰用戶數K為10,電影推薦數目H為25部.使用平均絕對誤差MAE指標來分析不同 值下的算法性能,其中描述的是傳統協同過濾算法.實驗結果如圖3所示.

圖3 不同α值對應MAE值對比Fig.3 Comparison of MAE values with different alpha
從圖3的實驗結果中可以看出,未改進的傳統算法MAE值達到了0.802,隨著α增加到0.5時,本文改進算法的MAE值減小到最小值,為0.758,降低了5.48%;但當α繼續增大,MAE值開始增大,當α=1時,MAE值為0.828,算法表現比傳統算法還要差,這表明平衡參數α需要調優.
結合圖1熱門因子與熱門程度關系圖中可以看出,當α值比較小時,冷門物品與熱門物品對相似度的貢獻pf差別不是很明顯,對熱門物品的懲罰力度相對不大,盡管MAE值有所下降,改進算法性能有所上升,但未達到最佳性能;當α值比較大時,則過分的獎勵了冷門物品對用戶相似度的貢獻,比如,有兩個用戶共同評價過的物品只有一個冷門的物品p,這表明這兩個用戶相似性并不大,但改進后的算法認為這兩個用戶具有很強的相似性并進行推薦行為.導致了MAE值上升,改進算法的推薦準確率下降.因此,需要找出最優的平衡參數α.圖3表明在MovieLens電影推薦數據集中,α的最優參數可選為0.5.
采用不同數據規模的數據集對改進算法的性能進行驗證,α取實驗一中得出的最優值0.5,利用準確率(Precision)和召回率(Recall)評價指標進行評價.由于實驗數據規模比較大,數據集3的評分記錄達到了1000萬條,因此本文采用spark分布式大數據處理平臺進行實驗,將本文改進算法同時與傳統算法和文獻[9]改進算法進行對比.實驗結果如圖4召回率對比,圖5準確率對比所示.

圖4 召回率結果對比Fig.4 Comparison of recall
在圖4、圖5中,算法1表示傳統算法,算法2表示文獻[9]改進算法,算法3表示本文改進算法.

圖5 準確率對比Fig.5 Comparison of precision
根據圖4和圖5實驗結果顯示,本文改進算法和文獻[9]改進算法無論是在召回率還是準確率指標上,都比傳統算法有很大的性能提升.另外,對比本文改進算法與文獻[9]改進算法實驗數據發現,本文算法在召回率和準確率上均略優于文獻[9]改進算法.并且當評分記錄數據規模從10萬條增加到100萬條、1000萬條時,文獻[9]改進算法在召回率和準確率上基本沒有變化,而本文改進算法隨著數據規模的擴增,在召回率和準確率上都有小幅度的上升.當數據規模達到了1000萬條時,本文改進算法性能已經比較明顯地優于文獻[9]改進算法,在召回率上和準確率上分別高于文獻[9]改進算法14.4%和10.9%.這主要是由于文獻[9]改進算法采用物品評分頻數來衡量物品熱門程度,這就導致了當數據規模擴增時,盡管物品c的評分頻數|mc|增大,但用戶總數量|M|更大,也就是說有更少比例的用戶對物品c進行評價或購買行為,物品c的熱門程度沒有增加,但文獻[9]改進算法在計算用戶相似度時會引入更大的物品c熱門懲罰因子,不能準確的度量用戶之間相似性.而本文改進算法采用物品評分頻率衡量熱門程度f,避免了在數據規模過大的情況下評分頻數|mc|對用戶相似度帶來的絕對性影響,因此具有更好的推薦性能.
本文首先對傳統的基于皮爾遜相似度的協同過濾算法進行了分析,指出傳統算法在相似性計算方法上的不足之處并進行了算法改進,改進算法考慮了物品熱門程度對用戶相似度的貢獻.實驗結果顯示,在MAE,準確率和召回率等指標上改進算法要比傳統算法表現得更好.除了考慮物品熱門程度因素外,推薦系統需要根據具體應用來提高推薦質量,例如在電影推薦中,用戶的年齡,物品的標簽,電影的導演和演員等因素都可以影響推薦效果,需要研究人員根據具體場景改進或融合算法.另外,推薦系統需要大量的數據作為支撐,本文中使用的spark數據分布式處理平臺作為近年來最流行的大數據處理平臺,十分適合用于推薦系統后臺數據分析與處理,基于spark平臺開發推薦系統也是未來工程實現的發展方向之一.
[1] Xiang Liang.Recommendation system practice[M].Beijing:Posts & Telecom Press,2012:2-4.
[2] Thangiah S R,Fergany A,Wilson B,et a1.School bus routing in rural school districts[C].Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport,Spring,2008:209-232.
[3] Tao Yong-cai,Zhang Ning-ning,Shi Lei,et al.Researching on the dynamic management of data copy of cloud computing data in heterogeneous environment [J].Journal of Chinese Computer Systems,2013,34 (7):1487-1492.
[4] Goldberg D,Nichols D,Oki B M,et al.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM,1992,35(12):61-70.
[5] Xu Hai-ling,Wu Xiao,Li Xiao-dong,et al.Comparison study of Internet recommendation system[J].Software Journal,2009,20(2):350-362.
[6] Pera M S,Ng Y K.A group recommender for movies based on content similarity and popularity[J].Information Processing & Management,2013,49(3):673-687.
[7] Ma Hong-wei,Zhang Guang-wei,Li Peng,et al.Survey of collaborative filtering algorithms[J].Journal of Chinese Computer Systems,2009,30(7):1282-1288.
[8] Tang X,Chen M.Reputation-based recommendation trust model in the interoperable environment[C].International Conference on Electronics,Communications and Control.IEEE,2011:2226-2228.
[9] Zhou Hai-ping,Huang Cou-ying,Liu Ni,et al.Collaborative filtering recommendation algorithm based on rating prediction[J].Journal of Data Acquisition & Processing,2016,31(6):1234-1241.
[10] Hao Li-yan,Wang Jing.Collaborative filtering top n-recommendation algorithmBased on item popularity[J].Computer Engineeringand Design,2013,34(10):3497-3501.
[11] Wang Dao-ping,Li Zhi-long,Yang Cen.Knowledge push algorithm based on hot item punishment and user interest change[J].Systems Engineering,2014,32(1):118-123.
[12] Ahn H J.A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem[J].Information Sciences,2008,178(1):37-51.
[13] Steck H.Item popularity and recommendation accuracy[C].ACM Conference on Recommender Systems,Recsys 2011,Chicago,II,Usa,October.DBLP,2011:125-132.
[14] Sun Hui,Ma Yue,Yang Hai-bo,et al.Collaborative filtering recommendation algorithm by optimizing similarity and clustering users[J].Journal of Chinese Computer Systems,2014,35(9):1967-1970.
[15] Park J,Kim B I.The school bus routing problem:a review[J].European Journal of Operational Research,2010,202(2):311-319.
附中文參考文獻:
[1] 項 亮.推薦系統實踐[M].北京:人民郵電出版社,2012:2-4.
[3] 陶永才,張寧寧,石 磊,等.異構環境下云計算數據副本動態管理研究[J].小型微型計算機系統,2013,34(7):1487-1492.
[5] 許海玲,吳 瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報,2009,20(2):350-362.
[7] 馬宏偉,張光衛,李 鵬.協同過濾推薦算法綜述[J].小型微型計算機系統,2009,30(7):1282-1288.
[9] 周海平,黃湊英,劉 妮,等.基于評分預測的協同過濾推薦算法[J].數據采集與處理,2016,31(6):1234-1241.
[10] 郝立燕,王 靖.基于項目流行度的協同過濾TopN推薦算法[J].計算機工程與設計,2013,34(10):3497-3501.
[11] 王道平,李志隆,楊 岑.基于熱門物品懲罰和用戶興趣變化的知識推送算法[J].系統工程,2014,32(1):118-123.
[14] 孫 輝,馬 躍,楊海波,等.一種相似度改進的用戶聚類協同過濾推薦算法[J].小型微型計算機系統,2014,35(9):1967-1970.
本刊檢索與收錄
國內
中文核心期刊
中國學術期刊文摘(中英文版)收錄
中國科學引文數據庫(CSCD)來源期刊
中國科技論文統計源期刊
中國期刊全文數據庫(CJFD)收錄期刊
中國科技期刊精品數據庫收錄期刊
中國學術期刊綜合評價數據庫(CAJCED)收錄期刊
中國核心期刊(遴選)數據庫收錄期刊
中文科技期刊數據庫收錄期刊
國際
英國《科學文摘》(INSPEC)
荷蘭《文摘與引文數據庫》(SCOPUS)
俄羅斯《文摘雜志》(AJ,VINITI)
美國《劍橋科學文摘(自然科學)》CSA(NS); Cambridge Scientific Abstracts(Natural Science)
美國《劍橋科學文摘》CSA(T);Cambridge Scientific Abstracts(Technology)
美國《烏利希期刊指南》UPD(Ulrich′s Periodicals Directory)
日本《日本科學技術振興機構中國文獻數據庫》(JST,China)
波蘭《哥白尼索引》(IC, Index of Copurnicus)