基于优化的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.