高良誠(chéng)

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，與現(xiàn)實(shí)社會(huì)相比，社交網(wǎng)絡(luò)以其時(shí)空方面的優(yōu)越性，在人們的工作和生活中發(fā)揮著越來越重要的作用。社交網(wǎng)絡(luò)用戶眾多，數(shù)據(jù)龐大，高效地讓用戶找到可能成為好友的其他用戶顯得十分重要，但用戶普遍對(duì)周邊信息缺乏有效過濾，在好友推薦方面存在信息投送不精準(zhǔn)和信息利用率低等問題，如何設(shè)計(jì)出高效的好友推薦算法已成為當(dāng)前重要研究課題[1-2]。

經(jīng)典的好友推薦算法主要有基于用戶屬性特征相似度和基于用戶間的拓?fù)浣Y(jié)構(gòu)兩種，但存在推薦結(jié)果不準(zhǔn)確或推薦范圍過窄等問題。鏈路預(yù)測(cè)算法在好友推薦算法中得到廣泛應(yīng)用[3-4]，其基本思想是將社交網(wǎng)絡(luò)中的用戶作為網(wǎng)絡(luò)中的節(jié)點(diǎn)，利用好友屬性，計(jì)算節(jié)點(diǎn)之間的相似度，據(jù)此形成新鏈路來進(jìn)行好友推薦，但在鏈路預(yù)測(cè)時(shí)，只考慮單一的網(wǎng)絡(luò)結(jié)構(gòu)，導(dǎo)致推薦準(zhǔn)確度不高。目前好友推薦算法普遍綜合多元化的用戶屬性，如用戶基本信息、社交關(guān)系、地理位置等，解決推薦精度低、信息過載等問題[5-9]。文獻(xiàn)[10]利用聚類算法對(duì)用戶進(jìn)行聚類，通過根節(jié)點(diǎn)到葉節(jié)點(diǎn)的加權(quán)求和進(jìn)行推薦，文獻(xiàn)[11]提出了一種基于圖聚類與蟻群算法的社交網(wǎng)絡(luò)聚類算法，有效地緩解稀疏性問題與冷啟動(dòng)問題，但均未充分考慮用戶位置信息。本文提出一種社交網(wǎng)絡(luò)中基于用戶屬性和改進(jìn)蟻群算法的好友推薦算法(Friend recommendation algorithm based on user attributes and ant colony optimization algorithm，UA-ACO)，綜合考慮用戶基本信息、社交關(guān)系、地理位置等用戶屬性和交互信息，計(jì)算用戶相似度，將其作為鏈路預(yù)測(cè)的依據(jù)，并通過改進(jìn)蟻群算法搜索好友用戶，增加好友推薦算法的精準(zhǔn)度。

1 系統(tǒng)模型及問題描述

本文設(shè)計(jì)了基于用戶屬性與用戶交互的相似性二維圖模型，綜合考慮用戶屬性和用戶交互，計(jì)算用戶間的相似度來進(jìn)行鏈路預(yù)測(cè)，建立用戶之間連接。系統(tǒng)模型用G=(V，E，W)表示，其中V(G)={v1,v2,…vn}表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，對(duì)應(yīng)為社交網(wǎng)絡(luò)的用戶；E(G)={e1,e2,…,en}表示網(wǎng)絡(luò)中邊的集合；W(G)={w1,w2,…,wn}，對(duì)應(yīng)邊的權(quán)值，對(duì)于任意一個(gè)邊e∈E(G)，對(duì)應(yīng)用戶相似性值。

根據(jù)用戶屬性和交互信息計(jì)算各個(gè)用戶與目標(biāo)用戶之間的相似性值，基于用戶屬性和交互信息的相似性計(jì)算公式為：

(1)

其中：Au,v為用戶u和v間的用戶屬性關(guān)系值，計(jì)算式為

(2)

其中：GF為用戶u和v共同好友數(shù)，PR為用戶u和v共同居住地?cái)?shù)，w1和w2為比例系數(shù)，Du,v為用戶u和v之間的距離，Davg為用戶間平均距離。根據(jù)用戶對(duì)評(píng)分項(xiàng)目的評(píng)論信息計(jì)算各個(gè)用戶與目標(biāo)用戶之間的相似性值，基于皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient, PCC)的相似性計(jì)算公式為：

simu,v=

(3)

2 基于Q學(xué)習(xí)和蟻群算法的好友推薦算法

2.1 Q-Learning算法

