(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211109967.4 (22)申请日 2022.09.13 (71)申请人 中南民族大 学 地址 430074 湖北省武汉市洪山路民族大 道182号 申请人 武汉空天软件技 术有限公司 (72)发明人 孟博　张国兴　王德军　李子茂　 (74)专利代理 机构 武汉科皓知识产权代理事务 所(特殊普通 合伙) 42222 专利代理师 张辰 (51)Int.Cl. G06F 21/62(2013.01) (54)发明名称 基于分组合并的差分隐私直方图发布方法 及设备 (57)摘要 本发明提供了一种基于分组合并的差分隐 私直方图发布方法及设备。 所述方法包括： 步骤 S1至步骤S5。 本发明通过对直方图采用分组合并 的方式， 对数据进行合理准确的划分， 有效的提 升了分组划分的准确性， 进而降低了发布数据的 误差， 提升了数据的可用性， 可 以实现直方图分 组最优划分， 大幅度降低噪音对 数据准确性带来 的影响， 在满足差分隐私约束的同时， 有效的提 升了数据的可用性和发布效率。 权利要求书3页 说明书9页 附图2页 CN 115495778 A 2022.12.20 CN 115495778 A 1.一种基于分组合并的差分隐私直方图发布方法， 其特征在于， 包括： S1： 隐私预算划 分， 将隐私预算 ε划分为 ε1和 ε2； S2： 分组合并， 首先设置 最终合并分组数K， 并将 原始直方图H ＝{h1,h2,...,hn}中的每个桶为一个单独的分组， 得到分组集合g(g1,g2,...,gn)； 然后对g 中分组进 行两两合并， 并遍历出所有的合并方案， 计算出每个合并方案的方案距离， 通过指 数机制选取合并方案进行近似合并,并将合并后的方案视为一个新的分组， 替代原有的两 个分组， 重复上述合并过程， 直至达到最 终分组数K， 并得到最 终合并方案， 形成直方图分组 G(G1,G2,...,Gk)； 其中： H＝{h1,h2,...,hn}表示原始直方图序列； h1,h2,...,hn表示直方图 中的桶， n为原始直方图桶的总数； g(g1,g2,...,gn)表示合并前的初始分组集合； g1,g2,..., gn表示初始分组集合中的分组， 每个分组由一个桶组成， 因此初始分组总数为n； G(G1, G2,...,Gk)表示合并得到的最终分组集合， G1,G2,...,Gk表示最终分组集合中的分组， Gk表 示第K个分组； S3： 对G的每个 分组求取均值得到 其中 表示求取 均值后的均值分组集合； 表示第K个均值分组； S4： 对 添加Laplace噪声得到 其中： 表示由均值分组集合添加噪音得到的噪音分组集合； 表示第K个添加噪音的分组； S5： 对 恢复原始直方图顺序， 得到发布的差分隐私直方图 其中： 表示由 恢复原始直方图顺序得到的差分隐私直方 图； 表示直方图中添加噪音的桶； n表示差分隐私直方图桶的总数。 2.根据权利要求1所述的基于分组合并的差分隐私直方图发布方法， 其特征在于， 步骤 S1中的隐私预算 ε是 给定的正 值， 并且 ε 1用于分组合并， ε2用于分组添加噪声。 3.根据权利要求2所述的基于分组合并的差分隐私直方图发布方法， 其特征在于， 步骤 S2的实现具体包括： S2.1设置最终分组数K， 其中， K＝1,2,...,n， n为直方图的分组数； S2.2 将原始直方图H＝{h1,h2,...,hn}中的每个桶视为一个单独的分组， 得到分组集合g(g1, g2,...,gn)； S2.3对直方图内的分组进行两两合并， 遍历出所有可能的合并方案P(p1, p2,...,py)； 其中： P(p1,p2,...,py)表示合并方案 集合； p1,p2,...,py表示有所有可能的合并 方案； y表示方案总数； S2.4计算出每个合并方案的方案距离u(p,ps)， 并将其设置为效用函 数： 其中： ps(gi,gj)为方案集合P中的一个合并方案， Ps中包含两个分组 gi和gj， h为gi中的某 个桶， h′表示gj中的某个桶， 表示分组之间的最小距离， 该距离用来衡量分 组之间的相似性， 效用函数设置应满足要求： 分组之间的距离越小， 被合并的概率也就越 大； 为后续概率计算满足此要求， 采用分组距离的相反数 来构造效用函 数； S2.5利用指数机制结合方案距离计算出每 个合并方案的抽样概 率Pr(p,ps)：权　利　要　求　书 1/3 页 2 CN 115495778 A 2其中， 合并方案概率Pr(p,ps)表示合并方案Ps被选取概率， ε1为隐私预算； Δu为全局敏 感度； u(p,ps)为Ps的效用函 数； 由全局敏感度的定义 可知， 在数据集中删除任意一 条记录对 效用函数的影响最大为1， 因此Δu＝1， y表示方案总数； 为合并方案Ps的 适应度函数； 分子计算的是合并方案Ps的适应度值， 分母计算的是所有合并方案 的适应度 值的总和； S2.6根据每个合并方案的抽样概率； 利用轮盘对合并方案进 行选取； S2.7将 选取 到的合并方案进行合并， 并将其视为一个新的分组， 替代原有的两个分组； S2.8重复S2.3 ‑ S2.7， 直到合并为K个分组， 循环结束； S2.9返回最终合并方案G(G1,G2,...,Gk)。 4.根据权利要求3所述的基于分组合并的差分隐私直方图发布方法， 其特征在于， 步骤 S2中， 若直方图的桶数目为 n个， 则分组也 为n个。 5.根据权利要求4所述的基于分组合并的差分隐私直方图发布方法， 其特征在于， 步骤 S4中对 添加的Laplace噪声的大小为 ε2。 6.根据权利要求5所述的基于分组合并的差分隐私直方图发布方法， 其特征在于， 步骤 S5中的差分隐私直方图 的维度为 一维。 7.一种基于分组合并的差分隐私直方图发布装置， 其特征在于， 包括： 第一主模块， 用 于实现S1： 隐私预算划分， 将隐私预算ε划分为ε1和 ε2； 第二主模块， 用于实现S2： 分组合并， 首先设置最终合并分组数K， 并将原始直方图H＝{h1,h2,...,hn}中的每个桶为一个单独的 分组， 得到分组集合g(g1,g2,...,gn)； 然后对g中分组进行两两合并， 并遍历出所有的合并 方案， 计算出每个合并方案的方案距离， 通过指数机制选取合并方案进 行近似合并,并将合 并后的方案视为一个新的分组， 替代原有的两个分组， 重复上述合并过程， 直至达到最 终分 组数K， 并得到最终合并方案， 形成直方图分组G(G1,G2,...,Gk)； 其中： H＝{h1,h2,...,hn}表 示原始直方图序列； h1,h2,...,hn表示直方图中的桶， n为原始直方图桶的总数； g(g1, g2,...,gn)表示合并前的初始分组集合； g1,g2,...,gn表示初始分组集合 中的分组， 每个分 组由一个桶组成， 因此初始分组总数为n； G(G1,G2,...,Gk)表示合并得到的最终分组集合， G1,G2,...,Gk表示最终分组集合中的分组， Gk表示第K个分组； 第三主模块， 用于 实现S3： 对G 的每个分组求取均值得到 其中 表示求取均值后的均值分组集 合； 表示第K个均值分组； 第四主模块， 用于实现S4： 对 添加Laplace噪声得到 其中： 表示由均值分组集合添加噪音得到的噪音分组集合； 表示第K个 添加噪音的分 组； 第五主模块， 用于实现S5： 对 恢复原始直方图顺序， 得到发 布的差分隐私直方图 其中： 表示由 恢复原始直方图顺序权　利　要　求　书 2/3 页 3 CN 115495778 A 3