基于改進(jìn)相似度的協(xié)同過(guò)濾算法

高興前，王曉峰

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0 引言

隨著互聯(lián)網(wǎng)和信息技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)中所蘊(yùn)含的信息量呈指數(shù)級(jí)增長(zhǎng)，導(dǎo)致了信息過(guò)載等一系列問(wèn)題。據(jù)國(guó)際數(shù)據(jù)公司IDC（International Data Corpora?tion）2012年報(bào)告顯示：預(yù)計(jì)到2020年，全球數(shù)據(jù)總量將達(dá)到35.2ZB，這一數(shù)據(jù)量是2011年的22倍[1]，而在這海量數(shù)據(jù)中用戶(hù)很難發(fā)現(xiàn)自己感興趣的部分。推薦系統(tǒng)因此應(yīng)運(yùn)而生，通過(guò)分析用戶(hù)的歷史數(shù)據(jù)建模，然后將用戶(hù)感興趣信息推薦給用戶(hù)。

協(xié)同過(guò)濾CF（Collaborative Filtering）無(wú)疑是當(dāng)前使用最為廣泛的推薦算法之一[2]，最早在1992年由Goldberg等人提出［3］。它依據(jù)用戶(hù)-項(xiàng)目評(píng)分?jǐn)?shù)據(jù)，計(jì)算用戶(hù)（或項(xiàng)目）之間的相似度，然后將一個(gè)用戶(hù)感興趣的項(xiàng)目推薦給其他與之相似的用戶(hù)。因此，用戶(hù)（或項(xiàng)目）之間相似度計(jì)算準(zhǔn)確與否直接影響到整個(gè)系統(tǒng)的推薦質(zhì)量。

國(guó)內(nèi)外學(xué)者對(duì)協(xié)同過(guò)濾算法的相似性度量展開(kāi)了一系列的研究。例如，Ahh[4]提出了修正余弦相似性（Adjusted Cosine Correlation）。Shardanand[5]考慮到評(píng)分的正負(fù)性，提出了約束皮爾遜相關(guān)系數(shù)（Constrained Pearson Correlation Coefficient）。Bobadilla[6]等人提出了將均值平方差異函數(shù)（Mean Square Difference）與Jacca?rd系數(shù)結(jié)合形成基于Jaccard系數(shù)的均方差異系數(shù)（Jaccard-based Mean Square Difference）。于金明[7]等人提出了一種基于 IPSS（IIF-based Proximity-Signifi?cance-Singularity）的協(xié)同過(guò)濾選法。于世彩[8]等人提出了一種基于項(xiàng)目類(lèi)別和用戶(hù)興趣相似度融合（ICF_SI）的協(xié)同過(guò)濾算法。何順[18]等人提出基于加權(quán)多融合偏好與結(jié)構(gòu)相似度（MCF）的協(xié)同過(guò)濾算法。上述方法在數(shù)據(jù)稀疏時(shí)，其性能受到影響，推薦效果不夠理想。

本文針對(duì)在數(shù)據(jù)稀疏的情況下相似度計(jì)算不準(zhǔn)確的問(wèn)題展開(kāi)研究，充分考慮用戶(hù)之間各種評(píng)分信息的差異，在原有相似度計(jì)算方法的基礎(chǔ)上加入3個(gè)修正因子時(shí)間權(quán)重（詳見(jiàn)2.1）、用戶(hù)共同評(píng)分權(quán)重（詳見(jiàn)2.2）以及用戶(hù)平均分權(quán)重（詳見(jiàn)2.3），可以在數(shù)據(jù)稀疏的情況下，獲得比較好的度量用戶(hù)的相似度，提高了推薦精度。

1 協(xié)同過(guò)濾算法

1.1傳統(tǒng)的協(xié)同過(guò)濾算法

協(xié)同過(guò)濾推薦方法分為基于內(nèi)存[9]和基于模型[10]兩類(lèi)，廣泛應(yīng)用于推薦領(lǐng)域[11-12]，基于模型的方法是利用機(jī)器學(xué)習(xí)理論建立數(shù)學(xué)模型實(shí)現(xiàn)推薦[11]，基于內(nèi)存的方法屬于啟發(fā)式方法，包括基于項(xiàng)目的方法（Item-Based Collaborative Filtering）和基于用戶(hù)的方法（User-Based Collaborative Filtering）[11]兩種。當(dāng)給定用戶(hù)項(xiàng)目評(píng)分矩陣時(shí)，基于項(xiàng)目和基于用戶(hù)兩種方法原理類(lèi)似，均使用近鄰思想搜索出最相似的項(xiàng)目或用戶(hù)列表進(jìn)行推薦。

