第5次课关联规则new.ppt

《第5次课关联规则new.ppt》由会员分享，可在线阅读，更多相关《第5次课关联规则new.ppt（89页珍藏版）》请在三一文库上搜索。

1、第 5 章 关联规则,第5章 关联规则,主要内容,关联规则挖掘简介,关联规则基本模型,关联规则研究趋势,关联规则参考文献,第5章 关联规则,关联规则挖掘简介,关联规则基本模型,关联规则研究趋势,关联规则参考文献,主要内容,第5章 关联规则,关联规则挖掘简介,关联规则（Association Rule）是数据中所蕴含的一类重要规 律，对关联规则进行挖掘是数据挖掘中的一项根本性任务，甚至 可以说是数据库和数据挖掘领域中所发明的并被广泛研究的最为 重要的模型。,第5章 关联规则,关联规则挖掘简介,关联规则（Association Rule）反映一个事物与其他事物 之间的相互依存性和关联性。是对一个事

2、物和其它事物的相 互依存和关联关系的描述。若两个或多个变量的取值存在某 种规律，称为关联。关联规则是寻找在同一个事件中出现的 不同项的相关性。如果两个或者多个事物之间存在一定的关 联关系，那么，其中一个事物就能够通过其他事物预测到。,关联规则是数据挖掘中用于表示局部模式的最流行方法之 一。关联分析的目的是挖掘隐藏在数据间的相互关系，自动探 测以前未发现的蕴藏着的模式模式是一种局部概念，它反映的 是数据某一方面的信息。而模型则是对数据的全面描述。,第5章 关联规则,关联规则挖掘简介,典型的关联规则发现问题是对超市中的货篮数据 （Market Basket）进行分析。通过发现顾客放入货篮中的不同

3、商品之间的关系来分析顾客的购买习惯。（关联规则应用最适 合的应用案例） 货篮数据的特点：数据量巨大，数据稀疏。(行为百万级， 列至少是千级别的，行表示一次购买事件，列表示商店的商品) 对一个描述超市的数据集合来说，模式可能是“十分之一” 的顾客购买了酒和牛奶。,第5章 关联规则,关联规则挖掘简介,购物篮数据中，行表示顾客购买行为，列表示商店的商品。 若顾客 购买了某种商品，则表中表示为1，反之为0,第5章 关联规则,关联规则挖掘简介,关联规则 关联规则是对数据库中某些特定事件一起发生的概率的简单 陈述； 首先被Agrawal, Imielinski and Swami在1993年的SIGMOD

4、会议 上提出； 在事务、关系数据库中的项集和对象中发现频繁模式、关联 规则、相关性或者因果结构。 频繁模式是指数据库中频繁出现的项集。,SIGMOD：Special Interest Group on Management of Data,第5章 关联规则,关联规则挖掘简介,研究关联规则的目标：发现数据中的规律 超市中的什么产品经常会被一起购买；-啤酒与尿布 在购买了PC机后，顾客下一步一般购买什么产品； 如何自动对WEB文档分类； 用户上了CCTV网站后，一般将会去那些其他网站； 用户购买了“XXX”书后，一般还会购买什么书; 某一类纳税人在当月未纳税，则其下个月也不纳税的可能性,第5章 关

5、联规则,关联规则挖掘简介,关联规则特别适用于稀疏的数据集合。如购物篮等。 为简单起见，设所有变量都是二值的，则关联规则具有以下 的形式： 如果A=1，且B=1, 则C=1 的概率为p。 其中，A、B、C是二值变量。且 p=p(C=1|A=1,B=1) ， 即给定A=1，B=1时C=1的条件概率。P有时被称为规则的精度 或可信度。p(C=1，A=1，B=1) 称为支持度。 寻找规则结构的典型目标就是寻找满足以下约束的所有规则： 可信度p大于某个阈值pa，支持度大于某个阈值 ps。 例如寻找支持度大于0.05 ,可信度大于0.8的所有规则。,第5章 关联规则,关联规则挖掘简介,关于规则(Rule)

