基于隐私保护的决策树分类模型的研究

摘要

数据挖掘被广泛应用于多个领域，尤其是在如银行、电信、保险、交通、零售等商业领域。但数据挖掘也会带来一些社会问题，其中最敏感的要属隐私保护问题。因此，有必要研究如何在数据挖掘中保护信息隐私，并且建立基于隐私保护的挖掘模型，以保证在挖掘过程中敏感信息的安全。 本文主要探讨基于隐私保护的决策树分类模型的构造问题，其中决策树的生成算法采用ID3算法。该问题具体定义为：有两个不同站点，站点A和站点B，欲基于数据集共同构造决策树；站点A和站点B各自拥有数据集的一部分；在构造决策树的同时，必须保证站点A和站点B均不会泄露自己数据的具体字段信息。 根据不同的分布情况，数据集可分为：集中式数据集、水平分布数据集和垂直分布数据集。本文对上述三种数据集的保护隐私的决策树构造方法进行了描述与分析，并分别讨论了随机化方法和安全多方计算方法在保护隐私的决策树生成算法中的应用。 对于集中式数据集，应用随机化方法实现建树过程中的隐私保护。首先，采用服从均匀分布或高斯分布的随机变量对原始数据进行变换。其次，应用一种基于贝叶斯理论的重构方法对数据进行重构。最后，在重构的数据上构造决策树。对于数据集水平分布和垂直分布的情况，应用安全多方计算协议实现建树过程中的隐私保护，即参与计算的各站点分别输入保密信息，运用安全计算协议得到随机分享值。 针对垂直分布的数据集，本文提出了一种保护隐私的决策树构造方法PVID3算法。该方法与前面提到的基于垂直分布数据的保护隐私的决策树构造方法的不同之处如下： ①前者应用的安全协议为标量积协议；PVID3应用的安全协议为安全计算交集协议。 ②前者需要引入第三方服务器，且假设第三方服务器为半诚信；PVID3无需第三方服务器的参与。 ③前者要求两方站点的数据集均包含类标号属性；PVID3只要求一方站点包含类标号属性信息。 本文给出了基于PVID3算法的决策树分类模型的实现过程，并且对算法的传输开销和计算复杂度进行了分析。

目录

文摘

英文文摘

学位论文独创性声明及学位论文使用授权声明

第一章引言

1.1研究背景

1.2国内外的研究现状

1.3本文所做的工作

1.4本文的组织

第二章安全多方计算和保护隐私的数据挖掘

2.1数据挖掘概述

2.1.1数据挖掘的步骤

2.1.2预言型数据挖掘

2.1.3决策树分类

2.2安全多方计算SMC

2.3保护隐私的数据挖掘

2.3.1问题的提出

2.3.2定义

2.3.3研究的问题

2.3.4与分布式数据挖掘的区别

2.4保护隐私技术的分类

2.5小结

第三章集中式隐私数据的决策树构造

3.1问题定义

3.2采用的隐私保护方法

3.2.1离散化方法

3.2.2数值变换

3.2.3信息保护度的定义

3.3基于贝叶斯理论的数据重构方法

3.3.1重构过程

3.3.2重构算法

3.3.3迭代停止条件

3.3.4实验值

3.4三种构造决策树的方法

3.4.1构造决策树的两个步骤

3.4.2重构分布的三种时机

3.5算法评估

3.6小结

第四章水平分布隐私数据的决策树构造

4.1问题定义

4.2无隐私保护的决策树构造

4.2.1ID3算法

4.2.2计算信息熵

4.2.3无隐私保护的分布式ID3算法

4.3基于ID3 δ的保护隐私的决策树构造

4.3.1问题定义

4.3.2 ID3近似算法ID3δ

4.3.3确定分裂属性

4.3.4保护隐私的水平分布的ID3δ算法

4.3.5 Inx协议

4.3.6 xlnx协议

4.4算法传输开销分析

4.5小结

第五章保护隐私的垂直分布数据的决策树构造

5.1问题定义

5.2相关概念

5.2.1商品服务器

5.2.2标量积

5.3基于标量积协议的决策树构造

5.3.1分裂属性的确定

5.3.2保护隐私的垂直分布的ID3算法

5.3.3标量积协议

5.3.4对数协议

5.4基于安全交集计算协议的决策树构造

5.4.1问题定义

5.4.2划分数据集

5.4.3确定分裂属性

5.4.4交换加密

5.4.5安全计算交集协议

5.4.6基于垂直分布的隐私数据的ID3算法PVID3

5.5小结

第六章PVID3的实现与性能分析

6.1 PVID3的各函数描述

6.1.1判断属性集是否为空函数

6.1.2设置条件约束函数

6.1.3统计树节点对应的数据集信息函数

6.1.4判断数据集S中所有记录是否属于同一类函数

6.1.5计算信息熵函数

6.1.6选择分裂属性函数

6.2 PVID3算法

6.3安全性分析

6.3.1 PVID3各函数的安全性分析

6.3.2 PVID3算法的安全性分析

6.4传输开销与计算复杂度

6.5小结

第七章总结与展望

参考文献

致谢

攻读硕士学位期间参加的项目及发表的学术论文目录