1、第9章 根據(jù)內(nèi)容檢索,本章目標(biāo) 介紹根據(jù)內(nèi)容檢索的基本概念。 介紹檢索系統(tǒng)的評(píng)介方法。 討論針對(duì)文本數(shù)據(jù)的根據(jù)內(nèi)容檢索問(wèn)題，集中討論向量空間表示，以及文檔中匹配查詢(xún)的算法、隱含語(yǔ)義索引和文檔分類(lèi)。 介紹用于對(duì)個(gè)人偏好建模的自動(dòng)推薦系統(tǒng)。,第9章 根據(jù)內(nèi)容檢索,本章目標(biāo) 討論圖像檢索算法中表示和檢索問(wèn)題。 介紹匹配時(shí)間序列和序列的基本概念。,9.1 簡(jiǎn)介,傳統(tǒng)的數(shù)據(jù)庫(kù)查詢(xún)定義為：查詢(xún)是一種返回精確匹配指定要求的記錄集合(或表項(xiàng)集合)的操作。例如，查詢(xún)“l(fā)evel=MANAGER AND age30”， 返回的結(jié)果是有具有重要職務(wù)的年輕雇員的列表。 但在數(shù)據(jù)分析時(shí)，所感興趣的是更一般的但不很精確的

2、查詢(xún)。 例如，假設(shè)已知一個(gè)患者的人口統(tǒng)計(jì)學(xué)信息(比如年齡性別等等)、血液和其他常規(guī)檢查的結(jié)果，以及生物醫(yī)學(xué)方面的時(shí)間序列、X-光和圖像。,為了輔助對(duì)這個(gè)患者進(jìn)行診斷，醫(yī)生希望了解醫(yī)院數(shù)據(jù)庫(kù)中是否包含類(lèi)似的患者，如果有類(lèi)似的患者，那么他們的診斷、治療方法和最終結(jié)果如何？ 這個(gè)問(wèn)題的難點(diǎn)在于如何根據(jù)不同的數(shù)據(jù)類(lèi)型(多元變量、時(shí)間序列和圖像數(shù)據(jù))來(lái)判斷各個(gè)患者間的相似性。這類(lèi)問(wèn)題采用精確匹配是行不通的，因?yàn)閿?shù)據(jù)庫(kù)中不可能存在各項(xiàng)指標(biāo)完全匹配的患者。,因此，需要解決的是在數(shù)據(jù)庫(kù)找出和指定查詢(xún)或指定對(duì)象最相似的k個(gè)對(duì)象的各種技術(shù)問(wèn)題。 可以把這種形式的檢索看是交互式的數(shù)據(jù)挖掘，因?yàn)橛脩?hù)直接參與了探索數(shù)據(jù)

3、集的過(guò)程指定查詢(xún)并解決匹配過(guò)程得到的結(jié)果。 如果數(shù)據(jù)集是根據(jù)內(nèi)容批注的，那么檢索問(wèn)題就簡(jiǎn)化為標(biāo)準(zhǔn)的數(shù)據(jù)庫(kù)索引問(wèn)題，如果數(shù)據(jù)庫(kù)沒(méi)有被預(yù)先索引，我們僅有要尋找目標(biāo)Q(查詢(xún)模式)的一個(gè)實(shí)例，根據(jù)這個(gè)查詢(xún)模式Q，我們要推論出數(shù)據(jù)集中哪些其他對(duì)象和它相近。,這種檢索方法被稱(chēng)為根據(jù)內(nèi)容檢索(retrieval by content)，它的最著名應(yīng)用是在文本中檢索。在文本檢索中，查詢(xún)模式Q通常是很短的(查詢(xún)?cè)~匯列表)，然后在很大的文檔集合匹配這個(gè)模式。 這類(lèi)問(wèn)題由三個(gè)基本部分組成： 1.如何定義對(duì)象間的相似尺度； 2.如何實(shí)現(xiàn)高計(jì)算效率的搜索算法(對(duì)于給定的相似尺度)； 3.如何在檢索過(guò)程中融入用戶(hù)的反饋并

