第11章文本挖掘與Web挖掘

第11章文本挖掘與Web挖掘

目錄13.1文本挖掘概述

13.2文本挖掘13.3Web挖掘

13.1文本挖掘概述

13.1.1文本挖掘的基本概念

13.1.2文本特征的表示

13.1.3文本特征的提取

13.1.1文本挖掘的基本概念

文本挖掘一詞出現(xiàn)于1998年第十屆歐洲機器學習會議上。Kodratoff認為文本挖掘的目的是從文本集合中，試圖在一定的理解水平上盡可能多地提取知識。1.概念文本挖掘是一個從大量文本數(shù)據(jù)中提取以前未知的、有用的、可理解的、可操作的知識的過程。文本數(shù)據(jù)包括：技術報告、文本集、新聞、電子郵件、網(wǎng)頁、用戶手冊等。2.主要任務

（1）短語提取提取文本集中所有相關的短語。（2）概念提取（聚類）對這些短語之間的關系，建立一個該文本集中的主要概念

。（3）可視化顯示和導航

從多個視角出發(fā)進行分析.3.文本挖掘與數(shù)據(jù)挖掘

數(shù)據(jù)挖掘文本挖掘研究對象用數(shù)字表示的、結構化的數(shù)據(jù)無結構或者半結構化的文本對象結構關系數(shù)據(jù)庫自由開放的文本目標獲取知識，預測以后的狀態(tài)提取概念和知識方法歸納學習、決策樹、神經(jīng)網(wǎng)絡、粗糙集、遺傳算法等提取短語、形成概念、關聯(lián)分析、聚類、分類成熟度從1994年開始得到廣泛應用從2000年開始得到廣泛應用13.1.2文本特征的表示

文本特征指的是關于文本的元數(shù)據(jù)：（1）描述性特征，例如文本的名稱、日期、大小、類型等；（2）語義性特征，例如文本的作者、機構、標題、內容等。矢量空間模型（VSM）是效果較好的表示文本特征的方法。每個文本d表示為其中的一個規(guī)范化特征矢量：V(d)=(t1，w1(d)；…；ti，wi(d)；…；tn，wn(d))d中出現(xiàn)的所有單詞作為ti，或所有短語。wi(d)一般被定義為ti在d中出現(xiàn)頻率tfi(d)的函數(shù)。

函數(shù)wi(d)=Ψ(tfi(d))

，常用的Ψ有：

（1）平方根函數(shù)（2）對數(shù)函數(shù)13.1.3文本特征的提取

特征提取主要是識別文本中代表其特征的詞項。文本特征分為一般特征和數(shù)字特征，其中一般特征主要包括動詞和名詞短語，如人名、組織名等；數(shù)字特征主要包括日期、時間、貨幣以及單純數(shù)字信息。

特征項抽取的判斷算法（1）該特征項集合包含所有該類中出現(xiàn)的詞。（2）對于每個詞，計算詞Wi和類別Cj的互信息量I(W,C)

（3)對于該類中所有的詞，依據(jù)上面計算的互信息量排序。（4）抽取互信息量大的詞作為特征項。（5）根據(jù)抽取的特征項進行向量壓縮，精簡向量表示。13.2文本挖掘

13.2.1文本挖掘功能層次

13.2.2關聯(lián)分析

13.2.3文本聚類

13.2.4文本分類13.2.1文本挖掘功能層次

關鍵詞相似檢索詞語關聯(lián)分析自然語言處理文本聚類文本分類文本挖掘功能層次（1）關鍵詞檢索關鍵詞建立倒排文件索引，與傳統(tǒng)的信息檢索使用的技術類似。（2）相似檢索找到相似內容的文本。（3）詞語關聯(lián)分析聚焦在詞語（包括關鍵詞）之間的關聯(lián)信息分析上。（4）文本聚類和文本分類實現(xiàn)文本的聚類和分類。（5）自然語言處理揭示自然語言處理技術的語義，進行文本語義挖掘。13.2.2關聯(lián)分析

在文本數(shù)據(jù)庫中，每一文本被視為一個事務，文本中的關鍵詞組可視為事務中的一組事務項。即文本數(shù)據(jù)庫可表示為：{文本編號，關鍵詞集}

