隐私保护下的车辆轨迹聚类方法研究

田冉; 高普伦; 刘颜星

doi:10.1631/FITEE.2300369

Your Location：

Home >

Browse articles >

隐私保护下的车辆轨迹聚类方法研究

常规文章 | Updated：2024-07-28

- 隐私保护下的车辆轨迹聚类方法研究
- A privacy-preserving vehicle trajectory clustering framework
- 信息与电子工程前沿(英文版) 2024年25卷第7期页码：988-1002
- Affiliations：
  
  College of Computer Science & Engineering, Northwest Normal University, Lanzhou 730070, China
- Author bio：
  
  ‡Corresponding author
  202031603111@nwnu.edu.cn
  lyanxing@nwnu.edu.cn
- Funds：
  
  the National Natural Science Foundation of China(71961028);the Key Research and Development Program of Gansu Province, China(22YF7GA171);the University Industry Support Program of Gansu Province, China(2023QB-115);the Innovation Fund for Science and Technology-based Small and Medium Enterprises of Gansu Province, China(23CXGA0136);the Traditional Chinese Medicine Industry Innovation Consortium Project of Gansu Province, China(22ZD6FA021-5);the Scientific Research Project of the Lanzhou Science and Technology Program, China(2018-01-58)
- DOI：10.1631/FITEE.2300369
  中图分类号： TP183
- 收稿：2023-05-23，
  
  修回：2023-07-21，
  
  纸质出版：2024-07-0
- Accepted：
Scan QR Code
田冉, 高普伦, 刘颜星. 隐私保护下的车辆轨迹聚类方法研究[J]. 信息与电子工程前沿(英文版), 2024,25(7):988-1002.

Ran TIAN, Pulun GAO, Yanxing LIU. A privacy-preserving vehicle trajectory clustering framework[J]. Frontiers of Information Technology & Electronic Engineering, 2024, 25(7): 988-1002.
田冉, 高普伦, 刘颜星. 隐私保护下的车辆轨迹聚类方法研究[J]. 信息与电子工程前沿(英文版), 2024,25(7):988-1002. DOI： 10.1631/FITEE.2300369.

Ran TIAN, Pulun GAO, Yanxing LIU. A privacy-preserving vehicle trajectory clustering framework[J]. Frontiers of Information Technology & Electronic Engineering, 2024, 25(7): 988-1002. DOI： 10.1631/FITEE.2300369.

摘要

车辆轨迹聚类方法作为时空交通数据挖掘的重要工具之一，被广泛地运用于挖掘车辆的行为模式。但是如果直接将原始车辆轨迹数据上传到服务器并进行聚类则具有隐私泄露的风险。因此，针对在保护用户隐私的同时进行车辆轨迹聚类这一挑战，本文提出一种隐私保护下的车辆轨迹聚类框架，并构建了基于变分自编码器和改进

-means算法的车辆轨迹聚类模型（IKV）。在该框架中，客户端计算出车辆轨迹的隐藏变量并上传至服务端，服务端再利用隐藏变量计算出聚类结果，并将分析结果发放给各客户端。IKV的工作流程如下：首先利用历史车辆轨迹数据在变分自编码器上进行训练，当变分自编码器的解码器接近原始数据时，将变分自编码器的编码器部署到车辆端的边缘计算设备；其次由车辆端的编码器计算车辆本地轨迹数据的隐变量，并将隐变量上传至服务器端；最后在服务器端利用改进的

-means算法基于车辆上传的隐变量进行车辆轨迹聚类计算。在三个真实数据集上，我们将IKV与多种基准方法在多个评价指标上进行了比较。在9组性能对比实验中，IKV算法在6组中达到了最优或接近最优的性能水平。同时在9组敏感性分析实验中，该算法在7组实验中展现出了显著的稳定性和对参数变化的鲁棒性。这些结果验证了本文提出的框架不仅适用于注重隐私的生产环境，如拼车服务，而且由于其对聚簇数量的低敏感性，还能适应不同规模的聚类任务。

Abstract

As one of the essential tools for spatio‒temporal traffic data mining

vehicle trajectory clustering is widely used to mine the behavior patterns of vehicles. However

uploading original vehicle trajectory data to the server and clustering carry the risk of privacy leakage. Therefore

