基于差分隐私的频繁序列模式挖掘算法

针对当数据集含有敏感信息时,直接发布频繁序列模式本身及其支持度计数都有可能泄露用户隐私信息的问题,提出一种满足差分隐私（DP）的频繁序列模式挖掘（DP-FSM）算法。该算法利用向下封闭性质生成候选序列模式集,基于智能截断方法从候选模式中挑选出频繁的序列模式,最后采用几何机制对所选出模式的真实支持度添加噪声进行扰动。另外,为了提高挖掘结果的可用性,设计了一个阈值修正的策略来减小挖掘过程中的截断误差和传播误差。理论分析证明了该算法满足ε-差分隐私。实验结果表明了该算法在拒真率（FNR）和相对支持度误差（RSE）两个指标上明显低于对比算法PFS²,有效地提高了挖掘结果的准确度。     

一种面向数据流top-k频繁模式发布的差分隐私保护方案

频繁模式挖掘是事务数据分析的常用技术,面向数据流的频繁模式挖掘具有重要的应用价值.然而当事务为敏感信息时,直接发布频繁模式及支持度会导致个体隐私泄露.差分隐私是一种严格且可证明的隐私保护模型,目前虽然已有基于差分隐私的频繁模式发布方案,但它们大都是面向静态数据做一次性发布的隐私保护.本文是面向数据流频繁模式发布的隐私保护,旨在设计一种兼顾可用性和发布效率的持续发布的差分隐私保护方案.与静态发布方案不同,面向数据流的隐私保护处理面临两大挑战:一是持续发布过程中隐私预算的累计消耗会造成发布结果可用性较低;二是候选模式集增大会造成发布结果误差较大和发布效率较低.为解决隐私预算的累计消耗问题,方案设计了满足event级差分隐私的保护机制.该机制可以最大化隐私预算利用率,提高发布结果可用性.为降低候选模式集大小,从而提高发布结果可用性和发布效率,方案首先设计了一种基于模式估计的长事务拆分预处理策略,并对拆分所致的信息丢失率进行了分析和弥补.然后在持续发布阶段,在基于Cantree的挖掘中,先基于支持度阈值对候选模式集进一步缩减.基于缩减后的候选模式集,本文设计了一种蓄水池抽样和指数机制(EM)相结合的持续更新发布策略,该策略通过一遍扫描抽样集,在保证可用性和隐私保护级别的前提下提高了发布效率.最后,理论证明了该方案满足ε-差分隐私,实验结果验证了该方案具有较好的可用性和较高的工作效率.     

本地化差分隐私下的频繁序列模式挖掘算法PrivSPM

序列数据中可能包含大量敏感信息,因此直接对序列数据的频繁模式进行挖掘存在泄露用户隐私信息的风险。本地化差分隐私（LDP）能够抵御具有任意背景知识的攻击者,可以对敏感信息提供更全面的保护。序列数据内在序列性和高维度的特点为LDP应用于频繁序列模式挖掘带来了挑战。为解决这个问题,提出一种满足ε-LDP的top-k频繁序列模式挖掘算法PrivSPM。该算法结合填充和采样技术、自适应频率估计算法与频繁项预测技术来构造候选集;基于新域,利用基于指数机制的策略对用户数据进行扰动,并结合频率估计算法识别最终的频繁序列模式。理论分析证明了该算法满足ε-LDP。在3个真实数据集上的实验结果表明,PrivSPM算法在纳真率（TPR）和归一化累积排名（NCR）上明显高于对比算法,能有效提高挖掘结果的准确度。     

基于事务分离的差分隐私频繁项集挖掘方法

频繁项集挖掘在加入差分隐私后将带来敏感度过高、噪声过大、数据可用性较差的问题。为了解决这些问题，提出了基于事务分离的差分隐私频繁项集挖掘方法。利用指数机制对事务最大限制长度进行筛选，将长事务分离成为多个短事务，以此降低全局敏感度并避免截断误差的产生。在数据挖掘过程中，采用Apriori算法挖掘频繁项集，利用双阈值进行项集判断以及修正支持度，减小传输误差的产生和噪音。实验结果表明，该方法满足差分隐私的要求，可有效提高数据可用性。     

差分隐私的数据流关键模式挖掘方法

频繁模式挖掘是数据挖掘的重要任务之一，在数据流上挖掘简洁的关键模式比频繁模式更有优势，因为关键模式既可以避免频繁模式里包含的冗余信息以减少内存存储空间，又可以高效无损地提取频繁模式.但是由于相邻时间戳的统计信息可以作为背景知识增强攻击者的推理能力，所以从包含个人信息的数据流中挖掘关键模式比静态场景下更容易泄露隐私.分析指出了数据流关键模式挖掘的隐私泄露问题及原理，并提出了一种满足差分隐私的数据流关键模式挖掘算法DP-CPM，该算法在每个时间戳设计一种两阶段机制：差异计算阶段和噪音挖掘阶段.该机制既考虑了隐私和数据效用之间的权衡，又考虑了挖掘时间和维护开销之间的权衡.为了提高数据流中连续发布时的数据效用性，在第1阶段通过计算差异来决定当前时间戳是返回低噪音统计值还是精确的近似统计值.如果是返回低噪音统计值，算法进入噪音挖掘阶段.在噪音挖掘阶段，首先通过判断查询集筛选出关键模式候选集，然后通过给筛选出的候选集里的模式支持度加入服从拉普拉斯分布的随机噪音，得到最终的噪音支持度.最后，给出了严格的理论分析和大量的实验，表明DP-CPM算法的有效性和执行效率.     

