Trajectory Interest Points Mining Based on Label Propagation and Privacy Protection

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

CLC Number:

TP393

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.

References

［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.