第11章其他挖掘方法

數據挖掘的研究范圍十分廣泛，除了前面幾章介紹的基本數據挖掘方法外，數據挖掘方法應用到不同的領域形成了與相關領域相結合的各種數據挖掘技術。本章主要介紹文本挖掘、Web挖掘和空間數據挖掘方法。11.1文本挖掘技術11.1.1文本挖掘概述1.什么是文本挖掘文本挖掘處理的是非結構化的文本信息，文本挖掘的主要任務是分析文本的內容特征，發現文本中概念、文本之間的相互作用，為用戶提供相關知識和信息。2.文本挖掘過程3.文本挖掘和數據挖掘的區別區別項數據挖掘文本挖掘研究對象用數字表示的、結構化的數據無結構或者半結構化的文本對象結構關系數據庫自由開放的文本目標獲取知識，預測以后的狀態提取概念和知識方法關聯分析、k-最近鄰、決策樹、貝葉斯分類、神經網絡、支持向量機、粗糙集、聚類算法等提取短語、形成概念、關聯分析、文本分類、文本聚類等11.1.2數據預處理技術1.分詞技術（1）基于詞庫的分詞方法基于詞庫的分詞方法是按照一定的策略，將文本中的一部分可能被切成一個詞的小段與一個詞典（詞庫）里面的詞進行比較，若存在，則劃分為一個詞。根據采用的策略不同又分為正向最大匹配和逆向最大匹配等。例如，一個句子為S=“我們是學生”，長度n=5。正向最大匹配S1=“我們是學”S1=“我們是”S1=“我們”，找到了S2=“是學生”，S2=“是學”S2=“是”，找到了S3=“學生”，找到了所以S的分詞結果是“我們/是/學生”。例如，一個句子為S=“我們是學生”，長度n=5。反向最大匹配S1=“我們是學生”S1=“們是學生”S1=“是學生”S1=“學生”，找到了S2=“我們是”S2=“們是”S2=“是”，找到了S3=“學生”，找到了所以S的分詞結果同樣是“我們/是/學生”。（2）基于無詞典的分詞方法這種方法是基于詞頻的統計，將原文中任意前后緊鄰的兩個字作為一個詞進行出現頻率的統計，出現的次數越高，成為一個詞的可能性也就越大，在頻率超過某個預先設定的閾值時，就將其作為一個詞進行索引。2.特征表示文本特征指的是關于文本的元數據，分為描述性特征（如文本的名稱、日期、大小、類型等）和語義性特征（如文本的作者、機構、標題、內容等）。特征表示是指以一定特征項（如詞或描述）來代表文檔，在文本挖掘時只需對這些特征項進行處理，從而實現對非結構化的文本處理。這是一個非結構化向結構化轉換的處理步驟。特征表示模型中常用的是向量空間模型（VectorSpaceModel，VSM）。在向量空間模型中，一個文本集由若干文本組成，每個文本被表示為在一個高維詞空間中的一個特征向量：

di=（ti,1：wi,1，ti,2：wi,2，…，ti,m：wi,m）其中di為文本，ti,j表示第i個文本di中的第j個詞，wi,j表示詞ti,j在文本di中的權重。詞的權重一般采用wi,j=tf×idf方法來計算得到。

定義11.1詞頻tf（TermFrequency）是指一個詞在一個文本中出現的頻數，其定義為:其中，是詞ti,j在文本di中出現的次數，Ni是文本di中所有詞出現的總數。顯然，一個詞的tf值越大，則對文本的貢獻度越大。

定義11.2逆文本頻度idf（InverseDocumentFrequency）表示一個詞在整個文本集中的分布情況，其定義為其中，N是文本集中包含的文本總數，是包含詞ti,j的文本個數。

tf×idf是一種常用的詞權重計算方法，有多種形式。如果一個詞或短語在一篇文章中出現的詞頻tf高，并且在其他文章中很少出現，則認為該詞或短語具有律好的類別區分能力，適合用來分類。

