面向数据流的关联规则挖掘精确度研究

论文摘要

当今时代是信息的时代是数字化的时代,随着通信、互联网的发展,社会各行各业存储的数据越来越庞大,在这种背景下,一种新的数据形式——数据流引起了计算机从业人员的关注。如何在海洋一样广阔的数据流中准确的挖掘有价值的信息成为了数据挖掘研究工作新的挑战。面向数据流的关联规则挖掘是数据挖掘的新形式,近些年来的研究热点,被广泛的应用于网络通信、设备维护、证券交易等领域,对于社会的生产和日常生活有着重要的意义。数据挖掘工作者对数据流的关联规则挖掘工作展开了大量的相关研究,对数据挖掘的思想、流程、算法提出了许多新的设计。然而这些方法大都把主要的研究工作放在了挖掘的过程、数据处理等方面,忽略了对于关联规则挖掘结果精确度的关注,同时在对挖掘过程的设计中,对于数据准确性的研究也比较有限。数据挖掘的目的是获得可信的、准确的、有价值的信息,由于在数据流环境下的挖掘只能够得到近似的挖掘结果,因此,挖掘结果的精确度将是评价挖掘的关键指标。本文围绕着提高挖掘结果精确度的目的,提出了面向数据流的关联规则挖掘的方法,在数据流的获取、处理以及信息的发现等挖掘流程的设计过程中,从处理细节入手,将提高挖掘精确度的思想贯穿其中。本文对数据流关联规则挖掘的工作主要分为三个部分的研究成果：数据获取部分、数据存储部分和数据挖掘部分,围绕着如何提高挖掘精确度,对每一个部分的设计进行了详细的描述。首先,在数据获取部分提出了使用滑动时间窗口模型获取数据,并按照每个窗口将数据流分割成为事务形式,这个模型既符合了数据流的特点,又满足了频繁项集挖掘对数据的要求。其次,数据存储模型由数据存储结构、数据更新算法和最大误差的选取三部分组成。通过对经典算法FP-growth算法中FP树的改进,本文提出了一个新的数据存储结构FP-Atree,这个存储结构符合了只能一遍读取数据的数据环境要求,节省了数据存储空间,简化了数据逻辑,压缩了存储体积。数据更新算法把整个数据存储时间划分为多个时间框,在时间框结束时对FP-Atree进行剪枝,删除支持度小于最大误差的项集,从而保证了有限的空间资源的到充分的利用,避免了因为数据流的无边界性而导致的存储数据的无限扩张。第三部分为最大误差的选取,研究中使用了多项式近似的策略,发现了最大误差与环境资源参数之间的关系,既有效地控制了空间资源,又尽量避免了有效信息的丢失,为提高挖掘结果精确度提供了保障。数据挖掘模型的主要意义在于提高了挖掘精确度,在这一模型中本文提出了基于滑动时间窗口的新阈值,最小支持度阈值S经过修正,每个项集都有适用于本身的阈值。这个模型保证了所有真实支持度大于S的项集都能成为频繁项集,减少了结果项集中非频繁项集的比例,提高了挖掘结果的精确度。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 本文的研究背景和理论意义
• 1.2 数据流关联规则挖掘的研究现状
• 1.3 主要研究工作和文章结构
• 第2章 数据流挖掘框架和滑动时间窗口模型
• 2.1 数据流挖掘框架
• 2.2 数据流截取要求分析
• 2.3 滑动时间窗口模型
• 第3章 基于FP-Atree的存储模型
• 3.1 数据存储和资源控制分析
• 3.2 数据存储结构
• 3.3 FP-Atree树挖掘算法
• 3.3.1 算法详述
• 3.3.2 Format算法
• 3.3.3 Ins2tree算法
• 3.3.4 FrePatMining算法
• 3.3.5 算法举例
• 3.4 数据的更新与剪枝
• 第4章 最大误差的选取和变动阈值
• 4.1 挖掘结果精度分析
• 4.2 最大误差的选取
• 4.2.1 了解挖掘环境
• 4.2.2 多项式拟合
• 4.2.3 边界确认
• 4.3 基于滑动时间窗口的新阈值
• 4.4 面向数据流的关联规则挖掘FPT算法
• 第5章 挖掘系统模型的实验与应用
• 5.1 实验环境
• 5.2 实验数据流
• 5.3 实验结果
• 5.3.1 实验1
• 5.3.2 实验2
• 第6章 总结与展望
• 6.1 本文工作总结
• 6.2 对下一步工作的展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 攻读学位期间参与科研项目情况
• 学位论文评阅及答辩情况表