论文部分内容阅读
近年来,数据挖掘相关的研究领域越来越热门,除了关联规则的挖掘外,也有学者致力于探讨时间因子的关联规则,大致可区分为消费者购买行为分析、网页浏览分析,以及时间趋势分析等。而在探讨消费者购买行为的时间序列,多借着候选序列的产生及验证,以渐进的过程来产生频繁模式,然而验证的过程必须重复扫描数据库,也因此造成系统沉重的负担而导致效率不佳。序列模式挖掘作为数据挖掘领域的研究热点之一,其任务是从序列数据库中挖掘出最大频繁序列供决策者做出决策。它主要用于捕获与时间相关的典型行为,即捕获那些重复出现从而可用于决策的行为。假如有一个序列数据库,其中每个序列是一个按照事务时间排序的事务集合的列表,每个事务集合是一个项的集合,那么序列模式挖掘就是要找出满足用户给定的最小支持度的所有序列模式。挖掘系统的效率问题是数据挖掘研究的重要内容之一。经典的序列模式挖掘算法AprioriAll在空间和时间的复杂性上,有着难以避免的局限性,本文引入了一种基于邻接矩阵的序列模式挖掘算法,在中间过程中不需要产生候选项的算法,从而避免了反复扫描数据库时在时间上的开销。但是,基于邻接矩阵算法在数据库中的项目较多,并且含有大量事务时,内存空间的开销很大,当内存不能装入所有模式映射信息时,算法将难以有效地工作。本文提出了一种新的序列模式挖掘算法TTSP。在此算法中,我们采用了一种我们称之为“序列线索树”(sequences thread tree)的数据结构。在建构算法的过程中,我们详细地讨论了算法的每个步骤,并且在几个不同尺寸的合成数据库上对算法的挖掘功能做了实验,验证了TTSP算法的有效性,并分析了算法的关键参数对算法性能的影响。通过对TTSP和FPAM进行对比试验,验证了TTSP的优越性。实验结果同时还表明,采用此算法的增量挖掘功能比其它正常挖掘算法在效率上有了很大的提高;同时,由于此算法的执行成效与事务数据库尺寸呈现出一种线性关系,因此认为该算法具有较好的可伸缩性。