轨迹规律的挖掘方法、装置、存储介质及电子设备转让专利
申请号 : CN201811401804.7
文献号 : CN109697221B
文献日 : 2021-07-09
发明人 : 徐丽丽 , 王宇飞 , 董俊龙
申请人 : 东软集团股份有限公司
摘要 :
权利要求 :
1.一种轨迹规律的挖掘方法,其特征在于,所述方法包括:基于历史轨迹数据确定频繁点区域,所述频繁点区域包括频繁起点区域以及频繁终点区域;
根据所述历史轨迹数据中起止点位于所述频繁点区域内的多条轨迹的采样点数据,确定所述频繁起点区域到所述频繁终点区域之间至少一条连通路径;
确定目标轨迹与每一所述连通路径的相似度,并根据所述相似度确定所述目标轨迹所属的连通路径;
所述根据所述历史轨迹数据中起止点位于所述频繁点区域内的多条轨迹的采样点数据,确定所述频繁起点区域到所述频繁终点区域之间至少一条连通路径,包括:从所述历史轨迹数据中提取起点在所述频繁起点区域,以及终点在所述频繁终点区域的多条轨迹的采样点数据;
根据所述采样点数据提取所述频繁起点区域到所述频繁终点区域之间所有路段;
确定各路段之间的接续关系,以得到所述频繁起点区域到所述频繁终点区域之间至少一条连通路径;
根据所述采样点数据提取所述频繁起点区域到所述频繁终点区域之间所有路段,包括:
按照方位角对所述采样点数据进行一次聚类;
按照经纬度对一次聚类结果进行二次聚类,以提取得到所述频繁起点区域到所述频繁终点区域之间所有路段。
2.根据权利要求1所述的方法,其特征在于,所述基于历史轨迹数据确定频繁点区域,包括:
对所述历史轨迹数据的起止点分别进行聚类,以形成多个类簇;
合并类簇中心距离小于距离阈值的类簇,得到多个目标类簇;
确定起止点数量最多的目标类簇为频繁点区域。
3.根据权利要求1所述的方法,其特征在于,每一所述路段包括路段方位角、路段边界以及路段长度,所述确定各路段之间的接续关系,以得到所述频繁起点区域到所述频繁终点区域之间至少一条连通路径,包括:根据每一所述路段的采样点数据的采集时序确定各路段之间的接续关系,并构建路径有向图;
采用广度优先算法或者深度优先算法遍历所述路径有向图,以得到所述频繁起点区域到所述频繁终点区域之间至少一条连通路径。
4.根据权利要求1至3中任一项所述的方法,其特征在于,所述目标轨迹为实时获取到的车辆的行驶路径,所述方法还包括:获取所述目标轨迹所属连通路径的路况信息,将所述路况信息发送给所述车辆。
5.根据权利要求1至3中任一项所述的方法,其特征在于,所述方法还包括:在得到每一所述历史轨迹所属的连通路径后,根据每一所述连通路径包括历史轨迹的数量确定所述连通路径中的频繁路径。
6.一种轨迹规律的挖掘装置,其特征在于,所述装置包括:频繁点区域确定模块,用于基于历史轨迹数据确定频繁点区域,所述频繁点区域包括频繁起点区域以及频繁终点区域;
连通路径确定模块,用于根据所述历史轨迹数据中起止点位于所述频繁点区域内的多条轨迹的采样点数据,确定所述频繁起点区域到所述频繁终点区域之间至少一条连通路径;
路径相似度计算模块,用于确定目标轨迹与每一所述连通路径的相似度,并根据所述相似度确定所述目标轨迹所属的连通路径;
连通路径确定模块包括数据提取子模块,用于从历史轨迹数据中提取起点在频繁起点区域,以及终点在频繁终点区域的多条轨迹的采样点数据;路段提取子模块,用于根据采样点数据提取频繁起点区域到频繁终点区域之间所有路段;关系确定子模块,用于确定各路段之间的接续关系,以得到频繁起点区域到频繁终点区域之间至少一条连通路径;
所述路段提取子模块用于:按照方位角对所述采样点数据进行一次聚类;按照经纬度对一次聚类结果进行二次聚类,以提取得到所述频繁起点区域到所述频繁终点区域之间所有路段。
7.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现权利要求1至5中任一项所述方法的步骤。
8.一种电子设备,其特征在于,包括:存储器,其上存储有计算机程序;
处理器,用于执行所述存储器中的所述计算机程序,以实现权利要求1至5中任一项所述方法的步骤。
说明书 :
轨迹规律的挖掘方法、装置、存储介质及电子设备
技术领域
背景技术
蕴藏在数据中丰富的信息,包括用户的出行习惯、生活经验等。在现有技术中,通常采用如
下方法对轨迹规律进行挖掘:
高,网格太少,轨迹分类效果不佳。
用于采样频率较低的应用场景。
发明内容
包括:
路径;
终点位于频繁终点区域内的多条轨迹的采样点数据,可以刻画出频繁起点区域到频繁终点
区域之间至少一条连通路径,然后通过计算任一轨迹与每一连通路径的相似度,确定与该
轨迹相似度最高的连通路径为它的所属连通路径。这样,可以避免由于特殊点选取不准确
或者特殊值设置不合理对轨迹分类结果造成的影响,即使轨迹的采样频率较低,也能融合
历史轨迹数据刻画出该轨迹的连通路径,提升了对低频采样轨迹进行规律分析的准确性。
附图说明
具体实施方式
提取道路特征,利用现有技术即可实现轨迹规律的挖掘。然而,若轨迹采样频率较低,例如
采样点个数少且分布稀疏,利用现有技术进行轨迹规律的挖掘可能会导致轨迹分类的准确
率不高,甚至无法进行规律分析等问题。
明。
户起点位置信息,例如停车点位置。由于用户停车位置不固定,可以按照合适的半径对停车
点位置进行分区,或者按照聚类算法对起点进行聚类,以得到多个起点区域,并确定包含起
点位置数量最多的区域为频繁起点区域。
点区域、且终点位于频繁终点区域的多条轨迹的采样点数据,该采样点数据包括方向信息
以及位置信息,按照各采样点之间的接续关系可以得到一条或多条频繁起点区域到频繁终
点区域之间的连通路径。
连通路径,也就是说该连通路径包含目标轨迹。其中,目标轨迹可以是任一历史轨迹,也可
以是实时获取到的车辆的行驶轨迹。例如,频繁起点区域到频繁终点区域之间有3条连通路
径,历史轨迹A与连通路径1、连通路径2、连通路径3的相似度分别为75%、1、25%,则历史轨
迹A的所属连通路径为连通路径2。
位于频繁终点区域内的多条轨迹的采样点数据,可以刻画出频繁起点区域到频繁终点区域
之间至少一条连通路径,然后通过计算任一轨迹与每一连通路径的相似度,确定与该轨迹
相似度最高的连通路径为它的所属连通路径。这样,可以避免由于特殊点选取不准确或者
特殊值设置不合理对轨迹分类结果造成的影响,即使轨迹的采样频率较低,也能融合历史
轨迹数据刻画出该轨迹的连通路径,提升了对低频采样轨迹进行规律分析的准确性。
进行聚类,以形成多个起点类簇,其中,DBSAN算法的参数包括给定点在邻域内成为核心对
象的最小邻域点数和邻域半径,可以设置邻域半径范围为(10m,50m)。
可以通过如下公式计算得到:
点区域的多条轨迹的采样点数据。
取得到频繁起点区域到频繁终点区域之间所有路段。
的多个采样点P按照方位角进行类聚,可以得到方位角不同三个路段类别:路段1、路段2和
路段3。对方位角聚类后的各个路段类别内的采样点数据分布进行二次聚类,二次聚类后的
结果如图4所示,共有五个路段类别,分别为路段1.1、路段1.2、路段2.1、路段2.2、路段3。
确定频繁起点区域到频繁终点区域之间的连通路径可以根据每一路段的采样点数据的采
集时序确定各路段之间的接续关系,构建路径有向图,并采用广度优先算法或者深度优先
算法遍历路径有向图,即可得到频繁起点区域到频繁终点区域之间至少一条连通路径。
据的方位角确定路段方向,根据采样点数据的采集时序确定连接关系,所构建的路径有向
图如图5所示。采用广度优先算法或者深度优先算法遍历路径有向图,可以得到频繁起点区
域到频繁终点区域之间的连通路径包括路径1(O‑>A‑>C‑>D‑>E),以及路径2(O‑>B‑>C‑>D‑>
E)。
E,该行程路径与路径1(O‑>A‑>C‑>D‑>E)的相似度为1,与路径2(O‑>B‑>C‑>D‑>E)的相似度
为2/3。定义与行程路径相似度最大的连通路径为行程路径的所属连通路径,那么该行程路
径所属的连通路径为路径1。
可以预测用户的行程,并预先获取该连通路径上的路况信息,以在交通拥堵的情况下及时
通知用户重新规划出行路线,达到规避拥堵风险的目的。
轨迹映射为起点至终点的行程路径,统计每一行程路径与每一连通路径的相似度。通过计
算得到每一行程路径与每一连通路径的相似度,可以确定每一行程路径的所属连通路径,
以及得到每一连通路径所包含的行程路径数量,进一步可以确定包含历史轨迹数量最多的
连通路径为频繁路径。例如,连通路径1、连通路径2、连通路径3包含的历史轨迹数量分别为
1024、375、226,则可以确定连通路径1为频繁起点区域到频繁终点区域之间的频繁路径。基
于频繁路径可以向用户推送周边美食、景区等服务消息。
务。
繁起点区域到频繁终点区域的连通路径;为了保证聚类后路段类别呈现道路线形,利用分
属性聚类的方法,分别按照方位角和经纬度对路段进行聚类,并利用广度或者深度优先搜
索可以得到频繁起点区域到频繁终点区域之间的连通路径,最后将各个历史轨迹映射为从
起点到终点的行程路径,依次对比行程路径与连通路径的相似度,可以确定频繁路径、相似
路径以及不同路径。因而,采用上述方法进行轨迹规律挖掘,可以避免由于特殊点选取不准
确或者特殊值设置不合理对轨迹规律分类结果造成的影响,即使轨迹的采样频率较低,也
能融合历史轨迹数据刻画该轨迹的连通路径,提升了对低频采样轨迹进行规律分析的准确
性,同时扩展了轨迹规律挖掘方法的应用场景。
括:
簇,得到多个目标类簇;确定子模块,用于确定起止点数量最多的目标类簇为频繁点区域。
块,用于根据采样点数据提取频繁起点区域到频繁终点区域之间所有路段;关系确定子模
块,用于确定各路段之间的接续关系,以得到频繁起点区域到频繁终点区域之间至少一条
连通路径。
段。
度优先算法或者深度优先算法遍历路径有向图,以得到频繁起点区域到频繁终点区域之间
至少一条连通路径。
径。
繁终点区域的连通路径;为了保证聚类后路段类别呈现道路线形,利用分属性聚类的方法,
分别按照方位角和经纬度对路段进行聚类,并利用广度或者深度优先搜索可以得到频繁起
点区域到频繁终点区域之间的连通路径,最后将各个历史轨迹映射为从起点到终点的行程
路径,依次对比行程路径与连通路径的相似度,可以确定频繁路径、相似路径以及不同路
径。综上,采用上述装置,可以避免由于特殊点选取不准确或者特殊值设置不合理对轨迹规
律分类结果造成的影响,即使轨迹的采样频率较低,也能融合历史轨迹数据刻画该轨迹的
连通路径,提升了对低频采样轨迹进行规律分析的准确性。
输出(I/O)接口704,以及通信组件705中的一者或多者。
700的操作,这些数据例如可以包括用于在该电子设备700上操作的任何应用程序或方法的
指令,以及应用程序相关的数据,例如联系人数据、收发的消息、图片、音频、视频等等。该存
储器702可以由任何类型的易失性或非易失性存储设备或者它们的组合实现,例如静态随
机存取存储器(Static Random Access Memory,简称SRAM),电可擦除可编程只读存储器
(Electrically Erasable Programmable Read‑Only Memory,简称EEPROM),可擦除可编程
只读存储器(Erasable Programmable Read‑Only Memory,简称EPROM),可编程只读存储器
(Programmable Read‑Only Memory,简称PROM),只读存储器(Read‑Only Memory,简称
ROM),磁存储器,快闪存储器,磁盘或光盘。多媒体组件703可以包括屏幕和音频组件。其中
屏幕例如可以是触摸屏,音频组件用于输出和/或输入音频信号。例如,音频组件可以包括
一个麦克风,麦克风用于接收外部音频信号。所接收的音频信号可以被进一步存储在存储
器702或通过通信组件705发送。音频组件还包括至少一个扬声器,用于输出音频信号。I/O
接口704为处理器701和其他接口模块之间提供接口,上述其他接口模块可以是键盘,鼠标,
按钮等。这些按钮可以是虚拟按钮或者实体按钮。通信组件705用于该电子设备700与其他
设备之间进行有线或无线通信。无线通信,例如Wi‑Fi,蓝牙,近场通信(Near Field
Communication,简称NFC),2G、3G或4G,或它们中的一种或几种的组合,因此相应的该通信
组件705可以包括:Wi‑Fi模块,蓝牙模块,NFC模块。
Signal Processor,简称DSP)、数字信号处理设备(Digital Signal Processing Device,
简称DSPD)、可编程逻辑器件(Programmable Logic Device,简称PLD)、现场可编程门阵列
(Field Programmable Gate Array,简称FPGA)、控制器、微控制器、微处理器或其他电子元
件实现,用于执行上述的轨迹规律的挖掘方法。
储介质可以为上述包括程序指令的存储器702,上述程序指令可由电子设备700的处理器
701执行以完成上述的轨迹规律的挖掘方法。
单变型,这些简单变型均属于本公开的保护范围。
能的组合方式不再另行说明。