喬 治，周 川，紀(jì)現(xiàn)才，曹亞男，郭 莉

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 北京100190； 2. 中國(guó)科學(xué)院大學(xué) 北京100049; 3. 中國(guó)科學(xué)院 信息工程研究所 北京100093)

基于地域特征和異構(gòu)社交關(guān)系的事件推薦算法研究

喬 治1,2，周 川2，3，紀(jì)現(xiàn)才3，曹亞男3，郭 莉3

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 北京100190； 2. 中國(guó)科學(xué)院大學(xué) 北京100049; 3. 中國(guó)科學(xué)院 信息工程研究所 北京100093)

近幾年，在基于事件的社交網(wǎng)絡(luò)(EBSNs)服務(wù)中，為便于增強(qiáng)用戶(hù)體驗(yàn)，事件推薦任務(wù)一直被廣泛研究。本文基于對(duì)EBSN中用戶(hù)行為數(shù)據(jù)的詳細(xì)分析，提出了一種新型的融合多種數(shù)據(jù)特征的潛在因子模型。該模型綜合考慮EBSN中兩種新型的數(shù)據(jù)特征： 異構(gòu)的社交關(guān)系特征(線(xiàn)上社交關(guān)系+線(xiàn)下社交關(guān)系)和用戶(hù)參與行為的地域性特征?；谡鎸?shí)的Meetup數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果表明我們的算法在解決事件推薦問(wèn)題時(shí)比傳統(tǒng)的算法有更好的性能。

事件推薦；基于事件的社交網(wǎng)絡(luò)；用戶(hù)行為傾向；協(xié)從過(guò)濾；地域特征；異構(gòu)社交關(guān)系

1 引言

近年來(lái)，基于事件的社交網(wǎng)絡(luò)(EBSN)快速發(fā)展，積累了大量的用戶(hù)群體并深受廣大用戶(hù)的喜歡。這種新型社交網(wǎng)絡(luò)服務(wù)的主要應(yīng)用包括國(guó)內(nèi)的豆瓣同城以及美國(guó)的Meetup等網(wǎng)站。這種服務(wù)主要給用戶(hù)提供一種組織、參與、評(píng)論和分享線(xiàn)下事件(如酒會(huì)、沙龍、演唱會(huì)等)的平臺(tái)。面向該應(yīng)用場(chǎng)景的事件推薦任務(wù),獲得國(guó)內(nèi)外研究者的廣泛研究和探索。事件推薦任務(wù)旨在為用戶(hù)推薦最相關(guān)、最感興趣以及用戶(hù)最有可能參與的事件。從網(wǎng)絡(luò)服務(wù)的宏觀(guān)角度看，該任務(wù)無(wú)論對(duì)于線(xiàn)下事件的組織者還是事件的參與者都提供便利。對(duì)于事件的組織者，線(xiàn)下活動(dòng)可以被自動(dòng)地推送給合適的用戶(hù)群從而吸引更多感興趣的用戶(hù)參與；對(duì)于事件的參與者，推薦任務(wù)可以過(guò)濾不相關(guān)事件，使得用戶(hù)可以從海量的信息中快速發(fā)現(xiàn)自己可能喜歡的事件。

區(qū)別于已有的推薦問(wèn)題[1-4]，在EBSN中的事件推薦任務(wù)面臨以下數(shù)據(jù)特征所帶來(lái)的挑戰(zhàn)。

? 地域特征。根據(jù)數(shù)據(jù)分析，我們發(fā)現(xiàn)用戶(hù)在選擇參與線(xiàn)下事件時(shí)，存在區(qū)域傾向性。即用戶(hù)除了對(duì)事件內(nèi)容有個(gè)體性興趣傾向外，用戶(hù)對(duì)于事件舉辦地點(diǎn)的喜好也會(huì)影響用戶(hù)對(duì)于某一事件的參與行為。

? 異構(gòu)社交關(guān)系特征。在基于事件的社交網(wǎng)絡(luò)中存在兩種社交關(guān)系。一種是線(xiàn)上社交關(guān)系，即傳統(tǒng)社交網(wǎng)絡(luò)應(yīng)用中關(guān)聯(lián)用戶(hù)的社交關(guān)系。用戶(hù)通過(guò)EBSN中的線(xiàn)上社交網(wǎng)絡(luò)可以互相溝通、分享感興趣的事件以及體驗(yàn)。第二種社交關(guān)系是線(xiàn)下社交關(guān)系。在數(shù)據(jù)挖掘頂級(jí)會(huì)議KDD-12[5]上，IBM研究院的研究人員在分析基于事件的社交網(wǎng)絡(luò)數(shù)據(jù)時(shí)提出并定義了這種新型的社交關(guān)系。這種關(guān)系的紐帶是線(xiàn)下事件。當(dāng)用戶(hù)參與了同一線(xiàn)下事件時(shí)，他們勢(shì)必會(huì)有面對(duì)面的交流與互動(dòng)，這種線(xiàn)下的關(guān)聯(lián)是對(duì)虛擬社交關(guān)聯(lián)的補(bǔ)充，被定義為線(xiàn)下社交關(guān)系。在EBSN中，同時(shí)存在著兩種異構(gòu)的社交關(guān)聯(lián)。

EBSN數(shù)據(jù)的上述兩種特征給我們的問(wèn)題分析和建模帶來(lái)了新的挑戰(zhàn)。為設(shè)計(jì)有效的推薦算法，我們需要聯(lián)合考慮上述兩種數(shù)據(jù)特征。在本文中，我們提出了一種新型的潛在因子模型(簡(jiǎn)寫(xiě)為HeSi)，該模型綜合考慮了異構(gòu)社交信息與區(qū)域傾向性，有效地解決了事件推薦問(wèn)題。實(shí)驗(yàn)表明，我們所設(shè)計(jì)的HeSi算法在解決事件推薦問(wèn)題時(shí)比傳統(tǒng)的算法在精度上提高了近5%。

2 基于事件的社交網(wǎng)絡(luò)數(shù)據(jù)分析

在本文中，我們選擇Meetup數(shù)據(jù)集作為重點(diǎn)分析對(duì)象。Meetup網(wǎng)站是世界知名的EBSN應(yīng)用，該數(shù)據(jù)集主要取自Meetup網(wǎng)站的用戶(hù)對(duì)線(xiàn)下活動(dòng)的參與行為的數(shù)據(jù)。IBM研究人員在采集和清洗后開(kāi)源了該數(shù)據(jù)集供研究者使用，并在KDD-12[5]中針對(duì)以Meetup網(wǎng)站為代表的一類(lèi)EBSN應(yīng)用做了詳細(xì)的數(shù)據(jù)分析工作。該論文的研究成果表明線(xiàn)下事件與參與者多在同一個(gè)地理區(qū)域。因此，我們從該數(shù)據(jù)集中選取五個(gè)有代表性的城市進(jìn)行數(shù)據(jù)分析，(包括紐約、洛杉磯、休斯頓、芝加哥和舊金山)。首先，統(tǒng)計(jì)這些城市中的用戶(hù)和事件數(shù)量，如表1所示；然后，分析數(shù)據(jù)集的地域特性和異構(gòu)社交關(guān)系特性。數(shù)據(jù)分析結(jié)果將在下文進(jìn)行詳細(xì)介紹。

表1 數(shù)據(jù)集信息統(tǒng)計(jì)[6]

2.1 地域特性

在文獻(xiàn)[6]中，作者清洗并獲得了北美五座城市的事件數(shù)據(jù)(表1)，并對(duì)基于事件的社交網(wǎng)絡(luò)數(shù)據(jù)的地域特征做了詳細(xì)的分析，圖1展示了休斯頓 數(shù)據(jù)的聚類(lèi)結(jié)果。直觀(guān)上來(lái)看，每個(gè)類(lèi)簇內(nèi)的大多數(shù)事件呈中央集中型分布，同一顏色的點(diǎn)越密集表示該區(qū)域內(nèi)發(fā)生的事件越多。采用均值法求出每個(gè)類(lèi)簇的中心點(diǎn)坐標(biāo)，發(fā)現(xiàn)中心點(diǎn)所在區(qū)域大多位于休斯頓當(dāng)?shù)氐牟叫薪?、?gòu)物中心等繁華場(chǎng)所。因此，本文提出假設(shè)，社交事件一般發(fā)生在繁華區(qū)域并以這些區(qū)域?yàn)橹行某始行头植肌?/p>

圖1 基于事件地理坐標(biāo)的休斯頓數(shù)據(jù)的聚類(lèi)分析注： 置類(lèi)簇?cái)?shù)目為20，將不同類(lèi)簇的事件用不同顏色進(jìn)行標(biāo)記；每一個(gè)點(diǎn)表示在該城市內(nèi)組織的一個(gè)事件，橫縱坐標(biāo)分別表示緯度和經(jīng)度，相同顏色的點(diǎn)表示從屬同一個(gè)聚類(lèi)[6]