文本數(shù)據(jù)庫中關鍵詞關聯(lián)挖掘的問題就變成事務數(shù)據(jù)庫中事務項的關聯(lián)挖掘。

關聯(lián)分析挖掘可以用于找出詞或關鍵詞間的關聯(lián)。

13.2.3文本聚類

層次聚類法對于給定的文本集合D={d1，…，di，…，dn}:（1）將D中的每個文本di看作是一個具有單成員的類ci={di}，這些類構成了D的一個聚類:C={c1，…，ci，…，cn}；（2）計算C中每對類(ci，cj)之間的相似度sim(ci，cj)；（3）選取具有最大相似度的類對，并將ci和cj合并為一個新的類ck=ci∪cj，從而構成了D的一個新的聚類C={c1，…，cn-1}；（4）重復上述步驟，直至C中剩下一個類為止。該過程構造出一棵生成樹，其中包含了類的層次信息，以及所有類內和類間的相似度。

13.2.4文本分類

首先，把一組預先聚類過的文本作為訓練集。然后對訓練集進行分析以便得出各類的分類模式。對文本分類的有效方法是基于關聯(lián)的分類:（1）提出關鍵詞和詞組。（2）生成關鍵詞和詞組的概念層次，或類層次結構。（3）詞關聯(lián)挖掘方法用于發(fā)現(xiàn)關聯(lián)詞，它可以最大化區(qū)分一類文本與另一類文本。這導致了對每一類文本，有一組關聯(lián)規(guī)則。11.3Web挖掘13.3.1Web挖掘概述13.3.2

Web內容挖掘13.3.3Web結構挖掘13.3.4Web應用挖掘13.3.5Web日志分析與實例13.3.1Web挖掘概述1．Web信息特點（1）Web信息特別龐大（2）Web信息非常復雜（3）Web信息是動態(tài)的（4）Web信息使用者復雜（5）Web信息中的“垃圾”非常多2.Web數(shù)據(jù)挖掘的意義Web挖掘的實質:從Web頁面及其鏈接和用戶對頁面的訪問中挖掘出用戶感興趣的知識。通過Web數(shù)據(jù)挖掘，可以從數(shù)以億計存儲大量多種多樣信息的Web頁面及其鏈接和用戶對頁面的訪問中挖掘出需要的有用知識。Web挖掘的數(shù)據(jù)來源是網(wǎng)站數(shù)據(jù)，這些數(shù)據(jù)包括網(wǎng)頁文本信息、網(wǎng)頁鏈接信息、網(wǎng)站的訪問記錄以及其他可收集的信息。例如：Web日志（服務器日志、錯誤日志、Cookie日志等）、在線市場數(shù)據(jù)、Web頁面、Web頁面超鏈接以及包括用戶注冊信息等數(shù)據(jù)源。3．Web挖掘分類Web挖掘分類（1）Web內容挖掘提取文字、圖片或其他組成網(wǎng)頁內容成分的信息和知識。

（2）Web結構挖掘提取網(wǎng)絡的拓撲信息，即網(wǎng)頁之間的鏈接信息。

（3）Web應用挖掘提取關于客戶如何運用瀏覽器瀏覽和使用頁面鏈接的信息。（4）區(qū)別與聯(lián)系結構挖掘的表達方式是鏈接圖，提示了哪些頁面通過當前頁可以幾步內到達。內容挖掘的表達方式是一個網(wǎng)絡索引，提示了網(wǎng)頁的主題。應用挖掘集中于挖掘客戶的行為，特別是隨著時間的變化。13.3.2Web內容挖掘Web內容挖掘的基本技術是文本挖掘。

1．信息檢索信息檢索的目標是找到你想要找的，從兩個方面來判斷該查詢的有效性：“召回（recall）”和“精度（precision）”。“精度”回答了“在返回的網(wǎng)頁中，正確的標題的比例是多少”；“召回”回答了“返回了多少正確頁面”。2．從純文本中提取信息

