Apriori算法描述

Apriori算法描述

Apriori算法指导我们，如果要发现强关联规则，就必须先找到频繁集。所谓频繁集，即支持度大于最小支持度的项集。如何得到数据集合D中的所有频繁集呢？

有一个非常土的办法，就是对于数据集D，遍历它的每一条记录T，得到T的所有子集，然后计算每一个子集的支持度，最后的结果再与最小支持度比较。且不论这个数据集D中有多少条记录（十万？百万？），就说每一条记录T的子集个数（{1,2,3}的子集有{1}，{2}，{3}，{1,2}，{2,3}，{1,3}，{1,2,3}，即如果记录T中含有n项，那么它的子集个数是2^n-1）。计算量非常巨大，自然是不可取的。

所以Aprior算法提出了一个逐层搜索的方法，如何逐层搜索呢？包含两个步骤：

1.自连接获取候选集。第一轮的候选集就是数据集D中的项，而其他轮次的候选集则是由前一轮次频繁集自连接得到（频繁集由候选集剪枝得到）。

2.对于候选集进行剪枝。如何剪枝呢？候选集的每一条记录T，如果它的支持度小于最小支持度，那么就会被剪掉；此外，如果一条记录T，它的子集有不是频繁集的，也会被剪掉。

算法的终止条件是，如果自连接得到的已经不再是频繁集，那么取最后一次得到的频繁集作为结果。

需要值得注意的是：

Apriori算法为了进一步缩小需要计算支持度的候选集大小，减小计算量，所以在取得候选集时就进行了它的子集是否有非频繁集的判断。（参见《数据挖掘：概念与技术》一书）。

另外，两个K项集进行连接的条件是，它们至少有K-1项相同。