《基于轨迹聚类的热点路径分析方法.doc》由会员分享，可在线阅读，更多相关《基于轨迹聚类的热点路径分析方法.doc（5页珍藏版）》请在三一办公上搜索。
1、DOI: 10 3979 / j issn 1673-825X 2011 05 020基于轨迹聚类的热点路径分析方法英1 ，温海平1 ，张旭2夏( 1 重庆邮电大学 计算机学院，重庆 400065; 2 韩国仁荷大学 韩国 仁川 402751)摘 要: 随着智能终端、移动定位、无线通信等技术的快速发展，在交通、物流等应用领域，大量受路网约束的轨迹数据得以收集。利用轨迹数据分析热点路径，可以在时空和语义特征不变的前提下反映移动对象的运动和行为模 式。在提取道路交叉点的基础上，引入轨迹的停留点语义，并将两者共同作为特征点进行轨迹划分，在轨迹聚类的 基础上进行子轨迹权重分析，从而获得语义更为完整且用
2、户关注度更高的热点路径。实验表明了轨迹划分和热点 路径分析方法的有效性。关键词: 路网约束; 轨迹划分; 轨迹聚类; 热点路径中图分类号: TP311. 13文献标识码: A文章编号: 1673-825X( 2011) 05-0602-05Hot route analysis method based on trajectory clusteringXIA Ying1 ，WEN Hai-Ping1 ，ZHANG Xu2( 1 School of Computer Science and Technology，Chongqing University of Posts and Telecommu
3、nications，Chongqing，400065，China;2 Inha University，Incheon，402751，Korea)Abstract: With the development of smart device，mobile positioning and wireless communication technologies，numeroustrajectory data constrained by road network can be collected from application fields such as transportation and lo
4、gistics Hot route analysis using trajectory data is beneficial for reflecting the motion and action patterns of moving objects without chan- ging the spatio-temporal and semantic properties In this paper，the crossing points of road network and semantic feature stops of trajectory are extracted as ch
5、aracteristic points for trajectory partition The hot routes with higher semantic integrity and user attention degree can be acquired by analyzing the weight of sub-trajectories based on the result of trajectory cluste- ring Experiments show that the trajectory partition and hot route analysis method
6、s are effectiveKey words: road network constrain; trajectory partition; trajectory clustering; hot routes点路径，可辅助城市规划、交通管理、用户调查等领域的决策分析2。热点路径可以通过移动对象聚类、高流量路径 的连通性分析、轨迹聚类等方法获得2-3。其中，移引言0随着智能终端、移动定位、无线通信等技术的快速发展，在交通、物流等应用领域，通过智能手机、行 业 PDA( personal digital assistant) 等移动终端能够及 时收集大量的轨迹数据。这些轨迹数据包括时间、 位置、
7、速度等基础信息，并在空间上受道路网络的约 束，其中蕴含着丰富的知识1。热点路径通常是指 移动对象频繁经过的路线，一定程度上反映着移动 对象的个体或群体运动模式。从轨迹数据中获取热动对象聚类方法侧重于分析移动对象的静态分布。高流量路径的连通性分析方法涉及流量统计和道路连通性判定，侧重于分析移动对象的群体性模式，处 理过程复杂。而基于轨迹聚类的热点路径分析方法 可直接利用原始轨迹数据，通过发现相似的子轨迹 来反映移动对象的运动和行为模式。这种方法有利收稿日期: 2011-04-01 修订日期: 2011-07-10基金项目: 重庆市计算机网络与通信技术重点实验室开放基金( CY-CNCL-2009
8、-01) ; 重庆市科委科技项目( CSTC2009CB2015)Foundation Items: The Open Foundation of Chongqing Computer Networks and Communications Technology Laboratory ( CY-CNCL-2009-01) ; The Project of Chongqing Municipal Science and Technology Commission( CSTC 2009CB2015)于保持轨迹原有的时空和语义特性不变，且同时适合于移动对象个体和群体的模式分析。目前已有很多轨迹聚类方
9、法被提出。张延玲 等4提出 T-CLUS 方法，通过轨迹聚类得到运动模 式。Ahmed Kharrat 等5提出了路网空间下基于密 度的轨迹聚类方法 NETSCAN，该方法首先根据移动 对象经过的道路计算出繁忙路径，然后根据用户设( 2) 式 中:Lc ( Traji ，Trajj )表 示 轨 迹 Traji 和 轨 迹Trajj 的重叠子轨迹累积长度;L( Traji )表示轨迹Traji 在空间或时间特性上的累积长度。根据以上定义，2 个轨迹的空间相似度( spatialsimilarity，Sim ) 与时间相似度 ( temporalsimilarity，SSimT ) 可分别计算。
10、2 个轨迹的时空相似度( spatio-temporal similarity，SimST ) 可由空间相似度与时间相似性的乘积得到7，即SimST ( Traji ，Trajj ) = SimS ( Traji ，Trajj ) 置的密 度参数对子轨迹进行聚 类。 Jung-ImWon等6提出首先计算重叠路段长度的相似度，然后进行聚类。Xia Ying 等7提出了在路网约束下综合考 虑时间和空间约束的轨迹相似性度量方法，并应用 于轨迹聚类。实际上，轨迹数据中包含有丰富的语义，如行 进、停留、畅通、拥堵等。热点路径可以理解为移动 对象频繁经过的路段或停留的区域，它们都体现了 移动用户在运动或行
11、为过程中对某地理空间的关注程度。目前的轨迹聚类方法中，主要考虑了轨迹的时间和空间特征，但对轨迹本身所具有的语义特征 利用不足。本文在文献7中提出的综合考虑时空 约束的轨迹相似性度量方法的基础上，通过增加停 留点( stop) 语义信息来提高子轨迹划分的合理性， 并通过轨迹聚类和子轨迹权重分析获得更加合理的 热点路径。SimT ( Traji ，Trajj )( 3)( 3) 式中，Sim 取值为0，1 ，0 表示 2 条轨迹在时ST空上不相关，1 表示两条轨迹在时空上重叠。2 个轨迹的时空距离( spatio-temporal distance，7DistST ) 用其时空相异度表示 ，即Di
12、stST ( Traji ，Trajj ) = 1 SimST ( Traji ，Trajj )( 4)( 4) 式中: DistST 的取值为0，1 ; 0 表示两条轨迹在 时空上重叠; 1 表示两条轨迹在时空上不相关。增加停留点语义的轨迹划分方法轨迹划分是轨迹聚类的基础，其前提是找到反 映轨迹变化的特征点，从而将轨迹划分为若干个时 间和空间上相邻的子轨迹4。在文献7中，考虑到移动对象的运动空间受 路网的限制，在道路交叉点( crossing points) 会出现 明显的汇集或分流状态，因此很自然地将道路交叉 点作为轨迹的特征点。实际上，原始的轨迹数据中 还蕴含着丰富的语义，如移动对象在何
13、地停留了多 长时间等。适当地增加语义特征有利于更全面地表 达移动对象的运动和行为状态。2相关概念现实中，人们大多通过离散的位置序列来描述 物体的运动过程。轨迹( trajectory，简写为 Traj) 由 随时间连续变化的位置序列构成。特征点( charac- teristic points，CP) 7是指运动或状态发生明显变化 的位置，通过特征点可将轨迹划分为若干个子轨迹( subTrajectory，subTraj) ，即Traj = subTraj1 ， ，subTraji ， ，subTrajn ( 1)( 1) 式中，subTraji 表示第 i 个子轨迹段。子轨迹是 轨迹聚类的最
14、小单元。18提出了一种新的轨迹模型。 在Spaccapietra该模型中，停留点( stops) 和运动( moves) 2 个集合用于体现轨迹本身的语义。其中，停留点表示移动对 象处于相对静止状态时的位置集合，而运动表示移 动对象行进的子轨迹段集合。本文引入文献8中 的停留点语义，将停留点理解为某移动对象停留时 间超过阈值 T 的某位置或区域，并将道路交叉点和时 空 相 似 性 度 量 (spatio-temporal similaritymeasure) 是轨迹聚类的基本操作，它描述了 2 个轨迹在时间和空间上的相似程度。轨迹 Traji 和 Trajj 的相似程度可以表示为两者在某特征上
15、的重叠子轨 迹累积长度与两者累积长度之和减去重叠子轨迹累 积长度的比值，其计算方法如下7停留点共同作为特征点用于轨迹划分，如图 1 所示。从而使得划分后的子轨迹能够保留更加完整的时空和语义信息。Lc ( Traji ，Trajj )基于轨迹聚类的热点路径检测算法基于轨迹聚类的热点路径检测算法的基本思路Sim( Traji ，Trajj )3= L( Traj ) + L( Traj ) L ( Traj ，Traj )ijcij( 2)是，对划分后的子轨迹进行聚类以形成轨迹簇，并在此基础上通过各子轨迹在轨迹簇中的权重分析获得 热点路径。If( TrajSet 中任意两轨迹的重叠子轨迹累积长度
16、MinLns) 生成簇编号 k; CTk = TrajSet;Traji 及 TrajSet 中所有轨迹的状态设置 为 clustered;For each Clustered CTk do For each subTrajj 图 1 轨迹划分中特征点的选取Fig 1 Selection of characteristic points for trajectory partition定义 1轨迹的 时空近邻 N ( Traji ) 是指与 轨迹 Traji 之间的时空距离小于 的轨迹集合。If(W( subTrajj ) )Add SubTraji to HR;假设原始轨迹中的位置点总个数为
17、 n，为了进行 轨迹划分，首先扫描位置点集合并提取道路交叉点和 停留点，其时间复杂度为 O( n) ; 假设轨迹特征点个数 为 m( m n) ，对轨迹进行时空近邻判断并生成簇 的时间复杂度为 O( m2 ) ; 在此基础上，对各子轨迹进轨迹簇( clustered trajectory，CT) 是一定义 2组特征相似的轨迹。定义 3子 轨 迹 权 值 W( subTraji ) 为 子 轨 迹subTraji 在轨迹簇 CT 中的出现次数与该轨迹簇中的轨迹总数的比值。定义 4 当子轨迹权值大于阈值 时，该子轨 迹为热点路径。 取值范围为0，1 ，通常根据领域 知识由用户确定。算法首先将热点路
18、径集设为空，并设置所有轨 迹为未处理状态。随机选取一条轨迹 Traji ，计算其 与轨迹集合中其余所有轨迹的时空距离，得到轨迹 Traji 的 时空近邻集合 TrajSet ，然后计算 TrajSet 中任意 2 条轨迹的重叠子轨迹的累积长度，如果所 得长度大于设定的最小重叠子轨迹累积长度阈值 MinLns ，则将 TrajSet 中的轨迹聚类成一个簇 CTk 。 从尚未被聚类的轨迹集合中再随机选取一条，重复 以上处理。最后，对每个轨迹簇，计算每条轨迹中各 子轨迹的权值，如果该权值大于给定的阈值 ，将该 子轨迹段加入热点路径集合 HR。算法名: 基于轨迹聚类的热点路径检测输入: 轨迹集合 Tr
19、aj ，时空邻域阈值 ，最小 轨迹累积长度阈值 MinLns ，子轨迹权重阈值 输出: 轨迹簇集合 CT，热点路径集合 HR步骤:初始化 CT 及 HR 并置为空; 所有轨迹状态设置为 unclustered; For each Traji do If( Traji 状态为 unclustered) TrajSet = N ( Traji ) ;行权值分析并发现热点路径的时间复杂度为 O( m) 。因此，算法的时间复杂度为 O( n + m2 + m) 。4实验为了测试算法性能，设置实验环境为 Genuine In-tel( R) 1. 6 GHz 处理器，1 GByte 内存，80 GByt
20、e 硬盘，操作系统为 Windows XP professional。实验中采用的德国 Odenburg 地图和 100 条轨迹数据是利用 ThomasBrinkhoff 数据生成器9产生的，如图 2 所示。图 2Fig 2基于 Odenburg 地图产生的 100 条轨迹100 trajectories generated on Odenburg map与 文 献7进 行 对 比，采 用 同 样 的实验一DBSCAN 轨迹聚类方法，分析在轨迹划分阶段引入停留点语义特征对聚类结果的影响。设定最小重叠子轨迹累积长度阈值 MinLns 为3。仅将道路交叉点作为特征点进行划分后的轨迹 聚类结果如表
21、1 所示。将停留时间超过 10 ms 的位 置设定为停留点，将道路交叉点和停留点均作为特 征点进行轨迹划分并聚类，结果如表 2 所示。可见， 表 2 中列出 5 个聚类簇，而表 1 中只有 3 个。这是 由于在轨迹划分时引入停留点语义，增加了子轨迹 的个数，从而在符合实际语义的前提下找到了更多 的轨迹簇。通过对新增轨迹簇的分析，可以同时确 定被移动对象关注的停留点区域。表 1 不考虑停留点时的轨迹聚类结果Tab 1 Results of clustering without considering stops结论5热点路径分析有利于辅助决策分析，可应用于交通、物流等受路网约束的领域。本文综合考
22、虑轨 迹的时空特性和停留点语义，并通过轨迹划分、轨迹 聚类和子轨迹权值分析发现语义更完整、用户关注 度更高的热点路径。这种方法在移动对象的原始轨 迹数据基础上进行处理，保留了轨迹原有的时空和 语义特性，能更全面地反映移动用户的运动和行为 模式。参考文献:1桂智明，陈彩 基于语义的移动对象轨迹知识发现研究J 计算机工程，2008，35( 16) : 14-16.GUI Zhi-ming，CHEN Cai Study on Semantic Based Moving Objects Trajectory Knowledge Discovery J Computer Engineering，2008
23、，35( 16) : 14-16.LI Xiao-lei，HAN Jia-wei，LEE Jae-Gil，et al TrafficDensity-Based Discovery of Hot Routes in Road NetworksC/ / Proceedings of the 10th International Symposium on Spatial and Temporal Databases Boston，MA，USA: Springer，2007: 441-459.陈继东，孟小峰，赖彩凤 基于道路网络的对象聚类J 软件学报，2007，18( 2) : 332-344.CHE
24、N Ji-dong，MENG Xiao-feng，LAI Cai-feng Cluste- ring Objects in a Road NetworkJ Journal of Software，2007，18( 2) : 332-334.张延玲，刘金鹏，姜保庆 移动对象子轨迹段分割与 聚类算法J 计算机工程与应用，2009，45 ( 10 ) : 65-68.ZHANG Yan-ling，LIU Jin-peng，JIANG Bao-qing Par- tition and clustering for sub-trajectories of moving objectsJ Computer
25、 Engineering and Applications，2009，45( 10) : 65-68.KHARRAT A，POPA I S，ZEITOUNI Karine，et al Clustering Algorithm for Network Constraint TrajectoriesC/ / Proceedings of 13th International Symposium onSpatial Data Handling，Montpellier，France: Springer，2008: 631-647.WON Jung-im，KIM Sang-wook，BAEK Ji-ha
26、eng，et al Trajectory clustering in road network environmentC/ / Proceedings of the IEEE Symposium on Computational In- telligence and Data Mining Nashville，TN，USA: IEEE press 2009: 299-305.XIA Ying，WANG Guo-yin，ZHANG Xu，et al Re- search of Spatio-Temporal Similarity Measure on Network Constrained Tr
27、ajectory DataC/ / Proceedings of 5th In- ternational Conference on Rough Set and Knowledge Technology ( RSKT ) ，Beijing，China: Springer，2010:簇编号所包含的轨迹数 / 个123151492表 2考虑停留点时的聚类结果Tab 2 Results of clustering with considering stops簇编号所包含的轨迹数 / 个123451184333实验二 在轨迹聚类的基础上，设置子轨迹权重阀值为 0. 5，分析每个子轨迹在各轨迹簇的权重
28、并发现热点路径，如图 3 所示。结果表明，通过权重 分析，用户关注程度更高的路径被选择出来。456图 3 发现的热点路径Fig 3 Results of hot route7温海平( 1984-) ，男，湖北人，硕士研究生，491-4988 SPACCAPIETRA S，PARENT C，DAMIANI M L，et al VANGENOT C A conceptual view on trajectoriesJ Data and Knowledge Engineering，2008，65 ( 1 ) : 126-146.9 BRINKHOFF T A Framework for Genera
29、ting Network- Based Moving ObjectstsJ GeoInformatica，2002，6( 2) : 153-180主要研究方向为时空数据挖掘。E-mail:whp_898 163 com。作者简介:张 旭( 1981-) ，男，山东人，博士研究生，夏 英( 1972-) ，女，四川人，教授，主要研究方向为数据库与数据挖掘、地理信息系 统等。E-mail: xiaying cqupt edu cn。主要研究方向为数据库与数据挖掘。E-mail: zhangxu dblab inha ac kr。( 编辑: 刘 勇)( 上接第 584 页)LONG Zhao-hua
30、，CHENG hong，JIANG Gui-quan，et al An optimal macroblock level rate control algorithm based on H 264 / AVCJ Journal of Chongqing University of Posts and Telecommu-nications: Natural Science Edition，2009，21( 6) : 776-780.10 候靳勇 无线多媒体跨层协议传输系统研究与设计D 长沙: 国防科学技术大学，2008.HOU Jin-yong The Research and Impleme
31、ntation on Transmission System of Wireless Multimedia Cross-Layer Protocol D Changsha: National University of Deffense Technology，2008.11 李宾 无线局域网多速率和多 信 道 MAC 协 议 研 究D 厦门: 厦门大学，2008.LI Bin Research on multi-rate and multichannel MACprotocol in WLAN D Xiamen: Ximen University，2008.12 严德汗，曾致远，章珉 一种改进
32、的实时多媒体自适应 传输控制策略J 计算机工程与应用 2004，19: 147-150.YAN De-han，ZENG Zhi-yua，ZHANG Min A Modified Adaptive Transmitted Control Strategy for Real Time Mul- timediaJ Computer Engineering and Applications2004，19: 147-150作者简介:龙昭华( 1962-) ，男，贵州遵义人，教授，学士，CCF 高级会员，普适计算专员会、无 线传感器网络专委会委员，研究方向为 网络通信与嵌入式系统。E-mail: longzh cqupt edu cn。马 艳( 1985-) ，女，山东菏泽人，硕士研究生，研究方向为计算机网络与嵌入式 系统。E-mail: myyan_1119 126 com。张 林( 1972-) ，男，重庆人，讲师，硕士。研究方向为网络通信与嵌入式系统。E-mail:zhanglin cqupt edu cn。杨年鹏( 1986-) ，男，湖北人，硕士研究生，研究方向为嵌入式系 统。 E-mail: ynp130 163 com。( 编辑: 刘 勇)
