基于優化的ST?DBSCAN算法的智能手機及車輛定位模型

摘" 要： 為了降低HOV車道檢測所需的建設成本和設備維護費用，進一步擴大監管區域，提出以優化ST?DBSCAN算法建立手機及車輛定位分析模型，能在一定程度上有效判斷出在HOV車道上運行車輛的實際乘客數，為執行HOV車道中車輛實時監測提供一種新的輔助檢測手段。通過采集道路上運行車輛及移動智能手機GPS和基站定位數據，運用優化的ST?DBSCAN聚類算法進行分類建立定位分析模型，計算出各個簇的關鍵對象度量值，根據HOV車道實際規定車載人數作為其最小支持度，滿足最小支持度的數據集就是最后挖掘建立模型的依據。實驗結果表明，該模型在HOV車道上的應用能有效輔助檢測HOV車道車輛并有較高的檢測準確率。

關鍵詞： 定位分析模型; ST?DBSCAN聚類算法; HOV車道; GPS定位; 基站定位; 結果分析

中圖分類號： TN929.5?34" " " " " " " " " " " " 文獻標識碼： A" " " " " " " " " " " " "文章編號： 1004?373X（2019）21?0134?07

Abstract： In order to reduce the cost of construction and equipment maintenance required for HOV lane detection and further expand the regulatory area， a model of mobile phone and vehicle positioning analysis is proposed by optimizing the ST?DBSCAN algorithm， with which the quantity of actual passengers in vehicles running on the HOV lane can be effectively judged to a certain extent， and a new auxiliary detection method is provided for the implementation of real?time monitoring of vehicles in the HOV lane. The optimized ST?DBSCAN clustering algorithm is used to achieve classification establishment of positioning analysis models classify and by collecting GPS and base station positioning data of mobile smart phones and vehicles running on the road， and figure out the key object metrical values of each cluster." The HOV lane regulation about" the actual number of persons on the vehicle is taken as the minimum support to meet the data sets with minimum support for the final mining and model building. The experiment result indicates that the model used in the HOV lane can effectively assist the detection of vehicles on HOV lane and has high detection accuracy.

Keywords： positioning analysis model; ST?DBSCAN clustering algorithm; HOV lane; GPS positioning; base station location; results analysis

0" 引" 言

當前，道路交通路測的方法主要有基于視頻圖像檢測法、紅外線掃描檢測、超聲波檢測法等，這些方法在一定程度上都需要運用額外的基礎儀器設備獲取車輛通過的交通信息，檢測結果的精準度主要取決于檢測儀器自身的精準度、穩定性以及道路上檢測設備的分布程度[1]。在針對國內的HOV車道車輛監測方面，目前交警部門執法人員主要應用紅外熱成像技術識別車輛實載乘員數，依托視頻監控設備對違規駛入HOV車道車輛的自動抓拍從而進行監測執法。這種方法雖然有效，但在前期的基礎設施投資較大，監測主要集中于設備部署范圍內，存在監測盲區。移動智能手機以及定位技術的迅速發展，提供了在不需要額外基礎設施的情況下監測高速公路交通車輛運行狀況的機會。移動智能手機集成GPS模塊、加速感應器、陀螺儀等多種傳感裝置，可以為手機使用者提供基本的移動位置導航服務，將手機定位數據以及車輛定位數據與聚類算法有效地結合，可對道路上車輛內人員的分布情況進行研究分析，并可應用于HOV車道的運行車輛智能檢測。

基于手機信令及GPS定位信息挖掘算法的研究與應用一直受到國內外相關學者的持續關注，不同學者從不同角度進行了分析研究，但在車輛內人員監測方面，采用手機GPS數據信息以及車輛定位數據相結合，應用相關算法分析的研究并不多見。為了解決在HOV車道中監測行駛車輛內乘客人數以及是否出現超員異常的問題，本文結合K?means的ST?DBSCAN聚類算法，在假設車載乘客每人只攜帶一部智能移動手機的條件下，建立車輛及手機定位數據分析模型，可對道路上車輛內人員的分布情況進行研究分析，為進行HOV車道的車輛實時監測提供一種新的輔助檢測方法。

本文提出一種應用優化的ST?DBSCAN算法，通過結合歷史數據挖掘和在線實時檢測兩種方式，基于車載GPS定位數據以及車載乘客的移動智能手機定位數據建立模型，有效地估計判斷出車輛上實際乘客人數，為行駛于HOV車道的車輛實時監測提供一種新的輔助檢測方法。

