第 ２７ 卷第 ８ 期 ２０１０ 年 ８ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ 隐 私 保 护 的 分 布 式 决 策 树 分 类 算 法 的 研 究 申艳光， 邵　慧， 张永强 （ 河北工程大学 信息与电气工程学院， 河北 邯郸 ０５６０３８ ） Ｖｏｌ．２７ Ｎｏ．８ Ａｕｇ．２０１０ 倡 摘　要： 针对分布式决策树构造过程中的隐私保护问题，引入安全多方计算方法设计了可以保护隐私的分布式 Ｃ４．５ 决策树分类算法。 该算法适用于数据集垂直分布和水平分布两种情况，同时提出了一种新的隐私保护程 度的度量方法。 实验结果证明设计的隐私保护分布式决策树分类算法不仅很好地保护了原始数据不泄露，同时 保持了较高的分类精度。 关键词： 分布式数据挖掘； 隐私保护； 安全多方计算； Ｃ４．５ 决策树算法； 垂直分布； 水平分布 中图分类号： ＴＰ３１１　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１０）０８唱３０７０唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１０．０８．０６９ Ｒｅｓｅａｒｃｈ ｏｎ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄｉｓｔｒｉｂｕｔｅｄ ｄｅｃｉｓｉｏｎ唱ｔｒｅｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ Abstract： Ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｏｆ ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｄｅｃｉｓｉｏｎ唱ｔｒｅｅ ｂｕｉｌｄｉｎｇ ｐｒｏｃｅｓｓ， ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｄ ｔｈｅ ｓｅｃｕｒｅ ｍｕｌｔｉ唱ｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎ ｍｅｔｈｏｄ ａｎｄ ｄｅｓｉｇｎｅｄ ａｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄｉｓｔｒｉｂｕｔｅｄ Ｃ４．５ ａｌｇｏｒｉｔｈｍ ，ｗｈｉｃｈ ｗａｓ ａｐｐｌｉｃａｂｌｅ ｔｏ ｔｈｅ ｖｅｒｔｉｃａｌｌｙ ａｎｄ ｈｏｒｉｚｏｎｔａｌｌｙ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａｓｅｔ， ａｎｄ ａｌｓｏ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ｃｏｍｐｕｔａｔｉｏｎ ｍｅｔｈｏｄ ｏｆ ｔｈｅ ｄｅｇｒｅｅ ｏｆ ｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ａｌｇｏｒｉｔｈｍ ｃａｎ ｗｅｌｌ ｐｒｏｔｅｃｔ ｔｈｅ ｏｒｉｇｉｎａｌ ｄａｔａ ｆｒｏｍ ｒｅｖｅａｌｉｎｇ， ａｎｄ ｋｅｅｐ ｈｉｇｈ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｒｒｅｃｔ ａｃｃｕｒａｃｙ． Key words： ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａ ｍｉｎｉｎｇ； ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ； ｓｅｃｕｒｅ ｍｕｌｔｉ唱ｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎ； Ｃ４．５ ｄｅｃｉｓｉｏｎ唱ｔｒｅｅ ａｌｇｏｒｉｔｈｍ； ｖｅｒ唱 ｔｉｃａｌｌｙ ｄｉｓｔｒｉｂｕｔｅｄ； ｈｏｒｉｚｏｎｔａｌｌｙ ｄｉｓｔｒｉｂｕｔｅｄ （School of Information Science ＆ Electrical Engineering， Hebei University of Engineering， Handan Hebei ０５６０３８， China） ＳＨＥＮ Ｙａｎ唱ｇｕａｎｇ， ＳＨＡＯ Ｈｕｉ， ＺＨＡＮＧ Ｙｏｎｇ唱ｑｉａｎｇ 本文假设数据集 S 垂直（ 水平） 分布于 A 和 B 两方，分别 Ｂｅｇｉｎ （１） 创建根节点 T； 垂直划分：A 计算 Sa 中每一属性的信息增益比例，B 计算 Sb 中每 　　收稿日期： ２０１０唱０１唱０１； 修回日期： ２０１０唱０２唱２９　　基金项目： 河北省教育厅科学研究计划项目（２００９４２１）；河北省自然科学基金资助项目 （Ｆ２００８０００７５２） 　　作者简介： 申艳光（１９７０唱），女，河北邯郸人，教授，硕士，主要研究方向为数据挖掘和信息安全（ｓｈｅｎｙａｎｇｕａｎｇ＠ｙａｈｏｏ．ｃｏｍ）；邵慧（１９８３唱），女， 山东泰安人，硕士，主要研究方向为数据挖掘；张永强（１９６６唱），男，教授，主要研究方向为软件工程． ［１］ ［２］ 首次提出了隐私保护 和 Ｌｉｎｄｅｌｌ 等人 　　数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随 机的数据集中提取隐含的、事先未知的、但又潜在有用的信息 和知识的过程。 与此同时，数据挖掘也面临着许多问题的挑 战。 其中，数据挖掘的隐私和信息安全问题尤其得到关注。 ２０００ 年 Ａｇｒａｗａｌ 等人 的数据挖掘概念，引起了学术界和产业界的广泛关注，并吸引 了一批学者致力于该领域的研究。 从此，隐私保护的数据挖掘 成为了研究重点。 近年来，随着 ＷＷＷ 的普及应用，Ｉｎｔｅｒｎｅｔ 成 为最大的分布式数据源，在数据挖掘过程中，经常需要来自不 同站点数据库中的数据，如不同银行希望从共享数据中得到欺 诈行为的模式；政府机构需要与航天部门合作，挖掘恐怖行为 的踪迹，在这类情况下，数据常常分布在不同的地点，这些机构 在进行协同工作完成全局性的数据挖掘时，往往希望在不共享 自己精确数据的前提下，获取准确的挖掘规则结果。 因此，隐 私保护的分布式数据挖掘成为了一个全新的研究方向。 本文主要考虑数据挖掘者为两方的情况，数据集水平分布 时，应用安全多方和协议和安全 xｌｎ（x） 协议构造具有隐私保 护效果的决策树分类器；数据集垂直分布时，应用标量积协议 和安全 xｌｎ（x）协议构造具有隐私保护效果的决策树分类器。 1　问题描述 为 Sa 和 Sb，并且数据集 S ＝Sa∪Sb，则： ａ）如果数据集 S 垂直划分：则 A 和 B 两方有相同的记录 数，用 N 代表总的记录数；每一条记录被分为两部分，Sa 包含 一部分属性，Sb 则包含另一部分属性，用 n 表示所有属性个 数；A 和 B 共享属性集及类标号属性，用 m 表示类的个数。 ｂ）如果数据集 S 水平划分：则 A 和 B 两方拥有不同的记 录数，但每条记录是完整的，A 和 B 共享属性集以及类标号属 性，用 m 表示类的个数。 2　隐私保护的分布式决策树算法研究 2畅1　隐私保护的 PPC4.5 决策树算法 Ｃ４．５ 算法由 Ｑｕｉｎｌａｎ Ｊ Ｒ 在１９９３ 年提出，是ＩＤ３ 算法的改 进。 Ｃ４．５ 算法在 ＩＤ３ 的基础上增加了对连续型属性和属性值 空缺情况的处理，对树剪枝也有了较成熟的方法。 与 ＩＤ３ 不 同，Ｃ４．５ 采用基于信息增益比例（ＧａｉｎＲａｔｉｏ） 的方法选择测试 属性。 本文以Ｃ４．５ 算法 为基础，设计了保护隐私的ＰＰＣ４．５ （S，＾A＿ａｔｔｒｉｂｕｔｅ）算法，文中假设 ＾A 表示当前节点，＾A＿ａｔｔｒｉｂｕｔｅ 表 示当前测试属性集，S ＝Sa∪Sb 表示当前数据库。 ［３］ 