在協(xié)同過(guò)濾算法中，對(duì)目標(biāo)用戶(hù)產(chǎn)生推薦，主要分為三步：獲取用戶(hù)-項(xiàng)目矩陣、相似度計(jì)算并以此產(chǎn)生最近鄰、進(jìn)行評(píng)分預(yù)測(cè)[9]。常見(jiàn)的相似度計(jì)算方法有余弦相似度、相關(guān)相似性和修正的余弦相似性[11]。

（1）余弦相似性[14]。將用戶(hù)評(píng)分?jǐn)?shù)據(jù)看作n維向量，則用戶(hù)之間的相似性用余弦函數(shù)來(lái)計(jì)算，若用戶(hù)對(duì)某項(xiàng)沒(méi)有評(píng)分，則默認(rèn)將該項(xiàng)評(píng)分為0。將用戶(hù)i和用戶(hù)j在的評(píng)分看作兩組向量，分別用a→和b→表示，則用戶(hù)i、j的余弦相似度sim()i,j[13]為：

（2）相關(guān)相似性[11]。Pearson相關(guān)系數(shù)常是用來(lái)衡量?jī)蓚€(gè)數(shù)據(jù)集合之間的線性關(guān)系，則用戶(hù)i和j之間的相似性sim(i,j)為：

其中：ru,i用戶(hù)u對(duì)項(xiàng)目i的評(píng)分,ru,j用戶(hù)u對(duì)項(xiàng)目 j的評(píng)分，ri表示項(xiàng)目 i所有評(píng)分的平均值,rj表示項(xiàng)目j所有評(píng)分的平均值，Uij表示對(duì)用戶(hù)對(duì)項(xiàng)目i和j評(píng)分的交集。

（3）修正的余弦相似性[11]。用戶(hù)i和j之間的相似性sim(i,j)為：

其中：Uij表示用戶(hù)i和用戶(hù)j共同評(píng)分項(xiàng)目集合,表示用戶(hù)u所有評(píng)分的均值。

1.2傳統(tǒng)相似度計(jì)算方法的缺陷

隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)中的信息呈指數(shù)級(jí)增長(zhǎng)，用戶(hù)數(shù)和項(xiàng)目數(shù)也隨之飛快的增長(zhǎng)，用戶(hù)評(píng)分項(xiàng)目在總項(xiàng)目的占比一般不到1%[14]，用戶(hù)共同評(píng)分項(xiàng)目則少之又少，這將使得用戶(hù)評(píng)分矩陣變得極度稀疏。在這種情況下，傳統(tǒng)的相似度量值顯然是不夠準(zhǔn)確的，進(jìn)而帶來(lái)是很難找到真正的最近鄰居，推薦質(zhì)量不高。本文就此分析以下三個(gè)方面。

（1）用戶(hù)評(píng)分時(shí)間

傳統(tǒng)的相似度計(jì)算，評(píng)分項(xiàng)目在計(jì)算過(guò)程中權(quán)重相同，并沒(méi)有考慮到用戶(hù)的興趣愛(ài)好隨時(shí)間的變化。例如，用戶(hù)1、2、3有著相同的共同評(píng)分項(xiàng)目，但是用戶(hù)1和用戶(hù)2的評(píng)分時(shí)間和用戶(hù)3的評(píng)分時(shí)間相隔很長(zhǎng)，顯然用戶(hù)1和用戶(hù)2比用戶(hù)1和用戶(hù)3更為相似，但應(yīng)用傳統(tǒng)相似度計(jì)算方法卻可以得到相等的結(jié)果。

（2）用戶(hù)共同評(píng)分

