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

3934 Journal of Software 软件学报 Vol.32, No.12 December 2021

一个元素 C .
A
文献[22]第 3.3 节、第 3.4 节给出了手工进行支持度重构的完整例子.
2.2.3 支持计数重构递归公式

有两种方法可加快求解整个项集空间的 2 个项集支持度的计算过程:第 1 种方法是根据 C = I m P ⋅ − 1 C′ 求取
m
I

m
2 个项集在 D 中的净计数,然后由项集的支持计数与净计数的关系 S = T C⋅ 求得此 2 个项集的支持计数;第 2
m
I I
m
种方法是导出项集支持计数重构递归公式,见后文公式(4),根据该递归公式只需 2 次求解,便可求取整个项集
m
空间的 2 个项集的支持度.下面给出公式(4)的推导过程:

k
假设 S′ A [ , ,...,S S′ = ′ 0 1 S′ k ] 为 k-项集 A 的 2 个子集在 D′中的支持数构成的向量,由文献[13]命题 1,知
2 − 1

k
k
−
1
S′ = TPT S .其中,T=[T ij ]为 2 ×2 矩阵,满足:
A
k
A
⎧ 1, ⊆f ; f
T ij = (, ) = T i j ( ,f f j ) = T ⎨ i j
i
⎩ 0, others.
−1
其中,f i 和 f j 均为 A 的子集.令 U=P k T ,则根据 P = k w P + 1 k 1 w P + 2 k 2 ... w P+ n k n ,可得:
n
g
U = (w P 1 + 2 k 2 + w ...+ P w n k n )T − 1 = P ∑ w P T − 1 .
g k
1 k
g = 1
n n
i
令 V=TU,则有V = T ∑ w P T − 1 = ∑ wTP T − 1 ,由文献[13]的公式(11),易推得:
i
i
k
ik
i= 1 i= 1
⎧ n | j f | (1− | | |− f | j ⊆
⎪∑
i f
(, ) =
Vi j ( ,f f j ) =V ⎨g = 1 g (2p g − w 1) p g ) , f j i ; f (2)
i
⎪ 0, others.
⎩

结合 S′ = A TPT S = k − 1 A V S 和公式(2),得到向量 S′ 的最后一个元素 S′ 满足:
A
A
A
⎛ n ⎞ ⎛ n ⎞ ⎛ n ⎞
A
A
S
S ′ = A ⎜ ⎜ (2p g − ∑∑ 1) (1− w || f p g ) | | | |− f ⎟ S f = ⎜ ⎜ g g (2p g − ⎟ 1) ⎟ | | A ⎟ S A + w ⎜ ∑ ⎜ g (2p g − ∑ 1) (1− ∑ w || f p g ) | | ||− f ⎟ ⎟ f (3)
f ⊆ A = ⎝ 1 ⎠ g g = ⎝ 1 ⎠ f ⊂ A = ⎝ 1 ⎠ g
根据公式(3),得到项集支持计数重构递归公式如下:
⎛ n ⎞
A
S ′ − A ⎜ ⎜ g (2p g − ∑∑ 1) (1− w || f p g ) (| | | |)− f ⎟ ⎟ f
S
S A = f ⊂ A = ⎝ 1 n ⎠ g ,S | = D | (4)
∅
∑ w g (2p g − 1) || A
g = 1
2.3 GR-PPFM挖掘方法
GR-PPFM 利用支持数重构递归公式(4),在频繁项集生成算法 Apriori 基础上形成,支持数重构递归公式是
算法的核心,Apriori 构成了方法的主框架.
算法. 分组随机化隐私保护频繁项集生成方法 GR-PPFM.
输入:分组多参随机化数据 D′;分组比例和随机化参数(p g ,w g )(g=1,…,n);最小支持度阈值 min_sup;

输出:从 D′重构出的频繁项集集合 F .
1. 扫描事务集 D′,记录每个项 j 的支持计数 j.S′,所有项的集合构成 I;
2. for each item j∈I:
. j S′
(a) . js′ ← ; //得到项 j 在 D′中的支持度;
| D |