Apriori算法关联规则挖掘技术研究(3)
时间:2017-06-10 14:52 来源:毕业论文 作者:毕业论文 点击:次
Ei-Hajj等人[18]提出了一种基于反转矩阵的算法，它类似于FP-Growth算法，该算法首先将数据库映射为一个基于磁盘的反转矩阵，然后针对该反转矩阵在内存中建立COFI（Co-Ocurrence Frequent Item）树，利用COFI树发现频繁项目集。实验结果表明，该算法优于Apriori和FP-Growth，对于超大规模数据库和较小支持度的情况，优势更加明显。另外，反转矩阵的结构特点决定了它便于实现并行挖掘算法。 1.2.4 关联规则挖掘算法的进一步发展 除了上述基本关联规则挖掘算法研究，人们还进行了诸如多层关联规则、量化关联规则、基于约束的关联规则、时态关联规则、空间关联规则等类型关联规则挖掘算法的研究。 Srikant和Agrawal从广义关联规则挖掘的角度研究了多层关联规则挖掘问题，多层关联规则挖掘利用概念分层的背景知识在更高的抽象层次上挖掘关联规则，从而解决了稀疏数据中关联规则的支持度阈值过低而难以挖掘的问题。 Srikant等人通过将数值型数据划分为不同区间的方法，在这些区间之上进行定量关联规则的挖掘。 为了克服Agrawal频集方法的缺陷，人们还提出了一些新的关联规则挖掘方法。 关联规则挖掘技术正蓬勃发展着。 2 关联规则挖掘基本概念 2.1 基本概念和问题描述 设I={i1, i2,…, im}是项的集合，其中的元素称为项(item)。记D为事务T(transaction)的集合，这里事务T是项的集合，并且T∈I 。对应每一个事务有唯一的标识，如事务号，记作TID。设X是I中项的一个集合，假设X包含于T，那么称事务T包含X。 一个关联规则是形如X=>Y的蕴涵式，这里X包含于I, Y包含于I。规则X=>Y在事务数据库D中的支持度（support）是事务集中包含X和Y的事务数与所有事务数之比，记为support(XY)，即support(XY)= P(X Y)。规则X=>Y在事务集中的可信度（confidence）是指包含X和Y的事务数与包含X的交易数之比，记为confidence(XY)，即confidence(XY)= P(X|Y)。给定一个事务集D，挖掘关联规则问题就是寻找支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。 2.2 关联规则的种类 我们将关联规则按不同的情况进行分类：基于规则处理的变量类型、基于规则中数据的抽象层次以及基于规则中涉及到的数据的文数。 2.2.1 基于处理的变量类型 基于规则处理的变量类型，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多文关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如：性别：女与职业：秘书 ，是布尔型关联规则；性别：女与avg（收入）：2300，其中涉及的收入是数值类型，所以是一个数值型关联规则。 2.2.2 基于数据的抽象层次 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：IBM台式机与Sony打印机，是一个细节数据上的单层关联规则；台式机与Sony打印机，是一个较高层次和细节层次之间的多层关联规则。 2.2.3 基于数据的文数 基于规则中涉及到的数据的文数关联规则可以分为单文的和多文的关联规则。 在单文的关联规则中，我们只涉及到数据的一个文，如用户购买的物品；而在多文的关联规则中，要处理的数据将会涉及多个文。换成另一句话，单文关联规则是处理单个属性中的一些关系；多文关联规则是处理各个属性之间的某些关系。 (责任编辑：qin) |