基于Hadoop的頻繁項集挖掘算法在圖書借閱數(shù)據(jù)中的應(yīng)用

彭增焰++吳東++張立敏

摘 要針對挖掘圖書借閱記錄中蘊含價值的問題，以圖書分類號作為圖書特征，給出了結(jié)合Apriori的頻繁項集挖掘算法。針對海量圖書借閱記錄難以處理的問題，將頻繁項集挖掘算法融入Hadoop大數(shù)據(jù)平臺，設(shè)計了基于Hadoop的頻繁項集挖掘算法，有效解決了數(shù)據(jù)存儲和并行處理的問題。實驗結(jié)果表明，部分圖書之間的關(guān)聯(lián)程度高。

【關(guān)鍵詞】頻繁項集 圖書 Hadoop Apriori MapReduce

1 引言

隨著數(shù)字化校園不斷發(fā)展，高校圖書館積累了海量的信息，如圖書入庫、讀者信息、圖書借閱信息和圖書書架排列等信息。面對海量圖書數(shù)據(jù)，雖然給圖書館管理工作帶來了一定的挑戰(zhàn)，但其蘊含的大數(shù)據(jù)價值高，若能夠從中有效挖掘圖書間的內(nèi)在關(guān)系，既能提高管理效率，又能方便讀者查閱圖書。

學(xué)者們對挖掘圖書信息蘊含的內(nèi)在關(guān)系進行了大量研究，文獻[1]和文獻[2]主要采用關(guān)聯(lián)規(guī)則的Apriori算法分析讀者借閱的圖書之間的關(guān)聯(lián)度，文獻[3]直接使用SPSS的關(guān)聯(lián)規(guī)則模塊挖掘深圳大學(xué)圖書館一學(xué)年的流通數(shù)據(jù)。

學(xué)者們側(cè)重于挖掘圖書之間的蘊含關(guān)系，但隨著大數(shù)據(jù)時代的到來，現(xiàn)在的數(shù)據(jù)處理方式逐漸不能適應(yīng)圖書借閱記錄劇增的情況，迫切需要尋找一種有效應(yīng)對海量圖書數(shù)據(jù)處理的方法。Hadoop[4]是一種大數(shù)據(jù)離線處理技術(shù)，非常適合對海量的圖書數(shù)據(jù)進行處理。本文先介紹基于Apriori的頻繁項集挖掘算法，以及Hadoop大數(shù)據(jù)技術(shù)基本原理，通過結(jié)合兩者設(shè)計出基于Hadoop的頻繁項集挖掘算法。

2 頻繁項集挖掘算法

頻繁項集挖掘，需收集并清洗原始數(shù)據(jù)集，該數(shù)據(jù)集稱為事務(wù)數(shù)據(jù)；針對事務(wù)數(shù)據(jù)，統(tǒng)計各項集之間出現(xiàn)的次數(shù)，一般可取出現(xiàn)頻率靠前的項集作為頻繁項集。為提高頻繁項集的求解效率，常采用Apriori算法進行優(yōu)化。結(jié)合Apriori的頻繁項集挖掘算法包括事務(wù)數(shù)據(jù)清洗、1項集求解、k項集迭代求解的過程。

2.1 事務(wù)數(shù)據(jù)清洗

過濾不符合格式的數(shù)據(jù)，根據(jù)實際場景生成新的事務(wù)數(shù)據(jù)。

2.2 1項集求解

掃描每條事務(wù)數(shù)據(jù)記錄，分解出每一項，并計數(shù)1，最后統(tǒng)計每一項出現(xiàn)的總次數(shù)，取靠前的項集作為頻繁1-項集。

2.3 k項集的求解

k項集的生成依賴k-1項集，若k-1項集完全自連接，生成的候選k項集組合龐大，且容易生成部分無效k項集，降低算法效率，常采用Apriori算法對候選k項集生成過程進行優(yōu)化。Apriori算法優(yōu)化的基本原理[4]如下：

（1）頻繁項集的任何非空子集都是頻繁的。

（2）非頻繁項集的任何超集都是非頻繁的。

生成k項集階段，包括了連接和剪枝過程，其中兩個k-1項集進行連接的條件是：它們至少有k-2項相同。

3 Hadoop大數(shù)據(jù)技術(shù)

Hadoop是一門已應(yīng)用于實際生產(chǎn)環(huán)境的大數(shù)據(jù)離線處理技術(shù)。Hadoop生態(tài)系統(tǒng)成熟完善，包含數(shù)據(jù)收集、數(shù)據(jù)存儲、數(shù)據(jù)管理與數(shù)據(jù)處理分析等組件。其中數(shù)據(jù)存儲使用分布式文件系統(tǒng)（HDFS）、數(shù)據(jù)處理使用分布式并行計算編程模型（MapReduce）。

3.1 HDFS

HDFS[4]是Hadoop默認的分布式文件系統(tǒng)，包括一個NameNode和多個DataNode。NameNode是負責(zé)元數(shù)據(jù)管理的主節(jié)點，DataNode是數(shù)據(jù)存儲的從節(jié)點。文件在HDFS上存儲時，是以數(shù)據(jù)塊的方式存儲管理的，一個數(shù)據(jù)塊大小為64MB（Hadoop1.0），每個數(shù)據(jù)塊采用保存3個副本的策略，保證了系統(tǒng)的高可靠性。

3.2 MapReduce

MapReduce[4]是Hadoop的并行處理計算模型，包括兩個重要的階段：Map和Reduce階段。MapReduce編程模型如圖1所示。

3.2.1 Map階段

針對每個InputFormat定義的split邏輯數(shù)據(jù)塊，系統(tǒng)會啟動一個map任務(wù)，通過RecordReader將字節(jié)流數(shù)據(jù)轉(zhuǎn)為一條條的記錄，默認記錄為一個鍵值對<當(dāng)前行偏移量，一行內(nèi)容>。每個鍵值對將會被用戶重寫的map函數(shù)處理，該函數(shù)往往是數(shù)據(jù)處理中需重點設(shè)計的地方，經(jīng)過map函數(shù)后會發(fā)射出一個新的鍵值對，待下一階段處理。

3.2.2 Reduce階段

首先遠程獲取map任務(wù)節(jié)點中特定分區(qū)的數(shù)據(jù)，然后對數(shù)據(jù)進行排序，歸并具有相同鍵的鍵值對。針對每個歸并后的鍵值對將會被用戶重寫的reduce函數(shù)處理，該函數(shù)的邏輯關(guān)系也是需要被重點設(shè)計，最后將新的鍵值對輸出到HDFS文件系統(tǒng)上。

map函數(shù)和reduce函數(shù)的設(shè)計是MapReduce并行處理數(shù)據(jù)的重點，但僅僅設(shè)計這兩函數(shù)是不夠的，一般還需要做一些初始化操作，往往通過重寫setup函數(shù)來實現(xiàn)。setup函數(shù)在每個map任務(wù)中只執(zhí)行一次，執(zhí)行后再循環(huán)執(zhí)行map函數(shù)或reduce函數(shù)。

4 基于Hadoop的頻繁項集挖掘算法設(shè)計

Hadoop大數(shù)據(jù)技術(shù)能解決圖書館海量借閱記錄有效被處理的難題，下面詳細闡述借助Hadoop技術(shù)，實現(xiàn)頻繁項集挖掘算法的基本設(shè)計流程。

該算法由兩大部分組成，一是頻繁1項集的求解，二是頻繁k項集的求解。

4.1 頻繁1項集求解

算法具體實現(xiàn)步驟如下：

第1步：按行讀取清洗后的借閱記錄事務(wù)數(shù)據(jù)，由系統(tǒng)生成鍵值對，key為當(dāng)前行偏移量，value為讀者的圖書借閱記錄；

第2步：map函數(shù)中提取出圖書分類號，生成鍵值對<圖書分類號， 1>；

第3步：Combiner函數(shù)匯總當(dāng)前map任務(wù)的鍵值對，生成新鍵值對<圖書分類號， 出現(xiàn)次數(shù)>；

第4步：Reduce函數(shù)中匯總相同圖書分類號的出現(xiàn)次數(shù)，生成<圖書分類號，出現(xiàn)總次數(shù)>的鍵值對，并將其寫入HDFS中。

經(jīng)過以上步驟即可統(tǒng)計出1-項集，一般選取頻率高的項作為頻繁1-項集。

4.2 頻繁k項集求解

本部分以第一部分求解的頻繁1項集為基礎(chǔ)，輸入為圖書借閱記錄事務(wù)數(shù)據(jù)。算法具體實現(xiàn)步驟如下：

第1步：設(shè)定k大小和臨時變量i=2。

第2步：加載頻繁i-1項集。將i-1項集通過分布式緩存文件的方式發(fā)送給每個map任務(wù)，在setup函數(shù)里加載該文件。

第3步：連接剪枝生成候選i-項集。在setup函數(shù)中根據(jù)Apriori優(yōu)化算法對頻繁i-1項集進行連接并剪枝，并將生成的候選i-項集保存于全局變量中。

