一种基于本地化差分隐私保护的高效用朴素贝叶斯分类方案

王慧婷，陈燕俐，彭春春

(南京邮电大学 计算机学院、软件学院、网络空间安全学院， 江苏 南京 210023)

数据挖掘技术利用算法能够从海量信息中提取潜在的有效信息和知识，目前已被应用到各行业中，例如：疫情监测、天气预报、股票交易、智慧城市构建等。 但与此同时，大量敏感信息的披露将给用户带来无法估量的威胁和损失，因此在进行数据挖掘和分析的同时，需要对用户个人提供的数据进行隐私保护。 当前主流的隐私保护技术主要分为3 类［1］：基于加密的隐私保护技术、基于匿名的隐私保护技术以及基于失真的隐私保护技术。 由于大数据的大规模、多样性和高速性的特点，加密技术在加解密和验证环节中会带来较大的计算开销代价和通信代价；而匿名发布的方法存在数据损失和数据可用性较低的弊端，不利于数据的挖掘和分析。 基于失真的隐私保护技术通过扰动原始数据，使攻击者无法进行重构，典型的方法即差分隐私技术（Differential Privacy，DP）［2］。 差分隐私技术完全独立于攻击者的背景知识，通过集中收集后添加随机噪声使敏感数据失真后再发布，添加噪声后的某些数据仍然保持原有数据的某些统计特性，因而更适合大数据下对数据进行隐私保护。

传统的差分隐私技术（中心化差分隐私）需要可信的第三方数据收集者集中收集数据，再进行隐私保护，然而在实际应用中，即使第三方数据收集者宣称不会窃取和泄露用户的敏感信息，用户的隐私依旧得不到保障。 2011 年，Kasiviswanatha 等［3］提出的本地化差分隐私（Local Differential Privacy，LDP）技术，将数据的隐私化处理过程从第三方数据收集者转移到每个用户上，可以在不需要信任第三方数据收集者的情况下，在本地环境下对个人敏感数据加噪实现隐私保护，同时从宏观角度保证数据收集者可正确地推断出群体统计信息。 这既保证了群体统计信息的相对准确性，又保护了个人的原始数据，解决了用户隐私数据被不可信第三方外包管理的问题，因而LDP 适用场景更广，实用程度更高，被广泛应用在数据收集、统计和分析的领域。

根据挖掘的模式，数据挖掘技术可分为：分类、聚类、关联分析和异常检测等，其中分类算法是数据挖掘研究领域中基础和核心技术之一［4］。 在分类算法中，首先是学习阶段，通过分析一个训练数据集，找到一个描述并区分数据集的分类模型即分类器；其次是使用该分类模型对未知类标记的样本，即新的数据集进行预测分类。 常用的分类算法包括决策树、支持向量机、神经网络、逻辑回归、贝叶斯分类器等。 其中的朴素贝叶斯分类（Naive Bayes Classifier，NBC）是一种基于概率，对未标记的数据进行分类的简单、高效有监督的学习方法［5］。 NBC假定了模型的变量遵循某种概率分布，并根据概率分布和观察数据推理，从而得出最优决策。 相较于其他分类算法，由于其核心是贝叶斯定理，因此有着扎实的数学基础和较稳定的分类能力。 由于在训练阶段无需迭代，时间复杂度相对较低；并且由于属性条件独立性的假设，建模过程中运算速度较高，处理数据量较大时更为简单高效，因此NBC 被广泛应用在计算机视觉、模式识别、自然语言处理等领域。 为了使数据的分析结果更加准确，NBC 通常需要足够多的数据用于训练，然而训练数据的收集涉及了用户的隐私信息，可能带来隐私安全问题，因此针对朴素贝叶斯分类的差分隐私保护相关方案陆续被提出，但大部分都集中在中心化环境，即第三方服务器可信的情况［6－11］。 2020 年，Yilmaz 等［12］首次设计了基于本地差分隐私保护的贝叶斯分类算法，算法能支持离散和连续属性数据，在训练分类器的同时保护了用户数据隐私，但时间开销较高。 2021 年，Xue 等［13］也利用本地差分隐私设计了训练贝叶斯分类器的方案，使用联合分布来计算条件概率，由于每次计算中随机采样原始用户数据的单个属性值，因此能够有效降低通信代价，然而当属性较多时，方案存在采样率过低，统计结果会产生较大采样误差的问题。

