面向安防系统的高效用语义轨迹模式挖掘

doi:10.19678/j.issn.1000-3428.0064950

摘要/Abstract

摘要： 在安防系统中，将大量目标轨迹先转化为语义轨迹后再进行频繁模式挖掘，有助于分析目标行为模式、识别危险源及增强安防系统内部防控。针对现有频繁模式挖掘方法未考虑目标停留点的效用差异问题，提出一种高效用语义轨迹模式挖掘算法。综合停留点兴趣度、目标停留时间以及目标语义轨迹支持度这3个参数定义语义轨迹效用值，采用蚁群算法挖掘高效用语义轨迹模式。利用精英蚂蚁策略改进蚂蚁种群的迭代方式，通过轮盘赌选择法优化蚂蚁对于下一个节点的选择策略，运用无效用编码向量剪枝策略提高算法执行效率。在Chess、Mushroom、Foodmart、Retail等4个公开数据集以及某安防系统的RFID定位数据集上的实验结果表明，相比于HUIM-ACS算法，该算法挖掘的高效用语义轨迹模式数量增加了10%~15%，运行时间减少了7%~12%。

关键词: 安防系统, 语义轨迹, 高效用模式挖掘, 蚁群算法, 剪枝策略

Abstract: In security systems，transforming a large number of collected target trajectories into semantic trajectories and mining their frequency patterns are helpful in analyzing target behavior patterns，identifying hazard sources，and enhancing internal prevention and control of security systems. Existing frequent-pattern mining methods do not consider the utility difference in stay-point values.To address this issue，this study proposes a high-utility semantic trajectory pattern mining method.The concept of semantic trajectory utility value is defined by integrating three parameters：the interest of the stay point，stay time of the target at stay point，and the support of target semantic trajectory.To achieve this，an ant colony algorithm is used to mine high-utility semantic trajectory patterns.The algorithm involves the elite ant strategy to improve the iterative method of ant population and the strategy of the ant selecting the next node through the roulette selection method. Next，the invalid coding vector-pruning strategy is used to improve the execution efficiency of the algorithm. The proposed algorithm is tested on four public datasets，namely Chess，Mushroom，Foodmart，and Retail，as well as the Radio Frequency IDentification（RFID） location dataset of a certain security system.The experimental results show that the proposed algorithm increases the number of high-utility semantic trajectory patterns by 10%-15% and reduces the running time by 7%-12% compared with the Ant Colony Optimization（ACO）-based approach to mine high-utility itemsets（HUIM-ACS）.

Key words: security system, semantic trajectory, high-utility pattern mining, ant colony algorithm, pruning strategy

中图分类号:

TP311

付嘉豪, 杨嘉怡, 李爱国. 面向安防系统的高效用语义轨迹模式挖掘[J]. 计算机工程, 2023, 49(6): 62-70.

FU Jiahao, YANG Jiayi, LI Aiguo. High-Utility Semantic Trajectory Pattern Mining for Security System[J]. Computer Engineering, 2023, 49(6): 62-70.

https://www.ecice06.com/CN/Y2023/V49/I6/62

图/表 7

20230615164509

20230615164512

20230615164515

20230615164519

20230615164522

20230615164526

20230615164529

参考文献