申艳光，等：隐私保护的分布式决策树分类算法的研究 ［４］ 增益比例的属性； 第 ８ 期 一属性的信息增益比例，用信息增益比例最大的节点做根节点； 水平划分：A、B 需要合作才能计算信息增益比例。 （２）ｉｆ S 都属于同一类 C，则返回 T 为叶节点，标记为类 C； 垂直划分：由于 A、B 双方共 同分享 类标号，要确 定 S 是否 属于同 一类 C，只需考察 Sa（Sb） 记录是否属于同一类 Ca（ Cb），若都属于同一 类，则返回叶节点，用 Ca（Cb） 标记。 水平划分：分别考察 Sa 中的记录是否属于同一类 Ca，Sb 中的记录 是否属于同一类 Cb。 若都属于同一类，再考察 Ca 是否等于 Cb。 运用 可以确定 Ca 是否等于 Cb。 若 Ca ＝Cb，则 Ｙａｏ 的安全两方比较协议 返回叶节点，用 Ca 或 Cb 标记。 （３）ｉｆ ＾A＿ａｔｔｒｉｂｕｔｅ 为空 ＯＲ S 中所剩 的样本 数少于 某给定 值，则返 回 T 为叶节点，用 S 中最频繁的类标记； 垂直划分：由于 A、B 两方共同分享所有属性的名称，则 ＾A＿ａｔｔｒｉｂｕｔｅ 是否为空它们都可知。 当 ＾A＿ａｔｔｒｉｂｕｔｅ 为空时，需 要找出 S 中最 频繁的 类 Ci，又因为 A、B 共享类标号，所以只需扫描 Sa（ Sb） 一个数据库统计 其最频繁的类即可。 水平划分：A 统计 Sa 中每个类的记录数｜Sa（ Ci） ｜，B 统计 Sb 中每 个类的记录 数 ｜Sb （ Ci） ｜。 运 用 Ｙａｏ 的 安 全 两 方 比 较 协 议， A 输 入 （ ｜Sa（C１） ｜，…，｜Sa（Cm） ｜），B 输入（ ｜Sb（ C１） ｜，…，｜Sb（ Cm） ｜），计算 输出为 i ＝ｍａｘ｛（ ｜Sa（Ci） ｜＋｜Sb（Ci） ｜）｝。 （４） 创建队列 Q，根节点 T 入队列 Q； （５）ｗｈｉｌｅ 队列不为空 （６） ｛ （７） 从队列中取出第一个节点 ＾A； （８）ｆｏｒ ｅａｃｈ＾A＿ａｔｔｒｉｂｕｔｅ 中的属性计算信息增益比例 ＧａｉｎＲａｔｉｏ； （９）T 的最佳分裂属性 ｔｅｓｔ＿ａｔｔｒｉｂｕｔｅ ＝＾A＿ａｔｔｒｉｂｕｔｅ 中 具有最 高信息 （１０）ｉｆ 分裂属性为连续型 ｔｈｅｎ 找到该属性的分割阈值； （１１） 用信息增益比例最大的那个属性把节点 ＾A 分为 k 个子集 ＾A１， （１２）ｆｏｒ ｅａｃｈ 由节点 ＾A 长出的新叶节点 ＾A｛ ｉｆ 该叶节点对应的样本子集只有惟一的一种决策 类别，则 将该叶 节点标记为该类别； ｅｌｓｅ 将该 节点入 队列 Q，在 该叶节 点上执 行 ＰＰＣ４．５（ S′，＾A＿ ａｔｔｒｉ唱 ｂｕｔｅ） 对它继续分裂； （１３）　　　 ｝ （１４） ｝ （１５） 计算每个节点的分类错误，进行树剪枝。 ｅｎｄ 2畅2　节点最佳分裂属性的确定方法 为了确定每一节点的最佳分裂属性，需要计算每一节点所 有属性的信息增益比例，将值最大的属性作为节点的分裂属 性，数据集垂直划分和水平划分的最佳分裂属性的确定方法不 同，分开来讨论。 2畅2畅1　数据集垂直划分的最佳分裂属性的确定方法 设 S 代表当前节点的数据集，R 表示计算当前节点属性的 信息增益比例所需要的数据集，会出现两种情况：ａ）R 中的属 性和当前测试属性集 ＾A＿ａｔｔｒｉｂｕｔｅ 属于一个数据集，则其中任意 一方均可以单独地计算属性的信息增益比例；ｂ）R 中的属性和 当前测试属性集 ＾A＿ａｔｔｒｉｂｕｔｅ 不属于同一个数据集，此时一方需 要联合另一方的数据才能计算信息增益比例。 下面主要讨论 情况 ｂ）的信息增益比例计算方法。 把 R 分为两个子集 Ra 和 Rb，设 Ra 是从 Sa 获取的数据 集，Rb 是从 Sb 获取的数据集。 Ea 表示仅与 Sa 中有关的属性 ＾A２，…，＾Ak； ·１７０３· 　　　 组成的逻辑表达式，Eb 表示仅与 Sb 中有关的属性组成的逻辑 表达式。 A 扫描 Sa 生成一个 N 维向量 Va，如果第 i 条记录满 足 Ea，则 Va（i） ＝１，否则 Va（i） ＝０。 A 可以自己计算出向量 Va 的值，同理，B 也可以自己计算出向量 Vb 的值。 V（i） ＝Va（i）∧ Vb（i） 表示同时满足条件 Ea 和 Eb 的记录。 设 Vi 是 一 个 N 维 向 量， 如 果 第 t 条 记 录 属 于 类 i 则 Vi（t） ＝１，否则 Vi（t） ＝０。 A 和 B 都可以独自计算出向量 Vi 的 值。 标量积 VaVb ＝∑N i ＝１Va（i）倡Vb（i） 表示同时满足条件 Ea 和 Eb 的非零项的记录个数；＾Pi ＝Va· （Vb∧Vi） ＝（Va∧Vi）· Vb 表示数据集 S 中属于类 i 的记录数。 s j ＝１ s１j ＋s２j ＋… ＋smj j ＝１PjI（s１j，s２j，…，smj） １）计算 E（S，＾A＿ａｔｔｒｉｂｕｔｅ） E（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝－∑v I（s１j，s２j，…，smj） ＝－∑v 其中：①Pj ＝Va· Vb｜S｜，｜S｜＝∑m i ＝１＾Pi； ②I（S１j，S２j，…，Smj） ＝－∑m i ＝１Pijｌｏｇ２（pij） ＝ Va· Vbｌｏｇ２（ ＾Pi ＾Pi －∑m Va· Vb i ＝１ ２）计算 Ｇａｉｎ（S，＾A＿ａｔｔｒｉｂｕｔｅ） Ｇａｉｎ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝I（S１，S２，…，Sm） －E（S，＾A＿ａｔｔｒｉｂｕｔｅ） ） 。 ＾Pi。 其中 I（s１，s２，…，sm）不用联合，一方可以单独完成这部分的计 算。 将１）计算出的熵的值代入此式即可求出信息增益的值。 将上式计算出的信息增益的值代入此式即可求出信息增 ３）计算 ＧａｉｎＲａｔｉｏ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＧａｉｎＲａｔｉｏ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝Ｇａｉｎ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＳｐｌｉｔI（S，＾A＿ａｔｔｒｉｂｕｔｅ） j ＝１Pjｌｏｇ２（pj）且 Pj ＝Va· Vb｜S｜，｜S｜＝∑m 其中 ＳｐｌｉｔI（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝－∑v 益比例的值。 重复上面的计算过程直到求出此节点所有属性 的信息增益比例值，选取值最大的属性分裂节点，循环直到决 策树构造完成。 2畅2畅2　数据集水平划分的最佳分裂属性的确定方法 假设｜Sa（Ci） ｜表示当前节点取自 Sa 的属于类 i 的记录 数，｜Sb（Ci） ｜表示当前节点取自 Sb 的属于 类 i 的 记录数； ｜Sa（ａｔｔｒj，Ci）｜表示当前节点取自 Sa 的属性值等于 j 的分支中 属于类 i 的记录数，｜Sb（ａｔｔｒj，Ci） ｜表示当前节点取自 Sb 的属 性值等于 j 的分支中属于类 i 的记录数。 i ＝１ Ｓｕｍ（∑m １）计算期望信息 I（s１，s２，…，sm） I（s１，s２，…，sm） ＝－∑m 其中 pi ＝ Ｓｕｍ（｜Sa（Ci）｜，｜Sb（Ci）｜） i ＝１｜Sb（Ci）｜）。 i ＝１piｌｏｇ２（pi） i ＝１｜Sa（Ci）｜，∑m ２）计算熵 E（S，＾A＿ａｔｔｒｉｂｕｔｅ） s１j ＋s２j ＋… ＋smj E（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝－∑v j ＝１ I（s１j，s２j，…，smj） ＝－∑v j ＝１PjI（s１j，s２j，…，smj） i ＝１｜Sb（ａｔｔｒj，Ci） ｜） i ＝１｜Sa（ａｔｔｒj，Ci） ｜，∑m Ｓｕｍ（∑m i ＝１｜Sa（Ci） ｜，∑m i ＝１｜Sb（Ci） ｜） 其中：①Pj ＝Ｓｕｍ（∑m s ； 

