Hadoop 平臺下的并行Web 日志挖掘算法

周詩慧，殷 建

(山東大學(威海)機電與信息工程學院，山東 威海 264209)

1 概述

隨著Internet的發展，Web已成為全球最大的數據倉庫。Web 所蘊含的數據不僅是網頁上的文字和圖片，還包括網絡的拓撲信息、網頁的鏈接結構以及用戶對網站的訪問和操作記錄。然而，如何從Web 的海量數據中挖掘出蘊含其中的信息，一直是國內外學者研究的熱點。將傳統的數據挖掘技術應用于Web 領域的技術即Web 挖掘[1]。Web 挖掘按應用可以分為3 類：Web 內容挖掘，Web 結構挖掘，Web使用挖掘[2]。Web 內容挖掘是從Web 的網頁內容中提取知識；Web 結構挖掘從Web 的組織結構和鏈接關系中挖掘出信息；Web 使用挖掘是利用Web 日志發現用戶的興趣模式，因此，Web 使用挖掘也稱作Web 日志挖掘。在通常情況下，相對于挖掘內容和結構，挖掘用戶的使用更有意義。

目前對Web 數據挖掘的研究主要集中在對挖掘算法的改進上，這雖然能夠提高系統的有效性，但卻缺乏對系統計算能力的改善[3]。當面對海量的Web 數據時，基于單一節點的Web 挖掘算法將面臨時間和空間復雜性上的瓶頸。想要解決這一問題就需要將并行計算應用到Web 挖掘中，但并行處理系統是由多個節點組成的，這就會存在節點失效、負載不平衡等問題，而且傳統的并行處理模型在易編程和易擴展方面表現欠佳。

Hadoop 是Apache 下的一個開源框架，是一個更容易開發和并行處理大規模數據的分布式計算平臺。同時并行計算存在的問題如負載平衡、工作調度、分布式存儲、容錯處理、網絡通信等也都由Hadoop 負責解決。因此，本文對Hadoop 進行介紹，包括HDFS 和MapReduce 的組成結構和工作原理，并設計一種基于Hadoop 的Web 日志并行挖掘算法。

2 Hadoop 相關技術

Hadoop 是一個集成了分布式文件系統HDFS 和大規模并行計算模型MapReduce 的開源框架[4]。Hadoop 具有如下優勢：(1)可伸縮性，能夠處理petabytes 級數據，并可以無限擴充存儲和計算能力。(2)可靠性，可以維護同一份數據的多份副本并自動對失敗的節點重新分布處理。(3)高效性，Hadoop 能并行地處理數據。同時，Hadoop 也是低成本的，因為它對硬件的要求不高，所以可以運行在普通的微機集群上。

2.1 Hadoop 的分布式文件系統

Hadoop 的分布式文件系統(Hadoop Distributed File System,HDFS)由 1 個 NameNode(管理節點)和 N 個DataNode 數據節點(數據節點)組成，這2類節點采用Master/Slave(管理者/工作者)模式運行[5]。其中，NameNode 充當Master 節點，DataNode 充當Slave 節點。其底層實現原理就是當有輸入文件提交到Master 節點后，Master 將輸入文件切割成多個Block 并為每個Block 拷貝數份副本，拷貝的副本數目是可配置的，然后將這些Block 分散地存儲在不同的Slave 節點上，從而實現容錯處理。NameNode 是整個文件管理系統的核心，負責維護文件系統的NameSpace(名字空間)，NameSpace 上記錄著輸入文件的分割情況、每個Block 的存儲位置以及每個Block 所在節點的狀態信息。DataNode 是整個文件系統的實際工作者，它們負責存儲Block，并定時向NameNode 匯報存儲塊的狀態信息[6]。

2.2 MapReduce 并行計算模型

MapReduce 編程模式解決了傳統并行計算在易編程性上的瓶頸，使得程序員更容易開發分布式并行計算程序。程序員只需要編寫2 個函數：Map 函數和Reduce 函數，這2 個函數的輸入和輸出都是鍵值對集合。Map 對輸入的＜key,value＞集合進行處理，生成中間結果＜key',value'＞集合。MapReduce 底層自動將具有相同key'值的鍵值對中相應的value'進行合并，生成＜key',List[value']＞集合，并將其作為Reduce 函數的輸入。Reduce 函數再進一步處理生成新的＜key'',value''＞集合作為輸出文件。

Hadoop 下的MapReduce 編程模式同HDFS 一樣采用Master/Slave 架構，由主控節點(JobTracker)和計算節點(TaskTracker)2 種節點組成。JobTracker 節點負責任務的調度和對TaskTracker 節點的管理，TaskTracker 節點負責執行Map 和Reduce 任務。TaskTracker 每隔一段時間就會向JobTracker 發送信號來證明其處于正常工作的狀態，JobTracker 就會將該TaskTracker 放入空閑列表。

3 基于Hadoop 的Web 日志挖掘算法

3.1 系統架構

