高興前，王曉峰

（上海海事大學信息工程學院，上海201306）

0 引言

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

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

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

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

1 協(xié)同過濾算法

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

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

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

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

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

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

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

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

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

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

（1）用戶評分時間

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

（2）用戶共同評分

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

表1 用戶評分矩陣

（3）用戶平均評分

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

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

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

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

2.1時間因子

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

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

2.2用戶共同評分

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

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

2.3平均評分

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

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

2.4改進的相似度計算方法

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

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

3 算法設計

對于改進算法設計如下：

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

輸出：訓練集預測評分與測試集的平均絕對偏差MAE

算法設計：

（1）指定訓練集TrainFile和測試集TestFile；

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

（3）計算一個用戶的平均評分；

（4）計算用戶相似度

①計算有共同評分用戶的評分時間差；

②計算有共同評分用戶的共同評分項目數(shù)；

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

（5）對用戶相似度表進行排序；

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

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

（7）與測試集比較獲得算法的準確度MAE。

4 實驗結果與分析

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

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

4.2評估標準

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

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

4.3實驗結果

（1）最近鄰居集

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

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

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

表2 不同鄰居下的MAE

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

（3）不同方法下的MAE值

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

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

5 結語

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