LBSN中基于活動區域劃分的元路徑興趣點推薦

徐澤鋒，劉文菊，王 賾

（天津工業大學計算機科學與軟件學院，天津 300387）

LBSN中基于活動區域劃分的元路徑興趣點推薦

徐澤鋒1，劉文菊2，王 賾2

（天津工業大學計算機科學與軟件學院，天津 300387）

基于位置的社交網絡（Location Based Social Networks，LBSN）的相關服務推薦越來越多，而興趣點（Point Of Interest，POI）推薦作為LBSN相關服務中的一項個性化推薦也備受關注，越來越多的學者投入研究。目前，各種基于位置的推薦算法層出不窮，但由于LBSN中的數據極度稀疏的原因，導致許多算法推薦精度不高，本文提出了一種基于用戶活動區域劃分的元路徑推薦算法。首先，根據用戶簽到以及點評的地點呈現區域性，將用戶活動區域分為頻繁活動區域和不經常活動區域，根據LBSN結構特征構建用戶-活動區域和活動區域-興趣點之間的二分圖模型，其次引入元路徑，計算從用戶到興趣點的實例路徑的關聯度，最后根據關聯度大小生成推薦列表。結果表明，該算法較傳統的LBSN推薦算法有更好的推薦效果。

基于位置的社交網絡；區域劃分；元路徑；興趣點推薦

0 引言

隨著網絡的發展，web 2.0技術的進步，衛星通信、無線傳感器網絡、GPS導航設備等不斷向前發展，用戶獲得實時位置的功能越來越精確，這樣也催生了基于位置的社交網絡（Location Based Social Network，LBSN），使得基于位置的社交網絡迅速發展。國內外一些流行的基于位置的服務如微信朋友圈、Gowalla、Foursquare、街旁等正在一步一步促進人們的社交模式從傳統的在線社交轉變為基于位置的社交。在LBSN中增加位置信息，以簽到的形式與好友分享興趣點（Point of Interest，POI）。基于LBSN的興趣點推薦能夠向用戶推薦一些未曾訪問過但是可能感興趣的興趣點，有效的使用戶對城市有進一步了解，增強用戶體驗，同時促進商業發展，意義重大。

隨著用戶的參與度的提高，用戶數量及簽到地點的數量巨大，個性化的推薦技術在不同應用領域也受到了工業界和學術界的廣泛關注[1]。但是，這些大規模用戶數量和各種信息為用戶了解身邊的事物帶來方便的的同時也給用戶帶來了困擾。面對如此巨大的信息量，用戶的選擇就有些遲疑，用戶所期待的是能智能地通過其自身的位置信息感知周圍環境向其進行個性化推薦服務。LBSN包含了用戶和其簽到的興趣點相關信息，但是由于興趣點數量巨大，同時每個用戶訪問的興趣點個數十分有限，所以用戶、興趣點之間的簽到矩陣極度稀疏，給興趣點推薦帶來了新的挑戰。但是，根據學者相關研究，用戶簽到位置呈現區域化，其活動范圍受空間和社會關系等的影響具有一定的規律性。

根據以上問題及其研究，本文提出了一種基于用戶活動區域劃分的元路徑興趣點推薦算法。首先根據用戶簽到信息呈現的區域化對用戶簽到的興趣點進行區域化劃分為經常活動區域和不經常活動區域；然后定義區域節點，構建用戶-活動區域、活動區域-興趣點的異構網絡模型；最后引入元路徑，計算用戶到興趣點之間的關聯度得到元路徑特征值，計算用戶到候選興趣點的簽到概率生成推薦列表。實驗表明，本文提出的推薦算法有較好的推薦效果，在提高推薦精確度的同時對數據稀疏性有一定的緩解。

1 相關工作

