用于短频繁项的隐私保护关联规则挖掘方法

张翠翠,阮树骅

(四川大学 计算机学院,四川 成都　610065)



用于短频繁项的隐私保护关联规则挖掘方法

张翠翠,阮树骅

(四川大学 计算机学院,四川 成都610065)

摘要随着数据量的增长,隐私保护的问题也愈发突出,文中是介绍了目前数据挖掘过程中隐私保护相关的基本技术,提出了一种数据集中式分布下布尔数据集的关联规则的挖掘算法,此方法在实现了隐私保护的同时,通过与或运算实现了数据集的压缩。相关实验数据表明,该算法有效减少了挖掘时间,并保证了误差在可接受的范围之内。

关键词隐私保护;关联规则;压缩;数据挖掘;短频繁项集

1研究意义与研究现状

1.1背景和意义

关联规则挖掘是数据挖掘中主要技术之一,可用于发现存在于数据库中项目或者属性之间事先未知的或隐藏的关系。世间万物事情的发生多少会有一些关联:一件事情发生,可能会引发另外一件事情的发生,或者说两个事件在较大程度上会一起发生[1]。通过这个关联规则,可由一件事情的发生来推测另一事件的发生,从而更好地了解和掌握事物的发展、动向等。

数据挖掘的目的在于从大量的数据中抽取出潜在的、有技术价值的知识。传统数据挖掘技术不可避免地暴露敏感数据,而这些敏感数据是数据所有者不希望被揭露的。另一方面,数据发布应用中,如果数据发布者不采用适当的数据保护措施,将可能造成敏感数据的泄露,从而给数据所有者带来危害[2]。隐私保护技术就是为了解决上述问题产生的。实施数据隐私保护主要考虑两个问题:如何保证数据应用过程中不泄露隐私;如何更有利于数据应用。

1.2研究现状

目前,基于隐私保护的关联规则挖掘的研究工作成果众多,本文从所保护内容的角度将关联规则的隐私保护分为两方面:(1)对敏感数据的隐藏保护。1)基于随机化的处理方法。随机响应技术[3]是1965年Warner在统计学中为了保护被调查者的隐私而设计的数据隐藏技术,后来用于关联规则挖掘的隐私保护中。这对后来的隐私保护算法有较大的影响,2004年Aggarwal提出了一种MASK算法[4],之后张鹏等人提出了一种RRPH算法[5],对MASK进行了改进;2)分布式数据的安全计算。2002年,Clifton提出了垂直分布下基于两个参与者的安全计算算法[6]。同年,文献[7]中提出的SMC算法被广泛应用于水平分布的数据库中。

(2)对敏感规则的隐藏保护。对于敏感关联规则的隐藏即是设计一种算法,在阻塞尽量少数据值的情况下,将敏感关联规则可能的支持度和置信度控制在预定阈值以下。

基于阻塞的技术。阻塞技术与随机化技术修改数据、提供非真实数据的方法不同,阻塞技术采用的是不发布某些特定数据的方法,因为某些应用更希望基于真实数据进行研究。2010年,文献[9]中提出了一种DSRRC算法,利用统计信息在尽量少修改数据的同时完成对敏感关联规则的隐私保护。

2关联规则挖掘的概念与步骤

2.1基本概念

设I={I1,I2,…,In}是项的集合。设任务相关的数据D是数据库事务的集合,其中每个事务t是项的集合,且t⊆I。每个事务有唯一的标识符TID。设a是一个项集,事务t包含a,当且仅当a⊆t。一个关联规则是形如a⟹b的蕴含式,其中a⊂I,b⊂I且a∩b=φ。规则a⟹b在事务集D中成立,具有支持度s,其中s是同时包含a和b的事务与总事务的比值,即事务集D中包含a∪b的百分比。

支持度的计算公式为

(1)

规则A⟹B在事务D中具有置信度c,其是事务集D中包含A的事务同时也包含事务B的百分比,即

(2)

2.2关联规则的挖掘算法原理

Apriori关联规则挖掘原理的过程分为以下两步:

步骤1发现支持度不低于用户给定的最小支持度阈值的频繁项集。

步骤2根据步骤1发现的频繁项集,产生置信度不低于用户给定的最小置信度阈值的关联规则。

隐私保护的关联规则的挖掘,就是要在不精确访问原始事务集D的条件下,尽可能精确的产生支持度和置信度分别不低于预先给定的阈值的关联规则。基于隐私保护的基本框架如图1所示。

图1　隐私保护挖掘关联规则基本框架

3关联规则的挖掘

3.1与或运算数据压缩的关联规则挖掘

从现有的隐私保护方法来看,主要是通过改变个体信息,保留或者按照可计算的方式改变总体的统计信息,从而实现隐私保护数据挖掘。

现有的算法所需要的时间为

t=t关联规则挖掘+t支持度还原

(3)

式(3)中,T关联规则挖掘∝N。本文提出了一种新的基于短频繁项的隐私保护方法,其中短频繁项是指频繁项中的项的个数比较小这种隐私保护方法能够有效的减少事务的数量,从而加快关联规则的挖掘时间。

