在線社會網(wǎng)絡(luò)中推薦算法的研究

黃藍(lán)會

(寶雞文理學(xué)院 計算機學(xué)院， 寶雞 721016)

在線社會網(wǎng)絡(luò)中推薦算法的研究

黃藍(lán)會

(寶雞文理學(xué)院 計算機學(xué)院， 寶雞 721016)

針對在線社會網(wǎng)絡(luò)中用戶間的關(guān)系存在多種關(guān)系復(fù)合的情況，應(yīng)用復(fù)雜網(wǎng)絡(luò)理論設(shè)計了結(jié)合協(xié)同過濾推薦算法和基于網(wǎng)絡(luò)結(jié)構(gòu)推薦算法的混合推薦算法。利用復(fù)合多子網(wǎng)模型和在線社會網(wǎng)絡(luò)演化模型設(shè)計的推薦系統(tǒng)用戶模型,并在此基礎(chǔ)上提出了基于在線社會網(wǎng)絡(luò)社團結(jié)構(gòu)的最近鄰查詢算法，并可根據(jù)最近鄰集合評分后做出推薦。仿真實驗證明，該算法具有較高的準(zhǔn)確率和召回率。

在線社會網(wǎng)絡(luò)； 復(fù)雜網(wǎng)絡(luò)； 數(shù)據(jù)挖掘； 推薦算法

0 引言

網(wǎng)絡(luò)的迅猛發(fā)展伴隨著信息量的倍數(shù)增加，目前的主要購物平臺京東、淘寶的在線商品數(shù)量超過了8億件，主要通信平臺微信用戶超過5億，由于信息量太多，用戶很難快速直接獲取有效信息，形成信息超載問題。[1][2]

目前，針對信息超載問題的解決辦法主要有兩種，一種是通過搜索引擎如Google、Baidu等檢索系統(tǒng)，但這些檢索系統(tǒng)只能被動地按照用戶給出的條件查詢，最后返回一樣的查詢結(jié)果，無法主動為用戶提供信息；另一種是個性化推薦系統(tǒng)[3]，通過收集用戶的信息，分析他的需求和興趣后向其推薦信息或產(chǎn)品。[2][4]目前大型的電子商務(wù)平臺如京東、淘寶等都使用了不同形式的自動推薦系統(tǒng)。[5]推薦系統(tǒng)是電子商務(wù)領(lǐng)域的重要研究內(nèi)容之一，其中的推薦算法是關(guān)鍵點，本文以豆瓣網(wǎng)為例，研究適合在線社會網(wǎng)絡(luò)的推薦算法。

豆瓣網(wǎng)是目前國內(nèi)用戶數(shù)量較大的書影音評價、推薦和交友網(wǎng)站，豆瓣注冊用戶之間的形成好友關(guān)系的方式總結(jié)起來有兩種，一種是直接通過“關(guān)注”操作形成顯式好友關(guān)系；還有一種是在豆瓣網(wǎng)中由于對同一個事物有相同的愛好成為隱式好友關(guān)系。在豆瓣網(wǎng)中用戶采用1-10分的數(shù)字代表自己對某部電影的喜好程度，喜好同一部電影的用戶因為興趣愛好可能組成討論組或好友群，這種隱含朋友關(guān)系實際上是從用戶的行為角度出發(fā)，利用相同興趣作為媒介，幫助用戶通過喜愛的電影資源找到興趣相似的其他用戶，然后通過他們找到更多適合自己的電影，最后發(fā)展為進(jìn)入電影購票網(wǎng)站購買電影票，成功完成一次推薦活動。

1 相關(guān)研究

