基于位存儲(chǔ)Tid的CPU并行化Eclat算法

孫宗鑫,張桂蕓

(天津師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,天津 300387)

0 概述

頻繁項(xiàng)目集挖掘(Frequent Itemset Mining,FIM)在關(guān)聯(lián)規(guī)則挖掘算法中具有重要的位置,其典型算法有AIS、Apriori、AprioriTid[1]、DHP[2]、Toivoen、Eclat[3]和FP-Growth算法[4]等,總體可分為3大類,分別為基于水平數(shù)據(jù)格式的Apriori系列算法[1-2]、基于垂直數(shù)據(jù)格式的Eclat系列算法[3,5-9]和基于樹型數(shù)據(jù)格式的FP-Growth系列[4]算法。

Eclat算法由Zaki等人在2000年提出,該算法采用垂直數(shù)據(jù)表示方式且無需復(fù)雜的數(shù)據(jù)結(jié)構(gòu),因此,在頻繁項(xiàng)目集挖掘效率方面優(yōu)于Apriori系列算法,在內(nèi)存消耗方面優(yōu)于FP-Growth算法。然而,Eclat算法在挖掘頻繁項(xiàng)目集過程中,需要大量內(nèi)存對項(xiàng)目垂直事務(wù)標(biāo)識(Transaction identifier,Tid)列表進(jìn)行維護(hù),同時(shí)交集計(jì)數(shù)的生成方式造成了算法對內(nèi)存的大量消耗和挖掘效率的下降。針對上述缺點(diǎn),諸多研究學(xué)者對Eclat算法進(jìn)行了優(yōu)化改進(jìn)。文獻(xiàn)[5]提出一種布爾散列的方法,將相交的2個(gè)垂直Tid列表映射到2個(gè)布爾列表中,使用布爾列表的標(biāo)志元素判斷2個(gè)垂直Tid列表是否存在交集,在一定程度上優(yōu)化了垂直Tid列表交集過程,但由于布爾列表的使用,一定程度上也增加了內(nèi)存消耗。文獻(xiàn)[6]提出的Eclat_opt算法在傳統(tǒng)的Eclat算法基礎(chǔ)上引入了雙層哈希表和剪枝策略,加快了頻繁項(xiàng)目集的挖掘速度,但由于挖掘過程中需要在內(nèi)存中長期維護(hù)一張索引二維表,因此導(dǎo)致內(nèi)存消耗進(jìn)一步增加。文獻(xiàn)[7]提出的PEclat算法由于使用多核挖掘和算法選擇策略,因此在內(nèi)存消耗和挖掘速度兩方面都得到了一定優(yōu)化,但算法仍存在一些弊端。

本文針對以上優(yōu)化算法存在的問題,在Eclat算法[8-9]的基礎(chǔ)上,提出一種位并行化Eclat(Bit Parallel Eclat,BPEclat)算法。該算法采用二進(jìn)制位存儲(chǔ)結(jié)構(gòu)[10-11]和動(dòng)態(tài)分配挖掘任務(wù)的CPU并行挖掘模式[12-13],以提高頻繁項(xiàng)目集的挖掘效率。

1 Eclat算法原理

事務(wù)數(shù)據(jù)庫中數(shù)據(jù)的表示格式分為2種[14]:1)水平數(shù)據(jù)表示,如圖1(a)所示,在水平數(shù)據(jù)表示的事務(wù)數(shù)據(jù)庫中一條事務(wù)由唯一的Tid和單個(gè)或多個(gè)項(xiàng)目組成;2)垂直數(shù)據(jù)表示,如圖1(b)所示,在垂直數(shù)據(jù)表示的事務(wù)數(shù)據(jù)庫中一條事務(wù)由唯一的項(xiàng)目和包含此項(xiàng)目的所有Tid組成。

圖1 2種數(shù)據(jù)表示格式

1.1 算法原理

Eclat算法是采用垂直數(shù)據(jù)表示格式的頻繁項(xiàng)目集挖掘算法,同時(shí)引入了等價(jià)類的概念將搜索空間劃分為多個(gè)不重疊的子空間,用深度優(yōu)先搜索策略依次挖掘每個(gè)子空間內(nèi)的頻繁項(xiàng)目集。

