本发明涉及车辆轨迹数据挖掘及隐私保护领域，具体为一种融合隐私保护的轨迹数据标签聚类方法。
背景技术：
随着车载无线传感设备的发展和普及，可以收集到的车辆轨迹数据信息也愈加完善。轨迹聚类方法是对轨迹数据进行分析、应用的关键技术之一。传统的轨迹聚类方法主要采用基于距离测量的方法，但存在聚类不精确、估算成本高、缺乏隐私保护机制等缺点。近年来提出的基于语义分析的轨迹聚类方法有效提高了聚类精度，但是在聚类的过程中，依然没有考虑隐私保护。因此如何在进行轨迹数据挖掘的同时保护隐私敏感数据不会泄露，成为亟需解决的问题。
技术实现要素：
针对现有技术中存在的问题，本发明提供一种融合隐私保护的轨迹数据标签聚类方法，能够有效保护车辆轨迹聚类过程中所涉及到的隐私信息。
为达到上述目的，本发明采用如下技术方案：
一种融合隐私保护的轨迹数据标签聚类方法，包括以下步骤：
步骤1)、数据预处理：将从车载传感器获取到的最原始轨迹数据进行降维处理；
步骤2)、对偶图转换：根据降维处理后的最原始轨迹数据将道路网中两个交叉路口之间的道路段建模为一个节点，并将每两个节点之间的交叉路口建模为节点间的连线，从而将道路网转换为对偶图；
步骤3)、初始化所有节点的标签信息，使得每个节点拥有唯一的标签，并为每一个节点设置一个存储历史标签的序列，然后对初始化后的标签信息通过slpa标签传播方法进行标签传播，完成标签聚类；
步骤4)、对存储历史标签的序列进行泛化处理；
步骤5)、去除低频标签：根据步骤3)标签序列中以及步骤4)泛化处理后的标签聚类结果，如果标签聚类结果中出现的频率低于预先设定的阈值，则删除该标签；否则直接输出最终聚类结果。
进一步的，将从车载传感器设备获取到的最原始轨迹数据中移除异常数据，同时从最原始轨迹数据集中提取gps坐标属性作为轨迹的语义标签；然后将原始轨迹数据进行高斯投影，将原始轨迹中的经纬度坐标转化为大地坐标，从而完成对最原始轨迹数据的降维处理。
进一步的，通过高斯投影坐标转换工具将原始轨迹数据进行高斯投影。
进一步的，步骤2)中，随机选择一个节点，记做监听节点，并将该节点设置为当前节点，将其邻居节点记做传播节点；
当前节点的每一个传播节点随机选择概率正比于在当前节点存储序列中出现概率(pi)的标签，并把该标签发送到监听节点；
其中，listi表示当前存储序列中选中标签出现的次数，∑listi表示当前标签序列中所有标签出现次数的总和，0<pi<＝1；
当前节点从传播节点传播的标签信息集中选择出现概率最大的标签添加到监听节点存储的标签列表中，并将出现概率最大的标签作为本次迭代中的新标签；
重复上述迭代过程使标签在不断的遍历过程中传播，直至收敛或遍历达到设定的次数，结束迭代。
进一步的，步骤4)中具体步骤包括：如果车辆身份识别号的属性列标识为准标识符列，则对该车辆身份识别号进行全局泛化处理；如果车辆身份识别号的属性列标识不是准标识符列，则判断车辆身份识别号的属性列标识是否为兴趣点，如果是兴趣点则对兴趣点处的位置坐标进行局部泛化处理。
进一步的，如果车辆身份识别号的属性列标识不是准标识符列，则进行以下步骤：
4.2.1在标签序列中对每一个位置点的取值个数进行统计，并取出统计个数大于等于阈值10的兴趣点坐标；
4.2.2取出的统计个数大于等于阈值10的兴趣点坐标按照统计个数的大小进行降序排列；
4.2.3按照步骤4.2.2中的排列顺序，选择统计个数最大的兴趣点坐标进行首次泛化处理；
4.2.4若首次泛化处理后的标签序列不满足泛化处理结果，跳转至步骤4.2.1，否则跳转至步骤4.2.5；
4.2.5进行迭代计算，直到所有大于等于阈值的兴趣点坐标全部完成局部泛化处理，否则跳转至步骤4.2.2；
4.3使用泛化处理对普通点的位置坐标进行全局泛化处理。
进一步的，普通点指位置坐标数据中除了兴趣点之外的点。
进一步的，全局泛化指对同一组数据一次性进行相同的泛化操作。
进一步的，局部泛化指为同一组数据中的不同子集进行不同的泛化操作。
与现有技术相比，本发明具有以下有益的技术效果：
本发明一种融合隐私保护的轨迹数据标签聚类方法，将从车载传感器获取到的最原始轨迹数据进行降维处理，将车辆轨迹数据挖掘与轨迹中兴趣点的隐私保护结合起来，根据降维处理后的最原始轨迹数据将道路网中两个交叉路口之间的道路段建模为一个节点，并将每两个节点之间的交叉路口建模为节点间的连线，从而将道路网转换为对偶图；在标签传播的过程中，对于存储的标签序列，首先将车辆身份识别号进行全局泛化处理，实现对单个车辆轨迹的匿名处理；对于精确到位置点的经纬度坐标列，结合车辆轨迹数据中的停留点数据，对兴趣点进行局部泛化处理，其他点采用全局泛化处理方法，继而实现对所有高频停留点的隐私保护，在聚类过程中，考虑了轨迹数据中的车辆身份标识号以及gps坐标属性语义信息，将车辆轨迹数据挖掘与泛化处理结合起来，对车辆轨迹数据中的敏感信息进行隐匿处理，本方法能够有效保护车辆轨迹聚类过程中所涉及到的隐私信息。
对于精确到位置点的经纬度坐标列，结合车辆轨迹数据中的停留点数据，对兴趣点进行局部泛化处理，其他点采用全局泛化处理方法，继而实现对所有高频停留点的隐私保护。
附图说明
图1为本发明实例中所述方法的流程框图。
图2为本发明实例中由道路网转换而来的对偶图。
具体实施方式
下面结合附图对本发明做进一步详细描述：
如图1、图2所示，本发明一种融合隐私保护的轨迹数据标签聚类方法，如图1所示，具体包括如下步骤，
步骤1，数据预处理；
1.1将从车载传感器设备获取到的最原始轨迹数据进行清洗处理得到原始轨迹数据；
清洗处理具体指从最原始轨迹数据移除异常数据，同时从最原始轨迹数据集中提取gps坐标属性作为轨迹的语义标签；gps坐标属性包括车辆速度、航向和高度。
1.2将原始轨迹数据(即清洗过的最原始轨迹数据)通过高斯投影坐标转换工具进行高斯投影，将原始轨迹中的经纬度坐标转化为大地坐标，从而完成对最原始轨迹数据的降维处理；
原始轨迹：表示一定时间间隔内对于车辆的时空采样点(vi，xi_t，yi_t，t)的序列。其中，xi_t表示车辆vi在t时刻的经度坐标，yi_t表示车辆vi在t时刻的纬度坐标。
步骤2，对偶图转换：
2.1根据降维处理后的最原始轨迹数据将道路网中两个交叉路口之间的道路段建模为一个节点，并将每两个节点之间的交叉路口建模为节点间的连线；
2.2按照步骤2.1中的建模方式，将道路网转换为对偶图，如图2所示；
步骤3，使用speaker-listener标签传播方法(speaker-listenerlabelpropagationalgorithm,slpa)进行标签传播；
3.1初始化所有节点的标签信息，使得每个节点拥有唯一的标签，并为每一个节点设置一个存储历史标签的序列；标签信息指融合轨迹数据语义信息的轨迹数据，包括车辆的速度、航向和高度；标签信息还可以是自定义的语义标签，包括车辆轨迹数目；
3.2进行标签传播过程，具体过程如下：
3.2.1随机选择一个节点，记做监听节点，并将该节点设置为当前节点，将其邻居节点记做传播节点；
3.2.2当前节点的每一个传播节点随机选择概率正比于在当前节点存储序列中出现概率(pi)的标签，并把该标签发送到监听节点；
其中，listi表示当前存储序列中选中标签出现的次数，∑listi表示当前标签序列中所有标签出现次数的总和，0<pi<＝1；
3.2.3当前节点从传播节点传播的标签信息集中选择出现概率最大的标签添加到监听节点存储的标签列表中，并将出现概率最大的标签作为本次迭代中的新标签；
3.2.4重复上述迭代过程直至收敛或遍历达到设定的次数(设定的次数由用户预定义产生)，结束迭代，否则，跳转至步骤3.2，使标签在不断的遍历过程中传播；
步骤4，对步骤3.1中存储历史标签的序列进行k匿名处理，k匿名处理指数据的泛化处理，即将不同的数据进行统一化的表示。由于车辆轨迹数据在相邻的时间段内取值略有差异，对不同的属性值进行统一化的表示，使得攻击者无法区分兴趣点与普通点，从而达到隐私保护的目的；
4.1使用k匿名处理对车辆身份识别号进行全局泛化处理；
4.1.1将车辆身份识别号的属性列标识为准标识符列；
4.1.2结合车辆原始轨迹数据中车辆身份标识号可以暴露该车辆身份信息的特点，对车辆身份识别号进行全局泛化处理，全局泛化表示对同一组数据一次性进行相同的泛化操作；全局泛化处理后进入步骤5；
4.2使用k匿名处理对兴趣点处的位置坐标进行局部泛化处理；兴趣点指结合车辆轨迹数据，在同一位置(经度坐标值和纬度坐标值相等)在标签序列中出现的次数超过预先设置阈值的采样点；本申请阈值设置为10。
4.2.1在标签序列中对每一个位置点的取值个数进行统计，并取出统计个数大于等于阈值10的兴趣点坐标；
4.2.2取出的统计个数大于等于阈值10的兴趣点坐标按照统计个数的大小进行降序排列；
4.2.3按照步骤4.2.2中的排列顺序，选择统计个数最大的兴趣点坐标进行首次泛化处理；
4.2.4检测首次泛化后的标签序列，若不符合泛化处理结果(在本实施例中指每条记录数据至少与其他k-1条数据的属性值相同)，跳转至步骤4.2.1，否则跳转至步骤4.2.5；
4.2.5进行迭代计算，直到所有大于等于阈值的兴趣点坐标全部完成局部泛化处理即可，否则跳转至步骤4.2.2；
4.3使用k匿名处理对普通点的位置坐标进行全局泛化处理，全局泛化处理后进入步骤5；
步骤5，去除低频标签；根据步骤3标签序列中的标签聚类结果，如果标签出现的频率低于预先设定的阈值，则删除该标签；否则，算法结束，输出最终聚类结果。
1.一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，包括以下步骤：
步骤1)、数据预处理：将从车载传感器获取到的最原始轨迹数据进行降维处理；
步骤2)、对偶图转换：根据降维处理后的最原始轨迹数据将道路网中两个交叉路口之间的道路段建模为一个节点，并将每两个节点之间的交叉路口建模为节点间的连线，从而将道路网转换为对偶图；
步骤3)、初始化所有节点的标签信息，使得每个节点拥有唯一的标签，并为每一个节点设置一个存储历史标签的序列，然后对初始化后的标签信息通过slpa标签传播方法进行标签传播，完成标签聚类；
步骤4)、对存储历史标签的序列进行泛化处理；
步骤5)、去除低频标签：根据步骤3)标签序列中以及步骤4)泛化处理后的标签聚类结果，如果标签聚类结果中出现的频率低于预先设定的阈值，则删除该标签；否则直接输出最终聚类结果。
2.根据权利要求1所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，将从车载传感器设备获取到的最原始轨迹数据中移除异常数据，同时从最原始轨迹数据集中提取gps坐标属性作为轨迹的语义标签；然后将原始轨迹数据进行高斯投影，将原始轨迹中的经纬度坐标转化为大地坐标，从而完成对最原始轨迹数据的降维处理。
3.根据权利要求2所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，通过高斯投影坐标转换工具将原始轨迹数据进行高斯投影。
4.根据权利要求1所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，步骤2)中，随机选择一个节点，记做监听节点，并将该节点设置为当前节点，将其邻居节点记做传播节点；
当前节点的每一个传播节点随机选择概率正比于在当前节点存储序列中出现概率pi的标签，并把该标签发送到监听节点；
其中，listi表示当前存储序列中选中标签出现的次数，∑listi表示当前标签序列中所有标签出现次数的总和，0<pi<＝1；
当前节点从传播节点传播的标签信息集中选择出现概率最大的标签添加到监听节点存储的标签列表中，并将出现概率最大的标签作为本次迭代中的新标签；
重复上述迭代过程使标签在不断的遍历过程中传播，直至收敛或遍历达到设定的次数，结束迭代。
5.根据权利要求1所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，步骤4)中具体步骤包括：如果车辆身份识别号的属性列标识为准标识符列，则对该车辆身份识别号进行全局泛化处理；如果车辆身份识别号的属性列标识不是准标识符列，则判断车辆身份识别号的属性列标识是否为兴趣点，如果是兴趣点则对兴趣点处的位置坐标进行局部泛化处理。
6.根据权利要求5所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，如果车辆身份识别号的属性列标识不是准标识符列，则进行以下步骤：
4.2.1在标签序列中对每一个位置点的取值个数进行统计，并取出统计个数大于等于阈值10的兴趣点坐标；
4.2.2取出的统计个数大于等于阈值10的兴趣点坐标按照统计个数的大小进行降序排列；
4.2.3按照步骤4.2.2中的排列顺序，选择统计个数最大的兴趣点坐标进行首次泛化处理；
4.2.4若首次泛化处理后的标签序列不满足泛化处理结果，跳转至步骤4.2.1，否则跳转至步骤4.2.5；
4.2.5进行迭代计算，直到所有大于等于阈值的兴趣点坐标全部完成局部泛化处理，否则跳转至步骤4.2.2；
4.3使用泛化处理对普通点的位置坐标进行全局泛化处理。
7.根据权利要求6所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，普通点指位置坐标数据中除了兴趣点之外的点。
8.根据权利要求6所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，全局泛化具体为对同一组数据一次性进行相同的泛化操作。
9.根据权利要求6所述的一种融合隐私保护的轨迹数据标签聚类方法，其特征在于，局部泛化具体为同一组数据中的不同子集进行不同的泛化操作。
技术总结