推薦系統(tǒng)中推薦方法很多，本文主要研究兩種推薦方法，一種是協(xié)同過濾推薦[6]。其基本思想是：系統(tǒng)認(rèn)為某個用戶傾向于購買具有相同興趣愛好的同類用戶所購買的商品，即他的鄰居用戶的購買行為會影響這個用戶可能的購買意向。該算法根據(jù)用戶對信息的評分建立評分矩陣，利用用戶和評分的模型建立評分矩陣，通過余弦相似度[7]、相關(guān)相似性[8]以及修正的余弦相似度算法來計算兩個用戶購買同一個商品的相似度。這種利用相似性算法來計算兩個用戶相似度的方案適用于評分矩陣數(shù)量較多的情況。[9]如果某些用戶為了保護(hù)個人信息或者是嫌麻煩沒有在購買商品或看到信息后給出評分，就會導(dǎo)致矩陣中數(shù)據(jù)較少，產(chǎn)生數(shù)據(jù)矩陣稀疏問題，從而降低了這種算法的推薦效果[10]。還一種推薦方法是基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦。其基本思想是：用戶和產(chǎn)品都抽象成節(jié)點，用戶和商品直接的關(guān)系抽象成邊，節(jié)點和邊組成網(wǎng)絡(luò)。周濤等[11]提出了二分圖上的資源分配關(guān)系，例如如果用戶在網(wǎng)絡(luò)中針對某個信息發(fā)表了評價或者購買了商品，就認(rèn)為用戶和該信息或商品建立了聯(lián)系。

2 推薦算法

本文將豆瓣網(wǎng)用戶關(guān)注的人所構(gòu)成的網(wǎng)絡(luò)稱之為豆瓣網(wǎng)用戶關(guān)注關(guān)系網(wǎng)，這個好友關(guān)系是顯式的，將豆瓣網(wǎng)用戶對電影的評價所構(gòu)成的網(wǎng)絡(luò)稱之為豆瓣網(wǎng)用戶影評關(guān)系網(wǎng)，這個好友關(guān)系是隱式的。利用復(fù)雜網(wǎng)絡(luò)理論，設(shè)計了一個將豆瓣網(wǎng)用戶關(guān)注關(guān)系網(wǎng)和豆瓣網(wǎng)用戶影評相似關(guān)系網(wǎng)組成的在線社會網(wǎng)絡(luò)演化模型[12]。根據(jù)用戶對一部電影評分的一致性設(shè)定相關(guān)興趣閾值，如果兩個節(jié)點的相似性系數(shù)超過閾值，則認(rèn)為這兩個用戶有相同的興趣，模型中表示為該用戶和電影之間有連邊，形成隱式好友關(guān)系。協(xié)同過濾推薦主要用隱式關(guān)系的相似性作為判斷依據(jù)，沒有考慮顯式好友關(guān)系有可能以后建立隱式關(guān)系，因此，本文將兩種關(guān)系都作為推薦系統(tǒng)中用戶間相似性的判斷依據(jù)，設(shè)計一個動態(tài)用戶模型。

建立動態(tài)用戶模型的步驟是，首先根據(jù)用戶電影評分?jǐn)?shù)據(jù)，建立隱式關(guān)系子網(wǎng)，然后建立顯式關(guān)系子網(wǎng)，再根據(jù)多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)模型的子網(wǎng)加載運算，構(gòu)造多關(guān)系的復(fù)合網(wǎng)，在構(gòu)建過程中將新用戶作為新的節(jié)點加進(jìn)去。

基于多關(guān)系的在線社會網(wǎng)絡(luò)演化模型建立動態(tài)用戶模型，建模步驟如下：

(1) 假設(shè)復(fù)合網(wǎng)G=(V，E，R，F(xiàn))中存在N種關(guān)系，其中穩(wěn)固關(guān)系為N1種，不穩(wěn)固關(guān)系為N2種，則R=R1×…×Ri×…×RN=((r1,…,ri,…,rN)|ri∈Ri，l≤i≤N)且dom(ri)=(0,1}(1≤i≤N)，其中1表示存在關(guān)系Ri，0表示不存在。

(2) 構(gòu)造初始網(wǎng)絡(luò)：構(gòu)造具有m0個節(jié)點，e0條邊的多關(guān)系網(wǎng)絡(luò)，確保節(jié)點沒有孤立點并且網(wǎng)絡(luò)中的邊沒有重連，同時vh，vi∈{m0}，∈{e0)，存在F()=(r1,…，ri,…，rN)且dom(ri)=1(1≤i≤N)。

