Taxi Trajectory Characteristics Analysis Based on Frequent Sequence Mining

doi:10.12141/j.issn.1000-565X.230375

Abstract

Abstract:

In order to further clarify the differences in routing behaviors of different taxis, this paper adopted the method of frequent sequence mining to extract the frequent path between the same OD pairs, construct path sets, and analyze the similar characteristics of path sets from static and dynamic perspectives. By taking the trajectory data of taxis in Xi’an City as the research object, the path set between OD pairs is obtained through grid division and road network matching. Then, the frequent path is redefined, the PrefixSpan evolution algorithm is adopted, and the dynamic threshold and frequency index based on the obtained frequent subsequences are introduced to mine frequent paths. Furthermore, in order to complete the construction of three kinds of effective path sets, the shortest path and other paths are extracted, and the general properties of the constructed path sets are analyzed. Finally, the similarity between two-dimension time series (tracks) on the path is represented as dynamic similarity, and the similarity between one-dimension directed sequences (sections) is represented as static similarity, and the similarity analysis of three types of paths is carried out based on the improved longest common subsequence and dynamic time regularity algorithm. The results show that: (1) the similarity between the frequent path and the shortest path is rather high, meaning that most taxis still choose the road with the lowest travel time but not the shortest path; (2) time and distance are still the main considerations for travelers when choosing a path, but travelers do not completely pursue the shortest time or distance; (3) the calculated dynamic similarity is significantly higher than the static similarity, which means that the two-dimension sequential similarity on the path is higher than the one-dimension shape similarity; and (4) the two proposed methods both possess the highest similarity between the frequent path and the shortest path and the lowest similarity between the shortest path and other paths The consistency of the comparison results indicates that the similarity of the static path can be roughly measured by the that of the dynamic trajectory. The proposed frequent path mining algorithm is of certain reliability. It can provide supports for urban traffic managers with recommend routes and planed roads.

Key words: traffic and transportation engineering, trajectory data, frequent sequence mining, path choice set, similarity characteristic analysis

CLC Number:

U491

