基于地理標(biāo)簽的LBSN鏈接預(yù)測模型①

王 勇,王 超,程 凱

1(銅陵有色金屬集團(tuán)股份有限公司金冠銅業(yè)分公司,銅陵 244000)

2(金誠信礦業(yè)管理股份有限公司,北京 100044)

3(北京宸控科技有限公司,北京 102200)

隨著智能手機(jī)的爆炸式發(fā)展,用戶可隨時隨地在各大社交平臺分享自己的地理位置信息.無論是視頻、圖片或文本信息,都可輕易地嵌入當(dāng)前用戶的地理位置標(biāo)簽(Location Tag).大量的位置Tag構(gòu)成了基于地理位置的社交網(wǎng)絡(luò)[1](Location-Based Social Networks,LBSN),結(jié)合現(xiàn)有的各種定位系統(tǒng),可以為用戶提供一些個性化服務(wù).根據(jù)LSBN中已經(jīng)存在的鏈接和節(jié)點(diǎn)信息,可以預(yù)測出用戶位置網(wǎng)絡(luò)中遺失的Tag或即將出現(xiàn)的Tag鏈接,該方法稱之為鏈接預(yù)測[2].例如,在微博、微信等社交平臺中,用戶等同于節(jié)點(diǎn),鏈接預(yù)測可用于建立新的好友關(guān)系.

文獻(xiàn)[3]表明,同一時間出現(xiàn)在同一位置的用戶成為好友的概率要遠(yuǎn)高于處于不同地理位置的用戶.因此,挖掘LBSN中潛在的標(biāo)簽信息對實(shí)現(xiàn)鏈接預(yù)測具有重大意義.目前,國內(nèi)外已有很多科研工作者專注于基于地理位置標(biāo)簽的推薦算法研究,判斷用戶地理位置的途徑主要有兩種:第一,挖掘用戶發(fā)布到互聯(lián)網(wǎng)中的內(nèi)容信息可推斷出用戶的地理位置信息[4].第二,通過社交平臺中好友的地理位置推測用戶的位置[5].近年來也有很多學(xué)者研究基于LDA主題建模的層次聚類[6]、無監(jiān)督學(xué)習(xí)[7]、標(biāo)簽關(guān)聯(lián)[8]推薦算法.為提高位置預(yù)測的準(zhǔn)確性,可對用戶位置信息進(jìn)行篩選,過濾掉無用的信息.還可對用戶簽到信息建立LDA主題生成模型,分析地理位置標(biāo)簽的特征,設(shè)計出基于地理位置的推薦系統(tǒng)[9].

從用戶簽到信息中提取出時間特征和位置特征對于鏈接預(yù)測算法至關(guān)重要,因?yàn)檫@些特征可用于評估用戶之間的相似度,進(jìn)而提高預(yù)測的準(zhǔn)確度.然而實(shí)際的LBSN簽到信息中,地理位置的分布十分稀疏,想要挖掘出位置和時間信息相當(dāng)困難.基于用戶地理位置標(biāo)簽,本文建立了新的LBSN鏈接預(yù)測模型,提高了鏈接預(yù)測的準(zhǔn)確度.首先,本文對Gowalla數(shù)據(jù)集進(jìn)行聚類分析,改善了地理位置分布的稀疏性問題.其次,本文對用戶地理位置標(biāo)簽進(jìn)行語義分析,建立基于用戶地理標(biāo)簽的LDA主題模型,采用Gibbs抽樣算法進(jìn)行參數(shù)估算,分析出用戶的地理位置標(biāo)簽的相似性特征.最后,本文綜合網(wǎng)絡(luò)結(jié)構(gòu)相似性特征和基于用戶地理位置信息的相似度特征,采用有監(jiān)督策略的鏈接預(yù)測在Gowalla數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,本文提出的模型能有效提高LBSN的鏈接預(yù)測準(zhǔn)確度.

1 基于地理位置的 LDA 主題模型

本文對LBSN中的用戶地理位置標(biāo)簽建立LDA主題模型,以便挖掘出用戶的行為偏好.用戶的位置標(biāo)簽集合可當(dāng)作一篇文檔,位置標(biāo)簽集合中的某條具體位置相當(dāng)于構(gòu)成文檔的詞匯.對該主題模型進(jìn)行求解,可得出用戶地理位置標(biāo)簽中隱藏的主題分布和地理標(biāo)簽主題下的位置分布.

