精华内容
下载资源
问答
  • 数据挖掘——关联规则挖掘
    千次阅读
    2022-04-14 15:54:57

    《数据挖掘》国防科技大学
    《数据挖掘》青岛大学

    数据挖掘之关联规则挖掘

    关联规则挖掘(Association Rule Mining)最早是由Agrawal等人提出。最初的动机是解决购物篮分析(Basket Analysis)问题,目的是发现交易数据库(Transaction Database)中不同商品之间的联系规则。

    1. 定义

    关联规则是描述在一个交易中物品之间同时出现的规律的知识模式,更确切的说,关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。
    关联分析 association analysis:关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系,所发现的模式通常用关联规则或频繁项集的形式表示。
    在这里插入图片描述

    形式化描述

    • 关联规则挖掘的交易数据集记为D
    • D ={T1,T2,…,Tk,…,Tn},Tk(k=1,2,…,n)称为交易,每个交易有唯一的标识,记作TID。
    • 元素 im(m=1,2,…,p)称为项。在交易数据集中,每个项 ik 代表一种商品的编号或名称。
    • 设 I = { i1,i2,…,im}是 D 中全体项组成的集合。D 中的每个事务Tk都是 I 的一个子集,即 Tk ⊆ I ( j=1,2,…,n)。
    • 由 I 中部分或全部项构成的一个集合称为项(itemset),任何非空项集中均不含有重复项。若 I 包含m个项,那么可以产生2m个非空项集。
    • 设 X 是一个 I 中项的集合,如果 X ⊆ Tk,那么称交易 Tk 包含项集 X。
    ◆ 若X,Y为项集,X⊂I, Y⊂I,并且X∩Y=Ø,则形如X→Y的表达式称为关联规则。

    度量

    • 支持度(support)
      支持度是对关联规则重要性的衡量,反映关联是否是普遍存在的规律,体现这条规则在所有交易中有多大的代表性。记为:support(X→Y)
      在这里插入图片描述
    • 置信度(confidence)
      置信度(或可信度、信任度)是对关联规则准确度的衡量,度量关联规则的强度。即在所有出现了X的活动中出现Y的频率,说明规则X→Y的必然性有多大。记为confidence(X→Y)。
      在这里插入图片描述

    基本概念

    • 挖掘关联规则
      在给定一个交易数据集D上,挖掘关联规则问题就是产生支持度和置信度分别大于等于用户给定的最小支持度阈值和最小置信度阈值的关联规则。
    • 支持度计数
      一般地,项集支持度是一个0~1的数值,由于在计算项集支持度时,所有分母是相同的,所以可以用分子即该项集出现的次数来代表支持度,称为支持度计数。
    • 频繁项集
      给定全局项集 I 和交易数据集 D,对于 I 的非空项集 I1,若其支持度大于或等于最小支持度阈值min_sup,则称 I1 为频繁项集(Frequent Itemsets)。
    • k-项集和频繁 k-项集
      对于I的非空子集 I1,若项集 I1 中包含有 I 中的 k 个项,称 I1 为 k-项集。若 k-项集 I1 是频繁项集,称为频繁 k-项集。
    • 超集
      如果一个集合S2中的每一个元素都在集合S1中,且集合S1中可能包含S2中没有的元素,则集合S1就是S2的一个超集,反过来,S2是S1的子集。 S1是S2的超集,若S1中一定有S2中没有的元素,则S1是S2的真超集,反过来S2是S1的真子集。

    2. 基本过程

    ① 找频繁项集:通过用户给定最小支持度阈值min_sup,寻找所有频繁项集,即仅保留大于或等于最小支持度阈值的项集。
    ② 生成强关联规则:通过用户给定最小置信度阈值min_conf,在每个最大频繁项集中寻找关联规则,即删除不满足最小置信度阈值的规则。
    注意:一个频繁X项集能够生成2X-2个候选关联规则

    3. 原始方法

    蛮力法(brute-force approach):计算每个可能的规则的支持度和置信度
    计算代价过高(可能提取的规则的数量达指数级)

    4. Apriori

    先验原理:
    · 如果一个项集是频繁的,则它的所有子集一定也是频繁的;相反,如果一个项集是非频繁的,则它的所有超集也一定是非频繁的。→提前剪枝
    注意事项:

    • 项的字典序:尽管集合具有无序性,但为了快速连接操作,通常对所有商品做一个默认的排序(类似于建立一个字典索引)。
    • 项的连接:可以降低候选项的生成
      在这里插入图片描述
      例子:
      在这里插入图片描述
      算法特点:
    • 多次扫描数据库
    • 候选项规模庞大
    • 计算支持度开销大
      提高算法性能的方法:
    • 散列项集计数 Hash-based itemset counting
    • 事务压缩 Transaction reduction
    • 划分 Partitioning
    • 采样 Sampling

    FPGrowth

    基本思想:

    • 只扫描数据库两遍,构造频繁模式树(FP-Tree)
    • 自底向上递归产生频繁项集
    • FP树是一种输入数据的压缩表示,它通过逐个读入事务,并把每个事务映射到FP树中的一条路径来构造。
      构造FP树:
    • 扫描数据库,得到频繁1-项集,并把项按支持度递减排序
    • 再一次扫描数据库,建立FP-tree(遍历每一个事务,构造成一条路径,并给项计数)
      在这里插入图片描述
      生成条件模式:
    • 从FP-tree的头表开始
    • 按照每个频繁项的连接遍历FP-tree
    • 列出能够到达此项的所有前缀路径,得到条件模式基
      在这里插入图片描述
      递归生成FP树:
      对每个模式库,计算库中每个项的支持度,用模式库中的频繁项建立FP-tree
      在这里插入图片描述
      优点:
    • 完备性:不会打破交易中的任何模式,包含了频繁模式挖掘所需的全部信息
    • 紧密性:支持度降序排列,支持度高的项在FP-tree中共享的机会也高;绝不会比原数据库大

    Apriori和FP-tree性能对比

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

    更多相关内容
  • 关联分析的一个典型例子是购物篮分析。在大数据时代,关联分析是最常见的数据挖掘任务之一。 概述 关联分析是一种简单、实用的分析技术,是指发现存在于大量数据集中的关联性或相关性,从而描述一个事物中某些属性...
  • 关联规则分析

    2022-02-19 14:20:51
    Y含义事务仅包含其涉及到的项目,而不包含项目的具体信息支持度 (support)置信度 (confidence)提升度 (lift)三、实验分析1、自制数据集2、电影数据集题材关联规则分析 一、经典案例 在美国,一些年轻的父亲下班后...

    一、经典案例

    • 在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,超市也因此发现了一个规律,在购买婴儿尿布的年轻父亲们中,有30%~40%的人同时要买一些啤酒。超市随后调整了货架的摆放,把尿布和啤酒放在一起,明显增加了销售额。如图1所示。
    • 若两个或多个变量的取值之间存在某种规律性,就称为关联。
    • 关联规则是寻找在同一个事件中出现的不同项的相关性,比如在一次购买活动中所买不同商品的相关性。
    • 例如:“在购买计算机的顾客中,有20%的人也同时购买了打印机。”
      在这里插入图片描述
    图1 购买尿布和啤酒的关联规则集合

    二、相关概念

    图2为一个实例。
    在这里插入图片描述

    图2 关联规则实例
    • 一个样本称为一个“事务”
    • 每个事务由多个属性来确定,这里的属性称为“项”
    • 多个项组成的集合称为“项集”

    由k个项构成的集合

    • {牛奶}、{花生酱}都是1-项集;
    • {牛奶, 啤酒}是2-项集;
    • {啤酒, 面包, 牛奶}是3-项集

    X=>Y含义

    • X和Y是项集
    • X称为规则前项(antecedent)
    • Y称为规则后项(consequent)

    事务仅包含其涉及到的项目,而不包含项目的具体信息

    • 在超级市场的关联规则挖掘问题中事务是顾客一次购物所购买的商品,但事务中并不包含这些商品的具体信息,如商品的数量、价格等。

    支持度 (support)

    • 一个项集或者规则在所有事务中出现的频率。 σ ( X ) \sigma(X) σ(X):表示项集 X X X的支持度计数
    • 项集 X X X的支持度: s ( X ) = σ ( X ) / N s(X)=\sigma(X)/N s(X)=σ(X)/N
    • 规则 X = > Y X=>Y X=>Y表示项集 X X X对项集 Y Y Y的支持度,也就是项集 X X X和项集 Y Y Y同时出现的概率
    • 某天共有100个顾客到电脑城购买物品,其中有20个顾客同时购买了计算机和打印机,那么上述的关联规则的支持度就是20%

    置信度 (confidence)

    • 确定 Y Y Y在包含 X X X的事务中出现的频率,即: c ( X = > Y ) = σ ( X ∪ Y ) / σ ( X ) c(X=>Y) = \sigma(X\cup Y)/\sigma(X) c(X=>Y)=σ(XY)/σ(X)
    • P ( Y ∣ X ) = P ( X Y ) / P ( X ) P(Y|X)=P(XY)/P(X) P(YX)P(XY)/P(X)
    • 置信度反应了关联规则的可信度,即购买了项集 X X X中的商品的顾客同时也购买了 Y Y Y中商品的可能性有多大
    • 购买咖啡的顾客中有50%的人购买了茶叶,则置信度为50%

    如图3所示,规则 ( A , B ) = > C (A,B)=>C (A,B)=>C

    • 支持度:交易中包含 { A , B , C } \{A,B,C\} {A,B,C}的可能性 (25%)
    • 置信度:在 { A , B } \{A,B\} {A,B}交易的前提下包含 C C C的条件概率 (100%)
      在这里插入图片描述
    图3

    设最小支持度为50%, 最小可信度为 50%, 则可得到 :

    • A = > C A=>C A=>C (50%, 66.6%)
    • C = > A C=>A C=>A (50%, 100%)

    若关联规则 X = > Y X=>Y X=>Y的支持度和置信度分别大于或等于用户指定的最小支持度 m i n s u p p o r t minsupport minsupport和最小置信度 m i n c o n f i d e n c e minconfidence minconfidence,则称关联规则 X = > Y X=>Y X=>Y为强关联规则,否则称关联规则 X = > Y X=>Y X=>Y为弱关联规则。

    提升度 (lift)

    • l i f t ( A = > B ) = c o n f i d e n c e ( A = > B ) / s u p p o r t ( B ) = P ( B ∣ A ) / P ( B ) lift(A=>B)=confidence(A=>B)/support(B)=P(B|A)/P(B) lift(A=>B)=confidence(A=>B)/support(B)=P(BA)/P(B)
    • 现在有1000 个消费者,有500人购买了茶叶,其中有400人同时购买了咖啡,另100人没有。由于confidence(茶叶=>咖啡)=450/500=80%,由此可能会认为喜欢喝茶的人往往喜欢喝咖啡。但如果另外没有购买茶叶的500人,其中同样有400人购买了咖啡,同样是很高的置信度80%,由此,得到不爱喝茶的也爱喝咖啡。这样看来,其实是否购买咖啡,与有没有购买茶叶并没有关联,两者是相互独立的,其提升度为90%/[(450+450)/1000]=1 。

    由此可见, l i f t lift lift正是弥补了 c o n f i d e n c e confidence confidence的这一缺陷,如果 l i f t = 1 lift=1 lift=1,则 X X X Y Y Y独立, X X X Y Y Y出现的可能性没有提升作用,其值越大 ( l i f t > 1 ) (lift>1) (lift>1),则表明 X X X Y Y Y的提升程度越大,也表明关联性越强。
    图4为一实例,可以看出, X X X Y Y Y的提升作用最大。
    在这里插入图片描述

    图4

    三、实验分析

    自制数据集

    可以使用mlxtend工具包得出频繁项集与规则,导包如下:

    import pandas as pd
    from mlxtend.frequent_patterns import apriori
    from mlxtend.frequent_patterns import association_rules
    

    自定义一份购物数据集,即:

    retail_shopping_basket = {'ID':[1,2,3,4,5,6],
                             'Basket':[['Beer', 'Diaper', 'Pretzels', 'Chips', 'Aspirin'],
                                       ['Diaper', 'Beer', 'Chips', 'Lotion', 'Juice', 'BabyFood', 'Milk'],
                                       ['Soda', 'Chips', 'Milk'],
                                       ['Soup', 'Beer', 'Diaper', 'Milk', 'IceCream'],
                                       ['Soda', 'Coffee', 'Milk', 'Bread'],
                                       ['Beer', 'Chips']]
    }
    

    展示一下:

    retail = pd.DataFrame(retail_shopping_basket)
    pd.options.display.max_colwidth=100
    retail
    

    在这里插入图片描述
    需要将现实数据转换成one-hot编码格式。
    首先,剔除无关特征。

    retail_id = retail.drop('Basket',1)
    retail_id
    

    显示如下:
    在这里插入图片描述
    其次,使用join()方法将列表改成字符串:

    retail_Basket = retail['Basket'].str.join(',')
    retail_Basket
    

    在这里插入图片描述
    然后,利用get_dummies()将分类变量转换为虚拟/指示符变量:

    retail_Basket = retail_Basket.str.get_dummies(',')
    retail_Basket
    

    在这里插入图片描述
    最后,将无关特征加进来即可:

    retail = retail_id.join(retail_Basket)
    retail
    

    在这里插入图片描述
    计算该数据集的支持度:

    frequent_itemsets = apriori(retail.drop('ID',1), use_colnames=True)
    frequent_itemsets
    

    在这里插入图片描述
    如果光考虑支持度support(X>Y),[Beer, Chips]和[Beer, Diaper]一样,哪一种组合更相关呢?因此,需要计算提升度:

    association_rules(frequent_itemsets,metric='lift')
    

    在这里插入图片描述
    显然{Diaper, Beer}更相关一些

    电影数据集题材

    数据集来源:https://grouplens.org/datasets/movielens/
    查看该数据集前10项内容,显示如下:
    在这里插入图片描述
    数据集中包括电影名字与电影类型的标签,第一步还是先转换成one-hot格式,并把无关特征设置为索引:

    movies_ohe = movies.drop('genres',1).join(movies.genres.str.get_dummies('|'))
    movies_ohe.set_index(['movieId','title'],inplace=True)
    pd.options.display.max_columns=100
    movies_ohe.head()
    

    部分显示如下:
    在这里插入图片描述

    movies_ohe.shape
    

    (9125, 20),说明数据集包括9125部电影,一共有20种不同类型。
    计算支持度大于0.015的频繁项集:

    frequent_itemsets_movies = apriori(movies_ohe,min_support=0.015,use_colnames=True)
    frequent_itemsets_movies
    

    在这里插入图片描述
    计算提升度大于1.25的项集:

    rules_movies = association_rules(frequent_itemsets_movies,metric='lift',min_threshold=1.25)
    rules_movies
    

    在这里插入图片描述
    计算提升度大于8的强关联项集,并按提升度值降序排列:

    rules_movies[(rules_movies['lift']>8)].sort_values(by=['lift'], ascending=False)
    

    在这里插入图片描述
    这说明Children和Animation这两个题材是最相关的。
    把包括{Children, Animation}的电影数据显示出来:

    movies[(movies.genres.str.contains('Children')) & (movies.genres.str.contains('Animation'))]
    

    在这里插入图片描述

    展开全文
  • 调用apriori进行关联规则分析,具体代码如下,其中数据集选取本博客 “机器学习算法——关联规则” 中的例子,可进行参考,设置最小支持度(min_support)为0.4,最小置信度(min_threshold)为0.1, 最小提升度...
  • 关联规则挖掘和序列模式挖掘的Apriori算法,介绍了关联规则和序列模式的基本概念,Apriori算法的思想和伪代码,挖掘频繁项集的例子
  • 关联规则挖掘(上)

    2021-08-08 11:04:23
    关联规则分析用于在一个数据集中找出各数据项之间的关联关系,广泛用于购物篮数据、生物信息学、医疗诊断、网页挖掘和科学数据分析中。 一、关联规则分析概述 关联规则分析又称购物篮分析,最早是为了发现超市销售...

    主要内容
    关联规则分析概述
    频繁项集、闭项集和关联规则
    频繁项集挖掘方法
    关联模式评估方法
    Apriori算法应用
    关联规则挖掘(上)
    关联规则挖掘(下)

    关联规则分析用于在一个数据集中找出各数据项之间的关联关系,广泛用于购物篮数据、生物信息学、医疗诊断、网页挖掘和科学数据分析中。

    一、关联规则分析概述

    关联规则分析又称购物篮分析,最早是为了发现超市销售数据库中不同商品之间的关联关系。
    采用关联模型比较典型的案例是“尿布与啤酒”的故事。
    关联规则分析通过量化的数字描述某物品的出现对其他物品的影响程度,是数据挖掘中较活跃的研究方法之一。目前,常用的关联规则分析算法如表6-1所示。
    在这里插入图片描述

    二、频繁项集、闭项集和关联规则

    关联规则分析最早是为了发现超市销售数据库中不同商品间的关联关系。
    频繁模式(Frequent Pattern)是指频繁出现在数据集中的模式(如项集,子序列或子结构)。挖掘频繁模式可以揭示数据集的内在的、重要的特性,可以作为很多重要数据挖掘任务的基础,比如:

    在这里插入图片描述
    1.关联规则的表示形式

    模式可以用关联规则(Association Rule)的形式表示。例如购买计算机也趋向于同时购买打印机,可以用如下关联规则表示。

    在这里插入图片描述
    规则的支持度(Support)和置信度(Confidence)是规则兴趣度的两种度量,分别反映规则的有用性和确定性。

    2.频繁项集和闭项集

    在这里插入图片描述
    同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称为强关联规则。
    在这里插入图片描述
    一般来说,关联规则的挖掘可以看作两步的过程:

    (1)找出所有频繁项集,该项集的每一个出现的支持度计数≥ min_sup;
    (2)由频繁项集产生强关联规则,即满足最小支持度和最小置信度的规则。

    由于第2步的开销远小于第1步,因此挖掘关联规则的总体性能由第1步决定。第1步主要是找到所有的频繁k项集,而在找频繁项集的过程中,需要对每个k项集,计算支持度计数以发现频繁项集,k项集的产生过程如图6.1
    在这里插入图片描述
    在这里插入图片描述
    因此,项集的个数太大严重影响算法的效率。为了克服这一困难,引入闭频繁项集和极大频繁项集的概念。
    项集X在数据集D中是闭的(Closed),如果不存在X的真超项集Y使得Y与X在D中具有相同的支持度计数。

    三、频繁项集挖掘方法

    Apriori算法

    Apriori算法是Agrawal和Srikant于1994年提出,是布尔关联规则挖掘频繁项集的原创性算法,通过限制候选产生发现频繁项集。Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索(k+1)项集。具体过程描述如下:首先扫描数据库,累计每个项的计数,并收集满足最小支持度的项找出频繁1项集记为L1。然后使用L1找出频繁2项集的集合L2,使用L2找出L3,迭代直到无法再找到频繁k项集为止。找出每个Lk需要一次完整的数据库扫描。

    Apriori算法使用一种称为先验性质的特性进行搜索空间的压缩,即频繁项集的所有非空子集也一定是频繁的。
    在这里插入图片描述
    Apriori算法产生k项频繁集的过程主要包括 连接剪枝 两步。

    在这里插入图片描述
    (2)剪枝
    Ck是Lk的超集,Ck的成员不一定全部是频繁的,但所有频繁的k项集都包含在Ck中。为了减少计算量,可以使用Apriori性质,即如果一个k项集的(k-1)子集不在Lk-1中,则该候选不可能是频繁的,可以直接从Ck删除。这种子集测试可以使用所有频繁项集的散列树快速完成。
    在这里插入图片描述
    由频繁项集产生关联规则

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

    提高Apriori算法的效率

    Apriori算法使用逐层搜索的迭代方法,随着k的递增不断寻找满足最小支持度阈值的“k项集”,第k次迭代从k-1次迭代的结果中查找频繁k项集,每一次迭代都要扫描一次数据库。而且,对候选项集的支持度计算非常繁琐。

    为了进一步提高Apriori算法的效率,一般采用减少对数据的扫描次数、缩小产生的候选项集以及改进对候选项集的支持度计算方法等策略。

    1.基于hash表的项集计数
    2.事务压缩(压缩进一步迭代的事务数)
    3.抽样(在给定数据的一个子集挖掘)
    4.动态项集计数

    频繁模式增长算法

    Apriori算法的候选产生-检查方法显著压缩了候选集的规模,但还是可能要产生大量的候选项集。而且,要重复扫描数据库,通过模式匹配检查一个很大的候选集合。

    1.FP树原理

    频繁模式增长(FP-growth)是一种不产生候选频繁项集的算法,它采用分治策略(Divide and Conquer),在经过第一遍扫描之后,把代表频繁项集的数据库压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息;然后将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关,再对这些条件库分别进行挖掘(降低了I/O开销)。

    2.FP树构建过程示例

    第一次扫描数据库,导出频繁项的集合(1 项集),并将频繁项按支持度计数降序排列。
    在这里插入图片描述
    根据上述生成的项集,构造FP树,如图6-4所示。
    在这里插入图片描述
    在这里插入图片描述
    为了方便树的遍历,创建一个项头表,使每项通过一个结点链指向它在树中的位置。扫描所有的事务,得到的FP树如图6-5所示。
    在这里插入图片描述
    3.FP树挖掘
    (1)从FP树到条件模式基

    从项头表开始挖掘,由频率低的结点开始。在图6.5的FP树中,首先依据结点o在该路径上的支持度更新前缀路径上结点的支持度计数。在此基础上,得到o点的条件模式基{f,c,a,b,m,l:1},{f,b:1}。

    构建条件FP树。利用o点的条件模式基得到o点的条件FP树。如果该条件FP树有多条路径,则继续迭代,构造条件FP树。否则,如果该FP树只有一条路径,则直接求以该结点结尾的频繁项集。

    FP-growth方法将发现长频繁模式的问题转换化为在较小的条件数据库中递归地搜索一些较短模式,然后连接后缀。它使用最不频繁的项做后缀,提供了较好的选择性,显著降低了搜索开销。

    当数据库很大时,构造基于主存的FP树是不现实的,一种有趣的选择是将数据库划分成投影数据库集合,然后在每个投影数据库上构造FP树并进行挖掘。

    使用垂直数据格式挖掘频繁项集

    Apriori算法和FP-growth算法都从TID项集格式(即{TID:itemset})的事务集中挖掘频繁模式。其中TID是事务标识符,而itemset是事务TID中购买的商品。这种数据格式称为水平数据格式(Horizontal Data Format)。

    使用垂直数据格式有效地挖掘频繁项集,它是等价类变换(Equivalenc CLAss Transformation,Eclat)算法的要点。

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

    例6.3解释了通过探查垂直数据格式挖掘频繁项集的过程。首先,通过扫描一次数据集,把水平格式的数据转换成垂直格式。项集的支持度计数简单地等于项集的TID集的长度。从k=1开始,可以根据先验性质,使用频繁k项集来构造候选(k+1)项集。通过取频繁k项集的TID集的交,计算对应的(k+1)项集的TID集。重复该过程,每次k增加1,直到不能再找到频繁项集或候选项集。

    展开全文
  • 从购物篮分析关联规则挖掘 Apriori算法 ​ 随着大量数据不断的收集和存储,许多业界人士对于从他们的数据库中挖掘知识越来越感兴趣。对于商场而言,从大量的商务事务记录中发现有价值的的关联关系,可以为货物摆放...

    从购物篮分析到关联规则挖掘 Apriori算法

    ​ 随着大量数据不断的收集和存储,许多业界人士对于从他们的数据库中挖掘知识越来越感兴趣。对于商场而言,从大量的商务事务记录中发现有价值的的关联关系,可以为货物摆放和分析顾客购物习惯等许多商务决策过程提供帮助。

    购物篮分析

    ​ 购物篮分析是一个典型的关联规则挖掘实例,例如如下图所示的9次购物中不同顾客购物篮中的商品,以此可以分析商品之间的关联和顾客的购物习惯,可以分析顾客可能会在一次购物中同时购买哪些商品。

    在这里插入图片描述

    ​ 一种简单的分析策略是通过搜索上述9个购买事务中的商品集合,那些经常出现在同一个商品集合中的商品可以认为他们之间存在关联关系,有很大概率会被顾客同时购买。

    频繁项集

    ​ 为了便于分析,我们为商品引入数字ID,购买事务也用事务编号代替,上述9个购买事务用数字化表示如下表所示:

    在这里插入图片描述

    ​ 同时,我们引入一些基础概念:

    • 项集 itemset:在购物篮分析中一个购买事务就是一个项集,购物篮中的商品就是该项集的 , 包含 k 个项的项集称为 k 项集
    • 频度/支持度计数 support_count:包含指定项集的事务数称为支持度计数,在购物篮分析中指的是同一个商品集合出现的次数
    • 频繁项集 frequent itemset:满足最小支持度阈值的项集称为频繁项集,在购物篮分析中即为多次出现且满足最小频度的商品集合。

    ​ 我们预设频繁项集的最小频度为2,可以直观的看出 I 1 , I 2 , I 3 {I1,I2,I3} I1,I2,I3 I 1 , I 2 , I 5 {I1,I2,I5} I1,I2,I5 被同时购买的次数是2,所以这两种商品组合可以被视为频繁项集,且这些商品之间可能存在关联关系。

    关联规则

    ​ 频繁项集中的项可能存在关联关系,如何得出这种关系呢?一种简单的关联关系分析方法就是计算商品组合之间的条件概率,以 I 1 , I 2 , I 5 {I1,I2,I5} I1,I2,I5 为例得出商品之间关系过程如下:

    在这里插入图片描述

    ​ 我们考虑最小条件概率为 80% 的购买模式才被视为有效的关联关系,则只有第 3 条、第 5 条和第 6 条是有效的商品关联关系。对应到商品就是: 麦片 > (牛奶,面包);(牛奶,麦片) > 面包; (面包,麦片) > 牛奶。

    ​ 上面得到的这种商品的购买模式可以用关联规则的形式表示,例如:(牛奶,麦片) > 面包: { I 1 , I 5 } = > I 2 \left\{I1, I5\right\} => I2 {I1,I5}=>I2 可以使用如下的关联规则表示:
    { I 1 , I 5 } = > I 2 [ s u p p o r t = 22 % ; c o n f i d e n c e = 100 % ] \left\{I1, I5\right\} => I2[support = 22\%; confidence = 100\%] {I1,I5}=>I2[support=22%;confidence=100%]
    ​ 其中,关联规则的支持度 support 和置信度 confidence 是规则兴趣度的两个度量:

    • 支持度 support:支持度是指事件 A 和事件 B 同时发生的概率,即联合概率:

    s u p p o r t ( A = > B ) = P ( A B ) = s u p p o r t _ c o u n t ( A ⋂ B ) s u p p o r t _ c o u n t ( a l l ) support(A=>B) = P(AB)=\frac{support\_count(A \bigcap B)}{support\_count(all)} support(A=>B)=P(AB)=support_count(all)support_count(AB)

    • 置信度 confidence:置信度指的是发生事件 A 的情况下发生事件 B 的概率,即条件概率:

    c o n f i d e n c e ( A = > B ) = P ( B ∣ A ) = s u p p o r t _ c o u n t ( A ⋃ B ) s u p p o r t _ c o u n t ( A ) confidence(A=>B) = P(B|A)=\frac{support\_count(A \bigcup B)}{support\_count(A)} confidence(A=>B)=P(BA)=support_count(A)support_count(AB)

    • 强规则:同时满足预定义的最小支持度 (min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡)和最小置信度 (min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒)的规则称为强规则。

    关联规则挖掘步骤

    1. 找出所有的频繁项集:这些项集的每一个频繁出现的次数大于等于预定义的最小支持度计数(min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡_𝑐𝑜𝑢𝑛𝑡)
    2. 由频繁项集产生强关联规则:这些规则必须同时满足预定义的最小支持度(min_𝑠𝑢𝑝𝑝𝑜𝑟𝑡)和最小置信度(min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒)

    Apriori 算法

    ​ 超市中的商品种类数以万计,假设我们要分析其中 100 种商品的关联关系那这一百种商品可以构成的项集数目如下:

    在这里插入图片描述

    ​ 可见随着项数目的增加,项集的数目是呈指数级增长的,这将带来极大的计算和存储问题。为了提高频繁项集的搜索效率,Apriori 算法使用一种称为先验性质的重要性质用于压缩搜索空间。

    • 先验性质描述为:频繁项集的所有非空子集也一定是频繁的。
    • 先验性质的逆否命题如果一个项集是非频繁的,那么它的所有超集也都是非频繁的。

    ​ 如下图所示,例如项集 { I 1 , I 2 } \left\{I1,I2\right\} {I1,I2}是非频繁的,那么它的超集 { I 1 , I 2 , I 3 } , { I 1 , I 2 , I 4 } , { I 1 , I 2 , I 3 , I 4 } \left\{I1,I2,I3\right\},\left\{I1,I2,I4\right\},\left\{I1,I2,I3,I4\right\} {I1,I2,I3},{I1,I2,I4},{I1,I2,I3,I4}都是非频繁项集,采用这种性质可以大幅度的压缩频繁项集的产生和计算。

    在这里插入图片描述

    Apriori 算法原理

    ​ 如下图所示,Apriori 算法是一种逐层搜索的迭代方法,使用 k 项集去搜索 k+1 项。首先, 生成频繁 1 项集: 扫描数据库,累计每个项的计数,收集满足最小支持度的项形成频繁 1 项集记为 𝐿1。然后,基于 𝐿1找出频繁 2 项集记为 𝐿2 基于𝐿2找出频繁 3 项集记为 𝐿3,如此逐层迭代搜索,直到不能在产生新的频繁 k 项集。
    在这里插入图片描述

    ​ Apriori 算法中除了第一层频繁项集挖掘,后面的逐层迭代都由以下两个步骤组成:

    连接步生成候选项集集合

    ​ Apriori 算法在每一层搜索迭代中,通过将上一层频繁项集的集合 𝐿_𝑘−1与自身连接产生候选 k 项集的集合 𝐶𝑘。

    ​ 𝐿_𝑘−1中频繁项集 𝑙1 和 𝑙2 可连接的条件是: 𝑙1 和 𝑙2 的 k-2 个项是相同的。

    剪枝步生成频繁项集集合

    ​ 连接步生成的候选 k 项集的集合 𝐶𝑘 是待求的频繁 k 项集集合 L𝑘的超集。从 𝐶𝑘 中找出频繁项集需要反复扫描数据库,确定 𝐶𝑘 中每个候选的计数,并根据最小支持度确定 L𝑘。
    ​ 当事务中项的数目很大时,将产生巨大的搜索空间,为了压缩 𝐶𝑘,使用先验性质对 𝐶𝑘 进行剪枝。即任何非频繁的 k-1 项集都不是频繁 k 项集的子集。所以,如果一个候选 k 项集的 k-1 项子集不在 L_𝑘-1 中,则该候选是非频繁的并从 𝐶𝑘 中剔除。

    Apriori 算法实例

    ​ 基于前面购物篮分析例子中的 9 个事务,使用 Apriori 算法挖掘频繁项集。预设最小支持度为 20% 即最小支持度计数大于等于 2 ,最小置信度为 80%。

    1. 挖掘频繁 1 项集:扫描数据库 D 中的所有事务,对每一个项的出现次数计数,得到候选 1 项集集合 𝐶1,根据最小支持度 20% 即最小支持度计数为 2 确定频繁 1 项集集合 𝐿1。

    在这里插入图片描述

    1. 挖掘频繁2项集:首先,连接步: 将频繁 1 项集集合中的元素进行连接产生候选 2 项集集合 𝐶2。然后,剪枝步: 𝐶2 中所有候选的子集都是频繁的,所以不删除任何候选。最后,确定频繁项集 :扫描数据库 D 中的所有事务,对 𝐶2中的每一个候选项集的出现次数计数 ,根据最小支持度确定频繁 2 项集 𝐿2。

    在这里插入图片描述

    1. 挖掘频繁3项集:首先,连接步: 将频繁 2 项集集合中的元素进行连接产生候选 3 项集集合 𝐶3。然后,剪枝步: 检查 𝐶3 中候选项集的子集是否都是频繁的,如果存在非频繁的子集,将该候选项集从 𝐶3 中删除。最后,确定频繁项集 :扫描数据库 D 中的所有事务,对 𝐶3 中的每一个候选项集的出现次数计数 ,根据最小支持度确定频繁 3 项集 𝐿3。

    在这里插入图片描述

    1. 停止寻找频繁项集 { I 1 , I 2 , I 3 } \left\{I1,I2,I3\right\} {I1,I2,I3} { I 1 , I 2 , I 5 } \left\{I1,I2,I5\right\} {I1,I2,I5} 连接的唯一个候选项集是 { I 1 , I 2 , I 3 , I 5 } \left\{I1,I2,I3,I5\right\} {I1,I2,I3,I5},但是其子集 { I 1 , I 3 , I 5 } \left\{I1,I3,I5\right\} {I1,I3,I5} { I 2 , I 3 , I 5 } \left\{I2,I3,I5\right\} {I2,I3,I5} 都是非频繁的,该候选项集将被剪去得到的候选 4 项集集合 𝐶4 为空,算法终止。所以最终得到的最大频繁项集是 { I 1 , I 2 , I 3 } \left\{I1,I2,I3\right\} {I1,I2,I3} { I 1 , I 2 , I 5 } \left\{I1,I2,I5\right\} {I1,I2,I5}

    2. 由频繁项集产生关联规则:关联规则产生,首先,对于每个频繁项集 𝑙,产生 𝑙的所有非空子集集合 𝑆;然后,对于 𝑙的每个非空子集 𝑠, 𝑙 在 𝑠下的条件概率满足最小置信度 (min_𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒) 则可以输出规则 𝑠⇒(𝑙−𝑠),这个规则是满足最小支持度和置信度的强规则。
      在这里插入图片描述

    Apriori 算法Python实现

    # 产生频繁1项集
    def scanD(D, Ck,minSupport) :#识别频繁项目集
        S = {}
        for i in D:
            for j in Ck:
                if j.issubset(i): 
                    if j not in S.keys():
                        S[j] = 1
                    else:
                        S[j] += 1
        numItems = float(len(D)) 
        L= []
        N=[]
        supportData = {} #候选集项Ck的支持度字典(key:候选项,value: 文持度)
        for key in S:
            support = S[key] / numItems
            supportData[key] = support
            if support >= minSupport:
                L. append(key)
            else:
                N.append(key)
        return L,N,supportData
    
    # Apriori算法 连接步和剪枝步
    def aprioriGen(Lk,k,N):
        Ck=[]
        lenLk = len(Lk)
        for i in range(lenLk):
            # 连接步 (子连接运算)
            for j in range(i + 1,lenLk):
                L1 = list(Lk[i])[:k - 2]
                L1.sort()
                L2 = list(Lk[j])[:k - 2]
                L2.sort()
                if L1==L2:
                    Ck.append(Lk[i]|Lk[j])#加入并集
            # 剪枝步 把子集中有属于非频繁项目集的项目删掉
            for i in N:
                for j in Ck:
                    if set(i).issubset(j):
                        Ck.remove(j)                   
        return Ck
    
    # Apriori算法 逐层迭代
    def apriori(D,minSupport):
        C1 = createCl(D)
        L1,N,supportData = scanD(D,C1,minSupport)
        L=[L1]
        k=2
        while (len(L[k-2]) > 0):
            Ck = aprioriGen(L[k-2],k,N)
            Lk,Nk,supK = scanD(D,Ck,minSupport)
            supportData.update(supK)
            N += Nk
            L.append(Lk)
            k +=1
        return L,N,supportData
    

    Apriori 算法改进

    Apriori 仍可能产生大量的候选集

    ​ Apriori 算法虽然通过剪枝在很大程度上压缩了候选项集集合,但是在逐层迭代搜索过程中,如果要生成一个很长的规则,这将产生大量的中间元素,仍然会产生大量的候选集,需要大量的计算和存储资源。

    使用哈希函数生成候选集

    ​ 在基于 𝐿𝑘−1生成候选项集集合 𝐶𝑘时,直接使用哈希函数生成候选项集,达到压缩候选项集目的。
    ​ 例如上述 Apriori 实例中由 𝐿1生成候选项集集合 𝐶2 时,使用如下哈希函数创建哈希表:
    h ( x , y ) = ( 10 x + y ) m o d 7 h(x,y)= (10x+y) mod 7 h(x,y)=(10x+y)mod7
    ​ 如果预设最小支持度计数为 3 ,则哈希地址为 0 、 1 、 3 、 4 中的候选项集都不可能是频繁的直接被剔除。

    在这里插入图片描述

    频繁模式增长算法 FP-growth

    ​ FP-growth 算法直接避免了繁杂而开销巨大的候选项集生成过程,采用如下分治策略:
    ​ (1) 首先,将代表频繁项集的数据库压缩到一棵频繁模式树 FP-Tree
    ​ (2) 然后,把这种压缩后的数据库划分成一组条件数据库 ,每个数据库关联一个频繁项或模式段,并分别挖掘每个条件数据库。对于每个模式段只需要考察与它相关联的数据集。随着被考察模式的增长,这种方法可以显著地压缩被搜索的数据集大小。

    1. 构造频繁模式树 FP-tree :首先,导出频繁 1 项集集合 𝐿,且将该频繁 1 项集集合按支持度计数降序排序 。然后,依据 𝐿构造频繁模式树,先创建树的根节点,用 null 标记;接着扫描数据库,将每个事务的项集中的项按 𝐿 的次序创建节点,并对每一个事物创建一个分枝。

    在这里插入图片描述

    1. 从FP-tree中挖掘频繁模式:从初始后缀模式即长度为1 的频繁模式开始挖掘,构造一个由 FP-tree 中与该后缀模式一起出现的前缀路径集组成的子数据库,称为该频繁模式的条件模式基。然后,构造该频繁模式的条件 FP-tree ,并递归地在该树上挖掘频繁模式。模式增长通过后缀模式与条件FP-tree产生的频繁模式连接实现。

    在这里插入图片描述

    Apriori 会产生大量虚假的关联规则

    ​ Apriori 算法衡量和生成关联规则的标准主要有两个,即支持度和置信度。但仅用这两个标准来衡量关联规则,往往会发现大量冗余的、虚假的关联规则。例如,有 10 个购物事物中有 6 个包含购买可口可乐的事物,有 7 个包含购买百事可乐的事务,同时包含购买可口可乐和百事可乐的事务有 4 个。预设最小支持度为 30%,最小置信度为 60%,使用 Apriori 算法可以得到如下关联规则:

    在这里插入图片描述

    ​ 事实上可口可乐和百事可乐的购买事务是负相关的,买一种会降低另一种被购买的可能性,所以这个关联规则是虚假的。

    ​ 可以看出仅仅使用支持度和置信度不足以过滤掉冗余的和虚假的关联规则。为此,可以使用相关性度量来扩充关联规则的支持度-置信度框架。加入了相关性度量的关联规则称为相关规则用如下形式表示:
    A = > B [ s u p p o r t , c o n f i d e n c e , c o r r e l a t i o n ] A => B [support, confidence,correlation] A=>B[support,confidence,correlation]
    ​ 常用的相关性度量由:

    1. 提升度:提升度是一种简单的相关性度量,如果值小于 1 表示 A 的出现和 B 的出现是负相关的,如果值大于 1 表示两者是正相关的,如果值等于 1 表示 A 和 B 是独立的,两者不具有相关性 。

    在这里插入图片描述

    1. 卡方检验:卡方检验也可以用于相关性度量通过表示实际观测值 (𝑎)与理论推断值 (𝑝)之间的偏离程度即卡方值大小来表示相关性 。 如果卡方值越大二者偏差程度越大呈负相关,反之二者偏差越小呈正相关,若两个值完全相等时,卡方值就为 0 表明理论值完全符合 表示事件互相独立 。

    在这里插入图片描述

    Apriori 对稀有信息分析效果差

    ​ Apriori 的频繁项集挖掘是基于最小支持度实现的,然而可能有一些有价值的规则的支持度小于这一预设的最小支持度或由于数据量较少无法正确生成相关规则。对于这种数据不平衡的情况,需要尽量减少事务总数的评估影响。

    零事务,提升度和卡方检验都受到被分析事务总数的影响,例如有102100 个事务中,可口可乐百事可乐被同时购买的事务有 100 个,可口可乐被单独购买的事务 1000 个,百事可乐被单独购买的事务有 1000 个。这个数据计算出来的提升度和卡方值都出现正关联错误评估。这是由大量的不包含那些考查项集的事务影响造成的,这些事务称为零事务 。实际情况中零事务的个数往往比被考察事务个数大很多。

    ​ 可以使用不平衡比来评估两个项集的不平衡程度,不平衡比值越大说明两个项集不平衡情况严重,若不平衡比值为 0 说明其平衡情况较好 ,计算公式如下:

    在这里插入图片描述

    ​ 常用的零不变性度量如下所示:

    在这里插入图片描述

    完整Apriori算法 PPT 和 Python 实现代码下载地址:下载地址

    展开全文
  • 关联规则挖掘

    2018-06-26 17:24:46
    原文关联规则挖掘基本概念定义一:设I={i1,i2,…,im}I={i1,i2,…,im},是m个不同的项目的集合,每个ikik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度,长度为k的项集称为k-项集。引例中每个商品...
  • 第三章 关联规则挖掘理论和算法;第三章 关联规则挖掘理论和算法;3.1 基本概念与解决方法;支持度与频繁项目集 ;支持度与频繁项目集 ;可信度与关联规则;关联规则挖掘基本过程;第三章 关联规则挖掘理论和算法;项目集格...
  • 重要概念关联规则挖掘关联规则的形式支持度置信度频繁项集3.挖掘关联规则的步骤【1】频繁项集的产生【2】规则的产生4.进行关联规则挖掘的方法【1】拿到一个数据集,首先——【2】减少候选项集的数量【3】减少比较的...
  • 关联规则挖掘 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系 关联规则挖掘的基本概念 关联规则挖掘(Association rule mining): ...购物篮分析关联规则挖掘的最初形式。 如,某商店经
  • 4、这些规则描述一个普遍的规律,这些规律可以帮我我们理解分析知识库中的数据,如找到一些国家通常与说同一种语言的国家交易。或结婚是一个对称关系,或使用同一个乐器的音乐家通常互相影响等等。 AMIE的目标是从...
  • 想必大家都听说过美国沃尔玛连锁超市“啤酒与尿不湿”的故事。...其实,这种通过研究已经产生的数据,将不同标的关联起来并挖掘二者之间联系的分析方法,就叫做关联分析法,也就是商场和电商领域的“购物篮分析”。 .
  • 关联规则Apriori算法例子

    千次阅读 2021-02-25 17:34:50
    '尿布', '啤酒'), ('面包', '牛奶', '尿布', '可乐')] # 挖掘频繁项集和频繁规则 itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1) print("频繁项集:\n", itemsets) print("关联规则:...
  • 关联规则挖掘-Apriori算法例题分析

    千次阅读 2021-10-12 16:39:33
    Apriori算法的基本思想是通过对数据的多次扫描来计算项集的支持度,发现所有的频繁项集从而生成关联规则 一: 找频繁项集关键是找到最小支持度或者最小支持计数,最小支持计数更加好理解。而找强关联规则,则是在...
  • 文章给出了改进的加权关联规则的定义,包括加权关联规则的支持度、信任度、有意义度及支持界等。设计了一套挖掘加权关联规则的行之有效的算法,并通过例子说明了算法的有效性。
  • 关联规则分析

    万次阅读 多人点赞 2017-11-27 17:11:03
    数据挖掘是指以某种方式分析数据源,从中发现一些潜在的有用的信息,所以数据挖掘又称作知识发现,而关联规则挖掘则是数据挖掘中的一个很重要的课题,顾名思义,它是从数据背后发现事物之间可能存在的关联或者联系。...
  • 关联规则挖掘算法

    千次阅读 2018-08-31 20:06:08
    “尿布与啤酒”是一个典型的关联规则挖掘例子,沃尔玛为了能够准确了解顾客在其门店的购买习惯,对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛利用所有用户...
  • 关联规则挖掘Apriori算法的实现

    千次阅读 2021-11-26 20:23:45
    2.利用weka工具对天气数据、美国国会议员投票信息、超市购物篮数据进行关联规则挖掘,并分析挖掘结果 实验步骤及结果 一.根据给定的事务数据库,支持数阈值2和置信度阈值0.7,编写代码生成频繁项目集及对应的关联...
  • 浅谈数据挖掘中的关联规则挖掘  数据挖掘是指以某种方式分析数据源,从中发现一些潜在的有用的信息,所以数据挖掘又称作知识发现,而关联规则挖掘则是数据挖掘中
  • Apriori 算法是一种发掘事物内在关联关系的算法,它可以加快关联分析的速度,从而让我们更有效的进行关联分析
  • Apriori算法存在候选集、频繁集产生效率低,丢失有趣强关联规则等问题,提出一种基于分辨矩阵可以采掘含负属性项强关联规则的改进算法,最后给出一个实际例子实现该算法
  • 在各种数据挖掘算法中,关联规则挖掘算是比较重要的一种,尤其是受购物篮分析的影响,关联规则被应用到很多实际业务中,本文对关联规则挖掘做一个小的总结。 首先,和聚类算法一样,关联规则挖掘属于无监督学习方法...
  • 关联规则挖掘概述

    万次阅读 多人点赞 2018-11-08 17:14:16
    在网上购物时,系统会主动推荐一些商品,赠送一些优惠券,并且...从大规模数据中挖掘对象之间的隐含关系被称为关联分析(associate analysis)或者关联规则学习(associate rules learning),其可以揭示数据中隐藏...
  • 公众号后台回复“图书“,了解更多号主新书内容 作者:林骥 来源: 林骥 曾经有一段时间,「数据挖掘」这个概念很火,其中「啤酒与尿布」的故事广为流传。据说,沃尔玛为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,448
精华内容 38,179
关键字:

关联规则挖掘例子