不确定数据中频繁序列模式挖掘算法的-研究

《不确定数据中频繁序列模式挖掘算法的-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、不确定数据中频繁序列模式挖掘算法的研究摘要近年来，不确定数据(UncertainData)得到了越来越广泛的重视。数据的不确定性本身存在于许多真实世界的应用，例如传感器数据监测、环境监视、移动轨迹、定位服务，归因于环境因素、设备缺陷、人为问题等。数据不确定性普遍存在的同时，且不确定性数据往往扮演着关键角色。不确定数据挖掘也成为数据挖掘领域中一个非常重要的研究课题。本文以不确定性数据的频繁序列模式挖掘算法作为研宄对象。相比于确定序列数据库，不确定序列数据库中挖掘序列模式更加复杂，其通常有着更大的搜索空间。由于数据的不同，已知的目前

2、被广泛应用的基于确定数据的序列模式挖掘方法也不能够直接用来解决不确定序列模式挖掘问题。本文分析了在确定的数据中挖掘序列模式的方法，分别基于候选集生成-测试框架与基于模式增长框架，介绍了几个经典的序列模式挖掘算法。通过对序列模式挖掘算法的分析，得知模式增长框架相比候选集生成-测试框架更具有扩展性。然后，阐述了不确定数据挖掘的一些基础理论。给出了可能世界数据模型，包括源头水平不确定数据模型与事件水平不确定数据模型。对本文所研究的一般不确定序列数据，需要序列模式进行判断是否为可能频繁序列模式，有两种常采用的断定方式：期望支持度和概率频

3、繁。综述了不确定数据中频繁序列模式挖掘算法，给出了不确定数据中挖掘频繁序列模式的一般思路与方法。通过不确定序列模式挖掘算法的比较分析，联系到经典的序列模式挖掘理论框架，得知模式增长框架比候选集生成框架更具扩展性。其中在对不确定数据序列频繁性的判断上概率频繁性优于期望支持度，同时在计算概率频繁上分而治之策略相对动态规划策略开销少些。对于不确定数据的频繁序列模式挖掘，会导致可能频繁模式数量的指数级出现，其中有些无用的挖掘结果，引起频繁序列的冗余。针对上述不足，提出了可能频繁闭序列模式(pfcsp)的定义，以及一种基于不确定数据的可能

4、频繁闭序列挖掘算法U-FCSM。此算法中，基于一种元组不确定数据模型，采取分而治之的策略去计算序列的概率频繁性，应用BIDE算法的闭序列思想判断可能频繁序列是否是可能频繁闭序列模式。为了减少搜索空间与避免冗余的计算，应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。关键词：不确定数据；概率频繁；频繁序列模式；数据挖掘；可能频繁闭序列模式；II硕士学位论文AbstractInrecentyears,uncertaindatahasbeenmorewidelyappreciated.Datauncert

5、aintyisinherentinmanyreal-worldapplications,suchassensordatamonitoring,environmentalsurveillance,mobiletrackingandlocation-basedservices,duetoenvironmentalfactors,devicelimitations,privacyissues,etc.Theprevalenceofuncertaindataanditoftenplaysakeyrole.Uncertaindatamin

6、ingalsobecameaveryimportantresearchtopicindatamining.Inthispaper,Itakethefrequentsequentialpatternminingalgorithmofuncertaindataasourresearchobject.Comparedtothedeterministicsequencedatabase,itismorecomplexthatminingsequentialpatternsinuncertainsequencedatabase,itusu

7、allyencountershugesearchspace.Duetothedifferencesbetweenthetwodatatypes,thosesequencialpatternminingmethodsbasedondeterministicdatawhichiswidelyusedinsequenceminingcannotbeusedtosolveuncertainsequencepatternminingproblemsdirectly.Thispaperanalyzesthemethodofminingseq

8、uentialpatternsinthedeterministicdata,respectivelybasedonthecandidategenerate-and-testapproachandpattern-growthapproach.Imakeresear