傳統(tǒng)相似度的計(jì)算，忽略了近鄰用戶(hù)共同評(píng)分項(xiàng)目的影響，尤其是在評(píng)分?jǐn)?shù)據(jù)疏的情況下，導(dǎo)致相似度計(jì)算偏差過(guò)大，以至于推薦精度不高。例如：由表1，顯而易見(jiàn)u2和u3有2個(gè)共同評(píng)分項(xiàng)目，而u2和u4有3個(gè)共同評(píng)分項(xiàng)目，則u2和u3的相似度應(yīng)小于u2和u4的相似度。然而，利用Pearson相關(guān)系數(shù)度量用戶(hù)u2和用戶(hù)u3及u4的相似度，可得 sim(u2,u3)為 1，sim(u2,u4)為 0.7895。

表1 用戶(hù)評(píng)分矩陣

（3）用戶(hù)平均評(píng)分

傳統(tǒng)的相似度的計(jì)算，只是簡(jiǎn)單計(jì)算兩個(gè)用戶(hù)評(píng)分向量的線性相關(guān)性，卻沒(méi)有考慮到用戶(hù)評(píng)分分?jǐn)?shù)的差異。如表1利用Pearson相關(guān)系數(shù)度量sim(u1,u4)=1，說(shuō)明用戶(hù)u1和u4用相同的喜好，但是從表中數(shù)據(jù)來(lái)看對(duì)于項(xiàng)目P1和P5，用戶(hù)u1評(píng)分都為2，用戶(hù)u4為4和5，顯然用戶(hù)u4比較喜歡這兩個(gè)項(xiàng)目。因此可以發(fā)現(xiàn)，傳統(tǒng)的相似度計(jì)算方法對(duì)數(shù)值并不敏感。

隨著用戶(hù)評(píng)分矩陣的擴(kuò)大，上述問(wèn)題變得越來(lái)越嚴(yán)重，無(wú)法正確的找到真正相似的鄰居，進(jìn)而導(dǎo)致推薦質(zhì)量的降低。

2 多因素融合的優(yōu)化協(xié)同過(guò)濾算法

對(duì)于傳統(tǒng)的相似度計(jì)算在數(shù)據(jù)極度稀疏，不能找到真正的鄰居，進(jìn)而導(dǎo)致推薦質(zhì)量不高的情況下，本文將在傳統(tǒng)相似度計(jì)算加入時(shí)間因子、用戶(hù)共同評(píng)分因子以及用戶(hù)平均評(píng)分因子進(jìn)行改進(jìn)和比較。

2.1時(shí)間因子

考慮到用戶(hù)的興趣隨時(shí)間而改變，本文引入優(yōu)化的sigmoid函數(shù)，作為用戶(hù)相似度計(jì)算的時(shí)間權(quán)重，用戶(hù)評(píng)分時(shí)間越接近，相似度也越高。計(jì)算公式如下：

其中，T(i,j)表示用戶(hù)i和j評(píng)分時(shí)間權(quán)重，Uij表示用戶(hù)i和j的共同評(píng)分集合，tiu和tju表示用戶(hù)i和j對(duì)項(xiàng)目u的評(píng)分時(shí)間段。根據(jù)sigmoid函數(shù)特性，隨著∣的增大，T(i,j)取值隨之減小，取值范圍為[0,1]。

2.2用戶(hù)共同評(píng)分

傳統(tǒng)的相似度計(jì)算對(duì)于用戶(hù)共同評(píng)分并不敏感，尤其是在在數(shù)據(jù)評(píng)分矩陣非常龐大的情況下，忽略用戶(hù)共同評(píng)分的影響，相似度的計(jì)算并不那么準(zhǔn)確，因此本文引入Jaccard Similarity方法，公式如下：

其中，J(i,j)表示共同評(píng)分權(quán)重，Ii表示用戶(hù)i評(píng)分項(xiàng)目集合，Ij表示用戶(hù)j評(píng)分項(xiàng)目集合。當(dāng)用戶(hù)i和j共同評(píng)分項(xiàng)目數(shù)越多，相似度也越高。

2.3平均評(píng)分

為了提高推薦質(zhì)量，在用戶(hù)評(píng)分矩陣稀疏的情況下，Herlocker等人提出了改進(jìn)用戶(hù)評(píng)分分?jǐn)?shù)的方法,對(duì)于那些和目標(biāo)用戶(hù)相似的用戶(hù),如果沒(méi)有對(duì)共同評(píng)分項(xiàng)目進(jìn)行評(píng)分,可以使用最近鄰居用戶(hù)的平均評(píng)分來(lái)填補(bǔ)[15]，該方法在數(shù)據(jù)評(píng)分矩陣極端稀疏的情況下并不理想，也不能代表用戶(hù)對(duì)該項(xiàng)目的評(píng)分，并且在最近鄰居不準(zhǔn)確的情況下，誤差增大。因此，本文將用戶(hù)的平均評(píng)分作為相似度計(jì)算的權(quán)重，公式如下：