该算法的思想是随机抽取两个样本以概率p进行或运算,以概率q=(1-p)进行与运算。然后通过与或运算后产生的新的数据集中项的支持度计算出原本数据集中对应的项的支持度,从而确定频繁项。该算法的优点是进行与或运算后能将数据集的数量压缩1/2,从而使得关联规则的挖掘时间减少了1/2,即T关联规则挖掘时间∝N/2。这样使得整个算法的时间减少,效率大幅提高。

3.2计算1项集的支持度

设i是一个项,π表示i在D中的支持度,λ表示i在D’中的支持度。下表描述了项i进行与或操作的结果,文中根据i在D和D,中的值是否相同得到关于λ和π的等式,从而得出i的支持度。

表1　1项集的与或结果

相对应各项的概率如图表2所示。

表2　1项集的与或概率

由表1和表2可知,1项集的计算方程

P×(1-π)×(1-π)+(1-P)×(1-π)×(1-π)+(1-P)×π×(1-π)+(1-P)×π×(1-π)=1-λ

P×π×(1-π)+P×π×(1-π)+P×π×π+(1-P)×π×π=λ

(4)

其解如式(5)所示

(5)

这样可利用D’中项i的支持度λ计算出i在D中的支持度π,当π≥预定支持度阈值时,文中便可确定项i是一个频繁项。

3.3计算k项集的支持度

设A={i1,i2,…,ik-1,ik}是一个k项集,其中k的相对比较小,包含了事务集T={t1,t2,t3,…,tn-1,tn},n=2k欲求得D中各事务的支持度,则需要先通过Apriori算法来求得D’中各事务的支持度,然后利用事务之间的关联关系来建立方程。定义1运算如式(6)所示

(6)

(7)

将所有事务的关系联立方程如(8)所示

⋮

(8)

其中

(9)

通过求解Si可得到原有的各支持度。

可利用支持度之间的关系来减少挖掘量,例如当需要计算二项集S(A,B)时,只需要挖掘出S(A,B),然后利用式(10)计算出项S(A,B)的其他相关值

(10)

3.4算法实现

可将以上方法应用到现有各种频繁项集生成的算法中,从而挖掘出感兴趣的关联规则。本文使用 Apriori 算法,对于变换后的数据,文中先利用 Apriori 算法得出候选项集的支持度,然后应用上述方法还原出候选项在数据变换前的支持度,进而确定频繁项集。算法步骤如下:

//对每个项i计数

scan,for each item I∈I count I.count;

for (k=2;L(k-1)≠φ;k++) {

Ck=aproiri_gen (Lk-1);

//生成候选k项集ck

for each transaction t∈D′ {

for (j=1;j≤k;j++) {

//事务t中恰好包含j项的候选k项集

Ct,j=partial_subset (Ck,t,j);

for each candidate c∈Ct,j

c.countj++;

}

}

for each candidate c∈Ck {

c.count=f(c.count0,c.count1,c.countn);

//通过现有关系求得c.count.

L(k)={{c}|c∈Ck,c.count/N≥s};

}

}

return L=∪L(k);

4实验与分析

文中通过一组实验来对比本算法与MASK方法在进行隐私保护关联规则挖掘时的效果,并说明参数P的选择,数据集大小对挖掘结果准确性的影响。

4.1实验方法

频繁项I的计算误差为

(11)

项集F的平均误差为

(12)

本文通过挖掘1项集的支持度来验证算法的可行性,将P设置成不同的值来观察P对SE(I)的影响。然后将P设置成0.4,利用上述算法来求得1项集的支持度,并与实际支持度做对比分析。最后将P设置为0.5,通过修改数据集的大小来观察数据集对SE(I)的影响。

4.2实验结果

4.2.1频繁项长度对误差的影响

首先将阈值设置为1%,P设置为0.4,将允许挖掘频繁项的长度逐步增大,结果如图2所示,可看出随着最大项集的增大,误差越来越大,因此本算法只适用于短频繁项的挖掘。现实数据中,长频繁项并不多见,因此本算法具有一定的实际应用价值。

图2　误差随最大频繁项集的长度的变化

4.2.2p对支持度误差的影响

1项集的SE(I)和SVE随P变化的情况分别如图3所示所示(P的变化步长为0.1)。

图3　2项集SEV随p变化情况

由图3可知,当在0.1～0.9的区间变化时,不同P对结果总误差的影响差不多,因此的选取对SEV的影响较小。

4.2.3数据集对误差和时间的影响

由图4可知,当数据集越大的时候误差趋向于减小。因此,可知对于该算法数据集越大精确度越高。由图5可知,当数据集增大时,本算法在时间上的优势愈发明显。

图4　误差随数据集大小的变化

图5　计算时间T随数据集大小的变化

4.3结果分析

4.3.1随机性选取对结果的影响

由于在数据压缩的过程中,即选取随机两个样本事务进行与或运算的过程中,如何选取两个样本事务是还原支持度的关键,因此,选取一种随机抽取方法是本算法实施的重要环节。

4.3.2数据集大小对结果的影响