1" 數據獲取及預處理

1.1 智能手機定位數據產生的原理

目前移動智能手機定位的方式主要有4種，分別是衛星定位（GPS、北斗、伽利略和Glonass）;LBS移動基站定位、WiFi輔助定位和AGPS（AssistedGPS：輔助全球衛星定位系統）定位。本文主要采用手機GPS和LBS移動基站產生的手機位置信息結合車載GPS數據進行數據處理分析。

四大衛星定位系統雖然提供的服務有些差異，但其背后的定位原理都是相同的。手機GPS通過與三到四顆衛星通信進而得知接收器的具體經緯度信息。GPS定位方式不需要手機SIM卡，不需要連接網絡，只要在戶外，基本上隨時隨地都可以準確定位。

LBS移動基站定位是指移動智能手機在插入SIM卡開機以后，可以主動與周圍的基站進行通信，建立聯系，而且在可以搜索到信號的區域，手機根據遠近程度及信號強弱可搜索到多個基站信息，在通信時會選取距離最近、信號最強的基站作為通信基站，及獲取移動智能手機當前的CELL?ID值。

WiFi輔助定位是指由于每個無線路由器都有一個唯一的MAC地址，移動智能手機利用附近無線路由器發送的廣播信息采集其具體的MAC地址和強弱信號程度，運用服務器的“MAC地址?經緯度”的對應分析以及每個信號的強弱程度得出手機的具體定位。

AGPS是一種基于網絡基站信號和GPS定位對未知對象進行定位的方法，利用基地臺代送輔助衛星數據，進而減少取得定位衛星信息的延遲時長，定位效率較高[2]。

1.2 車輛及乘客手機軌跡數據的獲取

為了有效分析車輛與車載乘客人數的關聯程度，本文研究采用了不同品牌和車型的車輛，分別是一汽奧迪Q3、上海大眾LAVIDA1.6、長安福特FOCUS 2013款、奔馳ML400、上海大眾TIGUAN、上海大眾POLO180、五菱宏光643IMF、金龍客車ZK6109H等，共30輛。

在同一時間段內以不同的車速來回行駛在一段1.0 km的實驗道路上，在6條不同的實驗道路上分別測試20次，每次測試過程中每輛車所載乘客數均有所變化，以希望盡可能得到實際道路載人車輛行駛路況，并且每輛車采用的都是同一款GPS導航設備。記錄每輛車在規定行駛道路上每隔相同的數據測行駛點的GPS軌跡點數據。

同時，為了有效對乘客所帶的不同移動智能手機的定位數據作對比分析，本文研究選取具備GPS定位、LBS基站定位功能的華為P系列（華為P10及P10 Plus、華為P9、華為P8）、榮耀系列（榮耀9、榮耀6X、榮耀8、榮耀7X）、魅族PRO7 Plus、魅藍Note6和小米系列（小米MIX 2、小米5X）等各一部，共247部智能手機，使用基于百度地圖開發的移動智能手機定位軟件，測試過程中間隔相同的時間段記錄，此次設置時間間隔為2 s，采集乘客手機的定位數據。

根據實驗需要，安排247名同學分散乘坐在30輛測試車輛中，測試中采集這247部手機來回經過6條不同的實驗道路的20次的軌跡數據以及車載GPS的軌跡數據，定位數據以txt文本形式進行存入，包含定位點的時間、經緯度等具體數據信息。

根據定位軟件的設置，由于不同的手機設備存在性能差異、運營商通信信號穩定性等原因，在不同測試試驗條件中，獲取的數據點個數存在差異，取一條實驗道路上部分智能手機的1次測量結果如表1所示。

1.3 數據預處理

在實際測試中，存在GPS定位偏離、誤差或周邊障礙物遮擋等外部因素對定位數據采集點位置信號的影響，車輛GPS及手機定位數據預處理的目的是使經處理的原始數據可以盡可能體現車輛及車載乘客的真實移動路徑，6條不同的實驗路線如圖1所示[3]。

圖2中的6.txt文本所表述的是30輛中其中一輛測試車輛編號為6的車載GPS系統所采集到的數據。數據第一列是車輛編號，第二列是年月日，第三列是測試的時間，第四、第五列數據則描述的是GPS定位的經緯度坐標。通過GPS地圖匹配軟件GPS Track Editor導入軌跡數據集進行地圖匹配，查看噪聲數據即偏離地圖上標識道路的離群軌跡數據點，對有明顯偏差的噪聲數據進行剔除，從而盡可能減少對后期聚類算法過程中誤差對模型建立結果的影響。

