一种有效的Web关联规则挖掘方法

[摘 要]Web挖掘是使用数据挖掘技术在WWW数据中发现潜在的、有用的模式或信息。关联规则是Web挖掘的一个重要研究领域。根据关联规则挖掘的要求与特点,结合遗传算法,提出一个有效的Web关联规则挖掘方法。实验结果表明,该算法在Web挖掘中具有一定的优势。

[关键词]数据挖掘 遗传算法 关联规则

[中图分类号]TP18[文献标识码]A[文章编号]1007-9416(2010)02-0109-02

1 引言

近年来,随着科技的进步,特别是信息产业的发展,把我们带入了一个崭新的信息时代。随着数据库技术的迅速发展以及数据库管理系统的广泛应用,同时条形码和信用卡的普及和使用,进一步加速了商业、金融、保险等领域的信息化进程。如此多领域的数据各自存放在相应的数据库中,致使数据库的规模日益扩大,已经达到数十兆字节,有的甚至更大。数据挖掘就是从大型数据库中的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在的有用的信息。提取的知识表示为概念(Concepts)、规则(Rule)、规律(Regularities)、模式(Patterns)等形式。

目前应用于数据挖掘的算法有很多种,如统计方法、机器学习方法、神经计算方法等。遗传算法由于其解决问题以混饨、随机和非线性为典型特征,它为其它科学技术无法解诀或难以解决的复杂问题提供了新的计算模型。这里,我们将遗传算法应用于数据挖掘领域,主要是因为:数据挖掘的目的就是要从大的数据库中提取信息与知识。为了达到这一目的,我们可以将整个数据库看作一个大搜索空间,而把挖掘算法看成一种搜索策略。显然,当数据库容量极其巨大时,进行穷举搜索是不可行的,必须采取一种有效的搜索策略。而与其它的启发式算法比较,遗传算法不仅具有很好的全局搜索能力,同时将其用于数据库领域时它能较好的处理数据库中不同属性之间的相互关系。正是因为遗传算法的这些特点,我们尝试将遗传算法用于数据库领域,实验证明算法是可靠的,可以得到数据库中具有较强预测能力的规则。本文提出用遗传算法挖掘关联规则,希望能在关联规则的提取方法上提出一种新的尝试。

2 关联规则挖掘

关联规则挖掘就是从大量的数据中挖掘出有价值的、描述数据项之间相互关系的有关知识。有效的发现、理解、运用关联规则,是完成数据挖掘任务的一个重要手段。Agrawal等人于1993年首先提出了挖掘顾客事务数据库中项集间的关联规则问题,其核心方法是基于频繁项集理论的递推方法。目前,数据挖掘的关联规则方法有多种,其中Apriori算法是一种找频繁项集的典型算法。这种算法简单易理解, 就是使用了不断通过连接产生候选集,并对侯选项集加以剪枝的方式来得到频繁集,再由频繁项集产生强关联规则的过程。关联规则是识别一组给定数据集的各特征值之间和各项之间的相互依赖及相互转化关系。关联规则是如下形式的一种规则:“在无力偿还贷款的人当中,60%的人的月收入在3000元以下。”关联规则的主要任务就是要挖掘出数据库D中所有的有用规则,在这个挖掘过程中,选择高效的关联规则算法进行数据挖掘是非常重要的。

设I={i1,i2,…im}为所有项目的集合,项目集,D为事务数据库,其中每个事务T是一个项目子集()。每一个事务具有惟一的事务标识Tid。我们说事务T包含项目集X,当且仅当。如果项集A中包含k个项目,则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是频繁项集(或大项集)。关联规则是形如X=>Y的逻辑蕴含式,其中,XT,YT,并且X∩Y=φ。X称作是前提,Y称作是结果。一般用两个参数描述关联规则的属性:

*支持度(support):如果事务数据库中有s%的事务包含X U Y,那么我们就说关联规则X=>Y的支持度support为s,Support(X=>Y)=P(X U Y)。

*信任度(support):如果事务数据库里包含X的事务中有c%的事务同时也包含Y,那么我们说关联规则X=>Y的信任度Confidence为c,Confidence(X=>Y)= P(Y|X)。

