一種基于協(xié)同過濾和混合相似性模型的推薦算法

丁家滿， 沈書琳， 賈連印， 游進(jìn)國， 李潤鑫

（1. 昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650500；2. 云南省人工智能重點實驗室，昆明 650500）

隨著大數(shù)據(jù)時代的到來，信息與日俱增，使得信息消費者難以從大量數(shù)據(jù)中獲取對自己有用的信息，而數(shù)據(jù)生產(chǎn)者也無法使自己的信息在眾多信息中得到用戶的關(guān)注，這就是信息過載問題[1]。推薦系統(tǒng)通過收集用戶的愛好、行為習(xí)慣等信息并加以分析，幫助用戶快速準(zhǔn)確地找到自己想要的信息，被認(rèn)為是緩解信息過載問題最有效的方法之一[2]。目前推薦系統(tǒng)所采用的推薦技術(shù)主要包括關(guān)聯(lián)規(guī)則（association rules）[3]、基于內(nèi)容的推薦（content-based recommendation）[4]、協(xié)同過濾（collaborative filtering, CF）、基于效用的推薦（utility-based recommendation）[5]和混合推薦（hybrid approach）[6-7]等。其中，協(xié)同過濾推薦算法是推薦系統(tǒng)中應(yīng)用最廣泛最成功的推薦技術(shù)之一[8]，其目標(biāo)是根據(jù)已知的信息計算未知的評級[9]。主要包括基于用戶（user-based）的協(xié)同過濾算法[10]、基于項目（item-based）的協(xié)同過濾算法[11]、基于模型（model-based）的協(xié)同過濾算法[12-13]，它們在針對不同目標(biāo)時都取得了很好的推薦效果。

但協(xié)同過濾算法仍存在著許多問題，最主要的是數(shù)據(jù)稀疏問題和冷啟動問題?，F(xiàn)實生活中用戶的評分?jǐn)?shù)量較少，占總項目數(shù)的比例較低，導(dǎo)致提取的用戶偏好特征較少，推薦結(jié)果不準(zhǔn)確，這就是數(shù)據(jù)稀疏問題。為了解決協(xié)同過濾算法中的數(shù)據(jù)稀疏問題，文獻(xiàn)[14]從用戶偏好和全局角度提出了一種基于用戶偏好聚類的有效協(xié)同過濾算法，以減少數(shù)據(jù)稀疏的影響。文獻(xiàn)[15]提出了一種基于優(yōu)化用戶相似度的協(xié)同推薦算法。在傳統(tǒng)的余弦相似算法中加入了一個平衡因子，用于計算不同用戶之間的項目評價尺度差異。文獻(xiàn)[16]提出一種混合用戶相似性方法，該方法在特定領(lǐng)域取得了較好推薦結(jié)果，但仍然存在冷啟動方面的問題。為了有效解決冷啟動問題，文獻(xiàn)[17]提出了將主題模型與矩陣分解（MF）相結(jié)合的LDA_MF模型，并融合改進(jìn)的結(jié)合內(nèi)容與行為的LDA_CF，Item_CF算法形成混合算法，提高長尾應(yīng)用的推薦率。文獻(xiàn)[18]提出了用戶時間權(quán)重信息概念，結(jié)合項目屬性信息解決完全新項目冷啟動問題，但過于依賴共同評分項目，在數(shù)據(jù)稀疏環(huán)境下，效果不佳。文獻(xiàn)[19]提出一種利用多群組智慧協(xié)同過濾算法，并結(jié)合用戶偏好模型，對于解決用戶冷啟動問題取得了較好的效果，但對于多群組數(shù)據(jù)缺失或者稀疏情況，推薦效果有待提高。

以上文獻(xiàn)分別在解決數(shù)據(jù)稀疏和冷啟動問題方面取得不錯的成果，但如何有效地同時解決這兩個問題有待改進(jìn)。為此，本文提出一種基于協(xié)同過濾和混合相似模型的推薦算法，利用PSS（proximity-significance-singularity）模型計算不同用戶在不同項目間的相似度，并將不同項目間的評分關(guān)系作為權(quán)重調(diào)整用戶相似度；接著，采用用戶-項目-特性和用戶-項目-標(biāo)簽的三分圖形式描述用戶、項目、特性、標(biāo)簽之間的關(guān)系，得到項目特性和項目標(biāo)簽的關(guān)系權(quán)重；同時，設(shè)定用戶偏好因子和不對稱因子作為權(quán)重調(diào)整不同用戶間的評分偏好并提高模型的可靠性；最后，結(jié)合用戶時間權(quán)重信息，構(gòu)成基于協(xié)同過濾和混合相似模型的推薦算法。