计 算 机 应 用 研 究 　 ·２７０３· ② I （ s１j， s２j， …， smj ） ＝ － ∑m Ｓｕｍ（ ｜Sa（ａｔｔｒ，Ci） ｜，｜Sb（ａｔｔｒj，Ci） ｜） ； Ｓｕｍ（∑m i ＝１｜Sa（ａｔｔｒj，Ci） ｜，∑m i ＝１｜Sb（ａｔｔｒj，Ci）） ３）计算信息增益 Ｇａｉｎ（S，＾A＿ ａｔｔｒｉｂｕｔｅ） Ｇａｉｎ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝I（s１，s２，…，sm） ＝－E（S，＾A＿ａｔｔｒｉｂｕｔｅ） i ＝１ pij ｌｏｇ２ （ pij ） pij ＝ 将上面两个公式计算得出的值代入此公式即可求得信息 第 ２７ 卷 增益的值４）计算信息增益比例 ＧａｉｎＲａｔｉｏ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＧａｉｎＲａｔｉｏ（A） ＝Ｇａｉｎ（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＳｐｌｉｔI（S，＾A＿ａｔｔｒｉｂｕｔｅ） 其中：ＳｐｌｉｔI（S，＾A＿ａｔｔｒｉｂｕｔｅ） ＝－∑v j ＝１pjｌｏｇ２（pj） 且 Pj ＝Ｓｕｍ（∑m i ＝１｜Sa（ａｔｔｒj，Ci）｜，∑m i ＝１｜Sb（ａｔｔｒj，Ci）｜） Ｓｕｍ（∑m i ＝１｜Sa（Ci）｜，∑m i ＝１｜Sb（Ci）｜） 数据集垂直分布时，应用标量积协议 ［５］ 议 ［６］ 协议 即可求出的 Va· Vb 值，并且 Va· Vb 的结果被分为两部分 xa 和 xb，即 Va· Vb ＝ xa ＋xb，A 保管 xa，B 保管 xb，这样可保证 A 无法知道 Vb 的内容， B 无法知道 Va 的内容，从而保护了各自的隐私。 应用 x ｌｎ（x） 可得 ｌｎ（xa ＋xb） ＝ua ＋ub，ua、ub 分别由 A、B 保管，所以 （xa ＋xb）ｌｎ（xa ＋xb） ＝（ xa ＋xb）（ ua ＋ub） ＝xaua ＋xbub ＋ xbua ＋xaub。 其中 xbua 的计算结果分为两部分 ya 和 yb，分别由 A、B 各自保管，同理，xaub 的计算结果也分为两部分 wa 和 wb， 分别由 A、B 各自保管。 A 可以计算 Za ＝xaua ＋ya ＋wa，B 可以 计算 Zb ＝xbub ＋yb ＋wb，则（xa ＋xb）ｌｎ（xa ＋xb） ＝Za ＋Zb，结果 仍是分为两部分 Za 和 Zb，分别由 A、B 各自保管，从而保护了 各自的 隐 私。 同 理， 数 据 集 水 平 分 布 时， 先 应 用 安 全 和 协 ［７］，然后再应用 xｌｎ（x） 协议即可实现双方的隐私保护。 3　隐私保护程度的度量方法 出的程度。 现有的隐私度量一般用“ 披露风险”（ｄｉｓｃｌｏｓｕｒｅ ｒｉｓｋ）［８］ 来描述，披露风险表示攻击者根据所发布的数据和其 他背景知识（ｂａｃｋｇｒｏｕｎｄ ｋｎｏｗｌｅｄｇｅ），可能披露隐私的概率。 披 露风险只给出了隐私度量的定性说明，没有给出一个定量计算 方法。 因此，本文提出了一种决策树分类挖掘隐私保护程度的 度量方法： 隐私保护程度是指防止原始数据或其隐含的知识被推导 隐私保护程度 ＝ＰＰＣ４．５ 算法获得的分类规则数倡 Wｐｐｃ４．５ ／Ｃ４．５ 获得的分类规则数倡Wｃ４．５ 其中：将决策树的叶子节点数定义为获得的分类规则数；分类 正确率指正确分类的记录数占总的记录数的比率，那么权重 Wｐｐｃ４．５ 指ＰＰＣ４．５ 算法的分类正确率，权重 Wｃ４．５ 指Ｃ４．５ 算法的 分类正确率。 4　实验结果分析 本文在 Ｗｅｋａ 平台上封装实现了隐私保护的 ＰＰＣ４．５ 算 法，如图１ 所示。 为了验证算法的可行性，这里选取了 Ｗｅｋａ 自带的２ 个数据集（ｓｏｙｂｅａｎ 和 ｉｒｉｓ） 和 ＵＣＩ 机器学习数据库 的 ３ 个数据集（ａｄｕｌｔ、ｃａｒ 和 ｃｒｅｄｉｔ） 进行了实验验证。 实 ［９］ 验结果如图２ ～４ 所示。 图２ 是 ＰＰＣ４．５ 和 Ｃ４．５ 算法的分类正确率的对比。 中 图３ 是对于５ 个不同的数据集 ＰＰＣ４．５ 和 Ｃ４．５ 算法获得 图４ 显示了ＰＰＣ４．５ 算法对不同数据集的隐私保护程度，根 的规则数的比较。 据隐私保护程度的计算公式和图２、３ 的数据可以得到图４。 本实验采用１０ 次交叉验证法验证生成决策树的分类精 度。 将本文提出的隐私保护分布式决策树分类算法的分类准 确率与传统算法对比可以看出，该算法的分类准确程度较传统 算法有所下降，但是下降在６％之内，仍然可以接受，隐私保护 程度在最差的情况下也可以达到７６％以上。 由实验结果可以 看出，本文提出的算法较好地保护了原始数据不泄露，同时保 持了较高的分类精度。 5　结束语 详细介绍了最佳分裂节点的确定方法和信息增益比例的计算 文将密码学中的安全多方计算方法与数据挖掘方法相结合设 现有的一些数据挖掘算法并没有考虑到数据隐私问题，本 计实现了具有隐私保护功能的分布式 Ｃ４．５ 决策树分类算法， 方法，同时提出了一种决策树挖掘隐私保护程度的度量方法。 本文只考虑了对隐私数据的隐藏，但未涉及规则的隐藏，并且 未考虑隐私保护的个性化需求，对规则的隐私保护以及个性化 隐私保护将是未来进一步研究的内容。 参考文献： ［１］ ＡＧＲＡＷＡＬ Ｒ， ＳＲＩＫＡＮＴ Ｒ．Ｐｒｉｖａｃｙ唱ｐｒｅｓｅｒｖｉｎｇ ｄａｔａ ｍｉｎｉｎｇ［Ｃ］ ／／ Ｐｒｏｃ ｏｆ ＡＣＭ ＳＩＧＭＯＤ ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ．２０００：４３９唱４５０． ［２］ ＬＩＮＤＥＬＬ Ｙ， ＰＩＮＫＡＳ Ｂ．Ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄａｔａ ｍｉｎｉｎｇ ［Ｊ］．Jour唱 nal of Cryptology，２００２（１５）：１７７唱２０６． ［３］ ＱＵＩＮＬＡＮ Ｒ Ｊ．Ｃ４．５： Ｐｒｏｇｒａｍｓ ｆｏｒ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ［Ｍ］．Ｓａｎ Ｍａ唱 ｔｅｏ， ＣＡ： Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒ，１９９３． ［４］ ＹＡＯ Ａ Ｃ．Ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｓｅｃｕｒｅ ｃｏｍｐｕｔａｔｉｏｎｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２３ｒｄ Ａｎｎｕａｌ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ．１９８２． ［５］ ＤＵ Ｗｅｎ唱ｌｉａｎｇ，ＺＨＡＮ Ｚｈｉ唱ｊｕｎ．Ｂｕｉｌｄｉｎｇ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｃｌａｓｓｉｆｉｅｒ ｏｎ ｐｒｉ唱 ｖａｔｅ ｄａｔａ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｉｖａｃｙ， Ｓｅｃｕｒｉｔｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｍａｅｂａｓｈｉ Ｃｉｔｙ： Ａｕｓ唱 ｔｒａｌｉａｎ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，Ｉｎｃ，２００２． ［６］ ＰＩＮＫＡＳ Ｂ， ＬＡＢＳ Ｈ Ｐ．Ｃｒｙｐｔｏｇｒａｐｈｉｃ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｐｒｉｖａｃｙ ｐｒｅｓｅｒ唱 ｖｉｎｇ ｄａｔａ ｍｉｎｉｎｇ ［Ｊ］．SIGKDD Explorations，２００２，4（２）：１２唱１９． ［７］ 杨林，张霞萍，白治国，等．基于 ＳＭＣ 协议的分布式聚类分析隐私 保护的研究［Ｊ］．计算机工程与设计，２００８，29（２１）：５４２４唱５４２６． ［８］ 周水庚，李丰，陶宇飞，等．面向数据库应用的隐私保护研究综述 ［Ｊ］．计算机学报， ２００９， 32（５）：８４７唱８６１． ［９］ ＵＣＩ．Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ． ｅｄｕ／ｍｌ／ｄａｔａｓｅｔｓ．ｈｔｍｌ．