喬亞瓊，羅向陽(yáng)，馬江濤，李晨亮，張萌，李瑞祥

（1.信息工程大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450001；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001；3.鄭州輕工業(yè)大學(xué)計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450001；4.武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430075）

1 引言

社交媒體用戶位置推斷是從社交媒體數(shù)據(jù)中挖掘用戶位置信息。社交媒體用戶位置推斷技術(shù)主要用于對(duì)社交媒體用戶所在的地理位置進(jìn)行分析和定位，可為基于位置的服務(wù)[1]、基于位置的事件分析[2]和基于位置的敏感人物分析[3]提供幫助。然而，出于對(duì)個(gè)人隱私保護(hù)的考慮[4-5]，社交媒體中的位置數(shù)據(jù)十分稀疏[6]。因此，有必要開(kāi)展社交媒體用戶位置推斷問(wèn)題研究，以應(yīng)對(duì)位置數(shù)據(jù)的稀疏性問(wèn)題。

常見(jiàn)的社交媒體用戶位置推斷方法通過(guò)提取社交媒體文本中與位置相關(guān)的話題、位置指示詞或地理名詞等特征推斷用戶位置。社交媒體上討論的話題通常因地理區(qū)域而異，因此，Eisenstein 等[7]和Ahmed 等[8]使用主題模型建模話題與位置的關(guān)系來(lái)推斷用戶位置。社交媒體文本使用的詞語(yǔ)具有地理位置偏向性，Wing 等[9]通過(guò)基于詞語(yǔ)的信息增益率提取位置指示詞來(lái)推斷用戶位置。統(tǒng)計(jì)分析結(jié)果表明，如果用戶經(jīng)常提到某個(gè)地理名詞，他很可能生活在該地理區(qū)域，因此可以使用文本中提及的地理名詞來(lái)推斷用戶位置[10]。常用的地名詞典有GeoNames 和DB-pedia。Rahimi 等[11-12]使用詞袋模型提取文本特征，然后結(jié)合邏輯回歸分類器或多層感知機(jī)分類器推斷用戶位置。

除了基于文本的用戶位置推斷，基于用戶社交關(guān)系的位置推斷也比較常見(jiàn)?；谟脩羯缃魂P(guān)系的方法假設(shè)有關(guān)注關(guān)系或者有提及關(guān)系的用戶地理位置接近[13]。此類方法通過(guò)使用用戶的關(guān)注關(guān)系或者用戶在文本中的提及關(guān)系構(gòu)建圖1 所示的同質(zhì)網(wǎng)絡(luò)來(lái)推斷用戶位置。如 Rahimi 等[14]提出的MADCEL-W 方法利用用戶的提及頻次構(gòu)建加權(quán)的用戶社交網(wǎng)絡(luò)，并去除名人節(jié)點(diǎn)，基于改進(jìn)的吸附傳播算法推斷用戶位置。Rahimi 等[15]提出的GCN-LP 方法將用戶鄰居節(jié)點(diǎn)的獨(dú)熱編碼作為用戶節(jié)點(diǎn)特征，使用用戶的提及關(guān)系構(gòu)建用戶的社交網(wǎng)絡(luò)，通過(guò)圖卷積網(wǎng)絡(luò)推斷用戶位置。

基于文本的方法忽略了用戶朋友對(duì)位置的影響，可達(dá)到的精度有限；基于社交關(guān)系的方法無(wú)法對(duì)無(wú)朋友的孤立用戶進(jìn)行位置推斷。為此，學(xué)者們嘗試使用文本和社交關(guān)系2 種視圖聯(lián)合推斷用戶位置[16]。如Rahimi 等[12]提出的MADCEL-W-MLP方法，首先基于用戶之間的提及關(guān)系構(gòu)建用戶的社交網(wǎng)絡(luò)，然后將基于文本的推斷結(jié)果作為附加節(jié)點(diǎn)與對(duì)應(yīng)用戶節(jié)點(diǎn)相連，使用標(biāo)簽傳播算法推斷用戶位置。Rahimi 等[15]提出的GCN 方法將用戶文本的詞袋特征作為用戶特征，使用用戶的提及關(guān)系構(gòu)建用戶的社交網(wǎng)絡(luò)，通過(guò)圖卷積網(wǎng)絡(luò)聯(lián)合文本視圖和網(wǎng)絡(luò)視圖推斷用戶位置。Rahimi 等[15]提出的MLP-TXT+NET 方法將基于詞袋模型提取的文本特征和用獨(dú)熱編碼表示的社交關(guān)系特征串聯(lián)，利用多層感知機(jī)分類器推斷用戶位置。Zhong 等[17]提出基于注意力機(jī)制的圖神經(jīng)網(wǎng)絡(luò)模型，聯(lián)合文本內(nèi)容和社交網(wǎng)絡(luò)推斷用戶位置。

