宋瑩,沈奇威,王晶
(1 北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,北京 100876;2 東信北郵信息技術(shù)有限公司,北京 100191)
隨著Internet的迅猛發(fā)展,Web上的信息急劇膨脹,而其中蘊(yùn)含的信息未能得到充分的挖掘和利用。因此,Web數(shù)據(jù)挖掘成為數(shù)據(jù)挖掘技術(shù)研究的熱點(diǎn)。Web數(shù)據(jù)挖掘主要分為3類:Web內(nèi)容挖掘(Web Content Mining),Web結(jié)構(gòu)挖掘(Web Structure Mining)和Web日志挖掘(Web Usage Mining)[1]。
Web日志挖掘就是對用戶訪問Web時(shí)的訪問記錄進(jìn)行數(shù)據(jù)挖掘。通過分析和研究日志的規(guī)律, 實(shí)現(xiàn)聚類、分類、關(guān)聯(lián)規(guī)則、序列分析等Web日志挖掘算法[2]。
Web日志挖掘過程一般分為3個(gè)階段[3]:預(yù)處理階段、挖掘算法實(shí)施階段、分析階段。數(shù)據(jù)預(yù)處理的目的就是將原始日志經(jīng)過處理形成用戶的會(huì)話文件,為挖掘算法實(shí)施階段作好數(shù)據(jù)準(zhǔn)備。作為整個(gè)挖掘過程的基礎(chǔ)和實(shí)施有效挖掘算法的前提,數(shù)據(jù)預(yù)處理環(huán)節(jié)非常關(guān)鍵。
Web日志包含了豐富和動(dòng)態(tài)Web頁面的訪問和使用信息,這為Web日志挖掘提供了豐富的資源。但是如何對Web日志進(jìn)行高效可靠的數(shù)據(jù)預(yù)處理具有極大的挑戰(zhàn)性[4]。
Hadoop是Apache下的一個(gè)開源分布式計(jì)算平臺(tái),它提供簡單的編程模型,對大量數(shù)據(jù)進(jìn)行分布式處理。Hadoop一般運(yùn)行在由大量普通計(jì)算機(jī)組成的集群上。Hadoop框架的核心是分布式文件系統(tǒng)HDFS和Map/Reduce。HDFS創(chuàng)建數(shù)據(jù)塊的多個(gè)副本,并將其分布存儲(chǔ)在集群的數(shù)據(jù)節(jié)點(diǎn)(Data Node)上,實(shí)現(xiàn)可靠而快速的計(jì)算。Map/Reduce是一個(gè)用于大數(shù)據(jù)量并行計(jì)算的編程模型,同時(shí)也是一種高效的任務(wù)調(diào)度模型,它將一個(gè)計(jì)算任務(wù)分成很多細(xì)粒度的子任務(wù),并在空閑的處理節(jié)點(diǎn)(Task Tracker)之間進(jìn)行調(diào)度,使處理速度快的節(jié)點(diǎn)處理更多的任務(wù)[5]。同時(shí)Map/Reduce也會(huì)針對失敗的任務(wù)重新分布處理,提供其高可用性。
本文采用高可拓展性的Hadoop分布式計(jì)算平臺(tái),通過對某典型書籍閱讀網(wǎng)站的日志進(jìn)行研究和分析,設(shè)計(jì)與實(shí)現(xiàn)了一個(gè)基于Hadoop的Web日志預(yù)處理方法,方便行之有效的進(jìn)行后續(xù)Web日志挖掘工作,進(jìn)而指導(dǎo)頁面的布局改造,優(yōu)化網(wǎng)站的總體架構(gòu),提升網(wǎng)站的流量,增加網(wǎng)站的收益。
Web日志挖掘首先要對日志中的原始數(shù)據(jù)進(jìn)行采集和預(yù)處理,其任務(wù)是將原始日志數(shù)據(jù)轉(zhuǎn)換成適合數(shù)據(jù)挖掘和模式發(fā)現(xiàn)所需的會(huì)話文件。傳統(tǒng)的Web日志預(yù)處理主要包括數(shù)據(jù)清洗、用戶識(shí)別、會(huì)話識(shí)別和路徑補(bǔ)充。我們的日志中含有用戶ID字段,每個(gè)用戶ID標(biāo)識(shí)一個(gè)用戶,故而省去用戶識(shí)別步驟。并結(jié)合路徑補(bǔ)充進(jìn)行適當(dāng)?shù)臅?huì)話拆分。
在進(jìn)行Web日志預(yù)處理和挖掘之前,首先要進(jìn)行數(shù)據(jù)采集,確定合適的數(shù)據(jù)源。Web用戶訪問數(shù)據(jù)可以服務(wù)器端、客戶端或代理服務(wù)器端進(jìn)行收集。本文的數(shù)據(jù)源為來自服務(wù)器端的Apache日志文件,它詳細(xì)記錄了該書籍閱讀網(wǎng)站用戶的訪問行為,日志格式如表1所示(省略部分空字段)。
表1 Web 日志格式
Web日志記錄了用戶對網(wǎng)站的每一次點(diǎn)擊訪問,但由于種種原因,Web日志中有很多記錄是多余的、不完整或錯(cuò)誤的,這對數(shù)據(jù)挖掘不但無用,還會(huì)增加處理的復(fù)雜性,甚至產(chǎn)生錯(cuò)誤結(jié)果。因此在進(jìn)行數(shù)據(jù)挖掘之前必須對數(shù)據(jù)進(jìn)行預(yù)處理,以消除數(shù)據(jù)的不完整性、噪聲和不一致性。
2.2.1 數(shù)據(jù)清洗
數(shù)據(jù)清洗是指根據(jù)需求,對日志文件進(jìn)行處理,刪除與挖掘任務(wù)不相關(guān)的數(shù)據(jù)并合并某些記錄,對用戶請求頁面時(shí)發(fā)生錯(cuò)誤的記錄進(jìn)行適當(dāng)?shù)奶幚淼鹊取?/p>
當(dāng)用戶請求一個(gè)網(wǎng)頁時(shí),與這個(gè)網(wǎng)頁有關(guān)的圖片、音頻等信息會(huì)自動(dòng)下載,并記錄在日志文件中,由于圖片、音頻等不是用戶顯式請求的,因此可以把日志中文件的后綴為gif、jpg、jpeg、wav等的記錄刪除。后綴名為cgi、js等的腳本文件對后面的分析處理沒有任何影響,也應(yīng)該刪除。
常見的頁面請求方法包括GET、POST和 HEAD。由于只有GET方法反映了用戶的訪問行為, 因此本文只保留 GET 方式的記錄。
2.2.2 會(huì)話識(shí)別
會(huì)話就是指一個(gè)用戶從進(jìn)入網(wǎng)站到離開網(wǎng)站所訪問的一系列頁面。會(huì)話識(shí)別的任務(wù)就是將每一個(gè)用戶的每一個(gè)會(huì)話識(shí)別出來。本文結(jié)合使用基于引用和基于頁面訪問時(shí)間間隔的方法完成會(huì)話識(shí)別,識(shí)別過程可描述如下:
(1)對同一用戶,按照頁面訪問時(shí)間排序,依次處理訪問頁面。
(2)如果用戶訪問的頁面為網(wǎng)站主頁,則認(rèn)為這是一個(gè)新的會(huì)話。
(3)檢查訪問頁面的ReferURL,如果ReferURL為網(wǎng)站主頁,且用戶訪問的上一頁不是網(wǎng)站主頁,也認(rèn)為這是一個(gè)新的會(huì)話;如果ReferURL為空,且該記錄與上一條記錄的訪問時(shí)間間隔大于10s[6],也認(rèn)為該記錄為一個(gè)新的用戶會(huì)話。
(4)設(shè)定相鄰頁面的訪問時(shí)間閾值δ。對于一個(gè)用戶訪問序列中的兩條相鄰訪問記錄,只有當(dāng)ti+1-ti<δi的時(shí)候,才認(rèn)為兩次訪問屬于同一個(gè)會(huì)話?,F(xiàn)有的會(huì)話識(shí)別方法一般將δ設(shè)為10min。由于本文的實(shí)驗(yàn)數(shù)據(jù)來自一個(gè)書籍閱讀網(wǎng)站,導(dǎo)航頁與書籍閱讀頁的信息含量差別很大,鑒于正常人的閱讀速度平均為每分鐘200~240字[7],而該書籍閱讀網(wǎng)站書籍閱讀頁頁面字?jǐn)?shù)為1000~6000不等,故而提出一種基于頁面包含字?jǐn)?shù)的時(shí)間閾值設(shè)定方法,假設(shè)頁面i包含字?jǐn)?shù)為Ci,其閾值設(shè)定為δi=Ci/200。
2.2.3 路徑補(bǔ)充與會(huì)話拆分
Taucher和Greenberg證明超過50%的頁面訪問是通過Backward按鈕進(jìn)行的[8]。由于代理服務(wù)器和瀏覽器緩存的存在,在Backward時(shí),不會(huì)訪問Web服務(wù)器,服務(wù)器上沒有任何該頁面的日志文件,路徑補(bǔ)充重點(diǎn)是把用戶通過Backward按鈕訪問的路徑記錄補(bǔ)全。
本文采用基于引用和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法進(jìn)行路徑補(bǔ)充,并據(jù)此進(jìn)行會(huì)話拆分。如果一條記錄的referURL不是上一條記錄的 URL, 則假定用戶使用回退按鈕訪問了緩存中的頁面,需要進(jìn)行路徑補(bǔ)充。根據(jù)referURL和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的路徑補(bǔ)充遵循以下規(guī)則:如果某條用戶會(huì)話的訪問路徑為a-b-c-d-e,而頁面d的ReferURL不等于c的URL,則依次查找d與頁面c、b、a之間的超鏈接關(guān)系,直到發(fā)現(xiàn)存在超鏈接關(guān)系的最近頁面,假設(shè)d與c、b之間均不存在超鏈接關(guān)系,而和a之間存在超鏈接關(guān)系,那么認(rèn)為這個(gè)用戶是通過Backward按妞,從本地Cache中調(diào)出頁面a,從而訪問頁面d,將該會(huì)話拆分為a-b-c和a-d-e;否則若頁面d和a、b、c均無超鏈接關(guān)系,則認(rèn)為用戶是從絕對地址到達(dá)頁面d,將該會(huì)話拆分為a-b-c和d-e。
Web日志預(yù)處理中的路徑補(bǔ)充和會(huì)話拆分需要根據(jù)網(wǎng)站的拓?fù)浣Y(jié)構(gòu),確定那些由于被代理服務(wù)器和瀏覽器緩存,而在服務(wù)器日志中沒有記錄且被用戶重復(fù)訪問的網(wǎng)頁;會(huì)話識(shí)別需要根據(jù)具體網(wǎng)頁包含字?jǐn)?shù)確定時(shí)間閾值δ,故而我們采用網(wǎng)絡(luò)爬蟲爬取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
網(wǎng)絡(luò)爬蟲的爬取策略一般分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先3種。廣度優(yōu)先搜索策略是指在抓取過程中,在完成當(dāng)前層次的搜索后,才進(jìn)行下一層次的搜索,算法的設(shè)計(jì)和實(shí)現(xiàn)相對簡單。本文使用廣度優(yōu)先搜索方法,多線程爬取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),直到所有線程全部超時(shí)。
將網(wǎng)站的拓?fù)浣Y(jié)構(gòu)采用有向圖表示。有向圖是一個(gè)二元組,記為D。即D=
經(jīng)過爬取、清洗、去重,得到該網(wǎng)站的149265個(gè)頂點(diǎn)、4825319條有向邊,平均頁面出度為32.33。
在爬取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí),計(jì)算所有頁面的字?jǐn)?shù)。字的定義為:頁面HTML標(biāo)簽頁,即“<”及“>”之間的字符不計(jì)算在內(nèi);每個(gè)中文字、每個(gè)標(biāo)點(diǎn)符號(hào)、每個(gè)英文單詞、每個(gè)數(shù)字均記為一個(gè)字。
根據(jù)2.2.2節(jié)提出的方法,得出頁面訪問時(shí)間閾值δ,對應(yīng)的頁面數(shù)統(tǒng)計(jì)如表2所示。
表2 頁面訪問時(shí)間閾值δ對應(yīng)的頁面數(shù)統(tǒng)計(jì)(min)
從表2可以看出,頁面的時(shí)間閾值雖然經(jīng)過調(diào)整。但在一些字?jǐn)?shù)較少的導(dǎo)航頁可能過小,當(dāng)δ<1min時(shí)將δ設(shè)置為1min。
使用目前常用的評價(jià)標(biāo)準(zhǔn)[9]:會(huì)話被算法完整重建的程度。使用精確度和查全度這2個(gè)指標(biāo)來衡量重建程度。設(shè)Rh為算法h生成的會(huì)話集合,R是真正的會(huì)話集合,則精確度p(h)=|Rh∩R|/|Rh|,查全度r(h)=|Rh∩R|/|R|。在對各種算法進(jìn)行比較時(shí),以基于引用的方法得到的會(huì)話集合作為基準(zhǔn)R,實(shí)驗(yàn)數(shù)據(jù)如表3所示。
表3 會(huì)話識(shí)別方法的比較結(jié)果
可以看到,相對于傳統(tǒng)的固定閾值10min,基于頁面字?jǐn)?shù)確定頁面時(shí)間閾值的會(huì)話識(shí)別算法精確度與查全度都有提高。改進(jìn)的值更能反映用戶的瀏覽習(xí)慣,使得劃分的會(huì)話更為準(zhǔn)確。
Map/Reduce提供了一個(gè)在大數(shù)據(jù)集上的并行計(jì)算框架。Mapper將輸入記錄打散,按照用戶要求形成 (1)隨著Web日志的大規(guī)模增長,每天的日增量上億,單一節(jié)點(diǎn)的計(jì)算能力已經(jīng)不能滿足要求,而MapReduce支持大規(guī)模集群操作,在集群上可以方便地增加多至上千個(gè)節(jié)點(diǎn)并行計(jì)算,其計(jì)算速度會(huì)隨集群數(shù)量相應(yīng)增加。 (2)Web日志的預(yù)處理,需要針對每個(gè)用戶處理其全部訪問,非常適合MapReduce的 3.2.1 Mapper操作 Mapper操作的輸入為Web日志記錄,對于每條記錄,進(jìn)行數(shù)據(jù)清洗工作,并選擇key為USID,value為 功能:清洗每條輸入日志記錄,形成 1. input[] ← 以" "分隔的輸入記錄 2. if input[5] = "GET" and input[6] 不以{gif、jpg、jpeg、wav、rm、css、cgi、js}結(jié)尾 and 200 <=input[8] <= 299 3. mapKey ← input[0] 4. mapValue ← input[5]|input[6]| input[8] 5. collect {mapKey,mapValue} 6. end if 3.2.2 Combiner操作 為了優(yōu)化MapReduce操作,我們增加一個(gè)可選的Combiner操作。Combiner在Mapper之后、Reducer之前運(yùn)行,它會(huì)在每一個(gè)運(yùn)行map任務(wù)的節(jié)點(diǎn)上運(yùn)行;接收節(jié)點(diǎn)上的Mapper的輸出作為輸入,對Mapper的輸出進(jìn)行聚合,同時(shí)聚合的結(jié)果也會(huì)作為Combiner的輸入進(jìn)一步進(jìn)行數(shù)據(jù)聚合,直到在該節(jié)點(diǎn)上的每個(gè)key聚合為一條記錄。Combiner的輸出會(huì)被發(fā)送到Reducer。 本文的Combiner操作將Mapper操作的輸出鍵值對聚合為 3.2.3 Reducer操作 將USID定義為Combiner的輸出key,將URLIt定義為包含Combiner輸出value的迭代器,將US定義為格式為 Reducer接收一系列 2. urlArray[] ← 以";”分隔的urls 4. USIt ← USIt + {url} 5. end for each 6. end for each 7. 將USIt按照Time字段升序排列 8. us1 ← USIt.next() 9. USL ← {us1} 10. reduceValue ← null 11. while USIt.hasnext() do 12. us2 ← USIt.next() 13. if (us2 = "index.jsp") or (us2.referURL =“index.jsp” and us1.URL ≠“index.jsp”) or(us2.referURL = null and us2.Time us1.Time <10s) or (us2.Time us1.Time > δus1.URL) then 14. reduceKey ← USL中全部記錄中的URL字段依序以"|"連接 15. collect {reduceKey,reduceValue} 16. us1 ← us2 17. USL ← {us1} 18. else if us2.referURL = us1.URL then 19. USL ← USL + {us2} 20. us1 ← us2 21. else if us2.referURL ≠ us1.URL then 22. reduceKey ← USL中全部記錄中的URL字段依序以"|"連接 23. collect {reduceKey,reduceValue} 24. us1 ← us2 25. 倒序掃描USL直到列表頭,until find usk,其中usk.URL = us2.referURL 26. USL ← USL – {us1…usk} + {us1} 27. if none usk.URL = us2.referURL 28. USL ← {us1} 29. end if 30. end if 31. end while 實(shí)驗(yàn)運(yùn)行在一個(gè)Hadoop集群上,這個(gè)集群由10臺(tái)服務(wù)器組成。其中的一臺(tái)服務(wù)器作為分布式文件系統(tǒng)HDFS的NameNode及MapReduce運(yùn)行過程中的JobTracker,這臺(tái)機(jī)器稱為主節(jié)點(diǎn)。另外9臺(tái)機(jī)器作為HDFS的DataNode和MapReduce運(yùn)行過程中的TaskTracker,這些節(jié)點(diǎn)稱為從節(jié)點(diǎn)。9臺(tái)從節(jié)點(diǎn)的配置如表4所示。 為驗(yàn)證Hadoop對Web日志預(yù)處理的有效性及高效性,我們在單機(jī)和Hadoop集群上分別用Java語言實(shí)現(xiàn)了前面相同的Web日志預(yù)處理方法(單機(jī)的配置為雙核3.2GHz處理器,4GB內(nèi)存),并在兩個(gè)平臺(tái)上分別對文件大小不同的Web日志文件分別進(jìn)行處理,計(jì)算執(zhí)行時(shí)間,其結(jié)果如圖1所示。 表4 集群DataNode配置表 圖1 單機(jī)系統(tǒng)與Hadoop集群執(zhí)行時(shí)間的對比 同時(shí)在Hadoop集群上針對更大量數(shù)據(jù)進(jìn)行測試,其結(jié)果如圖2所示。 圖2 大量數(shù)據(jù)在Hadoop集群執(zhí)行時(shí)間 由以上測試過程可以看出,采用Hadoop平臺(tái)處理Web日志是一個(gè)行之有效的方法。當(dāng)處理數(shù)據(jù)量較小時(shí),由于Hadoop平臺(tái)的啟動(dòng)耗時(shí)和中間文件的傳輸耗時(shí),并行運(yùn)算的總時(shí)間反而大于單機(jī)執(zhí)行的時(shí)間。但隨著數(shù)據(jù)量的增大,Hadoop平臺(tái)將數(shù)據(jù)分割后分派給多個(gè)計(jì)算節(jié)點(diǎn)并行處理,使并行運(yùn)算速度增長緩慢,而單機(jī)處理時(shí)間基本呈現(xiàn)線性增長的趨勢。隨著輸入數(shù)據(jù)的增加,兩者執(zhí)行效率的差距也越來越大。另外,Web日志條數(shù)在104的數(shù)量級上由于集群的計(jì)算節(jié)點(diǎn)一直未滿,故而時(shí)間增長非常緩慢;在106的數(shù)量級上,集群的計(jì)算節(jié)點(diǎn)基本已滿,此時(shí)Hadoop的處理時(shí)間呈現(xiàn)略小于線性的增長,而在這樣的數(shù)據(jù)集上,由于內(nèi)存、處理器能力等諸多條件的限制,單機(jī)運(yùn)算還可能出現(xiàn)內(nèi)存溢出等現(xiàn)象,需要進(jìn)行數(shù)據(jù)拆分。 Web日志挖掘中的一個(gè)重要的前提和基礎(chǔ)就是數(shù)據(jù)準(zhǔn)確性。高質(zhì)量的Web日志挖掘必須依賴高質(zhì)量的數(shù)據(jù)[10]。本文針對海量的Web日志,基于現(xiàn)有的Web日志預(yù)處理方法,提出一種改進(jìn)的會(huì)話識(shí)別、路徑補(bǔ)充和會(huì)話拆分方法,并基于Hadoop平臺(tái)實(shí)現(xiàn)。同時(shí)針對Hadoop與單機(jī)的處理效率進(jìn)行了對比,證實(shí)了Hadoop平臺(tái)對于Web日志預(yù)處理的有效及高效性。 [1] 楊清蓮,周慶敏,常志玲. Web挖掘技術(shù)及其在網(wǎng)絡(luò)教學(xué)評價(jià)中的應(yīng)用[J]. 南京工業(yè)大學(xué)學(xué)報(bào), 2005(05):100. [2] Ni P,Liao J X,Wang C,Ren K Y. Web information recommendation based on user behaviors[A]. 2009 WRI World Congress on Computer Science and Information Engineering[C]. March 31, 2009-April 2, 2009:426. [3] 楊怡玲,管旭東,陸麗娜. 一個(gè)簡單的日志挖掘系統(tǒng)[J]. 上海交通大學(xué)學(xué)報(bào), 2000(7):35- 37. [4] 朱鶴祥. Web日志挖掘中數(shù)據(jù)預(yù)處理算法的研究[D]. 大連:大連交通大學(xué), 2010:11. [5] 程苗,陳華平. 基于Hadoop的Web日志挖掘[J]. 計(jì)算機(jī)工程.2011,06(11):37. [6] Rosenbium M, Garfinkel T. Virtual machine monitors: current technology and future trends[J]. IEEE Computer Magazine, 2005, 38(5): 39-47. [7] 東尼?博贊(Tony Buzan). 博贊學(xué)習(xí)技巧[M]. 北京:中信出版社, 2009.41-42. [8] Taucher L,Greenberg S.Revisitation patterns in world wide web navigation[A].Proc of Int Conf CHI’97[C]. 1997 Atlanta. [9] Cooley R,Mobasher B,Srivastava J. Data preparation for mining world wide web browsing patterns[J]. Knowledge and Information System.1999,1(1):32-40. [10] 趙瑩瑩,韓元杰. Web日志數(shù)據(jù)挖掘中數(shù)據(jù)預(yù)處理模型的研究與建立[J]. 現(xiàn)代電子技術(shù), 2007(4):103-105.4 結(jié)果分析
5 結(jié)論