假定用戶u對應(yīng)的地理位置標(biāo)簽集合為相當(dāng)于一篇文檔,其中m代表用戶u的位置標(biāo)簽條數(shù),wu,i代表用戶u的第i(1≤i≤m)條位置標(biāo)簽信息,相當(dāng)于構(gòu)成文檔的某個詞匯.地理位置文檔集合為,其中M代表用戶數(shù)量.假定具體的位置數(shù)量為V,則可建立基于地理位置的LDA主題模型,如圖1所示.

圖1 基于地理位置的 LDA 主題模型

模型中的位置主題概率分布可用Gibbs[10]采樣算法估算得出,該分布可用一個 doc-topic矩陣來描述,用戶u在地點(diǎn)主題tk下出現(xiàn)的概率分布可表示為.同理,每個位置主題下對應(yīng)的位置概率分布可用一個topic-word矩陣來描述,其中 pk(φv)代表位置v在主題k下出現(xiàn)的概率.

2 基于位置信息的相似度分析

2.1 位置信息語義化

本文實(shí)驗(yàn)使用的數(shù)據(jù)集是Gowalla的地理位置標(biāo)簽數(shù)據(jù)集,可從SNAP官網(wǎng)直接下載得到,用戶地理位置標(biāo)簽的存儲格式為:

Checkini,j表示用戶i的第j條位置信息.此外,該數(shù)據(jù)集還記錄了用戶之間的好友關(guān)系.具體示例見表1和表2.

表1 地理位置標(biāo)簽格式

表2 用戶好友關(guān)系存儲格式

由于數(shù)據(jù)集并沒有具體的地理語義信息,故需要先對其進(jìn)行語義化.本文采用百度公司免費(fèi)的Place API和 Geocoding API進(jìn)行語義轉(zhuǎn)換,可將數(shù)據(jù)集中的地理坐標(biāo)轉(zhuǎn)換為具體的地址以及附近的POI (Point Of Interest)信息.

由于很多用戶只在某一個地點(diǎn)簽到過,或跟其他用戶沒有共同的簽到地點(diǎn),這類用戶稱之為孤點(diǎn)用戶.大量的孤點(diǎn)用戶造成了數(shù)據(jù)的稀疏性,嚴(yán)重影響鏈接預(yù)測的準(zhǔn)確性.為解決該問題,本文降低了具體地點(diǎn)的限制,對地點(diǎn)標(biāo)簽進(jìn)行層次聚類,以簽到區(qū)域來構(gòu)建用戶關(guān)系網(wǎng)絡(luò).設(shè)定一個距離閾值 δ,若不同簽到地點(diǎn)的距離不超過該值,則認(rèn)為兩個地點(diǎn)屬于一個區(qū)域,本文在實(shí)驗(yàn)章節(jié)會對該參數(shù)進(jìn)行調(diào)優(yōu)試驗(yàn).然后利用該距離閾值對簽到數(shù)據(jù)集進(jìn)行聚類,可得到區(qū)域集合D={d1,d2,···,dn},由此可得到區(qū)域矩陣:

式(1)中的di,j代表第i個用戶在區(qū)域j處的簽到.顯然,利用區(qū)域矩陣來構(gòu)建用戶網(wǎng)絡(luò)關(guān)系可極大地減小孤點(diǎn)用戶的數(shù)量,對簽到地點(diǎn)標(biāo)簽信息的挖掘也更充分,因此可降低數(shù)據(jù)稀疏性的影響.

2.2 基于位置信息的相似度分析

上文提到,采用Gibbs采樣算法可估算出LDA主題模型中的兩個概率分布:位置主題分布 Θ和所有主題下的地理位置分布 Ψ .每個用戶的簽到主題分布可以表示成K個位置主題的概率組合,所有用戶的簽到主題分布構(gòu)成矩陣 Θ.每個主題下的位置分布可以表示為簽到位置的概率組合,所有主題下的簽到位置分布構(gòu)成矩陣 Ψ .利用本文的簽到語義數(shù)據(jù)集,Gibbs采樣可輸出矩陣 Θ 和Ψ .