tf×idf結合了兩者，從詞出現在文本中的頻率和在文本集中的分布情況兩方面來衡量詞的重要性。3.特征提取特征提取算法一般是構造一個評價函數，對每個特征進行評估，然后把特征按分值高低排隊，預定數目分數最高的特征被選取。在文本處理中，常用的評估函數有信息增益、期望交叉熵（ExpectedCrossEntropy）、互信息（MutualInformation）、文本證據權（TheWeightofEvidenceforText）和詞頻等。11.1.3文本結構分析文本結構分析的目的是為了更好地理解文本的主題思想，了解文本所表達的內容以及采用的方式。最終結果是建立文本的邏輯結構，即文本結構樹。如圖11.2所示是文章的形式結構圖，根結點是文章層，依次為節層、段落層、句子層和詞層。11.1.4文本分類

樸素貝葉斯分類算法

類中心最近距離分類算法

k-最近鄰分類算法

決策樹分類算法

神經網絡分類性能評估查全率是衡量所有實際屬于某個類別的文本被劃分到該類別中的比率。查全率越高表明分類器在該類上可能漏掉的分類越少，它體現了分類的完備性“查準率是衡量所有被劃分到該類別的文本中正確文本的比率。查準率越高表明在該類別上出錯的概率越小，它體現了分類的準確程度：11.1.5文本聚類

基于劃分的方法

基于層次的方法

基于密度的方法

基于網格的方法

基于模型的方法11.1.5文本自動摘要1.單文檔自動摘要2.多文檔自動摘要文本摘要是指從文檔中抽取關鍵信息，用簡潔的形式對文檔內容進行解釋和概括。這樣，用戶不需要瀏覽全文就可以了解文檔或文檔集合的總體內容。11.1.6文本關聯分析采用基于關鍵字的關聯分析是從文本集中收集詞或者關鍵字的集合，將問題轉化為事務數據庫中事務項的關聯挖掘。其基本過程是，調用關聯挖掘算法發現頻繁共現的詞或關鍵字，即頻繁項集，然后根據頻繁項集生成詞或關鍵字的關聯規則。例如，產生這樣的關聯規則：{數據挖掘，密度}→{DBSCAN，OPTICS}（支持度=30%，置信度=50%）11.2Web挖掘11.2.1Web挖掘概述1.什么是Web挖掘Web挖掘是指從大量的Web文檔集合中發現蘊涵的、未知的、有潛在應用價值的、非平凡的模式。它所處理的對象包括靜態網頁、Web數據庫、Web結構、用戶使用記錄等信息。2.Web挖掘與數據挖掘的區別Web挖掘和數據挖掘有著不同的含義。Web挖掘的研究對象是以半結構化和無結構文檔為中心的Web網頁，這些數據沒有統一的模式，數據的內容和表示互相交織，數據內容基本上沒有語義信息進行描述，僅僅依靠HTML語法對數據進行結構上的描述，可以說Web網頁的復雜性遠比任何傳統的文本文檔大。3.Web挖掘的基本步驟查找資源：從目標Web文檔中得到數據。信息選擇和預處理：從取得的Web資源中剔除無用信息和將信息進行必要的整理。模式發現：在同一個站點內部或在多個站點之間自動進行模式發現。模式分析：驗證、解釋所發現的的模式。4.Web挖掘的分類5.Web挖掘的主要應用（1）Web挖掘在搜索引擎中的應用（2）Web挖掘在電子商務中的應用（3）Web挖掘在知識服務中的應用11.2.2Web結構挖掘Web結構包括不同網頁之間的超鏈接和一個網頁內部的超鏈接，以及文檔URL中的目錄路徑結構等。Web結構挖掘通常用于挖掘Web網頁上的超鏈接結構，即Web超鏈接結構分析，從而發現那些包含于超文本結構之中的信息，幫助自動推斷出那些權威網頁，揭示出蘊含于文檔結構中的個性化信息。Web結構挖掘常見的算法有PageRank和HITS。1.PageRank算法PageRank算法是Web超鏈接結構分析中最成功的代表之一。該算法由Stanford大學的Brin和Page提出，是評價網頁權威性的一種重要工具。搜索引擎Google就是利用該算法和anchortext標記、詞頻統計等因素相結合的方法對檢索出的大量結果進行相關度排序，將最權威的網頁盡量排在前面，網頁的權威性就是通過PageRank值來度量的。PageRank算法的假設是：若一個網頁a有到另一個網頁b的超鏈接，則認為此超鏈接是網頁a的作者對網頁b的推薦，且兩個網頁的內容具有相似的主題。如果大量的網頁推薦同一個網頁，則后者被認為是一個權威網頁。所以一個網頁的入度越大，其權威就越高。一個擁有高權威值的網頁指向的網頁比一個擁有低權威值的網頁指向的網頁更加重要。如果一個網頁被其他重要的網頁所指向，那么該網頁也很重要。

