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

高興前，王曉峰

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

0 引言

隨著互聯(lián)網(wǎng)和信息技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)中所蘊(yùn)含的信息量呈指數(shù)級增長，導(dǎo)致了信息過載等一系列問題。據(jù)國際數(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ù)中用戶很難發(fā)現(xiàn)自己感興趣的部分。推薦系統(tǒng)因此應(yīng)運(yùn)而生，通過分析用戶的歷史數(shù)據(jù)建模，然后將用戶感興趣信息推薦給用戶。

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

國內(nèi)外學(xué)者對協(xié)同過濾算法的相似性度量展開了一系列的研究。例如，Ahh[4]提出了修正余弦相似性（Adjusted Cosine Correlation）。Shardanand[5]考慮到評分的正負(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é)同過濾選法。于世彩[8]等人提出了一種基于項(xiàng)目類別和用戶興趣相似度融合（ICF_SI）的協(xié)同過濾算法。何順[18]等人提出基于加權(quán)多融合偏好與結(jié)構(gòu)相似度（MCF）的協(xié)同過濾算法。上述方法在數(shù)據(jù)稀疏時(shí)，其性能受到影響，推薦效果不夠理想。

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

1 協(xié)同過濾算法

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

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

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

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

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

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

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

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

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

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

（1）用戶評分時(shí)間

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

（2）用戶共同評分

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

表1 用戶評分矩陣

（3）用戶平均評分

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

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

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

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

2.1時(shí)間因子

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

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

2.2用戶共同評分

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

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

2.3平均評分

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

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

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

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

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

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

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

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

輸出：訓(xùn)練集預(yù)測評分與測試集的平均絕對偏差MAE

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

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

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

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

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

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

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

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

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

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

其中：Isim（i,n）表示用戶i和n的相似度，、分別表示用戶i和n的平均評分值；

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

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

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

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

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

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

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

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

（1）最近鄰居集

本文對MovieLens的5對數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，按照相似度形成鄰居用戶集，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析，如表2，鄰居數(shù)目過多或過少都會影響推薦質(zhì)量，因此需要確定鄰居數(shù)目k的大小。試驗(yàn)中，分別取k=10,20,30,40,50,60,70,80,90,100,每個(gè)k值對應(yīng)5個(gè)不同的數(shù)據(jù)集，并且將5次試驗(yàn)MAE的均值作為算法優(yōu)劣的衡量標(biāo)準(zhǔn)。如表2，隨著用戶鄰居的增大，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ì)算方法在測試集和訓(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)行對比，鄰居個(gè)數(shù)由上述實(shí)驗(yàn)結(jié)果選5到50，并選用MAE進(jìn)行比較：本文算法比文獻(xiàn)基于改進(jìn)相似性度量的項(xiàng)目協(xié)同過濾推薦算法[7]（Item Collaborative Filtering Recommendation Al?gorithm Based on Improved Similarity Measure，ICF_IP?SS），文獻(xiàn)基于加權(quán)多融合偏好與結(jié)構(gòu)相似度的協(xié)同過濾 算 法[18]（Collaborative Filtering Algorithm Based on Weighted Multi-Fusion Preference and Structure Similari?ty，MCF，權(quán)重取ω=0.7），文獻(xiàn)協(xié)同過濾的相似度融合改進(jìn)算法[8]（Improved Collaborative Filtering Algorithm of Similarity Integration，ICF_SI）的 MAE 都要低，表明改進(jìn)的算法推薦精度高，算法的改進(jìn)有效。

圖2 本文方法與其他方法推薦精度對比

5 結(jié)語

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