基于FP—growth的频繁模式挖掘算法的改进

王利军

摘要：经典的FP-growth数据挖掘需要两次遍历数据库，为了提高挖掘效率和减少遍历数据库的次数，本人提出一种采用二维表存储数据的方案，处理后的二维表中存储着删除了非频繁项和排完序的事务，可以为后续建FP-tree结构提供数据。

关键词：FP-growth；二维表；存储数据

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2019）04-0012-02

Abstract：The classical FP-growth data mining needs to traverse the database twice. In order to improve the efficiency of mining and reduce the number of times traversing the database， I propose a scheme of using atwo-dimensional table to store data. This table stores deleted infrequent items and arranged transactions， which can provide data for buildingFP-treestructure.

Key words： FP-growth； two-dimensional table； storage data

经典的FP-growth[1]数据挖掘主要包括如下步骤：首先遍历事务数据库D，并将数据库中事务数据信息读取出来并存储到内存中，对事务数据信息包含的数据项进行频度统计和排序，对每一个事务中事务项按照从高到低的顺序排序形成有序事务，根据最小支持度进行删除相应的事务项，符合要求的事务项按照从高到低的顺序从而生成项头表L；第二次对数据库D进行扫描来构建FP-tree[2]结构；最后根据FP-tree结构进行频繁模式[3]挖掘，获取关联规则。本文将对经典的FP-growth数据挖掘算法进行改进，减少对事务数据库的遍历次数，从而提高FP-growth数据挖掘的效率。

1算法改進：采用二维表[4]存储数据

本文以实例的方式进行阐述，设置最小支持度计数为2，为了减少对数据库的遍历次数可以在第一次对事务数据库D如表1所示进行扫描时，发现存在14个事务项，分别为A，B，C，D，E，F，G，I，J，O，P，L，M，N，为了使用二维表保存所有事务的信息，二维表中的行代表事务项，二维表中的列代表事务，事务项在事务中出现，则将对应的单元格的值修改为1，如表2所示，对所生成的二维表统计每行1的个数就是该事务项的支持度计数，根据各事务项的支持度计数按照从高到低进行排序，删除低于最小支持度计数的事务项，本案例中删除事务项O，P，I，J，L，M，N行，删除这些行时即对每一个事务中小于最小支持度计数的项进行了删除，后期编程第一次遍历事务数据库存储数据时采用动态数组，当进行了事务项删除后即可释放这些空间，以达到空间最优化，排序后的二维表如表3所示，保留下来的事务项和各自行1的个数即可确定项头表L中事务项名和支持度计数如表4所示，每一个事务已进行了删减和排序，纵向查看事务信息即可得到删除和排序后事务信息，如T001的事务信息为1110101，代表{A，C，E，B，F}，后期创建FP-tree结构直接根据排序后的二维表数据即可，无须再次遍历事务数据库，减少对数据库的遍历次数可以节省时间。

总之，采用二维表存储数据的方案在整个挖掘过程只需要遍历一次事务数据库D，从而达到减少扫描事务数据库D的次数，利用该二维表可以快速排序每个事务并删除了非频繁项，快速生成FP-tree的项头表，从而提高后续的建树效率。

参考文献：

[1] 唐颖峰，陈世平.一种基于后缀项表的并行闭频繁项集挖掘算法[J].计算机应用研究，2014.

[2] 尹治华，等.一种改进的基于FP-Tree的高效挖掘最大频繁项目集算法[J].济南大学学报（自然科学版） ，2017.

[3] 邢长征.垂直数据格式挖掘频繁项集算法的改进[J].计算机工程与科学，2017.

[4] 叶福兰.基于FP-tree的最大频繁模式挖掘算法的改进[J].成都大学学报（自然科学版），2014.

【通联编辑：光文玲】