0 引言

频繁序列挖掘(Frequent Sequence Mining，FSM)是数据挖掘研究领域的一个重要课题，其目的是找出相对时间或其他顺序频繁出现在数据集中的模式，是关联规则、相关性分析、分类、聚类等多种数据挖掘任务的基础。随着大量序列数据的收集和存储，频繁序列模式可以为诸如市场分析、需求预测等数据分析任务提供大量有价值的信息。然而，频繁序列模式本身和其相应支持度计数都有可能泄露隐私信息。

传统隐私保护方法大多基于k-匿名^[1]和划分，这类方法均需要对攻击模型和攻击者的背景知识预先作出假设，无法提供一种有效且严格的方法来证明其隐私保护水平。此外，随着诸如组合攻击和前景知识攻击等新型攻击模型的出现，对这些方法的有效性提出了严峻挑战。差分隐私(Differential Privacy，DP)^[2]是Dwork在2006年提出的一种基于数据失真，独立于攻击者背景知识和计算能力的强隐私保护模型，近年来已成为隐私保护领域的一个研究热点。

当前已有很多文献对差分隐私下的频繁序列模式挖掘进行了深入研究。文献[3-4]提出了两种非交互框架下的频繁序列模式挖掘方法，其关注于序列数据库的发布，挖掘结果效用性较差。不同于文献[3-4]，文献[5-6]提出交互式框架下的频繁序列模式挖掘方法，分别关注于挖掘连续序列模式和一般化的频繁序列挖掘。

尽管文献[6]提出的差分隐私下的频繁序列模式挖掘算法PFS²(differentially Private Frequent Sequence mining via Sampling-based Candidate Pruning)可以解决频繁序列模式挖掘过程中存在的隐私泄露问题。但是，该算法在重构序列数据库时未考虑不同候选序列重要程度的差异性，导致算法准确度低，挖掘结果效用性差。

针对上述问题，本文基于差分隐私，提出一种具有高效用性的频繁序列挖掘策略——DP-FSM(Differential Private Frequent Sequence Mining)算法。该算法主要从两个方面提高挖掘结果的准确度。首先，基于候选集中不同候选序列重要程度的差异性，提出了一种启发式的方法设计打分函数来区分不同候选序列的重要程度，从而能在序列截断时使具有高优先级的候选序列优先保留；其次，针对挖掘频繁序列模式的误差问题，提出一种阈值修正策略，通过判断某序列是否频繁和判断某序列是否用于产生候选序列而设置不同的阈值以减小误差。

1 相关工作

根据挖掘的对象不同，目前差分隐私保护下的频繁模式挖掘研究主要分为频繁项集挖掘和频繁序列挖掘，其中频繁序列挖掘与本文讨论的问题最为相关。

1.1 频繁项集挖掘

近年来，差分隐私下的频繁项集挖掘已取得一些重大的研究进展。Bhaskar等^[7]提出了两种满足差分隐私的top-k频繁项集挖掘策略。这两种方法借鉴截断频率的思想，分别运用拉普拉斯机制与指数机制。Li等^[8]提出一种可用于高维数据的PrivBasis算法，该算法结合θ-基与映射技术在保证计算性能的前提下实现差分隐私保护。张啸剑等^[9]提出一种采用后置处理技术对噪声计数进行求精处理，使输出结果满足一致性要求的方法，该方法能获得较好的可用性。Zeng等^[10]针对长事务会导致高查询敏感性的缺陷，提出了一种基于事务截断技术提高结果可用性的贪婪方法SmartTrunc。上述算法是交互式框架下的频繁项集挖掘方法，但它们只适用于特定的情境，而项集与序列的差异使得这些算法并不适用于挖掘频繁序列模式。

Chen等^[11]提出了一种基于上下文无关分类树,结合自顶向下的树划分方法来发布数据集；Lee等^[12]提出了一种使用前缀树来隐私地发布频繁项集的方法。这两种算法是非交互式框架下的频繁项集挖掘方法，这类方法通过隐私地发布数据集来支持频繁项集挖掘。

1.2 频繁序列挖掘

Chen等^[3]提出一种基于前缀树的方法隐私地发布轨迹数据集，用于支持频繁序列挖掘。此外，他们在文献[4]中还提出了一种基于变长n-gram模型来发布序列数据集的方法。这种方法主要利用变长n-gram模型提取序列数据库的必要信息，利用探索树减少添加噪声的数量。这两种方法与本文方法的不同之处在于前者关注于序列数据库的发布，而本文方法则关注于频繁序列的发布。

Bonomi等^[5]提出了一个满足差分隐私保护的两阶段的频繁连续序列挖掘策略。该方法首先利用一个前缀树来找到所有的候选序列，然后利用数据库局部转换技术细化候选序列的支持度。和这种方法只针对连续序列挖掘相比，Xu等^[6]提出了一个关注于一般化的频繁序列挖掘，忽略序列中的项是否连续的算法PFS²。这个算法的核心是利用一个基于采样的候选剪枝技术来减小候选序列的数目。该技术的主要思想是使用候选序列在样本数据库中的局部噪声支持度来估计该序列是否频繁。

本文的工作更类似于PFS²算法，但PFS²算法在序列重构时将所有候选序列等同看待，而本文则提出了区分不同候选序列重要程度的算法，并提出一种阈值修正策略来提高挖掘结果的准确度。

2 问题定义 2.1 差分隐私

差分隐私保护可以保证对数据集的查询处理结果对于具体某个记录的变化是不敏感的，即在数据集中添加或删除一条数据记录不会对查询的输出结果产生显著影响。因此，即使在最坏情况下，攻击者获得除目标记录外的所有记录信息，仍可以保证这一记录的敏感信息不会被泄露。

如果两个数据集D和D′相差最多为一个记录，则称D和D′为邻居数据集(Neighboring Datasets)。本文使用符号D~D′表示两个数据集是邻居关系。

  定义1  ε-差分隐私^[2]。给定两个邻居数据集D和D′以及一个随机算法A，Range(A)表示A的取值范围。若对于在数据集D和D′上的所有输出结果O(O∈Range(A))，算法A满足下列不等式，则称算法A满足ε-差分隐私。

