無為

??????????????????????????????????????????????????????????? 周 競 揚
???????????????????????????? MG0133041
??????????????????????????? 南京大學計算機科學與技術系分布式與并行系統實驗室
???????????????????????????? 江蘇 南京 210093
摘 要基于WEB 的數據挖掘是當前相當熱門的方向之一本文對此作了一個比較全面的
綜述概括了基于WEB 的數據挖掘的主要概念和特點說明各類WEB 挖掘尤其
是基于WEB 使用的挖掘所常用的技術最后簡單介紹了XML 在基于WEB 數據
挖掘中的應用
關鍵字基于WEB 的數據挖掘 基于WEB 使用的數據挖掘 半結構化 XML

Abstract: As web mining is one of the hottest research fields presently, this survey introduces itsbasic concepts and characteristics, including semi-structured data model. Three types ofweb mining and their applications are discussed in this paper, especially the web usagemining. Using XML in web mining is also stated in the last of the article.
Keywords: Web Mining Web Usage Mining Semi-structured XML

?????? 我們現在已經生活在一個相當數字化的時代中,通信、計算機和網絡技術正極大地影響著整個人類社會。然而，海量信息既給人們帶來方便也帶來了許多問題使我們驚嘆信息爆炸的同時，又不得不面對知識貧乏的苦惱信息過量難以消化信息真假難以辨別，信息安全難以保證，信息形式相異難以統一處理。人們開始考慮：“如何才能不被信息淹沒，而是從中及時發現有用的知識、提高信息利用率。”面對這一挑戰，數據挖掘技術應運而生，并得到長足的發展，顯示出了強大的生命力.
??????? 所謂數據挖掘Data Mining 就是從大量的、不完全的、有噪聲的、模糊的、隨機的原始數據中提取隱含在其中的、事先未知的、但又是潛在有用的信息和知識的過程[1] 。數據挖掘的誕生是人們對數據庫技術進行長期研究和開發的結果，而數據挖掘技術發展的同時它又反過來促使數據庫技術進入了一個更高級的階段：傳統的數據環境基本上是數據操作型的傳統的信息系統只負責數據的增刪及修改操作而在數據庫的基礎上可實現的工作就是OLTP （OnLine Transaction Process 聯機事務處理）。現在由于數據積累的不斷增多，人們需要分析型的數據環境，于是就出現了由數據庫導出的數據倉庫，以此為基礎則可以實現OLAP （OnLine Analysis Process 聯機分析處理）：隨著海量數據搜集的可能計算機處理技術的增強和先進數據挖掘算法的提出，數據挖掘技術不僅能對過去的數據進行查詢和遍歷，而且能夠找出過去數據之間潛在有價值的聯系并以一定的形式表現出來，從而極大的滿足了人們對知識的迫切需求。
??????? 數據挖掘基于的原始數據是形成知識的源泉，它既可以是結構化的如關系數據庫中的數據，也可以是半結構化的，如文本、圖形、圖像數據，甚至是分布在網絡上的異構型數據。本文將著重討論一種針對半結構化數據的挖掘—基于WEB 的數據挖掘，主要介紹了它的基本概念以及經常采用的技術最后簡單說明了XML 在其中的應用。
一、 基于WEB 的數據挖掘的主要概念
1、 什么是基于WEB 的數據挖掘
??????? 當前網絡發展迅速，各種網站比比皆是。但在競爭日益激烈的網絡經濟中，只有贏得用戶，才能最終贏得競爭的優勢。作為一個網站的管理員或擁有者，應該知道用戶都在他的網站上干什么，知道網站哪些部分最為用戶喜愛，哪些讓用戶感到厭煩，什么地方出了安全漏洞，什么樣的改動帶來了顯著的用戶滿意度，提高什么樣的改動反而丟失了用戶等等。“知己知彼”，才能“百戰不殆”。而基于WEB 數據挖掘技術正能滿足這些需求。
??????? 就基于WEB 數據挖掘的確切定義，到目前為止還沒有很明確而權威的說法。國外有認為：基于WEB 數據挖掘，就是利用數據挖掘技術自動地從網絡文檔以及服務中發現和抽取信息的過程。國內則眾說紛紜，有認為是在大量已知數據樣本的基礎上得到數據對象間的內在特性，并以此為依據在WEB 中進行有目的的信息提取過程。同時，也有學者將網絡環境下的數據挖掘歸入網絡信息檢索與網絡信息內容的開發等等。總之，基于WEB 的數據挖掘（Web Mining） 正是從萬維網（World Wide Web ）上獲取原始數據中從中挖掘出隱含其中且潛在可用的知識最終應用于商業運作以滿足管理者的需要。
2 、基于WEB 數據挖掘的分類
根據挖掘的對象不同我們可以把基于WEB 的數據挖掘分為三大類：
???基于WEB 內容的挖掘（Web Content Mining）
?? 基于WEB 結構的挖掘（Web Structure Mining）
?? 基于WEB 使用的挖掘（Web Usage Mining）
（1）基于WEB 內容的挖掘
??????? 所謂基于WEB 內容的挖掘實際上就是從WEB 文檔及其描述中獲取知識, WEB 文檔文件挖掘以及基于概念索引或Agent 技術的資源搜索也應該歸于此類。Web 信息資源類型眾多，目前WWW 信息資源已經成為網絡信息資源的主體，然而除了大量的人們可以直接從網上抓取、建立索引、實現查詢服務的資源之外，相當一部分信息是隱藏著的數據（如由用戶的提問而動態生成的結果，存在于數據庫系統中的數據，或是某些私人數據）無法被索引，從而無法提供對它們有效的檢索方式，這就迫使我們把這些內容挖掘出來。若從信息資源的表現形式來看，WEB 信息內容是由文本、圖像、音頻、視頻、元數據等種種形式的數據組成的，因而我們所說的基于WEB 內容的挖掘也是一種針對多媒體數據的挖掘。
2 、基于WEB 結構的挖掘
?????? 這一類型的挖掘是從萬維網的整體結構和網頁上的相互鏈接中發現知識的過程，它主要挖掘WEB 潛在的鏈接結構模式。這種思想源于引文分析，即通過分析一個網頁鏈接和被鏈接數量以及對象來建立WEB 自身的鏈接結構模式。這種模式可以用于網頁歸類并且可以由此獲得有關不同網頁間相似度及關聯度的信息。WEB 結構挖掘有助于用戶找到相關主題的權威站點，而且對網絡資源檢索結果的排序有很大意義。
3、 基于WEB 使用的挖掘
??????? 基于WEB 使用的挖掘，也稱為WEB 日志挖掘（Web Log Mining）。與前兩種挖掘方式以網上的原始數據為挖掘對象不同，基于WEB 使用的挖掘面對的是在用戶和網絡交互的過程中抽取出來的第二手數據。這些數據包括：網絡服務器訪問記錄、代理服務器日志記錄、用戶注冊信息以及用戶訪問網站時的行為動作等等。WEB 使用挖掘將這些數據一一紀錄到日志文件中，然后對積累起來的日志文件進行挖掘，從而了解用戶的網絡行為數據所具有的意義。我們前面所舉的例子正屬于這一種類型。
????????表1[2]從五個方面對三種挖掘形式做了比較其中的具體內容下文將會作進一步介紹。
??????????基于WEB 內容的挖掘：非結構化 半結構化\文本文檔 超文本文檔\Bag of words n-grams 詞短語 概念或實體 關系型數據\TFIDF 和變體機器學習統計學(包括自然語言處理)\歸類 聚類發掘 抽取規則 發掘文本模式 建立模式.
?????????? 基于WEB 結構的挖掘:半結構化 數據庫形式的網站 鏈接結構\超文本 文檔鏈接\邊界標志圖 OEM 關系型數據 圖形\Proprietary 算法 ILP (修改后)的關聯規則\發掘高頻的子結構 發掘網站體系結構 歸類 聚類.
????????? 基于WEB 使用的挖掘:交互形式\服務器日志記錄 瀏覽器日志記錄\關系型表 圖形\Proprietary 算法 機器學習 統計學 (修改后的）關聯規則\站點建設 改進與管理 銷建立用戶模式.
3、 基于WEB 數據挖掘的特點
（1） 、什么是半結構化
?????? 所謂半結構化是相對于結構化和非結構化而言的。我們稱傳統數據庫中的數據為完全結構化的數據，而同時還存在著一些諸如一本書、一張圖片等完全無結構的非結構化數據。半結構化則是介于兩者之間，具有隱含模式、信息結構不規則、無嚴格類型約束等特點。半結構化數據模式有如下特征[4]
????? 先有數據，后有模式；
????? 半結構化數據的模式是用于描述數據的結構信息，而不是對數據結構進行強制性的約束；
???? 半結構化數據的模式是非精確的，它只可能描述數據的一部分結構，也可能根據數據處理的不同階段的視角不同而異；
???? 半結構化數據的模式，可能規模很大甚至超過源數據的規模，而且會由于數據的不斷更新而處于動態變化過程中。
（2）、 WEB 數據的特點
??????? Web 上的數據最大特點就是半結構化。但是Web 上的數據與傳統的數據庫中的數據不同，傳統的數據庫都有一定的數據模型，可以根據模型來具體描述特定的數據而且按照一定的組織有規律的集中或者分布存放，結構性很強；而Web 上的數據非常復雜，沒有特定的模型描述每一站點的數據，都各自獨立設計并且數據本身具有自述性和動態可變性，因而Web 上的數據不是強結構性的。但與此同時Web 頁面又是有描述層次的，單個網站也是按照各自的結構構架的，從而具有一定的結構性。因此我們認為Web 上存在的數據既不是完全結構化的也不是完全非結構化的，而是介于兩者之間，一般稱之為半結構化數據。
??????? 半結構化是Web 上數據的最大特點，顯然面向Web 的數據挖掘比面向單個數據倉庫或者其他結構化數據集的數據挖掘要復雜得多。
4、使用基于WEB 數據挖掘能得到什么
??????? Web Mining 技術已經應用于解決多方面的問題，比如基于WEB 內容和結構的挖掘極大的幫助了我們從浩瀚的網絡資源中更加快速而準確的獲取所需要的資料，而基于使用的數據挖掘之威力，更是在商業運作上發揮的淋漓盡致，具體表現在：
（1） 對網站的修改能有目的有依據穩步的提高用戶滿意度
發現系統性能瓶頸，找到安全漏洞，查看網站流量模式，找到網站最重要的部分，發現用戶的需要和興趣，對需求強烈的地方提供優化，根據用戶訪問模式修改網頁之間的連接，把用戶想要的東西以更快且有效的方式提供給用戶，在正確的地方正確的時間把正確的信息提供給正確的人。
（2） 測定投資回報率
????? 測定廣告和促銷計劃的成功度
????? 找到最有價值的ISP 和搜索引擎
??????測定合作和結盟網站對自身的價值
（3） 提供個性化網站
????????? 對大多數WEB 應用來說，讓用戶感到真個網站是完全為他自己定制的個性化網站，是WEB 站點成功的秘訣。針對不同的用戶完全按照其個人的興趣和愛好（數據挖掘算法得到的用戶訪問模式）向用戶動態的提供要瀏覽的建議自動提供個性化的網站。
??????? 下面我們將就基于WEB 使用的挖掘，進一步討論它所經常采用的技術。
二、基于WEB 使用挖掘中的技術問題
1、 Web Usage Mining 中非技術問題
?????? 在基于使用的挖掘中，出于商業目的考量網站的擁有者或者管理者經常會對網站的某些方面提出一些分析，比如：流量分析（點擊量）、廣告分析、網站出入口分析、訪問路徑分析、用戶來源分析、瀏覽器和平臺分析等等。
?????? 就這些方面作進一步的智能分析，我們可以從中真正與數據挖掘相關的問題：
（1） 網頁相關性分析
?????? 哪些網頁具有密切的關系，如果很多人具有a.html-〉b.html-〉c.html 這樣的訪問模式，則我們可以認定a.html 和c.html 之間有一定的關系，從而考慮是否在a.html 上直接加上c.html的鏈接。
（2） 用戶訪問模式分析
??????? 有哪一些網頁用戶只要訪問了其中的一頁，則可以斷定他也要訪問其他的網頁即按不同的用戶訪問模式，把網頁分組得到一個一個的興趣點。哪些用戶所訪問的網頁組成比較類似（具有類似的興趣）即根據用戶行為的相似性，把用戶按行為模式分類。
（3） 用戶歸類
通過用戶填寫的信息如何把用戶歸入某一特定的類別，然后可對同一類別中的用戶提供相似的服務。
2 、Web Usage Mining 中的技術問題
（1） 數據處理
???????? 如何得到分析和數據挖掘所用的數據，主要采用兩種方法，一是直接使用Web Server的Log 文件，二是用網絡監聽的辦法，在數據包中提取出HTTP 請求和應答。最后兩種數據源都要轉換成固定的格式存放在數據庫或數據倉庫內，供統計分析和數據挖掘使用。
（2） 統計分析
????????? 在數據庫的基礎上，針對不同的數據運行各種統計函數。
（3） 數據挖掘
?????????? 數據挖掘技術是實現智能分析得到隱藏在大量繁雜數據內部知識的關鍵。通過對用戶訪問網站的歷史數據(即我們通過數據處理得到的數據)應用各種數據挖掘技術,得到高層知識，提供給用戶作決策支持，或利用這些知識動態生成網頁，為用戶提供訪問建議。
（4） 關聯規則Association Rules
?????????從服務器會話中發現請求網頁的相關性，可用于優化網站組織，實現網絡代理中的預取功能等。
（5） 聚集Clustering
???????? 使用分組（Usage Clusters ）把具有相似瀏覽模式的用戶分成組，可用于電子商務應用中市場分片（market segmentation） 和為用戶提供個性化服務，而網頁分組（page clusters ）按內容的相似性把網頁分類，可用于搜索引擎和Web 瀏覽助手（Web assistance providers ）為用戶提供推薦鏈接。
（6） 歸類Classification
????????? 根據用戶的個人資料，將其歸入某一特定的類，可使用決策樹、naive Bayesian
classifiers、 k-最近鄰居等算法。
（7） 序列模式Sequential Patterns
??????? 發現一個session 內部的網頁間的時間相關性，可用于預測用戶的訪問趨向而提供建議。
三、XML 技術在基于WEB 的數據挖掘中的應用
1 、XML 技術簡介
??????? XML （eXtsible Markup Language） 是SGML （Standard General MarkupLanguage ）的一個子集，近年來為IBM Microsoft 等公司大力推崇。和HTML（ Hyper Text Markup Language）類似，XML 也是一種標示語言，可提供描述結構化資料的格式，它們都可以用于可視化和用戶界面標準。
?????? 當前，Internet 只是文本和圖片的訪問媒體，并沒有智能搜索、數據交換、自適應表示和個人化的標準。為了超出設置信息訪問和顯示標準的限制，Internet 必須設置信息理解標準（表示數據的通用方式）以便軟件能夠更好地搜索移動顯示和處理上下文中隱藏的信息。由于 HTML 是一種描述如何表示 WEB 頁的格式，并不表示數據，所以它并不能完成以上處理。而 XML 提供了一種獨立的運行程序的方法來共享數據是用來自動描述信息的一種新的標準語言，它通過計算機通信“把Internet 的功能由信息傳遞擴大到人類其他多種多樣的活動中去”[3]。
2、技術的特點及其在Web Mining 中的應用
?????? 它最大的特點在于其Tag 是具有語義的，可由用戶定義能夠反映一定的數據的含義。此外，XML 還具有簡單易用、可擴展性、開發性、強標準化等特點,非常適合應用于WebMining 。從某種意義上說，XML 非常接近半結構化的數據模型它可供操作的基礎要比HTML 好得多。圖二是HTML 和XML 的文檔比較，我們不難看出XML 的文檔描述的語義非常清楚，而且我們很容易就可以將之和關系數據庫中的屬性一一對應起來，能夠支持實施十分精確的查詢，以及其他高級操作。而HTML 文檔只是按顯示方式進行描述的。由此可見，XML 將為在WEB 上的數據查詢和模式抽取提供了一個重要的契機。
?????? XML 由若干規則組成，這些規則可用于創建標記語言，并能用一種被稱作分析程序的簡明程序處理所有新創建的標記語言。XML 解決了HTML 不能解決的兩個Web 問題，即“Internet 發展速度快而接入速度慢”的問題，以及可利用的信息多但難以找到自己需要的那部分信息”的問題[3]。 XML 能增加結構和語義信息可使計算機和服務器即時處理多種形式的信息。因此，運用XML 的擴展功能不僅能從WEB 服務器下載大量的信息，還能大大減少網絡業務量。
????????以XML 為基礎的新一代WWW 環境是直接面對WEB 數據的，不僅可以很好地兼容原有的WEB 應用而且可以更好地實現WEB 中的信息共享與交換。XML 可看作一種半結構化的數據模型，可以很容易地將XML 的文檔描述與關系數據庫中的屬性一一對應起來，實施精確地查詢與模型抽取。
???????? 當用標準的HTML 無法完成某些WEB 應用時，XML 便能大顯身手這些應用從大的方面講可以被分成以下四類：需要WEB 客戶端在兩個或更多異質數據庫之間進行通信的應用；試圖將大部分處理負載從WEB 服務器轉到WEB 客戶端的應用；需要WEB 客戶端將同樣的數據以不同的瀏覽形式提供給不同的用戶的應用；需要智能WEB 代理根據個人用戶的需要裁減信息內容的應用。顯而易見，這些應用和WEB 的數據挖掘技術有著重要的聯系，基于WEB 的數據挖掘必須依靠它們來實現。
四、一些著名的Web Mining 產品簡介
1、Net percerptions
?????? Net Perceotion 公司的Net Percerptions ，采用了一個叫做實時建議的技術：讓它的產品對象（主要是網站）能夠根據用戶以往的瀏覽行為(比如以前的購買記錄) 在其他用戶（稱做Community 中）找出與他有相類似瀏覽行為的，根據這些用戶的瀏覽行為來預測該用戶以后的瀏覽行為，從而為用戶提供個性化的瀏覽建議。這種技術利用了網站用戶的瀏覽行為有相似的一面，因此其預言有很高的準確性。并且它是實時運行的，隨著瀏覽量的增加會變得越來越聰明。
2、 CommerceTrends
??????? WebTrends 公司的CommerceTrends 被宣稱為第一個用于VRM （Visitor Relationship Management） 的平臺，它能夠讓電子商務網站更好地理解其網站訪問者的行為，幫助網站采取一些行動來將這些訪問者變為顧客，將一次性的顧客變為長期的忠實顧客。?CommerceTrends 提供了完全的“browser-based” 方法，使得不同的部門（從市場部門到分析家）能在任何時間得到他所想得到的個性化報表。同時它還利用了強大的數據倉庫技術，這樣就不僅僅將原始數據存在數據庫里而是“Sessionizes ”了原始數據。
3. DBMiner
??????? 加拿大Simon Fraser 大學數據庫系統研究實驗室Database SystemResearchLaboratory
的知識發現研究組在數據挖掘技術領域經過多年的研究開發了名為DBMiner 的知識發現系統原型。它將機器學習方法學和數據庫技術結合起來，用于在大型數據庫和數據倉庫中交互地挖掘多層次的知識。該系統獨特之處在于緊密集成了聯機分析處理OLAP 和多種數據挖掘功能，包括特征化、關聯、分類和聚類。
五 結束語
??????????基于WEB 的數據挖掘是當前熱門研究方向之一，而且其應用范疇廣闊，潛力巨大；Web Mining 技術也在不斷提出和改進之中。但是Web Mining 技術還有很多缺陷和不足。我們還需要半結構化數據模型、Web 數據的過濾和轉換等方面作進一步研究，才能進一步發揮Web Mining 的無限威力

References
[1] Jiawei Han and Micheline Kamber Data Mining: Concepts and Techniques 2000 Morgan
Kaufmann Publishers
[2] 張 燕 淺談網絡信息挖掘
[3] 徐振航 劉莉芹 XML 與面向Web 的數據挖掘技術
[4] 王 靜 孟小峰 半結構化數據的模式研究綜述 計算機科學 2001 Vol. 28
[5] 於 丹 數據挖掘走向Internet 微電腦世界
[6] 王聰修 網絡數據挖掘
[7] What is Web Mining Lily BBS
[8] 李志鋒 網頁數據分析 天極網 2001.2
[9] Web Mining: 第二代網絡信息處理技術 Lily BBS
[10] 構造未來Web 頁面的工具語言XML Lily BBS