4、進(jìn)行交互。,本章主要討論第一和第三個(gè)問(wèn)題，第二個(gè)問(wèn)題通常是一種索引問(wèn)題(一個(gè)好的索引可以極大提高效率)。 在下面的分析中，我們使用“相似”這個(gè)詞，又使用“距離”這個(gè)詞。對(duì)應(yīng)的是相似尺度最大化和距離尺度最小化，其他章節(jié)的相似度和相異度。 根據(jù)內(nèi)容檢索需要解決的幾個(gè)問(wèn)題： 1.如何客觀地評(píng)估特定檢索算法的性能。 2.如何決定用以計(jì)算相似尺度的表示。,例如，通常用顏色、紋理和相似特征來(lái)地、表示圖像；用單詞的出現(xiàn)次數(shù)來(lái)表示文本。,9.2 檢索系統(tǒng)的評(píng)價(jià),一、評(píng)價(jià)檢索性能的困難之處 在分類(lèi)和回歸中，總能以一種客觀的方式來(lái)評(píng)判模型的性能。然而，對(duì)于根據(jù)內(nèi)容檢索來(lái)說(shuō)，評(píng)價(jià)一個(gè)特定算法或技術(shù)的性能要復(fù)雜和棘手

5、的多。 主要的難點(diǎn)是檢索系統(tǒng)的最終性能尺度是由檢索出的信息對(duì)用戶(hù)的實(shí)用性來(lái)決定的。檢索是一種以人為中心的交互過(guò)程，這給評(píng)價(jià)檢索性能帶來(lái)了很大困難。,首先我們假定相對(duì)一個(gè)特定的查詢(xún)，可以把對(duì)象標(biāo)記為相關(guān)或不相關(guān)。換句話(huà)來(lái)說(shuō)，對(duì)于任一個(gè)查詢(xún)Q，我們假定存在一個(gè)二值分類(lèi)標(biāo)簽的集合，該集合對(duì)應(yīng)數(shù)據(jù)中的所有對(duì)象，指出哪個(gè)對(duì)象是相關(guān)的，哪個(gè)是不相關(guān)的。最后我們假定已經(jīng)以某種方式為每個(gè)對(duì)象附加標(biāo)簽(假定是以一種比較客觀并與人類(lèi)判相一致的方式)。 基于這些假定，就可以把檢索問(wèn)題看作一種特殊形式的分類(lèi)問(wèn)題類(lèi)標(biāo)簽依賴(lài)于查詢(xún)Q，,也就是，“對(duì)于查詢(xún)Q相關(guān)還是不相關(guān)”，然后相對(duì)Q來(lái)估計(jì)數(shù)據(jù)庫(kù)中對(duì)象的類(lèi)標(biāo)簽。 檢索分類(lèi)

6、的特點(diǎn)： 1.分類(lèi)變量的定義是由用戶(hù)掌握的(用戶(hù)定義查詢(xún)Q)，因此每次運(yùn)行系統(tǒng)時(shí)都可能變化。 2.主要目標(biāo)不是分類(lèi)出數(shù)據(jù)庫(kù)的所有對(duì)象，而是返回與用戶(hù)查詢(xún)最相關(guān)的對(duì)象。,二、查準(zhǔn)率對(duì)查全率 假定我們?cè)谝粋€(gè)獨(dú)立的檢驗(yàn)數(shù)據(jù)集上評(píng)價(jià)一個(gè)指定檢索系統(tǒng)相對(duì)特定查詢(xún)Q的性能。檢驗(yàn)數(shù)據(jù)中的對(duì)象已經(jīng)被預(yù)先分類(lèi)為相對(duì)于查詢(xún)Q是相關(guān)還是不相關(guān)。假定這個(gè)檢驗(yàn)數(shù)據(jù)集沒(méi)有被這個(gè)檢索算法使用過(guò)，我們可以把檢索算法想象為就是要對(duì)這個(gè)數(shù)據(jù)集中的對(duì)象作出分類(lèi)(按照相對(duì)于查詢(xún)Q的相關(guān)性)。 如果這個(gè)算法是使用距離尺度(數(shù)據(jù)集中的每個(gè)對(duì)象相對(duì)于Q的距離)來(lái)排列對(duì)象集合的，那么這個(gè)算法通常具有一個(gè)閾值參數(shù)T。,算法將返回KT個(gè)對(duì)象和查