针对目前基于本地化差分隐私的贝叶斯分类算法存在时间开销和通信代价较高，以及采样率过低引起采样误差的问题，本文设计了一个高效的基于本地差分隐私的频数预测算法，并在此基础上，构建了准确率高并可有效保护用户个体隐私数据的朴素贝叶斯分类器。 本文的主要贡献如下：

（1） 设计了一种基于本地差分隐私的频数预测算法LDPbayes⁃FO。 算法的用户端扰动机制基于指数机制设计，将效用函数定义为输入和输出集合之间是否有交集，扰动输出的概率由效用函数决定。服务器端对数据聚合后还原出各编码值相应的频数。 LDPbayes⁃FO 算法能够在对用户提供的训练数据进行隐私保护的同时，很好地保证训练数据统计的质量，并有效提高数据统计结果的效用。

（2） 将LDPbayes⁃FO 与贝叶斯分类算法相结合，提出一种基于本地化差分隐私的贝叶斯分类方案——LDPBayes。 服务器端根据聚合后统计的各编码值频数，计算出条件概率和类标签概率，构建出一个有效安全的朴素贝叶斯分类器。 该分类器根据最大似然推理原则对待分类的数据进行分类预测。LDPBayes 方案相较于其他基于差分隐私的贝叶斯分类方案，将隐私化处理从服务器端转移到了本地，因此隐私保护的程度更高；同时相较于基于本地差分隐私的贝叶斯分类方案，分类准确率更高，且时间性能更优。

（3） 在多个真实的数据集上对LDPBayes 方案进行实验和评估，结果表明LDPBayes 方案相比与其他方案在分类准确率上均有不同程度的提高，同时避免了由于采样带来的统计结果误差。 在相同大小的训练集上，由于频数预测算法对数据隐私处理的时间效率更高，可缩短构建贝叶斯分类器的时间，并且通信代价更小。

1 相关工作

2006 年， Dwork 首次提出了差分隐私（Differential Privacy，DP）的保护框架［2］，作为一种可严格证明的隐私保护模型，严格定义了隐私保护的强度，任意一条记录的添加或删除都不会影响最终的查询结果。 2009 年，Mcsherry 等［14］提出一套提供差分隐私保护的应用框架 PINQ （Privacy Integrated Queries）。 差分隐私在假设攻击者具有任意背景知识和计算能力的前提下仍提供可证明的隐私保护，从而解决了层出不穷的新型攻击方式所带来的隐患；同时建立了隐私保护的严格证明框架和属性定量关系。 由于这些优势，专家们将差分隐私扩展到数据挖掘领域，从而避免隐私数据的泄露，主要的应用场景有回归、分类、聚类分析和频繁项挖掘等［15］。 其中，分类器作为分类分析中一个具体实现，引入差分隐私算法后在实现分类任务的同时为保护数据提供者的隐私提供了解决方案。 Zhang等［16］提出了一种满足差分隐私的逻辑回归方案，将损失函数的各项系数加入噪声从而保证其满足差分隐私。 Jagannathan 等［17］应用随机决策树算法，提出了完全访问模式下的差分隐私保护随机决策树分类器构建方法。 Rubinstein 等［18］探讨了在保护训练数据隐私的同时发布支持向量机（SVM）分类器。