当数据集较小时,本算法在还原支持度时会造成严重失真,因此本算法只能用于数量级较大的数据集上。由图4可知,当数据集越大时误差趋向于减小。因此,可知对于该算法数据集越大精确度越高。由图5可知,当数据集增大时,本算法在时间上的优势愈发明显。同时由图2也可以看到随着最大频繁项集长度的增加,误差也会越来越大,因此该方法适用于短频繁项计算。

4.3.3实验准确性分析

有实验的结果对比如图2所示,文中由经过算法变换之后还原一项集合二项集的支持度与直接从原始数据中挖掘数据项的支持度相比误差较小,达到了理想效果。同时,经过实验证明当项集的长度在一定范围内增加时,实验结果的准确度几乎不变。说明该算法在段频繁项上的应用是可行的,准确度相对较高。

5结束语

当频繁项的项数太多时会导致本算法的未知项过多,计算量过大,消耗时间长等问题,因此该算法只适用于短频繁项。由实验结果可知,在减少了一半事务的前提下本实验结果的误差在可接受的范围内,说明此算法在短频繁项中有较好的应用。

隐私保护技术在诸多领域都有广泛的应用,是近年来学术界新兴的研究课题。本文在压缩数据集的情况下进行了隐私保护关联规则挖掘的试探性工作。首先提出了通过对数据进行与或操作对数据集进行压缩,从而隐藏原始数据中的信息,同时使得变换后的数据集减少了一半,这样数据集变换后所占用的空间减少了1/2。本文不仅从理论上分析了运用该算法进行挖掘的准确性,且通过实验验证了这一结论。通过合理的数据选择,文中能实现在空间量减小一半的情况下,实现与原来方法效果相似的隐私性和准确性,且还具有较好的使用性。

参考文献

[1]Nkweteyim D L,Hirtle S C.A new joinless apriori algorithm for mining association rules[J].Computer Science,2005,3(3):284-288.

[2]周水庚,李丰,陶宇飞,等.面向数据库应用的隐私保护研究综述[J].计算机学报,2009,32(5):847-861.

[3]Warner S L.Randomized response:a survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(30):63-69.

[4]Aggarwal C C,Yu P S.A condensation approach to privacy preserving data mining[J].Lecture Notes in Computer Science,2004,25(12):183-199.

[5]张鹏,童云海,唐世渭,等.一种有效的隐私保护关联规则挖掘方法[J].软件学报,2006,17(8):1764-1774.

[6]Yan-Hua F U,Si-Yang G U.Privacy preserving association rule mining in vertically partitioned data[J].Journal of Computer Applications,2002,26(1):639-644.

[7]Kantarcioglu M,Clifton C,Kantarcioglu M.Privacy-preserving distributed mining of association rules on[J].IEEE Transactions on Knowledge & Data Engineering,2002,16(9):1026-1037.

[9]Saygin Y,Verykios V S,Elmagarmid A K.Privacy preserving association rule mining[J].Research Issues in Data Engineering:Engineering E-Commerce/E-Business Systems,2002,35(2):151-158.

[10]Modi C N,Rao U P,Patel D R.Maintaining privacy and data quality in privacy preserving association rule mining[C].San Diego,CA,USA:2010 International Conference on IEEE,IEEE,2010.

[11]葛伟平.隐私保护的数据挖掘[D].上海:复旦大学,2005.

[12]张海涛,黄慧慧,徐亮,等.隐私保护数据挖掘研究进展[J].计算机应用研究,2013,30(12):3529-3635.

[13]陈永春,王晓.隐私保护关联规则挖掘算法分析及研究进展[J].哈尔滨师范大学自然科学学报,2012,28(2):57-59,68.

[14]王锐,刘杰.隐私保护关联规则挖掘算法的研究[J].计算机工程与应用,2009,45(26):126-130.

[15]汤琳,何丰.隐私保护的数据挖掘方法的研究[J].计算机技术与发展,2011,21(4):156-159.

[16]刘浩然,刘方爱,李旭,等.有效的不确定数据概率频繁项集挖掘算法[J].计算机应用,2015(6):1757-1761.

[17]Borgelt C.Frequent item set mining[J].Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery,2012(6):437-456.

A Privacy Preserving Association Rules Mining Method for Short Frequent Itemsets

ZHANG Cuicui,RUAN Shuhua

(College of Computer,Sichuan University,Chengdu 610065,China)

AbstractThe explosion of data poses increasingly challenges on privacy preservation.This paper introduces basic technologies related to the privacy preservation in data mining,and puts forward a mining algorithm under association rule to deal with the Boolean data set distributed in a centralized manner.The method compresses the data set while preserving privacy,thus enormously reducing the time of data mining.Test results show that the mining time is significantly reduced with acceptable errors by this algorithm.

Keywordsprivacy preservation;association rule;compression;data mining;short frequent itemsets

doi:10.16180/j.cnki.issn1007-7820.2016.05.024

收稿日期:2015-10-18

作者简介:张翠翠(1990—),女,硕士研究生。研究方向:人工智能等。阮树骅(1966—),女,硕士,副教授。研究方向:数据库系统等。

中图分类号TP311.563

文献标识码A

文章编号1007-7820(2016)05-088-05