论文标题：Differential privacy histogram publishing method based on dynamic sliding window

期刊：Frontiers of Computer Science

作者：Qian CHEN, Zhiwei NI, Xuhui ZHU, Pingfan XIA

发表时间：15 Aug 2023

DOI：10.1007/s11704-022-1651-2

微信链接：点击此处阅读微信文章

原文信息

标 题：

Differential privacy histogram publishing method based on dynamic sliding window

原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-022-1651-2

引用格式：

Qian CHEN, Zhiwei NI, Xuhui ZHU, Pingfan XIA. Differential privacy histogram publishing method based on dynamic sliding window. Front. Comput. Sci., 2023, 17(4): 174809

公众号推文链接：

文章精要 | 基于动态滑动窗口的差分隐私直方图发布方法

01 导读

差分隐私是近年来被广泛认可的数据发布严格隐私保护模式，差分隐私直方图发布可以在保证用户隐私的前提下，直接显示统计数据的分布情况，便于数据查询、共享和分析，动态数据发布是一项具有广泛的当前行业需求的研究。然而，不同时期的数据量差异很大，不合理的数据处理会造成用户信息泄露和数据不可用的风险。

因此，本文设计了一种基于LSTM动态滑动窗口的差分隐私直方图发布方法(DPHP-DL)，可以在保证数据隐私的前提下提高数据可用性。DPHP-DL由DSW-LSTM和DPHK+集成而成。DSW -LSTM通过LSTM (long - short - term memory)网络基于数据值预测更新滑动窗口的大小，将数据流均匀地划分为多个窗口。DPHK+启发式发布非等距直方图，基于k- mean++自动聚类获取最优，实现动态数据的差分隐私直方图发布。并且，本文在实际动态数据集上进行了大量实验，证明了DPHP-DL的优越性能。

02 基于LSTM动态滑动窗口的差分隐私直方图发布方法

本文提出了一种基于LSTM动态滑动窗口的差分隐私直方图发布方法(DPHP-DL)，该方法由DSW-LSTM和DPHK+组成。首先，本文介绍了DPHP-DL的过程。随后，分别介绍了DSW-LSTM和DPHK+，并分析了DPHP-DL的隐私性。

为了有效实现随数据流动态变化的启发式非等距直方图发布，本文提出了DPHP-DL(算法1)。首先，使该算法积累一定量的数据，确定初始窗口大小，并通过DPHK+发布初始窗口内数据的直方图。然后，根据DSW-LSTM(算法2)更新每个窗口的大小。接着，根据更新后的窗口大小将窗口滑动到下一个时间戳。同时，基于DPHK+(算法3)发布新窗口的直方图。最后，不断更新窗口大小，发布每个直方图，获得数据流的直方图。

算法1、算法2、算法3分别如下所示：

基于LSTM的动态滑动窗口

本文提出了基于LSTM的动态滑动窗口(DSW-LSTM)来预测统计数据值的动态变化，并根据预测的数据值更新下一个滑动窗口的大小，以平衡窗口之间的数据分布。

DSW-LSTM使用当前窗口数据预测下一个时间戳的数据值，并动态更改窗口大小。该算法首先对当前窗口数据进行训练，并基于LSTM预测下一个戳的数据值。接着，它根据预测值更新窗口大小，并将新的窗口大小应用于下一个时间戳。同时，从滑动窗口中删除时间戳，其中的数据被丢弃或保存到数据库中，而新数据进入滑动窗口。最后，窗口滑动到下一个时间戳，重复上述步骤。

LSTM网络用于数据预测，由于LSTM单元具有遗忘门，故网络可以快速学习数据的新特征，实时更新网络，保证流数据预测的准确性，隐藏的叠加层可以加深模型以获得更准确的输出。本文使用LSTM模型，在窗口批次之间有堆栈，其结构如图1所示。

图1 堆叠LSTM模型结构

堆叠LSTM架构可以定义为由多个LSTM层组成的LSTM模型，上层LSTM层向下层LSTM层提供一系列输出，而不是单个值输出。本文使用堆叠的LSTM来预测下一个时间戳的数据值，从而指导窗口大小的调整。

滑动窗口的大小更新如下:

式中为窗口的固定部分(即初始窗口大小)，为窗口的可变部分，为平均统计值，为预测统计值。是平滑因子，用于防止过大或过小，为比较参数。

表2显示了各种窗口大小更新的示例，假设初始窗口大小为10，的预测值分别为30、24、20、18和10，它们的窗口大小由上述两式计算，三个窗口的大小结果分别为15、10、10、10和5。这个例子表明，如果预测值明显高于平均值，窗口大小将会增加，相反，窗口大小将减小。当统计值在一定范围内变化时，窗口大小保持不变。

基于K-means++的差分隐私直方图发布

本文提出了基于K-means++(DPHK+)的差分隐私直方图发布，实现启发式非等距直方图发布。

