基于網(wǎng)格概率的離群點(diǎn)檢測(cè)算法①

彭艷兵,馮利容,(烽火通信科技股份有限公司 IAO,南京 009)(武漢郵電科學(xué)研究院 電信系,武漢 430074)

?

基于網(wǎng)格概率的離群點(diǎn)檢測(cè)算法①

彭艷兵1,馮利容1,2
1(烽火通信科技股份有限公司 IAO,南京 210019)
2(武漢郵電科學(xué)研究院 電信系,武漢 430074)

摘 要:隨著移動(dòng)網(wǎng)絡(luò)、智能終端的迅猛發(fā)展,基于位置的服務(wù)LBS(Location-based Service)越來(lái)越熱門(mén),因此基站位置信息的正確與否成為關(guān)注的重點(diǎn).針對(duì)基站地理位置存在部分錯(cuò)誤這一現(xiàn)象,提出了基于網(wǎng)格概率的離群點(diǎn)檢測(cè)算法來(lái)核查錯(cuò)誤的基站.首先,根據(jù)基站分布的規(guī)則將數(shù)據(jù)空間分成若干網(wǎng)格單元; 其次,根據(jù)用戶軌跡簽到信息關(guān)聯(lián)出其在動(dòng)態(tài)時(shí)間范圍內(nèi)經(jīng)過(guò)的基站序列,將基站序列映射到網(wǎng)格中,計(jì)算出臨近網(wǎng)格單元集合;最后,根據(jù)基站分布特點(diǎn)對(duì)網(wǎng)格單元內(nèi)目標(biāo)基站的臨近基站求隸屬概率,篩選出離群點(diǎn),即錯(cuò)誤的基站.實(shí)驗(yàn)表明,該算法的時(shí)間復(fù)雜度低且核實(shí)準(zhǔn)確率較高.

關(guān)鍵詞:基于位置的服務(wù); 網(wǎng)格劃分; 隸屬概率; 離群點(diǎn)檢測(cè)

近些年,隨著定位技術(shù)的日趨成熟以及定位設(shè)備的大量普及,面向不同的應(yīng)用領(lǐng)域的移動(dòng)終端產(chǎn)生了大量的軌跡數(shù)據(jù).這些數(shù)據(jù)里面蘊(yùn)藏著非常豐富的知識(shí)信息,它能準(zhǔn)確地反映人們的移動(dòng)規(guī)律,能生動(dòng)地體現(xiàn)交通情況,能正確地揭示道路結(jié)構(gòu)[1].目前,與之相關(guān)的數(shù)據(jù)挖掘的研究備受關(guān)注,其中一項(xiàng)比較有現(xiàn)實(shí)意義的研究就是通過(guò)移動(dòng)軌跡數(shù)據(jù)來(lái)檢測(cè)核實(shí)錯(cuò)誤的定位設(shè)備(本文指的是基站).

在移動(dòng)通信發(fā)展的前幾年,各大運(yùn)營(yíng)商對(duì)于基站的建設(shè)沒(méi)有統(tǒng)一的規(guī)劃,導(dǎo)致許多基站的維護(hù)變得非常困難.目前隨著網(wǎng)絡(luò)時(shí)代的飛速發(fā)展,移動(dòng)通信進(jìn)入了高速發(fā)展的通信時(shí)代.因此,移動(dòng)基站坐標(biāo)的正確對(duì)于網(wǎng)絡(luò)發(fā)展來(lái)說(shuō),顯得越來(lái)越重要.但是,由于存在基站信息的變更、人工錄入失誤等因素,導(dǎo)致基站的坐標(biāo)數(shù)據(jù)可能存在3%左右的錯(cuò)誤,同時(shí)運(yùn)營(yíng)商每年更新的基站信息不會(huì)實(shí)時(shí)同步到位置信息服務(wù)商.所以高效地檢測(cè)出錯(cuò)誤的基站是非常有必要的.由于錯(cuò)誤基站的數(shù)量不會(huì)很多,可以將其看做異常點(diǎn)、離群點(diǎn),這種研究非常適用于離群點(diǎn)檢測(cè)這一應(yīng)用場(chǎng)景.

