1、9.3 文本檢索,三、隱含語義索引 上面所介紹的都是將文檔表示為T維詞條權(quán)向量的。但用戶可能提出的查詢中的詞條不在用在索引文檔的詞條中。 例如，從詞條相似性的角度來看，詞條“數(shù)據(jù)挖掘”和“知識發(fā)現(xiàn)”設有什么直接的共同點。然而，從語義角度來看，這兩個詞條有很大的相同點。,因此，在提出一個包含其中之一的查詢，那么應該考慮包含另一個的文檔。解決方法是：預先創(chuàng)建一個把語義相關(guān)詞條連接在一起的知識庫(同義詞典或本體集)。然而，這樣的知識庫存在固有的主觀性，因它取決于從何種角度來把詞條和語義內(nèi)容聯(lián)系起來。 隱含語義索引(latent semantic indexing)(LSI)一種可選的有趣又有價值的方

2、法。該方法不是僅使用詞條出現(xiàn)信息，而是從文本中提取出隱藏的語義結(jié)構(gòu)信息。,實際上，LSI采用T維詞條空間中前k個主成分來近似原始的T維詞條空間，使用NT的文檔-詞條來估計這個方向。 主成分方法的直觀解釋是，由原始詞條的加權(quán)組合所構(gòu)成的單個向量可以非常好的近似由大得多的向量集合所起的效果。于是可以把原來的NT大小的文檔-詞條矩陣簡化為Nk的矩陣(kT)， 對于固定的查全率，和前面討論的向量空間方法相比，LSI可以提高查準率。,對表9-2中的矩陣M計算奇異分解式(SVD)。,目標是，找一個分解式M=USVT。式中U是一個106的矩陣，它的每一行是相對特定文檔的權(quán)向量，S是每個主成分方向特征值的66

3、對角陣， 66的矩陣VT的各列提供了數(shù)據(jù)的新共軛基，被稱為主成分方向。 S矩陣的對角線元素是(協(xié)方差矩陣對應): 1, n=77.4,69.5,22.9,13.5,12.1,4.8 可見，前兩個主成分捕捉了數(shù)據(jù)中的主要變化，和直覺一致。 當使用兩個主成分時，那么二維表征所保留的變化比例0.925，信息丟失僅7.5%。,如果我們在新的二維主成分空間來表示文檔，那么每篇文檔的系數(shù)對應于U矩陣的前兩列(兩個主成分對應的特征向量，即新的文檔權(quán)值)：,這兩列可看作新的偽詞條，其作用相當于原來6個詞條的線性組合。 看一下前兩個主成分方向可以得到的信息(新共軛基)： V1=(0.74,0.49,0.27,0

4、.28,0.18,0.19) V2=(-0.28,-0.24,-0.12,0.74,0.37,0.31) 這兩個方向是原來6維詞條空間中數(shù)據(jù)最分散(具有最大方差)的方向。每方向更突出前兩個詞條(查詢,SQL)：實際上這是描述和數(shù)據(jù)庫有關(guān)文檔的方向。,第二方向突出了后三個詞條回歸、似然和線性，這是描述和回歸有關(guān)文檔的方向。圖9-4以圖形方式說明了這一點(將上面數(shù)據(jù)用圖表示)。,當把文檔投影到由前兩個主成分方向所決定的平面量，兩個不同組的文檔分布在兩個不同的方向上。注意文檔2幾乎落在文檔1上，使其有點模糊。文檔5和文檔10的詞條向量最大，因此離原最遠。 從圖可看出，文檔間的角度差異顯然是相似性的一

5、個有用指標，因為回歸和數(shù)據(jù)庫文檔在平面上是圍繞兩個不同的角度聚成簇的。 主成分方法的應用例子： 考慮一個新的文檔D1，詞條“查詢”在該文檔,中出現(xiàn)50次，另一個文檔D2，包含詞條“SQL”50次，兩且兩篇文檔都不包含其他的詞條。如果直接使用關(guān)鍵字表示，這兩個文檔不會被認為是相似的，因為它們沒有包含相同的詞條。 然而，如果使用兩個主成分詞條來表示這兩篇文檔，并把它們投影到這個空間中，那么正如圖9-3所示，二者都被投影到“數(shù)據(jù)庫”方向，盡管它們都 僅包含和數(shù)據(jù)庫有關(guān)的三個詞條中的一個。,從計算的角度來看，直接計算主成分向量(例如求解相關(guān)矩陣或協(xié)方差矩陣的特征值)通常要么是計算上不可行，要么是數(shù)值上

