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

（遼寧大學信息學院，沈陽110036）

0 引言

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

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

為此，本文提出一種EBSN 上基于有向標簽圖及用戶反饋的活動推薦方法。因為EBSN 是一種異構的復雜社交網絡，因此本文利用活動發(fā)生的時間先后順序將平臺上的活動抽象為有向標簽圖，其中節(jié)點表示活動，有向邊則表示兩個活動發(fā)生的先后以及發(fā)生地之間的距離，活動的屬性（如活動類型，發(fā)生的時間、地點等）則通過節(jié)點標簽進行表示，兩個活動是否同一天進行等屬性則通過邊標簽表示。同時將EBSN 上的活動推薦轉換成子圖查詢問題進行研究。本文的主要內容如下：

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

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

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

1 相關工作

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

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

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

2 有向圖結構特征索引

2.1 EBSN與有向標簽圖轉換

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

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

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

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

表1 節(jié)點屬性標簽表Tab.1 Node property label table

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

2.2 DGSF索引

2.2.1 NPF索引

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

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

2.2.2 DEPF索引

DEPF 索引同樣包含兩級結構：頂層結構為邊標簽類型；底層結構則為每種邊標簽類型所包含的邊，由〈id1，id2〉構成。值得注意的是，因為本文研究的是有向圖，所以AB和BA不是同一種類型。仍以圖1 為例，圖G 包含AA、AB、AC、BA、BB、BC、CA、CB、CC 共9 種類型的邊，其DEPF 索引如圖3 所示，其中id1、id2表示邊的兩個端點編號。

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

2.2.3 TF索引

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

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

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

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

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

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

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

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

3.2 多屬性候選邊集過濾

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

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

4 具有用戶反饋的改進UCB 算法

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

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

算法1 EN_UCB。

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

5 實驗與結果分析

5.1 實驗環(huán)境及配置

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

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

表2 實驗參數配置Tab.2 Experimental parameter configuration

5.2 結果分析

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

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

圖6 顯示了各算法的運行時間對比情況，隨著活動數的增加，運行時間逐漸增加。其中：UCB 算法最耗時，這是因為它需要為每個活動計算置信區(qū)間；TS 算法則需要通過采樣獲得θ，同樣需要花費一定的時間；當活動數量較少時，eGreedy算法運行速度較快，這是因為當小于參數ε 時，活動隨機安排；本文構建有向標簽圖以及DGSF 索引的過程均在線下進行，因此不計入EN_UCB 算法的運行時間，EN_UCB 算法僅在過濾后的較小候選集上進行查詢，因此運行時間最短。

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

圖6 不同算法在不同數據集上的的運行時間對比Fig.6 Running time comparison of different algrithms on different datasets

6 結語

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

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