2.2 传统数据集中频繁模式挖掘的典型算法
传统数据集中的频繁模式挖掘算法不仅是对应数据流中频繁模式挖掘算法的基础，同时也是不确定数据集中频繁模式挖掘算法[111,115,120-122,125]和高效用模式挖掘算法[127-132]的基础，同时在序列模式挖掘[152-155]、事务间的频繁项集挖掘、异常检测[73,156-159]、分类[157,160-163]和聚类[164]算法中得到应用。
本节主要详细描述几个传统数据集中典型的频繁模式挖掘算法。
2.2.1 Apriori算法
Apriori算法是一个典型的逐层挖掘算法，后继的很多逐层挖掘算法都是基于Apriori算法的改进。以Apriori算法为例说明逐层挖掘的算法步骤：①扫描一遍数据集，找出所有频繁1-项集。②用任两个频繁1-项集组合产生所有的候选2-项集，再扫描一遍数据集统计候选项集中每个项集的支持数，从中找出所有的频繁2-项集。③用频繁2-项集组合产生候选3-项集，要求组合的两个2-项集中有一个元素（项）相同；如果产生的3-项集的子集中存在长度为2的项集不是频繁2-项集，则该3-项集就不是一个候选项集；候选项集产生以后，再扫描一遍数据集统计候选3-项集中每个项集的支持数，从中找出所有的频繁3-项集。④同③中方法，逐次挖掘出频繁k-项集（k≥4），直到没有新的频繁项集产生为止。
算法Apriori的主要缺点是需要多次扫描数据集来统计候选项集的支持数，如果产生的最长频繁项集的长度是k，则算法需要k或k+1次数据集扫描；如果用户预定义的最小阈值比较小或者数据集比较大，则候选项集就会很多，因此该类算法的效率会受到很大的影响。
2.2.2 FP-Growth算法
FP-Growth算法是一个典型的模式增长算法，并且也是第一个模式增长算法，后继的很多模式增长算法都是基于该算法进行改进。FP-Growth算法相对Apriori算法，在很多情况下（如用户预定义最小阈值比较低、数据集包含的项比较多或者数据集中包含的长事务项集比较多等）, FP-Growth算法的效率得到了很大的提高。以表2.1中数据集为例说明FP-Growth算法的挖掘步骤（这里设定用户预定义的最小支持数为3）。
表2.1 一个传统事务数据集实例
步骤1 扫描一遍数据集，统计各项的支持数，并将支持数大于等于最小支持数的项按支持数从大到小保存到一个头表H中，图2.1（a）为实例中数据统计的头表H（其中头表中的link字段存储每项在树上的所有节点指针；还有另外一种处理方法，只将每个项在树上的第一个节点保存在link中，下一个同名节点的指针依次保存在上一个节点中）。
图2.1 FP-Tree的构建实例
步骤2 再次扫描数据集，将数据集中的所有事务项集添加到一棵树上，首先删除事务项集中不频繁的项（不在头表中的项都是不频繁的），事务项集中剩余项按头表的顺序添加到树上，对应的每个节点支持数都增加1。图2.1（b）是表2.1中第一个事务项集添加到树上后的结果，同时也将新建的节点指针保存到头表对应项的link中，节点上数字表示该节点的支持数；图2.1（c）是前两个事务项集添加到树上后的结果；当第三个事务项集{a, b, c, d}往树上添加的时候，由于可以和路径root-a-c-d共享节点a和c，所以只需将已存在的两个节点的支持数增加1，然后将剩余的项依次添加到节点c的子孙中，图2.1（d）是前三个事务项集添加到树上后的结果；图2.1（e）是所有事务项集添加到树上后的结果（为了能使FP-Tree看起来清晰，图2.1（e）中没有标识头表中link的信息）。
步骤3 从头表H的最后一项开始依次处理每一项，如头表H中的最后一项d，首先将该项添加到初始值为空的基项集base-itemset中，即base-itemset={d}；从头表H中的link信息中可以找到项d在FP-Tree上的所有节点，扫描每个节点d到根节点路径，统计出现的所有项及项的支持数，其中同一路径上所有项的支持数都为该路径上节点d的支持数，将统计的结果保存到同头表H结构相同的一个新头表subHd（该头表也称为子头表），同样该子头表中仅仅保存支持数大于等于最小支持数3的项，同时头表中所有项按支持数从小到大排序，新创建的头表subHd如图2.2（a）所示；再次扫描所有节点d到根节点的路径，将路径上的所有项按子头表subHd的顺序排序，同时删除不在子头表中的项，然后将有序的项集和支持数（所有项的支持数都等于节点d的支持数）添加到一棵子树subHd（该树也称为当前基项集{d}的条件子树，简称子树），如图2.2（b）所示；按照以上处理方法递归处理子头表subHd和子树subTd，分别能得到两个新的基项集{dc}、{dca}、{db}、{dba}和{da}，图2.2（c）是项集{dc}的子树和子头表。
图2.2 子（条件）FP-Tree和子头表
步骤4 从当前基项集base-itemset中删除当前处理的项。
步骤5 继续处理当前被处理头表的下一项。
FP-Growth算法的步骤可以简述如下：
步骤1 扫描数据集，创建头表H，如图2.1（a）中头表。
步骤2 扫描数据集，创建FP-Tree，如图2.1（e）中的FP-Tree。
步骤3 依次处理头表H中所有项（从最后一项开始，假设当前处理的项为Q）：
步骤3.1 将当前处理项Q添加到一个初始值为空的基项集（每新产生一个基项集，即为一个新频繁项集）。
步骤3.2 扫描FP-Tree上所有节点Q到根节点路径，构建一个子头表subHQ，构建子头表的具体方法如上例中子头表subHd的构建（图2.2（a））。
步骤3.3 如果子头表subHQ不为空，则为基项集构建一棵条件子树subTQ，具体构建方法如上例中条件子树subTd的构建，否则执行步骤4。
步骤3.4 按照处理头表H的方法，递归处理子头表subHQ和子树subTd。
步骤4 将当前处理的项从基项集中删除。
步骤5 处理当前处理头表的下一项。
2.2.3 COFI算法
COFI算法同FP-Growth一样，通过两遍数据集的扫描，创建一个头表H和一棵FP-Tree。接下来，就不像FP-Growth那样递归处理建好的树和头表，COFI是通过为头表中每一项构建一棵COFI-Tree来挖掘包含该项的所有频繁项集，下面以表2.1的数据为例来说明COFI算法的挖掘步骤。
步骤1 通过两遍数据集的扫描，构建了头表H和FP-Tree，如图2.3（a）、（b）所示，这里的头表和FP-Tree同图2.1（a）、（e）中的相同。
步骤2 从头表H的最后一项开始依次处理每项，扫描图2.3（b）中所有节点d到根节点root路径，统计出现项的支持数，得到图2.3（c）中的头表subHd。
步骤3 如果头表subHd不为空，按如下的子步骤创建一棵以d为根的COFI-Tree；否则执行步骤5。
步骤3.1 扫描图2.3（b）中所有节点d到根节点root的路径，将每个路径上所有项取出来（路径上取出的所有项记为项集X）。
步骤3.2 将项集X中不频繁的项（不在头表subHd中的项）删除。
步骤3.3 按头表subHd的顺序排列项集X中所有的项。
步骤3.4 将有序的项集X添加到一棵以d为根的COFI-Tree上。
按步骤3.1～3.3处理完所有包含节点d的路径后，得到4个项集：{a, c}、{b, a}、{b, a, c}和{b}，前3个的支持数都为1，最后一个是2；用这4个有序的项集所创建的以d为根的COFI-Tree，如图2.3（c）的树subTd所示，树上每个节点记录2个数值：一个是节点的总支持数，一个是节点参与支持数（该支持数是在挖掘过程中使用，初始值为0）。
图2.3 COFI算法的挖掘实例
步骤4 挖掘以d为根的COFI-Tree，挖掘的步骤如下：
步骤4.1 依次处理头表subHd中的每一项，从头表的最后一项c开始处理，树subTd上有两个路径上包含节点c，依次处理每个路径：①将第一个路径d-a-b-c上的所有节点的参与支持数（节点上记录的第二个数）增加2（2是该路径上节点c的支持数），如图2.3（d）上的路径d-a-b-c所示，同时取出路径上所有项，即ab和c; ②用这些项组合产生了一个项集的集合CS，该集合中每个项集的支持数都为节点c的支持数，即CS={a:2, ab:2, ac:2, abc:2, b:2, bc:2, c:2}; ③将项d添加到该集合的每个元素中，CS={ad:2, abd:2, acd:2, abcd:2, bd:2, bcd:2, cd:2}。
步骤4.2 依次处理包含节点c的另外一路径d-a-c:①将该路径上所有节点的参与支持数都增加1（1是该路径上节点c的支持数），如图2.3（e）上的路径d-a-c所示，同时取出该路径上所有项a和c; ②用这些项组合产生了一个项集的集合CS0，该集合中每个项集的支持数都为节点c的支持数，即CS0={a:1, ac:1, c:1}; ③将项d添加到该集合的每个元素中，CS0={ad:1, acd:1, cd:1}; ④将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS={ad:3, abd:2, acd:3, abcd:2, bd:2, bcd:2, cd:3}。
步骤4.3 依次处理头表subHd的第二项b，树subTd上有两个路径上包含节点b，依次处理这两个路径：①在第一个路径d-a-b上，节点b的支持数和参与支持数之差是1，即大于0，所以可以进一步对该路径进行处理；②将该路径上所有节点的参与支持数都增加1（1是该路径上节点b的支持数和参与支持数之差），如图2.3（f）上的路径d-a-b，同时取出该路径上项a和b; ③用这些项组合产生了一个项集的集合CS0，每个项集的支持数都为节点b的支持数和参与支持数之差，即CS0={a:1, ab:1, b:1}; ④将项d添加到该集合的每个元素中，CS0={ad:1, abd:1, bd:1}; ⑤将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS={ad:4, abd:3, acd:3, abcd:2, bd:3, bcd:2, cd:3}。
步骤4.4 处理包含节点b的第二个路径d-b，节点b的支持数和参与支持数的差是1，大于0，所以可以进一步对该路径进行处理：①将该路径上所有节点的参与支持数都增加1（1是该路径上节点b的支持数和参与支持数之差），如图2.3（f）上的路径d-b，同时取出该路径上项b; ②用这些项组合产生了一个项集的集合CS0，每个项集的支持数都为节点b的支持数和参与支持数之差，即CS0={b:1}; ③将项d添加到该集合的每个元素中，CS0={bd:1};④将CS0中每个元素合并到CS中，如果元素存在，则将对应元素（项集）的支持数累加到CS相应的元素中，合并后的CS={ad:4, abd:3, acd:3, abcd:2, bd:4, bcd:2, cd:3}。
步骤4.5 按照步骤4.3和步骤4.4的方法处理头表Hd中下一项a，处理完之后，树Td如图2.3（g）所示，CS={ad:4, abd:3, acd:3, abcd:2, bd:3, bcd:2, cd:3}。
步骤4.6 直到处理完subHd中的所有项之后，将CS中支持数大于等于3的项集添加到频繁项集FI中，清空项集CS。
步骤5 回到步骤2处理头表H中的下一项，直到处理完所有项为止。