请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5327|回复: 1

关联规则挖掘理论和算法研究

[复制链接]
字体大小: 正常 放大

2329

主题

34

听众

5965

积分

  • TA的每日心情

    2013-11-18 14:37
  • 签到天数: 76 天

    [LV.6]常住居民II

    自我介绍
    阳光

    群组2013年数学建模国赛备

    群组2013年国赛A题讨论组

    群组2013年国赛B题讨论组

    群组2013年国赛C题讨论组

    群组2013年国赛D题讨论组

    发表于 2013-8-17 10:52 |显示全部楼层
    |招呼Ta 关注Ta
    关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由Agrawal等人提出的(1993)[2]。最初提出的动机是针对购物篮分析问题提出的,其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式,可以用来指导商家科学地安排进货、库存以及货架设计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究[78~100]。他们的工作涉及到关联规则的挖掘理论的探索、原有的算法的改进和新算法的设计、并行关联规则挖掘(Parallel Association Rule Mining)以及数量关联规则挖掘(Quantitive Association Rule Mining)等问题。在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面,许多学者进行了不懈的努力。 4.1 基本概念与解决方法 一个事务数据库中的关联规则挖掘可以描述如下: 设I={ i1,i2,…,im }是一个项目集合,事务数据库D={ t1,t 2,…,tn }是由一系列具有唯一标识TID的事务组成,每个事务ti(i=1,2,…,n)都对应I上的一个子集。设I1íI,项目集I1在D上的支持度(support)是包含I1的事务在D中所占的百分比,即support(I1)= || {t? D | I1ít}|| / || D||。一个定义在I和D上的形如I1TI2的关联规则通过满足一定的可信度(confidence)来给出。所谓规则的可信度是指包含I1和I2的事务数与包含I1的事务数之比,即Confidence(I1TI2)= support(I1U I2)/ support(I1),其中I1,I2íI,I1∩I2=Ф。 给定一个事务数据库,关联规则挖掘问题就是通过用户指定最小支持度(minsupport)和最小可信度(minconfidence)来寻找合适关联规则的过程。 一般地,关联规则挖掘问题可以划分成两个子问题: (1)发现频繁项目集 通过用户给定的minsupport,寻找所有频繁项目集(Frequent Itemset),即满足support不小于minsupport的项目集。事实上,这些频繁项目集可能具有包含关系。一般地,我们只关心那些不被其它频繁项目集所包含的所谓频繁大项集(Frequent Large Itemset)的集合。这些频繁大项集是形成关联规则基础。 (2)生成关联规则 通过用户给定的minconfidence,在每个最大频繁项目项目集中,寻找confidence不小于minconfidence的关联规则。 子问题(1)是近年来关联规则挖掘算法研究的重点。比较流行的方法是基于Agrawal等人建立的项目集格空间理论。这个理论的核心是这样的原理:频繁项目集的子集是频繁项目集;非频繁项目集的超集是非频繁项目集。 对于子问题(2)而言,也许在每个频繁大项集中逐一匹配规则并进行Confidence(I1T I2)3 minconfidence的测试是必需的,因此这部分工作相对比较成熟。本章以后也主要是对发现频繁项目集方法的研究。 4.2 经典的关联规则挖掘算法分析 1994,Agrawal等在先前工作的基础上,完善了一个称为Apriori的关联规则挖掘算法[78]。这个算法一直作为经典的关联规则挖掘算法被引用。因此,本节将介绍这个算法,并且对它加以分析,其目的是发现它存在的缺点进而引入我们的研究问题。 (1)发现频繁项目集算法 算法4-1 Apriori----发现频繁项目集 (1) L1 = {large 1-itemsets}; (2) FOR (k=2; Lk-11F; k++) DO BEGIN (3) Ck=apriori-gen(Lk-1); // Ck 是k个元素的候选集 (4) FOR all transactions t?D DO BEGIN (5) Ct=subset(Ck,t); // Ct是所有t包含的候选集元素 (6) FOR all candidates c? Ct DO (7) c.count++; (8) END (9) Lk={c? Ck |c.count3minsup_count} (10) END (11) Answer= èkLk; 算法4-1中调用了apriori-gen(Lk-1),是为了通过k-1频繁项集产生K侯选集。算法4-2描述了apriori-gen过程。 算法4-2 apriori-gen(Lk-1)-----侯选集产生 (1) FOR all itemset p? Lk-1 DO BEGIN (2) FOR all itemset q? Lk-1 DO BEGIN (3) IF p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1 THEN BEGIN (4) c= p∞q;//把q的第k-1个元素连到p后 (5) IF has_infrequent_subset(c, Lk-1) THEN (6) delete c;//删除含有非频繁项目子集的侯选元素 (7) ELSE add c to Ck; (8) END (9) Return Ck; 算法4-2中调用了has_infrequent_subset(c, Lk-1),是为了判断c是否需要加入到k侯选集中。按着Agrarwal的项目集格空间理论,含有非频繁项目子集的元素不可能是频繁项目集,因此应该裁减掉,以提高效率。例如,如果L2={AB,AD,AC,BD},对于新产生的元素ABC不需要加入到C3 中,因为它的子集BC不在L2中;而ABD应该加入到C3 中,因为它的所有2-项子集都在L2中。算法4-3描述了这个过程。 算法4-3 has_infrequent_subset(c, Lk-1)-- 判断侯选集的元素 (1) FOR all (k-1)-subset s of c DO (2) IF s?Lk-1 THEN (3) Return TURE; (4) Return FALSE; Apriori算法是通过项目集元素数目不断增长来逐步完成频繁项目集发现的。首先产生1-频繁项集L1,然后是2-频繁项集L2,直到不再能扩展频繁项集的元素数目而算法停止。在第k次循环中,过程先产生k-候选项集的集合Ck,然后通过扫描数据库生成支持度并测试产生k-频繁项集Lk。 下面给出一个样本事务数据库(见表4-1),并对它实施Apriori算法。 表4-1 样本事务数据库 TID Itemset 12345 A,B,C,DB,C,EA,B,C,EB,D,EA,B,C,D 对表4-1所示的事务数据库实施Apriori算法的执行过程如下(设minsupport =40%): (1)L1生成:生成侯选集并通过扫描数据库得到它们的支持数,C 1={(A,3), (B,5), (C,4), (D,3), (E,3)};挑选minsup_count 32的项目集组成1-频繁项目集L1={A,B,C,D,E}。 (2)L2生成:由L1生成2-侯选集并通过扫描数据库得到它们的支持数C2={(AB,3), (AC,3), (AD,2), (AE,1), (BC,4), (BD,3), (BE,3), (CD,2), (CE,2), (DE,1)};挑选minsup_count >2的项目集组成2-频繁项目集L2={AB, AC,AD,BC, BD,BE,CD, CE}。 (3)L3生成:由L2生成3-侯选集并通过扫描数据库得到它们的支持数C3={(ABC,3), (ABD,2), (ACD,2), (BCD,2), (BCE,2) };挑选minsup_count>2的项目集组成3-频繁项目集L3={ABC,ABD,ACD,BCD,BCE}。 (4)L4生成:由L3生成4-侯选集并通过扫描数据库得到它们的支持数C4={(ABCD,2) };挑选minsup_count>2的项目集组成4-频繁项目集L4={ABCD}。 (5)L5生成:由L4生成5-侯选集C5= ?, L5= ?,算法停止。 于是频繁大项集为{ABCD,BCE}。 4.3 Apriori算法的性能瓶颈问题 很显然,Apriori算法有两个致命的性能瓶颈: n 多次扫描事务数据库,需要很大的I/O负载。对每次k循环,侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项集包含10个项的话,那么就至少需要扫描事务数据库10遍。 n 可能产生庞大的侯选集。由Lk-1 产生k-侯选集Ck 是指数增长的,例如104 的1-频繁项集就有可能产生接近107 个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。 正因为如此,包括Agrawal在内的许多学者提出了Apriori算法的改进方法 ***************************改进算法*************************** (2)FP-tree算法 2000,Han等提出了一个称为FP-tree的算法[81]。这个算法只进行2次数据库扫描。它不使用侯选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成关联规则。 我们简单地描述利用FP-tree算法构造频繁模式树的过程如下: (a) 按Apriori算法,扫描数据库一次生成1-频繁集,并把它们按降序排列,放入L表中; (b) 创建根节点,并标志为null,扫描数据库一次,当得到数据库的一个项目集(即一个元组)时,就把它中的元素按L表的次序排列,然后递归调用FP_growth来实现FP_Tree增长。 下面的算法4-4给出了递归过程FP-growth(Tree,α)的较为正式描述。 算法4-4 Procedure FP-growth (Tree,α)- 频繁模式树的生成 (1) IF Tree contains a single path P THEN (2) FOR all combination (denoted asβ) to the nodes in the path P DO (3) generate patter β∪αwith support=minsupport of nodes inβ; (4) ELSE FOR all αi in the header of Tree DO BEGIN (5) generate patter β=αi∪αwith support=αi.support; (6) construct conditional pattern base and generate Treeβ; (7) IF Treeβ≠ф THEN CALL FP-growth (Treeβ, β); (8) END; 由于这个算法抽象程度较高,为了正确理解它,下面通过一个具体的实例来说明它的执行过程。对于表4-1所给出的样本数据库,我们实施FP-tree的算法,图4-1给出了执行过程。 首先,扫描数据库对每个项目生成支持度并按降序排列,简单记为{B5,C4,A3,D3,E3}。然后递归调用FP-growth,生成频繁模式树。 图4-1 FP-tree算法的执行过程示例 FP-tree算法只有两次数据库扫描,的确在减少挖掘所需的I/O代价方面进行了有益的探索。而且它不会有庞大的侯选集产生,减少了内存临时空间的占用。但是,它的问题是随着频繁模式树的增长可能使效率变得很差。我们看一个例子,对于表4-2给出的事务数据库,它最后生成的树为图4-2的样子。 表4-2 样本事务数据库 TID Itemset 12345 A,B,C,D,FB,C,EA,B,DA,B,FC,D,F 6 E,F 在这棵树中,共有一个表、15个节点和28个链接需要存储和管理。而数据库也不过只有6个项目集(每个项目集平均3个多项目)组成。因此,FP-Tree算法在一些情况下的内存存储空间是不可低估的,而且这种树结构是一种非线性结构,一般需要链表等形式存储,本身就增加了存储链接信息的额外代价。因此,探讨新的改进方法是有价值的。本章将介绍我们设计的ISS-DM算法,它是一个使用线性结构存储扫描信息、一次数据库扫描的高效关联规则生成算法。这个算法是基于项目序列集格空间及其操作的。这部分工作经过整理已被发表。( @0 y+ _9 @0 G$ N+ d" F
    zan

    0

    主题

    12

    听众

    126

    积分

    升级  13%

  • TA的每日心情
    奋斗
    2017-1-11 08:59
  • 签到天数: 35 天

    [LV.5]常住居民I

    国际赛参赛者

    社区QQ达人

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 01:44 , Processed in 0.435255 second(s), 57 queries .

    回顶部