,

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

0 概述

目前,智能手機(jī)已經(jīng)普及,其他移動(dòng)設(shè)備也廣泛應(yīng)用。通過這些移動(dòng)設(shè)備,人們的位置信息可以被獲取和共享。在獲取和得到這些位置信息后,一些有特色的應(yīng)用就可以被開發(fā)出來。如位置導(dǎo)航可以依據(jù)當(dāng)前位置搜索到達(dá)目的地的最佳路線、基于位置的搜索可以展示周邊的服務(wù)設(shè)施、如文獻(xiàn)[1]基于位置的社交網(wǎng)絡(luò)能夠使大家可以分享自己的位置,并與周圍的人建立聯(lián)系。

這些包含位置信息、時(shí)間信息、社交信息、活動(dòng)信息的數(shù)據(jù)積累下來后,可以提供增值服務(wù)。例如,可以分析用戶的活動(dòng)規(guī)律,也可以為用戶進(jìn)行地點(diǎn)選擇、活動(dòng)選擇、場(chǎng)所選擇提供依據(jù),甚至系統(tǒng)主動(dòng)針對(duì)以上方面提供推薦。

目前,學(xué)術(shù)界研究較多的是一些位置推薦方法,而對(duì)于活動(dòng)推薦方法的研究并不多,活動(dòng)推薦是一個(gè)有價(jià)值的研究課題,如今人們的生活節(jié)奏在加快,各種活動(dòng)也日益的豐富多彩,而怎么樣為用戶推薦他所感興趣和喜歡的活動(dòng),從而來提高生活質(zhì)量和品質(zhì)具有重要意義,與此同時(shí),活動(dòng)推薦對(duì)各大商家也具有重要的商業(yè)意義,比如,商業(yè)促銷活動(dòng)怎么樣來吸引潛在客戶,從而來實(shí)現(xiàn)商業(yè)利益的優(yōu)化提升等。文獻(xiàn)[2]提出了一個(gè)基于用戶歷史活動(dòng)記錄的活動(dòng)推薦方法,該方法僅僅通過比較目前的活動(dòng)過記錄與過去活動(dòng)記錄序列的相似性來進(jìn)行活動(dòng)推薦。文獻(xiàn)[3]提出了根據(jù)用戶的屬性信息來進(jìn)行活動(dòng)推薦的方法,然而,在現(xiàn)實(shí)中,很難獲得用戶的具體屬性信息。這些方法沒有能夠利用朋友間的相互關(guān)系,因而無法對(duì)用戶沒有嘗試過的活動(dòng)進(jìn)行推薦。在文獻(xiàn)[4]中,提出了一個(gè)新穎的社會(huì)活動(dòng)推薦系統(tǒng),該系統(tǒng)能夠基于背景聲音識(shí)別、用戶在線交互歷史數(shù)據(jù)計(jì)算其偏好及社會(huì)關(guān)系親密度為用戶進(jìn)行活動(dòng)推薦,但是該方法中沒有針對(duì)時(shí)空環(huán)境進(jìn)行推薦。文獻(xiàn)[5]提到為群組提供活動(dòng)推薦,但是它們并不能為某一個(gè)單獨(dú)的用戶提供個(gè)性化活動(dòng)推薦?？傊?目前還很少綜合利用時(shí)空信息和用戶社交信息為用戶提供個(gè)性化活動(dòng)推薦的方法。

為此,本文提出一種時(shí)間和位置感知的個(gè)性化活動(dòng)推薦(Time and Location-aware Activity Recommendation,TLAR)方法。

1 相關(guān)工作

協(xié)同過濾是推薦領(lǐng)域最常用的方法。通常,協(xié)同過濾可以分為2種類型:如文獻(xiàn)[6-7]鄰域模型和矩陣分解模型?；卩徲虻膮f(xié)同過濾方法包括基于用戶的協(xié)同過濾方法和基于物品的協(xié)同過濾方法。而矩陣分解模型則是通過矩陣分解建立用戶和隱類之間的關(guān)系,物品和隱類之間的關(guān)系,最終得到用戶對(duì)物品的偏好關(guān)系。協(xié)同過濾比較適合于物品和用戶的二元關(guān)系。