6、表示 规则是人工智能领域研究的知识表示方法中最古老，最经典 的一种表示方法。应用非常广泛。具有易于解释的优点。 规则是由左侧的命题（前提或者条件）和右侧的结论组成。 规则的含义是如果左侧为真，则右侧也为真。规则的左侧一般可 以是合取式（conjunction ）。 规则具有固有的离散性，也就是说，规则左右侧均为布尔陈 述。因此规则特别适合于离散型和范畴型变量建模。 概率（Probabilistic）规则将此定义修改为：如果左侧为真， 则右侧为真的概率是p。概率p实际上就是给定左侧后，右侧为真 的条件概率。,第5章 关联规则,关联规则挖掘简介,如何从数据中发现模式？ 若给定了表示模式的某种方式及

7、这种表示方式下的所有可能 模式。最原始的方法就是依次试验每种模式，并观察它是否在数 据中发生。 若模式的数量较小，此方法是可以接受的。但一般都不行， 例如前述超市的例子。假定有5000种商品（以0,1表示是否购买） 则可能的模式个数是25000个。（实际上是25000 -1） 若各个模式之间毫无关系。只好采用原始的方式。实际上， 模式都存在大量的结构，可以使用这些模式结构引导搜索。 通常各个模式之间都存在泛化关系。,第5章 关联规则,关联规则挖掘简介,关于泛化 如果只要模式出现在数据中，模式也一定出现在数据 中，则称模式 就是模式的泛化。 例如 模式 “至少有10%的顾客购买了香烟” 是 模式

8、“至少有10%的顾客购买了香烟和啤酒”的泛化。 使用模式中的泛化关系可以得到一种简单的算法来寻找 出现在数据中的所有特定类型的模式。,第5章 关联规则,关联规则挖掘简介,关于频繁项集 对于从变量A1, .,Ap观察到的0,1集合 关联规则的形式如下： (Ai1=1) (Ai2=1) (Aik=1)= Aik+1=1 可以简化为 (Ai1 Ai2 Aik=1) 像(Ai1=1) (Ai2=1) (Aik=1)这样的模式被称为 项集（itemset）,第5章 关联规则,关联规则挖掘简介,关于属性值-属性值离散化 若数据集的属性都是布尔值，则此数据集中挖掘的关联 规则都是布尔关联规则。其它属性可以进

9、行转换。可以将非布 尔值数据转换为布尔数据值。,第5章 关联规则,关联规则挖掘简介,关于属性值-属性值离散化 上图中，挖掘某一个具体的年龄和一个具体的收入间的关 联关系，由于属性取值的多样性，通常很难满足最小支持度和 最小可信度阈值指标。 并且一般来说，发现类似Age(41)=Salary(4320)之类的表达 显然没有多大意义。更多的情况是希望发现年龄段与收入范围 间的关系。因此，可以将数量属性值划分为若干区间，按照区 间的划分将一个数量属性分解为若干个布尔属性。 例如将年龄按照20，30），30，40）， 收入按区间2000，3000），3000，4000）， 进行划分。,第5章 关联规则

10、,关联规则挖掘简介,关于属性值-属性值离散化,第5章 关联规则,主要内容,关联规则挖掘简介,关联规则基本模型,关联规则研究趋势,关联规则参考文献,第5章 关联规则,IBM公司Almaden研究中心的R.Agrawal首先提出关联规则模 型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。 其中，Apriori是关联规则模型中的经典算法。 给定一组事务； 产生所有的关联规则； 满足最小支持度和最小可信度。,关联规则的基本模型及算法,设I=i1, i2, im为所有项目的集合，D为事务数据库，事 务T是一个项目子集（TI）。每一个事务具有唯一的事务标识 TID。设A是一个由项目构

11、成的集合，称为项集。事务T包含项集 A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。 项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项 集的支持度。如果项集的支持度超过用户给定的最小支持度阈值， 就称该项集是频繁项集（或大项集）。,第5章 关联规则,关联规则的基本模型及算法,第5章 关联规则,关联规则的基本模型及算法,关联规则是形如XY的逻辑蕴含式，其中XI，YI， 且XY=。如果事务数据库D中有s%的事务包含XY，则 称关联规则XY的支持度为s%，实际上，支持度是一个概率值。 若项集X的支持度记为support (X)，规则的信任度为 support (XY)suppo

