序列模式的增量式挖掘算法研究

摘要

随着信息技术的发展,许多领域积累了大量的数据,迫切需要一种技术从中及时发现有用的知识,提高信息利用率,KDD技术应运而生.通常KDD包括数据准备、数据挖掘、解释与评价等步骤.其中数据挖掘是KDD的核心环节.目前,数据挖掘的研究主要集中在分类、关联规则、序列模式挖掘等方面.序列模式挖掘作为数据挖掘领域的研究热点之一,其任务是从序列数据库中挖掘出最大频繁序列供决策者做出决策.目前的挖掘算法主要分为两种,即一般的挖掘算法和增量式的挖掘算法.一般的挖掘算法如AprioriAll等以关联规则挖掘的相关算法为基础,当大型数据库需要加入新的数据时需要重新挖掘,降低了挖掘的效率,不能满足要求.于是序列模式的增量式挖掘算法被提出,现有的算法有MFS、ISM、ISE、IUS等,它们在原有数据库挖掘结果的基础上,往往只需遍历新增加的数据,或者只需较少次数的遍历原有数据库就能挖掘出新的序列模式,提高了挖掘的效率,其中IUS算法是最为先进的算法.该文通过对IUS及其它算法的研究,发现这些算法往往都只考虑了向数据库中增加数据的情况,而很少有考虑大型数据库也有删除数据的情况,这是问题一.而且,这些算法都是基于

目录

文摘

英文文摘

第1章 前言

1.1 KDD(数据库中的知识发现KNOWLEDGE DISCOVERY IN DATABASES)的产生

1.2 KDD的定义

1.2.1 KDD的步骤

1.2.2 KDD与DM的界定

1.3 数据挖掘技术

1.3.1 数据挖掘的任务

1.3.2数据挖掘的方法

1.3.3 数据挖掘的主要应用

1.4 序列模式挖掘技术

1.4.1 一般的序列模式挖掘算法

1.4.2 增量式序列模式挖掘算法

1.5 IUS算法

1.6 本文的主要工作

1.7 论文的组织

第2章 序列模式挖掘及其算法

2.1 序列模式挖掘的产生

2.2 序列模式挖掘中的定义

2.3 序列模式挖掘的应用及研究现状

2.4 序列模式与关联规则的异同点

2.4.1 关联规则简介

2.4.2相同点

2.4.3不同点

2.5 小结

第3章 序列模式的一般挖掘算法

3.1 与序列模式挖掘相关的技术

3.2 AprioriAll算法

3.3 GSP算法

3.3.1 ApriorAll算法的局限之处

3.3.2 GSP算法中的包含定理

3.3.3 GSP算法

3.4 SPADE算法

3.4.1 格分解-基于后缀的类。

3.4.2构建父类。

3.4.3 磁盘扫描。

3.4.4 临时id列表的交集。

3.5 FreeSpan算法

3.6 PrefixSpan算法

3.6.1 PrefixSpan中的一些定义

3.6.2 PrefixSpan算法的步骤

3.6.3 PrefixSpan算法

3.6.4对PrefixSpan算法的分析

3.7 增量式序列模式挖掘算法

3.8 小结

第4章 序列模式的增量式挖掘算法

4.1 问题的提出

4.2 MFS算法

4.2.1 MFS算法的步骤及其伪代码

4.2.2 MGen函数

4.3 ISE算法

4.3.1 ISE算法的主要思想

4.3.2 ISE算法的步骤

4.3.3 ISE算法的伪代码

4.4 ISM算法

4.4.1 ISM算法中的一些新的定义：

4.4.2 ISM算法的步骤

4.4.3 ISM算法的伪代码

4.5 IUS算法

4.6 其它增量式挖掘算法

4.6.1 GSP+和 MFS+

4.6.2 KISP

4.7 小结

第5章 IUS算法

5.1 以前各种增量式挖掘算法的不足

5.2 IUS算法中定义

5.3 IUS算法的挖掘过程

5.3.1 IUS算法的挖掘过程

5.3.2 IUS算法的伪代码

5.4 IUS算法的实验结果

5.5 对IUS算法的后续研究

5.6 对序列模式挖掘算法的总结和比较

5.7 小结

第6章 对IUS算法的改进

6.1 增量式挖掘算法的设计原则

6.2 IUS算法中存在的问题及改正方案

6.3 对IUS算法的改进

6.3.1 问题的产生

6.3.2 考虑数据删除的情况

6.3.3 最小支持度改变的情况

6.4 对改进方案的分析

6.5 小结

第7章 总结和展望

7.1 对本文的总结

7.2 对未来的展望

作者研究生期间发表论文

参考文献

致 谢