基于LBS的定位系統(tǒng)的研究與設計.doc

基于LBS的定位系統(tǒng)的研究與設計 高翔，張成文 （蘭州文理學院電子信息工程學院，甘肅蘭州730000） 摘要：LBS的廣泛應用帶來海量的位置信息數(shù)據(jù)，如何充分利用這些數(shù)據(jù)并從中挖掘出隱含其中的知識為決策提供數(shù)據(jù)支持，已經(jīng)成為空間數(shù)據(jù)挖掘技術的重要內(nèi)容。本文重點研究了空間數(shù)據(jù)挖掘中的聚類分析算法，以此提出了基于LBS的定位系統(tǒng)。該系統(tǒng)分析了DBSCAN和K-means算法，并提出了一種改進算法，實現(xiàn)異常位置檢測?；谏鲜鲅芯吭O計實現(xiàn)了基于LBS的定位系統(tǒng)，實現(xiàn)了實時定位查詢，時空查詢，異常軌跡分析等功能。 關鍵詞：lbs；聚類算法；定位系統(tǒng) ：TP393：A：1673-260X（xx）03-0009-03 1引言 基于位置的空間信息服務（LocationBasedService，LBS）1是基于地理信息系統(tǒng)，通過移動計算技術在無線環(huán)境下實現(xiàn)資源共享和數(shù)據(jù)傳輸而衍生的信息服務。LBS通過移動終端確定移動用戶的實際地理位置，從而提高用戶所需要的與位置相關的服務信息。位置服務技術廣泛的應用在民用和軍事的諸多方面，為人們的生活提供極大的便利。隨著無線通信技術和GPS技術的發(fā)展，基于位置的信息數(shù)據(jù)呈指數(shù)倍增長，海量的信息已經(jīng)遠遠超過了人工分析的能力，如何對這些信息進行有效的集成和分析，挖掘出這些空間數(shù)據(jù)背后隱藏的知識，從中發(fā)現(xiàn)出目標的運行規(guī)律，然后利用這些規(guī)律進行決策，實現(xiàn)決策的科學化合理化。 聚類分析是空間數(shù)據(jù)挖掘的常用方法，其通過將特征相近的空間數(shù)據(jù)歸結到一個組內(nèi)，最終根據(jù)不同的特征將數(shù)據(jù)劃分為幾個組。聚類分析結果中組與組之間的差別盡可能大，而組內(nèi)差異盡可能的小。聚類分析廣泛的應用在市場研究，模式識別和圖像處理等，本文采用的方法主要涉及到DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）2和K-means算法3。DBSCAN算法是基于密度的聚類算法，其最重要的兩個參數(shù)為區(qū)域半徑E，以及給定點在E鄰域內(nèi)成為核心對象的最小鄰域點數(shù)MinPts，這兩個參數(shù)在開始時刻設定，該算法的主要缺點是聚類結果對這兩個參數(shù)的依賴性非常大，當數(shù)據(jù)分布不均勻時，參數(shù)的取定對聚類的結果和質(zhì)量有很大的影響。K-means算法需給定初始值K，以及K個初始中心值，不同的K以及初始中心值帶來的聚類結果是不同的，上述兩個值的不同導致應用上的局限性。 針對上述問題，提出了異常軌跡點的查找算法，并基于該算法實現(xiàn)基于LBS的定位系統(tǒng)。該系統(tǒng)主要通過異常點檢測算法發(fā)現(xiàn)特殊人群的異常軌跡，從而判斷監(jiān)控對象活動的異常區(qū)域，這對異常監(jiān)控對象監(jiān)控具有非常具有實際意義。本文的剩余部分安排如下，第二節(jié)主要介紹異常軌跡點的查找算法，第三節(jié)介紹了基于LBS的定位系統(tǒng)的設計，并給出相關實現(xiàn)結果，第四節(jié)對全文進行總結并分析未來研究方向。 2異常軌跡點的查找算法 異常軌跡點的查找算法的中心思想就是在聚類分析過程中，將異常點盡可能的識別出來，然后在這些異常點中進行查找。通過對DBSCAN算法的分析，可以發(fā)現(xiàn)該算法具有良好的異常點檢測能力，然而由于算法的的特性，過多的將正常點歸類與異常點；而由于K-means算法將所有的點劃分到不同的類別中，如果沒有事先定義好相關的K值和K個初始聚類中心，會導致聚類結果不盡人意。由此可見可以將兩種方法結合，然后對他們的優(yōu)缺點進行互補，將DBSCAN的聚類結果由K-means進行二次分析，從而找出最異常的點。 異常軌跡點查找算法的具體步驟如下： （1）將目標的定位數(shù)據(jù)定義為數(shù)據(jù)集Dataset，并確定該Dataset的參數(shù)E和MinPts，由于本文中是定位系統(tǒng)，因此這里的聚類相似度參考值設為點與點之間的距離； （a）隨機抽取部分數(shù)據(jù)，并計算各點之間的距離，去中間值作為該Dataset的參數(shù)E； （b）觀察目標在空間中的分布圖，確定MinPts的值； （2）根據(jù)步驟（1）中確定的參數(shù)E和MinPts，對數(shù)據(jù)集D進行DBSCAN算法聚類，具體聚類步驟如下； （3）經(jīng)過DBSCAN算法計算得來的所有類簇，并把所有異常點定義為新的簇，并計算出每個簇的數(shù)目N1，N2，Nn，這些簇分別為W1，W2，Wn，其中心分別為C1，C2，Cn，最后對整個數(shù)據(jù)集D進行K-means聚類，其中K=n，聚類中心點為C1，C2，具體步驟如下： repeat 根據(jù)聚類中點的均值，將每個點指派到最相似的聚類； 更新聚類均值，即計算每個聚類中點的均值Zj（W）； until聚類不再發(fā)生變化 其中收斂準則函數(shù)為差方和函數(shù) （5）輸出聚類結果集，算法結束。 3定位系統(tǒng)的設計 3.1系統(tǒng)框架設計 本系統(tǒng)采用BS結構，使用MVC框架4，通過定位終端系統(tǒng)采集到的定位數(shù)據(jù)進行處理，并且將分析結果在地圖上顯示，總體框架如圖1所示。 3.2數(shù)據(jù)庫設計 系統(tǒng)主要使用的數(shù)據(jù)包括歷史位置信息，對這些數(shù)據(jù)進行分析和處理，需要對相關數(shù)據(jù)進行劃分，這些信息分為時空屬性和非時空屬性，因此系統(tǒng)使用主要的數(shù)據(jù)表如下。 監(jiān)控對象位置信息表，主要記錄待定位監(jiān)控對象的位置信息。 監(jiān)控對象歷史位置信息表，從結構上這和監(jiān)控對象位置信息表相同，每隔一段時間PersonLocationInfo的內(nèi)容轉存入監(jiān)控對象歷史位置信息表。將主要記錄待定位監(jiān)控對象的歷史位置信息。 用戶組表，主要記錄用戶組信息。 3.3系統(tǒng)功能設計 本系統(tǒng)主要功能包括查詢結果展示，當前位置查詢，歷史軌跡查詢，區(qū)域查詢和時空查詢等功能，具體如圖2所示。 其中歷史軌跡查詢，區(qū)域查詢和時空查詢使用了異常軌跡點的查找算法得到的結果，具體結果如下所示。 4結束語 本文提出了基于LBS定位的定位系統(tǒng)，主要根據(jù)對象的歷史位置信息進行時空數(shù)據(jù)挖掘。本文首先分析了DBSCAN和K-means算法在時空數(shù)據(jù)挖掘中的優(yōu)缺點，并根據(jù)這兩種算法提出一種異常軌跡點的查找算法，從而發(fā)現(xiàn)對象的經(jīng)常出現(xiàn)的位置信息，基于上述研究設計實現(xiàn)了基于LBS的定位系統(tǒng)，實現(xiàn)了實時定位查詢，時空查詢，異常軌跡分析等功能。通過異常點檢測算法發(fā)現(xiàn)特殊人群的異常軌跡，從而判斷監(jiān)控對象活動的異常區(qū)域，這對異常監(jiān)控對象監(jiān)控具有非常實際意義。 參考文獻： （1）黃瀟婷，柴彥威。面向LBS使用者的時間地理學研究評介J。地理科學進展，xx，28（6）：962-969. （2）周水庚，周傲英，曹晶，等。基于數(shù)據(jù)分區(qū)的DBSCAN算法J。計算機研究與發(fā)展，2000，37（10）：1