基于差分隐私的决策树发布技术研究与应用

发布时间：2017-09-11 14:32

1 绪论

1.1 研究背景与意义
随着各种移动应用的普及和快速发展，各种企业搜集了大量的用户数据，例如用户的位置信息，搜索记录，商品交易数据等。通过对搜集到的数据进行挖掘和分析建模，可以帮助企业更好的决策，同时改善产品的用户体验，提供更精确的服务。大数据时代的到来，数据已经成为提升企业综合竞争力的重要资源，单一的数据源已经无法满足数据分析的需求，促进了数据共享与发布的发展。直接发布未经隐私保护算法处理的数据会导致个人隐私信息的泄露，这些数据往往包含大量的隐私信息，如就医记录、消费记录、家庭地址以及其他一些具有个体特征的数据。删除或者替换明显的标识符能够在一定程度上保护个人的隐私安全，但随着发布的数据集规模增大，各数据集之间的联系日益增多，这种简单的操作远不足以保证隐私信息的安全。数据的隐私信息保护问题最早是由 Dalenius 提出来的，他指出要保护数据库中的隐私，就要保证任何人在访问数据库的过程中都无法获取关于任意个体的确切信息[1]，虽然这一定义具有理论上的指导意义，显然它是主观的和模糊的。以这一定义为目标，学者们在后续的研究中提出了许多量化指标更明确、可操作性强的隐私保护模型和方法。近年来出现了许多基于 k-匿名[2]和划分的隐私保护方法，尽管这些方法能够保护数据的更多细节，但是均需要特殊的攻击假设和背景知识。此外，针对上述隐私保护方法，出现了一些新的攻击模型。这些新的攻击模型对上述方法的有效性提出了严峻挑战。目前，差分隐私[3-8]已经成为一种新的隐私保护模型，该模型不关心攻击者拥有多少背景知识，通过向查询或者分析结果中添加适当噪音来达到隐私保护效果。差分隐私保护可以解决数据发布带来的隐私威胁问题。在数据发布过程中实施差分隐私保护技术主要考虑两个方面的问题[9]：（1）如何保证设计的算法满足差分隐私，以确保数据隐私不被泄露；（2）如何减少噪音带来的误差，以提高数据的可用性。综上，论文研究如何在数据发布过程中，保护数据隐私特性同时保证发布数据集的有效性，对隐私保护数据发布的研究工作具有十分重要的意义。论文提出的一种数据发布技术DT-DP（decision tree data publish），一定程度上解决了隐私保护与数据效用性之间的平衡问题。
.......

1.2 基于差分隐私决策树发布技术的研究现状
数据分析一般使用公开发布数据集，从数据中抽取或学习到有意义的模型和规则，模型和规则中隐含的敏感信息往往会造成个人隐私信息的泄露，使得基于分类的隐私保护技术广泛兴起。分类技术在数据分析预测中起着非常重要的作用，该项技术的主要目的是，从数据中挖掘可以区分数据属性或者概念的模型，用来预测未知数据的属性。决策树是分类技术的典型代表，它是一种树形结构的分类模型，其中树内分支节点代表某属性的分类，叶子节点表示具有相同属性取值的等价类，这三种方法主要考虑如何选择决策树各个节点的分割属性，在分类器的构造上都类似于 ID3[13]方法。
........

2 相关概念介绍

大数据时代的到来，不同来源的数据存在相互关联，一旦某个数据源的个人隐私信息泄露，通过关联其他数据集将会造成严重的后果，差分隐私保护可以为数据发布过程提供良好的隐私保护机制，防止由数据发布所造成的隐私泄露问题。本章主要从技术角度介绍论文涉及到的相关概念，比如隐私保护框架，差分隐私保护相关概念，数据发布技术和决策树相关概念等。

2.1 基于差分隐私保护的数据发布框架
差分隐私保护的数据发布框架主要有以下两种：交互式隐私保护框架与非交互式隐私保护框架。交互式的差分隐私保护框架又被称为在线查询框架，其数据交互基本流程如图 2-1 所示。当数据分析师向数据查询子模块提交查询Q 时，数据拥有者事先设计满足差分隐私保护的查询算法，经过该查询算法处理后，把符合查询需求的结果'Q 返回给数据分析师。一般经过差分隐私保护算法添加噪声处理后的数据可用性较低，通常情况下分析者提交的数据查询请求通常含有一定的语义约束[14]，此时数据拥有者可以采用后置处理技术对加噪后的结果进行优化处理。交互式的框架只允许数据分析师通过提供的查询接口提交数据查询任务，查询的数目不可以太多，因为提交的查询的数目直接决定着该框架的误差和性能，当提交查询的请求数目超过某个上界值时，将会耗尽隐私预算，该框架就不能满足差分隐私保护的要求。该框架所支持的查询请求一般包括聚集查询[15]、提交的数据挖掘任务[16]和批量查询[17]等。
.......

