雷建云， 何 順， 王淑娟

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

一種改進的基于用戶項目喜好的相似度度量方法

雷建云， 何 順， 王淑娟

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

針對傳統(tǒng)的基于用戶共同評分的相似度度量方法不能很準(zhǔn)確地衡量用戶間的相似性問題，提出了一種基于用戶項目喜好的相似度度量方法.實驗結(jié)果分析表明：使用新度量方法的協(xié)同過濾算法較使用傳統(tǒng)度量方法的協(xié)同過濾算法有更小的平均絕對誤差，證明了新的度量方法可以提高推薦的質(zhì)量.

協(xié)同過濾；相似度；用戶項目喜好；平均絕對誤差

伴隨互聯(lián)網(wǎng)的發(fā)展，每天產(chǎn)生的信息量巨大，人們進入一個信息過載的時代.無論是生產(chǎn)者還是消費者都面臨著挑戰(zhàn)，推薦系統(tǒng)的出現(xiàn)可以很好地解決這個問題.協(xié)同過濾是應(yīng)用最為廣泛的推薦技術(shù)手段[1]，也是迄今為止應(yīng)用最為成功的個性化推薦技術(shù)[2].目前電子商務(wù)平臺都具有推薦功能，為用戶提供便捷訪問的高質(zhì)量推薦，正是推薦系統(tǒng)研究領(lǐng)域的主要目標(biāo)[3].從用戶的歷史數(shù)據(jù)中挖掘信息，完成資源的推薦，亞馬遜是最為成功的案例.其思想是首先為目標(biāo)用戶尋找興趣相似的鄰近用戶，然后把鄰居用戶感興趣的項目推薦給目標(biāo)用戶.用戶間相似性計算是協(xié)同過濾算法的關(guān)鍵[4]，現(xiàn)有的用戶相似性度量方法是基于用戶共同評分相似性來計算的，但因為每個用戶對于項目的評價標(biāo)準(zhǔn)不同，并不能準(zhǔn)確挖掘用戶之間的相似性，導(dǎo)致選擇最近鄰集合的誤差，從而影響推薦系統(tǒng)的精度.

為了提高用戶相似性度量的精確度，本文提出一種基于用戶對項目喜好度量相似度的方法，從而提高推薦的質(zhì)量.

1 協(xié)同過濾算法

1.1 最近鄰?fù)扑]

最近鄰?fù)扑]是協(xié)同過濾最常用的推薦模式.對于一個目標(biāo)用戶產(chǎn)生推進列表需要3個步驟[5]：數(shù)據(jù)表述，發(fā)現(xiàn)最近鄰集合和產(chǎn)生推薦列表.

(1) 數(shù)據(jù)表述.根據(jù)用戶評分記錄，表示成一個m×n的矩陣R,其中m表示用戶數(shù)量，n表示項目數(shù)，Rij表示第i個用戶對第j個項目的評分值.

(2) 發(fā)現(xiàn)最近鄰集合.根據(jù)評分項目矩陣計算并找到與目標(biāo)用戶最為相似的前K個用戶.

(3) 產(chǎn)生推薦列表.根據(jù)最近鄰用戶的項目評分，預(yù)測目標(biāo)用戶未評分項目的評分值，選出預(yù)測評分值較高的前N個項目進行推薦.項目的預(yù)測評分的計算方法如下：

(1)

1.2 用戶相似性度量

用戶相似性計算作為協(xié)同過濾算法的關(guān)鍵[2]，傳統(tǒng)的相似性度量方法有Pearson方法，余弦相似度和Jaccard相似度.

1)Pearson相似性[6].

(2)

2) 余弦相似度.

(3)

3)Jaccard相似度.

(4)

公式(4)中‖表示集合中元素的個數(shù)，N(u),N(v)分別表示用戶u,v的評分項目集合.

選擇上面三種度量方法的任意一種計算得到相似度，利用⑴式即可求得項目的預(yù)測評分值.

2 改進相似度計算方法

傳統(tǒng)的Pearson方法和余弦相似度是基于用戶的共同評分，僅僅是通過數(shù)值計算而沒有考慮到數(shù)據(jù)背后所隱藏的信息，計算到的相似度并不能很好地衡量用戶間的相似性.Jaccard相似度是計算的用戶間的結(jié)構(gòu)相似度，沒用充分利用評分所包含的信息量，得到的相似度準(zhǔn)確度有待于提高.由于每個用戶可能有自己的評價標(biāo)準(zhǔn)，而用戶的評價標(biāo)準(zhǔn)可以從用戶的歷史評分?jǐn)?shù)據(jù)中得到，因而這里提出一種基于用戶對于項目的喜好情況來求解相似度的方法.

