1、 數據倉庫技術在學生成績管理中的應用課程名稱 數據倉庫與數據挖掘 院（系） 計算機學院軟件學院 專 業 計算機科學與技術指導老師 班 級 姓 名 學 號 Web挖掘研究摘要 因特網目前是一個巨大、 分布廣泛、全球性的信息服務中心,它涉及新聞、廣告、消費信息、金融管理、教育、政府、電子商務和許多其它信息服務.Web包含了豐富和動態的超鏈接信息,以及Web頁面的訪問和使用信息,這為數據挖掘提供了豐富的資源.Web挖掘就是從Web文檔和Web活動中抽取感興趣的潛在的有用模式和隱藏的信息.對Web挖掘最新技術及發展方向做了全面分析,包括Web結構挖掘、多層次Web數據倉庫方法以及Web Log挖掘等.

2、關鍵詞 數據挖掘，Web挖掘，Web倉庫、Web Log挖掘，Web使用記錄挖掘RESEARCH ON WEB MINING: A SURVEYAbstract The World Wide Web serves as huge, widely distributed, global information service center for various applications. Web contains a rich and dynamic collection of hyperlink information and Web page access and usage inform

3、ation, providing rich sources for data mining.The goal of Web mining is to discover the access pattern and hidden information from the huge collection of documents plus hyperlink information, access and usage information. Given in this paper is an overview of Web mining techniques and new trends, ma

4、inly involving Web Structure mining, a multilayered Web information base building, and Web Log mining.Key words data mining,Web mining,Web warehouse,Web Log mining,Web ueage mining1引言60年代,大的物理流伴隨著大信息流.傳統的文件方式不能適應信息處理的需求, 因此出現了數據庫技術.90年代,人類積累的數據量以高于每月15%(或每年5.3倍)的速度增加,數據海洋不能產生決策意志,為了進行決策,人們不斷地擴大數據庫能力

5、,搜集海量數據,但這使得決策者更難于決策,因此出現了數據挖掘技術,以便從數據庫中發現知識.數據挖掘技術包括特征、分類、關聯、聚類、偏差、時間序列、趨勢分析等.近年來,Internet正以令人難以置信的速度在飛速發展, 越來越多的機構、團體和個人在Internet上發布信息、查找信息. 雖然Internet上有海量的數據 但由于Web是無結構的、動態的，并且Web頁面的復雜程度遠遠超過了文本文檔，人們要想找到自己想要的數據猶如大海撈針一般.信息檢索界開發了許多搜索引擎，但其覆蓋率有限，因此查全率低，一般的搜索引擎是基于關鍵字的查詢，命中率較低，另外不能針對特定的用戶給出特殊的服務，因為每個人感興

6、趣的東西是不一樣的，因此不具有個性化.解決這些問題的一個途徑，就是將傳統的數據挖掘技術和Web結合起來，進行Web挖掘.Web挖掘就是從Web 文檔和Web活動中抽取感興趣的潛在的有用模式和隱藏的信息.Web挖掘可以在很多方面發揮作用，如對搜索引擎的結構進行挖掘，確定權威頁面，Web文檔分類，Web Log挖掘，智能查詢，建立Meta-Web數據倉庫等.萬維網目前是一個巨大、分布廣泛、全球性的信息服務中心，它涉及新聞、廣告、消費信息、金融管理、教育、政府、電子商務和許多其它信息服務.Web還包含了豐富和動態的超鏈接信息，以及Web頁面的訪問和使用信息，這為數據挖掘提供了豐富的資源.然而從以下的

7、分析可以看出對Web進行有效的資源和知識發現具有極大的挑戰性.對有效的數據倉庫和數據挖掘而言Web似乎太龐大了.Web的數據量目前以兆兆字節(terabytes)計算，而且仍然在迅速地增長.許多機構和社團都在把各自大量的可訪問信息置于網上.這使得幾乎不可能去構造一個數據倉庫來復制、存儲或集成Web上的所有數據.最近，有一些工作在致力于存儲或集成Web上的所有數據.例如，在/index1.html下,可訪問到一個巨大的數十兆兆字節的因特網存檔.(1) Web頁面的復雜性高于任何傳統的文本文檔.Web頁面缺乏同一的結構,它包含了遠比任何一組書籍或其它文本文

8、檔多得多的風格和內容.Web可以看做一個巨大的數字圖書館;然而,這一圖書館中的大量文檔并不根據任何有關排列次序加以組織.它沒有分類索引,更沒有按標題、作者、扉頁、目次等的索引.在這樣一個圖書館中搜索希望得到的信息是極具挑戰性的.(2) Web是一個動態性極強的信息源.Web不僅以極快的速度增長,而且其信息還在不斷地發生著更新.新聞、股票市場、公司廣告和Web服務中心都在不斷地更新著各自的頁面.鏈接信息和訪問記錄也在頻繁地更新之中.(3) Web面對的是一個廣泛的形形色色的用戶群體.目前因特網上連接有約5千萬臺工作站，其用戶群仍在不斷地擴展當中.各個用戶可以有不同的背景、興趣和使用目的.大部分用

9、戶并不了解信息網絡結構，不清楚搜索的高昂代價，極容易在“黑暗”的網絡中迷失方向，也極容易在“跳躍式”訪問中煩亂不已和在等待信息中失去耐心.(4) Web上的信息只有很小的一部分是相關的或有用的.據說99%的Web信息相對99%的用戶是無用的.雖然這看起來不是很明顯，但一個人只是關心Web上的很小很小一部分信息確是事實，Web所包含的其余信息對用戶來說是不感興趣的，而且會淹沒所希望得到的搜索結果.這些挑戰已經推動了如何高效且有效地發現和利用因特網上資源的研究工作.Web挖掘是一個更具挑戰性的課題，它實現對Web存取模式、Web結構、規則和動態的Web內容的查找.2 Web挖掘的分類Web數據挖掘

