基于云計(jì)算的大規(guī)模網(wǎng)頁日志挖掘研究

摘要：互聯(lián)網(wǎng)上的數(shù)據(jù)規(guī)模大、種類多、變化快，而且越來越復(fù)雜。通過數(shù)據(jù)挖掘和分析，可以獲取有潛在價(jià)值的信息。但是，傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)在數(shù)據(jù)存儲和計(jì)算性能上存在瓶頸。通過使用云計(jì)算技術(shù)，設(shè)計(jì)了一個(gè)基于Hadoop架構(gòu)的網(wǎng)頁日志數(shù)據(jù)挖掘和分析平臺來解決這個(gè)問題。同時(shí)，為了提高挖掘效率，為大規(guī)模網(wǎng)頁日志挖掘?qū)崿F(xiàn)了Apriori算法的并行化，并使用該平臺驗(yàn)證了該行算法的效率。

關(guān)鍵詞：數(shù)據(jù)挖掘；網(wǎng)頁日志挖掘；Apriori算法；云計(jì)算；Hadoop

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）28-6603-04

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，因特網(wǎng)上的數(shù)據(jù)成指數(shù)級增長。如何在這樣的一個(gè)環(huán)境中發(fā)現(xiàn)并挖掘出有價(jià)值的信息成了研究的熱點(diǎn)[1]。網(wǎng)頁日志挖掘是數(shù)據(jù)挖掘技術(shù)在網(wǎng)頁上的應(yīng)用，它需要大量的網(wǎng)頁數(shù)據(jù)[2]。這方面的研究一直集中在改進(jìn)挖掘算法上，而對于大規(guī)模數(shù)據(jù)的數(shù)據(jù)挖掘系統(tǒng)的處理能力尚未得到很大改善。在大規(guī)模數(shù)據(jù)挖掘方面，單個(gè)節(jié)點(diǎn)的計(jì)算能力遇到了瓶頸。解決這個(gè)問題的一個(gè)有效的方法就是利用云計(jì)算、分布式計(jì)算和虛擬化技術(shù)的優(yōu)勢，將復(fù)雜的計(jì)算通過網(wǎng)絡(luò)分配給多個(gè)節(jié)點(diǎn)。文章結(jié)合網(wǎng)頁日志文件的特性，設(shè)計(jì)了一個(gè)基于Hadoop集群架構(gòu)的數(shù)據(jù)挖掘平臺，改進(jìn)了Apriori算法，并通過實(shí)驗(yàn)驗(yàn)證了該算法的高效性。

1 云計(jì)算和數(shù)據(jù)挖掘技術(shù)

1.1 MapReduce編程模型

MapReduce是一種用于大規(guī)模數(shù)據(jù)集并行運(yùn)算的編程模型[3]。該模型處理集群上的大規(guī)模數(shù)據(jù)集時(shí)主要分兩步：“映射（Map）”和“歸約（Reduce）”。首先，通過映射處理輸入的鍵-值對數(shù)據(jù)，獲得鍵-值對形式的中間結(jié)果。然后，將獲得的中間結(jié)果整理并排序。最后，結(jié)合處理得到的結(jié)果進(jìn)行合并得到最終結(jié)果。整個(gè)過程如圖1所示。

1.2 網(wǎng)頁日志挖掘的概念

網(wǎng)頁日志是由網(wǎng)頁服務(wù)器在用戶瀏覽網(wǎng)頁時(shí)產(chǎn)生的數(shù)據(jù)文件。它記錄了用戶的交互操作。這樣做的目的是為了分析并找出有用的信息，比如用戶瀏覽網(wǎng)頁的方式，用戶的愛好等等。

1.3 網(wǎng)頁日志挖掘的過程

網(wǎng)頁日志挖掘主要分為三個(gè)步驟：

1） 預(yù)處理：網(wǎng)頁日志里的大多是些板結(jié)構(gòu)化或者非結(jié)構(gòu)化的數(shù)據(jù)。這使得數(shù)據(jù)挖掘的算法不能直接應(yīng)用于原始的日志數(shù)據(jù)。如果不進(jìn)行預(yù)處理，很難找出有價(jià)值的信息[4]。

2） 模式識別：通過此步為經(jīng)過預(yù)處理產(chǎn)生的數(shù)據(jù)文件選擇合適的數(shù)據(jù)挖掘技術(shù)和算法，找出能反映用戶特定行為、資源、會話以及簡明數(shù)據(jù)的隱式信息模式。

3） 模式分析：解析并分析上一步挖掘出的模式信息，找出感興趣的模式，然后以可視化的方式輸出結(jié)果。

