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

黄毅杰 张艺雪

(1漳州职业技术学院计算机工程系 福建漳州 363000；

2漳州卫生职业学院信息技术部 福建漳州 363000)

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

黄毅杰1张艺雪2

(1漳州职业技术学院计算机工程系 福建漳州 363000；

2漳州卫生职业学院信息技术部 福建漳州 363000)

对在传统的关联规则挖掘算法下产生的关联规则出现的问题进行分析，引入兴趣度并结合遗传算法的特点，提出一种基于遗传算法的关联规则挖掘算法，通过遗传算法的自适应寻优技术和兴趣度更好地筛选出关联规则。通过实验证明，该算法是有效的。

数据挖掘，关联规则，兴趣度，遗传算法

数据挖掘是一种信息分析技术，数据挖掘应用算法从大型数据库中提取有用的信息和知识，通过这些算法确定信息项之间的隐性关系，并且向用户显示这些关联[1]。数据挖掘将来自人工智能和模式识别的一组技术和系统方法组合在一起，帮助用户搜索模式。关联规则挖掘已经成为数据挖掘领域中重要的研究方向[2]。

1 关联规则概述

关联规则挖掘是从大量数据中发现数据之间的关系和关联以及相关的分组，关联规则可以确定数据库中存在的逻辑隐含规则，确定关联组。1994年， Agrawal等人提出了关联规则挖掘的经典算法Apriori，其最常见的例子是购物篮分析[3]。这是对客户总共购买的产品的分析，它的目标是确定产品之间最常见的关系。如果有记录一组购买事务的客户数据库，并通过购买的特定产品集来描述每个购买事务，则关联规则可表示为： X⟹Y，其中X和Y是产品集，该规则的直观含义是包含X中的产品的事务也倾向于包含Y中的产品。该规则的评估有用性的度量是支持度(support)和可信度(confidence)。support度量代表同时包含X和Y的事务的百分比，可以用公式“support(X⟹Y)=包含X∪Y的事务数量/事务总数量”表示。confidence度量代表包含X的事务中也包含Y的事务的百分比，可以用公式“confidence(X⟹Y)=包含X∪Y的事务数量/包含X的事务数量”表示。关联规则描述如：{买啤酒}⟹{买炸土豆片}，support=70%，confidence=85%表示85%的购买啤酒的客户也购买了炸土豆，这种关联只占数量的的70%。为了找出有用的关联规则，需要用户确定两个阈值，即最小支持度(min_sup)和最小可信度(min_conf)，满足support(X⟹Y)> min_sup且confidence(X⟹Y)> min_conf的规则称为强关联规则。

2 问题的提出

通过一个具体的实例来说明购买商品与不购买商品的关系。设I=(啤酒，炸土豆片)，交易集D，经过对D的分析，得到交易集分析，如表1所示。

表1 交易集分析

设定min_sup =0.2，min_conf =0.8，得到关联规则： {买炸土豆片} ⟹{买啤酒}，support =0.2，confidence =0.8即80%的人买了炸土豆片就会买啤酒。但从表1中可以很容易的得到结论：90%的人肯定会买啤酒，即买炸土豆片这个事件对于买啤酒这个事件的作用并没有想象中的那么大，反而是规则：{买啤酒}⟹{不买炸土豆片}，support =0.7，confidence =0.78，更具有商业销售的指导价值。

从上面的例子可以发现，基于支持度-可信度的关联规则评估体系存在着问题，其只能挖掘出正属性项的规则，不能挖掘出负属性项的规则，而这种知识往往具有更重要的价值[4]。

3 引入兴趣度

为了解决上面提出的问题，引入兴趣度概念来分析项集A和项集B的关系程度。兴趣度的公式为：

其反映了项集A与项集B的相关程度[5]。

如果I(A→B)=1，即P(AB)=P(A)P(B)表示项集A出现和项集B出现是相互独立的。

如果0

如果I(A→B)>1，表示A出现和B出现是正相关的，意味着A的出现蕴涵B的出现。其中I(A→B)的数值越大，意味着这条规则的兴趣度越大。

利用兴趣度对表1进行分析可以得出所有的关联规则如表2所示。

表2 所有的关联规则

从表2可以看出属于正相关规则的序号3和序号6的都大于1，可以列入进一步考虑的范围。

4 基于遗传算法的关联规则挖掘实现过程

4.1编码方法的选择

由于二进制编码的的编码操作和解码操作比较简单，本文采用二进制编码。二进制编码是基于确定的二进制位串I={0，1}L，若事务数据库D中的TID001事务包含I1，13，I6，项集I的项数为6，则可以用6位的二进制位串101001来对染色体进行编码，其中0表示项不存在，1表示项存在事务中[6]。

4.2适应度函数的确定

为了找到最优解，在适应度函数中加入了评估关联规则有用性的重要标准，即支持度，通过支持度来对适应度函数进行定义。首先通过支持度对规则进行筛选，然后判断筛选出来的规则是否满足最小支持度，最后确定这些规则的适应性。关联规则的适应度作如下定义：

