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

基于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) ：TP393：A：1673-260X（xx）03-0009-03 1引言 基于位置的空間信息服務(wù)（LocationBasedService，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-BasedSpatialClusteringofApplicationswithNoise）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算法聚類，具體聚類步驟如下； （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，具體步驟如下： 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所示。 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ù)表如下。 監(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ì)象的歷史位置信息。 用戶組表，主要記錄用戶組信息。 3.3系統(tǒng)功能設(shè)計(jì) 本系統(tǒng)主要功能包括查詢結(jié)果展示，當(dāng)前位置查詢，歷史軌跡查詢，區(qū)域查詢和時(shí)空查詢等功能，具體如圖2所示。 其中歷史軌跡查詢，區(qū)域查詢和時(shí)空查詢使用了異常軌跡點(diǎn)的查找算法得到的結(jié)果，具體結(jié)果如下所示。 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)展，xx，28（6）：962-969. （2）周水庚，周傲英，曹晶，等?；跀?shù)據(jù)分區(qū)的DBSCAN算法J。計(jì)算機(jī)研究與發(fā)展，2000，37（10）：1