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

汪千松，蔣勝，王忠群

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

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

汪千松，蔣勝，王忠群

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

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

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

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

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

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

1理論與方法

1.1基于用戶-項目評分的相似度計算

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

2)用戶-項目評分相似度計算目前相似度的計算方法主要余弦相似度、修正的余弦相似度及Pearson相關相似度度量方法，筆者采用修正的余弦相似度計算方法：

(1)

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

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

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

圖1　社會網(wǎng)絡中直接信任關系圖

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

對用戶uc所有評價項目集合Ic，且j∈Ic：

(2)

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

(3)

(4)

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

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

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

(5)

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

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

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

(6)

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

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

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

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

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

(7)

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

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

(8)

3算法描述及復雜度分析

3.1算法描述

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

輸出：Top-N推薦結果。

推薦步驟如下：

Step1對每個用戶u，找到同目標用戶uT共同評分過的項目，將其記錄在items中；

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

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

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

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

Step6根據(jù)式(8)計算得出目標用戶uT的所有項目的預測評分；

Step7為目標用戶uT生成Top-N推薦。

3.2復雜度分析

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

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

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

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

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

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

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

4試驗結果與分析

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

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

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

4.2評價指標

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

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

假設預測用戶評價集記為{p1,p2,…,pN}，而真實的用戶評價集記為{q1,q2,…,qN}，則平均絕對誤差MAE的計算公式為：

(9)

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

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

(10)

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

4.3結果分析

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

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

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

5結語

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

[參考文獻]

[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]叢麗輝,王科,夏秀峰,等.利用信任支持度構建客戶信任網(wǎng)絡[J].計算機工程與應用,2012,48(6):110～113.

[3]朱麗中,徐秀娟,劉宇.基于項目和信任的協(xié)同過濾推薦算法[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]徐守坤,孫德超,李寧,等.一種結合語義Web和用戶信任網(wǎng)絡的協(xié)同過濾推薦模型[J].計算機應用研究,2014，31(6):1714～1718.

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

[7] 張富國. 基于社交網(wǎng)絡的個性化推薦技術[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].計算機學報,2010,33(8):1369～1377.

[10]喬秀全,楊春,李曉峰,等.社交網(wǎng)絡服務中一種基于用戶上下文的信任度計算方法[J].計算機學報,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].計算機學報，2013,36(3):671~676.

[編輯]洪云飛

[引著格式]汪千松，蔣勝，王忠群.基于社會網(wǎng)絡的協(xié)同推薦方法[J].長江大學學報(自科版)，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ù)挖掘，電子商務方面的教學與研究工作；E-mail:huangsubin2007@163.com。

[基金項目]安徽省高校省級科學研究項目(TSKJ2014B10)；安徽工程大學青年基金項目(2013YQ30)；安徽工程大學計算機應用技術重點實驗室基金項目(JSJKF201504)。

[收稿日期]2015-02-18

[文獻標志碼]A

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

[中圖分類號]TP391