一種基于用戶標簽的社交網絡好友推薦算法

汪 強，何廣達，楊安桔，張臣坤

(安徽新華學院信息工程學院, 安徽 合肥 230088)

隨著互聯網中的增加，用戶需要從不同的互聯網平臺中獲取大量信息，但如何快速地獲取用戶目標信息是目前互聯網信息獲取急需解決的問題[1].而且隨著信息量的不斷增加，信息分類混亂的現象也日趨嚴重，即使是搜索引擎也很難檢索到用戶的目標信息[2].因此，推薦系統[3,4]應運而生，信息推薦系統是一種可以通過用戶在互聯網中產生的歷史數據信息，分析用戶個性化偏好，向用戶推薦感興趣的物品或信息的系統.

推薦系統采用的主要推薦算法是協同過濾算法[5,6]，協同過濾推薦算法分為：

(1)基于用戶的協同過濾算法

如果用戶對項目、產品等的評分比較相近，則他們可能有相同的興趣、愛好，那么他們可能對沒有產生評分的項目評分也比較相近.尋找相似興趣用戶作為最近鄰居，把最近鄰居的項目推薦給目標用戶.

(2)基于項目的協同過濾算法

與用戶之間的性質類似，項目之間也具有相似特征，根據已知用戶對項目的評分來預測用戶對未知相似項目的評分，將評分排序，按序將項目推薦給目標用戶.

協同過濾算法主要不足[7,8]有三個方面：

(1)數據稀疏問題.由于目前的應用系統中用戶和項目數據規模較大，用戶對項目產生的評分有限，造成評分數據稀疏，給相似性的計算和項目的推薦帶來困難；

(2)冷啟動問題.目前的應用系統產生新數據量巨大，每一個新項目進進入系統時，還沒有產生用戶評價，采用傳統的協同過濾算法就沒有辦法對新項目產生推薦.

(3)可擴展性問題.應用系統中的用戶和項目快速增長，推薦算法的復雜度也隨之快速增長，算法的時間復雜度大大增加，導致可擴展性較差.

現在大多數社交網絡的系統好友推薦都是基于共同好友的推薦.但對于新用戶，無法解決冷啟動的問題.然而社交網絡都為用戶提供標簽，由于標簽由用戶本人標記，所以標簽可以反映用戶的真實興趣，同時標簽不依賴已有的朋友圈，可以一定程序上解決冷啟動的問題.本文以新浪微博數據為基礎進行研究,提出一種基于用戶標簽的協同過濾算法,建立用戶推薦模型,為社交網絡用戶推薦具有相同興趣愛好的好友.在體現用戶興趣的同時，解決推薦系統冷啟動的問題.

1 基于用戶標簽的協同過濾算法

1.1 基于用戶的協同過濾算法

基于用戶的協同過濾推薦又稱為最近鄰(Nearest-Neighbor)協同過濾推薦或者 KNN(K-Nearest-Neighbor)算法，該推薦算法主要有以下步驟:

(1)數據初始化

根據用戶的評分信息建立用戶-項目評分矩陣,如表1所示：

表1 用戶-項目評分表

用戶與項目評分的關系用二部圖表示，令G={V，E}為用戶-項目二部圖，該圖是一個無向圖，其中 V=VU∪VI ， 其中VU是由用戶所構成的頂點集，VI是由物品構成的頂點集，且用戶對項目的評分作為用戶與項目頂點連邊上的權重，構成用戶-項目二部圖,如圖1所示：

(a) 不帶權重的二部圖 (b)帶權重的二部圖

表1中，U1,U2,U3為用戶，p,q為項目，表1中的數值為用戶對項目的評分，若數值為空則表示用戶沒有對項目評分.圖1的二部圖由表1轉換而來，圖的兩側為項目和用戶，圖1(a)和圖1(b)分別對應不帶權重和帶權重的二部圖，前者不考慮評分多少，只要有評分則連接對應的用戶和項目，后者在連接對應用戶和項目的時候需要加上評分.

(2)最近鄰居集的計算

采用相似度計算方法尋找目標用戶的最近鄰居集,主要選擇：Pearson相關系數[9]和約束Pearson 相關系數[10]，表示如下：

1)Pearson相關系數

Pearson相關系數是一種衡量兩個變量之間的線性相關性的方法.用戶u、v的 Pearson 系數相似性可由公式(1)表示:

sim(u,v)=

(1)

2)約束 Pearson 相關系數

約束 Pearson相關系數是在Pearson相關系數計算的基礎上改進得到，由公式(2)表示：

sim(u,v)=

(2)

其中Rmed表示系統設定的評分中值，如MovieLens系統中設置電影的評分區間為1～5，那么Rmed的值即為3.

(3)預測評分及產生推薦結果

首先計算目標用戶u的最近鄰居集，表示為： N (u)= {u1，u2，…uK}，然后選擇最近鄰居已評分項目，再預測目標用戶對這些項目的評分，最后預測評分按序推薦給目標用戶.

評分預測計算如公式(3)所示:

(3)

其中Ru和Rv為用戶u、v各自所有評分項目的打分均值.

1.2 基于用戶標簽的協同過濾算法

由于標簽由用戶手動產生，具有較強的主觀意愿，可以表示用戶的興趣，所以本文選擇應用系統中的用戶標簽數據，將標簽數據作為算法中的項目進行分析、建模，目標是為了發現相同興趣用戶圈子，較準確地建立基于用戶興趣的好友推薦算法.本文主要采用語義+標簽的數據分析方法，為系統中的用戶推薦更高質量的好友服務.