圖1 同質(zhì)網(wǎng)絡(luò)

盡管聯(lián)合推斷的方法在一定程度上降低了位置推斷誤差，卻沒(méi)有有效利用文本中的位置特征，且僅使用用戶之間的提及關(guān)系構(gòu)建網(wǎng)絡(luò)，忽略了文本中位置指示詞和地理名詞對(duì)用戶位置的指示性，導(dǎo)致位置推斷誤差仍然較大。為此，本文提出一種基于多種提及關(guān)系的社交媒體用戶位置推斷方法。該方法首先從用戶文本中提取用戶提及的朋友、位置指示詞和地理名詞；其次，根據(jù)用戶之間的提及關(guān)系、用戶對(duì)位置指示詞的提及關(guān)系和用戶對(duì)地理名詞的提及關(guān)系，構(gòu)建包含用戶、詞語(yǔ)（位置指示詞和地理名詞）和位置3 種節(jié)點(diǎn)的異質(zhì)網(wǎng)絡(luò)；再次，基于用戶對(duì)位置指示詞和地理名詞的共同提及關(guān)系提出一種異質(zhì)網(wǎng)絡(luò)簡(jiǎn)化方法，將地理位置鄰近的用戶更緊密地聯(lián)系起來(lái)；為了充分探索網(wǎng)絡(luò)結(jié)構(gòu)，緩解已知位置的稀疏性問(wèn)題，提出使用有偏的隨機(jī)游走算法對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)采樣以生成節(jié)點(diǎn)序列，用于用戶特征向量的學(xué)習(xí)；最后，基于學(xué)習(xí)得到的用戶特征向量，提出利用多層感知機(jī)分類器對(duì)用戶進(jìn)行位置推斷。

本文的主要貢獻(xiàn)如下。

1) 提出一種基于多種提及關(guān)系的社交媒體用戶位置推斷方法。與已有方法相比，該方法有效地集成了文本中提取的位置特征，能夠基于用戶與位置指示詞的提及關(guān)系、用戶對(duì)地理名詞的提及關(guān)系，以及用戶之間的提及關(guān)系，將文本視圖和用戶關(guān)系視圖更好地結(jié)合起來(lái)，聯(lián)合推斷用戶位置，并將孤立用戶連接到網(wǎng)絡(luò)中，有效降低用戶定位誤差并提高可定位用戶比例。

2) 提出一種新穎的用戶表示學(xué)習(xí)方法。與現(xiàn)有的僅基于用戶之間的提及關(guān)系構(gòu)建社交網(wǎng)絡(luò)并進(jìn)行特征向量學(xué)習(xí)的方法不同，本文提出基于多種提及關(guān)系構(gòu)建異質(zhì)圖，并根據(jù)用戶對(duì)位置指示詞和地理名詞的共同提及關(guān)系對(duì)異質(zhì)圖進(jìn)行簡(jiǎn)化，將位置鄰近的用戶更緊密地連接起來(lái)，并基于有偏的隨機(jī)游走算法生成節(jié)點(diǎn)序列以學(xué)習(xí)用戶特征向量，使地理位置鄰近用戶的特征向量距離更近。

3) 提出基于用戶表示學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)分類器推斷用戶位置。與現(xiàn)有基于標(biāo)簽傳播的位置推斷算法相比，本文方法可以有效緩解已知位置數(shù)據(jù)的稀疏性問(wèn)題，更好地利用網(wǎng)絡(luò)結(jié)構(gòu)推斷用戶位置，有效提高用戶定位準(zhǔn)確率。

2 問(wèn)題描述

為了便于理解，本節(jié)給出本文要解決問(wèn)題的定義和文中用到的主要符號(hào)及其含義。

給定社交媒體數(shù)據(jù)集D=(U,Tu)，該數(shù)據(jù)集包含位置已知的用戶集合UL、位置未知的用戶集合UN和用戶發(fā)布的文本集合T，Tu表示用戶u∈U的推文集合。則用戶集合U=UL∪UN。UL對(duì)應(yīng)的位置集合為YL。由于數(shù)據(jù)集中的雙向提及十分稀疏，本文基于用戶在文本中的單向提及構(gòu)建用戶社交網(wǎng)絡(luò)，用戶之間的社交關(guān)系集合用F表示。此外，用戶的位置集合L已知。本文將用戶位置推斷問(wèn)題視為分類問(wèn)題，用戶所在區(qū)域使用k-d 樹(shù)的劃分方法進(jìn)行區(qū)域劃分[18]，每個(gè)網(wǎng)格代表一個(gè)位置類別，表示用戶u所在的位置區(qū)域?yàn)閘i。假設(shè)待推斷的用戶位置包含在已知的位置集合中，社交網(wǎng)絡(luò)用戶位置推斷問(wèn)題可以用式(1)描述，即通過(guò)對(duì)用戶、用戶文本和用戶已知位置的分析，推斷出UN中用戶的位置集合YN。

