基于有序FP-tree结构和二维表的最大频繁模式挖掘算法

王利军，唐 立

（安徽经济管理学院 信息工程系，安徽 合肥230031）

FPMax算法［1］是基于FP-tree［2］树结构的最大频繁项集挖掘算法，该算法是一种深度优先算法，通过递归构建条件模式树进行挖掘直接获得候选最大频繁项集，检测通过后存入一根最大频繁项目树中，提高了最大频繁项集的存取速度.但FPMax算法仍存在一些问题，主要有几个方面：（1）FP-tree中的每一个节点都需要6个域空间，分别存储节点名称、支持度计数、子节点的指针、父节点的指针、兄弟节点的指针、同名节点的指针，因此FP-tree结构占用了较多的内存空间.（2）项头表中的除第一个事务项外的其他事务项都需要被挖掘，这样会大大减少挖掘效率.（3）FPMax算法进行最大频繁模式［3］挖掘时需要递归创建产生大量的条件模式树［4］，这些条件模式树仍需要占用大量的空间资源，会影响挖掘的时间效率.（4）MFI-tree［5］是FPMax算法用来存储已经产生的最大频繁模式的存储结构，并且在将候选最大频繁项集加入MFI-tree之前，需要进行超集检测浪费了一定时间资源，但其中一部分超集检测是可以避免的［6］.

1 改进方案

1.1 有序FP-tree替代FP-tree

针对FPMax算法在挖掘最大频繁模式存在的问题，需要将FP-tree结构进行改进，改进后的存储结构与FP-tree具有相似的结构，但具有单向有序性，它依旧完整地保存着频繁项集的信息，在此存储结构的基础上采用相关的策略可避免条件模式树的产生，减少遍历的节点个数和减少超集检测的次数.

1.1.1 有序FP-tree概述

有序FP-tree树结构［7］的项头表包含事务项名称、事务项编号和指向第一个节点的链接.项头表的事务项名称按照支持度计数的大小降序排列，支持度最大的事务项名称使用编号1，其他事务项的编号依次递增1，事务项名称与编号一一对应，方便后期生成最大频繁模式后进行转换.

有序FP-tree中的每个节点只包含4个域空间，它们分别为number，count，horizontal，vertical.number域存放事务项编号；count域为事务项的支持度计数；horizontal域在建立树结构时指向兄弟节点，建树完成后指向相同事务项编号的下一个节点，vertical域在建立树结构时指向第一个子节点，建树完成后实现逆转指向父节点.

有序FP-tree的建立过程与FP-tree相似，区别在建立有序FP-tree过程中，同一个父节点的子节点在插入时需要按照编号的大小升序依次排列，这样使得兄弟节点在树结构中是有序的，这样的排列结构可以为建树过程中减少遍历子节点的个数，提高了建树的效率.树结构成型后，执行指针逆转指向父节点，最终完成有序FP-tree的建立.

1.1.2 有序FP-tree与FP-tree的区别

有序FP-tree比FP-tree更优越，主要表现在几个方面.（1）FP-tree每个节点中的name域在实际使用时使用字符串数据类型存储事务名称，而有序FP-tree每个节点中的number域则采用整数型数据类型存储事务编号，字符串数据类型往往需要更大的存储空间，整数型数据类型只在完成数据挖掘后才将事务项编号转换成事务项名称.（2）有序FP-tree的每个节点只包含4个域空间，而FP-tree的每个节点则需要包含6个域空间，因此有序FP-tree比FP-tree更节省空间，结合（1）和（2）中所述，有序FP-tree占用的内存空间约为FP-tree的2/3.（3）有序FP-tree是单向的，有序FP-tree中只存在指向父节点的垂直指针和指向相同节点编号的水平指针.而FP-tree是双向的，不仅在水平方向上存在双向指向，并且在垂直方向上也存在双向指向.（4）有序FP-tree的节点在水平方向和垂直方向上都是有序排列的.建树过程可以利用水平方向上的有序性减少遍历子节点的个数，加快建树效率，而FP-tree树结构在子节点的插入步骤中没有考虑排列的顺序情况.有序FP-tree的有序性可以为后期挖掘最大频繁项集时减少挖掘事务项的数量和避免没必要的挖掘带来便利，加快挖掘效率.

1.2 消除冗余策略可以减少挖掘的事务项个数

有序FP-tree项头表中的事务项编号为1，2，3，n，最小支持度计数为minsup，根据有序FP-tree树结构的特点，该树结构具有几个特性.

