23.txt

This complete matlab for neural network

发信人: GzLi (笑梨), 信区: DataMining
标  题: [合集]欢迎大家对该论文的优缺点加以评论
发信站: 南京大学小百合站 (Fri Jul 18 00:16:06 2003)

surfgey (风卷云舒) 于Thu Jul 10 20:43:07 2003)
提到：

  欢迎大家对该论文的优缺点加以评论，论文的独到之处是什么？不足之处是什么？欢迎
你的补充和完善
                     

       关联规则挖掘综述

(蔡伟杰 [e-mail])

蔡伟杰 张晓辉 朱建秋 朱扬勇2

（复旦大学计算机科学系       上海  200433）

摘要  本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算
法进行了分析和评[1]价，指出传统关联规则衡量标准的不足，归纳出关联规则的价值衡量
方法，展望了关联规则挖掘的未来研究方向。

关键词  数据挖掘，关联规则，频集，OLAP

 

1引言
数据挖掘（Data Mining），又称数据库中的知识发现（Knowledge Discovery in Databa
se），在最近几年里已被数据库界所广泛研究，其中关联规则（Association Rules）的挖
掘是一个重要的问题。

关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模
式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计
、货存安排以及根据购买模式对用户进行分类。

Agrawal等于1993年[1]首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸
多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进
行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应
用进行推广。

最近也有独立于Agrawal的频集方法的工作[18,19]，以避免频集方法的一些缺陷，探索挖
掘关联规则的新方法。同时随着OLAP技术的成熟和应用，将OLAP和关联规则结合[20,21]也
成了一个重要的方向。也有一些工作[6]注重于对挖掘到的模式的价值进行评估，他们提出
的模型建议了一些值得考虑的研究方向。

本文第二部分是对关联规则基本概念的介绍，提出了关联规则的分类方法；第三部分是对
挖掘算法的介绍，从经典的apriori开始，然后描述了对该算法的优化拓展，接着讲述脱离
apriori算法的方法，最后是多层、多维的关联规则挖掘；第四部分归纳出关联规则价值衡
量方法，主要从两个方面进行考虑：系统客观层面和用户主观层面；最后展望了关联规则
挖掘的未来研究方向。

2关联规则的基本概念
2.1基本概念和问题描述
设I={i1, i2,…, im}是二进制文字的集合，其中的元素称为项(item)。记D为交易(trans
action)T的集合，这里交易T是项的集合，并且TÍI 。对应每一个交易有唯一的标
识，如交易号，记作TID。设X是一个I中项的集合，如果XÍT，那么称交易T包含X。

一个关联规则是形如XÞY的蕴涵式，这里XÌI, YÌI，并且XÇ
Y=F。规则XÞY在交易数据库D中的支持度（support）是交易集中包含X和Y的交易数
与所有交易数之比，记为support(XÞY)，即

support(XÞY)=|{T:XÈYÍT，TÎD}|/|D|

规则XÞY在交易集中的可信度（confidence）是指包含X和Y的交易数与包含X的交易
数之比，记为confidence(XÞY)，即

confidence(XÞY)=|{T: XÈYÍT，TÎD}|/|{T:XÍT，T&
Icirc;D}|

给定一个交易集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支
持度(minsupp)和最小可信度(minconf)的关联规则。

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

1.         基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。

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

例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=
2300，涉及的收入是数值类型，所以是一个数值型关联规则。

2.         基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。

在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而
在多层的关联规则中，对数据的多层性已经进行了充分的考虑。

例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机
，是一个较高层次和细节层次之间的多层关联规则。

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

在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联
规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中
的一些关系；多维关联规则是处理各个属性之间的某些关系。

例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”
，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。

 

给出了关联规则的分类之后，在下面的分析过程中，我们就可以考虑某个具体的方法适用
于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。

3.关联规则挖掘的算法
3.1经典频集方法
Agrawal等于1993年[1]首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心
方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量
的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提
高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规
则的应用进行推广。

3.1.1核心算法
Agrawal等[1]在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法 — 这
是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为两个子问题：

1)        找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频集（Fre
quent Itemset)。

2)        使用第1步找到的频集产生期望的规则。

这里的第2步相对简单一点。如给定了一个频集Y=I1I2...Ik，k³2，Ij∈I，产生只包
含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项
，(即形如[Y-Ii]ÞIi，"1£i£k)，这里采用的是[4]中规则的定义。一
旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规
则右部含两个以上项的规则，在其以后的工作中进行了研究，本文后面考虑的是这种情况
。

为了生成所有频集，使用了递推的方法。其核心思想如下：

(1)     L1 = {large 1-itemsets};

(2)     for (k=2; Lk-1¹F; k++) do begin

(3)       Ck=apriori-gen(Lk-1);   //新的候选集

(4)       for all transactions tÎD do begin

(5)           Ct=subset(Ck,t);    //事务t中包含的候选集

(6)           for all candidates cÎ Ct  do

(7)           c.count++;

(8)       end

(9)        Lk={cÎ Ck |c.count³minsup}

(10)    end

(11)    Answer=ÈkLk;

首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止
。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有
一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的
候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证
来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可
能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这
需要很大的I/O负载。

在论文[6]中，Agrawal等引入了修剪技术（Pruning）来减小候选集Ck的大小，由此可以显
著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集
是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集
不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候
选集的支持度的代价。文[6]中，还引入杂凑树（Hash Tree）方法来有效地计算每个项集
的支持度。

3.1.2频集算法的几种优化方法
虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意
的地方，于是人们相继提出了一些优化的方法。

1.         基于划分的方法。Savasere等[14]设计了一个基于划分(partition)的算法，
这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成
所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支
持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。
而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的
算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的