多项式回归的差分隐私保护算法

谢雅琪，杨 庚,2

(1.南京邮电大学 计算机学院，江苏 南京 210046；2.江苏省大数据安全与智能处理重点实验室，江苏 南京 210023)

0 引 言

多项式回归是利用数理统计中的回归分析，来确定两种或两种以上变量间相互依赖的非线性定量关系的一种统计分析方法，一般应用于数据属性之间的关联呈非线性的情况，拥有比线性回归更加广泛的应用场合，在数据挖掘领域中通常使用它对数据进行预测。

挖掘的数据集包含一些敏感属性，在数据挖掘过程和数据发布中，如不加保护会引起隐私泄露[1]。在回归分析中，常用的隐私保护算法有几种类型：匿名算法、数据加密和数据扰动[2]等。匿名算法中，k-匿名算法使用较为广泛；数据加密算法的研究中，常用的有同态加密[3]、安全多方计算[4]等；此外还有数据泛化[5]。

差分隐私(Differential Privacy，DP)[6]属于数据扰动算法，它以数学理论为支撑，为数据的隐私保护提供了有力手段[7]。DP通过对数据集或者查询函数添加噪声等方式实现隐私保护。DP最为基础的两个机制为拉普拉斯机制和指数机制[8]，分别应用于查询函数的输出是数值型和非数值型的情况，该文涉及的机制都是拉普拉斯机制。

在面向回归分析的差分隐私算法研究中，通常对数据集或查询函数加噪声。前者如Lei[9]提出的DPME算法，后者如函数扰动机制[10]。添加噪声的过程中，可以选择是否对代价函数进行敏感度分析。不做敏感度分析的情况下，可能会引入不必要的噪声；如果进行敏感度分析，相较于前者，能够减轻噪声添加过量影响可用性的问题[11]，具有代表性的算法是Zhang等[12]提出的FM(Function Mechanism)，现在许多研究者都在研究基于FM的改进算法[13-16]。

1 相关工作

2006年，Dwork提出了差分隐私的定义，它通过对数据集或者模型添加噪声实现隐私保护。相较于传统的隐私保护算法，差分隐私不仅拥有数学理论作为支撑，而且能够无视攻击者所拥有的知识背景，提供了有力的隐私保护。目前，差分隐私的机制仍在逐步完善中[17-18]。在差分隐私保护算法被提出后，面向回归分析领域的差分隐私算法研究在噪声添加机制方面主要分为了两类：直接对数据集添加噪声和对查询函数添加噪声。

早期面向回归分析领域的差分隐私研究集中在对数据集添加噪声方面，如Lei的DPME算法[9]，但这些算法不对数据集进行分析，直接对数据添加噪声，在数据集的维度较大时，会引入大量不必要的噪声影响数据集的可用性。

2011年，Chaudhuri等[10]提出了一种对回归模型的代价函数的系数添加噪声的差分隐私保护算法，并且对代价函数的敏感度进行了分析，进一步减少了噪声的添加量，提高了数据的可用性。在此基础上，Zhang等[12]提出了函数机制FM，该算法进一步提高了训练结果的精确性。Wang等[15]基于FM算法的思路，提出了DPC算法，主要为了应对模型逆向攻击(Model Inversion Attack)[19]，提高数据的安全性。

该文的主要贡献为：设计了三个面向多项式回归的差分隐私算法，通过多组实验衡量并比较它们在数据可用性方面的性能，并且优化了算法使其能用于高维度的数据集。

2 理论基础

2.1 多项式回归分析

多项式回归分析是根据自变量与因变量的依赖关系进行建模的统计分析方法,通常在自变量和因变量呈非线性关系时使用，如图1，是一个简单一元二次多项式回归的拟合结果，图中点对应每条数据(x,y)。

图1 简单多项式回归的拟合结果

多项式回归的拟合可以通过变量替换，将其转换成多元线性回归处理，通过如公式(2)的映射，将每个g(x)转化为新的自变量zi，就可以得到多元线性回归模型。

(1)

(2)

(3)

(4)

(5)

2.2 差分隐私保护技术

定义1(差分隐私[6])：当且仅当算法A的输入为两个邻近数据集D1和D2(最多只有一条记录有差别的两个数据集)且满足式(6)时，算法A满足ε-差分隐私。

Pr[A(D1)∈0]≤eε·Pr[A(D2)∈0]

(6)

其中，ε是可以任意设置的隐私预算，Pr[A(D1)∈0]代表输入为D1时，算法A的输出属于集合O的概率。

2.3 全局敏感度

定义2(全局敏感度)：假设有两个邻近数据集D和D',那么对于一个函数f：D→Rd，它的全局敏感度定义为：

(7)

3 面向多项式回归分析的差分隐私保护机制

3.1 多项式回归算法

(8)

再对式(8)利用最小二乘法求得ω*：

(9)

3.2 面向多项式回归分析的差分隐私保护算法

3.2.1 面向多项式回归的函数算法

面向多项式回归的函数算法(Functional Mechanism on Polynomial Regression)简称FM-on-PR。