式中S′为经过遗传操作所形成的一条新规则的支持度，S为用户给定的支持度阈值。

当fitness(Ri)>1， Ri保留并进入下一代遗传，当fit(Ri)<1， Ri将在下一代遗传中被淘汰。

4.3遗传算子的改进

(1)选择算子。 本文的选择算子采用基于适应值比较的方法，即随机抽取两个染色体，适应值大的染色体被选择，适应值小的染色体被淘汰，如果两个染色体的适应值相等，则选择两个染色体中的任意一个。该方法保证了群体的多样性，同时又保证了加入配对库的个体具有较大的适应值。

(2)交叉算子。 交叉算子也称配对算子，同源的染色体可通过染色体交配，重组出新的染色体，本文采用单点交叉的方法，单点交叉是在二进制位串中随机确定一个交叉位置，在进行交叉时，互换相应的子串。

(3)变异算子。 本文采用了自适应变异算子，该算子是基于基本变异算子的基础上引入自适应变异概率Pm，变异概率Pm随着群体中个体的多样性程度而自适应改变。变异算子具有局部搜索能力，自适应变异概率可以避免出现早熟现象。

4.4规则提取

由于本文引入了兴趣度，提取规则的标准是此规则首先要满足用户给定的可信度，其次要判断此规则的兴趣度是否大于1，如果大于1则输出，否则舍弃。

遗传算法流程如图1所示。

图1 遗传算法流程图

5 仿真实验和算法分析

某超市用户的购买的记录，记录中的交易记录有60条，项集数有6个(I1，I2，I3，I4，I5，I6)。编码映射表如表3所示。

表3 编码映射表

设min_sup=0.3，min_conf=0.6，通过本文提出的挖掘算法挖掘出的关联规则如表4所示。

表4 发现的关联规则

从表4可以看出，兴趣度大于1的有序号1，2，4，5，7，9，10，其中序号9和序号10的关联规则出现了负属性项。因为兴趣度小于1，可以舍弃序号为3、6、8的关联规则，序号4和序号10的关联规则是兴趣度最大的两个，意味着这两个规则的利用价值最大。

在测试较大数据时，数据库选用KDDCUP 2000的Bule Marrtini Software Inc的数据库BMS-POS，其事务数有515 600个，项数有1 660个，设交叉概率为60%，变异概率为10%，迭代次数界限为500，本文提出的算法与Apriori算法的性能比较如图2所示。

图2 算法性能比较

通过实验分析可以看出本文提出的挖掘算法特点有：

(1)通过把事务数据库进行二进制编码，只存储0和1，减少了占用的存储空间，提高了运算效率。

(2)在适应度函数中引入了支持度，构造一个更适用的适应度函数。

(3)引入自适应变异概率，避免出现早熟现象。

(4)引入了兴趣度，在规则提取时舍弃了一些无趣的规则。

6 结语

本文结合遗传算法的特点挖掘出关联规则，引入兴趣度对关联规则进行筛选，通过遗传算法的智能搜索技术，采用二进制编码方法，易于实现交叉、变异等操作，提高了算法的效率。通过支持度、可信度和兴趣度三个度量对关联规则筛选，使得挖掘出来的关联规则具有更大的意义和价值。

[1]Matteo Golfarelli，Stefano Rizzi. 战晓苏，吴云洁，皮人杰译.数据仓库设计：现代原理与方法[M].北京：清华大学出版社，2010.356.

[2]Paulraj Ponniah. 段云峰，李剑威，韩洁，等译.数据仓库基础[M]. 北京：电子工业出版社，2004.463.

[3]张玉芳，熊忠阳，彭燕，等. 基于兴趣度含正负项目的关联规则挖掘方法[J].电子科技大学学报，2010，39(3)：407.

[4]琚春华，鲍福光，王宗格. 关联规则的评价方法改进与度量框架研究[J].情报学报，2013，32(6)：584.

[5]梅志芳，王建. 关联规则兴趣度研究问题[J].计算机工程，2010，36(1)：38.

[6]刘建华，王勇，洪月好. 遗传算法编码设计及其在数据挖掘中的应用[J].上海电力学院学报，2005，21(3)：245.

(责任编辑李平)

Research on Mining Association Rules Based on Genetic Algorithm

HUANG Yijie1，ZHANG Yixue2

(1.Department of Computer Engineering, Zhangzhou Institute of Technology,

Zhangzhou, Fujian 363000， China; 2.Department of Information Technology,

Zhangzhou Health Vocation College, Zhangzhou, Fujian 363000，China)

In the analysis of the algorithm of mining association rules generated problems in traditional association rules, according to the interest and the feature of genetic algorithm,an algorithm for mining association rules based on genetic algorithm was proposed, and the better association rules were sifted by adaptive genetic algorithm optimization technique and the interest degree. Proved by experiments, the algorithm was effective.

data mining, association rules, interestingness, genetic algorithm

2014-6-9

黄毅杰， 32569528@qq.com。

TP 18

A

1674-9545(2014)03-0045-(04)