地理位置推薦是一個(gè)熱門的研究領(lǐng)域。不同學(xué)者提出了不同的方法。文獻(xiàn)[8]基于內(nèi)容和協(xié)同過濾方法上提出了一種基于模型的方法。文獻(xiàn)[9]提出了一種結(jié)合用戶的簽到行為、用戶特征及位置興趣點(diǎn)的語(yǔ)義特征,并將蟻群方法與改進(jìn)的混合協(xié)同過濾方法結(jié)合起來進(jìn)行個(gè)性化位置推薦。近年來,引入社交關(guān)系進(jìn)行地理位置推薦逐漸流行。例如,文獻(xiàn)[10]提出了一種基于分類層次偏好樹來提取個(gè)人偏好,同時(shí)結(jié)合位置社交網(wǎng)絡(luò)中的用戶信任關(guān)系來進(jìn)行位置推薦的方法。文獻(xiàn)[11]提出了一種分層模型的位置推薦方法,將地理位置社交網(wǎng)絡(luò)中的數(shù)據(jù)分為歷史位置層和社交關(guān)系層,在歷史位置層中,考慮用戶的歷史簽到位置序列具有冪律分布和瞬時(shí)效應(yīng)這2種特性,引入pitman-Yor模型來分析用戶的歷史位置簽到數(shù)據(jù),計(jì)算出下一次簽到位置的概率,結(jié)合社交關(guān)系,加入社交關(guān)系層的朋友數(shù)據(jù)信息,得出所有可能位置的概率分布,按照TopN方法給出推薦列表。

考慮時(shí)間因素進(jìn)行推薦也引起了研究者的興趣。例如,文獻(xiàn)[12]提出一種融合標(biāo)簽流行度和時(shí)間權(quán)重的矩陣分解推薦方法,該方法同時(shí)考慮用戶使用標(biāo)簽的頻率與用戶興趣隨時(shí)間變化的特點(diǎn),首先根據(jù)標(biāo)簽的流行度和時(shí)間特征刻畫用戶對(duì)資源的偏好,然后采用梯度下降法對(duì)用戶-資源矩陣進(jìn)行分解,最后利用分解后的特征矩陣對(duì)目標(biāo)用戶進(jìn)行預(yù)測(cè)并推薦。文獻(xiàn)[13]提出融合時(shí)間特征和協(xié)同過濾的興趣點(diǎn)推薦方法,首先利用基于位置社交網(wǎng)絡(luò)中大量的簽到數(shù)據(jù)提取用戶簽到的相似性特征以及時(shí)間的差異性,連續(xù)性特征,在此基礎(chǔ)上利用相似性特征進(jìn)行用戶過濾,然后采用基于連續(xù)時(shí)間槽的余弦相似度計(jì)算用戶間的相似度,最后給出時(shí)間特征和協(xié)同過濾的興趣點(diǎn)推薦方法。

針對(duì)活動(dòng)推薦,文獻(xiàn)[2-3]提出考慮用戶的歷史活動(dòng)信息以及用戶屬性的方法。文獻(xiàn)[14]提出一種基于語(yǔ)義和規(guī)則的業(yè)務(wù)活動(dòng)推薦方法,通過定義面向業(yè)務(wù)活動(dòng)的基礎(chǔ)本體模型并在此基礎(chǔ)上構(gòu)建了基本推理規(guī)則,推薦方法訪問知識(shí)庫(kù)并將生成最終的推薦結(jié)果呈現(xiàn)給用戶。除此以外,文獻(xiàn)[4-5]引入社交信息增強(qiáng)推薦效果也被提了出來。上述方法沒有綜合考慮時(shí)間、位置特性以及社交信息的綜合作用。

隨機(jī)游走已經(jīng)被用于推薦系統(tǒng)中。文獻(xiàn)[15]采用概念格從數(shù)據(jù)中挖掘知識(shí),利用用戶特征屬性和社交網(wǎng)絡(luò)圖建立概念格,提出了彈性隨機(jī)游走方法,并在此基礎(chǔ)上用概念格知識(shí)知道隨機(jī)游走,提出了融合概念格和隨機(jī)游走的方法,度量了用戶之間的相似性,方法最終根據(jù)相似度進(jìn)行朋友推薦,實(shí)驗(yàn)表明方法提高了準(zhǔn)確性。于是可以將隨機(jī)游走方法應(yīng)用在異構(gòu)信息網(wǎng)絡(luò)模型上。

以上的推薦方法各有其特點(diǎn),但是并沒有能夠?qū)⑸缃魂P(guān)系、地點(diǎn)、時(shí)間、活動(dòng)等信息加以綜合利用,而這正是本文方法的特點(diǎn)。

2 活動(dòng)異構(gòu)信息網(wǎng)絡(luò)模型和隨機(jī)游走方法

