基于網頁日志的頻繁模式挖掘

摘 要:頻繁模式挖掘應用廣泛，是數據挖掘中的一個重點研究領域，頻繁模式挖掘應用的其中一個領域就是基于網頁日志的數據挖掘。在網頁日志中發現頻繁模式的目的是獲得用戶的網絡瀏覽行為模式，這些信息可以為廣告設計以及創建動態用戶日志提供參考。從網頁數據挖掘的角度研究了三種頻繁模式挖掘方式，這三種方式分別是:網頁設置、網頁序列以及網頁圖片挖掘。

關鍵詞:模式挖掘; 序列挖掘; 圖形挖掘; 網頁日志挖掘

中圖分類號:TP29 文獻標識碼:A

文章編號:1004-373X(2010)09-0180-04

Frequent Pattern Mining in Web Log Data

SHEN Ming， DENG Yu-fen， ZHANG Bo

(Navy Oceanic Mapping and Survey Institute， Tianjing 300061， China)

Abstract: Frequent pattern mining is an important research field in data mining with wide application， one of the fields is the data mining based on Web log data. The aim of discovering frequent patterns in Web log data is to obtain information about the navigational behavior of the users， the information can provide references for advertising purpose and creating dynamic user profiles. Three pattern mining approaches are investigated from the Web data mining， the different patterns in Web log mining are page set， page sequence and page graphs mining.

Keywords: pattern mining; sequence mining; graph mining; Web log mining

0 引 言

萬維網提供了大量對用戶有用的數據，不同類型的數據應該組織成能夠被不同用戶有效使用的形式，因此，基于網頁的數據挖掘技術吸引了越來越多的研究人員。已有幾種數據挖掘方法應用于挖掘隱藏在網頁中的信息，當然算法需要進一步調整以適應網頁數據的屬性。而且，不只是數據挖掘算法，還有人工智能，信息獲取，以及自然語言處理技術都可以在數據挖掘中得到有效應用。因此，網頁挖掘技術已經伸展到自動研究領域。

本文主要介紹基于網頁日志的幾種不同類型的數據挖掘技術，這些挖掘技術用于挖掘隱藏在網頁中的不同的頻繁模式。包括:頻繁模式、序列態以及樹態。對于每個問題，都有相應的算法，用于高效挖掘相應的模態。頻繁模式(高頻網頁)挖掘采用文獻[1]中介紹的頻繁模式算法。頻繁模式算法的主要優勢在于可以快速挖掘低頻繁模式頁，對于更高頻繁模式的挖掘效果也得到了增強。序列挖掘算法采用文獻[2]中介紹的SM-樹算法，其中可以有效發現樹型模式的算法稱之為PD樹算法。兩種算法都可以充分利用自動化理論發現其中的頻繁模式。SM樹算法采用狀態機發現序列模式，PD樹算法采用疊加自動機確定在樹形數據庫中三種模式。

1 網頁挖掘任務

網頁挖掘包括:從網頁數據中發現和提取信息;提供有效的機制以使數據訪問更加有效和匹配;從用戶行為中發現信息，用戶行為信息一般存儲在網頁日志中，比如網頁緩存[3]。因此網頁挖掘可以根據需要挖掘的信息分為三類[4-6]，分別是:網頁內容挖掘，網頁結構挖掘和網頁使用方式挖掘。網頁挖掘的相關詳細研究請參考文獻[4-5，7-8]。

網頁內容挖掘的任務是在線發現有用信息。對用戶有用的信息包括:多媒體數據，結構化(XML)和半結構化數據(HTML)，以及非結構化數據(如文本)。網頁內容挖掘的目的是建立一個幫助用戶發現他們需要的信息的機制。網頁內容挖掘包括:組織和聚類文檔，提供相應的引擎以便用戶通過相關的關鍵詞信息、分類信息以及內容信息等獲取不同的文檔。

