一種結合項目屬性的混合推薦算法①

于 波, 陳庚午,2, 王愛玲,2, 林 川,2

?

一種結合項目屬性的混合推薦算法①

于 波1, 陳庚午1,2, 王愛玲1,2, 林 川1,2

1(中國科學院沈陽計算技術研究所, 沈陽 110168)2(中國科學院大學, 北京 100049)

傳統的協同過濾推薦算法中僅僅根據評分矩陣進行推薦, 由于矩陣的稀疏性, 存在推薦質量不高的問題. 本文提出了一種結合項目屬性相似性的混合推薦算法, 該算法通過計算項目之間屬性的相似性, 并且與基于項目的協同過濾算法中的相似性動態結合, 通過加權因子的變化控制兩種相似性的比重來改善協同過濾中的稀疏性問題, 并且將綜合預測評分和基于用戶的協同過濾預測評分相結合來提高推薦質量, 最終根據綜合評分來進行推薦. 通過實驗數據實驗證明, 該算法解決了協同過濾算法的矩陣稀疏性問題.

協同過濾; 混合算法; 綜合相似性; 稀疏性; 項目屬性

目前, 個性化推薦技術[1]是解決信息過載的主要的有效手段, 它根據分析用戶的歷史行為信息, 在海量信息中運用推薦算法自動快速的發現符合用戶個人興趣的服務和內容, 推薦算法作為個性化推薦技術的核心部分起到了重要作用, 其中協同過濾算法得到了廣泛地應用.

協同過濾算法[2-5]的基本原理是通過對用戶歷史行為數據的挖掘發現用戶的偏好, 基于不同的偏好對用戶進行群組劃分并推薦品味相似的商品. 根據協同過濾的相關特征, 協同過濾算法分成基于用戶的協同過濾算法和基于項目的協同過濾算法. 基于用戶的協同過濾首先計算活動用戶和其他用戶之間的相似度, 并從相似用戶的興趣為目標用戶進行推薦. 基于項目的協同過濾基于這樣的假設: 能夠引起用戶興趣的項, 必定與之前評分高的項相似.

本實驗室新媒體廣播項目主要是為沈陽廣播電臺, 煙臺廣播電臺和長春廣播電臺提供新媒體廣播服務, 旨在將電臺廣播與互聯網結合, 打造包括后臺服務、主持人端、導播端和移動端的一體化新媒體廣播服務平臺. 在移動端和主持人端的交互過程中發現, 服務平臺于廣播欄目的個性化推薦依然一種有效的推薦措施. 由于欄目的收聽和互動存在很強的時間聚集性,所以由此衍生的評分矩陣具有很強的稀疏性. 而且在協同過濾推薦算法中, 數據稀疏性問題是影響協同過濾系統推薦質量的一個關鍵原因, 由于評分矩陣的稀疏, 導致用戶相似性度計算的評分向量中共同評分項太少, 使得相似性的度量誤差變大, 最近鄰居搜尋的結果的準確性也就會變得難以保證, 最終進行評分預測時就會使最終的預測值和真實評分值之間產生較大的誤差, 從而影響推薦的準確度. 針對于此問題, 本文提出一種基于內容過濾和協同過濾相結合的混合模式推薦技術[6,7], 將基于項目屬性的相似性和協同過濾中基于項目的相似性結合, 提出一種新的相似性度量方法, 解決協同過濾中的矩陣稀疏問題.

1 相關工作

在大部分的推薦系統當中, 用戶對于項目的評分是非常有限的. 比如在視頻推薦的系統中, 視頻的數目數以十萬計, 然而用戶參與評價的視頻最多至幾十部, 再次基礎上的評分數據相當稀疏, 由此產生的評分向量并不能準確的計算用戶之間的相似性. 由此協同過濾的推薦質量大大下降.

協同過濾中矩陣稀疏性問題一直是人們研究的重點, 在眾多解決方法中, 最為簡單的辦法就是為用戶未評分的項目設定一個固定的缺省值, 一般將缺少的評分設定為整個評分范圍的中間值, 例如評分范圍為1~5分制時將評分設定為3分. 這種改進措施在一定程度上可以提高協同過濾的推薦準確度但是添加的缺省值并不能準確的表示實際評分情況, 所以此方法不能從根本上解決稀疏性帶來的問題. 目前很多學者也提出了可以有效解決協同過濾稀疏性的方法, 比較成功的主要有大類: 一種是通過數學原理降低矩陣的稀疏性, 通過奇異值分解技術平滑輸入矩陣, 降低矩陣的維數從而降低矩陣的稀疏性. 但是分解技術算法時間復雜度較高, 并且降低維數往往會導致評分矩陣中信息的丟失, 在評分極度稀疏的情況下, 效果并不理想. 另一種解決方法是通過融合推薦算法來解決協同過濾中矩陣稀疏性的問題, 在協同過濾的計算過程中加入內容的預測等. 本文即選擇了混合算法的策略, 提出了結合屬性相似性的協同過濾中的項目相似性的混合推薦算法.