時(shí)間和位置感知的活動(dòng)推薦問題可以描述如下:對(duì)于一個(gè)用戶當(dāng)知道其地理位置和時(shí)間的條件下,需要在其地理位置半徑r內(nèi),為其推薦感興趣的活動(dòng)。

于是結(jié)合異構(gòu)信息網(wǎng)絡(luò)模型,提出了一種時(shí)間位置感知的活動(dòng)推薦方法。該方法依據(jù)簽到數(shù)據(jù)在活動(dòng)異構(gòu)信息網(wǎng)絡(luò)上先獲取與該用戶相關(guān)的子圖,然后再在該圖上根據(jù)邊上的權(quán)重進(jìn)行隨機(jī)游走,最后產(chǎn)生活動(dòng)推薦。

2.1 活動(dòng)異構(gòu)信息網(wǎng)絡(luò)模型

一個(gè)異構(gòu)信息網(wǎng)絡(luò)中包含了一組屬于T(T>1)個(gè)類別的對(duì)象,即X={Xt},其中Xt是屬于第t種類型的對(duì)象集合。信息網(wǎng)絡(luò)可以表示為加權(quán)網(wǎng)絡(luò)圖G=,其中X表示對(duì)象,E是X上的二元關(guān)系,W:E→R+將邊e∈E映射成一個(gè)實(shí)數(shù)。

在異構(gòu)信息網(wǎng)絡(luò)中,對(duì)象有以下類型:

1)用戶。

2)地點(diǎn)。

3)活動(dòng)。

在該異構(gòu)信息網(wǎng)絡(luò)中,關(guān)系有以下類型:

1)用戶與用戶:朋友關(guān)系。

2)用戶與地點(diǎn):用戶到過某一地點(diǎn),訪問關(guān)系。

3)用戶與活動(dòng):用戶參加過某一項(xiàng)活動(dòng),參與關(guān)系。

4)地點(diǎn)與活動(dòng):某一地點(diǎn)中發(fā)生了某一活動(dòng),發(fā)生關(guān)系。

值得注意的是,上述關(guān)系的表達(dá)中,用戶與地點(diǎn)、用戶與活動(dòng)、地點(diǎn)與活動(dòng)的關(guān)系是與時(shí)間相關(guān)的。假設(shè)將一天分為若干個(gè)時(shí)間段,那么,在不同時(shí)間段中,該關(guān)系是否存在可以依據(jù)實(shí)際中數(shù)據(jù)而定。

2.2 時(shí)間和位置感知的個(gè)人異構(gòu)信息網(wǎng)絡(luò)

個(gè)人異構(gòu)信息網(wǎng)絡(luò)圖的構(gòu)建主要包括子圖的構(gòu)建以及對(duì)子圖的邊進(jìn)行賦予權(quán)重這2個(gè)部分。

首先構(gòu)造好子圖。本文介紹的活動(dòng)異構(gòu)信息網(wǎng)絡(luò)圖是針對(duì)所有人員的。然而,目的是要為某一人員在特定地點(diǎn)、特定時(shí)間下推薦活動(dòng),因此,需要從整體圖上獲取相關(guān)的子圖,以此為依據(jù)進(jìn)行活動(dòng)推薦。

子圖的構(gòu)建主要考慮:

1)時(shí)間因素:僅僅考慮用戶在某個(gè)時(shí)間點(diǎn)訪問過的地點(diǎn)、用戶在某個(gè)時(shí)間中執(zhí)行的活動(dòng)。

2)地點(diǎn)因素:僅僅考慮用戶到過的附近的某個(gè)地點(diǎn)。

同時(shí)為了考慮社會(huì)關(guān)系的影響,將其朋友引入,對(duì)于朋友的地點(diǎn)、活動(dòng)也通過時(shí)間和地點(diǎn)因素加以篩選。

另一方面,活躍用戶常常代表了一種有選擇經(jīng)驗(yàn)的人士,他們的意見具有很大的參考價(jià)值,也可以把他們引入,他們的地點(diǎn)、活動(dòng)也通過時(shí)間、地點(diǎn)因素進(jìn)行篩選。

其次對(duì)構(gòu)建好的子圖的所有的邊賦予權(quán)重,對(duì)子圖中每一條邊依據(jù)其在歷史數(shù)據(jù)中出現(xiàn)的相對(duì)頻率賦予一個(gè)權(quán)重,定義權(quán)重的方法如下:

在構(gòu)建好的子圖中,邊的類型可以分為3類,即<用戶,用戶>,<用戶,地點(diǎn)>和<用戶,活動(dòng)>,可以分別用3個(gè)集合U,P,A來表示該類型邊的集合。對(duì)每一個(gè)被推薦的用戶t,假設(shè)與其直接相連的邊的邊數(shù)為n,則|Ut|+|Pt|+|At|=n,設(shè)w()為某條邊的權(quán)重函數(shù)。

(1)

對(duì)于<用戶,用戶>類型的邊,其權(quán)重為:

對(duì)于<用戶,地點(diǎn)>,<用戶,活動(dòng)>類型的邊,其權(quán)重將按照該邊在訓(xùn)練集中占的頻率并根據(jù)此頻率對(duì)其所在的集合進(jìn)行進(jìn)一步分配。例如對(duì)于<用戶,地點(diǎn)>類型的邊pti(i=1,2,…,|pt|),其頻率為:

那么其權(quán)重為:

(2)

根據(jù)這兩部分方法,構(gòu)建了如圖1所示的用戶異構(gòu)信息網(wǎng)絡(luò)圖。它經(jīng)過了時(shí)間和地點(diǎn)的篩選,并為每條邊附上相應(yīng)的權(quán)重,用字母w表示。

圖1 子圖模型

方法1子圖的構(gòu)建方法

輸入1)uid為用戶ID,space為地點(diǎn),time為時(shí)間;2)Locs(uid,space,time)為用戶uid在時(shí)間time內(nèi)到達(dá)在space內(nèi)的地點(diǎn);3)Acts(uid,space,time)為用戶uid在時(shí)間time內(nèi)在space內(nèi)的活動(dòng);4)friend(uid);5)ActiveUser(space)為在該space內(nèi)的活躍用戶

輸出PG

1.Create new user vertex u for the user with //uid 根據(jù)uid//創(chuàng)建用戶結(jié)點(diǎn)

2.X←X∪{u}//更新結(jié)點(diǎn)集合

3.Call function addActandLoc(uid) //構(gòu)建用戶,地點(diǎn)//時(shí)間,活動(dòng)組成的三維模型

4.for each ufof friend(uid) do //循環(huán)遍歷用戶朋友結(jié)點(diǎn)

5. uf←new user vertex for uf//創(chuàng)建新的結(jié)點(diǎn)

6.X←X∪{uf}//更新結(jié)點(diǎn)集合

7. Ef←new edge between u and uf//創(chuàng)建新的邊

8. E←E∪{Ef}//更新邊的集合

9. CalladdActandLoc(uf.uid) //構(gòu)建用戶連入朋友的//三維模型

10.end for

11.for each uaof ActiveUser(Space) do //循環(huán)遍歷活躍//用戶的結(jié)點(diǎn)

12. ua←new user vertex for ua

13. X←X∪{ua}

14. Ea←new edge between u and ua

15. E←E∪{Ea}

16. Call addActandLoc(ua.uid)//構(gòu)建用戶連入活躍//用戶的三維模型

17.end for

18.function addActandLoc(uid)//依次迭代構(gòu)建

19.for all l in Locs(uid,space,time) do //循環(huán)遍歷已//有模型中的地點(diǎn)結(jié)點(diǎn)集合

20. Xl←new location vertex for l

21. X←X∪{Xl}

22.end for

23.for all a in Acts(uid,space,time) do //循環(huán)遍歷已有//模型中活動(dòng)結(jié)點(diǎn)集合

24.Xa←new activity vertex for a

25. for each l in Xl

26. if ActLoc(a,l,time)=True //如果活動(dòng)和地點(diǎn)//時(shí)間之間沒有連接的邊

27. El←new edge between a and l //兩者之間創(chuàng)建//新的邊

28. E←E∪ {El}//更新邊集合

29. end for

30.X←X∪{Xa} //更新結(jié)點(diǎn)集合

31.end for

32.end function

2.3 基于隨機(jī)游走的活動(dòng)推薦

在構(gòu)造了針對(duì)某一用戶的圖PG后,可以利用該圖進(jìn)行活動(dòng)推薦,采用的方法是隨機(jī)游走方法。因此,本節(jié)先對(duì)隨機(jī)游走方法進(jìn)行簡(jiǎn)單介紹,再介紹如何將它用于活動(dòng)推薦。

2.3.1 隨機(jī)游走方法