基于差分隐私的轨迹模式挖掘算法

针对现有基于差分隐私的频繁轨迹模式挖掘算法全局敏感度过高、挖掘结果可用性较低的问题,提出一种基于前缀序列格和轨迹截断的差分隐私下频繁轨迹模式挖掘算法--LTPM。该算法首先利用自适应的方法获得最优截断长度,然后采用一种动态规划的策略对原始数据库进行截断处理,在此基础上,利用等价关系构建前缀序列格,并挖掘频繁轨迹模式。理论分析表明LTPM算法满足ε-差分隐私;实验结果表明,LTPM算法的准确率（TPR）和平均相对误差（ARE）明显优于N-gram和Prefix算法,能有效提高挖掘结果的可用性。     

基于差分隐私的流式直方图发布方法

基于差分隐私保护模型,已经存在多种静态数据集上的直方图发布方法,而目前着重考虑数据流环境下的直方图发布方法却很少.由于数据流本身潜在的复杂性,直接利用现有的满足差分隐私的直方图发布方法处理数据流存在着很多不足,例如发布直方图的可用性低、发布误差大等.基于此,提出了一种基于滑动窗分割的流式直方图发布方法SHP(streaming histogram publication).该方法通过连续分割每个滑动窗中的桶计数,使其构成不同的分组.根据不同的范围计数查询敏感性,提出了3种拉普拉斯噪音添加机制以实现差分隐私保护,分别是滑动窗机制、时间点机制以及自适应抽样机制.在自适应抽样机制中,SHP算法基于当前的滑动窗,依赖于一种自适应抽样方法对下一时刻的计数进行预测,若预测值与真实值的差异小于给定的阈值则发布预测值,否则发布噪音值.该抽样方法可以有效地节省整体的隐私预算.在真实数据集上对SHP算法的可用性进行度量,结果显示,基于抽样的SHP算法的可用性高于另外两种方式.     

一种有效的差分隐私事务数据发布策略

近年来,隐私保护事务数据发布得到了研究者的广泛关注.事务数据的稀疏性导致个体隐私保护与数据效用性之间很难达到平衡.目前已有的方法大多是基于分组的匿名模型,但该类模型依赖于攻击者背景知识,且发布的数据无法满足事务数据分析任务的需要.针对事务数据隐私保护发布的数据安全性与效用性不足,基于差分隐私与压缩感知理论,提出一种有效的面向应用的事务数据发布策略(transaction data publish strategy,TDPS).首先构建事务数据库的完整Trie项集树,然后基于压缩感知技术对项集树添加满足差分隐私约束的噪音得到含噪Trie项集树,最后在含噪树上进行频繁项集挖掘任务.实验结果表明,TDPS不仅能很好地保护隐私,而且能有效保持数据效用性,满足事务数据分析任务对数据质量的要求.     

基于Spark的支持隐私保护的聚类算法

针对经典聚类方法无法应对任意背景知识下恶意攻击者在海量数据挖掘过程中的恶意攻击问题,结合差分隐私保护机制,提出一种适用于Spark内存计算框架下满足差分隐私保护的聚类算法,并从理论上证明了改进算法满足在Spark并行计算框架下的ε-差分隐私。实验结果表明,改进算法在保证聚类结果可用性前提下,具有良好的隐私保护性和满意的运行效率,在海量数据聚类分析的隐私保护挖掘中,具有很好的应用前景和价值。     

基于差分隐私的不确定数据频繁项集挖掘算法

基于不确定数据的频繁项集挖掘算法已经得到了广泛的研究。对于记录用户敏感信息的不确定数据,攻击者可以利用自己掌握的背景信息,通过分析基于不确定数据的频繁项集,从而获得用户的敏感信息。为了从不确定的数据集中挖掘出基于期望支持度的前K个最频繁的频繁项集,并且保证挖掘结果满足差分隐私,在本文中,FIMUDDP算法（Frequent Itemsets Mining for Uncertain Data based on Differential Privacy）被提出来。FIMUDDP利用差分隐私的指数机制和拉普拉斯机制确保从不确定数据中挖掘出的基于期望支持度的前K个最频繁的频繁项集和这些频繁项集的期望支持度满足差分隐私。通过对FIMUDDP进行理论分析和实验评估,验证了FIMUDDP的有效性。