一种考虑实用性的多属性数据去隐私方法

摘要

本发明公开了一种考虑实用性的多属性数据去隐私方法，包括以下步骤：步骤1：导入预处理后的多属性数据；步骤2：根据属性描述定义必要属性和敏感属性，设定必要属性的预分组规则，根据属性特征定义必要属性的顺序；步骤3：构建隐私暴露风险树，分别将步骤2中的属性顺序和预分组规则作为隐私暴露风险树的层级顺序和每层级分支产生的依据；步骤4：根据敏感属性在隐私暴露风险树的节点和边上编码风险测量结果信息；本发明可以灵活地从几种常用的语法匿名化和差异隐私模型中选择适合的方法来解决隐私问题，以满足对不同数据的多种隐私需求；其中隐私暴露风险树利用树结构特有的优势，实现了对多维集合的空间紧凑设计。

说明书

技术领域

本发明涉及信息隐藏技术领域，特别涉及一种考虑实用性的多属性数据去隐私方法。

背景技术

数据所有者在展示数据或者将数据公开用于分析之前，需要考虑该数据是否涉及到个体的敏感信息。若涉及相关问题，那么数据需要预先进行去隐私处理。

现有技术中关方法主要包括以下三个方面：第一方面隐私保护模型，在隐私保护领域，很多自动方法已经被提出，其中语义匿名模型和差分隐私模型是两类最常见的隐私保护模型。其中k-anonymity(L.Sweeney. k-anonymity:A model for protectingprivacy.International Journal of Uncertainty,Fuzziness and Knowledge-BasedSystems,10(05):557–570, 2002.)、l-diversity(A.Machanavajjhala,D.Kifer,J.Gehrke,and M. Venkitasubramaniam.l-diversity:Privacy beyond k-anonymity.ACMTransactions on Knowledge Discovery from Data,1(1):3,2007.)和t-closeness(N.Li,T.Li,and S.Venkatasubramanian.t-closeness:Privacy beyond k-anonymityandl-diversity.InProceedingsoftheIEEE23rdInternational Conference onData Engineering,pp.106–115.IEEE,2007.)是三种最经典的语义匿名模型。它们分别从等价类的数据项，等价类中敏感属性具有代表性值的数量以及等价类中敏感属性的分布和全体集合中敏感属性分布的差异三个方面来衡量当前数据集是否到达了隐私保护标准并同过合并集合，混淆等价类的方式来提供隐私保护。差分隐私模型则是通过给相关数据的属性值添加适量的噪音来保护数据中的敏感信息。遗憾的是，这些自动方法都存在一些缺陷，比如语义匿名模型难以处理高维数据，差分隐私方法会损失数据的相关性等等。

第二方面是隐私和实用性的取舍，一些语义匿名方法通过合并集合组距来反应信息损失的程度。基于上述标准，Loukides(J.Xu,W.Wang,J.Pei, X.Wang,B.Shi,and A.W.-C.Fu.Utility-based anonymization using local recoding.In Proceedings of the12th ACM SIGKDD international conference on Knowledge discovery and datamining,pp.785–790,2006.)和Shao(Data utility and privacy protection trade-offin k-anonymisation.In Proceedings of the international workshop on Privacyand anonymity in information society, pp.36–45.ACM,2008.)通过划分和确定最优聚类来解决权衡：先列出了参数设置和最优要求的可行选择，之后通过隐私和效用的曲线选择适当的组合。此外，Rastogi等人提出了αβ匿名算法(V.Rastogi,D.Suciu,and S.Hong.The boundary between privacy and utility in data publishing.InProceedings of the 33rd international conference on Very large data bases,pp.531–542.VLDB Endowment,2007.)，它将隐私和实用性视为有界对手。关于差分隐私模型，关于信息流动的信息理论框架(M.S.Alvim,M.E. Andr′es,K.Chatzikokolakis,P.Degano,and C.Palamidessi.Differential privacy:on the trade-off between utility andinformation leakage.In Proceedings of the International Workshop on FormalAspects in Security and Trust,pp.39–54.Springer,2011.)可以量化信息泄漏和效用。Ghosh等人 (A.Ghosh,T.Roughgarden,and M.Sundararajan.Universally utility-maximizing privacy mechanisms.SIAM Journal on Computing, 41(6):1673–1693,2012.)还通过添加随机拉普拉斯噪声来满足差分隐私约束，同时尽可能地最小化信息丢失来构建几何机制。

