高维不确定数据频繁项集挖掘技术研究——论文

1、项目名称 高维不确定数据频繁项集挖掘技术研究项目负责人（签名）_ _所在学校（盖章）_“研究类别”含义： 基础研究：指为获得关于现象和可观察事实的基本原理及新知识而进行的实验性和理论性工作，它不以任何专门或特定的应用或使用为目的。 应用研究：指为获得新知识而进行的创造性的研究，它主要是针对某一特定的实际目的或目标。 试验发展：指利用从科学研究和实际经验中所获得的现有知识、生产新材料、新产品、新装置、新流程和新方法，或对现有的材料、产品、装置、流程、方法进行本质性的改进而进行的系统性工作。 推广应用、科技服务：指与研究与发展活动相关并有助于科学技术知识的产生、传播和应用的活动。研究项目项目名称高

2、维不确定数据频繁项集挖掘技术研究研究类别11.基础研究 2.应用研究 3.试验发展 4.推广应用 5.科技服务依托的一级学科工学成果形式论文起止时间 2014.5-2015.6经费申请总额 1 万元其他经费及其来源项目负责人姓 名职 称工作单位电子邮箱项除目负组责主人要外成五员名姓名职称学位专业工作单位承担任务本人签名项目负责人近三年来承担的研究项目项目名称项目来源起止年月排名进展大规模耦合非线性系统中混沌同步和信息流动的研究宁波市自然基金20126-20146第一在研信息化环境下的高校差导化教学模式研究全国教育技术课题20136-20146第一在研面向大数据的高频金融时间序列高效用时态频繁模

3、式挖掘研究宁波市自然基金20139-20159第二在研基于BP神经网络Ni-TiO2纳米镀层的预测及优化研究省科研厅项目20136-20146第三在研项目负责人为第一署名人的代表性成果成果名称成果来源获得时间排名等级Research and Application of Algorithm for Mining Positive and Negative Association Rules国际会议2011年第一EIA study of Negative Association Rules Mining Algorithm Based on Multi_Database国际会议2013年第一EI

4、1本项目研究意义及国内外同类研究工作现状（附主要参考文献及出处）：（1）项目的背景和意义随着计算机信息处理领域的兴起，数据挖掘技术在近几十年的发展中越来越成熟，聚类、分类、关联频繁项集、回归预测、时序模式、孤立点检测等挖掘方法已被人们所接受，但这些处理均是针对确定数据进行的挖掘。事实上，随着科技的发展和信息应用需求的不断扩大，数据采集及数据处理技术得到了长足的发展，不确定性数据已广泛出现在诸多应用领域之中，如传感器网络、RFID应用、数据集成、LBS（Location Based Services）、Web 应用等。针对确定数据的传统挖掘方法显然不能实现不确定数据挖掘的目的，近年来不确定数据中

5、的数据挖掘问题成为了研究热点1。对不确定数据的研究主要有两个方面，数据管理和数据挖掘。在数据管理方面，由于传统技术已无法应对不确定数据，大批学者及工业界对研发新型的不确定管理技术有着浓厚的兴趣，已有了很多成果，主要研究有不确定的表示与模型定义2-3、预处理与集成4-6、存储与索引7-8、查询分析处理9-11，其技术已相对成熟。与不确定数据管理相比，不确定数据挖掘技术则起步较晚，由于数据的不确定性对挖掘的结果产生不可忽视的影响，甚至可能对研究的结论产生致命的错误，因此对不确定数据挖掘研究更显得意义重大。目前不确定数据挖掘研究主要内容有聚类、分类、频繁项集挖掘和孤立点检测，其中频繁项集挖掘是研究的

6、重点问题之一，而且频繁项集挖掘算法主要集中在完全频繁项集，而对于最大频繁项集和频繁闭项集的研究尚不多见，从我们自CNKI论文查阅来看，专门研究不确定数据的频繁项集挖掘的论文也不太多，由于高维数据存在“维灾”问题，因而研究高维不确定数据的频繁项集挖掘则更少。本项目拟对高维不确定数据及不确定数据流的频繁项集的挖掘算法进行研究，分析现有的相关的频繁项集挖掘算法的不足及缺陷，提出改进及扩展方案，在利用频繁闭项集设计高效的挖掘算法上有所突破，并通过实验验证新的算法的性能及执行效率。（2）国内外研究现状和研究趋势频繁项集挖掘起源于关联规则挖掘问题，关联规则挖掘问题首先是由Agrawal于1993年提出的1

