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 K-means algorithm. In the framework, the client calculates 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 K-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.

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

[1]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.

[2]Arif M, Chen JE, Wang GJ, et al., 2021. Privacy preserving and data publication for vehicular trajectories with differential privacy. Measurement, 173:108675.

[3]Atev S, Miller G, Papanikolopoulos NP, 2010. Clustering of vehicle trajectories. IEEE Trans Intell Transp Syst, 11(3):647-657.

[4]Benkert M, Gudmundsson J, Hübner F, et al., 2008. Reporting flock patterns. Comput Geomet, 41(3):111-125.

[5]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.

[6]Bezdek JC, 1981. Pattern Recognition with Fuzzy Objective Function Algorithms. Springer, New York, USA.

[7]Caliński T, Harabasz J, 1974. A dendrite method for cluster analysis. Commun Statist, 3(1):1-27.

[8]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.

[9]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.

[10]Cho K, Van Merriënboer B, Gulcehre C, et al., 2014. Learning phrase representations using RNN encoder–decoder for statistical machine translation.

[11]Davies DL, Bouldin DW, 1979. A cluster separation measure. IEEE Trans Patt Anal Mach Intell, PAMI-1(2):224-227.

[12]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.

[13]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.

[14]Gariel M, Srivastava AN, Feron E, 2011. Trajectory clustering and an application to airspace monitoring. IEEE Trans Intell Transp Syst, 12(4):1511-1524.

[15]Gazdag A, Lestyán S, Remeli M, et al., 2023. Privacy pitfalls of releasing in-vehicle network data. Veh Commun, 39:100565.

[16]Guo MM, Jin XY, Pissinou N, et al., 2015. In-network trajectory privacy preservation. ACM Comput Surv, 48(2):23.

[17]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.

[18]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.

[19]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.

[20]Kluger Y, Basri R, Chang JT, et al., 2003. Spectral biclustering of microarray data: coclustering genes and conditions. Genome Res, 13(4):703-716.

[21]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).

[22]Lu L, Lin Y, Wen Y, et al., 2023. Federated clustering for recognizing driving styles from private trajectories. Eng Appl Artif Intell, 118:105714.

[23]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.

[24]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.

[25]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.

[26]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.

[27]Pan XL, Wang HP, Cheng XQ, et al., 2020. Online detection of anomaly behaviors based on multidimensional trajectories. Inform Fusion, 58:40-51.

[28]Park HS, Jun CH, 2009. A simple and fast algorithm for K-medoids clustering. Expert Syst Appl, 36(2):3336-3341.

[29]Rousseeuw PJ, 1987. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J Comput Appl Math, 20:53-65.

[30]Sculley D, 2010. Web-scale k-means clustering. Proc 19^th Int Conf on World Wide Web, p.1177-1178.

[31]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).

[32]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.

[33]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.

[34]Xin Y, Xie ZQ, Yang J, 2017. The privacy preserving method for dynamic trajectory releasing based on adaptive clustering. Inform Sci, 378:131-143.

[35]Xu XH, Liu CS, Li JH, et al., 2022. Trajectory clustering for SVR-based time of arrival estimation. Ocean Eng, 259:111930.

[36]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.

[37]Yu QY, Luo YL, Chen CM, et al., 2019. Trajectory similarity clustering based on multi-feature distance measurement. Appl Intell, 49(6):2315-2338.

[38]Zhang T, Ramakrishnan R, Livny M, 1996. BIRCH: an efficient data clustering method for very large databases. ACM SIGMOD Rec, 25(2):103-114.

[39]Zhao XD, Pi DC, Chen JF, 2020. Novel trajectory privacy-preserving method based on clustering using differential privacy. Expert Syst Appl, 149:113241.

[40]Zheng Y, 2015. Trajectory data mining. ACM Trans Intell Syst Technol, 6(3):29.