然而，以上这些方法都是针对模型本身提出的实用性维护方法，并没有真正从分析的角度去全面考虑数据的特征。

第三方面是关于隐私的可视化研究，这部分内容主要分为通过理论研究和相关系统。在理论方面，Van提出了一个关于数据映射对用户感知影响的模型(J.J.Van Wijk.Thevalue of visualization.In Proceedings of the Visualization.IEEE,pp.79–86,2005.)。Dasgupta和Kosara(A.Dasgupta and R.Kosara.Adaptive privacy-preservingvisualization using parallel coordinates.Proceedings of the IEEE transactionson visualization and computer graphics,17(12):2241–2248,2011.)认为只有视觉聚类和数据聚类才能通过增加不确定性提供隐私保证，而且数据聚类方法可以以实用性降低为代价来实现隐私保护。相关系统主要是Chou等人(J.-K.Chou,C. Bryan,and K.-L.Ma.Privacy preserving visualization for social network data with ontologyinformation.2017.)(J.-K.Chou,Y.Wang,and K.-L.Ma. Privacy preserving eventsequence data visualization using a sankey diagram-like representation.InProceedings of the SIGGRAPH ASIA Symposium on Visualization,2016.)提出的针对轨迹数据和图数据的去隐私数据处理系统。

但是上述的已有的隐私保护方法没有向用户提供足够的实用性反馈。

发明内容

本发明提供了一种考虑实用性的多属性数据去隐私方法，帮助用户实时衡量实用性损失，并可以灵活地处理和发现数据中涉及的隐私问题。

一种考虑实用性的多属性数据去隐私方法，包括以下步骤：

步骤1：导入预处理后的多属性数据；

步骤2：根据属性描述定义必要属性和敏感属性，设定必要属性的预分组规则，根据属性特征定义必要属性的顺序；必要属性是指需要经过处理并展示的数据；敏感属性是指涉及隐私的属性。此处的预分组规则以及必要属性的顺序可以进行人为定义，为了更好地实现本发明，优选的，将敏感属性放在后层，将分组较少的属性放在前层。这样做可以在处理过程中观察到更多信息，并使处理过程更加灵活，一般的，结合常识设定必要属性的预分组规则。

步骤3：构建隐私暴露风险树，分别将步骤2中的属性顺序和预分组规则作为隐私暴露风险树的层级顺序和每层级分支产生的依据；具体构建方式如下，树的每个节点代表一个集合，在第i层的节点所代表的集合只由第1,2,…,i层所对应的属性值所限制。同时，为了简化布局，每一层将节点根据该层对应的属性值，将子节点合并为聚类节点。两种节点可以同时显示在视图中。

步骤4：根据敏感属性在隐私暴露风险树的节点和边上编码风险测量结果信息；

风险测量结果信息包括：边编码风险增量和节点编码风险值，根据三个经典语义匿名模型(k-anonymity,l-diversity,t-closeness)的思想来测量每个集合的隐私暴露风险。三个的测量方法具体为：k对应集合中的数据项数量；l对应集合中数据项的敏感属性值的数量；t对应敏感属性分布和全体属性分布的差异。若有敏感属性A₁,A₂,…,A_n，则依次产生1+2n个风险测量指标，将它排序为：k,l(A₁),t(A₁),l(A₂),t(A₂),…,l(A_n),t(A_n)，分别通过三种不同颜色的透明度将它们以条带的形式编码在节点上。由于子节点数量较多，空间较小，只使用灰色的透明度编码全部风险测量值中的最大值。除此之外，在边上也用灰色的透明度编码了父节点和子节点之间风险增量。

优选的，还包括步骤5：在隐私暴露风险树上进行基于语义匿名方法的属性值合并。拖动节点合并时，两个节点所代表的两个集合中所有数据相应属性的(精确)值被替换为同一个模糊范围，这个范围包括两个集合中所有原有的属性值。合并后的数据将精确的属性值匿名化，从而保护了隐私。

优选的，还包括步骤6：在隐私暴露风险树上进行基于差分隐私的对特定集合的特定属性添加不同大小的噪音。对选定集合中数据的响应属性值基于差分隐私的噪声。噪音增加了数据的不确定度，从而令观察数据的人难以确定实际属性值。

优选的，还包括以下步骤：

