差分隐私保护约束下集成分类算法的研究

贾俊杰,邱万勇*,马慧芳,2

1西北师范大学计算机科学与工程学院 兰州 中国 730070

2桂林电子科技大学 广西可信软件重点实验室 桂林 中国 541004

1 引言

互联网“颠覆性”的发展,使各种信息系统采集且积累了丰富的数据。机器学习即对海量的数据进行分析以获得各类可用的数据模型[1]。而数据集中通常都含有私有或敏感信息,如医疗诊断信息、电子商务购物信息等,由此引发人们对自身隐私泄露的担忧。

隐私保护技术[2-4]能有效处理数据模型发布当中个人隐私信息泄露问题。匿名技术依赖于攻击者的背景知识,所提供的隐私是“无法保证的”。Dwork等人[5]提出差分隐私定义,解决了传统隐私保护模型的两个缺陷: 1)差分隐私保护与背景知识无关; 2)差分隐私建立在严格的数学基础上,对隐私保护提供了量化的评估方法。差分隐私的核心概念涵盖了从隐私保护领域到数据科学(如机器学习、数据挖掘、统计和学习理论)等领域的一系列研究[6-10]。

针对机器学习中数据模型发布、分析时的个人隐私泄露问题,在特定算法中引入差分隐私,保护数据私有或敏感信息的同时,使得发布的模型发挥其最大的可用性[7-8]。差分隐私数据分析的基本任务是将现有的非隐私算法扩展到差分隐私算法。在集中学习模式下,基于数据分析的差分隐私模型研究中,由于模型本身会泄露训练数据中个体属性或敏感信息。对此,需设计相应扰动机制使模型训练过程实现差分隐私保护。一般为输入扰动、目标扰动、梯度扰动和输出扰动等[8,11]。

差分隐私已被广泛应用于传统机器学习中,如逻辑回归、支持向量机以及决策树[12-14]等分类模型,并能较好的平衡可用性和隐私性。本文以决策树作为基分类器进行差分隐私约束下的集成分类模型研究,表1汇总了差分隐私约束下基于决策树分类方法的相关研究[12-18]。在集成学习中,Patil和Singh[15]将差分隐私引入随机森林并提出 DiffPRF算法,其使用ID3作为基分类器且只能处理离散属性。穆海蓉等人[16]对其改进并提出DiffPRFs算法,引入指数机制处理连续属性。差分隐私保护下的集成分类模型 DP-AdaBoost[18]只能处理离散属性的ID3决策树,算法以决策树桩作为基分类器并在叶结点添加相应噪声,没有考虑树深度与隐私保护下分类模型的关系。

表1 差分隐私约束下基于决策树分类方法对比Table 1 Comparison of classification methods based on decision tree under differential privacy constraints

本文在分析已有差分隐私保护决策树相关研究的基础上构建CART提升树,提出一种基于差分隐私保护的 AdaBoost集成分类模型 CARTDPsAdaBoost(CART-Differential Privacy structure of AdaBoost),在树深度增加而模型复杂度增加的情况下,分析不同隐私保护水平对集成模型分类性能的影响,通过合理分配利用隐私预算,设计分类性能良好且安全有效的隐私保护集成模型。

本文的主要贡献包括3个方面:

1) 算法在Boosting过程中结合Bagging的思想和属性扰动中的随机子空间算法,增加基分类器多样性的同时使迭代过程中每个元组被选中的概率由它的权重决定。若添加噪声大小小于样本和特征采样的随机性,噪声对隐私的影响微乎其微。该方法对大数据集、高维度属性数据分类效率较好。

2) 算法构建CART提升树作为集成学习的基分类器,在建树过程中利用指数机制选择连续特征分裂点,利用Gini指数选择最佳分裂特征,并保证隐私预算的合理分配与利用。

3) 算法无需对数据进行离散化预处理,降低了分类系统性能的消耗。在满足差分隐私保护的需求下,分析最佳参数域,保持较高分类准确率,保证分类模型的隐私性。

本文第 2节描述差分隐私理论基础和改进后的CART提升树算法以及集成学习AdaBoost理论背景; 接下来,第 3节给出本文算法框架,并详细讨论提出的CART-DPsAdaBoost算法,对其隐私性进行合理证明与分析; 第4节提供完整的检验和讨论结果,这些结果来自两个标准数据集上的一系列实验分析; 文章结论部分总结了该方法的优点和局限性,并期待进一步的研究。

2 定义与理论基础

2.1 差分隐私理论基础

2.1.1 差分隐私定义

定义1.ε-差分隐私[5-6]。给定相邻数据集D和D′至多相差一条记录,即设有随机机制M,Range(M )为M的值域,M的任意输出结果 O (O ∊ Range(M ))若满足下列不等式,则M满足ε-差分隐私:

其中 P r[∙]表示隐私被披露的风险,隐私预算ε也称隐私保护水平指数。ε越小数据安全需求越高。

定义 2.全局敏感度[5-6]。对于任意满足的相邻数据集D和D′,给定查询函数f:D→Rd,函数 f的敏感度为:

2.1.2 噪声机制

定义 3.Laplace机制[5-6].给定任意函数f:D →Rd,表达式 K (D)的输出满足下列等式,则 K (D )满足ε-差分隐私。

Laplace机制通过Laplace分布产生的噪声,扰动真实输出值来实现差分隐私保护,Laplace机制仅适用于对数值结果的保护。对于非数值型数据,例如实体对象,McSherry等人[6,11]提出了指数机制。

定义 4.指数机制[5-6].给定一个效用函数q : (D × O ) → r (r ∊ R ange),函数 F (D ,q)满足下列等式,则 F (D ,q)满足ε-差分隐私。

其中输入为数据集D,输出为实体对象r,Δq是效用函数 q (D ,r)的全局敏感度。函数F以正比于的概率从Range中选择并输出r。

2.1.3 相关性质

性质 1.序列组合性[5-6]。设有算法M1,M2,∙ ∙∙,Mn其隐私预算分别为 ε1,ε2,∙ ∙ ∙,εn,对于同一数据集D,由这些算法构成的组合算法-差分隐私保护。

性质 2.并行组合性[5-6]。设有算法M1,M2,∙ ∙∙,Mn其 隐 私 预 算 分 别 为 ε1,ε2,∙ ∙∙,εn,对于不相交的数据集 D1,D2,∙ ∙∙,Dn,由这些算法构成的组合算法 M (M1( D1) ,M2(D2),∙ ∙∙,Mn(Dn))提供(m axεi)-差分隐私保护。

2.2 分类与回归树

构建CART提升树

CART(Classification and Regression Tree)分类与回归树[1,14]。本文以增加模型的多样性来提高基分类器一定程度的准确率,使基分类器“好而不同”,对此引入样本扰动和特征扰动两类随机性方案,即在集成算法迭代的过程中引入自适应采样方案,以及在特征选择中使用随机子空间算法来构建 CART提升树。穆海蓉等人[16]提出一种基于差分隐私的随机森林算法 DiffPRFs,在树的构建过程中采用指数机制选择分裂点和分裂特征,并根据Laplace机制添加噪声。该算法虽无需对数据进行离散化预处理,但每次迭代需调用两次指数机制,导致大量隐私预算消耗。

本文以改进后的 CART提升树作为集成学习的基分类器。对于连续特征使用指数机制选择分裂点,使用Gini指数选择分裂特征,迭代中只需调用一次指数机制,整个算法保证了隐私预算的充分利用。

假设有样本集 D (i),样本数N,属性集合Λ( A ∊Λ),类标签集 Y (∀ y∊Y ) ,分类类别数k,实体对象r,记录属于类别 k (k ∊K ) 的概率Prk,概率分布的 Gini值为 Gini(Pr)=则本文 CART提升树的构建如算法1所示。

?

