精华内容
下载资源
问答
  • 关联规则挖掘

    2017-10-07 13:31:06
    关联规则挖掘 定义频繁项目集 关联规则挖掘的任务 挖掘关联规则 生成频繁项目集

    关联规则挖掘

    已知一组交易数据,找到根据交易中其他项目的出现来预测项目发生的规则。
    例有如下市场交易情况
    关联关系可为:
    {Diaper} -> {Bear}
    {Milk, Bread} -> {Eggs,Coke}
    {Beer, Bread} -> {Milk}
    PS: 以上表示意味着同时出现,而不是因果关系


    定义:频繁项目集

    • 项目集Itemset
      • 一个或者多个项目的集合
        例如: {Milk, Bread, Diaper}
      • k-Itenset
        一个含有k个项目的项目集
    • 支持数Support count(δ)
      • 项目集出现的频度
      • 例如:δ({Milk, Bread, Diaper})=2
    • 支持度Support
      • 包含项目集的事务的分数
      • 例如 s({Milk, Bread, Diaper})=25
    • 频繁项目集
      • 一个支持度大等于最小支持度的项目集
    • 关联规则
      • 一种形式的含义表达 X->Y, 此处X和Y均为项目集
      • 例如:{Milk, Diaper}->{Beer}
    • 规则评估指标(Rule Evaluation Metrics)
    • 支持度Support(s)
      • 包含项目集的事务的分数
    • 置信度Confidence(c)
      • 衡量Y中的项目在包含X的交易中的频率
      • 例如:
        c=δ(Milk,Diaper,Beer)δ(Milk,Diaper)=23=0.67

    关联规则挖掘的任务

    1. 给定一组交易T, 关联规则挖掘的目标是找到所有规则它们符合以下定义:
      • 支持度support > 最小支持度 minsup
      • 置信度confidence > 最小置信度minconf
        1. 暴力方法:
      • 例举所有可能的关联规则
      • 计算每一个规则的支持度和置信度
      • 剪去支持度和置信度小于最小支持度及最小置信度的规则

    挖掘关联规则

    利用之前给出的图片例子,我们可以得出以下规则:
    {Milk, Diaper} -> {Beer} (s=0.4,c=0.67)
    {Milk, Beer} -> {Diaper} (s=0.4,c=1.0)
    {Diaper, Beer} -> {Milk} (s=0.4,c=0.67)
    {Beer} -> {Milk,Diaper} (s=0.4,c=0.67)
    {Diaper} -> {Beer} (s=0.4,c=0.5)
    {Milk} -> {Diaper, Beer} (s=0.4,c=0.5)

    观察:

    • 所有以上列出的规则都是相同项目集的二维划分
    • 来自相同项目集的规则具有唯一的支持度但不同的置信度
    • 因此,我们可以解分离支持度和置信度的要求

    两步方法
    1. 生成频繁项目集
    - 生成所有支持度大等于最小支持度的所有项目集
    2. 产生规则
    - 从每一个频繁项目集中生成高置信度的规则,每一个规则都是一个项目集的二维划分
    生成频繁项目集计算量巨大

    生成频繁项目集

    这里写图片描述

    • 暴力方法:
    • 栈中的每一个项目集都是候选频繁项目集
    • 通过扫描数据库技术每一个候选的支持度
    • 给定d个唯一的项目:
    • 项目集的总数=2d
    • 可能的关联规则总数
      R=k1d1[(dk)×j1dk(dk)]=3d2d+1+1

      如果d=6,那么就会生成602个规则

    生成频繁项目集策略

    1. 减少候选项的个数(M)
      • 完整的检索:M=2d
      • 使用剪枝技术去减少M
    2. 减少事务transaction的数量(N)
      • 随着项目集大小的增加,减小N的大小
      • 使用DHP(direct hashing and pruning)和vertical-based mining algorithms
    3. 减少比较的数量(NM)
      • 使用有效的数据结构去存储候选项和事务
      • 不需要匹配每个候选人与每个交易

    生成频繁项目集(减少候选项的个数)的方法

    • Apriori principle
    • PF-Tree
      关于具体生成频繁项目集的方法在其他几篇博客当中会有详细介绍。
    展开全文
  • 近年来国内外学者对关联规则进行了大量的研究,为深入理解关联规则挖掘技术,掌握其研究现状与发展趋势,首先介绍了关联规则相关定义与分类方法;其次从串行和并行两个角度总结了关联规则挖掘的一般方法,概述并分析...
  • 从购物篮分析关联规则挖掘 Apriori算法 ​ 随着大量数据不断的收集和存储,许多业界人士对于从他们的数据库中挖掘知识越来越感兴趣。对于商场而言,从大量的商务事务记录中发现有价值的的关联关系,可以为货物摆放...

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

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

    购物篮分析

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

    在这里插入图片描述

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

    频繁项集

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

    在这里插入图片描述

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

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

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

    关联规则

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

    在这里插入图片描述

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

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

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

    support(A=>B)=P(AB)=support_count(AB)support_count(all) support(A=>B) = P(AB)=\frac{support\_count(A \bigcap B)}{support\_count(all)}

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

    confidence(A=>B)=P(BA)=support_count(AB)support_count(A) confidence(A=>B) = P(B|A)=\frac{support\_count(A \bigcup B)}{support\_count(A)}

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

    关联规则挖掘步骤

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

    Apriori 算法

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

    在这里插入图片描述

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

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

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

    在这里插入图片描述

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

    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)=(10x+y)mod7 h(x,y)= (10x+y) mod 7
    ​ 如果预设最小支持度计数为 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[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-08-12 14:01:18
    关联规则分析也称为购物篮分析,最早是为了发现超市销售数据库中不同的商品之间的关联关系。 用于寻找数据集中各项之间的关联关系。根据所挖掘的关联关系,可以从一个属性的信息来推断另一个属性的信息。当置信度...

    关联规则分析也称为购物篮分析,最早是为了发现超市销售数据库中不同的商品之间的关联关系。

    用于寻找数据集中各项之间的关联关系。根据所挖掘的关联关系,可以从一个属性的信息来推断另一个属性的信息。当置信度达到某一阈值时,可以认为规则成立。

    常用的关联规则算法

    算法名称 算法描述
    Apriori

    关联规则最常用、最经典的挖掘频繁项集的算法,核心思想是通过连接产生候选项及其支持度,然后通过剪枝生成频繁项集

    无法处理连续型数值变量,往往分析之前需要对数据进行离散化。

    FP-Tree

    针对Apriori算法固有的多次扫描事务数据集的缺陷,提出的不产生候选频繁项集的方法。

    Apriori和FP-Tree都是寻找频繁项集的算法

    Eclat算法 一种深度优先算法,采用垂直数据表示形式,在概念格理论的基础上利用基于前缀的等价关系将搜索空间划分为较小的子空间
    灰色关联法 分析和确定各因素之间的影响程度,或是若干个子因素(子序列)对主因素(母序列)的贡献度而进行的一种分析方法

    本文介绍最常用的Apriori算法。

    项集:项的集合。包含k个项的项集成为k项集,如集合{牛奶、麦片、糖}是一个3项集

    频繁项集:如果项集I的相对支持度满足预定义的最小支持度阈值,则I是频繁项集

    支持度(相对支持度):项集A、B同时发生的概率。

    置信度:项集A发生,则项集B发生的概率。

    最小支持度:用户或专家定义的衡量支持度的一个阈值,表示项集在统计意义上的最低重要性。

    最小置信度:用户或专家定义的衡量置信度的一个阈值,表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则成为强规则。

    目前,设置最小支持度和最小置信度,大部分根据业务经验设置初始值,然后经过多次调整,获取与业务相符的关联规则结果。


    举例1:

    R语言实现:

    1、创建稀疏矩阵

    tr <- read.transactions("menu_orders.txt",format="basket",sep=",") #读入源数据并创建稀疏矩阵
    #format=c("basket", "single")用于注明源数据的格式。如果源数据每行内容就是一条交易购买的商品列表(类似于一行就是一个购物篮)那么使用basket;如果每行内容是交易号+单个商品,那么使用single。
    summary(tr) #查看数据集相关的统计汇总信息
    
    inspect(tr) #查看稀疏矩阵的内容

    输出如下:

    2、采用Apriori算法建模

    rule0 = apriori(tr,parameter = list(support=0.2,confidence = 0.5)) #设定支持度为0.2,置信度为0.5

    3、输出模型结果

    inspect(rule0)

    输出结果如下:

    结果分析(以结果第12条为例):

    a、b同时发生的概率是50%。

    a发生,则b发生的概率是71.42857%。

    这样就可以进行智能推荐了。


    举例2:

    trans = as(a,"transactions") #将数据转换成transactions属性
    
    inspect(trans[1:5]) #观察前五行的数据
    
    rules = apriori(trans,parameter = list(support=0.06,confidence = 0.75)) #调用Apriori算法,最小支持度为0.06,最小置信度为0.75
    
    rules #显示rules中关联规则条数
    
    inspect(rules) #观测rules中的关联规则

    输出结果如下:

    结果分析(以结果第2条为例):

    A4、F3~H4的支持度最大,为7.85%,置信度为87.96%。说明当A4、F3的条件满足时,H4的可能性为87.96%,而这种情况发生的可能性为7.85%。

     

    Python实现:

    import pandas as pd 
    from apriori import * 导入自己编写的Apriori函数
    data = pd.read_excel("menu_orders.xls",header=None)
    
    print(u'\n转换原始数据为0-1矩阵')
    ct = lambda x:pd.Series(1,index=x[pd.notnull(x)]) #转换0-1矩阵的过渡函数
    b = map(ct,data.as_matrix()) #用map方式执行
    data = pd.DataFrame(list(b)).fillna(0) #实现矩阵转换,空值用0填充
    print(u'\n转换完毕。')
    del b #删除中间变量b,节省内存
    
    support = 0.2 #最小支持度
    confidence = 0.5 #最小置信度
    ms = '---' #连接符
    find_rule(data,support,confidence,ms).to_excel('1.xls')

    输出结果如下:

    展开全文
  • 关联规则分析

    2019-06-23 16:18:29
    关联规则分析

    1. 定义

    关联规则分析是数据挖掘中最活跃的研究方法之一,目的是在一个数据集中找出各项之间的关联关系,而这种关系并没有在数据中直接表示出来。

    2. 概念

    1. 项目: 交易数据库中的一个属性字段,每个字段有一定的取值范围。对超级市场来讲,项目一般是指一次交易中的一个物品,
      例如,客户在某次交易中购买了“牛奶”、“黄油”和“面包”就代表了三个不同的项目。

    2. 交易:某个客户在一次交易中,发生的所有项目的集合。

    3. 项目集:包含若干个项目的集合。项目集可能是一个交易,也可能不是一个交易,但一个交易一定是一个项目集。
      在上个例子中,{“牛奶”,“面包”,“黄油”}、{“牛奶”}、{“牛奶”,“面包”}、{“面包”,“黄油”}等都是项目集,但只有{“牛奶”,“面包”,“黄油”}才是一个交易。

    4. 项目集的维数: 把一个项目集所包含的项目的个数称为此项目集的维数或项目集的长度。长度为k的项目集,称作k维项目集。
      例如:项目集I={“牛奶”,“面包”,“黄油”}的维数或长度为3,记作3-项目集。

    5. 支持度: 假定X是一个项目集,D是一个交易集合或交易数据库,称D中包含X的交易的个数与D 中总的交易个数之比为X在D中的支持度。
      例如:D={T1,T2,T3,T4}包含4 个交易,其中T1={A,B,C}、T2={B}、T3={A,B,C,D}、T4={B,C,D},如果X={B,C},则在D中包含X 的交易有:T1,T3,T4,此时D中总的交易个数为4,故X在D中的支持度为75%。X的支持度记作sup(X),而关联规则X⇒Y的支持度则记作sup(X∪Y)。
      在这里插入图片描述

    6. 可信度:对形如X⇒Y的关联规则,其中X和Y都是项目集,定义规则的可信度为交易集合D中既包含X也包含Y的交易个数与D中仅包含X而不包含Y的交易个数之比,或者说是项目集X∪Y的支持度与X的支持度之比,即sup(X∪Y)/ sup(X)。把规则X⇒Y的可信度记作conf(X⇒Y)。一个规则的可信度的范围在0到1之间。事实上可信度即是指在出现了项目集X的交易中,项目集Y也同时出现的概率有多大。即
      在这里插入图片描述

    7. 最小支持度:由用户定义的衡量支持度的一个阈值,表示项目集在统计意义上的最低重要性,记作minsup。

    8. 最小可信度:由用户定义的衡量可信度的一个阈值,表示规则的最低可靠性,记作minconf。

    9. 频繁项目集:对一个项目集X,如果X的支持度不小于用户定义的最小支持度阈值,即sup(X)≧minsup,称X为频繁项目集或大集(Large Itemset)。

    3. 常见的关联规则算法

    在这里插入图片描述

    4. Apriori 算法

    Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项目集的算法,最早是由 Agrawal等人提出的(1993年)。
    Apriori 算法的挖掘问题可以被归纳成两个子问题:
    (1) 找出所有频繁项集:根据定义,这些项集出现的频繁性至少等于最小支持度计数。
    (2) 由频繁项集产生强关联规则:根据定义,这些规则必须满足最小支持度和最小可信度。

    Apriori 算法使用逐层搜索迭代的方法,K-项集用于探索K+1-项集。首先,找出频繁1-项集的集合,该集合记做L1,L1用于找频繁2-项集的集合L2,而L2用于找L3,如此下去,直到找不到频繁项目集为止。找到每个Lk就需要扫描一次数据库。这里用到的核心原来就是:频繁项目集的子集是频繁项目集;非频繁项目集的超集是非频繁项目集。
    Apriori 算法的描述如下:
    输入:事务数据库D,最小支持度阈值min-sup
    输出:D中的频繁项集L
    方法:
    (1) find_frequent_1_itemsets(D)
    (2) for(k=2;Lk-1!=Φ;k++){
    (3) Ck=apriori-gen(Lk-1,minsup)//新的候选集
    (4) for each transaction t∈D{
    (5) Ct=subset(Ck,t);//事务t中包含的候选集
    (6) for each candidates c∈Ct do
    (7) c.count++;
    (8) }
    (9) Lk={c∈Ck|C.count>=minsup}
    (10) }
    (11) answer∪kLk;

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

    千次阅读 2018-08-31 20:06:08
    “尿布与啤酒”是一个典型的关联规则挖掘的例子,沃尔玛为了能够准确了解顾客在其门店的购买习惯,对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛利用所有用户...
  • 重要概念关联规则挖掘关联规则的形式支持度置信度频繁项集3.挖掘关联规则的步骤【1】频繁项集的产生【2】规则的产生4.进行关联规则挖掘的方法【1】拿到一个数据集,首先——【2】减少候选项集的数量【3】减少比较的...
  • 关联规则挖掘(一)

    千次阅读 2017-12-05 11:31:48
    关联规则挖掘是一种常用的数据挖掘手段,本文作为关联规则挖掘的第一篇文章,将主要介绍关联规则挖掘的来历与目的,以购物篮分析的一个简单例子熟悉基本概念,以及从多维度对关联规则挖掘进行分类。
  • 一个事务数据库中的关联规则挖掘可以描述如下 设I= {i1, i2, , im} 是一个项目集合 事务数据 库D= {t1, t2, , tn} 是由一系列具有惟一标识的TID事务组成 每一个事务ti (i=1, 2, , n)都对应I上的一个子集 定义3.1 设...
  • 针对模糊关联规则挖掘时隶属函数的确定困难以及区间划分边界过硬等问题,提出了模糊关系关联规则挖掘算法,确定了关系等级数目和相邻等级相似度,将语言表达式(事务的属性值)根据模糊运算规则映射到标签集的各个...
  • 关联规则 置信度定义

    2016-11-07 17:39:43
    关联规则中相关定义在附件中有定义  
  • 提出了流式数据上关联规则的形式化定义和基本挖掘算法,系统地回顾了近年来流式数据上关联规则挖掘的研究进展,详细分析了目前挖掘算法研究中存在的主要问题和解决途径,阐述了未来的研究方向。
  • 关联规则 挖掘 ,数据关联 融合

    千次阅读 2019-02-22 20:45:25
    关联规则 挖掘 ,数据关联 融合
  • 基于项目集的关联规则挖掘研究,包剑,,关联规则的发现是数据挖掘的知识模式中比较重要的一项任务,它的目的是发现项目集中所有的频繁模式。根据关联规则定义及属性,可
  • 关联规则挖掘是大数据分析与挖掘的基础,通过在大量数据中挖掘数据项之间的强关联关系,可以得到很多有趣而且有价值的信息。 01、基本概念 1、关联规则的挖掘是在大量数据的基础上,通过分析哪些数据项频繁地一起...
  • [数据挖掘]关联规则挖掘

    千次阅读 2013-05-03 21:26:13
    关联规则(association rule)是数据中所蕴含的一类重要...关联规则挖掘的经典应用是购物篮(Market Basket), 关联规则挖掘并没有考虑客户购买商品时的顺序。  在介绍关联规则挖掘算法前,我们先了解一些相关的概
  • 1 关联规则挖掘概念 2 关联规则基本模型 2.1 基本概念 2.2 关联规则的挖掘步骤 3 Apriori算法 3.1 介绍 3.2 实现步骤 3.3 伪代码 1 关联规则挖掘概念 一、定义 关联规则反映一个事物与其它事物之间的依赖...
  • 基于遥感图像的光谱...采用关联规则挖掘算法对图像纹理的频繁模式进行挖掘,通过联合关联规则来表达纹理。试验表明,挖掘出的关 联规则不仅能够表达规则纹理,而且能够较好表达随机纹理,据此可以进行纹理图像分割。
  • 如果设定支持度阀值为70%,置信度阀值为80%,利用之前关联规则挖掘算法,可以得到的关联规则{年龄在21-40}——>{购买笔记本},{文化程度为研究生}——>{购买笔记本} 注意事项: (1):标称属性值过多。比如...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 134,699
精华内容 53,879
关键字:

关联规则挖掘的定义