基于BDIF的关联规则挖掘算法研究

郭昌建

（合肥学院 计算机科学与技术系，安徽 合肥 230601）

基于BDIF的关联规则挖掘算法研究

郭昌建

（合肥学院 计算机科学与技术系，安徽 合肥 230601）

阐述了关联规则挖掘的研究情况，关联规则的分类方法等，对经典Apriori算法进行了分析和评价，在此基础上提出了一种高效产生频繁集的BDIF（Based Transactional Databases Including Frequent ItemSet）算法；它通过划分数据块，快速的搜寻频繁项目集，从而减少对数据块的扫描次数，提高了算法的效率。并用BorlandC++Builder6.0开发环境来调试、验证该算法。

数据挖掘；关联规则；BDIF

随着经济的发展和信息的增长，许多企业和组织积累了大量的数据，隐含在数据中的关联规则、模式等知识是对决策有帮助的信息。数据挖掘的目的就是发现隐含在数据中对决策有帮助的信息，它是实现智能决策支持系统的一个重要手段。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程[1]。

1 关联规则挖掘综述

关联规则挖掘是数据挖掘中最活跃的研究方法之一。关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。最早是由Agrawal等人提出的。之后有诸多的研究人员对关联规则的挖掘问题进行了大量的研究。包括对关联规则挖掘的理论探索、原有的算法的改进和新算法的设计、并行关联规则挖掘等问题[2]。

1.1 关联规则的基本概念

设I={i1, i2,…, im}是二进制文字的集合，其中的元素称为项（item），其中ik（k=1,2,…,m）可以是购物篮中的物品，也可以是保险公司的顾客。设任务相关的数据D是事务集（DB），其中每个事务T是项集，使得T⊆I。这里没有考虑事务中项的数量，也就是说项是由一个二进制的变量来表示它是否在事务中出现。每个事务都有一个相关的标识符或TID。（设A是一个项集，且A⊆T。）关联规则是如下形式的逻辑蕴涵：A⇒B，A⊂I, B⊂I，且A∩B=φ。关联规则具有支持度和置信度两个重要的属性[3]。

1.2 关联规则的分类

关联规则按不同情况可分为：（1）基于规则中处理的变量的类别：关联规则可分为布尔型和数值型；（2）基于规则中数据的抽象层次：可以分为单层关联规则和多层关联规则；（3）基于规则中涉及到的数据的维数：关联规则可分为单维的和多维的[4]。

2 关联规则挖掘算法分析

由关联规则的定义，可把关联规则挖掘分成两个阶段：一是基于最小支持度获取频繁项目集；二是在频繁项目集上基于最小置信度产生关联规则。在完成第一步后，第二步可很自然的得到结果。所以，关联规则的算法侧重讨论如何快速地实现第一步[5]。

2.1 经典Apriori算法

Agrawal等于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。

所有支持度大于最小支持度的项集称为频繁项集，简称频集。算法的基本思想是：找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度[6]。

2.2 几种优化方法

虽然Apriori算法自身已经进行了一定的优化，但在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法，主要有：基于划分的方法、基于Hash的方法、基于采样的方法和减少交易的个数等。但这些方法都是基于Apriori的频集方法。即使进行了优化，但是Apriori方法一些固有的缺陷还是无法克服；如：可能产生大量的候选集，无法对稀有信息进行分析，重复扫描数据库等。对产生大量的候选集问题可采用一种FP-growth的方法[6]。下面提出的BDIF算法通过划分数据块，有效快速的搜寻频繁项目集，从而减少对数据块的扫描次数，提高了算法的效率[7,8]。

3 BDIF算法及其实现

3.1 BDIF算法描述

黄酮类化合物是一种重要的植物生物活性成分，具有抗心脑血管疾病、抗衰老、抗氧化、消炎、镇痛、免疫调节和降血糖等多种功效[15]。仙草黄酮类化合物的主要成分为槲皮素[16]，具有祛痰、止咳、平喘等功效。冯国金等[17]利用高效液相色谱法测定仙草的槲皮素含量为0.18 mg/g。

BDIF（Based Transactional Databases Including Frequent Itemset）算法是一种在包含频繁k-项集的事务集中，搜索包含频繁k+1-项集的事务集算法。该算法将数据库D划分为若干个包含事务集的数据块；数据块的划分是根据各个事务中是否包含的频繁项目集。这样，对数据库D的扫描转换为对数据块的扫描。

3.1.1 产生频繁1-项集

扫描数据库，统计各个项目的支持度。按支持度从大到小对频繁1-项集进行排序，如果支持度相同，则按字典顺序，并记下每个频繁1-项集的序号x（序号从1开始计）。根据该顺序，排列相应的事务集Tx1。

3.1.2 搜寻包含最大频繁项集的事务集

经过第一步后，利用以上推论，扫描包含频繁1—项集的事务集Tx1。若P为数据库D中的项目数，为避免重复产生相同的事务集，对事务集Tx1只产生P-X个包含频繁2—项集的事务集Tx+12，……依次类推，对于每一个包含频繁K—项集的事务集，分别搜索其中所包含的不同的频繁K+1—项集，直到搜索到最大频繁项目集，或是用户指定的频繁M-项集。

3.1.3 频繁项集的产生

对每一个包含最大频繁项集的事务集，输出其中包含的最大频繁项集。如何依次扫描所有的事务集Txk以产生包含频繁K+1项集的事务集Tx+1k+1？这是算法能顺利实现的关键所在。在此引用一种数据结构——队列，以辅助算法的实现。引用队列来存储尚未进行搜索的若干个包含频繁k—项集的事务集，以及已搜索过的、满足再次搜索条件的、包含频繁k+1—项集的事务集，使得算法不会重复扫描相同的事务集。该方法的具体实现如下：

（1）选择频繁1-项集中支持度最大的频繁项目L[1]，若事务中包含此项目L[1]，则将该事务加入相应的T集合中。

（3）根据支持度大小，依次选择频繁1—项集中的频繁项目L[k]，重复（1）（2）。这样，依次入队的是根据支持度大小分别包含频繁1-项集的事务集。

对于列队中的事务集，依次出队；使D＝对头元素。从D中搜索包含给定候选项集的事务并生成新集合T，若T中的事务数>=minsup，则将T入队；

否则，若D中包含的频繁项目数最多，则D就是包含最大频繁项集的事务集。

3.2 BDIF算法的实现

输入：数据库D，最小支持度minsup；输出：若干个最大频繁项集I。过程如下：

3.3 BDIF算法分析与性能测试

为了测试算法的性能，将BDIF算法与经典的基于Apriori算法的的并行算法CD（CountDistribution）等进行性能比较。开发环境为Borland C++ Builder6.0，消息传递库为标准MPI，测试结果如图1所示。

由测试的结果可知，在相同支持度下，与CD等并行挖掘算法相比，数据库扫描次数和执行时间都降低了，而且随着支持度的下降，BDIF算法性能优势更加明显。

图1 测试结果

4 结束语

Apriori算法需多次扫描数据库所有事务，程序时间开销很大。而BDIF算法把整个数据库按频繁k-项集划分为几个小事务集，然后根据Apriori性质：包含频繁k+1-项集的事务集是包含频繁k-项集的事务集的子集，直接从包含频繁k-项集事务集推出包含频繁k+1-项集的事务集，无需多次扫描整个数据库。和经典算法相比，更节省时间，效率更高。

[1] 李文实.用关联规则挖掘算法的研究和实现[J].现代计算机2000(11):6-8.

[2] 刘大有,刘亚波,尹治东.关联规则最大频繁项目集的快速发现算法[J].吉林大学学报(理学版),2004,42(2):56-58.

[3] 胡侃,夏绍玮.基于大型数据仓库的数据采掘研究综述[J].软件学报,1998,9(1):53-63.

[4] 陆丽娜,陈亚萍挖掘关联规则中Apriori算法的研究[J].小型微型计算机系统,2000,21(9):940-943.

[5] 杜孝平,马秀莉.快速关联规则挖掘算法[J].计算机工程与应用,2002(11):1-4.

[6] J. Han, J. Pei, Y Yin. Mining frequent patterns without candidate generation[A]. Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data(SIGMOD’00)[C]. Dalas: TX, 2000.

[7] 吉根林,孙志挥.数据挖掘技术[J].中国图象图形学报, 2001,6(8):715-721.

[8] F. Korn, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rules: A new paradigm.for fast, quantifiable data mining. In Proc. 1998 VLDB, PP582-593.

（责任编辑、校对：田敬军）

On the Mining Algorithm Based on BDIF Association Rule

GUO Chang-jian

(Department of Computer Science and Technology, Hefei University, Hefei 230601, China)

This article describes research on association rule mining and classification methods of association rules, analyzes and evaluates the classic Apriori algorithm, which gives rise to an efficient frequent BDIF (Based Transactional Databases Including Frequent Item Set) algorithm. It thereby reduces scanning data block and improves algorithm efficiency by dividing data block and quickly searching for frequent item set.

data mining; association rules; based transactional databases including frequent item set

TP391.1

A

1009-9115(2015)02-0042-03

10.3969/j.issn.1009-9115.2015.02.013

合肥学院重点建设学科（2014xk08）

2014-09-02

郭昌建（1965-），男，安徽合肥人，硕士，副教授，研究方向为计算机网络、人工智能。