首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习实战 - 读书笔记(11) - 使用Apriori算法进行关联分析

机器学习实战 - 读书笔记(11) - 使用Apriori算法进行关联分析

作者头像
绿巨人
发布2018-05-17 11:21:24
1.1K0
发布2018-05-17 11:21:24
举报
文章被收录于专栏:绿巨人专栏绿巨人专栏

前言

最近在看Peter Harrington写的“机器学习实战”,这是我的学习心得,这次是第11章 - 使用Apriori算法进行关联分析。

基本概念

  • 关联分析(association analysis)或者关联规则学习(association rule learning) 这是非监督学习的一个特定的目标:发现数据的关联(association)关系。简单的说,就是那些数据(或者数据特征)会一起出现。 关联分析的目标包括两项:发现频繁项集和发现关联规则。首先需要找到频繁项集,然后才能获得关联规则。 频繁项集告诉我们哪些项集会经常出现,以及出现的支持概率。 关联规则告诉我们频繁项集中出现的关联规则,哪些原因项的出现决定另外一些结果项的出现,以及规则的可信概率。
  • 关联(association) 一个关联是一个满足最小支持度的项集。
  • 关联规则(association rule) 关联规则 X \Rightarrow Y \\ Where \\ \qquad X,Y\subseteq I \text{ and } X\cap Y=\emptyset \\ \qquad \text{I: an items set}
  • 前提集(antecedent) 也称为前件、左手边。是关联规则X \Rightarrow YX部分。
  • 结果集(consequent) 也称为前后件、右手边。是关联规则X \Rightarrow YY部分。
  • 项集 (items set) 一个项集包含一个或者多个元素项。 比如:{a} {b} {c} {ab} {ac} {bc} {abc}是7个项集。
  • 子集 {a} {b} {c} {ab} {ac} {bc} 都是的{abc}一个子集。
  • 超集 与子集相反:{ab}是{a}的一个超集。
  • 支持度(support) 关联项集的频繁度。
  • 可信度(confidence) 关联规则的可信度。

核心算法

Apriori算法:生成频繁项集

Apriori 是 A priori, “一个先验”的意思。可以说是一种发现关联的优化算法。 以购买商品为例,每条数据是一个交易的商品清单。我们是否可以发现哪些商品组合更容易出现? 客户可能购买1个商品,或者最多n个商品,如果商店一共有m个商品,那么共有种 \textstyle \coprod_{i=1}^n {m + 1 -i}组合方式。 计算每种组合方式的出现概率虽然看起来简单,但是效率非常低。

  • Apriori生成频繁项集算法的原理说明 如果一个项集是非频繁集,那么它的所有超集也是非频繁的。 假设数据集中只有4元素:1234 可能的关联规则根据结果项的项数分为4个level: 发现{4}是一个低支持度项集,则在Level 2中剪除含有{4}的项集,以此类推。 Level 1: 1; 2; 3; 4 Level 2: 12; 13; 14; 23; 24; 34 Level 3: 123; 124; 134; 234 Level 4: 1234
  • 输入
    • DateSet
    • 最小支持度:Minimum Support
  • 输出
    • 项集[项数 - 1, 项集]
    • 项集的支持度[项集, 支持度]
  • 逻辑过程

因此,它先计算1个元素的概率,去掉不满足最小支持度的项集,得到项集集合C1和每个项集的支持度; 然后在项集集合C1的基础上,找2个元素的支持度(这时将不会考虑去掉的项集,所以性能会优化),再去掉不满足最小支持度的2项项集,得到项集C2和每个项集的支持度; 以此类推,直到得到项集Cm和每个项集的支持度。

Apriori算法:从频繁项集中生成关联规则

  • Apriori生成关联规则算法的原理说明 在一个频繁项集中,如果p -> h是一条低可信度规则,那么,所有其它以h的超集作为后件的规则,可信度也会较低。 关联规则是根据每个项集生成的。我们举个有4个项的项集为例: 项集:1234 可能的关联规则根据结果项的项数分为3个level: 发现[123 > 4]是一个低可信度规则,则在Level 2中剪除结果项集中含有{4}的规则,以此类推。 Level 1: 234 > 1; 134 > 2; 124 > 3; 123 > 4 Level 2: 34 > 12; 24 > 13; 23 > 14; 14 > 23; 13 > 24; 12 > 34 Level 3: 4 > 123; 3 > 124; 2 > 134; 1 > 234
  • generateRules
    • 输入
      • 频繁项集[项数 - 1, 项集]
      • 项集的支持度[项集, 支持度]
      • 最小可信度:Minimum confidence
    • 输出
      • 关联规则[因项集,果项集,可信度]
    • 逻辑过程
对每个Level的项集(Level>0):
    对当前Level的每个项集:
        获取项集的元素List.
        如果Level = 1(2个项数的项集):
            calculateConfidence(当前项集,元素List,项集的支持度,关联规则, 最小可信度)
        如果Level > 1(至少3个项数的项集):
            rulesFromConsequence(当前项集,元素List,项集的支持度,关联规则, 最小可信度)
  • calculateConfidence
    • 输入
      • 项集
      • 目标项集List
      • 项集的支持度[项集, 支持度]
      • 关联规则[因项集,果项集,可信度]
      • 最小可信度:Minimum confidence
    • 输出
      • 有效目标集
    • 逻辑过程
对每个目标项集
    计算当前目标项集在当前项集上的可信度。
    如果可信度大于最小可信度:
        把[当前项集 - 目标项集, 目标项集, 可信度]加入关联规则;
        把当前目标项集加入有效目标集。
返回有效目标集
  • rulesFromConsequence
    • 输入
      • 项集
      • 目标项集List
      • 项集的支持度[项集, 支持度]
      • 关联规则[因项集,果项集,可信度]
      • 最小可信度:Minimum confidence
    • 输出
    • 逻辑过程
得到目标项集长度m.
如果当前项集元素的长度 > m + 1:
    得到目标项集元素个数为m + 1的目标项集List。
    有效目标集 = calculateConfidence(当前项集,目标项集,项集的支持度,关联规则, 最小可信度)
    如果有效目标集的长度 > 1:
        rulesFromConsequence(当前项集,有效目标集,项集的支持度,关联规则, 最小可信度)。

核心公式

  • 支持度(support level): S(C, X) = \frac{count(C)}{len(X)} \\ where \\ \qquad S(C, X) : 项集C的支持度 \\ \qquad C : 项集 \\ \qquad X : 数据集
  • 可信度(confidence level): 一条规则P -> H的可信度定义为: C(P, H) = \frac{support(P | H)}{support(P)} \\ where \\ \qquad C(P, H) : 关联规则P -> H的可信度 \\ \qquad P : 项集 \\ \qquad H : 项集 \\ \qquad support(P) : 项集P的支持度 \\ \qquad support(P | H) : 项集P,H并集的支持度

参考

  • Machine Learning in Action by Peter Harrington
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-08-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 基本概念
  • 核心算法
    • Apriori算法:生成频繁项集
      • Apriori算法:从频繁项集中生成关联规则
        • 核心公式
        • 参考
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档