1 問題定義

定義1 用戶相似度

假設(shè)兩個用戶u，v分別評價兩個項目i，j，評分等級分別為rui和rvj，項目評分權(quán)重為Sitem，則用戶相似度定義如式（1）所示。

式中，函數(shù)S1（rui,rvj）代表僅基于用戶不同項評級的相似度，利用文獻(xiàn)[16]中調(diào)整后的PSS模型進(jìn)行計算。函數(shù)S1（rui,rvj）具體公式如式（2）所示。

Proximity函數(shù)（見式（3））用于描述用戶間的評分絕對差值對相似度的影響；Significance（見式（4））函數(shù)描述用戶評分與評分域中值之間的關(guān)系；rmed表示評分域中值，如果用戶評級距離評分域中值較遠(yuǎn)，則此評級更為重要；Singularity（見式（5））函數(shù)描述一個評級對的均值與這兩個項目的全局評分均值的絕對差值對相似度的影響，μi，μj表示項目i，j的平均評分值。

S1函數(shù)采用的是不同用戶在不同項目間的相似度計算，為了使不同項目具有可比性，本文使用Sitem函數(shù)表示項目間的評分關(guān)系，并將此作為權(quán)重因子來調(diào)整用戶之間的相似度。為了使其能夠充分利用項目i，j的所有評分來解決共同評分的問題，這里式（6）采用調(diào)整后的標(biāo)準(zhǔn)化歐式距離進(jìn)行計算。

式中：rik，rjk表示某一用戶對項目i和項目j的評分值；sk表示用戶評分的標(biāo)準(zhǔn)差。這里考慮沒有評分的項以用戶評分均值代替。為了使項目間的相似權(quán)重更為準(zhǔn)確，將標(biāo)準(zhǔn)歐式距離進(jìn)行歸一化處理，使其結(jié)果在（0,1]之間，得到項目評分權(quán)重函數(shù)Sitem如式（7）所示。

定義2項目特性信息

設(shè)fui表示用戶u是否評價過項目i，fia表示項目i是否具有特性a，Ci表示項目i具有的特性個數(shù)，Ca表示共同擁有特性a的項目個數(shù)，則項目特性信息如式（8）所示。

項目特性信息描述用戶、項目與特性之間的關(guān)系。如果用戶u評價過項目i，則fui=1，反之fui=0；同樣，如果項目i具有特性a，則fia=1，反之，fia=0。

定義3項目標(biāo)簽信息

設(shè)fui表示用戶u是否評價過項目i，fti表示標(biāo)簽t是否標(biāo)注過項目i，Ci表示項目i被標(biāo)注的標(biāo)簽個數(shù)，Ct表示標(biāo)簽t標(biāo)記過的項目個數(shù)，即擁有共同標(biāo)簽的項目個數(shù)，則項目標(biāo)簽信息如式（9）所示。

項目標(biāo)簽信息描述用戶、項目與標(biāo)簽之間的關(guān)系。如果項目i具有標(biāo)簽t，則fti=1，反之，fti=0。

定義4不對稱因子

設(shè)Iu為用戶u的所有評分項目數(shù)量，Iv為用戶v的所有評分項目數(shù)量，則不對稱因子定義如式（10）所示。

不對稱因子S2通過描述兩個用戶的共同評分項目數(shù)量與目標(biāo)用戶評分項目數(shù)量的比例來強(qiáng)調(diào)用戶間的不對稱性。如果共同評分項目數(shù)量與用戶u的所有評分項目數(shù)量的比例大于其與用戶v的所有評分項目數(shù)量的比例，則表示共同評分項目對用戶u的影響要大于用戶v。

定義5偏好因子

設(shè)μu和μv表示用戶u和用戶v的評分均值，σu和σv表示用戶u和用戶v的評分標(biāo)準(zhǔn)差。偏好因子S3如式（11）所示。