隨機(jī)游走是基于物理中“布朗運(yùn)動(dòng)”相關(guān)的微觀粒子的運(yùn)動(dòng)形成的一個(gè)模型,后來這一模型作為數(shù)理金融中的重要的假設(shè),指的是證券價(jià)格的時(shí)間序列將呈現(xiàn)隨機(jī)狀態(tài),不會(huì)表現(xiàn)出某種可觀測(cè)或統(tǒng)計(jì)的確定趨勢(shì),即證券價(jià)格的變動(dòng)是不可預(yù)測(cè)的。在計(jì)算機(jī)領(lǐng)域,隨機(jī)游走則主要用來進(jìn)行一種關(guān)系的傳遞分析,文獻(xiàn)[16]經(jīng)常被用于圖的結(jié)點(diǎn)相關(guān)性排名。在隨機(jī)游走過程中,從某個(gè)特定節(jié)點(diǎn)開始,以一定的概率隨機(jī)選擇與該頂點(diǎn)相鄰的邊向其他結(jié)點(diǎn)游走,在每次游走過程中都會(huì)記錄游走過的結(jié)點(diǎn)以便于用于排名,持續(xù)這種游走過程,一段時(shí)間后將會(huì)趨于一個(gè)穩(wěn)定的狀態(tài),此時(shí)可以輸出被記錄的結(jié)點(diǎn)的訪問次數(shù)用于排序結(jié)點(diǎn)。如果一個(gè)圖有許多的結(jié)點(diǎn),隨機(jī)游走的話將會(huì)快速的遠(yuǎn)離開始結(jié)點(diǎn),從而可能導(dǎo)致更多訪問的是一些不那么重要的結(jié)點(diǎn)。為了避免并解決這個(gè)問題,本文采用一種重啟的隨機(jī)游走方法(Random Walk Restart,RWR)在這個(gè)方法里每次游走時(shí)都會(huì)有一個(gè)恒定的概率返回到起始節(jié)點(diǎn),于是那些離起始結(jié)點(diǎn)比較近的結(jié)點(diǎn)將會(huì)比那些離起始結(jié)點(diǎn)比較遠(yuǎn)的結(jié)點(diǎn)有更多的機(jī)會(huì)被訪問到。RWR的數(shù)學(xué)表達(dá)式為:

pt+1=(1-a)·s·pt+a·q

(3)

其中,pt,pt+1和q是列向量,pt第t步中的頂點(diǎn)概率分布,pit是第t步到達(dá)頂點(diǎn)i的概率。列向量q為重啟動(dòng)向量,表示初始狀態(tài),qi表示初始狀態(tài)下在頂點(diǎn)i的概率,列向量中設(shè)置用戶頂點(diǎn)值為1,其余為0,s是轉(zhuǎn)移概率矩陣,它的元素sij表示頂點(diǎn)i下一步到達(dá)頂點(diǎn)j的轉(zhuǎn)移概率。a為直接回到原始頂點(diǎn)的概率。穩(wěn)定概率分布使用該公式進(jìn)行計(jì)算,直到p收斂。

2.3.2 活動(dòng)推薦方法

本文利用RWR方法為用戶進(jìn)行個(gè)性化活動(dòng)的推薦。選擇用戶節(jié)點(diǎn)u為出發(fā)結(jié)點(diǎn),當(dāng)u開始游走時(shí),產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù),當(dāng)該隨機(jī)數(shù)落在與用戶u直接相連的邊對(duì)應(yīng)的權(quán)重區(qū)間,就沿著該邊向著下一個(gè)結(jié)點(diǎn)隨機(jī)游走,依次類似這樣的方法游走,如果到達(dá)的結(jié)點(diǎn)為某一活動(dòng)節(jié)點(diǎn)時(shí),就為它的計(jì)數(shù)上面加1,這樣依次迭代結(jié)束后,可以按照活動(dòng)的計(jì)數(shù)次數(shù)將活動(dòng)排序,并將結(jié)果輸出。

活動(dòng)推薦方法如下:

方法2基于隨機(jī)游走的活動(dòng)推薦方法

輸入PG;iterNum為迭代次數(shù),由子圖的邊數(shù)決定;r為重啟概率

輸出RankedActList

1.for i < iterNum do

2. p←rand(0,1)//隨機(jī)概率

3. if p

4. curNode←u //停止不走

5. else

6. curNode←SelectNextNodeByWeight (curNode) //依據(jù)當(dāng)前結(jié)點(diǎn)產(chǎn)生隨機(jī)概率落在邊的權(quán)重區(qū)間,來選擇游//走的下一個(gè)新結(jié)點(diǎn)

7. if curNode is activity then //如果游走的結(jié)點(diǎn)是活動(dòng)//結(jié)點(diǎn)

