精华内容
下载资源
问答
  • 第三章 关联规则挖掘理论和算法 内容提要;关联规则挖掘Association Rule Mining是数据挖掘中研究较早而且至今仍活跃的研究方法之一 最早是由Agrawal等人提出的1993...关联规则的挖掘工作成果颇丰例如关联规则的挖掘理论
  • 关联规则挖掘——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算法,通过一个实例分析进一步明��
  • 关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和...我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念: TID Items T1 {牛奶,面包} T2 {面包,尿布...

    关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和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的项集的组合个数为2n-1(除去空集),所需要的时间复杂度明显为O(2N),对于普通的超市,其商品的项集数也在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定理。最后生成三级频繁项集后,没有更高一级的候选项集,因此整个算法结束,{牛奶,面包,尿布}是最大频繁子集。

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

    public static void main(String[] args) {
    
    
    
    // TODO Auto-generated method stub
    
    record = getRecord();
    
    // 获取原始数据记录
    
    List<List<String>> cItemset = findFirstCandidate();
    
    // 获取第一次的备选集
    
    List<List<String>> lItemset = getSupportedItemset(cItemset);
    
    // 获取备选集cItemset满足支持的集合
    
    
    
    while (endTag != true) {
    
    // 只要能继续挖掘
    
    List<List<String>> ckItemset = getNextCandidate(lItemset);
    
    // 获取第下一次的备选集
    
    List<List<String>> lkItemset = getSupportedItemset(ckItemset);
    
    // 获取备选集cItemset满足支持的集合
    
    getConfidencedItemset(lkItemset, lItemset, dkCountMap, dCountMap);
    
    // 获取备选集cItemset满足置信度的集合
    
    if (confItemset.size() != 0)
    
    // 满足置信度的集合不为空
    
    printConfItemset(confItemset);
    
    // 打印满足置信度的集合
    
    confItemset.clear();
    
    // 清空置信度的集合
    
    cItemset = ckItemset;
    
    // 保存数据,为下次循环迭代准备
    
    lItemset = lkItemset;
    
    dCountMap.clear();
    
    dCountMap.putAll(dkCountMap);
    
    }
    
    展开全文
  • 一、基本概念 1. 关联规则 关联规则是形如X=>...关联规则的支持度是事务集中同时包含X和Y的事务数量与所有事务数量之比,它反映了X和Y中所含的事务的项在事务集中同时出现的频率,记为support(X=>Y),即s...

    一、基本概念

    1. 关联规则

    关联规则是形如X=>Y的蕴含式,其中X、Y分别是一事务的真子集,且X∩Y=Φ。X称为规则的前提,Y称为规则的结果。关联规则反映出X中的项目在事务中出现时,Y中的项目也跟着出现的规律。

    2.支持度

    关联规则的支持度是事务集中同时包含X和Y的事务数量与所有事务数量之比,它反映了X和Y中所含的事务的项在事务集中同时出现的频率,记为support(X=>Y),即support(X=>Y)=support(X∪Y)=P(XY)

    3.置信度

    关联规则的置信度是事务集中同时包含X和Y的事务数量与包含X的事务数量之比,记为confidence(X=>Y),置信度反映了包含X的事务中出现Y的条件概率。即 confidence(X=>Y)=support(X∪Y)/support(X)=P(XY)

    4. 频繁项集

    设U∈I,项目集U在事务集T上的支持度是包含U的事务在T中所占的百分比,即support(U)=|| {t∈T | U∈t} || / ||T||。式中,|| … ||表示集合中的元素数目。对项目集I,在事务数据库T中所有满足用户指定的最小支持度的项目集,即不小于最小支持度阀值的I的非空子集,称为频繁项目集或大项目集。

    二、Apriori算法原理

    1.算法思想

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

    2.Apriori算法产生频繁项集

    产生频繁项集的过程主要分为连接和剪枝两步:
    (1)连接步。为找到Lk(k≧2),通过L(k-1)与自身连接产生候选k-项集的集合Ck。自身连接时,两个项集对应的想按从小到大顺序排列好,当前除最后一项外的其他项都相等时,两个项集可连接,连接产生的结果为(l1[1], l1[2], …, l1[k-1], l2[k-2])。
    (2)剪枝步。由Apriori算法的性质可知,频繁k-项集的任何子集必须是频繁项集。由连接步产生的集合Ck需进行验证,除去不满足支持度的非频繁k-项集。

    3.Apriori算法的基本步骤

    (1)扫描全部数据,产生候选1-项集的集合C1;
    (2)根据最小支持度,由候选1-项集的集合C1产生频繁1-项集的集合L;
    (3)对k>1,重复执行步骤(4)、(5)、(6);
    (4)由Lk执行连接和剪枝操作,产生候选(k+1)-项集的集合C(k+1)。
    (5)根据最小支持度,由候选(k+1)-项集的集合C(k+1),产生频繁(k+1)-项集的集合L(k+1);
    (6)若L≠Ф,则k=k+1,跳往步骤(4);否则往下执行;
    (7)根据最小置信度,由频繁项集产生强关联规则,程序结束。

    三.Apriori算法实例

    下表是一个数据库事物列表,在数据库中有9笔交易,即 |D| =9下面描述一下Apriori算法寻找D中频繁项集的过程。
    数据库数据列表
    设最小支持度为2,产生候选项集及频繁项集的过程如下:
    1)第一次扫描
    扫描数据库D获得每个候选项的计数:
    在这里插入图片描述
    由于最小事务支持数为2,没有删除任何项目。
    2)第二次扫描
    为发现频繁2-项集的集合L2,算法使用L1∞L1产生候选2-项集的集合C2。在剪枝步没有候选项集从C2删除,因为这些候选项的子集也是频繁的。
    在这里插入图片描述
    3)第三次扫描
    L2∞L2产生候选3-项集的集合C3。
    在这里插入图片描述
    候选3项集C3产生的详细列表如下:
    ①连接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},}。
    ②使用Apriori性质剪枝:频繁项集的所有非空子集也必须是频繁的。例如{I1, I3, I5}的2-项子集是{I1, I3}, {I1, I5}, {I3, I5}。{I3, I5}不是L2的元素,因此不是频繁的。所有删掉C3中的{I1, I3, I5}。剪枝C3={{I1, I2, I3},{I1, I2, I5}}。

    4)第四次扫描
    算法使用L3∞L3产生候选集4-项集的集合C4。L3∞L3={{I1, I2, I3, I4}},根据Apriori性质,因为它的子集{I2, I3, I5}不是频繁的,使用这个项集被删除。这样C4=Φ,因此算法结束,找到了所有频繁项集。

    四、源码

    #include<iostream>
    #include<string> 
    #include <vector>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    class Apriori
    {
    public:
    	Apriori(size_t is = 0, unsigned int mv = 0)
    	{
    		item_size = is;
    		min_value = mv;
    	}
    	//~Apriori() {};
    	void getItem();
    	map< vector<string>, unsigned int> find_freitem();//求事务的频繁项
    	//连接连个k-1级频繁项,得到第k级频繁项
    	map< vector<string>, unsigned int > apri_gen(unsigned int K, map< vector<string>, unsigned int > K_item);
    	//展示频繁项集
    	void showAprioriItem(unsigned int K, map< vector<string>, unsigned int > showmap);
    private:
    	map< int, vector<string> > item;//存储所有最开始的事务及其项
    	map< vector<string>, unsigned int > K_item;//存储频繁项集
    	size_t item_size;//事务数目
    	unsigned  int min_value;//最小阈值
    };
    
    void Apriori::getItem()//用户输入最初的事务集
    {
    	int ci = item_size;
    	for (int i = 0;i < ci;i++)
    	{
    		string str;
    		vector<string> temp;
    		cout << "请输入第 " << i + 1 << "个事务的项集(123 end):";
    		while (cin >> str && str != "123")
    		{
    			temp.push_back(str);
    		}
    		sort(temp.begin(), temp.end());
    		pair< map<int, vector<string> >::iterator, bool> ret = item.insert(make_pair(i + 1, temp));
    		if (!ret.second)
    		{
    			--i;
    			cout << "你输入的元素已存在!请重新输入!" << endl;
    		}
    	}
    	cout << "-------------运行结果如下:--------------" << endl;
    }
    
    map< vector<string>, unsigned int> Apriori::find_freitem()
    {
    	unsigned int i = 1;
    	bool isEmpty = false;
    	map< int, vector<string> >::iterator mit;
    	for (mit = item.begin();mit != item.end();mit++)
    	{
    		vector<string> vec = mit->second;
    		if (vec.size() != 0)
    			break;
    	}
    	if (mit == item.end())//事务集为空
    	{
    		isEmpty = true;
    		cout << "事务集为空!程序无法进行..." << endl;
    		map< vector<string>, unsigned int> empty;
    		return empty;
    	}
    	while (1)
    	{
    		map< vector<string>, unsigned int > K_itemTemp = K_item;
    
    		K_item = apri_gen(i++, K_item);
    
    		if (K_itemTemp == K_item)
    		{
    			i = UINT_MAX;
    			break;
    		}
    		//判断是否需要进行下一次的寻找
    		map< vector<string>, unsigned int > pre_K_item = K_item;
    		size_t Kitemsize = K_item.size();
    		//存储应该删除的第K级频繁项集,不能和其他K级频繁项集构成第K+1级项集的集合
    		if (Kitemsize != 1 && i != 1)
    		{
    			vector< map< vector<string>, unsigned int >::iterator > eraseVecMit;
    			map< vector<string>, unsigned int >::iterator pre_K_item_it1 = pre_K_item.begin(), pre_K_item_it2;
    			while (pre_K_item_it1 != pre_K_item.end())
    			{
    				map< vector<string>, unsigned int >::iterator mit = pre_K_item_it1;
    				bool isExist = true;
    				vector<string> vec1;
    				vec1 = pre_K_item_it1->first;
    				vector<string> vec11(vec1.begin(), vec1.end() - 1);
    				while (mit != pre_K_item.end())
    				{
    					vector<string> vec2;
    					vec2 = mit->first;
    					vector<string> vec22(vec2.begin(), vec2.end() - 1);
    					if (vec11 == vec22)
    						break;
    					++mit;
    				}
    				if (mit == pre_K_item.end())
    					isExist = false;
    				if (!isExist && pre_K_item_it1 != pre_K_item.end())
    					eraseVecMit.push_back(pre_K_item_it1);//该第K级频繁项应该删除
    				++pre_K_item_it1;
    			}
    			size_t eraseSetSize = eraseVecMit.size();
    			if (eraseSetSize == Kitemsize)
    				break;
    			else
    			{
    				vector< map< vector<string>, unsigned int >::iterator >::iterator currentErs = eraseVecMit.begin();
    				while (currentErs != eraseVecMit.end())//删除所有应该删除的第K级频繁项
    				{
    					map< vector<string>, unsigned int >::iterator eraseMit = *currentErs;
    					K_item.erase(eraseMit);
    					++currentErs;
    				}
    			}
    		}
    		else
    			if (Kitemsize == 1)
    				break;
    	}
    	cout << endl;
    	showAprioriItem(i, K_item);
    	return K_item;
    }
    
    map< vector<string>, unsigned int > Apriori::apri_gen(unsigned int K, map< vector<string>, unsigned int > K_item)
    {
    	if (1 == K)//求候选集C1
    	{
    		size_t c1 = item_size;
    		map< int, vector<string> >::iterator mapit = item.begin();
    		vector<string> vec;
    		map<string, unsigned int> c1_itemtemp;
    		while (mapit != item.end())//将原事务中所有的单项统计出来
    		{
    
    			vector<string> temp = mapit->second;
    			vector<string>::iterator vecit = temp.begin();
    			while (vecit != temp.end())
    			{
    				pair< map<string, unsigned int>::iterator, bool > ret = c1_itemtemp.insert(make_pair(*vecit++, 1));
    				if (!ret.second)
    				{
    					++ret.first->second;
    				}
    			}
    			++mapit;
    		}
    		map<string, unsigned int>::iterator item_it = c1_itemtemp.begin();
    		map< vector<string>, unsigned int > c1_item;
    		while (item_it != c1_itemtemp.end())//构造第一级频繁项集
    		{
    			vector<string> temp;
    			if (item_it->second >= min_value)
    			{
    				temp.push_back(item_it->first);
    				c1_item.insert(make_pair(temp, item_it->second));
    			}
    			++item_it;
    		}
    		return c1_item;
    	}
    	else
    	{
    		cout << endl;
    		showAprioriItem(K - 1, K_item);
    		map< vector<string>, unsigned int >::iterator ck_item_it1 = K_item.begin(), ck_item_it2;
    		map< vector<string>, unsigned int > ck_item;
    		while (ck_item_it1 != K_item.end())
    		{
    			ck_item_it2 = ck_item_it1;
    			++ck_item_it2;
    			map< vector<string>, unsigned int >::iterator mit = ck_item_it2;
    
    			//取当前第K级频繁项与其后面的第K级频繁项集联合,但要注意联合条件
    			//联合条件:连个频繁项的前K-1项完全相同,只是第K项不同,然后两个联合生成第K+1级候选频繁项
    			while (mit != K_item.end())
    			{
    				vector<string> vec, vec1, vec2;
    				vec1 = ck_item_it1->first;
    				vec2 = mit->first;
    				vector<string>::iterator vit1, vit2;
    
    				vit1 = vec1.begin();
    				vit2 = vec2.begin();
    				while (vit1 < vec1.end() && vit2 < vec2.end())
    				{
    					string str1 = *vit1;
    					string str2 = *vit2;
    					++vit1;
    					++vit2;
    					if (K == 2 || str1 == str2)
    					{
    						if (vit1 != vec1.end() && vit2 != vec2.end())
    						{
    							vec.push_back(str1);
    						}
    
    					}
    					else
    						break;
    				}
    				if (vit1 == vec1.end() && vit2 == vec2.end())
    				{
    					--vit1;
    					--vit2;
    					string str1 = *vit1;
    					string str2 = *vit2;
    					if (str1 > str2)
    					{
    						vec.push_back(str2);
    						vec.push_back(str1);
    					}
    					else
    					{
    						vec.push_back(str1);
    						vec.push_back(str2);
    					}
    					map< int, vector<string> >::iterator base_item = item.begin();
    					unsigned int Acount = 0;
    					while (base_item != item.end())//统计该K+1级候选项在原事务集出现次数
    					{
    						unsigned int count = 0, mincount = UINT_MAX;
    						vector<string> vv = base_item->second;
    						vector<string>::iterator vecit, bvit;
    						for (vecit = vec.begin();vecit < vec.end();vecit++)
    						{
    							string t = *vecit;
    							count = 0;
    							for (bvit = vv.begin();bvit < vv.end();bvit++)
    							{
    								if (t == *bvit)
    									count++;
    							}
    							mincount = (count < mincount ? count : mincount);
    						}
    						if (mincount >= 1 && mincount != UINT_MAX)
    							Acount += mincount;
    						++base_item;
    					}
    					if (Acount >= min_value && Acount != 0)
    					{
    						sort(vec.begin(), vec.end());
    						//该第K+1级候选项为频繁项,插入频繁项集
    						pair< map< vector<string>, unsigned int >::iterator, bool> ret = ck_item.insert(make_pair(vec, Acount));
    						if (!ret.second)
    						{
    							ret.first->second += Acount;
    						}
    					}
    				}
    				++mit;
    			}
    			++ck_item_it1;
    		}
    		if (ck_item.empty())//该第K+1级频繁项集为空,说明调用结束,把上一级频繁项集返回
    			return K_item;
    		else
    			return ck_item;
    	}
    }
    void Apriori::showAprioriItem(unsigned int K, map< vector<string>, unsigned int > showmap)
    {
    	map< vector<string>, unsigned int >::iterator showit = showmap.begin();
    	if (K != UINT_MAX)
    		cout << endl << "第 " << K << " 级频繁项集为:" << endl;
    	else
    		cout << "最终的频繁项集为:" << endl;
    	cout << "项  集" << "  \t  " << "频率" << endl;
    	while (showit != showmap.end())
    	{
    		vector<string> vec = showit->first;
    		vector<string>::iterator vecit = vec.begin();
    		cout << "{ ";
    		while (vecit != vec.end())
    		{
    			cout << *vecit << "  ";
    			++vecit;
    		}
    		cout << "}" << "  \t  ";
    		cout << showit->second << endl;
    		++showit;
    	}
    }
    
    unsigned int parseNumber(const char * str)//对用户输入的数字进行判断和转换
    {
    	if (str == NULL)
    		return 0;
    	else
    	{
    		unsigned int num = 0;
    		size_t len = strlen(str);
    		for (size_t i = 0;i < len;i++)
    		{
    			num *= 10;
    			if (str[i] >= '0' && str[i] <= '9')
    				num += str[i] - '0';
    			else
    				return 0;
    		}
    		return num;
    	}
    }
    
    void main()
    {
    	//Apriori a;
    	unsigned int itemsize = 0;
    	unsigned int min;
    
    	do
    	{
    		cout << "请输入事务数:";
    		char * str = new char;
    		cin >> str;
    		itemsize = parseNumber(str);
    		if (itemsize == 0)
    		{
    			cout << "请输入大于0正整数!" << endl;
    		}
    	} while (itemsize == 0);
    
    	do
    	{
    		cout << "请输入最小阈值:";
    		char * str = new char;
    		cin >> str;
    		min = parseNumber(str);
    		if (min == 0)
    		{
    			cout << "请输入大于0正整数!" << endl;
    		}
    	} while (min == 0);
    
    	Apriori a(itemsize, min);
    	a.getItem();
    	map< vector<string>, unsigned int> AprioriMap = a.find_freitem();
    	//a.showAprioriItem(UINT_MAX,AprioriMap);
    	system("pause");
    }
    
    

    本文参考了王振武编著《数据挖掘算法原理与实现》一书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.

      

    展开全文
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说就是Apriori算法,通俗来讲apriori旨在寻找频繁项集,以帮助商家将消费者有可能一起搭配购买物品放置在同一个地方,提高消费者...
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说就是Apriori算法,通俗来讲apriori旨在寻找频繁项集,以帮助商家将消费者有可能一起搭配购买物品放置在同一个地方,提高消费者...
  • 今天看了一下关联规则分析中Apriori算法,先了解下基本概念: 关联规则分析用于发现隐藏在大型数据集中有意义联系。在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间频繁模式、...
  • 在上篇博客中介绍了关联规则分析的一些基本知识,将在接下来这几篇中总结一些关联规则的算法。这篇总结的是最经典的求关联规则的算法:Apriori算法。 1.求出频繁项集: 因为直接解释比较抽象,所以用例子来理解算法...
  • 介绍了关联规则挖掘的基本原理和方法,详细分析了分布式关联规则挖掘算法并给出其模型;提出一种充分考虑数据源异构性、基于相似度的的分布式数据挖掘方法。实验证明该模型提高了挖掘的准确率。
  • 关联规则与数据分析

    千次阅读 2019-01-13 13:55:59
    关联规则的产生背景2. 基本概念与原理Aprioir算法用SSAS对医疗数据进行关联分析 关联规则 1.关联规则的产生背景 最早是由Agrawal等人提出的(1993)。最初的动机是针对购物篮分析(Basket Analysis)问题提出的,...
  • 关联规则之Aprior算法

    2018-05-23 16:06:00
    关联规则挖掘在电商、零售、大气物理、生物医学已经有了广泛的应用,本篇文章将介绍一些基本知识和Aprori算法。...我们这里以一个超市购物篮迷你数据集来解释关联规则挖掘的基本概念: TID Items T1 {...
  • 关联规则挖掘算法——Apriori算法

    千次阅读 2007-10-07 20:49:00
    Agrawal等于1993年[1]首先提出了挖掘顾客交易数据库中项集间的关联规则问题,其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。...一、Apriori算法基本原理Agrawa
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说就是Apriori算法,通俗来讲apriori旨在寻找频繁项集,以帮助商家将消费者有可能一起搭配购买物品放置在同一个地方,提高消费者...
  • Apriori 算法apriori关联规则算法的原理设计较为简单,著名“啤酒和尿布”说就是Apriori算法,通俗来讲apriori旨在寻找频繁项集,以帮助商家将消费者有可能一起搭配购买物品放置在同一个地方,提高消费者...
  • 主要介绍关联规则的基本概念、Apriori算法原理和Apriori算法实例,文章末尾处附加Apriori算法源程序。二、关联规则挖掘的基本概念关联规则挖掘发现大量数据中项集之间有趣的关联关系。如果两项或者多项属性之间存在...
  • 1、基本原理 关联规则通常用支持度、置信度、增益三个指标来分别表示其显著性、正确性和价值。通过给性最小支持度、最小置信度作为门槛值。若该规则的支持度与置信度大于门槛值,则说明该规则有助于进行推论;若该...
  • ----------5 关联分析结果可视化对关联规则的支持度、置信度和提升值进行可视化 关联规则分析 本次报告主要包括以下内容: 数据介绍 基本原理介绍 结合理论进行案例分析 最后总结 附录加上参考和代码 数据介绍 ...
  • 关联规则之子图模式 文章的目的: 了解子图模式在什么...  首先我们要明白这样一个事情,在这么多关联规则的方法中,我们为什么要使用子图模式。这种子图模式在什么领域应用? 图1   由上图1我们可以...
  • 一、算法的基本原理 由k项频繁集去导出k+1项频繁集。 二、算法流程 1.扫描事务数据库,找出1项集,并根据最小支持度计数,剪枝得出频繁1项集。k=1. 2.由频繁k项集进行连接步操作,形成候选的k...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 263
精华内容 105
关键字:

关联规则的基本原理