(10)

FM-on-PR对回归模型的代价函数使用多项式逼近后转化为多项式，如式(11)：

根据式(4)和式(11)，可以将fD(ω)简化为fD(ω)=aω2+bω+c，对系数a,b,c各添加上服从Lap(Δf/)分布的噪声，如式(12)所示：

(12)

全局敏感度的推导与计算过程如下：

对于邻近数据集D和D'，以及它们的代价函数fD(ω)和fD'(ω)：

根据全局敏感度的定义(见定义2)有：

由此，可以得到全局敏感度Δ为：

(13)

算法1：FM-on-PR。

输入：数据集D，隐私预算，代价函数fD(ω)；

2：for each 1≤j≤Jdo

3： for eachφ∈Φjdo

5： end for

6：end for

由2.1节可知，因为多项式回归可以通过变量替换转为多元线性回归进行训练，因此任意多项式回归的代价函数最终都可以表示为式(4)的多元线性回归形式。

此外，根据推导，全局敏感度的公式(13)表明其只与数据集的维度有关，与代价函数是否为线性并无关系。因此全局敏感度的计算公式同样适用于转换为多元线性回归之后的多项式回归。由此达成了使用FM算法的前提条件，后续的几个算法同理。

3.2.2 面向多项式回归的不同系数扰动函数算法

面向多项式回归的不同系数扰动函数算法(Functional Mechanism with Different Perturbation of Coefficients on Polynomial Regression)简称DPC-on-PR。

定义Xs是包含了所有会泄露隐私的敏感属性xs的集合。在FM算法的基础上(见3.2.1)，对φ也进行划分：只要φ中有包含了任何一个Xs中的元素对应的系数ωs，就将其纳入集合Φs，否则纳入Φn中。对于Φs中的φ项，分给其相对较少隐私预算s， 而分给Φn的隐私预算n则相对更多。设s=γn，其中0<γ<1。给代价函数添加完噪声后，只需对添加过噪声的代价函数进行最优化求解，算法流程如下：

算法2：DPC-on-PR。

输入：数据集D，隐私预算，代价函数fD(ω)，隐私预算比率γ；

1：设置Φs={}，Φn={};

2：for each 1≤j≤Jdo

3： for eachφ∈Φjdo

4：ifφ不包括任意属于敏感集Xs中元素的ωs

5：then将φ添加至集合Φn；

6：else将φ添加至集合Φs；

7： end if

8： end for

9：end for

10：计算全局敏感度Δ(算法同(13))；

14：for each 1≤j≤Jdo

15： for eachφ∈Φjdo

16： ifφ∈Φnthen

18： else

20： end if

21： end for

22：end for

首先可以算出：

证毕。

3.2.3 面向多项式回归的差分隐私预算分配算法

面向多项式回归的差分隐私预算分配算法(Differentiated Privacy Budget Allocation on Polynomial Regression)简称DPBA-on-PR。

根据式(13)，可以得到代价函数fD(ω)的全局敏感度为ΔfD(ω)=2(2d+d2)。

随后，将fD(ω)(fD(ω)的表达式同式(4)形式)拆解开为2个单项式，分别为：

根据式(13)，同理可得gD(ω)和hD(ω)的全局敏感度分别为ΔgD(ω)=2d2,ΔhD(ω)=4d。

可以发现整个多项式的全局敏感度和两个单项式的全局敏感度满足如下关系：

ΔfD(ω)=2(2d+d2)=ΔgD(ω)+ΔhD(ω)

算法3：DPBA-on-PR。

输入：数据集D，隐私预算，代价函数fD(ω)；

1：计算gD(ω)的全局敏感度Δf1，hD(ω)的全局敏感度Δf2；

2：设gD(ω)的系数是a，hD(ω)的系数是b；

3：if Δf1>Δf2then

5：else

7：end if

算法流程中的参数β，是用来调节gD(ω)和hD(ω)的隐私预算分配比率的变量，其取值范围的端点(见上述算法流程中步骤4)分别对应着将总的隐私预算全部分配给gD(ω)和全部分配给hD(ω)。显然，gD(ω)相对于hD(ω)自然有较高的全局敏感度(式(13))，因此必须合理制定β的取值使得gD(ω)添加噪声规模较小。

在高维度的数据集中，根据全局敏感度的计算方法(式(13))，gD(ω)的全局敏感度Δf1更是远远高于Δf2的，因此为了保证训练结果的准确性，gD(ω)应该被分配到更多的隐私预算使得对其添加的噪声规模降低，根据算法3流程中的步骤4，β的取值就要增大。

表1总结了β为各个取值时，gD(ω)和hD(ω)被分配到的噪声服从的分布。

表1 β的取值以及gD(ω)和hD(ω)的噪声分布

(14)

最终β的取值范围为：

证明：如果给gD(ω)，hD(ω)分别分配隐私预算g，h，且设=h+g。根据FM机制中的相关证明(定理2)，这三个单独的代价函数又分别满足g-差分隐私，h-差分隐私。于是，由定理1差分隐私的串行组合性可知，ΔfD(ω)的算法满足-差分隐私。

