基于图形处理器的频繁项集挖掘

摘 要：随着各个行业的需要，频繁项集挖掘算法需要处理大量的、连续不断的、动态的数据，算法的计算量非常大，为了提高算法的性能，可以使用CPU和GPU的架构，用GPU的并行计算提高算法的性能。

关键词：频繁项集；图形处理器；挖掘；并行计算

中图分类号：TP311.13 文献标识码：A

1 引言（Introduction）

随着技术的发展，各个行业需要处理的数据的规模越来越庞大，数据挖掘技术能在海量的数据中发现数据之间隐藏的联系，关联规则挖掘能发现大量数据中的项集之间的关联，为决策提供依据。关联规则挖掘算法很多，这些算法的思想虽然有不同之处，但是挖掘关联规则的步骤都由挖掘频繁项集和发现关联规则组成。

计算机图形处理器（Graphics Processing Unit，GPU）的高速发展，为人们利用GPU进行图形处理以外的通用计算提供了良好的运行平台，GPU具有的科学计算能力在其他通用并行计算领域也得到广泛地应用。

频繁项集的挖掘算法需要处理大量的数据，GPU的通用计算能力能实现并行计算，能大大提升算法对数据的处理能力。本文主要分析在GPU的并行计算支持下的频繁项集挖掘算法。

2 频繁项集的基本概念（Basic concept of frequent

itemsets）

关联规则的挖掘是分两步来实现的，首先按照用户给定的最低阈值，找出数据集中的所有频繁项目集，然后从频繁项目集中构造规则，要求构造的规则的可信度大于等于用户设定的最低值[1]。

设U={U1，U2，…，Un}为n个不同字符的集合，其中的字符称为项或商品。任意一个集合XU称为一个项集，若|X|=k，则称X为k项集。事务（或交易）T是项的集合，且任意的TU，对应每一个事务有唯一的标识，记作TID。设A={T1，T2，…，Tn}，称A为U上的交易集或者数据集，简称交易集或者数据集。如果XT，称事务T包含X。对于一个项集X和一个交易集A，X在A中的支持度定义为X在A中的支持计数与A中总的交易个数之比，记作sup（X）。如果X的支持度大于某个给定的最小阈值，则称X是频繁的[2]。

频繁闭项集是一组事务都包含的项的最大项集。频繁闭项集和频繁项集的信息量相等，但是频繁闭项集比频繁项集的元素少很多，因此挖掘频繁闭项集能够满足用户的需求并且对减少了算法的开销，提升了频繁项集挖掘的效率，同时还减少了冗余信息的输出。最大频繁项集是指那些在所有的频繁项集中不存在超集的频繁项集。如果一个频繁项集不是其他任何频繁项集的真子项集，那么称此频繁项集为最大频繁项集。

3 图形处理器的通用计算（General computing of GPU）

最开始的GPU是专门为图形处理而设计，它内部的体系结构几乎完全按照图形流水线的方式设计，其中，每个硬件模块都代表一个图形流水线级。随着GPU的硬件结构和对应的编程语言的发展，它已经具有了通用计算能力，在需要大量计算的并行计算领域有很多应用[3]。GPU的硬件结构的更新，为其编程语言的设计提供了可靠的硬件平台，而GPU编程语言的发展也为GPU的广泛应用提供了软件环境。GPU能满足密集型数据的计算，并能实现并行化计算，但是它对计算的流程控制和数据的缓存能力较CPU弱。GPU上的执行的线程是超轻量级的，创建或释放线程需要的能量消耗较低，基本可以忽略线程切换的时钟消耗，因此，能对处理的不同数据频繁做线程切换，完成高密度计算，可以不使用较大的数据缓存，隐藏了存储器访问的延迟。

CUDA是一种通用的GPU编程模型，它绕过了图形流水线，直接对GPU的硬件核心做了一层多线程封装，根据GPU提供的多线程并行编程接口，可以有效地实现多线程编程，开发线程级别并行运算[4]。CUDA是对C语言的一个极小扩展，降低了程序员的学习难度，使得GPU能够更有效地用于通用计算。CUDA编程是在GPU和CPU的架构上实现的，使用单指令多线程的执行模型，具有很强的并行特点。CPU和GPU是互相协同工作的，其中，CPU作为主处理器，主要负责复杂控制逻辑的调度和运算和串行任务及计算，而GPU作为协处理器，主要负责并行任务的处理，执行并行计算，负责执行逻辑简单但是计算密度高的大规模任务。