用戶對于項目的喜好情況借助歷史評分?jǐn)?shù)據(jù)挖掘，其定義為：以用戶當(dāng)前已評分項目的平均分作為用戶的喜好標(biāo)準(zhǔn)，當(dāng)評分值大于或等于平均分表示喜愛項目；否則為不喜愛項目.

改進后相似度計算需要以下兩個步驟：用戶項目喜好矩陣和度量用戶相似性.

1) 用戶項目喜好矩陣.

(5)

由用戶項目評分矩陣得到用戶項目喜好矩陣，如表1和表2所示.

由表1可知User1的平均評分為2.5，User2的平均評分為3.75，User3的平均評分為4，按照⑸式計算得到用戶項目喜好如表2.

2) 度量用戶相似性.

由用戶項目喜好矩陣可獲取用戶基于共同評分項的喜好向量，根據(jù)用戶喜好向量計算相似度，計算公式如下.

(6)

其中Lu,Lv分別表示用戶u,v的項目喜好向量，N(Lu),N(Lv)分別表示用戶u,v喜好的項目集，‖表示項目個數(shù).

3) 基于改進相似度的協(xié)同過濾算法復(fù)雜度分析.

分析算法有時主要關(guān)心像內(nèi)存、通信帶寬或計算機硬件這類資源，但通常想度量的是計算時間.而且隨著科技發(fā)展，存儲空間對于算法的影響也逐漸弱化，這里只討論算法時間復(fù)雜度.若用戶的數(shù)量級為n，項目的數(shù)量級為m，算法時間主要開銷是計算用戶間相似度度量，傳統(tǒng)協(xié)同過濾算法的時間復(fù)雜度為O(n2m)，改進的協(xié)同過濾算法的時間復(fù)雜度分析如下:

算法運行時間為T(n)=c0(n+1)+c1(m(n+1))+c2(n+1)+c3(n(n+1))+c4(mn(n+1))+c5(n+1)+c6N0=(c3+c4m)n2+(c0+c1m+c2+c3+c4+c5)n+(c0+c1+c2+c3+c5+c6N0)，其中c0,c1,c2,c3,c5,c6,N0均為常數(shù)，可得T(n)=O(n2m)，基于改進相似度的協(xié)同過濾算法的時間復(fù)雜度和傳統(tǒng)的協(xié)同過濾在同一數(shù)量級，未增加過多的時間開銷.

4) 適用范圍.

基于用戶項目喜好的相似度度量方法，由于要挖掘用戶評分背后的喜好情況，若在一個推薦系統(tǒng)中用戶數(shù)量遠(yuǎn)遠(yuǎn)大于項目數(shù)量，從海量的用戶中發(fā)現(xiàn)兩個用戶間的共同評分項目會很少，不利于挖掘用戶對于項目的喜好情況的，以至于影響到喜好相似度的準(zhǔn)確性，最終導(dǎo)致在最近鄰選擇時存在誤差，影響推薦系統(tǒng)的精度.所以改進的度量方法更適用于用戶數(shù)量不遠(yuǎn)大于項目數(shù)的數(shù)據(jù)集.

3 實驗及分析

3.1 實驗數(shù)據(jù)集及評價標(biāo)準(zhǔn)

實驗數(shù)據(jù)集使用美國Minnesota大學(xué)GroupLens項目組提供的MovieLens數(shù)據(jù)集，該數(shù)據(jù)集有多種版本，在推薦系統(tǒng)的評測中得到廣泛使用.實驗中使用的數(shù)據(jù)集包含有943個用戶對1682個電影超過100000條評分記錄.每個用戶至少對20部電影存在評分記錄，評分分為5個等級，對應(yīng)評分為1～5分，分?jǐn)?shù)越高表示用戶越喜愛電影.實驗中選取80%數(shù)據(jù)作為訓(xùn)練集，其余20%作為測試集.

平均絕對誤差(MAE)是常用的評價協(xié)同過濾算法的指標(biāo)[7].本文將使用MAE作為評價標(biāo)準(zhǔn)，通過計算預(yù)測評分和實際評分值之間的偏差來度量預(yù)測的準(zhǔn)確度.MAE越小說明推薦系統(tǒng)的推薦質(zhì)量越高[8，9].若預(yù)測評分集合為{p1,p2,p3,…,pn}，實際評分集合為{r1,r2,r3,…,rn}，MAE定義如下[10]：

(7)

式中N表示預(yù)測評分的項目總數(shù).

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

