基于相似傳播和情景聚類的網絡協同過濾推薦算法研究

曾群　程曉

〔摘要〕互聯網時代，個性化推薦系統逐漸被應用到各個不同的領域，隨之個性化推薦算法也成為目前研究的熱點。然而，傳統的推薦算法往往存在著冷啟動、數據稀疏等問題。本文在對傳統推薦算法研究的基礎上，提出了一種基于相似傳播和情景聚類的協同過濾推薦算法，根據計算用戶間的情景相似度對用戶進行聚類，然后根據相似傳播原理找出目標用戶更多的最近鄰居，最后根據預測目標用戶對項目的評分進行推薦。借助網上公共數據集在Matlab上實現了該算法并驗證了算法的有效性。實驗結果表明，本文所提算法的準確性相比傳統算法有所提高，同時緩解了傳統推薦算法存在的冷啟動和數據稀疏性等問題。

〔關鍵詞〕相似傳播；情景聚類；協同過濾；推薦算法

DOI：10.3969/j.issn.1008-0821.2016.11.009

〔中圖分類號〕G2062〔文獻標識碼〕A〔文章編號〕1008-0821（2016）11-0050-05

〔Abstract〕In the age of the Internet era，the personalized recommendation system gradually is applied to different fields and recommendation algorithm has become a research hot spot at present.Traditional recommendation algorithm，however，often has some problems，for example a cold start，sparse data.In this paper，on the basis of researches on traditional recommendation algorithm，this paper proposed a collaborative filtering recommendation algorithm based on similarity propagation and context clustering.Computing the similarity between user for user clustering，then the paper found more nearest neighbors of target users，according to the similarity propagation to finally，it recommended projects according to the forecast target users ratings.With the help of online public data，the paper implemented the proposed algorithm and verified the effectiveness of the proposed algorithm on Matlab.experiment showed that the accuracy of the proposed algorithm compared with the traditional algorithm was higher，and the proposed algorithm relieved the problems of traditional recommendation algorithm，such as the cold start and sparse data，etc.

〔Key words〕similarity propagation；context clustering；collaborative filtering；recommendation algorithm

如今，互聯網已經成為人們獲取信息的重要途徑。然而，隨著網絡上信息量越來越大，信息過載的問題也越來越嚴重，這對人們在網上快速查找精確信息造成了很大的困難。個性化推薦系統能夠根據用戶的興趣偏好、項目、需求甚至通過感知用戶的情景來向用戶推薦信息，這不僅很好地解決了信息過載的問題，同時還滿足了用戶的個性化需求。在實際應用方面，亞馬遜、當當等大型電商網站都開發出了自己的推薦系統。在學術研究領域，個性化推薦方面的研究也逐漸進入學者的視野并得到關注，例如美國的Grouplens團隊、Alexander Tuzhilin教授、Paul Resnick教授等對個性化推薦系統及相關的推薦算法進行了深入的研究[1]。

1問題的提出

協同過濾推薦算法作為目前研究較成熟、應用范圍較廣的推薦算法已被廣泛地運用于互聯網各大推薦系統中[2]。然而，傳統的協同過濾推薦算法推薦的準確率和推薦效率往往受到多方面的影響，如對于新用戶存在的冷啟動問題和由于評分矩陣數據稀少導致的數據稀疏問題對推薦算法的質量產生的影響。

本文對傳統的推薦算法進行了改進，將相似傳播的思想和用戶的情景與協同過濾推薦相結合，提出了一種基于相似傳播和情景聚類的網絡協同過濾推薦算法，在傳統協同過濾算法存在的問題得到了較好緩解的同時也提高了推薦算法推薦的準確率。

2相關概念及理論

21情景的定義

情景在不同的領域有不同的定義，心理學、情報學、哲學、組織行為學、教育學、社會學等領域的眾多學者都對情景進行了深入的研究和探討，但關于情景的定義學者們都各執己見，不能達成一致共識，因此情景一直沒有統一的定義。Dey等人認為能描述某一實體特征的信息即為情景[3]。雖然這一定義目前被廣泛引用，但由于不同領域對情景的理解各不相同，情景的定義一直無法準確給出。大多數學者都認同：情景是和實體是不可分的，情景只有與實體產生聯系才具有意義，情景可以將實體的相關信息進行詳細的描述。

