《根據(jù)內(nèi)容檢索》PPT課件.ppt

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

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

3、對(duì)角陣， 66的矩陣VT的各列提供了數(shù)據(jù)的新共軛基，被稱為主成分方向。 S矩陣的對(duì)角線元素是(協(xié)方差矩陣對(duì)應(yīng)): 1, n=77.4,69.5,22.9,13.5,12.1,4.8 可見，前兩個(gè)主成分捕捉了數(shù)據(jù)中的主要變化，和直覺一致。 當(dāng)使用兩個(gè)主成分時(shí)，那么二維表征所保留的變化比例0.925，信息丟失僅7.5%。,如果我們?cè)谛碌亩S主成分空間來表示文檔，那么每篇文檔的系數(shù)對(duì)應(yīng)于U矩陣的前兩列(兩個(gè)主成分對(duì)應(yīng)的特征向量，即新的文檔權(quán)值)：,這兩列可看作新的偽詞條，其作用相當(dāng)于原來6個(gè)詞條的線性組合。 看一下前兩個(gè)主成分方向可以得到的信息(新共軛基)： 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) 這兩個(gè)方向是原來6維詞條空間中數(shù)據(jù)最分散(具有最大方差)的方向。每方向更突出前兩個(gè)詞條(查詢,SQL)：實(shí)際上這是描述和數(shù)據(jù)庫有關(guān)文檔的方向。,第二方向突出了后三個(gè)詞條回歸、似然和線性，這是描述和回歸有關(guān)文檔的方向。圖9-4以圖形方式說明了這一點(diǎn)(將上面數(shù)據(jù)用圖表示)。,當(dāng)把文檔投影到由前兩個(gè)主成分方向所決定的平面量，兩個(gè)不同組的文檔分布在兩個(gè)不同的方向上。注意文檔2幾乎落在文檔1上，使其有點(diǎn)模糊。文檔5和文檔10的詞條向量最大，因此離原最遠(yuǎn)。 從圖可看出，文檔間的角度差異顯然是相似性的一

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

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

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

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

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

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

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

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

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

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

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

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

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

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