基于LBS的定位系統的研究與設計

高　翔，張成文

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

?

基于LBS的定位系統的研究與設計

高翔，張成文

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

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

關鍵詞：LBS；聚類算法；定位系統

1　引言

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

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

針對上述問題，提出了異常軌跡點的查找算法，并基于該算法實現基于LBS的定位系統.該系統主要通過異常點檢測算法發現特殊人群的異常軌跡，從而判斷監控對象活動的異常區域，這對異常監控對象監控具有非常具有實際意義.本文的剩余部分安排如下，第二節主要介紹異常軌跡點的查找算法，第三節介紹了基于LBS的定位系統的設計，并給出相關實現結果，第四節對全文進行總結并分析未來研究方向.

2　異常軌跡點的查找算法

異常軌跡點的查找算法的中心思想就是在聚類分析過程中，將異常點盡可能的識別出來，然后在這些異常點中進行查找.通過對DBSCAN算法的分析，可以發現該算法具有良好的異常點檢測能力，然而由于算法的的特性，過多的將正常點歸類與異常點；而由于K- means算法將所有的點劃分到不同的類別中，如果沒有事先定義好相關的K值和K個初始聚類中心，會導致聚類結果不盡人意.由此可見可以將兩種方法結合，然后對他們的優缺點進行互補，將DBSCAN的聚類結果由K- means進行二次分析，從而找出最異常的點.

異常軌跡點查找算法的具體步驟如下：

（1）將目標的定位數據定義為數據集Dataset，并確定該Dataset的參數E和MinPts，由于本文中是定位系統，因此這里的聚類相似度參考值設為點與點之間的距離；

（a）隨機抽取部分數據，并計算各點之間的距離，去中間值作為該Dataset的參數E；

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

（2）根據步驟（1）中確定的參數E和MinPts，對數據集D進行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）經過DBSCAN算法計算得來的所有類簇，并把所有異常點定義為新的簇，并計算出每個簇的數目N1，N2，…，Nn，這些簇分別為W1，W2，…，Wn，其中心分別為C1，C2，…，Cn，最后對整個數據集D進行K- means聚類，其中K=n，聚類中心點為C1，C2，…，CN，具體步驟如下：

repeat

根據聚類中點的均值，將每個點指派到最相似的聚類；

更新聚類均值，即計算每個聚類中點的均值Zj(W)；

until聚類不再發生變化

其中收斂準則函數為差方和函數

（5）輸出聚類結果集，算法結束.

3　定位系統的設計

3.1系統框架設計

本系統采用BS結構，使用MVC框架[4]，通過定位終端系統采集到的定位數據進行處理，并且將分析結果在地圖上顯示，總體框架如圖1所示.

圖1　系統總框架

3.2數據庫設計

系統主要使用的數據包括歷史位置信息，對這些數據進行分析和處理，需要對相關數據進行劃分，這些信息分為時空屬性和非時空屬性，因此系統使用主要的數據表如下.

系統監控對象信息表，主要記錄待定位監控對象的相關信息.

表1　監控對象信息表(PersonInfo)

監控對象位置信息表，主要記錄待定位監控對象的位置信息.

監控對象歷史位置信息表，從結構上這和監控對象位置信息表相同，每隔一段時間PersonLocationInfo的內容轉存入監控對象歷史位置信息表.將主要記錄待定位監控對象的歷史位置信息.

表2　監控對象位置信息表(PersonLocationInfo)

表3　監控對象歷史位置信息表(PersonHistoryLocationInfo)

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

表4　用戶組表(PersonGroup)

表5　用戶表(SubUserInfo)

3.3系統功能設計

本系統主要功能包括查詢結果展示，當前位置查詢，歷史軌跡查詢，區域查詢和時空查詢等功能，具體如圖2所示.

圖2　系統功能圖

其中歷史軌跡查詢，區域查詢和時空查詢使用了異常軌跡點的查找算法得到的結果，具體結果如下所示.

圖3　系統主界面

4　結束語

本文提出了基于LBS定位的定位系統，主要根據對象的歷史位置信息進行時空數據挖掘.本文首先分析了DBSCAN和K- means算法在時空數據挖掘中的優缺點，并根據這兩種算法提出一種異常軌跡點的查找算法，從而發現對象的經常出現的位置信息，基于上述研究設計實現了基于LBS的定位系統，實現了實時定位查詢，時空查詢，異常軌跡分析等功能.通過異常點檢測算法發現特殊人群的異常軌跡，從而判斷監控對象活動的異常區域，這對異常監控對象監控具有非常實際意義.

參考文獻：

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

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

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

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

中圖分類號：TP393

文獻標識碼：A

文章編號：1673- 260X（2015）03- 0009- 03