4 实验与分析

4.1 实验环境

实验环境为Intel(R) Core(TM) i7-9750H CPU 2.60 GHz,16G内存。实验使用的数据集为：来自UCI的联合循环发电厂(CCPP)数据集、个人家庭用电(IHEPC)数据集和Kaggle上获取的diamond钻石价格预测数据集。属性如表2所示。

表2 实验中使用的数据集

为了验证所设计算法的可行性，在这三个数据集上依次使用该算法进行训练，通过训练结果的精确度来判断它们的可用性。此外，为了检测隐私预算对模型准确性的影响，对每个数据集也将以不同的隐私预算进行多次训练。由于噪声的影响，也会进行多次实验取结果的均值。

4.2 实验结果及其分析

4.2.1 隐私预算对拟合结果准确度的影响

回归分析有多种性能指标衡量其精确性，该文使用拟合优度(R2)来衡量训练模型的准确性，R2的取值不会超过1，越接近1表示训练结果的准确度越高，特别地，当R2<0时，表示拟合结果尚不如取数据集的平均值的精度高。

在多项式回归的阶数设置方面，经测试，对于CCPP数据集，将它们的阶数设置为3最佳；对于IHEPC数据集和Diamond数据集，设置为2最佳。

从图2可见，三个数据集的训练结果均遵循隐私预算越大，训练出的模型精确度越高的规律，并且当隐私预算足够大时，几个算法之间的精确度差距甚微，同时与无隐私保护的算法的精确度接近。

图2 在不同隐私预算下对三个数据集进行回归训练的结果

另一方面，无论基于哪个数据集的实验，结果都表明DPBA-on-PR算法拥有最高的精确度，其次是FM-on-PR算法，DPC-on-PR算法最次。由于DPC-on-PR算法提出的目的是为了加强FM-on-PR算法的数据安全性，它只对会泄露隐私的特征变量添加更多噪声，并考虑每个特征变量与输出的关联性，因此可能会对高敏感度的特征变量添加很多不必要的噪声，从而大大降低训练结果的准确性，因此精确性方面不如FM-on-PR算法。

4.2.2 DPBA-on-PR算法中β取值对训练精确度的影响

因为对该算法中隐私预算分配策略的优化是针对高维度的数据集，所以这部分实验中，选取维度较高的diamond数据集进行实验，经过数据集预处理后，它的原始维度d为9，将其多项式形式的目标函数转换为多元线性回归之后的维度d0达到了54。同样，衡量准确性的标准仍然是拟合优度R2。

图3是DPBA-on-PR算法取不同β值并在不同隐私预算下的训练结果，横坐标epsilon是隐私预算的取值，纵坐标是拟合优度R2；标签为value1的曲线中β取值均为value1=Δf1(即式(14)中的不等式上限)，在本实验中具体取值为5 832(计算公式参考表2)；标签为value2的曲线中的β取值为即式(14)中的不等式的中间项以及得出的β取值新上限)，在本实验中具体取值为5 771；标签为value3的曲线中的β的取值为即式(14)中的不等式下限)，在本实验中具体取值为5 621。

由于value1与value2的R2_score(即纵坐标值)差值和value2与value3的差值相差过大不便于比较，因此将比较结果分在了两张图表中。

图3 DPBA-on-PR算法中β取值对准确性的影响

图3(a)中，β取值为value1时，在=0.01和0.1的情况下，实验得到的R2_score均远远小于-1，而在此图中，value1代表的曲线在这两个取值上均以-1代替表示，仅代表在这两种情况下，训练结果不理想。结果看来，β取值为value2的训练精确度比value1时高很多，尤其在隐私预算较小时更明显。

图3(b)中，β取值为value3时，如3.2.3小节所述，此时的DPBA-on-PR算法就与FM-on-PR算法一致，β取值为value2的训练精确度比取值为value3时高，结合4.2.1的实验，这也证明了DPBA-on-PR算法的精确度性能是优于FM-on-DPBA的。

综上，在3.2.3节中β的取值策略是可行的。

5 结束语

该文研究并设计了三个面向多项式回归的差分隐私保护算法，并且理论证明了它们满足差分隐私性质；三个算法与无隐私保护的多项式算法的训练结果进行的比较，也证明了它们的可用性；此外经实验，得出了数据可用性最高的算法为DPBA-on-PR的结论。由于DPC-on-PR和DPBA-on-PR分别在数据安全性和数据可用性方面进行了改进，因此在实际应用中，可以根据需求来对两个算法进行选择。总体来说，面向多项式回归分析的差分隐私算法研究的重点是数据的安全性和可用性间平衡的问题，通常这方面研究的切入点是隐私预算的分配与全局敏感度的计算，目前，全局敏感度的计算也并没有达到相当精确的程度，因此，噪声的添加量仍有优化的余地，这也将是未来面向多项式回归的差分隐私保护算法研究的方向。