實驗分別使用Pearson方法，余弦相似度，Jaccard相似度和新的方法度量用戶間的相似度，對應(yīng)的協(xié)同過濾算法分別記為PCF,CCF,JCF和NCF,選擇的最近鄰數(shù)目從5開始，每次遞增5個，增至70，實驗結(jié)果如表3和圖1所示.

如表3和圖1所示使用改進相似度度量方法的協(xié)同過濾算法NCF有著較低的MAE，MAE的值越小說明推薦系統(tǒng)的推薦精度高，則算法NCF較其他三種基于傳統(tǒng)相似度度量方法的協(xié)同過濾算法效果更優(yōu)；從實驗結(jié)果數(shù)據(jù)中可以得知，最近鄰的數(shù)量影響著推薦的效果，可以看出最近鄰數(shù)量較少時，推薦質(zhì)量往往很差，而基于評分相似性的兩種算法PCF和CCF，由于相似度計算的誤差較大，隨著最近鄰的數(shù)量增加，最近鄰選取存在較大誤差，導(dǎo)致推薦的精度依舊很差.基于結(jié)構(gòu)相似度的協(xié)同過濾算法JCF，推薦效果雖然一定程度上優(yōu)于上面兩種算法，但次于改進算法的推薦效果.

4 結(jié)束語

本文主要介紹協(xié)同過濾算法的相似度計算方法，針對三種傳統(tǒng)相似度度量方法的不足，提出一種改進的相似度計算方法，即結(jié)合用戶項目喜好的度量方法，深入分析了基于改進方法的協(xié)同過濾算法的復(fù)雜度及其適用范圍，并通過實驗驗證改進的方法明顯優(yōu)于傳統(tǒng)的三種度量方法.改進的度量方法利用評分?jǐn)?shù)據(jù)的潛在信息，獲得用戶項目的喜好情況，結(jié)合用戶項目喜好矩陣應(yīng)用新的計算方法衡量用戶之間的相似性，使選擇的最近鄰誤差減小，從而獲得更好的推薦效果.

[1] Adomavicius G, Alexander Tuzhi lin. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[C]// IEEE .Transactions on Knowledge and Data Engineering. New Jersey: IEEE,2005:734-749.

[2] 邢春曉, 高鳳榮, 戰(zhàn)思南,等. 適應(yīng)用戶興趣變化的協(xié)同過濾推薦算法[J]. 計算機研究與發(fā)展, 2007, 44(2):296-301.

[3] 朱揚勇，孫 婧.推薦系統(tǒng)研究進展[J].計算機科學(xué)與探索，2015，9(5)：513-525.

[4] 嵇曉聲, 劉宴兵, 羅來明. 協(xié)同過濾中基于用戶興趣度的相似性度量方法[J].計算機應(yīng)用, 2010, 30(10):2618-2620.

[5] 劉芳先, 宋順林. 改進的協(xié)同過濾推薦算法[J]. 計算機工程與應(yīng)用, 2011, 47(8):72-75.

[6] 王 茜, 王均波. 一種改進的協(xié)同過濾推薦算法[J]. 計算機科學(xué), 2010, 37(6):226-228.

[7] LU L,MEDO M,YEUNG H C, et al. Recommender systems[J]. Physics Reports，2012,519( 1) : 1-49．

[8] 馬宏偉, 張光衛(wèi), 李 鵬. 協(xié)同過濾推薦算法綜述[J]. 小型微型計算機系統(tǒng),2009, 30(7):1282-1288.

[9] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]// ACM. Proceedings of the 10th international conference on World Wide Web. Texas: ACM, 2001:285-295.

[10] Herlocker J L, Konstan J A, Terveen L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems, 2004, 22(1):5-53.

[11] 黃創(chuàng)光,印 鑒,汪 靜,等. 不確定近鄰的協(xié)同過濾推薦算法[J].計算機學(xué)報，2010,08:1369-1377.

An Improved Similarity Measurement Method
Based on Users′ Item Preference

Lei Jianyun, He Shun, Wang Shujuan

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074,China)

In view of the fact that the traditional similarity measurement method based on users′ common score can′t measure the similarity between users accurately, a similarity measurement method based on users′ item preference is proposed. Through the experimental analysis, the collaborative filtering algorithm based on new measurement method has a smaller MAE than collaborative filtering algorithm based on traditional measurement method, and it is proved that the new method can improve the quality of recommendation.

collaborative filtering; similarity; user item preference; MAE

2015-09-10

雷建云(1972-)，男，教授，研究方向：信息安全，Email：leijianyun@mail.scuec.edu.cn

湖北省自然科學(xué)基金資助項目(2013CFB445)

TP393

A

1672-4321(2015)04-0094-04