偏好因子S3通過描述用戶之間評分均值和標(biāo)準(zhǔn)方差的絕對差值乘積來調(diào)整用戶的偏好，減少偏好差異帶來的影響。

定義6用戶時間權(quán)重

在現(xiàn)實生活中，不同用戶有不同的評級偏好。一些用戶更喜歡追求新事物，這些用戶為“積極用戶”，其評論時間與項目發(fā)布時間間隔較短。相反，有些用戶更喜歡別人給出過評分的項目，這類用戶為“消極用戶”，其評論時間與項目發(fā)布時間間隔較長。將用戶評論時間與項目發(fā)布時間間隔作為用戶時間權(quán)重信息，在推薦新項目時，優(yōu)先推薦給積極用戶。用戶時間權(quán)重為用戶評價項目總數(shù)與用戶對項目的評價時間和項目發(fā)布時間的時間間隔總和的比值。設(shè)sum為用戶u評價項目總數(shù)，timeui表示用戶u對項目i的評價時間，datei表示項目i的發(fā)布時間，則用戶u的時間權(quán)重如式（12）所示。

可以看出，（timeui-datei）越小，用戶時間權(quán)重wu越大，說明該用戶越喜愛新的事物，為積極用戶；反之，說明該用戶為消極用戶。

算例1為了更好理解，以用戶u1，u2，u3和項目i1，i2，i3，i4為例描述用戶時間權(quán)重信息，具體信息如表1所示。

表 1 用戶評價時間表Tab.1 User appraisal schedule

其中time代表用戶評價時間，date代表項目發(fā)布時間，根據(jù)式（12）可以得到用戶的時間權(quán)重信息如下：

由例子可以看出，用戶u3的時間權(quán)重最高，即用戶u3較用戶u1和u2更喜歡體驗新事物，為積極用戶，則優(yōu)先將新項目推薦給u3。

定義7預(yù)測評分值

為了得到用戶對未評級項的預(yù)測評分值，需要計算目標(biāo)用戶與其他用戶的相似度，篩選出與目標(biāo)用戶相似度最高的前K個鄰居用戶組成鄰近集，再根據(jù)預(yù)測評分公式進(jìn)行計算。設(shè)preui表示用戶u對未評級項目i的預(yù)測評分值，和分別表示用戶u和用戶v的平均評分值，rvi表示用戶v對項目i的評分，K表示用戶u的近鄰集合，S（u,v）表示用戶u和用戶v的相似度，則預(yù)測評分值如式（13）所示。

2 基于協(xié)同過濾和混合相似模型的推薦算法

傳統(tǒng)的相似性度量多采用用戶間的共同評分項進(jìn)行線性計算[20]，但實際情況中，數(shù)據(jù)稀疏問題使得共同評分項并不常見，變量之間通常也不存在線性關(guān)系，因此傳統(tǒng)推薦算法的準(zhǔn)確度也隨之降低。而為了解決共同評分項問題，采用不同用戶在不同項之間的評分來進(jìn)行相似度計算。并且為了更好地適應(yīng)非線性情況，考慮累積所有可能的評分，并將不同項之間的評分關(guān)系作為權(quán)重因子調(diào)整用戶相似度。

在考慮用戶評分的基礎(chǔ)上，還要考慮項目本身的特性，特別是新項目本身沒有用戶行為，因此更需要結(jié)合項目特性來解決項目冷啟動問題。同時，標(biāo)簽既能表達(dá)用戶對項目的自我理解，也能體現(xiàn)出項目本身所具備的特征，因此結(jié)合標(biāo)簽信息進(jìn)行推薦更能體現(xiàn)用戶的興趣和項目特點。

傳統(tǒng)的相似性度量在計算用戶相似度時通常將其看作對稱模式[21]，即兩個用戶間的相似影響相同。但在實際情況中，兩個用戶的評分?jǐn)?shù)一般并不相同，相似影響也不相同。因此，設(shè)計一個不對稱因子，用以強(qiáng)調(diào)用戶間相互影響的不對稱性。同時，考慮到用戶都有各自的評分偏好，有些用戶更喜歡評價高分，即使項目并不理想；也有些用戶更傾向于評價低分，哪怕項目很好也不會給很高的評分。為了平衡用戶偏好，使結(jié)果更為理想，設(shè)計偏好因子。