其中，M(i,j)表示平均評(píng)分權(quán)重，Uij表示用戶(hù)i和j共同評(píng)分項(xiàng)目，riu、rju表示用戶(hù)i和j對(duì)項(xiàng)目u的評(píng)分。M(i,j)越大，說(shuō)明用戶(hù)i和j評(píng)分差異越小，相似度越高；反之，M(i,j)越小，說(shuō)明用戶(hù)i和j的評(píng)分差異越大，相似度也越低。

2.4改進(jìn)的相似度計(jì)算方法

傳統(tǒng)的協(xié)同過(guò)濾算法，在相似度計(jì)算上存在偏差，包括忽略了用戶(hù)的興趣隨時(shí)間變化的因素、用戶(hù)之間共同評(píng)分的因素以及用戶(hù)評(píng)分差異等因素，導(dǎo)致推薦質(zhì)量下降，尤其是在評(píng)分矩陣極度稀疏的情況下，推薦質(zhì)量更是很差。本文融合以上因素提出一種改進(jìn)相似度的算法 Isim（i,j）,公式如下：

其中，sim(i,j)為傳統(tǒng)的相似度計(jì)算方法，本文采用時(shí)下常用的相關(guān)相似性。

3 算法設(shè)計(jì)

對(duì)于改進(jìn)算法設(shè)計(jì)如下：

輸入：MovieLens數(shù)據(jù)集

輸出：訓(xùn)練集預(yù)測(cè)評(píng)分與測(cè)試集的平均絕對(duì)偏差MAE

算法設(shè)計(jì)：

（1）指定訓(xùn)練集TrainFile和測(cè)試集TestFile；

（2）讀取訓(xùn)練集，生成電影用戶(hù)的倒排序表movie User；

（3）計(jì)算一個(gè)用戶(hù)的平均評(píng)分；

（4）計(jì)算用戶(hù)相似度

①計(jì)算有共同評(píng)分用戶(hù)的評(píng)分時(shí)間差；

②計(jì)算有共同評(píng)分用戶(hù)的共同評(píng)分項(xiàng)目數(shù)；

③計(jì)算基于平均評(píng)分、時(shí)間差異、共同評(píng)分項(xiàng)目數(shù)的相似性Isim()i,j；

（5）對(duì)用戶(hù)相似度表進(jìn)行排序；

（6）尋找用戶(hù)的k個(gè)最近鄰Nk={n1,n2,…,nk}，并生成推薦結(jié)果，計(jì)算方法如下：

其中：Isim（i,n）表示用戶(hù)i和n的相似度，、分別表示用戶(hù)i和n的平均評(píng)分值；

（7）與測(cè)試集比較獲得算法的準(zhǔn)確度MAE。

4 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)數(shù)據(jù)采用GroupLens小組提供的公開(kāi)Movie Lens［16］數(shù)據(jù)集。針對(duì)研究需求的不同，MovieLens 小組提供多個(gè)版本數(shù)據(jù)集。本文采用943個(gè)用戶(hù)對(duì)1682部電影10萬(wàn)次評(píng)分的小規(guī)模數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)由用戶(hù)看過(guò)的電影給予1～5的評(píng)分值形成，用戶(hù)-評(píng)分矩陣密度為，可見(jiàn)用戶(hù)評(píng)分矩陣十分稀疏。該數(shù)據(jù)集提供了5對(duì)訓(xùn)練集80%和測(cè)試集20%。數(shù)據(jù)集的數(shù)據(jù)包括用戶(hù)名、電影名稱(chēng)、評(píng)分及評(píng)分時(shí)間。

4.2評(píng)估標(biāo)準(zhǔn)