22聚類的概念

聚類是利用一定的方法將數據集合劃分成簇中各成員間相似度較高但簇與簇間各不相同的多個簇的過程。聚類的結果往往隨著所使用的聚類方法的改變而改變，使用不同的聚類方法對相同的數據集進行聚類，產生的最終結果也可能不同。劃分的過程不是通過人，而是通過聚類算法進行的。

23協同過濾推薦

協同過濾推薦（Collaborative Filtering Recommendation，CFR）是根據用戶的興趣偏好及相關信息找到與用戶相似的群體，將該群體感興趣的內容作為待推薦的內容推薦給用戶。協同過濾推薦不需要用戶顯式查找自己感興趣的內容或項目，而是根據已有用戶對項目的評分來預測計算該用戶的評分，進而根據評分高低對用戶進行推薦，因此該方法在許多領域得到廣泛的應用。

3傳統協同過濾推薦算法

協同過濾推薦的原理是根據用戶的興趣偏好及相關信息找到與用戶相似的群體，將該群體感興趣的內容作為待推薦的內容推薦給用戶。其中，基于記憶的協同過濾在實際運用中運用范圍較廣，它又可以根據被計算相似度的對象的不同分為用戶和項目兩種類型[4]。

31基于用戶的協同過濾

基于用戶的協同過濾（User-based CF）推薦算法首先是查找與目標用戶相似的群體（即目標用戶的最近鄰），這一過程通常通過利用系統中已有“用戶-項目”評分矩陣中的評分數據來計算用戶與用戶之間的相似度來完成；然后根據生成的最近鄰集合中的用戶對項目的評分數據，利用評分預測計算公式來計算得到目標用戶對某一項目的預測評分；最后根據預測結果對目標用戶進行推薦。整個推薦過程大致可分為目標用戶最近鄰查找和目標用戶對項目的評分預測。余弦相似性、修正的余弦相似性、Tanimoto系數，Pearson相關系數[5]等是在計算相關系數時較常使用的方法。

User-based協同過濾推薦算法在計算用戶間的相似度時多是采用Pearson相關系數的計算方法，根據已有用戶對項目的評分矩陣進行計算。計算用戶u與u′間的相似度，計算公式如下：

sim（u，u′）=∑s∈I（u，u′）（r（u，s）-（u））（r（u′，s）-（u′））∑s∈I（u，u′）（r（u，s）-（u））2（r（u′，s）-（u′））2

其中，r（u，s）代表用戶u對項目s的評分，r（u′，s）代表用戶u′對項目s的評分；（u）代表用戶u對所有項目評分的平均分，（u′）代表用戶u′對所有項目評分的平均分；I（u，u′）代表用戶u與用戶u′都有評分的項目的集合。

通過計算目標用戶與非目標用戶間的相似度找到與目標用戶相似的用戶群體，將該群體的集合作為目標用戶的最近鄰集合D。生成最近鄰集合后，將最近鄰集合中用戶對項目的評分數據代入評分預測公式來對目標用戶進行偏好預測。預測目標用戶u對某一項目s′的評分時可采用如下公式[6]：

P（u，s′）=∑u′∈D[sim（u，u′）R（u′，s′）]∑u′∈Dsim（u，u′）

其中R（u′，s′）代表用戶u的最近鄰集合中的用戶對項目s′的評分，sim（u，u′）代表用戶u與u′的相似度，D為用戶u的最近鄰集合。

以上公式計算出來的預測結果將作為對目標用戶進行推薦的依據。

32基于項目的協同過濾

