关联规则挖掘技术研究进展

减小字体 增大字体 作者:程舒通 徐从富  来源:www.zhonghualunwen.com  发布时间:2009-10-12 14:43:52

  0 引言
  
  关联规则(association rule)挖掘技术是数据挖掘研究的重要内容之一,旨在从大量数据中提取人们未知却又潜在有用的规则。例如发现交易数据库中不同商品(项)之间的联系,通过这些规则找出顾客购买行为模式。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
  Agrawal等人[1,2]首先提出从交易数据库发现项目间关联规则的相关问题,并给出了基于频繁集的Apriori 算法。该算法以递归统计为基础,以最小支持度为依据剪切生成频繁集。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究,他们的工作包括:对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;对关联规则的应用进行推广。
  
  1 相关定义
  
  定义1 关联规则。设I={i1,i2,NA1AD,in}是项的集合,设任务相关的数据D是数据库事务的集合。其中每个事务T是项的集合,使得TI。每一个事务有一个标志符,称做TID(transactionidentifier)。设A是一个项集,事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式。其中AI,BI,并且A∩B=。规则A∩B=在事务集D中成立,具有支持度s。其中s是D中事务包含A∪B(即A和B两者)的百分比,它是概率P(A∪B) 。规则A∩B=在事务集D中具有置信度c,如果D中包含A的事务同时也包含B的百分比是c,这是条件概率P(B|A),即
  support(AB)=P(A∪B)=|T:X∪YT,T∈D|/|D|
  confidence(AB)=P(B|A)=
  |T:X∪YT,T∈D|/|T:XT,T∈D|
  同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称为强规则。项的集合称为项集(itemset)。包含k个项的项集称为k-项集。项集的出现频率是包含项集的事务数,简称为项集的频率、支持计数或计数。如果项集的出现频繁大于或等于min_sup与中事务总数的乘积,则称项集满足最小支持度。如果项集满足最小支持度,则称它为频繁项集frequentitemset。频繁k-项集的集合通常记做Lk。
  关联规则的挖掘是一个两步的过程:
  a)所有频繁项集。根据定义,这些项集出现的频繁性至少与预定义的最小支持计数一样。
  b)频繁项集产生强关联规则。根据定义,这些规则必须满足最小支持度和最小置信度。
  
  2 关联规则分类
  
  1)基于规则中处理的变量类别
  关联规则可分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;数值型关联规则可以与多维关联或多层关联规则结合起来对数值型字段进行处理,将其进行动态的分割,或直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。
  2)基于规则中数据的抽象层次
  关联规则可以分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。
  3)基于规则中涉及到的数据的维数
  关联规则可以分为单维的和多维的。在单维的关联规则中只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换句话说,即单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。
  
  3 关联规则的评价
  
  1)系统客观层面
  系统客观的层面评价是指关联规则的有趣性是由规则的具体结构和在数据挖掘过程中所依赖的数据决定的。支持度和可信度度量是系统客观层面评价关联规则的两个常用客观性指标,这种方法主要是在这些规则上应用统计学方法,用定量的数值来判定规则的有趣性,从而避免了人为的主观意见。因此从这个意义上讲,规则有趣性的客观评价是可靠的、有说服力的。关于关联规则的系统客观层面评价方法近几年的研究较多,许多学者在传统的支持度—可信度评价方法基础上提出了很多实用的评价方法,如兴趣度评价[2~5]、新颖度评价[6]、简洁性评价[7]等。
     由于使用支持度和信任度框架可能会产生一些不正确的规则,只凭支持度和信任度阈值的系统客观的层面评价未必总能找出符合实际的规则。
  2)用户主观的层面
  只有用户才能决定规则的有效性、可行性,所以应该将用户的需求与系统更加紧密地结合起来,形成用户主观的层面评价。可以采用基于约束(constraint-based)的数据挖掘方法,具体约束的内容有数据约束、 限定数据挖掘的维和层次、规则约束。如果把某些约束条件与算法紧密结合,既能提高数据挖掘效率,又能明确数据挖掘的目标。
  
  4 关联规则挖掘技术进展
  
  关联规则挖掘在本质上是I/O负载集中的,为了高效地进行关联规则挖掘,需要减少对数据库的I/O操作次数,有以下两种方式,即减少对数据库的扫描次数和并行化。近年来,这两个方面的研究都取得了一些成果。
  4.1 减少对数据库的扫描次数
  4.1.1 Apriori算法及改进技术
  在基于一维布尔型关联规则的算法研究中,Agrawal首先提出关联规则模型,并给出求解算法AIS[1],随后又出现了SETM等算法。在前两者基础上,Agrawal等人提出的Apriori是经典关联规则算法。其主要理论依据是项集的两个基本性质:频繁项集的所有非空子集必是频繁项集;任何非频繁项集的超集也是非频繁项集。算法采用逐层搜索的迭代,由连接和剪枝这两步来实现。
  Apriori算法的优点是简单易懂,但同时也存在以下不足:
  a)当事务数据库中频繁1-项集的数目|L1|较大时,候选k-项集Ck尤其是候选2-项集将非常大,这也是Apriori算法的一个效率瓶颈。
  b)为了由Ck产生Lk,需要重复扫描数据库中的事务并计算Ck中各候选项集的支持计数,特别当事务数据库中的事务个数较大时,其效率十分低下。

[1] [2] [3] [4]  下一页

Tags:

作者:程舒通 徐从富
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

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

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