位置获取技术的兴起和互联网技术的蓬勃发展产生了大量的轨迹数据, 例如车辆、人的位置信息、用户行为信息。在轨迹数据上挖掘频繁模式, 其目的是找出频繁出现在数据中的模式, 是关联规则、相关性分析、分类、聚类和其他数据挖掘任务的基础, 被广泛应用于用户行为分析、交通规划、推荐系统等领域。然而从敏感数据库例如位置信息中乘客乘车和下车点信息、互联网用户点击流信息中挖掘出的频繁模式本身的内容以及支持度计数信息都有可能泄露个人隐私信息或者披露个人的真实身份。攻击者获得某些模式的支持度计数之后, 可以利用额外的背景知识进行攻击。例如表 1中b表示某一敏感位置, 攻击者想窃取“Tom是否去过b位置”这种信息。通过分析获知b为频繁模式, 其真实支持度计数为5。如果攻击者已经知道其他4人去过b位置, 则可推理出Tom也去过b位置, 进而导致Tom的敏感位置泄露。因此, 在挖掘频繁模式的过程中, 如何保护模式的支持度计数是主要的技术挑战。
|
表 1 轨迹数据库 Table 1 Trajectory dataset |
近年来，出现了几种差分隐私保护下的模式挖掘算法[1-5], 文献 [6]为了解决事务数据库高维度的难题, 将高维度的数据库转化为低维度, 结合θ-基和映射技术提出了PrivBasis算法, 根据θ-频繁对构建出候选集合, 最后对候选集合的所有项的频度添加噪声, 而后选取top-k频繁模式。
文献 [8]结合自顶向下的前缀树, 第一次提出了发布轨迹数据库的Prefix算法, 支持频繁模式挖掘。该算法对序列模式对应的真实支持度计数添加拉普拉斯噪声, 构建前缀序列树, 最终发布满足差分隐私的轨迹数据库。文献 [9]提出的N-gram算法为了降低序列维度的影响, 限制序列的最大长度为lmax。上述几种算法通过降低序列的维度或限制序列的最大长度来提高挖掘结果的可用性, 然而这些算法存在以下问题:
问题1 PrivBasis算法和N-gram算法虽然考虑到序列维度的影响, 但是仍然存在全局敏感度过高的问题；而且PrivBasis和N-gram算法仅适用于短序列居多的数据库，Prefix和N-gram算法限制序列长度的算法存在较大的信息损失。
问题2 从大规模轨迹数据库中挖掘频繁模式时, 常常会产生大量满足最小支持度阈值的序列集合, 序列冗余较严重, 而且上述算法均没有设计一种比较好的隐私预算的分配策略, 导致添加的噪声量很大, 从而造成挖掘结果可用性低下。
总而言之, 目前还没有一种很有效的频繁轨迹模式挖掘算法能够同时兼顾上述两个问题, 提高挖掘结果的可用性, 为此, 本文提出一种融合轨迹截断和前缀序列格的频繁轨迹模式挖掘算法——LTPM (Lattice-Trajectory Pattern Mining)。首先, 在满足差分隐私的前提下, 利用自适应的方法获取最优截断长度, 接下来采用动态规划策略对轨迹数据库进行截断处理, 然后基于前缀序列格结构压缩频繁轨迹模式, 避免隐私预算重复分配。
本文的主要工作:
1) 为了解决问题1, 本文基于动态规划策略提出一种满足差分隐私的轨迹序列截断算法DP_Trunc, 在有效降低全局敏感度的同时, 减少截断算法带来的误差。
2) 为了解决问题2, 提出基于前缀序列格的频繁轨迹模式挖掘算法LTPM, 借鉴Clospan算法[13]思想, 利用轨迹模式间的等价关系有效压缩频繁轨迹模式规模, 减少序列冗余, 避免隐私预算的重复分配。
3) 理论分析了LTPM算法满足ε-差分隐私, 通过真实数据库上的实验结果表明, LTPM在数据可用性方面优于N-gram算法和Prefix算法。
1 相关工作满足差分隐私的频繁模式挖掘的研究已取得很多成果。文献 [5]利用拉普拉斯机制[3]和指数机制[4]提出两种差分隐私下频繁模式挖掘算法, 从固定长度的模式中选取支持度最大的k个模式, 并对其添加噪声作为top-k频繁模式, 但是该算法受k值的影响比较大。文献 [6]为了解决事务数据库高维度的难题, 将高维度的数据库转化为低维度, 结合θ-基和映射技术提出了PrivBasis算法, 根据θ-频繁对构建出候选集合, 最后对候选集合的所有项的频度添加噪声, 而后选取top-k频繁模式。该算法适用于k值比较小的情况, 当k比较大时, 该算法的可用性会很低。文献 [7]分析了事务长度对全局敏感度的影响, 发现数据库中记录的最大长度与全局敏感度成正比, 为此提出一种基于事务截断的算法Smart Trunc来限制事务数据库的长度, 并通过双重标准降低截断算法带来的误差, 进而提高挖掘算法的可用性。该算法应用在短事务居多的事务数据库性能较高, 而在其他数据库中性能较差；并且该算法不支持频繁序列挖掘。文献 [8]结合自顶向下的前缀树, 第一次提出了发布轨迹数据库的Prefix算法, 支持频繁序列挖掘。该算法对序列模式对应的真实支持度计数添加拉普拉斯噪声, 构建前缀序列树, 最终发布满足差分隐私的轨迹数据库；但随着前缀序列树的增长, 每一子分割的序列数量会急剧减小, 严重影响发布序列的可用性。文献 [9]提出的N-gram算法为了降低序列维度的影响, 限制序列的最大长度为lmax。该算法应用在短事务居多的数据库时精度较高，但对于长序列居多的数据库，其可用性比较差, 而且存在较多的信息丢失。文献 [10]在设计DP-FIM (Differential Privacy Frequent Itemset Mining)时, 考虑到长事务数据处理导致信息损失和效率低下的问题, 提出了包含智能权重截取和支持度评估的DP Apriori算法。文献 [11]提出了一个频繁序列挖掘算法PFS2, 其核心是利用一个基于采样的候选剪枝技术来减小候选序列的数目, 并使用候选序列在样本数据库中的局部噪声支持度来估计该序列是否频繁。该算法未考虑不同候选序列重要程度的差异性, 导致挖掘结果可用性低下。文献 [12]提出的DiffPart算法基于上下文无关分类树, 自顶向下从根节点开始迭代地进行子分割并生成叶子节点, 再根据叶子节点的噪声计数重构并发布扰动后的集值型数据库, 支持频繁模式挖掘。DiffPart算法发布精度高, 但仅支持计数查询, 未考虑不同项之间的语义关系。
综上所述, 上述算法均存在各自的不足, 为此本文提出一种融合轨迹截断和前缀序列格的频繁轨迹模式挖掘算法LTPM, 以有效降低全局敏感度, 提高挖掘结果的可用性。
2 定义和概念 2.1 差分隐私相对于传统保护模型, 差分隐私保护模型具有两个显著的特点:1) 定义了一个相当严格的攻击模型, 不关心攻击者拥有多少背景知识。假设攻击者已掌握除某一条记录之外的所有记录信息, 该攻击者也无法从统计结果中推测出这条记录是否存在于数据集中。2) 对隐私保护水平给出了严格的定义和定量分析评估方法。
定义1 近邻关系。设T={t1, t2, …, tn}为原始轨迹数据库, T′={ t1, t2, …, tr-1, tr+1, …, tn}, T与T′相差一条记录, 则二者互为近邻关系。
结合T与T′给出ε-差分隐私的形式化定义, 如定义2所示:
定义2 ε-差分隐私。给定一个轨迹模式挖掘算法A, Range (A)为A的输出范围, 若算法A在T与T′上任意输出结果O (O∈Range (A))满足式(1), 则A满足ε-差分隐私。
| $\Pr \left[ A\left( T \right)=O \right]\le \exp \left( \varepsilon \right)\times \Pr \left[ A\left( {{T}'} \right)=O \right]$ | (1) |
其中:ε表示隐私预算, 用于衡量差分隐私保护的强度, 其值越小则算法A的隐私保护程度越高。实现差分隐私保护需要噪声机制的介入, 拉普拉斯与指数机制是实现差分隐私的主要技术。而所需要的噪声大小与其响应查询函数f的全局敏感性密切相关。
定义3 全局敏感性。设f为某一个查询, 且f:T→Rd, f的全局敏感性为:
| $\Delta f=\underset{T,{T}'}{\mathop{\max }}\,{{\left\| f\left( T \right)-f\left( {{T}'} \right) \right\|}_{1}}$ | (2) |
其中:R为映射的实数空间；d为f的查询维度。
文献 [3]提出的拉普拉斯机制可以取得差分隐私保护效果, 该机制利用拉普拉斯分布产生噪声, 进而使得频繁轨迹模式挖掘算法满足ε-差分隐私, 如定理1所示。
定理1[3] 设f为某个查询函数, 且f:T→Rd, 若算法A符合下列等式, 则A满足ε-差分隐私。
| $A\left( T \right)=f\left( T \right)+{{\left\langle lap\left( {\Delta f}/{\varepsilon }\; \right) \right\rangle }^{n}}$ | (3) |
其中:lap (Δf/ε)为相互独立的拉普拉斯噪声变量, 噪声量大小与Δf成正比, 与ε成反比。因此, 查询f的全局敏感性越大, 所需的噪声越多。
2.2 频繁轨迹模式挖掘轨迹数据是具有时间戳的按照时间先后排序的序列数据, 例如空间轨迹数据, 每个位置可表示成一个三元组〈xi, yi, wi〉, 则一条轨迹序列t可表示为t={(x1, y1, w1), (x2, y2, w2), …, (xn, yn, wn)}, 其中:w1 <wi <wn;xi和yi表示二维地理空间中的位置点信息, 在全球定位系统(Global Positioning System, GPS)系统中xi和yi分别对应于地理空间经度与纬度数据;wi为xi和yi位置的时间戳信息, 且1<i <n, wi<wi+1。根据北京公交车轨迹Geolife数据, 画出15条轨迹序列, 其可视化结果如图 1所示。
|
图 1 轨迹序列可视化结果 Figure 1 Visualization of trajectory sequence |
给定轨迹数据库T, |T|表示数据库大小, 字符表τ={i1, i2, …, in}是所有项的集合。例如, 表 1包含5条轨迹序列, 其中每一条轨迹序列记录按照时间先后排序。轨迹模式是否频繁, 取决于模式的支持度与最小支持度阈值的关系, 频繁轨迹模式挖掘的任务就是在轨迹数据库中找出所有大于最小支持度阈值的轨迹序列。
定义4[13] 闭频繁轨迹模式(CS)。如果不存在真超模式Y, 使得Y与X在轨迹数据库T中有相同的支持度计数, 则称X在轨迹数据库T中是闭的, 如果X是频繁模式, 则X就为闭频繁轨迹模式。
定义5[13] 等价关系。给定2个轨迹序列s和s′, 若等价当且仅当s′⊆s或s⊆s′且|Ds|=|Ds′|。其中Ds表示以s为前缀的子序列中出现的所有项的集合。
从大规模数据库中挖掘频繁轨迹模式常常产生大量满足最小支持度计数阈值的模式集, 序列冗余较严重。为了克服这一缺陷, 添加等价关系, 引入闭频繁轨迹模式，使得在具有更少轨迹模式的同时包含完整的信息。
本文利用前缀序列格结构挖掘频繁轨迹模式, 格结构是一种层次数据结构, 格中第i层节点代表的序列是第i-1层所有节点代表的序列排列组合的所有情况。前缀序列格和格结构类似, 不同的地方在于格中第i层节点代表的序列是第i-1层节点所代表序列通过序列扩展得到, 即第i-1序列是其第i层的孩子节点的前缀。前缀序列格基于前缀序列树构建。图 2就是针对表 1代表的轨迹数据库T, 采用前缀序列树结构挖掘的结果, 其中最小支持度阈值为1。掘频繁轨迹模式的过程中, 采用Clospan算法[13]思想, 通过等价关系判断, 对前缀序列树进行子树合并, 得到前缀序列格。3.4节对前缀序列格的构建作了详细的说明。
|
图 2 前缀序列树 Figure 2 Prefix sequence tree |
给定轨迹数据库T, 隐私预算ε, 最小支持度阈值min_up, 在设计满足差分隐私的频繁轨迹模式挖掘算法时, 需要考虑如下原则:
1) 针对轨迹数据库中长序列会带来很大的全局敏感度的问题, 所设计的挖掘算法在满足差分隐私的前提下, 应该能够有效降低全局敏感度, 同时保证较少的信息损失和高的数据可用性。
2) 针对大规模轨迹数据库频繁模式挖掘会产生大量冗余序列的问题, 所设计的算法在能够包含完整的频繁轨迹模式信息的前提下, 尽量压缩挖掘出的频繁轨迹模式的规模。
针对原则1和原则2, 本文提出一种基于轨迹截断和前缀序列格的轨迹模式挖掘算法LTPM。
3.1 LTPM算法实现算法1 LTPM算法。
输入 轨迹数据库T, 隐私预算ε, 最小支持度阈值min_up。
输出频繁轨迹序列模式FS。
1) ε=ε1+ε2
2) lopt← estimate_opt_length(T, ε1)
3) for each k (1≤k≤lopt) do
4) T′← DP_Trunc(T, Sk-1, lopt)
// Sk为频繁k-轨迹模式集合, 初始化S0为空
5) Sk ← Gen_ Lattice(SL, T′, ε2, Sk-1, min_up, lopt)
//SL为前缀序列格, 初始化SL为空
6) FS ← DFS(SL)
7) Return FS
该算法主要包含三个过程:估计最优截断长度过程(行2) )、截断轨迹数据库过程(行4) ), 构建前缀序列格过程(行3) ~5) )。接下来分别详细介绍上述三个过程。
3.2 最优截断长度选取首先需要确定针对轨迹数据库的最优截断长度lopt, 为了满足差分隐私, 本文采用一种自适应的方法确定lopt的大小, 算法2描述了估计最优截断长度estimate_opt_length的实现过程。
算法2 estimate_opt_length算法。
输入 轨迹数据库T, 隐私预算ε1。
输出 最优截断长度lopt。
1) z=〈z1, z2, …, zn〉, zi表示轨迹数据库中长度为i的个数
2) z′=z+〈g1, g2, …, gn〉, 其中gi从几何分布G (ε1)随机获得
3) Return lopt, 使得 lopt=
行3) 中η为常量, 大多数真实轨迹数据库序列长度分布比较偏颇, 因此本文选取η值为0.90。下面通过一个例子说明算法2的执行过程。
例1 给定轨迹数据库T如表 1所示, 则T长度分布z=〈0, 2, 1, 4〉, 利用几何机制加噪声后z′=〈1, 4, 2, 3〉, 因为(1+4) /7<0.90, (1+4+2) /7>0.90, 则选择最优截断长度为2。
定理2 算法2满足ε1-差分隐私。
证明 对于轨迹数据库T, 由于添加(删除)一个输入序列只影响T 变化1, 则这个计算的敏感度为1。因此, 在计算时添加几何噪声G (ε1)满足ε1-差分隐私。
基于上述最优截断长度lopt对轨迹数据库进行截断处理, 截断轨迹数据库过程核心步骤为DP_Trunc算法。
3.3 轨迹截断策略 3.3.1 全局敏感度分析在轨迹数据上挖掘频繁序列模式具有较高的全局敏感度。在满足差分隐私的前提下, 全局敏感度越大, 添加的噪声越大, 数据的可用性越低。
定理3[7] 计数全局敏感度。给定轨迹数据库T, T中序列的最大长度为lmax, 查询Q=[q1, q2, …, qn], 用以查询qi在数据库T中的支持度, qi的序列长度满足qi∈I=[qmin, qmax], 1≤qmin≤qmax, 查询Q的全局敏感度满足:
ΔfQ=ΔI×lmax
ΔI=(qmax-qmin)+1
在差分隐私保护模型下的k-频繁模式挖掘中, 求全局敏感度的准确值已被证明是一个NP问题[7], 通过全局敏感度的定义, 可以求出此时全局敏感度的上界是
定理3表明, 全局敏感度与轨迹数据的最大长度lmax成正比, 即使只有一个非常长的序列存在于轨迹数据库, 所有的频繁轨迹模式的支持度都要添加非常大的噪声。通过上述分析可知, 降低轨迹数据的最大长度, 将降低全局敏感度, 提高数据的可用性。
采用截断的方法将轨迹数据库T转换为T′后, 希望频繁轨迹模式的支持度不会发生变化或者变化很小。随机截断轨迹序列是最直接的方法, 但显然这种方法不可避免会造成很大的信息损失。在截断过程中, 如果一个频繁轨迹模式被错误地当成非频繁轨迹模式, 它的所有超集都会被误认为非频繁轨迹模式。例如轨迹序列t={a→b→c→d→e}, 序列{a→b}支持度计数为2, 最小支持度阈值为2, 随机截断后t′={c→d→e}, {a→b}支持度计数变为1, 则{a→b}被误认为非频繁的, 根据向下闭包性质, {a→b}所有的超集都会被误认为非频繁, 这样会造成很大的误差, 所以在截断轨迹序列s时, 为了减少上述误差, 提高挖掘结果的可用性, 需要找到一个最优的截断后的轨迹序列, 以保证能够保留那些足够频繁的轨迹序列。
3.3.2 动态规划轨迹截断为了表述更加确切, 以下称轨迹模式为轨迹序列。经分析发现, 如果一个候选k-轨迹序列的所有子序列足够频繁的话, 那么该k-轨迹序列很有可能是频繁的。为了衡量哪些轨迹序列是足够频繁的, 本文为每个轨迹序列定义一个权重, 每个候选k-轨迹序列的权重等于它的所有子序列的噪声支持度的和。
定义6 轨迹序列权重。给定频繁(k-1) -轨迹序列集合Sk-1={s(k-1) 1, s(k-1) 2, …, s(k-1) n}, 则候选k-轨迹序列集合Ck的权重为:
| $FW({{C}_{k}})=\sum\limits_{{{s}_{(k-1)j}}\subset {{S}_{k-1}}\wedge {{s}_{(k-1)j}}\in {{C}_{k}}}{{{s}_{(k-1)j}}.su{p}'}$ | (4) |
其中:s(k-1) j.sup′表示频繁轨迹序列s(k-1) j的噪声支持度。
例2 轨迹序列t={a→b→c}, 频繁2-轨迹序列{a→b}、{b→c}、{a→c}的噪声支持度分别为2、3、4, t的子序列为{a→b}、{b→c}, 则轨迹序列t的权重为5。
根据上面的定义, 轨迹序列t的最优截断问题可以表示为:
| $optimal({t}')=\max (FW({t}'))$ | (5) |
在最优截断长度lopt给定的情况下, 即找到一个长度为lopt截断后轨迹序列t′, 使得t′的权重最大。
基于上面的分析可知, 当轨迹序列规模很大的情况下, 最优截断问题的搜索空间会非常大, 而且在计算候选k-轨迹序列的权重时, 也许并不知道其(k-1) -子序列的噪声支持度, 只能依赖于现有的频繁轨迹序列集合来指导截断。因此, 本文提出一种满足差分隐私的轨迹截断算法DP_Trunc, 该算法采用动态规划的思想, 把多阶段过程转化为一系列单阶段问题, 利用各阶段之间的关系进行递推, 逐个求解。具体细节如算法3所示。
算法3 DP_Trunc算法。
输入 轨迹数据库T, 频繁(k-1) -序列集合Sk-1, 最优序列截断长度lopt。
输出 截断后的轨迹数据库T′。
1) for each t (t∈T) do
2) Ck←Apriori(Sk-1)
3) C′k={ck| ck⊂Ck and ck⊂t}
//获得Ck中轨迹t包含的候选k-轨迹序列的集合
4) for each ai(ai∈t and 1≤i≤t.length) do
5) 递推方程:
FW[i]=max{FW[i], Suffix[ai]-Suffix[ai-lopt]}
//Suffix[ai]值为C′k中以ai结尾的所有轨迹序列的权重和
6) site ← max(FW)
7) t′←{asite-lopt+1, asite-lopt+2, …, asite}
/*从t的第site-lopt+1个位置开始截取长度为lopt的连续序列t′ 并添加到T′*/
8) Return T′
首先行2) 利用Apriori算法[14]对Sk-1通过连接和剪枝操作获得候选k-轨迹序列Ck, Ck中序列权重等于其对应Sk-1中的子序列噪声支持度累加和。该算法核心步骤是利用行5) 的递推方程从轨迹序列t中找到权重最大的子序列。
假设轨迹序列t={a1→a2, …, ai, …, a|t|}, 给定候选k-序列集合Ck, 最优截断长度lopt, 则根据式(4) ~(5), 要找的截断后轨迹序列t′满足下面等式:
| $\begin{align} & optimal({t}')=\max \{\sum\limits_{{t}'\subset t}{\sum\limits_{{{c}_{kj}}\subset {{C}_{k}}\wedge {{c}_{kj}}\in {t}'}{{{c}_{kj}}.weight}}\}; \\ & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad 1\le j\le n-|t| \\ \end{align}$ | (6) |
从式(6) 可以看出, 问题的求解过程如果利用穷举法, 则时间复杂度为O (|T|n3), |T|为轨迹数据库记录条数, 利用动态规划的思想, 通过一遍扫描轨迹序列t, 递归地找到权重最大的子序列, 可以将时间复杂度降为O (|T|n)。递推公式如下:
| $FW[i]=\max \{FW[i],Suffix[{{a}_{i}}]-Suffix[{{a}_{i-{{l}_{\text{opt}}}}}]\}$ | (7) |
其中：FW[i]表示以轨迹t中ai结尾且长度为lopt的子序列权重和；Suffix[ai]表示以轨迹t中a1开头且以ai结尾的子序列权重和。
例3 给定轨迹序列t={a→b→c→d→e}, 候选2-序列及其权重:{a→b}:8, {b→c}:12, {c→d}:15, {d→e}:18, 最优截断长度lopt=3。按照lopt=3在t中选择出连续的子序列有三种情况, 分别为{a→b→c}、{b→c→d}、{c→d→e}, 从中选择权重最大的子序列作为t的截断序列。
首先计算Suffix[ai], 遍历轨迹t的每一项ai, 得到向量v=(0, 8, 20, 35, 53), v中第i个元素即为Suffix[ai], 则有Suffix[ai]-Suffix[ai-lopt]等于以ai开头且长度为lopt的子序列权重和。接下来可以将问题转化为求v中长度不超过3的最大连续子序列和问题。利用式(7), 递归地更新向量v, 最终得到结果v=(0, 0, 0, 35, 45), 找出v中的最大值, 对应的下标site=5即为截断的末尾位置, 然后从该位置向前截取长度为lopt=3的连续序列, 即得到最优截断序列t′={c→d→e}。
3.4 构建前缀序列格构建前缀序列格的具体实现细节见算法4。
算法4 Gen_Lattice算法。
输入 截断轨迹数据库T′, 隐私预算ε2, 最优截断长度lopt, 前缀序列格SL, 最小支持度阈值min_up, 频繁(k-1) -序列Sk-1。
输出 频繁k-序列Sk。
1) Ck←prefix_expend(Sk-1, T′)
// C1为轨迹数据库所有不同的项
2) ε=ε2/lopt
3)
4) if k= =1 then
5) ∀c1i⊂C1, c1i.sup′=c1i.sup+lap (Δf/ε )
6) if c1i.sup′>min_up then
7) S1=S1∪c1i
8) SL=SL+S1 //将S1添加到前缀序列格SL中
9) else
10) if cki(cki⊂Ck) 与∀s(k-1) i, ∀cki, s(k-1) i⊂Sk-1, cki⊂Ck存在等价关系 then
11) 修改前缀序列格指针指向, s(k-1) i父节点指向cki
12) Ck=Ck-cki
13) for each cki(cki⊂Ck) do
14) bi=cki.sup+lap (Δf/ε)
15) if bi>min_up then
16) Sk=Sk∪bi
17) SL=SL+Sk
//将Sk添加到SL中, 并根据包含关系添加指针指向
18) Return Sk
该算法通过层序遍历方式构建前缀序列格。构建过程如下:首先获取频繁1-轨迹序列, 并创建节点, 然后通过上层节点得出后继节点, 迭代构建SL的每一层, 构建过程中某一节点是否要往下划分, 即是否产生后继节点的条件为:1) 是否满足等价关系；2) 层次是否超过lopt。
首先行1) 根据频繁(k-1) -轨迹序列Sk-1, 扫描轨迹数据库T′, 获得以Sk-1中轨迹序列为前缀的所有序列, 即为Ck, 例如, 如图 2所示, 已知频繁轨迹序列S1={a, b, c}, 则候选轨迹序列集合为C2={a→b, a→c, b→a, b→c, c→a, c→b}, 接下来通过行5) ~行8) 以及行12) ~行16) 判断cki(cki⊂Ck)是否频繁, 如果频繁, 则将cki及其噪声支持度添加到频繁轨迹序列Sk中。行10) ~行12) 通过等价关系判断对前缀序列格进行子树合并操作, 很大程度上减少了候选轨迹序列的规模。
隐私预算的分配采用均分的策略, 通过层序方式构建前缀序列格的过程中, 每层分得的隐私预算为ε2/lopt, 为了减少加入的噪声量, 同时避免隐私预算的重复分配, 本文借鉴Clospan算法的思想, 通过等价关系的判定来减少冗余序列, 进而提高Gen_Lattice算法的可用性, 具体过程如例4所述。
例4 给定轨迹数据库如表 1所示, 其前缀序列树表示如图 2所示, 为了更直观地描述和表示, 图 3(b)中每个节点用其所代表的频繁轨迹序列表示。根据定义5可看出轨迹序列a→b与c→b存在等价关系以及b→a与c→a存在等价关系, 图 3(a)表示的即是合并等价关系的过程, 图 3(b)是在图 2的基础上, 通过合并等价关系得到的结果。合并前, a→b与c→b都需要添加噪声, 合并后, 只需为a→b添加噪声, 同时以c→b为前缀的序列都不需要添加噪声, 同理只需为b→a与c→a添加一次噪声即可, 因此, 通过等价关系合并轨迹序列, 很大程度上压缩了挖掘出的频繁轨迹序列的规模, 同时隐私预算得到了合理的分配。获得前缀序列格后, 通过深度优先遍历和回溯法, 可得到所有的频繁轨迹序列及其噪声支持度, 最终输出满足差分隐私的频繁轨迹序列集合FS。
|
图 3 构建前缀序列格过程 Figure 3 Process of building prefix sequential lattice |
定理4 构建前缀序列格过程满足ε2-差分隐私。
证明 构建前缀序列格过程即算法4, 由于一个长度为l的序列最多可以获得Clk 个不同的k-序列, 因此增加或者删除一条序列最多影响min{Clk, |Ck|}个k-序列的支持度变化。因此挖掘频繁轨迹模式过程的敏感度Δf=min{Clk, |Ck|}, 所以构建前缀序列格过程中添加lap (Δf/ε)噪声满足ε-差分隐私, 构建前缀序列格过程需要重复lopt次, 而ε =ε2/lopt。根据差分隐私的并行性质[15]和顺序性质[15]可知, 构建前缀序列格过程满足ε2-差分隐私。
定理5 LTPM算法满足ε-差分隐私。
根据算法1描述, LTPM算法包含三个过程:估计最优截断长度过程(行2) )、截断轨迹数据库过程(行4) ), 构建前缀序列格过程(行3) ~5) ), 截断轨迹数据库过程依赖于频繁(k-1) -轨迹序列的噪声支持度, 所以不消耗隐私预算。根据定理2与定理4, 以及结合差分隐私的顺序性质[15]可知, LTPM算法满足(ε1+ε2)-差分隐私, 即满足ε-差分隐私。
3.5.2 算法复杂度分析LTPM算法首先需要估计在轨迹数据库T上的最优截断长度lopt, 该过程只需遍历一次轨迹数据库T, 因此时间复杂度为O (|T|)。截断轨迹数据库过程采用动态规划的策略, 递归的找到每条轨迹数据库记录中权重最大的子序列, 可以将时间复杂度降为O (|T|n), n为当前候选轨迹序列集合的大小。构建前缀序列格过程采用层序的方式, 在构建当前层序列格过程中, 需判断候选轨迹序列集合中的频繁轨迹序列, 因此时间复杂度为O (n)。截断轨迹数据库和构建前缀序列格过程需重复lopt次, 所以最坏情况下, 整个算法的时间复杂度为O (lopt|T|n)。基于前缀树划分的Prefix算法的时间复杂度为O (h|T|n), 基于变长模型的N-gram算法的时间复杂度为O (lmax|T|n)。由于lopt≤lmax <h, 则LPTM算法的性能较好。
4 实验与分析实验平台是4核Intel i7-4790 CPU (4 GHz), 8 GB内存, Windows 7系统。所有算法均采用Python实现。实验采用4个真实轨迹数据库BMS1[18]、MSNBC[19]、Kosarak[20]、Geolife (https://www.microsoft.com/en-us/download)。Geolife为空间轨迹数据库, MSNBC、Kosarak、BMS1为用户行为轨迹数据库。其中Geolife数据库是微软亚洲研究院从2007年4月—2012年8月收集的包含182个用户、17621条轨迹信息的数据库, 每条轨迹记录的是用户的户外运动, 包括日常生活, 娱乐和体育活动。在Geolife数据库基础上, 选取北京市五环以内的数据作为实验数据库。MSNBC数据库是msnbc.com网站的点击流数据, 每条记录描述的是某个用户一天之内访问的新闻页面的轨迹, 包含989818条记录, 数据来源于UCI repository。Kosarak数据库是匈牙利新闻门户网站kosarak.org的点击流数据, 包含990002条记录。BMS1数据库是电子商务网站Gazelle.com几个月的点击流数据, 每条记录描述的是用户按照时间顺序访问的所有商品的轨迹, 包含59602条记录。四种轨迹数据库的具体特征与长度分布分别如表 2和图 4所示。
|
|
表 2 实验数据库的特征 Table 2 Characteristics of experimental data set |
|
图 4 数据库长度分布 Figure 4 Length distribution of data set |
本文将LTPM和两种满足差分隐私的序列数据库发布算法N-gram、Prefix进行可用性比较。为了得到满足差分隐私的频繁轨迹模式, 首先针对原始数据库T, 分别执行N-gram和Prefix算法, 获得隐私数据库T′, 然后在T′上执行频繁序列挖掘算法PrefixScan[16], 从而获得频繁轨迹模式。
结合上述四种数据库, 本文采用准确率(True Postive Rate, TPR)和平均相对误差(Average Relative Error, ARE)衡量LTPM、N-gram、Prefix算法的可用性。
设TF (T)表示原始轨迹数据库T对应的真实频繁轨迹模式集合, TF (T)表示满足差分隐私的频繁轨迹模式集合
1) 准确率。该标准主要用来度量频繁轨迹模式本身的可用性, 计算公式如下:
| $TPR=\frac{TF(T)\cap TF(\overline{T})}{TF(\overline{T})}$ | (8) |
根据公式可知TPR值越大, 算法的可用性越高。
2) 平均相对误差。该标准主要用来度量频繁轨迹模式支持度计数的可用性, 公式如下:
| $ARE=\frac{\sum\limits_{{{F}_{i}}\in TF(\overline{T})}{\frac{|TC({{F}_{i}},TF(T)-NC({{F}_{i}},TF(\overline{T})|}{TC({{F}_{i}},TF(T)}}}{TF(\overline{T})}$ | (9) |
其中:TC (Fi, TF (T)和NC (Fi, TF (T)分别表示频繁轨迹模式Fi对应的真实支持度计数和噪声支持度计数, 如果Fi不在TF (T)中, 则设置NC (Fi, TF (T)=0。根据公式可知ARE值越小, 算法的可用性越高。
本文实验隐私预算参数ε的取值为0.2、0.4、0.6、0.8、1.0, 隐私预算的分配策略如下:ε1=0.1ε, ε2=0.9ε。最小支持度阈值min_up为相对阈值, 即最小支持度阈值的取值随着数据库大小的不同而变化。每个算法分别执行100次, 并记录输出结果的平均值。分别通过固定隐私预算, 改变最小支持度阈值大小和固定最小支持度阈值, 改变隐私预算大小来比较LTPM、N-gram以及Prefix算法的准确率和平均相对误差, 进而比较四种算法的可用性。
1) 固定ε=0.5, 最小支持度阈值min_sup=0.01, 分别在四种数据库上执行轨迹截断算法DP_Trunc, 实验结果如图 5所示。由图 4可以看出, MSNBC、Kosarak、BMS1数据库中短序列占绝大部分, Geolife数据库含有大量长序列, 对比图 4和图 5, 能够直观地看出DP_Trunc算法仅仅将极少数长序列截断, 却大幅降低了轨迹的最大长度。
|
图 5 截断后数据库长度分布 Figure 5 Length distribution of truncated data set |
2) 基于Geolife数据库的LTPM、N-gram以及Prefix算法比较。
图 6(a)和图 6(b)显示, 固定ε=0.5, 最小支持度阈值min_up取值分别为数据库大小的0.020、0.025、0.030、0.035、0.040倍, 当min_up从0.020变化到0.040时, LTPM算法的TPR明显比N-gram和Prefix算法表现好, 其原因是N-gram和Prefix算法也限制序列长度, 但是直接删除超过限定长度的项, 因此会丢失大量信息, 而LTPM算法使用DP_Trunc算法, 在限制序列长度的同时, 很大程度上保留了序列的频繁信息。LTPM算法的ARE是Prefix算法的将近1/4, 是N-gram算法的将近1/13, 其原因是LTPM算法采用轨迹截断的方法, 明显降低了全局敏感度, 同时利用等价关系, 在减少序列冗余的同时, 进一步降低了全局敏感度。而N-gram和Prefix算法受序列长度影响较大, 仅适用于短序列居多的数据库。由图 6(c)和图 6(d)可看出, 当固定min_up=0.02, ε从0.2变化到1.0时, LTPM算法的TPR比N-gram和Prefix表现要好, 维持在0.8左右, 而N-gram和Prefix算法在0.6左右, LTPM算法的ARE随着ε的增大降低明显, 尤其在ε=1.0时, 是N-gram算法的将近1/15, 是Prefix算法的将近1/5。图 6(a)~图 6(d)可看出, LTPM算法明显要优于N-gram和Prefix算法。
|
图 6 频繁轨迹模式挖掘结果 Figure 6 Mining results of frequent trajectory patterns |
3) 基于MSNBC数据库的LTPM、N-gram以及Prefix算法比较图 6(e)和图 6(f)显示, 固定ε=0.5, 最小支持度阈值min_up取值分别为数据库大小的0.020、0.025、0.030、0.035、0.040, 当min_up逐渐变大时, LTPM算法的TPR比Prefix和N-gram算法好很多, LTPM算法的ARE是N-gram算法的将近1/7, 是Prefix算法的将近1/3, MSNBC数据库包含大量短序列记录, 所以N-gram和Prefix表现较好, ARE较低, 但是仍然高于LTPM算法。图 6(g)和图 6(h)可看出, 当固定min_up=0.02, ε从0.2变化到1.0时, LTPM算法的TPR同样好于N-gram和Prefix算法, LTPM算法的ARE随着ε的增大降低明显, 尤其是当ε=1.0时, 是N-gram算法的近1/9, 是Prefix算法的近1/6。
虽然N-gram和Prefix在短序列居多的数据库MSNBC中表现较好, 但LTPM算法仍然优于两者。
4) 基于Kosarak数据库的LTPM、N-gram以及Prefix算法比较。
图 6(i)和图 6(j)显示, 固定ε=0.5, 最小支持度阈值min_up取值分别为数据库大小的0.001、0.0015、0.0020、0.0025、0.0030倍, 当min_up逐渐变大时, LTPM算法的TPR优于N-gram和Prefix算法, ARE是N-gram算法的将近1/8, 是Prefix算法的将近1/6。由图 6(k)和图 6(l)可看出, 当固定min_up=0.001, ε从0.2变化到1.0时, LTPM算法的TPR同样好于N-gram和Prefix算法, 在最坏情况下, LTPM算法的ARE不到N-gram的1/3, 不到Prefix的1/2。由表 2和图 4(b)、(c)可看出, Kosarak数据库和MSNBC数据库特征类似, 都是短序列居多, 所以表现类似。
5) 基于BMS1数据库的LTPM、N-gram以及Prefix算法比较。
图 6(m)和图 6(n)显示, 固定ε=0.5, 最小支持度阈值min_up取值分别为数据库大小0.005、0.010、0.015、0.020、0.025倍, 当变化min_up时, LTPM算法的TPR比N-gram和Prefix稍好, ARE不足N-gram算法的1/2, 比Prefix算法低。由图 6(o)和图 6(p)可看出, 当固定最小支持度阈值min_up=0.005, 变化ε时, LTPM算法的TPR同样比N-gram和Prefix稍好, 在最好情况ε=1.0时, ARE不足N-gram算法的1/3, 是Prefix算法的近1/2。由表 2和图 4(d)可知, BMS1数据库绝大多数记录都是短序列, 所以N-gram和Prefix表现非常好, 但LTPM算法仍然优于两者, 其原因是DP_Trunc算法能有效降低截断带来的误差, 同时LTPM算法很大程度降低了全局敏感度。
5 结语针对目前的差分隐私下频繁轨迹模式挖掘算法全局敏感度过高, 会产生大量候选序列, 仅适用于短序列居多的数据库的问题, 结合轨迹截断和前缀序列格, 本文提出了一种满足差分隐私的频繁轨迹模式挖掘算法LTPM。从理论角度分析的结果显示, LTPM满足差分隐私。最后, 通过真实数据库的实验结果表明该算法在满足差分隐私的前提下可获得较高的数据可用性。在未来的工作中, 将研究如何更加合理地分配隐私保护预算, 以进一步提高挖掘结果的可用性。
| [1] | DWORK C. Differential privacy [C]//ICALP 2006: Proceedings of the 33rd International Conference on Automata, Languages and Programming. Berlin: Springer, 2006: 1-12. |
| [2] | DWORK C. LEI J. Differential privacy and robust statistics [C]//STOC 2009: Proceedings of the 41th Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 371-380. |
| [3] | DWORK C, McSHERRY F, NISSIM K, SMITH A. Calibrating noise to sensitivity in private data analysis [C]//TCC 2006: Proceedings of the 3th Theory of Cryptography Conference. Berlin: Springer, 2006: 363-385. |
| [4] | McSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//FOCS 2007: Proceedings of the 54th IEEE Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 2007: 94-103. |
| [5] | BHASKAR R, LAXMAN S, SMITH A, et al. Discovering frequent patterns in sensitive data[C]//KDD 2010: Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 503-512. |
| [6] | LI N, QARDOJI W, SU D, et al. PrivBasis: frequent itemset mining with differential privacy[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1340-1351. DOI:10.14778/2350229 |
| [7] | ZENG C, NAUGHTON J F, CAI J-Y. On differentially private frequent itemset mining[J]. Proceedings of the VLDB Endowment, 2012, 6(1): 25-36. DOI:10.14778/2428536 |
| [8] | CHEN R, FUNG B, DESAI B C, et al. Differentially private transit data publication: a case study on the montreal transportation system [C]//KDD 2012: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221. |
| [9] | CHEN R, GERGELY A, CLAUDE C. Differentially private sequential data publication via variable-length n-grams[C]//CCS 2012: Proceedings of the 19th ACM Conference on Computer and Communications Security. New York: ACM, 2012: 638-649. |
| [10] | CHENG X, SU S, XU S, et al. DP-Apriori: a differentially private frequent itemset mining algorithm based on transaction splitting[J]. Computers & Security, 2015, 50. |
| [11] | XU S, SU S, CHENG X, et al. Differentially private frequent sequence mining via sampling-based candidate pruning[C]//ICDE 2015: Proceedings of the 31st IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2015: 1035-1046. |
| [12] | CHEN R, MOHAMMED N, FUNG B C M, et al. Publishing set-valued data via differential privacy [EB/OL]. [2017-01-10]. http://www.vldb.org/pvldb/vol4/p1087-chen.pdf. |
| [13] | YAN X, HAN J, AFSHAR R. CloSpan: mining closed sequential patterns in large datasets[C]//SDM 2003: Proceedings of the 2003 SIAM International Conference on Data Mining. Philadelphia, Pennsylvania, USA: SIAM, 2003: 166-177. |
| [14] | AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases [C]//VLDB 1994: Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1994: 487-499. |
| [15] | McSHERRY F. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [C]//SIGMOD 2009: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009: 19-30. |
| [16] | PEI J, HAN J, MORTAZAVI-ASL B, et al. PrefixSpan: mining sequential patterns by prefix-projected growth [C]//ICDE 2001: Proceedings of the 17th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2001: 215-224. |
| [17] | 张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护研究综述[J]. 计算机学报, 2014, 37(4): 927-949. (ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.) |
| [18] | 丁丽萍, 卢国庆. 面向频繁模式挖掘的差分隐私保护研究综述[J]. 通信学报, 2014, 35(10): 200-209. (DING L P, LU G Q. Survey of differential privacy in frequent pattern mining[J]. Journal on Communications, 2014, 35(10): 200-209. DOI:10.3969/j.issn.1000-436x.2014.10.023) |
| [19] | 李艳辉, 刘浩, 袁野, 等. 基于差分隐私的频繁序列模式挖掘算法[J]. 计算机应用, 2017, 37(2): 316-321. (LI Y H, LIU H, YUAN Y, et al. Frequent sequence pattern mining with differential privacy[J]. Journal of Computer Applications, 2017, 37(2): 316-321. DOI:10.11772/j.issn.1001-9081.2017.02.0316) |
| [20] | 张啸剑, 王淼, 孟小峰. 差分隐私保护下一种精确挖掘top-k频繁模式方法[J]. 计算机研究与发展, 2014, 51(1): 104-114. (ZHANG X J, WANG M, MENG X F. An accurate method for mining top-k frequent pattern under differential privacy[J]. Journal of Computer Research and Development, 2014, 51(1): 104-114. DOI:10.7544/issn1000-1239.2014.20130685) |