1、基于ID3算法的Web日志挖掘預(yù)處理中的Frame頁面過濾技術(shù)的研究摘要描繪了eb日志數(shù)據(jù)預(yù)處理技術(shù)的一種改良技術(shù)Frae過濾技術(shù)，對其關(guān)鍵局部與運作形式進(jìn)展了研究與改良。討論了Frae頁面過濾預(yù)處理技術(shù)在eb頁面挖掘中的效率問題，分析了決策樹算法中最著名的算法ID3算法，并用ID3算法對Frae過濾算法進(jìn)展了改良，比擬新舊算法的執(zhí)行效率及算法結(jié)果質(zhì)量，得出了新算法執(zhí)行效率更高及質(zhì)量更好的結(jié)論，從而搞高了對存在Frae頁面的網(wǎng)站施行eb日志挖掘算法時挖掘結(jié)果的興趣度。關(guān)鍵詞ID3算法；eb日志挖掘；eb日志預(yù)處理;Frae頁面過濾Internet的迅速開展使得eb為人們提供了內(nèi)容豐富且數(shù)量龐大

2、的信息，隨著數(shù)據(jù)挖掘技術(shù)的出現(xiàn)以及開展，數(shù)據(jù)挖掘逐漸被應(yīng)用于eb數(shù)據(jù)。eb日志挖掘是三大類eb挖掘之一，它主要包括數(shù)據(jù)預(yù)處理和挖掘算法施行兩個主要階段.施行挖掘算法之前要對eb日志文件進(jìn)展預(yù)處理，將其轉(zhuǎn)化為用戶會話集.本文著重討論eb日志挖掘預(yù)處理技術(shù)中的Frae頁面過濾預(yù)處理技術(shù)，即在傳統(tǒng)的eb日志預(yù)處理過程中參加Frae頁面過濾這一步驟，并提出了用決策樹算法著名的ID3算法進(jìn)展Frae頁面過濾，進(jìn)一步進(jìn)步了日志數(shù)據(jù)預(yù)處理的質(zhì)量和效率，從而為挖掘算法的施行提供更為準(zhǔn)確的數(shù)據(jù)，進(jìn)步了對存在Frae頁面的網(wǎng)站施行eb日志挖掘算法時整個eb日志挖掘的效率及挖掘結(jié)果的興趣性。2.1eb日志預(yù)處理技術(shù)

3、現(xiàn)狀eb日志挖掘134是指將數(shù)據(jù)挖掘技術(shù)應(yīng)用于eb效勞器日志文件，以發(fā)現(xiàn)隱藏在其中的用戶訪問形式。eb日志預(yù)處理是在eb日志挖掘前，對eb日志進(jìn)展清理、過濾以及重新組合的過程，其目的是剔除日志中對挖掘過程無用的屬性及數(shù)據(jù)，并將eb日志數(shù)據(jù)轉(zhuǎn)換為挖掘算法可識別的保存形式。到目前為止提出的eb日志的預(yù)處理技術(shù)，它包含三種方法識別用戶的活動集合：(1)eb效勞器提供kie，那么具有一樣kie值的頁面懇求是來自同一個用戶，那么用戶會話識別的主要的任務(wù)就是將eb日志劃分為不同kie值所對應(yīng)的頁面懇求集合。(2)eb效勞器沒有提供kie，但每個網(wǎng)站用戶都要一個登錄標(biāo)識符方可訪問站點，那么分析工具即可利用登

4、錄標(biāo)識符識別會話。假如eb效勞器既沒有kie也沒有登錄標(biāo)識符，可以利用主機(jī)地址，同時分析日志中每條記錄的懇求頁和引用頁的URL，然后根據(jù)eb站點的拓?fù)錁?gòu)造超鏈接和其它啟發(fā)式規(guī)那么識別用戶會話，但是這種方法的準(zhǔn)確度較低，不能100正確地識別出每個懇求對應(yīng)的用戶。這里主要討論第3種預(yù)處理方法。一般eb日志預(yù)處理主要包括：數(shù)據(jù)凈化、用戶識別、會話識別、途徑補(bǔ)充、事務(wù)識別數(shù)據(jù)凈化指刪除eb效勞器日志中與挖掘算法無關(guān)的數(shù)據(jù)。由于在eb日志中通常只有HTL文件與用戶會話相關(guān)，所以通過檢查URL的后綴刪除不相關(guān)的數(shù)據(jù)。用戶識別是指要識別出每個訪問網(wǎng)站的用戶。一般eb日志挖掘工具中常使用基于日志/站點的方法，