下面給出本文用到的一些重要術(shù)語(yǔ)的定義。

定義1信息增益率。本文使用Han 等[19]提出的方法基于信息增益率提取位置指示詞。首先，對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理，去除停用詞，得到詞語(yǔ)集合M；然后，計(jì)算數(shù)據(jù)預(yù)處理后的每個(gè)詞語(yǔ)的信息增益率IGR(m)，m表示集合M中的詞語(yǔ)，如式(2)所示。

其中，IG(m)表示詞語(yǔ)m的信息增益，IV(m)表示詞語(yǔ)m的信息熵。

定義2位置特征詞。位置特征詞包括位置指示詞和地理名詞。位置指示詞有強(qiáng)烈的位置指示性[20]，具有緊湊的地理使用范圍[21]，根據(jù)詞語(yǔ)在不同位置被提及的統(tǒng)計(jì)特征篩選得到。例如，howdy 在美國(guó)德克薩斯州是一個(gè)典型的問(wèn)候語(yǔ)，它提示用戶在德克薩斯州或附近，而august、peace 和email 等詞不具有位置指示性[21]。地理名詞是表示地理位置的名詞，如Arizona。地理名詞可以借助地名詞典識(shí)別[22]，不需要借助詞語(yǔ)的統(tǒng)計(jì)特征。

定義3用戶?地理名詞矩陣。P是一個(gè)|U|×|Mp|維矩陣，P[i]是用戶ui的地理名詞向量，P[i][j]表示用戶ui提及第j個(gè)地理名詞mp的次數(shù)。

定義4用戶?位置指示詞矩陣。R是一個(gè)|U|×|Ml|維矩陣，R[i]是用戶ui位置指示詞向量，R[i][j]表示用戶ui提及第j個(gè)位置指示詞ml的次數(shù)。

定義5用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)。G=(V,E,W)，其中V=VU∪VM∪VL表示頂點(diǎn)集合，VU=U，VM=M，VL=L；M=Ml∪Mp表示位置特征詞集合，Ml表示位置指示詞集合，Mp表示地理名詞集合。E表示邊的集合，包含根據(jù)用戶之間的提及關(guān)系建立的用戶?用戶邊(u,u)、根據(jù)用戶對(duì)位置指示詞的提及關(guān)系建立的用戶?位置指示詞邊(u,ml)、根據(jù)用戶對(duì)地理名詞的提及關(guān)系建立的用戶?地理名詞邊(u,mp)，以及根據(jù)位置指示詞與其歸屬關(guān)系建立的位置指示詞?位置邊(ml,l)、根據(jù)地理名詞與其位置的歸屬關(guān)系建立的地理名詞?位置邊(mp,l)。邊的權(quán)重依次為用戶之間的提及次數(shù)、用戶對(duì)位置指示詞的提及次數(shù)和用戶對(duì)地理名詞的提及次數(shù)、位置指示詞?位置邊和地理名詞?位置邊的權(quán)重為1。此外，由于名人用戶的社交關(guān)系復(fù)雜，其關(guān)注者或者提及的用戶的位置分散，為了避免名人用戶帶來(lái)的偏差，本文將用戶朋友數(shù)量大于閾值γ的用戶視為全局名人[14]，從異質(zhì)網(wǎng)絡(luò)中剔除。

定義6用戶?位置異質(zhì)網(wǎng)絡(luò)。G′基于G簡(jiǎn)化得到。G′=(V′,E′,W′)，其中，為頂點(diǎn)集合，E′表示邊的集合，包含用戶?用戶邊(u,u)、用戶?位置邊(u,l)；W′為邊的權(quán)重集合，用戶?用戶邊及其權(quán)重根據(jù)用戶之間的提及頻次和用戶對(duì)位置特征詞的共同提及頻次構(gòu)建和計(jì)算；用戶?位置邊的權(quán)重根據(jù)用戶對(duì)位置特征詞的提及關(guān)系和位置特征詞的位置歸屬關(guān)系構(gòu)建，其權(quán)重根據(jù)用戶對(duì)位置特征詞的提及頻次計(jì)算。G′的詳細(xì)構(gòu)建方法見(jiàn)4.1 節(jié)。