綜上考慮，提出一種混合相似性模型如式（14）所示。

即利用PSS模型計算用戶間的相似度S1，并使用項目間評分關(guān)系權(quán)重Sitem調(diào)整用戶相似度；接著，描述用戶、項目、特性、標(biāo)簽之間的關(guān)系，得到項目特性權(quán)重和項目標(biāo)簽權(quán)重；同時，設(shè)定用戶不對稱因子S2和偏好因子S3作為權(quán)重調(diào)整不同用戶間的評分偏好并提高模型的可靠性，構(gòu)成混合相似性模型。式中：，代表信息偏好權(quán)重，即用戶對項目特性信息和標(biāo)簽信息的偏好比重，取值范圍為（0,1），且+=1；sumitem為項目總數(shù)。

最后結(jié)合用戶時間權(quán)重信息，使用預(yù)測評分公式（14）得到目標(biāo)用戶對未評級項目的預(yù)測評分值，結(jié)合用戶時間權(quán)重信息式（12）組成式（15），實現(xiàn)推薦。

算例2為了更好地理解以上公式，下面根據(jù)用戶-項目評分矩陣（表2），項目-特性矩陣（表3）以及項目-標(biāo)簽矩陣（表4）給出的例子進(jìn)行分步說明。

表2評分為1，2，3，4，5共5個等級；表3表示如果項目具有某一屬性，則設(shè)值為1，否則設(shè)值為0；表4同理。首先以用戶u1為研究目標(biāo)，根據(jù)表2給出的用戶評分矩陣，結(jié)合式（1）計算用戶u1分別與u2，u3的相似度。這里以u1，u3分別評價項目i1，i2為例，進(jìn)行具體公式計算如下：

表 2 用戶-項目評分矩陣Tab.2 User-item rate matrix

表 3 特性-項目矩陣Tab.3 Attribute-item matrix

表 4 標(biāo)簽-項目矩陣Tab.4 Tag-item matrix

為了更好地理解和計算項目特性權(quán)重信息和項目標(biāo)簽權(quán)重信息，以項目特性權(quán)重信息為例，將用戶-項目矩陣、項目-特性矩陣轉(zhuǎn)化為用戶-項目-特性三分圖形式，具體如圖1所示。

圖1 用戶-項目-特性信息Fig. 1 User-item-attribute information

圖1 中：u代表用戶；i代表項目；a代表特性。如果用戶u評價項目i，則使用一條直線連接用戶u和項目i；同理，如果項目i擁有特性a，則連接項目i和特性a。繼續(xù)以用戶u1為研究目標(biāo)，根據(jù)圖1可知，項目i1擁有特性a1和a3，而有3個項目共同擁有特性a1，同樣有3個項目共同擁有a3，結(jié)合式（10）計算項目i1的項目特性權(quán)重為

同理，使用式（9）計算項目i1的項目標(biāo)簽關(guān)系。然后，根據(jù)式（14）可以得到最終的用戶間的相似性，如表5所示。

表 5 用戶相似值Tab.5 Values of the user similarity

由表5可以看出，用戶u1和u2沒有共同評分項，但仍能根據(jù)其他信息得到相似度，說明本文方法并不依賴共同評分項，并且用戶間的相似影響基本不同。最后，根據(jù)式（15）計算用戶對未評級項目的評分，若該項目是新項目，則直接采用用戶時間權(quán)重信息與新項目特性信息結(jié)合得到預(yù)測評分值。最后對用戶的項目評級進(jìn)行排序，完成Top-N推薦。

基于協(xié)同過濾和混合相似性模型的推薦算法描述如表6所示。

表 6 RCFHSM算法描述Tab.6 Description of RCFHSM algorithm

3 實驗結(jié)果和分析

3.1 數(shù)據(jù)集預(yù)處理和度量標(biāo)準(zhǔn)

本實驗采用的數(shù)據(jù)集是由美國Minnesota大學(xué)的Grouplens研究小組創(chuàng)建并維護(hù)的MovieLens數(shù)據(jù)集[22]，在預(yù)處理后，將其劃分為互不相交的訓(xùn)練集和測試集，訓(xùn)練集占80%，測試集占20%。

3.2 實驗結(jié)果和分析