步骤7：根据必要属性展开二维矩阵，二维矩阵中右上角每个格子显示原始数据的相应联合分布，对角线显示表示相应属性分布的统计图，左下角每个格子显示处理后数据的相应联合分布。统计图可以采用柱状图、折线图等等。该二维矩阵与隐私暴露风险树联动，用户在基于隐私暴露风险树进行数据处理的过程中可以通过二维矩阵的图形分布和量化数值实时地、全面地了解当前的实用性变化。

优选的，步骤7中，原始数据的联合分布的类型包括：类别型-类别型原始图：通过点的半径编码同类数据项数量；类别型-数值型原始图：将点变形为矩形，通过矩形沿类别轴方向的长度编码同类数据项数量；数值型-数值型原始图：散点图。

优选的，步骤7中，处理后数据的联合分布的类型包括：基于语义匿名方法处理结果：矩阵图；基于差分隐私方法处理结果：散点图；综合处理结果：矩阵图和散点图的混合图表。

优选的，还包括以下步骤：

步骤8：实时对每个必要属性计算实用性指标，并在二维矩阵中进行显示和更新。

具体方法如下：将每个数据处理前后的属性值分别设为f_D(x)和f_D’(x)。如果该属性为数值型属性，分别对原始数据和处理后数据的集合中该属性的值进行升序排序，假设有m个数据项，f_D(x)在原始数据集合中排第i个，>D’(x)在处理后数据中排第j个，则计算：

u(f_D(x),f_D’(x))＝1-|i-j|/(m-1)；

对于没有层级信息的类别型数据，若f_D(x)＝f_D’(x)，则u(f_D(x),fD’(x))>

对于有层级信息的类别型数据，计算：

u(f_D(x),f_D’(x))＝level(f_D(x),f_D’(x))/H；

其中level(f_D(x),f_D’(x))为f_D(x)和f_D’(x)共同祖先的层级，H为整棵树的层级。

最后根据u(f_D(x),f_D’(x))计算每个属性的实用性指标：

U(f_D(x),f_D’(x))＝Σu(f_D(x),f_D’(x))/n。

在每次数据处理后更新实用性矩阵，并显示当前每个属性的实用性指标值，及前一次操作造成的指标值大小变动。

提供更加直观的分布比较方法，优选的，还包括以下步骤：

步骤9：分别将步骤7中原始数据和处理后数据的联合分布统一到同一粒度，若数据的原有粒度不一致，则将数据在其原有粒度中还原成均匀分布，再根据新定义的粒度进行数据项数量统计；

将上述统一粒度的两张图表做差，将每一格子中的处理后数据的数据项数量减去原始数据的数据项数量得到一个差值，该值的大小从正到零到负分别映射到以白色为中心的一对对比色颜色渐变上。颜色的深浅和分布可以清晰地向用户传达数据中二维联合分布的具体变化信息。

本发明的有益效果：

本发明的考虑实用性的多属性数据去隐私方法，可以灵活地从几种常用的语法匿名化和差异隐私模型中选择适合的方法来解决隐私问题，以满足对不同数据的多种隐私需求；其中隐私暴露风险树利用树结构特有的优势，实现了对多维集合的空间紧凑设计；同时，分枝可聚合功能和聚合节点的设计可帮助用户高效浏览多维数据，树结构边上的增量编码更可以辅助快速定位隐私问题源头；而实用性矩阵提供了以往自动算法无法给出的视觉反馈，这对实用性维护很有意义。

附图说明

图1为本发明方法构造隐私暴露风险树的过程示意图。

图2为本发明方法构造的隐私暴露风险树的示意图。

图3为本发明方法构造的实用性矩阵的示意图。

图4为本发明方法通过语义匿名方法处理数据后将处理结果与原始数据比较的结果。

图5为本发明方法通过差分隐私方法处理数据后将处理结果与原始数据比较的结果。

图6为本发明方法中将有主要问题的分支收起可以更直观地观察其他部分的隐私暴露风险时的示意图。

图7为本发明方法中将合并两个分支后，可以与图2对比看出，大部分隐私暴露风险都被解决了。

具体实施方式

本实施例中，使用的数据集是2015年美国怀俄明州普查时收集的公开微数据样本数据(PUMS)的部分数据集。此数据集中有许多以家庭为单位的信息。

本实施例的考虑实用性的多属性数据去隐私方法包括以下步骤：

步骤1：导入预处理后的多属性数据，从数据集中提取以下四个属性：“保险支出”(每年)，“家庭收入”(过去一年中)，“儿童”(家庭中18岁以下的人员数量)，以及“老人”(家庭中65岁以上的人员数量)；其中家庭收入被视为需要保护的敏感属性。