[1] ZHU C,ZHAO S,XIA Y,et al.An improved three-point localization method based on RSS for transceiver separation RFID systems[J].Measurement,2022,187:110283.
[2] HAYWARD S J,EARPS J,SHARPE R,et al.A novel inertial positioning update method,using passive RFID tags,for indoor asset localisation[J].CIRP Journal of Manufacturing Science and Technology,2021,35:968-982.
[3] 陈博.基于物联网的实物保护系统关键技术研究[D].西安:西安科技大学,2021.CHEN B.Research on key technologies of physical protection system based on Internet of Things[D].Xi'an:Xi'an University of Science and Technology,2021.(in Chinese)
[4] ZHANG Z,ZHAO X G,ZHANG Y C,et al.Efficient mining of hotspot regional patterns with multi-semantic trajectories[J].Big Data Research,2020,22:100157.
[5] 吴瑕,唐祖锴,祝园园,等.近似到达时间约束下的语义轨迹频繁模式挖掘[J].软件学报,2018,29(10):3184-3204.WU X,TANG Z K,ZHU Y Y,et al.Frequent pattern mining with approximate arrival-time in semantic trajectories[J].Journal of Software,2018,29(10):3184-3204.(in Chinese)
[6] 张春砚,韩萌,孙蕊,等.高效用模式挖掘关键技术综述[J].计算机应用研究,2021,38(2):330-340.ZHANG C Y,HAN M,SUN R,et al.Survey of key technologies for high utility patterns mining[J].Application Research of Computers,2021,38(2):330-340.(in Chinese)
[7] AZIYA S V S,GEORGE J.An efficient high utility pattern mining for finding time based customer purchase behavior[C]//Proceedings of International Conference on Computer Networks and Inventive Communication Technologies.Berlin,Germany:Springer,2019:400-407.
[8] 李慧,刘贵全,瞿春燕.频繁和高效用项集挖掘[J].计算机科学,2015,42(5):82-87,123.LI H,LIU G Q,QU C Y.Mining frequent and high utility itemsets[J].Computer Science,2015,42(5):82-87,123.(in Chinese)
[9] LIU Y,LIAO W,CHOUDHARY A.A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining.Berlin,Germany:Springer,2005:689-695.
[10] LIU Y,LIAO W K,CHOUDHARY A.A fast high utility itemsets mining algorithm[C]//Proceedings of the 1st International Workshop on Utility-based Data Mining.New York,USA:ACM Press,2005:90-99.
[11] RYANG H,YUN U.Top-k high utility pattern mining with effective threshold raising strategies[J].Knowledge-Based Systems,2015,76:109-126.
[12] RYANG H,YUN U.High utility pattern mining over data streams with sliding window technique[J].Expert Systems with Applications,2016,57:214-231.
[13] KIM D,YUN U.Mining high utility itemsets based on the time decaying model[J].Intelligent Data Analysis,2016,20(5):1157-1180.
[14] KIM D,YUN U.Efficient algorithm for mining high average-utility itemsets in incremental transaction databases[J].Applied Intelligence,2017,47(1):114-131.
[15] DENG Z H.An efficient structure for fast mining high utility itemsets[J].Applied Intelligence,2018,48(9):3161-3177.
[16] DUONG Q H,LIAO B,FOURNIER-VIGER P,et al.An efficient algorithm for mining the top-k high utility itemsets,using novel threshold raising and pruning strategies[J].Knowledge-Based Systems,2016,104:106-122.
[17] DAM T L,LI K L,FOURNIER-VIGER P,et al.An efficient algorithm for mining top-k on-shelf high utility itemsets[J].Knowledge and Information Systems,2017,52(3):621-655.
[18] DAM T L,LI K L,FOURNIER-VIGER P,et al.CLS-Miner:efficient and effective closed high-utility itemset mining[J].Frontiers of Computer Science,2019,13(2):357-381.
[19] KANNIMUTHU S,PREMALATHA K.Discovery of high utility itemsets using genetic algorithm with ranked mutation[J].Applied Artificial Intelligence,2014,28(4):337-359.
[20] LIN J C W,YANG L,FOURNIER-VIGER P,et al.A binary PSO approach to mine high-utility itemsets[J].Soft Computing,2017,21(17):5103-5121.
[21] WU J M T,ZHAN J,LIN J C W.An ACO-based approach to mine high-utility itemsets[J].Knowledge-Based Systems,2017,116:102-113.
[22] BAIN M.Chess dataset[EB/OL].[2022-05-14].http://archive.ics.uci.edu/ml/datasets/Chess+%28King-Rook+vs.+King%29.
[23] SCHLIMMER J.Mushroom dataset[EB/OL].[2022-05-14].http://archive.ics.uci.edu/ml/datasets/Mushroom.
[24] VIGER P F.Foodmart[EB/OL].[2022-05-14].http://www.Philippe-fournier-viger.com/spmf/datasets/foodmart.txt.
[25] CHEN D.Online Retail dataset[EB/OL].[2022-05-14].http://archive.Ics.uci.edu/ml/datasets/Online+Retail.

选择文件类型/文献管理软件名称

选择包含的内容