一种面向政务数据共享的本地化差分隐私方法

摘要

本发明涉及一种面向政务数据共享的本地化差分隐私方法，提出了基于本地化差分隐私的政务数据共享方法，该方法在CMS算法的基础上引入数据分箱思想，通过等宽分箱将数据记录分入更小的数据域范围内，形成BCS算法，从而克服了当前隐私保护算法在数据域较大且数据量较少时统计误差大的问题；之后将数据分箱思想延展应用至GRR算法中，形成BRR算法，也取得了明显的效果。为验证其有效性，将本发明改进的BCS和BRR算法分别与CMS和GRR算法在合成数据集和真实数据集上进行了对比分析，实验结果表明，本发明所提方法有效降低了统计误差，并在不同分布和数据域大小下提升了其效用性，具有较高的推广应用价值。

权利要求

1.一种面向政务数据共享的本地化差分隐私方法，其特征在于，该方法在CMS算法的基础上引入数据分箱思想，通过等宽分箱将数据记录分入与原始数据域相比更小的数据域范围内，并构造用于聚合的计数草图矩阵来降低时空复杂度，以克服当前隐私保护算法在数据分布稀疏处统计误差大的问题；

在数据提供方设计本地扰动器，用来扰动原始数据：首先根据敏感属性列的值的域大小对数据进行分箱，对于箱中的每一条数据，本地扰动器均选择一个随机哈希函数对其进行编码得到一个向量，并对该向量进行扰动；随后，将包含所选哈希函数索引和扰动向量的报告发送到数据需求方；

在数据需求方设计聚合器，当从数据提供方接收到所有扰动报告和相关参数后，数据需求方将通过聚合器对它们进行聚合，聚合私有化数据的数据结构是大小为k ⨯ m的计数草图矩阵，数据需求方通过对矩阵中k个哈希函数对应的计数进行平均，得到各属性值的频数估计，最后统计校正后生成可用的统计数据。

2.根据权利要求1所述的一种面向政务数据共享的本地化差分隐私方法，其特征在于，具体操作过程为：

S1、原始记录首先会通过随机选择的哈希函数进行编码，因此在数据提供方设计一组哈希函数H = {h1, h2,…，hk}，并规定H中的函数能够根据输入的数据输出一个不大于m的值，m为每一条数据记录中的敏感属性值d的初始化向量的长度，然后在数据提供方和数据需求方之间共享这组哈希函数；

S2、按照等宽分箱思想划分敏感属性值的域区间Z，Zi为划分后比原始数据域小的域区间；

S3、初始化一个集合V，用于存放后续得到的扰动报告，其中，Vi用来存放属于域区间Zi的数据记录的扰动报告；

S4、数据提供方依次对共享数据记录中的敏感属性值d进行扰动处理；

S5、数据需求方根据接收到的扰动报告和相关参数计算每个属性值的频数统计信息。

3.根据权利要求2所述的一种面向政务数据共享的本地化差分隐私方法，其特征在于，数据提供方的扰动处理过程为通过确保受扰动的数据服从本地化差分隐私来防止用户数据泄漏，具体为：

S41、为每一条数据记录中的敏感属性值d初始化一个长度为m的向量v，表示为v = {‑ m

1} ；

S42、在k范围内随机地选取数值 j，作为选择第j个哈希函数的索引，其中，hj(d)表示选择第j个函数对敏感属性值d取哈希，若hj(d) = 134，则将向量v的第134位赋值为1；

S43、将向量v的每一个比特位以  的概率进行随机翻转后生成新的向量Ѷ ，表示m

为Ѷ {‑1,1} ；

S44、将翻转后的向量Ѷ、哈希函数hj的索引j以及参数k、m、ε的值发送给数据需求方。

4.根据权利要求3所述的一种面向政务数据共享的本地化差分隐私方法，其特征在于，S5中，数据需求方在获取到数据提供方的扰动报告和相关参数后，数据需求方将使用相同的参数构造计数草图矩阵，通过计数草图矩阵，进而估计敏感属性值d的计数。

5.根据权利要求4所述的一种面向政务数据共享的本地化差分隐私方法，其特征在于，数据需求方具体操作为：

S51、初始化大小为k ⨯ m的全零矩阵M以构造计数草图矩阵，其中，k表示哈希函数的数目，m表示向量v的长度；

S52、处理每个扰动报告中的向量v并将其转化为向量x；

S53、对于每一个敏感属性值的扰动结果(x, j)，将向量x按位依次加到矩阵M的第j行，第j行代表选择了第j个哈希函数的记录项总和；

S54，数据需求方通过读取每一行 的值来计算这些估计的均值，从而获得无偏估计。

说明书

一种面向政务数据共享的本地化差分隐私方法

技术领域

[0001] 本专利申请属于隐私保护技术领域，更具体地说，是涉及一种面向政务数据共享的本地化差分隐私方法。