one of the current challenges is determining how to perform vehicle trajectory clustering while protecting user privacy. We propose a privacy-preserving vehicle trajectory clustering framework and construct a vehicle trajectory clustering model (IKV) based on the variational autoencoder (VAE) and an improved

-means algorithm. In the framework

the client calcula

tes the hidden variables of the vehicle trajectory and uploads the variables to the server; the server uses the hidden variables for clustering analysis and delivers the analysis results to the client. The IKV’ workflow is as follows: first

we train the VAE with historical vehicle trajectory data (when VAE’s decoder can approximate the original data

the encoder is deployed to the edge computing device); second

the edge device transmits the hidden variables to the server; finally

clustering is performed using improved

-means

which prevents the leakage of the vehicle trajectory. IKV is compared to numerous clustering methods on three datasets. In the nine performance comparison experiments

IKV achieves optimal or sub-optimal performance in six of the experiments. Furthermore

in the nine sensitivity analysis experiments

IKV not only demonstrates significant stability in seven experiments but also shows good robustness to hyperparameter variations. These results validate that the framework proposed in this paper is not only suitable for privacy-conscious production environments

such as carpooling tasks

but also adapts to clustering tasks of different magnitudes due to the low sensitivity to the number of cluster centers.

关键词

Keywords

references

Advani C , Bhaskar A , Haque MM , 2022 . Bi-level clustering of vehicle trajectories for path choice set and its nested structure identification . Transp Res Part C Emerg Technol , 144 : 103895 . https://doi.org/10.1016/j.trc.2022.103895 https://doi.org/10.1016/j.trc.2022.103895

Arif M , Chen JE , Wang GJ , et al. , 2021 . Privacy preserving and data publication for vehicular trajectories with differential privacy . Measurement , 173 : 108675 . https://doi.org/10.1016/j.measurement.2020.108675 https://doi.org/10.1016/j.measurement.2020.108675

Atev S , Miller G , Papanikolopoulos NP , 2010 . Clustering of vehicle trajectories . IEEE Trans Intell Transp Syst , 11 ( 3 ): 647 - 657 . https://doi.org/10.1109/tits.2010.2048101 https://doi.org/10.1109/tits.2010.2048101

Benkert M , Gudmundsson J , Hübner F , et al. , 2008 . Reporting flock patterns . Comput Geomet , 41 ( 3 ): 111 - 125 . https://doi.org/10.1016/j.comgeo.2007.10.003 https://doi.org/10.1016/j.comgeo.2007.10.003

Besse PC , Guillouet B , Loubes JM , et al. , 2016 . Review and perspective for distance-based clustering of vehicle trajectories . IEEE Trans Intell Transp Syst , 17 ( 11 ): 3306 - 3317 . https://doi.org/10.1109/tits.2016.2547641 https://doi.org/10.1109/tits.2016.2547641

Bezdek JC , 1981 . Pattern Recognition with Fuzzy Objective Function Algorithms . Springer , New York, USA . https://doi.org/10.1007/978-1-4757-0450-1 https://doi.org/10.1007/978-1-4757-0450-1

Caliński T , Harabasz J , 1974 . A dendrite method for cluster analysis . Commun Statist , 3 ( 1 ): 1 - 27 . https://doi.org/10.1080/03610927408827101 https://doi.org/10.1080/03610927408827101

Chang LC , Chang FJ , Yang SN , et al. , 2020 . Self-organizing maps of typhoon tracks allow for flood forecasts up to two days in advance . Nat Commun , 11 ( 1 ): 1983 . https://doi.org/10.1038/s41467-020-15734-7 https://doi.org/10.1038/s41467-020-15734-7

Chen CM , Ye Z , Hu F , et al. , 2021 . Vehicle trajectory-clustering method based on road-network-sensitive features . J Intell Fuzzy Syst , 41 ( 1 ): 2357 - 2375 . https://doi.org/10.3233/jifs-211270 https://doi.org/10.3233/jifs-211270

Cho K , Van Merriënboer B , Gulcehre C , et al. , 2014 . Learning phrase representations using RNN encoder–decoder for statistical machine translation . https://doi.org/10.48550/arxiv.1406.1078 https://doi.org/10.48550/arxiv.1406.1078

Davies DL , Bouldin DW , 1979 . A cluster separation measure . IEEE Trans Patt Anal Mach Intell , PAMI-1 ( 2 ): 224 - 227 . https://doi.org/10.1109/tpami.1979.4766909 https://doi.org/10.1109/tpami.1979.4766909

