基于Hadoop的頻繁項集挖掘算法在圖書借閱數據中的應用

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

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

【關鍵詞】頻繁項集 圖書 Hadoop Apriori MapReduce

1 引言

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

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

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

2 頻繁項集挖掘算法

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

2.1 事務數據清洗

過濾不符合格式的數據，根據實際場景生成新的事務數據。

2.2 1項集求解

掃描每條事務數據記錄，分解出每一項，并計數1，最后統計每一項出現的總次數，取靠前的項集作為頻繁1-項集。

2.3 k項集的求解

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

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

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

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

3 Hadoop大數據技術

Hadoop是一門已應用于實際生產環境的大數據離線處理技術。Hadoop生態系統成熟完善，包含數據收集、數據存儲、數據管理與數據處理分析等組件。其中數據存儲使用分布式文件系統（HDFS）、數據處理使用分布式并行計算編程模型（MapReduce）。

3.1 HDFS

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

3.2 MapReduce

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

3.2.1 Map階段

針對每個InputFormat定義的split邏輯數據塊，系統會啟動一個map任務，通過RecordReader將字節流數據轉為一條條的記錄，默認記錄為一個鍵值對<當前行偏移量，一行內容>。每個鍵值對將會被用戶重寫的map函數處理，該函數往往是數據處理中需重點設計的地方，經過map函數后會發射出一個新的鍵值對，待下一階段處理。

3.2.2 Reduce階段

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

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

4 基于Hadoop的頻繁項集挖掘算法設計

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

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

4.1 頻繁1項集求解

算法具體實現步驟如下：

第1步：按行讀取清洗后的借閱記錄事務數據，由系統生成鍵值對，key為當前行偏移量，value為讀者的圖書借閱記錄；

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

第3步：Combiner函數匯總當前map任務的鍵值對，生成新鍵值對<圖書分類號， 出現次數>；

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

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

4.2 頻繁k項集求解

本部分以第一部分求解的頻繁1項集為基礎，輸入為圖書借閱記錄事務數據。算法具體實現步驟如下：

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

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

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

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

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

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

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

5 實驗

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

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

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

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

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

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

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

6 總結

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

（通訊作者：彭增焰）

參考文獻

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

[2]何歡.圖書流通關聯規則分析[J].圖書館雜志，2011（07）：63-68.

[3]侯賀.基于關聯規則的圖書館流通數據挖掘——以深圳大學城圖書館為例[J].圖書館學刊，2017（02）.

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

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

作者簡介

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

作者單位

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