一种基于轨迹分段的轨迹数据隐私保护算法

发布时间：2021-01-23 00:04

　　随着基于位置服务应用的普及,应用提供商积累了大量的用户轨迹数据。通过数据分析,研究者从发布的轨迹数据集中提取出许多有用的信息,这些信息在交通监控、城市规划、移动性管理等领域有着广泛的应用前景。然而,直接发布蕴含丰富隐私信息的轨迹数据存在泄漏用户隐私的风险,为此需要在发布前对轨迹数据进行处理。由于轨迹数据具有规模大、维度高、背景知识丰富等特点,面向移动设备轨迹数据发布的隐私保护技术研究面临着严峻的挑战。本文针对轨迹数据发布中的隐私保护问题开展研究,提出了一种基于轨迹分段的轨迹数据隐私保护算法,该算法包含两个子算法。首先,针对传统方法丢弃时空点数目过多、划分后的等价类包含轨迹数目可能过少的问题,提出了一种基于轨迹分段填充的等价类划分子算法。算法将原始轨迹数据集划分为若干等价类,如果原始等价类大小小于阈值,便进行轨迹分段填充:选出若干等价类作为被分割的等价类（这些等价类的时间区间为当前等价类时间区间的超集）,然后将从被分割等价类中截取的轨迹分段填充到当前等价类。其次,针对传统方法时空点扰动距离过大以及删除的轨迹数目过多的问题,提出了一种基于轨迹分段聚类的聚类组构建子算法。算法的作用是将每个等... 

【文章来源】：广州大学广东省

【文章页数】：83 页

【学位级别】：硕士

【部分图文】：

不确定轨迹定义3.2（可能移动曲线PMC）轨迹的可能移动曲线为：

广州大学硕士学位论文22类集合，否则返回空集（13到16行）。该算法的功能其实就是在两个数组中找到所有相等的数，如果采用暴力解法需要循环m*n次，时间复杂度为O(mn)，其中m和n分别为两个数组的长度。如果先将数组排好序，再按照算法3.2的逻辑只需循环m+n次,时间复杂度为O(m+n)。下面有一个示例。下图中每个矩形代表一个等价类，矩形左上方和右上方数字分别代表等价类的开始时间、结束时间，矩形右侧的花括号内包含的数字都是轨迹ID。图3.2处理等价类[1,8]前开始时间为1的等价类集合图3.3处理等价类[1,8]前开始时间为9的等价类集合进入算法3.1，假设minEquivalence为12，当遍历到等价类ES1,8时，由于|ES1,8|=5<12，所以尝试在此刻获取候选等价类集合。调用算法3.2，传入第一个等价类集合ES1,H(8+1)={ES1,10,ES1,12,ES1,14,ES1,15}，传入第二个等价类集合ES9,={ES9,11,ES9,12,ES9,14,ES9,15}，传入阈值为minEquivalence|ES1,8|=62=4。算法3.2的处理

广州大学硕士学位论文22类集合，否则返回空集（13到16行）。该算法的功能其实就是在两个数组中找到所有相等的数，如果采用暴力解法需要循环m*n次，时间复杂度为O(mn)，其中m和n分别为两个数组的长度。如果先将数组排好序，再按照算法3.2的逻辑只需循环m+n次,时间复杂度为O(m+n)。下面有一个示例。下图中每个矩形代表一个等价类，矩形左上方和右上方数字分别代表等价类的开始时间、结束时间，矩形右侧的花括号内包含的数字都是轨迹ID。图3.2处理等价类[1,8]前开始时间为1的等价类集合图3.3处理等价类[1,8]前开始时间为9的等价类集合进入算法3.1，假设minEquivalence为12，当遍历到等价类ES1,8时，由于|ES1,8|=5<12，所以尝试在此刻获取候选等价类集合。调用算法3.2，传入第一个等价类集合ES1,H(8+1)={ES1,10,ES1,12,ES1,14,ES1,15}，传入第二个等价类集合ES9,={ES9,11,ES9,12,ES9,14,ES9,15}，传入阈值为minEquivalence|ES1,8|=62=4。算法3.2的处理


本文编号：2994157