定义1 最左最大分支：若有序FP-tree树结构中存在从事务项编号1到某个节点所组成的项集{1，2，3，…，k}（k≤n）为频繁项集，事务项编号是连续的，事务项编号k为后缀节点，并且该节点的支持度计数大于等于minsup，k的后续节点没有k+1或者后续节点有k+1但支持度计数小于minsup，根据有序FP-tree树结构的有序性，则＜1，2，3，…，k＞组成路径称为最左最大分支.

定理1 若＜1，2，3，…，k＞（k≤n）组成路径为最左最大分支，则{1，2，3，…，k}（k≤n）必为频繁项集，根据频繁项集的任何真子集都不可能是最大频繁项集，因此{1，2，3…，k-1}的任何子集都不是最大频繁项集.

证有序FP-tree与FP-tree树在结构上相似，＜1，2，3，…，k＞（k≤n）组成路径是以事务项编号k为后缀节点的路径，根据前缀路径性质，k的前缀路径中的每个节点与k在该路径上同时出现的次数正好等于k的支持度计数，{1，2，3，…，k}组成的项集的支持度计数为k的支持度计数，根据最左最大分支的定义可知，k的支持度计数必大于等于minsup，因此{1，2，3，…，k}项集必为频繁项集；频繁项集的任何真子集都不可能是最大频繁项集，从而获得以后缀节点为1，2，3，…，k-1的项集都不是最大频繁项集，定理得证.

根据定理1得到消除冗余策略方案，具体内容如下：若在有序FP-tree树结构中找到最左最大分支＜1，2，3，…，k＞（k≤n），则在后期的最大频繁项集挖掘时，只需要从项头表的最后一项n开始挖掘，挖掘到事务项编号k为止，而事务项编号1，2，3，…，k-1都不要挖掘，这样就可以减少挖掘的事务项个数，加快挖掘最大频繁项集的效率.

1.3 利用二维表格避免递归产生条件模式树

1.3.1 挖掘最大频繁项集的相关性质

挖掘项头表中事务项j的最大频繁项集时，设在有序FP-tree树结构中以j为尾节点的路径总数为m，则路径表示为 Pj{i}（i∈（1，m）），Pj{1}为最左侧路径，Pj{m}为最右侧路径，路径对应的项集 Dj{i}（i∈（1，m））.

定理2 若存在g，h∈（1，m），且g＜h，根据有序FP-tree的有序性，则Dj{g}不可能是Dj{h}的真子集，而Dj{h}可能是Dj{g}的真子集.

证利用反证法和举例法进行证明，存在g，h∈（1，m），且g＜h，假设 Dj{g}是 Dj{h}的真子集，则 Dj{h}包含的事务项编号必包含 Dj{g}的所有的事务项编号，如 Dj{h}为{1，3，4，6}，Dj{g}为{1，3，6}，根据有序 FP-tree 树结构建树规则要求在同一个父节点的子节点在插入时需要按照编号的大小升序依次排列，在插入Dj{g}中的事务编号6时，这个节点必在Dj{h}的事务编号4的右侧，这样Dj{h}表示的路径必在Dj{g}的左侧，即h＜g，这样与已知条件g＜h矛盾，Dj{g}不可能是Dj{h}的真子集得证；同理证得Dj{h}可能是Dj{g}的真子集.

定理3 若存在g，h∈（1，m），且g＜h和Dj{h}是Dj{g}的真子集.若Dj{g}是最大频繁项集，根据最大频繁项集的任何真子集都不可能是最大频繁项集，则Dj{h}不可能是最大频繁项集.

定理4 挖掘以j为尾节点的最大频繁项集一定是在3种情况下产生：

第一种：Dj{i}（i∈（1，m））自身就是最大频繁项集；

第二种：Dj{i}（i∈（1，m））自身不是最大频繁项集，但其右侧的以 j为尾节点的项集 Dj{t}，Dj{t}是 Dj{i}的子集，Dj{i}可能为最大频繁项集；

第三种：可能存在 a，b，…，f∈（1，m），a，b，…f，互不相等，则 Dj{a}∩Dj{b}…∩Dj{f}可能是最大频繁项集.

1.3.2 初始化二维表

