葉劍宇，王 南，陳笑蓉，李倩文，周昱烽

(1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州貴陽(yáng)550025;2.廣州市地下鐵道總公司，廣東廣州510180;3.貴陽(yáng)市人才服務(wù)中心，貴州貴陽(yáng)550001)

現(xiàn)如今，互聯(lián)網(wǎng)改變著人們的購(gòu)物習(xí)慣，電子商務(wù)大行其道，但人們?cè)诿鎸?duì)琳瑯滿目的商品時(shí)卻無(wú)從下手。推薦系統(tǒng)根據(jù)用戶數(shù)據(jù)預(yù)測(cè)用戶下一階段的購(gòu)買(mǎi)行為，為之推薦相關(guān)商品。目前，推薦系統(tǒng)在諸如:京東，當(dāng)當(dāng)，淘寶，亞馬遜等電商上獲得了較大的成功。

推薦系統(tǒng)主要分為兩種，一種是基于內(nèi)容推薦，另一種是協(xié)同過(guò)濾推薦［1］。前者是通過(guò)項(xiàng)目之間的特征屬性比對(duì)，找出最相似的項(xiàng)目作為推薦結(jié)果，后者是通過(guò)用戶評(píng)價(jià)機(jī)制，找出相似度較大的用戶集合，稱(chēng)為鄰居，然后根據(jù)鄰居的行為信息生成推薦結(jié)果。相對(duì)于基于內(nèi)容推薦，協(xié)同過(guò)濾對(duì)對(duì)象沒(méi)有要求，能處理非結(jié)構(gòu)化的對(duì)象，不需要對(duì)推薦項(xiàng)目進(jìn)行特征建立和建模，目前較為主流的推薦系統(tǒng)多采用協(xié)同過(guò)濾。

協(xié)同過(guò)濾算法又分為兩種，基于記憶的協(xié)同過(guò)濾與基于模型的協(xié)同過(guò)濾，前者是目前主流的算法，根據(jù)角度不同又可以將其分為基于用戶的協(xié)同過(guò)濾與基于項(xiàng)目的協(xié)同過(guò)濾［2，3］，兩種算法都是最近鄰搜索(NNS)，通過(guò)計(jì)算用戶(項(xiàng)目)之間的相似度，找到與被推薦用戶(項(xiàng)目)的鄰居，然后通過(guò)這些鄰居評(píng)價(jià)預(yù)測(cè)被推薦用戶未來(lái)的購(gòu)買(mǎi)行為。由此可見(jiàn)，計(jì)算相似度的算法好壞直接決定了推薦效果。目前計(jì)算相似度的算法常見(jiàn)的有皮爾森相關(guān)系數(shù)、余弦相似度、Jaccard系數(shù)，但是這些算法在處理稀疏數(shù)據(jù)上有明顯不足。事實(shí)上，許多用戶只購(gòu)買(mǎi)或評(píng)價(jià)零星的物品，這個(gè)現(xiàn)象在推薦系統(tǒng)中十分常見(jiàn)。

為了降低稀疏數(shù)據(jù)對(duì)推薦系統(tǒng)的影響，國(guó)內(nèi)外研究人員提出了一些解決方案。文獻(xiàn)［4］提出了一種壓縮稀疏用戶評(píng)分矩陣的協(xié)同過(guò)濾算法;文獻(xiàn)［5］提出了基于聚類(lèi)的數(shù)據(jù)平滑處理方法;文獻(xiàn)［6］使用樸素貝葉斯方法預(yù)測(cè)評(píng)分，降低數(shù)據(jù)稀疏度;本文提出基于路徑搜索的相似度計(jì)算方法(PSCF)，在處理稀疏數(shù)據(jù)時(shí)有較好的效果。其基本思想是將用戶－項(xiàng)目評(píng)價(jià)矩陣看做帶權(quán)重的鄰接矩陣，這樣就將其轉(zhuǎn)換為帶權(quán)的無(wú)向圖，然后計(jì)算出目標(biāo)用戶(項(xiàng)目)到其他用戶(項(xiàng)目)的簡(jiǎn)單路徑，進(jìn)而計(jì)算兩者之間的相似度。

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

目前，主流協(xié)同過(guò)濾算法有基于用戶與基于項(xiàng)目的協(xié)同過(guò)濾，兩者都是通過(guò)建立評(píng)價(jià)矩陣［7］，然后計(jì)算用戶或項(xiàng)目相似度，最后產(chǎn)生推薦結(jié)果。

本文以基于用戶的Top-N協(xié)同過(guò)濾算法作為推薦模型，過(guò)程如下:

1.1 評(píng)價(jià)矩陣的表示

設(shè)用戶集合為 U={u1，u2，u3，…，un}，項(xiàng)目集合為 I={i1，i2，i3，…，im}，評(píng)價(jià)集合為 R={rij}，其中1＜x＜n，1 ＜y＜ m，rxy∈{0，1，2，…，Max}的值是ui對(duì)ij的評(píng)價(jià)，0表示該用戶對(duì)該項(xiàng)目沒(méi)用任何評(píng)價(jià)記錄。

設(shè)Max=5，則有用評(píng)價(jià)矩陣見(jiàn)表1。

表1 用戶－項(xiàng)目評(píng)價(jià)矩陣

1.2 相似度計(jì)算

相似性計(jì)算是協(xié)同過(guò)濾推薦算法中最關(guān)鍵的一步，傳統(tǒng)的相似度計(jì)算方法有以下三種［8］。

(1)余弦相似度

將評(píng)價(jià)矩陣的每行看做用戶評(píng)分向量，用戶間的相似度通過(guò)余弦?jiàn)A角度數(shù)來(lái)衡量:

(2)Jaccard系數(shù)

該算法屬于余弦相似度的擴(kuò)展，直觀意義為計(jì)算兩者的重疊性，其值域?yàn)椋?，1］，完全重疊為1，不重疊為0，值越大說(shuō)明相似度越高:

(3)皮爾森相關(guān)系數(shù)

皮爾森相關(guān)系數(shù)用來(lái)反映兩個(gè)變量線性相關(guān)程度的統(tǒng)計(jì)量，值域?yàn)椋郏?，1］，值越大，相關(guān)性就越強(qiáng):

其中，Iuv表示用戶u，v共同評(píng)分的項(xiàng)目集合，ruk表示用戶x對(duì)項(xiàng)目k的評(píng)價(jià)，ru表示用戶x在Iuv上的項(xiàng)目評(píng)分均值。

1.3 推薦結(jié)果

根據(jù)相似度計(jì)算結(jié)果，選出目標(biāo)用戶的最近鄰居集合，例如選擇相似度大于預(yù)設(shè)閥值的用戶，或者相似度排名前N個(gè)的用戶。之后通過(guò)公式(4)預(yù)測(cè)用戶對(duì)未評(píng)價(jià)項(xiàng)目的評(píng)分。

其中，Pui表示用戶u對(duì)于未評(píng)價(jià)項(xiàng)目i預(yù)測(cè)評(píng)價(jià)，表示用戶u在全部項(xiàng)目集合I上的評(píng)價(jià)均值，集合NB是用戶u的鄰居集合。

最后，對(duì)各個(gè)預(yù)測(cè)評(píng)價(jià)由高到低排序，取前N個(gè)項(xiàng)目推薦給目標(biāo)用戶u。

2 基于路徑搜索的用戶相似度計(jì)算

2.1 評(píng)價(jià)矩陣圖的表示形式

為了計(jì)算方便，首先對(duì)評(píng)價(jià)集合R={rij}中的值進(jìn)行標(biāo)準(zhǔn)化，即

根據(jù)上述公式，將表1中的評(píng)價(jià)矩陣標(biāo)準(zhǔn)化，見(jiàn)表2。

表2 用戶－項(xiàng)目標(biāo)準(zhǔn)化后的評(píng)價(jià)矩陣

將評(píng)價(jià)矩陣看做一個(gè)鄰接矩陣，其所表示的帶權(quán)無(wú)向圖為G=〈V，E，w〉，其定義如下:

根據(jù)上述定義，將表2轉(zhuǎn)換成圖的表示形式如圖1所示。

圖1 評(píng)價(jià)矩陣圖表示形式

2.2 相似度定義

本文將用戶之間的相似度定義為，兩個(gè)用戶節(jié)點(diǎn)之間所有的路徑相似度之和，單條路徑相似度定義為該路徑上所有權(quán)重之積，則有計(jì)算公式為:

其中，P是兩節(jié)點(diǎn)之間單條路徑的邊集合，Path是兩點(diǎn)之間所有路徑集合。

根據(jù)式(5)計(jì)算圖1中u1和u3的相似度，其中含有兩條路徑，即{u1，i3，u2，i2，u3}和{u1，i3，u4，i2，u3}，那么u1和u3的相似度就為:

通過(guò)觀察可以發(fā)現(xiàn):相同的數(shù)據(jù)，如果使用公式(1)(2)(3)計(jì)算，u1與u3之間的相似度為0。由于數(shù)據(jù)較為稀疏，u1與u3之間并沒(méi)有共同評(píng)價(jià)項(xiàng)目，導(dǎo)致傳統(tǒng)算法判定其為不相關(guān)，但事實(shí)上u1與u3之間通過(guò)u2存在間接關(guān)系，可見(jiàn)，本方法能夠發(fā)現(xiàn)傳統(tǒng)算法所不能發(fā)現(xiàn)的間接關(guān)系，從而提高協(xié)同過(guò)濾的準(zhǔn)確度。

2.3 路徑尋找算法

要計(jì)算兩個(gè)節(jié)點(diǎn)相似度必須獲得兩者之間的所有路徑，因此，路徑尋找算法的好壞決定了推薦系統(tǒng)的性能，本文參考了夏道勛與謝曉堯提出的基于雙棧技術(shù)的全路徑搜索算法［9］，考慮到實(shí)際應(yīng)用，引入?yún)?shù)D和F分別用于控制最大搜索深度與最小路徑相似度。該算法的思想是基于廣度優(yōu)先算法，利用雙棧結(jié)構(gòu)，其中，節(jié)點(diǎn)棧存儲(chǔ)當(dāng)前出棧節(jié)點(diǎn)的未訪問(wèn)的鄰接節(jié)點(diǎn)信息;計(jì)數(shù)棧存儲(chǔ)出棧節(jié)點(diǎn)和它未被訪問(wèn)的鄰接節(jié)點(diǎn)的個(gè)數(shù)，主要用于環(huán)路判斷。使用雙棧處理能夠大大減少算法的時(shí)間復(fù)雜度，算法過(guò)程如下:

輸入:起點(diǎn)，終點(diǎn)。

輸出:起點(diǎn)與終點(diǎn)之間的所有路徑集合與所有路徑的相似度。

Step1:將起點(diǎn)入棧。

Step2:如果為空棧則算法結(jié)束，否則繼續(xù)。

Step3:如果棧的長(zhǎng)度大于等于D，則彈出棧頂并繼續(xù)，否則繼續(xù)。

Step4:判斷是否存在棧頂節(jié)點(diǎn)未訪問(wèn)過(guò)且不在棧中的相鄰節(jié)點(diǎn)，存在則將其入棧并繼續(xù)，否則將棧頂彈出并轉(zhuǎn)到Step2。

Step5:計(jì)算目前路徑相似度，如果小于F，則彈出棧頂并轉(zhuǎn)到Step2，否則繼續(xù)。

Step6:如果棧頂節(jié)點(diǎn)為終點(diǎn)，則保存路徑并彈出棧頂然后轉(zhuǎn)到Step2，否則直接轉(zhuǎn)到Step3。

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

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

為了驗(yàn)證算法效果，實(shí)驗(yàn)采用MovieLens的數(shù)據(jù)集，其中包括了超過(guò)1000的用戶對(duì)超過(guò)1600部電影的評(píng)分?jǐn)?shù)據(jù)，數(shù)據(jù)條數(shù)為100000，數(shù)據(jù)稀疏度為:

用戶對(duì)電影的評(píng)分標(biāo)準(zhǔn)從1到5。其中，1表示最低，5表示最高，0代表未評(píng)論。實(shí)驗(yàn)過(guò)程中訓(xùn)練數(shù)據(jù)集占80%，測(cè)試數(shù)據(jù)集占20%。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用兩種評(píng)價(jià)指標(biāo)，一種經(jīng)典度量方法是度量系統(tǒng)的預(yù)測(cè)打分與用戶的實(shí)際打分的平均絕對(duì)誤差(MAE)，其值越小，說(shuō)明結(jié)果越準(zhǔn)確［10］。

其中，n表示用戶u評(píng)價(jià)項(xiàng)目的個(gè)數(shù)，vui表示用戶u對(duì)項(xiàng)目i的預(yù)測(cè)評(píng)分，rui表示用戶u對(duì)于項(xiàng)目i的實(shí)際評(píng)分。

另一種采用精確率(Precision)來(lái)評(píng)價(jià)，精確率越高，表示推薦效果越好。

其中，R(u)表示是根據(jù)用戶在訓(xùn)練集上的行為給用戶作出的推薦列表，T(u)表示用戶在測(cè)試集上的行為列表。

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

3.3.1 算法間比較試驗(yàn)

為了驗(yàn)證基于路徑搜索的相似度計(jì)算方法(PSCF)在精確度上的效果，本文均采用TOP-N UserCF推薦模型，比較多種相似度計(jì)算方法:余弦相似度(Cos)，皮爾遜相關(guān)系數(shù)(Person)，Jaccard相似度。PSCF算法參數(shù)均設(shè)為D=6，F(xiàn)=0.01。實(shí)驗(yàn)結(jié)果如圖2，3所示。

圖2 多算法的MAE比較

從圖2，3看出，PSCF算法的MAE和精準(zhǔn)率改善提升明顯，而余弦相似度，皮爾遜相關(guān)系數(shù)，Jaccard相似度由于數(shù)據(jù)稀疏，共同評(píng)價(jià)項(xiàng)目較少，使得其準(zhǔn)確度較低，其算法的優(yōu)劣主要在共同評(píng)價(jià)項(xiàng)目中體現(xiàn)。隨著鄰居用戶的增加，各個(gè)算法的表現(xiàn)有所提高，鄰居數(shù)達(dá)到20時(shí)，PSCF算法提高較為明顯。

3.3.2 參數(shù)間比較

為了測(cè)試出不同參數(shù)對(duì)算法的影響，本組試驗(yàn)取三組參數(shù):PS1(D=4，F(xiàn)=0.1);PS2(D=6，F(xiàn)=0.01);PS3(D=10，F(xiàn)=0.001)，實(shí)驗(yàn)結(jié)果如圖4，5所示。

圖3 多算法的精確率比較

圖4 參數(shù)間的MAE比較

圖5 參數(shù)間的MAE比較

從圖4，5可以看出，PS3效果最好，PS2次之，PS1最差，由此可見(jiàn)，隨著D的增大，F(xiàn)的減小，算法效果越好，這是由于搜索的深度越大，關(guān)聯(lián)的用戶就越多。但是，PS3相對(duì)PS2的提升幅度有限，而搜索深度越大，算法運(yùn)行時(shí)間也會(huì)增大，所以在實(shí)際環(huán)境下，要有所取舍。

4 總結(jié)

本文將路徑搜索思想應(yīng)用到相似度計(jì)算中，通過(guò)路徑尋找用戶與項(xiàng)目之間的間接關(guān)系，從而降低了稀疏數(shù)據(jù)對(duì)推薦系統(tǒng)影響。本文的算法的使用范圍不僅僅局限在基于用戶的協(xié)同過(guò)濾，使用評(píng)分矩陣的方法理論上都能使用此算法。實(shí)驗(yàn)結(jié)果顯示，本文的算法在推薦效果上有所提高，下一步將對(duì)路徑搜索算法的加以改善，降低算法的時(shí)間復(fù)雜度，進(jìn)一步提高算法性能。

［1］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems;A survey of the state-of-the-art and possible extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(6):734 －749.

［2］ NORSTAD J.A MapReduce algorithm for matrix multiplication［EB/OL］.［2012 －11 － 02］.http://www.norstad.org/matrixmultiply/index.html.

［3］LIN C，HUANG Z H，YANG F，et al.Identify content quality in online social networks［J］.IET Communications，2012，6(12):1618－1624.

［4］J WANG，A P DE VRIES，Reinders M J T.Unifying user-based and item-based collaborative filtering approaches by similarity fusion［C］//Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval(SIGIR ＇06)，New York:ACM，2006:501 －508.

［5］G XUE，C LIN，Q YANG，et al.Scalable collaborative filtering using cluster-based smoothing［C］//Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval(SIGIR ＇05).New York:ACM，2005:114－121.

［6］李大學(xué)，謝名亮，趙學(xué)斌.基于樸素貝葉斯方法的協(xié)同過(guò)濾推薦算法［J］.計(jì)算機(jī)應(yīng)用，2010，30(6):1523 －1526.

［7］AL-GINDY A，AL-AHMAD H，QAHWAJI R，et al.Watermarking of colour images in the DCT domain using Y channel［C］//2009 IEEE/ACS International Conference on Computer Systems and Applications.Washington，DC:IEEE Computer Society，2009:1025－1028.

［8］Ahn Hyun g-Jun.A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem［J］.Information Sciences，2008，178(1):37.

［9］夏道勛，謝曉堯.基于雙棧技術(shù)的全路徑搜索算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(19):4425－4428.

［10］COX I J，KILIAN J，LEIGHTON T，et al.Secure spread spectrum watermarking for multimedia［J］.IEEE Transactions on Image Processing，1997，6(12):1673 －1687.