一种维持统计特征不变的跨路网位置匿名方法

摘要

本发明公开一种维持统计特征不变的跨路网位置匿名方法，首先根据目标区内的道路分布情况，提取路网进行划分得到路网区域；然后根据实际需要的保护范围和路网区域质心位置，构造满足保护要求的位置匿名候选集合；最后根据待保护路网区域与候选集合中路网区域之间的位置点数量差、质心点距离等参数的大小确定位置匿名的路网区域，通过位置交换的方式进行跨路网的位置匿名。本发明利用路网划分路网区域，在不同路网区域之间进行位置匿名，可以避免攻击者利用位置与属地关系的背景知识获取用户隐私；本发明通过位置交换的方式进行位置匿名，能够维持整体数据的统计特征不发生变化，不影响隐私保护后数据的可用性。

说明书

技术领域

本发明涉及信息安全领域，特别涉及一种空间位置大数据的隐私保护方法。

背景技术

随着GPS和基站定位等技术的发展，移动运营商可以获取大量移动用户的空间位置信息，这些位置信息通过分析和挖掘可以为政府、企业和个人提供决策服务。但是，用户在获取这些服务的过程中，也面临个人敏感信息泄露的风险。因此，如何在保护用户隐私的同时又能为用户提供高质量的数据分析与决策服务，是空间数据服务过程中必须解决的重要科学问题。

国内外学者在位置隐私保护方面已进行了许多有益的研究，包括：Meyerowitz等人提出了一个能够确保位置数据在线匿名的CacheCloak系统；Zhang等人把位置区域栅格化成敏感和非敏感区域，当移动对象进入敏感区域时，将抑制或推迟发布其位置更新；黄毅等人通过用户之间协作形成匿名组，匿名组内的用户用该组的密度中心代替真实位置来实现k-匿名的效果；Shin等人基于多边形和聚类的时空混合隐私保护机制，实现对用户位置的泛化，通过概率k匿名来评估用户的位置匿名水平。但是，现有位置隐私保护方法不能较好的满足空间数据服务的需求，尤其针对空间位置大数据，需要提出新的方法来提高隐私保护的抗攻击能力和隐私保护后数据的可用性。

发明内容

本发明的目的在于提供一种维持统计特征不变的跨路网位置匿名方法，以解决上述技术问题。本发明，首先根据目标区内的道路分布情况，提取路网进行划分得到路网区域；然后根据实际需要的保护范围和路网区域质心位置，构造满足保护要求的位置匿名候选集合；最后根据待保护路网区域与候选集合中路网区域之间的位置点数量差、质心点距离等参数的大小确定位置匿名的路网区域，通过位置交换的方式进行跨路网的位置匿名。

为了实现上述目的，本发明采用如下技术方案：

一种维持统计特征不变的跨路网位置匿名方法，包括以下步骤：

A.提取路网对目标区进行划分形成路网区域：根据目标区域内的道路分布情况，提取路网实现对目标区域的划分，并获取路网区域包含的位置点数量、路网区域质心位置特征；

B.构造满足保护要求的位置匿名候选集合：根据实际需要的保护区范围和路网区域质心位置，将满足条件的路网区域组成待保护路网区域的候选集合，并计算待保护路网区域与候选集合中路网区域之间未匿名的位置点数量差、质心点距离参数；

C.维持统计特征不变的跨路网位置匿名：根据位置点数量差、质心点距离的大小，在候选集合中确定位置匿名的路网区域，通过位置交换的方式对待保护路网区域中的位置点进行跨路网的匿名。

进一步的，步骤A具体包括以下步骤：

设目标区G左下角和右上角的坐标分别为(X_MIN，Y_MIN)、(X_MAX，Y_MAX)，以此范围在开放API上面截取目标区地图图片，通过颜色空间变换、腐蚀、膨胀、边界提取、包含关系判断操作，得到划分后的路网区域R₁、R₂、…、R_i、…、R_M；

设路网区域R_i包含的N_i个位置点分别为通过下式计算得到路网区域R_i的质心(X_i,Y_i)：

其中，i＝1,2,……,M。

进一步的，步骤A具体包括以下步骤：

