经典关联算法分析和Weka数据挖掘应用

中南林业科技大学计算机与信息工程学院 欧阳林 谭骏珊 唐 笑

1.关联规则

关联规则是数据中蕴含的一类重要规律，对关联规则进行挖掘是数据挖掘中的一项根本任务，甚至可以说是数据库和数据挖掘领域中所发明并被广泛研究的最为重要的模型[1]。简言之，关联规则挖掘是发现大量数据中项集之间的关系或相关联系[2]。这些关系往往是隐藏的，从大量商务数据中发些这些有趣的关系对交叉销售、配送服务、贱卖分析等是有价值的，这样也有利于商务决策的制定。

关联规则挖掘的经典应用是购物篮数据分析，该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯，得出哪些商品频繁的被顾客同时购买，可以优化商品的分类陈列、改善商店的布局。以下是一个关联规则的简单例子：

计算机=＞财务管理软件

[支持度=12%，置信度=60%]

这个规则表明12%的顾客同时购买电脑和财务管理软件，而在所有购买了电脑的顾客中有60%顾客也购买了财务管理软件。

2.关联规则相关概念

项目集合：I={i1，i2，i3，…，im}。

k-项集：项集中项目个数为k的项集。

事务集合：T=(t1，t2，t3，...，tm)。

关联规则表达模型：

XàY，其中X∈I，Y∈I，且X∩Y=ø。

这是一个蕴涵关系表达式，X称前件，Y称后件。

X覆盖ti：项集X是事务ti∈T的一个子集，则称ti包含X，也称X覆盖ti。

支持计数：是T中包含X的事务的数目，记做X.count。

支持度：规则XàY的支持度是T中包含X∪Y的事务的百分比，也可以看做是概率P(XUY)。支持度表示规则在事务集合T中使用的频繁程度。如果支持度的值太小，则表明这个规则可能是偶然发生的，研究它可能没什么价值。

置信度：规则XàY的置信度是既包含了X又包含了Y的事务的数量占所有包含了X的事务的百分比，也可看做是条件概率P(Y|X)。置信度决定了规则的可预测度，如果一条规则的置信度太低，那么从X就很难可靠地推断出Y。研究置信度太低的规则在实际应用中也不会有太大价值。

目标：关联规则挖掘就是要找出一个给定的事务T中所有满足用户指定的最小支持度(minsup)和最小置信度(mincof)的关联规则。如果一个关联规则满足最小支持度和最小置信度，那么就认为该关联规则是有意义的。

频繁项目集：一个支持度高于minsup的项集。

可信关联规则：置信度大于minconf的规则。

3.Apriori算法思想

Apriori算法是基于关联规则的经典挖掘算法，是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法分两步进行：

（1）生成所有频繁项目集。

（2）从频繁项目集中生成所有可信关联规则。

3.1 频繁项目集生成部分的算法

Apriori算法基于演绎原理（向下封闭属性）来高校的产生所有频繁项目集，其中向下封闭属性是指如果一个项集满足某个最小支持度要求，那么这个项集的任何非空子集必须都满足这个最小支持度。

Apriori使用一种逐层搜索的思想来生成频繁项目集。它采用多轮搜索的方法，每一轮搜索一遍整个数据集，并最终生成所有的频繁项目集。在第一轮搜索中，算法计算出所有只包含一个项目集的项集在事务集合中的支持度，并据此得到初始的单项目集（即1-频繁项目集）F1。随后的每一轮所搜都分为三步：

(1)将算法第(k-1)轮搜索生成的频繁项目集集合Fk-1作为种子集合产生候选的项集集合Ck，而Ck中的这些候选项集都是可能的频繁项目集，这个过程由candidate-gen()函数完成。

(2)随后算法对整个事务数据库进行扫描，计算Ck中的每个候选项集c的支持度，注意，在整个计算过程中并不需要将整个数据集加载入内存，事实上，在任何时候我们都只要在内存中保留一条事务记录，因此Apriori算法可以用于处理非常巨大的数据集。

(3)在本论搜索的最后，算法计算Ck中每个候选项集的支持度，并将符合最小支持度要求的候选项集加入Fk中。

算法最后输出的是所有频繁项目集的集合F。

3.2 候选项集集合Ck的生成函数

该函数分为两部分：合并和剪枝。