基于項目的協同過濾（Item-based CF）推薦算法首先是找到與項目相似的項目群，這一過程通常通過利用已有用戶對項目的評分數據計算項目與項目之間的相關系數來完成；項目相似群生成后，根據用戶對群體中各項目的已有評分數據來計算用戶對某一項目的預測評分；最后根據評分計算結果對用戶產生相關推薦。計算項目t與t′間的相似度，計算公式如下：

sim（t，t′）=∑u∈u（t，t′）（r（u，t）-（t））（r（u，t′）-（t′））∑u∈u（t，t′）（r（u，t）-（t））2（r（u，t′）-（t′））2

其中，r（u，t）代表用戶u對項目t的評分，r（u，t′）代表用戶u對項目t′的評分；（t）代表所有用戶對項目t評分的平均分，（t′）代表所有用戶對項目t′評分的平均分；u（t，t′）代表對項目t與t′都有評分的用戶的集合。

根據項目間相關系數的計算生成項目的最近鄰集合I，之后根據生成的相似的項目群體來預測用戶對項目的評分。如計算用戶a對項目i的預測評分，計算公式如下[7]：

P（a，i）=（i）+∑j∈I（i，j）sim（i，j）（r（a，j）-（j））∑j∈I（i，j）sim（i，j）

其中，（i）代表所有用戶對項目i評分的平均分，（j）代表所有用戶對項目j評分的平均分；sim（i，j）代表項目i與項目j間的相似度；I（i，j）代表項目i的最近鄰集合。

計算出預測評分后依據預測結果對用戶進行推薦。

然而，對于新用戶和評分數據較少的用戶，利用傳統的協同過濾推薦算法很難對其進行準確的推薦。本文在對傳統推薦算法研究的基礎上，將相似傳播的思想和用戶的情景與協同過濾推薦相結合，提出了一種基于相似傳播和情景聚類的協同過濾推薦算法，對傳統的推薦算法進行改進以解決冷啟動及數據稀疏等問題。由于在個性化推薦的過程中充分考慮用戶的情景，使得推薦結果更能滿足用戶個性化的需求，準確率也相對較高。

4基于相似傳播和情景聚類的協同過濾推薦算法

41算法思路

基于聚類的協同過濾推薦算法是根據一定的聚類算法利用已有的“用戶-項目”評分矩陣將用戶分成多個不同的簇，通過計算用戶與各簇的距離來找到與目標用戶距離最小的簇作為目標用戶的相似用戶群體，最后將目標用戶相似群體中的用戶對某一項目的加權平均分作為目標用戶對該項目的評分，以此方式來預測目標用戶對項目的偏好程度，然后對用戶進行推薦。

然而對于新用戶，由于缺少相關信息，在查找用戶最近鄰時可能會出現很大的誤差，最終影響推薦的準確性。情景能很好地描述用戶的特征，對個性化推薦有著至關重要的影響。

本文將用戶的情景因素引入到個性化推薦中，充分考慮情景對推薦效果的影響，對原有的基于聚類的協同過濾推薦算法在相似度計算公式和用戶評分預測公式進行改進，提出了一種基于相似傳播和情景聚類的協同過濾推薦算法。該算法根據用戶的情景對用戶進行聚類，同時引入相似度傳播的思想，能夠很好地緩解以前算法存在的數據稀疏性問題。

相似傳播，就是根據每個用戶或項目的最近鄰找出最近鄰的最近鄰，這樣能尋找出與目標用戶相似的更多的鄰居，提高推薦結果的準確性。例如，若用戶u的最近鄰為u1，而u1的最近鄰為u、u2和u3，則在預測用戶u對某一項目的評分時，可以根據一定的算法利用用戶u1、u2和u3的評分預測用戶u的評分，最終進行推薦。

在推薦系統中利用情景對推薦信息進行過濾的時間并非是固定的，根據利用情景的先后，可將情景感知推薦系統分為情景預過濾、后過濾與建模3種不同的形式[8]。情景預過濾是在推薦過程中首先根據用戶的情景剔除部分不匹配數據，生成與用戶情景相關的評分數據集，之后根據推薦算法對數據集進行用戶評分預測，最終將與用戶情景匹配的結果推薦給用戶。本文所提算法工作流程圖如圖1所示：