$\Pr (A(D)\in O)\le {{e}^{\varepsilon }}\Pr (A(D')\in O)$

(1)

其中，参数ε叫作隐私预算，控制着隐私保护的水平。ε越小，表示隐私保护水平越高。差分隐私的含义在于，对于算法的任一可能的输出结果而言，无论函数的输入是数据集D还是D′，得到这一输出的概率相差很小。

设计差分隐私算法的常用技术是向查询或者分析结果中添加噪声使数据失真。添加干扰噪声的大小与查询函数的敏感度密切相关。查询函数的敏感度是指改变数据集中任一记录对查询结果造成的最大改变量。

  定义2  全局敏感度。设有函数f:D→R^d，输入为一数据集D，输出为一个d维实数向量。对于任意的邻居数据集D和D′，函数f的全局敏感度为：

$G{{S}_{f}}=\underset{D\sim D'}{\mathop{\max }}\,||f(D)-f(D')|{{|}_{1}}$

(2)

其中‖·‖₁表示L₁距离。注意:函数的全局敏感度独立于数据集，仅由函数本身决定。不同的函数会有不同的敏感度。常用的计数查询的敏感度为1。

拉普拉斯机制是2006年由Dwork等^[13]提出的一种实现差分隐私保护的方法。该机制的形式化描述如下：给定一个函数f:D→R^d，若一个随机算法A的输出结果满足等式(3) ，则A满足ε-差分隐私。

$A(D)=f(D)+Lap{{(\Delta f/\varepsilon )}^{d}}$

(3)

Laplace机制适用于响应函数的返回值为实数型的情况，其主要思想是在真实的输出值上添加符合拉普拉斯分布的噪声以达到保护效果。添加的噪声量大小与Δf成正比，与ε成反比。对于函数返回值为整数的情况，Ghosh等^[14]提出了拉普拉斯机制的特例——几何机制。该机制添加的噪声大小服从概率密度函数为式(4) 的双边几何分布。本文方法也使用几何机制对频繁序列的支持度添加噪声。

$\Pr (\Delta =x)\tilde{\ }{{e}^{-\varepsilon |x|}}$

(4)

  定理1  几何机制。设f:D→R^d是一个输出为整数、敏感度为Δf的函数。若一个随机算法A的输出结果满足等式(5) ，则A满足ε-差分隐私。

$A(D)=f(D)+G{{(\varepsilon /\Delta f)}^{d}}$

(5)

通常，一个复杂的隐私保护问题通常需要多次运用差分隐私保护算法才能得以解决。在这种情形下，为了保证整个过程满足ε-差分隐私，需要合理地将全部预算分配到各个子过程中。这时经常利用差分隐私保护算法的一个很重要的性质——序列组合性。

  性质1  序列组合性。设有算法A₁,A₂,…,A_n，每个算法A_i提供ε_i-差分隐私，则在同一数据集D上，{A₁,A₂,…,A_n}的序列组合提供($(\sum\limits_{i=1}^{n}{{{\varepsilon }_{i}}})$-差分隐私。

2.2 频繁序列模式挖掘

设字母表I={i₁,i₂,…,i_|I|}，一个序列S是字母表中一些项的有序排列。使用S=s₁s₂…s_|S|表示一个长度为|S|的序列，也称为|S|-序列。一个序列数据库D是输入序列的集合，每个输入序列代表一个人的记录。

通常而言，模式是否频繁取决于模式的支持度与指定阈值的关系。基于这个事实，我们需要知道序列模式支持度的计算方法。在给出支持度的定义之前，先介绍序列的包含关系。

  定义3  包含关系。给定两个序列S=s₁s₂…s_|S|和T=t₁t₂…t_|T|。如果存在整数w₁＜w₂＜…＜w_|S|使得s₁=T_w1,s₂=T_w2,…,s_|S|=T_w|S|成立，则称S包含于T，表示为S⊆T。其中：S是T的子序列，T是S的超序列。

  定义4  支持度。给定一个序列模式S和一个序列数据库D，在D中T的支持度定义为D中包含S的轨迹的数量。也就是说，Sup(T)=|{o|o∈D∧S⊆o}|。

频繁序列模式挖掘的任务就是在给定的序列数据库中找出所有支持度大于给定阈值σ_k的序列模式。然而，在挖掘频繁序列模式过程中存在隐私泄露的风险。基于这一事实，本文提出一种在保护个人敏感信息的前提下隐私地挖掘频繁序列模式的算法。下面先给出本文的问题定义。

问题定义：给定一个语义轨迹数据库D、隐私参数ε和一个阈值σ_k，本文的目标是设计DP-FSM算法来挖掘所有支持度大于σ_k的频繁序列模式，并计算每个频繁序列的支持度。该算法需满足如下要求：1) DP-FSM算法满足ε-差分隐私;2) DP-FSM算法具有较高的数据可用性。

3 DP-FSM算法

为了使FSM满足差分隐私，最直接的方法是利用向下封闭属性^[15]生成所有候选序列(即所有可能的频繁序列)，并对每个候选序列的支持度添加扰动噪声，最后根据噪声支持度选出频繁序列。然而，这种方法结果效用性差。这是由于大量的候选序列会导致大量的扰动噪声，进而导致序列模式的噪声支持度主要取决于噪声，结果会造成严重失真。

基于以上分析，为了准确估计哪些候选序列是频繁的，需要减少添加的噪声量；而添加的噪声量取决于挖掘频繁序列函数的敏感度。根据敏感度的定义，对于计算k-序列支持度的敏感度Δk=min{|C_k|,|C_l^k|}，其中|C_k|表示候选序列的规模。由此可见，函数的敏感度与序列的长度正相关。为此，本文提出的DP-FSM算法通过约束序列长度来降低函数敏感度以提高挖掘序列模式的可用性。

3.1 算法描述

  算法1  DP-FSM算法。

  输入  序列数据库D，百分比η，阈值σ_k，隐私预算ε，字母表I；

  输出  频繁序列及其噪声计数。

  1)  〈l₁,l₂,…,l_n〉=Estimate_Distribution(D,ε₁)

      //估计序列数据库中的序列长度的分布

  2)  计算最小的整数l_max使得∑$\sum\limits_{i=1}^{{{l}_{\max }}}{{{l}_{i}}}\ge \eta $；

  3)  l_f=Estimate_Frequent_Maxlength(D，ε₂，σ_k)

      //估计频繁序列的最大长度

  4)  FS=Mining_FrequentSequence(D,l_max,σ_k,ε₃)

      //利用向下封闭属性^[15]性质按序列长度递增的

      //顺序挖掘所有长度小于l_f的频繁序列；

  5)  输出频繁序列模式及其噪声计数Perturb(FS,ε₄)。