2.2 隐私保护数据发布相关概念
近年来，如何发布具有代表性的数据，而不披露数据的隐私已成为数据库领域的研究热点。论文提出的数据发布技术基于非交互式框架，根据非交互式保护框架可知，数据发布技术一般可分为两类：（1）前置处理技术和（2）后置处理技术。为了更好理解数据发布技术，首先介绍隐私保护数据发布的定义，在详细介绍这两种数据发布技术。定义 3-1 隐私保护数据发布(Privacy-preserving data publishing, PPDP)定义。通过将隐私保护方法结合到数据发布方法当中，使原始数据既可以保护隐私信息不泄露，又可以保证有效的数据挖掘或分析任务[19-21]。（1）前置处理技术。先采用前置处理技术压缩原始数据集，再对转换后的数据添加噪音数据。此类处理方法在压缩原始数据的时候，会对原始数据带来一定程度上的信息缺损[36]。（2）后置处理技术。先对原始数据集添加噪音数据，然后根据各种优化方法处理数据，最后发布处理后的数据集[22]。此类方法通常要消耗大量的隐私保护预算。根据以上两类数据发布策略，已有的数据发布技术主要分为两类：直方图的发布方法和划分的发布方法。基于差分隐私的直方图发布技术是将数据按照不同属性划分成不相交的桶（Bin）。按照 Bin 的不同又可以分为等分直方图和V- 优化直方图等[22-25]。如下图2-3 可以看出如果直接发布图中的直方图，会导致隐私信息的泄露。如果攻击者掌握了除某人之外的其他人的患病情况，就可以根据 bin 的数量变化推断出某个人是否感染了 HBV。
.........

3 隐私数据发布过程设计........13
3.1 问题描述....13
3.2 相关决策树发布算法....15
3.3 基于差分隐私的决策树发布技术布...........18
3.4 本章小结....32
4 实验对比与分析..........33
4.1 实验环境与数据集概述..........33
4.2 评价指标....34
4.2.1 算法复杂度..........34
4.2.2 平均误差.....35
4.2.3 分类准确率...........35
4.3 实验对比....36
4.3.1 DT-DP 算法实验分析.... 36
4.3.2 对比实验分析.......38
4.4 本章小结....41
5 基于差分隐私的决策树发布算法应用.......42
5.1 商品交易数据发布应用..........42
5.2 本章小结....47

5 基于差分隐私的决策树发布算法应用

基于论文提出的隐私数据发布技术，本章内容根据真实数据需求，利用论文提出的数据发布技术进行数据发布。本章内容核心是根据数据集实例分析论文提出发布技术的隐私保护效果，发布后数据集能否进行有效的数据挖掘和数据分析任务。

5.1 商品交易数据发布应用

数据商业化分析的目的是为了从海量数据中学习到有用的规则或者模型，通过一些可视化的技术来展示数据分析的成果，这些数据的来源渠道是多种多样的，包括选民信息、医疗记录、通话记录、上网记录、购物信息等等，用户有权知道自己的数据的用途，但大部分的信息，用户并没有授权数据分析者使用该数据来分析建模的权利，这种情况下的数据分析很有可能导致隐私信息的泄露[48]。即使用户授予数据分析者正常使用的权利，在数据处理的整个生命周期中，存在着很多过程都会导致隐私信息的泄露，比如在数据的分析收集阶段，数据集被不可信的第三方服务截获，由第三方出卖给攻击者就可能导致个人隐私信息的泄露，除此之外，在数据的分析挖掘过程中也存在着聚类攻击、支持度攻击、特征攻击等等的攻击方式都会导致隐私信息的泄露[42]。一些公司或者购物网站通过搜集用户的购买记录，收藏记录等等可以获得用户的偏好等，对于预测用户的喜好，自定义向用户推荐商品具有很好的效果，如果这些网站或公司对外直接发布这些交易数据，攻击者利用这些交易记录，结合手上已有的其他数据记录，通过多个数据集的整合分析几乎可以推理出个人的所有隐私信息。由此可见对于一些公开发布的数据集采用一些隐私保护的发布算法尤为重要。本节主要是根据公开发布的商品交易数据，模拟真实发布场景，采用DT-DP 发布技术进行隐私保护发布，并利用实例证明该发布技术对于实现公开数据集的隐私保护具有很好的效果。

........

总结

大数据环境下数据的共享发布往往会导致个人信息的泄露，当需要公开发布的数据集含有各种敏感信息，利用隐私保护算法来发布数据是非常必要的。隐私数据发布的研究工作十分有意义。论文提出的基于差分隐私的决策树数据发布技术主要从三个方面展开研究：细分方案的设计、自适应分配隐私预算、等差加噪及后置优化。
（1）细分方案设计：连续属性较多时，细分方案集的规模增大，导致指数机制效率下降。论文利用权重委托的方式，用区间中点值的权重乘以整个区间的长度，代表整个区间的可用性水平参加最优细分方案的选择，该种方式极大减少了算法需要维护的决策树数量，提高了指数机制的效率。
（2）自适应分配隐私预算：已有算法均匀分配隐私预算?的方式，浪费了隐私预算，缩短了的生命周期。通过计算当前决策树的规模，自适应分配隐私预算，延长了?的使用周期，提高了隐私保护的力度。相同的隐私预算，自适应的分配方式，可以增加决策树的细分次数，，提高了决策树的分类准确率。
（3）等差加噪：论文进一步研究了基于拉普拉斯机制的异步等差加噪技术。通过添加服从等差分布的噪声，克服了现有算法噪声冗余的缺点。采用后置处理技术，根据原始数据的一致性约束条件，利用节点计数的最优无偏估计值代替加噪后的节点计数，降低噪声导致的结构误差，提高分类准确率。论文以分类准确率和隐私保护水平作为评价指标，采用标准数据集，对相关技术和算法进行了实验。实验结果验证了论文提出的基于差分隐私的决策树发布技术具有较高的隐私保护水平且数据保留较多的原始特性。将相关技术应用于真实的商品交易数据，通过实例分析了隐私数据的发布过程，验证了经过算法处理后的数据集不仅可以保护隐私，而且可以进行有效的数据挖掘和分析任务。
.........
参考文献（略）

本文编号：831273