2 實驗及結果分析

2.1 數據來源

新浪微博為數據研究人員開放了數據平臺的API[11]接口，采用Python語言抽取標簽數據存入文件便于下一步的分析.數據獲取流程步驟如下：

(1)獲取用戶的標簽數據；

(2)定時獲取數據中的數據；

(3)讀數據進行處理；

(4)將處理好的數據分別寫入對應的文件中.

如圖2所示：

圖2 數據獲取流程圖

根據圖2，設定特定的微博用戶帳號(uid)為實驗帳號，抽取實驗帳號已經關注的好友(friendid)標簽.由指定實驗帳號登陸微博平臺，進入信息抽取頁面；再獲取用戶的關注列表(即follow表)和用戶標簽(即tag表).

2.2實驗步驟

本文中實驗帳號用戶的標簽有: 旅行、出租車、美食、服裝、機器學習等9個標簽.下面是數據預處理的步驟：

(1)計算語義距離

由詞語之間的相近程序來表示語義距離，相似程度反映兩個詞之間關聯度.用戶標簽一般由若干個短語構成.本文實驗帳號用戶的標簽由9個短語構成，由這9個短語構成一個9×9相似度矩陣M9×9，矩陣中的每個值表示兩個短語間的相似度，即語義距離.

本文采用用Xsimilarity[12]語義距離計算軟件進行計算，計算結果如下矩陣：

圖3 相似度矩陣

其中標簽集合為C={class1，class2，class3，…，class9}，|C|=9.

(2)合并標簽

語義距離體現了短語之間的關聯程度，所以兩個關聯程度較高的短語可以合并為一類短語，可以降低數據維度.因此，在本文中，定義語義距離的閾值為0.5，當語義距離>=0.5時將兩個短語合并成一個短語.

本文實驗中的短語經合并后變為7個標簽，對應一個R'7×7的相似矩陣，即C'={class1，class2，class3，…，classn}，|C'|=7.如圖4所示：

圖4 合并后的相似矩陣

(3)計算各層用戶之間的相似度

1)求0層和第1層的相似度

2)取1層用戶的每一個標簽與第0層的一個標簽計算相似度

3)取1層用戶id

4)取1層用的每一個標簽

5)計算1、2層用戶間的相似度

6)計算1、2層用戶間的標簽相似度

7)取2層用戶id

8)計算1層用戶所有的標簽與1層用戶的某一個用戶的所有2層用戶標簽的權重.

圖5 Top-3推薦結果

經過以上計算，最終將用戶的相似矩陣導入到txt文件中，通過排序取出相似度排前三的用戶作為推薦對象.推薦結果如圖5(見上一頁)所示.

圖5中，1230663070、1664207987、1197930844為與目標用戶1191042674相似度前三的用戶，用戶下方向為推薦結果.根據圖5可以看出，本文中所采用的推薦算法，可以根據標簽信息發現朋友圈，在推薦系統中對好友進行有效推薦.

3 總結

本文以新浪微博的標簽數據作為推薦分析數據源，抽取了部分用戶標簽表(即tag表)和用戶關注表(即follow表)中的10個標簽作語義分析，建立基于用戶標簽的推薦算法.通過實驗驗證，通過標簽的相似計算，可以尋找到有相似興趣愛好的朋友圈，從而進行好友推薦，該方法可以在推薦系統中應用推廣.但由于數據的抽取受到限制，對推薦的準確性無法進一步衡量，下一步工作將繼續抽取大量數據進行實驗，進一步提高推薦的準確率.

參考文獻：

[1]呂本富, 張崇. “互聯網+”環境下信息安全的挑戰與機遇[J]. 中國信息安全, 2015,(6):34-36.

[2]王元卓,賈巖濤,劉大偉,等.基于開放網絡知識的信息檢索與數據挖掘[J]. 計算機研究與發展, 2015, (2):456-474.

[3]朱郁筱,呂琳媛.推薦系統評價指標綜述[J]. 電子科技大學學報, 2012, (2):163-175.

[4]孟祥武,劉樹棟,張玉潔,等.社會化推薦系統研究[J]. 軟件學報, 2015, (6):1356-1372.

[5]丁少衡,姬東鴻,王路路. 基于用戶屬性和評分的協同過濾推薦算法[J].計算機工程與設計, 2015,(2):487-491.

[6]碩良勛,柴變芳,張新東. 基于改進最近鄰的協同過濾推薦算法[J].計算機工程與應用, 2015,(5):137-141.

[7]于洪,李俊華.一種解決新項目冷啟動問題的推薦算法[J].軟件學報, 2015,(6):1395-1408.

[8]盛偉,王保云,何苗,等. 基于評分相似性的群稀疏矩陣分解推薦算法[J]. 計算機應用, 2017,(5):1397-1401.

[9]王紅.改進Pearson相關系數的個性化推薦算法[J]. 山東農業大學學報(自然科學版), 2016,(6):940-944.

[10]滕少華,麥嘉俊,張巍,等.一種基于混合相似度的用戶多興趣推薦算法[J]. 江西師范大學學報(自然版),2016,(5):481-486.

[11]程廣東,秦一方.基于新浪微博API的話題分析系統[J].山東交通學院學報, 2015,(4):78-86.

[12]Silva M E V D,Nunes E. XSimilarity : Uma Ferramenta para Consultas por Similaridade embutidas na Linguagem XQuery[R]. 2008.