步骤2：根据属性描述定义必要属性和敏感属性，设定必要属性的预分组规则，根据属性特征定义必要属性的顺序；结合常识设定必要属性的预分组规则，将类别型数据的属性值直接作为分组依据；对于数值型属性，根据属性含义和数据的分位点定义具体的分组规则；顺序为将敏感属性放在后层，将分组少的属性放在前层。

步骤3：构建隐私暴露风险树，分别将步骤2中的属性顺序和预分组规则作为隐私暴露风险树的层级顺序和每层级分支产生的依据；如图1和 2所示，构造隐私暴露风险树，其中边代表父子节点之间的包含关系，它的颜色深浅编码了分类后的风险增量；子节点指当前层及以上的全部属性关联形成的子集；聚类节点指只按当前属性分类得到的子集。因此，在第二层以后，聚类节点往往包含多个子节点。

通过观察图2所示的隐私暴露风险树，可以快速发现：有多于一位老年人的家庭更容易有隐私暴露风险。

步骤4：根据敏感属性在隐私暴露风险树的节点和边上编码风险测量结果信息；如图2所示，根据三个经典语义匿名模型(k-anonymity, l-diversity,t-closeness)的思想来测量每个集合的隐私暴露风险。三个的测量方法具体为：

k对应集合中的数据项数量；

l对应集合中数据项的敏感属性值的数量；

t对应敏感属性分布和全体属性分布的差异。

现有敏感属性家庭收入，则产生3个风险测量指标，将它排序为：k,l(家庭收入),t(家庭收入)，分别通过三种不同颜色的透明度将它们以条带的形式编码在节点上。由于子节点数量较多，空间较小，只使用灰色的透明度编码全部风险测量值中的最大值。除此之外，在边上也用灰色的透明度编码了父节点和子节点之间风险增量。

步骤5：在隐私暴露风险树上进行基于语义匿名方法的属性值合并。收起两个最有问题的分支：有一位老人的分支和有两位以上老人的分支时，如图6所示，整棵树的颜色都褪去了，也就是说大多数问题与这两个属性值相关。为了解决这个问题，选择是将具有隐私问题的分支合并，图7显示了合并后的隐私暴露风险树。之后发现第三层的后面两个节点残留了一些风险，在第一次尝试中，继续选择合并操作。然而，当通过实用性矩阵观察原来的相关性时，发现之前的图表信息被很大程度上影响了，如图7 所示。

步骤6：在隐私暴露风险树上进行基于差分隐私的对特定集合的特定属性添加不同大小的噪音。

步骤7：根据必要属性展开二维矩阵，二维矩阵中右上角每个格子显示原始数据的相应联合分布，对角线显示表示相应属性分布的统计图，左下角每个格子显示处理后数据的相应联合分布。如图3所示，二维矩阵为实用性矩阵，其中对角线为各个属性的一维分布图；对角线上方为原始图，其中，儿童-老人为类别型-类别型原始图；保险支出-家庭收入为数值型- 数值型原始图；其余皆为数值型-类别型原始图；对角线下方为基于语义匿名方法处理结果图，其中老人和儿童两个属性因为没有被处理，所以仍然显示原始图。本实施例中的每个维度上的预聚类是比较粗糙的。但是我们仍可以很快看出，家庭收入与保险费用正相关。与没有孩子的家庭(大部分家庭每年花费500-900元)相比，有孩子的家庭(其中大部分家庭每年花费900-1300元)往往愿意购买更多的保险。

步骤8：实时对每个必要属性计算实用性指标，并在二维矩阵中进行显示和更新。如图3的最顶部数据可知。

步骤9：分别将步骤7中原始数据和处理后数据的联合分布统一到同一粒度。因数据的原有粒度不一致(处理后的数据粒度较粗)，将数据在其原有粒度中还原成均匀分布，再根据新定义的粒度进行数据项数量统计；

将上述统一粒度的两张图表做差，将每一格子中的处理后数据的数据项数量减去原始数据的数据项数量得到一个差值，该值的大小从正到零到负分别映射到以白色为中心的一对对比色颜色渐变上。

图4是使用上述方案观察得到的结果：黑框框出的部分为我们希望保留的分布特征，但是从图中可以看出，这部分颜色很深，发生了很大的变化。因此，我们回退一步，转而采用差分隐私技术。在图5中，可以看到，这次框出的部分颜色较浅，因此实用性损失已经被控制在更可接受的水平。