隨著位置感知技術和基于位置的社會化網絡的興起與發展，為用戶提供網絡社交與共享平臺的同時，也能夠及時記錄用戶位置簽到信息，這為定量研究移動個體活動在時間、空間特征及社會關系的關聯性上提供了大量的數據，逐漸引起學者們的關注[2]，推薦技術發展到今天已經取得了不少成果。CHO等人[3]把用戶分成近距離好友、遠距離好友和其他用戶，然后利用協同過濾的推薦算法實現對用戶的近距離與遠距離的好友信息相結合來進行推薦。ZHENG等人[4]運用協同過濾的思想進行興趣點推薦。YE等人[5]結合用戶偏好、社交關系和興趣點地理位置三方面因素，綜合基于用戶的協同過濾推薦、基于好友的協同過濾推薦和基于地理位置的推薦的混合協同過濾推薦算法。

以上研究整體來說就是基于用戶的歷史簽到信息，分析用戶偏好、社交關系等，運用協同過濾的思想來設計推薦算法，而有研究人員結合上下文信息構建推薦模型。高榕等人[6]在已有的基于矩陣分解的基礎上融合關于興趣點的評論信息、用戶社交關聯和地理信息這3個因素進行興趣點推薦。陳志雄等人[7]針對現有社交網絡興趣點推薦的研究工作主要集中在挖掘興趣點的情景信息而對用戶偏好的影響尚未充分研究的問題，提出一種融合用戶偏好、時間信息、地理位置和評論信息的模型來進行興趣點推薦。CHENG等人[8]將用戶社交關系和地理位置融入概率矩陣分解模型，通過建立用戶在位置上的簽到概率模型作為多中心高斯模型來捕獲地理影響力，繼而吧社交信息和地理信息融入到一個廣義的矩陣分解模型中。

有學者對用戶的簽到信息進行分析，發現用戶的簽到位置呈現周期性和區域化[9]，這主要與他們在社交網絡中好友關系有關。PELECHRINIS等人[10]對大量移動個體用戶的活動進行分析，發現兩個個體的活動相似性與他們社會網絡中近鄰存在較強的關聯性，進一步研究發現個體移動活動、社交關系和鏈路預測彼此影響。

2 基于用戶活動區域劃分的元路徑興趣點推薦

2.1 用戶活動區域劃分

我們每天生活在一定區域，其位置變化隨著時間變化具有一定的隨機性，通過對大量用戶的位置軌跡追蹤研究，這種隨機性又表現出規律性，即用戶的活動范圍較為集中。對LBSN中的每個用戶來說，他可以借助于社交網絡分享自己感興趣的位置，并對這些位置做出自己的評價，通過統計這些點評位置的信息，同樣也能夠反映出一個移動用戶活動范圍。日常生活中用戶一般是以家庭所在地為中心，在一定區域范圍內活動。因此可以根據用戶點評實體對象的位置信息來確定其活動范圍，利用點評對象的區域分布密度來確定用戶活動范圍，這包括由于其日常周期性行為活動而形成的頻繁活動區域和非頻繁活動區域。

定義 1. 用戶集合：用戶 U={ui|i∈[1,n]}表示LBSN中用戶的集合，其中n表示用戶的個數。集合中每個用戶包含用戶 ID和一些基本屬性（如年齡、性別等）。

定義2. 實體對象集合：LBSN中實體對象的集合用L表示，L={lj| j∈[1,m]},其中m表示LBSN中實體對象的個數。LBSN中的實體對象即用戶簽到或感興趣的興趣點，如商場、餐館、游泳館等。每一個實體對象包含其ID、經度、緯度等相關信息。

定義3. 用戶活動區域：設在一定活動區域內所有用戶簽到的興趣點之間的最大距離和最小距離分別為Dmax和Dmin，兩個點評實體間距離大小的中位數設為D. Ru為用戶 u的所有點評或簽到的實體對象的中心點到最遠點評實體的距離，為該用戶在這個區域的一個活動范圍。若Ru< D，則將該用戶的活動范圍視為該用戶的頻繁活動區域；若Ru> D，則以該用戶點評或簽到的中心點為圓心，D為半徑的一個范圍視為該用戶的頻繁活動區域，而將Ru- D的范圍視為該用戶的非頻繁活動區域。

2.2 元路徑集的確定

2.2.1 元路徑

元路徑主要用來描述異構網絡中任意兩個節點間的不同路徑類型[11]。對于LBSN中兩個節點之間的連接路徑可以是不同長度，不同類型。節點間不同的路徑類型和路徑長度所代表的物理意義和體現的節點間關聯程度都是不同的。

