Page 269 - 《软件学报》2021年第12期

郭宇红 等:分组随机化隐私保护频繁模式挖掘 3933

就可根据文献[22]中的公式(3):
k
2 − 1
S = A a k C′ 0 a k C′ + 1 + ... a k k C′ + k = ∑ a k C′ j (1)
2 −
, 11
2 −
1,0
1 2 −
1
2 −
1,2 −
j= 0 2 − 1, j

−
k
1
估算出项集 A 的重构支持计数 S .而公式(1)中, a 2 − 1, j (j=0,1…,2 −1)为矩阵 P k 的逆矩阵 P 中的最后一行元素,
k
k
A
C′ 为 A 的第 j 个子集在 D′(I 1 …I k )中的净计数(即 D′(I 1 …I k )中恰等于第 j 个子集的事务数).因此,只要求出变换
j
1
−
概率矩阵 P k ,就可求得任意项集的重构支持计数和支持度了.因为求得 P k 就可得到 P ,进而得到 a ij .
k
2.2.2 变换概率矩阵
根据文献[22]表 1,易推出单参数随机化 4-项集的变换概率矩阵,见表 2.
Table 2 Transition probability matrix P 4 of mask
表 2 mask 变换概率矩阵 P 4
0 1 … 15
0000 0001 … 1111
Φ I 4 … I 1I 2I 3I 4
3
0 0000 Φ p 4 p (1−p) … (1−p) 4
3
3
1 0001 I 4 p (1−p) p 4 … (1−p) p
… … … … … ... …
15 1111 I 1I 2I 3I 4 (1−p) 4 p(1−p) 3 … p 4
对于表 1 的分组多参随机化,如何求得变换概率矩阵 P 呢?文献[22]的公式(5)给出了 P N/g 模型 p ij 的计算公
式.P N/g 模型每个分组记录数相同,而本文表 1 每个分组记录数不同,但仔细分析发现,文献[22]的公式(5)同样适
用于分组记录数不同的随机化.不过,文献[22]的公式(5)各组权重角标所用的组号 i,容易 与 p ij 中的角标 i 混淆,
本文使用 w g 和 p g ,分别表示第 g 个分组所占的比例权重和对应的随机化参数,得到 GR-PPFM 方法中 k-项集 A
k
k
对应的 2 ×2 变换概率矩阵 P k 中的元素值:
n
p ij = g g r (1− ∑ w p p g ) k −r (0≤≤r k ).
g = 1
例如表 1 中的分组随机化,事务“0000”转变“0000”的概率为
5
=p
00 ∑ w p g 4 (1− g ) = p 0 0.3 1× 4 + 0.2 0.9× 4 + 0.2 0.8× 4 + 0.2 0.7× 4 + 0.1 0.6× 4 = 0.57412;
g
g = 1
而“0001”(对应事务{I 4 })转变为“1110”(对应事务{I 1 I 2 I 3 })的概率为
5
1,14 ∑ w p g 0 (1− g ) = p 4 0.3 0× 4 + 0.2 0.1× 4 + 0.2 0.2× 4 + 0.2 0.3× 4 + 0.1 0.4× 4 = 0.00418.
= p
g
g = 1
这样便可得到 4-项集{I 1 I 2 I 3 I 4 }对应的 16×16 变换概率矩阵 P 4 中的所有元素,见表 3.
Table 3 Transition probability matrix P 4 of GR-PPFM
表 3 GR-PPFM 变换概率矩阵 P 4
0 1 … 15
0000 0001 … 1111
Φ I 4 … I 1I 2I 3I 4
5 4 5 5 4
0 0000 Φ ∑ wp g ∑ wp 3 g (1− p g ) … ∑ w g (1− p g )
g
g
g = 1 g = 1 g = 1
5 5 4 5
3
1 0001 I 4 ∑ wp g 3 (1− p g ) ∑ wp g … ∑ w g (1− p g ) p
g
g
g
g = 1 g = 1 g = 1
… … … … … ... …
5 5 5 4
3
15 1111 I 1I 2I 3I 4 ∑ w g (1− p g ) 4 ∑ w g (1− p g ) p g … ∑ wp g
g
g = 1 g = 1 g = 1

−
1
在得到矩阵 P k 后,就可根据 C = k P ⋅ C′ ,求得 k-项集 A 的支持计数了,其支持计数恰等于向量 C 中的最后
A
A
A