將去除噪聲后的數據導出形成新的數據集，如圖3所示為某個時刻測試車輛的GPS定位數據，便于進行下一步的數據分析[4?5]。

1.4 信令可匹配車輛的識別

由上述采集的車輛及車載手機信令軌跡進行軌跡匹配，如果給定其中一條車載手機信令軌跡的點與某一條既定車輛GPS軌跡中的點有[U]%相匹配，其中閾值[U≥90]，則說明這條給定的手機信令軌跡點集合與該車輛軌跡匹配度高達[U]%。在采集的所有車載手機信令軌跡中，找到匹配度達到[U]%的車輛軌跡點的集合，從而進行信令可匹配車輛的識別。

軌跡點匹配公式為：

式中：[Ljtj，logj_L，latj_L]表示[tj]時刻的基站所在位置;[Vytj，logj_y，latj_y]表示車輛[y]在[tj]時刻由經緯度[logi，lati]標記所在位置;[R]=6 371 km，表示地球的半徑;[G]表示測試的路徑為1 km;[T]表示測試的時間為5 min。

2" 基于K?means的ST?DBSCAN算法建立車輛及手機定位數據分析模型

2.1" 基于K?means的ST?DBSCAN算法原理

DBSCAN作為基本的聚類分析算法，研究的目的是盡可能形成密度可達的數據點最大簇，能快速進行聚類且對噪聲數據的區分，簇的形狀可任意構成。ST?DBSCAN是由Birant D等人在2007年對基本聚類算法DBSCAN加以改進，添加時間特征，用于處理帶有時空特征的數據對象，將二維的平面圓形搜索區域擴展為三維特征的立體圓柱搜索區域[6]，如圖4所示。

本文建立的數據定位分析模型基于這種優化ST?DBSCAN算法，主要包含三個步驟：

第一階段，通過某一路段的車載GPS軌跡點的集合的條數，確定出適合K?means算法所需的[K]值，即表示可行性數據集分配的簇族數;

第二階段，通過K?means算法對可行性數據集快速聚類，統計分析確定出適合ST?DBSCAN算法的兩個參數[ε]和[Minpts]的值;

第三階段，運用ST?DBSCAN算法，根據確定的參數值進行數值調優和聚類分析[7]。

基于這個設計思路，優化的ST?DBSCAN算法需要以下幾個重要的信息：

定義1：[ε]鄰域（[ε]?neighborhood）：以既定對象[p]為中心，[ε]為半徑的區域稱為該對象[p]的[ε]鄰域。

定義2：核心對象：對既定對象[p]，若滿足條件[Nεq≥Minpts]，則將其定義成核心對象。

定義3：直接密度可達（directly density reachable）：在給定的可行性數據集中，[p]從[q]出發時滿足條件：[p∈q]的[ε]?領域，且[Nεq≥Minpts]。

定義4：密度可達（density?reachable）：對于可行性對象集合[N]，如果存在 [p1，p2，…，pn]，[p=p1，q=pn]，對于[pi∈N]，[1≤i≤n]，[pi+1]是從[pi]關于[ε]和[Minpts]直接密度可達，則[p]是從[q]關于ε和 [Minpts]密度可達。

2.2" 基于K?means的ST?DBSCAN算法建立車輛及手機定位數據分析模型

2.2.1" 相關概念

定義1：HOV（High Occupancy Vehicle）即“高占有率的車”，指載客數多的車輛。專為HOV車輛行駛的道路稱為HOV車道，其上允許行駛的車輛包括公交車、車載人數為2人或以上的小客車或貨車[8]。

定義2：平均速度差[9]（Average Speed Difference，ASD）是在給定采集數據的時間內持續經過測量點的單一車道中相鄰車之間速度差絕對值的平均值。

2.2.2" 車速離散度分析

在HOV車道上采集車載GPS數據信息，引用元胞自動機模型中車速離散度（Speed Dispersion，SD），車速離散度指的是在相同的道路上不同車的平均速度差與平均速度之間的比率。若數值越大則表示車輛速度的離散水平越大[10]。本文建立的模型利用平均車速標準差作為數據初步的考量。該參數在一定程度上可以反映車道中相鄰車輛之間的相互作用，為建立車輛及手機定位數據分析模型提供參考依據，其表達式為：

2.2.3" 車速離散度分析

