事件社交網(wǎng)中基于有向標(biāo)簽圖及用戶反饋的活動推薦方法

單曉歡，張志國，宋寶燕，任成林

（遼寧大學(xué)信息學(xué)院，沈陽110036）

0 引言

近年來，信息技術(shù)及互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，推動了社交網(wǎng)絡(luò)的廣泛應(yīng)用，其中以Meetup［1］、Plancast［1］、Douban［2］和Google+Event［3］等為代表的基于事件的社交網(wǎng)絡(luò)（Event-Based Social Network，EBSN）［4］作為一種新型的社交網(wǎng)絡(luò)應(yīng)用得到了快速的發(fā)展。用戶可以在EBSN 平臺上注冊、創(chuàng)建、發(fā)布和組織社交活動，如籃球、音樂會、社團(tuán)活動、公益招募等，用戶可以根據(jù)自己的需求通過限制某些條件在線搜索并在線下參加其選擇的活動。

EBSN平臺會不定期地發(fā)布各種活動，同時(shí)也會將過期的活動下線。隨著社交網(wǎng)絡(luò)的不斷興起，EBSN上活躍用戶數(shù)以及活動數(shù)量日益增長。因此，用戶找到其感興趣的活動變得越來越困難，研究有效的EBSN 活動推薦方法以提高推薦質(zhì)量將面臨巨大的挑戰(zhàn)。

為此，本文提出一種EBSN 上基于有向標(biāo)簽圖及用戶反饋的活動推薦方法。因?yàn)镋BSN 是一種異構(gòu)的復(fù)雜社交網(wǎng)絡(luò)，因此本文利用活動發(fā)生的時(shí)間先后順序?qū)⑵脚_上的活動抽象為有向標(biāo)簽圖，其中節(jié)點(diǎn)表示活動，有向邊則表示兩個(gè)活動發(fā)生的先后以及發(fā)生地之間的距離，活動的屬性（如活動類型，發(fā)生的時(shí)間、地點(diǎn)等）則通過節(jié)點(diǎn)標(biāo)簽進(jìn)行表示，兩個(gè)活動是否同一天進(jìn)行等屬性則通過邊標(biāo)簽表示。同時(shí)將EBSN 上的活動推薦轉(zhuǎn)換成子圖查詢問題進(jìn)行研究。本文的主要內(nèi)容如下：

1）提出一種有向圖結(jié)構(gòu)特征（Directed Graph Structure Feature，DGSF）索引，該索引由節(jié)點(diǎn)屬性特征（Node Property Feature，NPF）索引、有向邊屬性特征（Directed Edge Property Feature，DEPF）索引以及時(shí)間特征（Time Feature，TF）索引構(gòu)成。利用NPF索引，根據(jù)時(shí)間、節(jié)點(diǎn)的入度及出度等信息過濾掉無效節(jié)點(diǎn)，以獲得較小的節(jié)點(diǎn)候選集；同理，利用DEPF 索引及TF索引，根據(jù)邊標(biāo)簽屬性以及活動發(fā)生的時(shí)間過濾掉無效邊，以獲得較小的邊候選集。

2）提出基于DGSF 索引的多屬性候選集過濾策略，利用時(shí)間、節(jié)點(diǎn)的入度、出度、標(biāo)簽類型以及相隔天數(shù)等特征的限制，實(shí)現(xiàn)對查詢圖候選集的進(jìn)一步剪枝，避免過多的冗余計(jì)算。

3）在獲得的候選集基礎(chǔ)上，提出一種帶有用戶反饋的改進(jìn)UCB（Upper Confidence Bound）活動推薦算法——EN_UCB（Elastic Net UCB），在UCB 算法中引入彈性網(wǎng)回歸，根據(jù)多影響因素計(jì)算用戶對活動的興趣值，并按興趣值從大到小向用戶進(jìn)行推薦，同時(shí)接收用戶的反饋，實(shí)現(xiàn)有效的在線活動推薦。