在一個Hadoop 集群中，HDFS 的管理節點和Map Reduce 的主控節點可以使用同一臺機器，也可以分別使用不同的機器。同樣數據節點和計算節點也可以共用同一臺機器。本文實現的基于Hadoop 的Web 日志挖掘系統架構如圖1 所示。其中，Master 節點負責NameNode 和JobTracker節點的工作；Slave 節點既要用來存儲數據塊還要執行Master 節點所分配的映射和化簡任務。

圖1 基于Hadoop 的Web 日志挖掘系統架構

日志收集服務器每天定時將待處理的日志導入Master節點。Master 節點將原始的日志文件作為輸入文件切分成M 份數據塊，分散存儲在不同的Slave 節點上并更新NameSpace。初始化完成后，Master 節點根據MapReduce底層實現的調度算法為空閑列表中的每個Slave 節點分配Map 或Reduce 任務。Slave 節點接收到任務后，首先將運行程序所需的文件和任務文件從NameNode 復制到本地文件系統。然后創建實例來運行任務。Map 任務生成的中間結果保存在本地Slave 節點上。MapReduce 底層將Map 生成的中間結果合并后，再分發到各個被分配執行Reduce 任務的Slave 節點上作為輸入文件。最后Master 節點將各個Reduce 任務的結果進行合并作為最終輸出文件發送到結果展示服務器。

3.2 數據預處理

所有服務器響應的請求都會被記錄在Web 日志中，同一時間內服務器可能為成百上千個用戶會話服務，同一用戶會話的記錄是不連續的。因此，必須對Web 日志進行預處理，將分散的、雜亂的日志記錄整理成用戶會話文件。數據預處理技術可以改進數據的質量，從而有助于提高其后的挖掘過程的精度和性能[7]。Web 日志預處理主要包括以下幾步：數據清理，用戶識別，會話識別，路徑補充和事務識別[8]。設L={l1,l2,…,ln}為用戶訪問集合，L 中的每個元素都代表一條日志記錄。令l∈L，用l.uid 表示用戶標識，l.url 表示用戶所訪問的頁面地址，l.time 表示訪問時間。設D={t1,t2,…,tm}為用戶事務集，任意事務t 即表示一個用戶會話。令t=＜uidt,urlt＞，t∈D。其中，urlt代表用戶ID 為uidt的用戶一次會話下瀏覽的頁面序列，令：

3.3 基于Hadoop 的FP-growth 算法

目前Web 日志挖掘算法主要有基于關聯規則的Apriori算法、最大向前訪問路徑(Max Forward Path,MFP)算法、基于聚類分析的k-means 算法及相應的改進算法等。其中，基于逐層搜索迭代方法的改進Apriori 算法被廣泛應用于Web 日志挖掘系統中。然而Apriori 算法通過LK-1項集生成候選集Ck的思想導致當數據量巨大的時候可能產生海量的候選項集，另外可能重復地掃描數據庫以匹配檢查候選集合。這2 種情況會影響Apriori 算法的執行效率和性能，帶來巨大的網絡傳輸開銷。采用分治策略的頻繁模式增長算法FP-growth 能夠做到不依靠產生候選項集的方式進行關聯規則挖掘[9]，從而解決了Apriori 算法的不足。FP-growth算法是近十年來數據挖掘方向最熱門的研究主題之一，在序列模式挖掘、結構模式挖掘、關聯挖掘等方面都起著重要作用[10]。

使用關聯規則的挖掘算法一般分為2 步：

(1)發現所有的頻繁項集：任意頻繁項集A 的支持度計數都要大于等于預定義的最小支持計數(這里采用的是絕對支持度，代表在事務集T 中包含項集A 的事務t 出現的次數。相對支持度則表示A 在事務集中出現的概率)。項集A的支持度計數表示為：Support _ count (A)。

(2)由頻繁項集產生強關聯規則：規則A ? B必須滿足事先定義好的最小支持計數 Support (A ?B)和最小置信度Confidence (A ?B)，其中：

本文提出基于Hadoop 的Web 日志挖掘算法——并行FP-growth 算法，將以上2 步交由Master 和Slave 節點上共同完成。算法的具體描如下：

(1)計算出全局頻繁1-項集，這一步可以由一對Map/Reduce 完成。

1)將事務集D(即預處理后得到的形如＜uidt,urlt＞的鍵值對集合)分割成M 份分發到不同的Slave 節點上。由Map函數識別出本地事務集中的每一個url，這里的url 就是挖掘算法中的項。將每一個url 作為輸出鍵值對的key，對應的value 設為1。

2)Reduce 函數將具有相同key 值的value 值進行累加得到每個url 出現的次數，然后刪除那些出現次數小于最小支持計數的url。合并所有Reduce 的輸出文件即得到全局頻繁1-項集的集合F_list。將F_list 按支持計數的降序排列得到L_list。將L_list 分為r 組：subL_list1,subL_list2,…,subL_listr。

