Apriori算法.docx

Apriori算法Apriori算法48最早是由Agrawa等人提出。算法通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集后，进一步生成关联规则。算法利用的核心思想是频繁项集的任何非空真子集必定也是频繁的，非频繁项集的任何超集必定不是频繁的。表5-1 Apriori算法步骤Table 5-1 Steps of Apriori AlgorithmApriori算法步骤：(1) 扫描整个数据库，产生候选1-项集的集合C1(2) 根据最小支持度min_sup，从C1中产生频繁1-项集的集合L1(3) 对k1，重复执行步骤(4)、(5)、(6)(4)对Lk执行连接和剪枝操作，产生候选(k+l)-项集的集合Ck+1，(5)根据最小支持度min_sup，从Ck+1中产生频繁 (k+1)-项集的集合Lk+1(6) 若Lk，则k=k+1，跳往步骤(4); 否则，跳往步骤(7);(7) 根据最小置信度min_con，由频繁项集产生强关联规则（8）结束。 其中对产生频繁项集的连接和剪枝操作解释如下：a) 连接(join)采用递推的连接方法求，用与自身作连接产生候选k-项集的集合。具体来说，设 和 是中的项集且各项按统一标准排序。当满足条件时，则和 是可连接的，产生新的项集为：，将该项集加入集合，直到不能产生新的项集。b) 剪枝(prune)频繁k-项集的任何子集必须是频繁项集。由连接生成的集合需要进行验证，去除小于支持度阈值的非频繁k-项集。5.2.2.2 Apriori 算法描述Apriori算法主要由4个函数构成，分别如表5-2-表5-5所示。表5-2 Apriori由频繁项集产生候选集Table5-2 Apriori from Frequent Set to Candidate SetApriori_gen (Lk-1) / 通过(k-1)-频繁项集产生k-候选集begin for al1 itemset I1 in Lk-1 do for al1itemset I2 in Lk-1 doif (Il1=I2l)(I12=I22) (I1k-1=I2k-1) c=I1 join I2 ;/ 连接产生候选集 if has_infrequent_subset(c，Lk-1) delete c; else add c to Ck;end forend forendreturn Ck;表5-3 Apriori发现频繁项集Table 5-3 Apriori Find Frequent SetApriori_genfreItems（D，min_sup）输入:数据库D，最小支持度阀值min_sup输出: D中的频繁集LBeginL1=1-频繁项集;for (k=2; Lk-1; k+) doCk=Apriori_gen(Lk-l); /构造候选集for all 事务 t in D do Ct=subset(Ck，t); / 搜索t包含的候选集for all CCt do C.sup=C.sup+1; end for; /计算支持数 end for;Lk= CCt | C.sup min_sup; /得到k阶频繁项集end forEndReturn Lk=;表5-4 判断集合是否含非频繁子集 表5-5由频繁项集生成规则Table 5-4 Determine Set is Frequent or Not Table 5-5 Produce Rules from Frequent Sethas-infrequent-subset(c，Lk-1) /判断c是否含有非频繁子集Beginfor all (k-1)- subset s of c do if s Lk-1 return true; return false; End generateRule (Lk，min_con)Beginfor each I Lk dofor XI and X doif support(L)/support(X