1 相關(guān)工作

隨著EBSN 中發(fā)布的活動越來越多，為用戶找到最符合其興趣的活動變得越來越困難［5］，同時(shí)EBNS中的活動推薦具有冷啟動、實(shí)時(shí)、容量限制及沖突限制等特性，這導(dǎo)致傳統(tǒng)的協(xié)同過濾、矩陣分解等推薦方法無法直接應(yīng)用于EBSN 的活動推薦。

文獻(xiàn)［6］在進(jìn)行活動推薦時(shí)，通過分析用戶的社會角色以及位置屬性，對現(xiàn)有的協(xié)同過濾算法進(jìn)行擴(kuò)展，定義了四種活動類別，提出一種基于社交及位置屬性的活動分類機(jī)制。一旦不同的類別被確定，利用適當(dāng)?shù)呐琶麨樾掠脩暨M(jìn)行推薦，解決了冷啟動問題。文獻(xiàn)［7］提出了一種EBSN 中基于上下文的推薦方法，該方法利用用戶的喜好和位置關(guān)系等多種信息進(jìn)行綜合評估，進(jìn)而推薦出最合適的活動。文獻(xiàn)［8］分析用戶對某個(gè)主題相關(guān)的活動感興趣，那么其有可能會參加該主題相關(guān)的后續(xù)活動，通過分析時(shí)間、空間等特征，對用戶進(jìn)行監(jiān)督學(xué)習(xí)，根據(jù)提取的特征進(jìn)行活動推薦。該算法明確了每個(gè)特征對參與活動的影響，算法相對簡單，但是它忽略了用戶間的社會屬性關(guān)系對活動推薦的影響。為解決活動推薦的冷啟動問題，一種貝葉斯泊松分解模型CBPF（Collective Bayesian Poisson Factorization）［9］被提出，其將貝葉斯泊松因式分解作為基本單元，用于建模用戶對活動、社會關(guān)系以及活動內(nèi)容的響應(yīng)；然后利用標(biāo)準(zhǔn)矩陣分解模型的思想進(jìn)一步連接這些基本單位。此外，該模型中活動內(nèi)容、組織者以及位置信息被用來表示預(yù)測用戶對冷啟動活動的響應(yīng)。SIARS（Social Infor?mation Augmented Recommender System）［10］充分利用活動組織者及群組成員的社會影響力，并結(jié)合基本的上下文信息進(jìn)行活動推薦。該系統(tǒng)結(jié)合EBSN 及其他社交網(wǎng)絡(luò)的信息描繪活動組織者的社會影響力，并考慮群組成員之間的互動以進(jìn)行活動推薦。此外，文獻(xiàn)［10］還提出了一種利用主題模型尋找活動所屬最相似主題的內(nèi)容感知推薦模型，該模型結(jié)合地點(diǎn)知名度及其分布的位置進(jìn)行活動推薦。該方法考慮了活動的組織者和群組成員的社會影響力對活動的影響，尋找與活動屬性相似的主題并結(jié)合地點(diǎn)分布進(jìn)行活動推薦，提高了活動推薦的準(zhǔn)確性；然而該模型未考慮活動沖突、活動容量等影響因素。

上述推薦方法雖然考慮了部分約束條件，但仍未達(dá)到全局最優(yōu)推薦，同時(shí)忽略了用戶是否接受推薦活動對后續(xù)推薦的影響。文獻(xiàn)［11］考慮了活動沖突、位置信息以及活動開銷等因素，提出了一種啟發(fā)式算法，考慮多種因素對活動推薦的影響，提高了活動安排的效率；然而該算法沒有考慮在線互動安排。文獻(xiàn)［12］提出了兩種利用剪枝技術(shù)的近似算法及精確算法解決不同活動之間存在沖突的問題，從而避免冗余安排，該算法實(shí)現(xiàn)了線上活動推薦。文獻(xiàn)［13］考慮了諸多限制因素，實(shí)現(xiàn)了線上活動推薦，同時(shí)為解決現(xiàn)有方法衡量事件屬性僅利用單個(gè)值和少量屬性的線性組合、權(quán)重采用預(yù)定義和固定值以及不考慮用戶是否接受推薦活動等問題，提出了一種新的在線活動推薦策略，引入MAB（Multi-Armed Bandit）問題［14］，分別利用TS（Thompson Sampling）算法、UCB 算法［15］以及eGreedy算法進(jìn)行活動推薦。

