数据挖掘课件

文本檢索三、隱含語義索引上面所介紹的都是將文檔表示為T維詞條權向量的。但用戶可能提出的查詢中的詞條不在用在索引文檔的詞條中。例如，從詞條相似性的角度來看，詞條“數據挖掘”和“知識發現”設有什麼直接的共同點。然而，從語義角度來看，這兩個詞條有很大的相同點。因此，在提出一個包含其中之一的查詢，那麼應該考慮包含另一個的文檔。解決方法是：預先創建一個把語義相關詞條連接在一起的知識庫(同義詞典或本體集)。然而，這樣的知識庫存在固有的主觀性，因它取決於從何種角度來把詞條和語義內容聯繫起來。隱含語義索引(latentsemanticindexing)(LSI)—一種可選的有趣又有價值的方法。該方法不是僅使用詞條出現資訊，而是從文本中提取出隱藏的語義結構資訊。實際上，LSI採用T維詞條空間中前k個主成分來近似原始的T維詞條空間，使用N×T的文檔-詞條來估計這個方向。主成分方法的直觀解釋是，由原始詞條的加權組合所構成的單個向量可以非常好的近似由大得多的向量集合所起的效果。於是可以把原來的N×T大小的文檔-詞條矩陣簡化為N×k的矩陣(k<<T)，對於固定的查全率，和前面討論的向量空間方法相比，LSI可以提高查準率。對表9-2中的矩陣M計算奇異分解式(SVD)。目標是，找一個分解式M=USVT。式中U是一個10×6的矩陣，它的每一行是相對特定文檔的權向量，S是每個主成分方向特徵值的6×6對角陣，6×6的矩陣VT的各列提供了數據的新共軛基，被稱為主成分方向。S矩陣的對角線元素是(協方差矩陣對應…):λ1,…,λn={77.4,69.5,22.9,13.5,12.1,4.8}可見，前兩個主成分捕捉了數據中的主要變化，和直覺一致。當使用兩個主成分時，那麼二維表徵所保留的變化比例0.925，資訊丟失僅7.5%。如果我們在新的二維主成分空間來表示文檔，那麼每篇文檔的係數對應於U矩陣的前兩列(兩個主成分對應的特徵向量，即新的文檔權值)：這兩列可看作新的偽詞條，其作用相當於原來6個詞條的線性組合。看一下前兩個主成分方向可以得到的資訊(新共軛基)：V1=(0.74,0.49,0.27,0.28,0.18,0.19)V2=(-0.28,-0.24,-0.12,0.74,0.37,0.31)這兩個方向是原來6維詞條空間中數據最分散(具有最大方差)的方向。每方向更突出前兩個詞條(查詢,SQL)：實際上這是描述和數據庫有關文檔的方向。第二方向突出了後三個詞條—回歸、似然和線性，這是描述和回歸有關文檔的方向。圖9-4以圖形方式說明了這一點(將上面數據用圖表示)。當把文檔投影到由前兩個主成分方向所決定的平面量，兩個不同組的文檔分佈在兩個不同的方向上。注意文檔2幾乎落在文檔1上，使其有點模糊。文檔5和文檔10的詞條向量最大，因此離原最遠。從圖可看出，文檔間的角度差異顯然是相似性的一個有用指標，因為回歸和數據庫文檔在平面上是圍繞兩個不同的角度聚成簇的。主成分方法的應用例子：考慮一個新的文檔D1，詞條“查詢”在該文檔中出現50次，另一個文檔D2，包含詞條“SQL”50次，兩且兩篇文檔都不包含其他的詞條。如果直接使用關鍵字表示，這兩個文檔不會被認為是相似的，因為它們沒有包含相同的詞條。然而，如果使用兩個主成分詞條來表示這兩篇文檔，並把它們投影到這個空間中，那麼正如圖9-3所示，二者都被投影到“資料庫”方向，儘管它們都僅包含和數據庫有關的三個詞條中的一個。從計算的角度來看，直接計算主成分向量(例如求解相關矩陣或協方差矩陣的特徵值)通常要麼是計算上不可行，要麼是數值上不穩定。實踐中，可以使用特別適合高維稀疏矩陣的SVD技術來估計PCA向量。四、文檔和文本分類上面的討論可以看出使用詞條向量來表示文檔為文檔分類提供了一種自然框架。有了這一框架對於預先有標籤的文檔我們可以使用有指導分類技術，對於沒有標籤的文檔我們可以使用無指導學習(聚類)框架。典型詞條向量的維數都是非常高的，基於這一事實，高維空間中的準確性和高效性通常是選擇分類器的首要標準。對於文檔表示來說，像一階貝葉斯分類器這樣的分類模型或者是加權線性組合可工作得很好。在文檔分類這一領域還有很多有趣的問題可以探討，例如認為每篇文檔屬於多個主題(類)而不是僅屬於某個類是有意義的。因此在分類時不再限於各個類是相互排斥的這一通用框架。一種簡單的方法是為每個類分別訓練一個二值分類器，此方法僅當類別總數較少時是可行的。9.4對個人偏好建模一、相關性回饋文本檢索系統比其他數據挖掘演算法更具有交互性。特別是，提出特定查詢Q的用戶可能願意反復使用演算法進行一系列不同的檢索嘗試，並通過為返回的文檔標記出相關與否來給演算法提供用戶回饋。在這方面，Rocchio演算法應用的特別廣泛。演算法的基本思想：從根本上講相關性是以用戶為中心的，也就是，如果用戶可以(理論上)看到所有的文檔，那麼原則上他可以把所有文檔分成兩個集合，相關的R和不相關的NR。如果給定了這兩個集合，那麼可以證明最佳查詢(利用向量模型)為：其中D代表文檔的詞條向量表示，它的標籤(用戶作出的)是已知的。在實際應用中，一般一個用戶不會把資料庫中所有文檔都標上分類標籤。相反，用戶是從一個特定查詢Qcurrent開始的，可以把這個查詢看作是相對Qoptimal次優的。演算法使用這個初始查詢返回文檔的一個較小子集，然後用戶把該子集的文檔標記為相關R’和不相關NR’。Rocchio演算法按下麵的方式來提煉查詢：該演算法使查詢朝著相關文檔的均值向量靠近，並遠離不相關文檔的均值向量。參數α、β和γ是正的常數(啟發式選取)，它們控制著新查詢對最近標記文檔的敏感性(相對於當前查詢向量Qcurrent)。不斷重複這個過程，把新的查詢Qnew與文檔集合進行匹配，然後讓用戶再一次標記文檔。原則上講，如果每一次迭代所作的標籤是一致的，那麼Qnew會逐步逼近Qoptimal。實驗證據表明，利用用戶回饋確實提高了查準率-查全率性能。然而，在實際應用時還有一些細節問題需要確定，比如顯示給讀者的文檔數量；使用的相關文檔和非相關文檔的相對數量；選取非相關文檔的方法等等。二、自動推薦系統9.5圖像檢索隨著圖像和視頻數據集合在的不斷增加，人們對圖像檢索的興趣也日益濃厚。手工對圖像進行注釋具有浪費時間、主觀性強等缺點，而且可能因為注釋者的看法不同而丟失圖像的某些特徵。一幅圖像可能要使用一千個詞來描述,但是到底使用哪一千個單詞卻不是簡單的問題.因此，開發高效而又準確的演算法來根據內容對圖像資料庫進行查詢是很有必要的。比如，檢索系統允許用戶提交這樣的查詢“找出和這幅圖像最相近的K幅圖像”或者“找出和這組圖像屬性最匹配的K幅圖像”。一、圖像理解圖像數據查詢是非常困難的任務。從某種意義上來說尋找彼此相似的圖像等價於求解圖像理解問題，也就是從圖像數據中抽取語義資訊。在這方面人類非常出色，然而，關於模式識別和電腦視覺的幾十年研究已經表明，要用電腦演算法來“複製”人類在視覺理解和識別方面的能力是極端困難的。舉例來說，嬰兒可以很快學會要任何背景下辨別各種動物，比如各種大小、顏色、體型的狗，而這種完全無約束的識別問題超出了目前任何視覺演算法的能力。因此，目前的大多數圖像檢索演算法還僅依賴於相當低級的可視提示。二、圖像表示為了便於檢索，可以把原始的像素數據抽象為特徵表示，通常是以類似色彩和紋理這樣的原語來表示圖像特徵。類似於文本表達方式，仍然採用數據矩陣格式來表示圖像，每一行代表一幅特定的圖像；每一列代表一個圖像特徵。這樣的特徵表示通常比直接的象素測量值對縮放和平移變化更有效。原始的像素數據被簡化為標準的N×p數據矩陣，在這個矩陣中每一幅圖像被表示為特徵空間中的一個p維向量。通過計算圖像局部化子區域的特徵可以粗略的引入空間資訊。例如，我們可以計算一幅1024×1024像素圖像的每個32×32子區域的顏色資訊。這樣便可以在圖像查詢中使用粗略的空間約束，比如“尋找中央主要為紅色，四周為藍色的圖像”。應用於圖像的根據內容檢索系統的一個著名商業實例是IBM開發的根據圖像內容查詢(QBIC)系統。該系統允許用戶互動式的查詢圖像和視頻數據，查詢的依據可以是圖像實例、用戶輸入的草圖、顏色和紋理模式、對象屬性等等。允許對景物、對象以及視頻幀序列或者是這些的任意組合進行查詢。QBIC系統使用了多種特徵以及多種和距離有關的尺度用於檢索：

