面向隐私保护的关联规则挖掘算法

范 敏 杨 庚,2

1(南京邮电大学计算机学院 南京 210023)

2(江苏省大数据安全与智能处理重点实验室 南京 210023)(193474168@qq.com)

关联规则挖掘(association rule mining, ARM)是一项基本的数据挖掘任务，它首先被应用于分析市场上的购物篮来发现购买习惯.其中最著名的例子就是“尿布和啤酒”的故事.也许很难想象这2个项目会有关联，但是经过关联分析，市场经理发现买尿布的人更有可能买啤酒.关联规则被广泛应用于各种领域,如电信网络、市场购物篮分析的风险管理、卫生保健、Web使用挖掘等[1].最近的进展在科学和技术领域都产生了有争议的影响.一方面，关联规则挖掘能够在海量数据中发现潜在的有用规则；另一方面，过度挖掘关联规则会使敏感数据和用户的机密信息面临风险.因此，在保证数据安全和用户隐私的前提下，开发保护隐私的关联规则挖掘算法成为一个迫切需要解决的问题[2].

差分隐私[3]作为一种数据隐私保护技术，通过添加随机噪声来防止敏感信息的泄露.差分隐私模型是完全独立于攻击者的背景知识和计算能力的强隐私概念，已成为近年来的研究热点.与传统的隐私保护模式相比，差分隐私有其独特的优势.首先，模型假设攻击者拥有最大的背景知识；其次，差分隐私具有完整的数学基础，对隐私保护有严格的定义和可靠的定量评价方法.差分隐私是一种有效的隐私保护机制，它在保护用户隐私的同时，保留了足够的有用信息供数据分析使用.

差分隐私保护已在学术界和业界得到了广泛注意和研究.满足差分隐私的机制已经融合在数据分析的很多领域，如数据发布、数据挖掘、机器学习和深度学习[4-9].特别是Google和Apple在各自的产品(即Chrome和iOS)中设计和部署了差分隐私机制，以更好地保护用户隐私[10].

目前已有多种满足差分隐私的关联规则挖掘算法被提出(如TF[11]， PrivSuper[12]),但这些算法在如何平衡安全性和可用性方面仍显不足，即在一定的隐私保护等级需求下，如何尽可能提高数据挖掘的可用性.从差分隐私保护的实现机制中我们发现，为了提高算法的可用性，对给定的隐私预算ε，降低全局敏感度是一种可行的方法.在关联规则挖掘算法中，全局敏感度依赖于数据集中最长记录的长度.因此，为了降低全局敏感度，多数算法使用截断数据集中的长记录来实现这一目标.但这样做会影响截断掉的集合及其子集的支持度，有可能会导致本来频繁的项集变为不频繁.针对这个问题，本文设计了一种事务分割的方法，并引入事务矩阵[13]减少数据库的扫描次数，提出了一种满足差分隐私的关联规则挖掘算法.

1 相关工作

关联规则挖掘问题最早由Agrawal等人[14]提出，并受到广泛关注.有几种著名的关联规则挖掘算法，如Apriori算法[14]和FP-Growth算法[15].Apriori算法具有广度优先搜索策略，结构直观，且具有向下闭包性，算法效率高，本文也是基于Apriori算法进行差分隐私保护算法设计.

近年来，差分隐私模型在隐私保护中得到了广泛的应用.Bhaskar等人[11]提出了一种基于截断频率的TF(truncated frequency)算法，该算法是一种发布top-k频繁项集及其频率的方法.TF算法由2个步骤组成：第1步，选择要发布的k个项目集；第2步，在添加噪音后发布这些项目集的频率.隐私预算ε在这2个步骤中平均分配.首先从不超过m个项集的所有项集中选择k个项集，然后对这些选择项集的频率添加噪声.对于较小的k值，这种算法效果比较好;但是对于较大的k值，准确性较差.主要原因是对于较大的k值，必须将大小限制m设置得更大.这将导致一个非常大的候选集，算法从中选择top-k，这会导致选择不准确.

受文献[11]的启发，Li等人[16]提出了PrivBasis算法，该算法避免从非常大的候选集中选择top-k项集，并且引入了基集的概念.通过将输入数据投影到人们所关心的少数选定维度上来应对高维性的挑战.

给定事务数据集D，其中所有项的集合记为I，该算法主要步骤如下：1)计算λ，即k个最频繁的项集所涉及的唯一项的数量；2)查找I中出现频率最高的λ项构成F；3)查找F中出现频率最高的项对的集合组成P，P中恰好包含出现在top-k项集中的项对；4)利用F和P构造B，B是一个具有较小宽度和长度的fk基集；5)得到候选项集C(B)，并对其添加拉普拉斯噪声，然后从C(B)中选择噪声支持度最高的k个项目集.该算法最关键的部分就在于基集的构造.

PrivBasis算法基于差分隐私生成频繁项集，利用噪声频繁项集查找关联规则，理论上可以确定高置信度规则，但实际上只有频率很高的规则被保留，而大量频率中等的规则被丢弃.Zhen等人[17]提出了能够自适应设置支持度阈值，提取高置信度规则的算法，该算法设置多个支持度阈值，即针对每个项集中各个项的真实支持度来设置特定的最小支持度阈值，以此来减少候选项集的数量，提取能够反映项目本身性质的规则，并利用随机截断和统一分区来降低数据集的维数.这2种方法都可以帮助降低查询的敏感度，降低所需噪声的规模，并提高挖掘结果的可用性.通过自适应地分配隐私预算来约束整体隐私损失，稳定了噪声规模.其不足之处在于随机截断会引起部分信息丢失，从而导致挖掘结果不准确.

现有的差分隐私关联规则挖掘算法大致可以分为2类:一类是需要挖掘频繁项集，这是关联规则挖掘的基本步骤.例如，TF算法[10]、PrivBasis算法[16].另一类是直接挖掘关联规则，如HCRMine算法[18].我们的工作是基于第1类挖掘算法.

2 理论基础

2.1 差分隐私

差分隐私允许对数据进行一般性的统计分析，同时以强有力的隐私保障保护个人数据.

差分隐私提供了不可区分性的保证:差分隐私结果不会产生很多关于在计算结果时使用了2个邻近数据集中的哪个数据库的信息.

定义2.差分隐私.给定至多有1条记录不同的任意2个邻近数据集D1和D2，设有随机算法M,PM为M所有可能的输出构成的集合，及PM的任何子集SM，若算法M满足式(1), 则称算法M提供ε-差分隐私保护.

Pr[M(D1)∈SM]≤exp(ε)×
Pr[M(D2)∈SM],

(1)

其中参数ε称为隐私保护预算，它定制了算法的隐私级别.ε越小，隐私保障越强，数据的可用性越差，同时也说明挖掘结果中注入了更多的噪声；ε越大，隐私保护效果越差，数据的可用性更高，挖掘结果中注入噪声更少.

拉普拉斯机制[19]和指数机制[20]是常见的噪声叠加机制.拉普拉斯机制适用于在数值查询结果中加入噪声.它通过在精确结果中加入满足拉普拉斯分布的随机噪声来实现差分隐私.在许多实际应用程序中，查询结果是实体特性(例如一个方案或一个选择).针对这种情况，McSherry等人[20]提出了指数机制，该机制适用于在非数值查询结果中添加噪声.这2种机制都是基于全局敏感度实现的.

定义3.全局敏感度.对于任意2个邻近数据集D1和D2，定义任意函数F:D→n的全局灵敏度为

(2)

定义4.拉普拉斯机制.对任意函数F:D→n，算法M返回式(3),则算法M满足ε-差分隐私.

(3)

其中,Δf为函数F的敏感度.

定义5.指数机制.给定数据集D，算法M满足式(4), 则算法M满足ε-差分隐私.

(4)

其中u为打分函数， Δu为打分函数的敏感度,r为输出域O中的任一输出项.指数机制的关键就在于打分函数的设置，分数越高，则输出的概率越大.因此，对于同一数据集，不同的打分函数可能导致截然不同的挖掘结果.

2.2 关联规则挖掘

关联规则挖掘是一种常用的数据挖掘算法，旨在发现事务数据库中项目集之间有趣的关系.关联规则挖掘的概念具体描述如下：项集I={i1,i2,…,in}由n个不同的项组成，D={t1,t2,…,tm}称为数据集，其中tk,k∈[1,m]称为事务.1条规则是由2个不同的项集组成的，表示为X⟹Y,其中X,Y∈I，X称为前提，Y称为结论.例如超市中的1条规则{黄油，面包}⟹{牛奶}，表示如果黄油和面包已经被同时购买，那么牛奶也会被购买.

从所有可能的规则中挑选出一些有用的规则，这些规则称为关联规则.为了能挑选出有用的规则，需要用到2个指标，分别是支持度和置信度，前者用于挖掘频繁项集，后者用于从频繁项集中发现关联规则.

