第九章 数据关联规则分析算法——基于Apriori算法的关联项分析
9.1 基于Apriori算法的关联分析
Aprior算法是关联规则分析中较为经典的频繁项集算法。关联规则反映的是两个或多个事物相互之间的依存性和关联性。如果两个或者多个事物相互之间存在一定的关联关系，则它们之间存在一种关联规则使得它们之间可以进行搭配。
9.1.1 基本概要
Apriori算法利用频繁项集的先验知识，不断地按照层次进行迭代，计算数据集中的所有可能的频繁项集，它的分析主要包括两个核心部分。
1、根据支持度找出频繁项集；
2、根据置信度产生关联规则。
9.1.2 Apriori算法原理
基本流程：
1、扫描历史数据，并对每项数据进行频率次数统计。
2、构建候选集 ，并计算其支持度，即数据出现频率次数与总数的比。
3、对候选项集进行筛选，筛选的数据项支持度应当不小于最小支持度，从而形成频繁项集 .
4、对频繁项集 进行连接生成候选集 ，重复上述步骤，最终形成频繁K项集或者最大频繁项集。
Apriori算法存在两大定理：
1、如果一个集合是频繁项集，那么它的所有子集都是频繁集合。
2、如果一个集合它不是频繁集合，那么它的所有超集都不是频繁项集。
9.1.3 Apriori算法优缺点
优：运算过程非常简单，理论方法也比较容易理解，对数据特征的要求也相对较低。
缺：
1、产生候选集是产生较多的组合，没有考虑将一些无关的元素排除后再进行组合。
2、每次计算项集的过程中都会扫描元素的数据表。
针对不足推出不断改进的Apriori算法：
1、将数据表（事务表）进行压缩。
2、利用哈希表的快速查找特性对项集进行计数统计。
3、合理选样。
关联规则之Apriori算法
Apriori算法的主要思想是找出存在于事物数据集中的最大频繁项集，再利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则。
项集是项的集合。包含k个项的项集成为k项集。项集的出现频率是所有包含项集的事务计数，又称为绝对支持度或支持度计数。如果项集I的相对支持度满足预定义的最小支持度阈值，则I是频繁项集。频繁k项集通常记作k。
项集A、B同时发生的概率称为关联规则的支持度（也称为相对支持度）。
项集A发生，则项集B发生的概率为关联规则的置信度。
最小支持度是用户或专家定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；最小置信度是用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。
项集A的支持度计数是事务数据集中包含项集A的事务个数，简称为项集的频率或计数。
频繁项集哦的所有非空自己也必须是频繁项集。根据该性质可以得出：向不是频繁项集I的项集中添加事务A，新的项集I U A一定也不是频繁项集。
1）找出所有的频繁项集（支持度必须大于等于给丁的最小支持度阈值），在这个过程中连接步和剪枝步互相融合，最终得到最大频繁项集Lk。
连接步的目的是找到K项集，对给定的最小支持度阈值，分别对1项候选集C1，剔除小于该阈值的项集得到1项频繁项集L1；下一步由L1自身连接产生2项候选集C2，保留C2中满足约束条件的项集得到2项频繁集，记为L2；再下一步由L2与L3连接产生3项候选集C3，保留C2中满足约束条件的项集得到3项频繁集，记为L3···这样循环下去，得到最大频繁项集Lk。
剪枝步紧接着连接步，在产生候选项Ck的过程中起到减小搜索空间的目的。由于Ck是Lk-1与L1连接产生的，根据Apriori的性质频繁项集的所有非空子集也必须是频繁项集，所以不满足该性质的项集不会存在于Ck中，该过程就是剪枝。
2）由频繁项集产生强关联规则：由过程1）可知未超过预定的最小支持度阈值的项集已被提出，如果剩下这些规则又满足了预定的最小置信度阈值，那么就挖掘出了强关联规则。