2 有向圖結(jié)構(gòu)特征索引

2.1 EBSN與有向標(biāo)簽圖轉(zhuǎn)換

本文將EBSN 抽象成有向標(biāo)簽圖G(V，E，LV，LE)，其中將EBSN 中活動抽象為圖中節(jié)點(diǎn)，V 表示節(jié)點(diǎn)集合；活動發(fā)生的先后順序則通過有向邊表示，E 則為邊集合；活動的屬性，如活動類型、舉辦時(shí)間、地點(diǎn)等抽象為節(jié)點(diǎn)標(biāo)簽，LV 則為節(jié)點(diǎn)標(biāo)簽屬性集合；兩個(gè)活動之間的距離以及舉辦時(shí)間利用邊標(biāo)簽表示，LE 為邊標(biāo)簽屬性集合。本文將滿足距離小于等于m（單位：m）的活動按舉辦時(shí)間的先后進(jìn)行連邊，先舉辦的活動指向在其之后舉辦的活動。

在EBSN 平臺中，不同的活動之間可能存在一定的沖突，如兩活動在同一時(shí)間舉辦或時(shí)間存在交叉等，為避免在后續(xù)查詢推薦過程中進(jìn)行沖突檢測等操作，本文將EBSN 抽象為有向標(biāo)簽圖的過程中已對沖突事件進(jìn)行過濾，有效提高了查詢效率。

下面以列舉的15 個(gè)活動為例，如表1 所示，將其抽象為15個(gè)節(jié)點(diǎn)，同時(shí)按活動類型分為足球A、電影B、音樂會C。其中如v3與v6因時(shí)間有交集，則認(rèn)為兩活動為沖突活動，無邊相連。轉(zhuǎn)換后的有向標(biāo)簽圖如圖1（a）所示。

圖1 有向標(biāo)簽圖及查詢圖示例Fig.1 Examples of directed label graph and query graph

表1 節(jié)點(diǎn)屬性標(biāo)簽表Tab.1 Node property label table

用戶在進(jìn)行活動搜索時(shí)，可以根據(jù)用戶的查詢限制條件，將活動搜索轉(zhuǎn)換為查詢圖表示，以實(shí)現(xiàn)將推薦活動轉(zhuǎn)換為子圖查詢。例如，用戶要系統(tǒng)為其推薦2019-03-17—2019-03-23期間的足球、音樂會和電影活動，同時(shí)足球和電影活動要相差一天。根據(jù)查詢需求可轉(zhuǎn)換為圖1（b）所示的6 種查詢圖表示，其中邊上的屬性b 表示活動不在同一天進(jìn)行，“1”則表示相差一天。

2.2 DGSF索引

2.2.1 NPF索引

本文有向標(biāo)簽圖中節(jié)點(diǎn)的類型、時(shí)間、出入度等屬性標(biāo)簽具有一定的標(biāo)志性和可辨別性，因此遍歷有向圖，獲取節(jié)點(diǎn)的屬性標(biāo)簽信息構(gòu)建NPF 索引。該索引由兩級結(jié)構(gòu)構(gòu)成：頂層結(jié)構(gòu)索引節(jié)點(diǎn)類型，由〈節(jié)點(diǎn)類型，所屬類型數(shù)量〉構(gòu)成；底層結(jié)構(gòu)則由〈節(jié)點(diǎn)編號，入度，日期，時(shí)間，出度，活動容納人數(shù)〉構(gòu)成，通過廣度優(yōu)先遍歷，統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)的上述信息。以圖1為例，有向標(biāo)簽圖G中包含了A、B、C三種類型的節(jié)點(diǎn)，其NPF索引如圖2 所示，其中：id 表示節(jié)點(diǎn)編號，ind 表示節(jié)點(diǎn)入度，date 表示活動舉辦日期，time 表示時(shí)間，og 表示節(jié)點(diǎn)出度，su則表示活動能容納的用戶數(shù)量。