為了有效的檢測(cè)出離群點(diǎn),很多研究人員已經(jīng)開(kāi)發(fā)了大量的離群點(diǎn)檢測(cè)算法,包括基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)算法、基于距離的離群點(diǎn)檢測(cè)算法、基于密度的離群點(diǎn)檢測(cè)算法和基于深度的離群點(diǎn)檢測(cè)算法等,其中基于距離的離群點(diǎn)檢測(cè)算法包含并且擴(kuò)展了基于統(tǒng)計(jì)的思想,需要首先確定參數(shù),然后將非數(shù)值型屬性轉(zhuǎn)換成數(shù)值型數(shù)據(jù),計(jì)算對(duì)象之間的歐式距離,最終確定離群點(diǎn).這算法比較容易理解,而且具有比較直觀的意義,故在實(shí)際場(chǎng)景中的應(yīng)用很多[2].Knorr[3,4]等人最先提出了基于距離的離群點(diǎn)的概念.Ramasmawy對(duì)基于距離的離群點(diǎn)的定義做了改進(jìn),通過(guò)對(duì)與對(duì)象距離最近的第K個(gè)對(duì)象之間的距離排序,將數(shù)據(jù)集中距離排在前面的m個(gè)對(duì)象標(biāo)記為離群點(diǎn)[5].FAngiulli等提出離群點(diǎn)是數(shù)據(jù)集中與其K個(gè)最近鄰居的平均距離最大的前m個(gè)對(duì)象[6],主要通過(guò)比較對(duì)象與K個(gè)最近鄰居的平均距離來(lái)檢測(cè)離群點(diǎn).這些算法將需要N2次的數(shù)據(jù)對(duì)象之間的距離計(jì)算,當(dāng)N很大時(shí)就不適用了.因此,本文在基于距離的思想上,提出基于網(wǎng)格概率的離群點(diǎn)檢測(cè)算法,直接通過(guò)數(shù)據(jù)點(diǎn)處于鄰近網(wǎng)格的概率來(lái)確定離群點(diǎn),避免了計(jì)算N2次的數(shù)據(jù)對(duì)象之間的距離,然后結(jié)合實(shí)際基站位置的空間位置關(guān)系,給出一種高效識(shí)別錯(cuò)誤基站的方法.

1　基本理論知識(shí)

1.1網(wǎng)格劃分和數(shù)據(jù)映射

把地球看成一個(gè)平面圖,選擇一個(gè)中心點(diǎn),中心點(diǎn)選擇“赤道與本初子午線交叉點(diǎn)”,然后以這個(gè)中心點(diǎn)同時(shí)向上下左右按步長(zhǎng)0.01度進(jìn)行擴(kuò)展,每擴(kuò)展一次可以得到一個(gè)長(zhǎng)和寬都為0.01度的正方形,此正方形則為一個(gè)柵格.通過(guò)此算法劃分出的每個(gè)柵格的地理面積約為1.24平方公里左右(地球兩極點(diǎn)除外)[7,8].

按照上述劃分方式,對(duì)本文實(shí)驗(yàn)數(shù)據(jù)空間進(jìn)行劃分.任意給定一地理區(qū)域,將其表示成二維空間M,按照經(jīng)緯度方向分別劃分為a、b等份,a>0 ,b>0且劃分的單位網(wǎng)格經(jīng)緯度均為0.01度,這樣區(qū)域被劃分為a*b個(gè)網(wǎng)格單元,

按照這種方式劃分之后,每個(gè)網(wǎng)格都有自己唯一的編號(hào)標(biāo)識(shí).各個(gè)維度劃分的網(wǎng)格數(shù)可以按式(1)、(2)計(jì)算且向上取整:

其中,amax,amin,bmax,bmin為每個(gè)維度的最值,讀取數(shù)據(jù)后,可形成如圖1所示的網(wǎng)格.

圖1　網(wǎng)格單元示意圖

網(wǎng)格劃分和數(shù)據(jù)映射的算法如下:

1.2隸屬概率

每個(gè)網(wǎng)格單元包含有兩層鄰居,第一層為緊鄰數(shù)據(jù)點(diǎn)O(a,b),所在網(wǎng)格單元的周?chē)耐獠烤W(wǎng)格單元,第二層為緊鄰第一層鄰居周?chē)耐獠烤W(wǎng)格單元.將這兩層鄰居稱(chēng)為O(a,b)所在單元網(wǎng)格的鄰近網(wǎng)格單元.