相對整幅圖像進行空間平均的三維顏色特徵向量，採用歐氏距離尺度。

K-維顏色直方圖，直方圖的柱位可以使用像使用K-平均這樣的基於劃分聚類演算法來選取。採用馬氏(Mahalanobis)距離尺度來表徵顏色相關性。

衡量粒度/比例、方向性和對比度特徵的三維紋理向量。採用加權的歐氏距離尺度來計算距離，權的缺省值為各個特徵方差的倒數。

20-維的對象形狀特徵，比如區域、圓度、離心率、軸方向、各種矩等等。採用歐氏距離來計算相似性。三、圖像查詢和文本數據的情況相同，用於抽象表示圖像的方法決定了支持何種類型的查詢和檢索操作。特徵表示提供了一種表示查詢的語言。有兩種形式來表示查詢。一種方法：通過樣例查詢，在這種樣例中，我們既可以為要尋找的目標提供一個圖像樣例，也可以勾畫出感興趣圖像的形狀。接下來便計算樣例圖像的特徵向量，然後再把計算出的查詢特徵向量和數據庫中預先計算出的特徵向量進行匹配。另一種方法：直接以特徵表徵表達查詢，比如“尋找這樣的圖像，50%的區域為紅色，並且包含具有特定方向和粒度特徵的紋理”。表示圖像和查詢的特徵向量形式與用於文本檢索的向量空間表示非常相似。一個主要差異是圖像特徵通常是一個實數，而詞條向量中的詞條分量通常是某種形式的加權計數，代表了這個詞條在文檔中出現的頻繁程度。不過，這兩種問題都是根據內容檢索的問題，這一共同特徵決定了用於文本檢索的很多技術也適應於圖像檢索應用。9.6時間序列和序列檢索在時間序列和序列數據集合中高效而又準確的定位有意義模式的問題對於很多應用都有重要意義，比如複雜系統的診斷和監控、生物醫學數據分析以及對科研和商業時間序列的探索性數據分析。這樣例子包括：

找出這樣的顧客：他們相對時間的消費模式和給定的消費特徵相似；

在複雜的即時監控和故障診斷系統中，搜索出與當前異常感測器信號相似的以前實例；

在蛋白質序列中進行有雜訊子串的匹配。和二維圖像數據相比，可以把序列數據看作是一維的。時間序列數據是相對時間測量出來的一系列觀察結果，因此可以用時間變數t來索引觀察值。序列數據的概念比時間序列數據的概念更廣，因為序列數據不一定是時間的函數。例如，在計算生物學中，蛋白質是以其在蛋白質序列中的順序位置來索引的。一、時間序列數據的全局模型傳統的時間序列建模技術(比如統計方法)主要是建立在全局線性模型基礎上的，典型的例子是Box-Jenkins自回歸模型族，該方法把當前值y(t)模擬成過去值y(t-k)的加權線性組合，再加上一個額外的雜訊項：式中αi是加權係數，e(t)是時間t的雜訊(通常被假定為均值為零的高斯函數)。Box-Jenkins方法的一個重要貢獻是，如果在時間序列中存在可識別的系統性非平穩分量(比如某種趨勢)，那麼很多情況下可以把這個不平穩分量刪除使這個時間序列變成平穩的形式。例如，像國內生產總值和道瓊斯指數這樣的經濟指標中包含著固有的上升趨勢(總體而言)，通常要在建模前將這種趨勢刪除。對於非平穩性比較複雜的情況，另一種有用方法是假定這個信號是相對時間局部平穩的。非線性的全局模型對上面公式進行了推廣，比如可以允許y(t)非線性地依賴過去值：其中g(.)是非線性的。從數據挖掘的角度來看，如果我們假定這樣的全局模型充分地描述了潛在的時間序列，那麼我們就可以使用模型參數(比如上面的各個權)作為表示數據的基礎，而不使用原始數據本身。通過把時間序列表示為參數向量，把序列問題轉化為本章前面所介紹的文本和圖像的方法，便可以在參數向量空間中定義相似性尺度、在這個空間中定義根據內容檢索的查詢。二、時間序列的結構和形狀考慮一個實數值時間序列的子序列Q=[q(t),…q(t+m)]，和一個長得多的歸檔時間序列X=[x(t),…,x(T)]，前者稱為查詢序列。我們的目標是在X中找到和Q最相似的一個子序列。現實情況下，X可能是由許多單個的時間序列組成的，但是為了簡單，我們假定它們已經被合成一條長的序列。並且假定X和Q都是使用相同採用時間間隔測量的。上一節所講的一般方法僅描述一個時間序列的全局特徵，根本沒有提供對局部形狀的描述，比如峰值等。通常，全局模型平均了這些局部的結構特徵。然而，對於很多時間序列來說，用結構特徵來描述它們會更自然。兩種查詢方法：◆第一種：在整個X數據中序列化在掃描查詢Q，順著X每次把查詢Q移動一個時間點，同時計算出每個時間點的距離尺度。該方法的主要特點是，①開銷大。②其焦點集中在低層次的數據採樣點，而不是高層次的結構特徵，比如峰值、高原、走勢和波谷等。③直接計算歐氏距離也對查詢Q和數據X中的微小岐變異常敏感。◆第二種：先局部化地估計查詢Q和歸檔X的基於形狀特徵，然後在較高層次上進行匹配。其特點是，①具有計算優勢，因為抽象實質上是一種壓縮數據，可以把信號的很多無關細節都忽略掉。②它可以以一種適合於人類解釋的形式提取結構化的資訊。第二種技術的一個典型實例是用分段線性化的片段來逼近信號。然後把分成段的序列表示為局部參數化的曲線列表，而後便可以直接根據參數描述計算結構特徵。可以使用概率模型把期望的形狀和變化性按這些特徵進第9章根據內容檢索本章目標討論圖像檢索演算法中表示和檢索問題。介紹匹配時間序列和序列的基本概念。9.1簡介傳統的資料庫查詢定義為：查詢是一種返回精確匹配指定要求的記錄集合(或表項集合)的操作。例如，查詢“[level=MANAGER]AND[age<30]”，返回的結果是有具有重要職務的年輕雇員的列表。但在數據分析時，所感興趣的是更一般的但不很精確的查詢。例如，假設已知一個患者的人口統計學資訊(比如年齡性別等等)、血液和其他常規檢查的結果，以及生物醫學方面的時間序列、X-光和圖像。為了輔助對這個患者進行診斷，醫生希望瞭解醫院資料庫中是否包含類似的患者，如果有類似的患者，那麼他們的診斷、治療方法和最終結果如何？這個問題的難點在於如何根據不同的數據類型(多元變數、時間序列和圖像數據)來判斷各個患者間的相似性。這類問題採用精確匹配是行不通的，因為資料庫中不可能存在各項指標完全匹配的患者。因此，需要解決的是在資料庫找出和指定查詢或指定對象最相似的k個對象的各種技術問題。可以把這種形式的檢索看是互動式的數據挖掘，因為用戶直接參與了探索數據集的過程—指定查詢並解決匹配過程得到的結果。如果數據集是根據內容批註的，那麼檢索問題就簡化為標準的資料庫索引問題，如果資料庫沒有被預先索引，我們僅有要尋找目標Q(查詢模式)的一個實例，根據這個查詢模式Q，我們要推論出數據集中哪些其他對象和它相近。這種檢索方法被稱為根據內容檢索(retrievalbycontent)，它的最著名應用是在文本中檢索。在文本檢索中，查詢模式Q通常是很短的(查詢辭彙列表)，然後在很大的文檔集合匹配這個模式。這類問題由三個基本部分組成：1.如何定義對象間的相似尺度；2.如何實現高計算效率的搜索演算法(對於給定的相似尺度)；3.如何在檢索過程中融入用戶的回饋並進行交互。本章主要討論第一和第三個問題，第二個問題通常是一種索引問題(一個好的索引可以極大提高效率)。在下面的分析中，我們使用“相似”這個詞，又使用“距離”這個詞。對應的是相似尺度最大化和距離尺度最小化，其他章節的相似度和相異度。根據內容檢索需要解決的幾個問題：1.如何客觀地評估特定檢索演算法的性能。2.如何決定用以計算相似尺度的表示。例如，通常用顏色、紋理和相似特徵來地、表示圖像；用單詞的出現次數來表示文本。9.2檢索系統的評價一、評價檢索性能的困難之處在分類和回歸中，總能以一種客觀的方式來評判模型的性能。然而，對於根據內容檢索來說，評價一個特定演算法或技術的性能要複雜和棘手的多。主要的難點是檢索系統的最終性能尺度是由檢索出的資訊對用戶的實用性來決定的。檢索是一種以人為中心的交互過程，這給評價檢索性能帶來了很大困難。首先我們假定相對一個特定的查詢，可以把對象標記為相關或不相關。換句話來說，對於任一個查詢Q，我們假定存在一個二值分類標籤的集合，該集合對應數據中的所有對象，指出哪個對象是相關的，哪個是不相關的。最後我們假定已經以某種方式為每個對象附加標籤(假定是以一種比較客觀並與人類判相一致的方式)。基於這些假定，就可以把檢索問題看作一種特殊形式的分類問題—類標籤依賴於查詢Q，也就是，“對於查詢Q相關還是不相關”，然後相對Q來估計資料庫中對象的類標籤。檢索分類的特點：1.分類變數的定義是由用戶掌握的(用戶定義查詢Q)，因此每次運行系統時都可能變化。2.主要目標不是分類出資料庫的所有對象，而是返回與用戶查詢最相關的對象。二、查準率對查全率假定我們在一個獨立的檢驗數據集上評價一個指定檢索系統相對特定查詢Q的性能。檢驗數據中的對象已經被預先分類為相對於查詢Q是相關還是不相關。假定這個檢驗數據集沒有被這個檢索演算法使用過，我們可以把檢索演算法想像為就是要對這個數據集中的對象作出分類(按照相對於查詢Q的相關性)。如果這個演算法是使用距離尺度(數據集中的每個對象相對於Q的距離)來排列對象集合的，那麼這個演算法通常具有一個閾值參數T。演算法將返回KT個對象—和查詢對象Q的距離小於T的KT個對象的有序列表。通過改變T來改變檢索系統的性能。假定對於有N個對象的檢索數據集合，檢索系統返回了KT個可能相關的對象，那麼可以用表9-1來歸納這個演算法的性能。表9-1中，實驗中已經標記出了各文檔相關還是不相關(相對於查詢Q)。列對應於真實情況，行對應於演算法對文檔的判斷。TP，FP，FN，TN分別對應於真的正，假的為正，假的為負和真的為負，其中正負是指演算法所給出的分類是否相關。理想的檢索演算法將產生FP=FN=0的對角矩陣。其中:N=TP+FP+TN+FN(對象總數)KT=TP+FP(返回對象的數量)TP+FN是相關對象的總數。查準率：TP/(TP+FP)(行)查全率：TP/(TP+FN)(列)存在著這樣一個問題：當KT增大時(提高閾值將返回更多的對象分類為相關)，查全率上升(極限情況，可以返回所有對象，查全率為1)，然而查準率會下降。如果使用不同的閾值T來運行檢索演算法，那麼會得到一系列(查全率，查準率)的點對。反過來使用這些點對描出這個特定檢索演算法(相對於查詢Q、特定的數據集、以及數據標籤)的查全率-查準率曲線，如圖9-1所示。圖9-1是三種假想查詢演算法的查全率-查準率曲線。由圖可見，在大多數情況下，難以判斷哪一種演算法有絕對優勢，因此不能完全根據查全率-查準率曲線來判定一個演算法就比另一個演算法更好。儘管如此，這些曲線對於在一定操作條件範圍內評價檢索演算法的相對、絕對性能還是有價值的。三、查準率和查全率的實踐應用查準率-查全率評價在文本檢索中一直特別流行。文本檢索會議(TREC)就是查準率-查全率評價試驗的一個大型例子。在這項試驗中使用幾個G位元組大小的文本文檔數據集合，大約是由一百萬個獨立的文檔(對象)組成的，平均每個文檔有500個術語索引。主要問題是如何評價相關性，特別是如何決定相關文檔總數以計算查全率。如果使用50個不同查詢，那麼就需要每個人工裁判員給出5千萬個分類標籤!由於TREC會議的參展系很多(>30),所以TREC裁判員把他們的裁判範圍限制在所有檢索系統所返回文檔的前100篇文檔的聯合，並假定這個集合通常已經包含了幾乎所有的相關文檔。因此，每個裁判者僅需作出幾千個相關性判斷，而不是幾千萬個。9.3文本檢索傳統上，一直把對文本資訊的檢索稱為資訊檢索(IR)，互聯網搜索引擎的出現使其成為一個備受關注的課題。文本由兩個基本單位組成，即文檔和詞條。按照IR慣例，文本查詢是由詞條集合指定的。一、文本的表示大多數關於文本檢索的研究集中在尋找支持如下兩個特徵的通用表示:1.盡可能保留數據語義內容的能力；2.可以高效的計算查詢和文檔間的距離。目前的IR系統通常依賴於簡單的詞條匹配和計數技術，即通過詞條出現次數向量隱含並近似地捕捉了文檔語義。假定已經預先定義了要檢索的一系列詞條tj,1≤j≤T，然後把每一篇文檔Di，1≤i≤N表示為詞條向量：Di=(di1,di2,…,diT)其中dij表示第j個詞條在第i篇文檔中出現的某種資訊，各個dij被稱為詞條權。在布爾表示中，dij取1或0。在向量空間表示中，可以是某個實數值的數字。下麵考慮一個涉及10篇文檔和6個詞條的簡單例子。六個詞條是：t1=資料庫，t2=SQL，t3=索引，t4=回歸t5=似然，t6=線性的。表9-2為10×6的文檔-詞條頻率矩陣M。文檔間的距離尺度採用余弦距離：

這是兩個向量夾角的余弦(等價於把它們標準化為單位長度後的內積)，因此它反映了兩個向量的詞條分量的相對分佈相似性。該距離尺度在IR試驗中特別有效。同樣地，我們也可以使用其他距離尺度，如歐氏距離。下圖是表9-2中的文檔-詞條頻率矩陣的像素形式距離矩陣。上圖是歐氏距離矩陣，下圖是余弦距離矩陣。較亮的方塊表示兩篇文檔比較接近，較暗的地方表示不相近。對於歐氏距離，白色對應兩篇文檔間的距離為0；黑色對應最大距離。對於余弦距離，較亮的像素對應於較大的余弦值(較小的角度)；較暗的像素對應於較小的余弦值(較大的角度)。在兩種距離矩陣中都可以清楚的看出存在兩個文檔簇，一類是關於資料庫的文檔，另一類是關於回歸的文檔，圖中的兩個顏色較淡的方塊區域。從圖中可見，余弦距離更好的區分了兩個組。在歐氏距離中，文檔3和文檔4(資料庫簇中)到文檔5(另一篇資料庫文檔)的距離比到文檔6,8和9(關於回歸的文檔)的距離還要遠。導致這一現象的原因就是文檔3和4(以及6,8和9)與文檔5相比更靠近原點。余弦距離發揮了基於角度距離的優點，更強調各個詞條的相對分佈，因此產生的區分更加明顯。上例的一個推廣，對於具有N篇文檔的T個詞條的集合，我們可以構造一個N×T的矩陣。通常這個矩陣是非常稀疏的。比如上面提到的TREC文檔群大約僅0.03%的單元是非零的。在文本檢索系統時，出於對詞條-文檔矩陣稀疏性的考慮，原始的文檔-詞條矩陣被表示為一種倒排檔結構(而不是直接表示為矩陣形式)，也就是按照T個詞條來索引檔，每個詞條tj指向一個N個數字的列表，這些數字描述了每篇文檔中出現該詞條的情況(dij,j固定)。二、匹配查詢和文檔也可以使用與文檔相同的基於詞條的表徵來表達查詢。實際上，可以把查詢本身當作一篇文檔來表示，只不過是通常查詢僅包含很少的詞條。在向量空間中，可以把查詢表示為一個權向量。詞條沒有出現時權值為0，詞條在查詢出現時，用戶可以指定權值，以表示每個詞條的相對重要性(權值限定在0～1之間)。令Q=(q1,…,qT)為查詢權向量。最簡單的形式，權值要麼為1要麼為0。下麵二值模式的例子，考慮三個查詢，每個都是由一個詞條組成的，分別是“資料庫”

，“SQL”，“回歸”。根據前面例子，可以把這三個查詢表達為三個向量：(1,0,0,0,0,0)、(0,1,0,0,0,0)和(0,0,0,1,0,0)。利用余弦距離在表9-2所示的數據中匹配這三個查詢，得到最相近的文檔，分別是d2、d3和d9。更一般的情況，是如何設置匹配查詢中權值，以提高檢索的性能。許多IR文獻有相關的報導。已經證明一種被稱為TF-IDF加權的特殊加權模式在實踐中特別有效。TF(termfrequency)代表詞條頻率，表9-2中的文檔-詞條示例矩陣就是以TF的形式表示的。然而，如果一個詞條在文檔集合中的很多文檔中頻繁出現，那麼利用TF代表權進行檢索的判斷力就很小了，也就是它會提高查全率但是查準率可能很差。文檔頻率倒數-IDF(inverse-document-frequency)權可以提高判別力。IDF定義為：log(N/nj)，式中N為文檔總數，nj為包含詞條j的文檔數量。IDF權偏向於僅在很少文檔中出現的詞條，也就是說它是有判別力的。採用對數形式是使這個權對文檔總數N不特別敏感。TF-IDF權就是特定詞條在特定文檔中的TF權和IDF權的乘積。表9-2中的文檔矩陣所產生的IDF權是：(0.105,0.693,0.511,0.693,0.357,0.693)。由此可得TF-IDF文檔-詞條矩陣(即把表9-2中的TF權乘以對應的IDF權)，如表9-3所示。在文檔中匹配查詢的經典方法是：●把查詢表示為詞條向量，1表示詞條出現在查詢中，0表示不出現；●利用向量分量的TF-IDF權把文檔表示為詞條向量；●使用余弦距離尺度按照文檔到查詢的距離來排列文檔。表9-4顯示了一個簡單查詢實例，比較了TF和TF-IDF方法。第八章關聯規則本章目標舉例說明使用HITs、LOGSOM和路徑遍曆演算法來進行Web挖掘的可行性。在指定提煉和萃取階段的基礎上定型文本挖掘的構架。關聯規則是數據挖掘的主要技術之一，也是在無指導學習系統中挖掘本地模式的最普遍形式。本章除了重點介紹關聯規則挖掘的Apriori技術外，還將討論一些和Web挖掘、文本挖掘相關的數據挖掘方法。8.1購物籃分析購物籃是顧客在一次事務中所購買項的集合，所謂事務是一個明確定義的商業行為。事務資料庫研究的一個最普通的例子就是尋找項的集合，或叫做項集。包含i個項的項集被稱為i-項集。包含該項集的事務的百分數叫做該項集的支持度。支持度超過指定閾值的項集叫做頻繁項集。基本概念：設I={i1,i2,…im}是項的集合，DB為事務集合，其中每個事務T是項的集合，且有。每一個事務有一個識別字，稱作TID。設X為一個項集，當且僅當時，即T包含X。關聯規則是形如的蘊涵式，其中,

,且。規則在事務集DB中成立，具有支持度s，其中s是DB中事務包含X和Y兩者的百分比。規則在事務集DB中具有置信度c，如果DB中包含X的事務同時也包含Y的百分比是c。支持度是概率。置信度是概率。置信度可以表示規則的可信性，支持度表示模式在規則中出現的頻率。具有高置信度和強支持度的規則被稱為強規則。挖掘關聯規則的問題可以分兩個階段：

1.發掘大項集，也就是事務支持度s大於預先給定的最小閾值的項的集合。

2.使用大項集來產生資料庫中置信度c大於預先給定的最小閾值的關聯規則。Apriori演算法是解決這個問題的常用方法。8.2APRIORI演算法Apriori演算法利用幾次迭代來計算資料庫中的頻繁項集。第i次迭代計算出所有頻繁i項集(包含i個元素的項集)。每一次迭代有兩個步驟：產生候選集；計算和選擇候選集。在第一次迭代中，產生的候選集包含所有1-項集，並計算其支持度s，s大於閾值的1-項集被選為頻繁1-項集。第二次迭代時，Apriori演算法首先去除非頻繁1-項集，在頻繁1-項集的基礎上進行產生頻繁2-項集。原理是：如果一個項集是頻繁，那麼它的所有子集也是頻繁的。例如，以表8-1中的數據為例。假設smin=50%。在第一次迭代的第一步中，所有單項集都作為候選集，產生一個候選集列表。在下一步中，計算每一項的支持度，然後在smin的基礎上選擇頻繁項集。圖8-1中給出第一次迭代的結果。在挖掘2-項集時，因為2-項集的任何子集都是頻繁項集，所以Apriori演算法使用L1*L1來產生候選集。*運算通常定義為：

Lk*Lk={X∪Y其中X,Y∈Lk,|X∩Y|=k+1}

注:|X∩Y|=k+1即X和Y合取容量為k+1當k=1時，因此，C2包含在第二次迭代中作為候選集由運算|L1|·|L1-1|/2所產生的2-項集。本例中為：4·3/2=6。用該列表來掃描DB，計算每一個候選集的s，並與smin比較2-項集L2。圖8-2給出了所有這些步驟和第二次迭代的結果。候選集C3

運用L2*L2來產生，運算結果得到{A,B,C},{A,C,E},{B,C,E}，但只有{B,C,E}的所有子集是頻繁項集，成為候選的3-項集。然後掃描DB，並且挖掘出頻繁3-項集，見圖8-3所示。因為本例的L3無法產生候選的4-項集，所以演算法停止迭代過程。該演算法不僅計算所有頻繁集的s，也計算那些沒有被刪除的非頻繁候選集的s。所有非頻繁但被演算法計算s的候選項集的集合被稱為負邊界。因此，如果項集非頻繁的，但它的子集都是頻繁的，那麼它就在負邊界之中。在本例中，負邊界由項集{D},{A,B},{A,E}組成。負邊界在一些Apriori的改進演算法中更為重要，例如生成大項集或導出負關聯規則時提高了有效性。8.3從頻繁項集得到關聯規則第二階段的工作是在第一階段的基礎上，來挖掘關聯規則。如果規則為{x1,x2,x3}→x4，那麼項集{x1,x2,x3,x4}和{x1,x2,x3}都必須是頻繁的。然後，規則置信度c=P({x4}|{x1,x2,x3})=s(x1,x2,x3,x4)/s(x1,x2,x3)。