7、詢(xún)對(duì)象Q的距離小于T的KT個(gè)對(duì)象的有序列表。通過(guò)改變T來(lái)改變檢索系統(tǒng)的性能。 假定對(duì)于有N個(gè)對(duì)象的檢索數(shù)據(jù)集合，檢索系統(tǒng)返回了KT個(gè)可能相關(guān)的對(duì)象，那么可以用表9-1來(lái)歸納這個(gè)算法的性能。,表9-1中，實(shí)驗(yàn)中已經(jīng)標(biāo)記出了各文檔相關(guān)還是不相關(guān)(相對(duì)于查詢(xún)Q)。列對(duì)應(yīng)于真實(shí)情況，行對(duì)應(yīng)于算法對(duì)文檔的判斷。TP，F(xiàn)P，F(xiàn)N，TN分別對(duì)應(yīng)于真的正，假的為正，假的為負(fù)和真的為負(fù)，其中正負(fù)是指算法所給出的分類(lèi)是否相關(guān)。理想的檢索算法將產(chǎn)生FP=FN=0的對(duì)角矩陣。 其中: N=TP+FP+TN+FN(對(duì)象總數(shù)) KT=TP+FP(返回對(duì)象的數(shù)量) TP+FN是相關(guān)對(duì)象的總數(shù)。,查準(zhǔn)率：TP/(TP+FP)

8、 (行) 查全率：TP/(TP+FN) (列) 存在著這樣一個(gè)問(wèn)題：當(dāng)KT增大時(shí)(提高閾值將返回更多的對(duì)象分類(lèi)為相關(guān))，查全率上升(極限情況，可以返回所有對(duì)象，查全率為1)，然而查準(zhǔn)率會(huì)下降。 如果使用不同的閾值T來(lái)運(yùn)行檢索算法，那么會(huì)得到一系列(查全率，查準(zhǔn)率)的點(diǎn)對(duì)。反過(guò)來(lái)使用這些點(diǎn)對(duì)描出這個(gè)特定檢索算法(相對(duì)于查詢(xún)Q、特定的數(shù)據(jù)集、以及數(shù)據(jù)標(biāo)簽)的查全率-查準(zhǔn)率曲線(xiàn)，如圖9-1所示。,圖9-1是三種假想查詢(xún)算法的查全率-查準(zhǔn)率曲線(xiàn)。由圖可見(jiàn)，在大多數(shù)情況下，難以判斷哪一種算法有絕對(duì)優(yōu)勢(shì)，因此不能完全根據(jù)查全率-查準(zhǔn)率曲線(xiàn)來(lái)判定一個(gè)算法就比另一個(gè)算法更好。盡管如此，這些曲線(xiàn)對(duì)于在一定操作條

9、件范圍內(nèi)評(píng)價(jià)檢索算法的相對(duì)、絕對(duì)性能還是有價(jià)值的。,三、查準(zhǔn)率和查全率的實(shí)踐應(yīng)用 查準(zhǔn)率-查全率評(píng)價(jià)在文本檢索中一直特別流行。文本檢索會(huì)議(TREC)就是查準(zhǔn)率-查全率評(píng)價(jià)試驗(yàn)的一個(gè)大型例子。在這項(xiàng)試驗(yàn)中使用幾個(gè)G字節(jié)大小的文本文檔數(shù)據(jù)集合，大約是由一百萬(wàn)個(gè)獨(dú)立的文檔(對(duì)象)組成的，平均每個(gè)文檔有500個(gè)術(shù)語(yǔ)索引。 主要問(wèn)題是如何評(píng)價(jià)相關(guān)性，特別是如何決定相關(guān)文檔總數(shù)以計(jì)算查全率。,如果使用50個(gè)不同查詢(xún)，那么就需要每個(gè)人工裁判員給出5千萬(wàn)個(gè)分類(lèi)標(biāo)簽!由于TREC會(huì)議的參展系很多(30),所以TREC裁判員把他們的裁判范圍限制在所有檢索系統(tǒng)所返回文檔的前100篇文檔的聯(lián)合，并假定這個(gè)集合通常已