6、不穩(wěn)定。實踐中，可以使用特別適合高維稀疏矩陣的SVD技術(shù)來估計PCA向量。,四、文檔和文本分類 上面的討論可以看出使用詞條向量來表示文檔為文檔分類提供了一種自然框架。 有了這一框架對于預先有標簽的文檔我們可以使用有指導分類技術(shù)，對于沒有標簽的文檔我們可以使用無指導學習(聚類)框架。 典型詞條向量的維數(shù)都是非常高的，基于這一事實，高維空間中的準確性和高效性通常是選擇分類器的首要標準。,對于文檔表示來說，像一階貝葉斯分類器這樣的分類模型或者是加權(quán)線性組合可工作得很好。 在文檔分類這一領(lǐng)域還有很多有趣的問題可以探討，例如認為每篇文檔屬于多個主題(類)而不是僅屬于某個類是有意義的。因此在分類時不再限于

7、各個類是相互排斥的這一通用框架。一種簡單的方法是為每個類分別訓練一個二值分類器，此方法僅當類別總數(shù)較少時是可行的。,9.4 對個人偏好建模,一、相關(guān)性反饋 文本檢索系統(tǒng)比其他數(shù)據(jù)挖掘算法更具有交互性。特別是，提出特定查詢Q的用戶可能愿意反復使用算法進行一系列不同的檢索嘗試，并通過為返回的文檔標記出相關(guān)與否來給算法提供用戶反饋。 在這方面，Rocchio算法應用的特別廣泛。算法的基本思想：,從根本上講相關(guān)性是以用戶為中心的，也就是，如果用戶可以(理論上)看到所有的文檔，那么原則上他可以把所有文檔分成兩個集合，相關(guān)的R和不相關(guān)的NR。如果給定了這兩個集合，那么可以證明最佳查詢(利用向量模型)為：

8、其中D代表文檔的詞條向量表示，它的標簽(用戶作出的)是已知的。,在實際應用中，一般一個用戶不會把數(shù)據(jù)庫中所有文檔都標上分類標簽。相反，用戶是從一個特定查詢Qcurrent開始的，可以把這個查詢看作是相對Qoptimal次優(yōu)的。算法使用這個初始查詢返回文檔的一個較小子集，然后用戶把該子集的文檔標記為相關(guān)R和不相關(guān)NR。Rocchio算法按下面的方式來提煉查詢：,該算法使查詢朝著相關(guān)文檔的均值向量靠近，并遠離不相關(guān)文檔的均值向量。參數(shù)、和是正的常數(shù)(啟發(fā)式選取)，它們控制著新查詢對最近標記文檔的敏感性(相對于當前查詢向量Qcurrent)。 不斷重復這個過程，把新的查詢Qnew與文檔集合進行匹配，

9、然后讓用戶再一次標記文檔。 原則上講，如果每一次迭代所作的標簽是一致的，那么Qnew會逐步逼近Qoptimal。,實驗證據(jù)表明，利用用戶反饋確實提高了查準率-查全率性能。然而，在實際應用時還有一些細節(jié)問題需要確定，比如顯示給讀者的文檔數(shù)量；使用的相關(guān)文檔和非相關(guān)文檔的相對數(shù)量；選取非相關(guān)文檔的方法等等。 二、自動推薦系統(tǒng),9.5 圖像檢索,隨著圖像和視頻數(shù)據(jù)集合在的不斷增加，人們對圖像檢索的興趣也日益濃厚。 手工對圖像進行注釋具有浪費時間、主觀性強等缺點，而且可能因為注釋者的看法不同而丟失圖像的某些特征。 一幅圖像可能要使用一千個詞來描述,但是到底使用哪一千個單詞卻不是簡單的問題.,因此，開發(fā)