2　算法相關理論

2.1 評分矩陣

推薦系統包含M個用戶和N個項目, 它們形成了一個 M×N的矩陣列表, 此列表即為用戶-項目評分矩陣, 矩陣中的值R表示用戶對項目的評分, 其中評分的值設置為0-5之間的整數, 如果R=0則表示用戶沒有對項目評分, 評分值越高表示用戶對項目喜愛程度越高.

2.2 相似度的計算方法

協同過濾算法中, 傳統的3種相似性度量方法分別為余弦相似性, 相關相似性和修正余弦相似性[8]. 本文采用修正余弦相似性計算方法. 在評分矩陣中, 每一個項目或者用戶都對應一個有評分構成的評分向量, 所以在基于用戶的協同過濾算法中, 用戶U---和用戶U的相似性計算公式如下所示:

表示用戶U---和U共同評分集合,表示平均評分.

和用戶的相似性計算類似, 在基于項目的協同過濾算法中, 項目V和V的相似性計算如下所示:

3 結合項目屬性相似的協同過濾研究

3.1 內容預測的原理

基于內容的推薦算法來源于信息檢索領域, 其基本原理根據項目的屬性特征構建項目的屬性特征文件, 然后通過項目的特征屬性文件與用戶的興趣愛好進行相似性匹配, 將用戶感興趣的項目推薦給用戶. 內容過濾的推薦技術僅僅考慮項目的屬性特征并不需要考慮到用戶的評價行為, 因此內容的預測不會受到用戶評分稀疏性的影響. 在此基礎上本節對協同過濾中加入項目屬性特征相似性進行了研究.

3.2 項目屬性相似性的計算

在協同過濾推薦算法中, 由于相似性是根據評分矩陣計算, 然而一些項目沒有足夠的評價, 所以由稀疏矩陣產生的評分向量并不能有效的計算項目之間的相似性[9]. 但是一般的協同過濾推薦系統會有對項目的簡單描述, 比如在廣播節目有欄目, 話題, 微博等類別屬性, 而欄目又具有生活, 醫療, 娛樂, 音樂, 交通等屬性. 這些欄目的屬性, 可以看成是有關項目的關鍵詞, 這樣, 每個項目Itemi就可以由關鍵詞來描述, 如下:

Itemi={A1, A2, …, An}

則通過分析項目信息就可以得到項目-屬性矩陣; 假設Item個數為n, 屬性的個數是k, 則項目-屬性矩陣如表1所示.

表1 項目-屬性表

其中, 1表示項目擁有屬性, 0表示沒有此屬性.

其中項目C和C表示項目V和項目V的屬性向量,表示結果向量中1的個數.

3.3 綜合相似性的計算

協同過濾的推薦效果一般要優于內容過濾[9], 因此, 在推薦過程中主要還是依賴協同過濾, 但是由于在評分矩陣極端稀疏的情況下, 對兩個項目進行評分的用戶集合可能很小. 如果只有一兩個用戶對項目共同評分, 即使算出的相似度較高其可信度也是較低的. 所以, 在基于項目的協同過濾中, 根據評分計算項目相似性的同時加入屬性的相似性, 將兩種相似行進行線性組合, 最終得到項目的綜合相似性.

在協同過濾算法中, 基于項目的基本原理是根據所有用戶對項目的偏好, 發現項目和項目之間的相似度, 即假設能夠引起使用者興趣的物品, 必定與其之前偏好的物品相似, 通過計算物品間的相關來做推薦[10]. 其原理如圖1所示.

如圖所示, 物品a同時被用戶a和用戶b喜歡, 物品c也同時被用戶a和用戶b喜歡, 因此可以認為物品a和物品c具有相似性, 同時用戶c喜歡物品a, 所以可以將與物品a具有相似性的物品c推薦給用戶.

根據上述原理, 通過評分矩陣提取出兩個項目的評分向量, 則通過基于項目的相似性計算公式即公式(2)可以得到兩個項目之間的相似性.

圖1 協同過濾原理圖

