基于Spark字典表壓縮存儲的關聯規則算法優化

劉麗娜 姜利群

(廣州工商學院計算機科學與工程系 廣東 廣州 510850)

0 引 言

數據挖掘的概念已提出多年，其宗旨在于從海量數據中分析出對現階段或未來有意義的數據信息，它涉及的經典算法分類有頻繁項集生成[1]、頻繁模式增長[2]和垂直格式等[3-4]。其中頻繁項集生成的關聯規則(Apriori)算法尤為經典，用于挖掘數據元素之間的關系，如通過關聯規則可以得出是吃米飯的家庭離婚率高還是吃面食的家庭離婚率高[5]。關聯規則是在海量元素中找出元素之間的有趣關系。頻繁模式增長的代表算法是FP-growth[6]，其基本原理是將頻繁項集規約至一棵模式樹中并根據條件按需挖掘。垂直格式主要針對數據維數及屬性較低的數據模型，以數據維數即列項作為行標，將事務項作為列標，從而達到壓縮數據庫的目的[7]。

面對數據大爆炸的信息時代，傳統的數據處理速率已無法應對龐大的數據量，同時無法滿足人們的需求，而Spark技術的出現彌補了該缺陷。Spark是在Hadoop的基礎上進一步改進以適用于大數據分析，當數據集全部載入內存且條件滿足的情況下其速度可比Hadoop快100倍之多[8]。但軟件的更新有限，數據的增長無限，劉莉萍等[4]指出，在Spark的并行處理之路上內存及數據是未來兩大研究突破點。

基于上述問題，本文在Spark的列式存儲技術的基礎上進行不斷壓縮剪枝，接近斷層式地減少數據量加快并行處理速度，通過實驗驗證該算法適用于分析各種結構化數據集。

1 相關研究

Apriori最初由Agrawal等[9]提出，后續學者為不斷提高運行速度對其進行了無數次改進。Han等[10]提出較具代表性的基于FP-tree的FP-growth算法，該算法從減少數據庫遍歷次數降低I/O消耗的角度考慮，由各個元素組成節點，只需遍歷一次數據庫，無候選頻繁項集產生，但由于需在內存中創建FP-tree拓撲結構消耗大量內存且只適用于分析單維類型的大數據。文獻[11]最初提出的Eclat算法是從減少數據量的角度分析，該算法通過顛覆數據存放常態減少重復元素，以每行中事務項的列元素轉為行標，而該列元素所出現的事務項轉為列標從而減少元素的重復次數以便于支持度計數，但該算法的運行效率與數據的特征息息相關，其元素個數越少事務項越多效率越高，在維數越多屬性值越多的多維數據中效率趨近于原始Apriori算法的效率。Yang等[12]提出通過抽取海量數據中的部分樣本減少數據執行量的抽樣加權向量矩陣法來對Apriori算法進行優化，該改進算法雖通過抽樣減少了數據量，但可能丟失一些特殊點規則。

近幾年并行處理興起，Hadoop的MapReduce框架僅通過Map函數和Reduce函數即可分布執行Apriori，數據量越大節點加入越多執行效率越高，Hadoop的MapReduce框架處理的簡單性既是優點又是缺點，只需執行Map算子和Reduce算子卻不能滿足現如今數據處理的復雜性以及人機交互的高要求。因此，Spark應運而生，內存模型、快速的迭代處理優勢、更支持交互查詢等諸多優點使其迅速崛起。黃劍等[13]在2017年提出基于Hadoop平臺的改進算法，該改進算法減少了候選集的產生，以布爾矩陣的模式壓縮數據集進行并行處理，從而多方面加快數據的處理速度，但該算法并未表明可以處理多維多屬性的數據，且有一定量的候選頻繁項集產生，存在一定的約束性。閆夢潔等[14]在2017年提出了基于Spark的Apriori優化算法IABS，實驗表明在同等條件下Spark執行Apriori比Hadoop的效率更高，且其采用YAFIM將候選頻繁項集存進哈希樹加速候選頻繁項集的查詢，讓算法的效率得到進一步的提高。但IABS算法在第一階段產生的候選頻繁項集及查詢自連接操作的復雜性一定程度上約束了算法的效率，同時該算法在處理數據的維度屬性的一般性及特殊性上并未做相應說明。由于篇幅有限，本文不再贅述，詳細研究見參考文獻[15-19]。

隨著數據量劇增、I/O消耗及有限內存的約束，算法的運行代價與日俱增，減少其數據量與降低內存耗費是未來丞待解決的兩大難題。本文依托Spark計算框架，從處理多維多屬性數據集的角度，消除候選頻繁項集，最大限度減低算法自連接時間提升Apriori算法的執行效率，提出IApriori算法(improved Apriori algorithm)。

2 構建關聯規則算法優化模型

2.1 算法介紹

Apriori算法分為剪枝和連枝兩個步驟。首先從候選集Ci中統計支持度，根據最小支持度SupMin剪去不合規格的元素e或連枝后的事務集t得到頻繁項集Li，再從頻繁項集Li∞Li連枝得到新的候選集Ci+1，如此循環迭代直到候選集為?，由此得到所有的規則。

設數據庫D={t1，t2，…，tm|m>0且m∈N}，每項事務t={e1，e2，…，en|n>0且n∈N}，e為事務項里包含的元素。

2.2 構建Spark計算框架

Hadoop雖提供同樣的分布式處理模式，但其只支持Map和Reduce兩個算子，限制了復雜場景的數據分析能力。Spark計算框架作為Hadoop計算框架的繼任[8]，提供了更為豐富的API，且其能將中間結果寫入內存的特性減少了數據的I/O，加速數據的分布處理。本文中Spark計算框架的搭建相對復雜，第一階段以R在RStudio平臺上分別在master節點和slave節點中安裝JDK，配置Hadoop及其環境變量，然后配置YARN、HDFS、HBase、Hive等，及其他組件和依賴包，配置完成后啟動Hadoop集群；第二階段配置Spark、配置環境變量及相關依賴包；第三階段采用Java運行改進的關聯規則代碼，Spark讀取HBase形成RDD，存入Hive。

本文所依托的Spark計算框架采用了主從節點結構的計算模型，如圖1所示。主節點master對從節點slave進行任務調度分布，slave節點在執行完job后將結果再返回master進行匯總，模型同時采用R結合Java對環境進行配置和算法執行。

圖1 Spark計算模型

2.3 字典表壓縮存儲多維多屬性并行方案

以往的Apriori優化基本以清洗轉化后的單維度布爾值為研究數據，而一般情況下，海量數據分為結構化數據與非結構化數據，且結構化數據不僅多維更兼多屬性。在數據預處理轉換為布爾矩陣時不僅前期需耗費大量的時間，且清洗之后的每個屬性值會根據占比消耗大部分的空間用于存儲“0”值。

假設有100條事務，每條事務有5個維度，每個維度有3個屬性值，原本的存儲空間為500(100×5)，而轉換為布爾矩陣之后的空間為1 500(100×(5×3))，則存儲空間的耗費量為原先的3倍，屬性值的個數x與空間耗費率為原本存儲空間η的x倍，即xη。

2.3.1基于HBase的行轉列式存儲

1) 常規行存儲模式。常規行存儲模式如圖2所示。行存儲的遍歷思想如下：從事務項的第一行自左到右遍歷至第一行結束，再從第二行以之前的模式遍歷，以此類推直至遍歷完所有數據。按照上述遍歷思想可得到如下一般形式：

圖2 行存儲模式

e11,e12,…，e1i;e21,e22,…，e2j;…;em1,em2,…，emk

(1)

式中：m表示有m行；i、j、k表示列，i、j、k的取值可等或不等。

結合圖2，其步驟可以描述如下：

第一步訪問第一行，可獲取信息(e11,e12,…，e1i)。

第二步訪問第二行，可獲取信息(e21,e22,…，e2j)。

以此類推，第m步訪問第m行，可獲取信息(em1,em2,…，emk)。

2) 行轉列式存儲模式。Spark是在Hadoop計算框架的基礎上進行了擴展，行轉列式存儲模式如圖3所示?；贖Base的行轉列式存儲的遍歷思想如下：從事務項的第一列自上而下遍歷至第一列結束，再從第二列以之前的模式遍歷，以此類推直至遍歷完所有數據。按照上述遍歷思想可得到如下一般形式：

圖3 HBase列存儲模式

e11,e21,…，em1;e12,e22,…,em2;…;e1i,e2j,…,emk

(2)

式中：m表示有m行，n表示最長的列數；i、j、k表示列，i、j、k的取值可等或不等。

第一步訪問第一列，可獲取信息(e11,e21,…，em1)。

第二步訪問第二列，可獲取信息(e12,e22,…，em2)。

以此類推，第m步訪問第n列，可獲取信息(e1i,e2j,…，emk)。

2.3.2字典表數據壓縮

首先，統計每一行的支持度σ，當支持度σ≤SupMin時，進行第一輪的剪枝，得到頻繁一項集。為便于理解，數據表中的元素e代入具體實例進行演示(限于篇幅，假設實例數據已進行過第一輪剪枝)。將表中對應的屬性值按ID及列的方式存儲為字典表，將屬性值轉換為占內存較少的整型數值(或字符)，如圖4所示。

圖4 字典表數據壓縮

在該步驟中，根據元素的n個維度構建n個字典表，字典表由ID號及維度屬性值構成，不同的屬性值對應該表中唯一的ID號。如該實例中薪酬級別維度字典表中“H2”屬性值對應的字典表ID號為“1”，平均成績維度字典表中“良”屬性值對應的字典表ID為“2”。在構建完字典表之后，根據維度字典表屬性值對應的ID號將數據集替換壓縮為整型數值表。該方法能在有效壓縮數據集的同時，便于為下一步的“與”操作鋪墊。

2.3.3基于字典表壓縮的連枝剪枝設計

將2.3.2節的頻繁一項集進行字典表對應壓縮后，執行行轉列式存儲，將原存儲的行事務項t轉為列，而元素維度轉為行，如圖5所示。同時統計每個維度字典表中各個屬性值的計數，為計算置信度ξ做數據準備。列式存儲在操作時只有涉及到計算的列會被讀取，減少I/O消耗加速算法執行數據分析。

（1）色彩管理系統（CMS）與數碼打樣色彩管理是CTP 系統中較為關鍵的技術，也是用于地圖印刷質量控制的核心。它將創建了顏色的色彩空間與要輸出該色的色彩空間進行比較，使要處理的地圖文件在流程中的各個輸出端（如屏幕顯示、打樣、印刷）上顯示的顏色盡可能保持一致。因此就要在數據輸入、處理、輸出時進行RGB 模式到CMYK 模式的轉換，由可校色的高質量顯示器近似模擬印刷效果，打樣輸出采用國際通用的ICC 標準，配備專業數碼打樣軟件輸出數碼樣張，經過色彩管理后的數碼打樣，能夠完全模擬印刷機的色彩曲線，輸出與印刷品感官色彩完全一樣的數碼樣張，提供客戶做印前檢查，印前可即時進行修改，且色彩穩定。

圖5 基于字典表壓縮的連枝設計

該步驟從第一列開始，逐列進行讀取，對每列的每個字典表ID值從“1”到“n”進行查詢，并逐一轉換為布爾值。如第一次查詢到第一列存在字典表ID 數值為“1”，則將其替換為布爾值“1”，其他值替換為布爾值“0”，第二列執行同樣操作，之后第一列與第二列執行“與”操作，將結果計算得出頻繁項集、支持度σ及置信度ξ，再替換回原來的值，列與列依次讀取并執行“與”操作直至存在值為“1”的最后一列；第二次查詢第一列字典表ID數值為“2”，則將“2”替換為布爾值“1”，其他值替換為布爾值“0”，第二列執行同樣操作，之后第一列與第二列執行“與”操作，將結果計算得出頻繁項集、支持度σ及置信度ξ，再替換回原來的值，涉及操作的列與列依次讀取并執行 “與”操作直至存在值為“2”的最后一列；依次操作，直到替換完字典表最大ID值n，完成所有維度屬性值的“與”操作。該步驟的遍歷操作順序如圖5所示，詳細的實例替換操作如圖6所示。

圖6 字典表壓縮的剪枝設計

本文取實例中第二次查詢替換維度屬性值“2”為例，如圖6所示，將學號“01”列中找到所有字典表ID數值為“2”的單元，并將其轉換為布爾值“1”，其他維度屬性值替換為布爾值“0”。根據該思想，本例中學號“01”列的原值為(2,1,2)，替換之后值為(1,0,1)，而實例中學號“02”列原值為(3,3,3)(見圖5中的實例列表)，對比該列無可替換值，無“與”操作價值，因而可跳過該列執行下一列，學號“03”列的原值為(2,2,2)，替換之后值為(1,1,1)，可與“01”列執行“與”操作，即(1,0,1)&(1,1,1)=(1,0,1)，計數器加1；計算支持度σ=1/5=0.2(第一次“與”操作計數，此時計數器為1，總列數為5)；假設最小支持度、置信度為SupMin=ConfMin=0.2，符合最小支持度， 則頻繁項集Lφ頻繁項數φ等于“與”操作結果中所有布爾值為“1”的和，即φ=1+0+1=2；“與”結果布爾值為“1”對應元素下標為關聯規則元素，即頻繁二項集的L2={[e1]2，[e3]2}，其中：規則([e1]2→[e3]2)置信度ξ=1/3=0.33(第一次“與”操作計數，此時計數器為1，在每個維度字典表中各個屬性值的計數中e1列中屬性值字典表ID值為“2”的計數值為3)，置信度ξ=0.33>ConfMin，符合要求；頻繁二項集L2={[e1]2，[e3]2}對應第一行及第三行的維度名，{[平均成績]2，[薪酬級別]2 },方括號后的“2”為替換維度屬性值“2”，對應字典表ID值為“2”的屬性值從而得到頻繁項集L2={平均成績.良，薪酬級別.H2}；將“與”操作完的列“01”及“02”還原為原來值。

取學號“04”列的原值為(2,1,2)，替換之后值為(1,0,1)，和“01&03”的“與”結果值(1,0,1)做再次“與”操作，即(1,0,1)&(1,0,1)=(1,0,1)，計數器加1；計算支持度σ=2/5=0.4(第二次“與”操作計數，此時計數器為2，總列數為5)，支持度σ=0.4>SupMin，符合要求，則頻繁項集Lφ頻繁項數φ等于“與”操作結果中所有布爾值為“1”的和，即φ=1+0+1=2；“與”結果布爾值為“1”對應元素下標為關聯規則元素，即頻繁二項集的L2={[e1]2，[e3]2}，其中：規則([e1]2→[e3]2)置信度ξ=2/3=0.66(第二次“與”操作計數，此時計數器為2，e1列中屬性值字典表ID值為“2”的計數值為3)，置信度ξ=0.66>ConfMin，符合要求；頻繁二項集L2={[e1]2，[e3]2}對應第一行及第三行的屬性名，{[平均成績]2，[薪酬級別]2 },其中方括號后的“2”為替換維度屬性值“2”，對應字典表ID值為“2”的屬性值從而得到頻繁二項集L2={平均成績.良，薪酬級別.H2}；將“與”操作完的“04”列還原為原來值。

基于以上思想，假設σ≥SupMin且ξ≥ConfMin，則存儲計算結果的“行”下標，且“行”下標所記的元素及e及循環次數i可以得到頻繁φ項集Lφ，而無須產生候選集。因此，Lφ={[ek]i,[ek+1]i,…,[en]i}，其中i為外層循環計數器，即替換值，根據元素下標及字典表得到相應的頻繁項集。

定義3en為存放“與”操作結果的數組，頻繁φ項集Lφ，其中φ的值等于“與”操作后“1”的和，從而得到一般形式下頻繁項集Lφ的項集數φ的計算式為：

(3)

定義4Counter為“與”次數計時器，從而得到一般形式下頻繁φ項集Lφ的支持度σ和規則(ei→ej)的置信度ξ計算公式分別如下：

(4)

(5)

式中：Counter(ei→ej)為規則(ei→ej)的“與”計數；Count(ei)為元素屬性值ei在數據庫中的統計數。

2.3.4改進算法IApriori實現

Spark的優勢是能在內存保存job的中間結果，降低I/O提高執行效率。該算法利用HBase列式存儲的特點，通過調用f算子轉存、g算子運算及h算子迭代生成RDD，算法實現步驟見算法1。

算法1IApriori算法

輸入：數據庫D。

輸入：最小支持度SupMin，最小置信度ConfMin。

1. for 1 tom

//m為事務項數

//計算每個維度屬性值ej的統計數

3. if(σj≤SupMin) deleteσi;//在列維度中，先進行每

//一列的支持度σ統計，如σ≤SupMin則先進行第一輪的剪枝

4. end for

5.f(ti，ej)=g(ej，ti);//構造函數，對事務項ti、事務項維

//度數ei進行行轉列式預處理

6. 抽取字典表T;

7. for 1 ton

//遍歷元素值“1”至“n”

8. fore1toen

//遍歷事務項的屬性值

9. if(ej=j)ej=1;

//轉換為布爾值

10. elseej=0;

11.φ=h(ei&e(i-1));

//構造函數，“與”操作后計算“1”的和

12. if(ti=1)a[k]=ti;

//構造數列a存儲“位”為1的行標

13. if(((i/n)>SupMin)&&((i/σj)>ConfMin))

14.σ=i/n;ξ=i/σj;Lφ={a[k]};

//σ為支持度，ξ為置信度

15.Lφ={a[k]};

//與字典表匹配

16.輸出Lφ頻繁項集;

17.輸出σ和ξ;

//輸出支持度及置信度

18. end for

19. end for

3 算法性能評估

3.1 分布式計算環境配置和部署

本實驗在青軟大數據平臺下的虛擬機中完成，本實驗采用1個master、4個slave共5個節點組建集群。每個節點采用CentOS 7版本64位操作系統，內存(RAM)3.88 GB可用，主頻2.60 GHz，軟件環境采用Hadoop2.6+Spark2.1+JDK1.8+SparkR、R、Java。首先以R語言部署安裝JDK，Hadoop及其環境變量并依次配置YARN、HDFS、HBase、Hive等及組件和相關依賴包，配置完成后啟動Hadoop集群。然后在Hadoop集群中以不同數據量和不同節點執行Apriori算法。最后再以R語言部署安裝Spark、配置環境變量及相關依賴包，在該環境中執行Apriori算法和列陣壓縮改進的IApriori算法。

實驗數據集取近十年若干個高校的學生信息約15萬條，為驗證算法的性能拷貝模擬數據至200萬條，數據量大小為146 MB，數據共有79列。

3.2 實驗結果分析

本實驗通過彈性分析算法在不同數據量及節點數的執行指標來評價改進算法IApriori的性能。通過對數據進行隨機取樣，在數據集不同，最小支持度SupMin=0.05的情況下的時間運行對比如圖7所示。IApriori算法在相同的數據集不同節點數上的運行時間對比如圖8所示。

圖7 不同算法運行時間對比

圖8 不同算法在不同節點個數時的執行時間

由圖7可見，在Hadoop計算框架中執行Apriori算法的效率要明顯低于基于內存運算的Spark框架。同時可以看出改進算法IApriori在數據量較少時執行效率較低，因為改進的算法采用的存儲方式需執行附加的步驟。但隨著數據量不斷加大，其執行效率高于同在Spark執行的Apriori傳統算法(SApriori)，而隨著節點數不斷增加，改進算法IApriori的執行效率顯著提高。

在不同節點數的彈性的對比分析中(如圖8所示)，在節點數分別為2、3、4和5時，Hadoop框架由于數據I/O消耗時間及Apriori算法本身產生過多的候選頻繁項集而拉低了算法的執行效率，在同一節點數執行相同數據集總比Spark計算框架耗時；而改進后的IApriori算法的效率優于原來的Apriori算法，但由于附加了行轉列式存儲時間及對數據字典表的加工時間而拉低了整體的效率，而未加改進的Apriori算法在執行數據前需增加大量的情況，則認為其清洗轉換工作并未包含在算法執行時間內。因而，改進算法IApriori與原算法Apriori在數據集的執行效率表現中優勢差距不非常明顯。

4 結 語

針對Apriori算法存在產生大量候選頻繁項集和多次遍歷數據庫增加I/O消耗的缺陷，本文在基于Spark多節點分布式執行算法的基礎之上提出了一種改進的算法。本文算法在Spark計算框架上采用HBase列式存儲，構建數據字典表，在計算過程中壓縮原本龐大的數據量，同時簡化連枝剪枝只需進行“與”操作，結合Spark分布式計算的特點使改進算法的執行效率在數據量不斷增大的模型下得到有效提高。通過實驗對比Hadoop計算框架下執行Apriori算法、Spark計算框架下執行Apriori算法及本文改進的算法，結果表明本文算法能分析多維多屬性值的數據集，一定程度上節省了數據處理前清洗及轉化工作，“與”操作后消除候選頻繁項集的產生約省了內存計算時間及空間，在Spark基于內存的分布式處理框架下改進算法IApriori的執行效率得到有效提高。