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

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

⎛ n ⎞
. ′ −j s ⎜ 1− ⎜ g g ⎟ ∑ w p ⎟
. ←
(b) js ⎝ g = 1 ⎠ ; //重构项 j 在 D 中的支持度;
n
2∑ wp g − 1
g
g = 1

F ←
3. 1 { j ∈ I | .j s ≥ min_sup} ; //得到重构频繁 1-项集集合;

4. for (k=2; F k − 1 ≠ ∅ ; k++):

;
(a) C ← apriori _ gen (F k − 1 ,min_sup) ; //由 F k − 1 生成候选频繁 k-项集集合 C
k
k
(b) for each transaction t∈D′, //扫描 D′记录每个候选 k-项集的支持计数
for each candidate cC∈ k ,
if c⊆t then c.S′++;
(c) for each candidate cC∈ :
k
. cS′
(i) . cs′ ← ; //得到候选频繁 k-项集 c 在 D′中的支持度;
| D |
⎛ n ⎞
k
. ′ −
cs ⎜ ⎜ g (2p g − ∑∑ 1) (1− w || f p g ) ( − f | |) ⎟ ⎟ . f s
. ←
(ii) cs f ⊂ c = ⎝ 1 ⎠ g ; //重构 c 在 D 中的支持度;
n
∑ w g (2p g − 1) k
g = 1

F ←
(d) {c C∈ | .c s ≥ min_sup} ; //得到重构频繁 k-项集集合;
k k

5. Return F ← ∪ F ;
k k
3 实验评价
3.1 实验数据
分别用人工合成购物篮数据集、真实购物篮数据集进行实验评价.
人工合成购物篮数据集.人工合成购物篮数据集 D 由 IBM Almaden 生成器生成,生成器参数为 T=3,
I=4,|D|=100K,N=10,即事务平均长度为 3,频繁项集的平均长度为 4,总事务数为 100K,总项数为 10.直接生成的
数据集为项集形式,可将其转化为 0,1 布尔表示的数据集;
真实购物篮数据.真实购物篮数据集 D 为某食品超市的购物数据 basket.txt,事务平均长度为 3,总事务数
940, 总项数 为 11, 包括 fruitveg,freshmeat,dairy,cannedveg,cannedmeat,frozenmeal,beer,wine,softdrink,fish,
confectionery.该数据可从以下网址获取:https://download.csdn.net/download/lol000/8693253(2020 年 2 月).
3.2 实验方法
• 第 1 步,挖掘原始数据集 D.
针对多个不同的最小支持度阈值,分别运用 Apriori 算法对数据集 D 进行挖掘,记录每次挖掘得到的所有频
繁项集和其支持数.
• 第 2 步,生成分组多参数随机化数据集.
对数据集 D 进行分组多参数随机化干扰,生成干扰后的数据集 D′.具体地讲,对数据集 D 按行分为 Group1~
Group5 共 5 组数据,这 5 组数据所占的比例分别为 w 1 =30%,w 2 =20%,w 3 =20%,w 4 =20%,w 5 =10%,对应的随机化参
数分别为 p 1 =1,p 2 =0.9,p 3 =0.8,p 4 =0.7,p 5 =0.6.即:第 1 组数据保持不变;第 2 组数据以 0.9 的概率保持原来的值,以
0.1 的概率取反;第 3 组~第 5 组数据分别以 0.8,0.7,0.6 的概率保持原值,以 0.2,0.3,0.4 的概率取反.直观地,数据
集 D 对应的分组多参随机化模型参数设置见表 4.
以上 5 组数据所占比例,大致依据本文开始提到的 AT&T 实验室 1999 年隐私态度调查报告中不同用户的