基于位表的关联规则挖掘及关联分类研究

摘要

随着人们利用信息技术生产和搜集数据的能力大幅度提高，数据资料的规模急速膨胀。如何快速有效的从海量数据中发现隐藏的、预先未知的信息和知识显得尤为重要，数据挖掘是解决这一问题的有力工具。关联规则(Association Rules)获取是数据挖掘研究的一个重要领域，从某种意义上来讲，关联规则挖掘就是数据挖掘的本质。近年来相关的研究与应用一直占有重要的比例并得到了迅速发展。研究如何快速有效的从海量数据库中挖掘蕴含其中的关联规则，并将挖掘得到的关联规则合理利用，具有十分重要的理论和实际意义。本文在分析现有挖掘算法中存在问题的基础上，提出基于位表的完全频繁项集和事务间频繁闭项集的挖掘算法，并进一步研究关联规则在分类问题中的应用，利用其解决遥感影像分类问题。本文的研究工作可概括为如下三个方面的内容： 1、研究事务内完全频繁项集的快速挖掘算法。现有的完全频繁项集挖掘算法多基于Apriori算法，称为Apriori类算法。其在生成候选集须逐个比较两个项集的前n-1项，并且在计算支持度需对全部或部分数据库进行逐条扫描，占用大量的计算时间和I/O操作，成为此类算法的主要瓶颈。针对以上问题，本文首先提出了位表(BitTable)数据结构及其相应的二进制操作。利用其对事务数据库进行压缩，同时通过二进制“与”、“或”操作快速计算候选项集的支持度，改善了低效率的数据库扫描操作；利用其对候选项集和频繁项集进行横向压缩，可直接生成候选项集，避免了逐项比较的复杂操作。该数据结构及其操作可以直接应用于现有的Apriori类算法中，有效地改善此类算法的效率问题。在位表数据结构的基础上，本文进一步提出了基于位表的关联规则挖掘算法BitTableFI。对常用数据集的仿真试验表明了该算法的有效性。 2、研究事务间频繁闭项集及其快速挖掘算法。相对于事务内频繁项集，事务间频繁项集能够有效的揭示各属性在不同时刻的关联性，是事务内频繁项集的扩展。然而事务间频繁项集的数量随滑动时间窗口的增大而迅速增加，造成挖掘效率降低，利用闭项集来表示事物间频繁项集能够在不丢失信息的情况下有效的减少项集的数量。本文通过分析事务内频繁闭项集和事务间频繁闭项的内在关系，提出了一种利用事务内频繁闭项集生成事务间频繁闭项集的算法。算法采用分割和条件数据库技术，有效的避免了生成庞大的扩展事务数据库，利用扩展的位表结构压缩事务从而提高支持度的计算效率。此外，采用动态排序和哈希技术极大地减少了频繁闭项集的测试次数。该算法为挖掘事物间频繁闭项集提供了一种有效而快速的算法。 3、研究模糊关联分类算法，并利用其解决遥感影像分类问题。关联分类将挖掘获取的频繁项集应用于解决分类问题，将关联规则的挖掘和应用问题紧密结合。将模糊方法引入到关联分类问题中，能够较好的解决规则的“尖锐边界“问题。然而，现有的模糊关联分类算法多采用固定模糊隶属度函数对连续型属性进行模糊划分，没有考虑数据本身的特性。基于此，本章提出一种基于自适应区间划分的模糊关联分类算法—FARC(Fuzzy association rules classification)，利用模糊c均值聚类算法根据数据本身的特点自适应地建立模糊区间，并在挖掘模糊关联规则时采用了新的剪枝策略，极大地减少了候选集的数量。新的规则权重度量方法能够更好的利用多模糊关联规则进行分类。对UC Irvine Machine Learning Repository测试数据的实验表明，FARC不仅是具有高精度的分类精度，同时具有对训练样本数量的不敏感性，在训练样本减少的情况下仍能保持较好的分类精度，是一种有效的分类方法。同时，本文将模糊关联分类算法引入遥感图像分类问题的研究中，在实际遥感分类问题中，训练样本往往较难获取，训练样本的不足会导致分类精度的下降，本文提出的FARC算法能够较好的适应训练样本较低情况下的分类问题，从而能够很好的应用于实际遥感分类问题。

目录

文摘

英文文摘

声明

1绪论

1.1数据挖掘研究概述

1.1.1数据挖掘技术的产生和发展

1.1.2数据挖掘的功能和方法

1.2关联规则挖掘的概念和研究内容

1.2.1关联规则的基本概念

1.2.2事务数据库的表示方法

1.2.3频繁项集挖掘的相关研究

1.3关联规则在分类问题中的研究

1.4本文的内容概要和结构安排

2基于位表的关联规则快速挖掘算法研究

2.1引言

2.2 Apriori类算法分析

2.2.1 Apriori算法描述

2.2.2算法性能分析

2.3位表数据结构及其相关操作

2.4基于位表的关联规则挖掘

2.4.1基于位表的快速支持度计算

2.4.2基于位表的快速候选频繁项集生成

2.4.3算法描述

2.5算法仿真

2.6小结

3基于位表的事务间关联规则快速挖掘研究

3.1引言

3.2事务间频繁闭项集及其性质

3.3基于位表的事务间频繁闭项集挖掘

3.3.1事务间频繁闭项集候选集的生成

3.3.2事务间频繁闭项集的支持度计算

3.3.3事务间频繁闭项集封闭性检查

3.3.4算法描述

3.4性能比较

3.5结论

4基于模糊关联规则的关联分类算法研究

4.1引言

4.2模糊关联分类算法研究

4.2.1模糊关联规则

4.2.2连续属性的离散化

4.2.3生成模糊分类规则

4.2.4模糊关联规则分类器

4.2.5算法描述

4.2.6仿真比较

4.3 FARC算法在遥感影像分类问题中的应用

4.4小结

5总结与展望

5.1总结

5.2展望

参考文献

攻读博士学位期间发表学术论文情况

攻读博士学位期间参加项目情况

创新点摘要

致 谢

作者简介