第 1 章 绪论
1.1 研究背景及意义
随着信息技术尤其是大数据、云计算以及 AI 等产业的快速发展，有关个人的数字信息的收集也在呈爆发增长趋势，一些企业或个人通过对这些收集到的海量数据进行分析和挖掘可以发现大量隐藏在数据背后的有价值的信息。决策树[1]是一种使用非常广泛的机器学习算法，其通过对数据集进行无参化建模来分析和挖掘数据集中一些有用的信息，从而能够指导企业和组织的决策和发展。决策树之所以受欢迎，不仅是因为其较高的精度和较少的参数[2]，而且也因为从基于属性的样本中提取的分类规则具有更好的可解释性[3-4]，这是一个在商业数据挖掘背景下特别吸引人的特性[5-6]。决策树在很多领域都有着广泛的应用，包括模式识别[7]，图像处理[8]，信息检索[9]等。
作为一种非常流行的机器学习算法，决策树长期以来都是国内外研究的热点，这期间涌现出了许多经典的决策树算法，主要包括基于贪婪方法的决策树（如 ID3[10]、CART[11]、C4.5[12]）和随机决策树（如 RDT[13]、ET[14]、PERT[15]、RS[16]）等。以自上而下方式构建的决策树本文称之为贪婪决策树，其策略是针对短期情况做出最佳决策而不考虑长期结果。贪婪决策树利用这种启发式的策略，在树的每个节点中最大化杂质度量函数以决定选择哪个属性将节点拆分成子节点。目前已经有许多不同的杂质度量函数被提出，如信息增益[17]、增益比[18]和基尼系数[19]等，它们都旨在尽可能地使子节点中的样本类别分的更开。通过随机选择属性来拆分节点从而构建的决策树本文称之为随机决策树。对于随机决策树，往往单棵树的效果会非常差，只有多棵随机决策树集成后才能表现良好。
2018 年，Mu 等人[20]提出了一种贪婪决策树算法——基于皮尔逊相关系数的决策树，该算法将皮尔逊相关系数作为一种新的杂质度量函数，通过计算树的每个节点中条件属性与决策属性之间的皮尔逊相关系数，然后选择皮尔逊相关系数最大的属性作为最佳分裂属性来对节点进行拆分，从而递归地构建决策树。这种算法可以在不对连续属性进行离散化处理的情况下同时处理离散属性和连续属性。
.......................
1.2 研究现状及分析
本节将根据基于贪婪方法和基于随机方法的这两类决策树算法来分别介绍其相关的差分隐私保护方法的研究现状。
1.2.1 基于随机方法的差分隐私决策树
在基于随机方法的决策树算法中，具有代表性的算法主要有 RDT 和 ET，这类算法通常首先在构建决策树的过程中不依赖训练数据地随机选择属性来对每个节点进行拆分，然后在树构建完成之后使用训练数据来更新每个节点中的统计信息，记录其中不同的类计数。由于这类算法往往在单棵树的时候效果很差，所以一般会集成多棵树来提高算法的性能。针对这类随机决策树算法，已经有一些基于差分隐私的保护方案相继提出，例如Jagannathan 等人[33]在 2012 年提出了一种基于随机决策树的差分隐私决策树集成算法，该算法集成多棵 RDT 随机决策树并将隐私预算平均分配给这些决策树，通过对每棵树的叶子节点添加拉普拉斯噪声来保护算法的隐私。但是当集成的随机决策树超过一定数量时，算法的预测精度就会明显降低，这是因为分配给每棵树的隐私预算会很少，导致添加到每棵树的噪声量会增大，从而降低了预测精度。另外该算法在数据量有限的情况下不能产生良好的精度。因此在 2013 年 Jagannathan 等人[34]又提出了一种半监督的差分隐私随机森林，他们通过结合公共数据使原始数据得到增强，从而使得该算法即使在数据量相当有限的情况下也能产生良好的预测精度。随后，Fletcher 和 Islam[35]在 2015 年提出了一种差分隐私决策森林算法，该算法使用信噪比理论来自动调整参数，保证了添加到结果中的噪声量不会超过叶节点中真实类计数。不过该算法的缺点是不能处理连续属性并且由于冗余的查询操作消耗了过多的隐私预算，使得算法预测精度不高。所以针对这个问题，他们在 2017 年又提出了一种差分隐私决策森林算法[36]，该算法通过构建一组随机决策树，避免了对原始数据集的一些冗余的查询操作（除了在叶节点中对多数类计数），最大限度地减少了所需查询的数量，节省了部分隐私预算。该算法利用指数机制仅输出类标签本身以降低查询的敏感度，同时也减少了为保护隐私而必须添加的噪声量。此外该算法还提出了“平滑敏感度”这一概念，即通过考虑特定数据的查询敏感度而不是全局的最坏情况下的敏感度来达到降低噪声量的目的，从而提高预测精度。
以上方法虽然在满足差分隐私的情况下都有不错的运行效率和预测精度，但是在单棵树的情况下就会表现得很糟糕，并且大多都不能处理连续属性。
............................
第 2 章 隐私保护模型以及基于皮尔逊相关系数的决策树算法概述
2.1 隐私保护模型
现如今随着信息技术应用的不断普及和深入，各种信息系统存储并积累了大量的数据（如医院的患者诊断信息、电子商务企业的顾客购物信息等），有关人的数据挖掘信息变得越来越重要。然而，在对这些数据进行处理的过程中容易对用户的隐私造成威胁。因此，这就需要一定的隐私保护模型来确保数据在处理的过程中攻击者无法推测或者获取用户的个人敏感信息。
2.1.1 基于分组的隐私保护模型
研究人员提出了各种保护隐私的方法并设计了许多度量标准来评估这些方法的隐私级别，这些方法及其隐私标准定义为隐私模型。为了在数据收集阶段保护隐私，隐私模型会被放置在决策者和数据提供者之间，以在提交给不受信任的决策者之前处理数据中的个人敏感信息。为了在数据发布和分析阶段保护隐私，隐私模型会被放置在决策者和公共用户之间。
在基于分组的隐私保护模型中最受欢迎的是 k-匿名，它要求一个个体不能从总数小于k 的组里面被识别出来。此外，还有许多其他隐私模型，例如 l-多样性，t-近似等。然而，这些模型的弱点在于它们很容易受到不受控制的背景知识的破坏。例如，当数据集被泛化直至最低程度满足 k-匿名的要求时，攻击者可能利用此最小等价组来反转匿名性并推测出原始数据集的可能版本。此过程称为最小攻击，这是记录链接攻击中的一种特殊方法。此外也存在另外一些对抗传统隐私模型的攻击方法，例如组合攻击、前景知识攻击等。组合攻击是指攻击者从其他渠道（例如 Web，公共记录或领域知识等）获取背景知识，然后他们结合这些丰富且现实的背景知识来从已发布的数据集中恶意推断出个人的隐私信息。与背景知识攻击相反，前景知识攻击是指当数据集没有进行匿名时，攻击者可以从已发布的数据集中生成模式，从而利用这些模式来获取个人隐私信息。
..............................
2.2 基于皮尔逊相关系数的决策树算法
在本小节中将详细介绍基于皮尔逊相关系数的决策树算法（以下简称 PCCDT）的具体过程和实现原理。特征评估是开发用于训练决策树的贪婪算法的基本问题，它确定决策树构造中的分裂规则。Mu 等人[20]在 2018 年提出了一个基于皮尔逊相关系数的决策树 PCCDT，该决策树使用皮尔逊相关系数作为杂质度量函数来测量属性的质量并获得最佳分裂属性。在统计学中，皮尔逊相关系数[47]是一种广泛用于测量两个变量之间线性相关性的方法。它基于数据的协方差矩阵来评估两个向量之间关系的强度。
一个是用来确定何时停止树的生长并标记叶节点的停止规则。另一个是在叶节点中分配类标签的标签规则。在 PCCDT 算法中采用了三个停止规则。第一个停止规则是如果节点中所有的样本都属于同一类别，则在该节点中停止树的生长。第二个是如果节点中样本的比例小于 s ，则树的生长将停止，这可以有效地避免过度分割问题。最后一个停止规则是不能通过最佳分裂点将样本划分为两个子集，这意味着皮尔逊相关系数不变。关于标签规则，本文将当前节点中样本数量最大的类别标记为叶节点的类标签，这在大多数决策树中都广泛地使用。根据上述规则，PCCDT 可以按照自顶向下递归的方式来进行构建，它遵循基于贪婪方法的决策树的策略。
软件工程论文怎么写
第 3 章 基于皮尔逊相关系数的差分隐私决策树方法 ......................... 12
3.1 隐私问题描述 ............................................. 12
3.2 Diff-PCCDT 算法总框架 .................................. 13
3.3 关键机制 ...................................... 15
第 4 章 基于皮尔逊相关系数的差分隐私并行决策树方法 .............................. 23
4.1 隐私问题描述 ............................ 23
4.2 DiffMR-PCCDT 算法总框架 ...................................... 25
4.3 关键机制 .................................. 26
第 5 章 总结与展望 ...................................... 31
5.1 总结 .............................................. 31
5.2 展望 ......................................... 31
第 4 章 基于皮尔逊相关系数的差分隐私并行决策树方法
4.1 隐私问题描述由本文 2.3 节可知，MR-PCCDT 算法主要是在非并行算法 PCCDT 基础上，在其分裂阶段采用了 MapReduce 并行框架使之能够有效处理大型数据集，因此也存在着如本文 3.1节中所描述的隐私问题。现在假设 MR-PCCDT 算法运行在一个云计算场景中，如图 4.1 所示。在这个场景中由三个主要的实体组成：（1）数据所有者，其拥有一个大型数据集，并允许机构或个人对数据集运行 MR-PCCDT 算法进行查询，以获得有用的结果。（2）服务提供商，其提供整个计算环境，允许数据所有者分享和上传数据同时允许机构或个人对这些数据运行 MR-PCCDT 算法进行查询。（3）机构或个人，其想对分享和上传的数据运行MR-PCCDT 算法进行查询以实现他们的目标，他们可能会恶意推断数据以查找一些他们想要了解的隐私信息。
由于该服务是在云计算环境中实现的，所以有多个计算节点可以存储所有者的数据并运行 MR-PCCDT 算法以提供给机构或个人查询使用，这其中就可能涉及到数据所有者的敏感数据。假如有一些机构或个人中存在攻击者，他们获取了 MR-PCCDT 算法在运行过程中得到的一些关键数据如属性之间的皮尔逊相关系数和叶节点中真实的类计数，那么他们就可能结合自己的背景知识来推断出数据所有者的一些个人隐私信息。因此，云计算场景下的 MR-PCCDT 算法同样存在着严重的隐私泄露风险。
软件工程论文参考
第 5 章 总结与展望
5.1 总结
近些年随着信息技术和大数据产业的飞速发展，有关个人的数字信息的收集也在快速增长。一些企业或个人对收集到的个人数据通过分析和挖掘能够发现大量有价值的信息。基于皮尔逊相关系数的决策树（PCCDT）作为一种新型的决策树算法在很多领域得到了广泛的应用，如模式识别，机器学习，信息检索等。然而，当数据集中包含敏感的个人信息（如病人的诊断信息，顾客的购物信息等）时，利用基于皮尔逊相关系数的决策树对数据集进行挖掘分析则可能产生隐私泄露问题，从而对用户的隐私安全造成威胁。本文在基于皮尔逊相关系数的决策树算法的基础之上提出了一种基于皮尔逊相关系数的差分隐私决策树算法，在满足差分隐私的前提下保证了算法的有效性和可用性。本文的主体工作如下：
（1）考虑到基于皮尔逊相关系数的决策树算法存在的隐私泄露问题，本文指出了该算法在分裂阶段和分类阶段可能会面临隐私风险，并且针对性地提出了基于皮尔逊相关系数的差分隐私决策树方法。该方法主要是由指数挑选机制与叶节点扰动机制两个方面组成，本文详细介绍了这两种机制并对算法的隐私预算分配和隐私安全性进行了严格的分析。在实验阶段，本文还将提出的算法与经典的差分隐私决策树算法 DiffP-ID3 进行了对比分析，结果证明本文所提出的算法在满足差分隐私要求的同时也兼顾了有效性和可用性。
（2）虽然本文提出的算法 Diff-PCCDT 在中小型数据集上表现良好，但是由于时间复杂度和存储容量的限制，其很难在大型数据集上运行并产生结果。因此本文提出了一种MapReduce 框架下基于皮尔逊相关系数的差分隐私并行决策树算法（DiffMR-PCCDT），通过将并行计算框架 MapReduce 嵌入到决策树中的每个中间节点来提高算法的运行效率。另外也分析了算法的隐私预算分配和隐私安全性，证明了算法满足差分隐私。最后本文将DiffMR-PCCDT 算法和 Diff-PCCDT 算法在几个中大型数据集上进行了比较，结果表明DiffMR-PCCDT 算法拥有良好的运行效率以及测试精度。
参考文献（略）