區(qū)域傾向性 線(xiàn)下事件區(qū)域呈集中性特點(diǎn)的基礎(chǔ)上，在文獻(xiàn)[6]中，作者又進(jìn)一步分析數(shù)據(jù)發(fā)現(xiàn)了區(qū)域傾向性。假設(shè)將每一個(gè)類(lèi)簇看作一個(gè)區(qū)域，那么每個(gè)城市均被劃分為20個(gè)區(qū)域，以用戶(hù)為關(guān)注點(diǎn)，我們分別統(tǒng)計(jì)每個(gè)城市中用戶(hù)參與事件的行為數(shù)據(jù)。分析結(jié)果表明： (1)超過(guò)80%以上的用戶(hù)僅訪(fǎng)問(wèn)了不到六個(gè)區(qū)域，如圖2所示； (2)大多數(shù)用戶(hù)對(duì)每個(gè)訪(fǎng)問(wèn)區(qū)域的平均訪(fǎng)問(wèn)次數(shù)超過(guò)一次，如圖3所示。可見(jiàn)，用戶(hù)對(duì)不同區(qū)域事件的參與并不是隨機(jī)的，而是帶有明顯的個(gè)體傾向性，即較頻繁地訪(fǎng)問(wèn)自己感興趣的區(qū)域。

圖2 用戶(hù)訪(fǎng)問(wèn)區(qū)域數(shù)的累計(jì)概率[6]

圖3 用戶(hù)平均訪(fǎng)問(wèn)次數(shù)在1和>1兩種情況下的概率分布[6]

2.2 異構(gòu)社交關(guān)系

針對(duì)本文的事件推薦任務(wù)，我們首先定義三種實(shí)體集合，包括用戶(hù)U、事件V和事件位置VL，以及兩種異構(gòu)的社交網(wǎng)絡(luò)： 線(xiàn)上社交網(wǎng)絡(luò)Gon和線(xiàn)下社交網(wǎng)絡(luò)Goff。其中U={u1,u2,…,un}表示用戶(hù)集合，V={v1,v2,…,vm}表示事件集合，對(duì)于每一個(gè)事件vi都具有描述該事件的位置信息。線(xiàn)上社交網(wǎng)絡(luò)Gon描述所有用戶(hù)的線(xiàn)上社交關(guān)系，線(xiàn)下社交網(wǎng)絡(luò)Goff描述所有用戶(hù)的線(xiàn)下社交關(guān)系。

(1)

其中，G(ui)表示任意用戶(hù)ui參與的線(xiàn)上社交組的集合；|G(ui)∩G(uj)|表示用戶(hù)ui和uj參與的相同社交組的數(shù)量；分母|G(ui)∪G(uj)|表示用戶(hù)ui和uj各自參與的社交組的并集的基數(shù)。

(2)

其中，E(ui)表示用戶(hù)ui參與的線(xiàn)下事件的集合；|E(ui)∩E(uj)|表示用戶(hù)ui和uj參與的相同線(xiàn)下事件的數(shù)量；分母|E(ui)∪E(uj)|表示用戶(hù)ui和uj各自參與的事件并集的基數(shù)。

圖4 EBSN中的異構(gòu)社交關(guān)系

2.3 問(wèn)題定義

事件推薦任務(wù)旨在為用戶(hù)推薦其可能感興趣的事件。本文將推薦問(wèn)題轉(zhuǎn)變?yōu)榕判騿?wèn)題，即根據(jù)用戶(hù)對(duì)于各個(gè)事件的感興趣程度對(duì)事件排序，將排名靠前的事件推薦給用戶(hù)。因此，事件推薦的核心任務(wù)即如何估計(jì)用戶(hù)對(duì)事件的感興趣程度。我們定義評(píng)分r(ui,vj)度量用戶(hù)ui對(duì)事件vj的感興趣程度?；诒竟?jié)數(shù)據(jù)分析結(jié)果，我們提出了一種基于矩陣因子分解技術(shù)的混合評(píng)分模型，將區(qū)域傾向性特征和異構(gòu)社交關(guān)系特征引入興趣評(píng)估模型。矩陣因子分解模型是一種簡(jiǎn)單、實(shí)用、高效的方法，可以靈活內(nèi)嵌異構(gòu)屬性，目前已被廣泛應(yīng)用。我們希望通過(guò)引入兩種新的特征來(lái)提高事件推薦的性能。

3 相關(guān)工作

近年來(lái)，推薦問(wèn)題已經(jīng)受到了國(guó)內(nèi)外研究者的廣泛關(guān)注。推薦算法可大致分為基于上下文的推薦和協(xié)從過(guò)濾兩大類(lèi)。其中矩陣因子分解模型被廣泛地應(yīng)用到推薦系統(tǒng)應(yīng)用中并獲得了較好的性能。在矩陣因子分解模型中，通過(guò)計(jì)算模型預(yù)測(cè)值與實(shí)際值的差值來(lái)度量估計(jì)誤差，如下式所示。

(3)

其中第一項(xiàng)為最小二乘的誤差評(píng)估函數(shù)，r(ui,vj)是模型預(yù)測(cè)值，Rij是實(shí)際評(píng)分值，Iij是指示變量，用來(lái)描述用戶(hù)ui是否參與了對(duì)事件vj的評(píng)分；為防止過(guò)擬合，我們引入了兩項(xiàng)正則化項(xiàng)‖Ui‖2和‖Vj‖2，它們分別是變量Ui和Vj的二范式。