~ ： ,类计数加噪D PartitionD y Y y y y =(i ,∀ ∊ =[]i )N NoisyCountD y =;6.ELSE节点未达到中止条件:THEN划分当前分裂节点,添加噪声量为( )( )y■ ■■ ■■max ,Laplace 12 ti■ ■,噪声量为( )( )ω ε′■Laplace ti ■ ■■ ■′max ,;■ω ε■7.IF 子空间Λ包含n个连续属性,执行步骤8;8.( )ε ′′′= +ε 2n1 9.用以下概率选择每个连续属性分裂点:exp ,2■qDA R q ■′( )■■Δi ■i ■∑i i i exp ,2′′■■ε ε′qDA R q ■ Δ( )■■■qDA为效用性函数,Δq为效用性函数的全局敏感度,/*其中 ( ),i R为区间集合的大i Di划分为两个子集 ()小*/10.END IF 11.将数据集 ()l D i;12.建立左右子树:r Di和()t Build DPTreeDiΛε d l =_(l (),,,+1 Dl )t Build DPTreeD iΛε d r=_(r (),,,+1 Dr )13.END IF 14.UNTIL节点达到中止条件即全部记录标签一致;达到最大深度d;隐私预算耗尽;15.RETURN ()g x t

2.3 集成学习之AdaBoost

AdaBoost[1,19]核心思想是针对同一数据分布将逐步强化生成的多个弱分类器进行集成,最终构成一个分类效果较好的强分类器。而强化的过程即算法核心步骤如下所述: 给定训练集,初始化样本分布,调用弱学习算法获得基分类器,根据其误差率调整训练样本权重。基于改变的样本分布,经过多次迭代,得到一组具有互补性的基分类器并将其线性组合成强分类器,以提高集成模型的准确性和稳定性。具体如算法2所示。

算法2.AdaBoost输入: ( )( ) ( )｛｝1 1 2 2,,,,,,n n D xy xy xy=∙∙∙~;基学习算法L;训练轮数T~;1.初始化样本权重分布: ()1 1 Dx=n~ ;2.FOR t=1 TO T~ DO 3.调用算法L生成基分类器: ( ),t t g DD= ~~~ L ;4.估计g~t的误差: ( () )t t t i xD P g x y τ= ≠~~ ~ ;5.IF 0.5 tτ﹥THEN 6.break;7.END IF 8.确定g~t的权重:~1 1ln 2 t t t α τ■ ■-τ=■■■ ■;9.更新样本分布:() ()( ) ()() ()() ()( )exp ,if exp ,if expt t t i t t t i t t ti t t D x g x y D x g x y Z D x yg x Z α α α+1■ - == ×■ ≠■=~~ ~~~ ~~ ~ ~其中Zt是规范化因子,以确保Dt+1~ 是一个分布;10.END FOR输出: () ()( )sign T t t t=1 Gx αgx= ∑~~~~

3 CART-DPsAdaBoost算法

发布最终的集成分类模型,要确保基分类器即决策树的结构不被泄露,因为树结构含有核心的分类规则和结果。假设数据分析者对数据集有完全访问的权限,则可以在基分类器的生成过程加入噪声。即在构建 CART提升树过程中向分裂节点及叶结点添加相应的Laplace机制噪声,并合理分配隐私预算来控制噪声量大小,最后进行隐私性的合理证明和适用性分析,以完善算法性能评估,分析隐私保护与模型效用之间的平衡。

3.1 算法与模型

给定算法的迭代次数为T,总的隐私预算为pε,每迭代一次生成新的基分类器。

步骤1,初始化数据样本权重分布。

步骤2,递归的使用采样策略,并根据权值分布找出最大的权重值作为敏感度参数。调用算法1在生成基分类器的过程中,根据噪声公式计算每个分裂节点和叶结点所需的噪声值并加入到基分类器中,得到满足差分隐私的基分类器。

步骤3,对生成的基分类器即决策树进行剪枝操作,计算被剪枝子树的隐私预算总量,并将其添加到被剪枝子树的父节点中。

步骤4,计算错误分类的数据比例,并根据误差率计算该基分类器在总体分类器中对应的权重系数。

步骤5,依据误差率更新数据样本的权值分布。

步骤6,判断当前迭代次数是否已满足设定值,若满足则终止,否则执行下一步。

步骤7,返回步骤2,继续构建新的基分类器。

步骤8,将所得到的基分类器进行线性组合,得到最终满足差分隐私保护的集成分类器。

通过上述步骤生成的强分类器即为带差分隐私保护的集成分类算法的分类模型,可以直接发布给数据挖掘工作者而不用担心隐私的泄露。