圖2 NPF索引示意圖Fig.2 Schematic graph of NPF index

2.2.2 DEPF索引

DEPF 索引同樣包含兩級結(jié)構(gòu)：頂層結(jié)構(gòu)為邊標(biāo)簽類型；底層結(jié)構(gòu)則為每種邊標(biāo)簽類型所包含的邊，由〈id1，id2〉構(gòu)成。值得注意的是，因?yàn)楸疚难芯康氖怯邢驁D，所以AB和BA不是同一種類型。仍以圖1 為例，圖G 包含AA、AB、AC、BA、BB、BC、CA、CB、CC 共9 種類型的邊，其DEPF 索引如圖3 所示，其中id1、id2表示邊的兩個(gè)端點(diǎn)編號。

圖3 DEPF索引示意圖Fig.3 Schematic graph of DEPF index

2.2.3 TF索引

TF 索引的兩級結(jié)構(gòu)中：頂層結(jié)構(gòu)用于判斷活動是否為同一天舉辦，相同則為a，反之則為b；底層結(jié)構(gòu)由〈端點(diǎn)1，端點(diǎn)2，相距時(shí)間〉構(gòu)成。仍以圖1 為例，TF 索引如圖4 所示，其中id1、id2表示邊的兩個(gè)端點(diǎn)，ti 表示相距時(shí)間（單位：min），day表示相距天數(shù)。

圖4 TF索引示意圖Fig.4 Schematic graph of TF index

3 基于DGSF索引的多屬性候選集過濾

子圖查詢效率與索引及節(jié)點(diǎn)、邊的過濾程度密切相關(guān)，因此本文提出了基于DGSF 索引的多屬性候選集過濾策略，其中包括節(jié)點(diǎn)過濾及邊過濾。

3.1 多屬性候選節(jié)點(diǎn)集過濾

本文的多屬性候選節(jié)點(diǎn)集過濾將利用時(shí)間及度進(jìn)行兩次過濾，以得到最終的節(jié)點(diǎn)候選集。

在時(shí)間過濾中，根據(jù)用戶給出的日期限制（可以是具體日期也可以是日期范圍）以及活動類型，利用NPF索引將不滿足日期的節(jié)點(diǎn)進(jìn)行剪枝，以獲得初步候選集。

度過濾中，根據(jù)查詢節(jié)點(diǎn)類型及出入度，利用DNF 索引，保證候選集中各節(jié)點(diǎn)的出入度不小于查詢節(jié)點(diǎn)，以獲得最后節(jié)點(diǎn)候選集。

3.2 多屬性候選邊集過濾

利用多屬性候選節(jié)點(diǎn)集過濾策略可以有效剪枝不滿足條件的節(jié)點(diǎn)，獲得相對較少的節(jié)點(diǎn)候選集。本節(jié)在候選節(jié)點(diǎn)集的基礎(chǔ)上，利用DEPF索引和TF索引，提出了多屬性候選邊集過濾策略。

該策略首先在查詢圖中根據(jù)邊的類型檢索DEPF 索引，找到類型相同且兩端點(diǎn)在對應(yīng)節(jié)點(diǎn)候選集中的邊，獲得一步候選邊集；然后根據(jù)用戶對時(shí)間的限制，利用TF 索引過濾掉不滿足時(shí)間限制的邊，獲得二步候選集；最后將一、二步候選集中具有相同連接節(jié)點(diǎn)的邊進(jìn)行連接，得到查詢候選集。