4 基于图形处理器的频繁项集挖掘（Frequent

itemset mining based on GPU）

Lossy Counting算法能在数据流中挖掘频繁项集，它把数据流信息存储在主存中的一个样本集合中，当数据流的项目到来时，判断它的值是否出现在这个存储好的样本集合中，如果该项目已存在样本集合中，就把该项目的相应的计数器加1；否则，将新到的数据流项目以及该项目此前在数据流中出现频率的上界加入到样本集合中。

FP-DS算法也是挖掘数据流频繁项集的一个有效算法，该算法根据数据流的特点，在FP-growth算法基础上，采用数据分段的思想对数据流进行逐段挖掘，用户可以连续在线获得当前的频繁项集。通过与给定的误差进行比较，FP-DS算法裁剪掉了大量的非频繁项集，从而减少了对数据的存储，节约了存储空间[5]。

FP-Stream算法以FP-Tree为基础，用FP-Growth挖掘频繁项集，并通过引入倾斜时间框架和Pattern-Tree来记录不同时间粒度的频繁项集，在数据流到来时，能维护和更新倾斜时间框架和Pattern-Tree结构的数据流频繁项集挖掘算法。FP-stream算法中的FP-stream结构包含两个部分，一个是一棵在内存中进行维护和更新的全局FP-tree，用来存储当前频繁项集，供挖掘使用；一个是嵌入到模式树的各个节点之中的倾斜时间窗口，用来存储不同时间段的支持度。

DSM-MFI算法是挖掘最大频繁项集的算法，该算法用于对界标窗口模型挖掘，仅需单遍扫描数据。DSM-MFI算法采用概述频繁项集森林结构存储所有的事务数据信息，当用户提出挖掘要求时，对概述频繁项集森林进行自顶向下的搜索，用以挖掘其中的所有最大频繁项集。DSM-MFI算法先从内存中读取一个窗口大小的事务，并按照文法顺序排序事务中的项目，然后构造并维护概述频繁项集森林，再从概述频繁项集森林中剪去非频繁信息，最后搜索概述频繁项集森林获得最大频繁项集。

除了这几种算法外，还有许多频繁项集的挖掘算法，但是这些算法都面临着共同的问题，数据量巨大且源源不断，使算法的计算量非常大。仅仅提高计算机的CPU性能很难让算法发挥最大效率，因此，可以利用GPU并行计算的特点，把这些算法移植到CPU+GPU的平台上，让GPU发挥协处理器的功能，提高对项集操作和支持度计算的运算速度，从而提高算法的效率。

5 结论（Conclusion）

作为数据挖掘的一个重要的研究领域，关联规则挖掘在各个领域尤其是商业销售方面有极其广泛及重要的应用。频繁项集挖掘算法的改进对关联规则挖掘至关重要，但是大部分频繁项集的挖掘算法的计算量都较大，而且要处理的数据量也是巨大。GPU的并行计算模式可以提高频繁项集挖掘算法的效率，提供算法的性能，是一个重要的研究方向。

参考文献（References）

[1] 朱彦霞，等.改进的频繁项集挖掘算法[J].计算机工程与应用，

2009，45（4）：143-145.

[2] 舒平达，陈华辉.数据流上最近频繁项集挖掘算法[J].计算机

工程与应用，2009，45（18）：152-155.

[3] 李海峰.基于GPU的闭合频繁项集挖掘方法[J].计算机工程，

2011，37（14）：59-61.

[4] 张庆科，等.基于GPU的现代并行优化算法[J].计算机科学，

2012，39（4）：304-310.

[5] 张敏，姚良威，侯宇.基于向量和矩阵的频繁项集挖掘算法研

究[J].计算机工程与设计，2013，34（3）：939-943.

作者简介：

陈凤娟（1979-），女，硕士，副教授.研究领域：数据挖掘，粗

糙集.endprint