2 基于云計(jì)算的網(wǎng)頁日志挖掘系統(tǒng)的設(shè)計(jì)

2.1單節(jié)點(diǎn)數(shù)據(jù)挖掘系統(tǒng)

傳統(tǒng)的集中式數(shù)據(jù)挖掘系統(tǒng)基于單節(jié)點(diǎn)，它使用一個(gè)服務(wù)器來完成包括數(shù)據(jù)采集、數(shù)據(jù)存儲、數(shù)據(jù)預(yù)處理以及數(shù)據(jù)挖掘等所有的工作。當(dāng)數(shù)據(jù)挖掘工作的復(fù)雜度不高，數(shù)據(jù)量不大的時(shí)候，單節(jié)點(diǎn)系統(tǒng)的工作效率很高。然而，隨著互聯(lián)網(wǎng)網(wǎng)頁日志數(shù)據(jù)的不斷增長，數(shù)據(jù)挖掘工作越來越復(fù)雜，集中式數(shù)據(jù)挖掘系統(tǒng)已經(jīng)不能滿足大規(guī)模網(wǎng)頁日志處理的要求。

2.2 基于云的大規(guī)模網(wǎng)頁日志挖掘系統(tǒng)

由分析可知，傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)在處理海量數(shù)據(jù)時(shí)有很多瓶頸，使用云計(jì)算技術(shù)可以有效地解決這個(gè)問題[5，6]。

云計(jì)算平臺包括一個(gè)主節(jié)點(diǎn)，一個(gè)名稱節(jié)點(diǎn)，一個(gè)算法存儲節(jié)點(diǎn)和一些數(shù)據(jù)節(jié)點(diǎn)。主節(jié)點(diǎn)負(fù)責(zé)各計(jì)算節(jié)點(diǎn)的計(jì)算流程的協(xié)調(diào)和調(diào)度，處理節(jié)點(diǎn)異常，負(fù)載均衡等事項(xiàng)。名稱節(jié)點(diǎn)存儲元數(shù)據(jù)信息。主節(jié)點(diǎn)也可以用作為名稱節(jié)點(diǎn)。為了減少由于數(shù)據(jù)傳輸占用的大量資源，每個(gè)數(shù)據(jù)節(jié)點(diǎn)也是計(jì)算節(jié)點(diǎn)。

通過上面的分析，通過使用Hadoop集群架構(gòu)，構(gòu)建一個(gè)基于云計(jì)算的大規(guī)模網(wǎng)頁日志挖掘系統(tǒng)[7]。該系統(tǒng)分為三層：分布式數(shù)據(jù)存儲層，功能層和可視化層。系統(tǒng)的整體結(jié)構(gòu)如圖2所示。

1） 分布式數(shù)據(jù)存儲層

分布式數(shù)據(jù)存儲層是本系統(tǒng)的硬件資源，由成本低的計(jì)算機(jī)和網(wǎng)絡(luò)設(shè)施組成。這些資源就是云計(jì)算平臺的數(shù)據(jù)節(jié)點(diǎn)。這些節(jié)點(diǎn)不僅提供了數(shù)據(jù)存儲功能，還提供了計(jì)算功能。系統(tǒng)采集的原始網(wǎng)頁日志數(shù)據(jù)文件經(jīng)過預(yù)處理后轉(zhuǎn)換為半結(jié)構(gòu)化的XML格式的文件，存儲到數(shù)據(jù)節(jié)點(diǎn)上。同一份數(shù)據(jù)文件會被復(fù)制存儲到不同的存儲節(jié)點(diǎn)上，這樣就可以避免由系統(tǒng)崩潰帶來的數(shù)據(jù)丟失的問題。

2） 功能層

功能層為系統(tǒng)提供了核心功能。數(shù)據(jù)預(yù)處理組件和數(shù)據(jù)挖掘算法就部署在該層。網(wǎng)頁日志數(shù)據(jù)挖掘由主節(jié)點(diǎn)負(fù)責(zé)。主節(jié)點(diǎn)將復(fù)雜的數(shù)據(jù)挖掘任務(wù)合理地分配給各計(jì)算節(jié)點(diǎn)。這樣數(shù)據(jù)挖掘任務(wù)可以同時(shí)執(zhí)行，達(dá)到了在分布式數(shù)據(jù)庫上并行挖掘的目的。

