一種基于自適應近鄰選擇的協(xié)同過濾推薦算法

彭玉+程小平

摘要：評分數(shù)據(jù)稀疏性問題和新用戶冷開始問題對推薦系統(tǒng)性能造成很大的影響，為了提高推薦精度本文提出了一種基于自適應組合協(xié)同過濾推薦方法ANCF。該算法首先通過推薦系統(tǒng)收集到的用戶特征數(shù)據(jù)和項目特征數(shù)據(jù)來改善原始相似度計算，然后再組合用戶鄰居集和項目鄰居集來為用戶未評分的項目進行預測評分。通過自適應協(xié)調因子協(xié)調處理兩方面的影響。通過實驗表明，該算法可以充分挖掘用戶群鄰居和項目群鄰居對推薦結果的預測作用，提高推薦系統(tǒng)的預測精度。

關鍵詞： 基于項目協(xié)同過濾；基于用戶協(xié)同過濾；推薦系統(tǒng)；相似性；屬性特征

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）16-0127-04

Abstract： Based on the analysis of the sparse problem and the cold start problem in the traditional collaborative filtering recommendation， a collaborative filtering recommendation algorithm based on adaptive nearest neighbor selection is proposed. The algorithm considers the influence factors of user characteristics and project attributes， and then calculates the nearest neighbor sets of target users and target projects by using the score similarity model. According to the situation of the sparse score data， the similarity measurement results of two aspects are handled by the adaptive coordination factors， so as to get the final project forecast score. Experiments show that the proposed algorithm can effectively balance the instability effects based on the user group score and the recommendation based on the project group， and effectively alleviate the problems caused by the sparse user rating data， so as to improve the prediction accuracy of the recommendation system.

Key words： item-based collaborative filtering； user-based collaborative filtering； recommendation system； similarity； attribute feature

1 概述

互聯(lián)網(wǎng)的迅速發(fā)展引發(fā)了信息過載問題[1]。推薦系統(tǒng)作為解決信息過載問題的重要手段，在電子商務領域被廣泛應用，主要通過發(fā)現(xiàn)用戶的潛在需求主動為用戶推薦感興趣的項目。在傳統(tǒng)的個性化推薦中，協(xié)同過濾推薦算法無疑是最成功的一種推薦技術。協(xié)同過濾推薦算法是基于某些特定項目的用戶之間的相似性計算，更一般而言，如果他們在某些項目上有類似的偏好，他們最有可能對一些其他項目感興趣。基于協(xié)同過濾的方法首先基于項目或基于用戶的相似性度量計算發(fā)現(xiàn)類似項目或用戶的鄰居，然后通過相似鄰居的評價，提出建議。雖然協(xié)同過濾是有效的，當用戶評分數(shù)據(jù)很少時，其推薦性能表現(xiàn)不佳。主要是由于數(shù)據(jù)極度稀疏，用戶只有幾個評級，相似度計算誤差很大，導致計算得到的鄰居集不準確，或者只能搜索到較少的鄰居，無法得到準確的推薦集[2]。

傳統(tǒng)的協(xié)同過濾推薦算法本質上是利用了用戶群或者項目群中個體與個體之間的相似性來尋找相似鄰居，用相似鄰居的歷史偏好來預測目標對象的喜好并做出推薦的過程。但是，當用戶評價數(shù)據(jù)極度稀疏或者新用戶和新項目的推薦問題時，只從相似用戶群或者相似項目群去搜索鄰居，得到的鄰居集都是比較片面的[3]。在現(xiàn)實生活中往往這兩者均不可或缺，可以考慮結合兩個群體來共同為當前對象做出預測。為了恰當平衡兩個群體對推薦結果的影響，可以定義一個隨案例數(shù)據(jù)變化而變化的近鄰因子。

2 傳統(tǒng)協(xié)同過濾方法

2.1 傳統(tǒng)相似性計算方法

協(xié)同過濾推薦的關鍵點是不同用戶之間的相似性度量。廣泛采用的方法是基于用戶的共同歷史評分數(shù)據(jù)項量來進行相似度的計算。在相似性計算方法中，雖然各有其優(yōu)缺點，但最常用的相似度量方法是余弦相似性、修正的余弦相似性和皮爾森相似性[4]。

1）余弦相似性：將用戶的評分數(shù)據(jù)轉換為多維向量，然后利用這些向量的余弦值來度量用戶之間的相似性。其定義如下：