推薦系統(tǒng)的動態(tài)用戶模型生成后的第二步就是根據(jù)對模型進(jìn)行聚類，通過社團發(fā)現(xiàn)算法可以得到多個鄰居用戶群，設(shè)定相關(guān)閾值后篩選出最近鄰居。本文設(shè)定目標(biāo)用戶ud，目標(biāo)用戶的最近鄰居數(shù)為m，聚類結(jié)果為C，社團中度最大的用戶節(jié)點a，相似性閾值為。

具體算法步驟如下：

(1) 設(shè)置最近鄰用戶集NUd=?；

(2) 判斷是否將社團加入最近鄰居用戶集合。首先計算每個社團結(jié)構(gòu)Ci中度最大的用戶節(jié)點與目標(biāo)用戶的相似度sim(ud,a)，將相似度按照降序排列；

(3) 將第(2)步得到的相似度和設(shè)定閾值比較，只有當(dāng)sim(ud,a)≥α?xí)r，將整個社團結(jié)構(gòu)加入最近鄰居用戶集；

(4) 在最近鄰居集合中選擇前K個用戶作為目標(biāo)用戶，根據(jù)第(2)步相似度的排序結(jié)果可知，這K個目標(biāo)用戶的相似度最高。

(5) 根據(jù)公式一生成第(4)步目標(biāo)用戶對同一部電影的預(yù)測評分。

推薦精度的高低由相似性閾值α來調(diào)整，如果候選鄰居集合少，可以調(diào)小α，這樣可以在更多的用戶集合中查找最近鄰居。

3 實驗結(jié)果與分析

評價推薦算法優(yōu)劣的方法很多，本文主要通過分類準(zhǔn)確度來評價該算法和協(xié)同過濾推薦算法。 衡量分類準(zhǔn)確度的主要指標(biāo)是準(zhǔn)確率和召回率。

準(zhǔn)確率定義為系統(tǒng)推薦的所有項目中用戶喜歡的項目的比例。

公式為準(zhǔn)確率=

召回率定義為用戶喜歡的項目中是系統(tǒng)推薦的項目比例。

公式為召回率=

本文利用自己編寫的程序[13]抓取豆瓣網(wǎng)的數(shù)據(jù)，利用協(xié)同過濾算法和本文推薦算法進(jìn)行準(zhǔn)確率和召回率的比較。經(jīng)過數(shù)據(jù)預(yù)先處理后抓取了其中的10 235個用戶以及他們在豆瓣網(wǎng)上評價的11 298部電影，根據(jù)推薦算法，為用戶推薦未評分但可能喜歡的電影。

將實驗中的用戶的電影評分?jǐn)?shù)據(jù)集劃分80%訓(xùn)練集和20%測試集，利用數(shù)據(jù)集合E隨機選取測試集Ep和訓(xùn)練集Et，某個用戶a相關(guān)的測試集定義為，訓(xùn)練集地定義為 。將測試集中用戶分成10組，同時獲取這10 235個用戶給出的電影評分,如圖1、圖2所示。

圖1 比較兩個算法的準(zhǔn)確率

圖2 比較兩個算法的召回率

從圖1和圖2可以看出，本文提出的推薦算法10組用戶表現(xiàn)平穩(wěn)，在準(zhǔn)確率和召回率方面都比協(xié)同過濾推薦算法高。

4 總結(jié)

個性化服務(wù)是Web信息處理的主要發(fā)展趨勢之一，個

性化服務(wù)技術(shù)中提高推薦信息的準(zhǔn)確率是目前個性化服務(wù)的主要研究方向。本文利用用戶在網(wǎng)絡(luò)中的多種關(guān)系建立網(wǎng)絡(luò)模型，緩解了推薦系統(tǒng)的數(shù)據(jù)稀疏問題，將新用戶采用動態(tài)更新的方式加到網(wǎng)絡(luò)中，解決了冷啟動問題，在購物平臺使用推薦算法，為用戶量身定做地推薦他感興趣的商品將是商業(yè)應(yīng)用的發(fā)展趨勢。