定义6.支持度.给定数据集D,项集X的支持度定义为：包含项集X的事务数与数据集D中的总事务数的比值.支持度用来表示项集在数据集中出现的频率，可表示为式(5)：

(5)

定义7.置信度.对于规则X⟹Y，其置信度为同时包含X和Y的事务数与包含X的事务数的比值.置信度用来表示规则的可信度，可表示为

(6)

3 基于双重条件机制事务分割的关联规则挖掘算法

一般算法通过截断长事务以期降低全局敏感度，本文考虑到事务截断会造成一定的信息损失，从而设计了一种基于双重条件机制对长事务进行分割的关联规则算法，即TS-ARM算法.TS-ARM算法由2大部分组成，分别是数据预处理和关联规则挖掘.数据预处理也就是对长事务进行分割后生成新数据集的过程，3.1节将对预处理过程进行详细的描述.3.2节则是利用3.1节的预处理结果挖掘关联规则.

3.1 预处理

本文算法采用双重条件对事务进行分割，首先确定一个事务长度阈值lmax，并按同样的方法确定分割支持度阈值sup′，然后对超过这个阈值的事务进行分割处理.分割支持度阈值的设置保证了支持度较高的项都能被分到同一事务中，进而降低了预处理对挖掘结果产生的影响.关于这2个阈值的确定，具体操作过程详见算法1：

算法1.确定最大事务长度阈值.

输入：数据集D；

输出：最大事务长度阈值lmax.

① FUNCTION(GetLenThreshold(D))

② [z1,z2,…,zn]←对D的事务长度按升序

排序；

④z′=0,l=1；

⑤ WHILEl

⑥z′=z′+zl；

⑦ IFz′>p×zsumTHEN

⑧lmax=zl；

⑨ END IF

⑩ END WHILE

算法1中p取值一般为0.85[21].算法1首先将所有事务的长度按升序排序，并按顺序对所有的事务长度做累加，直到累加和大于所有事务长度综合的0.85倍，记录当前的长度lmax，将其作为最大事务长度阈值.

分割支持度阈值的选取与事务长度阈值的选取类似，其中p的取值为0.2.首先将各个项的支持度按降序排序，并按顺序依次对支持度累加，直到累加和大于支持度总和的0.2倍，停止累加并记录当前的支持度sup′作为分割支持度阈值.

确定这2个阈值后，就可以对数据集中超过事务长度的事务进行分割.在事务分割过程中，1个长事务有可能被分割为若干个短事务.1个长事务t的分割过程描述如下：1)使用指数机制依次从事务t中不放回地挑选出lmax个项作为1个新事务，打分函数为项的支持度；2)判断事务t中剩余项的支持度是否大于sup′，若有，则继续使用指数机制，从事务t中挑选1项添加到新事务中，直到事务t中剩余项的支持度都不大于sup′；3)返回步骤1),直到|t|=0.对于数据集中所有超过长度阈值分割的具体实现过程如算法2所示，最终返回对长事务分割后的数据集D′.

算法2.事务分割.

输入：数据集D；

输出：对长事务分割后的数据集D′.

① FUNCTION(SplittingLongTransactions(D))

②lmax=GetLenThreshold(D)；

③Tb=∅，T′=∅，D′=D；

④ FOR each transactiont∈D′ DO

⑤tlen=length(t)；

⑥ IFtlen>lmaxTHEN

⑦Tb.add(t)；

⑧D′.delete(t)；

⑨ END IF

⑩ END FOR

中选取lmax个项；

按降序排序*/

3.2 关联规则挖掘

TS-ARM算法采用事务矩阵[12]存储数据集，可以有效减少存储空间，并且后续进行频繁项集支持度的计算都可以依赖事务矩阵计算完成，无需重复扫描数据库.图1为事务矩阵的转化示例.其中行对应数据集D中出现的所有项，列对应数据集D中的所有事务，若事务Tm中包含in,则将事务矩阵的第n行第m列置为1，否则置为0.得到事务矩阵G后，则可根据向量的运算规则，先对二进制向量“与”运算，再对各项进行求和，快速求得项集的支持度.

图1 事务矩阵的转化示例

