高　翔，張成文

（蘭州文理學(xué)院　電子信息工程學(xué)院，甘肅　蘭州　730000）

?

基于LBS的定位系統(tǒng)的研究與設(shè)計(jì)

高翔，張成文

（蘭州文理學(xué)院電子信息工程學(xué)院，甘肅蘭州730000）

摘要：LBS的廣泛應(yīng)用帶來海量的位置信息數(shù)據(jù)，如何充分利用這些數(shù)據(jù)并從中挖掘出隱含其中的知識(shí)為決策提供數(shù)據(jù)支持，已經(jīng)成為空間數(shù)據(jù)挖掘技術(shù)的重要內(nèi)容.本文重點(diǎn)研究了空間數(shù)據(jù)挖掘中的聚類分析算法，以此提出了基于LBS的定位系統(tǒng).該系統(tǒng)分析了DBSCAN和K-means算法，并提出了一種改進(jìn)算法，實(shí)現(xiàn)異常位置檢測(cè).基于上述研究設(shè)計(jì)實(shí)現(xiàn)了基于LBS的定位系統(tǒng)，實(shí)現(xiàn)了實(shí)時(shí)定位查詢，時(shí)空查詢，異常軌跡分析等功能.

關(guān)鍵詞：LBS；聚類算法；定位系統(tǒng)

1　引言

基于位置的空間信息服務(wù)(Location Based Service, LBS)[1]是基于地理信息系統(tǒng)，通過移動(dòng)計(jì)算技術(shù)在無線環(huán)境下實(shí)現(xiàn)資源共享和數(shù)據(jù)傳輸而衍生的信息服務(wù).LBS通過移動(dòng)終端確定移動(dòng)用戶的實(shí)際地理位置，從而提高用戶所需要的與位置相關(guān)的服務(wù)信息.位置服務(wù)技術(shù)廣泛的應(yīng)用在民用和軍事的諸多方面，為人們的生活提供極大的便利.隨著無線通信技術(shù)和GPS技術(shù)的發(fā)展，基于位置的信息數(shù)據(jù)呈指數(shù)倍增長(zhǎng)，海量的信息已經(jīng)遠(yuǎn)遠(yuǎn)超過了人工分析的能力，如何對(duì)這些信息進(jìn)行有效的集成和分析，挖掘出這些空間數(shù)據(jù)背后隱藏的知識(shí)，從中發(fā)現(xiàn)出目標(biāo)的運(yùn)行規(guī)律，然后利用這些規(guī)律進(jìn)行決策，實(shí)現(xiàn)決策的科學(xué)化合理化.

聚類分析是空間數(shù)據(jù)挖掘的常用方法，其通過將特征相近的空間數(shù)據(jù)歸結(jié)到一個(gè)組內(nèi)，最終根據(jù)不同的特征將數(shù)據(jù)劃分為幾個(gè)組.聚類分析結(jié)果中組與組之間的差別盡可能大，而組內(nèi)差異盡可能的小.聚類分析廣泛的應(yīng)用在市場(chǎng)研究，模式識(shí)別和圖像處理等，本文采用的方法主要涉及到DBSCAN (Density- Based Spatial Clustering of Applications with Noise)[2]和K- means算法[3].DBSCAN算法是基于密度的聚類算法，其最重要的兩個(gè)參數(shù)為區(qū)域半徑E，以及給定點(diǎn)在E鄰域內(nèi)成為核心對(duì)象的最小鄰域點(diǎn)數(shù)MinPts，這兩個(gè)參數(shù)在開始時(shí)刻設(shè)定，該算法的主要缺點(diǎn)是聚類結(jié)果對(duì)這兩個(gè)參數(shù)的依賴性非常大，當(dāng)數(shù)據(jù)分布不均勻時(shí)，參數(shù)的取定對(duì)聚類的結(jié)果和質(zhì)量有很大的影響.K- means算法需給定初始值K，以及K個(gè)初始中心值，不同的K以及初始中心值帶來的聚類結(jié)果是不同的，上述兩個(gè)值的不同導(dǎo)致應(yīng)用上的局限性.