對(duì)于數(shù)據(jù)點(diǎn)O(a,b),假設(shè)O∈Gi,j,則O(a,b)所在單元網(wǎng)格單元的鄰近網(wǎng)格單元集為

數(shù)據(jù)集中S一個(gè)對(duì)象O(a,b)為DB(P,N)-Outlier,如果它滿足以下性質(zhì): 數(shù)據(jù)集S中至少q*100%的對(duì)象處于臨近單元網(wǎng)格集G之外.這里隸屬概率為p=1-q*100%.換句話說(shuō),如果存在少于n (n=N*p*100%,N為數(shù)據(jù)集的總數(shù))個(gè)鄰居數(shù)據(jù)點(diǎn)位于G集合以內(nèi),則O(a,b)是關(guān)于隸屬概率為p的DB(P,N)離群點(diǎn).

隸屬概率公式為: p=n/N (其中n為處于的鄰近網(wǎng)格單元集合G內(nèi)的數(shù)據(jù)點(diǎn)個(gè)數(shù),N為數(shù)據(jù)空間中數(shù)據(jù)點(diǎn)的總個(gè)數(shù).)

1.3基站空間位置關(guān)系

參考文獻(xiàn)[9]提出的結(jié)論可知,無(wú)論城市區(qū)域還是鄉(xiāng)村區(qū)域,所有基站的位置分布并不是相互獨(dú)立的,城市內(nèi)的基站分布表現(xiàn)了比較強(qiáng)烈的聚類(lèi)特點(diǎn).而本文主要對(duì)密集城區(qū)的基站進(jìn)行分析,核查離群點(diǎn)基站.顯而易見(jiàn),密集城市中的基站與它近鄰的基站之間的距離應(yīng)該處于大致均勻的分布中,而且不會(huì)相差很遠(yuǎn).

考慮到用戶通過(guò)蜂窩網(wǎng)進(jìn)行LBS服務(wù)時(shí),需要與用戶所處地理位置的基站進(jìn)行交互,日志信息中保留了基站的編號(hào)信息、上下線的用戶經(jīng)緯度信息、交互的時(shí)間信息等.雖然基站的地理位置獲取困難,但是用戶的簽到信息獲取相對(duì)容易.對(duì)于基站密度比較密集的城區(qū),由于基站的覆蓋范圍較小,用戶的簽到信息過(guò)于密集、越區(qū)切換較頻繁,可以利用用戶一段時(shí)間的簽到軌跡信息關(guān)聯(lián)出一個(gè)基站ID網(wǎng)格序列(即臨近基站),然后根據(jù)這些臨近基站的位置特點(diǎn)來(lái)核實(shí)目標(biāo)基站的位置.

1.4用戶簽到信息

如圖2所示,從海量日志文件中提取關(guān)鍵的特征信息來(lái)表示用戶簽到軌跡Tr[10].Tr是具有時(shí)間戳的空間位置序列數(shù)據(jù),Tr=(,..,,…,)1≤i≤n,其中Ai表示用戶的手機(jī)賬號(hào)信息,表示空間地理位置信息,Ti為對(duì)應(yīng)位置的時(shí)間戳信息,BSIDi為Ai在Ti時(shí)刻所處的基站覆蓋范圍內(nèi)對(duì)應(yīng)的基站ID.

圖2 海量日志提取的特征信息網(wǎng)格單元

1.5基站的網(wǎng)格序列

每個(gè)基站ID也有唯一的地理位置.通過(guò)用戶的簽到軌跡信息可以關(guān)聯(lián)出該軌跡中基站所在的網(wǎng)格序列GridIDs,GridIDs是一個(gè)無(wú)序的網(wǎng)格集合.GridIDs滿足以下性質(zhì):

(1)Ai在時(shí)間范圍△t內(nèi)所處的地理位置對(duì)應(yīng)的基站ID所映射的網(wǎng)格.

(2)在△t/2時(shí)刻及很小的鄰域范圍內(nèi),Ai(1≦i≦n)經(jīng)過(guò)了相同的基站,該基站即為目標(biāo)基站,而根據(jù)時(shí)間△t關(guān)聯(lián)出的其他基站均為臨近基站.