关联规则就是支持度和信任度分别满足用户给定阈值的规则。为了提高Apriori算法的有效性,可以使用基于散列的技术压缩侯选k-项集;而基于划分的方法是将大型事务数据库划分成多块数据,以便将每块数据放入内存求其频繁项集,这种方法只需要两次数据库的扫描;基于采样的方法,是在给定数据的一个子集上挖掘;通过事务压缩减少扫描的事务个数;基于hash的方法,可以提高找侯选项集的效率。另一种不需产生侯选项集的频繁模式增长算法,也是一种高效的关联挖掘算法。 国内外在关联规则挖掘方面的研究已经取得了较大的进展,但关联规则挖掘技术在有些方面仍然存在着不足。需要进一步研究和提出更好的解决方案。

3 遗传算法的基本思想

遗传算法是基于生物学进化原理的全局搜索算法,通过计算机模拟生物进化过程,对群体不断优化,最终找出最优解。到目前为止,遗传算法已经在模式识别、图象处理、人工智能、经济管理、商业和金融等多个领域中获得了较成功的应用。构成遗传算法的要素主要有:染色体编码,个体适应度评价,遗传算子(选择算子,交叉算子,变异算子)以及遗传参数设置等。基本遗传算法一般要包含以下几个处理步骤:

(1)选择编码策略,把参数集合X和域转换为位串结构空间S;

(2)定义适应值函数f(x);

(3)确定遗传策略,包括选择群体大小n,选择、交叉、变异方法;

(4)随机初始化生成群体P;

(5)计算群体中个串解码后的适应值f(x);

(6)按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;

(7)判断群体性能是否满足某一指标,或者已完成预定迭代次数,不满足返回步骤(6),或者修改遗传策略再返回步骤(6)。

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

遗传算法(Genetic Algorithm-GA)是一种高效的启发式快速搜索算法,为了从海量数据中提取有用的信息与知识,我们可以将整个数据库看作一个大搜索空间,而把挖掘关联规则的算法看成一种搜索策略。当数据库容量极其巨大时,进行穷举搜索是不可行的,必须采取一种有效的搜索策略。针对传统的遗传算法容易导致算法的过早收敛而陷于局部最优困境,或收敛时间过长而消耗大量的搜索时间的缺陷,我们提出了一种改进的遗传算法,该算法采用一种自适应变异率和改进的个体选择方法,并且将这种改进遗传算法应用于web关联规则的挖掘,实验结果证明这种算法是有效的。

与其它的启发式算法比较,遗传算法不仅具有很好的全局搜索能力,同时将其用于数据库领域时它能较好的处理数据库中不同属性之间的相互关系。应用遗传算法进行关联规则发现,首先要对解决的实际问题进行编码,编码方法一般采用二进制编码,也可以采用十进制编码。关联规则挖掘的任务就是要发现能够反映记录属性之间的关系,通过遗传算法的适应度函数的定义,根据适应度函数的值进行搜索得到一组规则。利用交叉、变异运算对该组规则进行进化,再利用选择运算产生下一代规则,这样经过若干次迭代后,遗传算法满足终止条件,从而得到一组理想规则。接下来,利用这些规则对数据库中的数据进行加工,删除规则覆盖的例子,对剩余的数据继续采用以上遗传算法,去挖掘第二组规则。重复以上步骤,直至数据库中的所有例子都被覆盖或满足事先约定的终止条件。最后应用规则优化算法对所得规则进行优化,使之得到最简规则。基于遗传算法的关联规则挖掘技术可以应用在销售分析、金融信贷风险分析,物流货源分析等领域,具有较好的研究和应用价值。

[参考文献]

[1] 叶传奇,张涛.遗传算法在数据挖掘中的应用研究[J].洛阳工业高等专科学校学报,2003.

[2] 彭建.一种基于遗传算法的关联规则挖掘方法[J].计算技术与自动化,2005.

[3] 张志立,张鹏,齐德昱: 一种基于遗传算法的知识规则挖掘算法[J].郑州大学学报(理学版) ,2004.

[4] 周涛,岳振才.基于改进遗传算法的关联规则挖掘[J].陕西工学院学报,2004.

[作者简介]

周大镯(1971-),女,河北文安人,河北经贸大学计算机中心副教授,天津大学管理学院在读博士研究生。研究方向:数据挖掘。

[基金项目]

河北省科技厅项目(05213574)