置信度c大於給定的閾值的規則就是強規則。例如，檢驗表8-1DB中的關聯規則{B,C}→{E}是否為強關聯規則。由圖8-2和圖8-3可得支持度：

s(B,C)=2,s(B,C,E)=2

由支持度得置信度：c({B,C}→{E})=s(B,C,E)/s(B,C)=2/2=1(100%)

可見，無論閾值為多少，該規則都能通過，也就是說，如果事務包含B和C，那麼它也將包含E。我們現在有目標是在DB頻繁集中得到所有的強關聯規則。請注意:並不是所有的強關聯規則都是有用的或者有意義的。例如，一個穀類早餐的零售商對5000名學生的調查的案例。數據表明：60%的學生打籃球，75%的學生吃這類早餐，40%的學生即打籃球吃這類早餐。假設支持度閾值s=0.4，置信度閾值c=60%。基於上面數據和假設我們可挖掘出強關聯規則“(打籃球)→(吃早餐)”，因為其(打籃球)和(吃早餐)的支持度都大於支持度閾值，都是頻繁項，而規則的置信度c=40%/60%=66.6%也大於置信度閾值。然而，以上的關聯規則很容易產生誤解，因為吃早餐的比例為75%，大於66%。也就是說，打籃球與吃早餐實際上是負關聯的。為了消除這種誤導的規則，應該在關聯規則A→B的置信度超過某個特定的度量標準時，定義它為有意義的。因此挖掘關聯規則的正確方法是：

s(A,B)/s(A)-s(B)>d或者：

s(A,B)-s(A)·s(B)>k式中d或k是適當的常量。（計算上例）8.4提高Apriori演算法的效率因為挖掘頻繁項集時所處理的數據量越來越大，所以很有必要提高演算法的效率。Apriori演算法掃描DB的次數完全依賴於最大的頻繁項集中項的數量。為了解決這個問題，該演算法作了一些改進。基於劃分的Apriori演算法只需要對DB進行兩次掃描。DB被劃分成若干個非重疊的分區，分區與記憶體相匹配。在第一次掃描時，演算法讀取每一個分區，每個分區內計算局部頻繁項集。在第二次掃描時，演算法計算整個DB中所有局部頻繁集的支持度。如果項集對於整個資料庫來說是頻繁的，那麼它至少需要在一個分區中是頻繁的。因此，第二次掃描完成計算所有潛在的頻繁項集的超集。隨著資料庫大小的增加，取樣成為數據挖掘的一個不可多得的有效途徑，基於取樣的演算法需要以資料庫進行兩次掃描。第一次掃描，從DB中選擇一個樣本，並且產生一個在整個DB中很可能為頻繁的候選項集的集合。第二次掃描，演算法計算這些項集的實際支持度和它們的負邊界的支持度。如果在負邊界中沒有項集是頻繁的，那麼說明已挖掘出所有頻繁項集。否則，負邊界中的項集的一些超集可能就是頻繁的，但它的支持度還沒有計算出來。取樣演算法在隨後的掃描時，會產生並計算所有這些潛在有頻繁項集。圖8-4是實際應用的一個例子，該例揭示這樣一個問題，事務資料庫中的購買模式在最低層上不會顯示任何規則，但在一些高的概念層可能會顯示一些有意義的規則。Apriori演算法的一個擴展在DB項上涉及到is-a層次，它包含資料庫結構中已經存在的多抽象層的資訊。is-a層次定義哪些項是其他項的一般化或專門化。除了明確列出的項以外，事務還以分類的方式包含了它們的祖先，這樣就可以發掘出高層次的關係。8.5頻繁模式增長方法(FP-增長方法）一個Apriori演算法的可伸縮的問題。如果生成一個長度100的頻繁模式，例如{a1,a2,…,a100}，那麼所產生的候選集的數量至少為：計算的複雜性成指數增長，這是影響一些新關聯規則挖掘演算法發展的一個主要因素。頻繁模式增長(FP-growth)方法是在大型數據中挖掘頻繁項集的一個有效演算法。演算法進行中不存在產生候選集的繁瑣過程，當DB很大時，FP-增長演算法首先進行資料庫投影，得到頻繁集，然後通過構造一個壓縮的資料庫結構---FP-樹再進行挖掘。例如，表8-3給出DB，它的最小支持度閾值為3。第一步，掃描T，得到頻繁集的列表L:L={(f,4),(c,4),(a,3),(b,3),(m,3),(p,3)}

按支持度大小遞減排列。第二步，創建樹的根部(ROOT)，第二次掃描T。對第一個事務的掃描得樹的第一個分枝:{(f,1),(c,1),(a,1),(b,1),(m,1),(p,1)}。分枝中節點的計數(都是1)代表了樹中該節點項所出現的次數，並按Ｌ中順序排列。對第二個事務，與第一事務有相同項f,c,a，所有有同一個首碼(f,c,a)，得到一個新的分枝{(f,2),(c,2),(a,2),(b,1),(m,1)}，見圖8-5a。其他事務按同樣的方式插入到FP-樹中，圖8-5b給出了最後的FP-樹。按照頻繁項的表L，整個頻繁項的集合被劃分為幾個沒有重疊的子集:1)含有p的頻繁項集；2)含有m但不含有p的頻繁項集；3)含有b但不含有m,p的頻繁項集；…；6)只含有f的大項集。1)有兩個路徑{(f,4),(c,3),(a,3),(m,2),(p,2)}和{(c,1),(b,1),(p,1)},根據閾值產生新的頻繁項集(c,p)2)有兩個路徑{(f,4),(c,3),(a,3),(m,2)}和{(f,4),(c,3),(a,3),(b,1),(m,1)},滿足閾值的頻繁項集是{f,c,a,m}。例如，事務DB如表8-3所示。首先找出頻繁多維值的組合，然後尋找DB中相應的頻繁項集。設支持度閾值為2，即屬性值的組合出現兩次或兩次以上為頻繁項集，稱為多維模式或叫做MD-模式。要挖掘MD-模式時，可以使用最早由beyer和Ｒamakrishnan(它是個有效的“冰山立方體”，見下圖)開發的改進BUC演算法。BUC演算法的基本步驟如下:首先，在第一維(A1)中按值的字母順序將每個項進行排序。1.在該維中僅有的MD-模式為(a,*,*)，因為只有a值的支持度大於2。其他維的值(*)在第一步不相關，可取任意值。在DB中選擇那些具有MD-模式的項。即T01和T03事務。針對第二維(A2),值1和2,對簡化的DB進行再一次排序。沒有符合支持度的模式，所以不存在A1和A2值的MD-模式。因此可忽略A2。在第三維(A3)中按字母順序進行排序。子集(a,*,m)出現兩次，因此它是一個MD-模式。2.重複步驟1的過程：只從A2開始，不需要搜索第一維。第二次迭代從A2開始，MD-模式為(*,2,*),針對A3，不存在其他MD-模式。最後一次迭代，從A3開始，(*,*,m)為MD-模式.圖8-6是BUC演算法對表8-3的處理結果。找到MD-模式後，下一步對每個MD-模式在MD-投影中挖掘頻繁項集。8.7WEB挖掘在分佈式的資訊環境中,文檔或對象通常被鏈接在一起,從而可以起到互相訪問的作用。例如，WWW和線上服務，這類資訊提供的環境，通過工具(如超鏈接、URL地址)從一個對象轉到另一個對象，從而獲得有用的資訊。WEB是一個超8億頁的超文本的載體，而且資訊量還在不斷增長。幾乎每天要增加100萬個頁面，而且頁面每幾個月就會更新一次，因此，每月會有幾百G位元組的數據在變化。Web挖掘可以定義為使用資料庫挖掘技術在Web文檔和服務中自動在發掘並且提取資訊。它涉及到整個挖掘的過程，而不僅僅是應用標準的數據挖掘工具。Web挖掘任務劃分為４個子任務：