Eclat算法在候選項(xiàng)目的生成中依然采用Apriori算法的鏈接方式,對2個(gè)頻繁項(xiàng)目進(jìn)行鏈接,與此同時(shí)對2個(gè)頻繁項(xiàng)目的垂直Tid列表進(jìn)行交集計(jì)數(shù),從而可以使候選項(xiàng)目的支持度計(jì)算和候選項(xiàng)目的生成同時(shí)完成,加快了頻繁項(xiàng)目的挖掘速度。

Eclat算法描述如下:

輸入事務(wù)數(shù)據(jù)庫DB,支持度閾值Min_Supp

輸出所有頻繁項(xiàng)目集L

步驟1掃描數(shù)據(jù)庫計(jì)數(shù)挖掘頻繁1-項(xiàng)目集L1和頻繁1-項(xiàng)目集垂直Tid列表L1.Tid。

步驟2基于頻繁1-項(xiàng)目集垂直Tid列表來挖掘剩余頻繁K-項(xiàng)目集(k≥2)。

1.2 Eclat算法

1.2.1 內(nèi)存消耗問題

在Eclat算法及其改進(jìn)算法[5-7]中,多數(shù)存在內(nèi)存消耗過高問題。Eclat算法和改進(jìn)算法都采用整型數(shù)組存儲(chǔ)Tid,當(dāng)項(xiàng)目出現(xiàn)頻率高且交易事務(wù)數(shù)過大時(shí),算法在挖掘過程中需要大量內(nèi)存來存儲(chǔ)臨時(shí)整型垂直Tid列表。此外,文獻(xiàn)[5-6]改進(jìn)算法分別使用布爾矩陣和二維表索引,在提高了挖掘頻繁項(xiàng)目效率的同時(shí)更進(jìn)一步增加了內(nèi)存開銷。文獻(xiàn)[7]利用稀疏因子作為參數(shù)對Eclat和dEclat算法進(jìn)行了選擇使用,在一定程度上降低了內(nèi)存消耗,但效果一般。

1.2.2 挖掘效率問題

Eclat算法和文獻(xiàn)[7]改進(jìn)算法計(jì)算候選項(xiàng)目支持度時(shí)采用垂直Tid列表進(jìn)行交集計(jì)數(shù)方式,即遍歷2個(gè)項(xiàng)目垂直Tid列表判斷每個(gè)Tid是否相等,從而得出候選項(xiàng)目支持度,同時(shí)生成新的垂直Tid列表,交集計(jì)數(shù)方式效率低下。文獻(xiàn)[7]改進(jìn)算法雖然使用多核并行挖掘,但沒有過多考慮多核之間負(fù)載均衡問題。

2 BPEclat算法原理

2.1 BPEclat算法及其改進(jìn)

針對1.2節(jié)提出的Eclat及其改進(jìn)算法的不足,本文提出以下3點(diǎn)改進(jìn)策略:

1)二進(jìn)制串垂直Tid列表(以下簡稱位垂直Tid列表)。為降低Eclat算法及相關(guān)改進(jìn)算法對內(nèi)存的消耗,對算法中垂直Tid列表以存儲(chǔ)Tid的方式進(jìn)行深度優(yōu)化,將原有Tid由一個(gè)整數(shù)型記錄變?yōu)橛梢粋€(gè)二進(jìn)制位記錄。Tid信息標(biāo)記到與Tid相等的二進(jìn)制串下標(biāo)的位置,即將二進(jìn)制串下標(biāo)等于Tid的二進(jìn)制位置1,格式如圖2所示。其中,圖2(a)為6個(gè)項(xiàng)目Tid列表(采用Uint16數(shù)組存儲(chǔ))占用空間(16×20)320位,圖2(b)為存儲(chǔ)6個(gè)項(xiàng)目Tid列表占用空間(6×6)36位。

圖2 傳統(tǒng)垂直Tid列表與位垂直Tid列表對比