有序FP-tree树中已经包含了所有的最大频繁项集信息，为了避免产生条件模式树浪费时间和空间，采用二维表保存挖掘事务项编号的所有路径和交集，采用相应计算方法直接得到最大频繁项集，从而达到减少空间的浪费，加快挖掘速度［8］.

二维表由三部分组成：第一部分存放以挖掘事务项编号的路径及交集，第二部分存放支持度计数count1，该计数为挖掘的事务项编号在树结构中节点支持度计数，第三部分存放累计支持度计数count2，方便后期进行累加计算生成最大频繁项集.

二维表第一部分的标题头存放挖掘的事务项编号开始递减到1，查找有序FP-tree中以挖掘的事务项结尾的路径，按照从左到右的顺序将所有路径信息填入二维表格（路径上包含节点则置1，否则为0），将结尾节点的支持度计数填入count1，直接将0填入count2；另外将上述路径进行交集运算，将得到的结果无重复的也录入二维表格（包含节点则置1，否则为0），直接将0填入count1和count2，至此二维表格初始化完成.

1.3.3 使用二维表格生成最大频繁模式

从二维表的第1条记录开始进行判断，若该记录的count1与count2之和大于最小支持度计数，则进行超集检测符合要求则加入最大频繁项集集合，根据定理3可知该记录的所有真子集都不是最大频繁项集，根据定理2则只需要向下查找该记录的真子集位置，然后从二维表中删除无需挖掘，从而减少了不必要的挖掘过程，并且减少了超集检测；否则，将该记录的真子集的count2值分别加上该记录的count1.采用相同的方法逐行进行判断，二维表中所有记录执行完后即可得到最大频繁项集.

2 举例说明

2.1 举例生成有序FP-tree树结构

设置最小支持度计数为3，对事务数据库D进行扫描删除每个事务中非频繁项并进行排序，根据事务项的支持度大小进行编号，整理后的数据库D’见表1，采用上述建树方法得到有序FP-tree树结构见图1.

表1 事务数据库D’

图1 有序FP-tree树结构

2.2 利用二维表格挖掘最大频繁项集

查看有序FP-tree树结构发现最左最大分支为＜1，2，3＞，根据消除冗余策略挖掘时只需要从最后编号6 开始挖掘，挖掘到编号 3 即可.以编号 6 为结尾的路径有＜6，5，3，2，1＞和＜6，4，2＞，它们的交集为＜6，2＞，事务编号6的初始化二维表见表2.

表2 事务编号6的初始化二维表

挖掘完编号6得到的二维表格见表3，得到最大频繁模式{6，2∶3}直接加入MFS.

表3 挖掘后的二维表

同理挖掘编号5得到最大频繁模式{1，2，3，5∶3}，挖掘编号4得到最大频繁模式{4∶3}，挖掘编号3得到最大频繁模式{1，2，3∶3}，因该项集为{1，2，3，5∶3}的子集，故删除.挖掘完编号 3 后即可结束挖掘，最终的最大频繁项集集合为{{6，2∶3}，{1，2，3，5∶3}，{4∶3}}，还原成事务名称{{B，F∶3}，{A，B，C，E∶3}，{D∶3}}.

3 算法性能测试

采用Order Table FPMAX和FPMax两种不同的算法对相同数据库集进行挖掘比较，通过图表的方式显示挖掘的时间效率和空间使用情况，分析图表验证Order Table FPMAX算法的优越性.实验环境为CPU i5-6500@3.2 GHz，内存4 G，64位windows7操作系统，程序采用JAVA编写，JDK版本为1.8.实验使用的3个标准数据集见表4.

表4 数据集信息

图2 执行时间比较

图3 内存消耗比较

Order Table FPMax和FPMax两种算法在同一个数据集上采用相同的支持度阈值下挖掘得到的最大频繁项集的内容是一样的，表明Order Table FPMAX算法的正确性.实验选用的三种数据集分别代表稀疏数据集、密集数据集和人工数据集，这两种不同的算法在3种数据集上的执行时间见图2，在支持度阈值较大时，两种算法的执行时间相差不大，随着支持度阈值的减少，Order Table FPMAX算法在执行时间上的优越性逐渐体现出来.内存消耗情况见图3，两种算法都是随着支持度阈值的减少而升高，支持度阈值越低时，Order Table FPMAX算法的内存消耗明显少于FPMax算法.Order Table FPMAX算法在3种类型的数据集上都具有较好的执行效率，并且内存消耗上也相对较少，因此Order Table FPMAX算法比FPMAX更加优越.