通過將純文本轉化為結構化的數(shù)據(jù)，他們能夠直接應用數(shù)據(jù)挖掘技術做出預測。這種從非結構化數(shù)據(jù)中創(chuàng)建結構化數(shù)據(jù)的過程叫做特征抽取。通過以XML標記的形式向網(wǎng)站中添加更結構化的內容，比通過提高從非結構化的文本中提取信息的技術來得更加迅速一些。13.3.3Web結構挖掘結構挖掘可以告訴我們一些站點的受歡迎程度和它同其他站點的距離（通過跳轉次數(shù)來判定）。萬維網(wǎng)（www）是一個有向圖G=(V，E)，V是頁面的集合，E是頁面之間的超鏈接集合。頁面抽象為圖中的頂點，而頁面之間的超鏈接抽象為圖中的有向邊。頂點v的入邊表示對v的引用，出邊表示v引用了其它的頁面。Web頁面之間的超鏈接揭示了Web結構。1.網(wǎng)頁的引用一篇文章的有用與否在于這篇文章出現(xiàn)在其他文章的參考書目中的次數(shù)。特別是作者，會因為他的作品的重復引用而在某個學科出名。網(wǎng)頁引用的rank方法：（1）一個頁面被多次引用，則這個頁面很可能是重要的；（2）一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面很可能是重要的；（3）一個頁面的重要性被傳遞到它所引用的頁面。2、中樞和權威Kleinberg提出:一個鏈接到許多權威站點的站點叫做中樞（hub）;被許多中樞鏈接的站點叫做權威（authority）。這兩個概念放在一起可以辨別出權威和大眾化站點（如Yahoo）之間的區(qū)別。一種尋找權威的結構化的方法就是:

用其他的站點到該站點的鏈接數(shù)來將它們分級。要給站點分級，不要用指向它們的鏈接的總數(shù)，而是用指向它們的標題相關的中樞的數(shù)量來分級。3.導航頁

導航頁使他們能夠很容易地找到他們想要找的網(wǎng)頁。

4.目標頁目標頁給瀏覽者提供所有的內容。

