文档介绍：工学硕士学位论文
基于时间间隔的事件序列频繁模式挖掘算
法研究
RESEARCH ON ALGORITHM OF MINING
FREQUENT PATTERNS BASED ON TEMPORAL
INTERVALS
刘亚男
哈尔滨工业大学
2011 年 12 月
国内图书分类号: 学校代码:10213
国际图书分类号: 密级:公开
工学硕士学位论文
基于时间间隔的事件序列频繁模式挖掘算
法研究
硕士研究生: 刘亚男
导师: 张春慨副教授
申请学位: 工学硕士
学科: 计算机科学与技术
所在单位: 深圳研究生院
答辩日期: 2011 年 12 月
授予学位单位: 哈尔滨工业大学
Classified Index:
:
Thesis for the Master Degree of Engineering
RESEARCH ON ALGORITHM OF MINING
FREQUENT PATTERNS BASED ON TEMPORAL
INTERVALS
Candidate: Yanan Liu
Supervisor: Associate Prof. Chunkai Zhang
Academic Degree Applied for: Master of Engineering
Specialty: Computer Science & Technology
Affiliation: Shenzhen Graduate School
Date of Defence: Dec, 2011
Degree-Conferring-Institution: Harbin Institute of Technology
哈尔滨工业大学工学硕士学位论文
摘要
现存的序列模式挖掘算法多是基于瞬时事件的,然而在现实世界中很多事件
都是发生在一段时间内,例如语言分析,网络检测等,时间间隔事件序列频繁模
式挖掘在这些领域都有很重要的应用。本文的主要研究内容正是带有时间间隔的
事件序列频繁模式挖掘。
与传统的序列模式挖掘不同的是时间间隔事件之间的关系是很复杂的,这也
正是这种序列频繁模式挖掘的难点。到目前为止多数文章的关系定义都是基于
Allen 关系定义,本文中的事件关系定义也是基于 Allen 关系定义,并在此基础
上进行了去噪声处理,使之更适应现实场景。另外本文简单的描述了影响频繁模
式生成的各种兴趣度衡量,并且基于现实情况,本文采用支持度为兴趣度衡量。
而本文最主要的贡献是本文提出了一种基于“候选频繁模式生成—支持度计
算”的高效算法,并且在两个阶段都提出了改进策略。首先在候选频繁模式生成
阶段不同于传统的方法中利用 k 层频繁模式与 k 层频繁模式生成 k+1 层候选频繁
模式集,本文提出用 k 层频繁模式与 2 层频繁模式构成 k+1 层候选频繁模式集,
这样就能减少在合并两个频繁模式时的关于两个模式中间部分是否相等的比较
次数,这种策略在提高算法效率的同时也能够减少冗余候选频繁模式的生成。其
次,本文的算法维护一个 2-频繁模式集合,利用一定的策略来尽可能的减小用
于合并生成候选集的 2-频繁模式集,使得产生尽量少的候选频繁模式,提高算
法的效率。
在支持度计算阶段本文同样提出了两种改进策略。首先本文在构造候选频繁
模式集的同时构造了索引,指向需要遍历的客户序列,这能够有效的减小算法的
搜索空间,提高算法效率。其次不同于传统的挖掘算法中在计算支持度的时候多
次遍历数据库,本文提出了一种算法,当计算具有相同长度的候选频繁模式的支
持度时,只需遍历一次数据库。总之本文在支持度计算的过程中一方面减少遍历
数据库的次数,另一方面减少遍历数据库时的搜索空间。
最后,本文提出了仿真数据的生成。在此基础上本文进行了两个方面的实验,
一是本文提出了几个重要的参数对算法的影响,并且在实验中验证了提出的理论。
二是为了证明本文提出的算法的有效性,本文就算法的效率以及正确率两个方面
与枚举树算法和索引集算法进行了对比。
关键字:候选频繁模式;频繁模式;时间间隔事件;模式挖掘
-