石珂瑞， 劉建國(guó)

（上海理工大學(xué) 復(fù)雜系統(tǒng)科學(xué)研究中心，上海 200093）

協(xié)同過(guò)濾算法是應(yīng)用最廣泛的一種推薦算 法［1－6］.它的核心思想是利用朋友的歷史選擇信息預(yù)測(cè)目標(biāo)用戶(hù)的喜好程度.由于其具有較好的準(zhǔn)確率，因此，得到了廣泛的應(yīng)用，成為電子商務(wù)系統(tǒng)中解決信息超載的有效工具之一［7－8］.最近，基于物質(zhì)擴(kuò)散和熱傳導(dǎo)的方法已經(jīng)被成功地引入到個(gè)性化推薦算法的研究中，用來(lái)度量用戶(hù)之間的相似性行為，并且取得了不錯(cuò)的效果［3，9－10］.Liu等通過(guò)改變用戶(hù)相似度方向，提出了一種有向相似性的協(xié)同過(guò)濾算法［11］，該算法發(fā)現(xiàn)，增加度小用戶(hù)向度大目標(biāo)用戶(hù)推薦的強(qiáng)度，可以極大地提高算法準(zhǔn)確性和推薦列表多樣性.已有的統(tǒng)計(jì)結(jié)果表明，用戶(hù)的二階相似性可以大幅度提高推薦準(zhǔn)確性［10］.本文構(gòu)造二階有向相似推薦算法，綜合考察用戶(hù)的有向相似性和二階信息的影響，實(shí)驗(yàn)的數(shù)值結(jié)果表明，利用鄰居用戶(hù)到目標(biāo)用戶(hù)的二階相似性可以為目標(biāo)用戶(hù)提供更加準(zhǔn)確的推薦結(jié)果.

1 經(jīng)典協(xié)同過(guò)濾算法

協(xié)同過(guò)濾算法的思想是：首先，計(jì)算用戶(hù)之間的相似性；其次，根據(jù)用戶(hù)之間的相似選擇行為對(duì)目標(biāo)用戶(hù)進(jìn)行推薦.定義產(chǎn)品集合為用戶(hù)集合為那么，推薦系統(tǒng)可以表示為矩陣其中，aij＝1，表示用戶(hù)ui選擇了產(chǎn)品oj；否則，aij＝0.在經(jīng)典的協(xié)同過(guò)濾算法中，用戶(hù)ui和用戶(hù)uj的相似性根據(jù)夾角余弦系數(shù)或Pearson系數(shù)進(jìn)行計(jì)算.受到物質(zhì)擴(kuò)散過(guò)程的啟發(fā)，Liu等［12］提出了基于用戶(hù)－產(chǎn)品二部分圖的用戶(hù)ui和uj相似性Sij的計(jì)算方法.

式（1）表示的就是從鄰居用戶(hù)uj到目標(biāo)用戶(hù)ui的相似性.對(duì)于用戶(hù)－產(chǎn)品來(lái)說(shuō)，如果ui沒(méi)有選擇產(chǎn)品oα（即aiα＝0），那么，目標(biāo)用戶(hù)ui對(duì)產(chǎn)品oα的預(yù)測(cè)打分

式中，Sji表示從鄰居用戶(hù)uj到目標(biāo)用戶(hù)ui的相似性，即利用目標(biāo)用戶(hù)ui指向鄰居用戶(hù)uj的相似性來(lái)預(yù)測(cè)ui對(duì)產(chǎn)品oα的喜好程度.

2 改進(jìn)的協(xié)同過(guò)濾算法

在考慮了二階相似信息的協(xié)同過(guò)濾算法中，用戶(hù)ui和用戶(hù)uj的二階相似性可以用如下形式來(lái)表示：

式中，H 是目標(biāo)用戶(hù)ui和其鄰居用戶(hù)uj的二階相似性矩陣是由式（1）所得到的一階相似性定義；λ 是一個(gè)可調(diào)參數(shù).

考慮二階相似性和用戶(hù)相似性方向，作者設(shè)計(jì)一種改進(jìn)的算法.對(duì)于一個(gè)給定的用戶(hù)ui，改進(jìn)的協(xié)同過(guò)濾算法可以描述為：首先利用式（3）計(jì)算用戶(hù)之間的二階有向相似性，進(jìn)而對(duì)目標(biāo)用戶(hù)進(jìn)行推薦.