在每個(gè)周期中，主節(jié)點(diǎn)發(fā)送一個(gè)信號給數(shù)據(jù)節(jié)點(diǎn)，確定數(shù)據(jù)節(jié)點(diǎn)的狀態(tài)是工作中還是閑置。收到信號后，各數(shù)據(jù)節(jié)點(diǎn)將自己的狀態(tài)信息發(fā)送給主節(jié)點(diǎn)。主節(jié)點(diǎn)將根據(jù)收到的信息將閑置的節(jié)點(diǎn)列入到閑置節(jié)點(diǎn)列表中。當(dāng)主節(jié)點(diǎn)收到來自客戶端的任務(wù)請求時(shí)，就將任務(wù)分配給各數(shù)據(jù)節(jié)點(diǎn)。當(dāng)計(jì)算任務(wù)完成后，處理得到的數(shù)據(jù)文件塊會被返回給主節(jié)點(diǎn)。

3） 可視化層

可視化層為用戶提供交互界面和結(jié)果的可視化顯示功能。

3 網(wǎng)頁日志挖掘算法和并行化改進(jìn)

3.1 網(wǎng)頁日志挖掘算法

當(dāng)前，網(wǎng)頁日志挖掘算法包括最大正向引用序列法，關(guān)聯(lián)規(guī)則算法等。關(guān)聯(lián)規(guī)則算法是在一個(gè)事務(wù)中描述各個(gè)事件之間的聯(lián)系規(guī)律的一個(gè)知識模型。通過分析和處理網(wǎng)頁服務(wù)器的日志，關(guān)聯(lián)規(guī)則可以用來分析用戶訪問網(wǎng)頁的習(xí)慣和愛好，進(jìn)而為其提供個(gè)性化的信息。

關(guān)聯(lián)規(guī)則挖掘分兩步：首先是找出所有的頻繁項(xiàng)集。然后找出頻繁項(xiàng)集中各項(xiàng)目之間的緊密關(guān)系。

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個(gè)階段來挖掘頻繁項(xiàng)集[8]。算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全等各個(gè)領(lǐng)域。Apriori采用逐層搜索迭代的方法產(chǎn)生頻繁項(xiàng)集，比如，K-1項(xiàng)目集用來搜索產(chǎn)生K項(xiàng)目集。其步驟如下：

1） 首先，掃描數(shù)據(jù)庫找出滿足最小支持度的項(xiàng)目，構(gòu)成一個(gè)集合——“1項(xiàng)集”，記作L1。

2） 利用L1產(chǎn)生“2項(xiàng)集”的集合L2。

3） 重復(fù)上面的步驟，直到找不到“K項(xiàng)集”——LK。

3.2 基于MapReduce的并行化改進(jìn)

沖Apriori的工作步驟可以看出，在掃描數(shù)據(jù)庫的時(shí)候會產(chǎn)生大量的候選項(xiàng)目集。特別是在處理像網(wǎng)站的網(wǎng)頁這樣的WAN數(shù)據(jù)源的時(shí)候尤其如此。這是一個(gè)嚴(yán)重的缺陷，它會影響到挖掘的效率和準(zhǔn)確性?；谠朴?jì)算平臺的并行Apriori算法可以將上述各項(xiàng)工作分配給各個(gè)數(shù)據(jù)節(jié)點(diǎn)，由這些節(jié)點(diǎn)來進(jìn)行并發(fā)處理并產(chǎn)生各自的頻繁項(xiàng)集。主節(jié)點(diǎn)將所有節(jié)點(diǎn)產(chǎn)生的頻繁項(xiàng)集集中起來，產(chǎn)生全局的頻繁項(xiàng)集。這樣可以大大提高Apriori算法的效率。主要步驟如下：

1） 首先讀取配置參數(shù)、最小支持度和最小可信度，設(shè)置MapReduce參數(shù)。

2） 映射：將讀取到的數(shù)據(jù)映射為鍵值對。

3） 歸約：每次讀取到一個(gè)輸入時(shí)，同一個(gè)項(xiàng)集會被映射到相同的歸約器。歸約器會計(jì)算出項(xiàng)集的頻繁度并識別出滿足最低支持度的頻繁項(xiàng)集。

4） 將K項(xiàng)集記錄在本地。如果K項(xiàng)集為空，停止并跳到第6步。

5） 從本地讀取K項(xiàng)集并產(chǎn)生K+1項(xiàng)集。如果沒有新的候選項(xiàng)集，進(jìn)入第6步。否則，返回第2步。

6） 根據(jù)產(chǎn)生的頻繁項(xiàng)集和最小可信度，產(chǎn)生關(guān)聯(lián)規(guī)則。

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