定義 5. 實例路徑：設存在真實路徑 p=[a1, a2，…an]，ai為LBSN中節點。對任意i，節點ai的類型為 Ai， ai和 ai+1之間的關系類型為 Ri，則路徑p稱為元路徑的一條實例路徑，所有這樣的真實路徑稱為元路徑P的實例路徑集P′。

2.2.2 用戶活動區域圖模型構建

LBSN是一種異構網絡，主要由用戶和實體對象節點組成，用戶和用戶之間、實體對象和實體對象之間存在一定的關系，用戶和實體對象之間主要表現為簽到行為。如圖1表示的LBSN結構圖。

而在本文定義3中定義了頻繁活動區域和非頻繁活動區域，用戶、實體對象（興趣點）、位置信息是LBSN相關服務中三個基本對象。本文提出的算法中引入新的節點 R，用來表示活動區域。用戶在一定區域內的簽到數據可以分為在頻繁活動區域的簽到和在非頻繁活動區域的簽到。在引入新的區域節點R之后，利用用戶和活動區域的關系將簽到行為構建二分圖和(U為用戶，L為興趣點)，新節點R作為橋梁將用戶和興趣點連接起來，其形式如圖2。其中 Ri1表示用戶i的頻繁活動區域，Ri2表示用戶i的非頻繁活動區域。

圖1 LBSN 結構圖Fig. 1 LBSN structure diagram

圖2 LBSN 結構圖模型Fig.2 LBSN structure diagram model

2.2.3 LBSN中元路徑集的確定

由圖2可知，用戶簽到的興趣點一部分來自其頻繁活動區域，一部分來至非頻繁活動區域，通過活動區域節點將二者連接起來。圖2中用戶u1和u2在頻繁活動區域內都對l4興趣點有過簽到，則可以將l5這個興趣點推薦給用戶u1，其關聯的路徑為：u1-R11-u2-R21-l5，利用u1和u2之間的關聯性，將l5推薦給用戶 u1，同理可以將l1和l2推薦給 u2用戶，其關聯的路徑分別為u2-R21-u1-R11-l1、u2-R21-u1- R11-l2。

根據以上描述，歸納出四種路徑，U-Ru1-U*-R*1-L、U-Ru1-U*-R*2-L、U-Ru2-U*-R*1-L、U-Ru2-U*-R*2-L（其中U為目標用戶，Ru1、Ru2分別為目標用戶的頻繁活動區域和非頻繁活動區域，U*代表與目標用戶相關聯的用戶，R*1、R*2分別為用戶U*的頻繁活動區域和非頻繁活動區域，L為待推薦的興趣點）。

以上四種路徑都是從目標用戶到興趣點的，體現的是目標用戶和興趣點的關聯性，將這四種路徑作為元路徑集。

2.2.4 LBSN中元路徑特征值的計算

定義6. 元路徑特征值：元路徑的特征值體現的是元路徑中首末節點之間的一種關聯程度，其計算方法由所有實例路徑體現的關聯程度之和所得。

對于給定的元路徑，其實例路徑的關聯程度為實例路徑各邊權值之積。設E(P)表示元路徑特征值，c(p)表示實例路徑p的關聯程度，則元路徑特征值計算方法如下：

其中，n為元路徑P的實例路徑數：

在實驗過程中首先為實例路徑的每條邊計算一定的權值，然后根據權值計算實例路徑的關聯程度。

（1）對于元路徑中的用戶和活動區域這條邊（即U-R邊），采用用戶在活動區域的簽到比例，分別用以代表用戶與頻繁活動區域、用戶與非頻繁活動區域邊的權值。

（2）對于活動區域與用戶邊（即 R-U邊），采用兩個用戶的相似性來度量。在元路徑U-R-U*中，即采用U和U*兩個用戶的相似性。由于LBSN中用戶簽到矩陣極度稀疏，所以當用戶只有一個簽到興趣點時采用Jaccard計算這兩個用戶的相似度，當兩個用戶簽到的興趣點個數都大于1時，則用余弦相似性計算兩個用戶的相似度。