10、可以分為Web內容挖掘,Web結構挖掘,Web使用挖掘三類。Web 內容挖掘是從文檔內容或其描述中抽取有用信息的過程,Web內容挖掘有兩種策略:直接挖掘文檔的內容和在其他工具搜索的基礎上進行改進。采用第一種策略的有針對Web的查詢語言WebLOG,利用啟發式規則來尋找個人主頁信息的AHOY 等。采用第二種策略的方法主要是對搜索引擎的查詢結果進行進一步的處理,得到更為精確和有用的信息。屬于該類的有WebSQL,及對搜索引擎的返回結果進行聚類的技術等。根據挖掘處理的數據可以將Web內容挖掘分為文本挖掘和多媒體挖掘兩個部分。Web結構挖掘是從Web組織結構和鏈接關系中推導知識。挖掘頁面的結構和Web

11、 結構,可以用來指導對頁面進行分類和聚類,找到權威頁面、中心頁面,從而提高檢索的性能。同時還可以用來指導頁面采集工作,提高采集效率。Web 結構挖掘可以分為Web文檔內部結構挖掘和文檔間的超鏈接結構挖掘。這方面的代表有Page Rank和CLEVER,此外,在多層次Web數據倉庫( MLDB )中也利用了頁面的鏈接結構。Web使用挖掘是從服務器端記錄的用戶訪問日志或從用戶的瀏覽信息中抽取感興趣的模式,通過分析這些數據可以幫助理解用戶隱藏在數據中的行為模式,做出預測性分析,從而改進站點的結構或為用戶提供個性化的服務。Web 挖掘相關技術：數據挖掘方法通常可以分為兩類:一類是建立在統計模型的基礎上

12、,采用的技術有決策樹、分類、聚類、關聯規則等;另一類是建立一種以機器學習為主的人工智能模型,采用的方法有神經網絡、自然法則計算方法等。Web 內容挖掘：1、Web 文本挖掘Web 文本挖掘可以對Web上的大量文檔的集合的內容進行總結、分類、聚類、關聯分析,以及利用Web 文檔進行趨勢預測。在Internet上的文本數據一般是一組html格式的文檔集,要將這些文檔轉化成一種類似關系數據庫中記錄的規整且能反映文檔內容特征的表示,一般采用文檔特征向量,但目前所采用的文檔表示方法中,都存在一個弊端就是文檔特征向量具有非常大的維數,使得特征子集的選取成為Internet上文本數據挖掘過程中的必不可少的一

13、個環節。在完成文檔特征向量維數的縮減后,便可利用數據挖掘的各種方法,如分類、聚類、關聯分析等來提取面向特定應用的知識模式,最后對挖掘結果進行評價,若評價結果滿足一定的要求則輸出,否則返回到以前的某個環節,分析改進后進行新一輪的挖掘工作。關聯規則模式數據描述型模式,發現關聯規則的算法屬于無監督學習的方法。發現關聯規則通常要經過以下3個步驟:連接數據,做數據準備;給定最小支持度和最小可信度,利用數據挖掘工具提供的算法發現關聯規則;可視化顯示、理解、評估關聯規則。目前Web內容挖掘研究主要集中在基于文本內容的檢索、信息過濾的提煉、重復數據消除、數據模式抽取、中間形式表示、異構集成、文本分類和聚類、文

14、檔總結和結構提取、數據倉庫及OLAP等幾個方面，尤其是基于XML的上述專題研究。對分類挖掘而言，在預處理階段要做的事情就是把這個Web頁面集合文本信息轉化成一個二維的數據庫表，其中每一列是一個特征，每一行為一個Web頁面的特征集合。在文本學習中常用的方法是TF工DF向量表示法，它是一種文檔的詞集(bag-of-words)表示法，所有的詞從文檔中抽取出來，而不考慮詞間的次序和文本的結構。構造這種二維表的方法是:每一列為一個詞，列集(特征集)為辭典中的所有有區分價值的詞，所以整個列集可能有幾十萬列之多。每一行存儲一個頁面內詞的信息，這時，該頁面中的所有詞對應到列集(特征集)上。列集中的每一個列(

15、詞)，如果在該頁面中不出現，則其值為0;如果出現k次.那么其值就為k。這樣就可以表征出頁面中詞的頻度。這樣構造的二維表表示的是Web頁面集合的詞的統計信息，最終就可以采用Naive Bayesian方法或k-Nearest Neighbor方法進行分類挖掘。WebSQL 是一個用于Web 頁重構的查詢語言,利用Web 文檔的圖樹表示形式,可從在線的文檔站點或導游指南中獲取信息。而Ahoy則利用像搜索引擎一類的互聯網服務來獲取與個人有關的服務,利用試探法識別文檔中顯示該文檔作為個人主頁的句法特征。分詞目前已有很多分詞算法，如：正向最大匹配法(MM)、逆向最大匹配法(RMM)、逐詞遍歷匹配法、設立

16、切分標志法、正向最佳匹配法和逆向最佳匹配法等。近幾年又提出了很多新的方法旨在提高分詞的精度和分詞的速度，如：生成測試法通過詞法ATN和語義ATN之間的相互作用來進行歧分決策，以提高分詞的精確性；改進的MM分詞算法采用正向增字最大匹配法和跳躍匹配法，結合詞尾語義檢查和歸右原則以消除類型歧義；基于神經網絡的分詞方法嘗試利用神經網絡來處理歧分問題，但同時又引入一個問題：訓練樣本的選取，由于自然語言的復雜性，如何選取訓練樣本還需要作深入的研究；結合直接匹配算法、后綴分詞算法和詞表結構支持首字Hash的方法，局部提高了速度，但不能進行標準的二分查找；支持首字Hash的近鄰匹配算法利用最大增字匹配算法，并

