移動終端用戶群體發現研究范文

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

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

關鍵詞：移動終端；位置數據；重疊群體發現；反向標簽傳播；社會關系；位置屬性

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

1基本思路

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

2位置數據預處理

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

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

3反向標簽傳播算法

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

4Reverse-LPA可行性證明

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

5實驗及結果分析

5.1數據集簡介

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

5.2評價指標

5.2.1標準互信息　已知群體背景信息時，使用標準互信息（normalizedmutualinformation，NMI）評價群體發現算法的性能.NMI取值范圍為[0,1.0]，數值越大表明群體發現算法輸出結果與群體真實結構越接近，算法性能越好.

5.3結果分析

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

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