10、經(jīng)包含了幾乎所有的相關(guān)文檔。因此，每個(gè)裁判者僅需作出幾千個(gè)相關(guān)性判斷，而不是幾千萬(wàn)個(gè)。,9.3 文本檢索,傳統(tǒng)上，一直把對(duì)文本信息的檢索稱(chēng)為信息檢索(IR)，互聯(lián)網(wǎng)搜索引擎的出現(xiàn)使其成為一個(gè)備受關(guān)注的課題。 文本由兩個(gè)基本單位組成，即文檔和詞條。 按照IR慣例，文本查詢(xún)是由詞條集合指定的。,一、文本的表示 大多數(shù)關(guān)于文本檢索的研究集中在尋找支持如下兩個(gè)特征的通用表示 : 1.盡可能保留數(shù)據(jù)語(yǔ)義內(nèi)容的能力； 2.可以高效的計(jì)算查詢(xún)和文檔間的距離。 目前的IR系統(tǒng)通常依賴(lài)于簡(jiǎn)單的詞條匹配和計(jì)數(shù)技術(shù)，即通過(guò)詞條出現(xiàn)次數(shù)向量隱含并近似地捕捉了文檔語(yǔ)義。 假定已經(jīng)預(yù)先定義了要檢索的一系列詞條tj,1jT

11、，然后把每一篇文檔Di，1iN表示為詞條向量：,Di=(di1,di2,diT) 其中dij表示第j個(gè)詞條在第i篇文檔中出現(xiàn)的某種信息，各個(gè)dij被稱(chēng)為詞條權(quán)。 在布爾表示中， dij取1或0。在向量空間表示中，可以是某個(gè)實(shí)數(shù)值的數(shù)字。 下面考慮一個(gè)涉及10篇文檔和6個(gè)詞條的簡(jiǎn)單例子。六個(gè)詞條是： t1=數(shù)據(jù)庫(kù)，t2=SQL，t3=索引，t4=回歸 t5=似然，t6=線(xiàn)性的。,表9-2為106的文檔-詞條頻率矩陣M。,文檔間的距離尺度采用余弦距離： 這是兩個(gè)向量夾角的余弦(等價(jià)于把它們標(biāo)準(zhǔn)化為單位長(zhǎng)度后的內(nèi)積)，因此它反映了兩個(gè)向量的詞條分量的相對(duì)分布相似性。該距離尺度在IR試驗(yàn)中特別有效。同

12、樣地，我們也可以使用其它距離尺度，如歐氏距離。,下圖是表9-2中的文檔-詞條頻率矩陣的像素形式距離矩陣。上圖是歐氏距離矩陣，下圖是余弦距離矩陣。,較亮的方塊表示兩篇文檔比較接近，較暗的地方表示不相近。 對(duì)于歐氏距離，白色對(duì)應(yīng)兩篇文檔間的距離為0；黑色對(duì)應(yīng)最大距離。 對(duì)于余弦距離，較亮的像素對(duì)應(yīng)于較大的余弦值(較小的角度)；較暗的像素對(duì)應(yīng)于較小的余弦值(較大的角度)。 在兩種距離矩陣中都可以清楚的看出存在兩個(gè)文檔簇，一類(lèi)是關(guān)于數(shù)據(jù)庫(kù)的文檔，另一類(lèi)是關(guān)于回歸的文檔，圖中的兩個(gè)顏色較淡的方塊區(qū)域。,從圖中可見(jiàn)，余弦距離更好的區(qū)分了兩個(gè)組。 在歐氏距離中，文檔3和文檔4(數(shù)據(jù)庫(kù)簇中)到文檔5(另一篇數(shù)

13、據(jù)庫(kù)文檔)的距離比到文檔6,8和9(關(guān)于回歸的文檔)的距離還要遠(yuǎn)。導(dǎo)致這一現(xiàn)象的原因就是文檔3和4(以及6,8和9)與文檔5相比更靠近原點(diǎn)。 余弦距離發(fā)揮了基于角度距離的優(yōu)點(diǎn)，更強(qiáng)調(diào)各個(gè)詞條的相對(duì)分布，因此產(chǎn)生的區(qū)分更加明顯。,上例的一個(gè)推廣，對(duì)于具有N篇文檔的T個(gè)詞條的集合，我們可以構(gòu)造一個(gè)NT的矩陣。通常這個(gè)矩陣是非常稀疏的。比如上面提到的TREC文檔群大約僅0.03%的單元是非零的。 在文本檢索系統(tǒng)時(shí)，出于對(duì)詞條-文檔矩陣稀疏性的考慮，原始的文檔-詞條矩陣被表示為一種倒排文件結(jié)構(gòu)(而不是直接表示為矩陣形式)，也就是按照T個(gè)詞條來(lái)索引文件，每個(gè)詞條tj指向一個(gè)N個(gè)數(shù)字的列表，這些數(shù)字描述了