算法3.CART-DPsAdaBoost输入: ( )( ) ( )｛｝1 1 2 2,,,,,,n n D xy xy xy=∙∙∙ ;i x∊Λ; ｛ ｝1,1 i y∊-;迭代次数T;隐私预算pε;输出: 满足pε-差分隐私保护的集成分类器()Gx;1.初始化权重分布: ()[ ]1 1,1,D i i n n=∊ ;2.损失函数:(() ) ()( ),,exp i i Egx yi ygx= - ;3.ε()logα p c t T ε= -4.FOR t=1 TO T DO 5.从D中采样选取大小为D的训练集()Di;6.调用算法1生成基分类器 ()t g x() (() )_,,,t c g x Build DPTreeDiΛεd;=7.对生成的决策树进行剪枝:() (())_t t g x CART Prungx′ = ;8.计算被剪枝子树的隐私预算总量,并将其添加到被剪枝的子树的父节点中;

9.计算 ()t t t i i τ ω ■ ■′=;10.IF 0.5 t∑g′x的误差率:() () [ ],1,iIg x y i n≠ ∊■■tτ﹥THEN 11.break;12.END IF 13.计算 ()g′x的权重系数:α τ■ ■=■■■ ■1-τt t t 1ln 2;t 14.更新样本权重分布:() () ()Di yg x D i Z tit i t t t exp(-α ′)+1=其中 Zt是规范化因子 ()Z Diexp∙t t i=1=∑n( )α ′-ti t i ;15.END FOR 16.RETURN () ()yg (x)Gx αg x= ∑sign T( )t t t= ′1

通过 Laplace噪声机制对隐私信息进行保护,噪声量大小由隐私预算ε来控制.计算噪声时需考虑每一条记录权重值 ωt(i ),使得差分隐私噪声计算公式中函数敏感度动态变化[18],根据敏感度公式得出 Δ f = m ax ( ωt,i ),同时 Laplace机制噪声公式转化为 K (D)= f(x)+ (Laplace ( Δ f ε))d。算法中指数机制的效用函数使用Gini指数.最小化Gini指数等价于最大化 G iniΛ( D ),其敏感度 Δ qGini= 2 ,选择 Gini指数作为效用函数敏感度较低使得指数机制的效率有所增高[12]。本文预先指定迭代次数,在隐私预算分配中同时考虑每个弱分类器的权重值tα,即每个弱分类器分配到的预算为log(αt)。

3.2 分类

对新样本集中的每一条记录,应用最终的集成模型进行分类。最终分类结果是加入差分隐私噪声的每个基分类器结果与权重的乘积线性组合。基分类器的构建包含建树和剪枝两步骤。算法的集成分类器简化模型如图1所示。对新样本分类过程见算法4。

图1 差分隐私保护下的集成分类模型结构图Figure 1 Structure diagram of ensemble classification model under differential privacy protection

算法4.使用 ()Gx对新样本分类输入: 预测集ˆM;满足pε-差分隐私的集成

分类器 ()Gx输出: 预测集中样本的分类结果1.REPEAT 2.对每条待分类样本;3.FOR i=1 TO m DO 4.从当前树的根节点开始,根据当前节点类型,判断进入哪个子节点,直至到达叶子结点;5.得到当前树的预测结果与其权重值相乘;6.线性组合每棵树的结果: sign();7.END FOR 8.UNTIL到达叶子结点9.RETURN输出样本集ˆM的分类结果(ˆ)YM■ ■′■ ■■ ■∑T t t t αg x=1

通过本文算法构建满足隐私保护的集成分类器模型 G (x),可将该分类模型直接发布给数据挖掘工作者而不必担心数据集中的个体信息会被泄露。

3.3 算法的性能

隐私性

集成分类器生成过程中,预先定义了算法的迭代次数,故采用层次均分的方法[16-20]。首先将总的隐私预算pε平均分配给每一棵树基于Bagging思想采样的每棵树样本集有交集,根据差分隐私性质1,总的隐私预算为每棵树消耗预算的叠加。对于每一棵树将隐私预算平均分配到每一层由于每层节点样本之间不相交,根据差分隐私性质2,每个节点预算为用每个节点预算的一半来估计该节点实例数,之后判断是否到达终止条件,若满足则标记为叶结点并用另一半预算确定叶结点类计数。若当前节点有n个连续属性,则将另一半的预算均分为n+1份,用于选择每个连续属性的分裂点,每次指数机制消耗预算为,由序列组合性可知,多次指数机制消耗的预算为各次的叠加。

性质3.G (x)提供εp-差分隐私保护。

证明:

1) 对于每个连续属性有 ri种划分方法,ri被以指数机制选中的概率为其中 E (D ,ri)表示以 p (ri)为权重,则连续属性划分方案 ri以正比于 p (ri)E(D ,ri)的概率参与全局选择。

2) 对于离散属性使用 Gini指数划分,若属性A有v个值,则有个划分子集,以属性A划分所计算Gini指标值为:

其中N1、N2为不相交的子集,根据差分隐私性质1得。则Gini指数的差分隐私预算可根据性质2转化为:

根据差分隐私性质1,每棵树的隐私保护程度为:

因此,提供εc-差分隐私保护。

3) 对于集成分类模型 G (x),总的差分隐私预算满足:

因此,G (x)提供εp-差分隐私保护。得证。

4 实验结果与分析

4.1 实验数据

分类器训练、预测及数据预处理均使用python3.7实现,编辑器为 PyCharm。采用 UCI Machine Learning Repository中的Adult数据集设计对照实验,并在Census Income大规模、高维度数据集上验证算法的有效性。表2展示了相关数据集的基本信息。

表2 实验数据集Table 2 Experimental data set

Adult数据集包含6个连续属性、8个离散属性,类别属性为income lever,类别值为“<=50K”“>50K”;Adult_Train共 32561个元组,其中 70%作为训练集,30%作为测试集对训练模型进行剪枝操作;Adult_Predict为预测数据集其包含 16281个元组。Census Income共41个属性,其中8个数值属性,33个离散属性,Census Income_Train共 199523个元组,Census Income_Predict共99763个元组。为检验算法的有效性,设置ε= ( 0.05,0.1,0.25,0.5,0.75,1),决策树数量T=10,每棵树的深度d= ( 2 ,3,4,5,6),效用函数使用Gini指数,随机子空间算法中节点分裂时随机选取的特征数为k=5进行多组实验。

4.2 实验结果

1) 噪声对模型分类准确率的影响

图2 不同隐私水平下随树深度的增加分类准确率变化情况Figure 2 Changes in classification accuracy with increasing tree depth under different privacy levels

2) 树深度对模型分类准确率的影响

在隐私预算ε不变的情况下,随着树深度的增加,集成模型的准确率呈现上升趋势,这是因为树越深建立的规则越精确分类误差便降低。当然,随着树深度的增加,集成模型复杂度也随之增大,图2(a)在Adult数据集上当d﹥4时,模型已发生过拟合。实验以样本量与模型分类准确率变化情况做进一步解析。

3) 两个数据集上模型最优树深值的分析图3(a-f)实验中取值为ε=1,T=10。一个共同趋势是样本量较少时训练集模型准确率较高,测试集模型准确率低,随着样本量增加初始的过拟合现象逐渐好转,模型准确率逐渐趋于平稳。此外,两个数据集上随树深度的增加分类模型波动随之增大,这是由于模型越复杂所添加的噪声越多干扰越明显。Census Income数据集上的噪声干扰总体上较大,这是由于该数据集属性维度较高,建树相比较复杂从而使得噪声的影响更加显著。

如图3(a~c)在 Adult数据集上,模型准确率从35%上升到了 81%左右,当隐私预算越大即ε∊ [ 0.75,1]时越趋近于未加噪的模型准确率。对于Census Income高维度数据集从60%上升到了80%左右,由于该数据集特征数量较多模型更易于学习,400左右样本量已达到模型的最优值,准确率为80%左右。该算法在大规模、高维度数据集上表现更佳,时间效率更好,具有较好的数据扩展性。

图3 两个数据集上不同树深度的模型在训练集和测试集上样本量与模型准确率的关系Figure 3 The relationship between the sample size of the models with different tree depths on the training set and the test set and the accuracy of the model

