雷建云， 何 順， 王淑娟

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

一種改進(jìn)的基于用戶項(xiàng)目喜好的相似度度量方法

雷建云， 何 順， 王淑娟

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

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

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

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

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

1 協(xié)同過濾算法

1.1 最近鄰?fù)扑]

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

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

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

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

(1)

1.2 用戶相似性度量

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

1)Pearson相似性[6].

(2)

2) 余弦相似度.

(3)

3)Jaccard相似度.

(4)

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

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

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

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

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

改進(jìn)后相似度計(jì)算需要以下兩個(gè)步驟：用戶項(xiàng)目喜好矩陣和度量用戶相似性.

1) 用戶項(xiàng)目喜好矩陣.

(5)

由用戶項(xiàng)目評(píng)分矩陣得到用戶項(xiàng)目喜好矩陣，如表1和表2所示.

由表1可知User1的平均評(píng)分為2.5，User2的平均評(píng)分為3.75，User3的平均評(píng)分為4，按照⑸式計(jì)算得到用戶項(xiàng)目喜好如表2.

2) 度量用戶相似性.

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

(6)

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

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

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

算法運(yùn)行時(shí)間為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)，基于改進(jìn)相似度的協(xié)同過濾算法的時(shí)間復(fù)雜度和傳統(tǒng)的協(xié)同過濾在同一數(shù)量級(jí)，未增加過多的時(shí)間開銷.

4) 適用范圍.

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

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)標(biāo)準(zhǔn)

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

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

(7)

式中N表示預(yù)測(cè)評(píng)分的項(xiàng)目總數(shù).

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

4 結(jié)束語

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

[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]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(2):296-301.

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

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

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

[6] 王 茜, 王均波. 一種改進(jìn)的協(xié)同過濾推薦算法[J]. 計(jì)算機(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]. 小型微型計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，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é)基金資助項(xiàng)目(2013CFB445)

TP393

A

1672-4321(2015)04-0094-04