摘 要：隨著各個行業(yè)的需要，頻繁項集挖掘算法需要處理大量的、連續(xù)不斷的、動態(tài)的數(shù)據(jù)，算法的計算量非常大，為了提高算法的性能，可以使用CPU和GPU的架構(gòu)，用GPU的并行計算提高算法的性能。

關(guān)鍵詞：頻繁項集；圖形處理器；挖掘；并行計算

中圖分類號：TP311.13 文獻標(biāo)識碼：A

1 引言（Introduction）

隨著技術(shù)的發(fā)展，各個行業(yè)需要處理的數(shù)據(jù)的規(guī)模越來越龐大，數(shù)據(jù)挖掘技術(shù)能在海量的數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)之間隱藏的聯(lián)系，關(guān)聯(lián)規(guī)則挖掘能發(fā)現(xiàn)大量數(shù)據(jù)中的項集之間的關(guān)聯(lián)，為決策提供依據(jù)。關(guān)聯(lián)規(guī)則挖掘算法很多，這些算法的思想雖然有不同之處，但是挖掘關(guān)聯(lián)規(guī)則的步驟都由挖掘頻繁項集和發(fā)現(xiàn)關(guān)聯(lián)規(guī)則組成。

計算機圖形處理器（Graphics Processing Unit，GPU）的高速發(fā)展，為人們利用GPU進行圖形處理以外的通用計算提供了良好的運行平臺，GPU具有的科學(xué)計算能力在其他通用并行計算領(lǐng)域也得到廣泛地應(yīng)用。

頻繁項集的挖掘算法需要處理大量的數(shù)據(jù)，GPU的通用計算能力能實現(xiàn)并行計算，能大大提升算法對數(shù)據(jù)的處理能力。本文主要分析在GPU的并行計算支持下的頻繁項集挖掘算法。

2 頻繁項集的基本概念（Basic concept of frequent

itemsets）

關(guān)聯(lián)規(guī)則的挖掘是分兩步來實現(xiàn)的，首先按照用戶給定的最低閾值，找出數(shù)據(jù)集中的所有頻繁項目集，然后從頻繁項目集中構(gòu)造規(guī)則，要求構(gòu)造的規(guī)則的可信度大于等于用戶設(shè)定的最低值[1]。

設(shè)U={U1，U2，…，Un}為n個不同字符的集合，其中的字符稱為項或商品。任意一個集合XU稱為一個項集，若|X|=k，則稱X為k項集。事務(wù)（或交易）T是項的集合，且任意的TU，對應(yīng)每一個事務(wù)有唯一的標(biāo)識，記作TID。設(shè)A={T1，T2，…，Tn}，稱A為U上的交易集或者數(shù)據(jù)集，簡稱交易集或者數(shù)據(jù)集。如果XT，稱事務(wù)T包含X。對于一個項集X和一個交易集A，X在A中的支持度定義為X在A中的支持計數(shù)與A中總的交易個數(shù)之比，記作sup（X）。如果X的支持度大于某個給定的最小閾值，則稱X是頻繁的[2]。

頻繁閉項集是一組事務(wù)都包含的項的最大項集。頻繁閉項集和頻繁項集的信息量相等，但是頻繁閉項集比頻繁項集的元素少很多，因此挖掘頻繁閉項集能夠滿足用戶的需求并且對減少了算法的開銷，提升了頻繁項集挖掘的效率，同時還減少了冗余信息的輸出。最大頻繁項集是指那些在所有的頻繁項集中不存在超集的頻繁項集。如果一個頻繁項集不是其他任何頻繁項集的真子項集，那么稱此頻繁項集為最大頻繁項集。

3 圖形處理器的通用計算（General computing of GPU）

最開始的GPU是專門為圖形處理而設(shè)計，它內(nèi)部的體系結(jié)構(gòu)幾乎完全按照圖形流水線的方式設(shè)計，其中，每個硬件模塊都代表一個圖形流水線級。隨著GPU的硬件結(jié)構(gòu)和對應(yīng)的編程語言的發(fā)展，它已經(jīng)具有了通用計算能力，在需要大量計算的并行計算領(lǐng)域有很多應(yīng)用[3]。GPU的硬件結(jié)構(gòu)的更新，為其編程語言的設(shè)計提供了可靠的硬件平臺，而GPU編程語言的發(fā)展也為GPU的廣泛應(yīng)用提供了軟件環(huán)境。GPU能滿足密集型數(shù)據(jù)的計算，并能實現(xiàn)并行化計算，但是它對計算的流程控制和數(shù)據(jù)的緩存能力較CPU弱。GPU上的執(zhí)行的線程是超輕量級的，創(chuàng)建或釋放線程需要的能量消耗較低，基本可以忽略線程切換的時鐘消耗，因此，能對處理的不同數(shù)據(jù)頻繁做線程切換，完成高密度計算，可以不使用較大的數(shù)據(jù)緩存，隱藏了存儲器訪問的延遲。

CUDA是一種通用的GPU編程模型，它繞過了圖形流水線，直接對GPU的硬件核心做了一層多線程封裝，根據(jù)GPU提供的多線程并行編程接口，可以有效地實現(xiàn)多線程編程，開發(fā)線程級別并行運算[4]。CUDA是對C語言的一個極小擴展，降低了程序員的學(xué)習(xí)難度，使得GPU能夠更有效地用于通用計算。CUDA編程是在GPU和CPU的架構(gòu)上實現(xiàn)的，使用單指令多線程的執(zhí)行模型，具有很強的并行特點。CPU和GPU是互相協(xié)同工作的，其中，CPU作為主處理器，主要負責(zé)復(fù)雜控制邏輯的調(diào)度和運算和串行任務(wù)及計算，而GPU作為協(xié)處理器，主要負責(zé)并行任務(wù)的處理，執(zhí)行并行計算，負責(zé)執(zhí)行邏輯簡單但是計算密度高的大規(guī)模任務(wù)。