5、并輔助一些啟發(fā)式規(guī)那么幫助識別用戶。會話識別是將用戶的訪問記錄分為單個的會話。通常采用超時方法識別用戶會話，假如兩頁間懇求時間的差值超過一定的界限(超時閾值)就認(rèn)為用戶開場了一個新的會話。途徑補(bǔ)充是由于本地緩存和代理效勞器緩存的存在，使得效勞器的日志會遺漏一些重要的頁面懇求。途徑補(bǔ)充就是將這些遺漏的懇求補(bǔ)充到用戶會話中，解決的方法類似于用戶識別中的方法。事務(wù)識別，用戶會話是eb日志挖掘中唯一具備自然事務(wù)特征的元素，但是，對于某些挖掘算法來說可能用戶會話的粒度太大，需要利用分割算法將其轉(zhuǎn)化為更小的事務(wù)。一般通常采用圖1所示的數(shù)據(jù)預(yù)處理過程。假如按照前面所介紹的日志預(yù)處理技術(shù)對eb日志進(jìn)展預(yù)處理，

6、那么Frae頁面和其SubFrae頁面也將一起出如今用戶會話文件中。在這樣的用戶會話文件上進(jìn)展數(shù)據(jù)挖掘，F(xiàn)rae頁面和SubFrae頁面作為頻繁遍歷途徑或者頻繁訪問頁組出現(xiàn)的概率很高，并且他們同時出如今挖掘結(jié)果中，這就降低了挖掘結(jié)果的興趣性。圖1典型的eb日志數(shù)據(jù)預(yù)處理過程2.2Frae頁面過濾預(yù)處理技術(shù)HTL標(biāo)準(zhǔn)通過“Frae標(biāo)記支持多窗口頁面，每個窗口里裝載的頁面對應(yīng)一個URL。當(dāng)用戶懇求Frae頁面的URL時，F(xiàn)rae頁面和其中的SubFrae頁面作為一個多窗口頁面展如今用戶面前，我們可以將用戶對Frae頁面的懇求看成就是對多窗口頁面的懇求。這樣，在數(shù)據(jù)預(yù)處理階段將Frae頁面和其中的S

7、ubFrae頁面作為一個整體考慮，并且把Frae頁面對應(yīng)的URL當(dāng)作這個整體的代表。從全局而言，這樣處理可以有效地消除Frae頁面對日志挖掘的影響，最終進(jìn)步挖掘結(jié)果的興趣性。圖2改良的eb日志數(shù)據(jù)預(yù)處理過程為此，我們對圖1中描繪的常用的eb日志數(shù)據(jù)預(yù)處理技術(shù)進(jìn)展相應(yīng)的改良，圖2是改良后的數(shù)據(jù)預(yù)處理過程。改良的eb日志數(shù)據(jù)預(yù)處理過程中，在會話識別與途徑補(bǔ)充這兩個步驟之間增加了Frae頁面過濾。Frae頁面過濾要完成的任務(wù)是，根據(jù)從站點的拓?fù)錁?gòu)造中提取出的Frae-SubFrae關(guān)系表，從會話識別過程中生成的會話文件中，尋找Frae頁面及其SubFrae頁面，將會話文件中對Frae和其SubFra

8、e頁面的懇求用Frae頁面代替，從而刪除會話文件中多余的SubFrae頁面。由于刪除了會話文件中的SubFrae頁面，因此會喪失SubFrae頁面中包含的超鏈接信息，所以接下來的途徑補(bǔ)充步驟中必須使用提升的站點構(gòu)造。如上文所述，我們應(yīng)用Frae頁面過濾技術(shù)有效地消除了Frae頁面對日志挖掘的影響，然而我們知道eb日志挖掘的記錄是成千上萬的，上述Frae頁面過濾算法中是對每個用戶對話的每個頁面進(jìn)展是否Frae和SubFrae的判斷，并且對判斷出的子框架逐個地進(jìn)展刪除，而且因為SubFrae頁面的刪除導(dǎo)致后面必須用提升的站點構(gòu)造，雖然較一般預(yù)處理技術(shù)增加了興趣度，但是效率還是比擬低的，而且也增加了

9、開銷。并且SubFrae過濾中被刪去，在后面的途徑補(bǔ)全中能否完全恢復(fù)也值得高榷。而且有快速分類性質(zhì)允許多粒度層的決策樹分類算法可以解決此問題。本文在此用決策樹算法13中著名的ID3算法對進(jìn)步Frae過濾效率進(jìn)展了一些討論3.1ID3算法13的描繪ID3算法的根本思想是貪心算法，采用自上而下的分而治之的方法構(gòu)造決策樹。首先檢測訓(xùn)練數(shù)據(jù)集的所有特征，選擇信息增益最大的特征A建立決策樹根節(jié)點，由該特征的不同取值建立分枝，對各分枝的實例子集遞歸，用該方法建立樹的節(jié)點和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類別，或者沒有特征可以在用于對數(shù)據(jù)進(jìn)展分割。算法描繪如下：算法：Generate-deisin_tr

10、ee由給定的訓(xùn)練數(shù)據(jù)集產(chǎn)生一棵決策樹。輸入：訓(xùn)練樣本Saples，由離散值屬性表示；候選屬性的集合attribute_list輸出：一棵決策樹方法：1)創(chuàng)立結(jié)點N2)ifSaples都在同一類then3)返回N作為葉結(jié)點，以類標(biāo)記;4)ifattribute_list為空then5)返回N作為葉結(jié)點，標(biāo)記為Saples最普通的類；/使用多數(shù)表決。6)選擇attribute_list中具有最高信息增益(關(guān)于信息增益的求法請參見文獻(xiàn)3)的屬性test_attribute;7)標(biāo)記結(jié)點N為test_attribute;8)freahtest_attribute中值ai/劃分Saple;9)由結(jié)點N長