12、rt (X)。这是一个条件概率P (Y | X)。 也就是： support (XY)=P (X Y) confidence (XY)=P (Y | X),第5章 关联规则,关联规则的基本模型及算法,关联规则的挖掘一般分为两个步骤。 （1）找出所有支持度大于等于最小支持度阈值的频繁项集。 （2）由频繁项集生成满足可信度阈值的关联规则。 第一步工作相当费时，第二步相对容易得多。所以关联规则算法 的性能主要由第一步决定。,第5章 关联规则,关联规则的基本模型及算法,第5章 关联规则,关联规则的基本模型及算法,关联规则的典型数据挖掘算法组件： 1 任务：描述变量之间的关联关系； 2 结构：用概率表示

13、的“关联规则”模式； 3 评分函数：可信度与支持度的阈值； 4 搜索方式：系统搜索，带剪枝的广度优先； 5 数据管理技术：多重线性扫描。,第5章 关联规则,关联规则的基本模型及算法,关于评分函数 关联规则的评分函数是简单的二择一函数。有两个阈值： 可信度Pa，支持度Ps。 Ps是规则支持度的下限。当我们想要至少覆盖10%时，Ps=.1 Pa是规则可信度的下限。当我们想要精度不低于90%，Pa=.9 若一个模式满足上述两个条件，则得分为1，否则为0。 因此，算法的目标就是寻找得分为1的规则。 所有关联规则的数量非常巨大，前面提到5000种商品共有25000 种模式。但可用评分函数的优势，可以将平

14、均运行时间将到一个可 以接受的范围。,第5章 关联规则,关联规则的基本模型及算法,关于评分函数 注意若P(A=1) Ps，且P(B=1) Ps中任何一个成立。则 P(A=1,B=1) Ps。 因此，可以首先找概率大于Ps的所有单个事件（线性扫描一 次）。若事件（或一组事件）大于Ps，则称其为频繁项集（频繁 1项集）。然后，对这些频繁事件所有可能对作为容量为2的候选 频繁集合。,第5章 关联规则,关联规则的基本模型及算法,关于评分函数： 更一般的情况下。 当从容量为K-1的频繁项集生成容量为K的频繁项集时，可 以剪除任何容量为K的集合。只要它包含的K-1项的子集，且该 子集在K-1级是不频繁的。

15、 例如，若有容量为2的频繁项集（A=1，B=1 ）及 （B=1,C=1）。 将其组合为容量为3的频繁项集（ A=1，B=1，C=1） 若存在（ A=1，B=1 ）是不频繁的，则 （ A=1，B=1，C=1）是不频繁的，因此可以将其剪除。,第5章 关联规则,关联规则的基本模型及算法,关于评分函数 注意这种剪除可在不直接搜索数据的情况下进行，因此提高 了计算速度。 确定了修剪后的容量为K的频繁项集后，对数据库再执行一 次线性扫描以确定那些集合是频繁的。 然后将确定后的容量为K的频繁项集进行组合，以生成所有 可能的含有K+1 个事件的频繁集合，然后再修剪，再扫描一次数 据，直到无法产生新的频繁集。,

16、第5章 关联规则,关联规则的基本模型及算法,频繁项集的挖掘问题可以用图形形式表示。所有项集能构成的 组合用图所示的集合枚举树（Set-enumeration Tree）表示。 集合枚举树是一颗排序树。树中每个节点表示一种项集组合。树 根是空集。以下依次为1项集，2项集，3项集，. 频繁项集的数据挖掘问题实际上是从集合枚举树中找一条分割线 使分割线上的项集是频繁的，分割线下的项集是非频繁的。为找 出此分割线，需要以一定的策略遍历该树。,第5章 关联规则,关联规则的基本模型及算法,a b c d e,ab ac ad ae bc bd be cd ce de,abc abd abe acd ace

17、 ade bcd bce bde cde,abcd abce abde acde bcde,abcde,第5章 关联规则,关联规则的基本模型及算法,支持度和可信度,查找所有的规则 X & Y Z 具有最小支持度和可信度 支持度, s, 一次交易中包含X 、 Y 、 Z的可能性 可信度, c, 包含X 、 Y的交易中也包含Z的条件概率,设最小支持度为50%, 最小可信度为 50%, 则可得到 A C (50%, 66.6%) C A (50%, 100%),买尿布的客户,二者都买的客户,买啤酒的客户,第5章 关联规则,关联规则的基本模型及算法,Let min_support = 50%, min