14、每篇文檔中出現(xiàn)該詞條的情況(dij,j固定)。,二、匹配查詢(xún)和文檔 也可以使用與文檔相同的基于詞條的表征來(lái)表達(dá)查詢(xún)。實(shí)際上，可以把查詢(xún)本身當(dāng)作一篇文檔來(lái)表示，只不過(guò)是通常查詢(xún)僅包含很少的詞條。 在向量空間中，可以把查詢(xún)表示為一個(gè)權(quán)向量。詞條沒(méi)有出現(xiàn)時(shí)權(quán)值為0，詞條在查詢(xún)出現(xiàn)時(shí)，用戶(hù)可以指定權(quán)值，以表示每個(gè)詞條的相對(duì)重要性(權(quán)值限定在01之間)。,令Q=(q1,qT)為查詢(xún)權(quán)向量。最簡(jiǎn)單的形式，權(quán)值要么為1要么為0。下面二值模式的例子，考慮三個(gè)查詢(xún)，每個(gè)都是由一個(gè)詞條組成的，分別是“數(shù)據(jù)庫(kù)” ，“SQL”，“回歸”。根據(jù)前面例子，可以把這三個(gè)查詢(xún)表達(dá)為三個(gè)向量：(1,0,0,0,0,0)、 (0

15、,1,0,0,0,0)和(0,0,0,1,0,0)。利用余弦距離在表9-2所示的數(shù)據(jù)中匹配這三個(gè)查詢(xún)，得到最相近的文檔，分別是d2、d3和d9。 更一般的情況，是如何設(shè)置匹配查詢(xún)中權(quán)值，以提高檢索的性能。許多IR文獻(xiàn)有相關(guān)的報(bào)導(dǎo)。,已經(jīng)證明一種被稱(chēng)為T(mén)F-IDF加權(quán)的特殊加權(quán)模式在實(shí)踐中特別有效。TF(term frequency)代表詞條頻率，表9-2中的文檔-詞條示例矩陣就是以TF的形式表示的。 然而，如果一個(gè)詞條在文檔集合中的很多文檔中頻繁出現(xiàn)，那么利用TF代表權(quán)進(jìn)行檢索的判斷力就很小了，也就是它會(huì)提高查全率但是查準(zhǔn)率可能很差。文檔頻率倒數(shù)-IDF(inverse-document-frequency)權(quán)可以提高判別力。 IDF定義為：log(N/nj)，式中N為文檔總數(shù)，nj為包含詞條j的文檔數(shù)量。,IDF權(quán)偏向于僅在很少文檔中出現(xiàn)的詞條，也就是說(shuō)它是有判別力的。采用對(duì)數(shù)形式是使這個(gè)權(quán)對(duì)文檔總數(shù)N不特別敏感。 TF-IDF權(quán)就是特定詞條在特定文檔中的TF權(quán)和IDF權(quán)的乘積。表9-2中的文檔矩陣所產(chǎn)生的IDF權(quán)是：(0.105,0.693,0.511,0.693,0.357,0.693)。由此可得TF-IDF文檔-詞條矩陣(即把表9-2