4 具有用戶反饋的改進(jìn)UCB 算法

UCB 算法為解決MAB 問題提供了理論保證，它適用于解決不同的MAB 變形問題。UCB 解決MAB 問題的思路是利用置信區(qū)間，即不確定程度，置信區(qū)間越寬，則越不確定，反之亦然。每個(gè)臂的興趣均值都有個(gè)置信區(qū)間，隨著實(shí)驗(yàn)次數(shù)的增加置信區(qū)間會變窄，每次選擇前，都根據(jù)已有實(shí)驗(yàn)的結(jié)果重新估計(jì)每個(gè)臂的均值和置信區(qū)間，選擇置信區(qū)間上最大的那個(gè)臂。

由于一個(gè)活動有多個(gè)特征屬性，但無法準(zhǔn)確判斷哪個(gè)特征屬性影響大，為此本文提出一種帶有用戶反饋的改進(jìn)UCB算法，即EN_UCB 算法。該算法在UCB 算法中引入了彈性網(wǎng)回歸，彈性網(wǎng)回歸既能實(shí)現(xiàn)嶺回歸對重要特征選擇的目的，又能像Lasson 回歸那樣，刪除對因變量影響較小的特征。具體算法如算法1所示。

算法1 EN_UCB。

在算法1中，輸入?yún)?shù)中：λ1表示初始化單位矩陣系數(shù)；α表示EN_UCB 算法對活動推薦探索系數(shù)；Vsum表示利用DGSF索引得到的活動候選集，Vsin則是候選集的一個(gè)子集，其活動數(shù)由用戶選擇接納活動的數(shù)量決定；v表示某一活動。輸出參數(shù)At則是最終推薦的活動結(jié)果集。該算法利用一個(gè)d×d 的矩陣Y 存儲每個(gè)活動通過反饋不斷修正的屬性值變化，利用一個(gè)d×1 的向量b 存儲活動獲得的獎勵變化，該處獎勵為用戶反饋接受推薦活動與否對活動的影響，用一個(gè)隨機(jī)變量的期望進(jìn)行表示，即。算法中基于彈性網(wǎng)回歸更新Y 和b，如第5）行所示，并利用更新后的Y 和b 來計(jì)算權(quán)向量。利用先驗(yàn)知識，計(jì)算每個(gè)活動的獎勵值，如第8）行所示。計(jì)算候選子集的獎勵值，如第10）行所示，同時(shí)每次更新，并按其進(jìn)行排序，將排序靠前的活動推薦給用戶，如第11）行所示。用戶可以選擇接受或是拒絕，用戶的反饋結(jié)果將影響后續(xù)的推薦。

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

5.1 實(shí)驗(yàn)環(huán)境及配置

本文實(shí)驗(yàn)環(huán)境為Intel Core i7-8550U CPU@1.80 GHz 2.00 GHz處理器，16 GB 內(nèi)存，256 GB SSD+1 TB 硬盤，編程語言為Java。

實(shí)驗(yàn)分別在真實(shí)數(shù)據(jù)集和仿真數(shù)據(jù)集上完成。真實(shí)數(shù)據(jù)集來自Meetup 社交網(wǎng)站中美國舊金山附近用戶及其相關(guān)活動的數(shù)據(jù)，時(shí)間范圍是2016-08-31—2018-06-31。其中用戶數(shù)據(jù)包含了用戶的位置、偏好等信息，活動數(shù)據(jù)包括活動的屬性、舉辦日期、時(shí)間、舉辦人、地點(diǎn)等信息。在仿真數(shù)據(jù)集中，產(chǎn)生的?符合正態(tài)分布，特征向量符合正態(tài)分布和均勻分布，生成一個(gè)具有16維的特征。實(shí)驗(yàn)具體參數(shù)配置如表2所示。