3 數(shù)值實(shí)驗(yàn)

使用標(biāo)準(zhǔn)數(shù)據(jù)集Movielens測(cè)試新算法的性能表現(xiàn).該數(shù)據(jù)集包括943個(gè)用戶(hù)和1 682個(gè)產(chǎn)品（電影）.用戶(hù)會(huì)對(duì)自己看過(guò)的產(chǎn)品按照5 分制進(jìn)行打分，1分表示最不喜歡，5分表示最喜歡.在此假設(shè)用戶(hù)打分大于2 分的就看作他選擇了該產(chǎn)品，進(jìn)而構(gòu)建用戶(hù)－產(chǎn)品二部分圖.刪除部分連邊后數(shù)據(jù)集剩余943個(gè)用戶(hù)，1 574個(gè)產(chǎn)品和82 520條邊.將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集這兩部分.利用數(shù)據(jù)集的90%作為訓(xùn)練集預(yù)測(cè)用戶(hù)對(duì)未選擇產(chǎn)品的喜好程度，利用其余10%作為測(cè)試集度量算法的表現(xiàn).

3.1 評(píng)價(jià)指標(biāo)

a.準(zhǔn)確度.一個(gè)好的算法應(yīng)該是要將訓(xùn)練集中已知的用戶(hù)喜歡的產(chǎn)品排在比較靠前的位置，本文采用平均排序打分度量推薦算法的準(zhǔn)確性.若有Li＝100個(gè)產(chǎn)品沒(méi)有被ui選擇，而oα在推薦列表中排名第10個(gè)，即oα的位置是10／100，其排序打分記為riα＝0.1.平均排序打分〈r〉越小，說(shuō)明產(chǎn)品在推薦列表中的位置越靠前，算法的準(zhǔn)確性就越高，反之亦然.

b.流行性和多樣性.推薦產(chǎn)品的平均度〈k〉是評(píng)價(jià)推薦算法的重要指標(biāo).如果算法趨向于推薦流行的產(chǎn)品，那么，被推薦產(chǎn)品的平均度會(huì)很高；反之，如果算法趨向于推薦不太流行的產(chǎn)品，則其平均度會(huì)很低.此外，利用平均海明距離度量推薦列表的多樣性.用戶(hù)ui和uj推薦列表的平均海明距離被定義為pij＝1－Qij／L.其中，L 為推薦列表的長(zhǎng)度，Qij為推薦給用戶(hù)ui和uj的2個(gè)推薦列表中相同產(chǎn)品的個(gè)數(shù).推薦列表的多樣性定義為pij的平均值P，S＝pij.P 越大，算法可以提供更多樣化的推薦，反之亦然.

3.2 結(jié)果分析

當(dāng)采用90%的數(shù)據(jù)作為訓(xùn)練集時(shí)，從圖1中可以看出，在Movielens數(shù)據(jù)集上，經(jīng)典的二階協(xié)同過(guò)濾算法的平均排序打分〈r〉在λ 為－0.815 附近達(dá)到最小值0.083，而本文算法的〈r〉在λ 為－0.726附近可以達(dá)到0.080 8.圖2表示推薦產(chǎn)品的平均度和推薦列表的多樣性隨著參數(shù)λ 的變化趨勢(shì).從圖2中可以得到，推薦產(chǎn)品的平均度〈k〉和λ 正相關(guān)，也就是說(shuō)降低用戶(hù)所選擇主流產(chǎn)品的影響會(huì)給不太流行產(chǎn)品更多的被推薦機(jī)會(huì)，當(dāng)推薦列表長(zhǎng)度L＝50時(shí)，在最優(yōu)點(diǎn)λopt＝－0.726處，產(chǎn)品的平均度〈k〉＝191，相對(duì)于經(jīng)典的基于物質(zhì)擴(kuò)散的協(xié)同過(guò)濾（CF）算法，流行性降低了10.32%.從圖2中也可以發(fā)現(xiàn)，算法的平均海明距離P 和λ 負(fù)相關(guān)，表明考慮了鄰居用戶(hù)對(duì)目標(biāo)的二階相似性后使得推薦列表更為離散，并且當(dāng)推薦列表長(zhǎng)度L＝50時(shí)，在λopt＝－0.726處，產(chǎn)品的平均海明距離P 大約為0.775，多樣性提高了10.87%.因此，這種新算法在增加CF算法的精確性方面具有很大優(yōu)勢(shì)，并且也可以較好地幫助目標(biāo)用戶(hù)發(fā)現(xiàn)一些隱藏的暗信息，為目標(biāo)用戶(hù)提供更為多樣化的推薦.

