基于树结构的精简序列模式挖掘算法研究

《基于树结构的精简序列模式挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、工学硕士学位论文基于树结构的精简序列模式挖掘算法研究燕山大学2010年10月万方数据国内图书分类号：TP311.131国际图书分类号：621.3工学硕士学位论文基于树结构的精简序列模式挖掘算法研究万方数据硕士研究生：导师：申请学位级别：学科、专业：所在单位：授予学位单位：解玉洁任家东教授工学硕士计算机软件与理论信息科学与工程学院燕山大学ClassifiedIndex:TP311.131U.D.C.:621.3DissertationfortheMasterDegreeinEngineeringRESEARCHONCONDENSEDSEQUE

2、NTIALPATTERNMININGBASEDONTREESTRUCTURE万方数据Candidate:Supervisor:AcademicDegreeAppliedfor:Speciality:University:YujieXieProf.RenJiadongMasterofEngineeringComputerSoftwareandTheoryYanshanUniversity燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《基于树结构的精简序列模式挖掘算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独

3、立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本课题的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字日期：年月日燕山大学硕士学位论文使用授权书《基于树结构的精简序列模式挖掘算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允

4、许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。保密□，在年解密后适用本授权书。本学位论文属于不保密□。（请在以上相应方框内打“√”）作者签名：导师签名：日期：日期：年年月月日日万方数据摘要现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列模式集，然而在很多实际应用中，用户更希望找出感兴趣的、更简洁的模式，而不是所有的模式。本文主要研究了如何挖掘精简序列模式，如何有效的增量挖掘精简序列模式，以及如何精确的挖掘重复间隔精简序列模式等问题，这些问题的研究在顾客购物分析

5、，交易分析，Web页面的访问模式预测，DNA序列分析，软件行为模式分析中具有重要的意义。本文首先设计了一种基于改进前缀树的最大序列模式挖掘算法CSMS，算法利用纵向、横向结合搜索位置信息表的序列扩展匹配方法找到潜在最大序列模式，同时，把每个找到的潜在最大序列模式存储在改进的前缀树PStree中，最后通过对PStree进行剪枝，得到由最大序列模式组成的前缀树MPStree。该算法具有较好的时间效率和扩展性。其次，提出了一种基于重复链接WAP-Tree结构的闭合重复间隔序列模式挖掘算法MRCGP，算法首先为频繁1项集构建一个位置信息表，然后通过搜索

6、位置信息表找到所有由不同项组成的2序列模式，最后构建一个重复链接WAP-Tree维护所有的频繁项集，通过逐步挖掘已存在模式的投影树，得到所有的闭合重复间隔序列模式集。该算法的性能优于CloGSgrow。最后，设计了一个面向软件漏洞特征提取的闭合序列模式挖掘算法MSPT和更新算法UMSPT。算法MSPT首先搜索半频繁和频繁2模式，然后为半频繁和频繁项构建一个漏洞序列树，利用投影技术，逐步找到半闭合和闭合序列模式。算法UMSPT插入新的序列到漏洞序列树，搜索树中新插入的分支找到新序列中的闭合和半闭合模式。最后通过检查已存在模式的包含关系以及支持度信

7、息得到更新数据库中的所有半闭合和闭合序列模式集。本文使用现实数据集进行挖掘，通过实验对本文所提出的CSMS算法、I万方数据MRCGP算法、MSPT算法以及UMSPT算法进行验证。关键词位置信息表；序列扩展匹配；WAP-Tree；投影树；漏洞特征提取II万方数据AbstractTheexistingsequentialpatternminingalgorithmcanefficientlyminethecompletesetofsequentialpatterninalargedatabase.However，inmanyapplication,

8、theusermaywanttofindthemoresuccinctpatterns,ratherthanallofthepatterns.Thep