表2 實(shí)驗(yàn)參數(shù)配置Tab.2 Experimental parameter configuration

5.2 結(jié)果分析

本節(jié)將從接受率、遺憾率［12］以及查詢時(shí)間等方面進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文方法的有效性和可行性。

如圖5所示，k=103，隨著用戶數(shù)量的增加，接受率在逐漸上升而遺憾率逐漸降低，這是因?yàn)樗惴ǖ墓烙?jì)θ經(jīng)過若干次修正后變得更加精準(zhǔn)。TS 算法性能最差，其接受率較低而遺憾率很高，這是因?yàn)樵诰哂刑卣鞯腗AB的情況下，所有活動通過共享θ相關(guān)聯(lián)，TS不能通過前期推薦的活動而預(yù)估其對后續(xù)活動的影響。eGreedy算法雖然會在每次推薦后，改善其后續(xù)推薦，但由于小于參數(shù)ε時(shí)，活動是隨機(jī)安排的，這導(dǎo)致用戶的接受率和遺憾率會相對低于UCB。本文EN_UCB 算法引入彈性網(wǎng)回歸對特征進(jìn)行篩選，提高了推薦的準(zhǔn)確性，因此用戶接受率更高。在仿真數(shù)據(jù)集及真實(shí)數(shù)據(jù)集中，接受率及遺憾率出現(xiàn)突然下降的情況，這是受活動容量限制的影響；同時(shí)接受率與遺憾率出現(xiàn)上升或下降的波動則是受用戶反饋的影響。

圖6 顯示了各算法的運(yùn)行時(shí)間對比情況，隨著活動數(shù)的增加，運(yùn)行時(shí)間逐漸增加。其中：UCB 算法最耗時(shí)，這是因?yàn)樗枰獮槊總€(gè)活動計(jì)算置信區(qū)間；TS 算法則需要通過采樣獲得θ，同樣需要花費(fèi)一定的時(shí)間；當(dāng)活動數(shù)量較少時(shí)，eGreedy算法運(yùn)行速度較快，這是因?yàn)楫?dāng)小于參數(shù)ε 時(shí)，活動隨機(jī)安排；本文構(gòu)建有向標(biāo)簽圖以及DGSF 索引的過程均在線下進(jìn)行，因此不計(jì)入EN_UCB 算法的運(yùn)行時(shí)間，EN_UCB 算法僅在過濾后的較小候選集上進(jìn)行查詢，因此運(yùn)行時(shí)間最短。

圖5 不同數(shù)據(jù)集上接受率及遺憾率對比Fig.5 Comparison of accept and regret rates on different datasets

圖6 不同算法在不同數(shù)據(jù)集上的的運(yùn)行時(shí)間對比Fig.6 Running time comparison of different algrithms on different datasets

6 結(jié)語

本文針對EBSN 上的活動推薦問題展開研究，首先將EBSN轉(zhuǎn)換為有向標(biāo)簽圖，并在轉(zhuǎn)換過程中對沖突活動進(jìn)行過濾；其次，提取節(jié)點(diǎn)及邊的屬性特征信息，構(gòu)建DGSF 索引；然后，提出基于DGSF 索引的多屬性候選集過濾策略，利用時(shí)間等特征限制進(jìn)行剪枝過濾，以獲得查詢候選集；提出一種具有用戶反饋的改進(jìn)UCB 活動推薦算法，引入彈性網(wǎng)回歸以提高推薦準(zhǔn)確性，同時(shí)接收用戶反饋，以優(yōu)化后續(xù)活動推薦。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能快速準(zhǔn)確地為用戶推薦活動，具有一定的實(shí)際應(yīng)用價(jià)值。

然而，在本文的研究中未考慮EBSN 中活動動態(tài)變化的情況，因此在未來工作中將對動態(tài)變化下的索引維護(hù)問題進(jìn)行研究，使得本文方法更加完善。