基于密度聚类的出租车异常轨迹检测

出租车GPS装备的普及使用产生了大量轨迹数据。出租车异常轨迹的检测和分析，可为惩罚具有欺诈行为的出租车司机提供有益支撑。针对出租车稀疏轨迹，基于轨迹相对相似度检测异常轨迹，由于其具有不对称性，类似于DBSCAN的传统密度聚类方法无法适应此种情况，本文提出基于密度RDBSCAN算法用于出租车异常轨迹聚类检测。对于聚类得出的候选异常轨迹，结合轨迹密度异常值和轨迹长度异常值的概念，利用证据理论综合前述2个因素来判别轨迹的异常程度，进而得到异常程度最高的TOP-N异常轨迹。使用旧金山真实的出租车数据，通过提取相同起点和终点（Origin-Destination, OD）的轨迹集进行实验，实验结果表明本文提出的方法能够有效地检测到异常轨迹，并成功给出异常程度最高的TOP-N异常轨迹。     

基于稀疏采样GPS轨迹数据的路口识别方法

目前的路口识别算法多数在密集采样的全球定位系统(GPS)轨迹数据基础上,采用车辆行驶方向转变作为依据进行路口识别。但稀疏采样的GPS轨迹数据由于采样时间间隔较长,无法准确模拟出车辆行驶方向。为此,针对交叉路口容易发生停车现象的特点,提出一种GPS轨迹数据的路口识别方法。从稀疏采样的GPS轨迹数据中提取出行驶轨迹的停车点及其后续点作为研究对象,依据改进GDBSCAN算法对提取出的停车点进行聚类,判断停车事件发生的热区。运用提取出的后续点对热区进行连通性计算,并根据连通性确定是否存在路口。实验结果表明,该路口识别方法具有较好的识别能力,且与DBSCAN算法相比,聚类速度明显提高。     

基于出租车GPS轨迹和POI数据的商业选址推荐

针对商业选址问题,提出一种基于城市出租车GPS轨迹和POI数据的商业选址推荐算法。首先,对城市出租车GPS轨迹和POI数据进行预处理及地图匹配,然后将城区进行交通小区划分,用OD矩阵分析交通小区之间的交通流量特征,并结合交通小区内POI的分布特征和语义属性,构建基于OD矩阵和对应小区POI数据相结合的商业地址推荐模型。最后,应用兰州市出租车GPS轨迹与POI数据验证了推荐算法的有效性和实用性,并将推荐结果在交通小区尺度上进行可视化呈现。实验结果表明,该推荐算法不仅能够推荐合理的商业选址,为商业选址决策提供快速有效的可视化定量分析方法,同时能够为城市公共服务设施空间布局规划提供决策依据。     

基于密度分区的出租车载客热点区域聚类分析

基于城市居民出行的随机性和出租车行驶的机动性，对出租车轨迹数据进行载客热点区域的挖掘，得到城市居民出行规律。由于出租车轨迹数据密度分布不均匀，应用一般的聚类方法效果不佳，因此提出一种基于密度分区的聚类算法。该算法通过求取每个出租车上车点位置数据的局部密度，得到密度峰值点作为簇中心，实现对轨迹数据集基于密度的快速划分，得到不同密度的轨迹数据集，在此基础上进行二次聚类。实验结果表明，该算法可以有效识别不同密度的出租车载客热点区域，提高聚类结果的精确度。     

基于轨迹信息熵分布的异常轨迹检测方法

针对异常轨迹检测多特征检测和检测单元造成的检测效率低等问题。提出一种基于轨迹信息熵分布的异常轨迹检测方法。该算法根据轨迹偏转角与速度将轨迹分割成若干轨迹段,计算轨迹段间加权多特征距离判断轨迹间相似度,进而完成轨迹聚类并计算出每类代表性轨迹,然后对待检测轨迹进行分割,利用代表性轨迹计算每个轨迹段的信息熵,通过比较轨迹信息熵大小及其分布特点实现异常轨迹检测。大西洋飓风数据仿真实验结果表明该方法提高了聚类效果,克服以整条轨迹检测效率低的缺点,提升了异常轨迹检测算法的有效性。     

基于聚类的出租车异常轨迹检测

出租车全球定位系统数据中蕴含城市交通和移动对象行为的宏观信息,从中可以挖掘出有价值的异常轨迹模式。将位置和几何形状、行驶时间分别作为出租车轨迹的空间与时间特征,根据特征偏离情况划分时间、空间和时空异常轨迹。从轨迹数据中提取相同起终点的轨迹集,将轨迹划分成轨迹片段,计算轨迹间的相似度并进行基于距离和密度的聚类,在空间特征上初步分离出频繁和稀疏轨迹,根据数据异常判定的kσ准则确定时间特征异常的分离阈值,对时间特征进行再次划分,最终实现出租车异常轨迹检测。实验结果表明,该方法能从异常轨迹中挖掘出个性化路线、异常停留位置和交通路段,为智能交通、物流高效规划和执行等提供参考信息。     

基于密度核心的出租车载客轨迹聚类算法

目前常见的轨迹聚类大多基于OPTICS、DBSCAN和K-means等算法,但这些聚类方法的时间复杂度随着轨迹数量的增加会大幅上升。针对该问题,提出一种基于密度核心的轨迹聚类算法。通过引入密度核心的概念,设计轨迹密度计算函数以获取聚类簇的致密核心轨迹,同时利用出租车载客轨迹自身的方向和速度等属性提取轨迹特征点,减少轨迹数据量。在此基础上,根据聚类簇中致密核心轨迹与参与聚类轨迹的相似度距离判断轨迹的匹配程度,进而聚合相似轨迹,并将聚类结果储存在聚类节点中。实验结果表明,与TRACLUS和OPTICS聚类算法相比,该算法能够得到更准确的聚类效果,并且时间效率更高。     

大规模轨迹数据并行化地图匹配算法

为解决大规模轨迹数据的地图匹配问题,提出一种并行化的地图匹配算法。该算法将数据转换为弹性分布式数据集,利用Spark算子并行化计算出轨迹点的匹配路段,对原始GPS轨迹点进行校正,并采用GeoHash编码对候选路段的选取进行优化。采用Spark集群平台和约14.7 GB的西安市出租车轨迹数据对方案的规模增长性、加速比和可扩展性等性能进行了实验分析,并与一种基于Hadoop的同类地图匹配算法进行了性能比较,实验结果显示所设计算法效率提高了约31倍,表明本方案有较大的改进。     

基于深度聚类的航空交通流识别与异常检测研究

针对传统的聚类算法无法捕获高维轨迹数据在低维空间中的隐含关系，且难以定义适当的相似性度量以同时考虑轨迹的局部和全局特征的问题，提出了一种基于深度神经网络的多变量轨迹深度聚类框架(MTDC)并将其用于航空交通流识别与异常检测。该框架主要包含一个非对称的自编码器和一个自定义的轨迹聚类层。自编码器由一维卷积神经网络和双向长短时记忆网络堆叠而成，用于学习原始输入在低维隐空间中的特征表示。轨迹聚类层则通过计算隐空间中样本的Q分布实现聚类。结合自编码器的重建损失和轨迹聚类Q分布定义了一个新的异常分数，用于检测异常轨迹。使用基于广播式自动相关监视(ADS-B)的真实轨迹数据进行实验，结果表明，所提框架能有效地进行航空交通流识别，并能检测出具有实际意义且可解释的异常轨迹。     

A method for real-time trajectory monitoring to improve taxi service using GPS big data

As taxi service is supervised by certain electronic equipment (e.g., global positioning system (GPS) equipment) and network technique (e.g., cab reservation through Uber in USA or DIDI in China), taxi business is a typical electronic commerce mode. For a long time, taxi service is facing a typical challenge, that is, passengers may be detoured and overcharged by some unethical taxi drivers, especially when traveling in unfamiliar cities. As a result, it is important to detect taxi drivers’ misbehavior through taxi’s GPS big data analysis in a real-time manner for enhancing the quality of taxi services. In view of this challenge, an online anomalous trajectory detection method, named OnATrade (pronounced “on a trade,” which means activities in a taxi trade on the fly), is investigated in this paper for improving taxi service using GPS big data. The method mainly consists of two steps: route recommendation and online detection. In the first step, route candidates are generated by using a route recommendation algorithm. In the second step, an online anomalous trajectory detection approach is presented to find taxis that have driving anomalies. Experiments evaluate the validity of our method on large-scale, real-world taxi GPS trajectories. Finally, several value-added applications benefiting from big data analysis over taxi’s GPS data sets are discussed for potential commercial applications.     

多重处理的道路拥堵识别可视化融合分析

目的 随着城市交通拥堵问题的日益严重,建立有效的道路拥堵可视化系统,对智慧城市建设起着重要作用。针对目前基于车辆密度分析法、车速判定法、行驶时间判定法等模式单一,可信度低的问题,提出了一种基于DBSCAN+（density-based spatial clustering of applications with noise plus）的道路拥堵识别可视化方法。方法 引入分块并行计算,相较于传统密度算法,可以适应大规模轨迹数据,并行降维聚类速度快。对结果中缓行区类簇判别路段起始点和终止点,通过曲线拟合和拓扑网络纠偏算法,将类簇中轨迹样本点所表征的路段通过地图匹配算法匹配在电子地图中,并结合各类簇中浮动车平均行驶速度判别道路拥堵程度,以颜色深浅程度进行区分可视化。结果 实验结果表明,DBSCAN+算法相较现有改进的DBSCAN算法时间复杂度具有优势,由指数降为线性,可适应海量轨迹点。相较主流地图产品,利用城市出租车车载OBD（on board diagnostics）数据进行城区道路拥堵识别,提取非畅通路段总检出长度相较最优产品提高28.9%,拥堵识别命中率高达91%,较主流产品城区拥堵识别平均命中率提高15%。结论 在城市路网中,基于DBSCAN+密度聚类和缓行区平均移动速度的多表征道路拥堵识别算法与主流地图产品相比,对拥堵识别率、通勤程度划分更具代表性,可信度更高,可以为道路拥堵识别的实时性提供保障。     