定義11.4PageRank值的具體定義如下：將Web對應成有向圖，令u、v為網頁，記Fu為u所指向的網頁集合（即若v∈Fu，則網頁u含有指向網頁v的鏈接），記Bu為指向網頁u的網頁集合。令Nu=|Fu|，即Nu為網頁u上的鏈接數，則網頁u的PageRank值（u的重要程度）PR(u)可以簡單地定義為：其中，c為常量，是為了使PageRank值規范化的因子，它的選取不影響PageRank值計算結果的相對大小。該式的含義是：網頁u的PageRank值等于所有指向它的網頁為它傳入的PageRank值。如果網頁u上有Nu個鏈接，那么它會把自身的PageRank值PR(u)平均地傳出，即每一個鏈接傳出PR(u)/Nu。例如：PR(A)=PR(B)+PR(C)+PR(D)

【例11.1】假設a、b、c是3個網頁，其鏈接結構如圖11.6所示。在開始計算之前先要賦給每個網頁一個初始PageRank值（初始值的選取不會影響PageRank值計算的結果），假設為（0，2.5，2.5）。計算的過程如下。（1）第1次迭代：PR(a)=PR(c)/1=2.5PR(b)=PR(a)/2=0（式中PR(a)=0）PR(c)=PR(a)/2+PR(b)/1=2.5（式中PR(a)=0，PR(b)=2.5）（2）第2次迭代：PR(a)=PR(c)/1=2.5/1=2.5PR(b)=PR(a)/2=2.5/2=1.25PR(c)=PR(a)/2+PR(b)/1=1.25+0=1.25（3）如此迭代下去，直到收斂（通常收斂條件為兩次迭代之間的PageRank值小于某個閾值）。在上述PageRank值簡單的計算過程中，若某個網頁的鏈出數為零（也稱為孤立網頁），計算過程就無法進行下去。為此修改PageRank值的計算公式如下：其中，p1、p2、…、pN是N個被研究的網頁，L(pj)是網頁pj鏈出的數目。其基本思想是：瀏覽者在一組無限周期性循環鏈接中瀏覽某個網頁時，一段時間后會感覺到厭倦，然后隨機地跳轉到任何網頁。用q表示停留在當前網頁的概率，1-q表示隨機地跳轉到任何網頁的概率，q也稱為阻尼系數。當瀏覽到一個孤立網頁時，可以理解為可以隨機地跳轉到任何網頁，所以可用鏈出數為N。q一般取值為0.85。E(pi)為網頁pi的原始rank值，給不同的網頁賦予不同的值可以使搜索結果不同，可以用于提供個性化的搜索，一般地，置每個網頁的值為1，即：N個網頁的PageRank值是一個特殊矩陣中的特征向量，這個特征向量為：R是如下等式的一個解：如果網頁pi有指向網頁pj的一個鏈接，則l(pi，pj)=1；否則l(pi，pj)=0。可以使用冪法求解PageRank值，即轉換為求解的值，其中矩陣為A=q×P+(1-q)×E/N，P為概率轉移矩陣。冪法計算PageRank值的算法如下：輸入：矩陣A，閾值ε輸出：PageRank矩陣R（表示N個網頁的PageRank值）方法：其過程描述如下：X為任意一個初始向量，用以設置每個網頁的初始PageRank值，一般均為1;R=AX;while(true) //迭代{if(|X-R|<ε) //如果最后兩次的結果近似或者相同，返回R returnR;else{ X=R;

R=AX;}}

