汪千松，蔣勝，王忠群

(安徽工程大學(xué)現(xiàn)代教育中心, 安徽 蕪湖 241000)

基于社會網(wǎng)絡(luò)的協(xié)同推薦方法

汪千松，蔣勝，王忠群

(安徽工程大學(xué)現(xiàn)代教育中心, 安徽 蕪湖 241000)

[摘要]針對傳統(tǒng)協(xié)同過濾推薦算法存在推薦精度低的問題,提出了一種基于社會網(wǎng)絡(luò)的協(xié)同推薦方法。該方法融合了社會網(wǎng)絡(luò)中用戶的相似度與信任度，首先計(jì)算用戶間的評分相似度；再由直接信任度與間接信任度加權(quán)得出用戶信任度；最后綜合用戶相似度與信任度得出用戶間的推薦權(quán)重，并以推薦權(quán)重來選取最近鄰居集，為目標(biāo)用戶形成推薦。試驗(yàn)結(jié)果證明，該方法可有效提高推薦系統(tǒng)的推薦精度。

[關(guān)鍵詞]社會網(wǎng)絡(luò)；協(xié)同過濾；推薦精度；信任度；推薦權(quán)重

隨著信息技術(shù)與電子商務(wù)的飛速發(fā)展，商品信息數(shù)據(jù)的爆發(fā)式增長導(dǎo)致人們淹沒于信息數(shù)據(jù)的海洋之中，如何快速、有效地找出用戶的興趣偏好信息并給予相應(yīng)地推薦這一問題，成為近年來人們研究的熱點(diǎn)。推薦技術(shù)可有效地緩解信息過載為人們帶來的困擾，但仍然存在推薦精度低的問題。

針對推薦技術(shù)精度低的問題，文獻(xiàn)[1]利用社會學(xué)原理，從用戶信任網(wǎng)絡(luò)出發(fā)，兼顧用戶群體間興趣偏好，通過信任的可傳遞性來提高推薦效率；文獻(xiàn)[2]通過引入了信任支持度的概念來準(zhǔn)確表述信任網(wǎng)絡(luò)中的客戶信任關(guān)系，提出了一種信任度與信任支持度相結(jié)合的客戶信任模型；文獻(xiàn)[3]采用隨機(jī)游走的方式選取最優(yōu)的鄰居集，以云模型相似度方法計(jì)算項(xiàng)目間的相似度，該方法提高了算法的效率；文獻(xiàn)[4]采用了正反相結(jié)合的方式，提出了基于信任與不信任關(guān)系的推薦方法；文獻(xiàn)[5]為了提高推薦結(jié)果的準(zhǔn)確性以及可靠性，提出了一種結(jié)合語義Web和用戶信任網(wǎng)絡(luò)的協(xié)同過濾推薦模型；文獻(xiàn)[6]為了在節(jié)點(diǎn)之間建立信任關(guān)系，從而提出了一種基于群組的信任管理模型。

最近鄰居集的選取作為協(xié)同過濾推薦技術(shù)的關(guān)鍵步驟，其準(zhǔn)確性直接影響系統(tǒng)的推薦準(zhǔn)確性。較早之前就有學(xué)者研究表明，用戶往往更加傾向于接受熟人、好友而非推薦系統(tǒng)的推薦[7~9]，可見推薦的準(zhǔn)確性不僅僅與目標(biāo)用戶的興趣偏好相關(guān)，還與其在社會網(wǎng)絡(luò)中的用戶信任有更加緊密的聯(lián)系。為此，筆者通過融合目標(biāo)用戶在社會網(wǎng)絡(luò)中的相似度與信任度，提出了一種基于社會網(wǎng)絡(luò)的協(xié)同推薦方法。

1理論與方法

1.1基于用戶-項(xiàng)目評分的相似度計(jì)算

1)建立用戶-項(xiàng)目集定義用戶集合為U={u1,u2,…,un}，商品項(xiàng)目集合為I={i1,i2,…,in}；ru,i表示用戶u對項(xiàng)目i的行為(如購買或評分行為)，當(dāng)用戶無行為時(shí)ru,i則記為0；所有用戶對項(xiàng)目的行為可以表示為一個(gè)m×n的矩陣，記為Rm×n。