17、支持首字Hash和標準二分查找以提高分詞速度。分詞的基本算法有: (1)基于詞典與規則匹配法。基于詞典與規則的方法應用詞典匹配, 漢語詞法或其它漢語語言知識進行分詞, 這類方法簡單、分詞效率較高,但對詞典的完備性、規則的一致性等要求比較高。匹配策略有: 最大匹配法、最小匹配法、逆向匹配法、增字或減字匹配法、雙向掃描法。(2)標志法。如切分標志法、統計標引法。(3)詞頻統計法?；诮y計的分詞方法將漢語基于字和詞的統計信息, 完備性較差。(4)語義語用法。如后綴分詞法。目前使用最多的是基于詞庫的分詞方法。由于中文在分詞時可能產生二義性, 如“計算機器”可分成“計算”“/ 機器”和“計算機”“/ 器

18、”, 這樣必須結合其它分分詞方法, 如基于語法規則的分詞法、基于樸素貝葉斯分詞法等。在具體的分詞過程中, 我們還可以將單詞變型歸并, 像同義詞、近義詞可進行歸并, 如“因特網”和“萬維網”可當成一個詞條處理。語義Web 是下一代的Web 技術，它賦予Web 以計算機可理解的語義信息。在語義Web技術中，本體起著重要的作用。本體是人們對領域知識達成的共識，是對領域的形式化與結構化的描述。本項目針對語義Web 目前存在的問題，應用語義Web 技術，信息集成和信息管理的若干關鍵技術，從多個方面對語義Web 進行研究。（1）語義信息集成。對本體的語義標注和本體集成方法進行研究，利用基于本體的語義標注和

19、本體映射技術從異構的資源中抽取出有用信息，并通過映射方法集成多種信息源的的信息。（2）語義查詢。實現語義信息的多種查詢方式，包括：本體的可視化導航查詢，針對概念/實例/屬性的查詢，基于全文檢索技術的查詢，語義關系的查詢。（3）語義信息挖掘。語義信息的挖掘一直處在一個很淺層的階段，目前的多數研究一直處在傳統的文本信息挖掘。本項目的研究主要從本體實例聚類、本體分類，本體關聯規則挖掘以及本體中關鍵詞的抽取。這些技術是語義Web 的應用的基礎，他們可以用來分析語義信息的趨勢，語義數據的自動處理等。（4）語義Web Service。通過系統定義的軟件本體對Web Service 進行描述，從而實現Web

20、Service 的評估、組裝等功能。（5）基于Peer to Peer 的語義信息管理。這個問題的核心思想是要通過集成已有的Peer to Peer框架實現語義挖掘平臺在P2P 環境下的應用。（6）算法解釋。利用定義的基礎數據結構對上述算法的執行過程進行log，從而輕松的實現用戶-算法及開發-算法之間的交互。提供針對算法本身的更友好的接口。 2 、Web 多媒體挖掘Web 多媒體挖掘與Web 文本挖掘的不同點就在于需要提取的特征不同。Web 多媒體挖掘需要提取的特征一般包括圖像或視頻的文件名URL 、類型、鍵值表、顏色向量等。然后可以對這些特征進行挖掘工作。如關聯分析發現類似“如果圖

21、像是大而且與關鍵詞草原有關,那么它是綠色的概率是0. 8”的關聯規則。當然也可以對多媒體進行分類、聚類等操作。多媒體數據挖掘的方法主要有：多媒體數據中的相似搜索，主要有兩種多媒體標引和檢索技術：基于描述的檢索系統和基于內容的檢索系統；多媒體數據的多維分析，可以按傳統的從關系數據中構造數據立方體的方法，設計和構造多媒體數據立方體；分類和預測分析，主要應用于天文學、地震學和地理科學的研究，決策樹分類是最常用的方法；多媒體數據的關聯規則挖掘，關聯規則的挖掘主要包括以下三類規則：圖像內容和非圖像內容之間的關聯、與空間關系無關的圖像內容的關聯、與空間關系有關的圖像內容的關聯。 3、特征提取經典

22、的文本表示模型是向量空間模型（VSMVector Space Model），由Salton 等人于60 年代末提出，并成功地應用于著名的SMART 文本檢索系統。向量空間模型對文本進行簡化表示，認為特征之間是相互獨立的而忽略其依賴性，將文檔內容用它所包含的特征詞來表示：D=（t1，t2，tN），其中tk 是文檔D 的第k 個特征詞，1 k N 。兩個文檔D1 和D2 之間內容的相似程度Sim（D1，D2）通過計算向量之間的相似性來度量。最常用的相似性度量方式是余弦距離。除了向量空間模型之外，Stephen Robertson 和Spark Jones 等人提出的概率模型得到了人們的廣泛認可。該

23、模型綜合考慮了詞頻、文檔頻率和文檔長度等因素，把文檔和用戶興趣（查詢）按照一定的概率關系融合，形成了著名的OKAPI 公式。該模型在信息檢索領域取得了成功。降維就是自動從原始特征空間中提取出部分特征的過程，一般通過兩種途徑：一是根據對樣本集的統計信息刪除不包含任何信息的特征；二是將若干低級的特征合成一個新特征。目前關于特征提取的方法很多，如文檔頻率法(DF)、信息增益(IG)、互關聯信息(MI)、 x2 統計法(CHI)、特征增強(TS)等。DF是指包含某一特征的文檔數，TS 法通過統計特征在一組相近文檔中出現的頻率來估計特征的重要性，然而，人們在實際應用中發現，某些DF值或TS值很低的特征反

24、而是信息相關的，不能從特征空間中刪去，因此這兩種方法在某些情況下不可靠，MI的弱點是受特征的邊緣概率的影響很大，CHI和IG的使用效果較好。一般用的評估函數有幾率比(Odds ratio) 、信息增益( Information Gain) 、期望交叉熵( Expected CrossEntropy) 、互信息( Mutual Information) 、詞頻( WordFrequency) 等。（1）IG(Information Gain):即信息贏取。IG值代表了特征在訓練集上的分布情況，它通過統計特征在各個類別中的出現次數來計算，公式如下:其中 t 代表特征 ，ci代表第i個類別，m為類別

25、個數，只Pr (cI)代表類別cI的概率，Pr (cI|i) 代表在包含特征t的條件下類別ci的概率，Pr (cI|-t) 代表在不包含特征t的條件下類別cI的概率，Pr(t) 代表特征t出 現 的 概率，Pr (-t) 代表特征t不出現的概率。IG值越高表示該特征在訓練集中的類別上分布越集中。IG方法提取IG值較高的特征，其基本思想為分布越集中的特征越重要。(2) MI(Mutual Information):即互信息值，它通過計算特征t和類別c間 的相關性來完成提取。計算公式為: 為方便計算，簡化為: 其中N為訓練集中包含的文本總數，A為t與c同時出現的次數，B為t出現而c不出現的次數，C

26、為c出現而t不出現的次數。通過該公式就可以取得特征與各類別間的互信息值。為了能取得特征在數據集上的整體評價，有以下兩種計算方法: 前 者代表 了 特 征 和 各類別的平均互信息值，后者則取特征與各類別互 信 息 值中的最大值。MI方法提取互信息值較高的特征，其基本思想為與類別相關性越高的特征越重要。(3)CHI具有和MI方法基本相似的思想，同樣通過計算特征t和類別c間的依賴程度來完成提取。但二者的計算細節不同，CHI作了更多地考慮 ，有種看法認為CHI是一種“正規化”了的MI。CHI的計算公式如下: 其中N為訓練集中包含的文本總數，A為t與c同時出現的次數，B為t出現而c未出現的次數，C為c出

27、現而t未出現的次數，D為二者都未出現的次數。與MI相同，CHI也有平均值和最大值兩種方法來取得特征的整體評價: CHI 方 法 的基本思想也是與類別關系越緊密的特征重要性越高。(4)DF (Document frequency):即文檔頻率，指訓練集中包含該特征的文本總數。所謂文本包含特征是指這個特征在該文本中出現，忽略其在文本中的出現次數。DF方法提取DF值較高的特征，它的目的是去掉在訓練集上出現次數過少的特征，保留出現達到一定次數、具有一定影響力的特征。在各個特征提取方法中，DF方法的計算是最簡單的。(5)WEE(WeightEvidence):即文本證據權，其計算公式如下: 其中，t是一

28、個特征，m是類別的數量，ci代表第i個類別，代表類別ci的概率，Pr (cI|t)代表在包含特征t的條件下類別ci的概率，Pr(t)代表特征t出現的概率。 4、分類目前文本分類的方法很多，如多元回歸模型、K-鄰近方法、神經網絡法、貝葉斯方法、決策樹法、支持向量機等，這些方法基本上可以分為兩類：統計分類方法和基于機器學習的分類方法。支持向量機(SVM)是統計學習理論領域近幾年才提出的新知識，目前仍處于發展階段，但就目前的應用而言，SVM在很多領域的運用效果都非常理想。網頁自動分類是Web內容挖掘的主要研究內容之一，采用的主要技術是分本分類技術，這是因為文本是目前Web內容的主體，并且對

29、文本的處理較音頻、視頻的處理容易。文本分類首先要進行特征抽取。所謂特征是指一個詞或詞組。目前英文分類算法大多以單詞為特征，在分詞的時候利用空格和其它一些標點符號作為分隔符，從而抽取出文檔中出現的所有特征，所有抽取出來的特征稱為全特征集。特征抽取完畢后一般還要進行特征提取。特征提取是指從全特征集中提取一個子集的過程。提取出來的子集稱為特征子集。根據John Pierre的理論，用來表示文本的特征理論上應具有如下特點;(1)數量上盡量少;(2)出 現頻率適中;(3)冗余少;(4)噪音少;(5)與其所屬類別語義相關;(6)含義盡量明確;從全特征集中提取特征子集時通常根據特征的權值進行取舍，權值的計算

30、方 法有多種，比如信息贏取(Information Gain)，互信息(Mutual Information)等。特征提取后就可以用特征子集來表示文本，然后就可以構造用不同分類方法用來分類。常見的分類模型有:(1)K一 近鄰模型，(2)Rocchio模型，(3)貝葉斯模型，(4)神經網絡模型，(5)決策樹模型。目前研究人員己經提出了許多文本分類方法，如向量空間法(VSM)、回歸模型、K近鄰法、貝葉斯概率方法、決策樹、神經網絡、在線學習、支持向量機等。在完成特征提取之后，我們就可以使用這些特征來表示一個文本。具體的表示方法因分類方法而異。每種分類模型都會采用自己的方法來表示一個文本，并將這種表示