2013 年，Vaidya 等［6］首次将差分隐私的保护机制引入到朴素贝叶斯分类算法，通过计算分类器的全局灵敏度来添加拉普拉斯噪声［19］，从而保证分类器满足差分隐私，然而该算法仅仅假设了连续属性服从高斯分布的条件，同时采用全局灵敏度可能存在的数据集中个人对结果的影响较大导致添加到输出中噪声较高的问题。 2015 年，Huai 等［7］将加密技术和差分隐私相结合，在分布式环境下能够以较低的计算成本和通信代价对贝叶斯分类器进行隐私保护。 2018 年，Li 等［8］提出了一种多数据源差分隐私贝叶斯分类算法，使得训练者在不同数据所有者共同提供的数据集上训练朴素贝叶斯分类器，因此无需一个可信的收集器。 2019 年，Tang 等［9］对离散属性的频数中加入拉普拉斯噪声，对连续属性假设了其遵循高斯分布、拉普拉斯分布和对数正态分布的情况下，将均值和标准差参数加入拉普拉斯噪声，计算先验概率和条件概率，从而构建满足差分隐私的贝叶斯分类器。 2020 年，Tang 等［10］提出了基于小波变换的差分隐私保护贝叶斯分类方案，对原始数据进行小波变换，得到指定分解层的非零近似系数，从而达到数据降维的目的，再将拉普拉斯噪声添加到降维数据集中，对噪声数据集执行贝叶斯分类。2021 年，Zafarani 等［11］针对文献［6］可能带来过高噪声的问题，将连续属性采用了平滑灵敏度，离散属性仍然采用了全局灵敏度，并使用柯西分布的噪声对参数扰动后再构建贝叶斯分类器，相较于文献［6］能够显著提高分类准确率，但也带来了更高的计算成本。

2011 年，本地化差分隐私（Local Differential Privacy，LDP）［3］在中心化差分隐私的基础上首次提出，将数据的扰动处理从服务器端转移到了客户端，从而消除了不可信第三方服务器带来的隐私泄露威胁。 在中心化差分隐私中，用户之间通常不存在交互关系，而收集用户数据的聚合器要求对于用户是可信任的，这使得在实际应用场景中难以落地。 而本地化差分隐私中，用户的隐私化处理从服务器端转移到了客户端，用户将数据编码成特定的格式，经过正向或负向的扰动，再发送给不可信任的聚合器，聚合器收到的每条用户信息几乎是全噪声的，这保证了用户数据在服务器端不会被泄露。 扰动后的大量用户信息通过聚合后解码估计和校正，从而收集到一个有效、无偏的统计结果，通常是频数或者均值。

2020 年，Yilmaz 等［12］首次将本地差分隐私和朴素贝叶斯分类算法相结合，应用了多个频率预测算法收集扰动数据，将扰动数据聚合后根据统计信息计算出先验概率和条件概率从而构建分类器；算法适用于离散和连续属性，但扰动算法带来的计算开销 较 高。 2021 年，Xue 等［13］基 于k⁃Subset 算法［20］设计了LDP 下的联合分布算法，将该算法应用于计算贝叶斯分类中的条件概率，该方案能有效降低通信代价，但当属性数据较多时则会带来采样误差。

2 预备知识

2.1 本地化差分隐私

定义1ε⁃本地差分隐私［3］：给定一个隐私算法M，定义域Dom（M）和值域Ran（M），在算法M中任 意 两 条 记 录x和x′， （x∈Dom（M），x′ ∈Dom（M）），得到相同的输出结果y（y∈Ran（M））满足以下不等式，则算法M满足ε⁃本地差分隐私。

Pr［M（x）＝y］ ≤eε× Pr［M（x′）＝y］ （1）

式中，Pr［·］ 表示事件发生的概率，参数ε表示隐私预算，隐私预算ε越小，输出相同结果的概率越大，说明算法M的隐私保护程度越高。

定理1 和定理2 给出了本地差分隐私的两个组合特性。

2.2 贝叶斯分类的相关理论

贝叶斯分类算法是基于统计学原理的一个分类算法。 采用了属性条件独立性假设，即对于已知类别，假设所有属性之间相互独立。

式中，N表示训练集D中所有可能的标签类别数，Nt表示第t个属性可能的取值数。

3 基于本地差分隐私的贝叶斯分类方案LDPBayes

3.1 方案概述

本系统包含一个第三方服务器和m个用户，即数据提供者，用户集U＝｛u1，u2，…，um｝。 设系统属性集A＝｛A0，A1，…，Ah－1｝，其中属性数量｜A ｜＝h，每种属性Aj对应的属性值数为nj。 类标签集C，其中类标签数量｜C ｜＝k。 每个用户ui向服务器提供个人数据，用于分类器的训练。ui的个人数据包括了h个属性值的集合｛Ri，0，Ri，1，…，Ri，h－1｝ 和1个类标签Ci。 本文主要考虑属性值是离散的情况，对于连续属性，可使用对连续数据离散化处理中常规的等宽法，将取值范围划分成等宽的多个区间，为每个区间设置一个对应的属性值，从而将连续变量转换成多个离散值。

