基于抽样分组的差分隐私直方图发布方法及设备与流程

1.本发明实施例涉及数据隐私保护技术领域，尤其涉及一种基于抽样分组的差分隐私直方图发布方法及设备。


背景技术：

2.随着信息化数字化时代的到来，整个社会产生着越来越多数据。对这些数据进行合理采用，能够产生巨大的价值。因此，数据拥有者通常会将数据发布给专业机构进行价值提取。但这也会造成一个问题，数据通常会包含用户的一些隐私，若将其直接发布，很容易被黑客窃取，造成用户隐私泄露。因此，在数据发布之前对数据进行去隐私化处理。差分隐私是一种有效的隐私保护手段，也是一个良好的数学模型，能够为数据隐私保护提供量化的支持。但差分隐私在保护数据隐私的也会对数据的可用性造成一定影响，因此，如何在保护数据隐私的同时，提升数据的可用性也是差分隐私使用者着重考虑的问题。直方图是分析数据流的常用统计分析技术。智慧城市物联传感器网络、疾病应急控制、城市防灾减灾、智能交通应用场景中存在大量的实时动态数据流统计分析任务。由于数据流中通常蕴含着敏感的企业和个人信息,直接发布直方图统计信息可能会披露企业和个人隐私。因此，开发一种基于抽样分组的差分隐私直方图发布方法及设备，可以有效克服上述相关技术中的缺陷，就成为业界亟待解决的技术问题。


技术实现要素：