1.尋找資源─這是一個從Web上的多媒體資源中線上或離線檢索數據的過程。電子時事通信、電子新聞專線、新聞組以及通過刪除HTML標記得到的HTML文檔。

2.資訊選擇和預處理─這是在上面的子任務中檢索出的不同種類的原始數據的轉換過程。轉換過程既可以是一種預處理，比例刪除停止字，障礙字等，或者旨在獲得所需要的表示法，例如查找在訓練主體中的習語，以第一順序邏輯的形式表示文本等。

3.總結─總結是一個在個別Web站點上自動地發掘出綜合模式的過程。本階段使用了不同的綜合目的機器學習、數據挖掘技術和指定的面向Web的方法。

4.分析─在這一過程中，執行生效和／或解釋已挖掘出模式。Web挖掘可以基於所挖掘的部分進行分類，分為3類:1.Web內容挖掘─描述從Web文檔發掘出有用的資訊。內容包括：文本、圖像、音頻、視頻、元數據以及超鏈接。2.Web結構挖掘─挖掘Web上的鏈接結構中的潛在模型。3.Web使用挖掘─挖掘在網上衝浪的過程或行為所產生的數據。當1類和2類利用Web上的真實或主要數據時，3類就會從用戶在同Web進行交互時的行為入手，挖掘第二級數據。這些數據包括訪問Web伺服器日誌、代理伺服器日誌、流覽器日誌、用戶數據、註冊數據、用戶會話或交易、Cookies、書簽數據以及任何個人同Web進行交互所產生的其他數據。在下兩小節中，介紹Web挖掘的３個主要技術。8.8HITS和LOGSOM演算法到目前為止，基於索引的Web搜索引擎是用戶搜索資訊的主要工具。問題是搜索引擎不適合那些大範圍的不精確的搜索任務。我們的目標是能搜索出最主要的網頁，即相關的且是高質量的網頁。因此Web挖掘中必須發掘出兩種重要類型的網頁：權威頁(提供了指定主題的最佳資訊來源)和Hub頁(提供同權威頁鏈接的集合)。Hub頁的一個顯著特徵就是：它們是某個焦點主題的權威頁的有力提供者。可以定義一個好的hub頁，如果它是指向一些好的權威頁。與些同時，一個好的權威頁，是被一些好的hub頁所指向的。兩者之間的這種相互加強關係，正是HITS演算法(Hyperlink-InducedTopicsearch)的中心思想，它正是一種搜索好的hub頁和權威頁的演算法。HITS演算法的兩個主要步驟：1.取樣組分(samplingcomponent)，構建在相關資訊中可能經常出現的網頁的集合。在取樣階段，將Web視為一個網頁的有向圖。HITS演算法首先構造子圖，在子圖中可以搜索hub頁和權威頁。目標是構造出蘊含高相關性、權威性的網頁的子圖。在構造子圖之前，先使用查詢方法從基本索引的搜索引擎中收集網頁的根集(rootset)。演算法希望根集含有部分權威頁，或根集同大多數權威網頁相鏈接。2.權重傳播(weight-propagation)，通過反復的過程來估計hub頁和權威頁，並且獲得最具相關性和權威性的網頁的子頁。在權威傳播階段，通過為所有優秀的hub頁和權威頁制定一個混合的數字運算式，從基本集合V中抽取它們。設非負的權威頁權重為ap，非負的hub頁為hp，且每一個網頁中p∈V。演算法只對權重的相對值感興趣，因此對權重進行標準化，使權重的總和在一定界限內。權重a和h的初始化均為一常量，但最終的權重不受他們的影響。演算法按以下方式更新權威頁和hub頁。如果一個網頁有一些好的hub頁來指向，那麼就增加它的權威頁的權重，因此，將網頁p的ap值設為所有指向p的網頁q的hq值之和：

相反，如果網頁指向一些好的權威頁，那麼就增加它的hub頁的權重：

有一種較簡單的更新方法。首先對網頁進行編號{1,2,…,n}，然後定義矩陣A為n×n階矩陣，第(i,j)個元素的值如果為1，則表示網頁i和網頁j相連，為0，相反。剛計算時，所有頁都是hub頁權威頁，而且用下麵向量表示：

a={a1,a2,…,an}和h={h1,h2,…,hn}

對權威頁和hub頁的更新規則為:a=ATh;h=Aa

或者：

a=ATh=(ATA)a;h=Aa=(AAT)h上面關係是向量a和h的重複計算，依線性代數的理論，最終結果標準化之後，收斂於特徵向量ATA。可見，計算的hub和權威頁實際上是所收集的鏈接網頁的本質特徵，而不是初始權重中派生出來。演算法輸出一個同指定的搜索主題相關的，由具有最大權重的網頁和具有最大權威權重的網頁所組成的列表。例如，以圖8-7為例，演示演算法的基本步驟。假設在查詢時，搜索引擎出6個相關的文檔，希望從中選出最重要的權威頁和hub頁。所選擇有文檔在一個有向子圖中相連接，見圖8-7a所示(少了3指向5)，圖8-7b為矩陣A和初始權重向量a和h。HITS演算法首先更改向量a和h：在演算法的第一步可得：文檔5最具權威性，文檔1是最好的hub。在隨後的步驟中會糾正兩個向量的權重因數，但本例的得出的權威頁和hub頁的順序保持不變。由於Internet的不斷增長，在使用單個詞進行搜索時會檢索出成千上萬的文檔，因此挖掘變得相當複雜和低效率，並且還有一些是不相干的網頁，一些可能被刪除，另一些則可能禁止訪問。HITS演算法適用於靜態網頁的挖掘，而LOGSOM演算法可用於動態網頁。LOGSOM演算法將資訊的佈局完全組織成為一個用戶可以理解的圖表。LOGSOM系統使用自組圖譜(SOM)按照用戶的導航模式將網頁組織成一個二維表。SOM技術是Web頁的組織問題是最常用的技術，它不僅可以將數據組織在一個類中，而且可以以圖表的形式來表示類之間的關係。系統首先創建一個Web日誌，用它來表示日期、時間的所請求Web頁的地址，以及用戶電腦的IP。假設存在一個有限的惟一URL的集合：

U={url1,url2,…,urln}

和一個有限的m個用戶事務集合：

T={t1,t2,…,tm}

事務用向量來表示：