2)Tid列表生成及支持度計(jì)數(shù)過程位(與)運(yùn)算化。為提高候選項(xiàng)目垂直Tid列表生成速度和候選項(xiàng)目支持度計(jì)算效率,在策略1)提出的以位存儲(chǔ)垂直Tid列表的基礎(chǔ)上,深度優(yōu)化Tid列表生成及支持度計(jì)算的過程,將以往采用2個(gè)垂直Tid列表交集計(jì)數(shù)來生成候選項(xiàng)目垂直Tid列表和計(jì)算候選項(xiàng)目支持度的方法,變?yōu)?個(gè)位垂直Tid列表的位(與)運(yùn)算和位右移計(jì)數(shù)法。對比過程如圖3所示。

圖3 Tid列表生成原理對比

3)基于動(dòng)態(tài)規(guī)劃分配策略的多線程挖掘任務(wù)分配策略[15-17]。根據(jù)Eclat算法中的等價(jià)類,將并行挖掘分配與等價(jià)類對應(yīng),Eclat算法并行化的主要難點(diǎn)在于如何有效地保持線程間的負(fù)載均衡。因此,本文將動(dòng)態(tài)規(guī)劃分配方法應(yīng)用到了挖掘任務(wù)分配階段,在整個(gè)挖掘過程中為各線程動(dòng)態(tài)分配挖掘任務(wù),以確保線程間負(fù)載均衡。等價(jià)類劃分多線程挖掘原理如圖4所示。

圖4 等價(jià)類多線程挖掘原理示意圖

2.2 BPEclat算法實(shí)現(xiàn)策略

2.2.1 位垂直Tid列表的數(shù)據(jù)結(jié)構(gòu)

BPEclat算法中項(xiàng)目位垂直Tid列表的存儲(chǔ)形式實(shí)際采用的是Uint64數(shù)組類型(即:無符號64位int型數(shù)組,每64個(gè)二進(jìn)制位用1個(gè)Uint64類型存儲(chǔ))。初始化存儲(chǔ)項(xiàng)目位垂直Tid列表的Uint64數(shù)組長度為Max_Tid/64(Max_Tid為事務(wù)數(shù)據(jù)庫DB中的事務(wù)數(shù))。

2.2.2 位垂直Tid列表的生成

BPEclat算法在整個(gè)挖掘過程中位垂直Tid列表的生成包含2個(gè)階段:

1)掃描數(shù)據(jù)庫生成候選1-項(xiàng)目位垂直Tid列表(即位垂直Tid列表的初始化)。首先內(nèi)存中維護(hù)一張hash類型位標(biāo)識表Bit_64_map(見圖5(a)),Bit_64_map中存儲(chǔ)了64位無符號整數(shù)型(Uint64)第1位到第64位為1時(shí)對應(yīng)整數(shù)值,將位垂直Tid列表相應(yīng)二進(jìn)制位所屬整數(shù)值與Bit_64_map表中相應(yīng)位整數(shù)相加,即可將項(xiàng)目位垂直Tid列表相應(yīng)二進(jìn)制位置為1,從而完成項(xiàng)目位垂直Tid列表初始化。

2)生成候選K-項(xiàng)目(K>1)位垂直Tid列表。此階段采用2.1節(jié)中策略2)給出的優(yōu)化策略來生成候選項(xiàng)目位垂直Tid列表。具體過程如圖5(b)所示。

圖5 位垂直Tid列表生成過程

2.2.3 候選項(xiàng)目的支持度計(jì)數(shù)

候選項(xiàng)目的支持度計(jì)數(shù)過程主要采用遍歷+位右移計(jì)數(shù)的方法,遍歷候選項(xiàng)目位垂直Tid列表中每個(gè)Uint64整數(shù),對每個(gè)Uint64整數(shù)采用位右移計(jì)數(shù)法,最終得出位垂直Tid列表中二進(jìn)制位為1的個(gè)數(shù),即候選項(xiàng)目的支持度。候選項(xiàng)目的支持度計(jì)數(shù)過程與圖5(b)中位垂直Tid列表的產(chǎn)生過程一同完成。

2.2.4 多線程挖掘任務(wù)分配

多線程挖掘任務(wù)分配方法如下:

1)等價(jià)類權(quán)重估算

xi的等價(jià)類[xi]的權(quán)重σ[xi]估算公式為:

2)動(dòng)態(tài)規(guī)劃分配方法的基本實(shí)現(xiàn)策略