10、高效而又準確的算法來根據(jù)內(nèi)容對圖像數(shù)據(jù)庫進行查詢是很有必要的。比如，檢索系統(tǒng)允許用戶提交這樣的查詢“找出和這幅圖像最相近的K幅圖像”或者“找出和這組圖像屬性最匹配的K幅圖像”。 一、圖像理解 圖像數(shù)據(jù)查詢是非常困難的任務。從某種意義上來說尋找彼此相似的圖像等價于求解圖像理解問題，也就是從圖像數(shù)據(jù)中抽取語義信息。,在這方面人類非常出色，然而，關(guān)于模式識別和計算機視覺的幾十年研究已經(jīng)表明，要用計算機算法來“復制”人類在視覺理解和識別方面的能力是極端困難的。 舉例來說，嬰兒可以很快學會要任何背景下辨別各種動物，比如各種大小、顏色、體型的狗，而這種完全無約束的識別問題超出了目前任何視覺算法的能力。因此

11、，目前的大多數(shù)圖像檢索算法還僅依賴于相當?shù)图壍目梢曁崾尽?二、圖像表示 為了便于檢索，可以把原始的像素數(shù)據(jù)抽象為特征表示，通常是以類似色彩和紋理這樣的原語來表示圖像特征。 類似于文本表達方式，仍然采用數(shù)據(jù)矩陣格式來表示圖像，每一行代表一幅特定的圖像；每一列代表一個圖像特征。這樣的特征表示通常比直接的象素測量值對縮放和平移變化更有效。,原始的像素數(shù)據(jù)被簡化為標準的Np數(shù)據(jù)矩陣，在這個矩陣中每一幅圖像被表示為特征空間中的一個p維向量。 通過計算圖像局部化子區(qū)域的特征可以粗略的引入空間信息。例如，我們可以計算一幅10241024像素圖像的每個3232子區(qū)域的顏色信息。這樣便可以在圖像查詢中使用粗略的

12、空間約束，比如“尋找中央主要為紅色，四周為藍色的圖像”。,應用于圖像的根據(jù)內(nèi)容檢索系統(tǒng)的一個著名商業(yè)實例是IBM開發(fā)的根據(jù)圖像內(nèi)容查詢(QBIC)系統(tǒng)。該系統(tǒng)允許用戶交互式的查詢圖像和視頻數(shù)據(jù)，查詢的依據(jù)可以是圖像實例、用戶輸入的草圖、顏色和紋理模式、對象屬性等等。允許對景物、對象以及視頻幀序列或者是這些的任意組合進行查詢。,QBIC系統(tǒng)使用了多種特征以及多種和距離有關(guān)的尺度用于檢索： 相對整幅圖像進行空間平均的三維顏色特征向量，采用歐氏距離尺度。 K-維顏色直方圖，直方圖的柱位可以使用像使用K-平均這樣的基于劃分聚類算法來選取。采用馬氏(Mahalanobis)距離尺度來表征顏色相關(guān)性。 衡

13、量粒度/比例、方向性和對比度特征的三維紋理向量。采用加權(quán)的歐氏距離尺度來計算距離，權(quán)的缺省值為各個特征方差的倒數(shù)。,20-維的對象形狀特征，比如區(qū)域、圓度、離心率、軸方向、各種矩等等。采用歐氏距離來計算相似性。 三、圖像查詢 和文本數(shù)據(jù)的情況相同，用于抽象表示圖像的方法決定了支持何種類型的查詢和檢索操作。特征表示提供了一種表示查詢的語言。有兩種形式來表示查詢。 一種方法：通過樣例查詢，在這種樣例中，我們既可以為要尋找的目標提供一個圖像樣例，也可以勾畫出感興趣圖像的形狀。,接下來便計算樣例圖像的特征向量，然后再把計算出的查詢特征向量和數(shù)據(jù)庫中預先計算出的特征向量進行匹配。 另一種方法：直接以特征

14、表征表達查詢，比如“尋找這樣的圖像，50%的區(qū)域為紅色，并且包含具有特定方向和粒度特征的紋理”。 表示圖像和查詢的特征向量形式與用于文本檢索的向量空間表示非常相似。一個主要差異是圖像特征通常是一個實數(shù)，而詞條向量中的詞條分量通常是某種形式的加權(quán)計數(shù)，代表了這個詞條在文檔中出現(xiàn)的頻繁程度。,不過，這兩種問題都是根據(jù)內(nèi)容檢索的問題，這一共同特征決定了用于文本檢索的很多技術(shù)也適應于圖像檢索應用。,9.6 時間序列和序列檢索,在時間序列和序列數(shù)據(jù)集合中高效而又準確的定位有意義模式的問題對于很多應用都有重要意義，比如復雜系統(tǒng)的診斷和監(jiān)控、生物醫(yī)學數(shù)據(jù)分析以及對科研和商業(yè)時間序列的探索性數(shù)據(jù)分析。這樣例子

