增量式的多源序列模式挖掘隐私保护算法

张　莹,钟　诚,李秋霞

(广西大学 计算机与电子信息学院,广西 南宁　530004)



增量式的多源序列模式挖掘隐私保护算法

张莹,钟诚,李秋霞

(广西大学 计算机与电子信息学院,广西 南宁530004)

摘要:为解决多数据源挖掘隐私保护问题,文章采取按相似度分类多源数据库及其增量数据库,利用原始数据库挖掘结果和增量数据库分析结果进行敏感序列模式匹配,以有效减少数据库扫描次数的方法,设计实现隐私保护的增量式的高投票率序列模式挖掘算法。实验结果表明,给出的算法既能够准确挖掘出多数据源中全局高投票率模式,又能有效地隐藏保护敏感模式,且显著缩短了挖掘时间。

关键词:多数据库挖掘;隐私保护;增量式算法;敏感模式

现实中的数据和信息都是时刻变化的,由此产生了序列模式挖掘增量式更新问题[1]。已有的序列模式挖掘增量式算法需要对原始数据库多次重复扫描,候选项集产生和选择花费大量时空代价[2-3]。基于前缀扫描的序列模式挖掘算法IncSpan[4]在测试阶段不产生候选集合,避免了数据库重复扫描问题。文献[5]提出的序列树前缀扫描算法采用深度优先搜索策略搜索序列树,以发现更新后数据库中的全部序列模式,避免了原始数据库每次更新导致的投影数据库的重复构建问题。另一类序列模式挖掘增量式算法使用频繁模式树而非频繁序列树作为存储结构[6]。文献[7]提出的序列模式挖掘增量式更新算法采用剪枝策略以减少序列模式比较和扫描次数。文献[8]定义频繁序列树作为序列存储结构,通过采用深度优先遍历频繁序列树的方法来找到序列模式。针对已有的增量式序列模式挖掘算法主要处理插入和扩展数据库更新的情况,文献[9]提出针对删除序列更新的增量式挖掘算法。上述算法均是基于单数据源环境设计的,而且它们没有考虑隐私保护问题。近年来,人们开始关注对隐私保护的多数据源序列模式挖掘问题研究。文献[10]采取“分类—清洗—合成—挖掘”方法,提出一种隐藏敏感模式的多数据源高投票率序列模式挖掘算法,但是该算法不适用于多数据库环境中隐私保护的序列模式增量式挖掘。

本文提出一种高效的隐私保护的多数据源序列模式挖掘增量式算法,使其在动态的多数据库环境下,既能准确挖掘出全局高投票率序列模式,又确保敏感序列模式被有效隐藏保护,且显著缩短挖掘时间。

1算法

多数据源序列模式增量式挖掘主要解决数据库分类和半频繁序列模式集合产生这2个问题。为此,首先给出扩展改进的多源序列模式挖掘增量式算法MD-ISPM。

算法1MD-ISPM算法。

输入:k个子数据库D1～Dk,相似度阈值γ,k个增量数据库db1～dbk,n个数据库类classα,α=1～n,缓冲比率μ,最小支持度min-sup,类classα中局部模式集合LPα。

输出:候选频繁模式集CFS,半频繁序列集SFS。

(1)for t=1 to k do

统计每个数据库中模式数sumpt;

For i=1 to sumptdo

统计每个模式Pi的支持数Num(Pi);

计算数据库Dt规模:

t=1～k；j=1～sumpt。

(2)按相似度分类数据库Dt(t=1～k)。①两两计算数据库的列矩阵Dt和Ds的相似度[11]:

② 将D1放入class1中,扫描D1与其余数据库的相似度,按照γ将相似度大于γ的数据库放入class1,并标记已放入class1中的数据库为已选取,α=2;③ 从下一个未选取数据库开始扫描其与其后数据库的相似度,按照阈值γ筛选,将相似度大于γ的数据库归入下一个类classα中;④ α=α+1,重复步骤③,直到全部数据库均被标记为已选取。

(3)输出数据库分类classα,α=1～n。

(4)按数据库分类classα,将k个增量数据库划分为对应的n个增量数据库类db-classα,α=1～n;

(5)for α=1 to n do

统计类classi中局部模式集合LPi每个模式pat的来源数据库Sdb-name(pat)、支持数Num(pat)和投票数Sdb(pat)。

