实现原理：Apriori算法

在开始介绍Apriori算法前，需要明确几个重要概念。

（1）N项集

表示由N个元素组成的元素集合（N为大于0的整数）。

（2）N项集的支持度

表示在所有样本中，能够匹配特定N项集要求的样本数量，它也可以表示成百分比的形式。

（3）频繁N项集（L[n]）

表示满足指定的最小支持度的所有N项集。

（4）候选N项集（C[n]）

它由频繁N-1项集L[n-1]生成，是计算频繁N项集的基础，C[n]必须保证包括所有的频繁N项集L[n]。(www.xing528.com)

现在开始介绍Apriori算法的基本实现原理。使用Apriori算法进行关联规则挖掘时主要分为以下几个步骤：

1）首先寻找L[1]（即频繁1项集）；

2）在L[k]的基础上生成候选频繁k+1项集C[k+1]；

3）用事务数据库D中的事务对所有C[k+1]进行支持度测试以寻找频繁项集L[k+1]，计算每个候选频繁项集的支持度，如果大于最小支持度，则加入到L[k+1]；

4）如果L[k+1]为空集，则结束，L[1]∪L[2]∪…即为结果；否则转2）继续。

Apriori算法的伪代码如代码清单6-1所示。

【代码清单6-1】

一讲到算法，也许很多读者都会产生抵触心理，笔者也不大喜欢一堆的数学符号，而是希望通过简单的实例来介绍算法的本质，下一节我们就将通过一个简单的例子来揭开Apriori算法的面纱。当然，如果读者对Apriori算法已经很了解可直接跳过下一节。