第11章其他挖掘方法

第11章其他挖掘方法

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

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

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

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

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

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

樸素貝葉斯分類(lèi)算法

類(lèi)中心最近距離分類(lèi)算法

k-最近鄰分類(lèi)算法

決策樹(shù)分類(lèi)算法

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

基于劃分的方法

基于層次的方法

基于密度的方法

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

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

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

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

R=AX;}}

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

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

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

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