圖1 Movinlens數(shù)據(jù)集上平均排序打分隨參數(shù)λ 的變化趨勢(shì)圖Fig.1 Correlation between the parameterλand the average ranking score〈r〉

圖2 Movielens數(shù)據(jù)集上推薦產(chǎn)品的平均度〈k〉及推薦列表的多樣性P 隨參數(shù)λ 的變化趨勢(shì)Fig.2 Correlation between the parameterλand the average object degree〈k〉as well as the diversity P on dataset Movielens

4 結(jié)束語(yǔ)

首先提出了二階有向協(xié)同過(guò)濾算法，并且研究了用戶(hù)的二階有向相似性對(duì)協(xié)同過(guò)濾算法的影響.在標(biāo)準(zhǔn)數(shù)據(jù)集Movielens上的試驗(yàn)結(jié)果表明，利用鄰居用戶(hù)到目標(biāo)用戶(hù)的二階相似信息可以提高推薦的準(zhǔn)確性.當(dāng)訓(xùn)練集的比例為90%時(shí)，算法的準(zhǔn)確度可以達(dá)到0.080 8，該結(jié)果較經(jīng)典的CF 提高了22.08%，這是已有的協(xié)同過(guò)濾算法中準(zhǔn)確性效果最好的.

除準(zhǔn)確性外，被推薦產(chǎn)品的平均度以及推薦列表的多樣性也是量化推薦算法性能表現(xiàn)的2個(gè)重要指標(biāo)，而數(shù)值結(jié)果顯示，新算法在這2種指標(biāo)下比經(jīng)典的CF算法都要好.作者下一步的工作，將關(guān)注在二階有向相似性下產(chǎn)品的度信息與產(chǎn)品打分的關(guān)系.

［1］Herlocker J L，Konstan J A，Terveen L G，et al.Evaluating collaborative filtering recommender system［J］.ACM Trans Inform Syst，2004，22（1）：5－53.

［2］Konstan J A，Miller B N，Maltz D，et al.GroupLens：applying collaborative filtering to Usenet news［J］.Commun ACM，1997，40（3）：77－87.

［3］Liu J G，Wang B H，Guo Q.Improved collaborative filtering algorithm via information transformation［J］.Int J Mod Phys C，2009，20（2）：285－293.

［4］宣照國(guó)，苗靜，黨延忠.基于擴(kuò)展鄰居的協(xié)同過(guò)濾算法［J］.情報(bào)學(xué)報(bào)，2010，29（3）：443－448.

［5］潘紅艷，林鴻飛，趙晶.基于矩陣劃分和興趣方差的協(xié)同過(guò)濾算法［J］.情報(bào)學(xué)報(bào)，2006，25（1）：49－54.

［6］張子柯.社會(huì)化標(biāo)簽系統(tǒng)的結(jié)構(gòu)、演化和功能［J］.上海理工大學(xué)學(xué)報(bào)，2011，33（5）：444－451.

［7］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems－a survey of the state－of－the art and possible extensions［J］.IEEE Trans Know and Data Eng，2005，17（6）：734－749.

［8］Liu J G，Chen M Z Q，Chen J，et al.Recent advances in personal recommendation systems［J］.Int J Info ＆Sys Sci，2009，5（2）：230－247.

［9］Zhou T，Ren J，Medo M，et al.Bipartite network projection and personal recommendation［J］.Phys Rev E，2005，76（4）：046115，1－4.

［10］Liu J G，Zhou T，Che H A，et al.Effects of high－order correlations on personalized recommendations for bipartite networks［J］.Physica A，2010，389（4）：881－886.

［11］Liu J G，Shi K R，Guo Q.Solving the accuracydiversity dilemma via directed random walks［J］.Phys Rev E，2012，85（1）：016118，1－4.

［12］Liu J G，Guo Q，Zhang Y C.Information filtering via weighted heat conduction algorithm［J］.Physica A，2011，390（12），2414－2420.