关联规则简介
数据挖掘是⼀项从⼤量的记录数据中提取有价值的、⼈们感兴趣的知识，这些知识是隐含的、事先未知的有⽤信息，提取的知识⼀般可表⽰为概念(Concepts)、规则(Rules)、规律(Regular ides)、模式(Patterns)等形式。
关联规则是当前数据挖掘研究的主要⽅法之⼀，它反映⼀个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在⼀定的关联关系，那么，其中⼀个事物就能够通过其他事物预测到。
典型的关联规则发现问题是对超市中的货篮数据（Market Basket）进行分析。通过发现顾客放⼊货篮中的不同商品之间的关系来分析顾客的购买习惯。
关联规则的基本概念
设I={i1, i2,…, im}为所有项的集合，D为事务数据库，事务T是⼀个项目子集（T⊆I）。设A是⼀个由项目构成的集合，称为项集。事务T包含项集A，当且仅当A⊆T。如果项集A中包含k个项目，则称其为k项集。
项集A在事务数据库D中出现的次数占D中总事务的百分⽐叫做项集的支持度。如果项集的⽀持度超过用户给定的最小支持度阈值，就称该项集是频繁项集。
关联规则是形如X⇒Y的逻辑蕴含式，其中X⊂I，Y⊂I，且X∩Y=∅。
如果事务数据库D中有s%的事务包含X∪Y，则称关联规则X⇒Y的支持度为s%。
关联规则的信任度为support (X∪Y)／support (X)。
通俗的讲，就是项集A在所有数据库中所占的百分比即为A的支持度。
项集A和项集B同时发生的概率比上项集A发生的概率称之为项集A的信任度。
我们在实际运用当中，往往会给予支持度和信任度一定的阈值，是否满足这一阈值我们称之为强关联规则，强关联规则就是⽀持度和信任度分别满足用户给定阈值的规则。
接下来，我们要介绍一种用于挖掘出数据关联规则的常用算法--Apriori算法。它用来找出数据值中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集，或者电商的网购数据集，如果我们找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。
Apriori算法
Apriori算法将发现关联规则的过程分为两个步骤：
通过迭代，检索出事务数据库中的所有频繁项集，即⽀持度不低于⽤户设定的阈值的项集。
利⽤频繁项集构造出满足用户最小信任度的规则。
挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的⼤部分。
Apriori的两条重要性质：
性质1：频繁项集的所有非空子集必为频繁项集。
性质2：非频繁项集的超集⼀定是⾮频繁的。
Apriori的具体步骤：
连接步：为找Lk ，通过将Lk-1与⾃⾝连接产⽣候选k项集的集合Ck
剪枝步：Ck是Lk 的超集，也就是说，Ck的成员可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。任何非频繁的（k-1）项集都不是频繁k项集的⼦集。
依靠之前的两条性质，我们可以在实际应用当中省去很多资源，比如在电商里面有百万级别的商品上新，两两组合后的维度是很惊人的，所以我们可以用到上面的方法，重复Apriori的步骤，在集合Ck中先行过滤掉支持度低的项集(性质2：非频繁项集的超集⼀定是⾮频繁的)，在多次重复后，可以大大降低统计的量。
Apriori算法的不足
 Ck中的每个元素需在交易数据库中进⾏验证来决定其是否加入Lk，频繁的扫描调用是对数据库和服务器造成很大的压力
 验证过程是性能瓶颈
 交易数据库可能⾮常⼤
 比如频集最多包含10个项，那么就需要扫描交易数据库10遍
 需要很⼤的I/O负载
因为Apriori算法本质是时间换空间的，换句话说就是利用多次的读取来利用有限的空间来完成计算，但是随着摩尔定律，我们的空间不在像之前那样宝贵和捉襟见肘了，所以，我们开始思考能不能有一种算法，利用空间，来换取时间，一次获得更快的速度。
如下个算法，只扫描一两次数据库，同时利用这两次扫描的来存储下的关键数据来获得相应的规则。
FP-tree算法
2000年，Han等提出了⼀个称为FP-tree的算法。FP-tree算法特点是只进⾏2次数据库扫描。
 no候选集
 直接压缩数据库成⼀个频繁模式树
通过这棵树⽣成关联规则
FP-tree两个主要步骤
 利用事务数据库中的数据构造FP-tree
从FP-tree中挖掘频繁模式
步骤1：构造 FP-tree树
具体过程：
扫描数据库⼀次，得到频繁1-项集
把项按⽀持度递减排
再⼀次扫描数据库，建⽴FP-tree
步骤2：频繁模式的挖掘
具体过程:
根据事务数据库D 和最⼩⽀持度min_sup， 调⽤建树过程建⽴FP-tree;
    if (FP-tree 为简单路径)：
        将路径上⽀持度计数⼤于等于min_sup 的节点任意组合，得到所需
        的频繁模式；
    else：
        初始化最⼤频繁模式集合为空；
按照⽀持频率升序，以每个1- 频繁项为后缀，调用挖掘算法挖掘最大频繁模式集。
根据最⼤频繁模式集合中最⼤频繁模式，输出全部的频繁模式。
FP - tree 算法的优缺点
优点
FP-tree 算法只需对事务数据库进⾏⼆次扫描。
避免产⽣的⼤量候选集。
缺点
要递归⽣成条件数据库和条件FP-tree，所以内存开销⼤。
只能用于挖掘单维的布尔关联规则。
不多就这样了，希望本文能够帮到你！~！
最后打个小广告，我的公众号，喜欢写点学习中的小心得，不介意可以关注下!~!