本文進(jìn)行兩類實驗，首先采用MAE，F(xiàn)1-measure方法進(jìn)行對照實驗，驗證算法的有效性；然后對數(shù)據(jù)進(jìn)行再處理，采用新穎度指標(biāo)進(jìn)行對照實驗，驗證推薦算法對解決新項目冷啟動問題的有效性。

實驗1推薦算法的準(zhǔn)確度。

將參數(shù)α和β取多種不同的值進(jìn)行組合，分別進(jìn)行準(zhǔn)確度實驗。由于推薦個數(shù)少時準(zhǔn)確率較高，因此，首先在推薦個數(shù)為5的情況下，計算不同參數(shù)取值組和近鄰集的K值影響，對K值進(jìn)行選擇，如圖2所示。

由圖2可以看出，在不同的參數(shù)組情況下取K=20時準(zhǔn)確度最高，因此，限于篇幅，只列出K=20時一部分不同推薦個數(shù)的準(zhǔn)確度對比，如表7所示。

圖2 不同K取值的準(zhǔn)確度Fig. 2 Accuracy of different K values

表 7 參數(shù)取值Tab.7 Parameter values

本文進(jìn)行多組實驗后發(fā)現(xiàn)，其實參數(shù)α，β對實驗結(jié)果的影響并不大，說明算法本身對參數(shù)取值依賴性不大，但仍選取α=0.4，β=0.6，此時，算法在此數(shù)據(jù)集中準(zhǔn)確率相對較好。將本文算法（簡稱 RCFHSM）與文獻(xiàn)[16]中的基于用戶推薦的UPCC算法、基于物品推薦的IPCC算法和混合用戶相似模型（以下簡稱HUSM）算法進(jìn)行MAE，F(xiàn)1-measure對比，結(jié)果如圖3和圖4所示。

觀察兩圖可知，本文提出的基于協(xié)同過濾和混合相似模型的推薦算法在評估方法MAE，F(xiàn)1-measure上都優(yōu)于其他推薦算法。這是因為相比其他算法，本文在累積所有評分項來解決共同評分項較少所導(dǎo)致的數(shù)據(jù)稀疏問題時，同時加入了特性權(quán)重信息和標(biāo)簽權(quán)重信息，提高了推薦的效果。

圖3 MAE對比Fig. 3 MAE for different algorithms

圖4 F1-measure對比Fig. 4 F1-measure for different algorithms

實驗2 解決新項目冷啟動問題。

原數(shù)據(jù)集中不存在新項目，即用戶未進(jìn)行評級的項目，因此對原數(shù)據(jù)集進(jìn)行再處理，在測試集中隨機(jī)抽取300，500，1 000個項目依次作為新項目，訓(xùn)練集中對應(yīng)的300，500，1 000個項目的評分信息及標(biāo)簽信息依次設(shè)為0。使用處理后的數(shù)據(jù)集對本文算法進(jìn)行準(zhǔn)確度和新穎度實驗，因為前面的幾個算法更多基于評分計算，在解決項目冷啟動方面效果并不好，為此加入文獻(xiàn)[18]的CUTATime推薦算法結(jié)果進(jìn)行對比。

從表8和表9中可以看出，本文算法的新穎度優(yōu)于CUTATime算法。這是因為在計算新穎度時加入了用戶評分均值，從而提高了新項目的推薦比例，使新項目能夠得到更多的推薦。

表 8 CUTATime算法準(zhǔn)確度和新穎度Tab.8 Accuracy and novelty of CUTATime algorithm

表 9 RCFHSM算法準(zhǔn)確度和新穎度Tab.9 Accuracy and novelty of RCFHSM algorithm

4 結(jié) 論

針對推薦算法一直以來的數(shù)據(jù)稀疏和冷啟動問題，提出一種基于協(xié)同過濾和混合相似性模型的推薦算法。該算法通過計算用戶在不同項目間的相似性來解決用戶間共同評分項較少所帶來的數(shù)據(jù)稀疏問題；并將項目特性權(quán)重和用戶時間權(quán)重信息相結(jié)合用于解決新項目冷啟動問題。在此基礎(chǔ)上進(jìn)行了對比實驗，實驗結(jié)果表明，本文提出的混合相似性模型合理可行，有較高的準(zhǔn)確度和新穎度，并能有效地解決數(shù)據(jù)稀疏和冷啟動問題。