3 數(shù)據(jù)分析

本節(jié)基于真實(shí)的Twitter 數(shù)據(jù)集GEOTEXT[7]進(jìn)行數(shù)據(jù)分析，展示位置特征詞的位置指示性。圖2給出了Arizona 和email 在GEOTEXT 數(shù)據(jù)集中被提及頻次的空間分布。

圖2 GEOTEXT 中Arizona 和email 被提及頻次的空間分布

圖2 中柱體表示該詞在該位置被提及，柱體的高度為該詞語(yǔ)被提及的頻次?？梢钥闯觯琫mail 分布范圍廣，在各個(gè)地區(qū)被提及的頻次相差不大，不具有位置指示性。Arizona 則被生活在亞利桑那州及其附近的用戶多次提及，具有明顯的位置指示性。

表1 給出了GEOTEXT 數(shù)據(jù)集基于信息增益率和字典匹配提取的部分位置指示詞和地理名詞。其中，l7、l20、l23、l29和l55為按照文獻(xiàn)[15,23]方法，基于k-d 樹(shù)對(duì)連續(xù)空間的進(jìn)行劃分后得到的位置標(biāo)簽；地理名詞的位置根據(jù)其表示的地理位置的坐標(biāo)確定，位置指示詞的位置基于以下的方法來(lái)確定。

對(duì)于位置指示詞ml，設(shè)該詞在所有位置出現(xiàn)的總次數(shù)為n，在位置k出現(xiàn)的次數(shù)為nk。則位置k出現(xiàn)該詞的概率為當(dāng)ε最大值唯一且滿足時(shí)，位置指示詞nl的位置是k，其中N為該詞出現(xiàn)次數(shù)不為0 的位置數(shù)。

從表1 可以看出，詞語(yǔ)在社交媒體中的使用具有明顯的地域特征。Austin 和Dallas 被生活在位置l20的用戶較多地提及，l20的中心地理坐標(biāo)為(?97.30,32.63)，Austin 的地理坐標(biāo)為(?97.10953,33.08234)，Dallas 的地理坐標(biāo)為(?97.10953,33.08234)?？梢钥闯觯@2 個(gè)地理名詞表示的地點(diǎn)奧斯汀和達(dá)拉斯在l20表示的地理區(qū)域內(nèi)。Chicago的縮寫(xiě)Chi 也較多地被該城市所屬的位置區(qū)域內(nèi)的用戶所提及。

但是，本文也觀察到，由于訓(xùn)練集中的數(shù)據(jù)偏差（例如l92僅包含一個(gè)用戶且只有少量推文），基于信息增益率獲取位置指示詞的方法無(wú)法提取某些位置的位置指示詞。因此，可以得出結(jié)論，由于位置指示詞基于詞語(yǔ)在不同區(qū)域中使用的統(tǒng)計(jì)特征提取，受訓(xùn)練集的數(shù)據(jù)影響非常大，其對(duì)用戶的位置指示性有限，這也是基于文本的位置推斷方法準(zhǔn)確率不高的原因之一。相比之下，地理名詞只需要查詢地理詞典，不需要任何訓(xùn)練數(shù)據(jù)，且其本身具有明顯的地域特征，因此，地理名詞對(duì)用戶的位置影響更為顯著。

4 本文算法描述

如圖3 所示，本文提出的方法包括基于文本的位置特征提取、用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建、用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建、基于有偏隨機(jī)游走的用戶表示學(xué)習(xí)和基于神經(jīng)網(wǎng)絡(luò)的用戶位置推斷5 個(gè)部分。

表1 詞語(yǔ)在不同位置的分布（GEOTEXT 數(shù)據(jù)集）

圖3 基于多種提及關(guān)系的社交媒體用戶位置推斷原理示意

基于文本的位置特征提取包括基于信息增益率的位置指示詞提取和基于地名詞典的地理名詞發(fā)現(xiàn)。由于用戶文本中使用的詞語(yǔ)中包含大量停用詞和與用戶位置無(wú)關(guān)的詞語(yǔ)，使用全部的詞語(yǔ)構(gòu)建用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)會(huì)導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，增加計(jì)算開(kāi)銷(xiāo)。因此，本文基于詞語(yǔ)信息增益率對(duì)詞語(yǔ)進(jìn)行初步篩選，過(guò)濾信息增益率較小的詞語(yǔ)，以識(shí)別位置指示詞，減少計(jì)算開(kāi)銷(xiāo)。此外，本文基于GeoNames 來(lái)識(shí)別文本中的地理名詞。

在提取文本中的位置特征詞之后，根據(jù)定義5給出的方法構(gòu)建圖3 所示的用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)。為了將相同位置區(qū)域的用戶更緊密地聯(lián)系起來(lái)，使地理位置鄰近的用戶的特征向量距離更近，本文提出基于提及關(guān)系簡(jiǎn)化用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)，以構(gòu)建用戶?位置異質(zhì)網(wǎng)絡(luò)，并提出基于有偏隨機(jī)游走的用戶表示學(xué)習(xí)算法學(xué)習(xí)用戶特征向量。下面詳細(xì)闡述這2 個(gè)算法。

4.1 用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建

得到用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)后，本文基于共同提及關(guān)系對(duì)其進(jìn)行簡(jiǎn)化，通過(guò)去除詞語(yǔ)節(jié)點(diǎn)將位置相近的用戶更緊密地聯(lián)系起來(lái)以構(gòu)建用戶?位置異質(zhì)網(wǎng)絡(luò)G′=(V′,E′,W′)，如算法1 所示。

算法1用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建算法（GELP）

輸入用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)G=(V,E,W)，用戶發(fā)布的推文集合T

輸出用戶?位置異質(zhì)網(wǎng)絡(luò)G′=(V′,E′,W′)

根據(jù)第3 節(jié)的分析結(jié)果，在去除詞語(yǔ)節(jié)點(diǎn)時(shí)，對(duì)于地理名詞，如果2 個(gè)用戶之間沒(méi)有邊，且他們共同提及同一地理名詞的次數(shù)大于閾值τ1，則在這2 個(gè)用戶之間添加邊，用戶?用戶邊的權(quán)重為用戶對(duì)所有地理名詞的最大共同提及次數(shù)sp，對(duì)應(yīng)的地理名詞記為mp，是第k個(gè)地理名詞。如果用戶之間已有邊，則將用戶對(duì)所有地理名詞的最大共同提及次數(shù)與已有邊的權(quán)重相加作為用戶?用戶邊的權(quán)重。同時(shí)，將與共同提及次數(shù)最多的地理名詞相連的用戶節(jié)點(diǎn)和位置節(jié)點(diǎn)lp直接相連，用戶?位置邊的權(quán)重為用戶對(duì)地理名詞的提及次數(shù)。對(duì)于位置指示詞，如果用戶對(duì)同一位置指示詞的共同提及次數(shù)大于閾值τ2，且用戶之間有邊，則用戶?用戶邊的權(quán)重為原有邊的權(quán)重和用戶對(duì)所有位置指示詞的共同提及次數(shù)的累加sl。為了避免位置指示詞帶來(lái)的噪音，本文不根據(jù)位置指示詞添加用戶?用戶邊和用戶?位置邊。下面給出用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建算法。

4.2 有偏隨機(jī)游走采樣

用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建的目的是將位置鄰近的用戶更緊密地聯(lián)系起來(lái)，且將用戶節(jié)點(diǎn)與其鄰近的位置節(jié)點(diǎn)緊密關(guān)聯(lián)。為了更好地保留節(jié)點(diǎn)的鄰域特征，本文提出有偏隨機(jī)游走策略對(duì)用戶?位置異質(zhì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行采樣生成節(jié)點(diǎn)序列。

算法2有偏隨機(jī)游走算法

輸入用戶?位置異質(zhì)網(wǎng)絡(luò)G′=(V′,E′)，單次游走長(zhǎng)度μ1，采樣長(zhǎng)度μ2

輸出節(jié)點(diǎn)序列S受Grover等[24]工作啟發(fā)，在節(jié)點(diǎn)采樣時(shí)本文使用回歸參數(shù)r控制在隨機(jī)游走中選擇上一個(gè)節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)的可能性，使用進(jìn)出參數(shù)q控制游走方向是“向內(nèi)”或“向外”。r＞1 時(shí)減少對(duì)已訪問(wèn)的節(jié)點(diǎn)進(jìn)行采樣的可能性，r＜1 時(shí)隨機(jī)游走徘徊在初始節(jié)點(diǎn)周?chē)?。q＞1，則隨機(jī)游走傾向于選擇接近上一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)，這種游走類似于廣度優(yōu)先采樣，采樣得到的節(jié)點(diǎn)序列捕獲初始節(jié)點(diǎn)附近的局部視圖；q＜1，則傾向于選擇遠(yuǎn)離上一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)，這種游走向外采樣，類似于深度優(yōu)先采樣。給定初始節(jié)點(diǎn)vi，則節(jié)點(diǎn)序列Si根據(jù)式(5)定義的轉(zhuǎn)移概率生成，其中φ(vi,vi?1)表示隨機(jī)游走從節(jié)點(diǎn)vi?1游走到節(jié)點(diǎn)vi的概率，轉(zhuǎn)移概率矩陣為ψ。假設(shè)節(jié)點(diǎn)vi?2，vi?1，vi∈E′。vi?2是vi?1的前一個(gè)節(jié)點(diǎn)，d=0 表示隨機(jī)游走從vi?1回到vi?2；d=1表示隨機(jī)游走從vi?1到與vi?2直接相連的節(jié)點(diǎn)；d=2 表示隨機(jī)游走從vi?1到與vi?2不直接相連的節(jié)點(diǎn)，Z為歸一化常數(shù)。下面給出有偏隨機(jī)游走的算法步驟。