實(shí)驗(yàn)用了7個(gè)安裝了Linux和Hadoop的服務(wù)器，其中一個(gè)為主節(jié)點(diǎn)，其他的為數(shù)據(jù)存儲兼計(jì)算節(jié)點(diǎn)。實(shí)驗(yàn)主要是挖掘網(wǎng)頁日志的頻繁項(xiàng)集。首先使用傳統(tǒng)的Apriori算法，用單個(gè)節(jié)點(diǎn)進(jìn)行挖掘，然后用改進(jìn)的Apriori算法進(jìn)行并行挖掘。通過對兩組結(jié)果進(jìn)行對比分析，可以看出并行的網(wǎng)頁日志挖掘系統(tǒng)和改進(jìn)的Apriori算法比傳統(tǒng)的方法的效率高很多。

4.1 實(shí)驗(yàn)1

將同一個(gè)網(wǎng)頁日志數(shù)據(jù)分別用單節(jié)點(diǎn)系統(tǒng)和Hadoop集群系統(tǒng)進(jìn)行挖掘。然后用比較數(shù)據(jù)集的大小。可以看到，單節(jié)點(diǎn)系統(tǒng)和Hadoop集群系統(tǒng)產(chǎn)生的頻繁項(xiàng)集的一致性波動很小，如圖3所示。

4.2 實(shí)驗(yàn)2

實(shí)驗(yàn)采用較大規(guī)模的數(shù)據(jù)作為輸入，比較處理相同規(guī)模的數(shù)據(jù)時(shí)單節(jié)點(diǎn)系統(tǒng)和Hadoop集群系統(tǒng)的效率。然后持續(xù)增加輸入數(shù)據(jù)的規(guī)模并記錄兩個(gè)系統(tǒng)的處理時(shí)間。從實(shí)驗(yàn)中可以得出一個(gè)結(jié)論：當(dāng)輸入的數(shù)據(jù)低于一定的規(guī)模時(shí)，兩個(gè)系統(tǒng)并沒有太大區(qū)別。隨著處理的數(shù)據(jù)規(guī)模增大，Hadoop集群系統(tǒng)處理數(shù)據(jù)的時(shí)間比單節(jié)點(diǎn)系統(tǒng)少得多，如圖4所示。

5 結(jié)論

介紹了數(shù)據(jù)挖掘的概念和云計(jì)算的相關(guān)技術(shù)，分析了傳統(tǒng)單節(jié)點(diǎn)數(shù)據(jù)挖掘系統(tǒng)存在的不足。設(shè)計(jì)了一個(gè)基于云計(jì)算和Hadoop集群架構(gòu)的網(wǎng)頁日志挖掘系統(tǒng)，并將Apriori算法和MapReduce結(jié)合起來，實(shí)現(xiàn)了并行Apriori算法。通過實(shí)驗(yàn)驗(yàn)證了在進(jìn)行大規(guī)模網(wǎng)頁日志挖掘時(shí)，并行系統(tǒng)比單節(jié)點(diǎn)系統(tǒng)的效率高很多。并行挖掘系統(tǒng)不僅解決了傳統(tǒng)系統(tǒng)的瓶頸問題，還提高了數(shù)據(jù)處理和分析的效率。

參考文獻(xiàn)：

[1] 馬妮娜.數(shù)據(jù)庫新的應(yīng)用技術(shù)——數(shù)據(jù)挖掘技術(shù)[J].中國電子商務(wù)，2003（7）.

[2] 陳修寬，董祥軍，石芙芙.Web數(shù)據(jù)挖掘綜述[J].山東輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2009（3）.

[3] 吳寶貴，丁振國.基于Map/Reduce的分布式搜索引擎研究[J].現(xiàn)代圖書情報(bào)技術(shù)，2007（8）.

[4] 魏爽.基于XML的Web分布式數(shù)據(jù)挖掘系統(tǒng)研究[J].電腦知識與技術(shù)，2013，9（5）.

[5] 朱紹軍，蘭帆，黃明和.Web結(jié)構(gòu)挖掘算法研究[J].計(jì)算機(jī)與信息技術(shù)，2009（4）.

[6] 李輝.基于云計(jì)算環(huán)境的web結(jié)構(gòu)挖掘算法研究[D].杭州：浙江理工大學(xué)，2012.

[7] 劉永增.基于Hadoop/Hive的海量web日志處理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].大連：大連理工大學(xué)，2011.

[8] 黃進(jìn)，尹治本.關(guān)聯(lián)規(guī)則挖掘的Apriori算法的改進(jìn)[J].電子科技大學(xué)學(xué)報(bào)，2003，32（1）.