2)用戶-項(xiàng)目評分相似度計(jì)算目前相似度的計(jì)算方法主要余弦相似度、修正的余弦相似度及Pearson相關(guān)相似度度量方法，筆者采用修正的余弦相似度計(jì)算方法：

(1)

1.2基于社會網(wǎng)絡(luò)的用戶信任度計(jì)算

傳統(tǒng)協(xié)同過濾推薦算法主要是依據(jù)相似用戶具有相似的偏好興趣，但由于用戶的評分?jǐn)?shù)據(jù)較為稀疏，導(dǎo)致在計(jì)算用戶相似度時(shí)，存在較大的偶然因素，無法較為準(zhǔn)確地度量用戶間的相似性[10]。假設(shè)在某個(gè)推薦數(shù)據(jù)集中，2個(gè)用戶ub、uc均屬于用戶ua的鄰居集；并且在以往的歷史推薦里，用戶ub、uc對ua各推薦了10次。通過用戶uc的反饋得知，由用戶ub推薦的10次結(jié)果中只有2次結(jié)果符合用戶ua的興趣；而由uc產(chǎn)生的推薦符合ua興趣偏好的結(jié)果有8次，這表明用戶ua對uc給出的推薦信任度要遠(yuǎn)遠(yuǎn)高于ub給出的推薦。而在現(xiàn)實(shí)環(huán)境中，人們更加傾向于采納親戚或好友給出的推薦，即在社會網(wǎng)絡(luò)中，信任度的高低對目標(biāo)用戶的購買決策具有較大的影響作用。

因此，筆者在用戶評分相似度的基礎(chǔ)之上，利用社會網(wǎng)絡(luò)中用戶間的信任關(guān)系作為選取最近鄰居的另一個(gè)根據(jù)。信任在社會網(wǎng)絡(luò)中的傳遞涉及到直接和間接信任2個(gè)方面：直接信任即是2個(gè)網(wǎng)絡(luò)用戶節(jié)點(diǎn)之間直接可以建立聯(lián)系，筆者的研究中表示為2個(gè)用戶之間有一定數(shù)量的共同評價(jià)項(xiàng)目；間接信任即2個(gè)網(wǎng)絡(luò)用戶節(jié)點(diǎn)之間并沒有直接的聯(lián)接關(guān)系，但是由網(wǎng)絡(luò)中的其他節(jié)點(diǎn)聯(lián)接起來，這體現(xiàn)了信任的可傳遞性。

圖1　社會網(wǎng)絡(luò)中直接信任關(guān)系圖

1)直接信任定義用戶直接信任度如圖1所示，其中item1,item2,…,itemn表示用戶ua與uc共同評分的項(xiàng)目集，tdir(a,c)表示用戶ua與uc的直接信任度，ra,n表示用戶ua對項(xiàng)目itemn的評分。

對用戶uc所有評價(jià)項(xiàng)目集合Ic，且j∈Ic：

(2)

依據(jù)預(yù)測評分與真實(shí)評分之間的誤差，可以得出用戶之間的直接信任計(jì)算公式：

(3)

(4)

圖2　社會網(wǎng)絡(luò)中用戶間接信任關(guān)系圖

2)間接信任社會網(wǎng)絡(luò)中，用戶間的間接信任反映出信任具有可傳遞性的特點(diǎn)。假設(shè)在用戶ub、uc之間并沒有共同評分項(xiàng)目，那么用戶間直接信任度為0；但這顯然對用戶信任度的描述是不完全正確的。因此，筆者定義用戶信任度是綜合了直接信任與間接信任。在社會網(wǎng)絡(luò)中用戶的間接信任關(guān)系圖如圖2所示，其中集合UB表示用戶ua、uc共同的鄰居集，tind(a,c)表示用戶ua對用戶uc的間接信任度。

基于以上分析，在社會網(wǎng)絡(luò)中，只考慮2步可達(dá)信任關(guān)系，即只通過一個(gè)中間用戶建立2個(gè)直接信任度為零的用戶。因此用戶間接信任度計(jì)算公式為：

(5)

式中，UB={ui|tdir(a,ui)≠0且tdir(ui,c)≠0}，即UB表示所有由用戶ua節(jié)點(diǎn)到用戶uc節(jié)點(diǎn)2步可達(dá)的用戶集合。

3)用戶綜合信任度的計(jì)算用戶ua對用戶uc的綜合信任度T(a,c)是綜合了直接信任與間接信任，其計(jì)算公式如下：