7、2，其目的在于确定超大型数据库中项集之间的关系，并从中求出所有频项集及其支持度。在传统数据库中进行频繁项集挖掘方法主要有两种，它们是基于先验的Apriori13-16算法和基于树结构的FP-growth算法17-22，之后的工作大多是在上述两类算法基础上进行改进及扩展。对于不确定数据的频繁项集，显然不能仅用传统的Apriori算法和FP-growth算法进行挖掘，需要根据不确定数据的特征对Apriori算法和FP-growth算法进行改进或扩展。不确定数据的频繁项集挖掘分为两类，一类是对不确定数据的频繁项集挖掘，另一类是对不确定数据流的频繁项集进行挖掘。（a）不确定数据的频繁项集挖掘为了在不确

8、定数据中挖掘频繁项集，Chui等人将Apriori算法进行了改进，提出了U-Apriori算法23。在Apriori算法中，候选集的支持度是通过累加其确定的支持数来计算的，如果该候选集在事务中出现了，则将其支持度加l；而在不确定数据库中，每个项的支持度是用概率表示的，每个项集的支持度是通过累加属于该项集的概率的乘积得到的。U-Apriori算法同样也是基于产生检验的，因此同样不适合于数据库比较大的情况，尤其是当候选项集中很多项的概率很小时，将其概率相乘再累加是毫无意义的计算，增加了执行时间及系统消耗。为了解决这个问题，Chui等人提出了一种剪枝策略，将原始数据库中小概率的事件先去掉，形成一个新

9、的数据库DT，然后在数据库DT中应用U-Apriori算法。该策略对原始数据库中小概率项的比重R敏感，并且在剪枝时还要设定一个剪枝阈值，且阈值的设定不太容易，如果设定太大，可能会减掉频繁的项集，如果设定太小相应减掉的项集也少，从而造成新的数据库DT过大，因此阈值的设定是有很大难度的24。为了解决以上问题，Chui等人于2008年又提出了一种替代方法，称为缩量剪枝法24。通过两种改进方案，可以产生更少的候选项集的非空子集，减少了系统消耗，提高了执行效率。类似于Apriori算法的改进，Leung等人在FP-growth算法的基础上提出一种适用于不确定数据库中挖掘频繁项集的基于树结构的算法UF-g

10、rowth算法25-27。UF-growth算法分为两步，一步是构建UF-tree，另一步是在UF-tree中进行频繁项集的挖掘。UF-growth挖掘过程与FP-growth的挖掘过程类似，但也有不同：(1)当为某个项集X建立子数据库的UF-tree时需要记录该项集X的支持度；(2)比项集X范围更大一点的项集的支持度是通过该分支上Z的支持度与Y的支持度相乘得到的。根据以上规则，结合FP-growth挖掘方法即可得到所有的频繁项集。由于在建树过程中只有当项名与其对应的支持度完全一致时才可以合并，最坏情况下树中结点的个数与数据库中所有事务中所有项的数目一致，这将占据很大的内存空间，为了节省内存空

11、间，Leung等人又提出了两种改进方案。方案一：在不确定数据库中，某些项的支持度可能是无限小数，在树结点中保存这些支持度本身就占据了大量的内存空间，因此，在建树之前可以约定保留几位有效数字，这样既可以减少保存无限小数减少占用的内存空间，也可能增加相同项名有相同支持度的几率，减少了树中结点的数目，节省内存空间。方案二：在挖掘过程中只为最初的原始数据库和单个项X建立UF-tree，即不为项集X建立UF-tree，从单个项X的UF-tree中提取其路径，计算出该路径上所有子集的支持度，从中找出所有频繁的项集。通过以上两种改进方案，Uf-growth算法可以更好地节省内存空间，提高算法的性能。(b)不

