2.6 关联分析模型

关联分析又称关联挖掘，就是在交易数据、关系数据或其他信息载体中查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。关联分析是一种简单、实用的分析技术，就是发现存在于大量数据集中的关联性或相关性，从而描述一个事物中某些属性同时出现的规律和模式。

关联分析的一个典型例子是购物篮分析，通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益，如图2-6所示。该过程通过发现顾客放入其购物篮中的不同商品之间的联系，分析顾客的购买习惯，帮助零售商制定营销策略等。

图2-6 啤酒与尿布

•事务：每一条交易称为一个事务。

•项：交易的每一个物品称为一个项。

•项集：包含零个或多个项的集合。

•k−项集：包含k个项的项集。

•支持度计数：一个项集出现在几个事务当中，它的支持度计数就是几。

•支持度：支持度计数除于总的事务数。

•频繁项集：支持度大于或等于某个阈值的项集。

•前件和后件：对于规则A→B, A叫作前件，B叫作后件。

•置信度：对于规则A→B，{A, B}的支持度计数除以A的为这个规则的置信度。

•强关联规则：大于或等于最小支持度阈值和最小置信度阈值的规则。

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最著名的关联规则挖掘算法之一。Apriori算法是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先，找出频繁1-项集的集合，记作L1，L1用于找出频繁2-项集的集合L2，再用于找出L3，如此下去，直到不能找到频繁k-项集。找出每个Lk都需要扫描一次数据库。

由于Apriori方法的效率仍然不能令人满意。2000年，Han Jiawei等人提出了基于频繁模式树（FP-tree）的发现频繁模式的算法FP-growth。它通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需要产生候选模式。