图1 LDPBayes 分类方案的框架

3.2 LDPbayes⁃FO 频数预测算法

LDPbayes⁃FO 频数预测算法共分为编码、扰动、聚合3 个步骤。 其中，用户端执行前两个步骤，将数据完成编码后利用随机化响应机制扰动，扰动后的数据发送给服务器。 服务器执行第三个步骤，对扰动的数据估计和校正还原。

3.2.1 编码

用户首先将向服务器提供用于分类器训练的个人数据，包括了类标签和属性值，并编码成整数，目的是减少通信代价并降低算法耦合性。 具体编码方式如下：

定理4 得证。

聚合后，估计值c～（v） 中可能会出现负数的情况，为满足非负性，将这些值置为0，并对所有的频数预测做归一化处理即可［23］。

3.3 LDPBayes 贝叶斯分类方案

LDPBayes 贝叶斯分类方案包括训练和测试两个部分。 训练阶段通过计算类标签的概率和属性的条件概率来构建分类器；在测试阶段，可对已知属性值但未知类别的数据分类和预测。

（1） 训练阶段

①计算类标签的概率

4 性能分析和实验仿真

4.1 方案性能比较

本方案与其他基于差分隐私的贝叶斯分类方案性能比较结果如表1 所示。 其中文献［6－8］方案是采用传统的差分隐私技术，即中心化差分隐私，需要可信的第三方数据收集者集中收集数据，再进行隐私保护。 其中，文献［6］的方案在假设连续属性满足高斯分布的情况下，通过计算全局敏感度来添加拉普拉斯噪声，使其满足差分隐私模型；然而该方案面向单一数据源，如果没有可信任的聚合器，则不能在分布式环境中直接使用它。 文献［7］的方案中考虑到来自多个数据源的训练样本，各参与方首先对自己的数据添加适当的噪声，然后基于安全多方计算（Secure Multi⁃Party Computation，SMPC）理论设计安全求和协议，得到所有参与方的噪声数据的全局统计求和查询结果；该方案能够抵御不安全的通信信道造成的窃听攻击，在分布式的场景中保证了多个参与方的数据安全；然而方案将数据的统计信息设置为公开，因此内部攻击者很容易知道所持有的样本是否包含特定的值。 文献［8］的方案中，使用同 态 加 密（Homomorphic Encryption， HE） 中 的Paillier 算法对提供者的数据进行隐私保护，在服务器端的聚合器中通过拉普拉斯机制对数据集添加噪声使得模型满足差分隐私的定义，能够保证数据统计信息既不被外部对手泄露，也不对内部对手泄露；然而同态加密所带来的计算开销较高。 与文献［6－8］相比，本方案LDPBayes 是基于本地化差分隐私技术，将隐私化的处理从服务器端转移到了用户本地，服务器端收集到的每条用户信息几乎是全噪声的，这保证了用户数据不会在服务器端被泄露，因此隐私保护的程度更高。

表1 方案性能对比

文献［12］方案和本方案LDPBayes 都是基于本地化差分隐私技术，可以在不需要信任第三方数据收集者的情况下，在本地环境下对个人敏感数据加噪实现隐私保护。 其中文献［13］提出一个满足本地差分隐私的计算联合分布算法JESS，并将其应用于NBC 条件概率的计算，该方案在每次计算中需随机采样原始用户数据的一个属性值，当属性较多时，采样率过低可能导致统计结果带来较大的采样误差。 相比之下LDPBayes 无需采样，从而减少了采样带来了统计效率低下和估计误差较高的问题。

文献［12］ 利 用DE（Direct Encoding）、OUE（Optimized Unary Encoding）等LDP 的频数预测算法［24］与NBC 相结合进行设计。 在DE 算法中，对于含有n个元素的输入集合si， 隐私预算ε将平均分成n份，每一份隐私预算ε／n作用到集合si中的每一个元素。 而现有的研究工作［25－27］表明，简单地将隐私预算均分的方法不能完全利用好隐私预算，可能会在扰动过程中带来大量的噪声，从而降低数据统计的精确度。 而在LDPbayes⁃FO 算法中，当给定隐私预算ε，将待扰动的集合si作为一个整体，经过基于指数机制设计的扰动算法后输出集合ti， 通过设定的效用函数决定集合ti的输出概率，不再将隐私预算ε简单地均分给集合ti中的单个元素，相较于直接均分隐私预算的方法降低了扰动过程中带来的噪声，从而提高了在数据统计中的效用。

