随着数据分析和发布等应用需求的出现和发展,如何保护隐私数据和防止敏感信息泄露成为当前面临的重大挑战。基于k-匿名或者划分的隐私保护方法,只适应特定背景知识下的攻击而存在严重的局限性。差分隐私作为一种新出现的隐私保护框架,能够防范攻击者在拥有任意背景知识情况下的攻击并提供有力的保护。对隐私数据的发布和分析均有可能导致个人敏感信息的泄露,发布的数据要能够防止数据收集者与攻击者的攻击；而所设计的分析方法,则要在给出分析结果时防止泄露个人隐私信息。针对上述两种应用场景,本节对差分隐私保护领域已有的研究成果进行了总结,对该技术的基本原理和特征进行了阐述,重点对当前的数据发布和分析工作进行了概述和总结。

(一)差分隐私保护框架

差分隐私下数据保护框架通常有两种：交互式框架和非交互式框架。

交互式的差分隐私保护框架也可以称为在线查询框架,其基本结构如图8-1所示。当数据分析者通过查询接口提交查询Q时,数据拥有者会根据查询需求,设计满足差分隐私的查询算法,经过差分隐私算法过滤后,把结果Q′返回给用户。分析者提交的查询通常包含一定的语义约束,这会使得返回结果的可用性较低。数据拥有者常采用后置处理技术对噪声结果进行求精处理。由于交互式框架只允许数据分析者通过查询接口提交查询,查询数目决定着该框架的误差和性能,若提交查询的数目超过某个上界,隐私预算ε会被耗尽,该框架则不能满足差分隐私。该框架所支持的查询通常包括聚集查询、批量查询以及提交的数据挖掘任务等。

图8-1　交互式框架

非交互式框架也称为离线发布框架,其基本结构如图8-2所示。数据拥有者通过差分隐私发布算法来发布数据库的相关统计信息。数据分析者向发布数据库提交查询或者挖掘任务Q并得到噪声结果Q′。非交互式发布框架下的主要研究是如何设计高效的发布算法,该类算法既要满足差分隐私,又要具有高的可用性。目前,数据拥有者采用数据压缩、数据转换与采样过滤等技术对原始数据进行处理以达到缩减发布误差和查询误差的目的。此外,数据发布过程中,合理的隐私预算分配策略也是保证差分隐私成立的关键。

图8-2　非交互式框架

以下主要根据非交互式框架介绍数据发布方法的两种策略。

(1)发布策略1

先对原始数据或者原始数据的统计信息添加噪声,然后对加过噪声的数据采用规划策略(如二次规划、凸规划等)进行优化,最后发布优化结果：这类方法的隐私代价通常比较大。该策略的基本流程如图8-3所示。

图8-3　策略1发布流程(www.daowen.com)

(2)发布策略2

先转换或者压缩原始数据,再对转换后的数据添加噪声。这类方法主要针对减少发布误差,以及提高数据可用性等。尽管这种策略响应查询的精度较高,然而数据转换或者压缩会带来原始数据的信息缺损。该策略的基本思想如图8-4所示。

图8-4　策略2发布流程

(二)数据发布方法

基于上述两类发布策略,已有的发布技术主要分为两类：基于直方图的发布方法和基于划分的发布方法。

直方图使用分箱技术近似描述数据统计信息,将一个比较大的数据集按照某属性划分成不相交的桶,每个桶由一个数字表示其特征。直方图可以分成等宽直方图、V-优化直方图等多种类型。

基于划分的发布方法通常基于发布策略2,考虑如何设计支持数据划分的索引结构,并依据索引结构发布隐私数据。常用的索引划分结构分为基于树结构的划分与基于网格结构的划分。这两种划分均要考虑是否在原始的基础数据上划分,如果是在基础数据上进行的划分,则称为数据依赖的划分,该类划分可能会使得划分结构自身泄露数据隐私；如果是在查询空间上的划分,而没有涉及基础数据,则称为数据独立的划分。

(三)数据分析方法

数据分析的目的在于从数据中抽取或者学习到有价值的模型和规则。模型与规则中的敏感信息可能导致个人隐私泄露,所以隐私保护的数据挖掘和机器学习得到广泛关注。

(1)基于频繁模式挖掘的分析方法。频繁模式挖掘是数据分析主要技术之一,其目的是找出频繁出现在数据集中的模式。然而频繁模式本身的内容以及相应的频度有可能泄露用户隐私信息。基于差分隐私的模式挖掘主要是为了保护模式的频度不被披露。

(2)基于分类的分析方法。分类技术在数据预测分析中起着关键作用,在决策树算法中,叶节点表示一个类。结合差分隐私与决策树的代表方法分别是Su LQ-based ID3、DiffP-C4.5以及DiffGen。这三种方法在生成分类器时类似于ID3,主要是考虑决策树各个节点上分割属性的选择问题。

(3)基于聚类的分析方法。聚类同样是数据分析的主要技术,它是把数据对象划分成多个簇的过程,而在聚类过程中数据隐私可能被泄露,如均值、中心点与中值等。满足差分隐私的扣均值聚簇中心发布方法Pk-means结合了采样与聚集技术,该方法给出了聚类敏感性的度量方法以及聚类误差的下界。此外,在k均值聚类过程中,隐私预算ε的设置也非常关键,包括两种分配方法。一是迭代次数n已知情况下,每一轮聚类预算为ε/n；二是迭代次数不知道的情况下,每次所分配的预算为上次剩余预算的一半。

(4)回归分析方法。常用的回归分析方法包括逻辑斯谛回归与线性回归。回归分析通常有两类函数,一是预测函数,二是目标函数,或者称为风险函数。无论是线性回归还是逻辑斯谛回归分析,通常归结为目标函数的最优化问题。该问题的形式化描述如下：给定的训练数据集D={t1,t2,…,tn}有n个元组,每个元组包含d+1个属性——xi,…,xd,y,其中xi∈Rn,y∈{0,1},或者y∈[-1,1]。元组t1=[(xi,yi)z,少r],其中xi表示(x1,x2,…,xd)向量。假设p(xi)表示预测函数,该函数通常由向量xi与其相应的权重向量w*的参数化形式表示。