(2)根據L_list 的分組情況對事務集重新分組。將本地事務集相應地劃分為subD1,subD2,…,subDr 并發送給r 個Reduce 任務。然后對各個子事務集進行并行FP-growth 挖掘。這步也由一對Map/Reduce 完成。

1)由Map 函數來完成事務集的分組操作。該Map 函數掃描本地事務集中的每個事務t，如果lkt.url∈subL_listi,1≤i≤r，則將事務t 添加到subDi 中。Map 函數偽碼如下：

2)Reduce 函數收到子事務集subDi 后，創建subDi 的頻繁模式樹并對其進行挖掘。該 Reduce 中調用的方法insert_tree(創建樹)和FP-growth(挖掘樹)就是傳統的創建和挖掘頻繁模式樹的算法。該Reduce 中調用的挖掘樹算法跟傳統算法相比，增加了一個參數subL_listi，這是因為傳統的FP-growth 算法是掃描全局的L_list，而本文只需要掃描局部subL_listi。Reduce 函數的偽碼如下：

3)根據生成的頻繁模式集和置信度公式推出關聯規則。

基于Hadoop 的并行FP-growth 算法可以有效地將一棵FP 樹分成多個小FP 樹，在多臺Slave 節點上并行計算，然后對各個Slave 節點上的挖掘結果取并集，得到目標的頻繁模式全集，最終根據頻繁項集的支持度計數和置信度推出關聯規則。

4 實驗結果與分析

為驗證本文算法的性能，本文實驗使用加速比作為評估指標。加速比是指同一任務在單處理器系統和并行處理器系統中運行消耗時間的比率，常用來衡量并行處理的性能和效果。實驗測試了在不同數目節點、不同大小數據集(分別為1 MB、1 GB 和2 GB)下本文算法的加速比，如圖2所示。

圖2 加速比測試結果

可以看出，當數據量較小時，加速比小于1，說明并行處理的時間反而大于單機的執行時間，這是因為基于Hadoop 的算法需要傳輸中間文件且Hadoop 框架的啟動、調度都需要一定的執行時間，而數據量較小時執行算法本身所需的時間并不長，所以當數據量較小時Hadoop 平臺所消耗的時間比重偏大，從而導致了并行處理時間大于單機執行時間。然而隨著數據量的增大，并行算法在執行效率上就體現出了優勢。此外，隨著節點數目的增加，算法的執行效率也得到了相應的提高，不過當節點數目大到一定程度時，加速比增長率的提高并不多，因此，可根據數據集的大小選擇合適的節點數目。

該實驗證明了并行FP-growth 算法優于串行FP-growth算法，并且隨著數據量的增大，并行FP-growth 算法的優勢也越來越明顯。

5 結束語

本文在Hadoop 集群平臺下設計并實現了Web 日志挖掘的FP-growth 算法。實驗結果證明，該算法適用于大規模數據的挖掘應用。Web 日志挖掘具有非常廣泛的應用領域，本文的并行Fp-growth 算法已經得到Web 日志中頻繁頁面序列。根據這一結果，下一步研究將對網站的訪客進行個性化推送，當訪客瀏覽了一組頻繁頁面序列中的大部分頁面時，可以向其推送該組頻繁模式的剩余頁面。同時，也可以得到頁面之間的強規則，進而分析網站模塊之間的關聯，對改善網站的鏈接結構提出相關意見。

[1]費洪曉,覃思明,李文興,等. 基于訪問興趣的Web 用戶聚類方法[J]. 計算機系統應用,2010,19(4): 62-65.

[2]王 凱,渠 芳,王 輝. 利用Web 挖掘技術實現個性化推送服務[J]. 情報雜志,2006,25(11): 86-88.

[3]程 苗,陳華平. 基于Hadoop 的Web 日志挖掘[J]. 計算機工程,2011,37(11): 37-39.

[4]王振宇,郭 力. 基于Hadoop 的搜索引擎用戶行為分析[J].計算機工程與科學,2011,33(4): 115-120.

[5]趙衛中,馬慧芳,傅燕翔,等. 基于云計算平臺Hadoop 的并行K-means 聚類算法設計研究[J]. 計算機科學,2011,38(10): 166-168,176.

[6]劉永增,張曉景,李先毅. 基于Hadoop/Hive 的Web 日志分析系統的設計[J]. 廣西大學學報: 自然科學版,2011,36(Z1): 37-39.

[7]Han Jiawei,Kamber M. Data Mining Concepts and Techniques[M]. [S. l.]: MorganKaufmann Publishers,2002.

[8]趙立江,何欽銘. 一種個性化Web 推薦系統的設計與實現[J]. 武漢理工大學學報,2004,28(5): 681-684.

[9]談克林,孫志揮. 一種FP 樹的并行挖掘算法[J]. 計算機工程與應用,2006,42(13): 155-157.

[10] Chen Min,Gao Xuedong,Li Huifei. An Efficient Parallel FP-growth Algorithm[C]//Proc. of Conference on Cyberenabled Distributed Computing and Knowledge Discovery.Zhangjiajie,China: [s. n.],2009.