由于本文的目標(biāo)是學(xué)習(xí)圖中所有節(jié)點(diǎn)的特征向量，因此最終節(jié)點(diǎn)序列通過(guò)對(duì)圖中每個(gè)節(jié)點(diǎn)進(jìn)行μ2次采樣生成。最終的節(jié)點(diǎn)序列長(zhǎng)度為|V′|μ2μ1。

得到節(jié)點(diǎn)序列后，將有偏隨機(jī)游走得到的節(jié)點(diǎn)序列作為輸入學(xué)習(xí)用戶特征向量，本文用skip-gram模型[25]來(lái)解決用戶特征向量學(xué)習(xí)的問(wèn)題。

4.3 基于神經(jīng)網(wǎng)絡(luò)的用戶位置推斷

在得到用戶的特征向量后，本文將其作為多層感知機(jī)的輸入訓(xùn)練用戶位置推斷模型，模型的輸出為基于k-d 樹(shù)的區(qū)域劃分后的位置類別。

是用戶的特征向量，σ()為激活函數(shù)，本文取ReLU 函數(shù)[26]為激活函數(shù)，k為隱含層的數(shù)量，本文設(shè)置為偏差向量，分別為第一、第k個(gè)隱含層和最后一層神經(jīng)網(wǎng)絡(luò)的輸出。多層感知機(jī)的參數(shù)使用Lasagne/Theano[27]基于Adam 方法[28]進(jìn)行優(yōu)化。

5 性能測(cè)試與分析

為了驗(yàn)證本文提出的方法，本文使用3 個(gè)真實(shí)Twitter 數(shù)據(jù)集 GEOTEXT[7]、TW-US[18]和TW-WORLD[29]來(lái)驗(yàn)證算法的有效性。

5.1 實(shí)驗(yàn)設(shè)置

1) 實(shí)驗(yàn)數(shù)據(jù)

GEOTEXT 和TW-US 數(shù)據(jù)集包含由來(lái)自美國(guó)的用戶發(fā)布的推文。GEOTEXT 使用每個(gè)用戶的第一條推文位置作為用戶的基準(zhǔn)位置[7]，TW-US 使用每個(gè)用戶發(fā)布的帶有位置標(biāo)簽的推文的中位數(shù)位置作為該用戶的基準(zhǔn)位置。TW-WORLD 包含來(lái)自全球的用戶發(fā)布的推文，提取每個(gè)用戶大部分推文位置附近的城市中心作為用戶的基準(zhǔn)位置。3 個(gè)數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)如表2 所示。

2) 評(píng)價(jià)標(biāo)準(zhǔn)

本文使用平均誤差mean、中位數(shù)誤差median、Acc@161 和覆蓋率coverage 來(lái)評(píng)估所提的位置推斷方法的性能，其中，Acc@161 為推斷位置與實(shí)際位置距離小于161 km 的用戶位置推斷準(zhǔn)確率。用戶覆蓋率為可定位的用戶占所有用戶的百分比。

3) 參數(shù)設(shè)置

對(duì)于本文用到的 3 個(gè)數(shù)據(jù)集，本文按照Rahimi 等[12]的方法，基于k-d 樹(shù)對(duì)連續(xù)空間進(jìn)行劃分，以確保每個(gè)區(qū)域內(nèi)有相似數(shù)量的用戶。根據(jù) Rahimi 等[12]的經(jīng)驗(yàn)，本文將 GEOTEXT，TW-US 和TW-WORLD 這3 個(gè)數(shù)據(jù)集基于k-d 樹(shù)劃分的參數(shù)依次設(shè)置為50、2 400 和2 400，分別生成了129、256 和930 個(gè)位置標(biāo)簽。與Rahimi等[12]的工作保持一致，本文每個(gè)區(qū)域內(nèi)所有用戶位置經(jīng)度、緯度的中位數(shù)作為該區(qū)域位置標(biāo)簽的地理坐標(biāo)。