(3)GridIDs中的元素均為臨近基站所在的網(wǎng)格單元,包括目標(biāo)基站所在的單元網(wǎng)格.

如圖3所示,虛線表示用戶A的簽到軌跡信息,實(shí)線表示用戶軌跡對(duì)應(yīng)的基站序列信息,目標(biāo)基站位于G2,2中,G2,2的GridIDs={ G1,1,G2,3,G1,3，G2,2},實(shí)際情況中經(jīng)過(guò)目標(biāo)基站的用戶可能不止用戶A,應(yīng)該把所有符合情況的臨近基站補(bǔ)充完整,并且將這些臨近基站所屬網(wǎng)格也全部添加到GridIDs集合中.

圖3 用戶簽到軌跡對(duì)應(yīng)的基站的網(wǎng)格轉(zhuǎn)換圖示

2　基于網(wǎng)格概率的離群點(diǎn)識(shí)別

2.1算法描述

首先按照數(shù)據(jù)集D(所有的基站)的維度將數(shù)據(jù)空間劃分為多個(gè)相鄰的網(wǎng)格單元,遍歷數(shù)據(jù)集將其映射到所屬的網(wǎng)格單元中,從而將無(wú)序的數(shù)據(jù)集合轉(zhuǎn)換成一種有序的數(shù)據(jù)結(jié)構(gòu).然后根據(jù)海量日志文件中的用戶軌跡信息關(guān)聯(lián)出空間數(shù)據(jù)點(diǎn)之間的聯(lián)系,即目標(biāo)基站點(diǎn)和臨近基站點(diǎn)的關(guān)系,進(jìn)而轉(zhuǎn)換為基站所在網(wǎng)格之間的關(guān)系.根據(jù)隸屬概率的概念,判斷該目標(biāo)基站是否為離群點(diǎn)基站.

算法流程如圖4所示.

圖4　算法流程圖

2.2算法說(shuō)明

(1)將待核實(shí)的所有基站最初標(biāo)記為unvisited,在遍歷數(shù)據(jù)集中的基站點(diǎn)時(shí),將其依次打標(biāo)為BSGoal,通過(guò)參照臨近基站位置計(jì)算出隸屬概率之后將目標(biāo)基站標(biāo)記為visited.算法結(jié)束的條件為所有待核實(shí)的基站標(biāo)號(hào)均為visited.

(2)算法在每次確定目標(biāo)基站之后,必須根據(jù)時(shí)間戳計(jì)算出該目標(biāo)基站的臨近基站,即重新確定臨近網(wǎng)格集合的范圍,這是由用戶的簽到軌跡信息決定的.

3　實(shí)驗(yàn)與性能分析

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

實(shí)驗(yàn)數(shù)據(jù)采用兩個(gè)數(shù)據(jù)集,做對(duì)比分析的原始測(cè)試基站數(shù)據(jù)來(lái)自采集到的國(guó)內(nèi)某收費(fèi)網(wǎng)站,數(shù)據(jù)量為7334825; 用戶軌跡數(shù)據(jù)為某LBSN網(wǎng)站華中某省2015年2月5日到2015年2月11 共7天的簽到數(shù)據(jù),數(shù)據(jù)總量為128163870.本文只對(duì)用戶的群體特征進(jìn)行分析,不對(duì)用戶的敏感信息進(jìn)行挖掘,對(duì)基站信息只用于核實(shí)正誤,不用于其他不安全的行為.

實(shí)驗(yàn)開(kāi)始前對(duì)兩個(gè)數(shù)據(jù)集進(jìn)行預(yù)處理[11],如針對(duì)基站編碼不符合編碼規(guī)范中國(guó)移動(dòng)的基站不以“46000”開(kāi)頭,經(jīng)緯度倒置,經(jīng)緯度明顯錯(cuò)誤,用戶位置信息重復(fù)等問(wèn)題進(jìn)行過(guò)濾.經(jīng)過(guò)預(yù)處理之后的基站基礎(chǔ)表中的數(shù)據(jù)為7152425條,用戶數(shù)據(jù)為128152794 條,明顯減少了數(shù)據(jù)的運(yùn)算量.