（3）對于活動區域和興趣點邊（即 R-L邊），本文引用一個關注度來衡量用 (,)con u l表示用戶u對興趣點l的關注度，其計算公式如下：

其中， (,)N u l表示用戶u在興趣點l處的簽到次數， ()N u為用戶簽到的總次數， ()N U 為所有的簽到用戶數， ()N l為在興趣點l簽到的用戶數。如果一個用戶在某個興趣點的簽到次數高于其他用戶，則可以認為這個用戶對這興趣點的關注度較其他用戶高。由公式（3）可以看出若一個用戶頻繁訪問一個興趣點，但是這個興趣點總的來說并不被其他用戶頻繁訪問，則 (,)con u l值就越大，即用戶對此興趣點的關注度較高。

2.3 推薦算法及結果生成

在給定用戶以及用戶的簽到信息，根據特定的元路徑，給用戶推薦其可能訪問的興趣點，其計算方式為：

根據公式（4），對于給定的用戶u，可以計算其對興趣點l訪問的一個概率，再由概率由大到小返回一個推薦列表。

3 實驗與分析

3.1 實驗數據集

本文采用的數據集為Gowalla公開數據集，此數據集共包括 196585個簽到用戶，對每個用戶包括用戶 ID、簽到時間、簽到興趣點的經緯度和簽到興趣點的ID。用戶簽到的總記錄為6442892條，以及700000個簽到興趣點，簽到矩陣是極度疏松。根據本文提出的算法，對數據進行處理，得到21700個用戶，1560352條簽到記錄，共76956個簽到興趣點。

3.2 評價指標及對比實驗

在興趣點推薦問題中，通常采用準確率（precision）和召回率（recall）來評價算法的優劣。其計算方法如下：

3.3 實驗結果與分析

本文提出的基于用戶活動區域劃分的元路徑興趣點推薦算法（OurMethod）將與基于用戶簽到記錄計算用戶相似度的協同推薦方法[5]（User-Based Collaborative Filtering，UBCF）和基于用戶共同好友計算用戶相似度的協同過濾推薦方法[12]（Friend-Based Collaborative Filtering，FBCF）來進行試驗對比和分析。其中，UBCF算法是基于用戶簽到記錄計算用戶相似性，再運用傳統協同過濾方法進行推薦；FBCF是基于用戶共同好友和簽到信息計算用戶相似性，再運用傳統協同過濾算法進行推薦。本文針對同一數據集（Gowalla公開數據集）進行實驗，選取推薦列表興趣點個數分別為 5，10，15，20，25五種情況，就三種推薦算法推薦的準確率和召回率進行對比，其實驗對比圖如圖3、圖4所示。

圖3 準確率對比圖Fig.3 The precision of the comparison chart

圖4 召回率對比圖Fig.4 The recall of the comparison chart

根據實驗的結果，隨著推薦興趣點數量的增加，推薦準確度（precision）逐漸降低，而召回率（recall）逐漸升高，實驗結果與實際應有趨勢相符。總體看來，本文提出的基于用戶活動區域劃分的元路徑興趣點推薦算法優于基于用戶簽到記錄計算用戶相似度的協同推薦算法和基于用戶共同好友計算用戶相似度的協同過濾推薦算法，具有更好的推薦效果。

4 總結

在對LBSN的異構網絡運用傳統的推薦方法進行興趣點推薦的過程中，因為數據的極度稀疏性或多或少存在一些局限性。本文提出的基于用戶活動區域劃分的元路徑推薦算法。首先，根據用戶簽到、點評地點呈現區域性，將用戶活動區域分為頻繁活動區域和不經常活動區域，根據LBSN結構特征構建用戶-活動區域、活動區域-興趣點之間的二分圖模型，其次引入元路徑，計算從用戶到興趣點的實例路徑的關聯度，最后根據實例路徑關聯度計算用戶到興趣點的概率，然后根據概率大小生成推薦列表。結果表明，該算法較傳統的推薦算法有更好的準確率和召回率。

本文仍然存在一些不足有待進一步加強，如果考慮上下文信息如時間、天氣、交通工具等因素，使得推薦結果更具個性化，達到用戶更滿意的效果。