设目标区G左下角和右上角的坐标分别为(X_MIN，Y_MIN)、(X_MAX，Y_MAX)，以此范围在开放API上面截取目标区地图图片，将其转换到HSV颜色空间；设表示道路的线条颜色值为Color，Color颜色范围的上界为Color_max＝{H_max,S_max,V_max}，下界为Color_min＝{H_min,S_min,V_min}；设像素点pixel的HSV颜色值为Color_pixel＝{h,s,v},如果Color_min≤Color_pixel≤Color_max则color_pixel＝0,否则color_pixel＝1；由所有像素点的color_pixel得到二值图像Figure_s；

扫描二值图像Figure_s的每一个像素pixel，用3×3的结构元素与其覆盖的二值图像Figure_s中的部分做“与”运算，如果运算结果为则结果图像的该像素为1，否则为0，重复两次上述操作；扫描二值图像Figure_s的每一个像素pixel，用3×3的结构元素与其覆盖的二值图像Figure_s中的做“与”运算，如果运算结果为则结果图像的该像素为0，否则为1；经过两次腐蚀操作和一次膨胀操作后的结果图像为路网图Figure_R；

对路网图像Figure_R执行边界提取操作后得到划分后的路网区域R₁、R₂、…、R_i、…、R_M，用点集(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)表示路网区域R_i的边界；对于任一位置点(x,y),分别计算它与(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)之间的空间距离，并求出其中最小的空间距离d_min，若d_min＝0则点(x,y)属于路网区域R_i；若d_min≠0，则以(x,y)为圆心、d_min为半径做圆Circle，分别计算(x,y)与(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)构成的直线与圆Circle的e个交点，设为o₁、o₂、o₃……、o_e,通过矢量计算公式o_jo_j+1＝o_j+1-o_j(j＝1,2,……e)得到矢量和若矢量和为0,则点(x,y)属于路网区域R_i；

设路网区域R_i包含的N_i个位置点分别为通过下式计算得到路网区域R_i的质心(X_i,Y_i)：

其中，i＝1,2,……,M。

进一步的，步骤B具体包括以下步骤：

设实际需要的保护区边长为d，对于待保护的路网区域R_i，如果路网区域R_p，p≠i的质心(X_p,Y_p)满足条件且则将R_p加入R_i的候选交换集合S(R_i)，即：

且

设待保护路网区域R_i与候选集合中某一路网区域R_p中未匿名的位置点数分别为n_i、n_p，R_i与R_p之间未匿名的位置点数量差为Δn(R_i,R_p)，质心点之间的距离为D(R_i,R_p)，则有：

Δn(R_i,R_p)＝|n_i-n_p|(3)

进一步的，步骤C具体包括以下步骤：

比较所有的Δn(R_i,R_p)将未匿名位置点数量差最小的路网区域记为R_q，若未匿名位置点数量差最小的路网区域不唯一，则分别计算它们质心点与R_i质心点之间的距离，选择距离值最小的路网区域记为R_q；

若n_i≤n_q，则从R_q中随机选出n_i个点和R_i中所有的n_i个点进行位置互换，且使n_q＝Δn(R_i,R_p)；若n_i>n_q，则将R_q中所有点和R_i中随机选出的n_i个随机点进行位置互换，且使n_i＝Δn(R_i,R_p)。

进一步的，重复步骤B和步骤C直至目标区中的所有路网区域处理完毕。

相对于现有技术，本发明具有以下有益效果：

本发明利用路网划分路网区域，在不同路网区域之间进行位置匿名，可以避免攻击者利用位置与属地关系的背景知识获取用户隐私；本发明通过位置交换的方式进行位置匿名，能够维持整体数据的统计特征不发生变化，不影响隐私保护后数据的可用性。

具体实施方式

下面对本发明的实施过程做进一步详细说明。

本发明一种维持统计特征不变的跨路网位置匿名方法，包括以下步骤：

步骤A.提取路网对目标区进行划分形成路网区域：根据目标区域内的道路分布情况，提取路网实现对目标区域的划分，并获取路网区域包含的位置点数量、路网区域质心位置特征。

设目标区域左下角和右上角的经纬度分别为(X_MIN，Y_MIN)、(X_MAX，Y_MAX)，根据实际应用需求(例如：比例尺为1：1000)，以此范围在开放API上面截取目标区域地图图片，并将其转换到HSV颜色空间。设表示道路的线条颜色值为Color，Color颜色范围的上界为Color_max＝{H_max,S_max,V_max}，下界为Color_min＝{H_min,S_min,V_min}；设像素点pixel的HSV颜色值为Color_pixel＝{h,s,v},如果Color_min≤Color_pixel≤Color_max则color_pixel＝0,否则color_pixel＝1；由所有像素点的color_pixel得到二值图像Figure_s。