目前，隨著各種新型網(wǎng)絡(luò)應(yīng)用的出現(xiàn)和發(fā)展，為了應(yīng)對(duì)新型網(wǎng)絡(luò)特征帶來(lái)的挑戰(zhàn)，推薦算法得到了進(jìn)一步的增強(qiáng)和改進(jìn)[6-12]。這些研究工作將多種新特征引入到推薦算法中從而提高推薦精度，包括社交關(guān)聯(lián)、地理信息等。

引入社交關(guān)聯(lián)的推薦算法主要包括基于社交關(guān)系的協(xié)從過(guò)濾和通過(guò)社交正則對(duì)評(píng)分行為做糾正的方法[13-16]。Fengkun Liu等[14]將社交關(guān)系應(yīng)用于用戶(hù)間相似度的計(jì)算，提出了一種新型的協(xié)從過(guò)濾算法。該算法與傳統(tǒng)的基于行為相似度的協(xié)從過(guò)濾算法相比可以獲得精度的提升；然而當(dāng)評(píng)分?jǐn)?shù)據(jù)較稀疏時(shí)，算法性能并沒(méi)有明顯的優(yōu)勢(shì)。Irwin King等[15]將用戶(hù)看作節(jié)點(diǎn)，將社交關(guān)系看作節(jié)點(diǎn)間的關(guān)聯(lián)提出了一種基于連續(xù)條件隨機(jī)場(chǎng)的社交推薦框架，以高昂的時(shí)間開(kāi)銷(xiāo)換取了較高的精度。Hao Ma等[16]提出了一種社交正則的協(xié)從推薦方法，巧妙地將社交關(guān)系引入矩陣因子分解模型從而有效提高了算法精度。因此，在本文中，我們也采用社交正則的方法，將異構(gòu)社交關(guān)系引入誤差函數(shù)，對(duì)模型參數(shù)作糾正。

考慮地理信息的推薦算法主要包括基于距離的協(xié)從推薦和面向位置信息的用戶(hù)行為傾向建模[17-23]。移動(dòng)互聯(lián)網(wǎng)的興起使人們意識(shí)到位置信息對(duì)于用戶(hù)行為估計(jì)的影響，因此協(xié)從地理位置信息的推薦算法研究得到了廣泛的關(guān)注。其中,大多數(shù)研究工作僅依據(jù)位置信息進(jìn)行推薦，例如S Chaudhuri等[24]采用KNN方法為用戶(hù)推薦最近的其他用戶(hù)信息。然而，在事件推薦問(wèn)題中，推薦的核心在于事件位置信息只是輔助問(wèn)題研究的特征之一。另外，有一類(lèi)研究工作探索位置信息對(duì)于推薦性能的影響，例如N Bruno等[25]提出了Top-K的改進(jìn)算法為用戶(hù)推薦距離較近的商品；Peng Zhang等[27]使用用戶(hù)的地理位置信息對(duì)用戶(hù)分組，探索不同用戶(hù)組對(duì)于商品類(lèi)別的傾向性，提出了新型的評(píng)分算法。然而基于位置的用戶(hù)分組并不適用于基于事件的社交網(wǎng)絡(luò)中的事件推薦任務(wù)，相比之下基于位置的事件分組所呈現(xiàn)的用戶(hù)行為具有更明顯的區(qū)域傾向的特征。

我們基于事件推薦問(wèn)題特有的數(shù)據(jù)特點(diǎn)，嘗試聯(lián)合建模地域特性和社交關(guān)系兩種特征提高推薦算法的性能。

4 聯(lián)合建模地域特性和社交關(guān)系的事件推薦框架

4.1 混合評(píng)分

為了便于聯(lián)合建模用戶(hù)個(gè)體興趣與區(qū)域傾向，我們使用文獻(xiàn)[6]中的混合評(píng)分模型，它由個(gè)體興趣評(píng)分和區(qū)域傾向評(píng)分兩部分加權(quán)生成。

(4)

個(gè)體興趣評(píng)分 類(lèi)似于基于矩陣分解的潛在因子模型，假設(shè)因子向量的維度為l，定義每一個(gè)用戶(hù)ui有一個(gè)潛在的維因子向量Ui∈Rl，每一個(gè)事件vj也有一個(gè)潛在的l維因子向量Vj∈Rl。我們將因子空間看作興趣空間，使用因子向量描述用戶(hù)或事件在因子空間的投影，那么用戶(hù)的個(gè)體特性決定了其在因子空間的興趣分布，線(xiàn)下事件在因子空間的投影反應(yīng)了事件的興趣分布。因此，可以使用向量?jī)?nèi)積來(lái)計(jì)算用戶(hù)對(duì)于事件的個(gè)體興趣評(píng)分，如下所示：

(5)

區(qū)域傾向評(píng)分 由于用戶(hù)對(duì)事件所處地理位置的喜好也會(huì)影響用戶(hù)參與該事件的行為傾向，因此我們我們需要對(duì)用戶(hù)的區(qū)域傾向性進(jìn)行評(píng)價(jià)。通過(guò)2.1節(jié)的數(shù)據(jù)分析，我們發(fā)現(xiàn)事件呈區(qū)域集中式分布，即是圖中同種顏色的類(lèi)簇由中心向外的發(fā)散特點(diǎn)。分析類(lèi)簇中心點(diǎn)所在的具體位置，發(fā)現(xiàn)類(lèi)簇多集中在城市內(nèi)的商業(yè)街或金融街一類(lèi)繁華的地段。因此，可以將事件聚類(lèi)結(jié)果看作對(duì)相應(yīng)城市的區(qū)域劃分。我們可以使用聚類(lèi)的方法獲得事件的近似區(qū)域。我們使用文獻(xiàn)[6]中區(qū)域傾向評(píng)分的建模方式去建模此處的區(qū)域傾向評(píng)分。與個(gè)體興趣評(píng)分類(lèi)似，我們?yōu)槊恳粋€(gè)用戶(hù)ui定義區(qū)域相關(guān)的因子向量Πi，為每個(gè)區(qū)域定義區(qū)域相關(guān)的因子向量Mk。用向量Πi和Mk的內(nèi)積表示用戶(hù)ui對(duì)第k個(gè)區(qū)域的傾向評(píng)分。由于事件類(lèi)簇只是對(duì)實(shí)際區(qū)域的近似，因此我們引入從屬因子Cjk來(lái)表示第j個(gè)事件屬于第k個(gè)區(qū)域的概率。最終，用戶(hù)對(duì)區(qū)域的傾向性評(píng)分是通過(guò)對(duì)事件所處各個(gè)區(qū)域的評(píng)分加權(quán)求得的，賦予權(quán)值的依據(jù)是事件對(duì)區(qū)域的從屬概率。

(6)

為了求解Cjk，我們首先假設(shè)每一個(gè)區(qū)域內(nèi)的事件呈高斯分布，定義參數(shù)(μ,∑)描述區(qū)域特征，其中μ表示均值向量，∑表示協(xié)方差矩陣。因此，可以通過(guò)式(7)對(duì)Cjk進(jìn)行求解。

(7)

其中，N(Li|μk,Σk)表示用戶(hù)ui的位置Li出現(xiàn)在區(qū)域k的概率密度。

4.2HeSi模型

鑒于矩陣因子分解模型在精度和效率等方面的優(yōu)越性，我們將上一節(jié)中的混合評(píng)分函數(shù)嵌入矩陣因子分解模型中，誤差評(píng)估函數(shù)中的模型預(yù)測(cè)值采用式(4)，并為參數(shù)Π和M增加二范式正則項(xiàng)以便約束參數(shù)的取值范圍。從而獲得以下目標(biāo)函數(shù)。

(8)

(9)

HeSi目標(biāo)優(yōu)化函數(shù) 將異構(gòu)社交正則[見(jiàn)公式(8)]應(yīng)用到基于混合評(píng)分的矩陣因子分解模型[見(jiàn)公式(9)]中， 獲得最終的目標(biāo)優(yōu)化函數(shù)，如式(10)所示。

(10)

4.3 參數(shù)學(xué)習(xí)

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

本節(jié)主要通過(guò)使用真實(shí)網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)集來(lái)驗(yàn)證事件推薦算法的性能。在本節(jié)中，首先介紹實(shí)驗(yàn)數(shù)據(jù)集和評(píng)價(jià)指標(biāo)，然后介紹對(duì)比方法，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行討論。

5.1 數(shù)據(jù)集

我們主要采用Meetup數(shù)據(jù)集作為我們的實(shí)驗(yàn)數(shù)據(jù)集。如文章第三部分所示，我們首先抽取出美國(guó)五座代表型城市的相關(guān)數(shù)據(jù)構(gòu)造五個(gè)實(shí)驗(yàn)數(shù)據(jù)集合，每座城市的數(shù)據(jù)集合包括該城市內(nèi)注冊(cè)的用戶(hù)、注冊(cè)的事件以及發(fā)生的參與行為。數(shù)據(jù)的詳細(xì)信息已在表1中詳細(xì)闡述。

5.2 評(píng)價(jià)指標(biāo)

為了便于評(píng)價(jià)事件推薦算法的性能，我們采用三種標(biāo)準(zhǔn)的評(píng)價(jià)方法AUC、P@k以及MAP。