由于硬件條件的限制,理想狀態(tài)下為每個(gè)等價(jià)類分配一個(gè)線程并行挖掘各自等價(jià)類的頻繁項(xiàng)目,在多數(shù)挖掘環(huán)境下無法實(shí)現(xiàn)(因?yàn)檫壿嬏幚砥鲾?shù)量<<等價(jià)類數(shù)量,而等價(jià)類數(shù)量與挖掘深度的平方成正比),因此算法在并行挖掘階段采用動(dòng)態(tài)規(guī)劃分配方法,對挖掘任務(wù)進(jìn)行實(shí)時(shí)分配以確保各線程的負(fù)載均衡。具體策略如下:

(1)挖掘任務(wù)初始分配。根據(jù)挖掘平臺CPU核心及線程數(shù)同時(shí)計(jì)算每個(gè)等價(jià)類權(quán)重σ[xi],然后依據(jù)每個(gè)等價(jià)類權(quán)重σ[xi]把等價(jià)類分配到各線程進(jìn)行頻繁項(xiàng)目挖掘。

(2)各線程挖掘任務(wù)再分配。當(dāng)檢測到各線程當(dāng)前工作線程數(shù)小于任務(wù)初始化的并行工作線程數(shù)時(shí)(一般等于挖掘平臺的邏輯處理器個(gè)數(shù)),將隨時(shí)采用挖掘初始任務(wù)分配策略依線程內(nèi)的等價(jià)類權(quán)重進(jìn)行再分配,以確保硬件資源滿負(fù)荷工作。

采用動(dòng)態(tài)規(guī)劃分配方法進(jìn)行任務(wù)分組,在一定程度上確保了各個(gè)線程間負(fù)載均衡。

算法整體流程如圖6所示。

圖6 BPEclat算法總體流程

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)環(huán)境為Sugon小型服務(wù)器,服務(wù)器配置信息如下:CPU為AMD 6234,48核2.4 GHz(實(shí)際使用4核),RAM為128 GB,OS為Windowsserver2012 R2,算法實(shí)現(xiàn)平臺為VS2015,算法實(shí)現(xiàn)語言為C#。

為進(jìn)行算法挖掘效率對比,使用以上平臺及語言分別實(shí)現(xiàn)了文獻(xiàn)[3]中的Eclat算法和文獻(xiàn)[7]中的PEclat算法。實(shí)驗(yàn)選取了如表1所示的4個(gè)數(shù)據(jù)集,T10.I4.D100K和T40.I10.D100K數(shù)據(jù)集是使用IBM_Quest_data_generator合成的稀疏型數(shù)據(jù)集,Mushroom和Chess數(shù)據(jù)集則來自UCI數(shù)據(jù)倉庫和fimi.ua.ac.be的密集型數(shù)據(jù)集。

表1 實(shí)驗(yàn)數(shù)據(jù)集主要特征

3.2 結(jié)果對比分析

3.2.1 算法結(jié)果對比

圖7～圖10為算法在4個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間和內(nèi)存消耗的實(shí)驗(yàn)結(jié)果。

圖7 3種算法在數(shù)據(jù)集1上的運(yùn)行時(shí)間和內(nèi)存消耗對比

圖8 3種算法在數(shù)據(jù)集2上的運(yùn)行時(shí)間和內(nèi)存消耗對比

圖9 3種算法在數(shù)據(jù)集3上的運(yùn)行時(shí)間和內(nèi)存消耗對比

圖10 3種算法在數(shù)據(jù)集4上的運(yùn)行時(shí)間和內(nèi)存消耗對比

實(shí)驗(yàn)中PEclat算法和Eclat算法的每個(gè)項(xiàng)目垂直Tid列表均采用Uint32數(shù)組類型存儲(chǔ)Tid列表。

3.2.2 算法結(jié)果分析

Eclat算法分析結(jié)果如下:

1)由實(shí)驗(yàn)得出BPEclat算法在4個(gè)數(shù)據(jù)集上內(nèi)存消耗對比(Eclat/BPEclat、PEclat/BPEclat),在圖7(b)、圖8(b)、圖9(b)、圖10(b)中依次為:(11.7,5.3),(2.9,2.2),(28.8,16.9),(3.1,2.4),在稀疏型數(shù)據(jù)集上算法空間復(fù)雜度平均降低15倍左右,在密集型數(shù)據(jù)集上算法空間復(fù)雜度平均降低2.5倍左右。