18、_conf = 50%: A C (50%, 66.7%) C A (50%, 100%),第5章 关联规则,关联规则的基本模型及算法,For rule A C: support = support(AC) = 50% confidence = support(AC)/support(A) = 66.6%,Min. support 50% Min. confidence 50%,第5章 关联规则,关联规则的基本模型及算法,Apriori算法,Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法.算法名字是缘于算法使用了频繁项集的性质这一先验知识. 思想: Apriori 使用了一

19、种称作level-wise搜索的迭代方法,其中k-项集被用作寻找(k+1)-项集. 首先,找出频繁1-项集,以L1表示.L1用来寻找L2,即频繁2-项集的集合.L2用来寻找L3,以此类推,直至没有新的频繁k-项集被发现.每个Lk都要求对数据库作一次完全扫描,第5章 关联规则,关联规则的基本模型及算法,Apriori算法-频繁项集,为了避免计算所有项集的支持度（实际上频繁项集只占很少 一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项 集的集合记为Ck ，频繁k项集的集合记为Lk ，m个项目构成的k项 集的集合为 ，则三者之间满足关系Lk Ck 。构成潜在频繁 项集所遵循的原则是

20、“频繁项集的子集必为频繁项集”。,第5章 关联规则,关联规则的基本模型及算法,Apriori算法-关联规则的性质,性质1：频繁项集的子集必为频繁项集。 性质2：非频繁项集的超集一定是非频繁的。 Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。,第5章 关联规则,关联规则的基本模型及算法,Apriori算法-关联规则的性质,Apriori算法是反单调的 即一个集合如果不能通过测试，则该集合

21、的所有超集也 不能通过相同的测试。,第5章 关联规则,关联规则的基本模型及算法,a b c d e,ab ac ad ae bc bd be cd ce de,abc abd abe acd ace ade bcd bce bde cde,abcd abce abde acde bcde,abcde,若c,d,e是频繁的，则其 子集c,d、 c,e、 d, e c、d 、e一定是频繁的 反之，如果一个集合是非频 繁的，则其超级必然也是非 频繁的,第5章 关联规则,关联规则的基本模型及算法,关联规则性质的应用-啤酒尿布问题,第5章 关联规则,关联规则的基本模型及算法,关联规则性质的应用-啤酒尿布

22、问题,支持度60%。计数3次以上,支持度不够被删除的项,可乐、鸡蛋被丢弃，注意， 根据性质2保证了所有非频 繁的一项集其超集都是非 频繁的。因此产生2项集时 候选集项数由 变为,若不采用先验规则，则全部搜索需要产生的项是 采用先验规则，需要产生的项数时 候选项数降低了68%,第5章 关联规则,关联规则的基本模型及算法,(1) L1=频繁1项集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集 (4) for all transactions tD do begin (5) Ct=subset(Ck,t); /t

23、中包含的潜在频繁项集 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.countminsup (10) end; (11) Answer=,第5章 关联规则,关联规则的基本模型及算法,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,第5章 关联规则,关联规则的基本模型及算法,为什么需要支持度和可信度？ 支持度是一种重要的度量，因为支持度低的规则可能只是 偶然出现。从商务角度看，低支持度的规则多半也是不令人感 兴趣的，因为对顾客很少同时购买

24、的商品进行促销没有意义。 另一方面，可信度度量通过规则进行推理的可靠性。对于 给定的规则 X -Y，可信度越高，Y在包含X的事务中出现的 可能性就越大。可信度也提供了Y在给定X下的条件概率的估计,第5章 关联规则,关联规则的基本模型及算法,应用实例-图书推荐系统关联规则挖掘,图书馆每天都有大量书刊被借阅，也有大量的书刊经采编入库，在业务、 管理和服务中形成的大量数据存贮在图书馆自动化系统的数据库中，但这些 由各项业务操作而产生的数据，仅仅是工作记录和传统统计的数据源，一般 用来做统计流通量、读者或书刊排行等，其利用比较有限。随着计算机水平 的提高和数据挖掘技术的发展，这些在以前看来没有太大价值