1) AUC評(píng)價(jià)方法可以用來(lái)度量整體的分類(lèi)結(jié)果。在本實(shí)驗(yàn)數(shù)據(jù)集中未評(píng)分事件占較大比例，AUC評(píng)價(jià)方法恰適合于不平衡數(shù)據(jù)。具體計(jì)算過(guò)程如式(9)所示。

(19)

2) P@k指Top-k個(gè)估計(jì)值中正確估值的比例，多用于排序問(wèn)題。在事件推薦任務(wù)，把評(píng)分較高的事件推薦給用戶(hù)，也可看作為排序問(wèn)題。

3) MAP是P@k的均值，指算法在選擇不同Top-k時(shí)的精度的均值，可根據(jù)式(20)計(jì)算。

(20)

其中L(u)描述采用模型估計(jì)出的用戶(hù)u對(duì)各個(gè)事件評(píng)分的降序排列，Lk(u)描述這個(gè)排序中興趣度第k大的事件，函數(shù)I是指示函數(shù)。

算法1：HeSi模型學(xué)習(xí)輸入：評(píng)分?jǐn)?shù)據(jù)R、線(xiàn)上社交關(guān)系Won、線(xiàn)下社交關(guān)系Woff、地理位置信息、參數(shù)Θ、區(qū)域數(shù)K輸出：用戶(hù)興趣因子U、事件興趣因子V、用戶(hù)區(qū)域傾向因子Π、區(qū)域因子M01 初始化模型參數(shù)U，V，Π，M02 使用K?Means算法聚類(lèi)事件產(chǎn)生K個(gè)區(qū)域03 計(jì)算每個(gè)區(qū)域的特有參數(shù)(μ，∑i)，i=1，…，K04 計(jì)算事件與區(qū)域的從屬概率Cij，參見(jiàn)公式(7)

05 定義并初始化變量P=006 計(jì)算當(dāng)前參數(shù)下模型誤差值Q(使用公式(8)的第一部分)07 WhileQ-P>ε08 P=Q09 采用公式計(jì)算目標(biāo)函數(shù)在當(dāng)前參數(shù)值下的偏導(dǎo)數(shù)，參見(jiàn)公式(15)～(18)10 采用公式更新模型參數(shù)，參見(jiàn)公式(11)～(14)11 計(jì)算模型誤差值Q12 EndWhile13 返回當(dāng)前的參數(shù)值計(jì)算模型誤差值Q14 EndWhile

5.3 對(duì)比方法

我們使用以下四種模型與Hesi模型進(jìn)行對(duì)比，它們分別是： 1)矩陣因子分解(MF)[26]； 2)基于社交正則的矩陣因子分解(MFs)； 3)基于異構(gòu)社交正則的矩陣因子分解(MFh)； 4)基于區(qū)域傾向的矩陣因子分解(gMF)。

5.4 實(shí)驗(yàn)結(jié)果

參數(shù)α討論 在混合評(píng)分中，參數(shù)α聯(lián)合個(gè)體興趣評(píng)分和區(qū)域傾向評(píng)分，并決定兩種評(píng)分的比重，見(jiàn)等式(4)。因此，我們首先討論參數(shù)α的取值對(duì)于模型性能的影響。此處，使用AUC評(píng)價(jià)方法，在五個(gè)數(shù)據(jù)集上，分別測(cè)試模型在不同的α取值(0.91～0.99)下，模型精度的變化。實(shí)驗(yàn)結(jié)果顯示圖5中。如圖所示，在五個(gè)數(shù)據(jù)集上，模型精度伴隨著α取值的變化而輕微變化，在0.95附近出現(xiàn)明顯的波動(dòng)，并取得近似局部最優(yōu)值。因此，在后邊的實(shí)驗(yàn)中，我們定義α取值為0.95。

整體性能評(píng)價(jià) 為了便于驗(yàn)證算法整體的分類(lèi)性能，我們首先在五個(gè)實(shí)驗(yàn)數(shù)據(jù)集上，使用AUC評(píng)價(jià)標(biāo)準(zhǔn)，對(duì)比HeSi算法與其他四種算法的性能優(yōu)劣。實(shí)驗(yàn)結(jié)果如表2所示。從實(shí)驗(yàn)結(jié)果中，我們可以發(fā)現(xiàn)以下五個(gè)特征： 1)矩陣因子分解的算法可以獲得比基于用戶(hù)/對(duì)象相似度的協(xié)從過(guò)濾算法更高的精度； 2)使用社交正則后的矩陣因子分解算法的性能優(yōu)于未使用社交正則的矩陣因子分解算法； 3)異構(gòu)社交正則的方法除了增加了線(xiàn)上社交關(guān)系的約束也增加了線(xiàn)下社交關(guān)系的約束，比起單純使用線(xiàn)上社交關(guān)系有更好性能； 4)只使用基于區(qū)域傾向的矩陣因子分解算法在性能上比其他算法并沒(méi)有明顯優(yōu)勢(shì)； 5)基于混合個(gè)體興趣與區(qū)域傾向性的矩陣因子分解方法在異構(gòu)社交正則的約束下可以獲得更好的性能。

