本站小編為你精心準(zhǔn)備了移動終端用戶群體發(fā)現(xiàn)研究參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要：針對現(xiàn)有方法在移動終端用戶群體發(fā)現(xiàn)中不能兼顧社會關(guān)系和位置屬性的問題，提出基于反向標(biāo)簽傳播算法的重疊群體發(fā)現(xiàn)方法.根據(jù)移動終端用戶的位置信息推斷社會關(guān)系拓?fù)鋱D，提取時空共現(xiàn)區(qū).將時空共現(xiàn)區(qū)作為位置屬性標(biāo)簽，標(biāo)注社會關(guān)系拓?fù)鋱D.在標(biāo)簽拓?fù)鋱D上進行反向標(biāo)簽傳播，消除節(jié)點伴隨標(biāo)簽.經(jīng)過反復(fù)迭代，在標(biāo)簽穩(wěn)定狀態(tài)下的每一個節(jié)點保留所屬群體的主標(biāo)簽.根據(jù)用戶社會關(guān)系和穩(wěn)定狀態(tài)下的節(jié)點主標(biāo)簽完成群體劃分與識別.在4個真實數(shù)據(jù)集上比較反向標(biāo)簽傳播算法與3種同類方法，實驗結(jié)果表明，反向標(biāo)簽傳播算法較好地兼顧了用戶社會關(guān)系和位置屬性，群體發(fā)現(xiàn)結(jié)果的標(biāo)準(zhǔn)互信息（NMI）與綜合評價函數(shù)（F）分別比次優(yōu)者平均高8.97%和3.87%.

關(guān)鍵詞：移動終端；位置數(shù)據(jù)；重疊群體發(fā)現(xiàn)；反向標(biāo)簽傳播；社會關(guān)系；位置屬性

