维普资讯 http://www.cqvip.com 第３Ｏ卷第８期 计 算 机 学 报 ＶｏＩ．３Ｏ Ｎｏ．８ Ａｕｇ．２００７ ２００７年８月 ＣＨＩＮＥＳＥ ＪＯＵＲＮＡＬ ＯＦ ＣＯＭＰＵＴＥＲＳ 朴素贝叶斯分类中的隐私保护方法研究 张 鹏” 唐世渭 北京 １０００３５） （中国电信股份有限公司北京研究院（北京大学信息科学技术学院北京 １００８７１） 摘要数据挖掘中的隐私保护方法，试图在不精确访问原始数据详细信息的条件下，挖掘出准确的模式与规则． 围绕着分类挖掘中的隐私保护问题展开研究，给出了一种基于数据处理和特征重构的朴素贝叶斯分类中的隐私保护 方法．分别提出了一种针对枚举类型的隐私数据处理与特征重构方法——扩展的部分隐藏随机化回答（Ｅｘｔｅｎｄｅｄ Ｒａｎｄｏｍｉｚｅｄ Ｒｅｓｐｏｎｓｅ ｗｉｔｈ Ｐａｒｔｉａｌ Ｈｉｄｉｎｇ，ＥＲＲＰＨ）方法和一种针对数值类型的隐私数据处理与特征重构方 法——转换的随机化回答（Ｔｒａｎｓｆｏｒｍｉｎｇ Ｒａｎｄｏｍｉｚｅｄ Ｒｅｓｐｏｎｓｅ，ＴＲＲ）方法，并在此基础上实现了一个完整的隐私 保护的朴素贝叶斯分类算法．理论分析和实验结果均表明：朴素贝叶斯分类中基于ＥＲＲＰＨ和ＴＲＲ的隐私保护方 法具有很好的隐私性、准确性、高效性和适用性． 关键词数据挖掘；隐私保护；朴素贝叶斯分类；随机处理；特征重构 ＴＰ３１１ 中图法分类号Ｐｒｉｖａｃｙ Ｐｒｅｓｅｒｖｉｎｇ Ｎａｉｖｅ Ｂａｙｅｓ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ＺＨＡＮＧ Ｐｅｎｇ”ＴＡＮＧ Ｓｈｉ～Ｗｅｉ （Ｂｅｉｊｉｎｇ Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ，Ｃｈｉｎａ Ｔｅｌｅｃｏｍ Ｃｏｒｐｏｒａｔｉｏｎ Ｌｉｍｉｔｅｄ，Ｂｅｉｊｉｎｇ １０００３５） （Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｐｅｋｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００８７１） Ａｂｓｔｒａｃｔ Ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄａｔａ ｍｉｎｉｎｇ ｉｓ ｔｏ ｄｉｓｃｏｖｅｒ ａｃｃｕｒａｔｅ ｐａｔｔｅｒｎｓ ｗｉｔｈｏｕｔ ｐｒｅｃｉｓｅ ａｃｃｅｓｓ ｔｏ ｔｈｅ ｏｒｉｇｉｎａｌ ｄａｔａ．Ｔｈｉｓ ｐａｐｅｒ ｆｏｃｕｓｅｓ ｏｎ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ａｎｄ ｐｒｅｓｅｎｔｓ ａ ｐｒｉｖａ— ｃｙ ｐｒｅｓｅｒｖｉｎｇ Ｎａｉｖｅ Ｂａｙｅｓ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｄａｔａ ｒａｎｄｏｍｉｚａｔｉｏｎ ａｎｄ ｆｅａｔｕｒｅ ｒｅｃｏｎ— ｓｔｒｕｃｔｉｏｎ．Ａｎ ＥＲＲＰＨ（Ｅｘｔｅｎｄｅｄ Ｒａｎｄｏｍｉｚｅｄ Ｒｅｓｐｏｎｓｅ ｗｉｔｈ ＰａｒｔｉａＩ Ｈｉｄｄｉｎｇ）ｍｅｔｈｏｄ ａｎｄ ａ ＴＲＲ（Ｔｒａｎｓｆｏｒｍｉｎｇ Ｒａｎｄｏｍｉｚｅｄ Ｒｅｓｐｏｎｓｅ）ｍｅｔｈｏｄ ａｒｅ ｒｅｓｐｅｃｔｉｖｅｌｙ ｐｒｅｓｅｎｔｅｄ ｆｏｒ ｅｎｕｍｅｒａｔｅｄ ｄａｔａ ａｎｄ ｎｕｍｅｒｉｃａｌ ｄａｔａ．Ｔｈｅｎ，ａ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ Ｎａｉｖｅ Ｂａｙｅｓ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｉｍ— ｐｌｅｍｅｎｔｅｄ ｂａｓｅｄ ｏｎ ｔｈｏｓｅ ｍｅｔｈｏｄｓ．Ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｅｓ ｓｈｏｗ ｔｈａｔ ｉｔ ｃａｎ ｐｒｏｖｉｄｅ ｂｅｔｔｅｒ ｐｒｉｖａｃｙ， ａｃｃｕｒａｃｙ，ｅｆｆｉｃｉｅｎｃｙ，ａｎｄ ａｐｐｌｉｃａｂｉｌｉｔｙ．Ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｉｓ ａｌｓｏ ｖｅｒｉｆｉｅｄ ｂｙ ｅｘｐｅｒｉｍｅｎｔｓ． Ｋｅｙｗｏｒｄｓ ｄａｔａ ｍｉｎｉｎｇ；ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖａｔｉｏｎ；Ｎａｉｖｅ Ｂａｙｅｓ ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｄａｔａ ｒａｎｄｏｍｉｚａｔｉｏｎ； ｆｅａｔｕｒｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ 管理和分析变得越来越方便．包括分类挖掘在内的 引 目 随着信息技术，特别是网络技术、数据存储技术 和高性能处理器技术的飞速发展，海量数据的收集、 各种数据挖掘技术，更是在一些深层次的应用中发 挥了非常积极的作用．但与此同时，也带来了隐私保 护方面的诸多问题．例如，通过对电信客户的基本信 息和消费行为数据进行挖掘，可以预测新增客户的 收稿日期：２００７—０３ ０５；修改稿收到日期：２００７—０５ ２２．本课题得到国家自然科学基金（６０４０３０４１）和北京市科学技术委员会博士论文专项 基金（ＺＺ６０２７）资助．张鹏，男，１９７８年生，博士，工程师，主要研究方向为数据仓库、数据挖掘、联机分析处理．Ｅ－ｍａｉｌ：ｚｈａｎｇｐｅｎｇ＠ｅｔ— ｂｒｉ．ｃｏｒｎ．ｃｎ．唐世渭，男，１９３９年生，教授，博士生导师，主要研究领域为数据模型、数据库系统、数据仓库、数据挖掘． 维普资讯 http://www.cqvip.com 计 算 机 学 报 服务偏好和价值走向，但在使用一般方法进行挖掘 的过程中，不可避免地会使客户数据暴露，从而造成 客户隐私的泄露．于是，如何在数据挖掘的过程中解 决好隐私信息保护的问题，成为了数据挖掘界的一 个研究热点［１］．数据挖掘有一个重要特征，就是从大 量数据中挖掘出来的模式或者规则，通常是针对综 合数据而非细节数据．那么，能否基于非精确的原始 数据而抽取出准确的模式与规则呢？实现隐私数据 的合理保护和基于统计数据的模式抽取两者兼得， 正是数据挖掘中隐私保护方法研究的出发点和最终 目标． 数据挖掘中隐私保护的概念是由Ａｇｒａｗａｌ等 人［ｚ 提出的，他们专门针对决策树分类问题，采用随 机变换ｌＬ３ 的数据干扰策略，实现了数值类型数据的 变换和重构以及隐私保护的决策树分类算法；在此 基础上，Ａｇｒａｗａｌ等人又提出了一种基于期望最大 化的分布重构方法［４］．但是，这些方法都不能处理布 尔类型和枚举类型的数据．之后，Ｄｕ等人针对布尔 类型的数据，提出了一种决策树分类中基于随机化 回答的隐私保护方法［５］，但该方法与此前提出的随 机处理方法［６］一样，利用的都是统计学中的沃纳模 型，不仅由于变换后的所有数据都与真实的原始数 据直接相关，而使得对隐私信息的保护程度不高，并 且随机化参数的选择也受到，必须偏离Ｏ．５．与 此同时，Ｊｏｈｎｓｔｅｎ等人还提出了利用数据隐藏策略， 实现隐私保护的分类方法［７］，虽然一部分敏感信息 得到了保护，但由于数据所有者提供的数据全部都 是真实数据，所以此类方法对整个数据集的隐私保 护程度并不理想．Ｚｈａｎｇ等人则将数据干扰和查询 的隐私保护策略相结合，提出了一种部分隐藏 的随机化回答（Ｒａｎｄｏｍｉｚｅｄ Ｒｅｓｐｏｎｓｅ ｗｉｔｈ Ｐａｒｔｉａｌ Ｈｉｄｉｎｇ，ＲＲＰＨ）方法【８］，进行数据的变换和隐藏；然 后针对经过ＲＲＰＨ方法处理的数据，设计了一种简 单、高效的频繁项集生成算法，进而实现了关联规则 挖掘中的隐私保护．与之相比，分类算法所要处理的 数据类型更加广泛，不但包括布尔类型的数据，而且 还包括枚举类型和数值类型的数据．在分布式环境 下的隐私保护方法中，文献［９—１１］分别通过安全多 方计算协议，实现了决策树构建中的隐私保护方法； Ｖａｉｄｙａ等人则相继提出了朴素贝叶斯分类中基于 水平数据划分［１ ］和垂直数据划分口。］的隐私保护方 法；Ｃｌｉｆｔｏｎ等人还提供了一组分布式环境下，支持 数据挖掘中隐私保护计算的工具集 ．但是，这些 方法都只能用于分布式数据库，并且所有的数据提 供者都必须参与到计算中来，单点故障就会导致错 误结果的产生，甚至造成整个挖掘的无法进行． 可以看出，分类作为数据挖掘中一种重要的方 法，目前在隐私保护方面的研究大多数都是针对决 策树的构建方法展开的，包括朴素贝叶斯在内的其 它分类方法只在分布式环境下有少量的应用．然而， 在属性相互的条件下，朴素贝叶斯分类具有实 现简单、结果准确的特点，还可以针对枚举类型的数 据实现增量挖掘．于是，本文紧紧围绕分类挖掘中的 隐私保护问题展开研究，给出了一个基于数据处理 和特征重构的朴素贝叶斯分类中的隐私保护方法， 主要研究内容和创新成果包括：（１）提出了一种扩 展的部分隐藏随机化回答（ＥＲＲＰＨ）方法，实现了 枚举类型隐私数据的处理和特征重构；（２）提出了 一种转换的随机化回答（ＴＲＲ）方法，实现了数值类 型隐私数据的处理和特征重构；（３）在ＥＲＲＰＨ方 法和ＴＲＲ方法的基础上，实现了一个完整的隐私 保护的朴素贝叶斯分类算法；（４）通过理论分析和 实验结果，说明了朴素贝叶斯分类中基于ＥＲＲＰＨ 和ＴＲＲ的隐私保护方法具有很好的隐私性、准确 性、高效性和适用性． 本文第２节首先给出分类挖掘中隐私保护问题 的描述，然后提出解决方法的总体架构；第３节提出 一种ＥＲＲＰＨ方法，实现枚举类型数据的随机处理 和特征重构；第４节再提出一种ＴＲＲ方法，实现数 值类型数据的随机处理和特征重构；第５节说明如 何使用经过ＥＲＲＰＨ和ＴＲＲ方法处理得到的发布 数据集，构造朴素贝叶斯分类器，预测未知样本的类 标号；对方法的详细分析和评价以及同原有方法的 比较在第６节中给出；第７节中展示相关的实验结 果；最后的第８节给出全文的总结． ２问题与架构 本节中，我们将首先给出分类挖掘中隐私保护 问题的描述，然后提出解决方法的总体架构． ２．１ 问题描述 给定的数据集Ｄ包含１＂／个属性，分别记作Ａ ， Ａ ，…，Ａ ，且Ａ （ 一１，２，…， ）的值域为ｄｏｍ（Ａ ）． Ｄ中的每个样本用一个ｎ维特征向量Ｘ一（．ｚ ， ．ｚｚ，…，．ｚ ）表示，其中．ｚ ∈ｄｏｍ（Ａ ），ｉ一１，２，…，ｎ， 分别表示该样本中属性Ａ的取值．而且数据集Ｄ中 的全体样本被分成 个类，并分别用Ｃ ，Ｃ ，…， 维普资讯 http://www.cqvip.com ８期 张鹏等：朴素贝叶斯分类中的隐私保护方法研究 进行标记．那么，给定一个未知的数据样本Ｚ（类标 号未知），分类的目的就是要根据数据集Ｄ来预测 出样本Ｚ的类标号．而分类挖掘中的隐私保护问 题，就是要在不精确访问原始数据集Ｄ的条件下， 尽可能准确地预测出Ｚ的类标号． ２．２总体架构 ３扩展的部分隐藏随机化回答 （ＥＲＲＰＨ）方法 本节将提出一种ＥＲＲＰＨ方法，实现枚举类型 隐私数据的处理和特征重构． ３．１数据处理 为解决上述问题，本文提出了一种朴素贝叶斯 分类中的隐私保护方法．该方法基于ＫＤ。（Ｋｎｏｗｌ— 随机化回答方法的基本思想是：数据提供者依 ｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｉｎ Ｄｉｓｔｏｒｔｅｄ Ｄａｔａｂａｓｅ）架构［１ ，分 两阶段进行：首先用随机化回答的方法对原始数据 进行处理；然后再利用特征重构的方法，借助经过处 理的数据来对未知样本进行朴素贝叶斯分类．特别 要指出的是，我们会根据不同的数据类型来选择具 体的随机处理和特征重构方法．整个方法的总体架 构如图１所示． 图ｌ朴素贝叶斯分类中基于ＥＲＲＰＨ和 ＴＲＲ的隐私保护方法 第一个阶段针对枚举类型和数值类型的数据， 分别利用ＥＲＲＰＨ方法和ＴＲＲ方法来对原始数据 进行处理，具体的方法在第３和第４节中给出．第二 个阶段则将基于经过ＥＲＲＰＨ方法和ＴＲＲ方法处 理的发布数据，对原始数据的分布特征进行重构，以 此估算未知样本的后验概率，进而预测出分类标号， 详细的过程在第５节中介绍．整个方法中，连接两个 阶段操作的除了经过ＥＲＲＰＨ方法和ＴＲＲ方法处 理的数据以外，还有一组随机化参数，在第一个阶段 描述随机处理的规则；在第二个阶段指导分布的重 构和后验概率的计算．而且，参数值的选择对于隐私 的保护程度和挖掘结果的准确性，都具有非常重要 的影响． 照给定的随机化参数对原始数据进行变换，再提供 给数据使用者．在使用者得到的信息中，虽然详细信 息被提供者进行了处理，但在数据量比较大的情况 下，统计信息和聚集信息仍然可以被相当精确地估 算出来．由于样本分类，特别是朴素贝叶斯分类，是 基于一个数据集合的聚集信息值，而非一个个详细 的数据项，因此随机化回答方法可以很好地用于朴 素贝叶斯分类中的隐私保护问题．本节提出了一种 处理枚举类型隐私数据的ＥＲＲＰＨ方法，其具体描 述如下： 设属性Ａ有ｋ个可能的取值，其值域ｄｏｍ（Ａ）一 ｛ａ ，ａ ，…，ａ ｝．给定一组随机化参数ｏ＜－１）。，Ｐ ，…， Ｐ １，使得Ｐ。＋Ｐ ＋…＋Ｐ 一１．对任意的３２∈ ｄｏｒａ（Ａ），令ｒｏ一３２，ｒ，一ａ，（ 一１，２，…，ｋ），则随 机化函数ｒ（．ｚ）以Ｐ，（ 一０，１，…，ｋ）的概率返回ｒＪ． 数据集Ｄ中的样本可以用向量Ｘ一（．ｚ ，３２ ，…，３２ ） 来表示，其中３２ ∈Ａ ，且Ａ 的值域ｄｏｍ（Ａ ）一 ｛ａ ａ …，ａ嚏｝．于是，随机处理后的样本ｌ，一（ ， Ｙ ，…，Ｙ ）可以通过Ｙ＝Ｒ（ｘ）计算得到，其中Ｙ 一ｒ （．ｚ ）．也就是说，Ｙ 以Ｐ。的概率取值为－ｚ ，而以Ｐ 的 概率取值为ａ 这样，对数据集Ｄ中的每一个样本ｘ，经过随 机化函数Ｒ的处理得到ｌ，，而且由于ｌ，在形式上仍 然是一个与ｘ相似的数据样本，所以就可以作为一 个伪造的样本，加入到伪造的数据集Ｄ 中． 需要说明的是，在ＥＲＲＰＨ方法中，我们可以对 不同的属性分别使用不同的随机化参数进行干扰． 但为了简单起见，我们将对所有属性使用相同的随 机化参数进行数据处理． ３．２特征重构 那么，如何利用经过ＥＲＲＰＨ方法处理得到的 发布数据集Ｄ 来重构原始数据集Ｄ中属性的分 布情况呢？设丌，表示原始数据集Ｄ中属性Ａ的取 值为ａ，的样本所占的比例； ，表示发布数据集Ｄ 中 属性Ａ的取值为ａ，的样本所占的比例，其中 一１， ２，…，ｋ．Ｄ中的样本ｘ经过ＥＲＲＰＨ方法处理，变 维普资讯 http://www.cqvip.com 计 算 机 学 报 成Ｄ 中的样本ｙ，而ｘ和ｙ对应属性Ａ的取值分别 用（ｎ ，ｎ。，…，ｎ ）表示，则ＸＡ和 的取值与映射概 后的数据就可以通过Ｙ—ｒ（ｚ）计算得到．设原始数 据集Ｄ中包含 条记录，这 条记录所对应的属性 率如表１所示． 表１ ＥＲＲＰＨ方法处理数据的映射概率 由表１可得 一Ｐ。・丌＋ ，．于是， １一＾ 丌丌，一， 一—丝 （１）１ Ｐ ０ 也就是说，我们可以首先计算出发布数据集Ｄ 中属性Ａ的取值为ｎ，的样本所占的比例 ，然后再 利用式（１）估算出原始数据集Ｄ中属性Ａ的取值为 ｎ，的样本所占的比例丌． 为了简单起见，我们通常会假设除了Ｐ。以外的 忌个参数都相等，也就是说，Ｐ 一Ｐ。一・一Ｐ 一 １一 ．这样，在原始数据集中对应属性Ａ的不同取 值的样本就可以通过相同的式（１）计算得到． ４转换的随机化回答（ＴＲＲ）方法 本节将基于统计学中的转换模型，提出一种针对 数值类型数据的ＴＲＲ随机处理与特征重构方法． ４．１数据处理 转换的随机化回答（ＴＲＲ）方法，首先需要随机 生成一个满足给定特征的变换函数，然后利用这个 函数对原始的数值类型数据进行变换，并将变换后 的数值作为随机化回答的结果．方法的具体描述 如下： 给定集合Ａ一｛ｎ ，ｎ。，…，ｎ ），且设其中元素的 均值和方差分别为 １ ｌ １ ｌ 一 ∑ｎ ， — ∑（ｎ 一 ）。； ｉ一１ ｉ一１ 再给定集合Ｂ一｛ｂ ，ｂ。，…，ｂ ），且设其中元素的均 值和方差分别为 对数值类型的数据 ，随ｉ豆一 ∑６， ， 一 ｍ－－∑（ｂｉ－ｍｌ－．－Ｊ 机＝化豆）。． 函数ｒ（ ）一 ｎ ＋ｂ，其中ｎ∈Ａ，是从Ａ中随机选取的一个元素， 而６∈Ｂ，是从Ｂ中随机选取的一个元素．这样，变换 Ａｆ的取值分别为Ｘ一｛ ， 。，…， ）．那么，发布数 据集Ｄ 中的 条记录所对应的属性Ａｔ的取值ｙ一 ｛Ｙ ，Ｙ。，…，Ｙ ）就可以通过ｙ—Ｒ（Ｘ）计算得到，其 中Ｙ 一ｒ（ｘ ）， 一１，２，…， ． ４．２特征重构 按照上述的ＴＲＲ方法，我们将原始数据 转 换成Ｙ—ｒ（ ）：ａｘ－［－ｂ．当Ａ一＝／：Ｏ时，令 估计量圣一 ｙ－－Ｂ，且圣是 的无偏估计量．原始数据集Ｄ中的 条记录所对应的属性Ａｆ的取值Ｘ一｛ ， ｚ，…， ｚ ），被转换为了发布数据集Ｄ 中的 条记录所对 应的属性Ａｆ的取值ｙ一｛ ， 。，…， ）． 为了进行朴素贝叶斯分类，我们假设Ｘ符合高 斯分布Ｎ（ ， ２）．我们知道，互一 ∑ 是 的无 偏估计量．但 是未知的，故我们用圣 代替 ，得到 估计量至一 １ 一 骞 一 ． 通常，为了计算简便，可以设计豆一０，进而得到 ｚ均值的估计值 至一 ｙ一 一 一一（ｚ） ｎＡ ２／， （２） ．一 另一方面，Ｖａｒ（ ）一 ｒ（ｎ ＋６）一（ ＋Ａ。）・ Ｖａｒ（ ）＋ ・互。＋ ．因此， Ｖａｔ（ｘ）－ ． 但互未知，故用至一 来代替．于是得到 的方差估 计值 沪 １ 。一 一 一— — 雨－一 这样，就可以利用集合Ａ中元素的均值Ａ和方 差 ｉ以及集合Ｂ中元素的方差 §，并通过发布数据 集Ｄ 中属性Ａｔ的取值ｙ一｛ ， 。，…， ），来根据 式（２）和式（３），计算出至和Ｓ。的取值．然后，以此作 为原始数据集Ｄ中属性Ａｔ的取值Ｘ一｛ ， ｚ，…， ３７ ）的分布特征Ｎ（圣，Ｓ。），进而实施分类挖掘． 维普资讯 http://www.cqvip.com ８期 张鹏等：朴素贝叶斯分类中的隐私保护方法研究 ５隐私保护的朴素贝叶斯分类算法 本节将在一般的朴素贝叶斯分类算法的基础 上，利用基于ＥＲＲＰＨ的枚举类型数据特征重构方 法和基于ＴＲＲ的数值类型数据特征重构方法，给 。志蓦ｃ ｉ＋ 一 ’ １ 于是可知 Ｐ（ｚｋ ｌＣｉ）＝ｇ（ｚｋ，五 ， ） 去ｅ。 （５） 出通过发布数据集Ｄ 来对未知样本Ｚ进行分类的 算法． 朴素贝叶斯作为一种简单实用的分类方法，将预 测未知样本Ｚ属于具有最高后验概率（条件Ｚ）的类． 即将未知的样本分配给类Ｇ，当且仅当Ｐ（Ｃ ｌ Ｚ）三三＝ Ｐ（Ｃ，ｌ Ｚ），其中１ ｍ且Ｊ≠ｉ．这样，我们最大化 Ｐ（Ｃｉ ｌ Ｚ）的值，而使得Ｐ（Ｃ ｌ Ｚ）最大的类Ｃ 则称 为最大后验假定．根据贝叶斯定理，有Ｐ（Ｃ ｌ Ｚ）一 ．由于Ｐ（ｚ）对于所有类为常数，故 只需让Ｐ（ＺｌＣ ）Ｐ（Ｃ ）的取值最大即可．于是，朴素 贝叶斯分类算法的核心内容就是要计算和比较 Ｐ（ＺｌＣ ）Ｐ（Ｃ ）的值，其中ｉ一１，２，…，ｍ． 在经过ＥＲＲＰＨ方法和ＴＲＲ方法随机处理所 得到的发布数据集Ｄ 中，因为类标号是没有进行处 理的，所以类的先验概率仍然可以用Ｐ（Ｃ，）＝＝＝＿ｏｉ计 算，其中ｓ。是类Ｃ 中的训练样本数，而ｓ—ｌ Ｄ ｌ是训 练样本总数．在属性相互的条件下，Ｐ（Ｚｌ Ｃ。）一 Ｉｌ Ｐ（ｚ ｌ Ｃｉ）．但Ｐ（ｚ ｌ Ｃ ），Ｐ（ｚｚ ｌ Ｃ ），…，Ｐ（ｚ ｌ Ｃ ） 的值无法通过训练样本直接计算得到，而需要借助 ＥＲＲＰＨ（对枚举类型数据）和ＴＲＲ（对数值类型数 据）的特征重构方法． （１）如果Ａ是枚举类型的属性，则设Ｐ （ ｌ Ｃ ）＝＝＝ ， ｃ，其中ｓ 是在发布数据集Ｄ 中属性Ａ 的取值为 ５ｉ ｚ ，且属于类Ｃ 的训练样本数，而ｓ 是属于类Ｃ 中 的训练样本数．根据式（１）可知 Ｐ（ ｌＣ ）一 ｌ）二 Ｐ １Ｐｌ （４） （２）如果Ａ 是数值类型的属性，则设发布数据 集Ｄ 中属于类Ｃ 的训练样本数为Ｎ ，分别记作ｙ ， ｙ。，…，ｙ ，它们的均值为歹 而样本ｙ』在属性Ａ 上的取值为ｙ 分别根据式（２）和式（３），我们可以 计算得到 １ 一而‘刍 ” 这样，Ｐ（Ｚ｝Ｃ。）Ｐ（Ｃ ）就可以通过式（４）和式（５） 计算得到．对未知样本Ｚ分类时，就可以使用经 过ＥＲＲＰＨ方法和ＴＲＲ方法随机处理过的发布数 据集Ｄ ，来对每个类Ｃ ，计算Ｐ（Ｚｌ Ｃｉ）Ｐ（Ｃｉ）的值． 并将未知样本Ｚ分到类Ｃ。，当且仅当Ｐ（Ｃ ｌ Ｚ）三三＝ Ｐ（ＣＪ ｌＺ），其中１ ｍ且Ｊ≠ｉ． ６分析与评价 本节将从隐私性、准确性、高效性和适用性这 ４个方面，对本文提出的朴素贝叶斯分类中基于 ＥＲＲＰＨ和ＴＲＲ的隐私保护方法进行详细的分析 和评价，并与原有的隐私数据决策树构建（Ｂｕｉｌｄｉｎｇ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ ｏｎ Ｐｒｉｖａｔｅ Ｄａｔａ，ＤＴＰＤ）方法以及基 于随机化数据的决策树分类（Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ Ｃｌａｓｓｉ— ｆｉｃａｔｉｏｎ ｏｖｅｒ Ｒａｎｄｏｍｉｚｅｄ Ｄａｔａ，ＤＴＣＲＤ）方法进行 对比． ６．１ 隐私性 数据挖掘中隐私保护方法研究的出发点和最终 目标，是在合理保护隐私数据的前提下，进行数据挖 掘和知识发现，寻找其中潜在的模式和规则．本文提 出的朴素贝叶斯分类中的隐私保护方法是基于 ＫＤ。架构设计的，分两个阶段进行．而隐私性则主要 是在第一个阶段，即利用ＥＲＲＰＨ方法和ＴＲＲ方 法进行随机处理的过程中实现的． 在处理枚举类型数据的时候，使用的是ＥＲＲＰＨ 方法．数据使用者得到．ｙ—ｒ（ｚ），而且ｙ和ｚ的取值 范围是相同的，都是ｄｏｍ（Ａ）＝｛ａ ，ａ。，…，ａ ）．对于 给定的．ｙ值来讲，ｚ可以是ｄｏｒａ（Ａ）中的任意一个 取值，因而无法通过．ｙ值来还原ｚ的取值，也就是 说隐私信息ｚ得到了保护．在发布数据集中，比例 为１一Ｐ。的数据被隐藏，只有比例为Ｐ。的真实数据 混杂在大量的伪造数据中被提交给了数据使用者． 并且由于每条记录所对应的随机化参数都是未知 的，因而这些真实数据是很难被识别出来的．即使是 在随机化参数被泄露的情况下，也至多暴露比例为 Ｐ。的真实数据．这样，ＥＲＲＰＨ方法既克服了基于数 据干扰策略的处理方法中，所有变化后的数据均与 维普资讯 http://www.cqvip.com 计 算 机 学 报 真实的原始数据直接相关的不足，又消除了基于查 询策略的处理方法中，所有提供的都是真实原 间宽度与ＤＴＣＲＤ方法中使用高斯分布进行干扰 （这也是隐私保护程度最高的一种方式）时的隐私破 坏区间宽度是一致的，而比使用其它干扰方式（包括 离散化和均值分布干扰）进行隐私信息保护时的效 果要好． 始数据的缺陷，从而实现了对隐私信息的很好保护． 为了比较不同方法对隐私信息的保护程度，我 们提出了一个隐私破坏系数Ｂｒｅａｃｈ的指标．它是指 原始数据被重构或者预测出来的概率，其定义如下： ＢｒＰ乜ｃ 一Ｐ真实数据的比例×Ｐ真实数据被识别出的概率＋ Ｐ非真实数据的比例×Ｐ非真实数据被识别出的概率× Ｐ非真实数据被还原的概率． 于是，ＥＲＲＰＨ方法的隐私破坏系数为Ｂｒｅａｃｈ一 Ｐ。・＿半＿．当除Ｐ。之外的其余ｋ个随机化参数均 ＰｏＴｐ １一＾ 相等，即Ｐ１一Ｐ２一・一Ｐ 一半时，Ｂｒｅａｃｈ— Ｐ ｋ・Ｐ １ ｒ 如果ｋ一２，则ＥＲＲＰＨ 方法退化成ＲＲＰＨ方法，此时Ｂｒｅａｃｈ一 ．因 Ｐｏ Ｔ 为ＤＴＰＤ方法使用的是基于沃纳模型的随机化回 答方法，所以根据文献［８］中的分析结果可知：当 １ ０＜ ＜ 时，该方法比ＤＴＰＤ方法具有更高的隐私 √Ｚ 保护程度． 在处理数值类型数据的时候，使用的是ＴＲＲ 方法，这是基于统计学中的转换模型构建的．数据使 用者得到的是 —ｒ（ｚ）一ｎｚ＋６，其中ａ和ｂ是分别 从集合Ａ与集合Ｂ中随机选取的元素．由于我们只 知道集合Ａ与集合Ｂ中的元素分别服从给定均值 和方差的高斯分布，但并不知道它们具体可能的取 值，因而无法通过Ｙ值来还原ｚ的取值，也就是说 隐私信息ｚ得到了保护． 为了能够评价类似方法的隐私保护程度，我们 引入了一个隐私破坏区间宽度ＢｒｅａｃｈＷｉｄｔｈ的指 标．它的定义是：如果原始数据ｚ落到区间［ｚ ，ｚ。］ 上的概率为Ｃ，即Ｐ（ｚ ｚ ｚ。）一Ｃ，则称区间 ［ｚ ，ｚ。］是置信度为Ｃ的隐私破坏区间，而该区间的 宽度（ｚ。一ｚ ）就定义了置信度为Ｃ的隐私破坏区间 宽度，即 ＢｒｅａｃｈＷｉｄｔｈ—ｚ２一ｚ１． 由于Ｘ服从高斯分布Ｎ（／１，ｄ。），所以ＴＲＲ方 法在不同置信度条件下的隐私破坏区间宽度如表２ 所示．可以看出，ＴＲＲ方法的隐私破坏区间宽度只 和Ｘ所服从的分布的标准差有关，并且随着置信度 的增加而不断变大．另外，ＴＲＲ方法的隐私破坏区 表２不同置信度的隐私破坏区间宽度 ６．２准确性 保护好数据的隐私，是数据挖掘中隐私保护方 法的最基本要求，而我们的最终目标是要通过挖掘 来获取真实、可用的知识与规则． 对于ＥＲＲＰＨ方法，由式（１）得到的估计量 一 是 的无偏估计量；方差 ｒ（ 一去 ｒ（ ． 设数据集中Ｄ中的样本总数为Ｎ，则 一 二ｌ ±！ ！二 ！ 二 Ｎ ‘ 所以， Ｖａｔ（ｉｔ ）一 Ｐｉ（１一Ｐ１）＋Ｐｏ（１一 。一２ ）Ｉｒｉ．巩（１一巩） Ｎｐ 。 Ｎ ‘ 忽略抽样误差， Ｖａｒ（ｉｒ￣）＝ ． 当 一 ｚ一…一户 一 时， ｒ（ ）一 ｊ１ －ｐ庀。ｐｏ Ｅｋ一１＋ 。＋忌（忌一２）ｐ。 ］．如果忌一２，则 ）一 ． 对于数值类型的数据，使用的是ＴＲＲ方法．为 了进行朴素贝叶斯分类，假设Ｘ符合高斯分布 Ｎ（／１ ，ｄ ２）． 我们知道，至一吉 ｚ 是 的无偏估计量．但 ｚ 是未知的，因而用奎 代替ｚ ，得到估计量至一 维普资讯 http://www.cqvip.com ８期 张鹏等：朴素贝叶斯分类中的隐私保护方法研究 骞圣 ，也是 的无偏估计量．于是， ｒ（ 骞 ） 骞 ｒ（ ． ＋ 一一 一 一— 。 因为其中的３２未知，所以要计算Ｖａｒ（奎）的估计量 ｒ（互）一 骞 ．由Ｅ［ ｒ（至）］一 ・ 堕÷ 一 ｒ（互），知 ｒ（互）是 ｒ（互）的 无偏估计量．－￣Ｎｗｔ，由于 ｒ（５７）中不包含豆．因此 … … 著脚 一 ， …一 ａ ｌ ＋ａ￣一 ． （ ｔ 一 Ｉ ｉ １ＤＡ ， Ｅ（Ｓ ）一Ｅ ｌ— 一— 一 三＋ 一Ｅ（ｚａ，－（ｙ）－ （芸） 一 §］ Ｌ—— 一ｊ —Ｖａｔ（３一 Ｖａ ２）一——— ＿ ＝－Ｆ—ａ ，￣ｘ￣－－ａＭｚ￣（－一，ｘ）一一Ｖａ ｒ（ｚ）．． 也就是说，§ｚ是Ｖａｒ（ｚ）的无偏估计量． 我们记卢一 耋（ 一 一 Ｅ（ 一 蓦一（ ＋ ２）歹 ．于是， 一 Ｖａｒ （ｆ１）一 ＋（ｎ－－１）一ｙＺ— ・ ］ （ 一１ 再 。 可以看出，在ＴＲＲ方法中，原始数据方差估计 值的误差会随着集合Ａ中元素均值和方差的增大 而增加．在下一节中，我们将通过实验，对于不同方 法的挖掘结果准确性进行详细的分析比较． ６．３高效性 与普通数据挖掘方法相比，隐私保护的数据挖 掘方法面对着更加复杂的要求．本文提出的朴素贝 叶斯分类中基于ＥＲＲＰＨ和ＴＲＲ的隐私保护方 法，在对隐私信息进行合理保护和对未知样本做出 较准确分类的同时，并没有带来过多的计算复杂度 增长，其时间和空间代价与一般的朴素贝叶斯分类 方法成线性关系． 原有的ＤＴＰＤ方法和ＤＴＣＲＤ方法都是决策 树构建中的隐私保护方法．对于ＤＴＰＤ方法来讲， 其计算的复杂度与一般的决策树分类方法成线性关 系；而对于ＤＴＣＲＤ方法来讲，会由于在分布重构过 程中所进行的大量迭代计算，而使得计算的复杂度 大幅度增加． ６．４适用性 本文提出的朴素贝叶斯分类中的隐私数据保护 方法，还具有非常好的适用性．具体体现在数据挖掘 算法的适用性、隐私数据类型的适用性和数据分布 状况的适用性这三个方面． 首先，从数据挖掘算法的角度来看，本文提出的 朴素贝叶斯分类中的隐私保护方法，是在ＫＤ。通用 架构与流程的基础上设计的，将整个方法分成了相 对的两个阶段，所以当我们希望将其扩展，用于 决策树构建等其它的分类算法、关联规则挖掘等其 它的数据挖掘算法时，第一阶段的ＥＲＲＰＨ方法和 ＴＲＲ方法可以直接使用，只需要在第二阶段的挖掘 过程中，利用相应的特征重构方法就可以了． 其次，从数据类型的角度来看，现有数据挖掘中 隐私保护方法所使用的随机处理方法，针对的都是 数值类型或者布尔类型的数据，都不适用于枚举类 型的数据．例如，ＤＴＰＤ方法是分类挖掘中布尔类型 隐私数据的保护方法；而ＤＴＣＲＤ方法则是分类挖 掘中数值类型隐私数据的保护方法．而本文提出的 ＥＲＲＰＨ数据处理和特种重构方法，能够很好地处 理枚举类型的数据．而且，通过ＥＲＲＰＨ方法和 ＴＲＲ方法的配合使用，实现了能够同时支持枚举类 型和数值类型的完整的隐私保护的朴素贝叶斯分类 算法． 另外，现有的朴素贝叶斯分类中的隐私保护方 法，只能适用在基于水平划分或者垂直划分的分布 式数据库中，而本文提出的基于ＥＲＲＰＨ和ＴＲＲ 的隐私保护方法，能够同时适用于集中式数据库和 分布式数据库．无论原始数据属于一个还是多个数 据所有者，都可以将经过ＥＲＲＰＨ方法和ＴＲＲ方 法随机处理后的发布数据集交给数据使用者，并利 于相应的特征重构方法，对未知样本实施朴素贝叶 斯分类． 综上所述，本文提出的朴素贝叶斯分类中基于 维普资讯 http://www.cqvip.com 计 算 机 学 报 ＥＲＲＰＨ和ＴＲＲ的隐私保护方法，在隐私性、准确 性、高效性和适用性等方面都取得了良好的效果．下 一用ＥＲＲＰＨ方法对原始数据进行随机处理．对于 数值类型的属性，我们则将选取满足给定高斯分布 的随机数ａ和ｂ，来对原始数据集进行随机处理． 其中，ａ分别服从高斯分布Ｎ（１，１）和高斯分布 Ｎ（２，１０）；ｂ则分别服从标准正态分布Ｎ（Ｏ，１）和高 斯分布Ｎ（０，５）． 接下来，我们就可以使用本文提出的ＰＰＮＢ方 法，根据经过随机处理的训练数据集，来对测试数据 集中样本的类标号进行预测，并与它们实际的类标 节将通过实验对相应的分析结果做进一步的 印证． ７ 实验分析 在本节中，我们将通过一组实验，来检验本文提 出的朴素贝叶斯分类中基于ＥＲＲＰＨ和ＴＲＲ的隐 私保护（Ｐｒｉｖａｃｙ Ｐｒｅｓｅｒｖｉｎｇ Ｎａｉｖｅ Ｂａｙｅｓ，ＰＰＮＢ）方 号相对照，计算出分类结果的准确率．为了有所参 照，我们还将利用一般的朴素贝叶斯分类方法，来根 据原始的训练数据集对测试数据集中的样本标号进 法．一方面，我们会将ＰＰＮＢ方法与原始的朴素贝 叶斯（Ｎａｉｖｅ Ｂａｙｅｓ，ＮＢ）分类方法，对同一批未知样 本进行分类的结果进行对照；另一方面，我们还会将 ＰＰＮＢ方法与ＤＴＰＤ方法，在进行隐私保护分类挖 掘时结果的准确性进行对比，并说明数据隐私性和 挖掘结果准确性与随机化参数之间的关系． ７．１实验方法 行预测，并计算出分类结果的准确率． 最后，为了与现有分类挖掘中的隐私保护方法 ＤＴＰＤ相比较，我们将针对模拟数据集，分别选取一 个分界点将所有属性都转化成了布尔属性．然后，选 取不同的随机化参数 一户一０．１，０．２，０．３，０．３５， ０．４，０．４５，０．４９，０．５１，０．５５，０．６，０．６５，０．７，０．８， １一 我们在实验中将使用一组模拟的数据集和一组 真实的数据集．模拟数据集是一组银行卡客户信息， 包括客户的年龄、学历、职业、婚姻状况、收入水平、 ０．９；Ｐ１一Ｐ 一半厶 ，分别利用ＥＲＲＰＨ（此时已经 持卡数量、刷卡频率、刷卡额度、存款额度、贷款额度 等描述属性以及客户价值（高、中、低）的分类属性． 我们随机抽取了５００００个样本作为训练数据集，另 取了５０００个样本作为测试数据集．真实数据集来自 退化为ＲＲＰＨ）方法和ＤＴＰＴ方法先对原始数据进 行随机处理；再利用经过处理的训练数据集，对测试 集中的样本进行分类，并比较两种方法的分类结果 准确性． ７．２实验结果 某刑侦系统的犯罪嫌疑人信息，总计３３３８９条记录， 我们选取前３００００条记录作为训练数据集，其余 ３３８９条记录作为测试数据集，并将根据犯罪嫌疑人 的属性信息，预测其参与案件的类型． 针对这两个数据集，我们将首先利用ＥＲＲＰＨ 方法和ＴＲＲ方法对它们进行随机处理．对于枚举 类型的属性，将选取不同的随机化参数Ｐ。一０．１， ０．２，０．３，０．３５，０．４，０．４５，０．４９，０．５１，０．５５，０．６， １一＾ 图２中分别给出了ＰＰＮＢ方法在不同随机化参 数取值的情况下，针对（ａ）银行卡客户数据和（ｂ）刑 侦数据的分类结果准确率．其中，横轴表示针对枚举 类型属性的ＥＲＲＰＨ方法中Ｐ。的值，纵轴表示分类 结果准确率，两条则折线表示针对数值类型属性的 ＴＲＲ方法中不同的两组参数．另外，我们还与普通 的ＮＢ方法针对原始数据集的分类结果准确率进行 了比较． ０．６５，０．７，０．８，０．９；Ｐ 一夕２一・一夕＾一 ，使 褂 器 姆 随机化参数 （ａ）银行卡系统客户数据 ，随机化参数 （ｂ）刑侦系统犯罪嫌疑人数据 图２ ＰＰＮＢ方法的分类结果准确率 维普资讯 http://www.cqvip.com ８期 张鹏等：朴素贝叶斯分类中的隐私保护方法研究 １２７５ 图３（ａ）中给出了ＰＰＮＢ方法和ＤＴＰＤ方法，对 银行卡客户数据的分类结果准确率随参数Ｐ变化 的情况；图３（ｂ）中则给出了这两种方法，对犯罪嫌 疑人数据的分类结果准确率随参数Ｐ变化的情况． 随机化参数 （ａ）银行卡系统客户数据 随机化参数 （ｂ）刑侦系统犯罪嫌疑人数据 图３ ＰＰＮＢ方法和ＤＴＰＤ方法的分类结果准确率比较 ７．３结果分析 但真实的数据集中属性间是存在相互依赖关系的． 尽管如此，只要参数选择合理，ＰＰＮＢ方法仍然可以 首先，从图２的结果可以看出：ＰＰＮＢ方法的分 类结果准确率会随着ＥＲＲＰＨ方法中随机化参数 Ｐ。（即真实数据所占的比例）取值的增大而不断提高； 还将随着ＴＲＲ方法中参数集合方差的增大而降低． 然后，从图３的结果可以看出：ＤＴＰＤ方法的分 类结果准确率变化比较大，当Ｐ接近０或１时，挖掘 结果比较准确；但此时的隐私破坏系数接近１，方法 对隐私的保护程度很差．在Ｐ从０或１逐渐接近 取得较好的分类效果． 在理论分析和实验结果的基础上，权衡数据的 隐私性和挖掘结果的准确性，我们建议在区间 ［０．３５，０．６］上选取随机化参数Ｐ的值，在分类挖掘 中使用ＰＰＮＢ方法进行隐私信息的保护． ８ 总 结 在本文中，我们紧紧围绕分类挖掘中的隐私保 护问题展开研究，给出了一种基于数据处理和特征 重构的朴素贝叶斯分类中的隐私保护方法．我们根 据隐私数据类型的不同，分别提出了一种针对枚举 类型的ＥＲＲＰＨ数据处理和特征重构方法和一种针 对数值类型的ＴＲＲ数据处理和特征重构方法；并 在此基础上实现了一个完整的隐私保护的朴素贝叶 斯分类算法． 我们还通过理论分析和实验，说明了在朴素贝 ０．５的过程中，隐私破坏系数会逐渐减小，隐私保护 的程度不断提高，但挖掘结果的准确率将显著下降． 而本文提出的ＰＰＮＢ方法，分类结果的准确率变化 相对平稳，随着Ｐ值，也就是真实数据所占的比例， 从０增加到１，隐私破坏系数也从０增长到１，方法 对隐私的保护程度不断下降，而挖掘结果准确率不 断提高． 再从图３（ａ）的详细结果还可以看出：当Ｐ的取 值较小时，ＤＴＰＤ方法的准确率比ＰＰＮＢ方法高； 而当Ｐ的取值超过０．３以后，ＰＰＮＢ方法的准确率 就要高于ＤＴＰＤ方法了，特别是当Ｐ值接近０．５ 时，准确率更是相差了很多．这些实验结果与第６节 中关于隐私性和准确性方面的论证是完全一致的． 图３（ｂ）的结果和图３（ａ）的结果相比，整体效 叶斯分类中基于ＥＲＲＰＨ和ＴＲＲ的隐私保护方法 中，随机化参数的选择与数据隐私性和挖掘结果准 确性之间的关系与相互影响，并就方法的运行效率 和适用范围进行了详尽分析．分析和实验的结果均 表明，该方法具有很好的隐私性、准确性、高效性和 适用性． 果基本一致，只是两种方法的分类结果准确率都有 不同程度下降．其中，ＰＰＮＢ方法的分类结果正确率 下降的更加明显，在图３（ａ）中，当Ｐ ０．３时就比 ＤＴＰＤ方法具有更高的分类结果准确率，而在图３ （ｂ）中只有Ｐ在区间［０．４，０．７］上时才具有更高的 分类结果准确率．这是因为朴素贝叶斯分类的方法 需要类条件的假定，模拟数据集是这样构造的， 参 考 文 献 Ｅｌｉ Ｖｅｒｙｋｉｏｓ Ｖ Ｓ，Ｂｅｒｔｉｎｏ Ｅ，Ｆｏｖｉｎｏ Ｉ Ｎ，Ｐｒｏｖｅｎｚａ Ｌ Ｐ，Ｓａｙｇｉｎ Ｙ，Ｔｈｅｏｄｏｒｉｄｉｓ Ｙ．Ｓｔａｔｅ～ｏｆ－ｔｈｅ—ａｒｔ ｉｎ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｄａ— 维普资讯 http://www.cqvip.com