合并：将两个(k-1)-频繁项目集合并来产生一个可能的k-候选项集c。两个频繁项目集f1和f2的前k-2个项目都是相同的，只有最一个项目是不同的，随后，c被加入到候选项集集合Ck中。

剪枝：从合并步中得到的候选项集并不是最终的Ck。有一部分候选项集可以被剪枝。这一步判断c的所有(k-1)-子集是否都在Fk-1中。如果其中任何一个子集不在Fk-1中，则根据向下封闭原理，c必然不可能是频繁项目集，于是可将c从候选项集Ck中删除。

3.3 关联规则生成算法

给定一个频繁项目集f，如果一条关联规则的后件为a，那么所有以a的任意一个非空子集为后件的候选规则都是关联规则。基于此，得出了一个类似于频繁项目集生成的关联规则生成算法。首先，从频繁项目集f中生成只有一项的关联规则，然后利用所得到的关联规则和candidate-gen函数生成所有2-后件候选关联规则，依此类推。

3.4 缺点

在实践中，关联规则可能不像人们期望的那么有用。一个主要缺点是支持度、置信度框架常常产生过多的规则。另一个缺点是其中大部分规则是显而易见的。关联分析需要技巧，用严格的统计学知识处理规则增值将是有益的[4]。

3.5 提高Apriori的有效性

为提高Apriori算法的有效性，我们可以从以下几个方面考虑：

基于散列的方法：通过实验可以发现寻找频繁项集主要的计算是在生成频繁2-项集上，一种基于散列的技术可以用于压缩候选k-项集Ck(k＞1)。例如，当扫描数据库中每个事务，由C1中的候选1-项集产生频繁1-项集L1时，可以对每个事务产生所有的2-项集，将它们散列（即映射）到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2-项集不可能是频繁2-项集，因而应当由候选集中删除。这种基于散列的技术可以大大压缩要考察的k-项集，特别是利用这一技术来改进产生频繁2-项集。

事务压缩：减少用于未来扫描的事务集的大小。一个基本的原理就是不包含任何k-项集的事务不可能包含任何（k+1）-项集。从而就可以将这些事务在其后的考虑时加上标记或删除，因为为产生j-项集（j＞k），扫描数据库时不再需要它们，这样在下一遍的扫描中就可以减少要进行扫描的事务集的个数。

基于划分的方法：为了降低算法对内存的需求同时提高并行性，基于划分的方法把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些频繁项集的支持度，这里每一个部分的大小和划分的数目确定，使得每一部分能够放入内存，这样每个阶段只需要被扫描一次，而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。此算法可以使高度并行的，可以把每一部分分配给某一个处理器生成频繁项集。

基于选样的方法：在给定数据的一个子集挖掘。选样的方法的基本思想是：选取给定数据库D的随机样本S，然后，在S而不是在D中搜索频繁项集，得到一些在整个数据库中可能成立的规则，然后对数据库剩余部分验证这个结果。用这种方法，牺牲了一些精度换取了有效性。样本S的大小这样选取，使得可以在内存搜索S中频繁项集；这样，总共只需要扫描一次S中的事务。由于搜索S中而不是D中的频繁项集，可能丢失一些全局频繁项集。为减少这种可能性，使用比最小支持度低的支持度阈值来找出局部于S的频繁项集（记作LS）。然后，数据库的其余部分用于计算LS中每个项集的实际频繁度。采用下列方法来确定是否所有的频繁项集都包含在LS中：如果LS实际包含了D中的所有频繁项集，只需要扫描一次D；否则，可以做第二次扫描，以找出在第一次扫描时遗漏的频繁项集。当效率最为重要时，如计算密集的应用必须在频繁度不同的数据上运行时，选择方法特别合适。

动态项集计数：动态项集计数技术将数据库划分为标记开始点的块在扫描的不同点添加候选项集，不像Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种方法中，可以在任何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。

4.weka实现数据挖掘

Weka是一个功能全面的机器学习和数据挖掘应用程序平台[4]。Weka用Java编程，其中提供了优秀的学习算法，现在我们使用上面已经分析了的Apriori算法做一些机器学习工作。本文中，我们在windows xp下，使用的是weka3.6版以及Mysql5.0版本数据库，对深海油气田的数据库中的oilField表中的FieldLife和Total用Apriori进行分析。

4.1 weka连接数据库

