精华内容
下载资源
问答
  • 关联规则挖掘Association Rule Mining是数据挖掘中研究较早而且至今仍活跃研究方法之一 最早是由Agrawal等人提出1993最初提出动机是针对购物篮分析Basket Analysis问题提出其目的是为了发现交易数据库...
  • 关联规则挖掘——Apriori算法的基本原理以及改进

    万次阅读 多人点赞 2016-11-24 17:09:06
    关联规则挖掘的一个典型例子就是购物篮分析,该过程通过发现顾客放入其购物篮中不同商品之间的联系,分析出顾客的购买习惯,通过了解哪些商品频繁地被顾客同时买入,能够帮助零售商制定合理的营销策略。购物篮事务的...

    问题引入

    关联规则挖掘发现大量数据中项集之间有趣的关联或者相互联系。关联规则挖掘的一个典型例子就是购物篮分析,该过程通过发现顾客放入其购物篮中不同商品之间的联系,分析出顾客的购买习惯,通过了解哪些商品频繁地被顾客同时买入,能够帮助零售商制定合理的营销策略。购物篮事务的例子如下图所示:
    购物篮事务的例子
    例如:在同一次去超级市场时,如果顾客购买牛奶,同时他也购买面包的可能性有多大?
    通过帮助零售商有选择地经销和安排货架,这种信息会引导销售。零售商有两种方法可以进行安排货架,第一种方法是将牛奶和面包尽可能的放的近一些,方便顾客自取,第二种方法是将牛奶和面包放的远一些,顾客在购买这两件物品的时候,这中间货架上的物品也会被顾客选择购买。这两种方法都可以进一步刺激消费。但是,如何发现牛奶和面包之间的关联关系呢?Apriori算法可以进行关联规则挖掘。

    算法中的基本概念

    1、项集和K-项集

    令I={i1,i2,i3……id}是购物篮数据中所有项的集合,而T={t1,t2,t3….tN}是所有事务的集合,每个事务ti包含的项集都是I的子集。在关联分析中,包含0个或多个项的集合称为项集。如果一个项集包含K个项,则称它为K-项集。空集是指不包含任何项的项集。例如,在购物篮事务的例子中,{啤酒,尿布,牛奶}是一个3-项集。

    2、支持度计数

    项集的一个重要性质是它的支持度计数,即包含特定项集的事务个数,数学上,项集X的支持度计数σ(X)可以表示为
    σ(X)=|{ti|X⊆ti,ti∈T}|
    其中,符号|*|表示集合中元素的个数。
    在购物篮事务的例子中,项集{啤酒,尿布,牛奶}的支持度计数为2,因为只有3和4两个事务中同时包含这3个项。

    3、关联规则

    关联规则是形如X→Y的蕴含表达式,其中X和Y是不相交的项集,即X∩Y=∅。
    关联规则的强度可以用它的支持度(support)和置信度(confidence)来度量。支持度确定规则可以用于给定数据集的频繁程度,而置信度确定Y在包含X的事务中出现的频繁程度。
    支持度(s)和置信度(c)这两种度量的形式定义如下:
    s(X→Y)=σ(X∪Y)/N
    c(X→Y)=σ(X∪Y)/σ(X)
    其中, σ(X∪Y)是(X∪Y)的支持度计数,N为事务总数,σ(X)是X的支持度计数。

    Example

    在购物篮事务的例子中,考虑规则{牛奶,尿布}→{啤酒}。由于项集{牛奶,尿布,啤酒}的支持度计数为2,而事务的总数为5,所以规则的支持度为2/5=0.4。
    规则的置信度是项集{牛奶,尿布,啤酒}的支持度计数与项集{牛奶,尿布}支持度技术的商,由于存在3个事务同时包含牛奶和尿布,所以规则的置信度为2/3=0.67。

    关联规则发现

    给定事务的集合T,关联规则发现是指找出支持度大于等于minsup (最小支持度)并且置信度大于等于minconf(最小置信度)的所有规则,minsup和minconf是对应的支持度和置信度阈值。

    关联规则的挖掘是一个两步的过程:
    (1)频繁项集产生:其目标是发现满足最小支持度阈值的所有项集(至少和预定义的最小支持计数一样),这些项集称作频繁项集。
    (2)规则的产生:其目标是从上一步发现的频繁项集中提取所有高置信度的规则,这些规则称作强规则。(必须满足最小支持度和最小置信度)

    Apriori算法介绍

    Apriori算法的实质使用候选项集找频繁项集。
    Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的名字基于这样的事实:算法使用频繁项集性质的先验知识, 正如我们将看到的。Apriori 使用一种称作逐层搜索的迭代方法,k-项集用于探索(k+1)-项集。首先,找出频繁1-项集的集合。该集合记作L1。L1 用于找频繁2-项集的集合L2,而L2 用于找L3,如此下去,直到不能找到频繁k-项集。找每个Lk 需要一次数据库扫描。

    Apriori性质

    Apriori性质:频繁项集的所有非空子集都必须也是频繁的。 Apriori 性质基于如下观察:根据定义,如果项集I不满足最小支持度阈值s,则I不是频繁的,即P(I)< s。如果项A添加到I,则结果项集(即I∪A)不可能比I更频繁出现。因此, I∪A也不是频繁的,即 P(I∪A)< s 。
    该性质属于一种特殊的分类,称作反单调,意指如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试。称它为反单调的,因为在通不过测试的意义下,该性质是单调的。

    先验定理

    先验定理:如果一个项集是频繁的,则它的所有子集一定也是频繁的。

    (关于先验定理、单调与反单调可以参考下面的例子理解)
    先验定理
    如图所示,假定{c,d,e}是频繁项集。显而易见,任何包含项集{c,d,e}的事务一定包含它的子集{c,d},{c,e},{d,e},{c},{d}和{e}。这样,如果{c,d,e}是频繁的,则它的所有子集一定也是频繁的。

    反单调性
    如果项集{a,b}是非频繁的,则它的所有超集也一定是非频繁的。即一旦发现{a,b}是非频繁的,则整个包含{a,b}超集的子图可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝。
    这种剪枝策略依赖于支持度度量的一个关键性质,即一个项集的支持度绝不会超过它的子集的支持度。这个性质也称支持度度量的反单调性

    挖掘频繁项集

    Apriori算法的关键是如何用Lk-1找Lk?由下面的两步过程连接和剪枝组成。
    连接步:为找Lk,通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。设l1和l2是Lk-1中的项集。记号li[j]表示li的第j项(例如,l1[k-2]表示l1的倒数第3项)。为方便计,假定事务或项集中的项按字典次序排序。执行连接Lk-1 Lk-1;其中,Lk-1的元素是可连接的,如果它们前(k-2)个项相同;即,Lk-1的元素l1和l2是可连接的,如果(l1[1]=l2[1])∧(l1[2]=l2[2])∧…∧(l1[k-2]=l2[k-2])∧(l1[k-1]< l2[k-1])。条件(l1[k-1]< l2[k-1])是简单地保证不产生重复。连接l1和l2产生的结果项集是l1[1]l1[2]…l1[k-1]l2[k-1]。
    剪枝步:Ck是Lk的超集;即,它的成员可以是频繁的,也可以不是频繁的,但所有的频繁k-项集都包含在Ck中。扫描数据库,确定Ck中每个候选的计数,从而确定Lk(即,根据定义,计数值不小于最小支持度计数的所有候选是频繁的,从而属于Lk)。然而,Ck可能很大,这样所涉及的计算量就很大。为压缩Ck,可以用以下办法使用Apriori性质:任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。因此,如果一个候选k-项集的(k-1)-子集不在Lk-1中,则该候选也不可能是频繁的,从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。

    Apriori算法

    算法6.2.1(Apriori)  使用逐层迭代找出频繁项集
    输入:事务数据库D;最小支持度阈值。
    输出:D中的频繁项集L。
    方法:
    1) L1 = find_frequent_1_itemsets(D); //找出频繁1-项集的集合L1
    2) for(k = 2; Lk-1 ≠ ∅; k++) { //产生候选,并剪枝
    3) Ck = aproiri_gen(Lk-1,min_sup); 
    4) for each transaction t∈D{ //扫描D进行候选计数
    5) Ct = subset(Ck,t); //得到t的子集
    6) for each candidate c∈Ct
    7) c.count++; //支持度计数
    8) } 
    9) Lk={c∈Ck| c.count ≥min_sup} //返回候选项集中不小于最小支持度的项集
    10)  } 
    11)  return L = ∪kLk;//所有的频繁集
    
    第一步(连接 joinProcedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support) 
    1) for each itemset l1∈Lk-1
    2) for each itemset l2∈Lk-1
    3) if(l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]<l2[k-1]) then{ 
    4) c = l1 l2; //连接步:l1连接l2
                   //连接步产生候选,若K-1项集中已经存在子集c,则进行剪枝
    5) if has_infrequent_subset(c,Lk-1) then
    6) delete c; //剪枝步:删除非频繁候选
    7) else add c to Ck; 
    8) } 
    9) return Ck; 
    
    第二步:剪枝(prune)
    Procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent (k-1)-itemset) //使用先验定理
    1) for each (k-1)-subset s of c 
    2) if cLk-1 then
    3) return TRUE; 
    4) return FALSE; 
    

    由频繁项集产生关联规则

    一旦由数据库D中的事务找出频繁项集,由它们产生强关联规则是直接了当的(强关联规则满足最小支持度和最小置信度)。对于置信度,可以用下式,其中条件概率用项集支持度计数表示。
    confidence(A→B)=P(A│B)=support(A∪B)/support(A)
    其中,support(A∪B)是(A∪B)的支持度计数,support(A)是A的支持度计数。
    根据该式,关联规则可以产生如下:
    ƒ 1、对于每个频繁项集l,产生l的所有非空子集。
    ƒ 2、对于l的每个非空子集s,如果support(l)/support(s) ≥min_conf,则输出规则“s⇒(l-s)”。其中,min_conf是最小置信度阈值。
    由于规则由频繁项集产生,每个规则都自动满足最小支持度。频繁项集连同它们的支持度预先存放在hash表中,使得它们可以快速被访问。

    Apriori算法的实例

    问题:数据库中有9个事务,即|D| = 9。Apriori假定事务中的项按字典次序存放。我们使用下图解释Apriori算法发现D中的频繁项集。
    这里写图片描述

    分析与解:

    (一)、挖掘频繁项集

    1、在算法的第一次迭代,每个项都是候选1-项集的集合C1的成员,算法简单地扫描所有的事务,对每个项的出现次数计数。
    2、假定最小事务支持计数为2(即,minsup=2/9=22%)。可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。
    C1与L1的生成
    3、为发现频繁2-项集的集合L2,算法使用L1 L1产生候选2-项集的集合C2。
    4、下一步,扫描D中事务,计算C2中每个候选项集的支持计数。
    5、确定频繁2-项集的集合L2,它由具有最小支持度的C2中的候选2-项集组成。
    【注】 L1 L1等价于L1×L1,因为Lk Lk的定义要求两个连接的项集共享k-1个项。
    C2与L2的生成结果
    6、候选3-项集的集合C3的产生详细地列在图中。首先,令C3 = L2 L2 = {{I1,I2,I3}, {I1,I2,I5}, {I1,I3,I5}, {I2,I3,I4}, {I2,I3,I5}, {I2,I4,I5}}。根据Apriori性质,频繁项集的所有子集必须是频繁的,我们可以确定后4个候选不可能是频繁的。因此,我们把它们由C3删除,这样,在此后扫描D确定L3时就不必再求它们的计数值。注意,Apriori算法使用逐层搜索技术,给定k-项集,我们只需要检查它们的(k-1)-子集是否频繁。

    【L2 L2连接生成C3的过程】
    1.连接:C3= L2 L2={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}  {{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}} = {{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}
    2.使用Apriori性质剪枝:频繁项集的所有子集必须是频繁的。存在候选项集,其子集不是频繁的吗?
    ƒ{I1,I2,I3}的2-项子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-项子集都是L2的元素。因此,保留{I1,I2,I3}在C3中。
    ƒ{I1,I2,I5}的2-项子集是{I1,I2},{I1,I5}和{I2,I5}。{I1,I2,I5}的所有2-项子集都是L2的元素。因此,保留{I1,I2,I5}在C3中。
    ƒ{I1,I3,I5}的2-项子集是{I1,I3},{I1,I5}和{I3,I5}。{I3,I5}不是L2的元素,因而不是频繁的。这样,由C3中删除{I1,I3,I5}。
    ƒ{I2,I3,I4}的2-项子集是{I2,I3},{I2,I4}和{I3,I4}。{I3,I4}不是L2的元素,因而不是频繁的。这样,由C3中删除{I2,I3,I4}。
    ƒ{I2,I3,I5}的2-项子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素,因而不是频繁的。这样,由C3中删除{I2,I3,I5}。
    ƒ{I2,I4,I5}的2-项子集是{I2,I4},{I2,I5}和{I4,I5}。{I4,I5}不是L2的元素,因而不是频繁的。这样,由C3中删除{I2,I3,I5}。
    3.这样,剪枝后C3 = {{I1,I2,I3},{I1,I2,I5}}

    7、扫描D中事务,以确定L3,它由具有最小支持度的C3中的候选3-项集组成。

    C3与L3的生成过程

    8、算法使用L3 L3产生候选4-项集的集合C4。尽管连接产生结果{{I1,I2,I3,I5}},这个项集被剪去,因为它的子集{I1,I3,I5}不是频繁的。这样,C4=∅,因此算法终止,找出了所有的频繁项集。

    (二)、由频繁项集产生关联规则

    假定数据包含频繁项集l={I1,I2,I5},可以由l产生哪些关联规则?l的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2}和{I5}。结果关联规则如下,每个都列出置信度。
    I1∩I2→I5, confidence=2/4=0.5=50%
    I1∩I5→I2, confidence=2/2=1=100%
    I2∩I5→I1, confidence=2/2=1=100%
    I1→I2∩I5, confidence=2/6=0.33=33%
    I2→I1∩I5, confidence=2/7=0.29=29%
    I5→I1∩I2, confidence=2/2=1=100%
    如果最小置信度阈值为70%,则只有2、3和最后一个规则可以输出,因为只有这些才是强规则。

    优缺点

    优点

    使用先验性质,大大提高了频繁项集逐层产生的效率;简单易理解;数据集要求低。

    缺点

    1、候选频繁K项集数量巨大。
    2、在验证候选频繁K项集的时候,需要对整个数据库进行扫描,非常耗时。

    改进算法

    算法思想:

    上面的原始算法中由Ck(Lk-1直接生成的)到Lk经过了两步处理,第一步根据Lk-1进行裁剪,第二步根据minsupport裁剪。上面提到的两个提高效率的方法都是基于第一步的。当经过联接生成K维数据项集时,判断它的K-1维子集是否存在于Lk-1中,如果不在直接删除。这样每生成一个K维数据项集时,就要搜索一遍Lk-1。改进算法的思想就是只需要搜索一遍Lk-1就可以了。当所有联接完成的时候,扫描一遍Lk-1,对于Lk-1任意元素A,判断A是否为Ck中元素 c的子集,如果是,对子集c进行计数。也就是统计Lk-1中包含Ck中任意元素c的K-1维子集的个数。最后根据c进行裁剪。c的计数,即 Lk-1中包含的c的子集的个数,小于K,则删除。

    改进算法伪代码

    算法的主体不变,aprriori_gen函数改变如下,函数 has_infrequent_subset不再需要。
    procedure apriori_gen(Lk-1:frequent(k-1)-itemsets;minsupport:minimum support threshold)
    (1)for each itemset l1 ∈ Lk-1
    (2)for each itemset l2∈ L k-1
    (3)if(l1[1]=l2[1])∧(l1[2]=l2[2])∧…∧(l1[k-2]=l2[k-2])∧(l1[k-1]=l2[k-1]) then
    (4)c=l1∪ l2;
    (5)for each itemset l1∈ L k-1 //扫描Lk-1中的元素
    (6)for each candidate c∈ Ck //扫描 Ck中的元素
    (7)if l1 is the subset of Ck then //判断前者是不是后者的子集,如果是计数加1
    (8)c.number++;      
    (9)C'k={ c∈Ck |c.number=k};
    (10)return C'k;
    

    例子对比:

    问题:假设Lk-1={{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,3,4}},求Lk。
    由Lk-1得到Ck={{1,2,3,4},{2,3,4,5},{1,2,3,5}}。

    原算法:首先得到{1,2,3,4}的子集{1,2,3},{1,2,4},{2,3,4},{1,3,4}。然后判断这些子集是不是 Lk-1的元素。如果都是则保留,否则删除。这里保留,{2,3,4,5}和{1,2,3,5}则应该删除。得到C’k={{1,2,3,4}}。

    改进算法:首先从Lk-1中取元素{1,2,3},扫描Ck中的元素,看{1,2,3}是不是Ck元中元素的子集,{1,2,3}是{1,2,3,4}的子集,{1,2,3,4}的计数加1,{1,2,3}不是{2,3,4,5}的子集,计数不变,是{1,2,3,5}的子集,计数加1,经过对{1,2,3}处理后得到计数{1,0,1};然后看{1,2,4},{1,2,4}是{1,2,3,4}的子集,而不是 {2,3,4,5}的子集,也不是{1,2,3,5}的子集,计数不变,计数变为{2,0,1};考察{2,3,4},{2,3,4}是{1,2,3,4}的子集,也是{2,3,4,5}的子集,不是{1,2,3,5}的子集,计数变为{3,1,1};{2,3,5}不是{1,2,3,4}的子集,是{2,3,4,5}的子集,也是{1,2,3,5}的子集,计数变为{3,2,2};{1,3,4}是{1,2,3,4}的子集,不是{2,3,4,5}的子集,也不是{1,2,3,5}的子集,计数变为{4,2,2}。对数据扫描完毕。此时K=4,只有第一个元素的计数为4,为高频数据项集。得到C’k={{1,2,3,4}}。

    复杂度对比
    下面对原算法和改进算法的性能进行比较。Lk-1中的数据项集的个数记为|Lk-1|,Ck中的数据项集的个数记为|Ck|,Ck中元素的子集个数设为ni,其中i=1~|Ck| 。这里只分析从Ck~C’k的处理。原 算法从 AprioriCk中取元素,然后求该元素的子集,判断该子集是否在 |Ck| 中。需要进行的计算为这里写图片描述次, 1<=|L’k-1|<=|L’k-1|,1< = n’i <=n i。而改进算法是从Lk-1中选取元素,看是不是Ck中元素的子集,对 Ck中数据项集的子集个数进行统计。需要进行的计算是(|Lk-1|+1)*|Ck| 次。如果 n’i =1,就是每次只取Ck中数据项集的一个子集就可以判断该数据项集,则两个算法的效率基本相同,但是这种情况很少出现,从而大部分情况下,改进算法的效率要高于原算法。

    展开全文
  • 数据挖掘关联规则挖掘的应用研究 ,吴海玲,王志坚,本文首先介绍关联规则的基本原理,并简单概括其挖掘任务,然后说明关联规则的经典挖掘算法Apriori算法,通过一个实例分析进一步明��
  • 关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。...我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念: TID Items

    关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。

     啤酒与尿布的故事已经成为了关联规则挖掘的经典案例,还有人专门出了一本书《啤酒与尿布》,虽然说这个故事是哈弗商学院杜撰出来的,但确实能很好的解释关联规则挖掘的原理。我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念:

    TID Items
    T1 {牛奶,面包}
    T2 {面包,尿布,啤酒,鸡蛋}
    T3 {牛奶,尿布,啤酒,可乐}
    T4 {面包,牛奶,尿布,啤酒}
    T5 {面包,牛奶,尿布,可乐}

       表中的每一行代表一次购买清单(注意你购买十盒牛奶也只计一次,即只记录某个商品的出现与否)。数据记录的所有项的集合称为总项集,上表中的总项集S={牛奶,面包,尿布,啤酒,鸡蛋,可乐}。

     一、关联规则、自信度、自持度的定义

      关联规则就是有关联的规则,形式是这样定义的:两个不相交的非空集合X、Y,如果有X-->Y,就说X-->Y是一条关联规则。举个例子,在上面的表中,我们发现购买啤酒就一定会购买尿布,{啤酒}-->{尿布}就是一条关联规则。关联规则的强度用支持度(support)和自信度(confidence)来描述,

       支持度的定义:support(X-->Y) = |X交Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。例如:support({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/数据记录数 = 3/5=60%。

      自信度的定义:confidence(X-->Y) = |X交Y|/|X| = 集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数 。例如:confidence({啤酒}-->{尿布}) = 啤酒和尿布同时出现的次数/啤酒出现的次数=3/3=100%;confidence({尿布}-->{啤酒}) = 啤酒和尿布同时出现的次数/尿布出现的次数 = 3/4 = 75%。

      这里定义的支持度和自信度都是相对的支持度和自信度,不是绝对支持度,绝对支持度abs_support = 数据记录数N*support。

      支持度和自信度越高,说明规则越强,关联规则挖掘就是挖掘出满足一定强度的规则。

    二、关联规则挖掘的定义与步骤

      关联规则挖掘的定义:给定一个交易数据集T,找出其中所有支持度support >= min_support、自信度confidence >= min_confidence的关联规则。

      有一个简单而粗鲁的方法可以找出所需要的规则,那就是穷举项集的所有组合,并测试每个组合是否满足条件,一个元素个数为n的项集的组合个数为2^n-1(除去空集),所需要的时间复杂度明显为O(2^N),对于普通的超市,其商品的项集数也在1万以上,用指数时间复杂度的算法不能在可接受的时间内解决问题。怎样快速挖出满足条件的关联规则是关联挖掘的需要解决的主要问题。

      仔细想一下,我们会发现对于{啤酒-->尿布},{尿布-->啤酒}这两个规则的支持度实际上只需要计算{尿布,啤酒}的支持度,即它们交集的支持度。于是我们把关联规则挖掘分两步进行:

      1)生成频繁项集

      这一阶段找出所有满足最小支持度的项集,找出的这些项集称为频繁项集。

      2)生成规则

      在上一步产生的频繁项集的基础上生成满足最小自信度的规则,产生的规则称为强规则。

      关联规则挖掘所花费的时间主要是在生成频繁项集上,因为找出的频繁项集往往不会很多,利用频繁项集生成规则也就不会花太多的时间,而生成频繁项集需要测试很多的备选项集,如果不加优化,所需的时间是O(2^N)。

    三、Apriori定律

      为了减少频繁项集的生成时间,我们应该尽早的消除一些完全不可能是频繁项集的集合,Apriori的两条定律就是干这事的。

      Apriori定律1):如果一个集合是频繁项集,则它的所有子集都是频繁项集。举例:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。

      Apriori定律2):如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。举例:假设集合{A}不是频繁项集,即A出现的次数小于min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。

      利用这两条定律,我们抛掉很多的候选项集,Apriori算法就是利用这两个定理来实现快速挖掘频繁项集的。

    四、Apriori算法

      Apriori是由a priori合并而来的,它的意思是后面的是在前面的基础上推出来的,即先验推导,怎么个先验法,其实就是二级频繁项集是在一级频繁项集的基础上产生的,三级频繁项集是在二级频繁项集的基础上产生的,以此类推。

      Apriori算法属于候选消除算法,是一个生成候选集、消除不满足条件的候选集、并不断循环直到不再产生候选集的过程。

      

      上面的图演示了Apriori算法的过程,注意看由二级频繁项集生成三级候选项集时,没有{牛奶,面包,啤酒},那是因为{面包,啤酒}不是二级频繁项集,这里利用了Apriori定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。

      算法的思想知道了,这里也就不上伪代码了,我认为理解了算法的思想后,子集去构思实现才能理解更深刻,这里贴一下我的关键代码:

    复制代码
     1 public static void main(String[] args) {
     2         // TODO Auto-generated method stub
     3         record = getRecord();// 获取原始数据记录
     4         List<List<String>> cItemset = findFirstCandidate();// 获取第一次的备选集
     5         List<List<String>> lItemset = getSupportedItemset(cItemset);// 获取备选集cItemset满足支持的集合
     6 
     7         while (endTag != true) {// 只要能继续挖掘
     8             List<List<String>> ckItemset = getNextCandidate(lItemset);// 获取第下一次的备选集
     9             List<List<String>> lkItemset = getSupportedItemset(ckItemset);// 获取备选集cItemset满足支持的集合
    10             getConfidencedItemset(lkItemset, lItemset, dkCountMap, dCountMap);// 获取备选集cItemset满足置信度的集合
    11             if (confItemset.size() != 0)// 满足置信度的集合不为空
    12                 printConfItemset(confItemset);// 打印满足置信度的集合
    13             confItemset.clear();// 清空置信度的集合
    14             cItemset = ckItemset;// 保存数据,为下次循环迭代准备
    15             lItemset = lkItemset;
    16             dCountMap.clear();
    17             dCountMap.putAll(dkCountMap);
    18         }
    复制代码

      如果想看完整的代码,可以查看我的github,数据集的格式跟本文所述的略有不通,但不影响对算法的理解。

      下一篇将介绍效率更高的算法--FP-Grow算法。

    参考文献:

      [1].Pang-Ning Tan,Michael Steinbach. Introduction to Data Mining.

      [2].HanJiaWei. Data Mining: concept and  techniques.

      

    展开全文
  • 二、关联规则挖掘的基本概念关联规则挖掘发现大量数据中项集之间有趣的关联关系。如果两项或者多项属性之间存在关联,那么其中一项的属性可以依靠其他属性值进行预测。关联规则挖掘问题可以分为两个子问题:1、找出...

    一、概述

    本篇博文主要阐述数据挖掘相关的关联规则挖掘的算法(Apriori算法)。主要介绍关联规则的基本概念、Apriori算法原理和Apriori算法实例,文章末尾处附加Apriori算法源程序。

    二、关联规则挖掘的基本概念

    关联规则挖掘发现大量数据中项集之间有趣的关联关系。如果两项或者多项属性之间存在关联,那么其中一项的属性可以依靠其他属性值进行预测。

    关联规则挖掘问题可以分为两个子问题:1、找出事物数据库中所有大于等于用户指定的最小支持度的数据项集;2、利用频繁项集生成所欲需要的关联规则,根据用户设置的最小置信度进行取舍,最后得到强关联规则。

    2.1、项与项集

    数据库中不可分割的最小单位信息称为项,用符号i表示。项的集合称为项集,用 I 表示。项集的个数为k称为k-项集。比如,集合{啤酒、尿布、奶粉}称为3-项集。

    2.2、事物

    事物数据库T={t1,t2,t3,....,tn}是由一系列具有唯一标识的事务组成的。每个事务ti(i=1,2,3,4,5....,n)包含的项集都是I的子集。

    2.3、项集的频数(支持度计数)

    包括项集的事务个数称之为项集的频数(支持度计数)

    2.4、关联规则

    关联规则x==>y 的蕴含式。其中x,y都是I的真子集,并且x∩y=∅。x称之为前提,y称之为结果。关联规则反应x中的项目出现时,y中项目也跟着出现的规律。

    2.5、关联规则的支持度(support)

    关联规则的支持度是交易集中同时包含x和y的交易数和所有交易数之比。它反应了x和y中所包含的项在事务集中同时出现的概率,support(x==》y)

    support(x==>y) = support(x∪y)=p(xy)

    2.6、关联规则的置信度(confidence)

    关联规则的置信度是交易集包含x和y的交易数与所有交易数和包含x的交易数之比。ji为confidence(x==>y)= support(x∪y)/support(x)=p(y|x)

    通常情况下,用户需要制定最小支持度的阈值和最小置信度的阈值。关联规则必须要满足这两种阈值。如果关联规则既满足大于等于最小置信度,并且大于等于最小支持度则成只为强关联规则,反之不是。通常我们所说的都是强关联规则。

    项集U在T中所占的支持度的百分比就是他的支持度。support(U)=||{t∈T|U∈t}/||T||.对于项目集I,在事务数据库T中所满足用户指定的最小支持度的项目集,称之为频繁项目集。

    项目集空间理论-----频繁项集的子集仍然是频繁项集,非频繁项集的超集是非频繁项目集。

    3、关联规则挖掘算法------Apriori算法原理

    3.1、Apriori算法的基本思想

    Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度,发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描得到频繁1-项集的集合L1,第K(k>1)次扫描首先利用第(k-1)次扫描的结果Lk-1来产生候选集k-项集的集合Ck,然后在扫描的过程中确定Ck的支持度。最后,在每次扫描结束时计算频繁k-项集的集合Lk,算法在候选集k-项集的集合Ck为空时结束。

    3.2、Apriori算法产生频繁项集的过程

    产生频繁项集的过程只要分为连接和减枝两步:

    1、连接:为找到Lk(k>1),通过Lk-1与自身做连接产生候选k-项集的集合Ck。设l1,l2是Lk-1中的项集。记li[j]表示li的第j个项。Apriori算法假定事务或项集中的项按字典次序排序;如果Lk-1的元素l1,l2的前k-2项相等,l1的k-1项小于l2的k-1项,则可以认为l1和l2可以做连接。连接结果(l1[1],l1[2],l1[3],l1[4],.......,l1[k-1],l2[k-1])

    2、减枝:由Apriori的性质可知,频繁项集k-项集的任何子集都是必须是频繁项集,由连接生成的集合Ck需要进行验证,去除不满足支持度的非频繁k-项集。

    3.3、Apriori算法的主要步骤

    1. 扫描全部数据,产生候选1-项集的集合C1.
    2. 根据最小支持度,由候选1-项集的集合C1产生频繁1-项集的集合L1.
    3. 对k>1,重复执行步骤4,5,6
    4. 由Lk执行连接和减枝操作,产生候选k+1-项集的集合Ck+1
    5. 根据最小支持度,由候选(k+1)-项集的集合Ck+1,产生频繁(k+1)-项集的集合Lk+1
    6. 若L不等于∅,则k=k+1,步骤跳4,否则结束
    7. 根据最小置信度,由频繁项集产生强关联规则,结束

    3.4、Apriori算法描述

    输入:数据库D,最小支持度阈值min_sup。

    输出:D中的频繁集L.

    Begin

    L1=1-频繁项集

    for(k=2;Lk-1≠∅;k++)do begin

    Ck=Apriori_gen(Lk-1);{调用函数Apriori——gen(Lk-1)通过频繁(k-1)-项集产生候选k-项集}

    for所有数据集t∈D do begin {扫描D用于计数}

    Ct=subset(ck,t);{用sbuset找出该事务中候选的所有子集}

    for所有候选集c属于Ct,do

    c.count++

    end;

    Lk={c∈Ck|c.count>=min_sup}

    end

    end

    return L1∪L2∪......∪Lm{形成频繁项集的集合}

    3、Apriori算法实例


    展开全文
  • 关联规则挖掘 基本概念 Apriori算法 Apriori裁剪原理: 对于任意项集,如果它不是频繁集,则它任何超集不用产生/测试! 算法流程: 关于连接操作: 一个例子: Apriori算法存在问题: 多次扫描数据库 产生...

    关联规则挖掘

    基本概念

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    Apriori算法

    Apriori裁剪原理: 对于任意项集,如果它不是频繁集,则它的任何超集不用产生/测试!
    算法流程:

    在这里插入图片描述

    关于连接操作:

    在这里插入图片描述

    一个例子:

    在这里插入图片描述

    Apriori算法存在问题:

    1. 多次扫描数据库
    2. 产生大量的候选集合

    FP-Tree算法

    可以参考:https://blog.csdn.net/kisslotus/article/details/80328045

    FP-tree 算法的优点

    1. FP-tree 算法只需对事务数据库进行二次扫描;
    2. 避免产生大量候选集;

    FP-tree 算法的缺点

    1. 要递归生成条件数据库和条件 FP-tree,所以内存开销大;
    2. 只能用于挖掘单维的布尔关联规则;

    多维关联规则挖掘

    多维关联规则:规则中有两个以上的谓词。
    例如:
    Age(X, “30到40”)∧Income(X, “4万-6万”)→ Buys(X, “computer”)

    展开全文
  • 今天看了一下关联规则分析中Apriori算法,先了解下基本概念: 关联规则分析用于发现隐藏在大型数据集中有意义联系。在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间频繁模式、...
  • 关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和...我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念: TID Items T1 {牛奶,面包} T2 {面包,尿布...
  • 介绍了关联规则挖掘的基本原理和方法,详细分析了分布式关联规则挖掘算法并给出其模型;提出一种充分考虑数据源异构性、基于相似度的的分布式数据挖掘方法。实验证明该模型提高了挖掘的准确率。
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说...Apriori还是十大数据挖掘算法之一,可见Apriori关联规则算法重要性。(一)算法基本理论1、基本概念Apriori是最常用最经典挖掘频...
  • 本人刚开始学数据挖掘,虽然之前看过一本《数据挖掘原理与应用:SQL Server 2005数据库》,但是只是大体上了解了一些数据挖掘的概念,并没有深入去了解一个算法。前段时间开始比较深入的学习,就以关联规则作为学习...
  • 关联规则是从庞大的数据中提取一系列变量或因子间关系,以探索数据的变量或项目间隐含关系。 1、基本原理 关联规则通常用支持度、置信度、增益三个指标来分别表示其显著性、正确性和价值。通过给性最小支持度、...
  • 关联规则数据分析

    千次阅读 2019-01-13 13:55:59
    关联规则数据挖掘关联规则1.关联规则产生背景2. 基本概念与原理Aprioir算法用SSAS对医疗数据进行关联分析 关联规则 1.关联规则产生背景 最早是由Agrawal等人提出(1993)。最初动机是针对购物篮分析...
  • 众所周知,关联规则挖掘是数据挖掘中重要的一部分,如著名的啤酒和尿布的问题。今天要学习的是经典的关联规则挖掘算法——Apriori算法 一、算法的基本原理 由k项频繁集去导出k+1项频繁集。 二、算法...
  • 数据挖掘原理.rar

    2019-07-09 06:15:06
    长期以来,很多相互独立的不同学科分别致力于数据挖掘的各个方面。本书把信息科学、计算科学和统计学在数据挖掘方面的应用融合在一起,是第一本真正和跨学科教材。 本书由三部分构成。第一部分是基础,介绍了数据...
  • 关联分析用于发现隐藏在大型数据集中令人感兴趣联系,所发现模式通常用关联规则或频繁项集形式表示。 关联分析可以应用于生物信息学、医疗诊断、网页挖掘、科学数据分析等 频繁项集 项集:包含0个或多个项...
  • 实验六、数据挖掘关联分析一、实验目的1. 理解Apriori算法的基本原理2. 理解FP增长算法的基本原理3. 学会用python实现Apriori算法4. 学会用python实现FP增长算法二、实验工具1. Anaconda2. sklearn3. Pandas三、...
  • 实验六、数据挖掘关联分析 一、实验目的 1. 理解Apriori算法的基本原理 2. 理解FP增长算法的基本原理 3. 学会用python实现Apriori算法 4. 学会用python实现FP增长算法 二、实验工具 1. Anaconda 2. ...
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说...Apriori还是十大数据挖掘算法之一,可见Apriori关联规则算法重要性。(一)算法基本理论1、基本概念Apriori是最常用最经典挖掘频...
  • 本书对数据挖掘的基本算法进行了系统介绍,每种算法不仅介绍了算法的基本原理,而且配有大量例题以及源代码,并对源代码进行了分析,这种理论和实践相结合的方式有助于读者较好地理解和掌握抽象的数据挖掘算法。...

空空如也

空空如也

1 2 3 4
收藏数 74
精华内容 29
关键字:

关联规则数据挖掘的基本原理