首先，使用K -means++算法对当前窗口中不同值的数据进行聚类，其次，根据与SSE的关系图，计算相邻坡度变化度获得最优，得到初始分组结果，最优值为组数。最后在初始分组结果中加入拉普拉斯噪声，实现直方图发布。

最优值的选择对于直方图的有效发布至关重要，根据与SSE的关系图计算相邻坡度变化度如下：首先，记录各点在和SSE图中的坐标，计算每两点之间的斜率。其次，计算每个点对相邻点的斜率变化度，

其中是点和前一点之间的斜率，是点和下一点之间的斜率，是点与其邻点的斜率变化的程度。如果小于阈值，则停止迭代，并且的值作为的最优值对应的最大值被选择，所选择的最优值示例如表1和图2所示。

表1 以和的计算为例，选择最优K值

图2 与SSE的关系图示例

图2显示了和SSE之间的关系。随着值的增大，SSE不断减小，达到一定值后趋于稳定。表1给出了和的计算，从表中可以看出，是到的最大值。因此，本例的最优值为3(即)。

隐私分析

本节算法的隐私性通过满足微分隐私的算法的定义和性质来证明,主要证明直方图发布算法是否满足微分隐私，因为在得到待发布的组后，拉普拉斯噪声会被加入每一组。

证明：在本文的DPHP-DL方法中，使用数据流为每个窗口发布直方图，并使用发布直方图中的组间距按比例分配隐私预算。每个窗口对应一个直方图作为范围查询，因此直方图查询存在于发布的数据流中。在本文的频率直方图中，修改一条记录影响一个数据桶。因此，全局灵敏度为，其计算如下:

其中两个数据流和相邻，只有一条记录差异，数据是带有窗口的频率统计，和分别为第个窗口的频率统计值和窗口大小。

分配给每个窗口的隐私预算为，每一组都满足微分隐私。由于每组数据集彼此不相交，并且。因此，DPHP-DL满足差分隐私。

03 主要贡献

（1）提出了基于LSTM的动态滑动窗口(DSWLSTM)来更新数据流上的滑动窗口，将LSTM用于预测统计数据值的动态变化，并提出了相应的训练方法。下一个窗口的大小可以根据预测的数据值进行更新，改善了窗口之间数据分布的平衡。

（2）提出了基于kmeme++ (DPHK+)的差分隐私直方图发布，实现了当前窗口数据的启发式非等距直方图发布，采用k -means++对已发布的数据进行聚类。自动选择值进行非等距分组，并结合拉普拉斯噪声进行差分隐私直方图发布。该方法考虑了窗口内数据的稀疏性，能够准确反映每个时间窗口内的数据分布。

（3）将PDH-LSTM和DPHK+相结合，提出了一种处理动态变化数据流的DPHP-DL方法。在真实的合成动态数据集上对DPHP-DL进行了实验评估，证明了其在数据隐私性和可用性方面的有效性和高效性。

04 实验分析

本文通过大量的实验，将DPHP-DL与其他有代表性的方法进行比较。首先，通过实验比较了DSWLSTM与FSW和DSW速度的方差[18]。其次，通过SSE和运行时间对DPHK+与DPHK进行比较。第三，使用工作负载误差和运行时开销来评估DPHP-DL和其他代表性方法，包括Baseline、FSWDPHK、FSW-DPHK+、DSWL-DPHK、SHP和DP-FC。最后，对烧蚀进行了研究和分析。此外，各方法的特点及窗口大小设置如表2所示。

表2 所有比较方法的特点和窗口大小设置

方差

当初始窗口大小发生变化时，通过方差将DSW-LSTM与FSW和DSW速度进行比较。FSW的窗口大小始终与初始窗口大小相同，当前DSW速度的窗口大小根据前一个窗口计算的数据速度动态变化。以50步的速度将窗口大小从100增加到300，并将拉普拉斯噪声直接添加到这三种方法的原始直方图中。如图3所示，在所有情况下，DSW-LSTM的方差最小，比FSW和DSW-LSTM平均分别高出41.3%和18.8%。随着初始窗口大小的增加，DSW-LSTM在方差方面的性能优于FSW和DSW速度，这是因为窗口数据量的增加可以提高LSTM的预测精度。

图3 数据流中窗口数据统计的方差

集群性能

直方图发布的有效性和效率受到聚类算法的影响，SSE (Sum of Squared Error)是用来衡量聚类效果的指标。SSE越小，数据点离质心越近，聚类效果越好。因此，本文在固定窗口的Adult数据集上评估了DPHK和DPHK+算法的SSE和运行时性能。DPHK是一种基于-means的差分隐私直方图发布方法，它使用-means算法进行聚类和分组。通过斜率变化程度计算出最优值，并加入拉普拉斯噪声完成直方图发布。