12、确定数据流的频繁项集挖掘由于数据流是连续的、无限的，并且数据流中的数据不是均匀分布的，其分布通常随着时间的变化而变化，因此在数据流中挖掘频繁项集难度更大。早期 Giannella 等人提出了FP-streaming算法，但是该算法是基于静态的数据流的。要想实现从不确定数据流中挖掘频繁项集就需要提出新的算法或对已有的算法进行改进。根据FP-stream的思路，Leung等人于2009年提出了UF-stream算法28。UF-stream算法存在以下几个问题：首先，找出的“可能频繁”的项，不是真正频繁的，想要找出真正频繁的还要进行后期的处理，并且依靠“预备阈值”也可能会漏掉频繁的项，同时选取该预备

13、阈值如同选取阈值一样也是有很大困难的。其次，该算法需要一个额外的结构(UF-stream)来保存挖掘的项集。第三，该算法是“立即”挖掘的也就是每个数据流过来的时候都要保存，而这其中的很多可能并不是用户需要的，这就造成了大量的浪费。为了解决以上问题，Leung等人又提出了另一种算法SUF-growth算法。SUF-growth算法也是基于树结构的，首先，建立一棵SUF-tree用来保存数据流中的项，由于数据流是不断变化的，树上的结点的位置会随着数据流中数据的不断变化而改变，因此在建立SUF-tree时要选择一种规范的排序方式(如词典顺序)，这样树中结点的位置就不会随时问而改变了。UF-tree中

14、每个结点包括三部分：项的名称、项的支持度以及一个记录表，其中该记录表保存了该项的支持度在当前窗口中的每批数据流中出现的次数，这样当新的数据项到达时比较容易更新结点保存的信息。与UF-streaming算法相比，SUF-growth有以下优势：首先，SUF-tree返回给用户的是真正频繁项集；其次，该算法不需要额外的UF-stream树结构来保存挖掘到的项集；第三，该算法采用“推迟”的挖掘模式，也就是当数据需要的时候才进行挖掘，这就避免造成大量的浪费。为了验证这两种方法的优劣，Leung等人分别在IBM数据集、FIMI数据集以及UCI数据集上设计了对比实验，其实验结果是相似的。综上所述，对不确定

15、数据的频繁项集挖掘，不管是对不确定数据还是对不确定数据流的挖掘，都是近几年发展的技术，而且主要集中在完全频繁相集上，而对于最大频繁项集和频繁闭集的挖掘研究尚不太多，本项目拟对高维不确定数据及不确定数据流的频繁项集的挖掘算法进行研究，一方面，针对高维不确定数据，解决“维灾”问题，专门对稀疏类不确定数据进行频繁集挖掘；另一方面，利用频繁闭项集设计高效的数据挖掘算法，并通过实验验证新的算法的性能及执行效率。参考文献:1 李雪，江贺.不确定数据挖掘技术研究进展J.中国科技论文在线，2009. 2 C.CAggarwalManaging and dining uncertain dataMSpringe

16、r,20093 ADSarma，OBenjel loun，AHalevy，et alWorking models for uncertain dataCProc of the 22nd IEEE International Conference on Data Engineering， 7-7，20064 FSadriModeling uncertainty in databasesCProcof the 7th International Conference on Data Engineering，122131，19915 MGruteser，DGrunwaldAnonymous usag

17、e of locationbased services through spatial and temporal cloakingCProcof the 1st International Conference on Mobl ie SystemsApplicat ions and Services，3142，20036 JRCheng，JCChen，XXieCleaning uncertain data with quality guaranteesCProcof the Very Large Data Bases Endowment，1(1)，722735，20087 RCheng，SSi

18、ngh，SPrabhakarU-DBMS：A database system for managing constantlyevolving dataCProcof the 31”International Conference on Very Large Data Bases，127 1127420058 LAntova，CKoch，DOlteanuMayBMS：Managing incomplete information with probabilistic worldset decompositionsCProc of the 23rd International Conference

19、 on Data Engineering，14791480，20079 NDalvi，DSuciuEfficient query evaluation on probabilistic databasesCProcof the 13th International Conference on Very Large Data Bases，864875，200410 N Dalvi，D SuciuAnswering queries from statistics and probabilistic viewsCProc of the 31st International Conference on

20、 Very Large Data Bases， 200511 MASol iman，IFIlyas，KCCChangTop k-query processing in uncertain databasesCProcof the 23rd IEEE International Conference on Data Engineering，200712 R Agrawal,T Imielinski, A Swami. Mining Association Rules Between Sets of Item in Large Databases. In Proc. Of the ACM-SIGM

21、OD Int. of Con. on Management of Data. Washington D. C. ,1993,207-216.13 Agrawal R.Srikant RFast algorithms for mining association rules in large databasesC.Proc of 20th ICDE1997：487-49914 Agrawal RSrikant RMining sequential pattemsC.Proc of the l lth ICDE。1995：3-1415 Bonehi F，Lucchese CPushing toug

22、her constraints in frequent pattern miningQ.Ho T BCheung D，Liu HLNCS 35 I 8：PAKDD 2005Heidelberg：Springer，2005：114-12416 Agrawal RSrikant RFast algorithms for mining association mlesC.Proe VLDB，1994：487-49917 Cheung W，Zaiane O RIncremental mining of frequent patterns without candidate generation or

23、support constraintC.Proc IDEAS2003：111-11618 E1Hajj MZaiane O RCOFI-tree mining：a new approach to pattern growth with reduced candidacy generationC.Proc FIMI200319 Giannella C，Hart JMining frequent patterns in data streams at multiple time granularitiesC.Data Mining：Next Generation Challenges and Fu

24、ture Directions，200420 Hart J.Pei J，Yin YMining frequent patterns without candidate generationC.Proc SIGMOD2000：1-1221 Leung C K S，lrani P P，Carmichael C LFlsViz：a frequent itemset visuaHzeC.Washio T.Suzuki ETing K M，et a1LNCS 5012：PAKDD 2008Heidelberg：Springer，2008：64465222 Leung C K S，Mateo M A F，

25、8rajczuk D AA tree-based approach for frequent pattem mining from uncertain dataC.LNAI 5012：PAKDD2008：653-66123 Chui C K，Kao B，Hung EMining frequent item sets from uncertain dataC.Zhou Z HLi HYang QLNAJ 4426：PAKDD，2007：47-5824 Chui C K，Kao BA decremental approach for mining frequent item sets from u

26、ncertain dataC.LNAl 50 1 2：PAKDD，2008：647525 Leung C K S，Mateo M A F，8rajczuk D AA tree-based approach for frequent pattem mining from uncertain dataC.LNAI 5012：PAKDD2008：653-66126 Leung C K S，Carmichael C L，Hao BEfficient mining of frequent patterns from uncertain dataC.Proc .1EEE 1CDM Workshops200

27、7：489-494.27 Leung C K SBrajczuk A D Efficient mining of frequent itemsets from data strearnsC.LNCS 5071：BNCOD，2008：2-1428 Leung C K SHao BMining of frequent items from stream of uncertain dataC.Proc IEEE Computer Society2009：166316702主要研究内容、目标、方案和进度及拟解决的关键问题：(1) 项目研究目标研究高维不确定数据的频繁模式的挖掘技术，分析现有相关频繁项集

28、挖掘算法的不足及缺陷，提出改进及扩展优化方案，以期提高挖掘算法的性能及执行效率。(2) 项目研究内容围绕上述研究目标，本申请项目计划在以下几个方面开展研究：(a) 不确定数据频繁项集挖掘模型的建立不确定性数据的种类较多，如多维数据、半结构化数据、流数据、空间数据、图数据、移动对象数据等。针对不确定数据定义模型有多种方法，本申请项目拟采用最通用的可能世界模型(possible world model)定义不确定数据频繁项集。(b) 频繁模式的挖掘算法分析本项目研究不确定数据的频繁项集的挖掘算法从两类入手，即不确定数据频繁项集挖掘与不确定数据流频繁项集挖掘。 不确定数据频繁项集挖掘算法分析根据采用

29、的模型，对当前两类频繁项集，即基于期望支持度模型和基于概率频繁模式模型，从基于先验的确定数据的Apriori-based挖掘算法，到基于产生检验的不确定数据的U-Apriori算法，再到U-Apriori算法的缩量剪枝UCP-Apriori算法；从基于树结构的确定数据的FP-growth算法到适用于不确定数据的UF-growth算法。对以上算法从数据及数据库的类型、检验的标准、挖掘步骤及过程、内存的占用、算法运行时间、资源消耗等作深入分析，为算法的改进及扩展作好理论及实践准备。 不确定数据流频繁项集算法分析对不确定性数据流频繁项集挖掘的两个主要算法UF-sreaming算法和SUF-rowth