背景技术

[0002] 智慧政府需要利用数据以帮助其更准确更客观的做出决策。在各种数据中，统计数据以其概括性、及时性与服务性的特点被各领域广泛应用。智慧政府建设中，应当存在共
享统计数据这样一种业务需求。为了更合理化的决策，通常一个政府部门会根据业务需求
向其他部门共享某类数据记录，为本部门管理或服务决策提供辅助参考依据。政务数据共
享是指政府部门为了能够打破数据壁垒，充分发挥数据价值，依照法律法规等借助信息共
享平台或其他技术手段将信息或数据从一个政府部门转移到另一个部门的过程。政府数据
通常涉及大量个人、企业相关数据。但若在没有适当预防措施的情况下就共享政务数据，将
很容易推断出敏感信息，这一点可以从过去二十年中公开的数据泄露事件中得到证明，这
些事件包括马萨诸塞州公共健康记录的去匿名化、Netflix用户的去匿名化以及参与全基
因组协会研究的个人的去匿名化。

[0003] 现有研究使用隐私保护技术对政务数据中可能存在的敏感信息泄露进行了研究。当前的数据隐私保护技术大致可分为三类：基于匿名的隐私保护技术、基于加密的隐私保
护技术和基于差分隐私的隐私保护技术。基于匿名的隐私保护技术根据隐私数据类型与应
用场景的差别，又可以进一步划分为关系型数据隐私保护、社交图谱数据隐私保护以及位
置与轨迹数据隐私保护。但基于匿名的方法通常缺乏严格的隐私安全保证，因此其更适用
于小规模数据的隐私保护。基于加密的方法虽然具有更好的安全性保证，但其加密操作会
带来大量的计算开销，这使其难以应用于资源受限的场景中。在过去的十几年中，差分隐私
(DP)蓬勃发展。它能够从理论上准确的限定隐私泄露的上限，这也是它优于传统隐私保护
方案的主要特点。美国人口普查局(US Census Bureau)对人口统计数据就采用了DP模型。
传统的DP模型被部署在了中央服务器上，但在实践中很难找到一个真正的可信第三方，这
在一定程度上限制了传统差分隐私的应用。本地化差分隐私(LDP)在DP的基础上应运而生，
其不仅可以抵御任意背景知识攻击，还能够抵御不可信第三方攻击。目前，谷歌、Apple等公
司已使用LDP模型用于收集用户默认浏览器主页和搜索引擎设置的信息。

[0004] 但将LDP模型应用于隐私保护政务数据共享中的研究工作还较少，这是由于这些前沿方法需要结合应用场景和变化的需求进行创新应用。在政务数据共享场景中，LDP模型
存在准确性低、统计误差大等缺点，在数据域大且数据量较少的情形中尤为显著。

[0005] 本地化差分隐私提供了比中心化差分隐私更强的隐私保障，其正式定义如下：

[0006] 定义1：本地化差分隐私(ε‑LDP)。假设x是一个私有信息，该私有信息从含k个元素的集合X中取值(令X＝[k]:＝{0,1,2,3,…,k‑1},x∈X)。私有化机制Q是从[k]到输出集Z的
随机映射Q，它以概率Q(z|x)将x∈X映射到z∈Z，映射后输出的z被称为私有化样本。如果对
于所有的x，x’∈X，当ε>0时，有

[0007]

[0008] 则认为Q满足ε‑本地化差分隐私。由公式(1)可知，较小的隐私预算ε可以保证较高的隐私水平。且任意一对x，x’的映射输出都是相似的，因此不能通过输出结果推断出特定
的输入。

[0009] 政府统计数据共享是电子政务的重要组成部分，但共享过程中存在的隐私泄露很大程度上影响了政府统计信息公开的力度和透明度。在本地化差分隐私中，一个统计数据
库的查询结果不会受到任何单一隐私数据的影响，它能在确保处理后统计信息可用的需求
下保护个人信息不被泄露。因此可将LDP应用到政府部门间共享统计数据的场景中，确保数
据共享过程中敏感信息的安全。

[0010] 在政府业务中应当存在这样的部门间数据共享应用场景。即一个政府部门以增量方式不断地获得某项数据记录，而另一个部门需要共享这些数据记录的统计信息用作该部
门管理或服务决策的辅助参考依据。在本地化差分隐私中，一个统计数据库的查询结果不
会受到任何单一隐私数据的影响，它能在确保处理后统计信息可用的需求下保护个人信息
不被泄露。结合这一场景，我们需要用本地化差分隐私方法实现政府部门间隐私保护数据
共享的解决方案，并通过实验分析其有效性。

[0011] 传统的本地化差分隐私系统架构：