隨著移動通信網(wǎng)絡(luò)的快速發(fā)展和移動終端定位技術(shù)的廣泛應(yīng)用，基于位置的服務(wù)（locationbasedservices,LBS）[1]影響著人類生產(chǎn)生活的方方面面.通過LBS應(yīng)用，移動終端用戶構(gòu)成了龐大的社會網(wǎng)絡(luò)，產(chǎn)生了大量的位置數(shù)據(jù).群體是指2個及以上的個體由于特定的內(nèi)在因素（興趣、目標(biāo)、利益等）自發(fā)或者有組織地聚集在一起形成的集合[2].群體發(fā)現(xiàn)是社會網(wǎng)絡(luò)研究的重要內(nèi)容[3]，有助于進一步分析群體用戶的行為模式與交互規(guī)律，實施輿情引導(dǎo)控制和異常群體監(jiān)控[4].移動終端用戶群體發(fā)現(xiàn)是指通過分析用戶在使用LBS應(yīng)用時產(chǎn)生的位置數(shù)據(jù)，挖掘具有相同內(nèi)在因素的用戶集合.復(fù)雜網(wǎng)絡(luò)的社團挖掘方法[5]主要依據(jù)用戶關(guān)系拓?fù)鋱D進行聚類，忽略了用戶的其他屬性，難以發(fā)現(xiàn)屬性特征相似的群體[2].移動終端用戶具有較強的位置屬性，復(fù)雜網(wǎng)絡(luò)的社團挖掘方法不適用于移動終端用戶的群體發(fā)現(xiàn).在現(xiàn)有的針對位置社交網(wǎng)絡(luò)（location-basedsocialnetwork,LB-SN）的社團挖掘方法中，Hung等[6]和Boston等[7]根據(jù)位置數(shù)據(jù)提取用戶的移動行為模式，將行為模式相似的用戶聚類為一個社團/群體.但是現(xiàn)實生活中行為模式相似的用戶不一定具有社會關(guān)系，例如在相同路線經(jīng)過的上班族、在同一個商圈居住的居民等，所以Boston等[7]所述方法發(fā)現(xiàn)的群體存在不準(zhǔn)確性.Jayadevan等[8]根據(jù)位置共現(xiàn)信息估計用戶社會關(guān)系強度，得到社會關(guān)系拓?fù)鋱D，使用社團挖掘方法發(fā)現(xiàn)移動用戶群體，但是該方法將共現(xiàn)信息轉(zhuǎn)化為社會關(guān)系，弱化了用戶的位置屬性.假定場景：給定3個用戶（1、2、3）和3個位置（Ⅰ、Ⅱ、Ⅲ）.用戶1頻繁出現(xiàn)在Ⅰ和Ⅱ，用戶2頻繁出現(xiàn)在Ⅰ和Ⅲ，用戶3頻繁出現(xiàn)在Ⅱ和Ⅲ.每2個用戶通過共現(xiàn)位置建立了社會關(guān)系.從社會關(guān)系的角度分析，3個用戶可以屬于同一個群體；但是從位置屬性的角度看，三者沒有共同的共現(xiàn)位置，屬于不同的群體.Lim等[9]指出時空疊加關(guān)系發(fā)現(xiàn)的群體以位置為中心，具有高度的位置相似性.Brown等[10]根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)圖和用戶簽到的位置信息研究同一網(wǎng)絡(luò)中線上和線下用戶群體的差異性，指出線下用戶群體具有位置聚集性.Brown等[11]和Liu等[12]利用用戶社會關(guān)系和簽到地點雙重信息發(fā)現(xiàn)位置社團，根據(jù)簽到信息計算用戶的社會關(guān)系強度，將社會關(guān)系強度作為社會關(guān)系拓?fù)鋱D中邊的權(quán)值，刪除權(quán)值小于閾值的邊，用傳統(tǒng)社團挖掘算法發(fā)現(xiàn)位置社團.但是Brown等[11]和Liu等[12]將位置信息與社會關(guān)系相融合，根據(jù)社會關(guān)系拓?fù)鋱D發(fā)現(xiàn)的群體同樣可能存在位置屬性不強的問題；同時移動終端上既有社交類應(yīng)用，也有非社交類應(yīng)用，在非社交類應(yīng)用中用戶間交流互動較少，無法直接提取用戶的社會關(guān)系，因此Brown等[11]和Liu等[12]的方法在移動終端用戶的群體發(fā)現(xiàn)中的普適性不強.綜上所述，位置數(shù)據(jù)不能直接表達(dá)用戶的社會關(guān)系，復(fù)雜網(wǎng)絡(luò)群體發(fā)現(xiàn)方法不能直接用于移動用戶的群體發(fā)現(xiàn)；同時移動用戶群體具有社會關(guān)系和位置聚集雙重屬性，現(xiàn)有以復(fù)雜網(wǎng)絡(luò)和位置社交網(wǎng)絡(luò)為對象的社團挖掘方法難以同時兼顧社會關(guān)系和位置屬性，所發(fā)現(xiàn)群體具有不準(zhǔn)確性.為此，以位置信息為對象，提取用戶社會關(guān)系和位置屬性，將前者作為用戶關(guān)系拓?fù)鋱D，后者作為用戶標(biāo)簽，并通過標(biāo)簽傳播算法將兩者結(jié)合起來，提出一種有效的移動終端用戶群體發(fā)現(xiàn)方法.

1基本思路

移動終端用戶群體發(fā)現(xiàn)的目的是從數(shù)量眾多的用戶中篩選出具有稠密社會關(guān)系和相似位置屬性的用戶群體.一方面，移動用戶通常在多個地點簽到，具有多個位置標(biāo)簽；另一方面，現(xiàn)實生活中每個用戶擁有多種類型的社會關(guān)系，可能屬于多個群體.同一群體成員的位置標(biāo)簽既有共性，也有差異.用戶在某個群體中的標(biāo)簽差異性可能與用戶所屬的其他群體有關(guān).現(xiàn)有方法不能很好處理上述位置屬性多標(biāo)簽與社會關(guān)系多群體的問題.本研究提出基于反向標(biāo)簽傳播算法（reversela-belpropagationalgorithm,Reverse-LPA）的移動終端用戶重疊群體發(fā)現(xiàn)方法.根據(jù)簽到位置信息推斷移動終端用戶社會關(guān)系拓?fù)鋱D，提取用戶的時空共現(xiàn)區(qū)作為標(biāo)簽，通過標(biāo)簽初始化得到標(biāo)簽拓?fù)鋱D.在標(biāo)簽拓?fù)鋱D上進行反向標(biāo)簽傳播，對于節(jié)點的每個標(biāo)簽，依據(jù)其在鄰居節(jié)點中的狀態(tài)，標(biāo)記其狀態(tài)為“保留”或“消除”；反復(fù)迭代，根據(jù)標(biāo)簽的狀態(tài)將符合條件標(biāo)簽刪除，得到穩(wěn)定狀態(tài)的用戶標(biāo)簽拓?fù)鋱D；最終在標(biāo)簽拓?fù)鋱D上根據(jù)節(jié)點連接關(guān)系和標(biāo)簽分布情況提取用戶群體.

