论文部分内容阅读
序列模式挖掘是指挖掘相对于时间或其他模式出现频率高的模式,是数据挖掘的一个重要分支。在交易数据分析,病症分析,Web日志分析,天气预报等领域具有广泛的应用前景。
本文选择序列模式作为研究对象,系统的分析了当前序列模式挖掘的现状;针对一般序列模式算法、交互式序列模式、增量式序列模式三个方面展开研究和实验。主要研究工作和成果有:
1、分析了序列模式国内外的研究现状。从序列模式挖掘的基本方法和序列模式挖掘现有的模型两个角度对相关文献进行归类分析。
2、提出了一种基于CTID的改进算法SPM(Sequential Patterns Mining)。该算法利用时序连接,将时序情况分为时序前缀和时序后缀两种情况进行计算,可以得到更多有效序列;并且在剪枝过程中充分利用CTID表的特点,简化了剪枝步骤,从而提高了算法效率。
3、提出了一种基于投影数据库的交互式序列模式挖掘算法FISP (Fast Interactive Sequential Patterns Mining )。在实际挖掘的过程中,用户通常会指定不同的最小支持度,以得到满意的序列模式。所以整个挖掘过程是一个迭代和交互的过程。如果支持度改变时,重新挖掘显然是低效的。FISP利用前次挖掘得到的序列,来缩减本次挖掘的投影数据库;并设置了一个全局阈值来减少整个交互过程的时间和空间消耗。
4、 提出了基于投影数据库的增量式更新算法ISMP (Incremental Sequential Patterns Mining Based on Projected Database)。数据库往往是随时间动态更新的。更新后,一部分旧的序列模式可能会不再满足最小支持度,并且会有新的序列模式出现。在处理具有大量数据的大型数据库时,对整个数据库重新执行一般的序列模式挖掘算法显然是低效的,因此需要有效的算法来更新、维护和管理已经发现的知识,以反映这种交易数据库的动态更新。ISMP用间接拼接更新已经得到序列,用增量数据库来减小投影数据库,提高了算法效率。并且考虑了数据库减小时的序列模式更新。当增量数据库较大时,算法效率更高。
通过实验对上述三种算法进行了验证,结果表明算法是有效可行的。