42算法

本文所提算法大致可分為以下3個步驟：

421聚類

本文根據用戶情景的不同將用戶進行聚類。首先確定出k個聚類中心，然后計算不同情景間的相似度，依此將用戶分成k個簇，使得每個簇中的用戶有相似的情景。由于情景的屬性是混合型的，在計算情景間相似度前需對用戶的情景進行抽象描述。本文通過采用余弦相似性計算用戶情景的相似性對用戶進行聚類。將用戶的情景定義為C，計算情景C1與情景C2間的相似性的計算方式如下：

sim（C1，C2）=C1·C2C1C2

通過計算情景間的相似性，將情景相似度高的用戶聚類在一起，生成情景最近鄰集合M。

422最近鄰集合的生成

計算目標用戶到通過情景聚類得到的各簇之間的距離，找到與目標用戶距離最近的簇，并計算目標用戶與簇中各用戶間的相似度。本文在傳統的計算用戶相似度的基礎上引入用戶的情景因素，對傳統的相似度計算方法進行改進，提出了基于情景的用戶相似度的計算，如計算目標用戶u與用戶u′間的相似度，計算方法如下：

sim（u，u′）=∑j∈I（u，u′，c）（r（u，c，j）-（u，c））（r（u′，c，j）-（u′，c））∑j∈I（u，u′，c）（r（u，c，j）-（u，c））2（r（u′，c，j）-（u′，c））2

其中，r（u，c，j）代表用戶u在情景c下對項目j的評分，r（u′，c，j）代表用戶u′在情景c下對項目j的評分；（u，c）代表用戶u在情景c下對所有項目評分的平均分，（u′，c）代表用戶u′在情景c下對所有項目評分的平均分；I（u，u′，c）代表用戶u與用戶u′在情景c下有共同評分的項目的集合。

根據以上公式計算出目標用戶與簇中各用戶的相關系數，將與目標用戶相似度較高的用戶放入同一集合中，生成目標用戶的最近鄰集合N。

在計算項目與項目間的相似度時，本文在基于項目的協同過濾經典算法Slope One算法[9]中引入用戶的情景，形成“用戶-情景-項目”模型，在計算項目間相似度時將情景因素對用戶對項目評分的影響考慮在內，提出基于情景的項目相似度計算方法，計算項目t與項目t′的相似度的計算方法如下：

sim（t，t′）=1-∑u∈U（c，t，t′）[r（u，c，t）-r（u，c，t′）]U（c，t，t′）Pm

其中r（u，c，t）代表用戶u在情景c下對項目t的評分，r（u，c，t′）代表用戶u在情景c下對項目t′的評分；U（c，t，t′）代表在情景c下對項目t與t′均有評分的用戶數，U（c，t，t′）代表在情景c下對項目t與項目t′均有評分的用戶的集合，Pm表示滿分評分。

通過計算項目間的相關性生成項目的相似項目群作為項目的最近鄰集合A。

423推薦的生成

假設用戶u的用戶最近鄰集合表示為N，情景c的情景最近鄰集合表示為M，項目t的項目最近鄰集合表示為A，則用戶u在情景c下對項目t的預測評分Gu，c，t可通過目標用戶u的用戶最近鄰集合N中的用戶在情景c下對項目t的評分，目標用戶u在情景c的情景最近鄰集合M下對項目t的評分，以及目標用戶u在情景c下對項目t的項目最近鄰集合A中項目的評分求得。用戶u在情景c下對項目t的預測評分計算方法如下：

Gu，c，t=13k1∑u′∈Nsim（u，u′）[R（u′，c，t）-（u′，c）]+（u，c）+k2∑c′∈Msim（c，c′）[R（u，c′，t）-（c′，t）]+12[（c，t）+（u，c）]+k3∑t′∈Asim（t，t′）[R（u，c，t′）-（c，t′）]+（c，t）

