探析关联规则挖掘

减小字体 增大字体 作者:杜英  来源:www.zhonghualunwen.com  发布时间:2012-09-12 10:54:50

一、关联规则基本概念

关联规则是关联分析中的一种常用技术。关联规则是寻找在同一个事件中出现的不同项的相关性。其形式如下。

二、关联规则的分类

我们将关联规则按不同的情况进行分类:

1、基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理。

2、基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。

3、基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。

三、关联规则经典算法-Apriori算法

(一)Apriori算法概述

在众多的算法中 Apriori 算法是最为经典的关联规则挖掘算法。该算法由 Agrawal 等人于1993年首次提出。

Aprior算法的策略是,将关联规则挖掘任务分解为两步:

1) 频繁项集的产生:通过迭代,从数据库中发现满足最小支持度阀值的所有项集,即发现所有频繁项集。

2) 产生关联规则:从上一步发现的频繁项集中提取高置信度的规则,即强关联规则。

产生频繁项集的基本思想是:算法需要对数据集进行多步处理。第一步,统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的一维最大项目集。然后从第二步开始循环处理到再没有最大项目集生成停止。

(二)Apriori算法改进技术

可以从下面的角度对Apriori算法进行改进。

1、数据划分 Partition 方法

Savasere 等人提出了基于 Partition 的划分方法以减少数据库的扫描次数。Partition 算法先将数据库分成许多段,它的核心思想是:整个数据库上的频繁项集至少在数据库的一个分段上是频繁的,那么每个分段上的频繁项目集的并集就是整个数据库上潜在的频繁项目集的集合。整个算法可以分为两个步骤:

a) 将数据库分为许多小段,每个小段都能完全装入内存。并且这只需要扫描一趟数据库。

b) 将每个分段的频繁项目集合并起来。并对数据库进行第二趟扫描来验证每个候选集是否是真正的频繁项目集。

2、散列(Hash)方法

由 Park 等人提出的 DHP 算法,使用散列技术有效地提高了Apriori算法的效率,是一个能高效地产生频集的算法。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上,Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。

3、采样(Sampling)方法

为了提高Apriori 算法的效率 Mannila 等人提出了基于采样的方法。基于采样的优化方法是选取数据库 D的随机样本S进行挖掘,在S而不是在D中搜索频繁项集。

4、减少交易的个数。

减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集,则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去,这样在下一遍的扫描中就可以减少要进行扫描的事务集的个数。

四、结束语

关联规则是数据挖掘的众多知识类型中最为典型的一种。本文首先介绍了关联规则挖掘的一些基本的概念以及分类。接下来介绍了关联规则挖掘的经典算法 Apriori 算法及其改进技术。

【参考文献】

[1]陈安,陈宁,周龙骧. 数据挖掘技术及应用.2006[3]

[2]钱雪忠,孔芳.关联规则挖掘中对Apriori算法的研究[J].计算机工程与应用,2008,44 (17): 138-140.

[3]刘华婷,郭仁祥,姜浩.关联规则挖掘 Apriori 算法的研究与改进[J].计算机应用与软件,2009,26(1):147-149.

Tags:数据挖掘

作者:杜英
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论