序列模式发现中关键问题的研究与实现

《序列模式发现中关键问题的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥工业大学硕士学位论文序列模式发现中关键问题的研究与实现姓名：孙莹申请学位级别：硕士专业：计算机应用技术指导教师：胡学钢20050401序列模式发现中关键问题的研究与实现摘要数据库知识发现(KnowledgeDiscoveryinDatabases，简称KDD)是当前涉及人工智能和数据库等学科的一门相当活跃的研究领域，序列模式发现是其中的一个重要研究方向。当前序列模式发现研究存在以下三个主要问题：①传统的序列模式发现算法(如AprioriAll算法等)需要多次扫描数据库，因而时间开销较大：②传统的序列模式发现期望挖掘出所有的频繁序列，整个过程缺乏针对性，时问代价高，结果数量巨

2、大且难以理解；③在实际应用中，最小支持度的设置是一个敏感问题。本文针对这三个问题进行了研究。主要工作如下：传统算法需要多次扫描数据库，因而时间开销较大。基于概念格扩展模型挖掘序列模式可以较好地提高时间性能。概念格扩展模型(ECL)适用于挖掘包括序列模式在内的各种知识。依据序列模式发现的特点和阈值，对ECL进行剪枝而得到的频繁概念格可以改善模式发现的时空性能。由于构造频繁概念格的时间性能是基于频繁概念格进行序列模式发现的关键，因此，本文提出了一种逐层构造频繁概念格的算法FL．Chein，仅需扫描数据库一次。在此基础上，实现了基于频繁概念格的序列模式发现算法SECLSP。传统的序列

3、模式挖掘发现所有的频繁序列，整个过程缺少针对性，时间代价高，结果数量巨大且难以理解。在序列模式发现中引入闭合模式概念，可以在信息不丢失的情况下减少冗余序列，大大降低结果的规模。本文抛弃了传统的升维的挖掘思想，从最长的序列模式开始挖掘，并采用了一定的优化策略，提出了一种有效的闭合序列发现算法Multi—passCS。top—k闭合模式是闭合模式的进一步扩展，而挖掘top．k闭合序列模式，可以解决传统序列模式挖掘存在的第三个难题一一最小支持度设置敏感问题。基于Multi—passCS算法的思想，本文提出了一种快速的top．k闭合序列模式发现算法TKCS。基于上述研究，实现了一个原型

4、系统。并从理论和实验上证明了所提出的算法对于解决上述三个问题具有一定的优越性。关键词：知识发现；频繁模式：序列模式；概念格；闭合模式TheResearchandImplementationofCrucialProblemsinSequentialPatternMiningABSTRACTKnowledgediscoveryindatabases(KDD)isarapidlyemergingresearchfieldrelevanttoartificialintelligenceanddatabasesystem．Thediscoveryofsequentialpattemsis

5、animportantfieldinKDD．Thereexiststhreemainproblemsinthediscoveryofsequentialpatterns：(i)traditionalsequentialpatternsminingalgorithmssuchasAprioriAUalgorithmneedtoscandatabasesformultipletimes，thereforethetimeperformanceofthesealgorithmsispoor．②Theaimoftraditionalsequentialpatternsminingisto

6、discoverallthefrequentsequences，Thewholeprocessislackofpeainence，timecostlyandoftengeneratesalargenumberofpattems．⑧Inthepracticaluse，settingmin_supportisasubtletask．Theworkofthisdissertationaimsattheproblemsmentionedabove．Themaincontextisasfollows：TraditionalsequentialpaRernsminingalgorithms

7、requiremultiplyscansofdatabase，sotheprocessistimecostly．TheExtendedmodelofConceptLaRice(ECL)issuitabletodiscovervariousknowledgeincludingsequentialpatterns．Consideringthecharactersofthesequentialpatternsmining，FequentConceptLattice(FCL)builtthrough