時間與位置感知的活動個性化推薦方法

,

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

0 概述

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

這些包含位置信息、時間信息、社交信息、活動信息的數據積累下來后,可以提供增值服務。例如,可以分析用戶的活動規律,也可以為用戶進行地點選擇、活動選擇、場所選擇提供依據,甚至系統主動針對以上方面提供推薦。

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

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

1 相關工作

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

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

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

針對活動推薦,文獻[2-3]提出考慮用戶的歷史活動信息以及用戶屬性的方法。文獻[14]提出一種基于語義和規則的業務活動推薦方法,通過定義面向業務活動的基礎本體模型并在此基礎上構建了基本推理規則,推薦方法訪問知識庫并將生成最終的推薦結果呈現給用戶。除此以外,文獻[4-5]引入社交信息增強推薦效果也被提了出來。上述方法沒有綜合考慮時間、位置特性以及社交信息的綜合作用。

隨機游走已經被用于推薦系統中。文獻[15]采用概念格從數據中挖掘知識,利用用戶特征屬性和社交網絡圖建立概念格,提出了彈性隨機游走方法,并在此基礎上用概念格知識知道隨機游走,提出了融合概念格和隨機游走的方法,度量了用戶之間的相似性,方法最終根據相似度進行朋友推薦,實驗表明方法提高了準確性。于是可以將隨機游走方法應用在異構信息網絡模型上。

以上的推薦方法各有其特點,但是并沒有能夠將社交關系、地點、時間、活動等信息加以綜合利用,而這正是本文方法的特點。

2 活動異構信息網絡模型和隨機游走方法

時間和位置感知的活動推薦問題可以描述如下:對于一個用戶當知道其地理位置和時間的條件下,需要在其地理位置半徑r內,為其推薦感興趣的活動。

于是結合異構信息網絡模型,提出了一種時間位置感知的活動推薦方法。該方法依據簽到數據在活動異構信息網絡上先獲取與該用戶相關的子圖,然后再在該圖上根據邊上的權重進行隨機游走,最后產生活動推薦。

2.1 活動異構信息網絡模型

一個異構信息網絡中包含了一組屬于T(T>1)個類別的對象,即X={Xt},其中Xt是屬于第t種類型的對象集合。信息網絡可以表示為加權網絡圖G=,其中X表示對象,E是X上的二元關系,W:E→R+將邊e∈E映射成一個實數。

在異構信息網絡中,對象有以下類型:

1)用戶。

2)地點。

3)活動。

在該異構信息網絡中,關系有以下類型:

1)用戶與用戶:朋友關系。

2)用戶與地點:用戶到過某一地點,訪問關系。

3)用戶與活動:用戶參加過某一項活動,參與關系。

4)地點與活動:某一地點中發生了某一活動,發生關系。

值得注意的是,上述關系的表達中,用戶與地點、用戶與活動、地點與活動的關系是與時間相關的。假設將一天分為若干個時間段,那么,在不同時間段中,該關系是否存在可以依據實際中數據而定。

2.2 時間和位置感知的個人異構信息網絡

個人異構信息網絡圖的構建主要包括子圖的構建以及對子圖的邊進行賦予權重這2個部分。

首先構造好子圖。本文介紹的活動異構信息網絡圖是針對所有人員的。然而,目的是要為某一人員在特定地點、特定時間下推薦活動,因此,需要從整體圖上獲取相關的子圖,以此為依據進行活動推薦。

子圖的構建主要考慮:

1)時間因素:僅僅考慮用戶在某個時間點訪問過的地點、用戶在某個時間中執行的活動。

2)地點因素:僅僅考慮用戶到過的附近的某個地點。

同時為了考慮社會關系的影響,將其朋友引入,對于朋友的地點、活動也通過時間和地點因素加以篩選。

另一方面,活躍用戶常常代表了一種有選擇經驗的人士,他們的意見具有很大的參考價值,也可以把他們引入,他們的地點、活動也通過時間、地點因素進行篩選。

其次對構建好的子圖的所有的邊賦予權重,對子圖中每一條邊依據其在歷史數據中出現的相對頻率賦予一個權重,定義權重的方法如下:

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

(1)

對于<用戶,用戶>類型的邊,其權重為:

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

那么其權重為:

(2)

根據這兩部分方法,構建了如圖1所示的用戶異構信息網絡圖。它經過了時間和地點的篩選,并為每條邊附上相應的權重,用字母w表示。

圖1 子圖模型

方法1子圖的構建方法

輸入1)uid為用戶ID,space為地點,time為時間;2)Locs(uid,space,time)為用戶uid在時間time內到達在space內的地點;3)Acts(uid,space,time)為用戶uid在時間time內在space內的活動;4)friend(uid);5)ActiveUser(space)為在該space內的活躍用戶

輸出PG

1.Create new user vertex u for the user with //uid 根據uid//創建用戶結點

2.X←X∪{u}//更新結點集合

3.Call function addActandLoc(uid) //構建用戶,地點//時間,活動組成的三維模型

4.for each ufof friend(uid) do //循環遍歷用戶朋友結點

5. uf←new user vertex for uf//創建新的結點

6.X←X∪{uf}//更新結點集合

7. Ef←new edge between u and uf//創建新的邊

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

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

10.end for

11.for each uaof ActiveUser(Space) do //循環遍歷活躍//用戶的結點

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)//構建用戶連入活躍//用戶的三維模型

17.end for

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

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

20. Xl←new location vertex for l

21. X←X∪{Xl}

22.end for

23.for all a in Acts(uid,space,time) do //循環遍歷已有//模型中活動結點集合

24.Xa←new activity vertex for a

25. for each l in Xl

26. if ActLoc(a,l,time)=True //如果活動和地點//時間之間沒有連接的邊

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

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

