基于地理標簽的LBSN鏈接預測模型①

王 勇,王 超,程 凱

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

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

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

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

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

從用戶簽到信息中提取出時間特征和位置特征對于鏈接預測算法至關重要,因為這些特征可用于評估用戶之間的相似度,進而提高預測的準確度.然而實際的LBSN簽到信息中,地理位置的分布十分稀疏,想要挖掘出位置和時間信息相當困難.基于用戶地理位置標簽,本文建立了新的LBSN鏈接預測模型,提高了鏈接預測的準確度.首先,本文對Gowalla數據集進行聚類分析,改善了地理位置分布的稀疏性問題.其次,本文對用戶地理位置標簽進行語義分析,建立基于用戶地理標簽的LDA主題模型,采用Gibbs抽樣算法進行參數估算,分析出用戶的地理位置標簽的相似性特征.最后,本文綜合網絡結構相似性特征和基于用戶地理位置信息的相似度特征,采用有監督策略的鏈接預測在Gowalla數據集上進行實驗.實驗結果表明,本文提出的模型能有效提高LBSN的鏈接預測準確度.

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

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

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

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

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

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

2.1 位置信息語義化

本文實驗使用的數據集是Gowalla的地理位置標簽數據集,可從SNAP官網直接下載得到,用戶地理位置標簽的存儲格式為:

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

表1 地理位置標簽格式

表2 用戶好友關系存儲格式

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

由于很多用戶只在某一個地點簽到過,或跟其他用戶沒有共同的簽到地點,這類用戶稱之為孤點用戶.大量的孤點用戶造成了數據的稀疏性,嚴重影響鏈接預測的準確性.為解決該問題,本文降低了具體地點的限制,對地點標簽進行層次聚類,以簽到區域來構建用戶關系網絡.設定一個距離閾值 δ,若不同簽到地點的距離不超過該值,則認為兩個地點屬于一個區域,本文在實驗章節會對該參數進行調優試驗.然后利用該距離閾值對簽到數據集進行聚類,可得到區域集合D={d1,d2,···,dn},由此可得到區域矩陣:

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

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

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

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

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

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

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

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

3 基于地理標簽的LBSN鏈接預測模型

3.1 實現方法

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

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

接下來,本文將采用有監督學習的策略對其進行鏈接預測.實驗中,LBSN鏈接預測采用Gowalla數據集進行仿真,使用LBSN基于地理位置語義分析的相似性特征進行輔助實驗.本文實施的鏈接預測實驗步驟如下:

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

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

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

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

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

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

(7)對社交網絡中所有隱藏用戶節點之間的相似度進行分析計算,此處主要記錄預測性能最佳的Resource allocation (RA)系數指標SRx,Ay.

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

3.2 評估方法

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

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

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

3.3 參數調優

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

上文提到,本文利用有監督的學習思想對模型中需要輸入的參數根據經驗預先給出,然后通過實驗對其不斷修正.本文模型中有三個輸入參數需要進行調優:對地理位置信息聚類處理時的距離閾值δ,基于用戶地理位置標簽的LDA主題模型中的主題K的取值,以及分析用戶相似度時TOP-K中K的取值.

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

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

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

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

圖4 主題個數K選取對預測性能影響曲線

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

3.4 實驗結果與分析

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

圖5 Top–K主題個數對預測性能的影響曲線

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

表3 預測結果對比

表3 預測結果對比

分類器 樸素貝葉斯(N B)隨機森林(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 結論與展望

為解決地理位置分布的稀疏性問題,本文對測試數據集進行聚類分析,并建立了基于用戶地理標簽的LDA主題模型,分析出用戶的地理位置標簽的相似性特征.最后,本文綜合了網絡結構相似性特征和基于用戶地理位置信息的相似度特征,采用有監督策略的鏈接預測在Gowalla數據集上進行實驗.實驗結果表明,本文提出的模型能有效提高LBSN的鏈接預測準確度,且具有良好的穩定性.然而隨著互聯網的發展,LBSN的數據規模呈現指數級的增長,未來可進一步研究基于大數據分布式平臺的鏈接預測算法.