針對(duì)上述問題，提出了異常軌跡點(diǎn)的查找算法，并基于該算法實(shí)現(xiàn)基于LBS的定位系統(tǒng).該系統(tǒng)主要通過異常點(diǎn)檢測(cè)算法發(fā)現(xiàn)特殊人群的異常軌跡，從而判斷監(jiān)控對(duì)象活動(dòng)的異常區(qū)域，這對(duì)異常監(jiān)控對(duì)象監(jiān)控具有非常具有實(shí)際意義.本文的剩余部分安排如下，第二節(jié)主要介紹異常軌跡點(diǎn)的查找算法，第三節(jié)介紹了基于LBS的定位系統(tǒng)的設(shè)計(jì)，并給出相關(guān)實(shí)現(xiàn)結(jié)果，第四節(jié)對(duì)全文進(jìn)行總結(jié)并分析未來研究方向.

2　異常軌跡點(diǎn)的查找算法

異常軌跡點(diǎn)的查找算法的中心思想就是在聚類分析過程中，將異常點(diǎn)盡可能的識(shí)別出來，然后在這些異常點(diǎn)中進(jìn)行查找.通過對(duì)DBSCAN算法的分析，可以發(fā)現(xiàn)該算法具有良好的異常點(diǎn)檢測(cè)能力，然而由于算法的的特性，過多的將正常點(diǎn)歸類與異常點(diǎn)；而由于K- means算法將所有的點(diǎn)劃分到不同的類別中，如果沒有事先定義好相關(guān)的K值和K個(gè)初始聚類中心，會(huì)導(dǎo)致聚類結(jié)果不盡人意.由此可見可以將兩種方法結(jié)合，然后對(duì)他們的優(yōu)缺點(diǎn)進(jìn)行互補(bǔ)，將DBSCAN的聚類結(jié)果由K- means進(jìn)行二次分析，從而找出最異常的點(diǎn).

異常軌跡點(diǎn)查找算法的具體步驟如下：

（1）將目標(biāo)的定位數(shù)據(jù)定義為數(shù)據(jù)集Dataset，并確定該Dataset的參數(shù)E和MinPts，由于本文中是定位系統(tǒng)，因此這里的聚類相似度參考值設(shè)為點(diǎn)與點(diǎn)之間的距離；

（a）隨機(jī)抽取部分?jǐn)?shù)據(jù)，并計(jì)算各點(diǎn)之間的距離，去中間值作為該Dataset的參數(shù)E；

（b）觀察目標(biāo)在空間中的分布圖，確定MinPts的值；

（2）根據(jù)步驟（1）中確定的參數(shù)E和MinPts，對(duì)數(shù)據(jù)集D進(jìn)行DBSCAN算法聚類，具體聚類步驟如下；

DBSCAN(D, E, MinPts)

C = 0

for each unvisited point P in dataset D

mark P as visited

NeighborPts = regionQuery(P, E)

if sizeof(NeighborPts) < MinPts

mark P as NOISE

else

C = next cluster

expandCluster(P, NeighborPts, C, E, MinPts)

expandCluster(P, NeighborPts, C, E, MinPts)

add P to cluster C

for each point P' in NeighborPts

if P' is not visited

mark P' as visited

NeighborPts' = regionQuery(P', E)