Dunn JC , 1973 . A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters . J Cybern , 3 ( 3 ): 32 - 57 . https://doi.org/10.1080/01969727308546046 https://doi.org/10.1080/01969727308546046

Gaffney S , Smyth P , 1999 . Trajectory clustering with mixtures of regression models . Proc 5 th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , p. 63 - 72 . https://doi.org/10.1145/312129.312198 https://doi.org/10.1145/312129.312198

Gariel M , Srivastava AN , Feron E , 2011 . Trajectory clustering and an application to airspace monitoring . IEEE Trans Intell Transp Syst , 12 ( 4 ): 1511 - 1524 . https://doi.org/10.1109/tits.2011.2160628 https://doi.org/10.1109/tits.2011.2160628

Gazdag A , Lestyán S , Remeli M , et al. , 2023 . Privacy pitfalls of releasing in-vehicle network data . Veh Commun , 39 : 100565 . https://doi.org/10.1016/j.vehcom.2022.100565 https://doi.org/10.1016/j.vehcom.2022.100565

Guo MM , Jin XY , Pissinou N , et al. , 2015 . In-network trajectory privacy preservation . ACM Comput Surv , 48 ( 2 ): 23 . https://doi.org/10.1145/2818183 https://doi.org/10.1145/2818183

Hong ZH , Chen Y , Mahmassani HS , et al. , 2017 . Commuter ride-sharing using topology-based vehicle trajectory clustering: methodology, application and impact evaluation . Transp Res Part C Emerg Technol , 85 : 573 - 590 . https://doi.org/10.1016/j.trc.2017.10.020 https://doi.org/10.1016/j.trc.2017.10.020

Hong ZH , Chen Y , Mahmassani HS , 2018 . Recognizing network trip patterns using a spatio-temporal vehicle trajectory clustering algorithm . IEEE Trans Intell Transp Syst , 19 ( 8 ): 2548 - 2557 . https://doi.org/10.1109/tits.2017.2754401 https://doi.org/10.1109/tits.2017.2754401

Jin FM , Hua W , Francia M , et al. , 2023 . A survey and experimental study on privacy-preserving trajectory data publishing . IEEE Trans Knowl Data Eng , 35 ( 6 ): 5577 - 5596 . https://doi.org/10.1109/tkde.2022.3174204 https://doi.org/10.1109/tkde.2022.3174204

Kluger Y , Basri R , Chang JT , et al. , 2003 . Spectral biclustering of microarray data: coclustering genes and conditions . Genome Res , 13 ( 4 ): 703 - 716 . https://doi.org/10.1101/gr.648603 https://doi.org/10.1101/gr.648603

Kong XP , Lu L , 2022 . Privacy-preserved vehicular trajectory embedding federated learning and clustering . J Nanjing Norm Univ (Eng Technol Ed) , 22 ( 2 ): 80 - 86 (in Chinese) . https://doi.org/10.3969/j.issn.1672-1292.2022.02.012 https://doi.org/10.3969/j.issn.1672-1292.2022.02.012

Lu L , Lin Y , Wen Y , et al. , 2023 . Federated clustering for recognizing driving styles from private trajectories . Eng Appl Artif Intell , 118 : 105714 . https://doi.org/10.1016/j.engappai.2022.105714 https://doi.org/10.1016/j.engappai.2022.105714

Ma Z , Zhang T , Liu XM , et al. , 2019 . Real-time privacy-preserving data release over vehicle trajectory . IEEE Trans Veh Technol , 68 ( 8 ): 8091 - 8102 . https://doi.org/10.1109/tvt.2019.2924679 https://doi.org/10.1109/tvt.2019.2924679

MacQueen J , 1967 . Some methods for classification and analysis of multivariate observations . Proc 5 th Berkeley Symp on Mathematical Statistics and Probability , p. 281 - 297 .

Ng AY , Jordan MI , Weiss Y , 2001 . On spectral clustering: analysis and an algorithm . Proc 14th Int Conf on Neural Information Processing Systems: Natural and Synthetic , p. 849 - 856 .

Oksanen J , Bergman C , Sainio J , et al. , 2015 . Methods for deriving and calibrating privacy-preserving heat maps from mobile sports tracking application data . J Transp Geogr , 48 : 135 - 144 . https://doi.org/10.1016/j.jtrangeo.2015.09.001 https://doi.org/10.1016/j.jtrangeo.2015.09.001