最后預測分值較高的項目便是目標用戶的可能推薦項目，即是協(xié)同過濾推薦系統(tǒng)的推薦結果。

2.2 相似性度量計算的改良

在傳統(tǒng)的協(xié)同過濾算法中相似度的計算都是在用戶共同的歷史評分的向量空間上進行的，如果共同評分的數(shù)據(jù)較少，則這個相似性度量計算的誤差就會很大，使得推薦性能急劇下降。Herlocker等在文獻[5]中提出用修正因子來調整相似度的計算，Ma等在文獻[6]中提出了影響性修正權重因子的設置，我們定義用戶和用戶之間共同評分的產(chǎn)品集為，給產(chǎn)品和產(chǎn)品共同評分的用戶集為，通過過設定某個閥值來將原來的用戶相似度和產(chǎn)品相似度調整如下：

3 基于自適應近鄰選擇的協(xié)同過濾推薦算法

傳統(tǒng)的協(xié)同過濾推薦算法本質上是利用了群體內(nèi)（這里面的群體可能是用戶群，也可能是產(chǎn)品群）個體與個體之間的相似性（尋找對當前對象影響力最大的個鄰居）來為目標對象的偏好做出預測的過程。但是，當用戶評價數(shù)據(jù)極度稀疏或者新用戶推薦問題時，只從相似用戶群或者相似項目群去搜索鄰居，得到的鄰居集都是比較片面的。所以本文研究思路是從影響推薦的兩個群體（鄰居用戶群和鄰居項目群）之間尋找一個自適應地可隨案例數(shù)據(jù)變化而變化的近鄰因子，結合兩個群體來共同為當前對象做出預測。所以本文結合UserCF算法和ItemCF算法的集成算法來進行推薦，它綜合了兩種協(xié)同過濾算法的優(yōu)點，改善推薦精度。

3.1 基本定義

在本節(jié)中我們首先來探討協(xié)同過濾推薦系統(tǒng)中數(shù)據(jù)定義的問題。一般來說，推薦系統(tǒng)可以收集到用戶注冊信息，產(chǎn)品屬性信息以后用戶對已經(jīng)選擇過的歷史產(chǎn)品的評價信息[7]。通過對這些信息的進一步整理清洗可以建立3個信息數(shù)據(jù)矩陣，分別是用戶-項評分矩陣、產(chǎn)品（項目）特征屬性矩陣以及用戶特征信息矩陣。分別如表1、表2、表3所示。

3.5 推薦算法過程描述

輸入：評分矩陣，項目特征矩陣，用戶特征矩陣，參數(shù)。

輸出：推薦結果。

具體算法步驟如下所示：

1） 在矩陣中搜索用戶未評分的所有項目記為集合，任意一個項目作為目標項目。

2）基于用戶-項評分矩陣，按式（5）計算用戶與其他任一用戶的評分相似度，基于用戶特征屬性矩陣按（7）計算用戶與其他任一用戶的特征相似度，再按式（8）進行相似度組合，得到用戶間相似度。

3） 基于用戶-項評分矩陣，按式（6）計算項目與其他任一項目的評分相似度，基于項目特征屬性矩陣按式（9）計算項目與其他任一項目的特征相似度，再按式（10）進行相似度組合，得到項目間相似度。

4）對于預先設定的用戶相似度閥值，按式（11）中所對應的用戶為用戶的候選鄰居用戶，得到用戶的候選鄰居用戶集，同時計算到值，。

5）根據(jù)項目相似度閥值，按式（12）中所對應的項目為項目的候選鄰居項目，得到項目的候選鄰居項目集，同時計算到值，。

6）選擇輸入合適的調和參數(shù)并將值代入到式（13）中，來計算得到自適應近鄰選擇因子和的值。

7）通過公式（14）并結合之前計算的和，計算用戶對項目的預測評分。

循環(huán)如上步驟，得到用戶對所有未評分項目的預測評分，預測評分較高的項目則為推薦結果。

4 試驗結果及其分析

4.1 數(shù)據(jù)集

為了驗證本文新提出的推薦算法比傳統(tǒng)的協(xié)同過濾算法具有更好的性能，我們收集了MovieLens站點的相關數(shù)據(jù)集來完成相應實驗。MovieLens數(shù)據(jù)集是最常用來測試推薦算法性能的標準數(shù)據(jù)集[8]。此數(shù)據(jù)集包含100000個等級從1到5的評價數(shù)值，由943名用戶對1682部電影的評價。在這個數(shù)據(jù)集中，用戶被要求至少對20部電影進行評分，數(shù)據(jù)稀疏率是95%左右。在實驗中數(shù)據(jù)集被分為訓練和測試部分（80%用于訓練測和20%用于測試集）。

