数据流频繁集挖掘算法研究.doc

文档介绍：电子科技大学
UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA
工程硕士学位论文
ENGINEERING MASTER DISSERTATION
论文题目: 数据流频繁集挖掘算法研究
工程领域: 软件工程
指导教师: 卢国明教授
作者姓名: 赵传冰
班学号: 200892303008
分类号密级
UDC
学位论文
数据流频繁集挖掘算法研究
赵传冰
指导教师姓名卢国明教授

(职务、职称、学位、单位名称及地址)
申请学位级别工程硕士专业名称软件工程
论文提交日期论文答辩日期
学位授予单位和日期
答辩委员会主席
评阅人
年月日
注1注明《国际十进分类法UDC》的类
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。
签名: 日期: 年月日
关于论文使用授权的说明
本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。
(保密的学位论文在解密后应遵守此规定)
签名: 导师签名:
日期: 年月日
摘要
频繁集挖掘是数据挖掘领域的一个重要的研究方向,它的研究成果已被广泛应用到关联规则挖掘、关联分类和序列模式挖掘等许多应用中。在过去的十几年间研究人员对频繁集挖掘进行了深入广泛的研究,取得了一系列研究成果。
近年来在高速网络、事务日志、金融和传感器网络等领域出现了一种称为数据流的新的数据类型。它具有与普通数据集截然不同的特点,如持续不断产生数据、数据产生速度快、数据太多以致只能顺序访问一遍数据、无法控制数据产生的次序等。针对数据流的数据挖掘已经成为研究的热点。但因为现存的绝大多数频繁集挖掘算法面向保存在持久存储介质中的数据并且在算法运行过程中需要多次访问数据,它们无法被直接应用到数据流领域。
本文详细讨论了基于数据流的频繁集挖掘,提出了一系列高性能、低空间需求和高准确度的单遍扫描算法:
(a) 结合频繁项挖掘算法,提出了两个基于数据流中观察到的所有数据的频繁集挖掘算法SinScanFISM算法和MulScanFISM 算法。SinScanFISM算法逐个处理新产生的事务,而MulScanFISM算法则批量处理新产生的事务。
(b)频繁集挖掘算法往往会产生大量的频繁模式,这不仅会影响算法的性能,也会影响对算法结果的理解,解决方法之一就是利用频繁集的无损简化表达方式。结合频繁集的无损简化表达方式提出了两个代表性的算法,其中 BorIFISM算法基于边界集表达方式,CloIFISM 算法基于闭合集表达方式。
通过实验也表明这些算法在挖掘各种规模与特性的数据集时具有较高的效率与可伸缩性。
关键词:数据挖掘,SinScanFISM算法,MulScanFISM 算法,BorIFISM算法,CloIFISM 算法
ABSTRACT
Frequent itemset mining is one of the important subjects of data mining, which has been studied extensively in the last decade. It is used by many data mining applications, such as the discovery of association rules, correlations, sequential rules and episodes.
Recently, there has been much interest in data arriving in the form of continuous streams, which is often referred to data streams. Data streams arise in several application domains like high-working, transaction logs, finance and works. Data streams putational characteristics, such as unkn