(6)GP←LP1∪LP2∪…∪LPn;CFS=∅。

(7)for i=1 to Num(GP)do

计算全局平均投票率:

(8)for i=1 to Num(GP)do

if Sdb(Pi)

CFS←GP-{Pi}。

(9)SFS=∅。

(10)将增量数据库类db-classα(α=1～n)中模式p分别与CFS比较,若模式p存在其中,则更新该模式支持度;否则若满足投影条件(supLDB(p)≥(1-μ)min-sup),则将模式存入SFS。

(11)输出候选频繁序列集合CFS和半频繁序列集合SFS。

MD-ISPM算法没有考虑挖掘数据库中可能包含敏感序列模式的情形。为了解决敏感序列模式隐藏保护问题,本文给出隐私保护的多源高投票率序列模式挖掘增量式算法HSMD-ISPM。

算法2HSMD-ISPM算法。

输入:原始数据库DB,候选频繁序列集CFS,增量数据库类db-classα(α=1～n),局部模式集db-LPα,缓冲比率μ,最小支持度min-sup,敏感模式集Ph,Ph中的模式Pj(j=1～m)。

输出:增量式更新后序列数据库Inc-DB(DBUdb)中的高投票率序列集Inc-HP。

(1)Inc-CHP=∅;Inc-HP=∅。

(2)for α=1 to n do

for i=1 to Num(db-LPα)do

//比较每个增量数据库类中模式pat与敏感模式集Ph中模式Pj(j=1～m)//

if pat=Pjthen

db-LPα←db-LPα-{pat}。

(3)for α=1 to n do

for i=1 to Num(db-LPα)do

//比较清洗后每个增量数据库类中模式Pi与CFS和SFS中模式Pj(j=1～m)//

if Pi=Pjthen

更新Sdb-name(Pj),Num(Pj),Sdb(Pj);

else

若Pi与非CFS中模式相同,则更新该模式支持数,将其放入CFS中;否则,若满足投影条件(supLDB(Pi)≥(1-μ)min-sup),那么更新后候选频繁序列集合Inc-CHP←Inc-CHP ∪{Pi}。

(4)for i=1 to Num(Inc-CHP)do

if Sdb(Pi)

Inc-CHP←Inc-CHP-{Pi}。

(5)Inc-CHP=CFS ∪ Inc-CHP。

(6)for i=1 to Num(Inc-CHP)do

计算Inc-CHP中每个模式Pi的局部支持度:

计算模式Pi的全局支持度:

(7)Inc-HP=∅。根据全局支持度SuppG(Pi)从高到低排序Pi,i=1～ Num(Inc-CHP)。

(8)输出前20%的模式P作为全局高投票率模式:Inc-HP←Inc-HP ∪ {P}。

HSMD-ISPM算法在步骤(2)中清洗敏感序列模式,将与敏感序列模式集合中相同的序列模式进行隐藏,以确保之后的挖掘中不再出现该敏感序列模式,有效地防止了敏感信息泄露;在步骤(3)中,扫描增量数据库与初次挖掘所得候选频繁序列集合,同时为防止非CFS中模式可能变频繁或者半频繁,将清洗筛选后剩余的增量模式与非CFS中模式比较,更新存在的模式支持数并加入候选频繁序列集CFS中,随后通过缓冲比率μ判断筛选符合条件的半频繁序列集合和候选增量更新后的频繁序列集合。因此,HSMD-ISPM算法既能够准确挖掘模式又确保敏感模式信息得到保护。

2实验

实验硬件平台为内存容量4 GB、CPU为AMD Athlon(tm)II X 4645的四核计算机,运行的操作系统为Windows XP,采用C++语言编程实现算法。实验所采用的原始数据由IBM人工数据生成器AssocGen产生,例如:交易事务数目为1 000的一个数据库生成参数选择为T4I1D1000C1L10。其中，参数T表示每条交易事务中平均包含模式数；I表示包含项集大小(单位为100个项集)；D表示包含交易事务数目；C表示数据库中顾客数(单位为100个顾客)；L表示序列平均长度。

表1所列为实验中使用的交易事务数、数据库中的模式数,其中D1～D5代表5个数据库,其最低支持度(%)依次为0.01、0.13、0.02、0.01和0.015。

表1　数据库及其对应的交易事务数、模式数