[0012] 具体而言，数据提供部门对拟共享数据的每条记录的敏感属性列的值进行隐私化处理，使得数据需求部门无法在接收到共享数据后推断出目标对象敏感属性的确定值。然
后，数据需求部门根据数据提供部门提供的相关隐私参数，对收到的共享数据进行统计校
正，得到需要的统计结果数据。如图1所示，编码和扰动操作由数据提供部门执行。每个编码
的记录通过随机函数生成一个扰动报告，从而满足了ε‑LDP的定义。最后，数据提供部门将
扰动后的报告发送到数据需求部门，并由数据需求部门执行解码和聚合操作，统计校正后
生成可用的统计数据。

[0013] 常用的LDP方法

[0014] 下面描述了当前常用的本地化差分隐私算法，并对其进行了简要分析，以寻求适用于政府部门间统计数据共享场景的方法。

[0015] 1.Generalized randomized response(GRR)

[0016] 随机响应算法(Randomized Response，RR)是最典型的LDP算法，最早于1965年由Warner等人提出，用于隐私保护。但RR存在一个不足，它仅对包含两种取值的离散型数据进
行响应，而对于具有超过两种取值的数据并不适用。为此，一个更普遍使用的随机响应GRR
算法被提出。对于收集到的每一条私有数据x∈X,X＝Z＝[k]，用户以p的概率发送x的真实
值，并以概率1‑p从X\{x}中发送随机选择的值x’，扰动函数如公式(2)所示。

[0017]

[0018] 2.Randomized aggregatable privacy‑preserving ordinal response(RAPPOR)

[0019] Randomized aggregatable privacy‑preserving ordinal response是Google提出的一个通用LDP算法。在RAPPOR机制中，用户的真实值x被编码到位向量B中。当category
属性众多时，RAPPOR存在通信成本高、准确度低等问题。为此，它使用了Bloom过滤器进行编
码。通过使用k个哈希函数将值x映射到位向量B中的不同位置。例如，映射位置设置为1，其
余位置设置为0。k‑RAPPOR的隐私输出B’是一个k位向量，它是以概率 翻转B的每一位
而得到的。

[0020] 3.Count Mean Sketch(CMS)

[0021] CMS由苹果差分隐私团队于2016年提出，它由客户端算法和服务器端算法组成。客户端算法通过将域的元素d与k个哈希函数之一进行映射，来确保传输的大小为m。在服务器
端，用于聚合隐私数据的数据结构是维数为k×m的草图矩阵M。为了计算域的元素 的
估计值，服务器端算法通过对矩阵M中与k个哈希函数相对应的计数取平均值，求得最终的
估计频数。

[0022] 上述所提的三种本地化差分隐私算法均是基于随机响应的，其不确定性使得估计结果的准确性不稳定。在数据域较大且数据量较少的情况下，这种现象尤为显著。它甚至可
能将一个低频属性值所对应的频数值估计为负，这在一定程度上降低了数据的参考价值。
因此，本发明专利的创新点之一是实现具有高数据效用性的LDP算法，提高在数据域较大且
数据量较少时估计结果的准确性，从而在保护数据隐私的同时为政府部门提供可用的统计
信息。

发明内容

[0023] 本发明需要解决的技术问题是提供一种面向政务数据共享的本地化差分隐私方法，以解决现有LDP算法的不足，提高估计结果准确性和稳定性。

[0024] 为了解决上述问题，本发明所采用的技术方案是：

[0025] 一种面向政务数据共享的本地化差分隐私方法，该方法在CMS算法(Count Mean Sketch)的基础上引入数据分箱思想，通过等宽分箱将数据记录分入与原始数据域相比更
小的数据域范围内，并构造用于聚合的计数草图矩阵来降低时空复杂度，以克服当前隐私
保护算法在数据分布稀疏处(此处数据域较大且数据量较少)统计误差大的问题。

[0026] 本发明技术方案的进一步改进在于：在数据提供方设计本地扰动器，用来扰动原始数据：首先根据敏感属性列的值(也就是下文要说的敏感属性值d)的域大小对数据进行
分箱，对于箱中的每一条数据，本地扰动器均选择一个随机哈希函数对其进行编码得到一
个向量，并对该向量进行扰动；随后，将包含所选哈希函数索引和扰动向量的报告发送到数
据需求方，由于数据提供方算法满足LDP定义，即使潜在攻击者拥有相关的背景知识，也无
从得知攻击目标敏感属性的准确信息；

[0027] 在数据需求方设计聚合器，当从数据提供方接收到所有扰动报告和相关参数后，数据需求方将通过聚合器对它们进行聚合，聚合私有化数据的数据结构是大小为k×m的计
数草图矩阵，数据需求方通过对矩阵中k个哈希函数对应的计数进行平均，得到各属性值的
频数估计，最后统计校正后生成可用的统计数据。

[0028] 本发明技术方案的进一步改进在于：具体操作过程为：

