《机器学习实战》笔记（十一）：Ch11 - 使用Apripri算

第11章 使用Apriori算法进行关联分析(代码)

• 关联分析

  • 关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:

    • 频繁项集（frequent item sets）: 经常出现在一块的物品的集合。

    • 关联规则（associational rules）: 暗示两种物品之间可能存在很强的关系。

频繁项集指的就是那些经常一起出现的物品集合，比如{啤酒，尿布，饼干}就是频繁项集中的一个例子，而根据上表也可以找到尿布->啤酒这样的关联规则。而我们是要通过关联分析大规模数据从而发现数据之间存在的有趣关系，那么问题来了，什么样的关系是有趣的呢？而这个有趣又是怎么定义的呢？我们可以通过支持度（support）和可信度（置信度confidence）来定义。一个项集的支持度指的是数据集中包含该项集记录所占的比例，上例中{豆奶}的支持度是2/5,{啤酒，尿布}的支持度是3/5；可信度是针对于像{尿布}->{啤酒}这样的关联规则来定义的，定义为：支持度({尿布，葡萄酒})/支持度（尿布）.

• Apriori 原理

  • Apriori算法优缺点

    • 优点：易编码实现

    • 缺点：在大数据集上可能较慢

    • 适用数据类型：数值型 或者 标称型数据。

  • Apriori 算法流程步骤

    • 收集数据：使用任意方法

    • 准备数据：任何数据类型都可以，因为我们只保存集合

    • 分析数据：使用任意方法

    • 训练数据：使用Apiori算法来找到频繁项集

    • 测试算法：不需要测试过程

    • 使用算法：用于发现频繁项集以及物品之间的关联规则

• 使用Apriori算法来发现频繁集

  • Apriori 算法的两个输入参数分别是最小支持度和数据集

  • 该算法首先会生成所有单个物品的项集列表

  • 接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度要求的集合会被去掉

  • 燃尽后对生下来的集合进行组合以声场包含两个元素的项集

  • 接下来再重新扫描交易记录，去掉不满足最小支持度的项集

  • 该过程重复进行直到所有项集被去掉

  • 生成候选项集

    • 数据集扫描伪代码

      • 对数据集中的每条交易记录 tran

      • 对每个候选项集 can

      • 检查一下 can 是否是 tran 的子集: 如果是则增加 can 的计数值

      • 对每个候选项集

      • 如果其支持度不低于最小值，则保留该项集

      • 返回所有频繁项集列表

• 从频繁项集中挖掘关联规则

  频繁项集可以使用Apriori算法寻找，当然下来就是要找出关联规则了。我们知道，假设有一个频繁项集，它们之间就有可能有一条关联规则，即可以表示为："...—>..."，但反过来并不一定成立（其中箭头左边对应的集合为前件，箭头右边对应的集合为后件）。在上一节，我们使用最小支持度来量化频繁项集，对应的，采用可信度来量化关联规则。其中一条规则p—>H的可信度定义为：support(P|H)/support(P)，为找到其中的关联规则，我们可以先生成一个可能的规则列表，然后测试每条规则的可信度，结合可信度的最小要求，得到关联规则。同寻找频繁项集类似，我们可以为每个频繁项集产生许多关联规则，这样就会有很多的关联规则产生。结合Apriori原理，如果某条规则不满足最小可信度要求，那么该规则的所有子集也就不满足最小可信度要求，据此我们可以减少需要测试的规则数目，简化问题。

  • 寻找关联规则的思想

    • 从一个频繁项集开始，创建一个规则列表，首先将规则的右边限定为一个元素，对这些规则进行测试
    • 合并剩下的规则来创建一个新的规则列表，规则的右边限定为两个元素

• 小节

  • 关联分析适用于发现发数据之间有趣关系的一个工作集，可以采用两种方式，一种是使用频繁项集，另外一种是使用关联规则

  • 使用Apriori原理可以有效的减少数据库上进行检查的集合的数目

代码托管见Github