精华内容
下载资源
问答
  • 关联规则常用算法

    千次阅读 2020-07-03 15:53:41
    关联规则常用算法   关联规则(Association Rules)是海量数据挖掘(Mining Massive Datasets,MMDs)非常经典的任务,其主要目标是试图从一系列事务集中挖掘出频繁项以及对应的关联规则关联规则来自于一个...

      关联规则Association Rules)是海量数据挖掘(Mining Massive Datasets,MMDs)非常经典的任务,其主要目标是试图从一系列事务集中挖掘出频繁项以及对应的关联规则。关联规则来自于一个家喻户晓的“啤酒与尿布”的故事,本文通过故事来引出关联规则的方法。

    啤酒与尿布的故事
      在一家超市里,有一个有趣的现象:尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话,而是发生在美国沃尔玛连锁店超市的真实案例,并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统,为了能够准确了解顾客在其门店的购买习惯,沃尔玛对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上,沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是:"跟尿布一起购买最多的商品竟是啤酒!经过大量实际调查和分析,揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自己买一些啤酒。产生这一现象的原因是:美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

      关联规则是一种大数据挖掘的任务,最初的动机是针对购物篮分析(Market Basket Analysis)问题提出的,例如上述的“啤酒与尿布”的故事,如果超市能够发现一些具有相关联的商品购物行为,通过对商品的适当调整可以提高顾客的购物体验,提升超市的销售额,因此如何发现这些潜在的规律呢?

    本文首先介绍关联规则的任务,以及相关概念,其次介绍相关算法,目录索引如下:

    1、关联规则形式化描述

      设 I = { I 1 , I 2 , . . . , I m } I=\{I_1,I_2,...,I_m\} I={I1,I2,...,Im}是一个项集(Item Set), m m m为项的个数,其中 I i I_i Ii表示第 i i i个项,对应于一个个商品。事务(Transaction) t i t_i ti表示 I I I的一个子集,对应于一个个订单。事务组成的集合记做 D = { t 1 , t 2 , . . . , t n } D=\{t_1,t_2,...,t_n\} D={t1,t2,...,tn},通常也称作事务数据库。通常描述中,每一个事务都有唯一的编号,记做TID,每个事务中都包含若干个项Items。
      关联规则是形如 X → Y X→Y XY的蕴涵式,其中, X X X Y Y Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。其中,关联规则 X Y XY XY,存在支持度和置信度,定义如下:

    • 支持度( X → Y X→Y XY = 同 时 包 含 X 和 Y 的 事 务 数 量 所 有 事 务 数 量 =\frac{同时包含X和Y的事务数量}{所有事务数量} =XY,理解为某一个项出现的概率。通常设置一个阈值minsupport,当支持度不小于该值时认为是频繁项;
    • 置信度( X → Y X→Y XY = 同 时 包 含 X 和 Y 的 事 务 数 量 包 含 X 的 事 务 数 量 =\frac{同时包含X和Y的事务数量}{包含X的事务数量} =XXY,理解为在X事务的基础上,X和Y均出现的条件概率。

    例题1:分别计算3-项集“面包,牛奶,尿布”和“面包→牛奶,尿布”对应支持度和置信度。
    在这里插入图片描述
    1.可统计“面包,牛奶,尿布”同时出现的TID有4和5,所以支持度是2/5;
    2.面包出现的TID有1,2,4,5,因此支持度为2/4。

    因此关联规则实际上包含两个子任务:

    • 频繁模式发现:也称频繁模式挖掘、频繁项挖掘等,是指从一系列候选的项中选择频繁的部分,通常衡量频繁的程度可以是对每一项出现的频率,当超过某一阈值是则任务这个项是频繁的。
    • 生成关联规则:在已经发现的最大频繁项目集中,寻找置信度不小于用户给定的minconfidence的关联规则。

    2、Apriori算法

      Apriori算法是经典的关联规则算法,其主要思路如下图所示:
    在这里插入图片描述
    算法流程:

    1. 首先对数据库中进行一次扫描,统计每一个项出现的次数,形成候选1-项集;
    2. 根据minsupport阈值筛选出频繁1-项集;
    3. 将频繁1-项集进行组合,形成候选2-项集;
    4. 对数据库进行第二次扫描,为每个候选2-项集进行计数,并筛选出频繁2-项集;
    5. 重复上述流程,直到候选项集为空;
    6. 根据生成的频繁项集,通过计算相应的置信度来生成管理规则。

      其中如果项集中包含k个不同的项,称之为k-项集。候选k-项集记做 C k C_k Ck,频繁k-项集记做 L k L_k Lk

      频繁模式挖掘的基本前提是:

    • 如果一个集合是频繁项集,则它的所有子集都是频繁项集。
    • 如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。

    例题2:使用Apriori算法对事务集 D D D进行频繁项挖掘,其中minsupport.count=2.
    在这里插入图片描述
      首先对事务数据库 D D D进行扫描,统计各个1-项的计数。由于最小计数阈值minsupport.count=2,因此可以筛选出频繁1-项集“ l 1 , l 2 , l 3 , l 4 , l 5 l_1,l_2,l_3,l_4,l_5 l1,l2,l3,l4,l5”。其次两两组合,形成 5 × 4 ÷ 2 = 10 5\times4\div2=10 5×4÷2=10个候选2-项集 C 2 C_2 C2,并进行第二次扫描数据库进行计数,发现 ( l 1 , l 4 ) , ( l 3 , l 4 ) , ( l 3 , l 5 ) , ( l 4 , l 5 ) (l_1,l_4),(l_3,l_4),(l_3,l_5),(l_4,l_5) (l1,l4),(l3,l4),(l3,l5),(l4,l5)低于阈值,所以剔除掉。对剩余的频繁2-项集 L 2 L_2 L2进行两两组合,去除重复的组合后形成候选3-项集 C 3 C_3 C3,以此类推,最终得到频繁3-项集为 ( l 1 , l 2 , l 3 ) , ( l 1 , l 2 , l 5 ) (l_1,l_2,l_3),(l_1,l_2,l_5) (l1,l2,l3),(l1,l2,l5)

    Apriori算法的特点:

    • 简单且易于实现,是最具代表性的关联规则挖掘算法
    • 随着数据集规模的不断增长,逐渐显现出一定的局限性:
        (1)需多次扫描数据库,很大的I/O负载,算法的执行效率较低;
        (2)产生大量的候选项目集,尤其是候选2-项集占用内存非常大,会消耗大量的内存;
        (3)对于每一趟扫描,只有当内存大小足够容纳需要进行计数的候选集时才能正确执行。如果内存不够大,要么使用一种空间复杂度更小的算法,要么只能对一个候选集进行多次扫描,否则将会出现“内存抖动”的情况,即在一趟扫描中页面频繁地移进移出内存(页面置换算法也无法避免内存抖动问题),造成运行时间的剧增。

    3、PCY算法

      为了改进Apriori算法,PCY由Park,Chen和Yu等提出,其目标是为了降低Apriori算法频繁的扫描数据库,其次降低候选项集所占用的内存。其主要创新点有:

    • 将哈希函数应用到频繁项挖掘中;
    • 第一次扫描事务数据库时,将剩余的空间存放哈希表,从而降低第二次扫描时占用的大量空间。

    在这里插入图片描述
      如上图,左边两个图表示Apriori算法的前两次扫描过程,可知第一次扫描内存空闲很大,而第二次扫描占用空间很多;右侧两个图则表示PCY算法的两次扫描,第一次扫描除了对1-项集进行计数外,额外利用一个2-项哈希表存储每个2-项的计数,再第二次扫描时则利用该哈希表对应的位图来判断是否保留该2-项,从而减少候选2-项集大小。

      PCY主要思想可总结如下:

    1. 首先第一次扫描事务数据库 D D D,并对候选1-项集 C 1 C_1 C1进行计数,根据阈值筛选出频繁1-项集 L 1 L_1 L1
    2. 在第一次扫描的同时,对事务集中每个事务中各个项进行两两组合,并通过哈希函数映射到相应的桶中,并将相应的桶计数+1;
    3. 第二次扫描之前,首先根据每个桶中的计数来判断是否为频繁桶,频繁桶是指计数不低于某个阈值的桶。频繁的桶对应的位图记做1,否则记做0;
    4. 第二次扫描事务数据库,此时根据频繁1-项集 L 1 L_1 L1生成一系列的2-项组合,分别通过哈希函数获得其桶的编号,并根据位图来判断。如果对应的位图值为1,则将其保留,否则剔除。因此最后保留的就是候选2-项集 C 2 C_2 C2,对其进行计数并筛选频繁2-项集 L 2 L_2 L2

    例题3:使用PCY算法生成频繁2-项集,其中minsupport.count=2,哈希函数为:
    在这里插入图片描述
    事务及集合 D D D
    在这里插入图片描述
    1.首先对1-项集进行计数,筛选出频繁1-项集 L 1 L_1 L1为{A},{B},{C},{E};
    2.其次根据事务集中每个事务的项两两组合,并通过哈希函数映射到7个桶中。例如 { A , C } \{A,C\} {A,C}哈希值为 ( 1 × 10 + 3 ) m o d 7 = 6 (1\times 10+3 )mod 7=6 (1×10+3)mod7=6,所以其映射到下标为6的桶中;最终形成的桶如下图所示,如果桶的计数超过不小于2,则为频繁桶,位图对应为1。所有桶的计数分别为3,1,2,0,3,1,3,位图对应为1,0,1,0,1,0,1。
    3.频繁1-项集 L 1 L_1 L1,中两两组合,并将每一个组合通过哈希函数得到对应的桶编号,如果对于的位图为1,则保留为候选2-项。最终从6个项中筛选出 { A , C } , { B , C } , { B , E } , { C , E } \{A,C\},\{B,C\},\{B,E\},\{C,E\} {A,C},{B,C},{B,E},{C,E}共4个作为候选项集 C 2 C_2 C2
    4.最后第二次扫描计数,得到对应的频繁2-项集 L 2 L_2 L2 { A , C } , { B , C } , { B , E } , { C , E } \{A,C\},\{B,C\},\{B,E\},\{C,E\} {A,C},{B,C},{B,E},{C,E}
    在这里插入图片描述

      因此总的来说,PCY算法的关键在于在第一次和第二次扫描之间通过哈希计数提前过滤掉一部分2-项集,使得候选2-项集规模变小,而这种筛选的规则则是根据频繁桶来确定。

    PCY算法特点:

    • 优点
        高效地产生频繁项集,提升了性能
        减少了数据库的扫描次数
        减少计数所需的内存空间的大小
    • 分析
        最差的情况:所有桶都是频繁桶,则第二遍扫描中PCY算法需要计算的相对数目与Apriori算法相比没有任何减少
        在寻找频繁3-项集以及更多项集时,PCY算法与Apriori算法相同
        如果桶的个数越多,每个桶内分的项数量变少
        如果不频繁的项映射到频繁的桶中,则可能不易过滤(改进:多阶段算法)

    4、多阶段算法

      事实上,PCY算法面临一个问题,即由于哈希函数的原因,有些非频繁项被映射到了频繁桶中,导致这部分非频繁项很难被过滤掉,因此多阶段算法旨在解决这个问题。其主要思路是:

    1. 在PCY的第一遍和第二遍之间插入额外的扫描过程,将2-项集哈希到另外的独立的哈希表中(使用不同的哈希函数)
    2. 在每个中间过程中,只需哈希那些在以往扫描中哈希到频繁桶的频繁项。

    如图所示:
    在这里插入图片描述

    1. 首先进行第一次扫描。该扫描与PCY第一次扫描一样,首先对1-项集计数,并将每个事务中各个项两两组合,通过第一个哈希函数映射到哈希表1中;
    2. 在第二次扫描时,使用第二个哈希表。当2-项集 { i , j } \{i,j\} {i,j}同时满足
      (1) i , j i,j i,j均为频繁项、(2) { i , j } \{i,j\} {i,j}在第一个哈希表中映射到频繁桶中;
      时,该2-项集可以映射到第二个哈希表中;
    3. 在第三次扫描时,根据频繁1-项集中各项两两组合,对于每个2-项集,当前仅当同时满足:
      (1) i , j i,j i,j均为频繁项、(2) { i , j } \{i,j\} {i,j}在第一个哈希表中映射到频繁桶中、(3) { i , j } \{i,j\} {i,j}在第二个哈希表中映射到频繁桶中;
      时,才保留其作为候选2-项集 C 2 C_2 C2
    4. 对所有候选2-项集筛选出频繁2-项集 L 2 L_2 L2

    多阶段算法特点:

    1. 因为在第二趟扫描时,不是所有的2-项集都被散列到桶中,因此桶的计数值变得比第一趟扫描时更小,最终结果是更多的桶变成非频繁桶;
    2. 由于两次扫描采用的哈希函数不同,那些在第一趟扫描时被散列到频繁桶中的非频繁2-项集很可能在第二趟扫描时被哈希到一个非频繁桶中
    3. 多阶段算法寻找频繁2-项集不只局限于使用3次扫描

    5、多哈希算法

      多哈希算法与PCY算法基本一致,不同在于PCY算法只使用一个哈希表,而多哈希算法则是使用了多个哈希表,其算法思想与PCY一致,只是在判断是否是候选2-项集时,需要同时判断多个对应位图是否均为1,如下图所示:
    在这里插入图片描述
    多哈希算法特点:

    1. 只要桶的平均计数不小于阈值,频繁桶的数目仍然比较多,这样一个非频繁2-项集同时哈希到两个哈希表的频繁桶内的概率就更低,可以减少第二遍扫描的运算量
    2. 风险:
        使用两个哈希表时,每个哈希表仅有PCY算法的一半的桶,这样每个桶上的平均计数会翻倍,必须保证大多数桶的计数不会达到阈值
        桶的平均计数可能会超过阈值
    3. 多哈希算法也不只局限于使用两个哈希表:

    6、FP-Tree算法

      先前的方法均存在一个问题,即频繁的对数据库进行扫描,而每次扫描的目的则是为了计数,因此如何只对数据库进行两次扫描便可以对所有可能的频繁项进行计数呢?FP-Tree算法巧妙的解决了这个问题。
      FP-Tree算法主要分为两个步骤:构建FP树频繁模式挖掘

    一、构建FP树算法:

    1. 对事务数据库 D D D进行一次扫描,统计所有项的计数,并根据最小支持度阈值保留频繁1-项集;
    2. 对频繁1-项集中所有的项递减顺序排列,形成对应的Head Table,其中Head Table每个元素表示频繁1-项集及其计数,指针默认为空;
    3. 创建一个根结点,扫描第二遍事务数据库 D D D,每一个事务对应的所有排序的项依次插入树中,计数默认为1,如果已存在该节点,则计数+1(同一个项在每个事务记录内排号相同时,此时两个结点是同一个,则直接+1)。若相同的项不在同一个分支时,通过指针相连。

    二、频繁模式挖掘

    1. 根据Head Table自底向上顺序依次进行频繁项挖掘,此时对于的元素作为条件模式基
    2. 在FP树中寻找相应的路径,且计数取最小值,去除掉小于阈值的项,保留不小于阈值的项;
    3. 根据条件模式基获得相同基的频繁项。

    例题4:已知最小支持度阈值为3,使用FP-Tree算法进行频繁项挖掘,事务数据库如图所示:
    在这里插入图片描述
      如图可知,事务数据库中共有9个事务,6个项。此时可知a,b,c,d,e,f的计数分别为7,6,5,5,3,1。首先第一次扫描后可过滤掉“f”,其次根据各自计数在每个事务记录内降序排列。
      根据计数生成Head Table;
      其次构建FP树,例如事务记录TID=1开始,向根结点依次插入结点(a:1),(b:1),(d:1),此时Head Table中的a,b,d指针分别指向新增的结点。当TID=2时,从根结点插入(b:1),(c:1),(d:1),需要注意的是,虽然当前也插入了b和c,但由于其层数与TID1不同,所以是在新的分支上。而对于TID=3时,第一个项是a,所以直接在(a:1)上计数,变为(a:2)。
      以此类推,即可生成如下图所示的FP-树:在这里插入图片描述
      其次进行频繁项挖掘,先以e开始,可知所有路径以e结尾的有(a:7,b:5,c:3,e:1)、(a:7,c:1,d:1,e:1),(a:7,d:1,e:1)。根据条件模式基,需要将每个结点的计数变为最小的值,即变为(a:1,b:1,c:1,e:1)、(a:1,c:1,d:1,e:1),(a:1,d:1,e:1)。此时可以发现每个项的计数有(a:3),(b:1),(c:2),(d:2),(e:3),由于阈值为3,则只保留(a:3)和(e:3)。因此可以得到频繁项有(ae:3)和(e:3)。需要注意的是,当前的基底是e,因此必须包含e,例如(a:3)不是e的条件模式基,则不能包含该项。

    FP-Tree算法特点:

    1. FP-Tree算法只需要进行两次扫描即可完成频繁模式挖掘,大大减少了I/O开销;
    2. 通过Head Table可对相同的项进行计数,省去了重复计数的时间开销,计数完全可以在内存内外存。

    7、XFP-Tree算法

      FP-Tree算法有许多可改进之处,例如如果当事务的数量非常庞大时,构建FP树会占用大量的时间,XFP-Tree算法旨在并行的构建FP树来提升效率。

      XFP-Tree算法需要创建两个数据结构,分别是XFP-Tree和位图矢量:

    1. XFP树:与FP树构建方式相同,不同点在于使用多核机制。首先对Head Table进行划分,划分的数量与内核数成整数倍,划分时尽量保证相对平均;其次在不同的分区上用不同的CPU核创建FP树,该过程是并行执行的,如下图所示(例4的示例),3个CPU核并行构建,每个颜色代表不同的CPU核,不同核构建的FP树通过指针连接。
      在这里插入图片描述
    2. 位图矢量:按照项对每个事务进行记录,例如TID1的事务只有abd三个项,所以位图为1,其他为0,即11010。位图矢量的功能是用于对项进行计数,而计数也可以通过多核机制进行并行。例如项ab,cd和e分别分配给P1,P2和P3执行计数。

    在这里插入图片描述

    8、GPApriori算法

      有相关工作对Apriori进行了改进,除了先前介绍的PCY,多阶段、多哈希外,使用GPU进行频繁模式挖掘也是一种改进之处。 GPApriori算法则使用GPU进行频繁项挖掘。

    在这里插入图片描述
      GPApriori算法主要创新点为:(1)使用字典树来保存候选项,(2)使用纵向事务列表,(3)可并行实现支持度计算;

    一、字典树
      由于许多的候选项可能有相同的前缀,例如候选3-项“1,2,4”和“1,2,5”都有相同的前缀“1,2”,因此可以使用字典树保存。
    在这里插入图片描述
    二、事务的纵向表示

      存储一个对应于每个候选集的事务id列表(tidset),每个列表也可以被表示为一个位掩码(bitset)。例如下图,左侧为传统的事务表示,右侧为纵向表示,Candidate表示候选的项集,tidset则表示对应项集包含的事务记录,其可以使用bit码表示。例如1-项集只有第1和第4个事务存在,所以bit码可以写成1001。
      之所以可以使用纵向表示,是因为:
    (1)当判断两个项的组合是否是频繁项时,直接将二者对应的bit码按位求与计算,结果中1的个数即为支持度计数值。例如判断2-项集(1,3)的计数,则直接求1001和1111的按位与,结果为1001,则说明有两个事务满足这个20项集,再例如3-项集(1,3,5),则可以表示为(1,3)的1001和(5) 的1101按位与,结果为1001,说明也有两个事务同时包含项1、3、5。
    (2)使用纵向表示法,可以并行的对支持度进行计数,这也是第三个贡献。

    在这里插入图片描述
    三、并行支持度计算
      当使用纵向表示时,可以将纵向事务表划分为多个分块,每个分块置于GPU计算节点上,最后使用并行归约法获得总计数。

    在这里插入图片描述

    参考文献
    【4】Zhang F, Zhang Y, Bakos J. Gpapriori: Gpu-accelerated frequent itemset mining[C]//Cluster Computing (CLUSTER), 2011 IEEE International Conference on. IEEE, 2011: 590-594.


      博客记录着学习的脚步,分享着最新的技术,非常感谢您的阅读,本博客将不断进行更新,希望能够给您在技术上带来帮助。

    展开全文
  • 文章目录一、 问题背景与意义:二、 问题定义三、 经典关联规则挖掘算法四、 关联规则的应用五、 总结与展望六、 参考文献 一、 问题背景与意义: 数据挖掘作为一种从数据中获取信息的有效方法,越来越受到人们的...

    一、 问题背景与意义:

    数据挖掘作为一种从数据中获取信息的有效方法,越来越受到人们的重视。其中,关联规则挖掘首先被用来发现购物篮数据事务中项目之间的有趣联系。此后,关联规则成为数据挖掘领域的一个重要研究方向,广泛应用于医学、金融、互联网等多个领域。

    随着大数据时代的到来,数据的收集和存储愈加重要,许多场景也对从数据中挖掘出频繁模式有着愈加迫切的需求,比如从大量商务事务记录中发现有价值的相关模式,可以为分类设计、交叉销售和顾客购买习惯分析等许多商务决策过程提供帮助。因此,关联规则算法的研究十分具有现实意义。

    1993年,Agrawal 首次突出了关联规则概念,随后给出了关联规则挖掘问题描述和相应的挖掘算法。1994 年,Agrawal 等人建立了项目集格空间理论,提出了著名的 Apriori 算法[1],目前该算法已经成为关联规则挖掘的经典算法。1995年Park 等人[2]提出了一种基于散列( hash) 技术产生频繁项集的算法同年基于划分( partition) 的算法[3]也被提出,克服了 Apriori 算法 I /O 开销大的瓶颈。针对数据库中数据量大、扫描数据库次数多的问题,Toivonen[4]提出了基于采样思想的 Sampling 关联规则算法;之后Han 等人[5]提出了一种不产生候选集的发现频繁项集的挖掘方法 FP-growth,大大提升了算法的效率,成为又一里程碑式的工作。之后随着关联规则处理的数据量呈现指数级的增长,分布式的算法逐渐成为主流,Agrawal 等人[6]提出了CD、DD及CaD三种并行算法。基于DIC思想,Cheung 等人[7]提出了APM并行算法。针对 DD 算法效率低下的问题,Han等[8]引入了 IDD、HD 算法。由于新需求数据流累关联规则挖掘算法应运而生,Giannella 等人[9]提出的 FP-stream 频繁项集挖掘算法是数据流挖掘的经典算法。图的广泛应用使得研究者将其引入关联规则挖掘,针对基于Apriori思想的算法产生大量候选子图的缺点,出现了基于 FP-growth 的频繁子图挖掘算法gSpan、FFSM、closeGraph。Agrawal 和 Strikant 也提出了序列模式挖掘的概念,提出了经典的水平格式的类 Apriori 算法 GSP[10],和基于垂直格式的序列模式算法 SPADE[11]。

    二、 问题定义

    规则的支持度support和置信度confidence是规则兴趣度的两种度量。它们分别反映所发现规则的有用性和确定性。
    在这里插入图片描述
    项的集合称为项集。包含k个项的项集称为k项集。项集的出现频度是包含项集的事务数,简称为项集的频度、支持度计数或计数。如果项集I的支持度满足预定义的最小支持度阈值,则I是频繁项集。则有:
    在这里插入图片描述

    一般而言,关联规则的挖掘是一个两步的过程:
    (1) 找出所有的频繁项集:根据定义,这些项集的每一个频繁出现的次数至少与预定义的最小支持度min_sup一样;
    (2) 由频繁项集产生强关联规则:根据定义,这些规则必须满足最小支持度min_sup和最小置信度min_con。

    三、 经典的关联规则挖掘算法

    关联规则挖掘算法根据其实现原理大致可以分为层次算法、图搜索算法、并行算法,下面本文将分别对其进行介绍,并简述其中较为经典的挖掘算法。

    3.1 层次算法

    按照关联规则中涉及到的变量的层次可以把关联规则分为单层关联规则和多层关联规则。单层关联规则只涉及数据的一个维度;而多层关联规则要处理多维数据,涉及多个变量。其中Apriori算法是该系列算法的开山代表之作。
    

    3.1.1 Apriori算法描述

    Apriori经典关联规则挖掘算法基于两个核心理论: 频繁项集的子集是频繁项集; 非频繁项集的超集是非频繁项集。其核心思想如下图1所示[1]:
    在这里插入图片描述

    图1
    即首先,找出频繁1项集的集合,该集合记作L1,然后由L1经过连接步和剪枝步得到L2,再由L2经过连接步和剪枝步得到L3,如此循环下去,直到不能找到频繁k项集。每找一层均需要进行一次数据库扫描。最后,利用频繁项集构造出满足用户最小置信度的规则。挖掘和识别出所有频繁项集是该算法的核心,占整个计算量的大部分。

    a) Apriori算法分析
    可以看出,Apriori算法有两个致命的瓶颈:第一是可能在算法执行过程中产生庞大的候选项目集,这大大增加了算法的时空复杂度。第二是需要多次扫描数据库,造成大量的I/O操作,耗时耗力。
    当然,Apriori算法在数据集比较稀疏时候,频繁集长度较短时候还是具有很好的性能的。

    b) Apriori算法的改进
    虽然Apriori算法自身已经进行了一定的优化,但是在实际的应用中,还是存在不令人满意的地方,于是人们相继在其基础上提出了一些优化的方法。

    i)数据库划分改进
    在这里插入图片描述

    ii)数据采样改进
    Toivonen[4]提出了基于采样思想的 Sampling关联规则算法,该方法首先用从数据库 中抽取采样数据 得到一些在整个数据库中可能成立的规则,然后对数据库的剩余部分验证这个结果。
    抽样技术可以快速实现频繁项集的挖掘,但由于Sampling 算法利用随机抽样法进行采样,容易造成数据扭曲问题,导致样本数据库挖掘结果与数据库D 挖掘结果误差增大。

    3.1.2 FP-Growth算法

    a)算法描述
    针对Apriori算法的固有缺陷,Han等人提出了一个称为FP-Growth的算法[5]。它是不产生候选集而直接生成频繁集的频繁模式增长算法,该方法在经过第一遍扫描之后,把数据库中的频繁项目集压缩进一棵频繁模式树(FP-Tree),同时依然保留其中的关联信息。然后再将FP-Tree分化成一些条件库,每个库和S个长度为l的频繁项目集相关,然后再对这些条件库递归地进行挖掘。该算法的步骤大致如下所示:
    (1)按Apriori算法,扫描数据库一次生成1频繁集,并把它们按降序排列,放入L表中。
    (2)创建根节点,并标记为null,扫描数据库一次,当得到数据库的一个项目集时,就把其中的元素按L表的次序排列,然后递归调用FP-Growth来实现FP-Tree增长。
    (3)迭代重复(1)和(2),直到树包含一个元素项为止。

    b)算法性能分析
    算法中存储信息的FP-Tree保证了数据信息的完整性,而且FP-Growth算法在运行过程中只需要进行两次数据库扫描,而且不用生成候选集,相较于Apriori大大降低了时空复杂度。
    但是构建FP-Tree这个数据结构本身也会消耗时间和内存,如果这个树很大,对于算法来说也是得不偿失的。

    3.2 图挖掘算法

    图挖掘是指将关联分析用于基于图的数据,在图的集合中发现一组公共子结构,即频繁子图挖掘。gSpan算法是图挖掘邻域的一个算法,而作为子图挖掘算法,又是其他图挖掘算法的基础,可见gSpan算法在图挖掘算法中的重要性。其算法流程如下:
    1、遍历所有的图,计算出所有的边和点的频度。
    2、将频度与最小支持度数做比较,移除不频繁的边和点。
    3、重新将剩下的点和边按照频度进行排序,将他们的排名号给边和点进行重新标号。
    4、再次计算每条边的频度,计算完后,然后初始化每条边,并且进行此边的subMining()挖掘过程。

    3.3 并行算法

    基于 DIC 思 想,Cheung 等 人[7] 提 出了 APM 并 行 算 法, APM 采用全局剪枝技术约减候选 2-项集,这在数据分布不均时十分有效。首先把数据库转化成布尔矩阵,根据要求的k项频繁项集来对矩阵进行裁减,然后用待生成的k-项集设计的匹配矩阵对裁减后的布尔矩阵进行运算产生与匹配矩阵对应的频繁 k-项集。APM 算法流程如下图2所示:
    在这里插入图片描述

    图2

    3.4 数据流算法

    不同于传统的静态数据库模型,数据流是在线联机产生的,其具有连续、无界、无序的特征。因此,基于数据流的关联规则挖掘不能采用以往多次扫描数据的形式,而应随着数据更新进行单次扫描。为了适应数据流的特征,解决存储空间不足的问题,一般通过滑动窗口技术对数据流作区域性限制进行窗口查询。
    Giannella 等人[9]提出的 FP-stream 频繁项集挖掘算法是数据流挖掘的经典算法,它将倾斜时间窗口表嵌入到基于内存的频繁和亚频繁序列信息频繁模式树(pattern-tree) 中,挖掘出具有近似支持度的时间敏感频繁模式,并实现多时间粒度的频繁模式增量维护。根据概念“频繁闭项集提供一种不丢失支持 度信息的最小表示”,可以对频繁闭项集挖掘,这样在时间和空间的复杂性上提高了挖掘效率。

    3.5 序列算法

    Agrawal和Strikant最早提出了序列模式挖掘的概念,即从序列数据库中挖掘满足最小支持度的频繁子序列的过程。序列模式挖掘不同于关联规则挖掘项集属性内部的联系,它主要研究项集之间的联系。
    序列模式挖掘较为经典的是类Apriori算法GSP,它的基本思路如下:
    1、长度为1的序列模式 ,作为初始的种子集;
    2、根据长度为i的种子集 ,通过连接操作和剪切操作生成长度为i+1的候选序列模式,然后扫描数据库,计算每个候选序列模式的支持度,产生长度为i+1的序列模式并作为新的种子集。
    3、重复第二步,直到没有新的序列模式或新的候选序列模式产生为止。

    四、 关联规则的应用

    关联规则挖掘是数据挖掘领域的重要技术,是继贝叶斯、支持向量机等方法之后的又一项重要的分类技术,随着相关算法研究日渐成熟,被广泛应用于文本分类、医学图像分类、农业病虫防治、蛋白质结构预测、网络入侵检测等领域,并取得了喜人的成效。

    五、 总结与展望

    综上所述,本文给出了关联规则挖掘的学术定义,并在回顾前人在关联规则挖掘算法研究的基础上,将算法按照原理大致分为5类,在每类中重点介绍了其中较为经典的一两种算法,并进行对比分析。
    关联分析算法带给人们便利的同时也存在诸多不足。比如一些关联度很大的A、B事物之间也有可能是负相关的事物,从整体看才发现原来买A之前B的销售额更多,这就需要关联算法更加智能化和专业化,结合当下炙手可热的AI技术是一个不错的研究方向。
    关联规则挖掘经过长期的研究与发展,已在频繁模式挖掘算法的设计及优化方面日趋成熟,广泛应用于互联网、金融、生物信息等领域。但该领域在未来研究的方向是仍具有挑战性的工作;设计更高效的挖掘算法;实现用户与挖掘系统的交互,开发易于理解的可视化界面; 结合特殊领域完善扩展型挖掘算法,实现与其它系统的集成,如周期模式挖掘等; 拓展关联规则的应用领域。

    六、 参考文献

    [1] Agrawal R,Srikant R. Fast algorithms for mining association rules [C]/ /Proc of International Conference on Very Large Databases. 1994: 487-499.
    [2] Park J S,Chen M S,Yu P S. An effective hash-based algorithm for mining association rules[J]. SIGMOD Record,1995,25( 2) : 175- 186.
    [3] Savasere A,Omiecinski E,Navathe S. An efficient algorithm for mining association rules in large databases[C]/ /Proc of the 21st International Conference on Very Large Databases. 1995.
    [4] Toivonen H. Sampling large databases for association rules[C]/ /Proc of the 22nd International Conference on Very Large Databases. 1996
    [5] Han Jiawei,Pei Jian,Yin Yiwen. Mining frequent patterns without candidate generation[C]/ /Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press,2000: 1-12.
    [6] Agrawal R,Shafer J. Parallel mining of association rules[J]. IEEE Trans on Knowledge and Data Engeering,1996,8( 6) : 962-969
    [7] Cheung D W,Han J,Ng V,et al. A fast distributed algorithm for mining association rules[C]/ /Proc of International Conference on Parallel and Distributed Information Systems. 1996: 31-44.
    [8] Han E S,Karypis G,Kumar V. Scalable parallel data mining for association rules[C]/ /Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press,1997: 277-288.
    [9] Giannella C,Han Jiawei,Pei Jian,et al. Mining frequent patterns in data streams at multiple time granularities[J]. Next Generation Data Mining,2006,35( 1) : 61-84.
    [10] Srikant R,Agrawal R. Mining sequential patterns: generalizations and performance improvements[C]/ /Proc of the 5th International Conference on Extending Data Base Technology. 1996: 3-17.
    [11] Zaki M J. SPADE: an efficient algorithm for mining frequent sequences [J]. Machine Learning,2001,42( 1) : 31-60.

    展开全文
  • 关联规则挖掘算法

    千次阅读 2018-08-31 20:06:08
    关联规则挖掘是一种基于规则的机器学习算法,该算法可以在大数据库中发现感兴趣的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现,而非预测,所以是属于无监督的...

    关联规则挖掘是一种基于规则的机器学习算法,该算法可以在大数据库中发现感兴趣的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现,而非预测,所以是属于无监督的机器学习方法。

    “尿布与啤酒”是一个典型的关联规则挖掘的例子,沃尔玛为了能够准确了解顾客在其门店的购买习惯,对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛利用所有用户的历史购物信息来进行挖掘分析,一个意外的发现是:"跟尿布一起购买最多的商品竟是啤酒!

    关联规则挖掘算法不仅被应用于购物篮分析,还被广泛的应用于网页浏览偏好挖掘,入侵检测,连续生产和生物信息学领域。

    与序列挖掘算法不同的是,传统的关联规则挖掘算法通常不考虑事务内或者事件之间的顺序

    支持度和置信度

    那么我们如何能够从所有可能规则的集合中选择感兴趣的规则呢?需要利用一些度量方法来筛选和过滤,比较有名的度量方法是最小支持度(minimum support)最小置信度(minimum confidence)

    假定我们一个数据库包含5条事务,每行表示一个购物记录,1 表示购买,0 表示没有购买,如下图表格所示:

    ID | milk | bread | butter | beer | diapers
    ----|------|------|------|----
    1 | 1| 1 | 0 | 0 | 0
    2| 0| 0| 1| 0| 0
    3| 0| 0| 0| 1| 1
    4| 1| 1| 1| 0| 0
    5| 0| 1| 0| 0| 0

    让 X,Y 各表示为一个 item-set, X ⇒ Y 表示为一条规则(尿布 ⇒ 啤酒 就是一条规则),用 T 表示为事务数据库(并不是说只局限于事务数据库)。

    支持度(Support)

    支持度表示 item-set 在整个 T 中出现的频率。假定 T 中含有 N 条数据,那么支持度的计算公式为:

    譬如在上面的示例数据库中,{beer, diaper} 的支持度为 1/5 = 0.2。5 条事务中只有一条事务同事包含 beer和 diaper ,实际使用中我们会设置一个最低的支持度(minimum support),那些大于或等于最低支持度的 X 称之为频繁的 item-set 。

    置信度(Confidence)

    置信度表示为规则 X ⇒ Y 在整个 T 中出现的频率。而置信度的值表示的意思是在包含了 X 的条件下,还含有 Y 的事务占总事务的比例。同样假定 T 中含有 N 条数据,那么置信度的计算公式为:

    譬如再上面的示例数据库中,{beer, diaper} 的置信度为 0.2/0.2 = 1。表面在所有包含 beer 的事务中都会一定包含 diaper。同样的,在实际使用中我们会设置一个最低置信度,那些大于或等于最小置信度的规则我们称之为是有意义的规则。

    相关性度量

    有时候使用支持度和置信度挖掘到的规则可能是无效的。

    举个例子:

    10000 个事务中, 6000 个事务包含计算机游戏, 7500 个包含游戏机游戏, 4000 个事务同时包含两者。关联规则(计算机游戏 ⇒ 游戏机游戏) 支持度为 0.4 ,看似很高,但其实这个关联规则是一个误导。在用户购买了计算机游戏后有 (4000÷6000) = 0.667 的概率的去购买游戏机游戏,而在没有任何前提条件时,用户反而有 (7500÷10000) = 0.75的概率去购买游戏机游戏,也就是说设置了购买计算机游戏这样的前置条件反而会降低用户去购买游戏机游戏的概率,所以计算机游戏和游戏机游戏是相斥的,也即表明是独立的。

    因此我们可以通过下面的一些相关性度量方法来筛选挖掘到的规则。

    提升度(Lift)

    提升度可以用来判断规则 X ⇒ Y 中的 X 和 Y 是否独立,如果独立,那么这个规则是无效的。

    计算提升度的公式如下:

    如果该值等于 1 ,说明两个条件没有任何关联。如果小于 1 ,说明 X 与 Y 是负相关的关系,意味着一个出现可能导致另外一个不出现。大于 1 才表示具有正相关的关系。一般在数据挖掘中当提升度大于 3 时,我们才承认挖掘出的关联规则是有价值的。

    他可以用来评估一个出现提升另外一个出现的程度。

    提升度是一种比较简单的判断手法,实际中受零事务(也即不包含 X 也不包含 Y 的事务)的影响比较大。所以如果数据中含有的零事务数量较大,该度量则不合适使用。

    全置信度 和 最大置信度

    给定两个项集 X 和 Y ,其全置信度为

    不难知道,最大置信度为

    全置信度和最大置信度的取值都是从 0 ~ 1 ,值越大,联系越大。

    该度量是不受零事务影响的。

    KULC 度量 + 不平衡比(IR)

    给定两个项集 X 和 Y,其 Kulczynski(Kulc) 度量定义为:

    可以看做是两个置信度的平均值,同样取值也是从 0 ~ 1,值越大,联系越大,关系越大。

    该度量同样也是不受零事务影响的。

    Apriori 算法

    在执行算法之前,用户需要先给定最小的支持度和最小的置信度。
    生成关联规则一般被划分为如下两个步骤:
    1、利用最小支持度从数据库中找到频繁项集。

    给定一个数据库 D ,寻找频繁项集流程如下图所示

    频繁项集的流程示意图

    C1 中 {1} 的支持度为 2/4 = 0.5 表示在 D 中的 4 条事务中,{1} 出现在其中的两条事务中,以后几个步骤的支持度计算方式也是类似的。假定给定的最小支持度为 0.5,那么最后我们可以得到一个包含 3 个项的频繁项集 {2 3 5}。

    另外,从图中我们可以看到 itemset 中所包含的 item 是从 1 增长到 3 的。并且每次增长都是利用上一个 itemset 中满足支持度的 item 来生成的,这个过程称之为候选集生成(candidate generation)。譬如说 C2 里就不包含 C1 中的 4 。

    2、利用最小置信度从频繁项集中找到关联规则。

    同样假定最小的置信度为 0.5 ,从频繁项集 {2 3 5} 中我们可以发现规则 {2 3} ⇒ {5} 的置信度为 1 > 0.5 ,所以我们可以说 {2 3} ⇒ {5} 是一个可能感兴趣的规则。

    从第一步中我们看出每次计算支持度都需要扫描数据库,这会造成很大的 I/O 开销,所以有很多变种的算法都会在该问题上进行优化(FP-Growth)。此外如何有效的生成候选集也是很多变种算法优化的问题之一(Apriori-all)。

    总结

    • 关联规则是无监督的学习算法,能够很好的用于知识的发现。
    • 缺点是很难严重算法的有效性,一般只能够通过肉眼观察结果是否合理。



    作者:曾梓华
    链接:https://www.jianshu.com/p/7d459ace31ab
    來源:简书
    简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

    展开全文
  • 关联规则Apriori算法

    千次阅读 2020-10-20 09:13:30
    参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联...关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成,分别是 频繁项集(frequ.

    参考《【机器学习实战-python3】使用Apriori算法进行关联 分析》,《 使用Apriori进行关联分析(一)》,《使用Apriori进行关联分析(二)》,《关于apriori算法中置信度、支持度怎么理解的问题


    关联规则的目的在于分析出经常出现在一起的物品的集合之间的关系。Apriori算法本质由两部分组成,分别是

    1. 频繁项集(frequent item sets)。包括计算:频繁项集的支持度(support)
    2. 关联规则(association rules)。包括计算:关联规则的置信度(confidence)

    接下来分别对这几个名词进行讲解,同时串通整个Apriori算法。

    1. 频繁项集(frequent item sets)

    假设下表为一个超市的交易记录,其中交易ID可以看作每个前来购物的顾客商品列表就是每个顾客购买的商品。

    交易ID商品列表
    0P1, P2, P5
    1P2, P4
    2P2, P3
    3P1, P2, P4
    4P1, P3
    5P2, P3
    6P1, P3
    7P1, P2, P3, P5
    8P1, P2, P3

    单是肉眼去观察的话,似乎顾客经常购买P1, P2这样的组合。这种的购物中出现的经常的组合,就是我们要找的频繁项集了。项集可以由一个商品组成,也可以由多个商品组成。比如{P1}是一个项集,{P1, P2}也是一个项集。

    现实生活中的数据肯定比这更加庞大,因此需要使用算法来帮助我们筛选出来哪些是频繁项集。

    1.1 频繁项集的支持度(support)和阈值

    一个项集的支持度被定义为数据集中包含该项集的记录所占的比例,比如在上表中,9个顾客中有4个购买了P1商品和P2商品,项集{P1, P2}的支持度就是 4 / 9 = 0.44 4/9=0.44 4/9=0.44支持项就是4项.

    通常来说,我们会手动设置支持度的阈值。比如设置阈值为50%,这样支持度小于该阈值的时候,就认为该项集并不频繁,也就没有挖掘关联规则的意义,因此不会进行后续的计算。

    1.2 频繁项集的特点

    频繁项集拥有如下特点:**如果某个项集是频繁的,那么它的所有子集也是频繁的。**比如项集{P1, P2}是频繁的,那么项集{P1}和{P2}也是频繁的。该原理倒过来推并不成立,也就是说当我们 只发现{P1}和{P2}是频繁的的时候,是无法推出项集{P1, P2}是频繁的,因为有可能他们的频繁是依靠和别的商品一起购买组合而成的。该原理可以用下图表示
    在这里插入图片描述

    已知阴影项集{2,3}是非频繁的。利用这个知识,我们就知道项集{0,2,3} ,{1,2,3}以及{0,1,2,3}也是非频繁的。该特点的最大用处是帮助我们减少计算,一旦计算出了{2,3}的支持度,知道它是非频繁的之后,就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度,因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长,从而在合理时间内计算出频繁项集。

    1.3 频繁项集支持度计算方法

    频繁项集的计算方法并不复杂,主要就是三步的不断循环。

    1. 计算当前频繁项的所有并集,得到新的频繁项候选集
    2. 对得到的所有频繁项候选集进行支持项/支持度的计算
    3. 使用阈值过滤掉不符合要求的频繁项,最终剩下的成为新的频繁项

    在这里插入图片描述

    具体代码如下

    def loadDataSet():
        return [[1,2,5],[2,4],[2,3],[1,2,4],[1,3],[2,3],[1,3],[1,2,3,5],[1,2,3]]
    #1.构建候选1项集C1
    def createC1(dataSet):
        C1 = []
        for transaction in dataSet:
            for item in transaction:
                if not [item] in C1:
                    C1.append([item])
    
        C1.sort()
        return list(map(frozenset, C1))
    
    #将候选集Ck转换为频繁项集Lk
    #D:原始数据集
    #Cn: 候选集项Ck
    #minSupport:支持度的最小值
    def scanD(D, Ck, minSupport):
        #候选集计数
        ssCnt = {}
        for tid in D:
            for can in Ck:
                if can.issubset(tid):
                    if can not in ssCnt.keys(): ssCnt[can] = 1
                    else: ssCnt[can] += 1
    
        numItems = float(len(D))
        Lk= []     # 候选集项Cn生成的频繁项集Lk
        supportData = {}    #候选集项Cn的支持度字典
        #计算候选项集的支持度, supportData key:候选项, value:支持度
        for key in ssCnt:
            support = ssCnt[key] / numItems
            if support >= minSupport:
                Lk.append(key)
            supportData[key] = support
        return Lk, supportData
    
    #连接操作,将频繁Lk-1项集通过拼接转换为候选k项集
    def aprioriGen(Lk_1, k):
        Ck = []
        lenLk = len(Lk_1)
        for i in range(lenLk):
            L1 = list(Lk_1[i])[:k - 2]
            L1.sort()
            for j in range(i + 1, lenLk):
                #前k-2个项相同时,将两个集合合并
                L2 = list(Lk_1[j])[:k - 2]
                L2.sort()
                if L1 == L2:
                    Ck.append(Lk_1[i] | Lk_1[j])
    
        return Ck
    
    def apriori(dataSet, minSupport = 0.5):
        C1 = createC1(dataSet)
        L1, supportData = scanD(dataSet, C1, minSupport)
        L = [L1]
        k = 2
        while (len(L[k-2]) > 0):
            Lk_1 = L[k-2]
            Ck = aprioriGen(Lk_1, k)
            print("ck:",Ck)
            Lk, supK = scanD(dataSet, Ck, minSupport)
            supportData.update(supK)
            print("lk:", Lk)
            L.append(Lk)
            k += 1
    
        return L, supportData
    
    dataset = loadDataSet()
    L, supportData = apriori(dataset, minSupport=0.2)
    

    最终输出如下,其中ck就是频繁项候选集lk就是经过阈值筛选后得到的新的频繁项候选集。该结果与上图一致。

    ck: [frozenset({1, 2}), frozenset({1, 5}), frozenset({1, 4}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({4, 5}), frozenset({3, 5}), frozenset({3, 4})]
    lk: [frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 5}), frozenset({2, 4}), frozenset({2, 3}), frozenset({1, 3})]
    ck: [frozenset({1, 2, 5}), frozenset({1, 2, 3}), frozenset({1, 3, 5}), frozenset({2, 4, 5}), frozenset({2, 3, 5}), frozenset({2, 3, 4})]
    lk: [frozenset({1, 2, 5}), frozenset({1, 2, 3})]
    ck: [frozenset({1, 2, 3, 5})]
    lk: []
    

    需要注意的是,在上述代码的aprioriGen方法中,假定购买商品是有顺序的,可以通过频繁2项集{P1,P2},{P1,P3}推导出频繁项{P1,P2,P3},但是不能通过频繁2项集{P3,P4},{P1,P3}推导出频繁项{P1,P3,P4}。如果去掉假设,则需要修改aprioriGen的代码:

    #将频繁Lk-1项集转换为候选k项集
    def aprioriGen(Lk_1, k):
        Ck = []
        lenLk = len(Lk_1)
        for i in range(lenLk):
            L1 = Lk_1[i]
            for j in range(i + 1, lenLk):
                L2 = Lk_1[j]
                if len(L1 & L2) == k - 2:
                    L1_2 = L1 | L2
                    if L1_2 not in Ck:
                        Ck.append(L1 | L2)
        return Ck
    

    2. 关联规则挖掘(association rules)

    2.1 关联规则的置信度(confidence)

    我们的目的是根据频繁项集挖掘出关联规则。关联规则的意思就是通过某个项集可以推导出另一个项集。比如一个频繁项集{P1, P2, P3},就可以推导出六个可能的关联规则。其中置信度最高的就是最有可能的关联规则。

    • {P1} → {P2, P3}
    • {P2} → {P1, P3}
    • {P3} → {P1, P2}
    • {P1, P2} → {P3}
    • {P2, P3} → {P1}
    • {P1, P3} → {P2}

    箭头左边的集合称为“前件”,右边集合称为“后件”,根据前件会有较大概率推导出后件,这个概率就是之前提到的置信度(confidence)。需要注意的是,如果A→B成立,B→A不一定成立。

    一个具有N个元素的频繁项集,共有M个可能的关联规则:
    M = ∑ N − 1 i = 1 C N i M = \sum_{N-1}^{i=1}C_N^i M=N1i=1CNi
    下图是一个频繁4项集的所有关联规则网格示意图
    M = C 4 1 + C 4 2 + C 4 3 = 14 M = C_4^1+C_4^2+C_4^3=14 M=C41+C42+C43=14

    上图中深色区域表示低可信度规则,如果012→3是一条低可信度规则,则所有其它3为后件的规则都是低可信度。这需要从可信度的概念去理解

    • Confidence(012→3) = P(3|0,1,2)
    • Confidence(01→23) = P(2,3|0,1)
    • P(3|0,1,2) >= P(2,3|0,1)

    由此可以对关联规则做剪枝处理。

    在这里插入图片描述

    2.2 关联规则置信度的计算过程

    置信度的计算公式为
    置 信 度 = 频 繁 项 集 的 出 现 数 量 某 可 能 规 则 的 出 现 数 量 置信度 =\frac{频繁项集的出现数量}{某可能规则的出现数量} =
    还是以上篇的超市交易数据为例,我们发现了如下的频繁项集:
    在这里插入图片描述

    对于寻找关联规则来说,频繁1项集L1没有用处,因为L1中的每个集合仅有一个数据项,至少有两个数据项才能生成A→B这样的关联规则。

    当最小置信度取0.5时,L2最终能够挖掘出9条关联规则:在这里插入图片描述

    以P2->P1为例,在本文最上面的表格中,P2出现了7次,频繁项集{P1, P2}的出现次数为4次,因此P2->P1的支持度就是4/7。同理,P1出现了6次,那么P1->P2的支持度就是4/6.

    从频繁3项集开始,挖掘的过程就较为复杂,要计算如{P1, P2}这样的复合频繁项集后件,并分别计算置信度。
    在这里插入图片描述
    假设有一个频繁4项集(这是杜撰的,文中的数据不能生成L4),其挖掘过程如下:
    在这里插入图片描述
    发掘关联规则的代码如下

    #生成关联规则
    #L: 频繁项集列表
    #supportData: 包含频繁项集支持数据的字典
    #minConf 最小置信度
    def generateRules(L, supportData, minConf=0.7):
        #包含置信度的规则列表
        bigRuleList = []
        #从频繁二项集开始遍历
        for i in range(1, len(L)):
            for freqSet in L[i]:
                H1 = [frozenset([item]) for item in freqSet]
                if (i > 1):
                    rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
                else:
                    calcConf(freqSet, H1, supportData, bigRuleList, minConf)
        return bigRuleList
    
    
    # 计算是否满足最小可信度
    def calcConf(freqSet, H, supportData, brl, minConf=0.7):
        prunedH = []
        #用每个conseq作为后件
        for conseq in H:
            # 计算置信度
            conf = supportData[freqSet] / supportData[freqSet - conseq]
            if conf >= minConf:
                print(freqSet - conseq, '-->', conseq, 'conf:', conf)
                # 元组中的三个元素:前件、后件、置信度
                brl.append((freqSet - conseq, conseq, conf))
                prunedH.append(conseq)
    
        #返回后件列表
        return prunedH
    
    
    # 对规则进行评估
    def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
        m = len(H[0])
        if (len(freqSet) > (m + 1)):
            Hmp1 = aprioriGen(H, m + 1)
           # print(1,H, Hmp1)
            Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
            if (len(Hmp1) > 0):
                rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
    
    generateRules(L, supportData)
    

    得到的结果如下所示

    frozenset({5}) --> frozenset({1}) conf: 1.0
    frozenset({5}) --> frozenset({2}) conf: 1.0
    frozenset({4}) --> frozenset({2}) conf: 1.0
    frozenset({5}) --> frozenset({1, 2}) conf: 1.0
    [(frozenset({5}), frozenset({1}), 1.0),
     (frozenset({5}), frozenset({2}), 1.0),
     (frozenset({4}), frozenset({2}), 1.0),
     (frozenset({5}), frozenset({1, 2}), 1.0)]
    

    3. 为什么需要置信度和支持度同时确定关联规则

    以超市购物为例。

    TIDItems
    1Bread, Milk
    2Break, Diaper, Beer, Eggs
    3Milk, Diaper, Beer, Coke
    4Bread, Milk, Diaper, Beer
    5Bread, Milk, Diaper, Coke

    TID是transaction ID 即交易编号,也就是有五个人在超市买了这样的东西(Iteams),现在我们统计一下,大家买的东西之间有没有什么规律,比如买面包的是不是很可能同时买牛奶这样的规律。

    在这里,支持度的计算过程为
    s u p p o r t = σ ( M i l k , D i a p e r , B e e r ) ∣ T ∣ = 2 5 = 0.4 support =\frac{\sigma(Milk, Diaper, Beer)}{|T|} = \frac{2}{5}=0.4 support=Tσ(Milk,Diaper,Beer)=52=0.4

    支持度越大,说明同时买这三个东西的人多,说明这三者之间有关系.

    但是当交易量特别大的时候,假如有一万个人买东西,只有10个人同时买了Milk、Diaper、Beer,但其他9990个人没有买这三者中的任何一个,那么此时S=10/10000=0.001。如果仅从这个0.001看,这三者之间没有任何关系,但是事实却不是这样,因为只有十个人这样买,并且同时买了这三种东西,所以他们之间应该是由关系的,而不是偶然。

    引入置信度的概念后,比如我们想看{Milk, Diaper}→{Beer}的置信度,则计算过程为
    c o n f i d e n c e = σ ( M i l k , D i a p e r , B e e r ) σ ( M i l k , D i a p e r ) = 2 3 = 0.67 confidence=\frac{\sigma(Milk, Diaper, Beer)}{\sigma(Milk, Diaper)} = \frac{2}{3}=0.67 confidence=σ(Milk,Diaper)σ(Milk,Diaper,Beer)=32=0.67
    和S支持度比较只有分母变了,变成了买了Milk和Diaper两种东西的人,这个式子是说买了Milk和Diaper两种东西的人里面又有多少人买了Beer这个东西!

    在上面支持度为0.001的情况下,此时置信度=10/10=100%!足以说明两者之间的关联性。

    但是只有置信度也是不可行的,比如10000个订单中,只有一个人同时购买了Milk,Diaper和Bear,那么此时的置信度为1/1=100%!可是支持度只有0.0001,非常的小。

    所以正确的有关联的判定是:置信度和支持度都应该比较大才可以认为这些东西之间有关联!

    展开全文
  • 关联规则算法   数据挖掘是指以某种方式分析数据源,从中发现一些潜在的有用的信息,其中关联规则挖掘是数据挖掘中的一个重要课题,它是从数据背后发现事物之间可能存在的关联或者联系。比如经调查发现30%的顾客会...
  • Apriori算法经典的挖掘频繁项集的算法,第一次实现了再大数据集上可行的关联规则提取,其核心思想是通过连接产生候选项与其支持度,然后通过剪枝生成频繁项集。 1.关联规则的一般方式 项...
  • 关联规则挖掘算法综述,姜丽莉,孟凡荣,关联规则挖掘是数据挖掘的重要研究领域之一。本文首先全面地关联规则的基本概念,包括项目、交易、支持度、置信度等,然后介绍了
  • MS关联规则分析算法

    2017-07-08 17:12:13
    MS关联规则分析算法 属于建议引擎算法,可根据已购买的...关联规则算法是Apriori算法的简单实现,下面是原理分析 3.1. 支持度:P(A∩B),既有A又有B的概率 3.2. 置信度:P(B|A),在A发生的事件中同时发生B的概率p
  • 关联规则挖掘这一章中,Apriori算法是非常重要的~之后本章的实验中也要实现—— 理解&自己编程实现Apriori算法 (所以要好好学一下哈~) 为啥需要Apriori算法呢?—— 在关联规则挖掘中,要产生频繁项集,要...
  • 关联规则DHP算法详解

    千次阅读 2016-09-29 17:05:38
    参考文献: [1]Park, J. S., Chen, M. S., & Yu, P. S. (1995). An effective hash-based algorithm for mining association rules.... Sigmod Record, 24(2), 175-... 关联规则dhp算法的研究与分析. 佛山科学技术学院学
  • Apriori算法是一种挖掘关联规则的频繁项集算法,其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持...
  • http://blog.csdn.net/lizhengnanhua/article/details/9061755
  • 摘要本文介绍了关联规则的基本概念和分类方法,列举了一些关联规则挖掘算法并简要分析了典型算法,展望了关联规则挖掘的未来研究方向。 关键词数据挖掘,关联规则,频集,Apriori算法,FP-树 1引言 ...
  • 数据关联规则分析算法

    千次阅读 2018-01-29 18:33:14
    数据关联规则(Associaton Rules,AR)是数据挖掘算法的重要目的之一,用于在海量数据中挖掘出具有价值的信息,通常在商业中用于数据与数据指尖的关系来产生更大的价值,典型的例子就是“啤酒与尿不湿”。 1、基于...
  • MAHOUT之关联规则挖掘算法

    千次阅读 2015-09-06 22:42:51
    需求说明目前正在对hive表中的数据做分析,期望从已有的数据中挖掘出类似购物篮的关联规则,但是单机环境下的关联规则算法实在是无法胜任大数据环境下的数据挖掘工作,无奈寻求大数据环境下的分布式挖掘算法,目前可...
  • 依据泛化值之间可能的相交或包含关系,将泛化值进行分层聚类,为了保存与不确定数据集挖掘相关的重要信息,给出了构建不确定频繁模式树的算法,在此 基础上,提出了UFI-DM子算法和GAR子算法,分别用于挖掘频繁项集和...
  • 关联规则算法总结

    千次阅读 2020-05-01 12:15:27
    关联规则A->B的支持度:1000个顾客购物,100个购买了面包和黄油。则面包->黄油 10% 可信度 关联规则A->B的可信度:1000个顾客购物,200个购买了面包和黄油,140个购买了黄油,则可信度为70%(140/200) ...
  • 2014/2015第二学期 多元统计分析课程设计 R Apriori 设计题目基于 语言的 算法在挖掘商品交易数据中的应用 摘 要 Apriori 算法是一种挖掘关联规则的频繁项集算法广泛应用于商业领域与 R arules Apriori 网络安全领域...
  • 针对这一问题,提出了一种基于树结构的关联规则挖掘算法。该算法运用关联矩阵将频繁项集映射到树结构中存储,并利用树中包含部分频繁项集的子树,逐步拓展成包含所有频繁项集的树结构;其不仅提高了候选项集的生成...
  • 关联规则算法Apriori以及FP-growth学习最近选择了关联规则算法进行学习,目标是先学习Apriori算法,再转FP-growth算法,因为Spark-mllib库支持的关联算法是FP,随笔用于边学边记录,完成后再进行整理一、概述关联...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 112,339
精华内容 44,935
关键字:

关联规则的经典算法包括