本文首先篩選出位置主題概率最大的K個主題來表達(dá)用戶的位置主題.K的取值可按照經(jīng)驗(yàn)預(yù)設(shè),剩下的主題概率可先置0.本文先設(shè)定K=5,在模型學(xué)習(xí)的過程中會對K值進(jìn)行不斷的修正.然后對這K個地理位置主題分布函數(shù)進(jìn)行歸一化處理,如公式(2)所示:

對于兩個不同用戶產(chǎn)生的概率分布函數(shù),需要計算出二者之間的距離.統(tǒng)計學(xué)中的KL 散度(KLDivergence)可用于測量不同概率分布的差異,被廣泛應(yīng)用于基于LDA的推薦算法.然而KL散度并不適用于本文基于地理位置標(biāo)簽的鏈接預(yù)測算法,因?yàn)樵摲椒ň邆浞菍ΨQ性特征.如果兩個用戶對某主題都無興趣,KL散度得出的結(jié)論是這兩個用戶具有很高的相似性.同理,如果兩個用戶都沒有在某個地點(diǎn)簽到,那么KL散度會認(rèn)為他們具有很高的相似度,這顯然會造成極大的誤差.因此,本文采用一種新的方法來評估用戶之間地理位置主題的差異性.用戶i在k個地理位置主題下的位置總數(shù)設(shè)為N(i,tk),則不同用戶x,y之間的相似度可用公式(3)計算得到:

其中,分子代表用戶x和y在k個主題下的位置總數(shù)最小值之和,該值越大,說明用戶x和y在同一區(qū)域簽到的數(shù)量越大,二者的相似度越高.式(3)進(jìn)行了歸一化處理,最終結(jié)果可用于計算用戶之間的相似度.

最后,為了驗(yàn)證fW(x,y)的有效性,基于從當(dāng)前數(shù)據(jù)集中獲取的網(wǎng)絡(luò)關(guān)系,本文將對比分析和fW(x,y)的性能.LBSN鏈接網(wǎng)絡(luò)中基于fW(x,y)的好友用戶對與非好友用戶對的累積分布圖(CDF)如圖2所示.

從圖2可看出,基于位置標(biāo)簽語義分析的用戶相似性特征fW(x,y)能夠有效地識別好友與非好友的區(qū)別.因此可得出結(jié)論,fW(x,y)對于分析用戶之間的鏈接預(yù)測具有重要意義.

3 基于地理標(biāo)簽的LBSN鏈接預(yù)測模型

3.1 實(shí)現(xiàn)方法

本文通過對用戶地理位置信息的充分挖掘,得出了基于地理位置語義分析的相似性特征.這是本文所提出的鏈接預(yù)測模型的基礎(chǔ).機(jī)器學(xué)習(xí)中的監(jiān)督式學(xué)習(xí)算法經(jīng)常被用于推薦系統(tǒng)的設(shè)計,將收集到的海量訓(xùn)練數(shù)據(jù)集作為先驗(yàn)知識,建立一個模型,并根據(jù)輸入的標(biāo)簽不斷修正該模型,最終該模型可針對新的輸入預(yù)測出相應(yīng)結(jié)果.本文的鏈接預(yù)測算法基于有監(jiān)督學(xué)習(xí)的思想,輸入為Gowalla數(shù)據(jù)集中的位置標(biāo)簽,建立用戶特征向量函數(shù),對其進(jìn)行模型訓(xùn)練,最終可用于鏈接預(yù)測.

圖2 fW(x,y)好友與非好友用戶的CDF曲線

接下來,本文將采用有監(jiān)督學(xué)習(xí)的策略對其進(jìn)行鏈接預(yù)測.實(shí)驗(yàn)中,LBSN鏈接預(yù)測采用Gowalla數(shù)據(jù)集進(jìn)行仿真,使用LBSN基于地理位置語義分析的相似性特征進(jìn)行輔助實(shí)驗(yàn).本文實(shí)施的鏈接預(yù)測實(shí)驗(yàn)步驟如下:

(1)篩選原始數(shù)據(jù)集,過濾掉其中無用的冗余信息和獨(dú)立用戶(即無任何好友關(guān)系的用戶),最總得到一個可用的LBSN社交關(guān)系網(wǎng)絡(luò)圖G=(V,E).

(2)對集合E進(jìn)行隨機(jī)采樣,其中2/3的數(shù)據(jù)作為訓(xùn)練集ET,余下1/3的鏈接數(shù)據(jù)作為測試數(shù)據(jù)集EP,顯然E=ET+EP且ET∩EP=?.從集合ET中取出現(xiàn)有鏈接中所有的用戶集合V′∈V且V′≠V,則子網(wǎng)絡(luò)圖G′=(V′,E′).由V′可將測試數(shù)據(jù)集修正為EP=E′∩EP,所以空間集合 (V′×V′)-ET可用來表示一切隱含節(jié)點(diǎn)對的集合.

(3)由V′可得出所有用戶的位置標(biāo)簽列表,獲取這個列表集合中的地理位置信息,對其進(jìn)行聚類,最終得出一個新的用戶-位置矩陣.

(4)分析求解隱藏的用戶節(jié)點(diǎn)信息中基于地理位置的相似性特征fUP(x,y).

(5)同理,分析求解隱藏的用戶節(jié)點(diǎn)對基于時間戳的相似性特征fT(x,y).

(6)采用Gibbs抽樣算法估算出用戶基于地理位置主題的概率分布函數(shù),然后進(jìn)一步求解隱藏用戶節(jié)點(diǎn)對基于地理位置信息的用戶相似度特征fW(x,y).

(7)對社交網(wǎng)絡(luò)中所有隱藏用戶節(jié)點(diǎn)之間的相似度進(jìn)行分析計算,此處主要記錄預(yù)測性能最佳的Resource allocation (RA)系數(shù)指標(biāo)SRx,Ay.

(8)利用有監(jiān)督學(xué)習(xí)策略的算法,對上文計算得出的各類相似性特征做鏈接預(yù)測,最終可得出特征向量,然 后對其進(jìn)行模型訓(xùn)練,最后再對測試數(shù)據(jù)集進(jìn)行鏈接預(yù)測,得出基于地理標(biāo)簽的LBSN鏈接預(yù)測結(jié)果.最終得到的結(jié)果集中,用1標(biāo)注確實(shí)存在的鏈接節(jié)點(diǎn)信息,0標(biāo)注不存在鏈接的節(jié)點(diǎn)信息.

3.2 評估方法

將上文求解得到的結(jié)果集與測試數(shù)據(jù)集做對比,可分析出本文鏈接預(yù)測算法的性能.由于本文采用有監(jiān)督的鏈接預(yù)測算法,故采用信息檢索算法中常用的四大性能評估指標(biāo)來衡量本文算法的性能優(yōu)劣:精度(Accuracy)、準(zhǔn)確率(Precision)、召回率(Recall)以及綜合Accuracy和Precision的加權(quán)調(diào)和平均(F-measure).

由于實(shí)驗(yàn)數(shù)據(jù)中鏈接分布不均勻,本文還采用了一個新的評估指標(biāo) AUC(area under the receive operating characteristic curve)[11],如公式 (4)所示:

其中,n代表測試數(shù)據(jù)集中所有標(biāo)簽對被隨機(jī)獨(dú)立抽樣的次數(shù),對于鏈接節(jié)點(diǎn)對而言,包含了存在和不存在兩種情況.n′表示鏈接節(jié)點(diǎn)對存在時的相似度分?jǐn)?shù)大于不存在時的次數(shù),n′′則表示兩種情況相似度分?jǐn)?shù)相等的次數(shù).從上式可看出,若存在鏈接的相似度值大于不存在時,則相似度值加 1,若相等則加 0.5.因此,AUC 指標(biāo)能夠整體地評估鏈接預(yù)測模型的準(zhǔn)確度,其值得取值范圍是 (0 .5,1),AUC的值越大,表示鏈接預(yù)測模型的精準(zhǔn)度越好.

3.3 參數(shù)調(diào)優(yōu)

