袁 健,蔣 宇,孫 悅

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

1 引 言

近年來,基于位置的社交網(wǎng)絡(luò)(簡稱LBSN)得到了迅速發(fā)展.國外比較主流的LBSN有Foursquare、Gowalla和Brightkite等,國內(nèi)有滴滴、街旁和大眾點評等.LBSN中有大量的簽到數(shù)據(jù)(包括用戶,位置,相應(yīng)的簽到時間和好友關(guān)系等)現(xiàn)已被廣泛應(yīng)用于研究人員的移動性問題中,其中如何將歷史簽到數(shù)據(jù)進行用戶位置預(yù)測是目前的研究熱點.若有高效的用戶位置預(yù)測方法將極大改善用戶的體驗.

當前與用戶位置預(yù)測相關(guān)的研究主要有兩種:對用戶家庭住址的位置預(yù)測和對用戶在未來的一段時間內(nèi)可能簽到的位置預(yù)測.對用戶未來可能簽到位置的預(yù)測又分為短期位置預(yù)測(數(shù)分鐘后、數(shù)天或數(shù)周后)和長期位置預(yù)測(數(shù)月乃至數(shù)年).本文研究的是對用戶在較短時間內(nèi)可能的簽到位置進行預(yù)測,該研究可以充分描述用戶的活動區(qū)域,從而精準地為用戶提供個性化推薦服務(wù);商家也可以通過短期位置預(yù)測獲得附近的人群用戶畫像,從而做出更精準的廣告投放或商業(yè)活動決策.

2 相關(guān)工作

對人類移動行為分析以及預(yù)測一直備受國內(nèi)外學(xué)者的關(guān)注.在移動設(shè)備還沒有普及的時候,研究者們只能采用GPS設(shè)備針對用戶移動的軌跡數(shù)據(jù)進行研究[1,2],其軌跡論證了用戶的歷史簽到數(shù)據(jù)對預(yù)測用戶將來所處位置的重要作用.Sch?nfelder[3],M.Ye[4]和 Li W[5]等人,通過對用戶的歷史簽到數(shù)據(jù)的研究,發(fā)現(xiàn)用戶將來所處的位置在固定的周期內(nèi)呈現(xiàn)很強的相似性,可建立模型對用戶將來出現(xiàn)的位置進行預(yù)測.

在早期,由于移動互聯(lián)網(wǎng)沒有普及,對位置預(yù)測的研究并未將社交關(guān)系這一因素考慮在內(nèi).故此類模型[2,5,6]存在預(yù)測結(jié)果精度低的問題.

隨著移動設(shè)備的普及和LBSN的蓬勃發(fā)展,新興的研究更多地從LBSN中的簽到數(shù)據(jù)[7-9]切入.其簽到數(shù)據(jù)可以有精確的簽到時間、簽到位置經(jīng)緯度信息以及用戶的社交關(guān)系,還可以對簽到位置標注相應(yīng)的功能標簽,以便于從多個維度對用戶的簽到行為進行挖掘.

