频繁序列挖掘中基于局部差分隐私的算法

我D-1沙特国王大学学报基于局部差分隐私的频繁序列挖掘王腾a、王伟、胡志ba中国陕西Xi邮电大学网络空间安全学院b中国陕西西北大学信息科学与技术学院阿提奇莱因福奥文章历史记录：2022年1月4日收到2022年3月23日修订2022年4月20日接受2022年4月25日在线提供保留字：频繁序列挖掘局部差分隐私前缀树构造数据实用程序A B S T R A C T频繁序列挖掘（FSM）是大数据时代分析序列数据的基础然而，收集和分析序列数据会给用户带来严重的隐私问题局部差异隐私（LDP）是数据统计和分析的一种流行的隐私范式由于序列数据的高维性，直接将LDP应用于FSM面临着严重的挑战，如严重的扰动，浪费隐私预算，准确性差，计算成本高 本文提出了两种 具有高数据利用率和低计算代价的LDP兼容有限状态机机制PrivFSM和PrivFSM/。具体地说，PrivFSM迭代构造序列到一个前缀树下LDP挖掘频繁序列从巨大的领域。此外，PrivFSM利用基于阈值的修剪策略来修剪伪节点，这减少了扰动和计算成本。作为PrivFSM的增强版本，PrivFSM<$2 不再分割隐私预算，而是对用户集进行分区以避免严重的噪声。 PrivFSM<$通过在每次迭代中使用完整的隐私预算来应用整个数据，从而最大限度地利用用户数据。我们对真实世界和合成数据集上的错误约束和广泛的实验进行了理论分析实验结果表明，与其他国家的最先进的机制相比，我们提出的算法的高数据效用版权所有©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍序列数据的大量产生和深度挖掘极大地推动了大数据时代各种实际应用的发展，如推荐系统、众包系统（Okolica et al. 2020; Yan等人，2020; Sunhare等人，2020年）。频繁序列挖掘（FSM）（ Renz-Wieland 等人， 2019; Srivastava 等人， 2021; Anwar 和Uma，2019）是分析连续数据的基本组成部分，几十年来变得更加普遍。有限状态机可以从大规模数据中挖掘出频繁序列，发现一些特殊情况或提供有价值的见解。然而，挖掘和发布这样的频繁序列可能对个人的私人信息造成严重威胁，例如行为、位置轨迹、网页浏览历史、甚至基因序列（Liuetal.，2020; Errounda和Liu，2021; Ma等人， 2021年）。*通讯作者。电子邮件地址：wangteng@xupt.edu.cn（T. Wang）。沙特国王大学负责同行审查制作和主办：Elsevier为了减轻隐私泄露，大量研究应用集中式差分隐私（DP）（Dwork和Roth，2014）来进行FSM，同时为用户提供隐私保证（Xu等人，2015; Bonomi和Xiong，2013; Xu等人，2016; Cheng等人， 2015年）。然而，集中式DP总是在可信服务器的保护下工作，因此不能防止由不可信服务器引起的局部差分隐私（LDP）（Duchi等人，2013; Wang等人， 2017a）被提出作为DP的分布式变体，其在本地扰动客户端上的每个用户的数据。自从LDP被引入以来，它已被广泛用于许多数据统计和分析任务，例如均值/频率估计（Wang et al.， 2019a），k路边缘（Wang等人，2019 b），机器学习（Arachchige et al.，2020）等。此外，LDP还被部署在许多流行的软件系统中，例如Google Chrome浏览器（Erlingsson等人，2014）和苹果iOS（差分隐私团队，2017）。因此，本文采用LDP作为频繁序列挖掘的隐私原则在有限状态机上应用LDP时，由于序列之间的顺序性假设一个序列是从d个项目的宇宙中绘制的，用户序列的最大长度然后，所有用户之间的序列的最大域将达到Pld i¼ dl1-d。再说了，你所有用户拥有的序列。 即实际https://doi.org/10.1016/j.jksuci.2022.04.0131319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comT. Wang和Z. 胡沙特国王大学学报3592序列结构域不能容易地确定总之，高维性在四个方面带来了挑战i）对每个序列中的每个数据进行扰动会严重扭曲真实序列，导致严重的扰动和低的数据效用。ii）将隐私预算分成l个部分导致隐私预算的浪费iii）整个序列中大量重复的子序列大大降低了挖掘结果的频率准确性。iv）收集和分析序列的所有可能组合负面地导致高计算开销。针对上述挑战，虽然有许多研究工作可以借鉴，但很难直接应用于频繁序列挖掘。其中，频繁新词发现是最接近频繁序列挖掘的问题之一.例如，Fanti等人（2016）提出了RAPPOR的增强版本（Erlingsson等人， 2014）只收集n-gram而不是完整的术语，这可以处理大量的英文字母组合，降低了高昂的成本。Kim等人（2020）提出了一种称为CCE（循环链编码）的新算法，用于从LDP下的数据中发现新词。类似地，CCE利用n-gram的链式规则和基于指纹的过滤过程来提高计算效率。为了提高数据效用，Wang et al.（2018 a）提出通过在LDP下迭代构建trie来收集频繁项。然而，频繁新词发现不同于频繁序列挖掘，因为后者除了高维问题外，还需要考虑其他额外的复杂问题。首先，数据收集和分析的场景是不同的，导致现有的方法（Fanti等人，2016; Wang等人，2018a; Kim等人， 2020年，不能直接使用。有限状态机的重点主要是收集频率，统计的是在所有输入序列中出现的序列的总数;而频繁新术语发现主要集中在文档频率，计算的是包含序列的用户数量。第二，整个序列中重复的子序列导致较大的搜索空间，这在频繁新术语发现中没有考虑。然而，当采用树结构对序列数据建模时，会出现重复节点，这在新术语发现中不会发生（Wang et al.，2018年a）。因此，LDP下的有限状态机还需要进一步的研究。在本文中，我们提出了两个符合LDP的频繁序列挖掘机制（即， PrivFSM和PrivFS M⁄）具有高数据利用率和低计算成本。我们的主要贡献总结如下。该算法通过迭代构造序列到一棵符合LDP规范的前缀树中，从巨大的序列域中挖掘频繁k为了减少扰动和计算成本，PrivFSM杠杆年龄基于阈值的修剪策略修剪假节点。在每次迭代中自适应地更新阈值。提出了一种改进的机制PrivFS M/2，通过划分数据而不是分割隐私预算来进一步减少噪声添加。PrivFSM<$通过在每次迭代中使用完整的隐私预算来最大限度地利用用户我们在真实世界和合成数据集上进行了广泛的实验。所有实验结果表明，我们提出的机制保持高的数据效用，同时实现了强的隐私保证。其余的文件组织如下。第2节提供了一个文献综述。第三节对研究问题进行了形式化描述，并介绍了一些基本概念。第4节介绍了我们提出的解决方案下的有限状态机LDP。第5节给出了实验结果。第六节是论文的总结。2. 相关工作频繁序列挖掘（FSM）可以从大规模序列数据中发现丰富的知识和 益 处 ， 在 大 数 据 时 代 已 被 广 泛 采 用 （ Srivastava et al.（2021））。 为了保护隐私，经典的差分隐私（DP）已经被许多研究采用来进行FSM（Xu et al.，2015;Bonomi和Xiong，2013; Xu等人，2016; Cheng等人，2015年）。具体而言，Bonomi和Xiong（2013）提出了一种基于模型的机制，该机制构建了马尔可夫模型以减少扰动噪声。 Xu et al. （2015）和Xu et al.（2016）开发了一种DP兼容的FSM算法，该算法涉及基于采样的candidate剪枝策略，以提高私有估计的准确性。此外，Cheng et al.（2015）专注于最大频繁序列挖掘，并提出了一种DP-MFSM机制，该机制利用数据集划分技术来提取预期的频繁序列。然而，由于这些研究都采用集中式DP作为隐私模型，并假设服务器是可信的，他们不适合分布式场景。近年来，局部差分隐私（LDP）（Duchi等人，2013;Wang等人，2017 a）已经成为许多应用中分布式数据隐私保护的流行隐私范例（Wanget al.，2020年）。已经提出了现有技术的算法来实现用于频率/均值估计的LDP（Wang 等人，2017 a; Wang 等人，2019a）、边际释放（Wang et al.，2019 b），机器学习（Arachchigeet al.，2020; Wei等人，2021）等。此外，集值数据的频繁项/项集挖掘也是众多研究的重点，这些研究试图解决集值数据领域庞大、项集大小异构的难题。巴西利等人（2017）提出通过构建二叉树来从大型域中发现频繁项，这提高了效率和准确性。此外，Wang et al. （2021）提出了一种前缀扩展方法（PEM），该方法将用户划分为大小相等的组，并使每个组与特定的前缀长度相关联，从而降低了计算成本。为了解决每个用户记录的项目数量不同的挑战，一些研究（Qin等人，2016; Wang等人，2018 b）利用填充和采样策略，通过将虚拟项添加到低于大小的记录中来将项填充到固定大小。发 现 频 繁 出 现 的 新 术 语 也 得 到 了 广 泛 的 研 究 。 RAPPOR（Erlingsson等人， 2014）是LDP的第一个实际部署，用于收集Chrome使用情况的统计数据。之后，改进的版本（Fanti等人，2016）的RAPPOR旨在进一步发现频繁的新术语，通过构建n-gram而不是完整术语来减少巨大的术语域。为了进一步提高数据效用并降低计算成本，Wang et al.（2018 a）提出了PrivTrie，将术语构造成trie并利用自适应用户分组策略。此外，针对LDP下的按键数据发现新词，Kim等. （2020）提出了一种循环链编码机制，该机制利用n元语法的链规则来提高计算效率。综上所述，目前的频繁序列挖掘隐私保护机制都采用集中式差分隐私作为隐私保护原则，无法应用于没有可信第三方服务器的分布式场景。局部差分隐私（LDP）是一种新的隐私范式，它为每个参与用户提供本地的隐私保证。LDP自问世以来，已被广泛应用于各种场合。然而，LDP下的频繁序列挖掘（FSM）现在从未进行过。LDP下与有限状态机相对接近的工作是频繁项挖掘和频繁新术语发现。然而，由于序列数据的序列性，现有的研究不能直接应用于在LDP下进行FSM。●●●●T. Wang和Z. 胡沙特国王大学学报3593ω2P21/4 f···gP¼½· ·····]h！ ！伊泽 ！我！ ！！！ 我2019年12月28日 ！！！快看！！伊希伊PmM满足s-LDP.我PMSbS6es·PMS0简体中文1/2bS;1/2b S因此，本文提出了PrivFSM和PrivFSM，首先处理有限状态机下的LDP，同时实现高数据利用率。Phb^i¼1ip<$1;如果bi<$1q¼e1个;如果b1/40ð2Þ锡吉3. 预赛3.1. 问题陈述设II1;I2; ;I d 是所有元素的宇宙，其中d是宇宙的大小。请注意，我们使用项目来表示序列中的单个元素或操作一个项目的语义因应用的不同而例如，一个项目可以是网络浏览历史监控下的网站，或移动跟踪系统中的位置，或DNA序列中的核碱基每个序列S都是来自论域I的项目的（时间/逻辑）有序列表。设N为用户数，U为用户集每个用户u，j，2U，j，2 1/21;N，j拥有一个序列S，j。 让S½hs1！ s2！···表示长度为k的序列，其中每个元素siI. S也被称为k序列，因为它包含k个连续的项。然后，聚合器可以计算作为p-Q目标值伊比岛通过将OUE应用于我们的问题与分类属性，每个分类值我我是编码成一d位向量B 0; ; 0; 1; 0;; 0，其中只有第i位是1。然后，我们可以通过使用OUE来扰动B4. 我们的解决方案由于序列数据的高维性，本文采用前缀树来表示序列。假设根节点位于前缀树的第0层。具有相同前缀的序列将被构建到前缀树的相同分支中表1中序列的前缀树如图1所示。在形式上，我们定义前缀如下。例如，第一条记录hI1！I2！表1中的I3i是3-定义2（前缀：P）。对于序列S¼ hs！ s！ ！ si，顺序为了简单起见，我们可以在某些上下文中使用S1/4s2···sk元素s的前缀在S12升S来表示S 1/4h！s2！··· 斯基岛此外，我们使用符号i是from的子序列表示的级联的两序列的比如说，I1I2I3I2I3I1I2I3I2I3.基于序列的支持度，我们将频繁序列定义为所有序列数据中的前x个因此，在本报告中考虑的自民党下的FSM给定阈值x和序列长度k，聚合器的目标是在所有列中找到前x个最多的k序列。选择N个用户的序列数据，同时实现对每个用户的。3.2. 本地差异隐私在没有对中心服务器或数据聚合器的任何假设的情况下，局部差分隐私（LDP）（Duchi等人，2013; Wang等人，2017a）可以通过使用随机响应技术来保护客户端（本地）侧的用户在形式上，LDP定义如下。定义1（s-LocalDifferential Privacy（s-LDP））.随机化机制M满足s-LDP当且仅当对于任意输入元组对S和S0，以及对于任意可能的输出bS，从s i开始，记为Ps ihs1！s2！··· 锡岛由于我们的目标是找到频繁的k-序列，因此我们也定义了一个序列的k-前缀如下。定义3（k-前缀：Pk）。 对于序列S 1/4 hs1！ s2！· ！ s li，S中元素s iiPk的k前缀是S中从s i的位置开始的k个先前项，表示为Pksihsl-k1！ sl-k12！ ··· 锡岛例如，给定序列S 1/4 hI3！ I2！ I1！ I4！ I1i;P I4I3I2I1I4和P3I4I2I1I4. 注意本文主要研究频繁k序列挖掘。因此，我们在下文中主要关注k前缀特别地，我们关注kP2表1采样序列数据。#序列一比一！ I2！ I3二比一！ I2三我三！ I2！ I1喜喜。 吉吉四我一！ I2！ I3五比一！I2！ I36I3！其中P表示概率。s是隐私预算。小一点的S意味着更强的隐私保护，反之亦然。LDP继承了差分隐私的可组合性我们在我们的机制中利用LDP的顺序组成，如下所示。定理1（顺序合成）。设每个Mi是一个si-LDP算法，M是M1;···; Mm的顺序合成.然后，1/1LDP的基本机制。用于频率估计的最先进的LDP机制已经被广泛研究，其在Wang 等人中被全面总结。（2020 年）。随机响应（RR）（Warner，1965）是实现LDP的主要方法，它通过允许用户对敏感查询做出合理的响应来在RR的基础上，优化的一元编码（OUE）（Wang等人，2017 b）被提出来扰动单个比特bi2 f 0; 1g，并报告具有概率的噪声输出bi^i七比一！ I2！ I3！ I18I3！ I2！ I3！ I2！ I1九我三！ I2！ I3！ I2！ I3Fig. 1. 表1中的序列的前缀树用于频繁3-序列挖掘。T. Wang和Z. 胡沙特国王大学学报3594¼ð Þ！！！！¼ð Þ因为k 1相当于频繁项挖掘，这在以前的工作中已经研究过，例如Qin etal.（2016）和Wang et al. （2021年）。为了实现隐私保护，我们使用LDP私下收集用户数据。使用符合LDP的算法的关键挑战是频繁序列的未知域。因此，在本发明中，我们的算法通过以自顶向下的方式基于用户的报告数据构建加权前缀树T来开始。每一个T的节点v（除了根节点）都是一个连续序列的项。P kv表示节点v的k-前缀，它是T的一条路或子路。并且，权重cv是节点v的k-前缀Pkv的支持，即，Pkv的出现数。图2示出了我们提出的解决方案的高级流程图（即，PrivFSM和PrivFS M/），其中PrivFS M/自适应地更新可用用户集以优化采样用户。在下文中，我们将首先介绍我们的基本解PrivFSM，然后介绍最优解PrivFS M<$.4.1. 碱性溶液在给出LDP下的频繁k序列挖掘算法之前，我们首先描述了几个观察结果，这些观察结果暗示了处理大规模序列数据时的关键问题，并将用于指导我们算法的设计。观察结果1：收集频率。一个用户的序列可以涉及多个重复的k序列而不是仅一个。 例如，表1中的第9个序列给出了3-序列I3的两个支持I2I3，即3-序列I3I2I3在整个序列中出现两次。这是指收集频率，它计算出现在所有输入序列。相反，序列的文档频率是指包含该序列的用户数量。在我们的算法中，我们考虑的集合频率是更复杂的文件频率的情况下，有限状态机。我们所提出的算法可以很容易地转换为计算LDP下的文档频率，只需要设置一个标志来判断一个序列是否被记录。基于观察1，前缀树T中的节点，其支持k-前缀大于零时，应直观地展开。然而，由于噪声的引入，这种方法会产生大量的假节点，增加了T中噪声的大小。因此，在我们的解决方案中采用支持阈值h来限制假鼻子的爆炸性增长，这将在后面讨论。观察2：重复节点。需要解决的第二个重要观察是前缀树T的一些特殊节点不需要进一步分裂。因为这类特殊节点的k-序列在前一个节点中已经被估计出来了。为了避免估计过高，我们将直接将这些特殊节点标记为修剪过的例如，如图所示。 1，节点v 16的3-前缀我是3！ I2！ 我3，并有一个支持2。但是，我们不会拆分节点v16. 这是因为，在访问节点v 16之前，我们已经分裂节点v 13以生成节点v 17 、v 18 和v19 。 基 于 节点v1 7 、v1 8 和v1 9 ， I2！ I3！I1;I2！ I3！ 我 2 ，我 2！ I3！ 我3估计。 一旦分割了v16，新的3前缀就与节点v 17、v 18和v 19的3前缀相同。因此，这些前缀的支持将被重复估计，导致不准确的估计。下面的引理1和引理2展示了如何判断那些特殊节点（如图1中的节点v 16）。①的人。下面我们把这些特殊的节点称为重复节点。引理1. 前缀树中重复节点的层数必须大于等于k，重复节点最早出现在第k层。引理2. （是否重复？） 设v c是当前节点v的子节点，V e是v c的k-1前缀序列的集合. 对于kP2，if序列Pk-1vc的子节点vc包含在V e 中，则v将是一个重复的节点，不会被添加到未访问的节点集中。观察3：隐私预算分配。为了实现s-LDP，前缀树的每一级的隐私预算是s=l，因为前缀树以虚拟根节点vr开始，其中l是序列的最大长度算法1综合考虑了以上三点，给出了在LDP下的频繁序列挖掘算法PrivFSM在PrivFSM中，聚合器基于报告的数据以自顶向下的方式构建前缀树所有用户都基于OUE机制上报数据，实现LDP保护。具体地，聚合器首先创建具有虚拟根的前缀树T节点v r，表示为AAAAA（线1）。聚合器还两组，即，包含未访问节点的未访问集合Vu，以及包含候选频繁k序列的候选集合Vc， （第2行）。将根节点添加到未访问集（即， V u<$V u[fv rg）（第3行）。图二. 建议解决方案的流程图。T. Wang和Z. 胡沙特国王大学学报3595ð Þð Þð ÞHðÞ关于我们nfnfv算法1：符合LDP的频繁序列挖掘算法：PrivFSM（s;k;h;l）然后，聚合器从上到下迭代地拆分Vu中的节点，直到未访问集合Vu为空，如第4行所示18.每次将节点v从Vu中出列时，如果树T的深度等于当前节点v的深度，则我们将Ve树的长度小于用户序列的长度T：深度h。为了避免如观察2中所解释的重复，应保持Pk-1v c基于RV e关于Lemma2此外，我们还需要确保1不失一般性，请注意，这里我们只添加序列Pk-1vc长度为k-1或Pk的函数vc将长度为k的函数v c代入Ve或Vc，因为我们只关注其中N是总用户数，U-1是累积密度函数的倒数，nf是伪节点可以产生的子节点数，nv是参与节点v支持度估计的用户数，p和q是扰动概率。证据设Ph为噪声通过h的概率。在构建前缀树时，一旦出现伪节点，伪节点的后代数量将以系数nfPh呈指数累积。这将导致过多的噪声和巨大的计算开销。为了解决这个问题，我们设置nfPh61，即，Ph61。使用基于OUE的挖掘频繁k序列。LDP算法，对k-前缀Pk∈v的无偏估计，T. Wang和Z. 胡沙特国王大学学报3596p-Q1/1.X.2p-q你好-你好-nvnf.Σnq1-qvf···g bcBC拉吉吉S2N [2019 -02-22]2019-02 - 2200：00：001/1我~N与E1/4v-nvq，则它成立，2NOl22002年，）Pr. Ev6nvhP1-1）U-pN节点v是Ev <$$>Iv-nvq，其中Iv是Pk<$v的支持，收到。将xi和^xi分别表示为真实数据和扰动数据。然后，我们有Iv<$Pnv^xi。实际上，我们可以把Iv看作-根据Bernstein“的。 N.#nv个二项变量的表示基于OUE，我们可以知道n^xi-xi≠1的概率是q。因此，双-P½j^cv-cvjPk]¼Pfo^iv-oivgPk1/1mial变量^xi-xi服从二项分布Bnv;q。从二项变量的正态近似性质，62·exp.-Pk23二项分布Bnv;q可以由正态分布给出，K2nvq;nvq1-q。p-Q¼2·exp @-。 A.A.Ev~N.0;nvq1-q！ð4Þ此外，对于所有N 用户，节点v的估计支持度为^Ev. 设Pr^cvPh是估计的为了确保^cvcv2和x50时，F分数大于0.7 PrivFS M<$的良好性能主要取决于最优的用户划分和前缀树构造。如 图 4 、 PrivFS M<$u 的 准 确 度 明 显 高 于 其 他 三 种方 法 。PrivFSM的Fscore是consis-明显低于PrivFS M⁄and PrivTrie，因为它们需要将s分成小部分，从而导致低精度。然而，比较PrivFSM和BSL这两种划分隐私参数的方法，前者总是比后者更准确。这表明我们提出的PrivFSM可以保持较高的数据比BSL在设置分裂s的实用程序。此外，两个PrivTrie表2序列数据集的特征。名称基数项目数（d）LmAvg.序列长度长度>lm的序列的数量MSNBC九八九，八一八17204.849,490圣经36,36913,9054521.641810SYN100,00010030300图三.不同数据集上的Fscore结果随k而变化（s1;x1）。T. Wang和Z. 胡沙特国王大学学报3599¼图四、MSNBC数据集上的Fscore结果（k¼3）。和BSL的Fscore明显低于PrivFS M/2，因为它们不是处理频繁序列挖掘的专家。当s越大，BSL、PrivTrie和PrivFSM的F值越大。盟友改善，但仍然一贯低于PrivFS M⁄。图5和6分别在数据集BIBLE和SYN上使用相同的参数设置重复相同的实验。可以再次观察到，PrivFSM<$总是比其他三种方法获得更大的Fscore这再次证明了PrivFS M<$确保了实践中的高精度。此外，通过比较图。 4-6，我们可以看到所有算法的相对性能与数据集MSNBC上的相同。相比之下，BIBLE数据集的Fscore通常低于MSNBC和SYN数据集。这是因为BIBLE数据集的总体规模很小，项目域很大，因此总体准确率相对较低。此外，SYN数据集的Fscore通常大于BIBLE，但小于MSNBC。类似地，这是因为SYN 数据集具有比BIBLE更大的群体大小和更小的项目域，但比MSNBC更大的项目域。5.2.2. 再评价这一部分给出了四种算法在三个数据集上的RE结果，如图2和图3所示。七比九我们比较了这些算法通过改变s从1到4和x从10到70。首先，从图。如图7 -9所示，我们可以看到PrivFS M/在所有情况下都保持最小的RE，这大大优于其他三种方法。 值得注意的是，PrivFSM⁄ s的RE始终低于0.3，当x为10时。在相同的设置中，其他方法的RE是更高。 这证明了PrivFS M<$.这也显示了PrivFS M/中涉及的最优用户划分和前缀树构造ion的优点。我们还可以观察到，当s变大时，所有算法的RE都减小。原因很明显，较小的s引入更多的扰动。此外，所有算法的RE将随着x的增加而增加。如图在图7（d）、8（d）和9（d）中，当x1/470时，在大多数情况下，三个数据集上的BSL和PrivFSM的RE超过0：6。这表明，将s分为FSM中的小部分将引起大量的扰动，从而降低精度。我们提出的PrivFSM<$i利用了一个最佳的用户分区策略