T(a,c)=χtdir(a,c)+(1-χ)tind(a,c)

(6)

式中，χ表示直接信任的被重視程度，χ∈(0，1)，取χ=0.8。

2基于社會網(wǎng)絡(luò)的協(xié)同過濾推薦算法

由于人們通常更加傾向于接受好友或親戚熟人的推薦，即使用戶之間的興趣偏好相似度較高的鄰居用戶，由于信任度的差異，最終的推薦結(jié)果也會有不同。融合用戶偏好的相似度與用戶間信任度對提升算法的推薦結(jié)果準(zhǔn)確性具有重要意義。因此，筆者提出一種基于社會網(wǎng)絡(luò)的協(xié)同過濾推薦算法，其推薦過程示意圖如圖3所示。

圖3　社會網(wǎng)絡(luò)中用戶間接信任關(guān)系圖

圖3基于社會網(wǎng)絡(luò)的推薦系統(tǒng)框架將引入推薦權(quán)重來綜合用戶偏好相似度及用戶信任度，推薦權(quán)重計(jì)算方法如下：

(7)

式中，w(a,c)表示用戶uc與目標(biāo)用戶ua的推薦權(quán)重。

依據(jù)上述推薦權(quán)重w(a,c)的計(jì)算結(jié)果，選擇權(quán)值最大的K個(gè)用戶作為目標(biāo)用戶的最近鄰居集UK。得出目標(biāo)用戶預(yù)測評分計(jì)算公式：

(8)

3算法描述及復(fù)雜度分析

3.1算法描述

輸入：目標(biāo)用戶uT，用戶-評分項(xiàng)目矩陣Rm×n，用戶信任矩陣Tm×m，鄰居數(shù)k；

輸出：Top-N推薦結(jié)果。

推薦步驟如下：

Step1對每個(gè)用戶u，找到同目標(biāo)用戶uT共同評分過的項(xiàng)目，將其記錄在items中；

Step2依據(jù)用戶評分矩陣Rm×n，使用式(1)計(jì)算用戶評分間的相似度sim(a,b)；

Step3由式(2)得出預(yù)測評分與真實(shí)評分之間的偏差值，然后由式(3)得出用戶間的直接信任度；

Step4根據(jù)式(5)計(jì)算用戶間的間接信任度，并通過式(6)計(jì)算用戶間的集成信任度，并將其結(jié)果存入矩陣Tm×m中；

Step5融合用戶相似度與信任度，由式(7)得出用戶間的推薦權(quán)重；

Step6根據(jù)式(8)計(jì)算得出目標(biāo)用戶uT的所有項(xiàng)目的預(yù)測評分；

Step7為目標(biāo)用戶uT生成Top-N推薦。

3.2復(fù)雜度分析

根據(jù)算法描述，假設(shè)用戶數(shù)為m，項(xiàng)目數(shù)為n，最近鄰居數(shù)目為k，則：

1)Step1系統(tǒng)初始化階段，遍歷目標(biāo)用戶與其他用戶間共同評分過的項(xiàng)目，因此其復(fù)雜度為O(n);

2)Step2由矩陣計(jì)算目標(biāo)用戶與其他用戶之間的相似度，復(fù)雜度為O(m2);

3)Step3計(jì)算預(yù)測評分與真實(shí)評分之間的偏差大小，復(fù)雜度為O(n2);

4)Step4計(jì)算用戶間的間接信任度，復(fù)雜度為O(m2)；

5)Step5、Step6、Step7階段為用戶推薦階段，主要的時(shí)間是在項(xiàng)目的排序上，因此復(fù)雜度最差為O(m2)。

雖然推薦計(jì)算量會隨著用戶評分?jǐn)?shù)據(jù)和標(biāo)簽數(shù)據(jù)的增加而有所增加，但是相比較傳統(tǒng)的協(xié)同過濾算法，新方法在提高推薦準(zhǔn)確度的同時(shí)并沒有增加算法的推薦時(shí)間，具有一定的可行性。

4試驗(yàn)結(jié)果與分析

4.1數(shù)據(jù)集及試驗(yàn)環(huán)境

采用來源于美國明尼達(dá)蘇大學(xué)GroupLens研究小組提供的MovieLens站點(diǎn)100K公開數(shù)據(jù)集。其內(nèi)容主要包括來自943個(gè)用戶對1682部電影的大約100000個(gè)評價(jià)分?jǐn)?shù)信息，每個(gè)注冊用戶均對其觀看過得電影進(jìn)行評價(jià)并給出評分值且都至少評價(jià)了20部電影；評分值在1到5之間；“1”表示“不喜歡”、“2”表示“不太喜歡”、“3”表示“一般喜歡”、“4”表示“比較喜歡”、“5”表示“非常喜歡”。試驗(yàn)過程中，整個(gè)數(shù)據(jù)集被隨機(jī)分出20%當(dāng)作試驗(yàn)的測試集，其余的80%當(dāng)作試驗(yàn)的訓(xùn)練集。

筆者采用Java實(shí)現(xiàn)了基于社會網(wǎng)絡(luò)的協(xié)同推薦方法，并設(shè)計(jì)了若干試驗(yàn)對該方法的推薦效率進(jìn)行驗(yàn)證。試驗(yàn)環(huán)境為Intel Core i5處理器，CPU主頻為2.5GHz，4G內(nèi)存的PC機(jī)，Windows7操作系統(tǒng)，jdk版本為1.7。

4.2評價(jià)指標(biāo)

考慮推薦算法優(yōu)劣程度，可以由很多指標(biāo)來評價(jià)。筆者通過系統(tǒng)的平均排序分、平均絕對誤差2個(gè)指標(biāo)驗(yàn)證算法的效率及其性能。

1)平均絕對誤差(MAE)通過計(jì)算測試集中用戶實(shí)際評分和利用推薦算法預(yù)測出來的評分間的絕對誤差值來度量推薦系統(tǒng)的推薦準(zhǔn)確度。當(dāng)MAE的值越小，表明推薦結(jié)果的精度越高，反之，則越低[11]。

假設(shè)預(yù)測用戶評價(jià)集記為{p1,p2,…,pN}，而真實(shí)的用戶評價(jià)集記為{q1,q2,…,qN}，則平均絕對誤差MAE的計(jì)算公式為：

(9)

式中，n為被評分項(xiàng)目的數(shù)量；pi為系統(tǒng)預(yù)測評分值；qi為數(shù)據(jù)集中的真實(shí)評分值。

2)平均排序分通過計(jì)算項(xiàng)目在列表中位置度量系統(tǒng)推薦的精準(zhǔn)性。其計(jì)算公式[12]如下：

(10)

式中，N為未被評分的項(xiàng)目數(shù)；Li為i在推薦列表中的序號。

4.3結(jié)果分析

1)算法的準(zhǔn)確率對比為了驗(yàn)證筆者提出算法在推薦結(jié)果精確度方面較其他類似算法具有的優(yōu)勢，把其與基于用戶的協(xié)同推薦算法(CF-USER)、基于項(xiàng)目的協(xié)同推薦算法(CF-ITEM)及其他基于信任的推薦方法[2](CF-信任支持度)進(jìn)行了對比，結(jié)果如圖4所示。由圖4可以看出，相同數(shù)量用戶鄰居集下，筆者提出算法的MAE值均低于其他幾種算法，且當(dāng)最近鄰居數(shù)為40時(shí)，該算法推薦精度達(dá)到最優(yōu)；繼續(xù)增大鄰居數(shù)量可以發(fā)現(xiàn)，該方法推薦精度逐漸地趨向于平穩(wěn)。

2)算法的平均排序分對比各算法平均排序分試驗(yàn)結(jié)果如圖5所示。由圖5中可以發(fā)現(xiàn)，隨著數(shù)據(jù)集中訓(xùn)練集占的比重逐漸增加，算法的平均排序分也慢慢地減小，筆者提出算法計(jì)算得出的平均排序分要低于另外3個(gè)算法。綜上所述，該方法在推薦精度上要高于其他幾個(gè)方法。

圖4　推薦算法的MAE比較　　　　　　　　　　　　　　　　　圖5　算法的平均排序分

5結(jié)語