窗口大小每50步从100增加到300，以评估两种直方图发布方法的SSE和运行时间。如图4和图5所示，DPHK+在所有情况下都优于DPHK，它在SSE中平均胜过DPHK 8.8%，在运行时平均胜过DPHK 75.6%。因此，在直方图发布方法中使用-means++可以提高发布效果，显著减少运行时间。

图4 固定窗口内聚类的SSE

图5 固定窗口的聚类运行时间

工作负载误差

本文比较了DPHP-DL与Baseline、FSW-DPHK、FSWDPHK+、DSWL-DPHK、SHP和DP-FC在不同隐私预算和初始窗口大小下在成人数据集、癌症患者数据集和眼病数据集上的工作负载误差，以评估其数据可用性。以0.25的步将从0.5增加到1.5，初始窗口大小为100，用于评估五种方法的工作负载误差。结果显示，DPHP-DL在成人数据集上的所有集合中都优于其他六种代表性方法，它比Baseline、FSW-DPHK、FSWDPHK+、DSWL-DPHK、SHP和DP-FC平均分别高出57.4%、48.0%、35.8%、20.9%、35.0%和29.9%。在癌症患者数据集和眼部疾病数据集上，DPHP-DL在所有情况下的工作量误差都小于其他方法，动态滑动窗口在提高动态变化的数据流的数据可用性方面具有更好的性能。

将初始窗口大小从100增加到300，步骤为50，并设置来评估五种方法的工作负载误差。结果显示，在成人数据集上，DPHP-DL在所有情况下都优于其他四种方法。DPHP-DL平均比Baseline、FSW-DPHK、FSWDPHK+、DSWL-DPHK、SHP和DP-FC分别高出55.5%、43.8%、32.9%、15.2%、27.7%和22.1%。同样，在癌症患者数据集和眼部疾病数据集上，DPHP-DL在所有情况下都优于其他方法。随着窗口大小的增加，窗口内的数据量也会增加，这就增加了每种方法的误差，DPHP-DL生成的误差上升更加平稳。由于每个窗口的数据都在增加，LSTM能更准确地预测数据量，因此，在Windows上的数据更加平衡，并且在所有Windows上的误差比其他方法要小。

以上对比实验结果表明，DSW-LSTM、DPHK+和DPHP-DL的性能优于其他代表性方法，证明了DPHP-DL在提高数据可用性方面的有效性。

运行时间

本文将DPHP-DL与基线方法、FSWDPHK、FSW-DPHK+、DSWL-DPHK、SHP和DP-FC在下的运行时进行比较，初始窗口大小为100，在成人数据集、癌症患者数据集和眼病数据集上评估效率。结果所示，所提出的方法DPHP-DL具有超强的运行时性能，基线、FSW-DPHK、FSW-DPHK+由于其简单的发布模型和难以保证数据隐私和可用性，具有更快的运行时间。

分析

本文比较了组件方法和DPHP-DL的时间复杂度、工作负载误差和运行时间，在成人数据集上，初始窗口大小为100。表3给出了DSW-LSTM、DPHK+和DPHP-DL的时间复杂度、工作负载错误和运行时间的比较，这里是窗口的数量。可以看出，虽然DSW-LSTM比DPHP-DL占用更多的运行时间，但它在提高数据可用性方面发挥的作用更为关键。以上实验表明，DPHP-DL在提高数据保密性和可用性方面具有有效性和高效性。

表3 对构件的研究方法

05 与其他相关研究的对比

现有关于差分隐私直方图发布方法的研究大多集中在静态数据集的发布上。然而，许多应用程序需要持续发布统计数据，类似的动态数据在实际应用中无处不在。对这些数据流进行在线处理，并能够实时发布相关统计数据，将会带来巨大的价值。然而，这些数据流中包含了大量的个人隐私信息。因此，动态数据差分隐私直方图的发布成为一个重要的研究方向。

然而，基于动态数据统计发布的要求和特点，现有的差分隐私直方图发布方法仍然存在一些不足。其中一点就是滑动窗口技术，它是动态数据处理中应用最广泛的技术之一，此技术中的直方图发布方法的窗口大小是固定的，只能处理具有微小变化的数据流。当数据量变化较大时，由于窗口大小固定，会导致窗口之间的数据分布不均匀。差分隐私(DP)可用于抵御像上述示例那样的背景知识攻击，但是，在数据可变的情况下，仍然会导致数据隐私性能较低，数据可用性降低。根据数据流动态改变窗口的大小，可以有效地解决数据分布不均匀的问题。然而，目前数据发布中使用的动态滑动窗口方法无法准确预测数据流中数据量的复杂变化。

而本文提出的一种基于LSTM动态滑动窗口的差分隐私直方图发布方法(DPHP-DL)，便可以很好地解决数据在窗口间分布不均匀、数据稀疏以及动态数据复杂变化带来的隐私泄露和数据不可用问题，并保证数据隐私的前提下提高数据的可用性。

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、 、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn