基于位存儲Tid的CPU并行化Eclat算法

孫宗鑫,張桂蕓

(天津師范大學 計算機與信息工程學院,天津 300387)

0 概述

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

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

本文針對以上優化算法存在的問題,在Eclat算法[8-9]的基礎上,提出一種位并行化Eclat(Bit Parallel Eclat,BPEclat)算法。該算法采用二進制位存儲結構[10-11]和動態分配挖掘任務的CPU并行挖掘模式[12-13],以提高頻繁項目集的挖掘效率。

1 Eclat算法原理

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

圖1 2種數據表示格式

1.1 算法原理

Eclat算法是采用垂直數據表示格式的頻繁項目集挖掘算法,同時引入了等價類的概念將搜索空間劃分為多個不重疊的子空間,用深度優先搜索策略依次挖掘每個子空間內的頻繁項目集。

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

Eclat算法描述如下:

輸入事務數據庫DB,支持度閾值Min_Supp

輸出所有頻繁項目集L

步驟1掃描數據庫計數挖掘頻繁1-項目集L1和頻繁1-項目集垂直Tid列表L1.Tid。

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

1.2 Eclat算法

1.2.1 內存消耗問題

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

1.2.2 挖掘效率問題

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

2 BPEclat算法原理

2.1 BPEclat算法及其改進

針對1.2節提出的Eclat及其改進算法的不足,本文提出以下3點改進策略:

1)二進制串垂直Tid列表(以下簡稱位垂直Tid列表)。為降低Eclat算法及相關改進算法對內存的消耗,對算法中垂直Tid列表以存儲Tid的方式進行深度優化,將原有Tid由一個整數型記錄變為由一個二進制位記錄。Tid信息標記到與Tid相等的二進制串下標的位置,即將二進制串下標等于Tid的二進制位置1,格式如圖2所示。其中,圖2(a)為6個項目Tid列表(采用Uint16數組存儲)占用空間(16×20)320位,圖2(b)為存儲6個項目Tid列表占用空間(6×6)36位。

圖2 傳統垂直Tid列表與位垂直Tid列表對比

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

圖3 Tid列表生成原理對比

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

圖4 等價類多線程挖掘原理示意圖

2.2 BPEclat算法實現策略

2.2.1 位垂直Tid列表的數據結構

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

2.2.2 位垂直Tid列表的生成

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

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

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

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

2.2.3 候選項目的支持度計數

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

2.2.4 多線程挖掘任務分配

多線程挖掘任務分配方法如下:

1)等價類權重估算

xi的等價類[xi]的權重σ[xi]估算公式為:

2)動態規劃分配方法的基本實現策略

由于硬件條件的限制,理想狀態下為每個等價類分配一個線程并行挖掘各自等價類的頻繁項目,在多數挖掘環境下無法實現(因為邏輯處理器數量<<等價類數量,而等價類數量與挖掘深度的平方成正比),因此算法在并行挖掘階段采用動態規劃分配方法,對挖掘任務進行實時分配以確保各線程的負載均衡。具體策略如下:

(1)挖掘任務初始分配。根據挖掘平臺CPU核心及線程數同時計算每個等價類權重σ[xi],然后依據每個等價類權重σ[xi]把等價類分配到各線程進行頻繁項目挖掘。

(2)各線程挖掘任務再分配。當檢測到各線程當前工作線程數小于任務初始化的并行工作線程數時(一般等于挖掘平臺的邏輯處理器個數),將隨時采用挖掘初始任務分配策略依線程內的等價類權重進行再分配,以確保硬件資源滿負荷工作。

采用動態規劃分配方法進行任務分組,在一定程度上確保了各個線程間負載均衡。

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

圖6 BPEclat算法總體流程

3 實驗結果與分析

3.1 實驗環境與實驗數據

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

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

表1 實驗數據集主要特征

3.2 結果對比分析

3.2.1 算法結果對比

圖7～圖10為算法在4個數據集上運行時間和內存消耗的實驗結果。

圖7 3種算法在數據集1上的運行時間和內存消耗對比

圖8 3種算法在數據集2上的運行時間和內存消耗對比

圖9 3種算法在數據集3上的運行時間和內存消耗對比

圖10 3種算法在數據集4上的運行時間和內存消耗對比

實驗中PEclat算法和Eclat算法的每個項目垂直Tid列表均采用Uint32數組類型存儲Tid列表。

3.2.2 算法結果分析

Eclat算法分析結果如下:

1)由實驗得出BPEclat算法在4個數據集上內存消耗對比(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),在稀疏型數據集上算法空間復雜度平均降低15倍左右,在密集型數據集上算法空間復雜度平均降低2.5倍左右。

從以上對比結果可得,采用位存儲Tid的BPEclat算法在內存消耗方面遠遠優于Eclat算法和PEclat算法,即使在多核多線程的挖掘模式下,內存消耗依然控制在較低水平。BPEclat算法在內存消耗方面的優越表現在稀疏型數據集上尤為突出。

2)由實驗得出BPEclat算法在4個數據集上運行時間對比(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),在稀疏型數據集上算法時間復雜度平均增加0.1倍左右,在密集型數據集上算法時間復雜度平均降低1.6倍左右。

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

綜合3種算法在4個實驗數據集的實驗對比可以驗證,BPEclat算法一定程度上提高挖掘效率,大大優化了內存的消耗。

4 結束語

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