综上实验进一步分析,在 Adult数据集上,模型分类准确率稳定在81%左右。而由图2(a)实验数据分析可知,当隐私预算不变时d=4模型准确率达到最佳,为0.8081813156441。在Census Income数据集上,准确率稳定在 80%左右,由图2(b)实验数据可知,d= 5 模型准确率达到最佳,为0.7993123634249。

4.2.1 评估

F-Measure[1,19]是用来评价分类器性能的常用指标,综合衡量模型的精准度和召回率,定义如下:

其中β为调节Precision和Recall相对重要性的系数(取1即为F1Score)。 F1Score的取值范围为[0,1],该值越大算法可用性越好。

同时使用 ROC[13-14,19](Receiver Operating Characteristic)曲线下的 AUC(Area Under Curve)值来评估分类器泛化性能。该值越大分类器泛化性能越高,AUC取值范围为[0,1]。两个数据集上实验结果如图4-5以及表3-4所示。

表3 随隐私水平ε的变化Precision,Recall, F1Scores值的变化情况Table 3 How Precision,Recall,and F1Scores vary withε

树深度设定为 d = ( 2 ,3,4,5,6),分配的隐私预算为 ε =(0.1,0.25,0.5,0.75,1)。图4(a~c)为 Adult数据集上的实验结果,图4(a)当d固定ε越大Precision值也随着增大。此外,如图4(a)(d)所示,Adult数据集上d=4时Precision最佳,Census Income数据集上d=5时Precision最佳。如图4(b)(e)所示为模型在数据集上的召回率变化情况,随着d的变化模型精准度和召回率互相影响,Precision值大时Recall较小,反之亦然。图4(c)(f)为F1Score值的变化情况,F1Score综合衡量了Precision和Recall的结果,ε≥ 0.25时,F1Score值在86%上下波动,模型的可用性较好。如图5(a) Adult数据集实验结果显示ε∊ [ 0.1,0.5]AUC变化波动较大,这是由于Adult数据集特征数量较少,调节隐私水平对AUC产生的扰动较大。而图5(b)所示在Census Income特征维度高的数据集上AUC表现较好。

图4 不同隐私水平下随树深度的增加Precision/Recall/F1Score值的变化情况Figure 4 The change of Precision/Recall/F1Score with the increase of tree depth at different privacy levels

4.2.2 对比

由于同类算法DP-AdaBoost是树深度为1的集成分类模型,相关对比实验设定ε=0.05,0.1,0.25,0.5,0.75,1,T=10,d=1,在不同隐私水平下,模型分类准确率比较结果如图5(c)所示。

表4 AUC性能对比Table 4 AUC performance comparison

图5 模型的ROC曲线部分图示以及同类算法对比Figure 5 Part of the model's ROC curve diagram and comparison of similar algorithms

当d=1时,相比 DP-AdaBoost同类算法旨在叶结点添加相应的噪声,本文算法在树的构建过程中对分裂节点和叶结点同时添加相应的 Laplace噪声,树深度较低时对模型分类性能影响较大,即以牺牲一定的模型准确率来换取更佳的数据隐私性。同时本文在研究不同树深度下隐私水平对分类模型的影响时,通过相关实验结果表明,算法在隐私保护策略下选择最优树深及隐私域时模型可以达到较好的分类效果。在分类树构建过程中消耗了一部分隐私预算用于处理连续特征,但无需对连续特征进行离散化预处理,一定程度上提高了分类效率。

5 结束语

在已有差分隐私决策树各类算法基础上,研究了差分隐私保护下 AdaBoost集成分类算法,保护数据隐私信息的同时保持集成模型较高的分类性能。实验表明,在集成当中提高了隐私预算的利用和算法的执行效率,能有效处理大规模、高维度数据分类问题。此外由于其可扩展性,该方法将可以适用于大数据环境.存在的不足之处: (1)隐私保护水平采用隐私预算ε定量分析,但实际算法和应用中的取值缺乏一个标准; (2)通常差分隐私假设数据记录相互独立,但在实际中数据库的记录可能存在关联性,会增加隐私泄露的风险。在接下来的工作中,会继续对算法做进一步优化,提升泛化性能。该研究的实验数据集和程序代码将在GitHub平台更新。

致 谢本课题得到国家自然科学基金项目(No.61967013),甘肃省高等学校创新能力提升项目(No.2019A-006),的资助,在此表示感谢。