欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2018112764527
申请人: 南京邮电大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种面向差分隐私保护的频繁项集挖掘方法,其特征在于,包括以下步骤:步骤1:基于预设的数据集D={T1,T2…Tm},项集域A={i1,i2…in},使用Apriori算法计算出所有项集的支持度,从中挑选出频繁项集;

步骤2:统计数据集中各条事务的长度并计算截断长度L,根据所述截断长度L截断数据集;

步骤3:计算频繁项集包含项的个数上限m和频繁项个数λ,根据λ值构造频繁项组成的集合F;

步骤4:构造最大频繁项集MFI集合B及候选项集集合C;

步骤5:使用最大频繁项集集合B对候选项集集合C中的项集进行加噪;

步骤6:使用初始最大频繁项集集合B计算得到各个候选项集的支持度,计算与真实支持度的误差之和E;遍历集合B,寻找Bi、Bj∈B,Bi、Bj是B中的两个最大频繁项集;合并Bi、Bj后的集合为B′,若使用B′对候选项集进行加噪产生的误差和小于E,则用B′取代B并且更新误差之和E的值;当误差之和E不再减小时停止迭代并输出结果;

步骤2中,所述截断长度L的统计向量{z1,z2…zn},zi为数据集中长度为i的事务的个数,i=1,……,n,对向量添加噪声其中,所述噪声函数 为双边几何分布,ε为隐私预算;双边几何分布概率密度函数如下:

将所述截断长度L设置为满足式(3)的值

2.根据权利要求1所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,步骤2中,根据所述截断长度L截断数据集具体方法如下:遍历数据集D,对任意事务Ti∈D,|Ti|表示Ti包含项的个数,若|Ti|>L,则只保留Ti中支持度前L大的项,剔除其余的项;若|Ti|≤L,则不对Ti进行变动。

3.根据权利要求2所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,步骤3中,计算向量 yi(D)表示长度为i的项集中支持度最大的取值,τ表示第k频繁项集的支持度,使用打分函数为‑|yi(D)‑τ|的指数机制从中挑选出m的值; 表示向下取整;

计算向量{x1(D),x2(D)…xn(D)},xi(D)表示第i频繁项的支持度,使用打分函数为‑|xi(D)‑τ|的指数机制从[1,2...n]中挑选出λ的值;

所有项按支持度由大到小排序,前λ个项组成集合F。

4.根据权利要求3所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,所述指数机制描述如下:

设定输出域为O,r表示从输出域中所选择的输出项,定义一个打分函数u(D,r),用来衡量输出结果为r时的准确度,则算法K输出为r的概率表示如下:其中,Δu表示打分函数的敏感度,ri表示输出域O中的一个输出项。

5.根据权利要求1所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,步骤4具体步骤如下:

初始化所述最大频繁项集MFI集合B和候选项集集合C为空集,再定义一个空集S;

先将F中的所有项添加到集合C中,接着以深度遍历的方式从F中挑选项,并将挑选出的项添加到集合S中构成新集合S‘;若S‘仍然是频繁的,继续从F中挑选项;若不是,将S添加到MFI集合B中,并将S的子集添加到集合C中,回溯到上一个结点。

6.根据权利要求1所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,步骤5具体方法如下:

对候选项集的支持度添加满足Laplace概率分布的噪音,挑选出加噪后支持度前k大的项集;

加噪过程如下:每个最大频繁项集Bi将数据集里的事务分配给 个互不相交的桶,每一个桶对应Bi的一个子集,表示为 其中 表示包含对应子集的项且不包含Bi中其他项的事务的个数,对桶的计数添加Laplace噪音,如式(5)所示:

其中,噪声函数 为拉普拉斯分布,ε为隐私预算,|B|为最大频繁项集的个数。

7.根据权利要求6所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,所述拉普拉斯分布的概率密度函数如下:

其中,x表示所有可能的取值,P(x)为所有取值的概率;

使用加噪后桶的计数计算候选项集的支持度。

8.根据权利要求7所述的面向差分隐私保护的频繁项集挖掘方法,其特征在于,用a,b,c分别表示三个项,则(a,b)的支持度是由{a,b,c}, 两个桶的计数值相加得到;其中(a,b)表示a和b组成的项集,{a,b,c}表示同时包含a、b、c的事务的个数, 表示包含a、b且不包含c的事务的个数,表示不包含。