本文研究通過采集在HOV車道上運行車輛的GPS定位數據以及道路上車載乘客手機的海量GPS定位數據和基站定位數據，對采集的數據進行數據格式校驗，剔除邏輯錯誤數據，補齊部分缺失數據等數據預處理操作生成可行性數據集存入數據庫，對其經緯度等具體定位信息與交通道路地圖進行匹配。再次掃描數據庫，通過平均車速標準差初步預估車道交通流稠密程度，將車輛GPS及手機定位數據集運用優化的ST?DBSCAN算法分類，計算出各個簇的關鍵對象度量值[ε]和[Minpts]。將每個簇的關鍵對象度量作為定位分析模型的支持度，由于HOV車道允許行駛公交車、車載人數為2人或以上的小客車或貨車，即[Minpts]大于等于2即可滿足交通法規。

最后將檢測符合條件的行駛車輛數據信息存入對應的數據庫，完成定位數據分析模型的建立，具體流程如圖5所示。

3" 結果分析與評價

通過基于真實車輛及乘客手機定位數據的實驗，評估本文提出的定位分析模型，采用Python實現，運行實驗的PC機軟硬件配置如下： Windows 10的操作系統，PC機CPU型號 Intel 酷睿i7 3520M，CPU主頻2.9 GHz，邏輯處理器4個，內存16 GB，固態硬盤256 GB。

本文通過優化的ST?DBSCAN算法對數據進行分析，測試中其中一次的結果如圖6所示，在運行過程中，首先確定出K?means的[K]值，本文測試車輛以不同的車速在既定路段上來回路程上行駛，此時[K]值為30。運用K?means算法對手機定位數據集進行快速聚類，為ST?DBSCAN估計每一個簇的[Minptsi]和[εi]，通過分類以參數值[ε]為0.15和最大的[Minpts]值為55作為標準參數值，可以區分不同的簇。

根據模型分析可以得出車載乘客人數的具體分布情況，由此判斷出符合在HOV車道上行駛的車輛，如圖7所示，符合HOV車道的車輛有20輛，8輛車不符合HOV車輛規定，另有2輛車存在缺失值。根據車輛及手機定位數據有明顯的聚類特征，說明兩者在時空上存在有時空的相似特征。盡管簇之間存在有少數的缺失點和模糊分界點，但是數據總體聚類效果呈現良好狀態[4]。

研究表明，在不首先使用K?means算法預估[Minptsi]和[εi]值，而是直接手動定義兩者參數值的結果與使用優化的ST?DBSCAN聚類算法進行分析，利用實驗得出定位分析模型的檢測準確率和運行時間，將最后的結果與運用傳統檢測方法在同一路段進行檢測對比，結果如表2所示。

由表2可知，使用優化的ST?DBSCAN算法進行計算時，模型的準確率由77.54%上升到86.69%，測試時間由1.318 s減少到1.195 s。測試時間相對減少了，而且準確度變化較為明顯，與傳統檢測方法相比，準確率也有所提升。由此可得出基于該優化的ST?DBSCAN算法建立的數據分析定位模型對車道車輛行駛檢測有較好的適用性，可輔助檢測車道上車輛的具體情況。

由于車載乘客存在一人攜帶多個手機的情況，對于此問題，文獻[11]提出獲取移動智能手機用戶身份信息的設計與實現，文獻[12]提出基于大數據融合分析對雙卡槽雙卡用戶進行識別。基于上述一些方法可對一人攜帶多個手機的問題進行判別，本文模型設計過程中只針對一人攜帶一部手機的情況進行分析，后期對于該問題仍會進行分析研究，從而更為全面地得出車載乘客的實際人數。

4" 結" 語

本文研究提出一種應用于HOV車道的車輛及乘客手機定位數據分析模型，在不需要額外基礎設施的情況下可以科學有效地輔助檢測高速公路交通車輛運行狀況。最終的測試結果表明，通過改進的ST?DBSCAN算法建立車輛及手機定位數據分析模型，在一定條件下能按現有交通法規對符合行駛在HOV車道上的車輛進行有效檢測，保證一定的準確率，為城市逐步建設HOV車道檢測問題提出一種切實可行的輔助檢測方法，為道路交通監管部門實時檢測道路路況提供了有效的科學依據。

參考文獻

[1] 黃旭.交通視頻中的車輛檢測與跟蹤技術研究及實現[D].成都：電子科技大學，2014.

