基于網(wǎng)格概率的離群點檢測算法①
2016-06-15 03:51:15彭艷兵馮利容烽火通信科技股份有限公司IAO南京009武漢郵電科學(xué)研究院電信系武漢430074
計算機系統(tǒng)應(yīng)用 2016年4期
彭艷兵,馮利容,(烽火通信科技股份有限公司 IAO,南京 009)(武漢郵電科學(xué)研究院 電信系,武漢 430074)
?
基于網(wǎng)格概率的離群點檢測算法①
彭艷兵1,馮利容1,2
1(烽火通信科技股份有限公司 IAO,南京 210019)
2(武漢郵電科學(xué)研究院 電信系,武漢 430074)
摘 要:隨著移動網(wǎng)絡(luò)、智能終端的迅猛發(fā)展,基于位置的服務(wù)LBS(Location-based Service)越來越熱門,因此基站位置信息的正確與否成為關(guān)注的重點.針對基站地理位置存在部分錯誤這一現(xiàn)象,提出了基于網(wǎng)格概率的離群點檢測算法來核查錯誤的基站.首先,根據(jù)基站分布的規(guī)則將數(shù)據(jù)空間分成若干網(wǎng)格單元; 其次,根據(jù)用戶軌跡簽到信息關(guān)聯(lián)出其在動態(tài)時間范圍內(nèi)經(jīng)過的基站序列,將基站序列映射到網(wǎng)格中,計算出臨近網(wǎng)格單元集合;最后,根據(jù)基站分布特點對網(wǎng)格單元內(nèi)目標(biāo)基站的臨近基站求隸屬概率,篩選出離群點,即錯誤的基站.實驗表明,該算法的時間復(fù)雜度低且核實準(zhǔn)確率較高.
關(guān)鍵詞:基于位置的服務(wù); 網(wǎng)格劃分; 隸屬概率; 離群點檢測
近些年,隨著定位技術(shù)的日趨成熟以及定位設(shè)備的大量普及,面向不同的應(yīng)用領(lǐng)域的移動終端產(chǎn)生了大量的軌跡數(shù)據(jù).這些數(shù)據(jù)里面蘊藏著非常豐富的知識信息,它能準(zhǔn)確地反映人們的移動規(guī)律,能生動地體現(xiàn)交通情況,能正確地揭示道路結(jié)構(gòu)[1].目前,與之相關(guān)的數(shù)據(jù)挖掘的研究備受關(guān)注,其中一項比較有現(xiàn)實意義的研究就是通過移動軌跡數(shù)據(jù)來檢測核實錯誤的定位設(shè)備(本文指的是基站).
在移動通信發(fā)展的前幾年,各大運營商對于基站的建設(shè)沒有統(tǒng)一的規(guī)劃,導(dǎo)致許多基站的維護變得非常困難.目前隨著網(wǎng)絡(luò)時代的飛速發(fā)展,移動通信進入了高速發(fā)展的通信時代.因此,移動基站坐標(biāo)的正確對于網(wǎng)絡(luò)發(fā)展來說,顯得越來越重要.但是,由于存在基站信息的變更、人工錄入失誤等因素,導(dǎo)致基站的坐標(biāo)數(shù)據(jù)可能存在3%左右的錯誤,同時運營商每年更新的基站信息不會實時同步到位置信息服務(wù)商.所以高效地檢測出錯誤的基站是非常有必要的.由于錯誤基站的數(shù)量不會很多,可以將其看做異常點、離群點,這種研究非常適用于離群點檢測這一應(yīng)用場景.
為了有效的檢測出離群點,很多研究人員已經(jīng)開發(fā)了大量的離群點檢測算法,包括基于統(tǒng)計的離群點檢測算法、基于距離的離群點檢測算法、基于密度的離群點檢測算法和基于深度的離群點檢測算法等,其中基于距離的離群點檢測算法包含并且擴展了基于統(tǒng)計的思想,需要首先確定參數(shù),然后將非數(shù)值型屬性轉(zhuǎn)換成數(shù)值型數(shù)據(jù),計算對象之間的歐式距離,最終確定離群點.這算法比較容易理解,而且具有比較直觀的意義,故在實際場景中的應(yīng)用很多[2].Knorr[3,4]等人最先提出了基于距離的離群點的概念.Ramasmawy對基于距離的離群點的定義做了改進,通過對與對象距離最近的第K個對象之間的距離排序,將數(shù)據(jù)集中距離排在前面的m個對象標(biāo)記為離群點[5].FAngiulli等提出離群點是數(shù)據(jù)集中與其K個最近鄰居的平均距離最大的前m個對象[6],主要通過比較對象與K個最近鄰居的平均距離來檢測離群點.這些算法將需要N2次的數(shù)據(jù)對象之間的距離計算,當(dāng)N很大時就不適用了.因此,本文在基于距離的思想上,提出基于網(wǎng)格概率的離群點檢測算法,直接通過數(shù)據(jù)點處于鄰近網(wǎng)格的概率來確定離群點,避免了計算N2次的數(shù)據(jù)對象之間的距離,然后結(jié)合實際基站位置的空間位置關(guān)系,給出一種高效識別錯誤基站的方法.
1 基本理論知識
1.1網(wǎng)格劃分和數(shù)據(jù)映射
把地球看成一個平面圖,選擇一個中心點,中心點選擇“赤道與本初子午線交叉點”,然后以這個中心點同時向上下左右按步長0.01度進行擴展,每擴展一次可以得到一個長和寬都為0.01度的正方形,此正方形則為一個柵格.通過此算法劃分出的每個柵格的地理面積約為1.24平方公里左右(地球兩極點除外)[7,8].
按照上述劃分方式,對本文實驗數(shù)據(jù)空間進行劃分.任意給定一地理區(qū)域,將其表示成二維空間M,按照經(jīng)緯度方向分別劃分為a、b等份,a>0 ,b>0且劃分的單位網(wǎng)格經(jīng)緯度均為0.01度,這樣區(qū)域被劃分為a*b個網(wǎng)格單元,
按照這種方式劃分之后,每個網(wǎng)格都有自己唯一的編號標(biāo)識.各個維度劃分的網(wǎng)格數(shù)可以按式(1)、(2)計算且向上取整:
其中,amax,amin,bmax,bmin為每個維度的最值,讀取數(shù)據(jù)后,可形成如圖1所示的網(wǎng)格.
圖1 網(wǎng)格單元示意圖
網(wǎng)格劃分和數(shù)據(jù)映射的算法如下:
1.2隸屬概率
每個網(wǎng)格單元包含有兩層鄰居,第一層為緊鄰數(shù)據(jù)點O(a,b),所在網(wǎng)格單元的周圍的外部網(wǎng)格單元,第二層為緊鄰第一層鄰居周圍的外部網(wǎng)格單元.將這兩層鄰居稱為O(a,b)所在單元網(wǎng)格的鄰近網(wǎng)格單元.
對于數(shù)據(jù)點O(a,b),假設(shè)O∈Gi,j,則O(a,b)所在單元網(wǎng)格單元的鄰近網(wǎng)格單元集為
數(shù)據(jù)集中S一個對象O(a,b)為DB(P,N)-Outlier,如果它滿足以下性質(zhì): 數(shù)據(jù)集S中至少q*100%的對象處于臨近單元網(wǎng)格集G之外.這里隸屬概率為p=1-q*100%.換句話說,如果存在少于n (n=N*p*100%,N為數(shù)據(jù)集的總數(shù))個鄰居數(shù)據(jù)點位于G集合以內(nèi),則O(a,b)是關(guān)于隸屬概率為p的DB(P,N)離群點.
隸屬概率公式為: p=n/N (其中n為處于的鄰近網(wǎng)格單元集合G內(nèi)的數(shù)據(jù)點個數(shù),N為數(shù)據(jù)空間中數(shù)據(jù)點的總個數(shù).)
1.3基站空間位置關(guān)系
參考文獻(xiàn)[9]提出的結(jié)論可知,無論城市區(qū)域還是鄉(xiāng)村區(qū)域,所有基站的位置分布并不是相互獨立的,城市內(nèi)的基站分布表現(xiàn)了比較強烈的聚類特點.而本文主要對密集城區(qū)的基站進行分析,核查離群點基站.顯而易見,密集城市中的基站與它近鄰的基站之間的距離應(yīng)該處于大致均勻的分布中,而且不會相差很遠(yuǎn).
考慮到用戶通過蜂窩網(wǎng)進行LBS服務(wù)時,需要與用戶所處地理位置的基站進行交互,日志信息中保留了基站的編號信息、上下線的用戶經(jīng)緯度信息、交互的時間信息等.雖然基站的地理位置獲取困難,但是用戶的簽到信息獲取相對容易.對于基站密度比較密集的城區(qū),由于基站的覆蓋范圍較小,用戶的簽到信息過于密集、越區(qū)切換較頻繁,可以利用用戶一段時間的簽到軌跡信息關(guān)聯(lián)出一個基站ID網(wǎng)格序列(即臨近基站),然后根據(jù)這些臨近基站的位置特點來核實目標(biāo)基站的位置.
1.4用戶簽到信息
如圖2所示,從海量日志文件中提取關(guān)鍵的特征信息來表示用戶簽到軌跡Tr[10].Tr是具有時間戳的空間位置序列數(shù)據(jù),Tr=(
圖2 海量日志提取的特征信息網(wǎng)格單元
1.5基站的網(wǎng)格序列
每個基站ID也有唯一的地理位置
(1)Ai在時間范圍△t內(nèi)所處的地理位置
(2)在△t/2時刻及很小的鄰域范圍內(nèi),Ai(1≦i≦n)經(jīng)過了相同的基站,該基站即為目標(biāo)基站,而根據(jù)時間△t關(guān)聯(lián)出的其他基站均為臨近基站.
(3)GridIDs中的元素均為臨近基站所在的網(wǎng)格單元,包括目標(biāo)基站所在的單元網(wǎng)格.
如圖3所示,虛線表示用戶A的簽到軌跡信息,實線表示用戶軌跡對應(yīng)的基站序列信息,目標(biāo)基站位于G2,2中,G2,2的GridIDs={ G1,1,G2,3,G1,3，G2,2},實際情況中經(jīng)過目標(biāo)基站的用戶可能不止用戶A,應(yīng)該把所有符合情況的臨近基站補充完整,并且將這些臨近基站所屬網(wǎng)格也全部添加到GridIDs集合中.
圖3 用戶簽到軌跡對應(yīng)的基站的網(wǎng)格轉(zhuǎn)換圖示
2 基于網(wǎng)格概率的離群點識別
2.1算法描述
首先按照數(shù)據(jù)集D(所有的基站)的維度將數(shù)據(jù)空間劃分為多個相鄰的網(wǎng)格單元,遍歷數(shù)據(jù)集將其映射到所屬的網(wǎng)格單元中,從而將無序的數(shù)據(jù)集合轉(zhuǎn)換成一種有序的數(shù)據(jù)結(jié)構(gòu).然后根據(jù)海量日志文件中的用戶軌跡信息關(guān)聯(lián)出空間數(shù)據(jù)點之間的聯(lián)系,即目標(biāo)基站點和臨近基站點的關(guān)系,進而轉(zhuǎn)換為基站所在網(wǎng)格之間的關(guān)系.根據(jù)隸屬概率的概念,判斷該目標(biāo)基站是否為離群點基站.
算法流程如圖4所示.
圖4 算法流程圖
2.2算法說明
(1)將待核實的所有基站最初標(biāo)記為unvisited,在遍歷數(shù)據(jù)集中的基站點時,將其依次打標(biāo)為BSGoal,通過參照臨近基站位置計算出隸屬概率之后將目標(biāo)基站標(biāo)記為visited.算法結(jié)束的條件為所有待核實的基站標(biāo)號均為visited.
(2)算法在每次確定目標(biāo)基站之后,必須根據(jù)時間戳計算出該目標(biāo)基站的臨近基站,即重新確定臨近網(wǎng)格集合的范圍,這是由用戶的簽到軌跡信息決定的.
3 實驗與性能分析
3.1實驗數(shù)據(jù)源
實驗數(shù)據(jù)采用兩個數(shù)據(jù)集,做對比分析的原始測試基站數(shù)據(jù)來自采集到的國內(nèi)某收費網(wǎng)站,數(shù)據(jù)量為7334825; 用戶軌跡數(shù)據(jù)為某LBSN網(wǎng)站華中某省2015年2月5日到2015年2月11 共7天的簽到數(shù)據(jù),數(shù)據(jù)總量為128163870.本文只對用戶的群體特征進行分析,不對用戶的敏感信息進行挖掘,對基站信息只用于核實正誤,不用于其他不安全的行為.
實驗開始前對兩個數(shù)據(jù)集進行預(yù)處理[11],如針對基站編碼不符合編碼規(guī)范中國移動的基站不以“46000”開頭,經(jīng)緯度倒置,經(jīng)緯度明顯錯誤,用戶位置信息重復(fù)等問題進行過濾.經(jīng)過預(yù)處理之后的基站基礎(chǔ)表中的數(shù)據(jù)為7152425條,用戶數(shù)據(jù)為128152794 條,明顯減少了數(shù)據(jù)的運算量.
3.2基站離群點檢測
根據(jù)網(wǎng)格劃分的規(guī)則,每個基站都會被映射到唯一的一個網(wǎng)格單元中,基于網(wǎng)格概率算法的網(wǎng)格劃分可以復(fù)用網(wǎng)格,為了設(shè)置算法中的參數(shù),即隸屬概率p,對每個網(wǎng)格的基站數(shù)量做統(tǒng)計分析,抽樣華中某省的原始測量基站總數(shù)為611440,其對應(yīng)的地理位置劃分網(wǎng)格為54607,平均每個網(wǎng)格中有11.2個基站.圖5為網(wǎng)格中所含基站的統(tǒng)計情況
圖5 網(wǎng)格包含基站個數(shù)的百分比示意圖
由于不同樣本的基站分布情況不同,故隸屬概率取值也會有所不同.在前面先抽取的樣本中,有85.73%的網(wǎng)格中所含的基站在10個以下,結(jié)合網(wǎng)格的面積約為1.21平方公里,顯而易見,基站與基站之間的距離不會很遠(yuǎn),這里分別取p=60%,p=70%,p=80%,p=90%對樣本數(shù)據(jù)進行離群點檢測,抽樣樣本總數(shù)據(jù)量為611440.檢測結(jié)果如表1所示.
表1 基于網(wǎng)格概率的離群點檢測測試結(jié)果
從表1可以明顯的觀察到,隸屬概率的值越小,滿足離群條件的離群點數(shù)量越少.由于隸屬概率與臨近基站點(上文提到)的數(shù)量成正比,隸屬概率越大,說明滿足離群點的條件的精度要求高,導(dǎo)致離群點數(shù)越多,但是結(jié)果不準(zhǔn)確.所以必須選擇一個適中的隸屬概率,結(jié)合表中的結(jié)果可知,隸屬概率選擇p=80%比較適合.
3.3實驗結(jié)果驗證
采用可視化工具Tableau來驗證上面離群點檢測結(jié)果.Tableau[12]是一款強大的可視化工具,它能夠創(chuàng)建與共享數(shù)據(jù)可視化內(nèi)容,快速處理數(shù)據(jù),并且能夠?qū)Χ喾N數(shù)據(jù)源提供接口,圖標(biāo)展示美觀,是一種將數(shù)據(jù)運算與美觀的圖標(biāo)相結(jié)合的工具,應(yīng)用非常廣泛.利用Tableau進行地理數(shù)據(jù)可視化時,只需要導(dǎo)入經(jīng)緯度數(shù)據(jù)信息后,選擇對應(yīng)的數(shù)據(jù)列標(biāo)注為地理角色,然后選擇地圖圖層信息,就可以將輸入坐標(biāo)信息準(zhǔn)確展現(xiàn).但是當(dāng)數(shù)據(jù)集過大時,視覺上是看不出具體的離群點的位置,故本文的實驗是在找出部分離群點之后,對比分析這些離群點在樣本中所標(biāo)識的位置與Tableau上所映射的位置是否在同一塊區(qū)域,比如一個省,或者一個市.很容易觀察出離群點是否跨市或者跨省.
下面將實驗檢測出的離群點情況分別映射到某省的地圖上(實驗數(shù)據(jù)來自網(wǎng)絡(luò)獲取的基站信息).如圖6,圖7,圖8,圖9所示,分別對應(yīng)在不同隸屬概率取值的情況下,離群點在Tableau 上的映射情況.
圖6 隸書概率p取60%
圖7 隸書概率p取70%
圖8 隸書概率p取80%
圖9 隸書概率p取90%
圖中藍(lán)色的點表示基站所取的正確省份,比較密集,相對而言,紅色的點表示偏離該省的基站數(shù),可以明顯的觀察到錯誤基站的數(shù)量.將圖6、圖7,圖8,圖9中的離群點占比以曲線的形式直觀展現(xiàn)如下圖10.
圖10 隸屬概率與離群點數(shù)量
3.4實驗結(jié)論
通過多次實驗論證,實驗結(jié)果表明基于網(wǎng)格的離群點檢測算法的準(zhǔn)確度比較高,而且實驗結(jié)論建議隸屬概率取值80%,但是由于不同地區(qū)的基站部署情況不一致,導(dǎo)致檢測結(jié)果會有少許偏差.
3.5實驗應(yīng)用場景
對中國34各省級自治區(qū)按20%抽樣,考慮到數(shù)據(jù)庫的樣本數(shù)量,選取華東六省一市共7個電信基站樣本集作離群點檢測分析,隸屬概率按照80%來計算,結(jié)果如表2.
表2 多地區(qū)的離群點檢測實驗結(jié)果
從表2可以明顯觀察到,各個樣本檢測出的離群點均在3%左右.對于全國百萬數(shù)的基站而言,能檢測出3%的錯誤基站也是非常有價值的,可以減少人工成本.
4 總結(jié)
本文為了找出錯誤基站的位置信息,提出了一種新的離群點檢測方式,通過劃分網(wǎng)格和計算隸屬概率的方法判定離群點,并且通過取各個地區(qū)的基站的做了實驗,得出了比較好的結(jié)果.可以將此方法應(yīng)用到實際的找出錯誤基站的實踐中,很大程度上減少人力勞動.
如果需要得到更精確的結(jié)果,可以綜合考慮繁華度和單位網(wǎng)格內(nèi)的基站數(shù)量,可以得到更好的精度,同時可以將其擴展出錯誤基站經(jīng)緯度數(shù)據(jù)的自動發(fā)現(xiàn),這方面的工作留作下一步研究的思路供研究者參考.
1吳俊偉,朱云龍,庫濤等.基于網(wǎng)格聚類的熱點路徑探測.吉林大學(xué)學(xué)報,2015,45(1).
2韓紅霞.基于距離離群點的分析與研究[學(xué)位論文].鎮(zhèn)江:江蘇大學(xué),2007.
3Knorr EM,Ng RT.Algorithms for mining distance-based outliers in large datasets.Proc.of 24th International Conference on Very Large Data Bases.New York: Morgan Kaufmann.1998.392–403.
4Knorr EM,Ng RT.Finding intensional knowledge of distancebased outliers.Proc.of 25th International Conference on Very Large Data Bases.New York.Morgan Kaufmann.1999.211–222.
5S Ramasmawy RR,Shim K.Efficient algorithms for mining outliers from large dataset.Proc.of 2000 ACM SIGMOD International Conference on Management of Data.Santa Barbara,CA.ACM Press,2000,(6): 427–438.
6Angiulli F,Pizzuti C.Fast outlier detection in high dimensional spaces.Proc.of the 6th European Conference on the Principles of Data Mining and Knowledge Discovery in Database.Helsinki,Finland.2002.19–23.
7程求江.基于NGID-DBSCAN算法與最小包圍圓模型的基站位置分析[碩士學(xué)位論文].武漢:武漢郵電科學(xué)研究院,2015.
8于浩,王斌,肖剛等.基于距離的不確定離群點檢測.計算機研究與發(fā)展,2010,47(3):474–484.
9應(yīng)倩嵐.基于蜂窩網(wǎng)實測數(shù)據(jù)的基站位置與業(yè)務(wù)空間分布研究[碩士學(xué)位論文].杭州:浙江大學(xué).2015.
10王亮,胡坤元,庫濤等.位置不確定移動時空軌跡頻繁模式挖掘.小型微型計算機系統(tǒng),2014,35(12):2659–2663.
11楊小漫.基于位置的服務(wù)中數(shù)據(jù)預(yù)處理研究[碩士學(xué)位論文].鄭州:鄭州大學(xué),2013.
12Nandeshwar A.Tableau 數(shù)據(jù)可視化實戰(zhàn).北京:機械工業(yè)出版社,2014.
Outlier Detection Algorithm Based on Grid Probability
PENG Yan-Bing1,FENG Li-Rong1，2
1(FiberHome Communications Science & Technology Development Co.,Ltd.Nanjing 210019,China)
2(Wuhan Research Institute of Posts and Telecommunications,Wuhan 430074,China)
Abstract:With the rapid development of the mobile networks and intelligent terminals,location-based service has become more and more hotter on the internet,therefore the correction of the base stations’ position becomes a critical factor.For the wrong base stations are uncertain,it proposes a new detecting algorithm based on the probability of the near grids,which is used to verify the wrong base stations.Firstly,it divides the data space into some grids.Secondly,combining with the users’ attendance location information,it gets the track of the base stations in a short dynamic time and maps them to the corresponding grids.Finally,referring to the position characteristics of the base stations,it could give the membership probabilistic and filter the outliers,that are the wrong base stations.The results show that the algorithm has low complexity and high accuracy of detecting the wrong ones.
Key words:location-based service; grid plot; membership probabilistic; outlier detection
收稿時間:①2015-08-17;收到修改稿時間:2015-10-26