29. end for

30.X←X∪{Xa} //更新結點集合

31.end for

32.end function

2.3 基于隨機游走的活動推薦

在構造了針對某一用戶的圖PG后,可以利用該圖進行活動推薦,采用的方法是隨機游走方法。因此,本節先對隨機游走方法進行簡單介紹,再介紹如何將它用于活動推薦。

2.3.1 隨機游走方法

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

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

(3)

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

2.3.2 活動推薦方法

本文利用RWR方法為用戶進行個性化活動的推薦。選擇用戶節點u為出發結點,當u開始游走時,產生一個0～1之間的隨機數,當該隨機數落在與用戶u直接相連的邊對應的權重區間,就沿著該邊向著下一個結點隨機游走,依次類似這樣的方法游走,如果到達的結點為某一活動節點時,就為它的計數上面加1,這樣依次迭代結束后,可以按照活動的計數次數將活動排序,并將結果輸出。

活動推薦方法如下:

方法2基于隨機游走的活動推薦方法

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

輸出RankedActList

1.for i < iterNum do

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

3. if p

4. curNode←u //停止不走

5. else

6. curNode←SelectNextNodeByWeight (curNode) //依據當前結點產生隨機概率落在邊的權重區間,來選擇游//走的下一個新結點

7. if curNode is activity then //如果游走的結點是活動//結點

8. curNode.visitNumber←curNode.visitNumber+1 //記錄下活動結點遍歷的次數

9. end if

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

11. i←i+1;

12.end for //最終迭代次數完成

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

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

3 實驗與結果分析

在實驗中,將比較常見的方法和本文提出的活動推薦方法在實際數據集上進行了對比,并采用統一的指標進行了對比評價。

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

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

2)基于社會關系的活動推薦(Social Based Activity Recommendation,SAR)方法:將在朋友中、相同的時間段內最為流行的活動推薦給用戶。

在實驗中,選取這2種方法同本文提出的方法進行了比較。

3.1 實驗數據集

在真實的Foursquare數據集[17]上評估了本文的方法。選取Foursquare上洛杉磯簽到的數據進行實驗,該數據有表示用戶ID的字段、場所ID字段、經度字段、維度字段、簽到時間戳字段,以及活動類別字段等。對于數據集,進行了分析并提取實驗所需的字段,并根據時間戳字段的時間先后順序選取了時間最近的其中10萬條數據組成數據集進行實驗測試。

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

表1 數據集統計信息

圖2 數據集時間分布

根據主題活動的性質,一般都與時間關系密切。比如晚上經常會去酒吧等,為了方便描述推薦活動,將數據集里的時間戳字段分成了4個時間區段:0—6時對應標志1;7—12時對應標志2;13—18時對應標志3;19—24時對應標志4。分別代表著24 h中的凌晨、上午、下午、和晚上4個時間區段。

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

表2 數據集活動類型

表3 數據集主題活動字段下子活動的數目

表4 數據集主題活動的流行度

3.2 評價方法和指標

對實驗的評價和指標采用精度和召回率2個評測指標,計算的公式如下:

(4)

(5)

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

圖3 PAR和TLAR的精度對比

圖4 PAR和TLAR的召回率對比

在對應的這3個不同的距離范圍,本文對PRA和TLAR推薦的平均時間也進行了實驗對比,如圖5所示。

圖5 PRA和TLAR的平均時間對比

由分析可知,推薦的時間效率隨著距離范圍的擴大而減慢,主要是因為距離范圍擴大后構造子圖的邊數明顯增多,方法迭代的次數也將明顯增加,由此時間效率將會變慢。

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

圖6 3種比例分割下TLAR的實驗結果對比

因而,最后實驗的配置參數,重啟概率為0.1,半徑為1 000 m,數據集分割比例為9∶1。

3.3 實驗結果

將TLAR方法同流行活動推薦方法(PAR),基于社會關系的活動推薦方法(SAR)進行實驗對比,詳細的對比實驗結果如圖7、圖8所示。隨著推薦個數的增加,TLAR的精度是越來越小,召回率越來越大,但是同PAR、SAR進行對比,無論是精度還是召回率TLAR都具有明顯的優勢。

圖7 3種方法精度對比

圖8 3種方法召回率對比

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

4 結束語

目前,利用位置信息進行活動推薦的研究并不多,本文提出的TLAR利用用戶的社交信息,能夠實現時間和空間感知的活動推薦。構造個性化的異構信息網絡子圖模型,然后進行隨機游走產生推薦。實驗結果表明,該方法在考慮因素和推薦效果上有著明顯的優勢。下一步將繼續豐富上下文環境,使用本文構造的模型進行朋友推薦等其他方面的推薦。

[1] 于亞新,李玉龍,劉 欣,等.LBSNs 中基于用戶活動和社交信任的好友及位置推薦算法[J].小型微型計算機系統,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] 楊 曜,郭 斌,於志文.一種基于背景聲音識別的移動社會活動推薦系統[J].計算機科學,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] 徐雅斌,孫曉晨.位置社交網絡的個性化位置推薦[J].北京郵電大學學報,2015,38(5):118-124.

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

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

[12] 郭 娣,趙海燕.融合標簽流行度和時間權重的矩陣分解推薦算法[J].小型微型計算機系統,2016,37(2):293-297.

[13] 宋亞偉,司亞利,劉文遠,等.融合時間特征和協同過濾的興趣點推薦算法[J].小型微型計算機系統,2016,37(6):1153-1158.

[14] 張 龍,應 時,賈向陽,等.一種基于語義的業務活動推薦方法[J].計算機科學,2014,41(9):185-189.

[15] 李宏濤,何克清,王 健,等.基于概念格和隨機游走的社交網朋友推薦算法[J].四川大學學報(工程科學版),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.