第4步：map函數(shù)計算候選i-項集的有效性。遍歷候選i-項集，比對當(dāng)前圖書借閱記錄事務(wù)數(shù)據(jù)，如果該事務(wù)數(shù)據(jù)包含候選i-項集，則將<當(dāng)前候選i-項集，1>的鍵值對發(fā)射出去。

第5步：reduce函數(shù)根據(jù)設(shè)定條件生成正式的i-項集。匯總當(dāng)前候選i-項集出現(xiàn)次數(shù)，判斷是否大于設(shè)定的支持度，若是則將<當(dāng)前候選i-項集，出現(xiàn)總次數(shù)>鍵值對寫入HDFS中。

第6步：如果不存在頻繁i-項集，則結(jié)束。

第7步：i=i+1，i是否小于等于k，若是返回第2步執(zhí)行，否則結(jié)束。

5 實驗

圖書分類號采用文獻[5]中設(shè)定的圖書分類方式，在Hadoop平臺上分別針對1級圖書分類號和2級圖書分類號進行頻繁項集挖掘。Hadoop平臺由4臺虛擬機組成，其中1臺為主節(jié)點，3臺為從節(jié)點。實驗的數(shù)據(jù)集來源于本校圖書館2010級至2013級的圖書借閱記錄。

5.1 圖書1級分類號的頻繁項集

圖書1級分類號的頻繁1項集和2項集如表1，表中數(shù)據(jù)是支持度大于100000頻繁1項集和支持度大于10000的頻繁2項集。

從表1中可以得知，本校圖書館對I類圖書需求量最大，在購買圖書時，經(jīng)費可適當(dāng)往該類傾斜；H類與I類圖書、G類與I類圖書支持度較高，說明這兩組中兩個類別的圖書被同一讀者借閱的可能性較大，在圖書分類上架時，可適當(dāng)考慮將這些圖書擺放在相鄰位置，方便讀者借閱。

5.2 圖書2級分類號的頻繁項集

由于T類圖書的1項集支持度較靠前，因此選擇T類圖書的2級圖書分類號進行頻繁2項集挖掘，如表2所示，其中表中列出支持度靠前的5個頻繁2項集。

從表2中可以得知，T類2級分類號的圖書中，TS類與TP類、TN與TP類圖書的支持度都較高，并且TP類圖書跟其他T類圖書支持度相對較高，合理安排TP類圖書的位置有利于提高圖書館的人性化服務(wù)程度和服務(wù)質(zhì)量。

6 總結(jié)

本文介紹了頻繁項集挖掘算法和Hadoop大數(shù)據(jù)技術(shù)，為應(yīng)對海量圖書借閱記錄，借助Hadoop技術(shù)，實現(xiàn)頻繁項集挖掘算法。實驗結(jié)果清晰表明I、H、G、T、J、K、B類別的圖書是比較受讀者歡迎，尤其是I類圖書；從T類圖書的頻繁2項集看出，TP類圖書是T類圖書的核心。圖書關(guān)聯(lián)關(guān)系不僅對圖書管理工作有很大的幫助，還利于提高圖書館的服務(wù)質(zhì)量，也能從一定程度增加讀者的借閱次數(shù)，更能為圖書推薦工作提供支持。

（通訊作者：彭增焰）

參考文獻

[1]茍元琴，王鈞玉.關(guān)聯(lián)規(guī)則在圖書館讀者借閱記錄中的挖掘應(yīng)用[J].科技信息，2009（17）：356-357.

[2]何歡.圖書流通關(guān)聯(lián)規(guī)則分析[J].圖書館雜志，2011（07）：63-68.

[3]侯賀.基于關(guān)聯(lián)規(guī)則的圖書館流通數(shù)據(jù)挖掘——以深圳大學(xué)城圖書館為例[J].圖書館學(xué)刊，2017（02）.

[4]黃宜華.深入理解大數(shù)據(jù)——大數(shù)據(jù)處理與編程實踐[M].機械工業(yè)出版社，2014：13-122.

[5]彭增焰，吳東.基于協(xié)同過濾的高校圖書個性化推薦算法研究[J].嶺南師范學(xué)院學(xué)報，2016，376）：103-108.

作者簡介

彭增焰（1987-），男，廣東省化州市人。碩士學(xué)問。嶺南師范學(xué)院信息工程學(xué)院助教，從事大數(shù)據(jù)技術(shù)研究。

作者單位

嶺南師范學(xué)院信息工程學(xué)院 廣東省湛江市 524048