apriori算法介绍.txt

经典的算法实例

对于单维、单层、布尔关联规则的最常用的经典算法是APRIORI算法，其他类型的关联规则算法通常是在一定约束条件下的APRIORI算法的变形。
APRRORI算法使用频繁项性质的先验知识，逐层搜索迭代，用K-项集产生(K+1)-项集。APRRORI算法的一个显著特点是:利用APRIORI性质，压缩了频繁项集，提高了算法的效率。APRIORI性质定理:频繁项集的所有非空子集都必须也是频繁的.根据定义如果项集I不满足最小支持度阐值，则I不是频繁的，即P(I)<MIN_SUP，如果项A添加到I，则结果项集(即IUA)不可能比I更频繁出现。因此，IUA也不是频繁的，即P(IUA)<MIN_SUP。APRIORI算法采用了连接和剪枝两步:(1)连接步:为找LK，通过LK-1与自己连接产生侯选K-项集的候选集合，该候选项集的集合记作CK。记号LI[J]表示LI的第J项。假定事务或项集中的项按字典次序排序， 如果(L1[1]=L2[1])∧(L1[2]=L2
[2])∧(L1[3] =L2[3])∧…∧(L1[k-2] =L2[k-2])∧(L1[k-1] <L2[k-2]) 则L1与L2是可连接的，连接产生的结果项集是L1[1]L1[2]… L1[k-1]L2[k-1] (2)剪枝步:Ck是Lk的超集:它的成员可以是频繁的，也可以是不频繁的，但所有的频繁K-项集都包含在Ck中。扫描数据库，确定Ck中每个候选的计数，从而确定Lk(即根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk)。在压缩Ck时，应用了APRIORI性质，即任何非频繁的K-1项集都不可能是频繁K项集的子集。因此，如果一个候选K项集的K-1项子集不属于Lk,则该候选项也不可能是频繁的，从Ck中删除。