【例11.2】假設網頁鏈接結構圖如圖11.6所示的，即N=3。設閾值ε的各元素值為0.01，采用PageRank算法求各網頁PageRank值的過程如下。（1）求A矩陣①求網頁鏈接矩陣、概率矩陣和概率轉移矩陣由圖11.6直接得到網頁鏈接矩陣P。圖中網頁a鏈向網頁b和c，所以一個用戶從網頁a跳轉到網頁b或c的概率各為1/2。因此由P根據每個網頁的鏈出數求出概率矩陣P'。再將P'轉置，得到相應的概率轉移矩陣P'T，如圖11.8所示。②求E/N。求E/N的結果如下：③求A矩陣A=q×P+(1-q)×E/N=0.85×P+0.15×E/N，其結果如下：初始每個網頁的PageRank值均為1，即（2）循環迭代計算PageRank值。①第1次迭代②因為X與R的差別較大，第2次迭代。……④第9次迭代。此時收斂條件成立（兩次迭代之間的PageRank值小于等于0.01），所以最終結果為（1.16，0.64，1.20），這樣c網頁最權威。PageRank算法的優點是：它是一個與查詢無關的靜態算法，所有網頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應時間。其缺點是：人們的查詢具有主題特征，PageRank忽略了主題相關性，導致結果的相關性和主題性降低，例如，許多鏈接只是為導航和廣告，PageRank可能錯誤地計算其重要性；另外，這樣計算的結果是舊網頁等級總會比新網頁高，因為即使是非常好的新網頁也不會有很多上游鏈接，除非它是某個站點的子站點。2.HITS算法HITS（Hyperlink-InducedTopicSearch）是1998年由Kleinberg提出的，它是基于鏈接的主題提取算法。所依賴的是超鏈接環境下鏈接結構的分析。在PageRank算法中，向外鏈接的權值是平均的，沒有考慮不同鏈接的不同重要性。事實上，不同鏈接的重要程度是有很大差異的。

定義11.5中心網頁（hub）是指一個指向權威網頁的超鏈接集合的Web網頁。也就是說，中心網頁是指那些本身的內容雖然未必具有權威性，但卻包含了多個指向權威網頁的超鏈接的網頁。

定義11.6權威網頁（authority）是指一個被多個hub頁指向的權威的Web網頁。也就是說，權威網頁指那些與查詢主題的上下文最為相關并且具有權威性的網頁，是人們對于主題查詢最關心的網頁。HITS算法描述了權威網頁和中心網頁之間的一種依賴關系：一個好的中心網頁應該指向很多好的權威性網頁，而一個好的權威性網頁應該被很多好的中心性網頁所指向。HITS算法為每個網頁pi分配兩個度量值：中心度hi和權威度ai。設向量a=（a1，a2，…，aN）代表所有基礎集合中網頁的權威度，而向量h=（h1，h2，…，hN）代表所有的中心度。最初，將這兩個向量均置為（1，1，…，1）T。對于任何一個網頁pi，其權威值ai通過指向它的所有網頁的中心度求和得到，其中心度hi可以通過它所指向的網頁的權威值求和得到。為此定義兩個操作：操作In(a)使向量a=ATh操作Out(h)使向量h=Aa。例如，如圖11.8所示，有3個網頁p1、p2和p3鏈入到p4網頁，則In(a4)=h1+h2+h3；網頁p4鏈出到p1、p2、p3網頁，則Out(h4)=a1+a2+a3。反復迭代上述兩個操作，每次迭代后對向量a和h規范化，以保證其數值不會使計算溢出。例如：HITS算法如下：輸入：矩陣A，自然數k輸出：a和h向量（表示N個網頁的權威度和中心度）方法：其過程描述如下：z=(1，1，…，1)T

