周詩慧，殷 建

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

1 概述

隨著Internet的發(fā)展，Web已成為全球最大的數(shù)據(jù)倉庫。Web 所蘊(yùn)含的數(shù)據(jù)不僅是網(wǎng)頁上的文字和圖片，還包括網(wǎng)絡(luò)的拓?fù)湫畔ⅰ⒕W(wǎng)頁的鏈接結(jié)構(gòu)以及用戶對網(wǎng)站的訪問和操作記錄。然而，如何從Web 的海量數(shù)據(jù)中挖掘出蘊(yùn)含其中的信息，一直是國內(nèi)外學(xué)者研究的熱點(diǎn)。將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)應(yīng)用于Web 領(lǐng)域的技術(shù)即Web 挖掘[1]。Web 挖掘按應(yīng)用可以分為3 類：Web 內(nèi)容挖掘，Web 結(jié)構(gòu)挖掘，Web使用挖掘[2]。Web 內(nèi)容挖掘是從Web 的網(wǎng)頁內(nèi)容中提取知識；Web 結(jié)構(gòu)挖掘從Web 的組織結(jié)構(gòu)和鏈接關(guān)系中挖掘出信息；Web 使用挖掘是利用Web 日志發(fā)現(xiàn)用戶的興趣模式，因此，Web 使用挖掘也稱作Web 日志挖掘。在通常情況下，相對于挖掘內(nèi)容和結(jié)構(gòu)，挖掘用戶的使用更有意義。

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

Hadoop 是Apache 下的一個(gè)開源框架，是一個(gè)更容易開發(fā)和并行處理大規(guī)模數(shù)據(jù)的分布式計(jì)算平臺。同時(shí)并行計(jì)算存在的問題如負(fù)載平衡、工作調(diào)度、分布式存儲、容錯(cuò)處理、網(wǎng)絡(luò)通信等也都由Hadoop 負(fù)責(zé)解決。因此，本文對Hadoop 進(jìn)行介紹，包括HDFS 和MapReduce 的組成結(jié)構(gòu)和工作原理，并設(shè)計(jì)一種基于Hadoop 的Web 日志并行挖掘算法。

2 Hadoop 相關(guān)技術(shù)

Hadoop 是一個(gè)集成了分布式文件系統(tǒng)HDFS 和大規(guī)模并行計(jì)算模型MapReduce 的開源框架[4]。Hadoop 具有如下優(yōu)勢：(1)可伸縮性，能夠處理petabytes 級數(shù)據(jù)，并可以無限擴(kuò)充存儲和計(jì)算能力。(2)可靠性，可以維護(hù)同一份數(shù)據(jù)的多份副本并自動(dòng)對失敗的節(jié)點(diǎn)重新分布處理。(3)高效性，Hadoop 能并行地處理數(shù)據(jù)。同時(shí)，Hadoop 也是低成本的，因?yàn)樗鼘τ布囊蟛桓?，所以可以運(yùn)行在普通的微機(jī)集群上。

2.1 Hadoop 的分布式文件系統(tǒng)

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

2.2 MapReduce 并行計(jì)算模型

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

Hadoop 下的MapReduce 編程模式同HDFS 一樣采用Master/Slave 架構(gòu)，由主控節(jié)點(diǎn)(JobTracker)和計(jì)算節(jié)點(diǎn)(TaskTracker)2 種節(jié)點(diǎn)組成。JobTracker 節(jié)點(diǎn)負(fù)責(zé)任務(wù)的調(diào)度和對TaskTracker 節(jié)點(diǎn)的管理，TaskTracker 節(jié)點(diǎn)負(fù)責(zé)執(zhí)行Map 和Reduce 任務(wù)。TaskTracker 每隔一段時(shí)間就會向JobTracker 發(fā)送信號來證明其處于正常工作的狀態(tài)，JobTracker 就會將該TaskTracker 放入空閑列表。

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

3.1 系統(tǒng)架構(gòu)

在一個(gè)Hadoop 集群中，HDFS 的管理節(jié)點(diǎn)和Map Reduce 的主控節(jié)點(diǎn)可以使用同一臺機(jī)器，也可以分別使用不同的機(jī)器。同樣數(shù)據(jù)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)也可以共用同一臺機(jī)器。本文實(shí)現(xiàn)的基于Hadoop 的Web 日志挖掘系統(tǒng)架構(gòu)如圖1 所示。其中，Master 節(jié)點(diǎn)負(fù)責(zé)NameNode 和JobTracker節(jié)點(diǎn)的工作；Slave 節(jié)點(diǎn)既要用來存儲數(shù)據(jù)塊還要執(zhí)行Master 節(jié)點(diǎn)所分配的映射和化簡任務(wù)。