本文采用有監(jiān)督學(xué)習(xí)的方式對樣本進(jìn)行分類學(xué)習(xí),基于前人對的研究,我們可獲取關(guān)于類別特征的先驗(yàn)知識.基于已有的類別特征信息,可對模型進(jìn)行訓(xùn)練并構(gòu)造相應(yīng)的分類器.由于本文采用的是真實(shí)的Gowalla數(shù)據(jù)集,故存在樣本數(shù)據(jù)分布不均勻的情況.為深入挖掘該數(shù)據(jù)集中的隱藏信息,可采用機(jī)器學(xué)習(xí)中常用的k-折交叉驗(yàn)證 (k-fold cross Validation)法,該方法得到的實(shí)驗(yàn)結(jié)果更加真實(shí).實(shí)驗(yàn)證明,當(dāng)k值取10的時候可得到最佳的實(shí)驗(yàn)效果[12],故本文采取10倍交叉驗(yàn)證來評估模型的性能.

上文提到,本文利用有監(jiān)督的學(xué)習(xí)思想對模型中需要輸入的參數(shù)根據(jù)經(jīng)驗(yàn)預(yù)先給出,然后通過實(shí)驗(yàn)對其不斷修正.本文模型中有三個輸入?yún)?shù)需要進(jìn)行調(diào)優(yōu):對地理位置信息聚類處理時的距離閾值δ,基于用戶地理位置標(biāo)簽的LDA主題模型中的主題K的取值,以及分析用戶相似度時TOP-K中K的取值.

對距離閾值 δ分別取不同的值,可得到用戶基于地理位置標(biāo)簽的相似度特征函數(shù)fUP(x,y),現(xiàn)將該特征函數(shù)導(dǎo)入樣本分類器進(jìn)行鏈接預(yù)測,實(shí)驗(yàn)得出的距離閾值 δ與加權(quán)調(diào)和平均F值的關(guān)系如圖3所示.

圖3 距離閾值δ 對鏈接預(yù)測性能影響曲線

由圖3可知,當(dāng)鏈接預(yù)測距離閾值δ=500 m 時,鏈接預(yù)測的結(jié)果最優(yōu).當(dāng) δ ∈[400,700]時,該算法的鏈接預(yù)測效果較為良好.此外,隨著 δ的不斷增大,加權(quán)調(diào)和平均F值不斷減小,即距離越大,鏈接預(yù)測效果越差.當(dāng) δ ＞1km時,F值的值顯著降低,說明人與人之間的地理位置距離越遠(yuǎn),兩者之間的關(guān)系也會越生疏,該結(jié)論顯然符合人類社會客觀事實(shí).基于以上分析,本文對地理位置標(biāo)簽進(jìn)行層次聚類時的最優(yōu)距離閾值設(shè)定為500 m.

上文提到,基于地理位置的LDA主題模型可采用Gibb采樣算法進(jìn)行分析求解,最后得出用戶地理位置主題分布 Θ和每個主題下的具體地點(diǎn)分布 Ψ .根據(jù) Θ和Ψ這兩個概率分布函數(shù)計算出基于地理位置標(biāo)簽信息的相似性特征函數(shù)fW(x,y).Gibbs采樣算法需要預(yù)設(shè)的參數(shù)是 α,β 和K.其中,α和 β是Dirchlet先驗(yàn)分布的經(jīng)驗(yàn)參數(shù),由于在對數(shù)據(jù)進(jìn)行抽樣的過程中會不斷地更新 α和 β,因此這兩個值先根據(jù)經(jīng)驗(yàn)預(yù)設(shè)即可,本文設(shè)定 α =0.1,β=0.01.LDA主題模型中主題個數(shù)K值的選取十分重要,故本文對其進(jìn)行參數(shù)調(diào)優(yōu)實(shí)驗(yàn).分別對不同的K值計算基于地理位置標(biāo)簽信息的相似性特征函數(shù)fW(x,y),然后根據(jù)fW(x,y)進(jìn)行鏈接預(yù)測實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果如圖4所示,該圖展示了主題個數(shù)K和加權(quán)調(diào)和平均F值的關(guān)系.由圖可知,當(dāng)主題個數(shù)為13時鏈接預(yù)測性能最優(yōu),因此本文實(shí)驗(yàn)設(shè)定K=13.