LONG Xueqin, WANG Han, WANG Ruixuan. Taxi Trajectory Characteristics Analysis Based on Frequent Sequence Mining[J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(6): 24-33.

Figures/Tables 18

Table 1

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 2

Table 3

Table 4

Table 5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Table 6

Fig.11

Table 7

References 16

1	CHEN G， CHEN B， YU Y ．Mining frequent trajectory patterns from GPS tracks［C］∥Proceedings of 2010 International Conference on the Computational Intelligence and Software Engineering．Wuhan：IEEE，2010：1-6．
2	LYU J， SUN Q， LI Q，et al ．Multi-scale and multi-scope convolutional neural networks for destination prediction of trajectories［J］．IEEE Transactions on Intelligent Transportation Systems，2020，21（8）：3184-3195．
3	BIN C， GU T， SUN Y，et al ．A personalized POI route recommendation system based on heterogeneous tourism data and sequential pattern mining［J］．Multimedia Tools and Applications，2019，78：35135-35156．
4	QIAN S， CHENG B， CAO J，et al ．Detecting taxi trajectory anomaly based on spatio-temporal relations［J］．IEEE Transactions on Intelligent Transportation Systems，2021，23（7）：11-12．
5	ZHENG L J， XIA D， ZHAO X，et al ．Spatial-temporal travel pattern mining using massive taxi trajectory data［J］．Physica A：Statistical Mechanics and Iits Applications，2018，501：24-41．
6	杨振娟．基于出租车GPS轨迹的热点路後挖掘和载客路径推荐［D］．兰州：西北师范大学，2020．
7	吴俊伟，朱云龙，库涛，等．基于网格聚类的热点路径探测［J］．吉林大学学报（工学版），2015，45（1）：274-282．
	WU Jun-wei， ZHU Yun-long， KU Tao，et al ．Hot routes detection algorithm based on grid clustering［J］．Journal of Jilin University （Engineering and Technology Edition），2015，45（1）：274-282．
8	段宗涛，任国亮，康军，等．基于频繁轨迹序列模式挖掘的路径推荐方法［J］．太原理工大学学报，2022，53（2）：240-247．
	DUAN Zong-tao， REN Guo-liang， KANG Jun，et al ．Route recommendation method based on frequent trajectory sequence pattern mining［J］．Journal of Taiyuan University of Technology，2022，53（2）：240-247
9	袁淑君．基于频繁序列挖掘与双层Logit模型的出租车寻客行为建模方法［D］．武汉：武汉大学，2019．
10	孙文平，常亮，宾辰忠，等．基于知识图谱和频繁序列挖掘的旅游路线推荐［J］．计算机科学，2019，46（2）：56-61．
	SUN Wen-ping， CHANG Liang， Chen-zhong BIN，et al ．Travel route recommendation based on knowledge graph and frequent sequence mining［J］．Computer Science，2019，46（2）：56-61．
11	胡冰冰，芦俊丽，郑承宇，等．改进的 PrefixSpan 算法在旅游热门路线上的应用［J］．云南民族大学学报（自然科学版），2022，31（1）：94-102．
	HU Bing-bing， LU Jun-li， ZHENG Cheng-yu，et al ．Application of improved PrefixSpan agorithm on popular travel routes［J］．Journal of Yunnan Nationalities University （Natural Sciences Edition），2022，31（1）：94-102．
12	林鹏飞，翁剑成，胡松，等．公共交通乘客个体活动链的日相似性研究［J］．交通运输系统工程与信息，2020，20（6）：178-183．
	LIN Peng-fei， WENG Jian-cheng， HU Song，et al ．Day-to-day similarity of individual activity chain of public transport passengers［J］．Journal of Transportation Systems Engineering and Information Technology，2020，20（6）：178-183．
13	吴刚，邱煜晶，王国仁．基于隐马尔可夫模型和遗传算法的地图匹配算法［J］．东北大学学报（自然科学版），2017，38（4）：472-475．
	WU Gang， QIU Yu-jing， WANG Guo-ren ．Map matching algorithm based on hidden Markov model and genetic algorithm［J］．Journal of Northeastern University （Natural Science），2017，38（4）：472-475．
14	SRIKANT R， AGRAWAL R ．Mining sequential patterns：generalization sandper form anceim provements［C］∥Proceedings of the 5th International Conferenceon Extending Database Technology：Advances in Database Technology．Avignon：［s. n.］，1996：3-17．
15	VLACHOS M， KOLLIOS G， GUNOPULOS D ．Discovering similar multidimensional trajectories［C］∥Proceedings of the 18th International Conference on Data Engineering．Washington DC：IEEE Computer Society，2002：673-684．
16	SANKOFF D， KRUSKAL J ．Time warps，string edits，and macromolecules：the theory and practice of sequence comparison［M］．Boston：Addison-Wesley，1983．

序号	字段	格式示例
1	车牌号	陕AD93000
2	时刻	Mon Nov 04 07：15：14 CST 2019
3	空重	0
4	纬度	34.161 466 67
5	经度	108.863 916 7
6	速度	0
7	角度	0

路径	路径序列	路段数
P₁	<<1，d><d，i><i，n><n，r><r，u><u，x><x，k><k，5>>	8
P₂	<<4，g><g，d><d，i><i，n><n，r><r，s><s，v><v，y><y，b><b，6>>	10
P₃	<<2，g><g，h><h，j><j，l><l，m><m，p><p，t><t，z><z，y><y，b><b，6>>	11
P₄	<<3，f><f，m><m，p><p，t><t，z><z，y><y，b><b，6>>	8
P₅	<<3，f><f，m><m，p><p，t><t，z><z，y><y，b><b，6>>	8
P₆	<<3，f><f，m><m，p><p，t><t，z><z，y><y，b><b，c><c，o><o，4>>	10

子序列	投影数据库	路段支持度	路径支持度	路径频繁度
<1，d>	<<d，i><i，n><n，r><r，u><u，x><x，k><k，5>>	1	10	10/8
<d，i>	<<i，n><n，r><r，u><u，x><x，k><k，5>>	2
<d，i>	<<i，n><n，r><r，s><s，v><v，y><y，b><b，6>>	2
<i，n>	<<n，r><r，u><u，x><x，k><k，5>>	2
<i，n>	<<n，r><r，s><s，v><v，y><y，b><b，6>>	2
<n，r>	<<r，u><u，x><x，k><k，5>>	2
<n，r>	<<r，s><s，v><v，y><y，b><b，6>>	2
<r，u>	<<u，x><x，k><k，5>>	1
<u，x>	<<x，k><k，5>>	1
<x，k>	<<k，5>>	1
<k，5>	< >	0

前缀	投影数据库	子序列项集支持度
<y，b>	<<b，6>>	4
<y，b>	<<b，c> <c，o> <o，4>>	1，1，1

前缀	投影数据库	子序列项集支持度
<y，b><b，6>	< >	0
<y，b>	<<b，c><c，o><o，4>>	1，1，1
<m，p><p，t><t，z><z，y><y，b><b，6>	< >	0
<m，p><p，t><t，z><z，y><y，b>	<<b，c><c，o><o，4>>	1，1，1
<p，t><t，z><z，y><y，b><b，6>	< >	0
<p，t><t，z><z，y><y，b>	<<b，c><c，o><o，4>>	1，1，1
<t，z><z，y><y，b><b，6>	< >	0
<t，z><z，y><y，b>	<<b，c><c，o><o，4>>	1，1，1
<z，y><y，b><b，6>	< >	0
<z，y><y，b>	<<b，c><c，o><o，4>>	1，1，1