Q-Learning是一種強(qiáng)化學(xué)習(xí)算法[12]，通過與環(huán)境交互，構(gòu)建(狀態(tài)，行動(dòng))函數(shù)值，根據(jù)函數(shù)值選擇下一動(dòng)作。在狀態(tài)s下，賦予動(dòng)作a獎(jiǎng)勵(lì)和懲罰信息，進(jìn)而能夠選擇最優(yōu)動(dòng)作。用Q(s,a)表示動(dòng)作a獲得收益的期望，在時(shí)刻t根據(jù)狀態(tài)s選擇動(dòng)作a，并獲得報(bào)酬rt，Q值計(jì)算公式如下：

Qt+1(s,a)=(1-δ)Qt(s,a)+δ(rt+1+γmaxQ(st+1,a))

(4)

其中，δ為學(xué)習(xí)因子，δ∈(0，1)，γ為折扣因子，γ∈(0，1)。

通過公式(4)看出，Q-Learning算法的Q值可以作為蟻群算法中的信息素，從而加快蟻群算法初期的收斂速度。

2.2 改進(jìn)蟻群算法

蟻群算法模擬螞蟻群體覓食過程，在解決離散優(yōu)化問題方面，具有收斂速度快和求解精度高等特點(diǎn)[13]。其核心思想是在一個(gè)加權(quán)圖中，螞蟻釋放信息素，根據(jù)路徑轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)，并通過信息素更新驅(qū)動(dòng)螞蟻選擇最優(yōu)路徑，實(shí)現(xiàn)螞蟻間信息交換，最終在圖中找出最優(yōu)路徑。

2.2.1 路徑轉(zhuǎn)移概率

(5)

其中：μj為節(jié)點(diǎn)j的信息素濃度，初始值為Q學(xué)習(xí)算法的Q值；α為路徑上信息素影響因子；ηij為路徑選擇函數(shù)，ηij=simi,j；β為路徑選擇影響因子；Tabuk存放螞蟻k目前訪問過的節(jié)點(diǎn)。

2.2.2 信息素更新

當(dāng)螞蟻經(jīng)過某節(jié)點(diǎn)時(shí)，需要更新該節(jié)點(diǎn)上的信息素。節(jié)點(diǎn)上路過螞蟻數(shù)量越多，信息素濃度越大，該節(jié)點(diǎn)被選擇為下一節(jié)點(diǎn)的概率越大。

μj為節(jié)點(diǎn)j的信息素濃度，信息素更新規(guī)則如下：

(6)

其中，δ為信息素?fù)]發(fā)因子，γ為折扣因子，Δμj為信息素的增量，由式(7)計(jì)算。

(7)

(8)

其中：Q為Q-Learning算法生成的初始信息素，Cost(i,j)為螞蟻k從節(jié)點(diǎn)i到當(dāng)前節(jié)點(diǎn)j的費(fèi)用函數(shù)，由式(9)計(jì)算。

(9)

其中：tu為目標(biāo)用戶，hosps(tu,j)為圖中從目標(biāo)用戶節(jié)點(diǎn)到用戶j對(duì)應(yīng)節(jié)點(diǎn)的路徑長(zhǎng)度。

式(8)表明，螞蟻到節(jié)點(diǎn)j所經(jīng)過路徑費(fèi)用越小，則節(jié)點(diǎn)j的信息素增量越大，螞蟻選擇節(jié)點(diǎn)j的概率越大，因此，費(fèi)用低的路徑被選擇的概率變大。

每次迭代結(jié)束后，更新所有節(jié)點(diǎn)的信息素，公式如下：

μj′=(1-ρ)μj

(10)

其中：ρ為信息系揮發(fā)因子。

2.2.3 信息素?cái)U(kuò)散

2.3 UA-ACO算法實(shí)現(xiàn)步驟

初始階段，每個(gè)節(jié)點(diǎn)的信息素為Q-Learning算法的Q值，螞蟻隨機(jī)地分布在圖中節(jié)點(diǎn)上。螞蟻根據(jù)路徑轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)，并進(jìn)行信息素更新和擴(kuò)散。重復(fù)迭代，直到符合結(jié)束條件。將節(jié)點(diǎn)按信息素降序排列，選擇信息素高的節(jié)點(diǎn)。

算法步驟如下：

1.使用公式(1)計(jì)算用戶之間的相似性。

2.初始化并精簡(jiǎn)網(wǎng)絡(luò)。根據(jù)給定相似度閾值，刪除不滿足要求的用戶和獨(dú)立節(jié)點(diǎn)集。