網頁結構挖掘[9-12]的目的是發現內嵌于網頁中超鏈接。實際上，網頁內容挖掘關注文檔內部信息，網頁結構挖掘則關注文檔之間的鏈接結構信息，其目的是為了標識相關主題的權威或者中心網頁。權威網頁包含了有用的信息，通過幾個鏈接指向它，這意味著這些網頁被引用頻度很高。一個擁有很多鏈接的網頁可以認為其內容是有用的、更好的和可靠的。中心網頁是指包含許多到權威網頁的鏈接的頁面，因此中心網頁有助于集中權威網頁。網頁結構挖掘可以通過門戶網頁或者整個網頁獲得。網頁結構挖掘也支持網頁內容挖掘，通過獲得網頁結構信息，可以更加有效地獲取文檔，發現文檔的可靠性和相關性也可以更好。網頁的圖形結構可以通過網頁結構挖掘實現，網頁的圖形結構挖掘可以提高信息獲取的能力，并提高文檔的分類效果。

網頁使用模式挖掘是指發現用戶瀏覽和轉換網頁的行為特征，其目的是通過理解用戶轉換網頁的喜好增強電子商務的服務質量，個性化門戶網站，或者提高網頁結構和網絡服務器的性能[13-14]。這種情況下，挖掘的數據對象是可以選擇作為網頁上的間接數據的網頁日志，其中通過網頁訪問的文檔可以理解為初始數據。

有三種類型的網頁日志可以用作數據挖掘的對象:存放在服務器端的日志數據，客戶端的日志數據，以及存放在代理服務器上的數據。由于不止一個地方存儲著用戶瀏覽網頁的信息，因此使數據挖掘過程變得困難。真實可靠的數據挖掘結果是建立在以上三種數據俱全的基礎上的。這是由于服務器端的數據并不包含存儲在代理服務器或者客戶端的數據，除了服務器端的數據，代理服務器還存儲了其他的信息。然而，存放在客戶端的網頁請求方面的數據是缺失的。但是，客戶端的所有信息是難以收集完整的。因此，大多數算法是基于服務器端數據的。一些應用在網頁使用模式挖掘的常用的數據挖掘算法包含:規則挖掘，序列挖掘，以及聚類挖掘[15]。

2 網頁使用模式挖掘

網頁使用模式挖掘，從數據挖掘的角度來看，就是將數據挖掘技術應用到網頁數據中，從而發現使用模式，為更好理解用戶瀏覽網頁的需要服務[16]。類似于其他的數據挖掘過程，網頁數據挖掘過程包括三步:數據預處理;模式發現;模式分析。

本文所說的模式發現是指將前面介紹過的模式發現方法應用到網頁日志上。為此，首先需要將數據進行預處理以使處理后的數據能夠符合算法輸入的格式。模式分析是指解釋數據挖掘結果，并作出相應的結論。

圖1顯示了網頁使用模式挖掘的實現過程，這個過程的輸入數據為日志數據。這些數據需要進行預處理，以使其符合算法所需的輸入數據格式。不同的算法需要的輸入數據格式也不同，圖中所示的預處理過程可以提供三種類型的輸入數據。

圖1 網頁使用模式挖掘流程

頻繁模式發現過程僅需要用戶提供的網頁數據。這種情況下，網頁序列是不相關的。相同網頁的重復瀏覽也可以忽略，網頁調用是預先定義的。

在序列挖掘中，網頁瀏覽序列是重要信息，同一網頁如果在規定時間內被用戶瀏覽多次，則每次都是相關網頁。因此整個系統的預處理模塊提供了用戶瀏覽網頁的序列信息。

對于用戶模式樹挖掘，則不僅需要網頁瀏覽序列信息，還需要被訪網頁的結構信息。這種情況下，后退瀏覽可以忽略，只有前向瀏覽是相關的，這樣，針對每個用戶就形成了一顆樹。發現過程完成后，下面的事情就是模式分析。通過圖1的反饋回路看出整個挖掘過程是一個迭代的任務過程。根據分析結果，可以調整預處理參數(比如重新選擇時間間隔)，或者調整數據挖掘算法的相關參數(這意味著需要設定數據挖掘的最小門檻值)。

本文中的網頁使用模式挖掘的目的是發現在同一時間內訪問頻率最高的網頁，發現用戶瀏覽網頁的次序。其結果用于幫助確定門戶網頁的結構，從而更好地滿足廣告要求，提供更加個性化的網頁門戶。