在人们的日常生活中，对于奢侈品的消费次数可能占比较小，但其金额却占了消费总金额的大部分，因此不能只设置1个最小支持度阈值来统计频繁项集.考虑到算法的实用性，参考文献[17]自适应设置项集的最小支持度阈值.项集支持度阈值的选取规则如下：选择该项集中支持度阈值最小的项，将其阈值作为该项集的支持度阈值，对每个项集都设置1个支持度阈值.算法3则是实现为每个项设置1个最小支持度阈值.

算法3.为每个项设置最小支持度阈值.

输入：数据集D、支持相关性ρ、允许MIS最小值λ；

输出：每个项的最小支持度阈值i.MIS.

① FUNCTION(AssignMIS(D,ρ,λ))

②G←根据D构建事务矩阵；

③I={i1,i2,…,in};/*数据集中包含的所

有项*/

④ FOR each itemi∈IDO

⑤i.sup←通过计算G中各行中1的个数；

⑥i.MIS=max{ρ×i.sup,λ}；

⑦ END FOR

⑧S=sort(I);/*按MIS升序对I排序*/

⑨ RETURNS.

算法4描述了TS-ARM算法的完整框架.对预处理、项集最小支持度阈值的设置、频繁项集挖掘和关联规则挖掘进行了实现.

算法4.TS-ARM算法.

输入：数据集D、支持相关性ρ、允许MIS最小值λ、隐私预算ε；

输出：所有关联规则的集合及其置信度.

① 确定事务长度阈值lmax和分割支持度阈值sup′，使用ε1的隐私预算对数据集D预处理得到D′，其中ε1=0.6ε；

② 由D′构建事务矩阵G；

③ 扫描G得到频繁1项集以及每个项的MIS，并删除G中不频繁1项对应的行；

④ 频繁项集Lk自连接得到候选项集Ck；

⑤ 扫描G计算候选项集的支持度，并根据项集中各个项的MIS值为每个项集设置特定的最小支持度阈值；

⑥ 使用ε2的隐私预算为候选项集的支持度添加Laplace噪声，并将噪音支持度与该项集的最小支持度阈值对比，生成噪音频繁项集，其中ε2=0.4ε；

⑦ 根据各个项集的噪音支持度计算项集之间的置信度，并设置最小置信度阈值，查找出所有的关联规则.

4 算法隐私与可用性分析

衡量差分隐私算法的性能，可以从隐私性和可用性2个方面进行分析.

4.1 隐私性分析

定理1.若算法M在使用双重条件机制分割处理后的数据集上满足ε-差分隐私，那么算法M在原始数据集上也满足ε-差分隐私.

证明.用r表示数据集的分割过程，由文献[20]可知，对于邻近数据集D1,D2，有:

Pr[M(r(D1))∈SM]≤exp (ε)×
Pr[M(r(D2))∈SM],

其中SM表示算法M可能输出的任一结果.

证毕.

定理2.TS-ARM算法满足ε-差分隐私.

证明.算法包含2个处理阶段：预处理和关联规则挖掘，在预处理阶段使用指数机制对超过长度阈值的长事务进行分割，记分配的隐私预算为ε1，在频繁项集查找阶段，对支持度计数采用Laplace机制进行噪声的添加，记分配的隐私预算为ε2.

关联规则的挖掘主要依赖于频繁项集，可以通过频繁项集查找阶段计算得到的噪音支持度来计算关联规则的置信度，不涉及隐私泄露.因此，由差分隐私的串行性质及定理1可知，TS-ARM算法满足ε-差分隐私，其中，ε=ε1+ε2.

证毕.

4.2 可用性分析

在隐私保护算法中，若算法满足(δ,η)-可用性，则表示算法在理论上证明是可用的.

定义8.δ-相似性.给定数据集D和阈值λ，设S为一频繁模式算法的输出结果，若S满足以下2个条件，则称其满足δ-相似性[19].

1) 支持度大于(1+δ)λ的项集都属于S；

2) 支持度小于(1-δ)λ的项集都不属于S.

定义9.(δ,η)-可用性.对于差分隐私保护算法M，若其在给定数据集D上的输出结果以大于1-η的概率满足δ-相似性，则称算法M满足(δ,η)-可用性，其中δ,η∈[0,1][20].

定理3.TS-ARM算法满足(δ,η)-可用性.

证明.给定数据集D,设n为其项集域大小，由文献[21]可知，若某算法满足式(7)则可保证算法既满足ε-差分隐私又满足(δ,η)-可用性.

(7)

其中(1-η)/η.

