經(jīng)典軌跡的魯棒相似度量算法
doi: 10.11999/JEIT190550 cstr: 32379.14.JEIT190550
-
中國(guó)電子科技集團(tuán)公司第十研究所 成都 610036
A Robust Trajectory Similarity Measure Method for Classical Trajectory
-
No.10 Research Institute of China Electronics Technology Group Corporation, Chengdu 610036, China
-
摘要:
針對(duì)經(jīng)典軌跡與實(shí)時(shí)軌跡之間的大差異性，該文利用最長(zhǎng)公共子序列理論，提出一種魯棒的軌跡相似度量方法。該方法首先利用點(diǎn)到線段之間的距離判斷經(jīng)典軌跡的點(diǎn)與實(shí)時(shí)軌跡的線段是否一致；然后利用改進(jìn)的多對(duì)1最長(zhǎng)公共子序列算法，計(jì)算經(jīng)典軌跡與實(shí)時(shí)軌跡之間的最長(zhǎng)公共子序列長(zhǎng)度；最后將最長(zhǎng)公共子序列長(zhǎng)度與經(jīng)典軌跡的點(diǎn)數(shù)的比值作為經(jīng)典軌跡與實(shí)時(shí)軌跡之間的相似度。實(shí)驗(yàn)說(shuō)明該算法的魯棒性，該算法能夠有效解決經(jīng)典軌跡與實(shí)時(shí)軌跡之間的大差異軌跡相似度量問(wèn)題。
-
關(guān)鍵詞:
- 軌跡相似度量 /
- 大差異軌跡 /
- 多對(duì)1最長(zhǎng)公共子序列 /
- 魯棒計(jì)算 /
- 經(jīng)典軌跡
Abstract:In view of the great difference between classical trajectory and real-time trajectory, a robust trajectory similarity measurement method is proposed based on the longest common subsequence theory. Firstly, the distance between point and line segment is used to judge whether the point of classical trajectory is consistent with the line segment of real-time trajectory. Secondly, the longest common subsequence length between classical trajectory and real-time trajectory is calculated by using the improved multi-to-one longest common subsequence algorithm. Finally, the ratio of the longest common subsequence length to the number of points of the classical trajectory is taken as the similarity between the classical trajectory and the real-time trajectory. Experiments show that the algorithm is robust and can effectively solve the problem of similarity measurement between the classical trajectories and real-time trajectories.
-
ANDRIENKO G, ANDRIENKO N, FUCHS G, et al. Clustering trajectories by relevant parts for air traffic analysis[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 34–44. doi: 10.1109/TVCG.2017.2744322 毛嘉莉, 金澈清, 章志剛, 等. 軌跡大數(shù)據(jù)異常檢測(cè): 研究進(jìn)展及系統(tǒng)框架[J]. 軟件學(xué)報(bào), 2017, 28(1): 17–34. doi: 10.13328/j.cnki.jos.005151MAO Jiali, JIN Cheqing, ZHANG Zhigang, et al. Anomaly detection for trajectory big data: Advancements and framework[J]. Journal of Software, 2017, 28(1): 17–34. doi: 10.13328/j.cnki.jos.005151 李保珠, 張林, 董云龍, 等. 基于航跡矢量分級(jí)聚類(lèi)的雷達(dá)與電子支援措施抗差關(guān)聯(lián)算法[J]. 電子與信息學(xué)報(bào), 2019, 41(6): 1310–1316. doi: 10.11999/JEIT180714LI Baozhu, ZHANG Lin, DONG Yunlong, et al. Anti-bias track association algorithm of radar and electronic support measurements based on track vectors hierarchical clustering[J]. Journal of Electronics &Information Technology, 2019, 41(6): 1310–1316. doi: 10.11999/JEIT180714 陳鴻昶, 徐乾, 黃瑞陽(yáng), 等. 一種基于用戶(hù)軌跡的跨社交網(wǎng)絡(luò)用戶(hù)身份識(shí)別算法[J]. 電子與信息學(xué)報(bào), 2018, 40(11): 2758–2764. doi: 10.11999/JEIT180130CHEN Hongchang, XU Qian, HUANG Ruiyang, et al. User identification across social networks based on user trajectory[J]. Journal of Electronics &Information Technology, 2018, 40(11): 2758–2764. doi: 10.11999/JEIT180130 AGRAWAL R, FALOUTSOS C, and SWAMI A. Efficient similarity search in sequence databases[C]. The 4th International Conference on Foundations of Data Organization and Algorithms, Chicago, USA, 1993: 69–84. KEOGH E and RATANAMAHATANA C A. Exact indexing of dynamic time warping[J]. Knowledge and Information Systems, 2005, 7(3): 358–386. doi: 10.1007/s10115-004-0154-9 GUO Ning, MA Mengyu, XIONG Wei, et al. An efficient query algorithm for trajectory similarity based on Fréchet distance threshold[J]. ISPRS International Journal of Geo-Information, 2017, 6(11): 326. doi: 10.3390/ijgi6110326 魏龍翔, 何小海, 滕奇志, 等. 結(jié)合Hausdorff距離和最長(zhǎng)公共子序列的軌跡分類(lèi)[J]. 電子與信息學(xué)報(bào), 2013, 35(4): 784–790. doi: 10.3724/SP.J.1146.2012.01078WEI Longxiang, HE Xiaohai, TENG Qizhi, et al. Trajectory classification based on Hausdorff distance and longest common subsequence[J]. Journal of Electronics &Information Technology, 2013, 35(4): 784–790. doi: 10.3724/SP.J.1146.2012.01078 朱進(jìn), 胡斌, 邵華. 基于多重運(yùn)動(dòng)特征的軌跡相似性度量模型[J]. 武漢大學(xué)學(xué)報(bào): 信息科學(xué)版, 2017, 42(12): 1703–1710. doi: 10.13203/j.whugis20150594ZHU Jin, HU Bin, and SHAO Hua. Trajectory similarity measure based on multiple movement features[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1703–1710. doi: 10.13203/j.whugis20150594 VLACHOS M, KOLLIOS G, and GUNOPULOS D. Discovering similar multidimensional trajectories[C]. The 18th International Conference on Data Engineering, San Jose, USA, 2002: 673–684. doi: 10.1109/ICDE.2002.994784. 劉宇, 王前東. 基于最長(zhǎng)公共子序列的非同步相似軌跡判斷[J]. 電訊技術(shù), 2017, 57(10): 1165–1170. doi: 10.3969/j.issn.1001-893x.2017.10.011LIU Yu and WANG Qiandong. Computing similar measure between two asynchronous trajectories based on longest common subsequence method[J]. Telecommunication Engineering, 2017, 57(10): 1165–1170. doi: 10.3969/j.issn.1001-893x.2017.10.011 WAGNER R A and FISCHER M J. The string-to-string correction problem[J]. Journal of the ACM, 1974, 21(1): 168–173. doi: 10.1145/321796.321811 CHOONG M Y, ANGELINE L, CHIN R K Y, et al. Modeling of vehicle trajectory clustering based on LCSS for traffic pattern extraction[C]. The 2nd IEEE International Conference on Automatic Control and Intelligent Systems, Kota Kinabalu, Malaysia, 2017: 74–79. doi: 10.1109/I2CACIS.2017.8239036. 王前東. 一種帶匹配路徑約束的最長(zhǎng)公共子序列長(zhǎng)度算法[J]. 電子與信息學(xué)報(bào), 2017, 39(11): 2615–2619. doi: 10.11999/JEIT170092WANG Qiandong. A matching path constrained longest common subsequence length algorithm[J]. Journal of Electronics &Information Technology, 2017, 39(11): 2615–2619. doi: 10.11999/JEIT170092 WANG Haoxin, ZHONG Jingdong, and ZHANG Defu. A duplicate code checking algorithm for the programming experiment[C]. The 2nd International Conference on Mathematics and Computers in Sciences and in Industry, Sliema, Malta, 2015: 39–42. doi: 10.1109/MCSI.2015.12. YUAN Guan, SUN Penghui, ZHAO Jie, et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review, 2017, 47(1): 123–144. doi: 10.1007/s10462-016-9477-7 -
下載:
計(jì)量
- 文章訪問(wèn)數(shù): 2360
- HTML全文瀏覽量: 1658
- PDF下載量: 83
- 被引次數(shù): 0
下載:
