目录
1.1 关联规则的含义
1.2 支持度和置信度的定义
1.3 支持度和置信度的意义
1.4 支持度和置信度的缺点

1.1 关联规则的含义
关联规则是形如X→Y的蕴涵式，其中， X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。其中，关联规则XY，存在支持度和置信度。
1.2 支持度和置信度的定义

支持度support：用来确定给定数据集的频繁程度，即给定数据集在所有数据集中出现的频率。如support（X,Y）=P（X，Y）/N
置信度confidence：用来确定Y在包含X的事务中出现的频繁程度。如confidence（X->Y）=P（X,Y）/P（X）

1.3 支持度和置信度的意义
支持度：如果很低的话，代表这个规则其实是偶然出现，基本上没有意义。因此，支持度通常用来删除那些无意义的规则。

置信度：只有置信度越高，Y出现在包含X的事务中的概率菜越大。
1.4 支持度和置信度的缺点
还是以上面的1000个交易记录为例子，500个交易包含购买商品A，700个交易包含购买商品B，300个交易同时包含购买A、B商品。Support(AB)=0.3，且Confidence(A==>B)= 0.6。不管支持度和置信度看上去都很高。但是这样的关联规则是有问题的。

Confidence(A==>B)= 0.6表示用户在购买了商品A后有0.6的概率的去购买商品B，而在没有任何前提条件时，用户反而有(700/1000=0.7)的概率去购买商品B，也就是说在购买了商品A的条件反而会降低用户去购买商品B的概率。这样看来使用(A==>B)这条规则来进行推荐，还不如不推荐，随机对顾客推荐好了。为此，引入另外一个量，即提升度(Lift)，以度量此规则是否可用。



也就是说这lift指标表示了一条关联规则是否有效，这里表示度量（A==>B）这条规则有效程度的值为1.32。满足最小支持度和最小置信度的规则，叫做“强关联规则”。然而，强关联规则里，也分有效的强关联规则和无效的强关联规则。

如果Lift(X→Y)>1，则规则“X→Y”是有效的强关联规则。

如果Lift(X→Y) <=1，则规则“X→Y”是无效的强关联规则。

特别地，如果Lift(X→Y) =1，则表示X与Y相互独立

基于Apriori算法的关联规则分析模型
5.3.1基于Apriori算法的关联规则分析
桥梁是一个复杂的结构系统，桥梁的监测参数受各方面的影响，与此同时，监测到的桥梁各参数也会发生变化，各参数代表的含义也不太一样，比如挠度是竖直方向位移的表示，倾斜角是竖直和水平方向位移的联合表示，索力是拉索拉力的表示。各属性之间既相互独立有相互关联。同时各参数都是在一定的条件下测量得到，如温度和湿度条件在测量时相对固定。
 建立桥梁状态评估的Apriori模型，通过对监测的历史数据分析，形成桥梁数据各属性之间强的关联规则，同时对各属性之间潜在的关联规则挖掘，为桥梁状态的评估提供更多的有数据支撑的依据，适应在线评估系统的实时性和快速性要求。对采集频率较快的系统或属性提供更有效的方法，利用构造FP-tree方法，减少对数据库的访问，更快的实现规则的挖掘。
5.3.2 算法实现及分析
1)数据分箱 
由于桥梁各属性通过传感器采集数据，数据类型一般为数值型数据，Apriori算法处理的数据一般为序列值或者符号型数据，需要对数据进行分箱化处理。通过对各属性做分箱化处理，减少由于各属性取值范围对模型的影响，根据数据值采取等间隔分箱，根据数据量的大小以及考虑算法的性能本文采用分箱数目为 4。通过分箱后，各种属性的值由连续值变为符号化的值，值的取值为 1、2、3、4。这样就构建了适合于模型处理的结构化数据。
 对原始的数据做标准化后，并且按照等距离进行分箱后，得到形如 1、2、3、4 离散的变量，各属性分箱对应表如图 5.7-图 5.10 所示，根据分箱的对应性，可以得到对应的各属性的值域。
2)  支持度和置信度的计算 
一旦由数据库D中的事务找出频繁项集，由它们产生强关联规则是直截了当的(强关联规则满足最小支持度和最小置信度)。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。
由于规则由频繁项集产生，每个规则都自动满足最小支持度。频繁项集连同它们的支持度预先存放在散列表中，使得它们可以快速被访问。
最小支持度和最小置信度阈值的大小对生成规则有很大的影响，支持度为序列在总体数据库里所占的比率，置信度为在某个状态下另外属性相应状态的条件概率。当阈值设置得太大时，不容易得到规则，当阈值设置得太小时，生成的规则太多，难以提取有效的规则，同时由于Apriori每次增加项集时，需遍历数据库，影响算法的实现效率。为了减小模型的复杂度，设置最大的前项数目为5。
对桥梁监测数据进行关联挖掘根据统计学的特性，提取正常状态下桥梁的数据，根据各类属性之间的相互关联序列形成相关的规则，当各类属性序列出现的频率较高时，这判定此序列为正常状态下的一个模式，当实时或者最近的数据序列中，当序列的前几个属性对应规则中的数据值时，而序列的后几个属性偏离规则中的值时，则可能是桥梁的结构发生了变异，需及时的跟踪和查找桥梁的状态，将桥梁的危害发现在萌芽状态。
3)项集和关联规则 
为了得到在桥梁正常营运过程中的常规数据模式，通过设置最小支持度和最小置信度来得到强关联规则，根据Apriori算法的性质，算法分为连接步和剪枝步，连接步通过查找各个属性子序列在数据库中的支持度，同时以子序列为前件，计算以另外属性为后件的置信度， 
4)结果验证和意义的分析 
Apriori提取的规则是在数据记录中，满足支持度和置信度大于设置的阈值时得到的频繁模式和强规则，并不一定符合所有正常状况记录的数据。因此对于这些规则的验证方法是判断验证数据集是否也具有相似的规则支持度和置信度，对于这些规则的应用同样也是用于判断给定的一段时间数据记录的强规则是否具有相似的支持度和置信度，相似时表明桥梁结构状况正常，否则可能有异常变化。可能是桥梁的结构发生了变异，这时需及时跟踪数据值的变化动向，以及查找与属性对应的桥梁的状态。
采用2011年6月所采集的120条数据对强关联规则进行验证：
通过验证可以看出，对应于样本集产生的强关联规则，根据强关联规则中的属性，验证集中属性落入强关联规则值域的记录数占验证集的比例基本与样本集一致，再以与样本集规则中同样属性作为前件的情况下，得到同样后件值域的置信度准确率平均为 98.87%。通过对样本集和验证集对比可看出，从样本数据得到的规则的具有较强的有效性。能有效地预测和归纳当前或以后的监测数据。
当桥梁的结构发生变异，影响桥梁的安全性时，此时结构的变异是不可逆过程，则桥梁的监测参数值将发生整体的偏移，对应于强关联规则中的属性，属性值也将发生整体的变化，当监测的数据或以后的数据集中，对于强关联规则中的属性，当支持度与置信度与正常数据样本集产生的规则的支持度和置信度发生较大的偏离时，则桥梁可能出现了异常。
此外，Apriori算法生成的规则可能会出现下述问题，因此对于规则的应用需要结合具体的桥梁专业知识进行具体分析。
①强关联规则不一定有意义，这时，通过挖掘出来的规则就可能起到误导的作用。这时，需提高对置信度阈值的设置，在一定的程度上减少这种规则的产生。同时，根据数据的统计特性，人工甄别这些规则。
②有意义的规则不一定是强关联规则。某些有意义的序列并不一定在总的事务中占大的比例，但是这些小比例事务可能蕴含了有价值的信息。判断规则的意义需从客观的因素和主观的因素去考虑，得到的规则需结合业务模型总体考虑，从客观的数据的角度得到的规则并不是全有意义，有意义的信息也不全包含在规则中，一些项目集的事务数在总事务数中占有的比例很少，但有可能隐含了一些有意义的规则。
基于数据的统计特性得到的关联规则提高分析效率，同时找到隐含的规律，对于支持度较小的可能有意义的规则，则通过本文中的Kohonen聚类算法或其它的方法，协助来寻找此类型规则，如根据聚类形成的簇，与其它的簇距离较大且簇中记录较少，对这些集中的记录进行重点的分析。
《非本人原创，经本人整理，以技术会友，广交天下朋友》

                    
关联规则用来发现数据间潜在的关联，最典型的应用是电商网站的购物车分析。本文将通过一个简单的例子来说明关联规则中各个术语的含义以及具体的计算方法。