Chang等人[10]利用Facebook公開的數(shù)據(jù)集,考慮用戶簽到的歷史位置,相似功能標簽地點,人口分布以及好友等因素,研究影響用戶在未來可能簽到的位置的特征因子,通過這些組合的特征因子對用戶未來可能的簽到地點進行預(yù)測,并采用邏輯回歸算法對多個維度進行組合,預(yù)測用戶即將簽到的位置,取得了不錯的效果.但是對于非線性特征,需要進行轉(zhuǎn)換,當特征空間很大時,邏輯回歸的性能不是很好.Gao等人[8]提出將社交關(guān)系和用戶歷史記錄綜合考慮的模型,訓(xùn)練出一個數(shù)學(xué)統(tǒng)計模型來預(yù)測用戶下一次的簽到可能發(fā)生的地點,并分析用戶簽到的歷史信息和好友簽到歷史信息兩者之間的關(guān)聯(lián)性作為社交影響因素加入統(tǒng)計模型.但是該模型需要依賴大量的訓(xùn)練數(shù)據(jù),并且構(gòu)造模型的時空消耗非常大.Ying等人[11]提出了一種UPOI-Mine模型,該模型融合了社交網(wǎng)絡(luò)關(guān)系,用戶個人偏好和人口等因素來預(yù)測用戶在將來可能的簽到位置,通過輸出一個POI評分來對簽到位置的可能性大小進行描述.最后通過建立決策樹模型對Gowalla數(shù)據(jù)集[12]中數(shù)據(jù)進行實驗.但是,該模型割裂了時間序列對位置預(yù)測的影響,而且由于數(shù)據(jù)集的原因?qū)€人偏好特征挖掘不充分.Lv[13]等人提出了基于多維混合特征的位置預(yù)測算法,但是該模型的泛化性較差,對訓(xùn)練的數(shù)據(jù)集產(chǎn)生過擬合,并且模型的準確率和召回率不夠高.Li 等人[14]分析了用戶簽到地點與時間變化之間的規(guī)律,考慮用戶的長期和短期的偏好因素,提出一種基于時間的興趣點預(yù)測算法,但是該模型依賴個體的偏好因素,沒有考慮用戶簽到位置受社交群體因素的影響.

綜上所述基于LBSN的用戶短期位置預(yù)測的研究面臨著如下問題.首先,簽到數(shù)據(jù)維度高但呈現(xiàn)稀疏性,且現(xiàn)有的研究模型預(yù)測的位置結(jié)果對訓(xùn)練樣本很敏感,泛化性較差;其次,數(shù)據(jù)特征的提取與應(yīng)用往往存在局限,預(yù)測的準確度不高.為此,本文針對用戶短期位置預(yù)測問題提出了基于改進隨機森林算法的LBSN用戶短期位置預(yù)測模型-short-termpositionpredictionmodelforLBSNusersbasedonimprovedrandomforestalgorithm(以下簡稱SPMLIRFA).該模型將位置預(yù)測問題看作是一個分類問題,首先對LBSN中的時間、空間、個人社交因素和社交群體的位置的熱門程度等關(guān)鍵特征進行量化,然后應(yīng)用提出的基于Fisher判別函數(shù)的過濾型特征選擇方法進行特征分區(qū),最后通過分類判斷用戶是否在給定時間在候選位置進行簽到從而實現(xiàn)用戶位置的預(yù)測.實驗結(jié)果證實了該模型對于預(yù)測用戶的短期簽到位置具有更好的泛化性和準確率.

3 相關(guān)定義

定義1.G,表示LBSN模型.其中U表示用戶集合,V表示位置集合,E表示邊緣集合,C表示歷史簽到集合.

定義2.Bootstrap(自助抽樣法),是從給定訓(xùn)練集中抽取后又放回的均勻抽樣的方法.

定義4.ri(t),i∈{d,w},表示不同模式下以小時為粒度切分的時間點集合.當i=d時表示日模式下的時間點集合,即rd(t)={1,2,…23}.當i=w時表示周模式,rw(t)={0,1,2,…,167}.

4 SPMLIRFA算法

4.1 隨機森林算法

隨機森林算法思路是利用Bootstrap采樣生成n個訓(xùn)練樣本;隨機抽取樣本數(shù)據(jù)中的k個相關(guān)屬性,依據(jù)最小熵原則分裂屬性構(gòu)建一顆CART決策樹[15];然后,不斷地重復(fù)上述操作直至構(gòu)建m棵CART樹;將這m棵決策樹看成一個整體,構(gòu)建出一個隨機森林.

隨機森林具有結(jié)構(gòu)簡單,構(gòu)建速度快的特點,能夠有效克服過擬合的特點,因此完全適合對用戶簽到行為進行預(yù)測.雖然隨機森林能夠做到對所有屬性無差別的隨機抽取,但是一旦樣本有著大量的屬性并且存在著對分類結(jié)果影響較小的屬性,隨機抽取的特征的質(zhì)量將低于有導(dǎo)向性抽取出的特征.

4.2 SPMLIRFA算法

隨機森林算法是一種組合型分類算法,它采用分類回歸樹(CART)作為基分類器來構(gòu)建分類模型,主要用在分類預(yù)測問題上.標準的隨機森林算法選擇特征是完全隨機的,因此任何一個特征被抽取到的概率都是相同的,然而,在實際情況下,不同的特征對最終分類結(jié)果的影響程度是不同的.本文對隨機森林算法進行了改進,將其應(yīng)用于LBSN用戶的短期位置預(yù)測,提出了SPMLIRFA模型.

SPMLIRFA將位置預(yù)測問題看作是一個分類問題,利用簽到數(shù)據(jù),在現(xiàn)有相關(guān)研究的基礎(chǔ)上,先將時間因素,空間因素,個人社交因素和社交群體的簽到地點熱門因素進行量化,將Fisher判別函數(shù)值(簡稱Fisher比)來衡量特征的重要程度,訓(xùn)練樣本則按照特征重要程度劃分的比例來采樣,訓(xùn)練生成多個決策樹后分類預(yù)測位置,從而實現(xiàn)LBSN中用戶位置的預(yù)測.

4.2.1 特征量化

1)周特征量化值Week_loc.

周模式下,給定用戶u和時間tgiven∈ri(t),i∈{d,w},該用戶的歷史簽到集合為Cu,其在歷史簽到集合中的t時刻表示為rw(c,t),c∈Cu.給定的候選位置Vcandidate的特征量化值Week_loc定義如公式(1):

(1)

2)日特征量化值Day_loc.

同周模式,給定的候選位置Vcandidate的日特征量化值的定義如公式(2),其中rd(tgiven)表示日模式下的一個給定時間,rd(c.t)表示給定用戶u在歷史簽到集合中日模式下t時刻.

3)空間特征量化值Distance.

(2)

空間特征量化值Distance的定義如公式(3)所示.

Distance]dist(Vcandidtae,center)

(3)

其中dist(vi,vj)表示從位置vi到位置vj的距離,center表示該用戶的簽到中心,本文選取該用戶所有簽到位置集合的經(jīng)緯度的均值作為其簽到中心的位置.

4)個人社交因素特征量化值Friendship.

個人社交因素特征量化值Friendship的定義如式(4):

(4)

其中weightu′代表好友u′對用戶u影響的權(quán)重,其取值正比于用戶u′和u所在歷史集合中共同的簽到位置數(shù)量,取值范圍為[0,1],P(Cu′=vcandidate)是好友u′在候選地點Vcandidate的簽到頻率,Fu代表用戶u的好友集合.

5)簽到地點熱門程度特征量化值fpop(p).

利用Gowalla數(shù)據(jù)集(公開的LBSN簽到數(shù)據(jù)集),本文對用戶社交群體在連續(xù)簽到的熱門位置距離的概率密度進行了研究.圖1為Gowalla數(shù)據(jù)集中所選的相鄰連續(xù)簽到位置的概率密度的情況.其中點表示Gowalla數(shù)據(jù)集中所有存在的連續(xù)簽到位置的分布情況(共約5萬個點).

若設(shè)定用戶u其社交群體(所有好友)的簽到位置的熱門程度的概率密度p服從冪率分布[16],其冪律分布的概率密度fpop(p)如公式(5)所示.

fpop(p)=(β-1)(p+1)-β,p≥0,β>1

(5)

其中,β是從簽到頻率矩陣中使用極大似然法[17]計算得出的值.如公式(6)所示.

(6)

其中,L代表簽到位置的集合,l,l′表示某用戶群體在歷史簽到集合中任意兩次連續(xù)簽到的位置,Rl′,l表示兩個簽到地點的經(jīng)緯度坐標計算出的空間距離的函數(shù)[18].

圖1 連續(xù)簽到熱門地點空間距離與概率密度分布Fig.1 Continuous sign-in to popular location space distance probability density distribution

按公式(5)在圖1中繪出圖形得到一直線,從圖中可看出數(shù)據(jù)集中的連續(xù)簽到熱門地點距離的概率密度和公式(5)的冪律分布較為近似,因此假設(shè)用戶的社交群體的簽到地點熱門程度特征量化值符合冪律分布,用fpop(p)表示.

4.2.2 SPMLIRFA模型主要步驟

SPMLIRFA模型的核心思想是先從數(shù)據(jù)集中自助取樣得到多個樣本,計算出各個樣本的特征重要程度的值(即Fisher比)并求得均值;再將樣本的特征根據(jù)重要程度的均值分區(qū):重要特征區(qū)和次要特征區(qū).然后,根據(jù)特征重要程度的值按照比例分別抽取不同分區(qū)特征組合成該樣本的特征子空間,再根據(jù)每個樣本的特征子空間構(gòu)造決策樹.接著對決策樹構(gòu)成的森林采用隨機森林算法進行投票分類,再根據(jù)分類結(jié)果進行用戶位置預(yù)測.SPMLIRFA模型的總體流程如圖2所示.

圖2 SPMLIRFA模型的總體流程圖Fig.2 SPMLIRFA model process

算法模型的主要步驟如下:

1)Bootstrap采樣

通過Bootstrap采樣從原始數(shù)據(jù)集抽取k個自助樣本集.

2)特征分區(qū)

(7)

(8)

(9)

則屬于第w個分類的所有樣本中第r維特征的Fisher比Fr可表示為公式(10).

(10)

(11)

(12)

NS+NW=n

(13)

3)分區(qū)采樣

如公式(14),公式(15),在抽取樣本特征時,分別隨機從FS區(qū)和FW區(qū)抽取出mS和mW個特征并將其組合,構(gòu)造成mtry維的特征子空間.

(14)

(15)

4)構(gòu)造樣本的決策樹

對于自助樣本集和每個樣本集對應(yīng)的mtry維特征子空間,以當前節(jié)點的熵值最小為特征選擇基準,選擇相應(yīng)的特征來分裂節(jié)點,若節(jié)點具有最小的熵值,即由該節(jié)點分類出的所有輸入只有一種分類結(jié)果,則該節(jié)點為決策樹的葉子節(jié)點.生成k個決策樹,構(gòu)成隨機森林[19].

5)投票分類

將測試數(shù)據(jù)集輸入至上面隨機森林,統(tǒng)計每一棵CART分類樹的分類結(jié)果,按照最大投票法[19]得出分類結(jié)果,作為模型的預(yù)測結(jié)果.

5 實驗與分析

5.1 實驗環(huán)境和數(shù)據(jù)集

實驗所用的數(shù)據(jù)集是知名的LBSN簽到數(shù)據(jù)集Gowalla[12].其中,選取數(shù)據(jù)的時間范圍為2010年1月到2012年1月,總計抽取其中的約600萬條簽到記錄作為訓(xùn)練集.篩選時間范圍為2012年2月的部分數(shù)據(jù)作為實驗的測試集(實驗假設(shè)個人社交因素在訓(xùn)練集和測試集的時間維度上是不變的).其中篩選規(guī)則為:對于在訓(xùn)練集上的每個用戶,若該用戶存在2012年2月的簽到記錄且該次簽到的地點屬于訓(xùn)練集的地點集合,則該條記錄滿足篩選條件.實驗前,先對數(shù)據(jù)集進行數(shù)據(jù)清洗與過濾,剔除了簽到記錄較少的不活躍用戶(簽到記錄數(shù)少于15條),去除了原始簽到記錄中不必要的信息如簽到商戶信息等,只保留本文研究的特征信息:時間戳,地理經(jīng)緯度,好友關(guān)系和地理位置總簽到次數(shù);然后清洗了一些缺失必要信息的簽到記錄,如簽到時間戳缺失,簽到經(jīng)緯度缺失的記錄;與此同時,剔除了一些明顯不合理的數(shù)據(jù),如經(jīng)緯度超出范圍的簽到記錄.最后經(jīng)過預(yù)處理后的數(shù)據(jù)集大致信息如表1所示.

實驗將原始數(shù)據(jù)集中的數(shù)據(jù)格式化至mysql數(shù)據(jù)庫,分別將簽到記錄,好友關(guān)系和簽到地點存至三張對應(yīng)的表中,表的信息如表2,表3,表4所示.實驗的機器CPU為intel(R)Core(TM)i5-3320M 2.6GHz,運存大小為6GB,操作系統(tǒng)為windows 7 sp1,代碼基于matlab 10和python 2.7,其中,數(shù)據(jù)的預(yù)處理環(huán)節(jié)和Fisher比計算使用python完成,再將由python抽樣得出的自助樣本集和計算出的樣本集對應(yīng)的特征子空間作為參數(shù)傳入基于matlab提供的隨機森林工具包(Windows-Precompoiled-RF_MexStandalone)構(gòu)建的代碼中,訓(xùn)練生成隨機森林.

表1 數(shù)據(jù)集信息
Table 1 Data set information

數(shù)據(jù)集簽到記錄數(shù)好友關(guān)系數(shù)地點數(shù)Gowalla5970244950523158345

表2 簽到記錄表
Table 2 Check-in record

屬性含義UserId簽到用戶idCheck-intimestamp簽到時間戳Latitude簽到地點經(jīng)度Longitude簽到地點緯度LocateId簽到點id

表3 好友關(guān)系表
Table 3 Friend relationship

屬性含義User1用戶1的idUser2用戶2的id

表4 簽到地點表
Table 4 Check-in location

屬性含義LocateId簽到點idcheckInNum總簽到次數(shù)

5.2 評估指標

5.2.1 準確率

準確率[20]表明了用戶真正簽到位置在所有預(yù)測結(jié)果中所占的比例.其中對于用戶u,R(u)表示算法的預(yù)測簽到位置集合,T(u)表示測試數(shù)據(jù)集中用戶u實際簽到的位置,準確率的公式如公式(16).

(16)

5.2.2 召回率

召回率[20]表示的是用戶實際簽到的位置在預(yù)測候選位置中所占的比例,召回率的表示如公式(17).

(17)

5.3 結(jié)果分析

5.3.1 SPMLIRFA和隨機森林(RFPA)算法比較

SPMLIRFA中的核心算法是本文提出的改進的隨機森林算法.下面對SPMLIRFA與基于隨機森林的用戶位置預(yù)測模型(簡稱RFPA)在測試集上的預(yù)測準確度和召回率進行了對比實驗,以下實驗得到的準確率和召回率均為相同訓(xùn)練集和測試集條件的20次實驗結(jié)果的平均取值.

1)準確率

從圖3可以看出,選取200個樣本生成200個決策樹的情況下,隨著原始數(shù)據(jù)集的規(guī)模越來越大,RFPA和SPMLIRFA的準確率呈現(xiàn)上升的趨勢,這表明兩者的分類的準確率都是隨著訓(xùn)練數(shù)據(jù)的變大而變好.在相同的樣本個數(shù)下,SPMLIRFA在準確率上基本優(yōu)于RFPA,并且,由于隨機森林算法的泛化性強,SPMLIRFA的實驗結(jié)果也做到了較為穩(wěn)定的準確率,而不會出現(xiàn)過分擬合的情況.

圖3 模型預(yù)測準確率-原始數(shù)據(jù)集規(guī)模大小折線圖Fig.3 Forecast accuracy-original dataset scale line chart

2)召回率

從圖4可以看出,選取200個樣本生成200個決策樹的情況下,隨著位置候選點的個數(shù)越來越大,RFPA和SPMLIRFA的召回率呈現(xiàn)上升的趨勢,這表明兩者的分類召回的效果都隨著候選點的個數(shù)的增加而變好.其次,在候選點個數(shù)相同的情況下,SPMLIRFA的召回率高于RFPA.同樣的,隨機森林算法的強泛化性也在圖4中得到了體現(xiàn).

圖4 模型預(yù)測召回率-位置候選點個數(shù)折線圖Fig.4 Predicted recall rate-candidate point location line chart

5.3.2 SPMLIRFA和LPMMF等算法比較

選擇對比LPMMF[13],UPOI-Mine[11],MFT-D[8]和MFT-W[8].其中LPMMF模型是一種融合了多個維度特征的位置預(yù)測模型,其使用邏輯回歸模型融合時間和空間等特征來預(yù)測用戶在給定的候選位置集合中出現(xiàn).UPOI-Mine是一個融合了個人偏好因素,社交因素和興趣點流行度因素的地點推薦模型,并且采用了決策樹回歸的方式預(yù)測結(jié)果.MFT-D和MFT-W是在文獻[8]中提出的對比基準算法,這兩個算法模型認為用戶在相同的時間模式的情況下,用戶在某候選位置簽到的概率和該用戶在歷史簽到記錄中在該位置簽到的頻率強相關(guān).SPMLIRFA的20次平均實驗結(jié)果與這三個算法模型的實驗對比原始訓(xùn)練集都為抽取的Gowalla數(shù)據(jù)集中5970244條簽到數(shù)據(jù).SPMLIRFA模型在200個決策樹的條件下(即抽取200個樣本),選取的位置候選點個數(shù)為17個,同時,在LPMMF中選取的備選位置的個數(shù)也為17個,UPOI-Mine中推薦列表的大小也是17.

1)準確率

由圖5可以看出,MFT-D和MFT-W在準確率上都要低于基于多維的特征算法模型SPMLIRFA和LPMMF,這表明用戶未來簽到的位置取決于多個因素的影響,UPOI-Mine模型因未考慮時間這一重要因素,且沒有對挖掘到的特征作出導(dǎo)向性的特征選擇,實驗得出的結(jié)果和只考慮單一的時空特征的模型MFT-D和MFT-W得出的結(jié)果相似,而融合了時間特征,空間特征,社交關(guān)系等多維特征的算法模型的效果明顯好于單一特征的算法模型.同時,觀察到SPMLIRFA算法模型在準確度上也優(yōu)于LPMMF,這證明,SPMLIRFA算法在特征因素的選取考慮、量化以及重要性劃分上的工作優(yōu)于LPMMF.

圖5 模型準確率對比圖Fig.5 Comparison of model accuracy ratio

2)召回率

由圖6可以看出,在召回率的對比中,SPMLIRFA依然是幾個算法中表現(xiàn)最好的,而LPMMF的召回率表現(xiàn)出一定的差距,這表明,LPMMF的在泛化性上也是不如SPMLIRFA的.

圖6 模型召回率對比圖Fig.6 Comparison of model recall rate

6 結(jié)束語

本文研究了LBSN中的用戶短期位置預(yù)測問題.并將其看成是一個是否在候選位置簽到的分類問題,模型以時間周期特征,空間距離特征,社交群體特征和簽到位置的熱門特征作為分類特征.然后以特征的量化值為依據(jù),建立特征的重要性度量體系(Fisher比),將帶有重要性度量的特征空間參與到隨機森林的訓(xùn)練過程中去.實驗結(jié)果表明,本文提出的SPMLIRFA算法模型具備隨機森林算法的優(yōu)秀的泛化能力,在位置預(yù)測方面有著穩(wěn)定的準確率和召回率,并且由于特征的重要性度量的引入,相比較現(xiàn)有的一些算法模型,在準確率上也具備相應(yīng)的提升.以后打算把用戶的動態(tài)偏好納入用戶的位置預(yù)測模型進行研究.此外,未來將研究來源于多種異構(gòu)網(wǎng)絡(luò)的信息的融合,這將有助于提高位置預(yù)測的準確率和性能.