基于优化的ST-DBSCAN算法的智能手机及车辆定位模型

刘云翔，陈 斌，林 涛，施 伟

（1.上海应用技术大学计算机科学与信息工程学院，上海 201400；2.江苏汽车技师学院汽车工程学院，江苏扬州 225000）

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]。

表1 各款智能手机定位数据统计表Table 1 Statistics of positioning data for each smartphone

图1 实验路线Fig.1 Experimental course

图2 中的6.txt 文本所表述的是30 辆中其中一辆测试车辆编号为6 的车载GPS 系统所采集到的数据。数据第一列是车辆编号，第二列是年月日，第三列是测试的时间，第四、第五列数据则描述的是GPS 定位的经纬度坐标。通过GPS 地图匹配软件GPS Track Editor 导入轨迹数据集进行地图匹配，查看噪声数据即偏离地图上标识道路的离群轨迹数据点，对有明显偏差的噪声数据进行剔除，从而尽可能减少对后期聚类算法过程中误差对模型建立结果的影响。

将去除噪声后的数据导出形成新的数据集，如图3所示为某个时刻测试车辆的GPS 定位数据，便于进行下一步的数据分析[4-5]。

图2 车辆GPS 定位数据Fig.2 Vehicle GPS positioning data

图3 预处理后车辆GPS 定位数据Fig.3 Vehicle GPS positioning data after preprocessing

1.4 信令可匹配车辆的识别

车辆轨迹和手机信令轨迹可以抽象成按时间序列组成一系列轨迹点的集合。令Vx(ti,logi,lati,LBSi)表示车载乘客所携带手机x的信令轨迹中的某个点，其含义为车载手机x在ti时刻在基站LBSi覆盖范围由经纬度(logi,lati)标记所在位置。令Vy(ti,logi,lati)表示车辆y在ti时刻由经纬度(logi,lati)标记所在位置。因此，车载手机x的信令轨迹定义为{Vx(t1,log1,lat1,LBS1),Vx(t2,log2,lat2,LBS2),…,Vx(tn,logn,latn,LBSn)} ，其中，t1＜t2＜…＜tn，车辆y的GPS 轨迹点的集合定义为{Vy(t1,log1,lat1)，Vy(t2,log2,lat2)，…，Vy(tm,logm,latm)}，其中t1＜t2＜…＜tm。

由上述采集的车辆及车载手机信令轨迹进行轨迹匹配，如果给定其中一条车载手机信令轨迹的点与某一条既定车辆GPS 轨迹中的点有U%相匹配，其中阈值U≥90，则说明这条给定的手机信令轨迹点集合与该车辆轨迹匹配度高达U%。在采集的所有车载手机信令轨迹中，找到匹配度达到U%的车辆轨迹点的集合，从而进行信令可匹配车辆的识别。

轨迹点匹配公式为：

式中：Lj(tj,logj_L,latj_L)表示tj时刻的基站所在位置；Vy(tj,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 所示。

图4 三维特征的立体圆柱搜索区域Fig.4 Stereoscopic cylindrical search area with three-dimensional features

本文建立的数据定位分析模型基于这种优化STDBSCAN 算法，主要包含三个步骤：

第一阶段，通过某一路段的车载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 密度可达。

优化的ST-DBSCAN 算法步骤如下所示：

input：date collectionN，the cluster of K-meansk

output：ε1,ε2,…,εk,Minpts

Step1：the value ofkis determined by the number of onboard GPS tracks on a certain road segment；

Step2：Use K-means to analyze on the feasible location data collectionN，get the collection of clusters (A1,A2,…,Ak)；

Step3：For each clusterAi，calculate the distance between each two samples， and obtain distance collectionDi,Di=(d1,d2,…,di)；

Step4：Calculate and compare the distancesDi(max) andDi(min) in the collectionDi，and calculate the radiusε=Di(min)+i⋅(Di(max)-Di(min))/N

Step5：Divide the sample collection into several different ranges byε，and find a set of clustersAicontaining the most trajectory data points；

Step6：Repeat the above steps to obtain theεiand Minptsivalues corresponding to different clustersAiin all datasets，and use the calculatedεand the maximum Minpts as the parameter standard values for each cluster

定义5：核心距离：指包含对象的对象p的最小半径，对象p的核心距离定义为：

定义6：可达性-距离：从对象p到q的可到达距离是p核心距离与从p到q的欧几里德距离之间的较大值。

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 所示。

图5 定位数据分析模型流程图Fig.5 Flow chart of establishment of location data analysis model

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 算法对手机定位数据集进行快速聚类，为STDBSCAN 估计每一个簇的Minptsi和εi，通过分类以参数值ε为0.15 和最大的Minpts 值为55 作为标准参数值，可以区分不同的簇。

图6 优化算法的运行结果图Fig.6 Operating results of optimizated algorithm

根据模型分析可以得出车载乘客人数的具体分布情况，由此判断出符合在HOV 车道上行驶的车辆，如图7 所示，符合HOV 车道的车辆有20 辆，8 辆车不符合HOV 车辆规定，另有2 辆车存在缺失值。根据车辆及手机定位数据有明显的聚类特征，说明两者在时空上存在有时空的相似特征。尽管簇之间存在有少数的缺失点和模糊分界点，但是数据总体聚类效果呈现良好状态[4]。

图7 优化算法的结果图Fig.7 Result of Optimizated algorithm

研究表明，在不首先使用K-means 算法预估Minptsi和εi值，而是直接手动定义两者参数值的结果与使用优化的ST-DBSCAN 聚类算法进行分析，利用实验得出定位分析模型的检测准确率和运行时间，将最后的结果与运用传统检测方法在同一路段进行检测对比，结果如表2 所示。

表2 结果对比Table 2 Comparison of detection results of different test methods

由表2 可知，使用优化的ST-DBSCAN 算法进行计算时，模型的准确率由77.54%上升到86.69%，测试时间由1.318 s 减少到1.195 s。测试时间相对减少了，而且准确度变化较为明显，与传统检测方法相比，准确率也有所提升。由此可得出基于该优化的ST-DBSCAN 算法建立的数据分析定位模型对车道车辆行驶检测有较好的适用性，可辅助检测车道上车辆的具体情况。

由于车载乘客存在一人携带多个手机的情况，对于此问题，文献[11]提出获取移动智能手机用户身份信息的设计与实现，文献[12]提出基于大数据融合分析对双卡槽双卡用户进行识别。基于上述一些方法可对一人携带多个手机的问题进行判别，本文模型设计过程中只针对一人携带一部手机的情况进行分析，后期对于该问题仍会进行分析研究，从而更为全面地得出车载乘客的实际人数。

4 结 语

本文研究提出一种应用于HOV 车道的车辆及乘客手机定位数据分析模型，在不需要额外基础设施的情况下可以科学有效地辅助检测高速公路交通车辆运行状况。最终的测试结果表明，通过改进的ST-DBSCAN 算法建立车辆及手机定位数据分析模型，在一定条件下能按现有交通法规对符合行驶在HOV 车道上的车辆进行有效检测，保证一定的准确率，为城市逐步建设HOV 车道检测问题提出一种切实可行的辅助检测方法，为道路交通监管部门实时检测道路路况提供了有效的科学依据。