1.1 .1Apriori算法的说明
在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集. 从第二步开始循环处理直到再没有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集, 然后对数据库进行搜索, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维最大项目集.
为方便后文叙述，现约定如下:
1.数据库事务中的项目都是以字母顺序排列的,每个项目用
2.每个项目集的项目数称为该项目集的size. 当项目集的size=k时, 称该项目集为k-itemset(k维项目集).
下文中遇到的以下符号,分别代表相应的内容 k-itemset k维项目集
Lk 具有最小支持度的最大k-itemset Ck 侯选的k-itemsets(潜在的最大项目集) 1.1.2关联规则经典挖掘算法Apriori
由 Agrawal 等人提出的 Apriori 是经典的关联规则和频繁项集挖掘算法，
围绕着它的改进和实现有大量的文献。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研究有着很大的影响。 为了提高频繁项目的挖掘效率，Apriori 算法利用了两个重要的性质，用于压缩搜索的空间。
【性质 3.1】若 X 为频繁项目集，则 X 的所有子集都是频繁项目集。 【性质 3.2】若 X 为非频繁项目集，则 X 的所有超集均为非频繁项目集。 Apriori 算法的处理流程为：宽度优先搜索整个项集空间，从 k=0 开始，迭代产生长
度为 k+1 的候选项集的集合 Ck+1。候选项集是其所有子集都是频繁项集的项集。C1由I0中所有的项构成，在第 k 层产生所有长度为 k+1 的项集。这由两步完成：第一步，Fk自连接。将 Fk中具有相同(k-1)-前缀的项集连接成长
度为 k 的候选项集。第二步是剪枝，如果项集的所有长度为 k 的子集都在 Fk中，该项集才能作为候选项集被加入 Ck+1中。
为了计算所有长度为 k 的候选项集的支持度，在数据库水平表示方式下，需要扫描数据库一遍。在每次扫描中，对数据库中的每条交易记录，为其中所包含的所有候选 k-项集
的支持度计数加 1。所有频繁的 k-项集被加入 Fk中。此过程直至 Ck+1等于空集时结束。
算法Apriori
Input: Transaction DataBase D，Minimum support threshold minsup。 Output： Frequent pattern L
(1) L1=search_frequent_1-itemsets( D ); (2) for(k=2;Lk-1≠φ;k++) do (3) begin
(4) Ck=apriori-gen(Lk-1); (5) for all transactions t∈D do (6) begin
(7) Ct=subset(Ck，t);
(8) for all candidates c∈Ct do (9) c.count++; (10) end
(11) Lk={c∈Ck|c.count≥minsup} (12) end
(13) Answer L=∪kLk;
Procedure Search_frequent_1-itemsets( D ) (1) begin
(2) for all transactions t∈D do (3) begin
(4) for each item ik∈t do (5) ik.count++;
(6) end
(7) L1={ i∈I | i.count≥minsup} (8) return L1; (9) end
Procedure apriori_gen(Lk) (1) begin
(2) for each itemset l1∈Lk do (3) for each itemset l2∈Lk do (4) begin
(5) if ( l1[1]=l2[1]) ∧ ( l1[2]=l2[2]) ∧ … ∧ ( l1[k-1]=l2[k-1]) ∧ ( l1[k] (8) if Is_include_infrenquent_subset(c,Lk) then (9) delete c; (10) else add c to Ck+1; (11) end (12) end (13) return Ck+1; (14) end Procedure Is_include_infrenquent_subset(c,Lk) (1)begin (2) for each k-subset s of c (3) if s Lk then (4) reture TURE; (5) return FALSE ; (6)end 在主程序中，第一步首先扫描整个交易数据库D，统计每个项目(item)的支持数，计算其支持度，将支持度大于等于最小支持度minsup的项目构成的集合 放入到L1 中；从第2步到第11步，用k-1频繁项目集构成的Lk-1生成候选集的集合Ck，以便从中生成Lk，其中apriori_gen函数(第4步)用来从Lk-1中生成Ck，然后对数据库进行扫描(第5步)，对于数据库中的每一个交易，subset函数用来发现此交易包含的所有候选集(第7步)，并为这些候选集的计数器加1(第8-9步)。最后满足minsup的候选集被放入到Lk中。 apriori_gen过程完成两种操作：并(join)和剪枝(prune)。在并运算步骤中，Lk-1 与Lk-1进行并运算生成潜在的候选集(2-7步)，条件l1[k-1] 示例说明Apriori算法运作过程 有一数据库D, 其中有四个事务记录, 分别表示为 TID Items T1 I1,I3,I4 T2 I2,I3,I5 T3 I1,I2,I3,I5 T4 I2,I5 在Apriori算法中每一步创建该步的侯选集.统计每个侯选项目集的支持度,并和预定义的最小支持度比较,来确定该步的最大项目集. 首先统计出一维项目集,即:C1.这里预定义最小支持度minsupport=2,侯选项目集中满足最小支持度要求的项目集组合成最大的1-itemsets.为生成最大的2-itemsets,使用了sc_candidate函数中join步,即: L1joinL1,并通过prune步删除那些C2的那些子集不在L1中的项目集.生成了侯选项目集C2.搜索D中4个事务,统计C2中每个侯选项目集的支持度.然后和最小支持度比较,生成L2.侯选项目集C3是由L2生成.要求自连接的两个最大2-itemsets中,第一个项目相同,在L2中满足该条件的有{I2,I3},{I2,I5}.这两个集合经过join步后, 产生集合{I2，I3，I5}.在prune步中,测试{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，