為了提高質量, 本文將兩種相似性進行線性組合, 引入權值變量λ, 由于基于評分的相似性與兩個項目的共同評分用戶的數量有關, 共同評分用戶越多相似性越準確, 所以權值變量λ的計算公式如下:

(5)

如公式所示, λ和兩個項目的共同評分用戶數目息息相關, 如果兩個項目的共同評分用戶數目越多, 則基于評分的項目相似性所占的比重越大, 從而使相似度計算更加準確.

通過分析公式(5)可知, 如果存在冷啟動項目, 即沒有用戶進行評價, 則λ的值為0, 此時可以根據項目本身的相似性計算得到其相似項目集合來預測評分. 如果存在評分矩陣極度稀疏的情況, 同樣λ的值會相應的減小, 根據評分計算的相似性比重也較少, 所以可以減少稀疏性對于相似性計算的影響, 由此可知, 綜合相似性的計算可以在一定程度上解決推薦算法中的矩陣稀疏性問題.

3.4 綜合評分的預測

由上述可知, 由綜合相似性得到的評分P僅僅是根據項目之間的相似性計算而來, 而忽略了用戶之間的相似性對于推薦算法的影響, 因此, 在得到項目之間的相似性的同時, 本文引入協同過濾中基于用戶的相似性計算. 在協同過濾中, 與計算項目相似性類似, 通過評分矩陣可以得到每個用戶的評分向量, 則通過公式(1)可以得到用戶之間的相似性, 由次引入基于用戶的協同過濾預測評分, 其計算公式如下:

(7)

在得到根據項目相似性計算的預測評分P和根據用戶之間的相似性計算的預測評分P之后, 通過權值因子將兩個評分線性組合, 通過實驗來確定的值, 最終得到綜合預測評分來進行推薦. 其組合公式如下:

其中為權重因子,∈[0,1].

3.5 推薦過程

為了解決協同過濾中冷啟動和稀疏性的問題, 本文引入了基于項目本身屬性相似性的計算, 將項目屬性相似和基于項目的協同過濾相似性線性結合, 然后將混合預測評分與基于用戶的協同過濾評分動態結合, 最終的到綜合預測評分. 其推薦過程如圖2所示.

推薦過程描述如下:

Step1: 根據公式(3)計算項目之間基于屬性的相似度.

Step2: 根據公式(2)計算項目之間基于評分的相似度.

Step3: 根據公式(5)計算項目之間的綜合相似度:.

Step4: 根據公式(6)計算基于項目綜合相似性的預測評分P.

Step5: 根據公式(7)計算基于用戶相似性的預測評分PU.

Step6: 根據公式(8)計算最終綜合預測評分P.

Step7: 根據綜合評分P對項目進行降序排序, 將集合的top—k推薦給用戶.

4 實驗結果及分析

4.1 實驗數據

本文采用本實驗室統計的用戶與欄目交互的實際數據, 用戶與欄目的互動行為包含收藏, 點贊, 評論, 閱讀, 和收聽五個行為, 根據用戶的行為為欄目打分, 其中收藏2分, 點贊, 評論分別1分, 閱讀收聽分別0.5分由此可得到用戶和欄目的評分矩陣. 根據實驗室得到的數據經過處理可以得到1000個用戶對97個欄目10000條評分記錄, 評分范圍為1~5. 數值越高表示用戶對欄目的偏愛程度越高, 本文將數據集按照80%的訓練集和20%的測試集劃分. 同時每部欄目都有其所屬的類別, 本文將欄目分成以下類別: 生活, 醫療, 音樂, 交通, 新聞, 教育, 談話, 服務, 戲劇, 綜藝. 然后將這10種類別作為欄目的屬性, 用于獲得欄目的屬性相似度.

4.2 度量標準

推薦系統常用的度量標準有平均絕對偏差MAE和均方根誤差RMSE. 本文采用平均絕對偏差MAE作為度量標準, MAE用于度量推薦算法的估計評分與真實值之間的差異. MAE值越小, 估計的準確性越高,定義如下:

其中P-為用戶對項目的預測評分,r為用戶對項目的真是實際評分,為測試集中記錄評分的個數.

4.3 實驗結果

實驗一: 確定權重因子.

取項目和用戶的最近鄰居數目都為30做實驗, 通過改變權重因子值觀測MAE的變化. 其中的值以0.1為步長從0.2變化到0.8. 混合推薦算法的平均絕對誤差MAE如圖3所示.

圖3 實驗一結果

從圖3可以看出, 當α的值取值太大或太小推薦效果并不是最好, 當α=0.6時MAE的值最小, 意味著推薦質量最好. 因此取α=0.6進行實驗二, 來確定最近鄰居數并比較兩種算法的優劣.