HUANG Xu. Research and implementation of vehicle detection and tracking technology in traffic video [D]. Chengdu： University of Electronic Science and Technology of China， 2014.

[2] 陳挺偉.淺析移動位置業務中的AGPS定位技術[J].江西水利科技，2014，40（2）：117?119.

CHEN Tingwei. Introduction of AGPS positioning technology in location based service [J]. Jiangxi hydraulic science amp; technology， 2014， 40（2）： 117?119.

[3] 金星.基于智能手機的多用戶軌跡共享機制研究與實現[D].長沙：國防科學技術大學，2014.

JIN Xing. Research and implementation of multi?user trajectory sharing mechanism based on smartphone [D]. Changsha： National University of Defense Technology， 2014.

[4] 陳冰潔.基于聚類算法的車輛軌跡時空相似性研究[D].福州：福建師范大學，2015.

CHEN Bingjie. The study of spatio?temporal similarity of vehicle trajectory data based on the clustering algorithm [D]. Fuzhou： Fujian Normal University， 2015.

[5] BRAKTSOULAS S， PFOSER D， SALAS R， et al. On map?matching vehicle tracking data [C]// Proceedings of 31st International Conference on Very Large Data Bases. Trondheim： IEEE， 2005： 853?864.

[6] 崔鄧.基于智能手機軌跡提取停留點的時空聚類算法研究[D].重慶：西南大學，2016.

CUI Deng. Research on spatial?temporal clustering algorithm based on the extraction of user trajectory of smartphone [D]. Chongqing： Southwest University， 2016.

[7] 劉爽.基于時空軌跡的交通數據分析與應用[D].成都：電子科技大學，2017.

LIU Shuang. Analysis and application of traffic data based on time?space trajectory [D]. Chengdu： University of Electronic Science and Technology of China， 2017.

[8] 詹嘉，潘曉東，高昂. HOV車道的設計應用研究[J].交通與運輸，2007（1）：17?20.

ZHAN Jia， PAN Xiaodong， GAO Ang. The research for the use and design of HOV lane [J]. Traffic amp; transportation， 2007（1）： 17?20.

[9] WANG H， WANG W， CHEN X， et al. Experimental features and characteristics of speed dispersion in urban freeway traffic [J]. Transportation research record： journal of the transportation research board， 2007， 1999（1）： 150?160.

[10] 王昊，王煒，陳竣.車速離散性對高速公路實際通行能力的影響[J].北京工業大學學報，2010，36（10）：1389?1395.

WANG Hao， WANG Wei， CHEN Jun. Effects of speed dispersion on capacity of freeways [J]. Journal of Beijing University of Technology， 2010， 36（10）： 1389?1395.

[11] 陳令，時玉彬.獲取4G用戶身份信息的設計與實現[J].北京工業大學學報，2018，23（4）：103?106.

CHEN Ling， SHI Yubin. Design and implement?ation of acquiring 4G user identity information [J]. Journal of Beijing University of Technology， 2018， 23（4）： 103?106.

[12] 陳錫清.基于大數據融合分析的雙卡槽雙卡用戶識別算法研究[J].福建電腦，2017，52（7）：98?99.

CHEN Xiqing. Research on double?card slot and double?card user identification algorithm based on large data fusion analysis [J]. Fujian computer， 2017， 52（7）： 98?99.

[13] GARG S， SINGH P. Vividhavahana：smartphone based vehicle classification and its applications in developing region [C]// Proceeding of 11th International Conference on Mobile and Ubiquitous Systems. London： ACM， 2014： 364?373.

[14] TAGHVAEEYAN S， RAJAMANI R. Portable roadside sensors for vehicle counting， classification， and speed measurement [J]. IEEE transactions on intelligent transportation systems， 2014， 15（1）： 73?83.

[15] FENG T， TIMMERMANS H J P. Transportation mode recognition using GPS and accelerometer data [J]. Transportation research part C： emerging technologies， 2013， 37（3）： 118?130.

[16] SUN Z， BAN X J. Vehicle classification using GPS data [J]. Transportation research part C： emerging technologies. 2013， 37（3）： 102?117.

[17] 朱宏佳，王丹.考慮ASD和LCR的高速公路多車道交通流元胞自動機模型[J].交通與運輸，2017（7）：50?54.

ZHU Hongjia， WANG Dan. A multilane cellular automaton model in highway considering the average speed difference （ASD） and lane?changing rules （LCR） [J]. Traffic amp; transportation， 2017（7）： 50?54.