3 相關工作

網頁使用模式挖掘過程中，有幾種數據挖掘算法可以利用。關聯規則挖掘用于發現即使沒有直接聯系也被用戶一同訪問的網頁，這可以發現組用戶之間相關的特殊興趣[13]。比如這些信息可以用于重組網站結構，如增加關聯網頁之間的鏈接。關聯規則挖掘可以參見文獻[17-20]。網頁序列挖掘可以用于發現用戶瀏覽相關網頁后緊接著瀏覽的網頁。利用這些知識就可以預測用戶瀏覽網頁的下一個行為，并預測下一個將被訪問的網頁。網頁序列挖掘在文獻[14]中有詳細介紹，稱之為WAP樹挖掘，樹形拓撲模式和頻率路徑轉換關系可以參見文獻[17]。

網頁使用模式挖掘在許多方面都是復雜的，這個過程中不僅使用數據挖掘技術，還使用了其他的技術。比如，文獻[6]中采用了稱之為Ngram模型的概率語法技術，通過該模型可以發現用戶網頁瀏覽行為模式。Ngram模型假設前面N次瀏覽的網頁影響第N+1次瀏覽的網頁。網頁預測可以采用網頁日志挖掘技術或者馬爾可夫預測器。

4 挖掘算法總結

在研究網頁使用模式挖掘過程之前，以及在解釋重要的挖掘步驟之前，首先需要簡要介紹頻繁模式挖掘算法。理解挖掘機制對于理解挖掘結果是必要的。另外一個重要的方面是，確定算法輸入參數，有助于數據預處理過程中明確合適的數據輸入格式。

就如前面所述，頻繁模式網頁是通過ItemSetCode算法完成的。這是基于先驗假設基礎上的一個備選挖掘算法。算法的目的是為了增強先驗假設在更低水平上的使用效果。這意味著，可以增強低頻繁模式網頁的發現。通過這種方法，也可以更快發現高頻繁模式的網頁。ItemSetCode的思想是將3階或者4階頻繁模式問題的規模降低到2階。ItemSetCode可以通過索引矩陣快速發現2階或者1階頻繁模式網頁。2階問題可以編碼解決，3階或者4階問題可以通過成對使用2階問題編碼解決。3階或者4階問題可以按照存儲結構要求進行存儲，這種方式可以保證高效的使用數組，而且，該結構對內存要求也很低，算法只是部分利用了先驗假設的好處，原因是必須使用壓縮存儲結構。ItemSetCode算法由于可以快速發現低頻繁模式頁，因此可以有效地發現高頻繁模式網頁，其獨立于問題層次的特點可以保證內存需求與事務多少無關。ItemSetCode算法輸入數據格式也可以適用于其他頻繁模式挖掘算法。它以行序讀取事務，每行包括了多個數據項。

網頁瀏覽次序挖掘可以使用SM樹算法[2]。SM樹算法的主要思想是在輸入項目的次序只處理一次的情況下測試子序列，算法的應用基礎是狀態有限機。通過聯合幾個自動機，一種稱之為SM樹的結構可以建立起來，該結構可以比采用不同的狀態機分別處理每個候選數據更快地處理候選數據?；谶@個特點，SM樹結構可以得到有效的處理。這個可以通過利用兩種類型的狀態的優勢，如固定狀態和臨時狀態獲得。算法更大的優勢在于其內存需求獨立于事務的個數。SM樹算法的輸入格式包含行事務，其中每行包含了數據項的序列信息。

5 數據處理

存儲在服務器端的記錄用戶行為的網頁日志數據不能夠以其存儲的格式直接應用到數據挖掘中。因為這一點，數據預處理過程必須在模式發現過程之前進行。

數據預處理過程分為三步:首先，收集的數據必須進行凈化，即刪除圖形和多媒體數據。其次，需要將不同的數據分屬到不同的用戶。當用戶在指定網點瀏覽網頁時，一次會話理解為該用戶的一組行為。從原始數據中標識會話是一個復雜的過程，因為服務器端并不總是存儲了所有必需信息。有些服務器端的網頁日志沒有存儲足夠的信息重建用戶會話過程，在這種情況下，可以使用面向時間的啟發式方法。會話經過標識后，數據預處理過程的第一步，網頁瀏覽次序也就決定了。最后，需要將數據轉化到挖掘算法需要的格式。如果會話和次序標識完畢，第三步的完成將簡便許多。