4.2 試驗結果及其分析

1）調整參數(shù)對推薦精度的影響

由于本文公式（8）中提出的用戶相似度度量中的為可調節(jié)參數(shù)，因此在取不同值時，所獲得的效果也不同，所以在該試驗中取值從0到1.0，每次增加0.1，觀察平均絕對偏差MAE（mean absolute error）的變化，MAE值越低推薦效果越好。實驗中調節(jié)因子取0.5，自適應因子取30，閥值取0.4，取0.55。選擇300個用戶進行測試，試驗結果如圖1所示。從圖1中可以看出，取值為0.7時推薦效果最好。

2）調整參數(shù)對推薦精度的影響

由于本文公式（10）提出的項目相似度度量中的為可調節(jié)參數(shù)，因此在取不同值時，所獲得的效果也不同，所以取值可能會對推薦精度有影響。所以在該試驗中取值從0到1.0，每次增加0.1，觀察MAE的變化。實驗中調節(jié)因子取0.5，自適應因子取30，閥值取0.4，取0.55。選擇300個用戶進行測試，試驗結果如圖2所示。從圖2中可以看出，取值為0.4時推薦效果最好。

3） 不同協(xié)同過濾算法推薦精度對比

將本文提出算法與其他協(xié)同過濾算法如Item-based CF， User-based CF以及近期業(yè)界比較領先的研究方法EMDP（Effective Missing Data Prediction）進行比較。從實驗結果可以看出本文改進的自適應近鄰選擇協(xié)同過濾算法（ANCF）獲得更低的MAE值，推薦效果更好。實驗結果如圖3所示。

5 結論

協(xié)調過濾推薦技術是推薦系統(tǒng)應用中的一個熱門研究，基于領域的方法作為協(xié)同過濾兩個分支之一，以其簡單、高效、穩(wěn)定和和解釋性強的特性廣泛應用于商業(yè)領域，但用戶-項矩陣的稀疏性問題是協(xié)同過濾的主要不足之處。本文根據(jù)基于用戶協(xié)同過濾算法和基于項目協(xié)同過濾算法各自的優(yōu)缺點，提出一種組合算法，針對預測數(shù)據(jù)的不確定性，同時在用戶群和項目群中搜索目標用戶的鄰居，并通過自適應因子來調節(jié)不同群體鄰居對推薦結果的影響。結合用戶以及項目的推薦結果，同時運用用戶鄰居和和項目鄰居來組合計算預測評分，大大改善了數(shù)據(jù)稀疏性對推薦性能造成的影響。不過這樣會增加推薦系統(tǒng)一些時間開銷，將來的研究將探討如何運用云計算和聚類技術等來降低算法的時間復雜性，加快推薦系統(tǒng)的推薦結果反饋時間。

參考文獻：

[1] Breese J， Hecherman D， Kadie C. Empirical analysis of predictive algorithms for collaborative filtering [C]. In： Proceedings of the 14th Conference on Uneertainty in Artifical Itelligence（UAI-98），1998：43-52

[2] 彭玉，程小平. 基于屬性相似性的Item-based協(xié)同過濾算法[J].計算機工程與應用，2007，43（14），144-147.

[3] 黃創(chuàng)光，印鑒. 不確定近鄰的協(xié)同過濾推薦算法[J].計算機學報，2010，33（8）：1369-1375.

[4] 鄧愛林.電子商務推薦系統(tǒng)關鍵技術研究[D].上海：復旦大學.2003

[5] Tsai C F， Hung C. Cluster ensembles in collaborative filtering recommendation[J].Appl， Soft Comput， 2012， 2：75-80.

[6] Qing Li S H M， Byeong Man Kim. A probabilistic music recommender considering user opinions and audio features[C]. Inf. Process， Manage， 2007：134-152.

[7] 彭玉，程小平.一種改進的Item-based協(xié)同過濾推薦算法[J].西南大學學報：自然科學版，2007，23（8）：132-136.

[8] Qing Li S H M， Byeong Man Kim. A probabilistic music recommender considering user opinions and audio features[C].Inf. Process， Manage， 2007：134-152.