Pan XL , Wang HP , Cheng XQ , et al. , 2020 . Online detection of anomaly behaviors based on multidimensional trajectories . Inform Fusion , 58 : 40 - 51 . https://doi.org/10.1016/j.inffus.2019.12.009 https://doi.org/10.1016/j.inffus.2019.12.009

Park HS , Jun CH , 2009 . A simple and fast algorithm for K -medoids clustering . Expert Syst Appl , 36 ( 2 ): 3336 - 3341 . https://doi.org/10.1016/j.eswa.2008.01.039 https://doi.org/10.1016/j.eswa.2008.01.039

Rousseeuw PJ , 1987 . Silhouettes: a graphical aid to the interpretation and validation of cluster analysis . J Comput Appl Math , 20 : 53 - 65 . https://doi.org/10.1016/0377-0427(87)90125-7 https://doi.org/10.1016/0377-0427(87)90125-7

Sculley D , 2010 . Web-scale k -means clustering . Proc 19 th Int Conf on World Wide Web , p. 1177 - 1178 . https://doi.org/10.1145/1772690.1772862 https://doi.org/10.1145/1772690.1772862

Wang H , Xu ZQ , 2018 . Differential privacy preserving method for trajectory clustering . J Huazhong Univ Sci Technol (Nat Sci Ed) , 46 ( 1 ): 32 - 36 (in Chinese) . https://doi.org/10.13245/j.hust.180107 https://doi.org/10.13245/j.hust.180107

Wang W , Xia F , Nie HS , et al. , 2021 . Vehicle trajectory clustering based on dynamic representation learning of Internet of Vehicles . IEEE Trans Intell Transp Syst , 22 ( 6 ): 3567 - 3576 . https://doi.org/10.1109/tits.2020.2995856 https://doi.org/10.1109/tits.2020.2995856

Xie XW , Wu B , Hou BT , 2023 . BEPHAP: a blockchain-based efficient privacy-preserving handover authentication protocol with key agreement for Internet of Vehicles . J Syst Archit , 138 : 102869 . https://doi.org/10.1016/j.sysarc.2023.102869 https://doi.org/10.1016/j.sysarc.2023.102869

Xin Y , Xie ZQ , Yang J , 2017 . The privacy preserving method for dynamic trajectory releasing based on adaptive clustering . Inform Sci , 378 : 131 - 143 . https://doi.org/10.1016/j.ins.2016.10.038 https://doi.org/10.1016/j.ins.2016.10.038

Xu XH , Liu CS , Li JH , et al. , 2022 . Trajectory clustering for SVR-based time of arrival estimation . Ocean Eng , 259 : 111930 . https://doi.org/10.1016/j.oceaneng.2022.111930 https://doi.org/10.1016/j.oceaneng.2022.111930

Yi DW , Su JY , Liu CJ , et al. , 2019 . Trajectory clustering aided personalized driver intention prediction for intelligent vehicles . IEEE Trans Ind Inform , 15 ( 6 ): 3693 - 3702 . https://doi.org/10.1109/tii.2018.2890141 https://doi.org/10.1109/tii.2018.2890141

Yu QY , Luo YL , Chen CM , et al. , 2019 . Trajectory similarity clustering based on multi-feature distance measurement . Appl Intell , 49 ( 6 ): 2315 - 2338 . https://doi.org/10.1007/s10489-018-1385-x https://doi.org/10.1007/s10489-018-1385-x

Zhang T , Ramakrishnan R , Livny M , 1996 . BIRCH: an efficient data clustering method for very large databases . ACM SIGMOD Rec , 25 ( 2 ): 103 - 114 . https://doi.org/10.1145/235968.233324 https://doi.org/10.1145/235968.233324

Zhao XD , Pi DC , Chen JF , 2020 . Novel trajectory privacy-preserving method based on clustering using differential privacy . Expert Syst Appl , 149 : 113241 . https://doi.org/10.1016/j.eswa.2020.113241 https://doi.org/10.1016/j.eswa.2020.113241

Zheng Y , 2015 . Trajectory data mining . ACM Trans Intell Syst Technol , 6 ( 3 ): 29 . https://doi.org/10.1145/2743025 https://doi.org/10.1145/2743025

浏览量

194

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

PPDO: a privacy-preservation-aware delay optimization task-offloading algorithm for collaborative edge computing