以pumsb_star[21]数据集为例，项集域大小为2 088，设阈值λ=400，设置η=0.7,δ=0.8，代入式(7)得ε≥0.964 3，即当ε≥0.964 3时，算法满足(0.8,0.7)-可用性.因此，在隐私预算不变时，在算法中合理设置δ与η的值，总能使其满足(δ,η)-可用性.

证毕.

5 实验结果与分析

5.1 实验环境与实验数据

本文实验环境为Inter®CoreTMi5-8250UCPU @ 1.60 GHz，4 GB内存，Windows10操作系统，实验采用Python语言进行编写.实验采用4个数据集，分别是某零售商店的销售数据retail、人口普查数据pumsb_star，以及IBM公司的数据生成器生成的2个模拟数据集T40I10D100K和T10I4D100K，这些数据集常被用于关联分析[11,21].表1给出了上述数据集的几种属性，包括事务数量、项数、最大事务长度、平均事务长度.

表1 数据集的属性描述

下面将在这4个数据集上进行实验，并与TF[10]算法和PrivBasis[16]算法进行对比，以验证本文提出算法的优越性.

5.2 数据预处理结果分析

在关联规则挖掘之前，为了降低查询的全局敏感度，首先要对数据预处理，即对长事务进行分割.表2为在不同的隐私预算下数据预处理后数据的最大事务长度：

表2 不同隐私预算下预处理后的事务长度

5.3 可用性分析

5.3.1 评价指标

为了验证算法的可用性，采用拒真率(FNR)和相对误差(RE)2个衡量指标.

定义10.拒真率(FNR).用于度量出现在F而没有在F′的项集在F中所占的比例:

F为真实频繁模式集，F′为噪音频繁模式集.

定义11.相对误差(RE).用于衡量算法输出结果中噪音项集支持度与真实支持度间的相对误差，其定义为

其中F′为算法输出结果的频繁项集集合，A为F′中的任意项集，support′A为项集A在算法输出结果中的支持度，即噪声支持度，supportA为项集A的真实支持度.

FNR和RE越小说明算法的可用性越高.

5.3.2 频繁项集可用性

验证频繁项集可用性采用pusmb_star, T10I4D100K，T40I10D100K这3个数据集，并与TF[10]和PrivBasis[16]算法进行对比.为了更好地比较算法的性能，每个数据集分别设置2个k值，设定支持相关性ρ=0.15，并设置TS-ARM算法的λ值与PrivBasis和TF算法的最小支持度阈值相等，其中pusmb_star,T10I4D100K，T40I10D100K这3个数据集的最小支持度阈值分别设置为0.6,0.005，0.05.

由图2、图3、图4均可以看出,3个数据集的FNR和RE都随ε的增大而减小，并且在同等条件下，TS-ARM算法的FNR和RE均小于PrivBasis和TF算法，这是因为本算法采用分割缩短事务长度，将长事务分割为若干个短事务，数据库中单个项的支持度不会产生影响，并且采用双重条件机制，保证了支持度较高的项仍然被分到同一事务中，从而进一步降低了挖掘误差.

图2 pumsb_star数据集的可用性随ε的变化情况

图3 T10I4D100K数据集的可用性随ε的变化情况

图4 T40I10D100K数据集的可用性随ε的变化情况

5.3.3 关联规则可用性

关联规则挖掘结果的可用性验证采用retail，pumsb_star，T10I4D100K这3个数据集.每个数据集设置不同的λ值，最小置信度阈值min_conf从0.1～0.5，间隔为0.1，支持相关性ρ=0.15，ε=0.6，分析FNR和RE的变化情况.由图5可知，3个数据集的FNR和RE均在0.5以下，且FNR值随min_conf的增大而增大，在min_conf>0.4后，其变化趋于平缓，RE的值随min_conf增大而平稳减小.并且3个数据集的FNR和RE均在0.5以下，因此由于噪音频繁项集而导致关联规则产生的误差也较低，并且较为稳定.

图5 3个数据集的挖掘结果可用性随min_conf的变化情况

6 结束语

本文提出了一种满足差分隐私的关联规则挖掘算法TS-ARM.在已有的多种事务截断算法的基础上，设计了一种双重条件机制事务分割方法，基于分割长度阈值和分割支持度阈值对长事务进行分割.该算法的隐私性和可用性在理论上是可证明的，并通过实验证明了算法的可用性.本文提出的分割算法会导致数据集的事务数量有所增加，下一步将考虑在控制事务数量的同时有效缩短事务长度.