在连接数据库之前我们需要下载安装了mysql-connector-java-3.1.14和Java的jdk，并将mysql-connectorjava-3.1.14-bin.jar的路径配置到环境变量classpath中。接着打开weka的安装路径，例如：我的路径为：G:Program FilesWeka-3-6，找到weka.jar文件，将其解压到当前文件夹下。在解压后的文件夹中找到wekaexperiment这个目录下的DatabaseUtils.props与DatabaseUtils.props.mysql。然后使用UltraEdit打开这两个文件。在DatabaseUtils.props.mysql文件中，我们能看到以下配置项：

（1）驱动加载项

将jdbcDriver=后的内容mysqlconnector-java-3.1.14-bin.jar里面的驱动，配置如下：

（2）类型转换

找到# specific data types部分，在其下配置mysql中各种类型对应转换成weka的数据类型，我们使用从DatabaseUtils.props中的#mysqlconversion下的配置项。其余部分的配置不需要更改，保存文件。此时我们再将DatabaseUtils.props重命名为任意名字，将DatabaseUtils.props.mysql改成DatabaseUtils.props。

（3）将weka重新打包

在命令提示符下我们进入到刚解压的文件夹下，运行jar –cvf weka.jar *.*，此命令将当前目录下的任意文件压缩到weka.jar里，并且weka.jar文件就生成在当前目录下。

（4）覆盖原文件，运行weka

我们将重新打包的weka.jar拷贝到安装目录下（建议将原文件重命名），然后运行weka。

（5）点击Explorer-Open DB

在url栏的最后面修改要连接的数据库名，点击user输入用户名与密码，点击connect连接数据库。

4.2 weka进行关联规则挖掘

（1）导入数据

在Query栏输入sql语句，点execute执行，点ok将结果集导入weka。本文导入了深海油气田数据库中的oilField表中的FieldLife和Total：

FieldLife：油田寿命

Total：油田储量

（2）数据离散化

在weka的preprocess的filter中选择unsupervised/attribute/discretize。在choose右侧点击显示输入参数界面，将bin改成5。然后点击apply，这样就将fieldlife和total离散成了5类数据。

（3）度量标准

Weka中有几个类似的度量代替置信度来衡量规则的关联程度，它们分别是：

Lift：P(L，R)/(P(L)P(R))。Lift=1时表示L和R独立。这个数越大，越表明L和R存在在一个购物篮中不是偶然现象。

Leverage：P(L,R)-P(L)P(R)。它和Lift的含义相近。Leverage=0时L和R独立，Leverage越大L和R的关系越密切。

Conviction：P(L)P(!R)/P(L,!R)（!R表示R没有发生）。Conviction也是用来衡量L和R的独立性。从它和lift的关系（对R取反，代入Lift公式后求倒数）可以看出，我们也希望这个值越大越好。

值得注意的是，用Lift和Leverage作标准时，L和R是对称的，Confidence和Conviction则不然。

（4）参数设置

现在计划挖掘出支持度在10%到100%之间，并且lift值超过1.5且lift值排在前10位的那些关联规则。我们把"lowerBoundMinSupport"和"upperBoundMinSupport"分别设为0.1和1，"metricType"设为lift，"minMetric"设为1.5，"numRules"设为10。其他选项保持默认即可。"OK"之后在"Explorer"中点击"Start"开始运行算法，在右边窗口显示数据集摘要和挖掘结果。

（5）结果及分析

虽然设置的numRules为10，但是相关的关联项只有四项。对于挖掘出的每条规则，WEKA列出了它们关联程度的四项指标。第一条规则的意思是油田寿命在5.797968868E17-7.693786214E17范围内的油田的储量大于7.87367106E17的可信度为55%。第二条规则是说油田储量大于7.87367106E17的油田的寿命在5.797968868E17-7.693786214E17范围内的可信度为43%，依此类推。所以，总的来说油田寿命较长的油田，其储量最高的可能性最大。

[1]Bing Lin.Web数据挖掘俞勇[M].薛贵荣,韩定一,译.北京:清华大学出版社.

[2]韩家炜.数据挖掘:概念与技术[M].机械工业出版社.

[3]Data Minng:Concepts and Techniques J.Han and M.Kamber Morgan Kaufman 2006 China Machine Press.

[4][印]K.P. Soman Shyam Diwakar V.Ajay.数据挖掘基础教程[M].范明,牛常勇,译.机械工业出版社.