if sizeof(NeighborPts') >= MinPts

NeighborPts = NeighborPts joined with NeighborPts'

if P' is not yet member of any cluster

add P' to cluster C

regionQuery(P, E)

return all points within P's E- neighborhood (including P)

（3）經(jīng)過DBSCAN算法計(jì)算得來的所有類簇，并把所有異常點(diǎn)定義為新的簇，并計(jì)算出每個(gè)簇的數(shù)目N1，N2，…，Nn，這些簇分別為W1，W2，…，Wn，其中心分別為C1，C2，…，Cn，最后對(duì)整個(gè)數(shù)據(jù)集D進(jìn)行K- means聚類，其中K=n，聚類中心點(diǎn)為C1，C2，…，CN，具體步驟如下：

repeat

根據(jù)聚類中點(diǎn)的均值，將每個(gè)點(diǎn)指派到最相似的聚類；

更新聚類均值，即計(jì)算每個(gè)聚類中點(diǎn)的均值Zj(W)；

until聚類不再發(fā)生變化

其中收斂準(zhǔn)則函數(shù)為差方和函數(shù)

（5）輸出聚類結(jié)果集，算法結(jié)束.

3　定位系統(tǒng)的設(shè)計(jì)

3.1系統(tǒng)框架設(shè)計(jì)

本系統(tǒng)采用BS結(jié)構(gòu)，使用MVC框架[4]，通過定位終端系統(tǒng)采集到的定位數(shù)據(jù)進(jìn)行處理，并且將分析結(jié)果在地圖上顯示，總體框架如圖1所示.

圖1　系統(tǒng)總框架

3.2數(shù)據(jù)庫(kù)設(shè)計(jì)

系統(tǒng)主要使用的數(shù)據(jù)包括歷史位置信息，對(duì)這些數(shù)據(jù)進(jìn)行分析和處理，需要對(duì)相關(guān)數(shù)據(jù)進(jìn)行劃分，這些信息分為時(shí)空屬性和非時(shí)空屬性，因此系統(tǒng)使用主要的數(shù)據(jù)表如下.

系統(tǒng)監(jiān)控對(duì)象信息表，主要記錄待定位監(jiān)控對(duì)象的相關(guān)信息.

表1　監(jiān)控對(duì)象信息表(PersonInfo)

監(jiān)控對(duì)象位置信息表，主要記錄待定位監(jiān)控對(duì)象的位置信息.

監(jiān)控對(duì)象歷史位置信息表，從結(jié)構(gòu)上這和監(jiān)控對(duì)象位置信息表相同，每隔一段時(shí)間PersonLocationInfo的內(nèi)容轉(zhuǎn)存入監(jiān)控對(duì)象歷史位置信息表.將主要記錄待定位監(jiān)控對(duì)象的歷史位置信息.

表2　監(jiān)控對(duì)象位置信息表(PersonLocationInfo)

表3　監(jiān)控對(duì)象歷史位置信息表(PersonHistoryLocationInfo)

用戶組表，主要記錄用戶組信息.

表4　用戶組表(PersonGroup)

表5　用戶表(SubUserInfo)

3.3系統(tǒng)功能設(shè)計(jì)

本系統(tǒng)主要功能包括查詢結(jié)果展示，當(dāng)前位置查詢，歷史軌跡查詢，區(qū)域查詢和時(shí)空查詢等功能，具體如圖2所示.

圖2　系統(tǒng)功能圖

其中歷史軌跡查詢，區(qū)域查詢和時(shí)空查詢使用了異常軌跡點(diǎn)的查找算法得到的結(jié)果，具體結(jié)果如下所示.

圖3　系統(tǒng)主界面

4　結(jié)束語

本文提出了基于LBS定位的定位系統(tǒng)，主要根據(jù)對(duì)象的歷史位置信息進(jìn)行時(shí)空數(shù)據(jù)挖掘.本文首先分析了DBSCAN和K- means算法在時(shí)空數(shù)據(jù)挖掘中的優(yōu)缺點(diǎn)，并根據(jù)這兩種算法提出一種異常軌跡點(diǎn)的查找算法，從而發(fā)現(xiàn)對(duì)象的經(jīng)常出現(xiàn)的位置信息，基于上述研究設(shè)計(jì)實(shí)現(xiàn)了基于LBS的定位系統(tǒng)，實(shí)現(xiàn)了實(shí)時(shí)定位查詢，時(shí)空查詢，異常軌跡分析等功能.通過異常點(diǎn)檢測(cè)算法發(fā)現(xiàn)特殊人群的異常軌跡，從而判斷監(jiān)控對(duì)象活動(dòng)的異常區(qū)域，這對(duì)異常監(jiān)控對(duì)象監(jiān)控具有非常實(shí)際意義.

參考文獻(xiàn)：

〔1〕黃瀟婷，柴彥威.面向LBS使用者的時(shí)間地理學(xué)研究評(píng)介[J].地理科學(xué)進(jìn)展，2009，28(6):962-969.

〔2〕周水庚，周傲英，曹晶，等.基于數(shù)據(jù)分區(qū)的DBSCAN算法[J].計(jì)算機(jī)研究與發(fā)展，2000，37(10):1153-1159.

〔3〕楊善林，李永森，胡笑旋，等.K-means算法中的k值優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐，2006，26(2):97-101.

〔4〕張宇，王映輝，張翔南，等.基于Spring的MVC框架設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2010，36(4):59-62.

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673- 260X（2015）03- 0009- 03