13.3.4Web應用(訪問信息）挖掘在Web應用挖掘中，我們考慮的是對客戶的理解，這時客戶應用模式就是非常關鍵的?？蛻魬媚Ｊ娇梢詮亩鄠€層次檢測和挖掘到，即從單個客戶在一次對話中的一系列的單擊到跨越了幾個月或數(shù)年的客戶群的購買中獲取應用模式。1．Web應用挖掘的意義

Web應用挖掘的意義：(1)改進Web站點的效率。

(2)實現(xiàn)個性化服務。(3)商業(yè)知識的發(fā)現(xiàn)。(4)發(fā)現(xiàn)導航模式。(5)抽取訪問信息特性。2.Web應用挖掘中的技術Web應用挖掘中的常用技術： (1)路徑分析。 (2)關聯(lián)規(guī)則發(fā)現(xiàn)。(3)序列模式發(fā)現(xiàn)。 (4)分類。 (5)聚類。

3.Web訪問日志挖掘（1）對訪問日志（WebLog）進行清洗、過濾和轉換，從中抽取感興趣的數(shù)據(jù)。（2）將資源的類型、大小、請求的時間、停留時間、請求者的域名、用戶、服務器狀態(tài)作為數(shù)據(jù)立方體的維變量。將對頁面和文件請求次數(shù)、來自不同域請求次數(shù)、事件、會話、錯誤次數(shù)分別作為在這些維變量下的度量變量，建立數(shù)據(jù)立方體。通過切塊、切片分析可以回答：哪些成分或特色被經(jīng)?；蚺紶柺褂?，網(wǎng)絡流量隨時間的變化規(guī)律。（3）利用數(shù)據(jù)挖掘技術進行Web流量分析、典型的事件序列和用戶行為模式分析。4．應用挖掘的作用(1)利用Web應用挖掘可以實現(xiàn)用戶建模； (2)利用Web應用挖掘發(fā)現(xiàn)導航模式，從而改進Web站點的結構設計，實行個性化推銷；(3)利用Web應用挖掘改進訪問效率，改進服務器性能； (4)利用Web應用挖掘還可以進行個性化服務；(5)利用Web應用挖掘進行商業(yè)知識的發(fā)現(xiàn)； (6)利用Web應用挖掘進行用戶移動模式的發(fā)現(xiàn)。13.3.5Web日志分析與實例1．Web日志數(shù)據(jù)概述 Web訪問日志數(shù)據(jù)具有如下基本特征： ⑴動態(tài)變化性⑵數(shù)據(jù)量大⑶多維性⑷結構化程度較高⑸包含大量瑣碎數(shù)據(jù)Web日志的記錄格式包括如下常用字段： ①每次訪問者的客戶端機器IP地址。 ②用戶訪問日期和時間，精確到秒。 ③用戶訪問的網(wǎng)頁名稱。 ④用戶的本次訪問請求是否成功的狀態(tài)。 ⑤傳輸文件的字節(jié)大小。 ⑥引導用戶訪問到本站點的前驅URL。 ⑦訪問者使用的瀏覽器版本和操作系統(tǒng)版本 在Web日志分析中，把握動態(tài)變化趨勢很重要，其內在規(guī)律、有用知識可能是稍縱即逝的，如用戶訪問趨勢、訪問熱點變化、異常訪問模式等。流式數(shù)據(jù)多維查詢與挖掘則是實現(xiàn)Web日志分析的有效工具。2．面向Web日志分析的流式數(shù)據(jù)多維模型(1)時間維度，是流式數(shù)據(jù)多維模型的基礎，其中包含年、月、日、時、分、秒等多個時間粒度層次信息。(2)主題維度，綜合網(wǎng)站可劃分為滾動新聞、明星新聞、影視新聞等多個子版塊，每個子版塊關注不同的新聞內容，即不同主題。(3)用戶維度，屬性取值代表不同地區(qū)的訪問者，其中的維成員對應于Web訪問日志中的訪問主機，即訪問客戶端的IP地址。

(4)度量屬性

①請求數(shù)：Web訪問日志的每一條記錄對應一次請求，②頁面瀏覽數(shù)：即頁面被打開（請求）的次數(shù)，是網(wǎng)站分析中最常見的度量。 ③傳輸數(shù)據(jù)量：傳輸數(shù)據(jù)量可用于統(tǒng)計網(wǎng)站的流量，以及衡量不同用戶以及不同周期內的訪問情況，需要將所有請求的傳輸字節(jié)數(shù)相加得到結果。3．Web日志數(shù)據(jù)的多維查詢

在Web日志分析中，經(jīng)常需獲取某一特定維度視角或數(shù)據(jù)粒度層次上的聚集信息。下面以流式數(shù)據(jù)三維視圖（小時，城市，視頻版塊）為例，進行Web日志多維查詢。對Web日志查詢舉例： （1）Q1：對上午6時至12時，查詢每個小時的頁面瀏覽數(shù)，查詢視圖為:

（小時，*，*）切塊查詢條件定義在時間維度上。

Q1查詢結果如表13.2所示，結果表明，網(wǎng)站的高峰訪問時間段為上午“9-10時”，而其他時段則相對較少。

表13.2Q1查詢結果

時間

頁面瀏覽數(shù) 5-7時 953 7-8時 1080 8-9時 3295 9-10時5122 10-11時 4270 11-12時 1945 （2）Q2：對工作時間7時至12時之間，查詢主要的子版塊的頁面瀏覽數(shù)，即在上面查詢的基礎上，下鉆到子版塊的查詢。查詢視圖為:

（小時，*，子版塊）在時間維度和主題維度上定義切塊查詢。

Q2查詢結果如表13.3所示，表明上午工作時間的訪問多集中在“滾動新聞”，而其他版塊相對較少。表13.3Q2查詢結果

時間 子版塊 頁面瀏覽數(shù) 7-12時 滾動新聞 1945 7-12時圖片新聞 5377-12時綜藝新聞 8997-12時明星新聞 3747-12時音樂新聞 3427-12時人物訪談 308（3）Q3：對晚間18時至22時之間，查詢主要省份的頁面瀏覽數(shù)，如北京，上海，廣東，湖南，江蘇，浙江，遼寧，重慶。查詢視圖為:

（小時，省，*）在時間維度和用戶維度上定義切塊查詢。

Q3查詢目的在于發(fā)現(xiàn)訪問者的區(qū)域分布情況，查詢結果如表13.4所示，表明熱點訪問省級區(qū)域為“浙江”和“北京”。 表13.4Q3查詢結果

時間 省份 頁面瀏覽數(shù) 8-22時 北京 54548-22時上海 5188-22時廣東 14158-22時湖南 3348-22時江蘇 7058-22時浙江 101018-22時遼寧 2618-22時重慶 165（4）Q4：對浙江省主要城市，查詢18點至22點之間的頁面瀏覽數(shù)，如杭州市，寧波市，溫州市，紹興市，嘉興市，金華市。查詢視圖為:

（小時，城市，*）在時間維度和用戶維度上定義切塊查詢。查詢結果如表13.5所示，結果表明網(wǎng)站的訪問者大部分來自于杭州市和嘉興市，而其他城市較少。 表13.5Q4查詢結果

時間 省份 城市 頁面瀏覽數(shù) 18-22時 浙江 杭州市 338118-22時浙江寧波市 15918-22時浙江溫州市 12018-22時浙江紹興市 8718-22時浙江嘉興市 113418-22時浙江金華市 33從以上的Web日志數(shù)據(jù)的多維查詢分析，可以得出的結論是：（1）網(wǎng)站上的頁面瀏覽的高峰訪問時段是上午9-10時。（2）工作時間訪問最多的是滾動新聞（3）晚間訪問網(wǎng)站最多的省份是浙江和北京，其中浙江省內訪問最多的的用戶主要是杭州市和嘉興市。4．連續(xù)查詢熱點訪問信息或異?，F(xiàn)象（5）Q5：連續(xù)跟蹤最近1小時內的每個版塊的頁面瀏覽總數(shù)變化趨勢。查詢視圖為:

（分鐘，*，子版塊）時間窗口為60分鐘，查詢條件分別對應不同版塊，包括明星新聞、滾動新聞、圖片新聞、影視新聞。

Q5連續(xù)的查詢結果表明，“滾動新聞”版塊的訪問量較高，在10-24時間段，訪問量相對穩(wěn)定在900次左右。比其它子版塊要高出400-600次，并且在上午9時監(jiān)測到一個高峰訪問周期，迏到1600次，比平均值高出近一倍，這是一個異常情況。（6）Q6：連續(xù)跟蹤最近1小對內不同城市的訪問量變化情況，包括浙江省的杭州市，嘉興市，麗水市。查詢視圖為:

（分鐘，城市，*）

時間窗口為60分鐘，查詢條件定義在用戶維度上。三城市不同時間訪問頁面次數(shù)對比表見表13.6。浙江省三城市

不同時間訪問頁面次數(shù)對比表時間杭州市嘉興市麗水市02時50150004時3050006時8050008時100180010時210220110012時10019070014時1505080016時6508070018時100150850202303060024時100500800Q6連續(xù)的查詢是針對杭州市、嘉興市和麗水市，進行對比分析結果表明：麗水市在8-24時，平均訪問量有800次，大大高于其它兩個城市（相當于4-6倍）。杭州市平均訪問量200次，嘉興市平均訪問量120次。麗水市在上午10時，頁面瀏覽數(shù)的訪問量達到最高峰1100次。杭州市在下午16時達到最高峰，訪問量是700次。嘉興市在上午9時達到最高峰，訪問量是400次。但麗水市清晨時的訪問量是0。可見麗水市在浙江省是一個特例。（7）Q7：連續(xù)跟蹤主要省份對特定版塊的訪問量變化情況，查詢視圖為:（分鐘， 省，滾動新聞），時間窗口為60分鐘，查詢條件定義在用戶維度上，用戶分別對應浙江省、江蘇省和上海市，主題維度的子版塊定為“滾動新聞”。Q7連續(xù)的查詢結果，表明浙江省對“滾動新聞”版塊關注較多，在0-7小時內，平均訪問量有30次左右；在