從以上對比結(jié)果可得,采用位存儲(chǔ)Tid的BPEclat算法在內(nèi)存消耗方面遠(yuǎn)遠(yuǎn)優(yōu)于Eclat算法和PEclat算法,即使在多核多線程的挖掘模式下,內(nèi)存消耗依然控制在較低水平。BPEclat算法在內(nèi)存消耗方面的優(yōu)越表現(xiàn)在稀疏型數(shù)據(jù)集上尤為突出。

2)由實(shí)驗(yàn)得出BPEclat算法在4個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間對比(Eclat/BPEclat、PEclat/BPEclat),在圖7(a)、圖8(a)、圖9(a)、圖10(a))中依次為:(1.9,1.7),(0.4,0.3),(1.6,1.3),(1.5,1.4),在稀疏型數(shù)據(jù)集上算法時(shí)間復(fù)雜度平均增加0.1倍左右,在密集型數(shù)據(jù)集上算法時(shí)間復(fù)雜度平均降低1.6倍左右。

通過以上運(yùn)行結(jié)果可以看出,在T10.I4.D100K數(shù)據(jù)集上(圖8(a))BPEclat挖掘效率下降。通過分析挖掘過程中的臨時(shí)數(shù)據(jù)后發(fā)現(xiàn),T10.I4.D100K數(shù)據(jù)集的頻繁K-頻繁項(xiàng)目(K>3)較少且大部分頻繁2-項(xiàng)目支持度過低(算法在支持度為0.02%時(shí)產(chǎn)生了70 764個(gè)頻繁2-項(xiàng)目,大約99%的頻繁2-項(xiàng)目支持度小于200),而針對T10.I4.D100K數(shù)據(jù)集的10萬條記錄,初始化每個(gè)項(xiàng)目位垂直Tid列表都要使用1 563(100 000/64+1)個(gè)Uint64,每個(gè)列表的平均占用率小于12%,算法對每個(gè)項(xiàng)目的位垂直Tid列表一次遍歷的元素個(gè)數(shù)遠(yuǎn)大于Eclat算法和PEclat算法,從而導(dǎo)致BPEclat算法在T10.I4.D100K數(shù)據(jù)集上的運(yùn)行效率不如其他2種算法。因此,BPEclat算法在對頻繁K-項(xiàng)目集(K>2)較少,且事務(wù)數(shù)據(jù)庫事務(wù)數(shù)較大的數(shù)據(jù)庫進(jìn)行頻繁項(xiàng)目集挖掘時(shí),挖掘性能表現(xiàn)不佳。

綜合3種算法在4個(gè)實(shí)驗(yàn)數(shù)據(jù)集的實(shí)驗(yàn)對比可以驗(yàn)證,BPEclat算法一定程度上提高挖掘效率,大大優(yōu)化了內(nèi)存的消耗。

4 結(jié)束語

Eclat算法是基于垂直列表的頻繁項(xiàng)目集挖掘算法,本文在分析Eclat算法及其現(xiàn)有改進(jìn)算法基礎(chǔ)上,提出一種位存儲(chǔ)事務(wù)標(biāo)識的CPU并行化Eclat算法。該算法使用二進(jìn)制位存儲(chǔ)Tid和基于動(dòng)態(tài)任務(wù)分配策略的并行挖掘模式,最大限度地提高CPU的運(yùn)算性能。實(shí)驗(yàn)結(jié)果表明,該算法在降低內(nèi)存消耗的同時(shí)提高了頻繁項(xiàng)目集的挖掘效率。但由于算法使用的多線程任務(wù)分配策略存在缺陷,在四核CPU下并行挖掘的平均加速比依然小于2.5(最優(yōu)值為4),今后將在以下2個(gè)方面進(jìn)行改進(jìn):完善BPEclat算法的多線程任務(wù)分配策略,提高算法在并行挖掘下的加速比;研究BPEclat算法的分布式并行模式,將BPEclat移植到分布式處理平臺上,以適應(yīng)大數(shù)據(jù)下的頻繁項(xiàng)目集挖掘。