8. curNode.visitNumber←curNode.visitNumber+1 //記錄下活動(dòng)結(jié)點(diǎn)遍歷的次數(shù)

9. end if

10.end if//一次游走迭代完成

11. i←i+1;

12.end for //最終迭代次數(shù)完成

13.RankedActList←Sort(Activities)//最終活動(dòng)推薦//列表

上述方法中SelectNextNodeByWeight( )方法表示當(dāng)前結(jié)點(diǎn)依據(jù)產(chǎn)生的0～1之間的隨機(jī)數(shù)落在某條邊對(duì)應(yīng)的權(quán)重區(qū)間,通過結(jié)點(diǎn)隨機(jī)產(chǎn)生的概率落在某條邊的權(quán)重上,就把該邊的另一個(gè)結(jié)點(diǎn)做為要選擇的新當(dāng)前結(jié)點(diǎn)。方法的時(shí)間復(fù)雜度由構(gòu)建用戶子圖和隨機(jī)游走這兩部分組成,構(gòu)造用戶子圖時(shí)間復(fù)雜度為線性,所以,時(shí)間復(fù)雜度主要依賴于為邊賦權(quán)重以及依據(jù)邊的權(quán)重隨機(jī)游走的時(shí)間,而這部分的時(shí)間又取決于迭代的次數(shù)即子圖的邊的個(gè)數(shù),綜合考慮,方法時(shí)間復(fù)雜度為O(X2)。在實(shí)際上,并不是任意頂點(diǎn)之間都會(huì)有邊。

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

在實(shí)驗(yàn)中,將比較常見的方法和本文提出的活動(dòng)推薦方法在實(shí)際數(shù)據(jù)集上進(jìn)行了對(duì)比,并采用統(tǒng)一的指標(biāo)進(jìn)行了對(duì)比評(píng)價(jià)。

下面是具有代表性的2種方法:

1)流行活動(dòng)推薦(Popularity Activity Recom-mendation,PAR)方法:將在預(yù)定的半徑范圍中、相同的時(shí)間段內(nèi)最為流行的活動(dòng)推薦給用戶。

2)基于社會(huì)關(guān)系的活動(dòng)推薦(Social Based Activity Recommendation,SAR)方法:將在朋友中、相同的時(shí)間段內(nèi)最為流行的活動(dòng)推薦給用戶。

在實(shí)驗(yàn)中,選取這2種方法同本文提出的方法進(jìn)行了比較。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

在真實(shí)的Foursquare數(shù)據(jù)集[17]上評(píng)估了本文的方法。選取Foursquare上洛杉磯簽到的數(shù)據(jù)進(jìn)行實(shí)驗(yàn),該數(shù)據(jù)有表示用戶ID的字段、場(chǎng)所ID字段、經(jīng)度字段、維度字段、簽到時(shí)間戳字段,以及活動(dòng)類別字段等。對(duì)于數(shù)據(jù)集,進(jìn)行了分析并提取實(shí)驗(yàn)所需的字段,并根據(jù)時(shí)間戳字段的時(shí)間先后順序選取了時(shí)間最近的其中10萬條數(shù)據(jù)組成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試。

表1給出了數(shù)據(jù)集的組成,其中的數(shù)據(jù)按年度分布如圖2所示。

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

圖2 數(shù)據(jù)集時(shí)間分布

根據(jù)主題活動(dòng)的性質(zhì),一般都與時(shí)間關(guān)系密切。比如晚上經(jīng)常會(huì)去酒吧等,為了方便描述推薦活動(dòng),將數(shù)據(jù)集里的時(shí)間戳字段分成了4個(gè)時(shí)間區(qū)段:0—6時(shí)對(duì)應(yīng)標(biāo)志1;7—12時(shí)對(duì)應(yīng)標(biāo)志2;13—18時(shí)對(duì)應(yīng)標(biāo)志3;19—24時(shí)對(duì)應(yīng)標(biāo)志4。分別代表著24 h中的凌晨、上午、下午、和晚上4個(gè)時(shí)間區(qū)段。

同時(shí),將數(shù)據(jù)集中涉及到的活動(dòng)類型進(jìn)行了歸納,形成了8種主題活動(dòng),如表2所示。各個(gè)活動(dòng)類型包含了更細(xì)的子活動(dòng),如表3所示。各個(gè)活動(dòng)類型的流行度如表4所示。對(duì)于活躍用戶的選取,是根據(jù)數(shù)據(jù)集中用戶執(zhí)行活動(dòng)的頻率高低選取頻率較高的一部分用戶作為活躍用戶。