[0029] S1、原始记录首先会通过随机选择的哈希函数进行编码，因此在数据提供方设计一组哈希函数H＝{h1,h2,…，hk}，并规定H中的函数能够根据输入的数据输出一个不大于m
的值，m为每一条数据记录中的敏感属性值d的初始化向量的长度，然后在数据提供方和数
据需求方之间共享这组哈希函数；

[0030] S2、按照等宽分箱思想划分敏感属性值的域区间Z，Zi为划分后比原始数据域更小的域区间；

[0031] S3、初始化一个集合V，用来存放后续得到的扰动报告，其中，Vi用来存放属于域区间Zi的数据记录的扰动报告；

[0032] S4、数据提供方依次对共享数据记录中敏感属性值d(i)进行扰动处理；

[0033] S5、数据需求方根据接收到的扰动报告和相关参数计算每个属性值的频数统计信息。

[0034] 本发明技术方案的进一步改进在于：数据提供方的扰动处理过程为通过确保受扰动的数据服从本地化差分隐私来防止用户数据泄漏，具体为：

[0035] S41、为每一条数据记录中的敏感属性值d初始化一个长度为m的向量v，表示为v＝m
{‑1}；

[0036] S42、在k范围内随机地选取数值j，作为选择第j个哈希函数的索引，其中，hj(d)表示选择第j个函数对敏感属性值d取哈希，若hj(d)＝134，则将v的第134位赋值为1；
ε/2

[0037] S43、将向量v的每一个比特位以 【也就是1/(e +1)】的概率进行随机翻转后生成新的向量 表示为

[0038] S44、将翻转后的向量 哈希函数hj的索引j以及参数k、m、ε的值发送给数据需求方。

[0039] 本发明技术方案的进一步改进在于：S5中，数据需求方在获取到数据提供方的扰动报告和相关参数后，数据需求方将使用相同的参数构造计数草图矩阵，通过草图矩阵，进
而估计敏感属性值d的计数。

[0040] 本发明技术方案的进一步改进在于：数据需求方具体操作为：

[0041] S51、初始化大小为k×m的全零矩阵M以构造草图矩阵，其中，k表示哈希函数的数目，m表示向量v的长度；

[0042] S52、处理每个扰动报告中的向量v并将其转化为向量x；

[0043] S53、对于每一个敏感属性值的扰动结果(x,j)，将x按位依次加到矩阵M的第j行，第j行代表选择了第j个哈希函数的记录项总和，当数据需求方获得足够多的记录，矩阵M的
规模会足够大；

[0044] S54、数据需求方通过读取每一行M[j,hj(d)]的值来计算这些估计的均值，从而获得无偏估计。

[0045] 由于采用了上述技术方案，本发明取得的有益效果是：

[0046] 本发明提出使用数据分箱和计数草图矩阵来降低统计误差，并实现在不同分布下获得较高的数据效用。数据分箱思想解决了当前隐私保护算法在数据域较大时对数据量要
求严格的问题，这样处理的好处是，利用分箱思想可以将数据记录分入更小的数据域范围
内。当聚合数据时，不同子域中的数据在各自域内进行聚合处理，可以防止本数据域中的数
据被划分到其他子域内，一定程度上提高了数据聚合的可靠性。

[0047] 本技术方案的主要有益效果具体为：

[0048] (1)针对政府部门间共享统计数据的场景，提出了基于本地化差分隐私的政务数据共享方法，其可在推行数据共享的基础上为敏感信息提供可控制的隐私保护。

[0049] (2)该方法解决了当前隐私保护算法在数据域较大时对数据量大小要求严格的问题，有效降低了数据的统计误差，能在保护政务数据隐私的同时，提供可用的统计信息。

[0050] (3)所提出的方法在不同的数据分布中均保持了较优的数据效用性，能适应于多种不同分布的隐私保护任务中。

附图说明

[0051] 图1为传统本地化差分隐私系统框架图；

[0052] 图2为本发明的数据提供方操作示意图；

[0053] 图3为本发明的数据需求方操作示意图；

[0054] 图4为本发明在仿真数据集1(满足几何分布)下经BCS算法处理后的统计结果与原始数据统计结果对比图；

[0055] 图5为本发明在仿真数据集2(满足均匀分布)下经BCS算法处理后的统计结果与原始数据统计结果对比图；

[0056] 图6为真实数据集(菲利宾家庭收入支出数据集)对应的频数直方图；

[0057] 图7为真实数据集下经CMS算法处理后得到的频数直方图；

[0058] 图8为真实数据集下利用本发明BCS算法处理后得到的频数直方图；

[0059] 图9为真实数据集下经GRR算法处理后得到的频数直方图；

[0060] 图10为真实数据集下利用本发明BRR算法处理后得到的频数直方图；

