文档介绍：工学硕士学位论文
DELAY-CFIM:基于滑动窗口的高速数据流闭
合频繁模式挖掘方法
DELAY-CFIM: A SLIDING WINDOW BASED
METHOD ON MINING CLOSED FREQUENT
ITEMSETS OVER HIGH-SPEED DATA STREAMS
张蕾
哈尔滨工业大学
2011 年 12 月
国内图书分类号: 学校代码:10213
国际图书分类号: 密级:公开
工学硕士学位论文
DELAY-CFIM:基于滑动窗口的高速数据流闭
合频繁模式挖掘方法
硕士研究生: 张蕾
导师: 张春慨副教授
申请学位: 工学硕士
学科: 计算机科学与技术
所在单位: 深圳研究生院
答辩日期: 2011 年 12 月
授予学位单位: 哈尔滨工业大学
Classified Index:
:
Thesis for the Master Degree of Engineering
DELAY-CFIM: A SLIDING WINDOW BASED
METHOD ON MINING CLOSED FREQUENT
ITEMSETS OVER HIGH-SPEED DATA STREAMS
Candidate: Lei Zhang
Supervisor: Associate Prof. Chunkai Zhang
Academic Degree Applied for: Master of Engineering
Specialty: Computer Science & Technology
Affiliation: Shenzhen Graduate School
Date of Defence: December, 2011
Degree-Conferring-Institution: Harbin Institute of Technology
Abstract
摘要
随着信息技术的发展,很多应用领域都产生了大量流数据,因此流数据挖掘
成为数据挖掘领域的热门研究课题。其中流数据闭合频繁模式挖掘是流数据挖掘
领域的一项关键技术,被广泛应用在商业决策,购物篮分析和网络数据分析等多
个领域。流数据闭合频繁模式挖掘要求在快速到达的数据流中高速的存储有用的
数据信息,在客户有需求的时候进行闭合频繁模式输出,以指导客户做出决策。
但是现存的流数据闭合频繁模式挖掘方法存在在线处理时间过长的问题,从而不
能处理数据高速产生的情况。
本文深入分析了现有的流数据闭合频繁模式方法,针对现有方法存在的在线
处理时间较长的问题提出了一种新的解决方法 DELAY-CFIM,将流数据闭合频繁
模式挖掘分成数据压缩与闭合频繁模式挖掘两个步骤。首先,在数据产生时对其
进行简单的统计和压缩。然后, 在客户提出查询要求时,再进行闭合频繁模式挖
掘,从而能够处理数据高速产生的情况。在客户查询不是很密集的情况下可以产
生很好的结果。
本文的主要研究内容如下:
(1) 本文提出了一种新的基于滑动窗口概要数据存储结构 OTT。OTT 在数据
到达的时候被用来存储数据频度信息,达到数据统计与压缩的作用,使得在客户
提出查询请求时可以缩短闭合模式挖掘所需时间。
(2) 本文提出了一种新的闭合树模型 CFIT。CFIT 结合了链表与树,将闭合模
式进行存储,在有需要的时候对频繁模式进行检测以判断它的闭合性,CFIT的特
殊存储结构能够大大加快闭合模式检测的速度。
(3) 本文提出了一种基于 OTT 和 CFIT 的闭合频繁模式挖掘方法 DELAY-
CFIM。首先在 OTT 上通过后缀重新插入的方法产生频繁模式,再通过 CFIT 对
这些模式进行闭合模式检测。从而在客户提出查询请求时正确输出闭合频繁模
式。
(4) 本文在上诉提出的闭合频繁模式挖掘方法的基础上提出了四种剪枝策略,
既减少了 OTT 上产生的潜在闭合频繁模式数量又缩短了闭合检测所需时间,从而
大大减少了算法运行时间。
本文最后将所提出的算法 DELAY-CFIM 与经典流数据闭合频繁模式挖掘算法
CFI-Stream 进行了比较。结果显示在客户查询不是很密集的情况下,本文算法可
- I-
Abstract