本文将HSMD-ISPM算法与MD-ISPM算法、HSMD-ISPM算法与非增量式的多源高投票率序列模式挖掘隐私保护算法HS-MDPM[10]进行实验测试，比较挖掘效率和挖掘准确度。

敏感模式数为17,原始数据库个数为5,最低支持度分别为0.01、0.13、0.02、0.01、0.015,序列更新比(增加数据集占总数据集比例)为20%,当数据集交易条数逐渐增加时,HSMD-ISPM算法与HS-MDPM算法所需的挖掘时间如图1所示。

由图1可知,在其他参数都固定的情形下,当数据集交易条数逐渐增加时,HSMD-ISPM算法与HS-MDPM算法所需的挖掘时间均随着数据集规模的增大相应增加。此外,HS-MDPM算法的运行时间要明显大于HSMD-ISPM算法。由于HS-MDPM算法需要重复扫描原数据库,时间消耗大,而HSMD-ISPM算法充分利用了前一次挖掘结果,通过对增量数据库中新增加模式的匹配分析,筛选出全局高投票率序列模式,只需对原始数据库进行一次扫描,因此运行时间显著缩短。实验结果表明,HSMD-ISPM与HS-MDPM算法虽然采用了不同的数据挖掘模型和方式,但最终都得到了相同的全局高投票率模式。本文提出的HSMD-ISPM算法在保证敏感序列模式被安全隐藏的同时,挖掘出准确的全局高投票率序列模式,有效减少了挖掘时间。

图1　HSMD-ISPM和HS-MDPM算法的运行时间

敏感模式数、原始数据库个数、每个数据库最低支持度、序列更新比固定,数据集交易条数逐渐增加时,HSMD-ISPM算法与MD-ISPM算法所需的挖掘时间如图2所示。

图2　HSMD-ISPM和MD-ISPM算法的运行时间

图2的结果表明,当其他参数都固定、数据集交易条数逐渐增加时,HSMD-ISPM算法与MD-ISPM算法所需的挖掘时间均随着数据集规模的增大相应增加。此外,HSMD-ISPM算法所需挖掘时间稍微多于MD-ISPM算法,这是因为HSMD-ISPM算法需要将候选模式集合中每个模式与敏感模式集合中的敏感模式进行匹配比较,将相同模式作为敏感模式清洗出候选高投票率模式集合,实现敏感模式的隐藏;而MD-ISPM算法没有进行敏感序列模式隐藏,无需进行匹配处理,因此其所需的处理时间相对少一些。此外,原始数据库中包含的部分模式既是高投票率模式又是敏感模式,在隐藏敏感序列模式增量式挖掘算法HSMD-ISPM中,这些敏感模式将被清洗掉,以确保挖掘结果的安全准确。这表明,在同样进行增量式挖掘前提下,HSMD-ISPM算法通过花费少量的敏感模式匹配处理时间,就可以确保挖掘出符合条件的全局高投票率序列模式的同时,实现敏感模式隐藏保护。

图3、图4所示分别为序列更新比和数据集支持度阈值变化时,HSMD-ISPM算法、HS-MDPM算法和MD-ISPM算法所需的运行时间。

图3　序列更新比变化对算法运行时间的影响

图4　支持度阈值变化对算法运行时间的影响

由图3可知,当数据集规模、敏感模式数、原始数据库个数、最低支持度阈值都固定时,随着增加的数据集占总数据集的比例逐渐增加,HSMD-ISPM算法、HS-MDPM算法以及MD-ISPM算法的挖掘时间都随着序列更新比的增大而相应增加；对于任意的序列更新比,HS-MDPM算法所需的运行时间都要明显大于其他2种算法。这表明增量式挖掘无需重复扫描原始数据库,可以有效缩短挖掘时间,提高效率。此外,HSMD-ISPM算法与MD-ISPM算法所需的挖掘时间差别并不十分明显。这表明,HSMD-ISPM算法既能保证挖掘出准确的全局高投票率模式,又能有效隐藏敏感序列模式,同时大大缩短了挖掘时间。