这是一些用户的购物数据，uid是用户的ID，后面是每个用户具体购买的商品名称，我们使用字母进行标识。下面我们将使用关联规则对这些数据进行分析，挖掘不同商品间的联系。

首先将前面的一维的购物车流水数据转换为二维的列表。然后在这个基础上计算不同商品及商品组成出现的频率。

在关联规则中，有三个重要的术语，分别为支持度(Support)，可信度(Confidence)和作用度(Lift)。第一个属于是支持度，支持度是一件商品在所有购物车中出现的频率。如果我们希望分析的是两件商品的关联，那么支持度就是这两件商品同时出现的频率。支持度的作用是用来衡量关联规则重要性的指标，简单来说就是我们所要挖掘的关系有多大的普遍性，普遍性越大这条关联规则越重要。第二个术语是可信度，可信度是指两件商品中当第一件出现时，第二件商品同时出现的频率。可信度用来衡量关联规则的准确性。第三个术语是作用度，作用度用来衡量关联规则对于商品出现频率的影响。只有作用度大于1的关联规则才有实际的应用意义。下面我们分别介绍这三个术语的计算方法。
支持度(Support)
支持度是两件商品在所有购物车中同时出现的概率，可以记录为P(A U B)。支持度的计算公式为A,B两件物品同时出现的次数与购物车总数的比率。对于前面例子中，如果我们要计算商品A和B在5条购物车记录中的支持度，具体的计算公式为1/5。商品A和B在5条购物车记录中只在uid1中同时出现过。

单件商品的支持度的计算方法与两件商品一样，如果我们要计算商品A的支持度，具体的计算公式为3/5。商品A在5条购物车记录中共出现了3次。单件商品的支持度描述了在没有其他商品影响的情况下，商品在购物车中出现的次数。


可信度(Confidence)
可信度是一个条件概率，两件商品其中一件出现在购物车中时，另一件也会出现的概率。可以记录为P(B|A)。对于前面的例子中，如果要计算A和B两件物品的可信度，具体的计算公式为1/3。商品A出现的3次，商品B同时出现的次数为1次。

作用度(Lift)
作用度通过衡量使用规则后的提升效果来判断规则是否可用，简单来说就是使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效，小于1则无效。对于前面的例子中，如果要计算规则A-B是否有效，计算公式为(1/5)/(3/5*3/5)=(0.2)/(0.6*0.6)=0.2/0.36=0.55。作用度小于1说明A-B规则对于商品B的提升没有效果。


按照前面的计算公式我们分别对下面的四个规则进行了计算，在获得支持度，可信度后计算出了四个规则的作用度。其中A-D规则作用度大于1，说明对购物车中已经包含商品A的用户推荐商品D，购买概率是单独推荐D的1.11倍。


本文作者：佚名
来源：51CTO

        
        
                
    

通过本文我们将了解：

x->y的含义
挖掘关联分析规则的两个步骤

aproori原理
算法优化–剪枝
如何生成频繁项集

没有重复的k-项候选集如何产生—>剪枝–>计数–频繁k-项集




关联分析规则的评估指标

什么是关联分析
关联分析是一种简单、实用的分析技术，就是发现存在于大量数据集中的关联性或相关性，从而描述了一个事物中某些属性同时出现的规律和模式。
关联分析是从大量数据中发现项集之间有趣的关联和相关联系。关联分析的一个典型例子是购物篮分析。该过程通过发现顾客放人其购物篮中的不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。其他的应用还包括价目表设计、商品促销、商品的排放和基于购买模式的顾客划分。
可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。


如“67%的顾客在购买啤酒的同时也会购买尿布”，因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益。


又如“‘C语言’课程优秀的同学，在学习‘数据结构’时为优秀的可能性达88%”，那么就可以通过强化“C语言”的学习来提高教学效果。


基本概念：


　我们来看上面的事务库，如同上表所示的二维数据集就是一个购物篮事务库。该事物库记录的是顾客购买商品的行为。这里的TID表示一次购买行为的编号，items表示顾客购买了哪些商品。

　

• 事务（Transaction）