2位置數(shù)據(jù)預(yù)處理

2.1社會關(guān)系推斷移動終端用戶社會關(guān)系推斷是指根據(jù)用戶簽到位置數(shù)據(jù)的時間和空間關(guān)系判斷用戶社會關(guān)系強度.目前常用的方法有共現(xiàn)頻次法[13]、軌跡相似法[14]和特征提取法[15-17]等.選取馬春來等[17]提出的方法，根據(jù)用戶簽到位置的總體屬性、用戶活躍性、位置多樣性和位置特殊性等4類特征，使用改進的隨機森林算法判斷用戶是否存在社會關(guān)系，在用戶社會關(guān)系判斷的基礎(chǔ)上構(gòu)建用戶關(guān)系拓?fù)鋱D.

2.2時空共現(xiàn)區(qū)提取d={u,p,⟨lo,la⟩}up⟨lo,la⟩zρ−τtρτzo−λsoλzc=(zρ−τt,zo−λs)zρ−τtzo−λs定義位置數(shù)據(jù)為，其中為用戶，為簽到時間，為經(jīng)緯度.時空共現(xiàn)（spatio-temporalco-occurrence）[13,15]是指用戶在一定的時間區(qū)間和空間區(qū)域相遇的事件，發(fā)生時空共現(xiàn)事件的時空區(qū)域稱為時空共現(xiàn)區(qū).設(shè)為以時間點為起點、時長為的時間段，為以為圓心、半徑為的空間區(qū)域，為不同用戶在時間段和空間區(qū)域內(nèi)相遇所對應(yīng)的時空共現(xiàn)區(qū).使用基于密度峰值的快速聚類算法（clusteringbyfastsearchandfindofdensitypeaks，CFSFDP）[18]對位置數(shù)據(jù)進行聚類，每一個聚類簇為1個時空共現(xiàn)區(qū).

3反向標(biāo)簽傳播算法

標(biāo)簽傳播算法（labelpropagationalgorithm,LPA）是一種復(fù)雜度較低的社團發(fā)現(xiàn)方法[19]，包括標(biāo)簽初始化、標(biāo)簽傳播和傳播停止條件3個部分.將用戶時空共現(xiàn)區(qū)作為位置屬性標(biāo)簽，結(jié)合標(biāo)簽初始化與用戶社會關(guān)系拓?fù)鋱D，有助于提高移動終端用戶群體發(fā)現(xiàn)結(jié)果的準(zhǔn)確性.因為移動終端用戶通常會在多個位置簽到，對應(yīng)多個時空共現(xiàn)區(qū)，所以標(biāo)簽初始化后的社會關(guān)系拓?fù)鋱D中的每個用戶節(jié)點擁有多個標(biāo)簽.現(xiàn)有LPA大多為1個用戶節(jié)點初始化1個標(biāo)簽，無法處理多標(biāo)簽的情況，因此本研究對現(xiàn)有的LPA進行改進，提出一種反向標(biāo)簽傳播算法.

4Reverse-LPA可行性證明

Reverse-LPA的標(biāo)簽傳播過程與現(xiàn)有的LPA差別比較大，需要證明可行性.Reverse-LPA的主要原理是在節(jié)點連接關(guān)系上經(jīng)過多次傳播獲取標(biāo)簽的穩(wěn)定狀態(tài)，保留每個群體熵值最小的主標(biāo)簽.根據(jù)Reverse-LPA的標(biāo)簽傳播過程，可以通過證明節(jié)點標(biāo)簽穩(wěn)定狀態(tài)的存在性論證Reverse-LPA的可行性.節(jié)點標(biāo)簽穩(wěn)定狀態(tài)的存在性可以從2個方面進行證明：伴隨標(biāo)簽的穩(wěn)定狀態(tài)為“消除”；熵值最小主標(biāo)簽的穩(wěn)定狀態(tài)為“保留”，其他主標(biāo)簽的穩(wěn)定狀態(tài)為“消除”.

5實驗及結(jié)果分析

5.1數(shù)據(jù)集簡介