图4的实验结果表明,当其他参数都固定时,随着数据集支持度阈值逐渐增加,HSMD-ISPM算法、HS-MDPM算法以及MD-ISPM算法的挖掘时间都随着支持度阈值的增大而相应减少。这是因为支持度阈值提高时,符合条件的高投票率序列模式数会相应减少,因此挖掘所需的时间会相应减少。从图4可以看出，HSMD-ISPM算法与MD-ISPM算法所需的挖掘时间几乎相同。此外,对于任一支持度阈值,HSMD-ISPM算法挖掘时间大大缩短,既能确保挖掘出准确的全局高投票率序列模式,又能有效隐藏敏感序列模式。

3结束语

本文提出了一种高效增量式的多源序列模式挖掘隐私保护算法,它能够准确挖掘多数据库中全局高投票率序列模式,同时隐藏敏感序列模式、保护敏感信息安全。下一步工作将研究在云存储平台上设计隐私保护[12]的多数据库源序列模式增量式挖掘并行算法。

[参考文献]

[1]彭慧丽,张啸剑,张亚东.IM-FTS:一种快速增量式频繁访问序列挖掘算法[J].计算机工程与应用,2009,45(3):138-141.

[2]Masseglia F,Poncelet P,Teisseire M.Incremental mining of sequential patterns in large databases[J].Data &Knowledge Engineering,2003,46(1):97-121.

[3]Hsieh C Y,Yang D L,Wu J.An efficient sequential pattern mining algorithm based on the 2-sequence matrix[C]//Proceedings of the 2008 IEEE International Conference on Data Mining Workshops,Piscataway,New Jersey.IEEE,2008:583-591.

[4]Cheng H,Yan X,Han J.IncSpan:incremental mining of sequential patterns in large database[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2004:527-532.

[5]Liu J,Yan S,Ren J.The design of frequent sequence tree in incremental mining of sequential patterns[C]//Proceedings of the IEEE 2nd International Conference on Software Engineering and Service Science,Piscataway,New Jersey.IEEE,2011:679-682.

[6]Lin C W,Hong T P,Lu W H,et al.An incremental FUSP-tree maintenance algorithm[C]//Proceedings of the 8th International Conference on Intelligent Systems Design and Applications,Piscataway,New Jersey.IEEE,2008:445-449.

[7]吴永俊,郑诚,孔令成.一种有效的序列模式增量式更新方法[J].计算机工程与应用,2011,47(9):118-120.

[8]刘佳新.一种高效的增量式序列模式挖掘算法[J].计算机工程,2012,38(12):39-41.

[9]刘佳新,严书亭,任家东.缩减投影数据库规模的增量式序列模式算法[J].计算机工程,2012,38(3):28-30.

[10]张莹,钟诚.隐私保护的多数据源高投票率序列模式挖掘[J].小型微型计算机系统,2015,36(1):100-105.

[11]Wu X,Zhang C,Zhang S.Database classification for multi-database mining[J].Information Systems,2005,30(1):71-88.

[12]朱晓姝,孙小雁,熊莉,等.基于密钥树的云平台隐私保护与分享技术研究[J].合肥工业大学学报:自然科学版,2015,38(8):1071-1073,1136.

(责任编辑张镅)

Efficient incremental algorithm for mining sequence patterns in multiple databases with privacy preserving

ZHANG Ying,ZHONG Cheng,LI Qiu-xia

(School of Computer,Electronics and Information,Guangxi University,Nanning 530004,China)

Abstract:To solve the problem for incremental mining sequence patterns in multiple databases with privacy preserving,the original databases and their corresponding incremental databases are classified by similarity of item set,the sensitive sequential pattern set is used to match each class of original databases and the incremental databases to reduce the scan times,and a privacy-preserving incremental algorithm for mining the global high-voting sequential patterns in multiple databases is designed.The experimental results show that the proposed algorithm can mine correctly the global high-voting sequential patterns in multiple databases,hide the sensitive patterns,and shorten remarkably the mining time.

Key words:multi-database mining;privacy preserving;incremental algorithm;sensitive pattern

收稿日期：2015-07-01；修回日期：2016-02-23

基金项目：广西自然科学基金资助项目(2011GXNSFA018152);广西大学实验技能和科技创新能力训练基金资助项目(SYJN20130701)

作者简介：张莹(1988-),女,陕西宝鸡人,广西大学硕士生;

doi:10.3969/j.issn.1003-5060.2016.04.010

中图分类号:TP319

文献标识码：A

文章编号：1003-5060(2016)04-0481-05

钟诚(1964-),男,广西桂平人,博士,广西大学教授,博士生导师.