表2 數(shù)據(jù)集活動(dòng)類型

表3 數(shù)據(jù)集主題活動(dòng)字段下子活動(dòng)的數(shù)目

表4 數(shù)據(jù)集主題活動(dòng)的流行度

3.2 評(píng)價(jià)方法和指標(biāo)

對(duì)實(shí)驗(yàn)的評(píng)價(jià)和指標(biāo)采用精度和召回率2個(gè)評(píng)測(cè)指標(biāo),計(jì)算的公式如下:

(4)

(5)

TLAR方法有一些配置參數(shù),比如重啟概率取值0.1,根據(jù)隨機(jī)游走的方程迭代收斂后得到。地理位置活動(dòng)半徑取值1 000 m,考慮到如果距離范圍過大將失去空間上下環(huán)境活動(dòng)推薦的現(xiàn)實(shí)意義,如果距離范圍過小,那么構(gòu)造子圖的結(jié)點(diǎn)和邊數(shù)將會(huì)有限,影響活動(dòng)推薦的效果。這里在測(cè)試集數(shù)據(jù)上就針對(duì)距離的不同對(duì)PAR和TLAR進(jìn)行實(shí)驗(yàn),距離范圍分別為500 m、1 000 m、1 500 m,實(shí)驗(yàn)結(jié)果表明,PAR在這3個(gè)距離范圍內(nèi),精度和召回率將會(huì)隨著距離的擴(kuò)大而減小,TLAR在這3個(gè)距離范圍內(nèi),精度和召回率基本沒有什么變化,對(duì)比實(shí)驗(yàn)結(jié)果如圖3和圖4所示。

圖3 PAR和TLAR的精度對(duì)比

圖4 PAR和TLAR的召回率對(duì)比

在對(duì)應(yīng)的這3個(gè)不同的距離范圍,本文對(duì)PRA和TLAR推薦的平均時(shí)間也進(jìn)行了實(shí)驗(yàn)對(duì)比,如圖5所示。

圖5 PRA和TLAR的平均時(shí)間對(duì)比

由分析可知,推薦的時(shí)間效率隨著距離范圍的擴(kuò)大而減慢,主要是因?yàn)榫嚯x范圍擴(kuò)大后構(gòu)造子圖的邊數(shù)明顯增多,方法迭代的次數(shù)也將明顯增加,由此時(shí)間效率將會(huì)變慢。

對(duì)于選取出來的10萬條數(shù)據(jù)集,分別按比例1為9∶1,比例2為8∶2,比例3為7∶3,分為3組對(duì)本文的方法TLAR進(jìn)行實(shí)驗(yàn)。推薦活動(dòng)個(gè)數(shù)依舊為3個(gè),分別取3組實(shí)驗(yàn)的最后平均精度、平均召回率做對(duì)比分析,實(shí)驗(yàn)結(jié)果表明,這3組比例分割得到的結(jié)果非常相近,誤差在千分位,實(shí)驗(yàn)對(duì)比結(jié)果如圖6所示。

圖6 3種比例分割下TLAR的實(shí)驗(yàn)結(jié)果對(duì)比

因而,最后實(shí)驗(yàn)的配置參數(shù),重啟概率為0.1,半徑為1 000 m,數(shù)據(jù)集分割比例為9∶1。

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

將TLAR方法同流行活動(dòng)推薦方法(PAR),基于社會(huì)關(guān)系的活動(dòng)推薦方法(SAR)進(jìn)行實(shí)驗(yàn)對(duì)比,詳細(xì)的對(duì)比實(shí)驗(yàn)結(jié)果如圖7、圖8所示。隨著推薦個(gè)數(shù)的增加,TLAR的精度是越來越小,召回率越來越大,但是同PAR、SAR進(jìn)行對(duì)比,無論是精度還是召回率TLAR都具有明顯的優(yōu)勢(shì)。

圖7 3種方法精度對(duì)比

圖8 3種方法召回率對(duì)比

PAR將地理位置距離內(nèi)最流行的活動(dòng)推薦給用戶,并沒有考慮到社交朋友關(guān)系,也沒有考慮到上下文時(shí)間關(guān)系;SAR考慮的只是社交朋友關(guān)系和上下文時(shí)間關(guān)系,并沒有考慮到地理位置信息關(guān)系;而本文的TLAR同時(shí)融合了地理位置、時(shí)間、社交朋友關(guān)系和區(qū)域內(nèi)活躍用戶這些上下環(huán)境信息來進(jìn)行隨機(jī)游走推薦。另外,TLAR的方法時(shí)間復(fù)雜度為O(X2),因此,本文提出的TLAR考慮因素全面,且推薦效果優(yōu)勢(shì)明顯。