4 基于圖形處理器的頻繁項集挖掘（Frequent

itemset mining based on GPU）

Lossy Counting算法能在數(shù)據(jù)流中挖掘頻繁項集，它把數(shù)據(jù)流信息存儲在主存中的一個樣本集合中，當(dāng)數(shù)據(jù)流的項目到來時，判斷它的值是否出現(xiàn)在這個存儲好的樣本集合中，如果該項目已存在樣本集合中，就把該項目的相應(yīng)的計數(shù)器加1；否則，將新到的數(shù)據(jù)流項目以及該項目此前在數(shù)據(jù)流中出現(xiàn)頻率的上界加入到樣本集合中。

FP-DS算法也是挖掘數(shù)據(jù)流頻繁項集的一個有效算法，該算法根據(jù)數(shù)據(jù)流的特點，在FP-growth算法基礎(chǔ)上，采用數(shù)據(jù)分段的思想對數(shù)據(jù)流進行逐段挖掘，用戶可以連續(xù)在線獲得當(dāng)前的頻繁項集。通過與給定的誤差進行比較，F(xiàn)P-DS算法裁剪掉了大量的非頻繁項集，從而減少了對數(shù)據(jù)的存儲，節(jié)約了存儲空間[5]。

FP-Stream算法以FP-Tree為基礎(chǔ)，用FP-Growth挖掘頻繁項集，并通過引入傾斜時間框架和Pattern-Tree來記錄不同時間粒度的頻繁項集，在數(shù)據(jù)流到來時，能維護和更新傾斜時間框架和Pattern-Tree結(jié)構(gòu)的數(shù)據(jù)流頻繁項集挖掘算法。FP-stream算法中的FP-stream結(jié)構(gòu)包含兩個部分，一個是一棵在內(nèi)存中進行維護和更新的全局FP-tree，用來存儲當(dāng)前頻繁項集，供挖掘使用；一個是嵌入到模式樹的各個節(jié)點之中的傾斜時間窗口，用來存儲不同時間段的支持度。

DSM-MFI算法是挖掘最大頻繁項集的算法，該算法用于對界標(biāo)窗口模型挖掘，僅需單遍掃描數(shù)據(jù)。DSM-MFI算法采用概述頻繁項集森林結(jié)構(gòu)存儲所有的事務(wù)數(shù)據(jù)信息，當(dāng)用戶提出挖掘要求時，對概述頻繁項集森林進行自頂向下的搜索，用以挖掘其中的所有最大頻繁項集。DSM-MFI算法先從內(nèi)存中讀取一個窗口大小的事務(wù)，并按照文法順序排序事務(wù)中的項目，然后構(gòu)造并維護概述頻繁項集森林，再從概述頻繁項集森林中剪去非頻繁信息，最后搜索概述頻繁項集森林獲得最大頻繁項集。

除了這幾種算法外，還有許多頻繁項集的挖掘算法，但是這些算法都面臨著共同的問題，數(shù)據(jù)量巨大且源源不斷，使算法的計算量非常大。僅僅提高計算機的CPU性能很難讓算法發(fā)揮最大效率，因此，可以利用GPU并行計算的特點，把這些算法移植到CPU+GPU的平臺上，讓GPU發(fā)揮協(xié)處理器的功能，提高對項集操作和支持度計算的運算速度，從而提高算法的效率。

5 結(jié)論（Conclusion）

作為數(shù)據(jù)挖掘的一個重要的研究領(lǐng)域，關(guān)聯(lián)規(guī)則挖掘在各個領(lǐng)域尤其是商業(yè)銷售方面有極其廣泛及重要的應(yīng)用。頻繁項集挖掘算法的改進對關(guān)聯(lián)規(guī)則挖掘至關(guān)重要，但是大部分頻繁項集的挖掘算法的計算量都較大，而且要處理的數(shù)據(jù)量也是巨大。GPU的并行計算模式可以提高頻繁項集挖掘算法的效率，提供算法的性能，是一個重要的研究方向。

參考文獻（References）

[1] 朱彥霞，等.改進的頻繁項集挖掘算法[J].計算機工程與應(yīng)用，

2009，45（4）：143-145.

[2] 舒平達，陳華輝.數(shù)據(jù)流上最近頻繁項集挖掘算法[J].計算機

工程與應(yīng)用，2009，45（18）：152-155.

[3] 李海峰.基于GPU的閉合頻繁項集挖掘方法[J].計算機工程，

2011，37（14）：59-61.

[4] 張慶科，等.基于GPU的現(xiàn)代并行優(yōu)化算法[J].計算機科學(xué)，

2012，39（4）：304-310.

[5] 張敏，姚良威，侯宇.基于向量和矩陣的頻繁項集挖掘算法研

究[J].計算機工程與設(shè)計，2013，34（3）：939-943.

作者簡介：

陳鳳娟（1979-），女，碩士，副教授.研究領(lǐng)域：數(shù)據(jù)挖掘，粗

糙集.endprint