A Detection Algorithm for Discovering Accompanying Relationship of Cruise Passengers Based on UWB Positioning
-
摘要: 准确发现邮轮内部空间乘客之间的伴随关系, 在室内环境安装UWB定位设备开展室内人员定位实验。根据UWB定位的位置数据特点, 提出结合室内位置语义的Hausdorff-DBSCAN算法以聚类邮轮乘员轨迹, 并利用LSTM神经网络对疑似伴随关系对象进行相似度变化趋势的预测。传统的Hausdorff算法在计算轨迹相似度时未考虑轨迹时序一致的问题, 引入位置语义序列能够较好地解决这个问题。改进后的Hausdorff-DBSCAN算法的输入为乘员轨迹数据集, 根据轨迹整体相似度阈值选定聚类半径, 输出具有伴随关系的乘员轨迹聚类结果; LSTM神经网络以定长时间窗口的点邻近度序列为输入, 预测后1个时刻点邻近度值, 结合轨迹相似度阈值和预测结果分析乘员伴随关系的时序变化。利用Anylogic建模单层邮轮室内环境进行乘员仿真得到的轨迹数据验证算法的有效性。改进的Hausdorff-DBSCAN算法的准确率为0.920, 召回率为0.950, F1值为0.934, 准确率高出对比算法至少5.7%, 召回率高出对比算法至少8.0%, F1值高出对比算法至少6.7%。同时LSTM在预测邮轮乘员之间相似度变化时, 收敛后的误差值能保持在3%~4%左右, 预测结果具有较高的准确性。Abstract: UWB positioning is used in the cruise to carry out an on-board personnel location experiment to discover the accompanying relationship among passengers in the interior space of a cruise. A improved scheme based on Haussdorff-DBSCAN is proposed combined with indoor positional semantics to study the clustering of the passenger trajectories, based on the characteristics of the UWB location data. Afterward, the LSTM neural network is applied to predict the changing similarity of the suspected companions. The traditional Hausdorff algorithm does not consider the consistency of trajectory timing while calculating the trajectory similarity, and the introduction of positional semantic sequence can solve this problem. In the first phase, the passenger trajectory data set is input to the improved Hausdorff-DBSCAN algorithm, and the clustering radius is determined according to the overall similarity threshold of trajectories. The outputs are the emerging clusters of passenger trajectories in the same companion group. In the second phase, the LSTM neural network takes the point similarity sequence with a fixed time window as the input to predict the point similarity value at the next time. The sequential change of passengers accompanying relationship is analyzed by the similarity threshold and predicted results. The validity of the presented algorithm is demonstrated by the trajectory data obtained from the simulation study, which is modeled in Anylogic. The results indicate that the precision of the proposed algorithm, the recall value, and the F1 value are 0.92, 0.95, and 0.934, which are at least 5.7%, 8.0%, and 6.7% higher than the compared algorithm, respectively. The LSTM neural network also shows a promising effect in predicting the changing trend of the similarity because the loss is at a stable level from 3% to 4%.
-
图 2 基于改进Hausdorff-DBSCAN的算法流程
Figure 2. Work flow of improved Hausdorff-DBSCAN Algorithm
图 9 非伴随乘员轨迹训练误差值变化
Figure 9. Training loss variation of the non-accompanying trajectories
图 10 LSTM模型输出与真值对比
Figure 10. Comparison of the output and the true value of LSTM model
图 12 伴随乘员轨迹训练误差值值变化
Figure 12. Training loss variation of the accompanying trajectories
图 13 LSTM模型输出与真值对比
Figure 13. Comparison of the output and the true value of LSTM model
表 1 t1时刻各乘员位置记录
Table 1. Position records of each passenger at time t1
编号 横向距离 纵向距离 区域 1 x1 y1 R1t1 2 x2 y2 R2t1 ⋮ ⋮ ⋮ ⋮ z xz yz Rzt1 
下载: 导出CSV
表 2 行人轨迹数据样本
Table 2. Samples of pedestrian trajectory data
编号 时间点 横向距离 纵向距离 区域 1 12 652.51 69.59 R1t12 5 30 640.82 49.74 R5t30 10 70 562.57 120.60 R10t70 28 80 554.84 125.36 R28t80
下载: 导出CSV
表 3 轨迹间归一化相似度
Table 3. Normalized similarity between trajectories
编号 0 1 2 ⋯ 197 198 199 0 1 ⋯ 0.28 0.37 0.23 1 0.38 1 ⋯ 0.81 0.89 0.77 2 0.78 1 ⋯ 0.15 0.16 0.01 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 198 0.37 0.89 0.16 ⋯ 1 199 0.23 0.77 0.01 ⋯ 1
下载: 导出CSV
表 4 部分聚类簇及其簇间元素
Table 4. Partial clusters and the elements among them
簇编号 簇中乘员ID 0 (0, 6, 53, 67, 94, 96, 119, 136, 141, 150) 4 (4, 13, 27, 42, 77, 84, 90, 92, 124, 143, 149, 166, 172, 173, 178) 6 (7, 11, 14, 39, 45, 46, 48, 75, 83, 106, 144, 147, 153, 171, 182, 186, 191, 196) 7 (8, 9, 12, 17, 29, 32, 35, 36, 49, 51, 54, 58, 62, 74, 99, 100, 103, 113, 122, 133, 142, 148, 152, 185) 9 (16, 30, 43, 81, 95, 104, 107, 115, 157)
下载: 导出CSV
表 5 不同聚类算法性能对比
Table 5. Performance comparison of different clustering algorithms
方法 precision recall F1 Grid-based 0.850 0.780 0.813 DTW-DBSCAN 0.820 0.750 0.794 improved-ANGES 0.870 0.880 0.875 Hausdorff-DBSCAN 0.920 0.950 0.934
下载: 导出CSV
-
[1] HE Suining, CHAN S H G. Wi-Fi fingerprint-based indoor positioning: Recent advances and comparisons[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 466-490. http://www.cs.ust.hk/faculty/gchan/papers/COMST16_IP.pdf [2] DARDARI D, CLOSAS P, DJURIC P M. Indoor tracking: Theory, methods, and technologies[J]. IEEE Transactions on Vehicular Technology, 2015, 64(4): 1263-1278. doi: 10.1109/TVT.2015.2403868 [3] 仇功达, 何杰, 杨明, 等. 异常轨迹数据预警与预测关键技术综述[J]. 系统仿真学报, 2017, 29(11): 2608-2617. https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201711002.htmQIU Gongda, HE Jie, YANG Ming. Key technologies of precaution and prediction of abnormal spatial-temporal trajectory: A review of recent advances[J]. Journal of System Simulation, 2017, 29(11): 2608-2617. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ201711002.htm [4] 许佳捷, 郑凯, 池明旻, 等. 轨迹大数据: 数据、应用与技术现状[J]. 通信学报, 2015, 36(12): 97-105. doi: 10.11959/j.issn.1000-436x.2015318XU Jiajie, ZHENG Kai, CHI Mingmin, et al. Trajectory big data: Data, applications and techniques[J]. Journal on Communications, 2015, 36(12): 97-105. (in Chinese) doi: 10.11959/j.issn.1000-436x.2015318 [5] 李颖, 赵莉, 赵祥模, 等. 基于大货车GPS数据的轨迹相似性度量有效性研究[J]. 中国公路学报, 2020, 33(2): 146-157. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL202002014.htmLI Ying, ZHAO Li, ZHAO Xiangmo, et al. Effectiveness of trajectory similarity measures based on truck GPS data[J]. China Journal of Highway and Transport, 2020, 33(2): 146-157. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL202002014.htm [6] 牟乃夏, 徐玉静, 张恒才, 等. 移动轨迹聚类方法研究综述[J]. 测绘通报, 2018(1): 1-7. https://www.cnki.com.cn/Article/CJFDTOTAL-CHTB201801001.htmMOU Naixia, XU Yujing, ZHANG Hengcai, et al. A review of the mobile trajectory clustering methods[J]. Bulletin of Surveying and Mapping, 2018(1): 1-7. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CHTB201801001.htm [7] JEUNG Hoyoung, YIU Manlung, SHEN Hengtao, et al. Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1(1): 1068-1080. doi: 10.14778/1453856.1453971 [8] 冯慧芳, 杨振娟. 基于时空相似度聚类的热点载客路径挖掘[J]. 交通运输系统工程与信息, 2019, 19(5): 94-100. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201905013.htmFENG Huifang, YANG Zhenjuan. Hot passenger routes mining based on spatial-temporal similarity clustering[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(5): 94-100. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201905013.htm [9] 唐炉亮, 于智伟, 任畅, 等. 基于车载GPS轨迹的立体交叉口空间结构信息获取方法[J]. 交通运输工程学报, 2019, 19(5): 170-179. doi: 10.3969/j.issn.1671-1637.2019.05.018TANG Luliang, YU Zhiwei, REN Chang, et al. Information acquisition method of three-dimensional intersection spatial structure based on vehicle GPS trajectory[J]. Journal of Traffic and Transportation Engineering, 2019, 19(5): 170-179. (in Chinese) doi: 10.3969/j.issn.1671-1637.2019.05.018 [10] 周洋, 杨超. 基于时空聚类算法的轨迹停驻点识别研究[J]. 交通运输系统工程与信息, 2018, 18(4): 88-95. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201804014.htmZHOU Yang, YANG Chao. Anchors identification in trajectory based on temporospatial clustering algorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 88-95. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201804014.htm [11] ORAKZAI F, PEDERSEN T B, CALDERS T. Distributed mining of convoys in large scale datasets[J]. GeoInformatica, 2021(1): 1-44. doi: 10.1007/s10707-020-00431-w [12] 周于涛, 吴华意, 成洪权, 等. 结合自注意力机制和结伴行为特征的行人轨迹预测模型[J]. 武汉大学学报(信息科学版), 2020, 45(12): 1989-1996. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH202012018.htmZHOU Yutao, WU Huayi, CHENG Hongquan, et al. Pedestrian trajectory prediction model combining self attention mechanism and companion behavior characteristics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(12): 1989-1996. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH202012018.htm [13] 连静, 王欣然, 李琳辉, 等. 基于人-车交互的行人轨迹预测[J]. 中国公路学报, 2021, 34(5): 215-223. doi: 10.3969/j.issn.1001-7372.2021.05.020LIAN Jing, WANG Xinran, LI Linhui, et al. Pedestrian trajectory prediction based on human-vehicle interaction[J]. China Journal of Highway and Transport, 2021, 34(5): 215-223. (in Chinese) doi: 10.3969/j.issn.1001-7372.2021.05.020 [14] 赛斌, 曹自强, 谭跃进, 等. 基于目标跟踪与轨迹聚类的行人移动数据挖掘方法研究[J]. 系统工程理论与实践, 2021, 41(1): 231-239. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL202101018.htmSAI Bin, CAO Ziqiang, TAN Yuejin, et al. Pedestrian data mining with object tracking and trajectory clustering[J]. Systerms Engineering Theory & Practice, 2021, 41(1): 215-223. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL202101018.htm [15] 夏英, 杨雪, 张旭. 基于RFID位置语义的室内移动轨迹聚类算法[J]. 重庆邮电大学学报(自然科学版), 2018, 30(3): 383-389. https://www.cnki.com.cn/Article/CJFDTOTAL-CASH201803013.htmXIA Ying, YANG Xue, ZHANG Xu. Clustering algorithm for indoor moving trajectory based on RFID location semantics[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2018, 30(3): 383-389. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-CASH201803013.htm [16] HUANG Weiqing, CHANG Ding, WANG Siye, et al. An Efficient clustering mining algorithm for indoor moving target trajectory based on the improved AGNES[C]. The 2015IEEE Trustcom. Washington, D. C. : IEEE, 2015. [17] 陈建伟, 李建波. 基于编码器-解码器模型的人群移动预测分析[J]. 计算机应用与软件, 2021, 38(6): 77-83+125. doi: 10.3969/j.issn.1000-386x.2021.06.013CHEN Jianwei, LI Jianbo. Human mobility predictive analysis based on encoder-decoder model[J]. Computer Applications and Software, 2021, 38(6): 77-83+125. (in Chinese) doi: 10.3969/j.issn.1000-386x.2021.06.013 [18] 张宇, 吴升, 赵志远, 等. 顾及相似用户特征的个人位置预测算法[J/OL]. (2021-03-26)[2021-12-06]. https://navi.cnki.net/knavi/journals/WHCH/detail?uniplatform=NZKPT.ZHANG Yu, WU Sheng, ZHAO Zhiyuan, et al. Personal location prediction algorithm considering similar user characteristics[J/OL]. (2021-03-26)[2021-12-06]. https://navi.cnki.net/knavi/journals/WHCH/detail?uniplatform=NZKPT. (inChinese) [19] 蒋通, 崔良中, 周钢, 等. 多步骤船舶轨迹聚类方法研究与实现[J]. 舰船电子工程, 2021, 41(9): 53-57+92. doi: 10.3969/j.issn.1672-9730.2021.09.012JIANG Tong, CUI Liangzhong, ZHOU Gang, et al. Research and implementation of multi-step ship track clustering method[J]. Ship Electronic Engineering, 2021, 41(9): 53-57+92. (in Chinese) doi: 10.3969/j.issn.1672-9730.2021.09.012 [20] EDLA D R, JANA P K. A grid clustering algorithmusing cluster boundaries[J]. Information and Communication Technologies, 2013, 15(3): 254-259. http://ieeexplore.ieee.org/document/6409084/ -
点击查看大图
图(14) / 表(5)
计量
- 文章访问数: 1031
- HTML全文浏览量: 645
- PDF下载量: 46
- 被引次数: 0