31、方法納入到自己的體系中去。所有的分類模型大體上都可分為訓練和分類兩個步驟。一般來說，訓練例越多分類的準確度越有保證，但也并不是越多越好。(1)基于TFIDF的Rocchio算法Rocchio 算法來源于向量空間模型理論，向量空間模型(Vector space model)的基本思想為采用向量來表示一個文本，之后的處理過程就可以轉化為空間中向量的運算?；赥FIDF的Rocchio是這種思想的一種實現方法，其中文本以一個N維向量來表示，向量維數N即特征數，向量分量是特征的某種權重表示，該權值的計算方法稱為TFIDF方法，步驟如下:通過 TFIDF方法首先將訓練集中的文本表示為向量，然后生成類別特

32、征向量(即可以用來代表一個類別的向量)。類別特征向量取值為該類中所有文本向量的平均值。Rocchio算法訓練的過程其實就是建立類別特征向量的過程。分類的時候，給定一個未知文本，先生成該文本的向量，然后計算該向量與各類別特征向量的相似度，最后將該文本分到與其最相似的類別中去。向量的相似度度量方法有兩種:(以x,y代表向量，xi,yi代表向量分量):總體來看，Rocchio算法簡單易行，運行速度尤其是分類速度較快。(2)樸素貝葉斯模型貝葉斯分類是一種統計學分類方法，它基于貝葉斯定理，可以用來預測類成員關系的可能性，給出文本屬于某特定類別的概率。分類時根據預測結果將該樣木分到概率最高的類別中去即可。

33、假定有m個類c1,c2,c3Cm，給定未知文本X,貝葉斯分類將給出條件X下具有最高后驗概率的類別，即最大化P(Ci|X)根據貝葉斯定理可得:顯而易見，P(X)對于所有類是個常數，則只需最大化P(X|Ci )P(Ci)即可。P(ci)可以根據訓練集中的類別分布來計算，即 ,其中|Ci|為類別Ci包含的文本數，|D|為訓練集中的文本總數。在一個具有許多屬性的事例中，計算P(X|Ci)的開銷會非常大，為了降低這種開銷而引出了稱為類條件獨立的樸素假定:假定文檔的一個屬性對于分類的影響獨立于其他屬性，即文檔的屬性之間是不相關的。這就是樸素貝葉斯(Naïve Bayes)的由來。這樣就可以簡單的

34、以各個屬性在類別Ci上出現的概率來推算P(X|Ci)。通常使用拉普拉斯估計(Laplacean prior)來推算。又因實現細節的不同有兩種樸素貝葉斯模型，多元模型(Multi-variate Bernoulli Model)只考慮了特征在文本中是否出現(出現記為1，否則記為。)，多項式模型(Multinomial Model)考慮了特征在文本中的出現次數:樸素貝葉斯分類模型訓練的過程其實就是統計每一個特征在各類中出現規律的過程。從理論上講，貝葉斯分類的出錯率最小，就試驗結果來看，樸素貝葉斯在大型的數據集上表現出來難得的速度和準確度。(3)決策樹決策樹(Decision Tree)是一個類似于

35、流程圖的樹結構，其中每個節點代表一個屬性上的測試，每個分支代表一個測試輸出，最后的葉結點代表類別。決策樹方便改寫為形如if-then的分類規則，易于理解。決策樹的核心算法是一種貪心算法，它以自頂向下的方式在訓練集的基礎上構造決策樹，之后取未知文本的屬性在決策樹上測試，路徑由根結點到葉結點，從而得到該文本的所屬類別。決策樹的算法有C4.5(發展于ID3),CART,CHAID等，他們的區別在于構造決策樹與樹枝剪除的算法細節不同。決策樹可以很好的抵抗噪聲。最大的缺點在于不適應大規模的數據集，此種情況下決策樹的構造會變得效率低下。(4)神經網絡神經網(Neural Network)的學習結果為目標函

36、數，根據這個目標函數的輸出作為分類的依據。輸入即為文本在各個特征上的各分量值。神經網絡實際上是一組連接的輸入/輸出單元，其中每一個連接都具有一定的權值。通過訓練集來訓練的過程就是調整這些權值的過程，使得神經網絡可以正確的預測類別。神經網絡的訓練是針對訓練例逐個進行的，所以神經網絡的訓練集可以隨時添加，不需要重新進行訓練就可完成網絡的調整。同時有實驗結果表明，在訓練例過少的情況下，神經網絡的分類準確率較低。因為可通過訓練來針對特征取一定的合適的權值，神經網絡可以較好地抵御噪音的干擾。(5)K近鄰K近鄰分類(K-nearest neighbor)的思想也來源于向量空間模型，同樣采用將文本轉化為向量

37、的思想。KNN是一種基于類比的分類方法。在訓練的過程中KNN會生成所有訓練例的特征向量，并將其保存下來。給定一個未知文本，首先生成它的特征向量，之后KNN會搜索所有的訓練例，通過向量相似度比較從中找出K個最接近的訓練例，然后將未知文本分到這K個近鄰中最普遍的類別中去。相似度可以通過歐幾里德距離或向量間夾角來度量。根據經驗x一般取45。KNN是一種懶散的方法，即它沒有學習過程，只是存放所有的訓練例，直到接到未知文本的時候才建立分類。ON的訓練過程較快，而且可以隨時添加或更新訓練例來調整。但它分類的開銷會很大，因為需要很大的空間來保存訓練例，而且分類效率很差。有看法認為在小數據集上KNN的表現優異