表2 AUC度量的算法準(zhǔn)確度評(píng)價(jià)

推薦結(jié)果評(píng)價(jià) 在真實(shí)的應(yīng)用場(chǎng)景中，用戶(hù)關(guān)注的是被展示的推薦結(jié)果，它的準(zhǔn)確與否決定了用戶(hù)體驗(yàn)的優(yōu)劣。因此，我們采用P@k和MAP方法去評(píng)價(jià)幾個(gè)算法的推薦性能。鑒于頁(yè)面信息的豐富性和用戶(hù)瀏覽的隨機(jī)性，用戶(hù)通常僅對(duì)排名靠前的結(jié)果感興趣而忽略大量剩余的推薦結(jié)果，因此我們主要測(cè)試了P@1和P@3。此外，我們使用MAP評(píng)價(jià)算法整體的推薦結(jié)果。在之前的性能評(píng)價(jià)中，我們已經(jīng)發(fā)現(xiàn)矩陣因子分解算法在性能上的優(yōu)勢(shì)。因此，我們只是比較HeSi算法和MF、MFh兩種算法，實(shí)驗(yàn)結(jié)果如圖6，7，8，9，10所示，采用P@1、P@3和MAP三種指標(biāo)進(jìn)行評(píng)價(jià)，HeSi算法比其他三種算法能得到更好的推薦性能。

圖5 混合因子α在不同取值下對(duì)于模型AUC精度的影響

圖6 休斯敦?cái)?shù)據(jù)集在三種不同評(píng)價(jià)下的算法精度度量

圖7 芝加哥數(shù)據(jù)集在三種不同評(píng)價(jià)下的算法精度度量

圖8 洛杉磯數(shù)據(jù)集在三種不同評(píng)價(jià)下的算法精度度量

圖9 紐約數(shù)據(jù)集在三種不同評(píng)價(jià)下的算法精度度量

圖10 舊金山數(shù)據(jù)集在三種不同評(píng)價(jià)下的算法精度度量

6 結(jié)論及展望

本文主要探索了社交網(wǎng)絡(luò)應(yīng)用中的事件推薦問(wèn)題。首先，通過(guò)分析Meetup數(shù)據(jù)，發(fā)現(xiàn)了EBSN數(shù)據(jù)的社交關(guān)系異構(gòu)性和區(qū)域傾向性。然后，針對(duì)這些屬性我們提出了融合地理特征和社交關(guān)系的HeSi模型，有效地提高了事件推薦的性能。

然而，在真實(shí)的應(yīng)用場(chǎng)景中，新用戶(hù)行為數(shù)據(jù)以數(shù)據(jù)流的形式持續(xù)實(shí)時(shí)到達(dá)，數(shù)據(jù)規(guī)模逐步增大。批處理學(xué)習(xí)難以應(yīng)對(duì)流式數(shù)據(jù)的挑戰(zhàn)。因此，在未來(lái)的研究工作中，我們主要關(guān)注事件推薦算法的在線(xiàn)學(xué)習(xí)策略。

[1] 彭澤環(huán),孫樂(lè),韓先培,石貝. 基于排序?qū)W習(xí)的微博用戶(hù)推薦[J].中文信息學(xué)報(bào), 2013, 27(4):96-102.

[2] 孫建凱,王帥強(qiáng),馬軍. Weighted-Tau Rank:一種采用加權(quán)Kendall Tau的面向排序的協(xié)同過(guò)濾算法[J].中文信息學(xué)報(bào), 2014, 28(1): 33-40.

[3] 羅成,劉奕群,張敏,馬少平,茹立云,張闊. 基于用戶(hù)意圖識(shí)別的查詢(xún)推薦研究[J].中文信息學(xué)報(bào), 2014, 28(1): 64-72.

[4] 李銳,王斌.一種基于作者建模的微博檢索模型[J].中文信息學(xué)報(bào), 2014, 28(2): 136-143.

[5] Liu X, Hey Q, Tiany Y, et al. Event-based social networks linking the online and offline social worlds[C]//Proceeding of the 18th ACM SIGKDD international conference on knowledge discovery and data mining, 2012: 1032-1040.

[6] Qiao Z, Zhang P, Cao Yanan,et al. Combining Heterogeneous Social and Geographical Information for Event Recommendation[C]//Proceeding of 28th AAAI Conference on Artificial Intelligence, 2014: 145-151.

[7] Salakhutdinov R, Mnih A. Probabilistic matrix factorization[C]//In Neural Information Processing Systems, 2008: 880-887.