3.將蟻群算法的初始信息素設(shè)置為Q-Learning算法迭代產(chǎn)生的Q值。

4.初始化蟻群算法的迭代次數(shù)NC。

5.將源節(jié)點(diǎn)放到螞蟻禁忌表tabu中，將k只螞蟻隨機(jī)放置到圖中節(jié)點(diǎn)上。

6.螞蟻根據(jù)公式(5)計(jì)算路徑轉(zhuǎn)移概率，選擇概率值大的鄰居節(jié)點(diǎn)作為下一節(jié)點(diǎn)。

7.按公式(6)對(duì)螞蟻選擇的節(jié)點(diǎn)進(jìn)行信息素更新，并將該節(jié)點(diǎn)放到禁忌表tabu中。

8.重復(fù)步驟6 和步驟7 直到路徑長(zhǎng)度超過5。

9.按照公式(10)全局更新信息素。

10.按2.2.3方法進(jìn)行信息素?cái)U(kuò)散。

11.重復(fù)步驟5～步驟10直到迭代次數(shù)超過NC，將節(jié)點(diǎn)信息素降序排列，選擇信息素濃度高的節(jié)點(diǎn)。

3 實(shí)驗(yàn)與結(jié)果分析

本文采用人人網(wǎng)作為數(shù)據(jù)來源，實(shí)驗(yàn)環(huán)境為PC機(jī)，PC機(jī)的配置為8GB內(nèi)存，i7 8550處理器，使用Matlab進(jìn)行仿真。設(shè)置參數(shù)w1=0.8，w2=0.9，δ=0.8，γ=1.1，α=1，β=1.2，θ=0.1，信息系揮發(fā)因子ρ=0.2，螞蟻數(shù)量150，迭代次數(shù)NC為100。

準(zhǔn)確率、召回率以及F1-measure 是好友推薦算法的重要指標(biāo)。準(zhǔn)確率是指推薦好友為真實(shí)好友數(shù)量與推薦好友數(shù)量的比例，召回率是推薦的真實(shí)好友數(shù)量與數(shù)據(jù)集中實(shí)際好友數(shù)量的比例，F(xiàn)1-measure是綜合衡量指標(biāo)。本文對(duì)UA-ACO算法、基于用戶的協(xié)同過濾算法(User-CF)[14]以及基于近鄰的協(xié)同過濾算法(NBCF)[15]，在準(zhǔn)確率、召回率以及 F1-measure指標(biāo)方面進(jìn)行比較與分析。

準(zhǔn)確率的計(jì)算公式如下：

(11)

召回率的計(jì)算公式如下：

(12)

F1-measure的計(jì)算公式如下：

(13)

圖1為不同算法的準(zhǔn)確率對(duì)比。由圖1可見，隨著推薦好友數(shù)的增加，幾種算法的準(zhǔn)確率均出現(xiàn)下降，但UA-ACO融合Q-Learning和改進(jìn)蟻群算法，加快了算法收斂速度，算法能更快地實(shí)現(xiàn)較高的準(zhǔn)確率，且準(zhǔn)確率下降幅度較小。

圖1 不同算法的準(zhǔn)確率對(duì)比

圖2為不同算法的召回率對(duì)比。由圖2可見，隨著推薦好友數(shù)的增加，幾種算法召回率均增大，UA-ACO采用改進(jìn)蟻群算法，把Q-Learning算法的Q值作為蟻群算法的初始信息素，算法收斂速度快，召回率增加更明顯。

圖2 不同算法的召回率對(duì)比

圖3為不同算法的F1-measure對(duì)比。由圖3可見，本文算法的F1-measure值指標(biāo)較好。

圖3 不同算法的F1-measure值對(duì)比

4 結(jié)語(yǔ)

文章提出了一種基于改進(jìn)蟻群算法的社交網(wǎng)絡(luò)好友推薦算法，綜合考慮用戶基本信息、社交關(guān)系、地理位置等用戶屬性，結(jié)合用戶交互關(guān)系，計(jì)算用戶間的相似度進(jìn)行鏈路預(yù)測(cè)，建立社交網(wǎng)絡(luò)二維圖，設(shè)定相似度閾值，去除不符合要求的用戶節(jié)點(diǎn)，減小好友推薦算法時(shí)間代價(jià)，在此基礎(chǔ)上，采用改進(jìn)蟻群算法，相似性值高的用戶被推薦的可能性增大。仿真實(shí)驗(yàn)表明，該算法準(zhǔn)確率和召回率性能較好。下一步將充分研究用戶對(duì)地理位置敏感的好友推薦需求。