基于相似傳播和情景聚類的網(wǎng)絡(luò)協(xié)同過濾推薦算法研究

曾群　程曉

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

〔關(guān)鍵詞〕相似傳播；情景聚類；協(xié)同過濾；推薦算法

DOI：10.3969/j.issn.1008-0821.2016.11.009

〔中圖分類號〕G2062〔文獻(xiàn)標(biāo)識碼〕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

如今，互聯(lián)網(wǎng)已經(jīng)成為人們獲取信息的重要途徑。然而，隨著網(wǎng)絡(luò)上信息量越來越大，信息過載的問題也越來越嚴(yán)重，這對人們在網(wǎng)上快速查找精確信息造成了很大的困難。個性化推薦系統(tǒng)能夠根據(jù)用戶的興趣偏好、項目、需求甚至通過感知用戶的情景來向用戶推薦信息，這不僅很好地解決了信息過載的問題，同時還滿足了用戶的個性化需求。在實(shí)際應(yīng)用方面，亞馬遜、當(dāng)當(dāng)?shù)却笮碗娚叹W(wǎng)站都開發(fā)出了自己的推薦系統(tǒng)。在學(xué)術(shù)研究領(lǐng)域，個性化推薦方面的研究也逐漸進(jìn)入學(xué)者的視野并得到關(guān)注，例如美國的Grouplens團(tuán)隊、Alexander Tuzhilin教授、Paul Resnick教授等對個性化推薦系統(tǒng)及相關(guān)的推薦算法進(jìn)行了深入的研究[1]。

1問題的提出

協(xié)同過濾推薦算法作為目前研究較成熟、應(yīng)用范圍較廣的推薦算法已被廣泛地運(yùn)用于互聯(lián)網(wǎng)各大推薦系統(tǒng)中[2]。然而，傳統(tǒng)的協(xié)同過濾推薦算法推薦的準(zhǔn)確率和推薦效率往往受到多方面的影響，如對于新用戶存在的冷啟動問題和由于評分矩陣數(shù)據(jù)稀少導(dǎo)致的數(shù)據(jù)稀疏問題對推薦算法的質(zhì)量產(chǎn)生的影響。

本文對傳統(tǒng)的推薦算法進(jìn)行了改進(jìn)，將相似傳播的思想和用戶的情景與協(xié)同過濾推薦相結(jié)合，提出了一種基于相似傳播和情景聚類的網(wǎng)絡(luò)協(xié)同過濾推薦算法，在傳統(tǒng)協(xié)同過濾算法存在的問題得到了較好緩解的同時也提高了推薦算法推薦的準(zhǔn)確率。

2相關(guān)概念及理論

21情景的定義

情景在不同的領(lǐng)域有不同的定義，心理學(xué)、情報學(xué)、哲學(xué)、組織行為學(xué)、教育學(xué)、社會學(xué)等領(lǐng)域的眾多學(xué)者都對情景進(jìn)行了深入的研究和探討，但關(guān)于情景的定義學(xué)者們都各執(zhí)己見，不能達(dá)成一致共識，因此情景一直沒有統(tǒng)一的定義。Dey等人認(rèn)為能描述某一實(shí)體特征的信息即為情景[3]。雖然這一定義目前被廣泛引用，但由于不同領(lǐng)域?qū)η榫暗睦斫飧鞑幌嗤榫暗亩x一直無法準(zhǔn)確給出。大多數(shù)學(xué)者都認(rèn)同：情景是和實(shí)體是不可分的，情景只有與實(shí)體產(chǎn)生聯(lián)系才具有意義，情景可以將實(shí)體的相關(guān)信息進(jìn)行詳細(xì)的描述。

22聚類的概念

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

23協(xié)同過濾推薦

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

3傳統(tǒng)協(xié)同過濾推薦算法

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

31基于用戶的協(xié)同過濾

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

User-based協(xié)同過濾推薦算法在計算用戶間的相似度時多是采用Pearson相關(guān)系數(shù)的計算方法，根據(jù)已有用戶對項目的評分矩陣進(jìn)行計算。計算用戶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′都有評分的項目的集合。

通過計算目標(biāo)用戶與非目標(biāo)用戶間的相似度找到與目標(biāo)用戶相似的用戶群體，將該群體的集合作為目標(biāo)用戶的最近鄰集合D。生成最近鄰集合后，將最近鄰集合中用戶對項目的評分?jǐn)?shù)據(jù)代入評分預(yù)測公式來對目標(biāo)用戶進(jìn)行偏好預(yù)測。預(yù)測目標(biāo)用戶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的最近鄰集合。

以上公式計算出來的預(yù)測結(jié)果將作為對目標(biāo)用戶進(jìn)行推薦的依據(jù)。

32基于項目的協(xié)同過濾

基于項目的協(xié)同過濾（Item-based CF）推薦算法首先是找到與項目相似的項目群，這一過程通常通過利用已有用戶對項目的評分?jǐn)?shù)據(jù)計算項目與項目之間的相關(guān)系數(shù)來完成；項目相似群生成后，根據(jù)用戶對群體中各項目的已有評分?jǐn)?shù)據(jù)來計算用戶對某一項目的預(yù)測評分；最后根據(jù)評分計算結(jié)果對用戶產(chǎn)生相關(guān)推薦。計算項目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′都有評分的用戶的集合。

根據(jù)項目間相關(guān)系數(shù)的計算生成項目的最近鄰集合I，之后根據(jù)生成的相似的項目群體來預(yù)測用戶對項目的評分。如計算用戶a對項目i的預(yù)測評分，計算公式如下[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的最近鄰集合。

計算出預(yù)測評分后依據(jù)預(yù)測結(jié)果對用戶進(jìn)行推薦。

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

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

41算法思路

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

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

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

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

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

42算法

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

421聚類

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

sim（C1，C2）=C1·C2C1C2

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

422最近鄰集合的生成

計算目標(biāo)用戶到通過情景聚類得到的各簇之間的距離，找到與目標(biāo)用戶距離最近的簇，并計算目標(biāo)用戶與簇中各用戶間的相似度。本文在傳統(tǒng)的計算用戶相似度的基礎(chǔ)上引入用戶的情景因素，對傳統(tǒng)的相似度計算方法進(jìn)行改進(jìn)，提出了基于情景的用戶相似度的計算，如計算目標(biāo)用戶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下有共同評分的項目的集合。

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

在計算項目與項目間的相似度時，本文在基于項目的協(xié)同過濾經(jīng)典算法Slope One算法[9]中引入用戶的情景，形成“用戶-情景-項目”模型，在計算項目間相似度時將情景因素對用戶對項目評分的影響考慮在內(nèi)，提出基于情景的項目相似度計算方法，計算項目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′均有評分的用戶數(shù)，U（c，t，t′）代表在情景c下對項目t與項目t′均有評分的用戶的集合，Pm表示滿分評分。

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

423推薦的生成

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

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實(shí)驗和結(jié)論

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

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

MAE=∑ni=1pi-qin

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

5結(jié)語

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

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

參考文獻(xiàn)

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

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

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

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

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

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

[7]董坤.基于協(xié)同過濾算法的高校圖書館圖書推薦系統(tǒng)研究[J].現(xiàn)代圖書情報技術(shù)，2011，（11）：44-47.

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

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

（本文責(zé)任編輯：郭沫含）