在OUE 算法中，需将隐私数据v∈D（D为输入集，输入集中共有l种不同的输入值）构建成长度为l，第v位为1，其余位为0 的二进制的向量V＝［0，…，1，…，0］，需对向量中每一位进行随机扰动，因此会带来较高的通信代价。 相比之下，LDPBayes 无需对输入集的元素重新构建成二进制向量，因此能够有效降低通信代价，算法的时间开销也会相应减少。

4.2 方案实验结果及分析

（1） 实验配置和数据集

实验环境为Intel（R） Core（TM） i7⁃4770HQ，2.20 GHz、16 GB 内存、Windows 10 操作系统。 采用了UCI （University of California， Irvine）提供的机器学习库中的Nursery、Adult、Bank 数据集。 其中，Nursery 中包含了托儿所信息，用于预测托儿所的排名等级；Adult 中包含了1994 年美国人口普查的个体信息，用于预测个人的年收入情况；Bank 中记录了葡萄牙银行机构的电话营销活动，用于预测客户是否会订阅定期存款。 数据集的参数如表2 所示。

表2 数据集的信息描述

实验中，Adult 数据集样本中存在缺失数据，由于缺失数据占总样本的比例极小，因此直接采用删除法［28］处理。 为防止零概率问题，即某个量x在训练集中没有出现过，会导致整个实例的概率结果为0，因此，在实验中需要引入拉普拉斯平滑机制解决零概率问题。

（2） 分类效用的比较

目前和本方案相同，采用本地化差分隐私的贝叶斯方案有文献［12－13］方案。 其中文献［13］当属性较多时，采样率过低可能导致统计结果带来较大的采样误差。 相比之下LDPBayes 无需采样，从而减少了采样带来了统计效率低下和估计误差较高的问题。 因此，本文在实验部分没有与文献［13］方案进行比较，只与文献［12］⁃DE、文献［12］⁃OUE 进行比较。

图2 展示了实验中在3 个数据集上不同ε取值的情况下各扰动方案的准确率，ε取值分别为0.2、0.4、0.6、0.8、1、1.5、2、3。

图2 SNB、［12］⁃DE、［12］⁃OUE 和LDPBayes在Adult、Nursery 和Bank 数据集上的分类准确率，其中ε ＝｛0.2，0.4，0.6，0.8，1，1.5，2，3｝

图2 中水平线SNB 表示基准正确率，即分类器在没有扰动情况下的准确率。 在相同ε取值的情况下，LDPBayes 相较于［12］⁃DE 和［12］⁃OUE 的分类准确率更高。 随着ε的增大，隐私保护程度降低，同时数据可用性也提高，使得分类准确率也逐步提高。例如将隐私预算设置成ε＝3 时，在3 个数据集上均有良好的分类效应，分类准确率的结果更加接近SNB。 本文的方案LDPBayes 相较于文献［12］⁃DE和文献［12］⁃OUE 能在分类效用上得到提高，得益于频数预测算法LDPbayes⁃FO 的设计，在扰动机制中，扰动后的输出概率由指数机制的效用函数决定，设定的效用函数对每一种输出结果计算出一个效用分值，效用分值越高则输出概率越高，从而保证数据统计的质量，有效提高数据统计结果的可用性，体现在贝叶斯分类中能使得分类准确率提高。 同时，在Bank 数 据 集 上 采 用［12］⁃DE、 ［12］⁃OUE 和LDPBayes 方案的准确率都接近SNB，得益于Bank数据集的规模较大，因此统计结果更接近真实值，算法的实用性也越高。

（3） 隐私保护程度的比较

差分隐私建立了隐私保护的严格证明框架和数学定量关系，不同参数处理下的数据集所提供的隐私保护程度可通过隐私预算ε量化。 当隐私预算ε一致时，LDPBayes 与文献［12－13］的方案所达到的隐私保护程度也一致。 隐私预算ε越小，隐私保护的程度越高，而数据的可用性越低。