DP-FSM主要由预处理、挖掘和扰动三个阶段组成。

预处理阶段(算法1) ~3) 行)：主要估计最大长度约束l_max和频繁序列的最大长度l_f。

l_max的计算方法如下：首先计算序列数据集D的集势|D|，然后从序列长度为1的开始，递增地计算每个长度为j的输入序列数目a_j，直到p$p=(\sum\nolimits_{j=1}^{{{l}_{i}}}{{{a}_{j}}})/|D|$至少为η为止。由于隐私要求，当计算|D|时需添加几何噪声G(ε₁₁)；计算a_j需添加几何噪声G(ε₁₂)。

l_f的计算方法如下：从1到l_max，计算i-序列的最大支持度，然后向其添加噪声G(ε₂/log(l_max))，选出支持度大于阈值σ_k最大的整数i。

挖掘阶段(算法第4) 行)：算法按照序列长度递增的方式隐私地发现频繁序列扰动阶段(算法第5) 行)：实现比较简单，向直接挑选出的频繁序列的支持度添加几何机制的噪声即可。

以下将着重介绍DP-FSM算法的核心——挖掘频繁序列阶段。

3.2 挖掘频繁序列模式

  算法2  DP-Mining Frequent Sequence。

  输入  频繁序列最大长度l_f，截断序列长度约束l_max，隐私预算ε₃，阈值σ_k；

输出 频繁序列集合FS。

  1)  For(k=1；k≤l_f；k++)

  2)  If k==1 then

    D′←D； C_k←I

    Else

  3)  C_k←Generate_CandidatSet(S_k-1)；

  4)  D′=Truncate_Database(D，C_k，l_max)  //截断数据库；

  5)  S_k←Choose_Candidate_Seed(D′，C_k，ε′，σ_k)；

  6)  FS_k=Discover_Frequent_Sequence(D′，C_k，ε′，σ_k)；

  7)  FS=FS+FS_k；

  8)  Return FS；

算法2描述了隐私地挖掘频繁序列模式的过程，其核心思想是利用候选序列在截断序列数据库D′中的噪声支持度判断该候选序列是否频繁。同时，为了提高挖掘结果的准确度，该算法从两个方面对阈值进行修正:1) 截断序列数据库后会造成某些候选序列频率信息的损失，考虑到这种截断情况产生的误差(称之为截断误差)，该算法修正判断阈值σ_k为σ_k-avg(θ′)+θ′，其中avg(θ′)为根据序列的噪声支持度θ′估计该序列在原数据库中的平均支持度。2) 如果一个频繁序列模式被错误地标注为不频繁的模式，则它的任何超序列在不计算其支持度的情况下即被判定为不频繁的序列模式。考虑到这种情况产生的传播误差，修正判断某一序列是否用于产生候选序列的阈值为σ_k-max(θ′)+θ′，其中max(θ′)为根据序列的噪声支持度θ′估计该序列在原数据库中的最大支持度。

1) 截断序列数据库。这一步的目的是转换序列数据库使其满足长度约束。理想情况下，当收缩序列时，希望新得到的序列既满足长度约束又保存尽可能多的潜在频繁序列模式的频率信息。基于此，提出一种序列收缩的方法，通过无关项删除、连续模式压缩和智能序列重构三种策略收缩序列的长度。

a)无关项删除。

给定一个序列，当一个项不包含在任何候选序列中时，显然这个项对于候选集中任何序列模式的支持度无贡献。这样的项称为无关项，从序列中删除无关项不会导致任何频率损失。