事务库中的每一条记录被称为一笔事务。在上表的购物篮事务中，每一行代表一个事务，每一个商品是一个项，表示一次购物行为。
• 项集（Item Sets）

包含0个或者多个项的集合称为项集。在购物篮事务中，每一样商品就是一个项，一次购买行为包含了多个项，把其中的项组合起来就构成了项集。包含k个项的集合称为k-项集。
•	关联规则（Association Rules）

由集合 X，可以在某置信度下推出集合 Y。关联规则是形如X->Y的蕴含表达式，X称为前件，Y称为后件，X和Y不包含相同的项。即如果 X 发生了，那么 Y 也很有可能会发生。

例如购买了{‘尿布’}的人很可能会购买{‘啤酒’}。 关联规则暗示两个物品之间可能存在很强的关系。
• 支持计数（Support count）

项集在事务中出现的次数。例如，｛Bread，Milk｝这个项集在事务库中一共出现了3次，那么它的支持度计数就是3

{Milk,Bread,Diaper｝这个项集在事务库中一共出现了2次，那么它的支持度计数就是2.

记作：$支持度计数：\sigma(\{Milk,Bread,Diaper\})=2$
• 支持度（Support）

指某频繁项集在整个数据集中的比例。假设数据集有 10 条记录，包含{‘啤酒’, ‘尿布’}的有 5 条记录，那么{‘啤酒’, ‘尿布’}的支持度就是 5/10 = 0.5。

又如在上表中共有5个事务，s({Milk,Bread,Diaper})=2/5
对于关联规则的支持度定义为：也就是同时包含X和Y这两个项集的事务占所有事务的比例。即（N是事务个数）：

$s(X\rightarrow Y)=\frac{\sigma (X \cup Y)}{N}$
•	频繁项集（Frequent Item Sets）

如果我们对项目集的支持度设定一个最小阈值（minsup），那么所有支持度大于这个阈值的项集就是频繁项集。
• 置信度（Confidence）

出现某些物品时，另外一些物品必定出现的概率，针对规则而言。

有关联规则如{‘尿布’} -> {‘啤酒’}，那么它的 置信度 = 支持度｛尿布，啤酒｝／支持度｛尿布｝**
对于关联规则的置信度定义为：这个定义确定的是Y在包含X的事务中出现的频繁程度。

$c(X\rightarrow Y)=\frac{\sigma (X \cup Y)}{\sigma (X)}$

看｛Bread，Milk｝→{Diaper}这个例子，包含｛Bread，Milk｝项的事务出现了2次，包含｛Bread，Milk，Diaper}的事务也出现了2次，那么这个规则的置信度就是1。
关联规则算法策略
大多数关联规则挖掘算法通常采用的策略是分解为两步


频繁项集的产生，其目标是发现满足具有最小支持度阈值的所有项集，称为频繁项集（frequent itemset）。


规则的产生，其目标是从上一步得到的频繁项集中提取高置信度的规则，称为强规则（strong rule）。通常频繁项集的产生所需的计算远大于规则产生的计算花销。


关联规则发现：
有了上述两个度量，就可以对所有规则做限定，找出对我们有意义的规则。
首先对支持度和置信度分别设置最小阈值minsup和minconf。然后在所有规则中找出支持度≥minsup和置信度≥minconf的所有关联规则。

给定一组事务集合T，关联规则挖掘的目标是查找符合以下条件的所有规则：


支持度 ≥ 支持度最小阈值 （support ≥ minsup）


置信度 ≥ 置信度最小阈值（confidence ≥ minconf ）


需要注意的是由简单关联规则得出的推论并不包含因果关系。我们只能由A→B得到A与B有明显同时发生的情况，但不能得出A是因，B是果。
暴力方法：

列出所有可能的关联规则
计算每个规则的支持和置信度
修剪规则，使最小值和最小阈值失败

但是这样做法的计算量令人望而却步！有几种方法可以降低产生频繁项集的计算复杂度。

减少候选项集的数目。如先验(apriori)原理，是一种不用计算支持度而删除某些候选项集的方法。
减少比较次数。利用更高级得到数据结构或者存储候选项集或者压缩数据集来减少比较次数。

我们来做一次分析：



观察：

上述所有规则都是同一项集的拆分：{Milk, Diaper, Beer} （{牛奶，尿布，啤酒}）