15、包括： 找出這樣的顧客：他們相對時間的消費模式和給定的消費特征相似； 在復雜的實時監(jiān)控和故障診斷系統(tǒng)中，搜索出與當前異常傳感器信號相似的以前實例； 在蛋白質(zhì)序列中進行有噪聲子串的匹配。,和二維圖像數(shù)據(jù)相比，可以把序列數(shù)據(jù)看作是一維的。時間序列數(shù)據(jù)是相對時間測量出來的一系列觀察結(jié)果，因此可以用時間變量t來索引觀察值。 序列數(shù)據(jù)的概念比時間序列數(shù)據(jù)的概念更廣，因為序列數(shù)據(jù)不一定是時間的函數(shù)。例如，在計算生物學中，蛋白質(zhì)是以其在蛋白質(zhì)序列中的順序位置來索引的。,一、時間序列數(shù)據(jù)的全局模型 傳統(tǒng)的時間序列建模技術(shù)(比如統(tǒng)計方法)主要是建立在全局線性模型基礎(chǔ)上的，典型的例子是Box-Jenkins自回歸

16、模型族，該方法把當前值y(t)模擬成過去值y(t-k)的加權(quán)線性組合，再加上一個額外的噪聲項： 式中i是加權(quán)系數(shù)，e(t)是時間t的噪聲(通常被假定為均值為零的高斯函數(shù))。,Box-Jenkins方法的一個重要貢獻是，如果在時間序列中存在可識別的系統(tǒng)性非平穩(wěn)分量(比如某種趨勢)，那么很多情況下可以把這個不平穩(wěn)分量刪除使這個時間序列變成平穩(wěn)的形式。例如，像國內(nèi)生產(chǎn)總值和道瓊斯指數(shù)這樣的經(jīng)濟指標中包含著固有的上升趨勢(總體而言)，通常要在建模前將這種趨勢刪除。 對于非平穩(wěn)性比較復雜的情況，另一種有用方法是假定這個信號是相對時間局部平穩(wěn)的。,非線性的全局模型對上面公式進行了推廣，比如可以允許y(t)

17、非線性地依賴過去值： 其中g(shù)(.)是非線性的。 從數(shù)據(jù)挖掘的角度來看，如果我們假定這樣的全局模型充分地描述了潛在的時間序列，那么我們就可以使用模型參數(shù)(比如上面的各個權(quán))作為表示數(shù)據(jù)的基礎(chǔ)，而不使用原始數(shù)據(jù)本身。,通過把時間序列表示為參數(shù)向量，把序列問題轉(zhuǎn)化為本章前面所介紹的文本和圖像的方法，便可以在參數(shù)向量空間中定義相似性尺度、在這個空間中定義根據(jù)內(nèi)容檢索的查詢。 二、時間序列的結(jié)構(gòu)和形狀 考慮一個實數(shù)值時間序列的子序列Q=q(t),q(t+m)，和一個長得多的歸檔時間序列X=x(t),x(T)，前者稱為查詢序列。,我們的目標是在X中找到和Q最相似的一個子序列。 現(xiàn)實情況下，X可能是由許多單

18、個的時間序列組成的，但是為了簡單，我們假定它們已經(jīng)被合成一條長的序列。并且假定X和Q都是使用相同采用時間間隔測量的。 上一節(jié)所講的一般方法僅描述一個時間序列的全局特征，根本沒有提供對局部形狀的描述，比如峰值等。通常，全局模型平均了這些局部的結(jié)構(gòu)特征。然而，對于很多時間序列來說，用結(jié)構(gòu)特征來描述它們會更自然。,兩種查詢方法： 第一種：在整個X數(shù)據(jù)中序列化在掃描查詢Q，順著X每次把查詢Q移動一個時間點，同時計算出每個時間點的距離尺度。該方法的主要特點是，開銷大。其焦點集中在低層次的數(shù)據(jù)采樣點，而不是高層次的結(jié)構(gòu)特征，比如峰值、高原、走勢和波谷等。直接計算歐氏距離也對查詢Q和數(shù)據(jù)X中的微小岐變異常敏感。,第二種：先局部化地估計查詢Q和歸檔X的基于形狀特征，然后在較高層次上進行匹配。其特點是，具有計算優(yōu)勢，因為