30、算法，从算法的主要思想、挖掘步骤及过程、不确定数据流的特点、存储结构的简易性、数据的维护等方面作深入分析，进一步为算法的改进及扩展作好准备。(c) 改进及扩展频繁项集挖掘算法通过前面对现有算法的深入分析，找出现有算法存在的不足及缺陷，并对其进行改进及扩展，产生新的频繁项集挖掘算法，这个算法与现有的算法相比，在系统消耗、内存占用、运行时间等方面一定要有更好的性能及效果。(d) 算法的性能及实验结果分析对新算法采用C+编写及设计，然后通过IBM数据生成器生成不同性质的合成数据验证算法的效率，另外还利用本单位与企业之间合作的条件获取大宗交易数据验证算法的性能，从理论到实践，全面验证及分析。(3) 方

31、案和进度（a）拟解决的方案 不确定数据模型的定义在不确定数据模型定义之前，先假定数据集D由d个事务t1,t2,td构成，每个事务ti有多个项组成，每个项X在事务ti中出现的概率用只P(x，ti)表示。这样，现实世界就存在两种可能的情况，称为两种可能世界W1和W2，W1表示项x出现在ti中(xti)，其概率P(W1)=P(x，ti)，W2表示项x没有出现在ti中(xti)，其概率P(W2)=1-P(x，ti)。更进一步说，每个事务ti中包含多个项，假设ti中包含x和y两个项则会出现4种可能世界，其中同时包含x和y的可能世界的概率为P(x，ti)*P(y，ti)。对于一个数据集X来说,其出现在现实

32、世界的预计支持度(except support)是通过累加项集X在每个可能世界Wj的支持度来得到的，X在可能世界影中出现的概率(x关于Wj的支持度)用S(X,Wj)表示。对于每一个可能世界形Wj来说，用P(Wj)表示可能世界Wj出现的概率，数据集X出现在现实世界中的支持度用expSup(X)表示，则有以下公式（1） （2）根据以上公式，如果项集X的支持度expSup(X)大于或等于用户指定的支持度阈值，则认为项集X是频繁的，否则认为项集X是不频繁的。 频繁模式的挖掘算法分析频繁项集挖掘是关联规则挖掘及其它数据挖掘应用中的关键技术和步骤，自从Agrawal等人提出关联规则的挖掘思想之后，人们对关

33、联规则和频繁项集挖掘的研究工作就没有停止过。目前对不确定数据的频繁项集挖掘的研究主要还是在传统的确定数据的频繁项集挖掘算法Apriori算法和FP-growth算法上作改进及扩展。Apriori算法是基于先验的确定数据的频繁项集挖掘，但它是在静态数据库中的挖掘，在挖掘过程中经常要回到原始数据库中检验候选项集是否频繁，当数据库比较大时，运行效率不高。为此，Chui等人将该方法进行了改进，提出了U-Apriori算法。U-Apriori方法也是基于产生-检验的，因此同样不适用于数据库比较大的情况，尤其是当事务数据库中有很多支持度较小的项时，将增加大量无意义的计算，这在很大程度上增加了算法执行时间及

34、系统消耗。为了解决这个问题，chui等人提出了一种剪枝策略，将原始数据库中支持度较小的项剪枝，形成一个新的数据库DT，然后在数据库DT中应用U-Apriori算法，如下图1所示是其挖掘处理过程。但鉴于修整阈值难以确定，Chui等人对U-Apriori进行改进，提出了UCP-Apriori算法，并提出交替递减剪枝技术。为了进一步提高U-Apriori算法的执行效率，Chui等人又提出了两种改进策略：单例整合方法AS（Aggreate by Singletons）和公共前缀方法CP集（Common Prefix Method）。通过这两种改进方案，可以有效减少候选项集产生的非空子集，减少系统的消耗