38、。(6)SVM方法SVM方法是建立在統計學習理論的VC維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的復雜性(即對特定訓練樣本的學習精度)和學習能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折中，以期獲得較好的綜合能力。SVM專門針對有限樣本，其目標是得到現有信息下的最優解而不僅僅是樣本數趨于無窮大時的最優值(KNN和Naive Bayes方法基于樣本數趨于無窮大)，從理論上說，SVM得到的將是全局最優點，從而解決了在神經網絡方法中無法避免的局部極值問題。此外，SVM將實際問題通過非線性變換轉換到高維的特征空間，在高維空間中構造線性判別函數來實現原空間中的非線性判別函數，特殊性質

39、能保證機器有較好的推廣能力，同時它巧妙地解決了維數問題，其算法復雜度與樣本維數無關。 5、網頁分類方法一般來說，網頁中對于分類有作用的部分首先是核心文本，即網頁中關于網頁內容的文本部分。其次是結構信息和超鏈接信息，再其次是多媒體信息。多媒體信息的識別涉及圖像檢索、語音識別等技術，且目前沒有較好的結果，因此很少被考慮。我們進行網頁分類的基本思路是:(1 )利用自行研制的網頁解析器分離出目標網頁的核心純文本。(2 )利用自行研制的分類系統TCS對目標網頁的核心純文本部分進行分詞、特征提取等操作，并產生目標網頁的初始特征向量。(3) 根據特征向量進行分類，確定目標網頁的類別。通常采用以下五

40、種標準在不同的方面來評價一個分類器: (1)精度 (precision) (2)查全率(recall) (3)F標準綜合了精度和查全率，將兩者賦予同樣的重要性來考慮，即 ，其中r代表查全率，p代表精度。這三個標準都只用于分類器在單個類別上分類準確度的評價。(4)宏觀平均值(macro-averaged score) (5)微觀平均值(micro-averaged score)。 Web 結構挖掘：整個Web 空間中,有用知識不僅包含在Web頁面內容中, 也包含在Web 頁間超鏈接結構與Web 頁面結構之中。挖掘Web 結構的目的是發現頁面的結構和Web 間的結構,在此基礎上對頁面進行

41、分類和聚類,從而找到權威頁面,這種方法可以用來改進搜索引擎。在搜索引擎中存貯了數以億計的頁面，很容易得到它們的鏈接結構。需要做到的是尋找一種好的利用鏈接結構來評價頁面重要性的方法。Page Rank 的基本思想是: 一個頁面被多次引用,則這個頁面很可能是重要的;一個頁面盡管沒有被多次引用,但被一個重要頁面引用,該頁面也可能是很重要的;一個頁面的重要性被均分并被傳遞到它所引用的頁面。在Page Rank方法中，Page Rank被定義為:設u為一個Web頁。Fu為所有的u指向的頁面的集合，Bu為所有的指向u的頁面的集合。設Nu=Fu為從u發出的鏈接的個數，C(C1)為一個歸一化的因子(因此所有頁

42、面的總的Page Rank為一個常數)，那么u頁面的Page Rank被定義為(簡化的版本): 即一 個 頁 面的PageRank被分配到所有它所指向的頁面:每一個頁面求和所有指向它的鏈接所帶來的PageRank得到它的新的PageRank。該公式是一個遞歸公式，在計算時可以從任何一個頁面開始，反復計算直到其收斂。對于 搜 索 引擎的鍵值搜索結果來說，PageRank是一個好的評價結果的方法，查詢的結果可以按照PageRank從大到小依次排列。從 we b結 構挖掘的現狀來看，純粹的網絡結構挖掘研究很少，多數是和其它web挖掘形式結合起來。主要的研究集中在網絡虛擬視圖生成與網絡導航、信息分類與

43、索引結構重組、文本分類、文本重要性確定等幾個方面。關鍵頁/ 權威頁(Hub/ Authority) 方法頁面的超鏈接關系十分復雜, 例如: 有的鏈接是為了導航, 因此不能簡單認為超鏈接即是引用關系; 此外由于商業的需要,很少有頁面會把其競爭對手的頁面作為鏈接。正是由于超鏈接結構中存在著以上的缺陷, 出現了關鍵頁/ 權威頁方法。關鍵頁/ 權威頁方法的思想是: Web 上存在著一種重要的頁面。所謂關鍵頁指的是自身不一定為多個頁面所鏈接, 但是它的頁面上存在著就某個專業領域而言最重要的站點鏈接。對于這種關鍵頁, 它起到了隱含說明其他Web文檔頁面重要性的作用。一個權威頁應當是被多個關鍵頁所鏈接的,

44、而一個關鍵頁應當包含很多權威頁的鏈接。將關鍵頁與權威頁的這種聯系按照算法計算出來, 就是關鍵頁/ 權威頁方法的主要思想。HITS和Page Rank、以及在鏈接結構中增加了Web內容信息的HITS改進算法等，主要用于模擬Web站點的拓撲結構，計算Web頁面的等級和Web頁面之間的關聯度，典型的例子是Clever System和Google. Web 使用挖掘：Web 使用挖掘又叫Web 使用記錄挖掘,是指通過挖掘Web 日志記錄來發現用戶訪問Web 頁面的模式?？梢酝ㄟ^分析和研究Web 日志記錄中的規律,來識別電子商務的潛在客戶;可以用基于擴展有向樹模型來識別用戶瀏覽模式,從而進行W

45、eb 日志挖掘;可以根據用戶訪問Web 的記錄挖掘用戶的興趣關聯規則,存放在興趣關聯知識庫中,作為對用戶行為進行預測的依據,從而為用戶預取一些Web 頁面,加快用戶獲取頁面的速度。Web 日志挖掘過程一般分為3 個階段: 預處理階段、挖掘算法實施階段、模式分析階段。Web 服務器日志記錄了用戶訪問本站點的信息,其中包括IP 地址、請求時間、方法、被請求文件的URL 、返回碼、傳輸字節數、引用頁的URL 和代理等信息。這些信息中有的對Web 挖掘并沒有作用,因此要進行數據預處理。預處理包括數據凈化、用戶識別、事務識別等過程。通過對Web 日志預處理后,就可以根據具體的分析需求選擇訪問模式發現的技