實驗二: 比較混合算法與協同過濾的優劣.

由實驗一確定α后, 通過改變最近鄰居數目來觀察MAE值的變化, 同時與基于用戶的協同過濾作推薦結果比較如圖4所示.

圖4 實驗二結果

從圖4可以看出, 當最近鄰居數目為50的時候推薦效果比較好, 而且通過兩個曲線比較可以看出, 混合算法的MAE相對于協同過濾算法有明顯的減小, 所以改進的推薦混合推薦算法具有比較好的準確性和比較好的推薦效果.

實驗三: 稀疏性比較

在通過實驗一和實驗二確定了α和最近鄰居的數目后, 此實驗通過改變評分矩陣的稀疏性來比較協同過濾和混合算法的優劣. 由實驗室的數據可以計算的當前數據集合的稀疏等級為1-10000/(97*1000)=0.89. 為此通過刪除評分數據來增加矩陣的稀疏等級, 刪除的策略為優先刪除參與評分用戶數目較少的項目的數據, 即優先刪除冷門欄目, 由此矩陣的評分更加稀疏. 分別選擇稀疏程度在0.89, 0.92, 0.95, 0.98數據集合進行試驗結果如圖5.

圖5 稀疏性比較

由實驗結果可知, 傳統的協同過濾在矩陣稀疏的情況下推薦質量會大大的減少, 而本文提出的混合推薦算法, 雖然隨著矩陣的稀疏增加推薦準確度也有所下降, 但是相對于協同過濾算法具有明顯的優勢. 因此混合推薦算法在降低了矩陣稀疏對于推薦結果的影響.

5　結語

本文對傳統推薦算法進行了優化, 增加權值因子來組合項目屬性相似性和協同過濾的相似性, 得到的相似性度量方法使得計算的項目的最近鄰居更加準確. 實驗結果表明, 本文提出的算法顯著提高了協同過濾推薦算法的推薦質量, 并且可以有效解決評分矩陣稀疏性的問題. 實驗不足之處是在解決用戶冷啟動問題上, 計算精度還有待提高, 需要進一步的深入研究.

1 冷亞軍,陸青,梁昌勇.協同過濾推薦技術綜述.模式識別與人工智能,2014,8:720–734.

2 楊博,趙鵬飛.推薦算法綜述.山西大學學報(自然科學版),2011,3:337–350.

3 劉青文.基于協同過濾的推薦算法研究[博士學位論文].合肥:中國科學技術大學,2013.

4 孔維梁.協同過濾推薦系統關鍵問題研究[博士學位論文].武漢:華中師范大學,2013.

5 Peng H. Research of collaborative filtering recommendation algorithm based on network structure. Journal of Networks, 2013: 810.

6 Gong S. A collaborative filtering recommendation algorithm based on user clustering and item clustering. Journal of Software, 2010, 5(7): 745–752.

7 張馳,陳剛,王慧敏.基于混合推薦技術的推薦模型.計算機工程,2010,22:248–250,253.

8 張旭陽.基于權重的混合推薦策略研究[碩士學位論文].昆明:云南大學,2015.

9 張騰季.個性化混合推薦算法的研究[碩士學位論文].杭州:浙江大學,2013.

10 高虎明,趙鳳躍.一種融合協同過濾和內容過濾的混合推薦方法.現代圖書情報技術,2015,6:20–26.

Hybrid Recommendation Algorithm Combined with the Project Properties

YU Bo1, CHEN Geng-Wu1,2, WANG Ai-Ling1,2, LIN Chuan1,2

1(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China)2( University of Chinese Academy of Sciences, Beijing 100049, China)

Traditional collaborative filtering recommendation algorithm only bases on matrix. Due to the sparsity of matrix, the quality of recommendation is not high. This paper proposes a hybrid recommendation algorithm whose similarity is combined with the properties of projects. This algorithm improves the data sparseness in collaborative filtering through the change of the weighted factor, controlling the proportion of two kinds of similarity that one is the similarity of attribute between projects and the other is the similarity of item-based collaborative filtering algorithm. And the comprehensive prediction score and user-based collaborative filtering prediction score are combined to improve the quality of recommendation. Finally, the recommendation is given according to the comprehensive scores. Experiments show that the algorithm has better recommendation quality.

collaborative filtering; hybrid algorithm; comprehensive similarity; sparse matrix; project properties

2016-04-06;收到修改稿時間:2016-04-27

[10.15888/j.cnki.csa.005490]