1700498831
1700498832
1700498833
1700498834
假设D表示交易数据集；K为项集，即包含k个项的集合；Lk表示满足最小支持度的k项集；Ck表示候选k项集。Apriori算法的参考文献[1]描述如下。
1700498835
1700498836
在该算法中，候选集的计算过程如下所示。
1700498837
1700498838
1700498839
1700498840
1700498841
首先进行连接运算如下：
1700498842
1700498843
1700498844
1700498845
1700498846
然后根据频繁项集定理（即频繁项集的子集必定是频繁项集）进行剪枝，过滤掉非频繁项集，过程如下所示：
1700498847
1700498848
1700498849
1700498850
1700498851
从上述算法中可以看出，该算法存在一些困难点，譬如需要频繁扫描交易数据集，这样如果面临海量数据集，就难以满足实际应用需求；对于大型数据集，计算候选集算法的效率较低，这也是一个难以克服的问题。目前已经有一些优化的方法用于处理这些问题，譬如FP-growth算法[2]。在实际应用中，随着数据的不断增长，可能还需要通过分布式计算来提高算法性能，譬如机器学习算法包Mahout[3]中实现了的并行版本FP-growth算法。
1700498852
1700498853
2.Apriori算法实例
1700498854
1700498855
假设给定如下电子商务网站的用户交易数据集，其中，定义最小支持度为2/9，即支持度计数为2，最小置信度为70%，现在要计算该数据集的关联规则，如表3-1所示。
1700498856
1700498857
1700498858
1700498859
1700498860
计算步骤如下所示。
1700498861
1700498862
步骤1，根据Apriori算法计算频繁项集。
1700498863
1700498864
1）计算频繁1项集。扫描交易数据集，统计每种商品出现的次数，选取大于或等于最小支持度的商品，得到了候选项集，如表3-2所示。
1700498865
1700498866
1700498867
1700498868
1700498869
2）根据频繁1项集，计算频繁2项集。首先将频繁1项集和频繁1项集进行连接运算，得到2项集，如下所示：
1700498870
1700498871
1700498872
1700498873
1700498874
扫描用户交易数据集，计算包含每个候选2项集的记录数，如表3-3所示。
1700498875
1700498876
1700498877
1700498878
1700498879
根据最小支持度，得到频繁2项集，如表3-4所示。
1700498880