3.2基站離群點(diǎn)檢測(cè)

根據(jù)網(wǎng)格劃分的規(guī)則,每個(gè)基站都會(huì)被映射到唯一的一個(gè)網(wǎng)格單元中,基于網(wǎng)格概率算法的網(wǎng)格劃分可以復(fù)用網(wǎng)格,為了設(shè)置算法中的參數(shù),即隸屬概率p,對(duì)每個(gè)網(wǎng)格的基站數(shù)量做統(tǒng)計(jì)分析,抽樣華中某省的原始測(cè)量基站總數(shù)為611440,其對(duì)應(yīng)的地理位置劃分網(wǎng)格為54607,平均每個(gè)網(wǎng)格中有11.2個(gè)基站.圖5為網(wǎng)格中所含基站的統(tǒng)計(jì)情況

圖5　網(wǎng)格包含基站個(gè)數(shù)的百分比示意圖

由于不同樣本的基站分布情況不同,故隸屬概率取值也會(huì)有所不同.在前面先抽取的樣本中,有85.73%的網(wǎng)格中所含的基站在10個(gè)以下,結(jié)合網(wǎng)格的面積約為1.21平方公里,顯而易見(jiàn),基站與基站之間的距離不會(huì)很遠(yuǎn),這里分別取p=60%,p=70%,p=80%,p=90%對(duì)樣本數(shù)據(jù)進(jìn)行離群點(diǎn)檢測(cè),抽樣樣本總數(shù)據(jù)量為611440.檢測(cè)結(jié)果如表1所示.

表1　基于網(wǎng)格概率的離群點(diǎn)檢測(cè)測(cè)試結(jié)果

從表1可以明顯的觀察到,隸屬概率的值越小,滿足離群條件的離群點(diǎn)數(shù)量越少.由于隸屬概率與臨近基站點(diǎn)(上文提到)的數(shù)量成正比,隸屬概率越大,說(shuō)明滿足離群點(diǎn)的條件的精度要求高,導(dǎo)致離群點(diǎn)數(shù)越多,但是結(jié)果不準(zhǔn)確.所以必須選擇一個(gè)適中的隸屬概率,結(jié)合表中的結(jié)果可知,隸屬概率選擇p=80%比較適合.

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

采用可視化工具Tableau來(lái)驗(yàn)證上面離群點(diǎn)檢測(cè)結(jié)果.Tableau[12]是一款強(qiáng)大的可視化工具,它能夠創(chuàng)建與共享數(shù)據(jù)可視化內(nèi)容,快速處理數(shù)據(jù),并且能夠?qū)Χ喾N數(shù)據(jù)源提供接口,圖標(biāo)展示美觀,是一種將數(shù)據(jù)運(yùn)算與美觀的圖標(biāo)相結(jié)合的工具,應(yīng)用非常廣泛.利用Tableau進(jìn)行地理數(shù)據(jù)可視化時(shí),只需要導(dǎo)入經(jīng)緯度數(shù)據(jù)信息后,選擇對(duì)應(yīng)的數(shù)據(jù)列標(biāo)注為地理角色,然后選擇地圖圖層信息,就可以將輸入坐標(biāo)信息準(zhǔn)確展現(xiàn).但是當(dāng)數(shù)據(jù)集過(guò)大時(shí),視覺(jué)上是看不出具體的離群點(diǎn)的位置,故本文的實(shí)驗(yàn)是在找出部分離群點(diǎn)之后,對(duì)比分析這些離群點(diǎn)在樣本中所標(biāo)識(shí)的位置與Tableau上所映射的位置是否在同一塊區(qū)域,比如一個(gè)省,或者一個(gè)市.很容易觀察出離群點(diǎn)是否跨市或者跨省.

下面將實(shí)驗(yàn)檢測(cè)出的離群點(diǎn)情況分別映射到某省的地圖上(實(shí)驗(yàn)數(shù)據(jù)來(lái)自網(wǎng)絡(luò)獲取的基站信息).如圖6,圖7,圖8,圖9所示,分別對(duì)應(yīng)在不同隸屬概率取值的情況下,離群點(diǎn)在Tableau 上的映射情況.

圖6　隸書(shū)概率p取60%

圖7　隸書(shū)概率p取70%