在本文的實驗中，使用了兩種網頁服務器日志，第一種來自msnbc.com 的異步數據，第二種從ECML/PKDD 2005 Discovery Challenge下載的鼠標單擊流數據。兩種數據的格式都不一樣，因此數據預處理過程也不一樣。

Msnbc日志數據記錄了用戶于1999.9.28訪問Msnbc網站的網頁信息。訪問按照時間先后序列以URL的形式記錄。這意味著預處理數據過程的第一步可以忽略。數據來自msnbc.com中的IIS日志。每一行對應用戶在24 h內訪問的網頁。網頁編碼格式如表1所示。客戶端緩存數據沒有記錄，因此這些數據主要包含服務器端日志數據。

這種情況下，只需要將msnbc的行數據轉換為相應的數據項網頁瀏覽次序和樹形結構，則另外一個數據預處理的步驟已經執行。轉換過程中忽略重復的網頁，因此直接按照編碼序列進行排列。這樣，ItemSetCode算法可以在數據表中執行。

表1 msnbc.com網頁分類編碼

類別編碼類別編碼類別編碼

主頁1音樂7匯總13

新聞2天氣8BBS14

技術3健康9旅行15

當地4生活10MSN新聞16

觀點5商務11MSN運動17

在線6運動12

為了獲得網頁序列模式，行數據轉換結果必須體現網頁瀏覽次序。一行實際上代表其中一個數據項的次序。因此，轉換為SM樹算法需要的序列格式意味著在每個代碼之間插入一個值-1。

為了能夠挖掘樹形模式，數據必須轉換為樹形事務格式。基于這個原因，每行按照以下的方式進行處理:根為行數據的第一個數據項。從根數據項可以生成分支，直到相應的數據項已經插入樹中。這種情況下，算法共插入的-1值的個數等于新數據項前面出現的相同數據項之間數據項個數。更多的數據項形成新的分支。比如對給定行:“1 2 3 4 2 5”，則對應行的樹形表示為“1 2 3 4 -1 -1 5”。

鼠標單擊流數據中，數據預處理過程需要更多的工作。包含546個文件，其中每個文件包含了1 h之內的所有用戶行為信息。每一行包含以下部分:

店名，時間，IP地址，惟一的會話標識符，訪問網頁，參考。

6 數據挖掘和模式分析

就如圖1所示的，網頁使用模式挖掘需要完成所有三種頻繁模式挖掘任務。對于挖掘過程，除了輸入數據，還需要設置最小的門檻值，這是關鍵之一。用戶交互和迭代過程需要持續下去，直到發現合適的數值為止。由于這個原因，在挖掘過程中需要用戶交互，建議在整個數據庫中迭代執行頻繁模式挖掘算法。選擇大小合適的數據樣本，如果數據樣本準確反映數據庫，程序響應時間很短。

頻繁模式數據項發現和關聯規則挖掘可以使用ItemsetCode算法完成，ItemsetCode同樣需要設置最小的支持門檻值和最小的可信度值。圖2顯示了根據msnbc.com網站的數據挖掘的關聯規則，其最小支持門檻值為0.1%，可行度門檻值為85%。通過分析其挖掘結果，用戶可以更好地確定廣告方式，以及門戶網頁結構。

圖2顯示了將SM樹算法應用到msnbc.com數據的挖掘結果，圖2(b)中的百分比值即為支持門檻值。

圖2 基于msnbc.com網站的數據挖掘

7 結 語

主要討論了如何從服務器端的網頁日志數據挖掘潛在有用信息的問題。文中主要介紹了網頁日志數據挖掘的過程，以及如何通過將頻繁模式模式挖掘算法應用到網頁日志數據挖掘中，獲得關于用戶瀏覽網頁的有用信息。

參考文獻

[1]IVNCSY R， VAJK I. Time-and memory-efficient frequent itemset discovering algorithm for association rule mining[J]. International Journal of Computer Application in Techology， 2005， 3(10): 213-217.

