【作者】 王现君；

【导师】 姜保庆；

【作者基本信息】 河南大学 ， 计算机应用技术， 2008， 硕士

【摘要】 序列模式是数据挖掘研究中一个重要的研究课题,其主要研究目的是从大型时序数据库中发现事件之间存在的隐藏的、有趣的序列关系。经典序列模式挖掘算法大都致力于挖掘序列模式全集,其空间效率低。挖掘闭序列集合能在保持信息完备性的前提下,比挖掘序列模式全集更加精简有效。本文着重对此进行了研究,研究内容主要包括以下几个部分:1.深入研究了序列模式挖掘经典算法。主要对基于前缀投影数据库的无候选序列生成的算法(PrefixSpan,CloSpan)和基于位图的SPAM算法进行了研究。对这些算法做了定性分析,比较了算法的运行效率,总结了每种算法的优点及不足。2.在对闭序列模式经典算法CloSpan的研究基础上,参考SPAM算法所采用的数据结构,将序列数据库用位图来表示,设计了基于位图的闭序列模式挖掘算法CSPBB。该算法是一个深度优先算法,采用前缀投影方法,处理的对象是用位图表示的序列数据库。通过算法分析和实验比较可知:对于长序列模式数据,CSPBB算法在时间和空间开销上均优于CloSpan算法。3.参考多维序列模式挖掘算法UniSeq、HTSeq,设计了多维闭序列模式挖掘算法Mul_Clo_Seq。该算法基本思想是:分裂多维序列数据库,分别进行闭序列模式与频繁多维信息挖掘,然后将二者结合、剪枝,最终生成多维闭序列模式。通过算法分析和实验比较可知:Mul_Clo_Seq的算法效率优于UniSeq算法。更多还原

【Abstract】 Sequential patterns mining is one of the important research areas in data mining. Its primary goal is to discover previously unknown, interesting relationships among attributes from large databases. Most classic algorithms of sequential patterns mining which have been proposed are focused on mining the complete sets of frequent patterns, The performance of those algorithms’space efficiency is low. The mining of closed sequential not only provides the same information, but also is more compact and effective. The work of this dissertation aims at the problems mentioned above. Therefore, in this paper we put the emphasis on mining frequent itemset. The main research is as follows:1.Certain classic sequential pattern mining algorithms are thoroughly studied. Mainly study focus on the algorithms without the candidate sequential generated which based on the prefix projection database and the algorithms SPAM based on the bitmap. Qualitative analysis are made in this paper, deeply, we compared the efficiency of these algorithms and conclude the virtue and the shortage of each algorithm.2.Based on the CloSpan algorithm, the classic algorithm of closed sequential patterns and referred to the data structure which the algorithm SPAM adopted, we used Bitmap to denote the database, and designed the Closed sequential pattern mining algorithm CSPBB based on Bitmap, which is a Depth priority algorithm, it’s object is the sequence database denoted by bitmap and the prefix projection algorithm is adopted. Analysis and experimental Comparison shown that, the algorithm CSPBB is excelled than the algorithm CloSpan in the time and space costs.3.Referred to the Multi-dimensional sequential pattern mining algorithms UniSeq and HTSeq, we designed the multi-dimensional closed sequential pattern mining algorithm Mul_Clo_Seq. The main idea of this algorithm is splitting the multi-dimensional sequence database, and the closed sequential patterns and the frequent multi-dimensional information mining are made separately. Then combining the closed sequential patterns and the frequent multi-dimensional to generate the multi-dimensional candidate closed sequence pattern, at last ,candidate sequence pattern pruning are made, we get the multi-dimensional closed sequential patterns. Analysis and experimental Comparison shown that, the algorithm Mul_Clo_Seq is excelled than the algorithm UniSeq in the efficiency.更多还原