基本知识

关联规则挖掘定义 

给定事务的集合 T, 关联规则发现是指找出支持度大于等于 min_sup并且置信度大于等于min_conf的所有规则，min_sup和min_conf是对应的支持度和置信度阈值
关联规则挖掘目的 

在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构
频繁模式：数据库中频繁出现的项集 
项集（Itemset） 

k-项集：包含k个项的集合
频繁项集（Frequent Itemset） 

满足最小支持度阈值（min_sup）的所有项集
支持度计数（Support count） 

包含特定项集的事务个数
支持度（Support） 

包含项集的事务数与总事务数的比值
关联规则（Association Rule） 

关联规则是形如 X→ Y 的蕴含表达式，其中X 和Y 是不相交的项集 
关联规则的提取 

将一个项集X 划分成两个非空的子集X 和 Y−X，使得 X→(Y−X) 满足置信度阈值
支持度 ：确定项集的频繁程度 
support(X→Y)=P(X∪Y)
置信度：确定Y在包含X的事务中出现的频繁程度 
Confidence(X→Y)=P(Y∣X)=support(X∪Y)support(X)
频繁项集产生（Frequent Itemset Generation）

Brute-force 方法（蛮力方法） 
把格结构中每个项集作为候选项集
将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数
把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选
候选产生相当简单的，但候选剪枝的开销极大，时间复杂度高
Apriori算法 

降低产生频繁项集计算复杂度，先验原理 
如果一个项集是频繁的，则它的所有子集一定也是频繁的（连接时减少）
如果一个项集是非频繁的，则它的所有超集也一定是非频繁的（剪纸原则）
基于支持度的剪枝（support-based pruning） 

由长度为k的频繁项集产生长度为 (k+1) 的候选项集，连接，剪枝
支持度度量的反单调性（anti-monotone） 

一个项集的支持度决不会超过它的子集的支持度
极大频繁项集 
如果X 是频繁的，且不存在超项集Y 使得Y⊃X 并且Y 是频繁的，则X 是极大频繁项集
有效地提供了频繁项集的紧凑表示，即所有的频繁项集是极大频繁项集的子集，但它不包含子集的支持度信息
提高Apriori算法的方法 
散列项集计数（Hash-based itemset counting） 

压缩候选k项集
事务压缩（Transaction reduction） 

不包含任何频繁k项集的事务不可能包含任何频k+1项集。因此这些事务在其后的考虑中，可以加上标记或删除
划分（Partitioning） 

项集在DB中是频繁的，它必须至少在DB的一个划分中是频繁的（分治的思想）
采样（Sampling） 

选取原数据库的一个样本，使用Apriori 算法在样本中挖掘频繁模式（牺牲一些精度换取有效性）
FP增长算法（Frequent-Pattern Growth） 

使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集

支持度排序：扫描一次数据集，将频繁项按照支持度的递减排序
构建FP树：再次扫描数据集，读入事务，每个事务都映射到FP树的一条路径，并不断更新支持度计数
例子1 

例子2 

条件模式基 

一个“子数据库”，由FP树中与该后缀模式一起出现的前缀路径集组成
将条件模式基看作为事务数据库，构造条件FP树 


挖掘频繁项集 
如果条件FP树为单个路径，则产生该路径下所有模式的组合 

如果条件FP树为多路径，则针对树的头表中的每一个项， 产生对应模式获取频繁模式 

优缺点 

对长和短的模式都是有效且可伸缩的，效率比Apriori算法快了一个数量级；但对内存要求较大， 算法实现相对复杂
关联模式的评估（Pattern Evaluation）

关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。建立一组广泛接受的评价关联模式质量的标准是非常重要的。

通过统计论据
通过主观论据 

置信度度量忽略了规则后件中出现的项集的支持度，高置信度的规则有时存在误导 
提升度（lift） 

规则置信度和规则后件中项集的支持度之间的比率
兴趣因子（interest factor）

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


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


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

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

支持度和置信度

那么我们如何能够从所有可能规则的集合中选择感兴趣的规则呢？需要利用一些度量方法来筛选和过滤，比较有名的度量方法是最小支持度（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

來源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

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


项目: 交易数据库中的一个属性字段，每个字段有一定的取值范围。对超级市场来讲，项目一般是指一次交易中的一个物品，

例如，客户在某次交易中购买了“牛奶”、“黄油”和“面包”就代表了三个不同的项目。


交易：某个客户在一次交易中，发生的所有项目的集合。


项目集:包含若干个项目的集合。项目集可能是一个交易，也可能不是一个交易，但一个交易一定是一个项目集。

在上个例子中，{“牛奶”,“面包”,“黄油”}、{“牛奶”}、{“牛奶”,“面包”}、{“面包”,“黄油”}等都是项目集，但只有{“牛奶”,“面包”,“黄油”}才是一个交易。


项目集的维数: 把一个项目集所包含的项目的个数称为此项目集的维数或项目集的长度。长度为k的项目集，称作k维项目集。

例如：项目集I={“牛奶”,“面包”,“黄油”}的维数或长度为3,记作3-项目集。


支持度: 假定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）。




可信度：对形如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也同时出现的概率有多大。即




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


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


频繁项目集：对一个项目集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;