35、，提高执行效率。基于树结构的FP-growth算法是在传统数据库的频繁项集挖掘中比较高效的算法，类似于在Apriori算法基础上提出U-Apriori的方法，Leung等人在FP-growth算法的基础上提出了一种用于不确定性数据库中频繁项集挖掘的基于树结构的算法UF-growth。与FP-growth算法类似，UF-growth算法也分为两个步骤：（1)构建UF-Tree； (2)在UF-Tree中进行频繁项集的挖掘。原始数据中的频繁项集原始数据库整理模块剪枝模块U-Apriori修补模块统计修整过的数据集DTDT的频繁项集可能的频繁项集非频繁k-项集wys 可能的频繁k-项集迭代K次已剪枝

36、的项集 图1 U-Apriori算法的处理过程尽管UF-growth挖掘过程与FP-growth的挖掘过程类似，但也有不同：(1)当为某个项集X建立子数据库的UF-tree时需要记录该项集X的支持度；(2)比项集X范围更大一点的项集的支持度是通过该分支上Z的支持度与Y的支持度相乘得到的。根据以上规则，结合FP-growth挖掘方法即可得到所有的频繁项集。由于在建树过程中只有当项名与其对应的支持度完全一致时才可以合并，最坏情况下树中结点的个数与数据库中所有事务中所有项的数目一致，这将占据很大的内存空间，为了节省内存空间，Leung等人又提出了两种改进方案。方案一：在不确定数据库中，某些项的支持度

37、可能是无限小数，在树结点中保存这些支持度本身就占据了大量的内存空间，因此，在建树之前可以约定保留几位有效数字，这样既可以减少保存无限小数减少占用的内存空间，也可能增加相同项名有相同支持度的几率，减少了树中结点的数目，节省内存空间。方案二：在挖掘过程中只为最初的原始数据库和单个项X建立UF-tree，即不为项集X建立UF-tree，从单个项X的UF-tree中提取其路径，计算出该路径上所有子集的支持度，从中找出所有频繁的项集。通过以上两种改进方案，Uf-growth算法可以更好地节省内存空间，提高算法的性能。UF-streaming算法的主要思想继承了确定性数据流挖掘算法FPstreaming的

38、思想。该算法分2步：第1步建立UF-stream结构，它是一棵前缀树，具有相同前缀的项集共享父节点，每个节点都有一个滑动窗口，记录着从节点到根节点路径上项集在该窗口中出现的期望值；第2步是挖掘频繁项集，遍历UF-stream结构，对每个节点的窗口中的期望值进行累加，如果期望值之和大于等于设置的最小期望支持度，则该节点到根节点路径上项集为频繁项集。当窗口满时，滑动UF-stream结构中每个节点的窗口删掉最旧的一批项集。以上算法由于没有考虑不确定性数据流的特点，因而存在储存结构复杂，维护困难，以及挖掘频繁项集时计算量大等缺点。 改进及扩展频繁项集挖掘算法从前面对现有算法的分析可以知道，现有算法一

39、般是基于完全频繁项集的，而且其执行效率有待提高。本项目拟采取频繁闭项集方式设计算法，在UF-growth基础上进一步改进。想办法通过自上而下的投影策略，适合于高维稀疏性的不确定数据，从而有效地提高执行效率。本项目拟备从两个方面进行改进，一是设计高效的数据结构，节省数据存储的空间及时间消耗；二是设计高效的剪枝策略，去掉无效的冗余数据，缩短扫描时间，提高执行效率。 算法的性能及实验结果分析对新算法程序设计拟定为用C+编写。实验中使用的数据拟通过IBM数据生成器生成不同性质的合成数据验证算法的效率。实验数据个数初步定为100K，平均事务长度为10，1000种不同项的数据集。对算法的性能测试拟定从最小支持度的阈值、数据的稀疏程度对算法性能的影响，算法的收缩性测试，在相同数据集下与现有的算法在时间运行与空间大小的比较等方面进行，如下表1及图2所示为基于UF-Tree的最大频繁项集挖掘算法中最小支持度阈值对算法运行时间的影响的实验结果供参考。表1 最大频繁项集挖掘算法运行时间最小支持度运行时间0215005350011352015301502580002588050312230005010150202503020406080120100图2 最小支持度阈值(b) 研究进度本项目计划在1年内完成，首先建立不确定数据频繁项集的挖掘模型，在模型基础上，对现有不确定数据及不确定数据流的挖掘算法进行分