扫描二值图像Figure_s的每一个像素pixel，用3×3的结构元素与其覆盖的二值图像Figure_s中的部分做“与”运算，如果运算结果为则结果图像的该像素为1，否则为0，重复两次上述操作。扫描二值图像Figure_s的每一个像素pixel，用3×3的结构元素与其覆盖的二值图像Figure_s中的做“与”运算，如果运算结果为则结果图像的该像素为0，否则为1。经过两次腐蚀操作和一次膨胀操作后的结果图像即为路网图Figure_R。

对路网图像Figure_R执行边界提取操作后得到划分后的路网区域R₁、R₂、…、R_i、…、R_M，用点集(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)表示路网区域R_i的边界。对于任一位置点(x,y),分别计算它与(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)之间的空间距离，并求出其中最小的空间距离d_min，若d_min＝0则点(x,y)属于路网区域R_i；若d_min≠0，则以(x,y)为圆心、d_min为半径做圆Circle，分别计算(x,y)与(x_i1,y_i1),(x_i2,y_i2),(x_i3,y_i3),……(x_ie,y_ie)构成的直线与圆Circle的e个交点，设为o₁、o₂、o₃……、o_e,通过矢量计算公式o_jo_j+1＝o_j+1-o_j(j＝1,2,……e)得到矢量和若矢量和为0,则点(x,y)属于路网区域R_i。

设路网区域R_i(i＝1,2,……,M)包含的N_i个位置点分别为通过下式计算得到路网区域R_i的质心(X_i,Y_i)：

步骤B.构造满足保护要求的位置匿名候选集合：根据实际需要的保护区范围和路网区域质心位置，将满足条件的路网区域组成待保护路网区域的候选集合，并计算待保护路网区域与候选集合中路网区域之间未匿名的位置点数量差、质心点距离参数。

对于待保护的路网区域R_i，设其对应的保护范围是以为顶点组成的矩形区域，其中d为根据实际需要设定的保护区边长。如果路网区域R_p(p≠i)的质心(X_p,Y_p)处在路网区域R_i对应的保护范围内，即(X_p,Y_p)同时满足和则将路网区域R_p作为R_i的一个候选交换对象，并将所有满足条件的候选交换对象组成一个待保护路网区域R_i的候选交换集合S(R_i)，即：

且

设待保护路网区域R_i中未匿名的位置点数为n_i，候选交换集合中某一路网区域R_p中未匿名的位置点数为n_p，则n_i的初始值为N_i，n_p的初始值为N_p；设待保护路网区域R_i中未匿名的位置点数量与候选交换集合中某一路网区域R_p中未匿名的位置点数量差为Δn(R_i,R_p)，则有：

Δn(R_i,R_p)＝|n_i-n_p|(3)

待保护路网区域R_i的质心点与候选交换集合中某一路网区域R_p的质心点之间的距离设为D(R_i,R_p)，则有：

步骤C.维持统计特征不变的跨路网位置匿名：根据位置点数量差、质心点距离的大小，在候选集合中确定位置匿名的路网区域，通过位置交换的方式对待保护路网区域中的位置进行跨路网的匿名。

对于候选交换集合S(R_i)中所有的R_p，分别计算它们与待保护路网区域R_i之间的Δn(R_i,R_p)，并将未匿名位置点数量差Δn(R_i,R_p)值最小的路网区域记为R_q；若未匿名位置点数量差最小的路网区域不唯一，则分别计算这些路网区域它们的质心点与R_i的质心点之间的距离D(R_i,R_p)，并将距离D(R_i,R_p)值最小的路网区域记为R_q；路网区域R_q将与待保护路网区域R_i进行位置交换完成匿名。

对于待保护路网区域R_i和路网区域R_q，若n_i≤n_q，则说明待保护路网区域R_i中的所有位置点都能够进行匿名，即从R_q中随机选出n_i个点和R_i中所有的n_i个点进行位置互换，互换后R_i的未匿名位置点数量n_i＝0，而路网区域R_q中未匿名位置点数量n_q＝Δn(R_i,R_q)；若n_i>n_q，则说明待保护路网区域R_i中的位置点不能全部都进行匿名，则从路网区域R_i中随机选出n_i个位置点和路网区域R_q中所有点进行位置互换，互换后路网区域R_i中未匿名位置点数量n_i＝Δn(R_i,R_p)。

重复步骤B和步骤C直至目标区中的所有路网区域处理完毕。