基于出租车数据的载客热点与打车热点研究

面对城市出租车高空载率和乘客打车难问题,本文针对出租车司机端和乘客端分别进行载客热点和打车热点的分析研究,提出了一种基于DBSCAN算法的数据处理模型.利用这个模型对北京市182辆出租车的GPS轨迹数据进行处理,提高了数据精度;对于不同的受众,采用K-means算法对数据进行聚类分析,得到相关热点.实验表明,划分目标用户进行各热点的推荐不仅可以有效地为出租车司机提供高概率的载客热点,乘客打车难问题也有了一种可行的解决方法.     

一种用于居住热区聚类的改进CLIQUE算法

在居住热区分析应用中,已有的CLIQUE算法密度阈值初始化多采用主观性较强的经验值,容易对聚类结果造成不良影响.针对该问题提出了一种自适应密度阈值选取的CLIQUE算法(APS-CLIQUE,Adaptive Parameter Selection-CLIQUE),并对聚类边界进行了优化处理.该算法首先使用四分位数箱型模型排除数据形态两端对结果的干扰,解决密度阈值自适应问题;其次通过边界网格的判定,提高了聚类边界精度.使用UCI标准数据集、成都市出租车GPS轨迹浮动数据集进行了对比实验,实验结果表明本文算法的Dunn指数较CLIQUE算法分别提高了26.53%、28.66%.     

基于样本权重的出租车聚集区识别算法

聚类技术可以用于对具有动态、随机和异步并发特性的出租车对象进行分类。但是,现有的聚类技术认为每个出租车样本对聚类的贡献相同,没有考虑到不同样本的不同影响,这在一定程度上影响了聚类的精度。提出了一种基于样本权重的出租车聚集区识别算法--SFTA_IB算法,算法引入了样本权重来充分反映不同样本的贡献度。在此基础上,将出租车视为原变量X,出租车坐标数据视为相关变量Y,目标是寻求压缩变量T,在T中最大化保留相关变量的信息。实验表明,SFTA_IB算法可以准确识别目标样本周边的出租车聚集区,针对性地指导目标出租车个体的巡游线路,提高乘客搜寻效率。     

Automatic intersection and traffic rule detection by mining motor-vehicle GPS trajectories

The generation of road networks from ubiquitous motor-vehicle GPS trajectories has recently gained wide interest. However, few attempts have been made to automatically extract road network properties such as intersections and traffic rules to facilitate the production of high-quality routable maps. For urban street networks, the vehicle trajectory logged by a GPS receiver tends to be straight on streets and curved at intersections although the local deviation exists due to vehicle paths deviating from road centrelines and GPS positioning errors. This paper uses large curved trajectories at traffic intersections and presents novel algorithms for automatically detecting road intersections and traffic rules. Two inherent issues related to GPS trajectories have been resolved using the proposed approach. First, the serious fluctuations of vehicle trajectories due to multipath reflectivity from high-rise buildings have been eliminated, thereby enabling the effective detection of real curved trajectories occurring at traffic intersections. Second, the heterogeneity of traffic density has been considered when using the curved trajectories to automatically detect road intersections. The proposed algorithm was implemented using open-source software libraries and tested using large taxi trajectories collected in Suzhou City, China. A total of 285 at-grade intersections were detected automatically, and dynamic traffic rules were elucidated for each intersection. Compared with the manually interpreted results, the detection results were high quality and provided detailed information for the construction of a routable map.     

基于经验分布的打车概率和等待时间预测

提出了一种预测乘客在指定位置和指定时间预测打车概率和等待时间的方法。设计了一种将地图离散化,使用特征点修复GPS轨迹的解决方案,且适用于大数据问题;在修复的GPS数据基础上提出了基于经验分布在等待特征点和时间点的打车概率和等待时间模型;并基于该模型预测用户指定位置和指定时间的打车概率。另外给出了基于该模型的增量学习的方法。大规模GPS轨迹数据使用Hadoop平台实现了管理和分析计算,证明了该方案的可行性;预测结果在仿真实验中取得了良好的效果,证明了模型具有较高的准确性,同时可以期望准确性随着数据量的增大而提升;另外该模型得到的特征点和特征时间概率和等待时间的参考表并不会随着GPS轨迹数据的增大而增大,证明了模型有良好的可扩展性。