11、出一個條件為test_attribute=ai的分枝；10)設(shè)Si是Saple中test_attribute=ai的樣本集合/一個劃分11)ifSi為空then12)加上一個樹葉，標(biāo)記為Saples中最普通的類；13)else加上一個由Generate_deisin_tree(Si，attribute_list_返回的結(jié)點3.2基于ID3算法的Frae頁面過濾算法與效率分析輸入：FS表PidFrae，PidSubFrae對的集合;侯選屬性的集合attribute_list(包括index.htl，tp.htl，left.htl，ain.htl)輸出：一棵斷定樹freahusersessinus

12、erid，pid1，pid2，pidkurrentFrae=nullake_nde(eb)if(urrentFrae，Pidi)FS)ake_tree(urrentFrae，eb_left)elseif(PidiD(FS)urrentFrae=Pidiake_deitin_tree(urrentFrae，eb_right)elseake_deisitn_tree(urrent，eb_left)ifattribute_list=nullake_deitin_tree(urrentFrae，eb_right);elseifGain(nefattribute_list)allgain(attribu

13、te_list);/Gain()為信息增益函數(shù)urrentFrae=test_attribute;fraifeahtest_attributeifnt(test_attribute=ai)ake_desitin_tree(ai，eb_left)elsegenerate_deisin_tree(ai，eb_right)我們在這里認(rèn)為網(wǎng)頁上每個頁面都是eb頁面，所以它的信息增益最高，因此以它為根結(jié)點。urrentFrae變量記錄了當(dāng)前處理的頁面，假如當(dāng)前頁不是Frae頁面時那么將其添到左子樹中，否那么，即PidiD(FS)，那么將當(dāng)前頁面的標(biāo)識符Pidi賦給urrentFrae，并將其添加到右子樹

14、中，且將它包含的SubFrae頁面仍添加到左子樹中。因為我們感趣的頁面是Frae頁面，所以它的點擊率最高，其信息增益最大，因此我們將信息增益最大的總是添加到eb右子樹中，而當(dāng)前頁不符合Frae頁面屬性的就是SubFrae頁，將其添加到左子樹中。這樣，決策樹的右枝就是Frae，左枝就是SubFrae.很容易就完成了會話識別，并且因為SubFrae并沒有被刪去，因此在后面的途徑補(bǔ)充中將其復(fù)原就可以了。較之Frae過濾算法，此算法略去了提升站點構(gòu)造這一步，因此更大地進(jìn)步了進(jìn)步了日志數(shù)據(jù)預(yù)處理的速度及預(yù)處理結(jié)果的質(zhì)量。3.3數(shù)據(jù)分析用長度為9B的日志，其中包含10萬條記錄。日志數(shù)據(jù)中有417個不同的H

15、TL頁面，從中識別出1902個用戶會話。通過挖掘頻繁訪問頁組比擬一般數(shù)據(jù)預(yù)處理技術(shù)Frae頁面過濾預(yù)處理技術(shù)和基于ID3頁面過濾預(yù)處理技術(shù)。其算法比擬如下表方法絕對支持度|FG1|FG2|FG3|FG4|FG5|FG6|FG7|一般技術(shù)7023578060243*6024779465254*Frae改良技術(shù)302331162+155510072203+基于ID3的Frae改良技術(shù)20243110+11065755510+說明：絕對支持度：指包含頻繁訪問頁組的最小用戶會話個數(shù)|FGi|：長度為i的頻繁訪問頁組的數(shù)目*：表示發(fā)現(xiàn)的頻繁訪問頁組是用戶不感興趣的+：表示發(fā)現(xiàn)的頻繁訪問頁組是用戶較感興趣的+：表示發(fā)現(xiàn)的頻繁訪問頁組是用戶感興趣的上述數(shù)據(jù)說明，通過在eb日志預(yù)處理階段增加ID3算法進(jìn)展Frae過濾步驟后，其日志數(shù)據(jù)預(yù)處理結(jié)果的質(zhì)量比一般技術(shù)及Frae改良技術(shù)都高，因此更大程度地進(jìn)步了挖掘結(jié)果的興趣性。而且由于算法本身的性質(zhì)及在途徑補(bǔ)充步驟中減少了提升站點構(gòu)造這一步，因此也極大地進(jìn)步預(yù)處理的效率，并由此搞高了整個eb日記挖掘的效率。文中用決策樹算法中的ID3算法改良了Frae過濾算法。經(jīng)歷證，在通過過濾原始日志數(shù)據(jù)中閱讀器自動在顯示Frae頁面時向效勞器懇求的SubFrae頁面，對存在Frae頁面的網(wǎng)站施行eb日志挖掘算法時，基于ID3算法的Frae頁面過濾技術(shù)進(jìn)一步進(jìn)步了對