而相较于中心化差分隐私需要一个可信的第三方数据收集者，需要更为苛刻的安全假设前提，本地化差分隐私将隐私化处理转移到了每个用户的终端，从而消除了不可信第三方服务器带来的隐私泄露的威胁。 在实验中将LDPBayes 与文献［6］⁃DPNBC 方案进行了对比。 文献［6］⁃DPNBC 采用了传统的中心化差分隐私的技术，敏感度依赖于训练样本的总数，因此在实验中以Adult 数据集为例，对该数据集重新进行了整合，训练样本数m设定为5 000、10 000、50 000 和100 000，同时隐私预算ε取值分别选择了0.005、0.01、0.05、0.1、0.5、1。

图3 展示了在不同训练样本数下，不同的ε取值下两种方案的准确率。 在隐私预算ε较小的情况下，由于隐私保护的程度较高，数据可用性较低，因此LDPBayes 和文献［6］⁃DPNBC 的准确率均较低，并且LDPBayes 的准确率相比文献［6］⁃DPNBC 更低，这是由于文献［6］⁃DPNBC 采用了传统的中心化差分隐私的技术，而LDPBayes 是基于本地化差分隐私，无需一个可信的第三方收集器，因此为达到和中心化差分隐私相似级别的隐私保护程度则需要引入更大的噪声。 而随着隐私预算ε的增加，LDPBayes 和 文 献［6］⁃DPNBC 的 准 确 率 均 接 近SNB，这是隐私保护的程度降低，数据的可用性提高，因此准确率逐渐增加并趋于稳定，分类结果更加接近真实结果。 当给定隐私预算较高时，LDPBayes方案的分类效用较高，在实用性和安全性上能够取得较好的平衡。

图3 LDPBayes 和文献［6］⁃DPNBC 在训练数据集大小m ＝｛100 000，50 000，10 000，5 000｝ 上的分类准确率，其中ε ＝｛0.005，0.01，0.05，0.1，0.5，1｝

（4） 时间性能比较

相较于普通的数据挖掘算法，基于本地差分隐私保护下的数据挖掘算法更为复杂，因此在关注数据挖掘任务性能的同时，也需关注带来的时间与空间的代价。

实验中，在隐私保护参数一致的情况下，将Adult 训练集大小分别取4 000、8 000、12 000、16 000、20 000、24 000、28 000 和32 000 训练，并用相同大小的测试集测试。 由于运行时间具有不确定性，取运行30 次的时间累加和。 在LDPBayes 中， LDPbayes⁃FO 算法仅需调用一次即可得到一组扰动的输出数据。 当应用DE 算法扰动时，集合数据中的每一个元素都需调用一次算法后才能得到全部的扰动数据。 对于OUE 算法，由于编码方式需将每一个数转换成二进制向量，而向量的每一位都需扰动，因此带来的时间和空间开销都随着编码个数的增大而剧增。 图4为对比结果，在不同训练集大小下，LDPBayes 方案 的 运 行 时 间 均 小 于 文 献［12］⁃DE 和 文献［12］⁃OUE 的方案，时间开销小于其他方案。

图4 在不同大小数据集上的时间性能

5 结束语

本文基于本地差分隐私设计了一个频数预测算法LDPbayes⁃FO，并设计了满足本地差分隐私的朴素贝叶斯分类算法LDPBayes。 在频数预测算法LDPbayes⁃FO 中，编码时保留了属性值和类标签之间的相关性，将原始数据编码进一个有序定长的集合。 扰动算法基于指数机制设计，其中效用函数被定义为输入集合和输出集合之间是否有交集，扰动输出的概率由效用函数决定，能有效提高数据收集的效用。 服务器端对编码值的频数聚合后可计算得到类标签概率和条件概率，从而训练成贝叶斯分类器。 实验结果表明，本文的算法在隐私保护水平一致的情况下，能够提升发布数据的可用性，同时相较于已有的相关工作，该算法的时间性能更优。 受朴素贝叶斯分类算法的影响，只能处理属性之间相互独立的分类数据，今后将研究支持更复杂的本地差分隐私的分类方案。