46、術,如路徑分析、關聯分析、時序模式識別以及分類和聚類技術等。模式挖掘出來以后還要進行分析,使之得到很好的利用。常用有兩種方法發現用戶使用記錄信息。一種方法是通過對日志文件進行分析, 包含兩種方式, 一是訪問前先進行預處理, 即將日志數據映射為關系表并采用相應的數據挖掘技術, 如關聯規則或聚類技術來訪問日志數據, 二是對日志數據進行直接訪問以獲取用戶的導航信息; 另一種是通過對用戶點擊事件的搜集和分析發現用戶導航行為。從研究目標的角度看, 已有的基于Web 服務器日志數據的研究大致可以分為3 類: 以分析系統性能為目標; 以改進系統設計為目標; 以理解用戶意圖為目標。由于各目標針對的功能不同,

47、采取的主要技術也不同。用戶使用記錄的挖掘通常要經過下面3 個步驟: 數據預處理階段。這是使用記錄信息挖掘最關鍵的階段, 數據預處理包括: 關于用戶使用記錄的預處理、關于內容預處理和結構的預處理; 模式識別階段。該階段采用的方法包括: 統計法、機器學習和模式識別等方法。實現算法可以是: 統計分析、聚類、分類、關聯規則、序列模式識別等; 模式分析階段。該階段的任務是從上一階段收集的數據集中過濾掉不感興趣和無關聯的數據及模式。具體的實現方法要依具體采用Web 挖掘技術而定,通常采用的方法有兩種: 一種采用SQL 查詢語句進行分析; 另外一種將數據導人多維數據立方體中, 而后利用OLA P 工具進行分

48、析并提供可視化的結構輸出。對挖掘用戶使用記錄的研究早期多采用的是統計的方法, 當用戶通過瀏覽器對Web 站點進行訪問時, 建立統計模型對用戶訪問模式進行多種簡單的統計, 如頻繁訪問頁、單位事件訪問數、訪問數據量隨時間分布圖等。早期使用的方法為以廣度優先算法為主的統計模型, 還有一種啟發式的HPG(hypertext probabilistic grammar) 模型用于用戶導航行為的發現, 它也是一種基于統計的方法, 由于HPG 模型與k 階馬爾可夫模型相當, 所以近來也有人提出用馬爾可夫模型挖掘用戶使用記錄。Web日志的挖掘的方法可以分為 (1)以JiaWei Han為代表的基于數據立方體（

49、data cube）的方法：將Web 日志保存為數據立方體，然后在其上進行數據挖掘和OLAP操作；（2）以Ming-Syan Chen為代表的基于Web 事物的方法：他們首先提出了最大向前引用序列（MFR）的概念，用MFR將用戶會話分割成一系列的的事務，然后采用與關聯規則相似的方法挖掘頻繁瀏覽路徑。Web 行為挖掘在電子商務中得到了廣泛的應用, 在對事務進行了劃分后, 就可以根據具體的分析需求選擇訪問模式發現的技術(路徑分析、關聯、規則挖掘、時序模式以及聚類和分類技術等)Web 使用挖掘中的模式分析,主要是為了在模式發現算法找到的模式集合中發現有趣模式。開發各種Web 分析技術和工具,可輔助分

50、析人員加深理解并使各種挖掘方法得到的模式獲得充分利用。如Webwiz (pitkow) 系統可將www 的訪問模式可視化;Webminer則采用類SQL 語言的知識查詢機制;另外也可以利用存儲Web 使用數據的數據倉庫,采用OLAP 方法發現數據中的特定模式。 6、Web 數據挖掘的四個步驟:1、查找資源: 任務是從目標Web文檔中得到數據。2、信息選擇和預處理:任務是從取得的Web資源中剔除無用信息和將信息進行必要的整理。3、模式發現:自動進行模式發現?？梢栽谕粋€站點內部或在多個站點之間進行。4、模式分析:驗證、解釋上一步驟產生的模式。 7、Web 挖掘在Interne

51、t 上有非常廣泛的應用,比較常見的有:(1)幫助尋找用戶感興趣的新聞或其他信息以在Web站點中提供個性化服務,吸引更多用戶。(2)在搜索引擎上對文檔進行自動分類從而降低在搜索引擎上為組織整理Internet 文檔所需消耗的人力資源,也可以對Web 頁面進行排序,改進搜索引擎。(3)Web日志挖掘在電子商務領域有很廣闊的應用前景,如發現顧客的購買習慣和瀏覽興趣所在,有針對性調整銷售模式,提高業務量。 8、通常Web挖掘可以分為3個子任務：資源發現、信息提取、概括。· 資源發現：是指從Web上搜索可用的信息；· 信息提取：是從已經發現的資源中提取出有用的信息。對于文本

52、信息而言，不僅要考慮文本內容，而且也要考慮文本的結構；·概括：是對Web信息自學習的過程，通過學習抽取一定的規則。一般來說，Web挖掘的數據來源途徑有兩個：搜索引擎的結果集和Web上的在線信息。這兩種方式各有所長，需要視具體的應用而定。目前，已經有幾種資源發現模型廣泛應用于Internet上：目錄/瀏覽模型(WAIS and Gopher)、檢索模型(Archie and AltaVista)、超立方體(Yahoo and Excite)。許多資源發現工具大都采用了基于Robot的檢索模型，這種方法掃描Web上的所有文檔，并建立索引，但它同時也將一些不相關的信息和過時的信息包含進來。