推薦系統(tǒng)作為解決信息過載的一種有效手段，如何提高其推薦精度已成為非常重要的研究問題。在社會網(wǎng)絡(luò)中考慮推薦信任對推薦準(zhǔn)確性的提高具有重要的意義。但人們對推薦技術(shù)的滿意度不僅僅體現(xiàn)在推薦結(jié)果的準(zhǔn)確性上，下一步的主要工作是提出有效的算法來提高用戶對推薦系統(tǒng)的滿意度，包括推薦結(jié)果的覆蓋率、多樣性等等。

[參考文獻(xiàn)]

[1]Massa P, Avesani P. Trust-Aware Collaborative Filtering for Recommender Systems[A].Proc of Federated Int Conference on the Move to Meaningful Internet: Coopis[C]. Springer Berlin Heidelberg, 2004:492～508.

[2]叢麗輝,王科,夏秀峰,等.利用信任支持度構(gòu)建客戶信任網(wǎng)絡(luò)[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(6):110～113.

[3]朱麗中,徐秀娟,劉宇.基于項(xiàng)目和信任的協(xié)同過濾推薦算法[J].計(jì)算機(jī)工程,2013:39(1):58～66.

[4]Victor, Cornelis P, Cock C, et al. Trust-and Distrust-Based Recommendations for Controversial Reviews[J]. Intelligent Systems IEEE, 2011, 26(1):48～55.

[5]徐守坤,孫德超,李寧,等.一種結(jié)合語義Web和用戶信任網(wǎng)絡(luò)的協(xié)同過濾推薦模型[J].計(jì)算機(jī)應(yīng)用研究,2014，31(6):1714～1718.

[6]施榮華,幸晶晶.一種基于群組的P2P網(wǎng)絡(luò)信任管理模型[J].計(jì)算機(jī)應(yīng)用研究,2010,27(7):2638～2640.

[7] 張富國. 基于社交網(wǎng)絡(luò)的個(gè)性化推薦技術(shù)[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2014, 35(7):1470～1476.

[8]Bhuiyan T. A survey on the relationship between trust and interest similarity in online social networks[J].Journal of Emerging Technologies in Web Intelligence, 2010,2(4):291～299.

[9]黃創(chuàng)光,印鑒,汪靜,等.不確定近鄰的協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(8):1369～1377.

[10]喬秀全,楊春,李曉峰,等.社交網(wǎng)絡(luò)服務(wù)中一種基于用戶上下文的信任度計(jì)算方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(12):2403～2413.

[11] Zhou T, Jiang L L, Su R Q, et al. Effect of initial configuration on network-based recommendation[J]. Epl：europhysics Letters, 2008, 81(5):15～18.

[12]趙琴琴,魯凱,王斌.SPCF:一種基于內(nèi)存的傳播史協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2013,36(3):671~676.

[編輯]洪云飛

[引著格式]汪千松，蔣勝，王忠群.基于社會網(wǎng)絡(luò)的協(xié)同推薦方法[J].長江大學(xué)學(xué)報(bào)(自科版)，2015,12(16)：29～33.

25 Design and Implementation of A Field Section Map Sketching System Based on ArcEngine Assistance

Li Gongquan,Gan Le,Wang Jing(YangtzeUniversity,Wuhan430100)

Abstract:Geological sectional map is a general geological map to present attitudes and distribution of rock strata.Rapid automatic mapping can meet the general requirement in practical application.The geography object and interface contained in ArcEngine component library can meet the requirement of geological section map.According to the production flow of field geological map, a new geological sectional map drawing system is designed based on ArcEngine, which is standardized, practical, easy for management and maintaining.The system adopts the single user system structure because a user occupies all the resources and different users can the exchange data by text files.The three main functions are considered including information inputting, section generating, and section filling.Through practical application,rock stratum map can be rapid built with topographical maps and collected data.It has higher practical value.

Key words:GIS; ArcEngine; geological sectional map

[作者簡介]皇蘇斌(1986-)，男，碩士，助教，現(xiàn)主要從事數(shù)據(jù)挖掘，電子商務(wù)方面的教學(xué)與研究工作；E-mail:huangsubin2007@163.com。

[基金項(xiàng)目]安徽省高校省級科學(xué)研究項(xiàng)目(TSKJ2014B10)；安徽工程大學(xué)青年基金項(xiàng)目(2013YQ30)；安徽工程大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目(JSJKF201504)。

[收稿日期]2015-02-18

[文獻(xiàn)標(biāo)志碼]A

[文章編號]1673-1409(2015)16-0029-05

[中圖分類號]TP391