平均絕對(duì)偏差（Means Absolute Error）和平均方根誤（Root Mean Squared Error）[17]是衡量算法推薦精度的重要指標(biāo)，本文采用MAE作為推薦算法準(zhǔn)確性的衡量標(biāo)準(zhǔn)，MAE是通過(guò)計(jì)算訓(xùn)練集上的預(yù)測(cè)評(píng)分和測(cè)試集的實(shí)際評(píng)分進(jìn)行比對(duì)，來(lái)確定推薦質(zhì)量。MAE越大，推薦質(zhì)量相應(yīng)的也越差，公式定義如下：

其中：{r1，r2,…,rn}為用戶(hù)在測(cè)試集的評(píng)分，{p1，p2，…，pn}為用戶(hù)在訓(xùn)練集上預(yù)測(cè)的評(píng)分，n為算法預(yù)測(cè)出評(píng)分集合的大小。

4.3實(shí)驗(yàn)結(jié)果

（1）最近鄰居集

本文對(duì)MovieLens的5對(duì)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，按照相似度形成鄰居用戶(hù)集，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，如表2，鄰居數(shù)目過(guò)多或過(guò)少都會(huì)影響推薦質(zhì)量，因此需要確定鄰居數(shù)目k的大小。試驗(yàn)中，分別取k=10,20,30,40,50,60,70,80,90,100,每個(gè)k值對(duì)應(yīng)5個(gè)不同的數(shù)據(jù)集，并且將5次試驗(yàn)MAE的均值作為算法優(yōu)劣的衡量標(biāo)準(zhǔn)。如表2，隨著用戶(hù)鄰居的增大，MAE變化逐漸趨于穩(wěn)定且當(dāng)k=50推薦質(zhì)量最好。

（2）和傳統(tǒng)相似度計(jì)算方法相比

為了驗(yàn)證改進(jìn)算法的推薦的準(zhǔn)確性，本文以傳統(tǒng)相似度計(jì)算方法與改進(jìn)的相似度計(jì)算方法進(jìn)行比較，在鄰居數(shù)k=50的條件下每個(gè)計(jì)算方法在測(cè)試集和訓(xùn)練集上各自進(jìn)行5次實(shí)驗(yàn)，如圖1，可以發(fā)現(xiàn)，改進(jìn)的相似度計(jì)算方法MAE比傳統(tǒng)的計(jì)算方法要優(yōu)秀，表明改進(jìn)的相似度計(jì)算方法有利于推薦質(zhì)量的提高。

表2 不同鄰居下的MAE

圖1 與傳統(tǒng)方法相比較

（3）不同方法下的MAE值

為了進(jìn)一步檢驗(yàn)本文提出相似性度量方法的有效性，本文與以下幾篇論文的成果進(jìn)行對(duì)比，鄰居個(gè)數(shù)由上述實(shí)驗(yàn)結(jié)果選5到50，并選用MAE進(jìn)行比較：本文算法比文獻(xiàn)基于改進(jìn)相似性度量的項(xiàng)目協(xié)同過(guò)濾推薦算法[7]（Item Collaborative Filtering Recommendation Al?gorithm Based on Improved Similarity Measure，ICF_IP?SS），文獻(xiàn)基于加權(quán)多融合偏好與結(jié)構(gòu)相似度的協(xié)同過(guò)濾 算 法[18]（Collaborative Filtering Algorithm Based on Weighted Multi-Fusion Preference and Structure Similari?ty，MCF，權(quán)重取ω=0.7），文獻(xiàn)協(xié)同過(guò)濾的相似度融合改進(jìn)算法[8]（Improved Collaborative Filtering Algorithm of Similarity Integration，ICF_SI）的 MAE 都要低，表明改進(jìn)的算法推薦精度高，算法的改進(jìn)有效。

圖2 本文方法與其他方法推薦精度對(duì)比

5 結(jié)語(yǔ)

本文分析了傳統(tǒng)相似性度量方法的不足,針對(duì)這些不足,將時(shí)間權(quán)重、共同評(píng)分項(xiàng)目權(quán)重及用戶(hù)平均評(píng)分權(quán)重引入用戶(hù)相似度的計(jì)算中，提出了一種基于改進(jìn)相似度的度量方法。該方法能夠有效的度量相似度，解決了傳統(tǒng)相似度計(jì)算方法存在的一些問(wèn)題,并且實(shí)驗(yàn)結(jié)果表明，該方法有效地提高了推薦質(zhì)量。