53、 9、Web挖掘的發展方向:目前，在國內外Web 挖掘的研究處于剛起步階段，是前沿性的研究領域。將來幾個非常有用的研究方向是：（1）Web 數據挖掘中內在機理的研究；（2）Web 知識庫（模式庫）的動態維護、更新，各種知識和模式的融合、提升，以及知識的評價綜合方法；（3）半結構、非結構化的文本數據、圖形圖像數據、多媒體數據的高效挖掘算法；（4）Web數據挖掘算法在海量數據挖掘時的適應性和時效性；（5）基于Web挖掘的智能搜索引擎的研究；（6）智能站點服務個性化和性能最優化的研究；（7）關聯規則和序列模式在構造自組織站點的研究；（8）分類在電子商務市場智能提取中的研究。 10

54、、研究意義和方向：路徑模式挖掘在Web中，文檔通過超鏈連接便于用戶瀏覽，用戶為尋找信息經常通過超鏈從一個頁面跳到另一個頁面。捕捉用戶瀏覽路徑稱為Path analysis。理解用戶瀏覽路徑有助于改進系統設計，而且有助于作出更好的市場決策，例如在適當的頁面出增加廣告.Web中的智能查詢數字時代的圖書館并不是一個有組織的信息倉庫，而更象一個又一個雜亂無章的信息倉庫，Web中的智能查詢包括以下三個方面:1)資源發現:重點是自動生成可查找的索引。2)信息抽取:發現了資源后，下一個任務就是進行信息的自動抽取。3)信息歸納:利用分類技術可自動組織和管理數據，也可以發現用戶感興趣的模式。Web智能工具Web

55、上的用戶需要借助與軟件系統來抽取、定位和管理Web文檔，才能跟上信息的改變速度這種軟件系統叫做Web工具.現有的Web工具缺乏識別和使用深層語義的能力，查詢語言描述能力有限。新一代的智能Web工具，利用智能Agent幫助用戶發現新的信息。它可以自動地獲取用戶的興趣主題，發現用戶的瀏覽模式和信息資源的修改模式。能更有效地利用網絡資源，將多個用戶的查詢要求聚成組，減少查詢次數。將抽取的文檔及其全文索引保存在數據庫中，并發現各種有用的模式。提高網絡響應速度傳統解決網絡響應速度慢的途徑，一般都基于客戶端:如優化傳輸，減少阻塞;根據預測，預先傳輸某些頁面。在服務器端利用關聯規則挖掘，不僅可以提高網絡的響

56、應速度而且可以有效地調度網絡代理的緩存。當用戶瀏覽某個頁面時，網絡代理可根據關聯規則預先下載與該頁面相關聯的頁面，即用戶很可能訪問到的頁面，從而提高網絡的響應速度，因為關聯規則是基于統計規律的，反映了大多數用戶的興趣。 11、基于Web挖掘的個性化技術的發展 (1) 與人工智能技術的結合 個性化系統領域的許多問題最終都可歸結到機器學習、知識發現等問題上。用戶建模過程用通常都應用到代理和多代理技術。因此人工智能技術與Web挖掘技術的結合將會促進Web個性化系統的飛速發展。 (2) 與交互式多媒體Web技術的結合 隨著下一代Internet技術的飛速發展與應用，未來的Web的將是多媒體的

57、世界。Web個性化技術和Web多媒體系統結合出現了交互式個性化多媒體Web系統。支持海量多媒體數據流的內容挖掘將成為Web挖掘技術的基本功能之一。由于這種基于內容的交互式個性化多媒體Web系統更能滿足用戶需要，因此也將成為Web個性化系統的發展方向之一。 (3) 與數據庫等技術的結合  12、數據挖掘和知識發現的發展方向：1、挖掘算法的效率和可擴放性。目前數據庫數據量大，維數高，使得數據挖掘的搜索空間增大，發現知識的盲目性提高。如何充分利用領域的知識，剔除與發現任務無關的數據，有效地降低問題的維數，設計出高效率的知識發現算法是下一步發展的重點。2、數據的時序性。在應用領域的數據庫中，

58、數據在不斷地更新，隨著時間的推移，原先發現的知識將不再有用，我們需要隨時間逐步修正發現模式來指導新的發現過程。3、和其它系統的集成。知識發現系統應該是數據庫、知識庫、專家系統、決策支持系統、可視化工具、網絡等多相技術集成的系統。4、交互性?？梢岳秘惾~斯確定數據的可能性及其分布來利用以前的知識，再就是利用演繹數據庫本身的演繹能力發現知識，并用于指導知識發現的過程。5、發現模式的精煉?？梢岳妙I域知識進一步提煉發現模式，從中提取有用的知識。6、互聯網上知識的發現。WWW正日益普及，從中可以找到很多新的知識，已有一些資源發現工具來發現含有關鍵字的文本，但對在WWW上發現知識的研究不多。加拿大的HAN等人提出利用多層次結構化的方法，通過對原始數據的一般化，構造出多層次的數據庫。例如可將WWW上的圖象描述而不是圖像本身存儲在高層數據庫中。現在的問題是如何從復雜的數據(例如多媒體數據)中提取有用的信息，對多層數據庫的維護，如何處理數據的異類性和自主性等等。 13、文本挖掘面臨許多新的研究課題:(1)文本挖掘算法的可擴展性問題Internet 的發展,電子商務和數字圖書館的興起和廣泛應用