[0061] 图11为真实数据集下经CMS与BCS算法处理后各属性值统计量的平均绝对百分比误差对比图；

[0062] 图12为真实数据集下经GRR与BRR算法处理后各属性值统计量的平均绝对百分比误差对比图；

[0063] 图13为分箱数对平均绝对百分比误差的影响图；

[0064] 图14为数据规模对统计数据误差的影响(CMS与BCS比对方向)；

[0065] 图15为数据规模对统计数据误差的影响(GRR与BRR比对方向)；

[0066] 图16为隐私预算对统计数据误差的影响(CMS与BCS比对方向)；

[0067] 图17为隐私预算对统计数据误差的影响(GRR与BRR比对方向)；

[0068] 图18为相同隐私预算下，分箱数对统计数据误差的影响(BCS fxs＝4/8/16的情况下)；

[0069] 图19为相同隐私预算下，分箱数对统计数据误差的影响(BRR fxs＝4/8/16的情况下)；

[0070] 图20为数据域大小对统计数据误差的影响(数据集满足Zipf分布，CMS与BCS的比对方向)；

[0071] 图21为数据域大小对统计数据误差的影响(数据集满足均匀分布，CMS与BCS的比对方向)。

具体实施方式

[0072] 下面结合实例对本发明做进一步详细说明。

[0073] 本发明公开了一种面向政务数据共享的本地化差分隐私方法，参见图1‑图21，具体过程详述如下。

[0074] 1.1基于本地化差分隐私的数据共享方案

[0075] 针对现有LDP算法的不足，我们在CMS算法的基础上采用数据分箱思想来解决当前隐私保护算法在数据域较大时对数据量要求严格的问题，并构造用于聚合的计数草图矩阵
来降低时空复杂度。这样处理的好处是，利用分箱思想可以将数据记录分入更小的数据域
范围内。当聚合数据时，不同子域中的数据在各自域内进行聚合处理，可以防止本数据域中
的数据被划分到其他子域内，一定程度上提高了数据聚合的可靠性。

[0076] 本地扰动器设计在数据提供方，用来扰动原始数据。首先根据敏感属性列的值的域大小对数据进行分箱。对于箱中的每一条数据，本地扰动器均选择一个随机哈希函数对
其进行编码得到一个向量，并对该向量进行扰动。随后，将包含所选哈希函数索引和扰动向
量的报告发送到数据需求方，如图2所示。由于数据提供方算法满足LDP定义，即使潜在攻击
者拥有相关的背景知识，也无从得知攻击目标敏感属性的准确信息。

[0077] 聚合器设计在数据需求方。当从数据提供方接收到所有扰动报告和相关参数后，数据需求方将通过聚合器对它们进行聚合。聚合私有化数据的数据结构是大小为k×m的计
数草图矩阵。数据需求方通过对矩阵中k个哈希函数对应的计数进行平均，得到各属性值的
频数估计。最后统计校正后生成可用的统计数据，如图3所示。

[0078] 1.2基于本地化差分隐私的数据共享算法设计

[0079] 常见的数据分箱有等宽分箱和等频分箱。等宽分箱以敏感属性值的域大小为前提，按相同区间宽度分箱，这时每个分箱内数据量不定。等频分箱则是把敏感属性值按照从
小到大的顺序排列，根据记录的个数将其等分为x部分，这时每个分箱内数据量相同。但等
频分箱的效果容易受数据分布的影响，特别是当数据记录集中在几个属性值上，如Zipf分
布和几何分布。因此，本专利采用等宽分箱对数据记录进行划分。为简化描述，将改进后的
算法记为BCS(Binning Count Sketch)。

[0080] 原始记录首先会通过随机选择的哈希函数进行编码，所以在数据提供方需要设计一组哈希函数H＝{h1,h2,…，hk}，并规定H中的函数能够根据输入的数据输出一个不大于m
的值。然后在数据提供方和数据需求方之间共享这组哈希函数。完整的BCS算法在算法1
(Algorithm 1)中给出。第2行按照等宽分箱思想划分了敏感属性值的域区间，Zi为划分后
更小的域区间。算法在第3行中初始化了一个集合V，用来存放之后得到的扰动报告。其中，
Vi用来存放属于域区间Zi的数据记录的扰动报告。第4‑8行由数据提供方执行，依次对共享
(i)
数据记录中敏感属性值d 进行扰动处理。第9‑11行由数据需求方根据接收到的扰动报告
和相关参数计算每个属性值的频数统计信息。

[0081]

[0082] 1.2.1数据提供端算法设计