3.针对现有技术存在的上述问题，本发明实施例提供了一种基于抽样分组的差分隐私直方图发布方法及设备。
4.第一方面，本发明的实施例提供了一种基于抽样分组的差分隐私直方图发布方法，包括：步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,hn}选取k个中心点得到分组中心点集合c(c1,c2,...,ck)；步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,gk)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,gk)；步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,hn}表示原始直方图；h1,h2,...,hn表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的整数；c(c1,c2,...,ck)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,gk)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；
g1,g2,...,gk表示初始分组集合中的分组序列；g(g1,g2,...,gk)表示通过抽样划分之后得到的最终分组，g1,g2,...,gk表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。
5.在上述方法实施例内容的基础上，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s1中ε1用于抽样分组，ε2用于分组加噪。
6.在上述方法实施例内容的基础上，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s2包括以下步骤：s2.1、设置分组数k，其中k＝1,2,3,...,n；s2.2、从原始数据中随机挑选一个桶作为初始中心点c1；s2.3、计算每个桶到已有中心点的最短距离d(x)；s2.4、根据d(x)计算出每个桶被选取作为下一中心点的概率，利用轮盘抽样选取出下一中心点；s2.5、重复步骤s2.3与s2.4，直至选出k个分组中心点c(c1,c2,...,ck)。
7.在上述方法实施例内容的基础上，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s3包括以下步骤：s3.1将c中每个中心点视为一个单独的分组，得到分组集合g(g1,g2,...,gk)；s3.2将去除中心点的剩余直方图数据放入集合s中；s3.3从s中随机抽取一个桶，计算出抽取桶与每个分组的分组中心的距离u(g,gj)，并将其设置为打分函数:
8.u(g,gj)＝-h-cj9.其中h是从s中抽取的桶，；cj∈c,j＝1,2,3...,k且cj是分组gj的分组中心，打分函数设置应满足要求：抽取桶与分组中心越近，分组被抽样的概率就越大；因此为了满足此要求，采用抽取桶h与分组中心cj之间距离的相反数来构造打分函数；s3.4利用指数机制结合分组距离计算出划分到每个分组的概率pr(g,gj):
[0010][0011]
其中，分组概率pr(g,gj)用以表示分组gj被选为目标分组的概率，ε1表示给定的隐私预算；δu为全局敏感度；u(g,gj)为打分函数；根据全局敏感度的定义可知；打分函数在相邻数据集上的最大变化为1，因此这里的δu＝1，k表示分组数；为分组gj的适应度函数；分子计算的是某一个分组的适应度值，分母计算的是所有分组的的适应度值的总和；s3.5根据每个分组对应的抽样概率；利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；s3.6重复步骤s3.3-s3.5步直至抽取完s中所有的桶，循环结束。得到最终分组方案g(g1,g2,...,gk)。
[0012]
在上述方法实施例内容的基础上，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s5中分组添加噪音的隐私预算为ε2。
[0013]
第二方面，本发明的实施例提供了一种基于抽样分组的差分隐私直方图发布装置，包括：第一主模块，用于实现步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,hn}选取k个中心点得到分组中心点集合c(c1,c2,...,ck)；第二主模块，用于实现步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,gk)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,gk)；第三主模块，用于实现步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到第四主模块，用于实现步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,hn}表示原始直方图；h1,h2,...,hn表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的整数；c(c1,c2,...,ck)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,gk)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；g1,g2,...,gk表示初始分组集合中的分组序列；g(g1,g2,...,gk)表示通过抽样划分之后得到的最终分组，g1,g2,...,gk表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。
[0014]
第三方面，本发明的实施例提供了一种电子设备，包括：
[0015]
至少一个处理器；以及
[0016]
与处理器通信连接的至少一个存储器，其中：
[0017]
存储器存储有可被处理器执行的程序指令，处理器调用程序指令能够执行第一方面的各种实现方式中任一种实现方式所提供的基于抽样分组的差分隐私直方图发布方法。
[0018]
第四方面，本发明的实施例提供了一种非暂态计算机可读存储介质，非暂态计算机可读存储介质存储计算机指令，计算机指令使计算机执行第一方面的各种实现方式中任一种实现方式所提供的基于抽样分组的差分隐私直方图发布方法。
[0019]
本发明实施例提供的基于抽样分组的差分隐私直方图发布方法及设备，在分组划分阶段采用指数机制对直方图进行抽样划分，满足差分隐私约束，通过直方图进行抽样近似划分，能够在满足差分隐私的同时，有效地提升分组的准确性；通过对分组过程进行合理优化，提升了分组的准确性，进而降低了发布数据的误差，提升了发布数据的可用性。
附图说明
[0020]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现
有技术描述中所需要使用的附图做一简单的介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0021]
图1为本发明实施例提供的基于抽样分组的差分隐私直方图发布方法流程图；
[0022]
图2为本发明实施例提供的基于抽样分组的差分隐私直方图发布装置结构示意图；
[0023]
图3为本发明实施例提供的电子设备的实体结构示意图；
[0024]
图4为本发明实施例提供的隐私预算ε取ln2的mse值示意图；
[0025]
图5为本发明实施例提供的隐私预算ε取1的mse值示意图；
[0026]
图6为本发明实施例提供的隐私预算ε取1.5的mse值示意图。
具体实施方式
[0027]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。另外，本发明提供的各个实施例或单个实施例中的技术特征可以相互任意结合，以形成可行的技术方案，这种结合不受步骤先后次序和/或结构组成模式的约束，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时，应当认为这种技术方案的结合不存在，也不在本发明要求的保护范围之内。
[0028]
首先对原始直方图挑取分组中心：为保证分组中心在数据中分布尽量离散，本方法采用分组中心点间的最短距离结合轮盘对分组中心点进行抽样选取。在选取好分组中心点之后，则对剩余桶进行抽样分组：首先将每个中心点视为一个单独的分组，计算抽取桶与每个分组的分组中心的距离，结合指数机制，计算出每个分组的分组抽样概率，采用轮盘选取目标分组，选好分组后，将抽取桶划入该分组中。当所有剩余桶都抽取完毕之后，形成最终分组。对分组求取均值再添加laplace噪声，恢复原始直方图顺序，得到发布的差分隐私直方图。基于这种思想，本发明实施例提供了一种基于抽样分组的差分隐私直方图发布方法，参见图1，该方法包括：步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,hn}选取k个中心点得到分组中心点集合c(c1,c2,...,ck)；步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,gk)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,gk)；步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,hn}表示原始直方图；h1,h2,...,hn表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的
整数；c(c1,c2,...,ck)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,gk)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；g1,g2,...,gk表示初始分组集合中的分组序列；g(g1,g2,...,gk)表示通过抽样划分之后得到的最终分组，g1,g2,...,gk表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。
[0029]
基于上述方法实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s1中ε1用于抽样分组，ε2用于分组加噪。
[0030]
基于上述方法实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s2包括以下步骤：s2.1、设置分组数k，其中k＝1,2,3,...,n；s2.2、从原始数据中随机挑选一个桶作为初始中心点c1；s2.3、计算每个桶到已有中心点的最短距离d(x)；s2.4、根据d(x)计算出每个桶被选取作为下一中心点的概率，利用轮盘抽样选取出下一中心点；s2.5、重复步骤s2.3与s2.4，直至选出k个分组中心点c(c1,c2,...,ck)。
[0031]
基于上述方法实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s3包括以下步骤：s3.1将c中每个中心点视为一个单独的分组，得到分组集合g(g1,g2,...,gk)；s3.2将去除中心点的剩余直方图数据放入集合s中；s3.3从s中随机抽取一个桶，计算出抽取桶与每个分组的分组中心的距离u(g,gj)，并将其设置为打分函数:
[0032]
u(g,gj)＝-h-cj[0033]
其中h是从s中抽取的桶，；cj∈c,j＝1,2,3...,k且cj是分组gj的分组中心，打分函数设置应满足要求：抽取桶与分组中心越近，分组被抽样的概率就越大；因此为了满足此要求，采用抽取桶h与分组中心cj之间距离的相反数来构造打分函数；s3.4利用指数机制结合分组距离计算出划分到每个分组的概率pr(g,gj):
[0034][0035]
其中，分组概率pr(g,gj)用以表示分组gj被选为目标分组的概率，ε1表示给定的隐私预算；δu为全局敏感度；u(g,gj)为打分函数；根据全局敏感度的定义可知；打分函数在相邻数据集上的最大变化为1，因此这里的δu＝1，k表示分组数；为分组gj的适应度函数；分子计算的是某一个分组的适应度值，分母计算的是所有分组的的适应度值的总和；s3.5根据每个分组对应的抽样概率；利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；s3.6重复步骤s3.3-s3.5步直至抽取完s中所有的桶，循环结束。得到最
终分组方案g(g1,g2,...,gk)。
[0036]
基于上述方法实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布方法，步骤s5中分组添加噪音的隐私预算为ε2。
[0037]
本发明实施例提供的基于抽样分组的差分隐私直方图发布方法，在分组划分阶段采用指数机制对直方图进行抽样划分，满足差分隐私约束，通过直方图进行抽样近似划分，能够在满足差分隐私的同时，有效地提升分组的准确性；通过对分组过程进行合理优化，提升了分组的准确性，进而降低了发布数据的误差，提升了发布数据的可用性。
[0038]
在另一实施例中，本发明实施例提供了一种基于抽样分组的差分隐私直方图发布方法，包括：
[0039]
s1：隐私预算设置：令ε＝ε1+ε2；
[0040]
s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,hn}选取k个中心点得到分组中心点集合c(c1,c2,...,ck)。
[0041]
s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,gk)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,gk)。
[0042]
s4：分组求取均值：将分组g求取均值得到
[0043]
s5：噪声添加：对添加大小为ε2的lapalce噪声得到
[0044]
s6：对恢复原始直方图顺序得到差分隐私直方图
[0045]
具体来说，差分隐私是一种有效的隐私保护方法，该方法的原理是通过对数据噪音添加来对数据进行隐私去除，但这种方式也会对数据的真实性进行模糊。因此使用差分隐私技术需要在数据的隐私性和可用性之间进行权衡。为了保护数据隐私同时提升数据的可用性，研究者最常用的方式是对直方图进行分组优化。因此，找到一种既能满足差分隐私又能提升数据可用性的分组划分方法是该领域的研究热点。
[0046]
基于此，本文提出了一种基于抽样分组的差分隐私直方图发布方法来解决上述问题。
[0047]
具体来说，该方法首先对原始直方图挑取分组中心：为了保证分组中心在数据中分布尽量离散，本方法利用了分组中心点间的最短距离结合轮盘对分组中心点进行抽样选取。在选取好分组中心点之后，则对剩余桶进行抽样分组：首先将每个中心点视为一个单独的分组，计算抽取桶与每个分组的分组中心的距离，结合指数机制，计算出每个分组的分组概率，然后利用轮盘选取目标分组，选好分组后，将抽取桶划入该分组中。当所有剩余桶都抽取完毕之后，形成最终分组。对分组求取均值再添加laplace噪声，恢复原始直方图顺序，得到发布的差分隐私直方图。
[0048]
在一种实施方式中，步骤s1中ε1用于抽样分组，ε2用于分组加噪。
[0049]
在一种实施方式中，步骤s2包括以下步骤：
[0050]
s2.1设置分组数k，其中k＝1,2,3,...,n；
[0051]
s2.2原始数据中随机挑选一个桶作为初始中心点c1；
[0052]
s2.3计算每个桶到已有中心点的最短距离d(x)；
[0053]
s2.4根据d(x)计算出每个桶被选取作为下一中心点的概率，利用轮盘抽样选取出下一中心点；
[0054]
s2.5重复步骤s2.3与s2.4；直至选出k个分组中心点c(c1,c2,...,ck)；)
[0055]
在一种实施方式中，步骤s3包括以下步骤：
[0056]
s3.1将c中每个中心点视为一个单独的分组，得到分组集合g(g1,g2,...,gk)；
[0057]
s3.2将去除中心点的剩余直方图数据放入集合s中；
[0058]
s3.3从s中随机抽取一个桶(不放回抽取)；计算出抽取桶与每个分组的分组中心的距离u(g,gj)，并将其设置为打分函数:
[0059]
u(g,gj)＝-h-cj[0060]
其中h是从s中抽取的桶，；cj∈c,j＝1,2,3...,k且cj是分组gj的分组中心，打分函数设置应满足要求：抽取桶与分组中心越近，分组被抽样的概率就越大；因此为了满足此要求，采用抽取桶h与分组中心cj之间距离的相反数来构造打分函数。
[0061]
s3.4利用指数机制结合分组距离计算出划分到每个分组的概率pr(g,gj):
[0062][0063]
其中，分组概率pr(g,gj)用以表示分组gj被选为目标分组的概率，ε1表示给定的隐私预算；δu为全局敏感度；u(g,gj)为打分函数；根据全局敏感度的定义可知；打分函数在相邻数据集上的最大变化为1，因此这里的δu＝1，k表示分组数；为分组gj的适应度函数；分子计算的是某一个分组的适应度值，分母计算的是所有分组的的适应度值的总和。
[0064]
s3.5根据每个分组对应的抽样概率；利用轮盘选取目标分组，并将该桶划分到选取的目标分组中。
[0065]
s3.6重复步骤s3.3-s3.5步直至抽取完s中所有的桶，循环结束。得到最终分组方案g(g1,g2,...,gk)。
[0066]
在一种实施方式中，步骤s5中分组添加噪音的隐私预算为ε2。
[0067]
在此以实验验证本发明方法的有效性。实验硬件配置为amd ryzen 53600-6-core processor 3.60ghz；16g内存，系统平台为windows10操作系统下jdk1.8以及matlab r2020a；实验数据集选取美国人口普查数据集adult。实验中通过对比同类直方图发布算法ahp、php进行分析。
[0068]
图4、5、6为例，隐私预算ε分别取ln2、1和1.5，查询范围为100～1000，使用三种算法分别对数据集adult处理20次，最后对实验产生的结果取平均值作为最终结果。可以看出：本发明方法相比于ahp算法和php算法产生的误差(mse)更少，因此本发明方法可用性更优。
[0069]
本发明具有如下优点：
[0070]
1)满足差分隐私约束。本方案在分组划分阶段采用指数机制对直方图进行抽样划分，该阶段使用的隐私预算大小为ε1，因此满足ε
1-差分隐私，同时分组加噪阶段添加大小为
ε2的laplace噪声，因此分组加噪阶段满足ε
2-差分隐私，由于ε＝ε1+ε2，因此该方法整体满足ε-差分隐私。
[0071]
2)分组准确性高。本方案通过直方图进行抽样近似划分，能够在满足差分隐私的同时，有效地提升分组的准确性。
[0072]
3)发布数据可用性高。本方案通过对分组过程进行合理优化，提升了分组的准确性，进而降低了发布数据的误差，提升了发布数据的可用性。
[0073]
本发明各个实施例的实现基础是通过具有处理器功能的设备进行程序化的处理实现的。因此在工程实际中，可以将本发明各个实施例的技术方案及其功能封装成各种模块。基于这种现实情况，在上述各实施例的基础上，本发明的实施例提供了一种基于抽样分组的差分隐私直方图发布装置，该装置用于执行上述方法实施例中的基于抽样分组的差分隐私直方图发布方法。参见图2，该装置包括：第一主模块，用于实现步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,hn}选取k个中心点得到分组中心点集合c(c1,c2,...,ck)；第二主模块，用于实现步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,gk)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,gk)；第三主模块，用于实现步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到第四主模块，用于实现步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,hn}表示原始直方图；h1,h2,...,hn表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的整数；c(c1,c2,...,ck)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,gk)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；g1,g2,...,gk表示初始分组集合中的分组序列；g(g1,g2,...,gk)表示通过抽样划分之后得到的最终分组，g1,g2,...,gk表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。
[0074]
本发明实施例提供的基于抽样分组的差分隐私直方图发布装置，采用图2中的若干模块，在分组划分阶段采用指数机制对直方图进行抽样划分，满足差分隐私约束，通过直方图进行抽样近似划分，能够在满足差分隐私的同时，有效地提升分组的准确性；通过对分组过程进行合理优化，提升了分组的准确性，进而降低了发布数据的误差，提升了发布数据的可用性。
[0075]
需要说明的是，本发明提供的装置实施例中的装置，除了可以用于实现上述方法
实施例中的方法外，还可以用于实现本发明提供的其他方法实施例中的方法，区别仅仅在于设置相应的功能模块，其原理与本发明提供的上述装置实施例的原理基本相同，只要本领域技术人员在上述装置实施例的基础上，参考其他方法实施例中的具体技术方案，通过组合技术特征获得相应的技术手段，以及由这些技术手段构成的技术方案，在保证技术方案具备实用性的前提下，就可以对上述装置实施例中的装置进行改进，从而得到相应的装置类实施例，用于实现其他方法类实施例中的方法。例如：
[0076]
基于上述装置实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布装置，还包括：第一子模块，用于实现步骤s1中ε1用于抽样分组，ε2用于分组加噪。
[0077]
基于上述装置实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布装置，还包括：第二子模块，用于实现步骤s2包括以下步骤：s2.1、设置分组数k，其中k＝1,2,3,...,n；s2.2、从原始数据中随机挑选一个桶作为初始中心点c1；s2.3、计算每个桶到已有中心点的最短距离d(x)；s2.4、根据d(x)计算出每个桶被选取作为下一中心点的概率，利用轮盘抽样选取出下一中心点；s2.5、重复步骤s2.3与s2.4，直至选出k个分组中心点c(c1,c2,...,ck)。
[0078]
基于上述装置实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布装置，还包括：第三子模块，用于实现步骤s3包括以下步骤：s3.1将c中每个中心点视为一个单独的分组，得到分组集合g(g1,g2,...,gk)；s3.2将去除中心点的剩余直方图数据放入集合s中；s3.3从s中随机抽取一个桶，计算出抽取桶与每个分组的分组中心的距离u(g,gj)，并将其设置为打分函数:
[0079]
u(g,gj)＝-h-cj[0080]
其中h是从s中抽取的桶，；cj∈c,j＝1,2,3...,k且cj是分组gj的分组中心，打分函数设置应满足要求：抽取桶与分组中心越近，分组被抽样的概率就越大；因此为了满足此要求，采用抽取桶h与分组中心cj之间距离的相反数来构造打分函数；s3.4利用指数机制结合分组距离计算出划分到每个分组的概率pr(g,gj):
[0081][0082]
其中，分组概率pr(g,gj)用以表示分组gj被选为目标分组的概率，ε1表示给定的隐私预算；δu为全局敏感度；u(g,gj)为打分函数；根据全局敏感度的定义可知；打分函数在相邻数据集上的最大变化为1，因此这里的δu＝1，k表示分组数；为分组gj的适应度函数；分子计算的是某一个分组的适应度值，分母计算的是所有分组的的适应度值的总和；s3.5根据每个分组对应的抽样概率；利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；s3.6重复步骤s3.3-s3.5步直至抽取完s中所有的桶，循环结束。得到最终分组方案g(g1,g2,...,gk)。
[0083]
基于上述装置实施例的内容，作为一种可选的实施例，本发明实施例中提供的基于抽样分组的差分隐私直方图发布装置，还包括：第四子模块，用于实现步骤s5中分组添加
噪音的隐私预算为ε2。
[0084]
本发明实施例的方法是依托电子设备实现的，因此对相关的电子设备有必要做一下介绍。基于此目的，本发明的实施例提供了一种电子设备，如图3所示，该电子设备包括：至少一个处理器(processor)、通信接口(communications interface)、至少一个存储器(memory)和通信总线，其中，至少一个处理器，通信接口，至少一个存储器通过通信总线完成相互间的通信。至少一个处理器可以调用至少一个存储器中的逻辑指令，以执行前述各个方法实施例提供的方法的全部或部分步骤。
[0085]
此外，上述的至少一个存储器中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个方法实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0086]
以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。
[0087]
通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件实现。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如rom/ram、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的一些部分所述的方法。
[0088]
附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。基于这种认识，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现方式中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
[0089]
需要说明的是，术语"包括"、"包含"或者其任何其它变体意在涵盖非排它性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其它要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句"包括
……
"限定的要素，并不排除在包括所述要素的过
程、方法、物品或者设备中还存在另外的相同要素。
[0090]
最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.一种基于抽样分组的差分隐私直方图发布方法，其特征在于，包括：步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,h
n
}选取k个中心点得到分组中心点集合c(c1,c2,...,c
k
)；步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,g
k
)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,g
k
)；步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,h
n
}表示原始直方图；h1,h2,...,h
n
表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的整数；c(c1,c2,...,c
k
)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,g
k
)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；g1,g2,...,g
k
表示初始分组集合中的分组序列；g(g1,g2,...,g
k
)表示通过抽样划分之后得到的最终分组，g1,g2,...,g
k
表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。2.根据权利要求1所述的基于抽样分组的差分隐私直方图发布方法，其特征在于，步骤s1中ε1用于抽样分组，ε2用于分组加噪。3.根据权利要求2所述的基于抽样分组的差分隐私直方图发布方法，其特征在于，步骤s2包括以下步骤：s2.1、设置分组数k，其中k＝1,2,3,...,n；s2.2、从原始数据中随机挑选一个桶作为初始中心点c1；s2.3、计算每个桶到已有中心点的最短距离d(x)；s2.4、根据d(x)计算出每个桶被选取作为下一中心点的概率，利用轮盘抽样选取出下一中心点；s2.5、重复步骤s2.3与s2.4，直至选出k个分组中心点c(c1,c2,...,c
k
)。4.根据权利要求3所述的基于抽样分组的差分隐私直方图发布方法，其特征在于，步骤s3包括以下步骤：s3.1将c中每个中心点视为一个单独的分组，得到分组集合g(g1,g2,...,g
k
)；s3.2将去除中心点的剩余直方图数据放入集合s中；s3.3从s中随机抽取一个桶，计算出抽取桶与每个分组的分组中心的距离u(g,g
j
)，并将其设置为打分函数:u(g,g
j
)＝-|h-c
j
|其中h是从s中抽取的桶，；c
j
∈c,j＝1,2,3...,k且c
j
是分组g
j
的分组中心，打分函数设置应满足要求：抽取桶与分组中心越近，分组被抽样的概率就越大；因此为了满足此要求，采用抽取桶h与分组中心c
j
之间距离的相反数来构造打分函数；s3.4利用指数机制结合分组距离计算出划分到每个分组的概率pr(g,g
j
):
其中，分组概率pr(g,g
j
)用以表示分组g
j
被选为目标分组的概率，ε1表示给定的隐私预算；δu为全局敏感度；u(g,g
j
)为打分函数；根据全局敏感度的定义可知；打分函数在相邻数据集上的最大变化为1，因此这里的δu＝1，k表示分组数；为分组g
j
的适应度函数；分子计算的是某一个分组的适应度值，分母计算的是所有分组的的适应度值的总和；s3.5根据每个分组对应的抽样概率；利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；s3.6重复步骤s3.3-s3.5步直至抽取完s中所有的桶，循环结束。得到最终分组方案g(g1,g2,...,g
k
)。5.根据权利要求4所述的基于抽样分组的差分隐私直方图发布方法，其特征在于，步骤s5中分组添加噪音的隐私预算为ε2。6.一种基于抽样分组的差分隐私直方图发布装置，其特征在于，包括：第一主模块，用于实现步骤s1：隐私预算设置：令ε＝ε1+ε2；步骤s2：分组中心选取：设置分组数k，从原始直方图h＝{h1,h2,...,h
n
}选取k个中心点得到分组中心点集合c(c1,c2,...,c
k
)；第二主模块，用于实现步骤s3：抽样分组：将c中每个中心点视为一个单独的分组得到g(g1,g2,...,g
k
)，并对剩余的非中心点桶进行逐次单个抽取，每抽取一次，计算出抽取桶与每个分组的分组中心的距离，利用指数机制结合分组距离计算出划分到每个分组概率，利用轮盘选取目标分组，并将该桶划分到选取的目标分组中；并最终形成g(g1,g2,...,g
k
)；第三主模块，用于实现步骤s4：分组求取均值：将分组g求取均值得到步骤s5：噪声添加：对添加大小为ε2的lapalce噪声得到第四主模块，用于实现步骤s6：对恢复原始直方图顺序得到差分隐私直方图其中，ε为总隐私预算，ε1为抽样分组过程消耗的隐私预算；ε2为分组求取均值之后添加噪声消耗的隐私预算，h＝{h1,h2,...,h
n
}表示原始直方图；h1,h2,...,h
n
表示直方图中的桶，n为原始直方图桶的总数；k表示人为设定的分组中心个数，为非负且非零的整数；c(c1,c2,...,c
k
)表示选取的分组中心点所组成的中心点集合，k表示中心点集合的分组数，其值与k相等；g(g1,g2,...,g
k
)表示将c中每个中心点视为一个单独的分组所得到的初始分组集合；g1,g2,...,g
k
表示初始分组集合中的分组序列；g(g1,g2,...,g
k
)表示通过抽样划分之后得到的最终分组，g1,g2,...,g
k
表示最终分组中的分组序列；表示对最终分组g求均值得到的均值分组，表示均值分组中的分组序列；表示对均值分组添加大小为ε2的拉普拉斯噪声所得到的噪声分组，表示噪声分组中的分组序列；表示对恢复原始直方图顺序的差分隐私直方图。7.一种电子设备，其特征在于，包括：
至少一个处理器、至少一个存储器和通信接口；其中，所述处理器、存储器和通信接口相互间进行通信；所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令，以执行权利要求1至5任一项权利要求所述的方法。8.一种非暂态计算机可读存储介质，其特征在于，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行权利要求1至5中任一项权利要求所述的方法。

技术总结
本发明提供了一种基于抽样分组的差分隐私直方图发布方法及设备。所述方法包括：步骤S1至步骤S6。本发明在分组划分阶段采用指数机制对直方图进行抽样划分，满足差分隐私约束，通过直方图进行抽样近似划分，能够在满足差分隐私的同时，有效地提升分组的准确性；通过对分组过程进行合理优化，提升了分组的准确性，进而降低了发布数据的误差，提升了发布数据的可用性。可用性。可用性。


技术研发人员：黄龙彬 李峰
受保护的技术使用者：武汉航城智慧科技有限公司
技术研发日：2022.10.24
技术公布日：2023/1/6