第11章其他挖掘方法

第11章其他挖掘方法

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

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

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

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

樸素貝葉斯分類算法

類中心最近距離分類算法

k-最近鄰分類算法

決策樹分類算法

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

基于劃分的方法

基于層次的方法

基于密度的方法

基于網(wǎng)格的方法

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

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

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

R=AX;}}

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

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

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

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