[0083] 算法2(Algorithm 2)描述了数据提供部门的扰动过程。通过确保受扰动的数据服从本地化差分隐私来防止用户数据泄漏。在第1行中，算法为每一条数据记录中的敏感属性
m
值d初始化一个长度为m的向量v，表示为v＝{‑1} 。第2‑3行中，在k范围内随机地选取数值
j，作为选择第j个哈希函数的索引，其中，hj(d)表示选择第j个函数对敏感属性值d取哈希。
若hj(d)＝134，则将v的第134位赋值为1。然后在5‑6行中，将向量v的每一个比特位以
的概率进行随机翻转后生成新的向量 表示为 最后在第8行中将翻转后的
向量 哈希函数hj的索引j以及参数k、m、ε的值发送给数据需求部门。

[0084]

[0085] 1.2.2数据需求端算法设计

[0086] 如图3所示，在获取到数据提供部门的扰动报告和相关参数后，数据需求部门将使用相同的参数构造计数草图矩阵。有了草图矩阵，最后一步就是估计敏感属性值d的计数，
这是通过对计数进行去偏并平均M中的相应哈希项来完成的。其中， 为敏感属性列的数据
域， 为敏感属性列分箱后的子数据域。算法3(Algorithm 3)中介绍了此过程。

[0087]

[0088]

[0089] 首先，在第1行初始化大小为k×m的全零矩阵M以构造草图矩阵，其中，k表示哈希函数的数目，m表示向量v的长度。然后，在第2‑4行中处理每个扰动报告中的向量v并将其转
化为x。在第5‑6行中，对于每一个敏感属性值d的扰动结果(x,j)，我们将x按位依次加到矩
阵M的第j行，第j行代表选择了第j个哈希函数的记录项总和。当数据需求方获得足够多的
记录，矩阵M的规模会足够大。最后，在第7‑8行，数据需求方通过读取每一行M[j,hj(d)]的
值来计算这些估计的均值，从而获得无偏估计。

[0090] 为了验证BCS算法的可行性，本专利首先生成两个含10万条记录的仿真数据集，它们分别满足几何分布和均匀分布。原始数据集的频数统计结果与经过BCS(fxs＝8)算法处
理后的数据的频数统计结果如图4‑图5所示。容易得出，经过BCS算法处理后的数据统计值
与原始数据统计值相差较小，具有统计学意义。

[0091] 图4‑图5为仿真数据集1和2分别经BCS算法处理后的统计结果与原始数据统计结果的对比图，图4为Geometric datasets，图5为Uniform datasets。

[0092] 1.3方法延展

[0093] 此外，本专利将数据分箱思想延伸至背景技术中提到的GRR算法，改进后的算法记为BRR(Binning Randomized Response)。BRR是对GRR工作的改进，且GRR可作为BRR在特定
情况下特定参数选择的方法，即当参数fxs＝1时，为GRR算法。回顾公式(2)可以发现，p接近
0或1的值并不可取。这是因为极端情况下当p＝1时，K＝1，此时敏感属性仅有一种取值，即
数据不翻转的概率为1，若共享数据将使敏感信息处于危险之中；而当p＝0时，数据翻转概
率最大，得到的扰动数据越背离原始数据，虽然增大了保护强度，但却违背了共享数据的初
衷。BRR算法中，敏感属性在子域中可取值的个数由敏感属性列的数据域和分箱数fxs共同
决定，要使敏感属性在子域中的取值超过1种，应保证分箱数取值不超过数据域的大小，从
而保护共享数据的隐私。

[0094] 2实验部分

[0095] 2.1实验数据集

[0096] 实验共采用三个数据集进行实验分析：两个仿真数据集和一个真实数据集。仿真数据集分别满足Zipf分布和均匀分布，且每个数据集中包含100000条数据。真实数据集则
选取Kaggle提供的菲利宾家庭收入支出数据集(Family Income and Expenditure)。设年
收入大于200 000比索的家庭为高收入家庭，以此为条件，共筛选出16685条数据用于后续
分析。由于该数据集中含有多个属性字段，因此数据提供部门可以以地区、年龄、婚姻状态
等各种维度对高收入家庭的统计分析数据进行共享。本专利以年龄维度为例，通过对各个
年龄的高收入家庭频数数据进行隐私保护处理，证明BCS与BRR算法的特性和优势。

[0097] 2.2实验指标

[0098] 隐私保护后数据的效用性通常用原始数据集与隐私处理后数据集的差异程度来评估。常用的误差度量标准有：相对误差、绝对误差、平均绝对百分比误差以及欧式距离等。
这里采用平均绝对百分比误差MAPE作为数据效用性的评价指标，通过与CMS算法进行比较，
证明BCS算法的效用性。对于每个数据值，我们计算估计频数和真实频数之间的绝对值，将
[42,43]
绝对值除以真实频数，然后将这些值累加，再除以数据域的大小。MAPE 的定义如下:

[0099]

[0100] 其中|D|为敏感属性列的类别域大小，yi为第i个属性值的真实频数，xi为第i个属性值的估计频数。MAPE的值越小，估计分布越接近真实分布，说明数据的效用越好。