25、的数据，已被 认识到可以用做深层次研究与服务。通过浏览一些读者的借阅史，发现在读 者曾经借阅过的众多图书当中，往往隐藏着图书之间的关联性。例如，读者 借阅了一本数据结构的图书，在他的借阅史中往往也会发现一本c语言 程序设计或者其它程序语言设计类的图书。这表明，图书馆可以自觉地利 用数据挖掘相关技术，从大量的流通数据中发现图书间的关联性，进而为每 个读者推荐最适宜的图书提供依据。图书馆自动化系统记录的流通数据可以 作为关联规则发现的数据 来源，经过数据预处理将流通数据”清洗”，以构建 适合挖掘的事务数据库，数据库中的每条记录就是每位读者在一段时期内借 阅过的图书，然后利用数据挖掘中的关联规则技术

26、，挖掘出最适宜读者的书。,第5章 关联规则,关联规则的基本模型及算法,应用实例-图书推荐系统关联规则挖掘,第5章 关联规则,关联规则的基本模型及算法,应用实例-图书推荐系统关联规则挖掘,第5章 关联规则,关联规则的基本模型及算法,应用实例-图书推荐系统关联规则挖掘,第5章 关联规则,关联规则的基本模型及算法,应用实例-图书推荐系统关联规则挖掘,由此得到最大频繁项集L3b，c，e，找到关联规则bc_+e，其置信度为100 ，满足最小置信度。在实际工作中，图书e就可作为推荐给此读者的参考书目，为读者提供个性化的服务。,第5章 关联规则,关联规则的基本模型及算法,示例2 AllElectronics

27、某分店的事务数据,在某超市数据库系统中包含以下的数据，请根据Apriori算法发现其候选项集及 频繁项集，并列举说明或画图说明。要求最小支持度计数为2。,第5章 关联规则,关联规则的基本模型及算法,示例2 AllElectronics某分店的事务数据,第5章 关联规则,关联规则的基本模型及算法,加权关联规则挖掘,传统的关联规则挖掘算法通常都认为数据库里每个项目都有 相同的重要性，没有主要、次要之分。但在实际中，往往存在一 类这样的情况：用户对每个项目的看重程度不一样，有的项目是 用户最看重、最关心的，有的项目是用户关注性不大，因此需要 引进权重的概念。,第5章 关联规则,关联规则的基本模型及算

28、法,设 是项的集合，每个项都有一个权值与之对应。它们的权值分别是w1,w2,wk（wi 0,1）。事先指定最小加权支持度阈值为 wminsup和最小置信度阈值 minconf。 对于项目集X，如果 wsup(X)wminsup，则 X 是加权频繁的。 形如X Y 的关联规则的加权支持度为： 置 信 度 的 定 义 仍 然 沿 用 Apriori算 法 里 的 定 义 ， 即 ：conf (X Y) = sup(X Y)/sup(X ) 。,第5章 关联规则,关联规则的基本模型及算法,对于项目集 X、Y， ，X Y = ，如果有 wsup( X Y )wminsup， 且 conf(XY)min

29、conf， 则称 XY 是一条加权关联规则。,加权支持度 (1)、平均值： (2)、归一化： (3)、最大值：,第5章 关联规则,关联规则的基本模型及算法,加权关联规则挖掘-权值的设定,第5章 关联规则,关联规则的基本模型及算法,先不考虑项目的权值，利用传统的 Apriori 算法找出支持度 不小于最小加权支持度的所有的频繁项目集。由于项目集的 权值小于 1，所以项目集的加权支持度一定小于支持度，所 以生成的频繁集一定是加权频繁集的超集。 (2) 计算所生成频繁项目集中所有项目集的加权支持度，并把加 权支持度小于最小加权支持度的项目集删除，从而得到所有 加权频繁集。 (3) 利用加权频繁集来生