//N個1初始化向量a和h為z;for(i=1;i<=k;i++){計算a=ATh; //執行In(a)操作計算h=Aa; //執行Out(h)操作對向量a和h進行規范化;}將a向量中最大的前c個值作為權威網頁輸出,將h向量中最大值作為中心網頁輸出;HITS算法的優點是收斂速度快，可以找到一些不包含關鍵字但與主題高度相關的網頁，因此可以獲得比較好的查全率，且具有很高的穩定性。其缺點是可能出現主題漂移和不合理的相互加強關系，因為在迭代過程中權威網頁和中心網頁交互傳播，兩者之間總是相互加強的。11.2.3Web內容挖掘Web內容挖掘可以看作是Web信息檢索和信息抽取的結合。Web內容挖掘是指對Web上大量文檔集合的“內容”進行總結、分類、聚類、關聯分析以及利用Web文檔進行趨勢預測等，是從Web文檔內容或其描述中抽取知識的過程。Web內容挖掘可分為Web文本挖掘和Web多媒體挖掘，針對的對象分別是Web文本信息和Web多媒體信息。11.2.4Web使用挖掘Web使用挖掘是指從服務器端記錄的客戶訪問日志或從客戶的瀏覽信息中抽取感興趣的模式。歸納起來，主要包括Web客戶挖掘和Web日志挖掘等。1.Web客戶挖掘①客戶發現②發現重要頁面③客戶細分④客戶保持⑤防范客戶的欺詐行為⑥客戶升級2.Web日志挖掘通過對Web日志預處理后，就可以根據具體的分析需求選擇訪問模式發現的技術，常用的挖掘算法如下：統計分析：是指通過分析服務器日志文件，獲取不同種類的統計分析結果，如用戶在某個網頁上駐留時間、用戶瀏覽路徑長度等。許多Web跟蹤分析工具可以定期報告一些統計分析結果，如最頻繁訪問頁，網頁的平均駐留時間、瀏覽某個網站的平均路徑長度等。關聯分析：用于發現網頁之間的依賴關系，如找到這樣的關聯規則：70%訪問羽毛球網頁的人也訪問了乒乓球網頁。通過關聯分析可以用來改進網站的設計結構，為用戶推薦相關網頁。時序模式發現：主要找出網頁（組）依照時間順序出現的內在模式。例如，9.81%的訪問者在瀏覽了Atlanta主頁后緊接著瀏覽了Sneakpeek的主頁。通過發現時序模式，能夠預測用戶的將來訪問模式，有助于開展有針對性的廣告服務等。分類和聚類：分類是指將一個對象分到事先定義好的類中，在Web日志挖掘中，分類可用于為一類特定用戶建立用戶檔案，通常使用的監督學習算法有決策樹、貝葉斯分類器、kNN分類器和支持向量機等。聚類將具有相似特征的對象聚在一起形成一個簇，在Web日志挖掘中，有兩種聚類，即用戶聚類和網頁聚類，前者用于向用戶提供個性化服務等，后者可于發現具有相關內容的網頁組等。導航模式發現：Web服務器中的每個會話記錄了一個用戶瀏覽網站的“蹤跡”，每條“蹤跡”，是一個按照用戶訪問時間排序的網頁序列。導航模式發現就是尋找在一個Web網站中被最頻繁訪問的路徑，例如某網站發現這樣的導航模式：70%訪問/company/product2的用戶是從company開始，然后沿/company/new到達該網頁的。11.2.5Web挖掘的發展方向Web數據挖掘中內在機理的研究。Web知識庫（模式庫）的動態維護、更新，各種知識和模式的融合、提升，以及知識的評價綜合方法。半結構、非結構化的文本數據、圖形圖像數據、多媒體數據的高效挖掘算法。Web數據挖掘算法在海量數據挖掘時的適應性和時效性。基于Web挖掘的智能搜索引擎的研究。智能站點服務個性化和性能最優化的研究。關聯規則和序列模式在構造自組織站點的研究。分類在電子商務市場智能提取中的研究。11.3空間數據挖掘空間數據挖掘與一般數據挖掘的區別在于：空間數據挖掘的研究對象主要是空間數據庫，它不僅存儲了空間對象的屬性數據和幾何屬性，而且存儲了空間對象之間的空間關系（拓撲關系、度量關系、方位關系等）；因此，其存儲結構、訪問方式、數據分析和操作等都有別于常規的事物處理型數據庫模式。11.3.1空間數據概述1.空間數據的基本類型空間對象特征主要包含空間特征和屬性特征，所以空間數據通常分為空間數據和屬性數據。2.矢量數據模型矢量數據利用了幾何圖形例如點、線和面來表現空間對象。以二維空間為例，點對象的表示為：[地物編號；（x,y）]。例如，如圖11