t={u1,u2,…,un}其中：預處理日誌檔可以用二進位矩陣的形式來表示。表8-4為一例子。現實中，(n×m)維的事務表可能很大，需要縮小數據量。通過使用K-meams聚類演算法，可以將事務分組到預定的第k(k<<m)個事務組中。表8-5為一減小的數據集的示例，其中行中的元素表示事務組訪問特定的URL的總次數(表的形式和值只是一個示例，與表8-4中的值不直接相關)。縮小後的新表作為SOM處理的輸入。SOM的聚類技術在相關的人工神經網路文獻仲介紹，此處只對應用SOM演算法得出的結果給予解釋。表8-6是SOM處理的典型結果。該表並不是表8-4和表8-5的處理結果，只是一個示例。每一個URL會基於它同其他URL的相似性，根據用戶的使用或是用戶的導航模式(表8-5中的事務組“權重”)，都會被映射到一個SOM上。表中的空白節點表示不存在相應的URL，其中有標號的節點表示每個節點(或每個類)中包含的URL的數量。LOGSOM演算法用於識別公司潛在的客戶訪問了公司的哪些網頁，從而為公司提供改善決策的資訊如果一個節點中的網頁能將客戶成功在導航他所想要的資訊或頁面中，在同一節點的其他頁面也可能獲得成功。這樣互聯網廣告的投放由用戶導航模式的直接支持。8.9挖掘路徑遍曆模式改進公司的WEB站點之前，先估計它的當前用量。每個站點都由Web伺服器電子化在管理，所有活動都會記入日誌，存放在日誌檔中。用戶的所有痕跡都存在這個檔中。因此，可應用數據挖掘技術，從該檔中提取一些可以間接在反應站點品質的資訊，也可以挖掘數據來優化Web伺服器的性能，找出哪些產品被合在一起購買，或者確定站點是否按照預期的情況使用。例如，事務DB如表8-3所示。首先找出頻繁多維值的組合，然後尋找DB中相應的頻繁項集。設支持度閾值為2，即屬性值的組合出現兩次或兩次以上為頻繁項集，稱為多維模式或叫做MD-模式。要挖掘MD-模式時，可以使用最早由beyer和Ｒamakrishnan(它是個有效的“冰山立方體”，見下圖)開發的改進BUC演算法。BUC演算法的基本步驟如下:首先，在第一維(A1)中按值的字母順序將每個項進行排序。1.在該維中僅有的MD-模式為(a,*,*)，因為只有a值的支持度大於2。其他維的值(*)在第一步不相關，可取任意值。在DB中選擇那些具有MD-模式的項。即T01和T03事務。針對第二維(A2),值1和2,對簡化的DB進行再一次排序。沒有符合支持度的模式，所以不存在A1和A2值的MD-模式。因此可忽略A2。在第三維(A3)中按字母順序進行排序。子集(a,*,m)出現兩次，因此它是一個MD-模式。2.重複步驟1的過程：只從A2開始，不需要搜索第一維。第二次迭代從A2開始，MD-模式為(*,2,*),針對A3，不存在其他MD-模式。最後一次迭代，從A3開始，(*,*,m)為MD-模式.圖8-6是BUC演算法對表8-3的處理結果。找到MD-模式後，下一步對每個MD-模式在MD-投影中挖掘頻繁項集。8.7WEB挖掘在分佈式的資訊環境中,文檔或對象通常被鏈接在一起,從而可以起到互相訪問的作用。例如，WWW和線上服務，這類資訊提供的環境，通過工具(如超鏈接、URL地址)從一個對象轉到另一個對象，從而獲得有用的資訊。WEB是一個超8億頁的超文本的載體，而且資訊量還在不斷增長。幾乎每天要增加100萬個頁面，而且頁面每幾個月就會更新一次，因此，每月會有幾百G位元組的數據在變化。Web挖掘可以定義為使用資料庫挖掘技術在Web文檔和服務中自動在發掘並且提取資訊。它涉及到整個挖掘的過程，而不僅僅是應用標準的數據挖掘工具。Web挖掘任務劃分為４個子任務：

1.尋找資源─這是一個從Web上的多媒體資源中線上或離線檢索數據的過程。電子時事通信、電子新聞專線、新聞組以及通過刪除HTML標記得到的HTML文檔。

2.資訊選擇和預處理─這是在上面的子任務中檢索出的不同種類的原始數據的轉換過程。轉換過程既可以是一種預處理，比例刪除停止字，障礙字等，或者旨在獲得所需要的表示法，例如查找在訓練主體中的習語，以第一順序邏輯的形式表示文本等。

3.總結─總結是一個在個別Web站點上自動地發掘出綜合模式的過程。本階段使用了不同的綜合目的機器學習、數據挖掘技術和指定的面向Web的方法。

4.分析─在這一過程中，執行生效和／或解釋已挖掘出模式。Web挖掘可以基於所挖掘的部分進行分類，分為3類:1.Web內容挖掘─描述從Web文檔發掘出有用的資訊。內容包括：文本、圖像、音頻、視頻、元數據以及超鏈接。2.Web結構挖掘─挖掘Web上的鏈接結構中的潛在模型。3.Web使用挖掘─挖掘在網上衝浪的過程或行為所產生的數據。當1類和2類利用Web上的真實或主要數據時，3類就會從用戶在同Web進行交互時的行為入手，挖掘第二級數據。這些數據包括訪問Web伺服器日誌、代理伺服器日誌、流覽器日誌、用戶數據、註冊數據、用戶會話或交易、Cookies、書簽數據以及任何個人同Web進行交互所產生的其他數據。在下兩小節中，介紹Web挖掘的３個主要技術。8.8HITS和LOGSOM演算法到目前為止，基於索引的Web搜索引擎是用戶搜索資訊的主要工具。問題是搜索引擎不適合那些大範圍的不精確的搜索任務。我們的目標是能搜索出最主要的網頁，即相關的且是高質量的網頁。因此Web挖掘中必須發掘出兩種重要類型的網頁：權威頁(提供了指定主題的最佳資訊來源)和Hub頁(提供同權威頁鏈接的集合)。Hub頁的一個顯著特徵就是：它們是某個焦點主題的權威頁的有力提供者。可以定義一個好的hub頁，如果它是指向一些好的權威頁。與些同時，一個好的權威頁，是被一些好的hub頁所指向的。兩者之間的這種相互加強關係，正是HITS演算法(Hyperlink-InducedTopicsearch)的中心思想，它正是一種搜索好的hub頁和權威頁的演算法。HITS演算法的兩個主要步驟：1.取樣組分(samplingcomponent)，構建在相關資訊中可能經常出現的網頁的集合。在取樣階段，將Web視為一個網頁的有向圖。HITS演算法首先構造子圖，在子圖中可以搜索hub頁和權威頁。目標是構造出蘊含高相關性、權威性的網頁的子圖。在構造子圖之前，先使用查詢方法從基本索引的搜索引擎中收集網頁的根集(rootset)。演算法希望根集含有部分權威頁，或根集同大多數權威網頁相鏈接。2.權重傳播(weight-propagation)，通過反復的過程來估計hub頁和權威頁，並且獲得最具相關性和權威性的網頁的子頁。在權威傳播階段，通過為所有優秀的hub頁和權威頁制定一個混合的數字運算式，從基本集合V中抽取它們。設非負的權威頁權重為ap，非負的hub頁為hp，且每一個網頁中p∈V。演算法只對權重的相對值感興趣，因此對權重進行標準化，使權重的總和在一定界限內。權重a和h的初始化均為一常量，但最終的權重不受他們的影響。演算法按以下方式更新權威頁和hub頁。如果一個網頁有一些好的hub頁來指向，那麼就增加它的權威頁的權重，因此，將網頁p的ap值設為所有指向p的網頁q的hq值之和：

相反，如果網頁指向一些好的權威頁，那麼就增加它的hub頁的權重：

有一種較簡單的更新方法。首先對網頁進行編號{1,2,…,n}，然後定義矩陣A為n×n階矩陣，第(i,j)個元素的值如果為1，則表示網頁i和網頁j相連，為0，相反。剛計算時，所有頁都是hub頁權威頁，而且用下麵向量表示：

a={a1,a2,…,an}和h={h1,h2,…,hn}

對權威頁和hub頁的更新規則為:a=ATh;h=Aa

或者：

a=ATh=(ATA)a;h=Aa=(AAT)h上面關係是向量a和h的重複計算，依線性代數的理論，最終結果標準化之後，收斂於特徵向量ATA。可見，計算的hub和權威頁實際上是所收集的鏈接網頁的本質特徵，而不是初始權重中派生出來。演算法輸出一個同指定的搜索主題相關的，由具有最大權重的網頁和具有最大權威權重的網頁所組成的列表。例如，以圖8-7為例，演示演算法的基本步驟。假設在查詢時，搜索引擎出6個相關的文檔，希望從中選出最重要的權威頁和hub頁。所選擇有文檔在一個有向子圖中相連接，見圖8-7a所示(少了3指向5)，圖8-7b為矩陣A和初始權重向量a和h。HITS演算法首先更改向量a和h：在演算法的第一步可得：文檔5最具權威性，文檔1是最好的hub。在隨後的步驟中會糾正兩個向量的權重因數，但本例的得出的權威頁和hub頁的順序保持不變。由於Internet的不斷增長，在使用單個詞進行搜索時會檢索出成千上萬的文檔，因此挖掘變得相當複雜和低效率，並且還有一些是不相干的網頁，一些可能被刪除，另一些則可能禁止訪問。HITS演算法適用於靜態網頁的挖掘，而LOGSOM演算法可用於動態網頁。LOGSOM演算法將資訊的佈局完全組織成為一個用戶可以理解的圖表。LOGSOM系統使用自組圖譜(SOM)按照用戶的導航模式將網頁組織成一個二維表。SOM技術是Web頁的組織問題是最常用的技術，它不僅可以將數據組織在一個類中，而且可以以圖表的形式來表示類之間的關係。系統首先創建一個Web日誌，用它來表示日期、時間的所請求Web頁的地址，以及用戶電腦的IP。假設存在一個有限的惟一URL的集合：

