一種優化的基于項目評分預測的協同過濾推薦算法
2008-12-31 00:00:00張忠平郭獻麗
計算機應用研究 2008年9期
摘 要：通過分析在用戶評分數據極端稀疏的情況下，現有的基于項目評分預測的協同過濾推薦算法中項目之間的相似性度量不準確以及新項目的冷開始問題，提出了一種優化的基于項目評分預測的協同過濾推薦算法。該算法在計算項目之間的相似性時，既考慮了項目的評分相似性，又考慮了項目的特征屬性相似性。實驗表明，優化后的算法使計算出的項目之間的相似性更準確，并有效地解決了新項目的推薦問題，使得數據稀疏性對推薦結果的負面影響變小，顯著提高了系統的推薦質量。
關鍵詞：推薦系統；協同過濾；屬性相似性；評分相似性
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)09-2658-03
Optimized collaborative filtering recommendation algorithmbased on item rating prediction
ZHANG Zhongping，GUO Xianli
(College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China)
Abstract:By analyzing the inaccuracy of item similarity and new item recommendation in present collaborative filtering algorithm based on item rating prediction under data sparsity condition，this paper proposed an optimized collaborative filtering recommendation algorithm based on item rating prediction.This algorithm considered for user rating and item attribute item similarity calculation. The experiment shows that the optimized algorithm makes the similarity between items more accurate and solves the problem of new item recommendation effectively. The algorithm reduces the negative effect on the final recommendation and can provide better recommendation results for the system.
Key words:recommender system; collaborative filtering; attribute similarity; rating similarity
1 協同過濾推薦技術綜述
協同過濾推薦技術是當前最成功的個性化推薦技術[1]。在協同過濾推薦中，用戶通過相互協作來選擇信息，即依據其他用戶對信息作出的評價來挑選信息。協同過濾方法對用戶的行為進行分析，并不關心信息的實際內容，系統通過收集用戶對信息的評價搜索具有相同興趣愛好的用戶，然后根據具有相同興趣愛好的用戶對信息的評價產生推薦結果。
協同過濾推薦主要分為基于用戶的協同過濾推薦和基于項目的協同過濾推薦。基于用戶的協同過濾是根據評分相似的最近鄰居的評分向目標用戶產生推薦。由于最近鄰居對項(電子商務中的商品、電影、音樂等)的評分與目標用戶非常相似，因此目標用戶對未評分項的評分可以通過最近鄰居對項的評分來進行預測。
為了找到目標用戶的最近鄰居進行推薦必須度量用戶之間的相似性，然后選擇相似性最高的若干用戶作為目標用的最近鄰居。計算用戶之間相似性的方法主要有：
a)余弦相似性(cosine)。用戶評分被看做是n維項目空間上的向量，如果用戶對項目沒有進行評分，則將用戶對該項目的評分設為0，用戶間的相似性通過向量間的余弦夾角度量。設用戶u和用戶v在n維項目空間上的評分分別表示為向量u和v，則用戶u和v之式中：分子為兩個用戶評分向量的內積；分母為兩個向量模的乘積，夾角越小，相似度越高。
基于項目的協同過濾推薦則是基于這樣一個假設：如果大部分用戶對一些項的評分比較相似，則當前用戶對這些項的評分也比較相似。所以可以根據當前用戶對目標項目的最近鄰居的評分預測當前用戶對目標項目的評分，然后選擇預測評分最高的前若干項作為推薦結果反饋給用戶。計算項目之間的相似性與計算用戶間的相似性類似，首先需要得到共同評分過項目i和項目j的用戶的集合，項目i和項目間的相似性
隨著電子商務系統規模的進一步擴大，用戶數目和項目數目急劇增加，導致用戶評分數據的極端稀疏性。在用戶評分數據極端稀疏的情況下，傳統相似性度量方法存在一定的弊端，使得計算得到的用戶或項目的最近鄰居不準確，推薦系統的推薦質量急劇下降。推薦系統面臨如下一系列的問題：
a)稀疏性。在許多推薦系統中，用戶—項評分矩陣相當稀疏，一般用戶評價信息所涉及的商品只占商品總數的1%~2%[2]，根據傳統的計算方法很難找到最近鄰居集合，導致推薦效果大大降低。
b)精確性。即提高對用戶的推薦質量。由于數據極端稀疏，推薦的可信度會隨之降低。
c)冷開始。如果一個新項目沒有人去評價它，則這個項目肯定得不到推薦，推薦系統就失去了作用。
d)擴展性。隨著用戶和項目數量的大大增加，現有大部分協同過濾算法將遭遇到嚴重的擴展性問題，難以保證系統的實時性要求。
為產生精確的推薦，保證推薦系統的實時性要求，研究者提出了各種不同的推薦算法，如協同過濾推薦系統、優化的協同過濾推薦算法[3]、聚類技術[4~6]、關聯規則技術[7]、基于圖的Horting圖技術[8]、基于用戶行為序列的推薦算法[9]、分類技術[10]、基于項目評分預測的協同過濾推薦技術[11]等以及基于修正條件概率的推薦算法[12]。
2 相關工作
2.1 基于項目評分預測的協同過濾推薦算法
由于用戶評分數據的極端稀疏性，傳統的相似性度量方法不能有效地計算目標用戶的最近鄰居，協同過濾推薦系統的推薦質量難以保證。為了解決用戶評分數據的稀疏性問題，最簡單的辦法就是將用戶對未評分項目的評分設為一個固定的缺省值，一般設為評分域的中間值或設為用戶的平均評分[1]。在余弦相似性度量方法中，將用戶未評分項目的評分假設為0。實驗表明，這些方法可以在一定程度上提高推薦系統的推薦精度，但在項目數量巨大且用戶評分數據極端稀疏的情況下，這樣假設的可信度不高。
文獻[11]提出的基于項目評分預測的協同過濾算法通過計算項目間的相似性，由用戶對相似項目的評分預測用戶對未評分項目的評分，使得用戶之間共同評分的項目比較多。在此基礎上計算得到的目標用戶的最近鄰居比較準確。該算法在解決數據稀疏性所帶來的問題和改善推薦結果的精確性方面有了一定程度的改進，但它在計算項目之間的相似性時，仍采用傳統的項目相似性度量方法。而在用戶評分數據極端稀疏的情況下(即代表共同評分過項目i和項目j的用戶集)中的用戶數目很少，用該方法不能準確地計算項目i和項目j之間的相似性，如果用戶集的用戶數目為0，用式(3)無法計算兩個項目之間的相似性。特別地，對于一個新項目，由于還沒有任何人對它作過評價，就無法找到它的相似項目集，該項目也就無法得到推薦。因此，傳統的相似性度量方法在評分數據極端稀疏時并不能有效地度量項目之間的相似性。由于無法準確度量項目間的相似性，后續的評分預測工作也將受到影響，從而影響到整個算法的推薦質量。
2.2 基于修正條件概率的推薦算法
在實際的推薦系統中，用戶評分多少是無法確定的，有些用戶可能評價的項目多一些，有些可能評價少一些，甚至只有一兩項，但這并不能說明這些用戶只喜歡該網站提供的項目中的一兩個。相反，對于某些只有很少評分的用戶來說，他們所給出的信息可能恰恰就代表了他在某一類項目上的偏好。如果僅僅因為評價信息過少而在用傳統的相似性度量方法計算時被忽略掉，就會造成信息的丟失。因此文獻[12]提出了基于修正條件概率的算法，充分利用了已有評分的作用，并在計算項目相似性時將項目的所屬類別考慮在內，使求得的目標項目的最近鄰更準確，提高了對未評分項目的預測精度，進而提高了系統的推薦質量。但該方法仍存在兩點不足：a）算法中用s表示項目i和項目j不屬于同一類別，用si表示項目i和項目j屬于同一類別。這樣的表示過于極端化，并不能進一步表明不同項目之間的類別相似程度。b)該算法在進行項目評分預測時首先將沒有任何用戶評價的新項目去掉，因此仍不能解決新項目的推薦問題。
基于上述分析，本文提出了一種優化的基于項目評分預測的協同過濾推薦算法，可以顯著提高系統的推薦精度。
3 優化算法描述
3.1 項目的特征屬性
傳統的協同過濾算法在進行目標項目的最近鄰查詢時僅依賴用戶對項目的已有評分來計算項目之間的相似性，而在實際的推薦系統中，用戶評分項目一般只占項目總數的1%~2%，評分數據的極端稀疏性導致了系統推薦質量大大降低。
在電子商務領域，任意項目（如電影，音樂等）通常都能用若干個典型的特征屬性來表示，在此將其抽象為{T1，T2，…，Tr}。建立如表1所示的項目特征屬性矩陣A，r為項目所具有的特征屬性數目。其中1表示某個項目具有某項屬性，0表示某個項目不具有某項屬性。項目特征屬性的抽取可以從項目的簡介網頁中提取，或者從推薦系統中用來記錄項目信息的表中整理得到，也可以通過人為輸入的方式獲得。
表1 項目特征屬性矩陣A
3.2 改進的項目相似性計算
為了在計算項目相似性時考慮到項目之間的屬性相似性對計算結果的影響，需要根據項目特征屬性矩陣A和式(4)計算系統中任意兩個項目(包括新項目)之間的屬性相似性，進而建立項目的屬性相似性矩陣T(T為n×n方陣，其元素的值以主對角線為軸對稱分布，即sim
通過矩陣T可以得到任意兩個項目的屬性相似性值。一般地，認為用戶對屬性比較相似的項目的評價也是比較相似的，所以本文利用項目之間的屬性相似性對傳統的相似性計算公式進行改進。
與這兩個項目之間的屬性相似性simT(i， j)進行線性組合，組合后的相似性作為項目
式中：α為設定用于調節基于兩種來源的項目相似性平衡參數。
3.3 優化后的推薦算法
為了解決在用戶評分數據極端稀疏的情況下，傳統相似性度量方法存在的不足以及新項目的冷開始問題，在文獻[11]提出的方法的基礎上再結合本文給出的改進措施，設計了一個綜合項目評分和項目特征屬性優化的基于項目評分預測的協同過濾推薦算法。通過該算法求出任意兩個項目之間的相似性，并給出相似性最高的k個鄰居，然后計算用戶對所有未評分項目的預測評分，最后根據相關相似性公式計算當前用戶的最近鄰居集合，并求得推薦集。算法1 綜合項目評分和項目特征屬性的推薦算法表述如下：
輸入：用戶—項目評分矩陣R， 項目特征屬性矩陣A， 最近鄰居個數k， 推薦集元素個數r， 項目相似性平衡參數α；
4 實驗及分析
4.1 數據集
本文實驗數據集取自MovieLens站點(http://movielens.umn.edu)，該站點是一個基于Web的研究型推薦系統，注冊用戶必須至少對他所擁有的電影中的15部進行評價才可使用該系統。因此，該站點所擁有的注冊用戶每一個人都至少對15部電影進行過評價。目前，該站點的用戶已經超過45 000人，用戶評分過的電影超過6 600部。從該站點數據集中隨機抽取100 000個評價數據作為實驗數據集，其中包含了943名用戶對1 682部電影的評價，并要求每一位用戶至少對100部電影進行了評價；同時，還整理出這1 682部電影的20個特征屬性并對每個特征屬性賦予了一定的權值。將該實驗數據集分為訓練集和測試集兩部分進行實驗，其中訓練集數據占整個數據集的80%，測試集占整個數據集的20%。
4.2 評價標準
評價推薦系統推薦質量的度量標準采用統計度量方法中的平均絕對偏差MAE(mean absolute error)進行度量。MAE通過計算預測的用戶評分與實際的用戶評分之間的偏差來度量預測的準確性，MAE越小，推薦質量越高。對于評分數據，預測的評分集合表示為{p1，p2，…，pN}，實際的評分集合表示為{q1，q2，…，qN}，采用常用的推薦質量度量方法MAE=Ni=1|pi-qi|/N進行度量。
4.3 實驗結果及分析
為了檢驗本文提出的算法的有效性，采用基于項目評分和項目特征屬性相結合的方法來計算項目之間的相似性，在此基礎上利用本文提出的優化算法計算推薦集。同時將本文的算法與文獻[11]中原始的基于項目評分預測的協同過濾算法以及文獻[12]提出的一種改進算法，即基于修正條件概率的推薦算法作比較，計算各種推薦算法的MAE。鄰居個數從2增加到18，間隔為4，實驗結果如圖1所示。
由圖1可知，在鄰居個數不同時，本文提出的優化的基于項目評分預測的協同過濾推薦算法總具有最小的MAE。因此，在用戶評分數據極端稀疏的情況下進行
項目相似性度量時，綜合考慮項目之間的評分相似性和項目之間的屬性相似性的方法可以顯著地提高推薦系統的推薦質量。
5 結束語
本文提出了一種優化的基于項目評分預測的協同過濾推薦算法。該算法在計算項目相似性時既考慮了項目之間的評分相似性，又考慮了項目之間的屬性相似性，使得數據稀疏性對計算結果的負面影響變小。實驗結果表明，本文提出的優化算法能夠有效地解決評分數據的稀疏性和新項目的推薦問題，在一定程度上提高了系統的推薦質量。
參考文獻：
［1］BREESE J， HECHERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]//Proc of the 14th Conference on Uncertainty in Artificial Intelligence. 1998:43-52.
[2]SARWAR B， KARYPIS G， KONSTAN J，et al.Itembased collaborative filtering recommendation algorithms[C]//Proc of the 10th International Conference on World Wide Web.New York:ACM Press，2001:285-295.
[3]AHN H J.A new similarity measure for collaborative filtering to alleviate the new user coldstarting problem[J].Information Sciences，2008，178(1):37-51.
[4]HERLOCKER J，O′CONNER M.Clustering items for collaborative filtering[C]//Proc of the ACM SIGIR Workshop on Recommender Systems.New York:ACM Press，1999:439-446.
[5]鄧愛林，左子葉，朱揚勇.基于項目聚類的協同過濾推薦算法[J]. 小型微型計算機系統，2004，25(9):16651670.
[6]王輝，高利軍，王聽忠.個性化服務中基于用戶聚類的協同過濾推薦[J].計算機應用，2007，27(5):12251227.
[7]SARWAR B，KARYPIS G，KONSTAN J，et al.Analysis of recommendation algorithms for ecommerce[C]//Proc of the 2nd ACM Conference on Electronic Commerce. New York: ACM Press，2000:158167.
[8]WOLF J，AGGARWAL C，WU K L，et al.Horting hatches an egg:a new graphtheoretic approach to collaborative filtering[C]//Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press，1999:201-212.
[9]CHO Y B，CHO Y H，KIM S H.Mining changes in customer buying behavior for collaborative recommendations[J].Expert Systems with Applications，2005，28(2):359-369.
[10]LEE J S，JUN C H，LEE J，et al.Classificationbased collaborative filtering using market basket data[J].Expert System with Applications，2005，29(3): 700704.
[11]鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報，2003，14(9):16211628.
[12]周軍鋒，湯顯，郭景鋒.一種優化的協同過濾推薦算法[J].計算機研究與發展，2004，41(10):18421847