基于Reverse-LPA的移動終端用戶群體發(fā)現(xiàn)方法，Boston等[7]和Jayadevan等[8]提出的對比方法只需要位置信息即可完成群體發(fā)現(xiàn)工作，但Liu等[12]提出的對比方法還需要用戶社會關(guān)系信息，數(shù)據(jù)集需要同時具有用戶簽到位置和社會關(guān)系信息.本研究選取來自社交網(wǎng)站Gowalla、Brightkite和Foursquare上的簽到位置數(shù)據(jù)，通過實驗驗證Reverse-LPA的有效性.Gowalla、Brightkite數(shù)據(jù)集來源于Cho等[22]的研究，數(shù)據(jù)內(nèi)容主要包括用戶ID、位置、時間和關(guān)注關(guān)系.Foursquare數(shù)據(jù)集來源于Bao等[23]的研究，內(nèi)容包括用戶身份、簽到事件、地點和關(guān)注關(guān)系.由于Foursquare用戶的簽到頻率比較稀疏，為了保證數(shù)據(jù)的可用性，選取簽到事件不少于8次的用戶進行實驗.為了分析Reverse-LPA群體發(fā)現(xiàn)的準(zhǔn)確性，利用Foursquare數(shù)據(jù)集相對豐富的用戶信息，使用問卷調(diào)查獲取部分用戶的真實群體信息.根據(jù)身份信息和Foursquare網(wǎng)站定位用戶的Facebook主頁，獲取用戶的Email并且發(fā)送調(diào)查問卷.問卷內(nèi)容主要包括與用戶有關(guān)注關(guān)系的Foursquare用戶的Face-book昵稱和社會關(guān)系類型選項.根據(jù)問卷結(jié)果，將用戶身份數(shù)據(jù)中家庭地址（HomeCity）一致并且有家人（Family）關(guān)系的用戶劃分為一個群體；將Facebook主頁中工作地點（或單位）一致并且有同事（Colleague）關(guān)系的用戶劃分為一個群體.在49062個Foursquare用戶中獲取到Email賬號31049個，回收有效調(diào)查問卷648份，成功劃分群體154個，涉及1832個用戶，命名為Fsqtrue數(shù)據(jù)集.

5.2評價指標(biāo)

5.2.1標(biāo)準(zhǔn)互信息　已知群體背景信息時，使用標(biāo)準(zhǔn)互信息（normalizedmutualinformation，NMI）評價群體發(fā)現(xiàn)算法的性能.NMI取值范圍為[0,1.0]，數(shù)值越大表明群體發(fā)現(xiàn)算法輸出結(jié)果與群體真實結(jié)構(gòu)越接近，算法性能越好.

5.3結(jié)果分析

QovSg實驗結(jié)果分析包含兩部分.首先在4個數(shù)據(jù)集上觀察評價指標(biāo)NMI、、、F在Reverse-LPA迭代過程中的變化規(guī)律，驗證Reverse-LPA的可行性；其次通過比較Reverse-LPA與其他算法在數(shù)據(jù)集上的群體劃分指標(biāo)值.6結(jié)　語NMIF提出了基于Reverse-LPA的移動終端用戶群體發(fā)現(xiàn)方法，根據(jù)位置數(shù)據(jù)推斷用戶社會關(guān)系拓?fù)鋱D，提取用戶時空共現(xiàn)區(qū).以時空共現(xiàn)區(qū)為標(biāo)簽標(biāo)記社會關(guān)系拓?fù)鋱D，在標(biāo)簽拓?fù)鋱D上進行反向標(biāo)簽傳播.通過反復(fù)迭代，逐步消除伴隨標(biāo)簽，最終保留每個用戶所屬群體的主標(biāo)簽.將拓?fù)鋱D上擁有相同主標(biāo)簽的用戶劃分為一個群體，得到移動終端用戶群體結(jié)構(gòu).Reverse-LPA算法較好地考慮了用戶社會關(guān)系和位置屬性，其可行性和有效性在真實數(shù)據(jù)集上得到了驗證，Reverse-LPA的評價指標(biāo)與分別比次優(yōu)者平均高出8.97%和3.87%.今后可在此基礎(chǔ)上進一步研究在用戶社會關(guān)系類型等信息輔助下的移動終端用戶群體發(fā)現(xiàn)方法.

作者：李志；單洪；馬濤；黃郡單位：國防科技大學(xué)