[8] Somekh O, Aizenberg N, Koren Y. Build your own music recommender by modeling internet radio streams[C]//Proceedings of the 21st international conference on World Wide Web, 2012: 1-10.

[9] Wang C, Blei D M. Collaborative topic modeling for for recommending scientific articles[C]//Proceeding of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011: 448-456.

[10] Zhang P, Zhou C, Wang P,et al. E-tree: An efficient indexing structure for ensemble models on data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(2): 461-474.

[11] Rendle S, Freudenthaler C, Gantner Z,et al. Bpr: Bayesian personalized ranking from implicit feedback[C]//Proceeding of the 25 Conference on Uncertainty in Artificial Intelligence, 2009: 452-461.

[12] Pan W, Xiang E, Yang Q. Transfer learning in collaborative filtering with uncertain ratings[C]//Proceeding of Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012: 662-668.

[13] Ma H, Yang H, Lyu M R,et al. SoRec: social recommendation using probabilistic matrix factorization[C]//Proceeding of the 17th ACM conference on information and knowledge management, 2008: 931-940.

[14] Liua F, and Lee H J. Use of social network information enhance collaborative filtering performance[J]. Expert Systems with Applications, 2010, 37(7): 4772-4778.

[15] Xin X, King I, Deng H,et al.A social recommendation framework based on multi-scale continuous conditional random fields[C]//Proceeding of the 18th ACM conference on information and knowledge management, 2009: 1247-1256.

[16] Ma H, Zhou D, Liu C, et al.Recommender systems with social regularization[C]//Proceeding of the 4 ACM international conference on Web search and data mining, 2011:287-296.

[17] Lu Y, Tsaparas P, Ntoulas A,et al. Exploiting social context for review quality prediction[C]//Proceeding of the 19th International Conference on World Wide Web, 2010: 691-700.

[18] Cheng C, Yang H, King I,et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]//Proceeding of the 26 AAAI Conference on Artificial Intelligence, 2012: 542-548.

[19] Ye M, Yin P Y, Lee W-C L,et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceeding of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2011: 325-334.

[20] Zheng V W, Zheng Y, Xie X, et al. Collaborative location and activity recommendations with gps history data[C]//Proceeding of the 19th international conference on World Wide Web, 2010: 1029-1038.

[21] Qiao Z, Zhang P, He J,et al. Combining geographical information of users and content of items for accurate rating prediction[C]//Proceeding of 23rd International World Wide Web Conference, 2014: 361-362.

[22] Takeuchi Y, Sugimoto M. Cityvoyager: An outdoor recommendation system based on user location[J]. ubiPCMM, 2005, 4(3):625-636.

[23] Borzsonyil S, Kossmann D, Stocker K. The skyline operator[C]//Proceeding of 17th International Conference on Data Engineering, 2011:421-430.

[24] Chaudhuri S, Gravano L. Evaluating top-k selection queries[C]//Proceeding of the 25th International Conference on Very Large Data Bases, 1999: 397-410.

[25] Bruno N, Gravano L, Marian A. Evaluating top-k queries over web-accessible databases[J]. In ACM Transactions on Database Systems, 2004, 29(2): 369-369.

[26] Koren Y, Bell R, Volinsky C. Matrix factorization technology for recommendation system[J]. Journal of Computer, 2009, 42(8), 30-37.

Event Recommendation Based on Geographical Features and Heterogeneous Social Relationships

QIAO Zhi1,2, ZHOU Chuan2,3, JI Xiancai3, CAO Yanan3, GUO Li3

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190，China) (2. University of Chinese Academy of Sciences, Beijing 100049,China) (3. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093,China)

In order to improve users’ experience in event-based social networks (EBSNs) services, the event recommendation task has been studied in the recent years. In this paper, the user motivation data of EBSN applications is analyzed, and a novel latent factor model unifying multiple data features is proposed. This method considers two new types of features, i.e., heterogeneous online& offline social relationships and regional preference of users, and applies them for event recommendation. Experimental results on real-world data sets showed our method had better performance than some traditional methods.

event recommendation; event-based social network; collaborative filtering; regional preference; heterogeneous social relationship

喬治(1986—)，博士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘。E?mail：qxs1986@126．com周川(1984—)，博士，副研究員，主要研究領(lǐng)域?yàn)樯鐣?huì)計(jì)算。E?mail：zhouchuan@iie．a(chǎn)c．cn紀(jì)現(xiàn)才(1976—)，博士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。E?mail：jixiancai@iie．a(chǎn)c．cn，

1003-0077(2016)05-0047-10

2015-03-09 定稿日期： 2015-07-22

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)(2013CB329605)；國(guó)家自然科學(xué)基金(61502479，61403369)；中國(guó)科學(xué)院戰(zhàn)略先導(dǎo)科技專(zhuān)項(xiàng)(XDA06030200)

TP

A