30、成所有的加权关联规则。,第5章 关联规则,关联规则的基本模型及算法,Apriori算法的核心: 用频繁的(k 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 扫描数据库次数： 如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描,Apriori算法的瓶颈,Apriore算法小结，两个问题： 1、复杂的候选建立过程消耗了大量的时间、空间和内容； 2、对数据库的多遍扫描；,第5章 关联规则,关联规则的基本模型及算法,事务压缩: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集 基于划分: 一个项集

31、要想在整个数据库中是频繁的，那么他至少在数据库 的一个分割上是频繁的。 采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法 动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他 的所有子集都是频繁的。 基于哈希表的算法,效率问题,主要内容,关联规则挖掘简介,关联规则基本模型,关联规则研究趋势,关联规则参考文献,第5章 关联规则,关联规则研究趋势,目前主要的研究集中在改进关联规则算法的效率： 1）减少对数据库扫描的遍数； 2）抽样指导方法； 3）并行化 4）对结构模型增加额外的约束,第5章 关联规则,关联规则研究趋势,减少对数据库扫描的遍数,FP树是继Apriori之后关联规

32、则挖掘的一个里程碑。频繁项集 的建立仅经过两遍数据库扫描，并且不产生候选建立过程。FP树 是一种扩展的前缀树结构，存储关键的和频繁模式的数量。节点 中的树仅仅包含频繁1项集。FP树的优点表现在三个方面： FP树是一种对原始数据库数据的压缩表达，仅有频繁项可以 加入到树中；其他不相关的数据被剪枝； 该算法仅仅扫描数据库两遍。 FP树采用分治方法减少了后续的条件FP树的数量。,第5章 关联规则,关联规则研究趋势,抽样指导方法,抽样方法一般包括两个步骤： 1、获取数据库的抽样并获得抽样的关联规则； 2、将上述结果在数据库中验证。,规则集,Validation,第5章 关联规则,关联规则研究趋势,抽样

33、指导方法,1 Toivonen. H. Sampling Large Databases for Association Rules, The VLDB Journal 1996,134-145 2 Pathasarathy. A. Efficient Progressive Sampling for Association Rules. ICDM 2002: 354-361 3 Chuang. K. Progressive Sampling for Association Rules Based on Sampling Error Estimation. Lecture Notes in C

34、omputer Science, 2005, 35(18):505-515 4 Li. Y. Effective Sampling for Mining Association Rules. Lecture Notes in Computer Science, 2004(1): 391-401,参考阅读文献,第5章 关联规则,关联规则研究趋势,并行化,利用并行系统可以利用其高速和高存储特点。FDM算法是 Apriori算法的并行化实现（采用SN结构）。从研究上看，在此 方面可以有所作为。,第5章 关联规则,关联规则研究趋势,关联规则挖掘的约束,多数发现频繁模式的数据挖掘技术针对数据集合。一般，

35、 其目标是发现频繁出现在数据集中（超过用户定义的域值）的 所有模式。但用户往往想要通过增加额外的约束限制被发现的 模式，例如对模式结构的约束。 数据挖掘系统应该运用这些约束加速数据挖掘的过程。应 用到约束驱动的模式发现主要分以下几类： 1、后处理技术。在挖掘过程完成后，将不满足用户约束要 求的模式过滤掉； 2、模式过滤技术。将约束集成到数据挖掘过程中，只建立 满足用户约束的模式； 3、数据集合过滤。将不满足用户约束的数据集合过滤掉。,第5章 关联规则,关联规则研究趋势,关联规则挖掘的约束,参考阅读文献,1 Wojciechpwski.M。Dataset Filtering Techniques

36、 in Constraint-Based Frequent Pattern Mining. Lecture Notes in Computer Science. 2002, 77-83 2 Tien Dung Do. Mining Frequent Itemsets with Category-based Constraints. Lecture Notes in Computer Science,2003,76-86 3 Das.A. Rapid Association Rule Mining. In Proceedings of the tenth International confer

37、ence on Information and Knowledge Management, 474-481,第5章 关联规则,FP-TREE,用Frequent-Pattern tree (FP-tree) 结构压缩数据库, -高度浓缩，同时对频繁集的挖掘又完备的 - 避免代价较高的数据库扫描 开发一种高效的基于FP-tree的频繁集挖掘算法 -采用分而治之的方法学：分解数据挖掘任务为小任务 - 避免生成关联规则: 只使用部分数据库!,关联规则研究趋势,第5章 关联规则,FP-TREE,FP树是一种输入数据的压缩表示，它通过逐个读入事务，并 把每个事务映射到FP树种的一条路径来构造。由于不同的

38、事务可 能有若干个相同的项，因此它们的路径可能部分重叠。路径相互 重叠越多，使用FP树结构获得的压缩效果越好。,关联规则研究趋势,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）,问题：获取所有频繁项集，使得其支持度大于3,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）,回顾Apriori算法,L1,C2,L2,C3,L3,候选键产生,1、连接步 2、剪枝步,2项集 建立,3项集 建立,频繁项集产生,计算步骤,问题：处理庞大的 候选集合,问题：重复扫描数据 表检查候选模式,第5章 关联规则,关联规则研究趋势,利用FP-TRE

39、E方法实现频繁项集挖掘（示例）,FP树,扫描数据库表两次 第1次获取并存储所有的关于数据结构的基本信息，得到 频繁1项集； 第2次建立FP树.,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）,(1),(2),(3),门槛值=3,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:1,b:1,d:1,e:1,f:1,g:1,读入TID100后,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:2,b:1,d:1,e:1,f:1,g:1,读入TID200后,f:1,g:1,第5章

40、关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:2,b:1,d:1,e:1,f:1,g:1,读入TID300后,f:1,g:1,b:1,d:1,e:1,f:1,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:3,b:2,d:2,e:1,f:1,g:1,读入TID400后,f:1,g:1,b:1,d:1,e:1,f:1,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:4,b:3,d:2,e:1,f:1,g:1,读入TID500后,f:1,g:1,b:1,d:1,e:1,f:

41、1,e:1,g:1,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:4,b:3,d:2,e:1,f:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,e:1,g:1,G的FP树条件库,（a:1, b:1, d:1, e:1, f:1, g:1,第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:4,b:3,d:2,e:1,f:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,e:1,g:1,G的FP树条件库,（a:1, b:1, d:1, e:1, f:1, g:1), (a:1, b:1,

42、 e:1, g:1),第5章 关联规则,关联规则研究趋势,利用FP-TREE方法实现频繁项集挖掘（示例）, ,a:4,b:3,d:2,e:1,f:1,g:1,f:1,g:1,b:1,d:1,e:1,f:1,e:1,g:1,G的FP树条件库,（a:1, b:1, d:1, e:1, f:1, g:1), (a:1, b:1, e:1, g:1), (a:1, f:1, g:1),门槛值=3,第5章 关联规则,FP-TREE结构的优势,完备: 不会打破交易中的任何模式 包含了频繁模式挖掘所需的全部信息 紧密 去除不相关信息不包含非频繁项 支持度降序排列: 支持度高的项在FP-tree中共享的机会也