[2]IVNCSY R， VAJK I. Efficient sequential pattern mining algorithms[J]. WSEAS Trans. on Computers， 2005， 4(2): 96-101.

[3]YANG Q， ZHANG H H. Web-log mining for predictive web caching[J]. IEEE Trans. on Knowl. Data Eng.， 2003， 15(4): 1050-1053.

[4]BLOCKEEL Kosala. Web mining research[J]. ACM， 2000， 1(2):15-20.

[5]MADRIA S K， BHOWMICK S S. Research issues in web data mining[J]. Data Warehousing and Knowledge Disco-very，1999: 303-312.

[6]BPRGES J， LEVENE M. Data mining of user navigation patterns[J]. WEBKDD， 1999: 92-111.

[7]GAROFALAKIS M N， RASTOGI R， SESHADRI S， et al. Data mining and the web: past， present and future[C]// ACM CIKM′99 2nd Workshop on Web Information and Data Management， USA: [S.n.]， 1999: 43-47.

[8]CHAKRABARTI S. Data mining for hypertext[J]. ACM， 2000，1(2): 1-11.

[9]CHAKRABARTI S， DOM B， INDYK P. Enhanced hypertext categorization using hyperlinks[C]// SIGMOD ′98: Proceedings of the 1998 ACM SIGMOD international conference on Management of Data， New York: ACM Press， 1998: 307-318.

[10]KLEINBERG J M， KUMAR R， RAGHAVAN P， et al. The Web as a graph: measurements， models and methods[J]. Lecture Notes in Computer Science，1999，1627: 1-18.

[11]HOU J， ZHANG Y. Effectively finding relevant web pages from linkage information[J]. IEEE Trans. on Knowl. Data Eng.，2003，15(4): 940-951.

[12]HAN H， ELMASRI R. Learning rules for conceptual structure on the web[J]. Intell. Inf. Syst.， 2004， 22(3): 237-256.

[13]EIRINAKI M， VAZIRGIANNIS M. Web mining for web personalization[J]. ACM Trans.on Inter. Tech.， 2003， 3(1): 1-27.

[14]PEI J， HAN J， MORTAZAVI-Asl B， et al. Mining access patterns efficiently from web logs[C]// PADKK ′00: Proceedings of the 4th Pacific-Asia Conference on Know-ledge Discovery and Data Mining， Current Issues and New Applications， London: Springer-Verlag， 2000: 396-407.

[15]COOLEY R， MOBASHER B， SIRIVASTAVA J. Data preparation for mining world wide web browsing patterns[J]. Knowledge and Information Systems， 1999，1(1): 5-32.

[16]SRIVASTAVA J， COOLEY R， DESHPANDE M， et al. Web usage mining: discovery and applications of usage patterns from web data[J]. SIGKDD Explorations， 2000， 1(2): 12-23.

[17]CHEN M S， PARK J S， YU P S. Data mining for path traversal patterns in a web environment[C]. Sixteenth International Conference on Distributed Computing Systems， 1996: 385-392.

[18]PUNIN J， KRISHNAMOORTHY M， ZAKI M. Web usage mining: languages and algorithms in Studies in Classification， data analysis， and knowledge organization[M]. [S.l.]: Springer-Verlag， 2001.

[19]ZAIANE O R， XIN M， HAN J. Discovering web access patterns and trends by applying olap and data mining technology on web logs[C]// ADL '98: Proceedings of the Advances in Digital Libraries Conference， USA: IEEE Computer Society， 1998: 1-19.

[20]SHEN Li， CHENG Ling， STEINBERG T. Steinberg. Mining the most interesting web access associations[C]. WebNet 2000-World Conference on the WWW and Internet， 2000.

[21]IVNCSY R， VAJK I. PD-tree: a new approach to subtree discovery[J]. WSEAS Trans. on Information Science and Applications， 2005， 2(11): 1772-1779.

[22]BALABANOVIC M， SHOHAM Y. Shoham. Learning information retrieval agents:Experiments with automated web browsing[J]. Proceedings of the AAAI Spring Symposium on Information Gathering from Heterogenous，Distributed Resources， 1995: 13-18.