【免费】LDP树的算法2资源-CSDN文库

需积分: 0 5 浏览量 2022-08-03 13:38:58 上传评论收藏 1.36MB PDF 举报

资源详情

资源评论

资源推荐

LDP机制下快速的频繁模式挖掘方法

王家礼

2020 年 3 月 16 日

1 简介

目前，本地化差分隐私主要研究方向有频率估计、均值估计、奨奥奡奶她奨奩奴奴奥奲、频繁模式挖掘和键值数

据收集等。其中，对频繁模式挖掘的工作相对较少，文献奛夵奝首次提出奌奄奐奍奩奮奥奲方法解决女奥奴夭奖奡奬奵奥奤场景

下本地化数据聚合，并将频繁模式挖掘任务作为开放性问题提出，并没有实际解决该问题。由于本地化差

分隐私具有强隐私保护性，任意第三方不会持有用户的敏感数据，所以，如何在噪声数据上进行频繁模

式挖掘，并且同时保证奌奄奐的隐私性以及估计结果的有效性，成为了当前一大难点问题。文献奛夸奝首次提

出了基于频率推测的候选集构造奓奖奓奍方法，其解决了频繁模式挖掘奴奯奰夭奫问题。该方法的缺点在于，随

着k值得不断增大，频率推测构造候选集的额外开销明细增大（详见夵央失节），极大得限制了方法的应用。

为了解决奓奖奓奍方法额外开销的问题，本文通过引入奆奐奧奲奯奷奴奨奛夲奝模式挖掘算法，一方面实现了基

于奌奄奐的频繁模式挖掘方法，另一方面在挖掘结果有效的前提下，大大降低了所需的额外开销。

本文贡献：

失、奌奄奐机制下频繁模式树的层次建立；

夲、对模式树及挖掘结果的优化；

夳、大大降低奓奖奓奍奛夸奝方法的额外计算开销。

2 背景知识介绍

2.1 频繁模式挖掘

频繁模式是指频繁地出现在数据集中的模式，如：项集、子序列或子结构，本文主要针对频繁项集的

挖掘（奆奉奍问题）。自文献奛失奝首次研究在数据库中发掘项集，奆奉奍已被广泛的研究。奆奉奍任务的定义如下。

给定一个用户交易数据库，奆奉奍的目的是发掘数据库中频繁出现的项目和一起出现项目集合（项集）。

频繁项集挖掘（FIM）夺令DB 夽 {t

1

, t

2

, . . . , t

n

}表示n位用户的交易数据集，其中用户u

i

的交易记

录t

i

⊂ I 夽 {x

1

, x

2

, . . . , x

d

}，I为总项目集合，x

j

表示项目（或商品），失 ≤ i ≤ n，失 ≤ j ≤ d。奆奉奍任务的

结果在于挖掘出DB中所有频繁出现的项集。如图失所示，为n 夽夵, I 夽 {a, b, c, f, g, h, l, n, o, p}时的交易数

据集。

定义、频繁项集（frequent itemset）：若X ⊂ I，则X表示一个项集。当其支持度（在数据集中出现

次数）support夨X天不低于给定阈值时，则X是一个频繁项集。

定义、α − itemset：项集X的项目个数记为α 夽 |X|，则X是一个α − itemset。

2.1.1 FPgrowth模式挖掘方法[2]

本节是对非隐私保护情况下，奆奐奧奲奯奷奴奨模式挖掘方法的简介。奆奐奧奲奯奷奴奨主要分为两个步骤：建立模

式树存储用户信息和挖掘模式树获得频繁模式。

失

夲背景知识介绍夲

图失夺交易数据集

图夲夺预处理数据集

一、建立频繁模式树FP（本文主要工作是，在LDP场景下，构建有效的FP树）

1、建立项头表 ——（第一次扫描数据集，得到项头表，也即频繁失 − itemset）

扫描交易数据集一遍，记录每个项出现的次数，根据给定的最小支持度计数（或最小支持度）筛选得

到频繁失 − itemset及它们的支持度计数，按计数值从大到小依次排序得到项头表。

如：图失交易数据集（每行为一个交易），在给定最小支持度计数为夳得到项头表如图夳

图夳夺项头表

2、预处理数据集 ——（根据所得项头表，预处理数据集，将非频繁的项删除，只保留频繁的项，并

且进行排序）

因为原始的交易数据集中的交易可能包含频繁失 − itemset中没有的项（即除项头表以外的项），所

以对于每个事务要把非频繁失 − itemset中的项过滤掉，同时为了方便奆奐树的建立，需要把每个交易中的

项夨过滤后天按照其支持度大小排序，得到新交易数据集。预处理后新的交易数据集如图夲。

处理规则：将原始的交易数据集中的每一个交易夨每一行天删除项头表中没有的项，并且剩下项按照

项头表中每一项的支持度计数从大到小排序（所有交易共用一个项目排序，c, f, a, b, p）。

3、FP树的建立 —— （第二次扫描数据集，根据每个处理后交易记录，构建模式树）

失）、奆奐树的根节点默认为root，其相应的计数为总用户数n；

夲）、将新交易数据集中的每个交易变成奆奐树中的一条路径，并统计每个项出现的次数；

夳）、对于后插入的交易先从树的根节点开始找与其相同的部分，从第一个不重合的项开始建立一个

新的分支。

例：新的交易数据集如图2

扫描第一个交易为c, f, a, p：

扫描第二个交易为c, f, a, b：

剩余17页未读，继续阅读

评论0

内容反馈

易烫YCC

粉丝: 23
资源: 315

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip