基于FP-Growth算法改进的多层次关联规则挖掘算法

摘要：针对FP算法的缺陷，将OLAP技术和Apriori关联规则相结合，提出了一种针对FP算法的改进的多层次关联规则数据挖掘算法，在分析了关联规则数据挖掘结构的基础上，给出了该算法的思想与执行步骤，对于关联规则数据挖掘的研究具有一定的理论意义。

关键词：算法改进；多层次；关联规则；数据挖掘

中图分类号：TP312文献标识码：A文章编号：1009-3044(34)-1994-03

Multi-level Association Rules with Data Mining Based on FP Arithmetic Improvement

WANG Juan

(Cizhou College, Computer Center, Cizhou 247000, China)

Abstract: Aiming at the problems of FP arithmetic, the OLAP technology was combined with Apriori association rules, and the new arithmetic that aimed the problems of FP arithmetic was given out, which was the FP arithmetic improvement, and on the basis of analyzing the structure of data rules with data mining, the new arithmetic’s theory and its implementation steps were also developed. All of these work was significative for researching data rules with data mining.

Key words: arithmetic improvement; multi-level; association rules; data mining

1 引言

众所周知，在实际进行空间数据库和属性数据库设计时，为优化设计，将空间数据库按照地物的类型分成不同的数据层，如道路层，建筑物层等；对属性数据库常常依据范式理论，将其分解为若干通过关键字、外关键字或其他属性相互关联的若干张表的有机组合，这导致了许多空间数据被分别存放在不同层中，而其属性被分别放在不同的表中。挖掘这些表中蕴藏的知识和信息，显然有重要的理论和实践意义。在许多应用场合，空间关联规则的挖掘要求在多个数据层和表中进行。

对于关联规则算法，传统经典的关联规则Apriori算法有许多不同的改进方法。可能产生大量的候选集以及可能需要重复扫描数据库，是Apriori算法的两大缺点。针对Apriori 算法的固有缺陷，国外有学者提出了不产生候选挖掘频繁项集的方法―FP 算法。FP对不同长度的规则都有很好的适应性，同时在效率上较Apriori算法有巨大的提高。许多应用，特别是电子商务的应用中，在最低层或原始层的数据项之间，可能很难找出强关联规则和有趣的购买模式。在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易，在较高的概念层发现的强关联规则可能提供普遍意义的知识。因此，我们需要挖掘多层次的关联规则。

2 基本理论

笔者研究了一种有效的多层次关联规则挖掘方法，这种方法把FP算法、OLAP技术和Apriori关联规则挖掘算法结合起来。由于在方法中要涉及到数据仓库、OLAP、关联规则挖掘等概念，所以下面先对这些概念进行简要的介绍。

数据仓库是面向主题的、稳定的、完整的、时变性的数据集合，数据仓库为决策支持提供支持。为了进行有效的数据处理，数据仓库中的一部分必须预先计算，笔者把数据仓库中预先计算的那部分称为数据立方体。

OLAP是由数据仓库提供的，用于以多层次，多维的形式来操作数据。OLAP的基本操作包括：向上综合，向下考察，局部分析，旋转等。因此，联机分析处理的过程就是根据数据分析的要求，从原始数据中构造各种数据立方体，并对立方体执行有关的操作，把结果返回给用户的过程。

关联规则是数据间依赖关系的描述，是知识发现研究的重要内容。信息系统S 定义为四元组：(U,A,V,f)，U是对象集合，A={a1,a2,…,ap}是属性集合，V=V1∪V2…∪Vp是属性的值域集合，f：U×AV 定义对象的属性值。通常，属性是可分类的，数据的分类层次(hierarchies) 表示了自底向上的概括(generalization) 和自顶向下的特殊化(specification)。基于分类层次的关联规则挖掘算法主要包括：算法Cumulate 和Stratify，算法ML-T2L1，以及Srikant提出的利用布尔表达限定规则中项目的出现（指定关联规则的形式）提高挖掘针对性的算法。基于分类的方法仅适用于单个属性有清晰分类层次的应用。

3 关联规则挖掘的结构

此关联规则挖掘方法是以数据立方体的数据结构为基础，它是把关联规则挖掘和FP算法、OLAP技术合成起来的方法。下面重点讨论OLAP关联规则挖掘的结构。OLAP关联规则挖掘的结构由三部分组成：数据仓库，OLAP引擎和关联规则挖掘引擎。下面分别讨论这三部分。

1) 数据仓库：

数据仓库在语义上是用来存储数据，为决策支持提供服务，但也存储一些企业决策时需要的信息。它包括的数据主要有三部分：第一部分是完整的历史数据，这就允许挖掘器能够轻易而快捷地获取整个历史数据；第二部分是已物化的数据立方体，由于物化的数据立方体已存储在数据仓库中，这就为挖掘器节省了好多工作；第三部分是元数据，对挖掘器起来说，元数据可以被看作是路标。元数据不仅用来描述数据的内容而且用来描述信息的上下文环境。一种非常重要的元数据就是概念层次结构。概念层次结构是数据仓库和OLAP的基本要素，它嵌入在维的规范说明中。

2) OLAP引擎：

一旦把工作数据立方体建好，在挖掘过程中所需要的完整信息就保存在数据立方体中。这样，数据立方体就可以作为挖掘的数据源，也可作为原始数据和挖掘任务之间的接口。因为数据立方体含有的数据量非常大，所以有必要对数据立方体建立丰富的运算函数。这样OLAP引擎的主要任务就是计算用户的OLAP指令，最后把结果返回给用户界面层。可以看出OLAP引擎在OLAP关联规则挖掘的结构中具有非常重要的作用。

3) 关联规则挖掘引擎：

关联规则挖掘引擎是关联规则挖掘系统的一个非常重要组成部分，下面先介绍关联规则的类型，其次讨论关联规则挖掘引擎的框架。

该论文将提到三种类型的关联规则：维之间的关联规则，维之内的关联规则，合成关联规则。

维之间的关联规则，规则的主体和头都在不同的维中，如，Location(X,South)，Profit(X,Bad)Product(X,tent)。可以看出，在这个关联规则中所有的项目都在不同的维中，且没有重复。

维之内的关联规则，所有的项目都在同一维内，因此也称为单维关联规则。如，Product(X,clothes)Product(X,tent)。

合成关联规则是上两种关联规则的合成，因此也称为多维相关规则。如，Location(X,South)，Product(X,clothes)Product(X,tent)。

一般情况下，在产生工作数据立方体后，发现关联规则的任务可以分为两步。第一步是找出所有符合支持度的经常项目集。在此阶段，输入的是与任务相关的工作数据立方体，支持度的最小值和用户的限制条件，输出的是满足条件的经常项目集。根据关联规则的类型，输出的经常项目集可以是单维经常项目集，多维经常项目集或合成项目集。第二步是利用经常项目集产生期望的关联规则。在此阶段，输入的是上一阶段输出的经常项目集，置信度的最小值和用户的限制条件。输出的是满足置信度和用户限制条件的关联规则。

4 关联规则数据挖掘算法描述

从上面的讨论得知，在对FP算法进行改进、进行OLAP关联规则挖掘时，可以分为三个步骤：

1) 预处理：从log 表过滤出相关的信息，然后根据概念层次树，自顶向下，对数据库中的项进行编码，得到编码后的数据库D。

2) 执行改进的FP算法，分别找出各个层次的频繁项集。

3) 找出交叉层次的关联规则。

下面逐一进行说明设计。

4.1 预处理

1) 从log表过滤出相关的信息，得出经过数据清洗后的log表d。

2) 根据概念层次树，自顶向下，对数据库中的项进行编码，得到编码后的数据库D。

概念层次树可以由专家给出，也可以从数据库和Web 日志生成。

4.2 执行改进的FP算法

基本思想：自顶向下，逐层寻找每层的频繁项集。删去不满足阈值的项集。如果其祖先不满足最小支持度阈值，则不需要再计算它的支持度，直接删去即可。

对于每层(设层号为i)寻找频繁项集，均执行下面步骤：

1) 找出频繁1项集

扫描编码后的数据库D，收集每项的支持度。按支持度降序排列，删去不满足对应第i 层的最小支持度的项，结果为频繁1项集，存入频繁项表L[i]；同时，删去冗余的多层（后代）频繁1项集。

2) 构建FP树

① 根节点标记为null，它的子节点为一个项前缀子树的集合，还有一个频繁项组成的头表。

② 每个项前缀子树的节点有3个域：item-name，count，node_link。item-name 记录该节点所代表的项的名字，count记录所在路径代表的交易中达到此节点的交易个数，node_link 指向下一个具有同样的item-name 域的节点，如果没有这样一个节点，就为null。

③ 频繁项头表的每个表项由两个域组成： item-name 和node_link。node_link 指向FP-tree 中具有与该表项相同item-name域的第1个节点。

创建FP-tree 根节点，记为T，并标记为null。对于D 中每个会话session，执行：选择session 中的频繁项，并按L[i]中的次序排序。设排序后的频繁项表为[p|P]，其中p 是第1个元素，P是剩余元素的表。调用insert_tree([p|P],T)。

函数insert_tree([p|P],T)的运行如下：如果T有一个子结点N，其中N.item-name=p.item-name，则将N 的count域值增加1；否则，创建一个新节点N，使它的count 为1，使它的父节点为T， 并且使它的node_link 和那些具有相同item_name 域串起来。如果P 非空， 则递归调用insert_tree(P,N)。

3) 递归挖掘FP树：FP-树的挖掘通过调用FP-growth(FP_tree,null)实现

4.3 找出交叉层次的关联规则

基本思想：自底向上，从最低层的频繁项集开始，计算交叉层次的频繁项集。对交叉层次的频繁项集，根据满足最小支持度阈值的概率来筛选出合适的频繁项集，删去不满足概率的项集。

在OLAP关联规则挖掘时，把要挖掘的维称为项目维，而把与这个维相关的另外的维称为事务处理维，产生经常项目集的算法和Apriori算法类似，只是在判断是否满足支持度时，Apriori算法扫描的是交易数据表，而该方法扫描的是部分数据立方体。由于维之内关联规则挖掘的经常项目集产生方法和Apriori算法的一样，而合成关联规则挖掘的经常项目集产生方法是维之内关联规则挖掘和维之间关联规则挖掘经常项目集产生方法的综合，由于篇幅的关系这里只对维之间关联规则挖掘的经常项目集产生方法做一具体介绍。

维之间关联规则就是存在于一组维之内的相关规则。算法的整个过程也是以Apriori算法为基础。因为项目存在于不同的维中，这里通过利用数据立方体的概念分层结构来直接获取每个项目集的置信度。这个算法的输入条件是n 维的数据立方体CB[d1,d2,……dn]和所要求的最低支持度。

4.4 算法实验结果对比分析

为了比较上述多层空间关联规则挖掘算法的效率，用Visual C++在内存为512MB的C4 1.7G计算机上实现了FP算法与本改进算法的性能比较。测试数据集共包括2个数据层各含有5个属性，每个属性泛化后有2~10个属性值，采用的元模式形如 P(t,x)∧Q(t,y)R(t,z)，而各层的最低支持度均为6%，最低信任均为75%。

测试了算法的随记录的增加时间的变化(时间复杂性)，将测试数据库的元组数从1000开始，逐渐递增到5000。两算法的时间复杂性数据曲线如图1所示，从图中矿业发现，两个算法的时间复杂性均较好，不过随数据库规模的增大，针对FP算法的改进OLAP结构算法在执行时间更为迅速，而且在时间的增长上更为平缓一些，所以本论文提出的改进算法是可行的。

5 结语

该文中首先对数据仓库、OLAP、相关规则的挖掘进行了总体的介绍，其次全面讨论了OLAP相关规则挖掘的结构，最后讨论了基于FP算法改进，利用OLAP 关联规则挖掘结构实现的多层次关联挖掘算法。

根据用户及网站的访问使用，为用户提供动态个性化推荐，是电子商务中极为重要的功能。本文提出的挖掘多层关联规则算法，通过数据库和Web 日志构建概念层次树，在继承FP 算法思想的基础上，利用OLAP关联规则的结构，由概念层次树挖掘多层包括交叉层次的关联规则算法。本算法是对数据挖掘算法的必要补充，具有一定的理论意义，不仅能有效地应用于电子商务的个性化推荐，而且能方便地推广到其他有关的应用中。

参考文献：

[1] 高峰,谢剑英.多值属性关联规则的理论基础[J].计算机工程,2000,26(11):47-49.

[2] 王文清,乔雪峰.带有时态约束的多层次关联规则的挖掘[J].北京理工大学学报,2003,23(1):87-90.

[3] Chen J P, Bian F L, Fu Z L, et al. An Improved Algorithm of Apriori[J].Geomatics and Inform ation Science of Wuhan University,2003(1):94-99.

[4] 许兆新,周双娥,郝燕玲.最优关联规则的形式和挖掘思想的研究[J].计算机工程与应用,2000(20):118-119.

[5] 张玉林,仲伟俊,梅姝娥.一类表内多概念间多层次关联规则挖掘算法及应用[J].计算机工程与应用,2001(14):91-92,102.