圖8　隸書(shū)概率p取80%

圖9　隸書(shū)概率p取90%

圖中藍(lán)色的點(diǎn)表示基站所取的正確省份,比較密集,相對(duì)而言,紅色的點(diǎn)表示偏離該省的基站數(shù),可以明顯的觀察到錯(cuò)誤基站的數(shù)量.將圖6、圖7,圖8,圖9中的離群點(diǎn)占比以曲線的形式直觀展現(xiàn)如下圖10.

圖10　隸屬概率與離群點(diǎn)數(shù)量

3.4實(shí)驗(yàn)結(jié)論

通過(guò)多次實(shí)驗(yàn)論證,實(shí)驗(yàn)結(jié)果表明基于網(wǎng)格的離群點(diǎn)檢測(cè)算法的準(zhǔn)確度比較高,而且實(shí)驗(yàn)結(jié)論建議隸屬概率取值80%,但是由于不同地區(qū)的基站部署情況不一致,導(dǎo)致檢測(cè)結(jié)果會(huì)有少許偏差.

3.5實(shí)驗(yàn)應(yīng)用場(chǎng)景

對(duì)中國(guó)34各省級(jí)自治區(qū)按20%抽樣,考慮到數(shù)據(jù)庫(kù)的樣本數(shù)量,選取華東六省一市共7個(gè)電信基站樣本集作離群點(diǎn)檢測(cè)分析,隸屬概率按照80%來(lái)計(jì)算,結(jié)果如表2.

表2　多地區(qū)的離群點(diǎn)檢測(cè)實(shí)驗(yàn)結(jié)果

從表2可以明顯觀察到,各個(gè)樣本檢測(cè)出的離群點(diǎn)均在3%左右.對(duì)于全國(guó)百萬(wàn)數(shù)的基站而言,能檢測(cè)出3%的錯(cuò)誤基站也是非常有價(jià)值的,可以減少人工成本.

4　總結(jié)

本文為了找出錯(cuò)誤基站的位置信息,提出了一種新的離群點(diǎn)檢測(cè)方式,通過(guò)劃分網(wǎng)格和計(jì)算隸屬概率的方法判定離群點(diǎn),并且通過(guò)取各個(gè)地區(qū)的基站的做了實(shí)驗(yàn),得出了比較好的結(jié)果.可以將此方法應(yīng)用到實(shí)際的找出錯(cuò)誤基站的實(shí)踐中,很大程度上減少人力勞動(dòng).

如果需要得到更精確的結(jié)果,可以綜合考慮繁華度和單位網(wǎng)格內(nèi)的基站數(shù)量,可以得到更好的精度,同時(shí)可以將其擴(kuò)展出錯(cuò)誤基站經(jīng)緯度數(shù)據(jù)的自動(dòng)發(fā)現(xiàn),這方面的工作留作下一步研究的思路供研究者參考.

1吳俊偉,朱云龍,庫(kù)濤等.基于網(wǎng)格聚類(lèi)的熱點(diǎn)路徑探測(cè).吉林大學(xué)學(xué)報(bào),2015,45(1).

2韓紅霞.基于距離離群點(diǎn)的分析與研究[學(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于浩,王斌,肖剛等.基于距離的不確定離群點(diǎn)檢測(cè).計(jì)算機(jī)研究與發(fā)展,2010,47(3):474–484.

9應(yīng)倩嵐.基于蜂窩網(wǎng)實(shí)測(cè)數(shù)據(jù)的基站位置與業(yè)務(wù)空間分布研究[碩士學(xué)位論文].杭州:浙江大學(xué).2015.

10王亮,胡坤元,庫(kù)濤等.位置不確定移動(dòng)時(shí)空軌跡頻繁模式挖掘.小型微型計(jì)算機(jī)系統(tǒng),2014,35(12):2659–2663.

11楊小漫.基于位置的服務(wù)中數(shù)據(jù)預(yù)處理研究[碩士學(xué)位論文].鄭州:鄭州大學(xué),2013.

12Nandeshwar A.Tableau 數(shù)據(jù)可視化實(shí)戰(zhàn).北京:機(jī)械工業(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

收稿時(shí)間:①2015-08-17;收到修改稿時(shí)間:2015-10-26