[0101] 2.3实验结果分析

[0102] 2.3.1频数估计

[0103] 为了清楚显示频数分布趋势并便于观察，我们计算了每个属性值的估计频数。根据所选数据分别绘制了三种类型的高收入家庭年龄分布直方图，如图6所示。其中图6为原
始的真实数据集对应的频数直方图、图7为ε＝2时由CMS算法处理后得到的频数直方图、图8
为ε＝2，fxs＝16时由BCS算法处理后得到的频数直方图、图9为ε＝2时由GRR算法处理后得
到的频数直方图、图10为ε＝2，fxs＝16时由BRR处理后得到的频数直方图。观察图6‑图10的
频数直方图可以发现，隐私保护后的数据虽然改变了记录的具体值，但是从数据总体变化
趋势而言，保留了原始数据的分布性质，仍存在着较强的参考价值。同CMS算法相比，BCS算
法处理后的数据的估计频数更接近真实值，在数据量较少的两端尤为显著。

[0104] 2.3.2误差分析

[0105] 分别以CMS、GRR为对照组，我们计算了隐私保护处理后每个年龄对应的高收入家庭户数统计量的MAPE，图11‑图12为隐私处理后各年龄统计量的平均绝对百分比误差，图11
为CMS与BCS比较，图12为GRR与BRR比较。

[0106] 如图11‑图12所示，我们将参数设置为m＝1024，k＝2048和ε＝2。分析实验数据可知，当户主年龄分别为15、17、93、97、99时，由CMS算法隐私保护后的数据对应的统计值误差
最大。同样，当户主年龄分别为15、17、89、96、98时，由GRR算法隐私保护后的数据对应的统
计值误差最大。容易发现，这些户主年龄对应的户数均属于数据量过少的情况，分别为2、4、
3、2、3、2、4、5、3、4。相较于CMS和GRR算法，BCS和BRR算法在数据量较少时对应的统计误差则
小很多，统计误差均低于未改进前，总体趋势也更平稳。

[0107] 2.3.3分箱数对统计数据误差的影响

[0108] 为了验证分箱数量对统计数据误差的影响，我们计算了不同分箱数下每个户主年龄对应的高收入家庭户数统计量的平均绝对百分比误差，其中参数m＝1024，k＝2048，ε＝
2。图13显示了分箱数对统计数据误差的影响，从图13可以直观发现，随着分箱数量的增加，
MAPE逐渐降低。这是由于分箱可以在一定程度上限制随机响应技术带来的误差，保证某一
低频数的年龄值被隐私保护处理后仍处于距离该原始年龄值较近的位置。另外，需要注意
的是，BCS和BRR算法中分箱数的最大值不应超过数据域值的大小，尤其是BRR算法。若分箱
数取值超过数据域大小，会使敏感属性在子域Zi中可取值的个数接近于1，即数据不翻转概
率接近1。当子数据域1<＝Zi<＝1.5时，在图11‑图12中，分箱数的取值为56<＝fxs<＝84，此
时BRR算法对应的误差值逐渐接近于0。若直接共享这样的数据，将使敏感信息处于危险之
中，这是不可取的。

[0109] 2.3.4数据规模对统计数据误差的影响

[0110] 为了证实BCS和BRR算法在不同规模数据上的效用性，我们对上面筛选的菲律宾高收入家庭原始数据集(16685条数据)进行了翻倍处理，分别生成4倍(66740条数据)、8倍、12
倍、16倍、20倍(333700条数据)的数据集进行实验。同时将参数分别设置为m＝1024，k＝
2048，ε＝2以及fxs＝4。以CMS和GRR为对照组，观察在不同数据规模下，统计量误差值的变
化情况。

[0111] 图14‑图15显示了数据规模对统计数据误差的影响，由图14‑图15可以看出，随着数据规模的增加，经过不同隐私保护算法处理后的数据统计量整体误差逐渐降低。相较于
CMS和GRR，BCS与BRR在不同数据规模下均保持了更好的数据效用性，尤其当数据规模较小
时，BCS与BRR的优势更为明显。当数据集达到一定规模时，BCS与BRR统计量的整体误差在小
范围内浮动。实验结果也验证了叶青青等人在文献中指出的“用于统计的数据量大小决定
了数据效用性高低”这一说法。

[0112] 2.3.5隐私预算对统计数据误差的影响

