1.1.2 算法原理

频繁模式（Frequent Pattern）是频繁地出现在数据集中的模式（如项集、子序列或者子结构）。例如，频繁地同时出现在交易数据集中的商品（如牛奶和面包）的集合是频繁项集。一个子序列，如首先购买PC，然后是数码相机，再是内存卡，如果它频繁地出现在购物车历史数据库中，则称它为一个（频繁的）序列模式。一个子结构可能涉及不同的结构形式，如子图、子树或子格，它可能与项集或者子序列结合在一起。如果一个子结构频繁地出现，则称它为（频繁的）结构模式。对于挖掘数据之间的关联、相关性和许多其他有趣的联系来说，发现这种频繁模式起着至关重要的作用。此外，它对数据分类、聚类和其他数据挖掘任务也有帮助。因此，频繁模式的挖掘就成为一项重要的数据挖掘任务和数据挖掘研究关注的主题之一。

Apriori算法使用一种称为逐层搜索的迭代方法，其中，k-项集用于探索（k+1）-项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1-项集的集合。该集合记为L1。然后使用L1找出频繁2-项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k-项集。找出每个Lk需要一次数据库的完整扫描。一般而言，诸如Apriori的关联规则挖掘是一个两步的过程。

步骤1　找出所有的频繁项集。

根据定义，这些项集的每一个频繁项出现的次数至少与规定的最小支持度计数min_sup相同。

步骤2　由频繁项集产生强关联规则。

根据定义，这些规则必须满足最小支持度和最小置信度。

为了提高频繁项集逐层产生的效率，一种称为先验性质（Apriori Property）的重要性质用于压缩搜索空间。先验性质：频繁项集的所有非空子集也一定是频繁的。

先验性质基于如下观察。根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P（I）<min_sup。如果把项集A添加到项集I中，则结果项集（即I∪A）不可能比I更频繁地出现。因此，A∪A也不是频繁的，即P（A∪A）<min_sup。

该性质属于一种特殊的性质，称为反单调性（Antimonotone），意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。称它为反单调的，是因为在通不过测试的意义下，该性质是单调的。

为了理解“如何在算法中使用先验性质”这一点，我们考虑如何使用Lk−1找出Lk，其中，k≥2。后续过程由连接步和剪枝步组成。

步骤1　连接步。

为找出Lk，通过将Lk-1与自身连接产生候选k-项集的集合，该候选项集的集合记为Ck。设l1和l2是Lk-1中的项集，li[j]表示li的第j项。为了有效地实现，Apriori算法假定事务或项集中的项按字典排序。对于（k-1）-项集li，这意味着把项排序，使得li[1]<li[2]<…<li[k-1]。如果（l1[1]=l2[1]）∧（l1[2]=l2[2]）∧…∧（l1[k-2]=l2[k-2]）∧（l1[k-1]<l2[k-1]），即l1与l2共享前（k-2）项，则l1与l2是可连接的。条件（l1[k-1]<l2[k-1]）是简单地确保不产生重复，连接l1和l2产生的结果项集是｛l1[1],l1[2],…,l1[k-1],l2[k-1]｝。

步骤2　剪枝步。

Ck是Lk的超集，也就是说，Ck的成员可能是频繁的也可能不是频繁的，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk（即根据定义，计数值不小于最小支持度计数的所有候选都是频繁的，从而属于Lk）。然而，Ck可能很大，因此计算量就很大，为了压缩Ck，可以使用先验性质。任何非频繁的（k-1）-项集都不是频繁k项集的子集。如果一个候选的k-项集的（k−1）-项子集并不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除。这种子集测试可以使用频繁项集的散列树快速完成[2]。

一旦由数据库D中的事务找出频繁项集，就可以直接由它们产生强关联规则（满足最小支持度和最小置信度）。对于置信度，可以用式（1-1）计算：

条件概率用项集的支持度计数表示，其中，support_count（A∪B）是包含项集A∪B的事务数，而support_count（A）是包含项集A的事务数。根据式（1-1），产生关联规则如下：

• 对于每个频繁项集l，产生l的所有非空子集；

• 对于l的每个非空子集s，如果，则输出规则

“s⇒（l−s）”。其中，min_conf是最小置信度阈值。

由于规则由频繁项集产生，每个规则都自动地满足最小支持度。频繁项集和它们的支持度可以预先存放在散列表中，使得它们可以被快速访问。