4 結(jié)束語(yǔ)

目前,利用位置信息進(jìn)行活動(dòng)推薦的研究并不多,本文提出的TLAR利用用戶的社交信息,能夠?qū)崿F(xiàn)時(shí)間和空間感知的活動(dòng)推薦。構(gòu)造個(gè)性化的異構(gòu)信息網(wǎng)絡(luò)子圖模型,然后進(jìn)行隨機(jī)游走產(chǎn)生推薦。實(shí)驗(yàn)結(jié)果表明,該方法在考慮因素和推薦效果上有著明顯的優(yōu)勢(shì)。下一步將繼續(xù)豐富上下文環(huán)境,使用本文構(gòu)造的模型進(jìn)行朋友推薦等其他方面的推薦。

[1] 于亞新,李玉龍,劉 欣,等.LBSNs 中基于用戶活動(dòng)和社交信任的好友及位置推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(10):2262-2266.

[2] KUMAR G,JERBI H,GURRIN C,et al.Towards activity recommendation from lifelogs[C]//Proceedings of the 16th International Conference on Information Integration and Web-based Applications & Services.New York,USA:ACM Press, 2014:87-96.

[3] CABALLERO A,GARCíA-VALVERDE T,PEREíGUEZ F,et al.Activity recommendation in intelligent campus environments based on the eduroam federation[J].Journal of Ambient Intelligence and Smart Environments,2016,8(1):35-46.

[4] 楊 曜,郭 斌,於志文.一種基于背景聲音識(shí)別的移動(dòng)社會(huì)活動(dòng)推薦系統(tǒng)[J].計(jì)算機(jī)科學(xué),2014,41(10):62-66.

[5] PURUSHOTHAM S,KUO C C J,SHAHABDEEN J,et al.Collaborative group-activity recommendation in location-based social networks[C]//Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Crowdsourced and Volunteered Geographic Information.New York,USA:ACM Press,2014:8-15.

[6] SARWAR B,KARYPIS G,KONSTAN J,et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International Conference on World Wide Web.Washington D.C.,USA:IEEE Press,2001:285-295.

[7] YEHUDA K.Factorization meets the neighborhood:a multifaceted collaborative filtering model[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2008,426-434.

[8] JIANG D,GUO X,GAO Y,et al.Locations recommendation based on check-in data from location-based social network[C]//Proceedings of the 22nd International Conference on Geoinformatics.Washington D.C.,USA:IEEE Press,2014:1-4.

[9] 徐雅斌,孫曉晨.位置社交網(wǎng)絡(luò)的個(gè)性化位置推薦[J].北京郵電大學(xué)學(xué)報(bào),2015,38(5):118-124.

[10] 林樹寬,柳 帥,陳祖龍,等.基于分類層次偏好樹和用戶間信任度的位置推薦方法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(8):1677-1681.

[11] 孔曉笛,周健勇.基于分層模型的位置推薦方法研究[J].計(jì)算機(jī)與數(shù)字工程,2015,43(3):468-472.

[12] 郭 娣,趙海燕.融合標(biāo)簽流行度和時(shí)間權(quán)重的矩陣分解推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(2):293-297.

[13] 宋亞偉,司亞利,劉文遠(yuǎn),等.融合時(shí)間特征和協(xié)同過濾的興趣點(diǎn)推薦算法[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(6):1153-1158.

[14] 張 龍,應(yīng) 時(shí),賈向陽(yáng),等.一種基于語(yǔ)義的業(yè)務(wù)活動(dòng)推薦方法[J].計(jì)算機(jī)科學(xué),2014,41(9):185-189.

[15] 李宏濤,何克清,王 健,等.基于概念格和隨機(jī)游走的社交網(wǎng)朋友推薦算法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2015,47(6):131-138.

[16] WANG Y,YOON B J,QIAN X.Co-Segmentation of multiple images through random walk on graphs[C]//Proceedings of 2016 IEEE International Conference on Acoustics,Speech and Signal Processing.Washington D.C.,USA:IEEE Press,2016:1811-1815.

[17] NASIROV N,ALBAYRAK S.Modelling user’s location check-ins on location-based social networks[C]//Proceedings of the 23rd Signal Processing and Communications Applications Conference.Washington D.C.,USA:IEEE Press,2015:2246-2249.