1、融合隐私保护的车辆轨迹数据停留点挖掘方法徐燕,樊娜,段宗涛,郝家欢,梁星(长安大学信息工程学院,西安710064)通信作者:樊娜,E-mail:摘要:随着车载 GPS 定位设备的普及,产生了大量的车辆轨迹数据和位置信息,各种轨迹挖掘技术也应运而生.然而,现有的轨迹挖掘技术较少考虑用户的隐私泄露问题,因此,本文提出了一种融合隐私保护的车辆轨迹数据停留点挖掘方法.在该算法中,首先通过密度聚类筛选出轨迹停留点,其次结合差分隐私技术对停留点进行隐私保护.通过实验验证,该方法不仅能有效识别出停留点的位置,还能保护其隐私不被泄露.关键词:数据挖掘;时空轨迹;停留点;隐私保护;差分隐私引用格式:徐燕,樊娜,
2、段宗涛,郝家欢,梁星.融合隐私保护的车辆轨迹数据停留点挖掘方法.计算机系统应用,2023,32(2):329338.http:/www.c-s- Method of Vehicle Trajectory Data Stay Point Fused with Privacy ProtectionXUYan,FANNa,DUANZong-Tao,HAOJia-Huan,LIANGXing(SchoolofInformationEngineering,ChanganUniversity,Xian710064,China)Abstract:Withthepopularizationofon-board
3、GPSpositioningequipment,alargeamountofvehicletrajectorydataandlocationinformationhavebeengenerated,andvarioustrajectoryminingtechnologieshaveemergedasthetimesrequire.However,theexistingtrajectoryminingtechnologiesrarelyconsidertheleakageofusersprivacy.Therefore,thisstudyproposesamethodofstaypointmin
4、ingfromvehicletrajectorydataintegratingprivacyprotection.Inthisalgorithm,thestaypointsinthetrajectoryarescreenedoutbydensityclustering,andprivacyprotectionofthestaypointsisthenconductedwiththedifferentialprivacytechnology.Theexperimentalverificationshowsthattheproposedmethodcannotonlyeffectivelyiden
5、tifythelocationofthestaypointsbutalsoprotecttheirprivacyfrombeingleaked.Key words:datamining;spatiotemporaltrajectory;staypoint;privacyprotection;differentialprivacy随着具有 GPS 定位功能的移动设备和车载传感装置的普及,海量的车辆时空轨迹数据被收集.对车载终端采集的时空轨迹数据进行挖掘和分析能够给商业机构、交通管理部门、法律信息查询机构以及基于位置的服务部门等提供相应的数据支持1,2.轨迹数据是移动对象运动过程中产生的离散采样位
6、置点,包括时间戳、经度、纬度、速度、高度等,这些采样点根据采样时间顺序构成了轨迹数据3.停留点是离散的轨迹数据中在某些位置停留时间达到一定程度的数据点,合理地对轨迹数据进行挖掘与研究,获取数据背后蕴含的有价值的内容,根据挖掘的信息预测人们的行为,能够为人们的生产生活提供便利,同时也能提供新的商业运作方式和科研工作方法.然而,随着信息化的不断发展以及近些年信息泄露导致的违法行为发生,人们逐渐认识到了隐私保护的重要性.当人们将个人轨迹数据上传至第三方服务器来获取位置服务时(服务器一般是不可信的),攻击者很容易获取到轨迹数据并进行恶意挖掘,严重泄露用户隐私比如工作单位、家庭住址等敏感信息.敏感信息的
7、泄漏可能会给用户带来不可估量的损失,进而计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(2):329338doi:10.15888/ki.csa.008934http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:陕西省重点研发计划(2022GY-039)收稿时间:2022-06-27;修改时间:2022-07-25;采用时间:2022-08-09;csa 在线出版时间:2022-10-28CNKI 网络首发时间:2022-11-16Rese
8、archandDevelopment研究开发329导致越来越多的用户由于担心信息泄露而拒绝使用相关的服务,这样会阻碍国内基于位置的相关服务的良性发展.我国“十三五”规划中曾提及要重视位置信息隐私安全建设,“十四五”规划中也再次对网络安全建设提出了新的要求4.车辆停留信息中一般包含用户的诸多隐私信息,现有的车辆轨迹停留点挖掘技术较多关注停留点的识别算法研究,考虑到隐私保护问题的研究较少.有效挖掘车辆停留信息同时保护用户的隐私不被侵犯是未来基于位置信息的服务行业持续良性发展的重要保障,同时也是响应国家“十四五”规划的要求.因此,如何有效挖掘车辆停留信息同时保护用户的隐私不被侵犯成为亟待解决的问题.
9、目前,针对轨迹数据停留点挖掘的隐私保护还是一个新兴的研究热点,存在两个主要问题亟待解决:(1)如何有效挖掘出停留点.(2)如何保证在挖掘停留点的过程中不泄露用户隐私.针对上述问题,本文提出一种融合隐私保护的车辆轨迹数据停留点挖掘方法,主要工作为:(1)结合密度聚类算法,设置时间阈值、距离阈值和速度阈值的判定条件,缩小停留点的筛选范围,有效挖掘出相关停留点.(2)基于差分隐私机制,对挖掘出来的停留点添加拉普拉斯噪声.传统的添加噪声方法是对整个轨迹序列加噪,不仅会消耗隐私预算还会降低数据可用性.本文是有针对性地对停留点添加噪声,能够减少隐私预算的消耗,提高数据可用性.(3)在真实重型卡车轨迹数据集
10、上进行了实验,以验证本文方法的有效性.1研究现状随着大数据的发展,时空轨迹数据挖掘逐渐成为学者的研究重点.时空轨迹数据在一定程度上反映了移动对象的性质、类别、状态等信息.时空轨迹数据挖掘指对人们的历史轨迹进行大数据分析,挖掘针对某些特定研究对象的新颖有价值的信息或者根据过去的轨迹数据对未来做出预测等.目前轨迹数据的挖掘方法主要有统计分析、轨迹聚类、轨迹孤立点识别、遗传算法、神经网络算法等5.轨迹聚类是目前比较经典的数据挖掘技术之一.通过车辆轨迹数据聚类,可以发现轨迹的相似行为,挖掘车辆的出行模式,停留信息等,可用于城市建设、交通规划、智能交通、区域规划等.按照聚类模型的不同,聚类分为密度聚类、
11、划分聚类、网格聚类、模型聚类以及层次聚类等6.Cao 等人7基于 GPS 轨迹数据提出了一个轨迹模式挖掘系统,结合 K-means 聚类匹配用户相似性轨迹,能够发现城市的密集区域.Enami 等人8利用 PrefixSpan和 BIDE 的序列模式挖掘算法,能够基于大量轨迹数据提取出频繁轨迹模式来预测对象未来轨迹的移动性.Cheng 等人9考虑轨迹的时间和空间特征,采用密度聚类的方法研究出租车的运动模式.在轨迹停留点挖掘方面,Zhou 等人10提出了 DJ-cluster 聚类算法,结合轨迹的空间特征筛选轨迹邻域点数,将不符合邻域最小点数的点标记为噪声,但轨迹属性较为单一,没有考虑轨迹的时间特
12、性.Gao 等人11设置时间阈值来判断停留点,用滑动窗口方法筛选停留点,提高了识别效率,但该方法对数据采用频率以及数据实时性要求较高.Niu 等人12提出了一种基于属性选择的轨迹的停止和移动挖掘算法,能够在缺乏详细地理数据的基础上,结合特征选择挖掘出轨迹聚类的核心属性,提高了位置挖掘的准确性,但没有考虑轨迹的隐私保护问题.在此基础上,部分学者关注到轨迹的隐私保护问题.Wang 等人13结合位置相似性度量将轨迹采样位置分成不同的等价概率类,采用假位置生成的方法对这些等价概率类中的轨迹进行重组,满足了采样轨迹的隐私保护要求.Mahdavifar 等人14采用匿名的方式保护轨迹隐私,根据移动对象的不
13、同而分配不同的隐私级别,使得具有一定背景知识的攻击者无法识别特定轨迹.Peng 等人15考虑到用户之间的位置信息相关性,提出了一种数据发布机制来抵抗推断攻击并自适应地保护用户相关的位置信息.Ning 等人16考虑到网络传输中的数据包含大量的图结构数据,而加权图中的边权重可能会带来隐私泄露的风险,提出了一种基于加权图的隐私保护算法,通过对整个图集添加噪声以及为边权重分配隐私预算的方式实现对数据的隐私保护.此外,部分学者也关注到了轨迹挖掘与隐私保护相结合的研究方向.Han 等人17通过指数机制,将同一时间的位置集快速准确地划分为不同的分区,输出更准确的位置点分区和轨迹计数组,可以安全快速地进行数据
14、挖掘工作,同时将拉普拉斯噪声添加到轨迹数据中保护隐私.Zhao 等人18将拉普拉斯噪声添加到集群的轨迹位置计数中以加强数据保护,然后,将受约束的拉普拉斯噪声加入到聚类中的轨迹位置数据中,根据噪声位置数据和噪声位置计数,得到聚类中的噪声计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第2期330研究开发ResearchandDevelopment聚类中心,之后使用差分隐私技术增强隐私保护能力,该方法具有良好的聚类效果同时兼具隐私保护功能.Xu 等人19制定了轨迹混淆问题,以选择与原始轨迹序列差异最小的最优轨迹序列,为了防止隐私泄露,他们分别在位置混淆矩阵生成和轨迹序列函数
15、生成阶段将拉普拉斯噪声和指数噪声添加到输出中,该方法可以较为准确地挖掘社区轨迹信息,同时防止数据泄漏.王豪等人20在传统的聚类和差分隐私中加入了二维拉普拉斯噪声,并将噪声转换坐标系由直角坐标系转换为极坐标系,将其融入到原始轨迹数据中.赵书鹏21将AP 轨迹聚类算法与豪斯多夫距离相结合,提出一种新的基于聚类的差分隐私保护方法,该方法受轨迹集合密集程度和范围变化的影响较小.赵濛22将-差分隐私技术与幂迭代聚类算法相结合,该算法根据目标的不同添加不同的噪声函数,做到了数据挖掘和隐私保护相统一,但是该算法本身过于复杂且在小数据集上效果不佳.多数研究工作中里采用的是轨迹点密集的人类移动数据集,较少考虑经
16、纬度跨度大的车辆轨迹数据集.在轨迹隐私保护过程中,部分研究会忽略攻击者的背景知识,没有考虑位置服务提供商(locationserviceprovider,LSP)的不可信性.因此,本文重点考虑 LSP不完全可信的情况下,如何在车辆轨迹数据挖掘的过程中,保护其隐私信息不被泄露.2融合隐私保护的车辆轨迹数据停留点挖掘方法近年来,融合隐私保护的数据挖掘得到了广泛关注23.常见的隐私保护技术有数据加密、匿名、差分隐私等24.数据加密技术通过密码学原理将数据加密成不可读的信息,需要通过某种解密机制来获取数据的原始信息.这种技术具有可靠性高、数据不易丢失等特点,但加密过程需要较高的运算成本,且运算效率较低.匿名技术通常是对数据进行抽象化的描述,使数据挖掘者无法在公开数据集中关联到隐私个体.这种技术可以有效保护用户隐私,但无法抵御背景知识攻击.差分隐私是 Dwork25在 2006 年首次提出的一种基于数据扰动的隐私保护模型,由于该模型具有严格的数学定理证明,能够抵御攻击者的背景知识攻击进而提供有效的隐私保护,成为当下隐私保护领域的研究热点.基于此,本节针对车辆停留点挖掘过程中可能产生的隐私泄露问题
