1.关联规则
世间万物普遍存在着联系，有些联系是我们知道的，比如说有些疾病有遗传问题、肺癌跟吸烟习惯有关联等。更多的联系是我们现在还未知的，需要我们去探索的。机器学习的关联规则算法，可以发现大量数据中项集之间有趣的未知联系。
通过关联规则可以发现未知的、想象不到的联系。例如，药品于疗效之间的联系。某医药公司研究了一种治疗心脏病的药物，通过临床数据检验发现对于心脏病疗效不明显，但通过关联规则挖掘后发现对性功能疗效明显，服用此药的病例中有大量数据表明性功能改善，因此此药物最后用于治疗性功能障碍。本节将先后介绍关联的概念、关联规则的两个常用算法Apriori算法和FP-树频集算法，以及关联规则的评价指标Lift的有关内容。

2.关联规则概念：
关联规则是指大量数据中项集之间的有趣关联或相关关系。关联规则是以事务为单位的，而事物(Event)是由项(Item)组成(Item Set,即项的集合)，它最终寻求的是项与项之间的关系。我们用i(i)表示项；T表示事物，T是一些项的集合；D表示所有事物的集合也就是数据库。I={i(1),i(2),…,i(m)}是所有项的集合，T包含在I中，每个事物可以用唯一的标识TID来标识。设X为某些项的集合，如果X包含在T中，则称事物T包含X。一个关联规则是形如X–>Y的蕴含式，这里X属于I,Y属于I,并且X∩Y为空。规则X–>Y在事务数据库D中的支持度(Support)是事物集中包含X和Y的事物数与所有事务数之比，记为Support(X–>Y),即Support(X–>Y)=P(X∪Y)。规则X–>Y在事务集中的置信度(Confidence)是指包含X和Y的事务数与所有事务数之比，记为Confidence(X–>Y),即Confidence(X–>Y)=P(X|Y)。给定一个事务集D,挖掘关联规则问题就是寻找寻找支持度和置信度分别大于用户给定的最小支持度(minsupp)和最小置信度(minconf)的关联规则。
关联规则挖掘问题可分解为以下两个子问题：
找出事务数据库D中所有大于等于用户指定最小支持度的项目(itemset)。具有最小支持度的项集称为最大项集。项集的支持度指包含该项目集的数目。
利用最大项集生成所需的关联规则对每一最大项集A,找到A的所有非空子集a,如果比率：Support(A)/Support(a)>=minconf,就生成关联规则a=>(A-a)。Support(A)/Support(a),即规则a=>(A-a)的置信度。

Apriori算法：
Apriori算法是关联规则的一个传统且比较有效的方法。基于经典的Apriori算法，后来又产生了很多不同的改进版本，但它们的基本原理都是类似的，这里，我们将经典的Apriori算法进行展示和回顾，因为很多商业项目中仍然使用它，并且它的基本思想在机器学习应用的很多地方还具有借鉴作用。

Apriori算法思想：
Apriori算法基于先验原理，它反应了子集与超集之间的关系：即频繁项集的所有非空子集都必须是频繁的，非频繁项集的所有所有超集必是非频繁的。如果项集I不满足最小支持度阈值s,则I不是频繁的，即P(I)<s.如果项A添加是到I,则结果集（I∪A）不可能比I更频繁的出现。因此，（I,A）也不是频繁的，即P(IUA)<s。因此，Apriori算法的性质主要是用于搜索频繁项集的时候对候选式的筛选过程。Apriori算法中利用Apriori性质，能够比较好地避免盲目的搜索，提高频繁项集的查找效率。
Apriori算法实现：
Apriori算法是使用逐层迭代找出频繁项集的。算法需要对数据集进行多步处理。
Apriori算法的基本过程如下：
输入：事务数据库D;最小支持度阈值。
1）简单统计所有含一个元素项集出现的概率，并找出那些不小于最小支持度的项集，即一维最大项集。
2）开始循环处理，直到再没有最大项集生成。
3）循环过程是：第k步中，根据第k-1步生成(k-1)维最大项集产生k维候选项集，然后对数据库进行搜索，得到候选项集的项集支持度，与最小支持度比较，从而找到k维最大项集。
输出：D中的频繁项集L。

算法的缺点如下：
在每一步产生候选项集时循环产生的组合过多，没有排除不应该参与组合的元素。
每次计算项集的支持度时，都对数据D中的全部记录进行一遍扫描比较。如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销，而这种代价随着数据库的记录的增加呈现出几何级的增加。因此人们开始寻求一种能减少这种系统I/O开销的更为快捷的算法。

FP树频集：
FP树频集算法思想完全不同于Apriori算法，它是一种从FP树紧凑数据结构中抽取频繁项集的方法。

FP树频集算法思想：
在经历过一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-Tree）,同时依然保留其中的关键信息，随后再将FP树分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得一个FP树可以放入主存中。

FP树频集算法实现：
基于FP树的最大频繁模式挖掘算法，主要包括构造频繁模式树FP树和利用FP树挖掘最大频繁模式两大步骤。逻辑算法如下：
频繁模式树FP树的构造：
输入：事务数据库D;最小支持度Support
输出：事务数据库D的频繁模式树，FP树

利用FP树挖掘最大频繁模式：
输入：D的频繁模式树FP树；频繁项最小支持数Support
输出：D中的最大频繁模式集

4. 提升(Lift)
   无论是Apriori算法，还是FP树频集算法，在某些情况下，即使支持度和置信度两个指标都比较高，但产生的规则依然可能是没有用的。提升指标(Lift)给出了评估规则质量的一个新指标。Lift指示给定的前件和后件随机同时出现的规则强度，它提供了一个改进的信息，以提高给定前件下后件出现的概率。Lift的定义如下：
   （Rule Support）/(Support(Antecedent)✖Support(Consequent))
   其中：
   Rule Support:是关联规则的支持度。
   Support (Antecedent):是关联规则前件的支持度。
   Support(Consequent):是关联规则后件的支持度。
   任何Lift<1的规则都不能显示是一个真正的内在并发现象，无论它的支持度和置信度有多高，因为它不能比随机现象更能预测更能预测前件和后件的并发出现。