基于向下封闭性质，如果一个项对于候选k-序列是无关项，那么对于长度大于k的候选序列也是无关项。

例1 设有序列A=abababebcdfg及候选2-序列集合{ab,bc,cd,ac}，则efg为无关项，删除后为A₁=abababbcd。

b)连续模式压缩。

一个序列可能包含一个连续出现的序列模式。对于k-序列的估计，可在不引起任何频率信息损失的情况下压缩连续的j个序列模式为连续的k个序列模式。这是由于在候选k-序列中的k个项最多来自k个模式。继续上面的例1，序列ab在A₁中出现3次，则可用2个连续模式去代替它，即A₂=ababbcd。

c)智能序列重构。

无关项删除和连续模式压缩在不导致频率(支持度)损失的情况下有效地收缩了序列。然而，在经过这两种方法处理轨迹序列后，某些序列仍然违背序列长度约束。直观地，收缩一个序列时仅需保留频繁序列的子序列，这是由于不频繁的子序列对频繁序列的支持度无贡献。然而，我们的目标是隐私地找到这些频繁的序列模式，为此提出一个启发式的方法预测某一个候选序列是否是频繁的。在实际生活中，如果一个候选序列的所有子序列是充分频繁的，那么该候选序列很可能是频繁的序列模式。基于这个观察，对每个候选i-序列(i≥2) 分配一个频率分。

  定义5  频率分。给定一个频繁(i-1) -序列的集合GS={S₁,S₂,…,S_d}，一个i-序列X的频率分数为:

$fs(X)=\underset{{}}{\mathop{\sum\limits_{{{S}_{i}}\subset GS\Lambda {{S}_{i}}\subset X}{{{S}_{i}}.\sup '}}}\,$

(6)

其中，S_i.sup′代表序列S_i的噪声支持度。

收缩序列时，需要保留高频率分数的序列，因此该问题可表述为:给定一个候选序列的集合X={X₁,X₂,…,X_d}，找到最优的l_max-序列S_lmax，使得该序列的覆盖分最高。其中覆盖分为:$cs({{S}_{l\max }})=\sum\limits_{{{S}_{i}}\subset {{S}_{l\max }}\Lambda {{S}_{i}}\subset X}{fs({{S}_{i}})}$。

但找到最优的l_max-序列这个问题是NP-hard的，为此提出一个贪心算法来收缩序列。贪心算法的思想如下：对于每条序列，迭代地添加包含在输入序列中高频率分数的候选序列，直到重构的序列达到最大集势。同时，我们注意到一个候选序列的频率分不应该是静态的:当一个候选序列的一些子序列已经添加到重构序列中后，为了使重构序列包含候选序列，该候选序列需要添加的子序列中项的数目少于其他候选序列。因此，在一个候选序列的一些子序列已经添加到重构序列后，应更新受影响的候选序列的频率分。

更新策略如下：假设一个候选序列X_i被添加到重构轨迹序列中，需更新集合X的频率分。对于每个剩余候选序列X_j⊂{X₁,…,X_i-1,X_i+1,…,X_d}，计算单个项的得分α_j=fs(X_j)/i。假设已在重构序列中的最大子序列包含的项的数目为β_j，则更新候选序列的频率分为 fs(X_j)=fs(X_j)+α_j*β_j。

例2 继续上面的例1，同时假设候选序列的权重情况如下集合所示：{ab:8;bc:6;cd:4;ac:2}；以及假设序列限制长度为4。经过无关项删除机制和连续模式压缩机制处理后，序列A由序列A₂=ababbcd表示，但它的长度依然大于限制长度4，因此需要根据智能序列重构机制处理。依据该规则，首先选取ab加入到结果序列t′中去，然后更新候选序列bc的权重为6+1×8/2=10。cd的权重保持不变，ac的权重更新为2+1×2/2=3。则将bc添加到事务t′中，此时t′=abc，长度仍小于约束长度4。再按同样的方法进行下一次迭代，得到t′=abcd。此时t′的长度已达到了序列限制长度，因此，用序列abcd表示原序列A=abababebcdfg。

2) 阈值修正。为了弥补截断误差和传播误差导致的频率信息的损失，受“双重标准”机制^[10]的启发，提出一种新的支持度预估方法。该方法根据序列在转换后事务数据库中的噪声支持度估算序列在原始数据集中真实支持度信息，进而使用平均支持度来判断该序列是否频繁，使用最大支持度决定该序列是否会被用来生成候选序列。具体地来说，新的支持度预估方法主要由以下两步组成。

第一步：给定序列X的噪声支持度θ′，估算序列X在转换后数据集中的真实支持度θ^real。根据“双重标准”中给定的定理可以得出：

$\Pr ({{\theta }^{\text{rea}l}}\text{ }\!\!|\!\!\text{ }{\theta }')\approx {{e}^{-}}^{\varepsilon ({{\theta }^{real}}-{\theta }')}$

(7)

第二步：根据序列在转换后数据集中真实支持度θ^real，进一步估计序列在原始数据集中的真实支持度θ。这里通过分析随机截取方法产生的信息损失来衡量截断序列数据库方法产生的信息损失量。直观地，给定一个长度为l的序列记录t，若将t截取为t′序列记录，如果t中不包含序列S，则t′事务中也必然不包含序列S。因此只需要利用包含序列S的截断序列记录来计算其支持度。给定长度为l的序列记录，将长度为|t|包含i-序列S的事务t截取为t′序列记录，截取为t′序列记录包含i-序列S的概率为：

$Pr=C_{l-i}^{|t|-i}/C_{l}^{|t|}$

(8)

将序列S在转换后数据集中的支持度看为随机变量，则该变量的期望是：

$E({{\theta }^{\text{real}}})=\theta *(\sum\limits_{j=1}^{l}{{{\partial }_{j}}+\sum\limits_{j=l+1}^{|t|}{{{\partial }_{j}}\frac{C_{l-i}^{j-i}}{C_{l}^{j}}}})$

(9)

与“双重标准”中计算最大支持度和平均支持度的方法相似，给定序列在转换后数据集中的支持度θ^real，则序列在原始数据库的平均支持度：

$avg({{\theta }^{\text{real}}})=\frac{{{\theta }^{\text{real}}}}{(\sum\limits_{j=1}^{l}{{{\partial }_{j}}+\sum\limits_{j=l+1}^{|t|}{{{\partial }_{j}}\frac{C_{l-i}^{j-i}}{C_{l}^{j}}}})}$

(10)

序列在原始数据库的最大支持度：

$\begin{align} & \max ({{\theta }^{''}})= \\ & \left\{ \begin{array}{*{35}{l}} \frac{{{\theta }^{''}}-\ln \rho +\sqrt{\ln \rho *(\ln \rho -2{{\theta }^{''}})}}{\sum\limits_{j=1}^{l}{{{\partial }_{j}}+\sum\limits_{j=l+1}^{|t|}{{{\partial }_{j}}\frac{(\frac{j-i}{l-i})}{(\frac{j}{l})}}}}; & \ln \rho \le 2{{\theta }^{''}} \\ avg({{\theta }^{''}}); & \ln \rho >2{{\theta }^{''}} \\ \end{array} \right. \\ \end{align}$

(11)

结合第一步和第二步的结论，给定序列在转换后数据集中的噪声支持度θ′，我们估算该序列在原始数据集中平均支持度为：

$avg({\theta }')=\sum\limits_{i=0}^{+\infty }{\Pr (i|{\theta }')avg({\theta }')}$

(12)

最大支持度为：

$\max ({\theta }')=\sum\limits_{i=0}^{+\infty }{\Pr (i|{\theta }')\max ({\theta }')}$

(13)

综上，在挖掘频繁序列模式过程中利用i-序列S的平均支持度来判断该序列是否频繁，利用最大支持度来决定该序列是否会被用来生成候选(i+1) -序列。换句话说，我们在判断是否频繁时将阈值σ_k修正为σ_k-avg(θ′)+θ′；在判断某序列是否用于生成候选序列时阈值σ_k修正为σ_k-max(θ′)+θ′。

4 隐私性能分析

以下首先对DP-FSM算法各阶段的隐私性能进行分析，然后利用差分隐私的序列组合性(性质1) 给出整个算法的隐私性能结果。

预处理阶段： 对于序列数据库的集势|D|的计算，由于添加(删除)一个输入序列只影响|D|变化1，则这个计算的敏感度为1。因此，在计算时添加几何噪声G(ε₁₁)满足ε₁₁-差分隐私。相似地，计算a_j的敏感度为1，添加G(ε₁₂)也满足ε₁₂-差分隐私。因此，根据差分隐私的序列组合性，计算l_max满足ε₁差分隐私。对于l_f的计算，当估计每个i-序列的最大噪声支持度时向其加入符合G(ε₂/log(l_max))的噪声，文献[2]已给出证明，表明该过程符合ε₂-差分隐私。

挖掘阶段： 在此阶段，算法首先产生候选序列集C_k和截断序列数据库D′。这两个操作由于仅依赖于(k-1) -序列的噪声支持度，故不消耗任何隐私预算。接下来，算法使用候选序列的噪声支持度估计频繁候选序列集合和用于产生候选序列的种子节点集合。为了减少在挖掘过程中添加噪声的量，算法使用序列收缩方法对序列数据库的长度进行了约束。由于一个长度为l_max的序列最多可以获得C^k_lmax个不同的k-序列，因此增加或者删除一条序列最多影响min{|C_k|,|C^k_lmax|}个k-序列的支持度变化1。这意味着计算C_k的支持度的敏感度Δk=min{|C_k|,|C^k_lmax|}。因此，向C_k的支持度中添加G(ε′/Δk)满足ε′-差分隐私，其中ε′=ε₃/l_f。由于上述过程重复l_f次，则整个过程满足(ε₃/l_f*l_f=ε₃)-差分隐私。

扰动阶段：扰动阶段的主要目标是向挑选出的频繁序列集合FS的真实支持度中添加噪声达到隐私保护的目的。此时，增加或者删除一条序列最多影响|FS|个频繁序列的支持度变化1，则计算频繁序列集合FS的支持度计数的敏感度为ΔFS=|FS|。因此，向FS的支持度计数添加G(ε₄/ΔFS)满足ε₄-差分隐私。

  定理2  DP-FSM算法满足ε-差分隐私，其中ε=ε₁+ε₂+ε₃+ε₄。

证明 可以根据差分隐私的序列组合性(性质1) 直接得出结论。

5 实验结果与分析

以下通过实验来评估DP-FSM算法的性能，实验环境为CPU Inter Core i7-2600，频率3.40 GHz，8 GB内存，500 GB硬盘，Windows 7操作系统,所有的代码用C++编程语言实现。实验中将DP-FSM与目前最先进的隐私地挖掘频繁序列的算法PFS²进行比较。由于算法涉及到随机化，算法各运行15次后取平均值作为结果发布。

5.1 实验设置

实验中使用两个真实序列数据集：BIBLE^[16]和MSNBC(http://kdd.ics.uci.edu/databases/msnbc/msnbc.html)，数据集的参数设置如表 1所示。

实验采用以下两种可用性度量指标来衡量DP-FSM的性能。设FSP(D)表示数据集D中的真实频繁序列模式集合,$FSP(\tilde{D})$表示DP-FSM算法挖掘的频繁序列模式集合。

1) 拒真率(False Negative Rate,FNR)：衡量$FSP(\tilde{D})$中的模式不在真实的频繁序列模式集合FSP(D)的比例，即反映不希望出现在输出结果中的模式占总体模式的比值。FNR值越小说明发布的频繁序列模式集合$FSP(\tilde{D})$越接近于真实的频繁序列模式集合FSP(D)，算法的可用性越高。其计算公式如下：

$FNR=1-\frac{|FSP(D)\cap FSP(\tilde{D})|}{|FSP(D)|}$

(14)

2) 相对支持度误差(Relative Support Error,RSE)：衡量FSP()中的一个模式的支持度相对于支持度阈值σ_k的平均误差率，其计算公式如下：

$RSE=\frac{\sum\limits_{X\in FSP(D)}{Sup(X)}-\sum\limits_{\tilde{X}\in FSP(\tilde{D})}{Sup(\tilde{X})}}{{{\sigma }_{k}}|FSP(D)|}$

(15)

其中：$\sum\limits_{X\in FSP(D)}{Sup(X)}$表示FSP(D)中所有模式的支持度总和，$\sum\limits_{\tilde{X}\in FSP(\tilde{D})}{Sup(\tilde{X})}$表示$FSP(\tilde{D})$中所有模式的支持度总和。RSE越小说明算法的可用性越高。

5.2 实验结果 5.2.1 DP-FSM和PFS²算法的性能比较

图 1(a)分析了在数据集MSNBC上阈值参数σ_k对FNR的影响。需要注意的是，实验中的阈值是指相对于整个数据集大小的比例。从实验结果可以看出，随着阈值参数σ_k的增大，PFS²算法的FNR呈现增大的趋势，这意味着随着σ_k的增大，PFS²算法挖掘结果的准确度降低，算法性能变差；而DP-FSM算法的FNR总体上呈现相对稳定的趋势。除此之外，从实验结果上看，就FNR而言，DP-FSM算法的性能总体上优于PFS²算法的性能。

上述实验结果是合理的。原因如下：阈值σ_k的增大意味着用于判断序列是否频繁的支持度变大，这样使得更多的序列变为非频繁的序列。PFS²算法在重构序列时未考虑候选序列频繁程度的差异性，很有可能导致频繁序列在截断序列数据库时未被保留，进一步导致根据噪声支持度错误地判断该候选序列为非频繁的序列模式。而DP-FSM算法由于在截断序列数据库时考虑了候选序列的差异性，有效地减小了误差。

图 1(b)分析了在数据集MSNBC上阈值参数σ_k对两个算法的RSE的影响。从实验结果可以看出，随着σ_k的增大，DP-FSM算法的RSE变化不大，而PFS²算法的RSE也呈现增大的趋势。这种现象是由于随着σ_k的增大，对频繁序列设置的阈值要求更高。PFS²由于在重构序列时未考虑候选序列的差异性，导致结果集中含有大量的非频繁序列；又由于非频繁序列的支持度较低，故根据式(15) ，可得出随着σ_k的增大，PFS²算法的RSE增大。

图 2是算法DP-FSM和PFS²在数据集BIBLE上的性能结果。从中可以看出，这两个算法在该数据集的性能总体趋势与在数据集MSNBC上大体相似。

5.2.2 阈值修正策略对DP-FSM算法性能的影响

为研究阈值修正策略对DP-FSM算法准确度的影响，将不带阈值修正策略的挖掘频繁序列模式的算法称为DP-RS。图 3分析了阈值修正策略随着σ_k的变化对算法性能的影响。从中可以看出，带阈值修正的DP-FSM算法的性能优于不带阈值修正策略的DP-RS算法，并且随着阈值参数σ_k的增大，两个算法的性能差异性越大。因为阈值修正策略减少了挖掘频繁序列过程中的截断误差与传播误差，故相对于DP-RS算法，DP-FSM算法的准确度较高。又由于随着σ_k的增大，对频繁序列的要求更为严格，DP-RS算法由于误差的存在导致结果集中存在许多非频繁模式，从而导致FNR增大；并且大多非频繁模式的支持度较低，故DP-RS算法的RSE也较大。

6 结语

本文首次针对频繁序列模式挖掘过程中的隐私泄露问题,提出了一种满足ε-差分隐私的算法DP-FSM。该算法首先从候选集中挖掘所有频繁序列模式，然后采用几何机制对挑选出来的模式的支持度添加几何噪声扰动。除此之外，为了提高挖掘结果的可用性，本文提出了一个阈值修正策略来减小挖掘过程中的截断误差和传播误差。最后，通过实验验证了该算法在满足差分隐私的前提下可获得较高的数据可用性。在未来的工作中，我们将研究如何合理地分配隐私预算使得挖掘结果的准确度达到最高值。