圖4 主題個數(shù)K選取對預(yù)測性能影響曲線

為了以最低的時間復(fù)雜度計算出特征函數(shù)fW(x,y),并取得最優(yōu)的鏈接預(yù)測效果,本文將對地理位置標(biāo)簽主題進(jìn)行TOP-K選擇,然后根據(jù)選取的TOP-K個主題計算基于地理位置標(biāo)簽信息的相似性特征函數(shù)fW(x,y).實(shí)驗(yàn)結(jié)果如圖5所示,途中展示了TOP-K值與加權(quán)調(diào)和平均F值的關(guān)系.從圖中觀察到當(dāng)TOP-K≥10時,F值較高且相對平穩(wěn),而當(dāng)TOP-K=5時F值達(dá)到巔峰,故本文選取TOP-K=5進(jìn)行鏈接預(yù)測實(shí)驗(yàn).

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

本文在第3.3小節(jié)進(jìn)行了相關(guān)參數(shù)調(diào)優(yōu),接下來本文將使用開源的智能分析環(huán)境WEKA提供的幾種分類器對Gowalla數(shù)據(jù)集進(jìn)行鏈接預(yù)測實(shí)驗(yàn):樸素貝葉斯分類器(NB)、隨機(jī)森林分類器(RF)以及決策樹分類器(J48).分別對特征向量和單一的用戶網(wǎng)絡(luò)特征進(jìn)行實(shí)驗(yàn),并對比分析兩種不同算法的性能.采用的評估指標(biāo)是Precision、Recall、F-measure和AUC,這些指標(biāo)值是通過對比鏈接預(yù)測的實(shí)驗(yàn)結(jié)果和測試數(shù)據(jù)集中真是的數(shù)據(jù)作對比所得出的,如表3所示.

圖5 Top–K主題個數(shù)對預(yù)測性能的影響曲線

從表3中還可看出,以上兩個實(shí)驗(yàn)中鏈接預(yù)測性能優(yōu)劣為隨機(jī)森林算法優(yōu)于樸素貝葉斯算法,而樸素貝葉斯算法又優(yōu)于決策樹算法,單三者之間并無明顯差異,說明本文提出的算法具有良好的穩(wěn)定性,不同分類器對該算法的影響幾乎可以忽略不計.

表3 預(yù)測結(jié)果對比

表3 預(yù)測結(jié)果對比

分類器 樸素貝葉斯(N B)隨機(jī)森林(R F)決策樹(J 4 8)提升(%)提升(%)提升(%)f e a t u r e(x,y)?P r e c i s i o n0.9 2 0 8.6 0.9 2 1 8.6 0.9 1 8 8.5 R e c a l l0.7 5 9 4.1 0.7 6 2 4.2 0.7 5 8 4.1 F-m e a s u r e0.8 4 0 4.9 0.8 3 4 4.9 0.8 3 3 4.9 A U C 0.8 9 7.5 0.9 1 5 8.4 0.9 1 4 7.9 S R A x,y P r e c i s i o n0.8 4 7 0.8 4 9 0.8 4 8 R e c a l l0.7 2 9 0.7 3 0 0.7 2 9 F-m e a s u r e0.7 8 2 0.7 8 5 0.7 8 4 A U C 0.8 3 3 0.8 3 0 0.8 3 6

4 結(jié)論與展望

為解決地理位置分布的稀疏性問題,本文對測試數(shù)據(jù)集進(jìn)行聚類分析,并建立了基于用戶地理標(biāo)簽的LDA主題模型,分析出用戶的地理位置標(biāo)簽的相似性特征.最后,本文綜合了網(wǎng)絡(luò)結(jié)構(gòu)相似性特征和基于用戶地理位置信息的相似度特征,采用有監(jiān)督策略的鏈接預(yù)測在Gowalla數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,本文提出的模型能有效提高LBSN的鏈接預(yù)測準(zhǔn)確度,且具有良好的穩(wěn)定性.然而隨著互聯(lián)網(wǎng)的發(fā)展,LBSN的數(shù)據(jù)規(guī)模呈現(xiàn)指數(shù)級的增長,未來可進(jìn)一步研究基于大數(shù)據(jù)分布式平臺的鏈接預(yù)測算法.