[1] 陳潔敏,湯庸,李建國,等. 個性化推薦算法研究[J]. 華南師范大學(xué)學(xué)報(自然科學(xué)版),2014,46(5):9-15.

[2] 王國霞,劉賀平. 個性化推薦系統(tǒng)綜述[J]. 計算機工程與應(yīng)用,2012,48(7):66-74.

[3] 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 Oil Knowledgeand Data Engineering,2005,17(6):734-749．

[4] 吳泓辰,王新軍,成勇,等. 基于協(xié)同過濾與劃分聚類的改進(jìn)推薦算法[J]. 計算機研究與發(fā)展,2011,48:205-212.

[5] 李濤等. 王建東,葉飛躍,等.一種基于用戶聚類的協(xié)同過濾推薦算法[J]. 系統(tǒng)工程與電子技術(shù),2007,29(7):1178-1182.

[6] Adomavicius G,Tuzhilin A. Towards the next generation of recommender system: a survey of the state-of-the-art and possible extensions[J]. IEEE Transaction on Knowledge and Data Engineering,2005,17(6):734-749.

[7] Salton G，McGill M. Introduction to modem informationretrieval [M]. New York, USA：McGraw-Hill,1983.

[8] Resnick P,Iacovou N，Suchak M. An open architecture for collaborative fileting of net news[C]∥Proc. of ACM conferenceon Computer Supported Cooperative Work,1994.

[9] 文俊浩,舒珊. 一種改進(jìn)相似性度量的協(xié)同過濾推薦算法[J]. 計算機科學(xué),2014,41(5):68-70.

[10] 鄧愛林,朱揚勇,施伯樂. 基于項目評分預(yù)測的協(xié)同過濾推薦算法[J]. 軟件學(xué)報,2003,14(9):1621-1628.

[11] Zhou T, Jiang LL, Su R Q, et al. Effect of initialconfigurationon network-basedrecommendation [J]. EPL(Euro physics Letters),2008,81(5):58004.

[12] 黃藍(lán)會. 基于社會媒體網(wǎng)絡(luò)的聚類方法的研究[J].微型電腦應(yīng)用,2016,32(6):1-2.

[13] 黃藍(lán)會.基于在線社會網(wǎng)絡(luò)的網(wǎng)絡(luò)爬蟲的研究和設(shè)計[J].電子設(shè)計工程,2014,22(6):106-108.

Recommendation Algorithm in Online Social Network

Huang Lanhui

School of Computer,Baoji University of Arts and Science,Baoji 721016,China

In the online social network, there are many kinds of relationships. In this paper, a hybrid algorithm is introduced to design the complex network. This algorithm combines the two algorithms, one is a collaborative filtering recommendation algorithm, and other is based on the characteristics of the network structure recommendation algorithm. Based on the above researches, a recommendation algorithm for multi-relationship online social network is proposed. User model of the recommendation system is derived from multi-relationship online social network evolution model. Based on the user model, the nearest neighbors query method of community in multi-relationship online social network is proposed, recommendations are made based on the nearest neighbor set and items set selected by the nearest neighbors. Experiments prove that evaluation criteria of recommended system, such as, recall rate, precision rate and so on are higher than those of traditional collaborative filtering recommendation system, and its prediction is more accurate.

Online social network; Complex network; Data mining; Recommendation algorithm

國家自然科學(xué)基金(No.61379030);陜西省教育廳專項科研項目(15JK1028)

黃藍(lán)會(1980-),女,湖南岳陽人,碩士,講師,研究方向:物聯(lián)網(wǎng)應(yīng)用,數(shù)據(jù)挖掘。

1007-757X(2017)04-0042-03

TP311

A

2016.10.14)