基于标签传播的轨迹兴趣点挖掘及隐私保护

doi:10.3969/j.issn.1006-2475.2024.05.009

摘要/Abstract

摘要： 摘要：随着全球定位系统和移动数据采集设备的普及，产生了大量的轨迹数据，挖掘轨迹数据中潜在信息具有重要的现实意义，但在挖掘过程中存在着隐私信息泄露的危险。因此，本文提出一种基于标签传播的轨迹兴趣点挖掘及数据隐私保护机制，该机制将原始轨迹数据集进行预处理之后，进行基于密度的初次聚类，再运用改进的标签传播算法进行再次聚类，此算法在挖掘过程融入轨迹数据的多维度信息，提高了数据的利用率和兴趣点的精确度。同时，该机制融入一种基于改进的指数机制的差分隐私保护算法，此算法可以有效地保护用户的隐私信息不被泄露。对比实验结果表明，本文提出的方法与现有方法相比，具有更好的性能优势，同时有效地解决了用户隐私信息泄露的问题。

关键词: 关键词：数据挖掘, 兴趣点, 轨迹聚类, 差分隐私

Abstract: Abstract： With the popularization of global positioning systems and mobile data collection devices， a large amount of trajectory data has been generated. Mining potential information in trajectory data has important practical significance， but there is a risk of privacy information leakage during the mining process. Therefore， we propose a trajectory interest point mining and data privacy protection mechanism based on label propagation. This mechanism preprocesses the original trajectory dataset， performs density based initial clustering， and then uses an improved label propagation algorithm for clustering. This algorithm incorporates multi-dimensional information of trajectory data in the mining process， improving data utilization and accuracy of interest points. At the same time， a differential privacy protection algorithm based on an improved exponential mechanism is proposed， which can effectively protect users’ privacy information from being leaked. The comparative experimental results show that the proposed method has better performance advantages compared to existing methods， and effectively solves the problem of user privacy information leakage.

Key words: Key words： data mining, points of interest, trajectory clustering, differential privacy

中图分类号:

TP393

袁红伟1, 常利军1, 郝家欢2, 樊娜2, 王超2, 罗闯2, 张泽辉2. 基于标签传播的轨迹兴趣点挖掘及隐私保护[J]. 计算机与现代化, 2024, 0(05): 46-54.

YUAN Hongwei1, CHANG Lijun1, HAO Jianhuan2, FAN Na2, WANG Chao2, LUO Chuang2, ZHANG Zehui2. Trajectory Interest Points Mining Based on Label Propagation and Privacy Protection[J]. Computer and Modernization, 2024, 0(05): 46-54.

参考文献

［1］ XIA C， HUA J Y， TONG W， et al. Distributed K-means clustering guaranteeing local differential privacy［J］. Computers & Security， 2020， 90（3）：101699.1-101699.11.
［2］严斯柔. 基于GPS数据的轨迹聚类算法研究［D］. 杭州：杭州电子科技大学， 2021.
［3］黄涛. 基于特征安全的位置数据隐私保护方法研究［D］. 武汉：华中科技大学， 2019.
［4］ TANG J， LIU L F， WU J G， et al. Trajectory clustering method based on spatial-temporal properties for mobile social networks［J］. Journal of Intelligent Information Systems， 2021，56：73-95.
［5］ WU H R， YEH M Y， CHEN M S. Profiling moving objects by dividing and clustering trajectories spatiotemporally［J］. IEEE Transactions on Knowledge and Data Engineering， 2012，25（11）：2615-2628.
［6］ KOH Z， ZHOU Y， LAU B P L， et al. Clustering and analysis of GPS trajectory data using distance-based features［J］. IEEE Access， 2022，10：125387-125399.
［7］ QIAO D F， YANG X Y， LIANG Y， et al. Rapid trajectory clustering based on neighbor spatial analysis［J］. Pattern Recognition Letters， 2022，156：167-173.
［8］ BELCASTRO L， KECHADI M T， MAROZZO F， et al. Parallel extraction of regions-of-interest from social media data［J］. Concurrency and Computation： Practice and Experience， 2021，33（8）： e5638.
［9］ LIU J Y， XUE C J， DONG Q， et al. A process-oriented spatiotemporal clustering method for complex trajectories of dynamic geographic phenomena［J］. IEEE Access， 2019，7：155951-155964.
［10］ QIN H C， LI R H， WANG G R， et al. Mining stable communities in temporal networks by density-based clustering［J］. IEEE Transactions on Big Data， 2020，8（3）：671-684.
［11］ AO M S， ZENG X Q， CHEN C H， et al. Identification of the survey points from network RTK trajectory with improved DBSCAN clustering， case study on HNCORS［J］. Earth Science Informatics， 2023，16（2）：1835-1847.
［12］ LI F， SHI W Z， ZHANG H. A two-phase clustering approach for urban hotspot detection with spatiotemporal and network constraints［J］. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing， 2021，14：3695-3705.
［13］ ZHANG H， ZHANG L L， CHE F， et al. Revealing urban traffic demand by constructing dynamic networks with taxi trajectory data［J］. IEEE Access， 2020，8：147673-147681.
［14］ DU M， WU F. Grid-based clustering using boundary detection［J］. Entropy， 2022， 24（11）：1606.
［15］ KASHANI E S， BAGHERI SHOURAKI S， NOROUZI Y， et al. A density-grid-based method for clustering k-dimensional data［J］. Applied Intelligence， 2022，53：10559-10573.
［16］ LANGARI R K， SARDAR S， MOUSAVI S A A， et al. Combined fuzzy clustering and firefly algorithm for privacy preserving in social networks［J］. Expert Systems with Applications， 2020，141：112968.1-112968.15.
［17］ AL-KHARJI S， TIAN Y， AL-RODHAAN M. A novel （K， X）-isomorphism method for protecting privacy in weighted social network［C］// 2018 21st Saudi Computer Society National Computer Conference （NCC）. IEEE， 2018：1-6.
［18］ TIAN H， LU Y， LIU J T， et al. Betweenness centrality based k-anonymity for privacy preserving in social networks［C］// Proceedings of the 16th International Conference on Advances in Mobile Computing and Multimedia（MoMM’2018）. ACM， 2018：3-7.
［19］ WANG H. Trajectory privacy protection mechanism based on social attributes［J］. arXiv preprint arXiv：2212.06600， 2022.
［20］ XIA C， HUA J Y， TONG W， et al. Distributed K-means clustering guaranteeing local differential privacy［J］. Computers & Security， 2020，90：101699. DOI：10.1016/j.cose.2019.101699.
［21］ LIN G B， ZHAO H J， ZHAO L Y， et al. Differential privacy information publishing algorithm based on cluster anonymity［C］// 2020 International Conference on Big Data， Artificial Intelligence and Internet of Things Engineering （ICBAIE）. IEEE， 2020. DOI： 10.1109/ICBAIE49996.2020.00054.
［22］ LU Z G， SHEN H. Differentially private k-means clustering with guaranteed convergence［J］. arXiv preprint arXiv：2002.01043， 2020.
［23］ QIAN K， LI X H. LBS user location privacy protection scheme based on trajectory similarity［J］. Scientific Reports， 2022， 12：13982.
［24］李宏霞. 基于标签传播的社区检测算法研究［D］. 兰州：兰州大学， 2021.
［25］焦荟聪，刘文菊，王赜. 基于指数机制的轨迹差分隐私保护方法［J］. 大数据， 2023，9（1）：141-152.
［26］ ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［C］// Proceedings of the Second International Conference on Knowledge Discovery and Data Mining（KDD’96）. ACM， 1996：226-231.
［27］ DASGUPTA S， FROST N， MOSHKOVITZ M， et al. Explainable k-means and k-medians clustering［C］// Proceedings of the 37th International Conference on Machine Learning（ICML）. PMLR， 2020：7012-7022.
［28］ XU G Q， GUO J W， YANG P L. TNS-LPA： An improved label propagation algorithm for community detection based on two-level neighbourhood similarity［J］. IEEE Access， 2020，9：23526-23536.
［29］ HAN Q H， YOSHIKAWA A， YAMAMURA M. Mining user similarity from GPS trajectory based on spatial-temporal and semantic information［C］// 2022 3rd International Conference on Information Science， Parallel and Distributed Systems （ISPDS）. IEEE， 2022：174-180.
［30］ WANG S， NEPAL S， SINNOTT R， et al. P-STM： Privacy-protected social tie mining of individual trajectories［C］// 2019 IEEE International Conference on Web Services（ICWS）. IEEE，2019. DOI： 10.1109/ICWS.2019.00014.
［31］任晓宇. 基于差分隐私的位置隐私保护技术研究［D］. 太原：山西师范大学， 2021.

[1]	曾钟静昕, 甘刚. 基于卷积自编码器的侧信道分析[J]. 计算机与现代化, 2024, 0(03): 110-114.
[2]	冯申, 於跃成, 张宗海. 结合动态多类信息的兴趣点推荐[J]. 计算机与现代化, 2022, 0(08): 57-64.
[3]	贾冲，冯慧芳，杨振娟. 基于出租车GPS轨迹和POI数据的商业选址推荐[J]. 计算机与现代化, 2020, 0(02): 21-.
[4]	陈晓利，祁云嵩，林嘉炜. 基于船舶融合点迹行为识别的雷达监视系统[J]. 计算机与现代化, 2018, 0(05): 25-.
[5]	吕温，徐贵力，程月华，李开宇，王彪. 基于局部时空特征的人体行为软分类识别[J]. 计算机与现代化, 2014, 0(3): 94-98,103.
[6]	胥皇，於志文，封云，周兴社. 基于LBSN的个性化旅游包推荐系统[J]. 计算机与现代化, 2014, 0(1): 186-191.
[7]	施惟;. 基于话题模型的视频动作识别系统研究[J]. 计算机与现代化, 2013, 1(4): 1-4.
[8]	陆萍;赵建祥. 基于Google API的导航地图软件设计与实现[J]. 计算机与现代化, 2012, 8(08): 213-217.