低速轉(zhuǎn)向時(shí)需要電動(dòng)機(jī)輸出大轉(zhuǎn)矩,高速轉(zhuǎn)向時(shí)需要電動(dòng)機(jī)輸出小轉(zhuǎn)矩,即隨著v增大,F(v)減小,所以F(v)為v的指數(shù)遞減函數(shù).G(Td)為輸入不同大小扭矩時(shí)的特性曲線函數(shù)表達(dá)式,隨著輸入扭矩的增大和減小,其結(jié)果也隨之增大和減小,所以G(Td)為T(mén)d的遞增函數(shù).通過(guò)以上分析,可以得到F(v)的表達(dá)式為

此外，在構(gòu)建用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)時(shí)，本文將名人節(jié)點(diǎn)去除的閾值γ在GEOTEXT、TW-US和TW-WORLD 上依次設(shè)置為5、15 和5?；谛畔⒃鲆媛蔬x取候選位置指示詞集的閾值設(shè)為0.25[19]。在學(xué)習(xí)用戶特征向量時(shí)，本文將有偏隨機(jī)游走的參數(shù)設(shè)置為r=4，q=0.25，μ2=10，μ1=80。

5.2 實(shí)驗(yàn)結(jié)果

本節(jié)將提出的用戶位置推斷方法與經(jīng)典的方法進(jìn)行比較，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

表3 給出了所提方法與經(jīng)典方法的性能對(duì)比?？梢钥闯?，在3 個(gè)數(shù)據(jù)集上，所提方法在Acc@161、mean、median 上的表現(xiàn)均優(yōu)于所有經(jīng)典方法。在GEOTEXT 數(shù)據(jù)集上，Acc@161 比性能最好的MAGNN 高出2%，平均誤差降低25 km。表明本文提出的異質(zhì)網(wǎng)絡(luò)的社交媒體用戶位置推斷方法可以通過(guò)用戶和位置的關(guān)系加強(qiáng)用戶之間的聯(lián)系，提高用戶位置推斷性能。

5.3 不同提及關(guān)系的影響分析

為了探索不同提及關(guān)系對(duì)用戶位置推斷的性能的影響，本文提出以下4 種用戶?位置異質(zhì)網(wǎng)絡(luò)構(gòu)建方法，并進(jìn)行了對(duì)比測(cè)試。

表2 數(shù)據(jù)集的統(tǒng)計(jì)信息

表3 在3 個(gè)Twitter 數(shù)據(jù)集上的位置推斷性能

1) GELP-MEW。通過(guò)將提及同一詞語(yǔ)的節(jié)點(diǎn)直接相連去除用戶?詞語(yǔ)?位置異質(zhì)網(wǎng)絡(luò)中的詞語(yǔ)節(jié)點(diǎn)。去除詞語(yǔ)節(jié)點(diǎn)之后，用戶?用戶邊的權(quán)重為共同提及位置指示詞的最小次數(shù)加上用戶之間的提及次數(shù)，用戶?位置邊的權(quán)重為用戶對(duì)詞語(yǔ)的提及次數(shù)。

2) GELP-MW。在去除詞語(yǔ)節(jié)點(diǎn)時(shí)，僅將連接同一詞語(yǔ)的用戶節(jié)點(diǎn)和位置節(jié)點(diǎn)相連。去除詞語(yǔ)節(jié)點(diǎn)之后，用戶?用戶邊的權(quán)重為共同提及位置指示詞的最小次數(shù)加上用戶之間的提及次數(shù)，用戶?位置邊的權(quán)重為用戶對(duì)詞語(yǔ)的提及次數(shù)。

3) GELP-I。在去除詞語(yǔ)節(jié)點(diǎn)時(shí)，僅將與該詞相鄰的孤立用戶以及訓(xùn)練集中的用戶和位置節(jié)點(diǎn)相連。去除詞語(yǔ)節(jié)點(diǎn)之后，用戶?用戶邊的權(quán)重為1，用戶?位置邊的權(quán)重為1。

4) GELP-UW。在去除詞語(yǔ)節(jié)點(diǎn)時(shí)，僅將訓(xùn)練集中的用戶節(jié)點(diǎn)和位置節(jié)點(diǎn)相連。去除詞語(yǔ)節(jié)點(diǎn)之后，用戶?用戶邊的權(quán)重為用戶之間的提及次數(shù)之和，用戶?位置邊的權(quán)重為1。

