论文摘要
计算机科学是一门与信息相关联的学科,信息在计算机中以数据的形式存储、传播、使用。大部分的计算机数据存储在数据库中,因此数据库管理与应用技术一直是学术界研究的热点之一。目前,数据挖掘与知识发现作为数据库应用的一个分支受到了越来越多的关注,原因是随着大量的数据源源不断地汇入数据库中,面对着海量数据,用户往往只需要找出满足其要求的特定内容。从关系数据库中挖掘出满足条件的项的集合,简称项集挖掘,是数据挖掘与知识发现领域的基础性问题。主要原因：一是,按照不同的条件设定,可以定义各种各样的项集挖掘问题,这些问题又具有相关性,针对一个问题开发的新方法可能移植用于解决其他问题；再者,挖掘出的项集不仅可以直接使用,而且也可以作为中间物提供给其他应用,如关联规则挖掘、分类、聚类等等。项集挖掘问题的特点是定义简单、解决方法多样,但是,此类问题的难点是搜索空间太大,对于一个包含n个项的数据库,有2n个可能解。因此,研究者非常重视挖掘算法的效率,通俗地说,即算法是否足够地快。本论文研究频繁项集挖掘问题及高可用项集挖掘问题。前者通过项集在数据库记录中的出现次数来定义频繁性；后者通过附加在项上的权值来定义可用性。这两个问题的输入是一个数据库和一个最小频繁/可用阈值,要求找出所有超过阈值的项集。本论文以这两个问题为中心,以提升解决这两个问题算法的效率为主线,重点阐述了四个最新的算法,主要内容概括如下：·通过分析经典的频繁项集挖掘算法FP-growth,识别了影响此算法性能的三个重要因素,即遍历花费、计数花费、构造花费。为了减少这些花费,提出了BFP-growth算法,其核心思想是批处理。BFP-growth能够大幅度地减少FP-growth的遍历和构造花费,而且,相对于FPgrowth*（目前最快的FP-growth变种,减少了遍历花费但增加了计数花费）,BFP-growth的计数花费保持不变。实验结果显示BFP-growth要快于FP-growth及FPgrowth*。·提出了用于频繁项集挖掘的NS算法。NS算法采用结点集合作为挖掘过程中的核心结构。FP-growth使用的数据结构是前缀树,另一重要算法Eclat采用记录列表结构。前缀树具有压缩性,记录列表具有连续性,而结点集合结构兼具这两个优点。通过实验,NS算法被证明要快于FPgrowth*、dEclat（最快的Eclat变种）、及LCMv2（公开源码的最快频繁项集挖掘算法）。·目前高可用项集挖掘算法具有相似的流程：先生成候选项集,再计算精确有用性值过滤出高可用项集。这些算法的问题是：多数情况下,大部分的候选者不是高可用项集而最终被丢弃,这造成了计算时间存储空间的巨大浪费。为解决这个问题,提出了HUI-Miner算法,此算法采用新颖的有用性列表作为数据结构。HUI-Miner在挖掘过程中不产生候选项集。因此,不论是运行时间还是内存耗费,HUI-Miner均优于最新的算法（例如UP-Growth+）几个数量级。·同时,我们关注了先前研究忽视的一个问题：精确有用性值的计算。在实际的挖掘任务中,先前算法的精确有用性值计算时间要远大于候选项集生成时间。然而,已有的研究几乎全部致力于减少候选生成时间。借助于一棵存储所有候选项集的前缀树,本论文提出的FIA算法能够快速地计算精确有用性值。在实验中,集成FIA的UP-Growth+算法的性能已经能和HUI-Miner算法相匹敌了。
论文目录
摘要ABSTRACT第一章 引言1.1 项集：数据挖掘研究领域的焦点之一1.2 频繁及高可用项集挖掘问题的研究现状1.3 本论文主要内容与组织结构第二章 频繁项集挖掘问题2.1 概述2.1.1 问题形式化定义2.1.2 搜索空间与方法2.2 基础频繁项集挖掘算法介绍2.2.1 经典的候选生成Apriori算法2.2.2 以垂直视角处理数据库的Eclat算法2.2.3 基于前缀树结构的FP-growth算法2.3 性能测试的软硬件环境2.3.1 数据库描述2.3.2 参照算法介绍2.3.3 其他软硬件设施2.4 实验一：三种基础算法的性能测试2.4.1 实验结果2.4.2 性能评价第三章 BFP-growth：一种快速的模式增长算法3.1 经典模式增长算法的性能分析3.1.1 影响FP-growth性能的三个因素*'>3.1.2 ICDM最佳算法：FPgrowth*3.2 批量模式增长算法：BFP-growth3.2.1 性能提升的途径3.2.2 核心步骤：两次前缀树遍历3.2.3 算法伪代码3.3 BFP-growth算法的性能分析3.3.1 更少的遍历花费3.3.2 FP-array技术应该集成在BFP-growth中吗3.3.3 无修饰的前缀树结构3.4 实验二：BFP-growth的性能测试及讨论*与基础算法的对比'>3.4.1 BFP-growth及FPgrowth*与基础算法的对比3.4.2 实验结果讨论3.5 小结第四章 基于结点集合结构的NS算法4.1 Eclat及FP-growth算法的优缺点4.2 结点集合结构（Node-set）4.2.1 条件结点4.2.2 结点拓扑序号4.2.3 使用结点集合结构表示前缀树4.3 NS算法4.3.1 映射前缀树到结点集合结构4.3.2 从结点集合结构中挖掘频繁项集4.3.3 一个例子4.3.4 NS算法的原子操作4.4 实验三：NS算法与其他快速挖掘算法的性能对比4.4.1 实验结果4.4.2 结果讨论：NS算法的性能优势4.5 小结第五章 频繁项集挖掘算法的内存耗费5.1 BFP-growth算法内存使用情况分析5.2 NS算法内存使用情况分析5.3 实验四：快速挖掘算法的内存耗费第六章 高可用项集挖掘问题6.1 从频繁项集到高可用项集6.2 问题的形式化定义6.3 已有挖掘算法概述第七章 非候选生成的高可用项集挖掘算法7.1 项集有用性列表结构7.1.1 初始有用性列表7.1.2 2-项集的有用性列表7.1.3 k-项集有用性列表（k≥3）7.2 HUI-Miner算法7.2.1 剪枝策略7.2.2 算法伪代码7.3 HUI-Miner算法的实现细节7.3.1 有用性列表表头7.3.2 重新标注tid7.3.3 交易权重有用性增加的顺序7.4 实验五：HUI-Miner性能测试7.4.1 实验设置7.4.2 HUI-Miner及对比算法的运行时间7.4.3 HUI-Miner及对比算法的内存耗费7.4.4 项处理顺序对HUI-Miner性能的影响7.4.5 可扩展性7.4.6 实验结果讨论7.5 小结第八章 从候选集合中快速识别高可用项集8.1 先前算法的性能瓶颈8.2 基本识别算法（BIA）8.3 基于候选树的快速识别算法（FIA）8.3.1 候选树结构8.3.2 快速识别算法8.4 算法分析：BIA与FIA8.5 实验六：BIA与FIA的性能对比8.5.1 高可用项集识别时间8.5.2 候选项集生成时间8.5.3 内存耗费8.5.4 实验结果分析8.6 实验七：FIA-UP-Growth+和HUI-Miner的性能对比8.6.1 运行时间&内存耗费8.6.2 实验结果分析8.7 小结第九章 总结与展望参考文献攻博期间研究经历和科研成果致谢
相关论文文献
标签：数据挖掘论文; 算法论文; 频繁项集论文; 高可用项集论文;