U={url1,url2,…,urln}

和一個有限的m個用戶事務集合：

T={t1,t2,…,tm}

事務用向量來表示：

t={u1,u2,…,un}其中：預處理日誌檔可以用二進位矩陣的形式來表示。表8-4為一例子。現實中，(n×m)維的事務表可能很大，需要縮小數據量。通過使用K-meams聚類演算法，可以將事務分組到預定的第k(k<<m)個事務組中。表8-5為一減小的數據集的示例，其中行中的元素表示事務組訪問特定的URL的總次數(表的形式和值只是一個示例，與表8-4中的值不直接相關)。縮小後的新表作為SOM處理的輸入。SOM的聚類技術在相關的人工神經網路文獻仲介紹，此處只對應用SOM演算法得出的結果給予解釋。表8-6是SOM處理的典型結果。該表並不是表8-4和表8-5的處理結果，只是一個示例。每一個URL會基於它同其他URL的相似性，根據用戶的使用或是用戶的導航模式(表8-5中的事務組“權重”)，都會被映射到一個SOM上。表中的空白節點表示不存在相應的URL，其中有標號的節點表示每個節點(或每個類)中包含的URL的數量。LOGSOM演算法用於識別公司潛在的客戶訪問了公司的哪些網頁，從而為公司提供改善決策的資訊如果一個節點中的網頁能將客戶成功在導航他所想要的資訊或頁面中，在同一節點的其他頁面也可能獲得成功。這樣互聯網廣告的投放由用戶導航模式的直接支持。8.9挖掘路徑遍曆模式改進公司的WEB站點之前，先估計它的當前用量。每個站點都由Web伺服器電子化在管理，所有活動都會記入日誌，存放在日誌檔中。用戶的所有痕跡都存在這個檔中。因此，可應用數據挖掘技術，從該檔中提取一些可以間接在反應站點品質的資訊，也可以挖掘數據來優化Web伺服器的性能，找出哪些產品被合在一起購買，或者確定站點是否按照預期的情況使用。LOGSOM方法重點在於Web頁面的相似性，而其他技術則強調用戶經過Web的路徑的相似性。捕捉Web環境中的用戶訪問模式被稱為挖掘路徑遍曆模式，它屬於另一種數據挖掘技術。這種技術還處於萌芽階段，但卻在互聯網應用中顯示出了極光明的前景。由於用戶沿著資訊路徑在網上搜尋想要的資訊，一些對象或文檔只是因為它們的位置而被訪問，而不是因為它們的內容。這個特徵不可避免在增加從遍歷數據中獲取有用資訊的難度，同時也解釋了為什麼當前的網路用量主要是為旅行點而不是為旅行路徑提供統計數據。8.10文本挖掘存在於多數文本資料庫中的資訊都是半結構化數據，文本挖掘用於從大型文本形式的資料庫集中發現新的資訊。文本挖掘的兩種技術：一種是互聯網搜索能力，另一種是文本分析方法。搜索引擎是互聯網用於幫助用戶找到他們想要的內容，使用戶只要處理更少的鏈接、頁面和索引，就可以獲得得相關的資訊。在資訊檢索(IR)領域，文檔典型地表述為向量空間的模型，並用簡單的語法規則(如英語中的空白分隔)來加以標記，標號被轉化成標準形式，每個標準標號代表歐氏空間裏的一根軸。文檔就是n維空間裏的向量。如果一個也可叫做詞的標號t在文檔d中出現n次，那麼很簡單，文檔d第t個座標就是n。可以選擇L1,L2,…,L∞範數將文檔的長度標準化為1。

其中n(d,t)是文檔d中詞t出現的次數。存在這樣一個事實：一些叫關鍵字的詞(像“algorithm”)在確定文檔的內容方面比其他的一些詞(像“the”，“is”)更重要。如果在N個文檔中，有nt個文檔中出現詞t，nt/N表示稀有性，表示詞t的重要性。逆文檔頻數IDF=1+log(nt/N)用於延長向量空間中的軸，這種延長是有差別的。因此，可以用加權向量空間(n(d,t)/|d1|×IDF(t)的值來表示文檔d的第t個座標的值。超文本文檔通常表示為Web的基本成分，它是基於文本文檔的一種特珠的類型，其內容除了文本外，還有超鏈接。有一種最簡單的模型，超文本可以被當作是有向圖表(D,L)，其中D是表述文檔或Web頁面的節點集，L是鏈接集。文本挖掘是一個建立在文本分析技術基礎上的新興的功能集合。文本挖掘必須提供一些超越文本索引檢索的值，如關鍵字。文本挖掘是一個涉及到資訊檢索、文本分析、資訊提取、聚類、分類、可視化、機器學習和已經包括在數據挖掘“菜單”中的其他技術的多學科領域。文本挖掘處理分為兩個階段：

1.文本提煉，將自由形式的文本文檔轉換成所選的仲介形式。

2.知識萃取，從中介形式中演繹出模式或知識。2.1

原始數據的表述常見的數據類型：數據挖掘過程的基本對象是數據樣本，每個樣本都用幾個特徵來描述，每個特徵有不同的類型的值。常見類型：數值型和分類型。數值型的值包括實型變數和整型變數。數值型：其特徵是其值有順序關係和距離關係。分類型：其特徵是變數間是否相等，且可用二進位數來表述。基於變數值的變數分類法：連續型變數和離散型變數．連續型變數也稱為定量型或度量型變數。可用間隔尺度或比例尺度來衡量。溫度尺度屬間隔尺度，沒有絕對零點。高度、長度和工資屬比例尺度，有絕對零點，離散型變數也稱為定性型變數。可用名義尺度或有序尺度來衡量。顧客類型標誌和郵編屬名義尺度，排名屬有序尺度。週期變數是一種特殊的離散變數，存在距離關係不存在順序關係。星期、月屬週期變數。基於數據的與時間有關的行為特性的類型：靜態數據和動態數據。在數據挖掘初始階段面對的數據也許有潛在的雜亂性，存在著丟失值、失真、誤記錄和不適當的樣本。因此在必須根據已有的數據甚至是丟失值的數據進行建模。這樣就可能避免在挖掘前處理丟失值問題。2.2原始數據的特性另一個問題是必須有處理“非常值”的機制，來消除“非常值”對最終結果的影響，數據可能並不是來自我們假定的總體。異常點是典型的例子。失真的數據、方法上錯誤的步驟、濫用挖掘工具、模型太理想化、超出各種不確定性和模糊性的數據來源的模型可能導致挖掘方向的錯誤。因此挖掘不只是簡單在應用一系列工具於已知問題，而是一種批判性的鑒定、考查、檢查以及評估過程。挖掘過程中一個最關鍵的步驟是對初始數據集的預備和轉換，數據預備有兩個中心任務：1.把數據組織成一種標準形式，使其能被挖掘工具和其他基於電腦的工具處理（一個關係表）2.準備數據集使之能得到最佳的挖掘效果1.標準化挖掘中基於n維空間距離計算的方法需要對數據進行標準化處理來達到最佳效果,將數據按比例對應到特定的範圍，否則距離測量將會超出平均起來數值更大的那些特徵。標準化常用技術：2.3