在線社會網絡中推薦算法的研究

黃藍會

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

在線社會網絡中推薦算法的研究

黃藍會

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

針對在線社會網絡中用戶間的關系存在多種關系復合的情況，應用復雜網絡理論設計了結合協同過濾推薦算法和基于網絡結構推薦算法的混合推薦算法。利用復合多子網模型和在線社會網絡演化模型設計的推薦系統用戶模型,并在此基礎上提出了基于在線社會網絡社團結構的最近鄰查詢算法，并可根據最近鄰集合評分后做出推薦。仿真實驗證明，該算法具有較高的準確率和召回率。

在線社會網絡； 復雜網絡； 數據挖掘； 推薦算法

0 引言

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

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

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

1 相關研究

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

2 推薦算法

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

建立動態用戶模型的步驟是，首先根據用戶電影評分數據，建立隱式關系子網，然后建立顯式關系子網，再根據多子網復合復雜網絡模型的子網加載運算，構造多關系的復合網，在構建過程中將新用戶作為新的節點加進去。

基于多關系的在線社會網絡演化模型建立動態用戶模型，建模步驟如下：

(1) 假設復合網G=(V，E，R，F)中存在N種關系，其中穩固關系為N1種，不穩固關系為N2種，則R=R1×…×Ri×…×RN=((r1,…,ri,…,rN)|ri∈Ri，l≤i≤N)且dom(ri)=(0,1}(1≤i≤N)，其中1表示存在關系Ri，0表示不存在。

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

推薦系統的動態用戶模型生成后的第二步就是根據對模型進行聚類，通過社團發現算法可以得到多個鄰居用戶群，設定相關閾值后篩選出最近鄰居。本文設定目標用戶ud，目標用戶的最近鄰居數為m，聚類結果為C，社團中度最大的用戶節點a，相似性閾值為。

具體算法步驟如下：

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

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

(3) 將第(2)步得到的相似度和設定閾值比較，只有當sim(ud,a)≥α時，將整個社團結構加入最近鄰居用戶集；

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

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

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

3 實驗結果與分析

評價推薦算法優劣的方法很多，本文主要通過分類準確度來評價該算法和協同過濾推薦算法。 衡量分類準確度的主要指標是準確率和召回率。

準確率定義為系統推薦的所有項目中用戶喜歡的項目的比例。

公式為準確率=

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

公式為召回率=

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

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

圖1 比較兩個算法的準確率

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

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

4 總結

個性化服務是Web信息處理的主要發展趨勢之一，個

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

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

[2] 王國霞,劉賀平. 個性化推薦系統綜述[J]. 計算機工程與應用,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] 吳泓辰,王新軍,成勇,等. 基于協同過濾與劃分聚類的改進推薦算法[J]. 計算機研究與發展,2011,48:205-212.

[5] 李濤等. 王建東,葉飛躍,等.一種基于用戶聚類的協同過濾推薦算法[J]. 系統工程與電子技術,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]. 計算機科學,2014,41(5):68-70.

[10] 鄧愛林,朱揚勇,施伯樂. 基于項目評分預測的協同過濾推薦算法[J]. 軟件學報,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] 黃藍會. 基于社會媒體網絡的聚類方法的研究[J].微型電腦應用,2016,32(6):1-2.

[13] 黃藍會.基于在線社會網絡的網絡爬蟲的研究和設計[J].電子設計工程,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

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

黃藍會(1980-),女,湖南岳陽人,碩士,講師,研究方向:物聯網應用,數據挖掘。

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

TP311

A

2016.10.14)