其中k1=1∑u′∈Nsim（u，u′），k2=1∑c′∈Msim（c，c′），k3=1∑t′∈Asim（t，t′）。R（u′，c，t）代表用戶u′在情景c下對項目t的評分，R（u，c′，t）代表用戶u在情景c′下對t的評分，R（u，c，t′）代表用戶u在情景c下對項目t′的評分；（u′，c）代表用戶u′在情景c下對所有項目評分的平均分，（c′，t）代表所有用戶在情景c′下對項目t評分的平均分，（c，t′）代表所有用戶在情景c下對項目t′評分的平均分；（u，c）代表用戶u在情景c下對所有項目評分的平均分，（c，t）代表所有用戶在情景c下對項目t的評分的平均分。

43實驗和結論

為了驗證本算法的有效性，筆者利用Matlab進行了驗證。本文用來驗證的數據集來自Grouplens提供的公開數據集，該數據集中包含了用戶的情景信息、用戶對電影的評分（1～5分之間）。筆者通過對公開數據集中數據的處理，從原始數據集中選出評分較多的用戶，其中包括1 000名用戶在不同情景下對3 000部電影做出的160 000條評分作為驗證數據，其中用來訓練的數據占70%，用來測試的數據占30%，實驗對預測分數達45分以上的電影向用戶做推薦。

在仿真過程中，通過計算不同算法（含本文算法與傳統算法）間的平均絕對誤差（MAE，Mean Absolute Error）來加以證明本文算法的有效性。設預測評分集合為P={p1，p2，p3，…，pi，…，pn}，實際評分集合為Q={q1，q2，q3，…，qi，qn}，則平均絕對誤差的計算公式如下：

MAE=∑ni=1pi-qin

所得結果如圖2所示。由圖中可看出在最近鄰數目相同時，本文算法的MAE值明顯小于Slope One算法和傳統的協同過濾推薦算法，本文所提算法推薦的準確率與以上兩種算法相比相對較高。

5結語

本文在對用戶進行推薦時充分考慮用戶的情景因素對推薦結果的影響，根據情景間的差異將用戶進行聚類，且在計算用戶和項目相似度以及用戶對項目的預測評分時也將情景的影響考慮在內，最終實現對用戶的項目推薦，仿真實驗證明了本文所提算法是有效且可行的。由于在推薦過程中不僅考慮用戶的情景因素對用戶偏好的影響，同時引入相似傳播的思想使得目標用戶能找到更多的鄰居，這樣很好地緩解了傳統算法中一直存在的冷啟動問題，而且進一步提高了推薦算法的準確率。但由于在根據用戶情景對用戶進行聚類時需反復迭代，計算所花時間較長，造成整個推薦過程所花時間相對較長，因此未來的研究希望能圖2不同算法的MAE值比較

在提高推薦效率上有所突破。

參考文獻

[1]馮鵬程.基于情境感知的個性化推薦算法的研究[D].上海：東華大學，2014.

[2]鄧曉懿，金淳，韓慶平，等.基于情境聚類和用戶評級的協同過濾推薦模型[J].系統工程理論與實踐，2013，（11）：2945-2953.

[3]詹麗華，李育嫦，潘瑞冰.基于情景感知的移動搜索的演變和實現[J].圖書館理論與實踐，2015，（11）：102-105.

[4]奉國和，梁曉婷.協同過濾推薦研究綜述[J].圖書情報工作，2011，16：126-130.

[5]邱均平，張聰.高校圖書館館藏資源協同推薦系統研究[J].圖書情報工作，2013，22：132-137.

[6]羅文.協同過濾推薦算法綜述[J].科技傳播，2015，（7）：115，196.

[7]董坤.基于協同過濾算法的高校圖書館圖書推薦系統研究[J].現代圖書情報技術，2011，（11）：44-47.

[8]申艷光，郭高尚，吳晶晶.結合情景和協同過濾的移動推薦算法[J].科學技術與工程，2014，（8）：49-52，64.

[9]王毅，樓恒越.一種改進的Slope One協同過濾算法[J].計算機科學，2011，（S1）：192-194.

（本文責任編輯：郭沫含）