43、高 决不会比原数据库大（如果不计算树节点的额外开销),关联规则研究趋势,第5章 关联规则,用FP-TREE挖掘频繁集,基本思想 (分而治之) 用FP-tree递归增长频繁集 方法 对每个项，生成它的 条件模式库, 然后是它的 条件 FP-tree 对每个新生成的条件FP-tree，重复这个步骤 直到结果FP-tree为空, 或只含唯一的一个路径 (此路径的每个子 路径对应的项集都是频繁集),关联规则研究趋势,第5章 关联规则,主要步骤,为FP-tree中的每个节点生成条件模式库 用条件模式库构造对应的条件FP-tree 递归构造条件 FP-trees 同时增长其包含的频繁集 如果条件FP-tr

44、ee只包含一个路径，则直接生成所包含的频繁集。 如果条件FP-tree包含多个路径，则采用混合的方法,关联规则研究趋势,第5章 关联规则,关联规则研究趋势,在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。 R.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。 Lin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。,第5章 关联规则,关联规则研究趋势,数据

45、挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。 Agrawal首先提出事务缩减技术，Han和Park等人也分别在减小数据规模上做了一些工作。 抽样的方法是由Toivonen提出的。 Brin等人采用动态项集计数方法求解频繁项集。 Aggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。,第5章 关联规则,关联规则研究趋势,关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。 还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。 Guralnik提出顺序时间段问题的形式描述语言，

46、以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。 最大模式挖掘是Bayardo等人提出来的。,第5章 关联规则,关联规则研究趋势,随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。 B.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。 贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（Calendric Association Rules）算法，用以进行市场货篮分析。 Fang等人给出冰山查询数据挖掘算法。,第5章 关联

47、规则,关联规则研究趋势,T.Hannu等人把负边界引入规则发现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。 Srikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。 Zakia还用项集聚类技术求解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。 CAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。,第5章 关联规则,关联规则研究趋势,Cheung等人提出关联规则的增量算法。 Thomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据挖掘算法。 Oates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。,第5章 关联规则,关联规则研究趋势,Agrawal R, Imielinski T, and