[1] ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender system: A survey of the state-of-the-art and possible extensions. IEEE Transaction on Knowledge and Data Engineering, 2005, 17(6): 734-749.

[2] WANG D, PEDRESCHI D, SONG C M, et al. Human mobility social ties and link prediction. In Proc. of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011: 1100-1108.

[3] CHO E, MYERS S A, LESKOVEC J. Friendship and Mobility: user movement in location-based social networks. In Proc.of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011: 1082-1090.

[4] ZHENG Y, XIE X. Learning travel recommendation from user-generated GPS traces. ACM Transaction on Intelligent Systems and Technology(TIST), 2011, 2(1): 2-30.

[5] YE M, YIN P, LEE W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing, China, 2011: 325-334.

[6] 高榕, 李晶, 杜博等. 一種融合情景和評論信息的位置社交網絡興趣點推薦模型[J]. 計算機研究與發展, 2016,53(4): 752-763.GAO R, LI J, DU B, et al. An interest point recommendation model for location social network based on scenario and comment information[J]. Journal of Computer Research and Development, 2016, 53(4): 752-763.

[7] 陳志雄, 曾誠, 高榕. 一種基于位置社交網絡融合多種情景信息的興趣點推薦模型[J]. 計算機應用研究, 2017,34(10).CHEN Z X, ZENG C, GAO R. An interest point recommendation model based on location social network fusing multiple situational information[J]. Application Research of Computers, 2017, 34(10).

[8] CHENG C, YANG H Q, KING I, et al. Fused matrix factorization with geographical and social influence in location-based networks[C]//Proc of the 26th AAAI conf on Artificial Intelligence(AAAI’12). Menlo Park, CA: AAAI,2012: 211-276.

[9] LI Z, DING B, HAN J, et al. Mining periodic behaviors for moving objects. In proc. of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010: 1099-1108.

[10] PELECHRINIS K, KRISHNAMURTHY P. Location Affiliation Networks: Bonding Social and Spatial Information. In Proc. of the 2012 European conference on Machine Learning and Knowledge Discovery in Databases. 2012: 531-547.

[11] SUN Y, HAN J, YAN X, et al. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB(Very Large Data Base)Endowment, 2011, 4(11): 235-246

[12] MA H, KING I, LYU M R. Learning to recommendation with social trust ensemble. SIGIR, 2009: 189-196.

Recommendation of Meta Path Interest Points Based on Active Region Partition in LBSN

XU Ze-feng1, LIU Wen-ju2, WANG Ze2
(School of Computer Science and Software Technology, Tianjin Polytechnic University, Tianjin, 300387, China)

Location Based Social network (Location -based Social Networks, LBSN) recommended related services more and more, and the Point Of Interest (Point Of Interest, POI) is recommended as a personalized recommendation in LBSN related services also, much attention has been paid more and more scholars research on. At present, all kinds of location based recommendation algorithm emerge in endlessly, but due to data in LBSN extremely sparse, caused many recommended precision is not high, this paper proposes a meta-path recommendation algorithm based on user activity area partition. First of all, according to the users to sign in and comment on the location of the present regional, frequent user activity area can be divided into active area and not often activity area,according to the characters of LBSN structure building user interest points-activity area and activity area - the dichotomy between graph model, then introduce meta-path, calculated from the user to an instance of an interest point path correlation degree, according to the size of the correlation generated recommended list. The results show that this algorithm has better recommendation effect than traditional LBSN recommendation algorithm.

Location based social network; Division; meta-path; Point of interest recommend

TP389.1

A

10.3969/j.issn.1003-6970.2017.11.017

本文著錄格式：徐澤鋒，劉文菊，王賾. LBSN中基于活動區域劃分的元路徑興趣點推薦[J]. 軟件，2017，38（11）：85-89

徐澤鋒，男，碩士研究生，主要研究方向：推薦系統； 劉文菊，女，教授，主要研究方向：企業信息化、計算機網絡與安全；王賾，男，教授，主要研究方向：計算機網絡與安全、互聯網+應用、云網絡安全。

劉文菊，女，教授，主要研究方向：企業信息化、計算機網絡與安全。