[0113] 本专利在不同隐私预算(0～5)取值下，对菲律宾高收入家庭原始数据集进行隐私保护，以验证隐私预算参数对BCS和BRR数据效用性的影响。同上，分别以CMS和GRR为对照
组，选择参数m＝1027，k＝2048。以fxs＝8为例，从图16‑图17不难发现，随着隐私预算的增
加，这两种算法的MAPE值越小。即当隐私预算增加时，得到的估计数据更接近于原始数据。
其次，在相同隐私预算下，BCS与BRR算法的误差值更小，尤其当ε<2.5(ε<3.5)时，BCS(BRR)
算法的数据效用性显著优于CMS(GRR)。此外，在相同参数设置下，分别计算了fxs＝4,fxs＝
8，fxs＝16时的MAPE，如图18‑图19所示，容易发现，在相同隐私预算下，分箱数fxs越大，统
计数据误差MAPE越小。

[0114] 图16‑图17显示了隐私预算对统计数据误差的影响，图16为CMS与BCS比对，图17为GRR与BRR比对。

[0115] 图18‑图19显示了相同隐私预算下，分箱数fxs对统计数据误差的影响。

[0116] 2.3.6数据域大小对统计数据误差的影响

[0117] BCS算法在编码阶段采用了哈希函数对数据编码，这就容易出现哈希碰撞现象。这一现象的出现主要是因为不同的值可能会被映射到同一个哈希函数下的相同位置，从而降
低了数据的估计精度。本专利利用不同的数据域大小来生成满足Zipf分布和均匀分布的数
据集，数据集大小均为100000，并测试了不同域大小下的算法效用。将参数分别设置为m＝
256，k＝1024，ε＝2和fxs＝8。如图20‑图21所示，BCS和CMS算法在Zipf分布和均匀分布下的
误差均随着数据域大小的增大而增大，在|D|>m时较为显著。其次，不管在Zipf分布还是均
匀分布下，当数据域相同时BCS算法的效用性明显优于CMS算法。

[0118] 图20‑图21分别从Zipf数据集(Zipf datasets)方面和均匀数据集(Uniform datasets)方面显示了数据域大小对统计数据误差的影响。

[0119] 2.4算法特性分析

[0120] 我们从以下两个方面分析BCS与BRR算法特性：

[0121] (1)较好的数据效用性。从频数直方图的误差角度看，CMS与GRR算法的误差值主要源于敏感属性取值稀疏的部分。本专利提出基于数据分箱的隐私保护算法BCS与BRR，通过
将数据分入更小的数据域，得到更小的误差量。从数据规模、隐私预算、数据域大小等方面
进行讨论分析，表明BCS与BRR具有更好的数据效用性。

[0122] (2)略高的时间复杂度。使用BCS、BRR算法所需的时间复杂度与CMS、GRR算法相比较，仅多出了数据分箱的时间。但由于政府共享的个人统计数据通常不会涉及很大的数量
级，略高的时间复杂度不会成为本算法在政府领域实际应用的制约因素。

[0123] 3.结论

[0124] 为帮助智慧政府利用数据做出更准确更客观的决策，数据共享是其建设进程中必不可少的任务。由于政务数据中含有大量个人敏感信息，直接共享这些数据或是对已共享
的数据进行分析都有可能造成隐私信息的泄露。因此，本专利就政府在推行政务数据共享
的同时如何保护个人隐私信息不泄露进行了研究。首先，本专利针对政府部门间共享统计
数据场景，讨论了现有的隐私保护技术，提出了基于本地化差分隐私的政务数据共享算法
BCS(Binning Count Sketch)。然后与算法CMS进行比较，验证了所提算法具有较高的效用
性，可在不同分布和数据域大小下保持其效用性。但本专利提出的算法目前仅适用于单值
敏感属性的情况，下一步工作将考虑如何在多值敏感属性的情况下保证数据的敏感性与效
用性问题。

[0125] 智慧政府作为服务型政府的延伸，需要利用数据帮助其更准确更客观的做出决策。为了更合理化的决策，通常一个政府部门会根据业务需求向其他部门共享某类数据记
录，为本部门管理或服务决策提供辅助参考依据。但若在没有适当预防措施的情况下就共
享政务数据，将容易造成隐私信息的泄露。因此，如何保护个人隐私信息不泄露是政府在推
行可信政务数据共享、建设安全智慧政府的同时需解决的关键问题。就政府部门间共享统
计数据的场景而言，本专利提出了基于本地化差分隐私的政务数据共享方法。该方法在算
法Count Mean Sketch(CMS)的基础上引入数据分箱思想，通过等宽分箱将数据记录分入更
小的数据域范围内，以克服当前隐私保护算法在数据域较大且数据量较少时统计误差大的
问题。之后将数据分箱思想延展应用至Generalized randomized response(GRR)算法中，
也取得了明显的效果。为验证其有效性，将本发明改进的Binning Count Sketch(BCS)和
Binning randomized response(BRR)算法分别与CMS和GRR算法在合成数据集和真实数据
集上进行了对比分析。实验结果表明，本发明所提方法有效降低了统计误差，并在不同分布
和数据域大小下提升了其效用性，具有较高的推广应用价值。