移動(dòng)終端用戶群體發(fā)現(xiàn)研究范文

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

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

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

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

1基本思路

移動(dòng)終端用戶群體發(fā)現(xiàn)的目的是從數(shù)量眾多的用戶中篩選出具有稠密社會(huì)關(guān)系和相似位置屬性的用戶群體.一方面，移動(dòng)用戶通常在多個(gè)地點(diǎn)簽到，具有多個(gè)位置標(biāo)簽；另一方面，現(xiàn)實(shí)生活中每個(gè)用戶擁有多種類型的社會(huì)關(guān)系，可能屬于多個(gè)群體.同一群體成員的位置標(biāo)簽既有共性，也有差異.用戶在某個(gè)群體中的標(biāo)簽差異性可能與用戶所屬的其他群體有關(guān).現(xiàn)有方法不能很好處理上述位置屬性多標(biāo)簽與社會(huì)關(guān)系多群體的問題.本研究提出基于反向標(biāo)簽傳播算法（reversela-belpropagationalgorithm,Reverse-LPA）的移動(dòng)終端用戶重疊群體發(fā)現(xiàn)方法.根據(jù)簽到位置信息推斷移動(dòng)終端用戶社會(huì)關(guān)系拓?fù)鋱D，提取用戶的時(shí)空共現(xiàn)區(qū)作為標(biāo)簽，通過標(biāo)簽初始化得到標(biāo)簽拓?fù)鋱D.在標(biāo)簽拓?fù)鋱D上進(jìn)行反向標(biāo)簽傳播，對(duì)于節(jié)點(diǎn)的每個(gè)標(biāo)簽，依據(jù)其在鄰居節(jié)點(diǎn)中的狀態(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é)點(diǎn)連接關(guān)系和標(biāo)簽分布情況提取用戶群體.

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

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

2.2時(shí)空共現(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ù)為，其中為用戶，為簽到時(shí)間，為經(jīng)緯度.時(shí)空共現(xiàn)（spatio-temporalco-occurrence）[13,15]是指用戶在一定的時(shí)間區(qū)間和空間區(qū)域相遇的事件，發(fā)生時(shí)空共現(xiàn)事件的時(shí)空區(qū)域稱為時(shí)空共現(xiàn)區(qū).設(shè)為以時(shí)間點(diǎn)為起點(diǎn)、時(shí)長(zhǎng)為的時(shí)間段，為以為圓心、半徑為的空間區(qū)域，為不同用戶在時(shí)間段和空間區(qū)域內(nèi)相遇所對(duì)應(yīng)的時(shí)空共現(xiàn)區(qū).使用基于密度峰值的快速聚類算法（clusteringbyfastsearchandfindofdensitypeaks，CFSFDP）[18]對(duì)位置數(shù)據(jù)進(jìn)行聚類，每一個(gè)聚類簇為1個(gè)時(shí)空共現(xiàn)區(qū).

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

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

4Reverse-LPA可行性證明

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

5實(shí)驗(yàn)及結(jié)果分析

5.1數(shù)據(jù)集簡(jiǎn)介

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

5.2評(píng)價(jià)指標(biāo)

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

5.3結(jié)果分析

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

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