表4 不同異質(zhì)網(wǎng)絡(luò)構(gòu)建方法的位置推斷結(jié)果（GEOTEXT 數(shù)據(jù)集）

從表4 中可以看出，GELP 取得了最好的位置推斷結(jié)果，并且具有較高的用戶覆蓋率。雖然其用戶覆蓋率不是最高，但仍然高出典型的用戶位置推斷算法（CGN）2.76%。GELP-UW 的位置推斷結(jié)果比GELP 稍差，與GELP 的用戶覆蓋率相同。GELP-I、GELP-MW 和GELP-MEW 具有最大的用戶覆蓋率，GELP-MEW 表現(xiàn)最差。

結(jié)合以上實(shí)驗(yàn)結(jié)果，本文得到以下結(jié)論。

1) 使用用戶對(duì)詞語(yǔ)的共同提及關(guān)系連接用戶節(jié)點(diǎn)，會(huì)降低用戶位置推斷性能。原因是，盡管用戶對(duì)位置指示詞的提及反映了用戶的位置，但是由于用戶共同提及的位置指示詞有多個(gè)，且這些位置指示詞可能指示不同的位置，簡(jiǎn)單地根據(jù)用戶對(duì)位置指示詞的共同提及添加用戶?用戶邊，引入了大量的噪聲，從而降低了用戶位置推斷的性能。

2) 使用用戶對(duì)位置指示詞的提及添加開(kāi)發(fā)集和測(cè)試集的用戶?位置節(jié)點(diǎn)，并基于用戶對(duì)位置指示詞提及的次數(shù)對(duì)用戶?用戶邊加權(quán)，可以提高可定位用戶比例，但是不能提高用戶位置推斷準(zhǔn)確率。原因是訓(xùn)練集上的數(shù)據(jù)偏差使基于信息增益率獲取的位置指示詞包含噪聲詞匯，基于位置指示詞添加用戶?位置邊引入了噪聲，降低了用戶位置推斷準(zhǔn)確率。

3) 使用用戶提及的位置特征詞僅將孤立用戶連接到網(wǎng)絡(luò)中，可以增加可定位用戶比例，并保持較高的用戶位置推斷準(zhǔn)確率。

4) 使用用戶之間的提及關(guān)系對(duì)用戶?用戶邊加權(quán)，不能提高用戶位置推斷準(zhǔn)確率，說(shuō)明用戶的提及次數(shù)并不代表用戶位置的緊密度。

5.4 用戶特征向量的可視化

圖4 給出了在GEOTEXT 數(shù)據(jù)集中隨機(jī)選擇的5 個(gè)區(qū)域內(nèi)對(duì)用戶特征向量進(jìn)行主成分分析（PCA,principal component analysis）降維后的可視化結(jié)果?？梢钥闯?，與GELP-MEW 相比，GCN和GELP 的用戶特征向量在不同的位置的可分辨能力較強(qiáng)。與GCN 和GELP-MEW 相比，GELP可以將相同區(qū)域的用戶更好地聚集在一起。

6 結(jié)束語(yǔ)

本文提出了一種多種提及關(guān)系的社交媒體用戶位置推斷方法。通過(guò)綜合考慮用戶之間的提及關(guān)系、對(duì)位置指示詞和地理名詞的提及關(guān)系構(gòu)建異質(zhì)網(wǎng)絡(luò)，探索了異質(zhì)社交網(wǎng)絡(luò)中用戶的位置推斷方法。將異質(zhì)網(wǎng)絡(luò)用于用戶位置推斷是一個(gè)新的嘗試，基于異質(zhì)網(wǎng)絡(luò)中豐富的異質(zhì)信息，可以更全面地捕獲用戶的位置特征，在真實(shí)Twitter 數(shù)據(jù)集上的大量實(shí)驗(yàn)表明，本文提出的方法有效提高了位置推斷的準(zhǔn)確率和覆蓋率，降低了平均誤差和中位數(shù)誤差。

盡管本文方法獲得了較好的效果，但如何使用更大規(guī)模的異質(zhì)數(shù)據(jù)源構(gòu)建異質(zhì)網(wǎng)絡(luò)仍然有待進(jìn)一步研究。將來(lái)的工作中將對(duì)此進(jìn)一步開(kāi)展相關(guān)研究。

圖4 來(lái)自GEOTEXT 數(shù)據(jù)集的5 個(gè)隨機(jī)選擇區(qū)域中的用戶嵌入的PCA 可視化效果比較