圖1 基于Hadoop 的Web 日志挖掘系統(tǒng)架構(gòu)

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

3.2 數(shù)據(jù)預(yù)處理

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

3.3 基于Hadoop 的FP-growth 算法

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

使用關(guān)聯(lián)規(guī)則的挖掘算法一般分為2 步：

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

(2)由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：規(guī)則A ? B必須滿足事先定義好的最小支持計(jì)數(shù) Support (A ?B)和最小置信度Confidence (A ?B)，其中：

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

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

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

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

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

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

2)Reduce 函數(shù)收到子事務(wù)集subDi 后，創(chuàng)建subDi 的頻繁模式樹并對其進(jìn)行挖掘。該 Reduce 中調(diào)用的方法insert_tree(創(chuàng)建樹)和FP-growth(挖掘樹)就是傳統(tǒng)的創(chuàng)建和挖掘頻繁模式樹的算法。該Reduce 中調(diào)用的挖掘樹算法跟傳統(tǒng)算法相比，增加了一個(gè)參數(shù)subL_listi，這是因?yàn)閭鹘y(tǒng)的FP-growth 算法是掃描全局的L_list，而本文只需要掃描局部subL_listi。Reduce 函數(shù)的偽碼如下：

3)根據(jù)生成的頻繁模式集和置信度公式推出關(guān)聯(lián)規(guī)則。

基于Hadoop 的并行FP-growth 算法可以有效地將一棵FP 樹分成多個(gè)小FP 樹，在多臺Slave 節(jié)點(diǎn)上并行計(jì)算，然后對各個(gè)Slave 節(jié)點(diǎn)上的挖掘結(jié)果取并集，得到目標(biāo)的頻繁模式全集，最終根據(jù)頻繁項(xiàng)集的支持度計(jì)數(shù)和置信度推出關(guān)聯(lián)規(guī)則。

4 實(shí)驗(yàn)結(jié)果與分析

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

圖2 加速比測試結(jié)果

可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，加速比小于1，說明并行處理的時(shí)間反而大于單機(jī)的執(zhí)行時(shí)間，這是因?yàn)榛贖adoop 的算法需要傳輸中間文件且Hadoop 框架的啟動(dòng)、調(diào)度都需要一定的執(zhí)行時(shí)間，而數(shù)據(jù)量較小時(shí)執(zhí)行算法本身所需的時(shí)間并不長，所以當(dāng)數(shù)據(jù)量較小時(shí)Hadoop 平臺所消耗的時(shí)間比重偏大，從而導(dǎo)致了并行處理時(shí)間大于單機(jī)執(zhí)行時(shí)間。然而隨著數(shù)據(jù)量的增大，并行算法在執(zhí)行效率上就體現(xiàn)出了優(yōu)勢。此外，隨著節(jié)點(diǎn)數(shù)目的增加，算法的執(zhí)行效率也得到了相應(yīng)的提高，不過當(dāng)節(jié)點(diǎn)數(shù)目大到一定程度時(shí)，加速比增長率的提高并不多，因此，可根據(jù)數(shù)據(jù)集的大小選擇合適的節(jié)點(diǎn)數(shù)目。

該實(shí)驗(yàn)證明了并行FP-growth 算法優(yōu)于串行FP-growth算法，并且隨著數(shù)據(jù)量的增大，并行FP-growth 算法的優(yōu)勢也越來越明顯。

5 結(jié)束語

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

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

[2]王 凱,渠 芳,王 輝. 利用Web 挖掘技術(shù)實(shí)現(xiàn)個(gè)性化推送服務(wù)[J]. 情報(bào)雜志,2006,25(11): 86-88.

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

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

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

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

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

[8]趙立江,何欽銘. 一種個(gè)性化Web 推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 武漢理工大學(xué)學(xué)報(bào),2004,28(5): 681-684.

[9]談克林,孫志揮. 一種FP 樹的并行挖掘算法[J]. 計(jì)算機(jī)工程與應(yīng)用,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.