论文部分内容阅读
关联规则挖掘是数据挖掘领域中一个重要的研究问题，从1993年Agrawal等人提出至今，一直是学术界和产业界广泛关注的热点。随着生物数据的快速增长，生物信息学已成为关联规则挖掘最富有机遇与挑战性的应用领域之一。本文围绕关联规则挖掘问题，对关联规则挖掘算法及其并行化、以及关联规则挖掘在基因表达数据中的应用展开了较全面和深入的研究，其主要内容和贡献包括：（1）基于FP-tree的最大频繁模式挖掘算法研究由于最大频繁模式搜索空间是项目数的指数级，所以修剪策略在最大频繁模式挖掘算法中一直是一个非常重要的技术。本文在分析研究了前人提出的最大频繁模式挖掘算法FPmax*基础上，使用本文提出的完全子集修剪和起始项目集修剪策略，提出了进一步优化的改进算法FPmax**。实例分析表明，这两项修剪技术可进一步减少计算开销，提高原FPmax*算法的性能。（2）基于FP-tree的频繁闭合模式挖掘并行算法研究由于在频繁闭合模式挖掘过程中，除了判断模式的频繁性外，还必须判断模式的闭合性，所以，频繁闭合模式挖掘的并行化相比频繁模式挖掘的并行化难度更大。本文在研究了共享存储结构和分布式存储结构下的频繁模式挖掘与最大频繁模式挖掘并行算法的基础上，明确提出了共享存储结构下的频繁闭合模式挖掘并行算法SL-FP和SP-FP算法，以及分布式存储结构下的频繁闭合模式挖掘并行算法DL-FP和DP-FP算法。理论分析表明，SL-FP算法与DP-FP算法具有处理器之间同步较少，并行度更高，I／O与通信开销较小以及良好的负载平衡。（3）基于超链接结构的自底向上频繁闭合模式挖掘算法研究针对已有面向基因表达数据集的频繁闭合模式挖掘算法多次扫描数据集转置表带来巨大开销的缺陷，本文提出了基于超链接结构的频繁闭合模式挖掘算法HTclose。理论分析表明，该算法的时间和空间性能比反复扫描转置表的算法有较大的提高；在真实数据集上的实验结果表明，该算法普遍快于反复扫描转置表的算法，最高达1个数量级以上。（4）基于形式概念分析的自顶向下频繁闭合模式挖掘算法研究针对已有面向基因表达数据集的自底向上频繁闭合模式算法无法充分修剪空间可能遭遇计算开销过大的问题，本文提出了通过转换搜索空间自顶向下和直接自顶向下搜索频繁闭合模式两种策略，并设计了相应的TPclose和TP+close算法。理论上证明了这两个算法的正确性；在真实数据集上的实验结果表明，一般情况下，它们具有良好的性能和较好的可扩展性，比已有的自底向上频繁闭合模式挖掘算法最高快2个数量级以上。