源自同一项集的规则具有相同的支持度（support），但可以有不同的置信度（confidence）

因此，我们可以分离支持度和置信度要求。
再次重申，大多数的关联规则挖掘算法通常采用分解成两步的以下的两个主要子任务的策略：

频繁项集的产生：其目标是发现满足最小支持度阈值的所有项集，这些项集叫做频繁项集（frequent itemset）。
规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则叫做强规则（strong rule）。

通常频繁项集的产生所需的计算远大于规则产生的计算花销。
第一步，频繁项集产生（Frequent Itemset Generation）
格结构常常被用来枚举所有可能的项集，下图显示了$I=\{a,b,c,d\}$的格结构。一般来说，一个包含k个项的数据集可能产生$2^k-1$个频繁项集（不包括空集在内）。由于实际应用中k取值可能非常大，需要探查的项集搜索空间可能是指数规模的。


有几种方法可以降低产生频繁项集的复杂度：

减少候选项集的数目。如先验(apriori)原理，是一种不用计算支持度而删除某些候选项集的方法。
减少比较次数。利用更高级得到数据结构或者存储候选项集或者压缩数据集来减少比较次数。

先验原理
$先验原理:\,\,\,\,\,\,\,\,\,如果一个项集是频繁的，则它的所有子集一定也是频繁的$
先验原理其实非常好理解：如图

假设{ABC}是频繁的，那么显然{AB}也是频繁的。相反，如果如果{A，B}是非频繁的，那么它的所有超集也是非频繁的。

而一旦发现{AB}是非频繁的，那么包含{AB}的超集可以被立即剪枝（下图灰色部分），这种基于支持度度量修建指数搜索空间的策略叫做 基于支持度的剪枝。

这种剪枝策略依赖于支持度度量的一个关键性质：即一个项集的支持度绝不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性。


apriori算法的频繁项集产生
下面给出一个实例：

对于下面的事务，假设支持度阈值是60%。即最小支持度计数为3。



初始时每个项都被看做候选1-项集。对他们进行支持度计数后（下图）。{coke},{Eggs}被丢弃（因为他们出现的次数小于3)



下一次迭代我们仅使用频繁1-项集来生成频繁2-项集。由于只有4个频繁1-项集，所以算法产生的候选2-项集的数目为6（$C^2_4$)。

计算完他们的支持度阈值，有4个候选集是非频繁的。



继续生成3-项集，4个项可生成3（$C^3_4$）个3-项集。

根据先验原理，只保留子集都频繁的3-项集，最后符合的不难看出为{bread，Milk，Diaper}


我们再看暴力做法产生的候选集：（中间的3-候选集个数不难算出为$C^3_6=20$），而枚举所有项集（到3-项集将产生$C^1_6+C^2_6+C^3_6=41$。而使用先验原理减少为6+6+1=13，在这个简单的例子中减少了68%候选集数目。


关联分析规则的评估指标（Measure for Association Rules）
客观兴趣度量（interestingness Measure)
给定 X ->Y或 {X，Y}，可以从列联表(Contingency table)中获取计算兴趣度量所需的信息



$f_{11}: support \,of X and Y$

$f_{10}: support \,of X and \bar{Y}$

$f_{01}: support \,of  \bar{X} and Y$

$f_{00}: support \,of \bar{X} and \bar{Y}$
举个例子：



关联规则 Tea->Coffee

置信度 $\approx$ P（Coffee|Tea） = 15/20 = 0.75

置信度 > 50%， 这意味着喝茶的人更有可能喝咖啡， 而不是不喝
看起来规则似乎很合理

一个喝茶的人有75%的可能性会喝咖。

但 P(Coffee)= 0.9， 这意味着一个人喝茶会降低一个人喝咖啡的可能性！

请注意，P(Coffee|$\bar{Tea}$) = 75/80 = 0.9375
再来看

P（蜂蜜]茶）=50%

confident(Tea→honey)的值不高

但是P（蜂蜜）=12%，所以可以认为喝茶的人更容易点蜂蜜。



上面茶与咖啡的例子中，

P(Coffee|Tea) = 15/20 = 0.75

P(Coffee)= 0.9

Lift = 0.75/0.9 =0.8333 （＜1，因此呈负相关）
主观论据