信息內(nèi)容檢索技術

信息內(nèi)容平安王佰靈網(wǎng)絡技術研究所哈爾濱工業(yè)大學（威海）技術Email:wbl@本章課程內(nèi)容5.1信息檢索模型概述5.2布爾模型5.3向量空間模型5.4擴展的布爾模型5.5基于本體論的信息檢索模型5.1信息檢索模型概述5.1.1什么是模型？模型是采用數(shù)學工具，對現(xiàn)實世界某種事物或某種運動的抽象描述面對相同的輸入，模型的輸出應能夠無限地逼近現(xiàn)實世界的輸出舉例：天氣的預測模型信息檢索模型是表示文檔，用戶查詢以及查詢與文檔的關系的框架5.1.2信息檢索模型信息檢索模型是一個四元組[D,Q,F,R(qi,dj)]D:文檔集的機內(nèi)表示Q:用戶需求的機內(nèi)表示F:文檔表示、查詢表示和它們之間的關系的模型框架(Frame)R(qi,dj):排序函數(shù)，給queryqi

和documentdj評分信息檢索模型取決于：從什么樣的視角去看待查詢式和文檔基于什么樣的理論去看待查詢式和文檔的關系如何計算查詢式和文檔之間的相似度5.1.3模型分類信息檢索模型布爾向量空間概率知識模糊集擴展的布爾模型集合論代數(shù)擴展的向量空間隱性語義索引神經(jīng)網(wǎng)絡語言模型推理網(wǎng)絡信念網(wǎng)絡概率基于本體論的模型人工智能5.2布爾模型5.2.1布爾模型來源最早的IR模型，也是應用最廣泛的模型目前仍然應用于商業(yè)系統(tǒng)中Lucene是基于布爾〔Boolean〕模型的5.2.1布爾模型描述文檔D表示一個文檔被表示為關鍵詞的集合查詢式Q表示查詢式(Queries)被表示為關鍵詞的布爾組合，用“與、或、非〞連接起來，并用括弧指示優(yōu)先次序匹配F一個文檔當且僅當它能夠滿足布爾查詢式時，才將其檢索出來檢索策略基于二值判定標準算法R根據(jù)匹配框架F判定相關5.2.2布爾模型舉例Q=病毒AND〔計算機OR電腦〕ANDNOT醫(yī)文檔：D1:…據(jù)報道計算機病毒最近猖獗D2：小王雖然是學醫(yī)的，但對研究電腦病毒也感興趣…D3：計算機程序發(fā)現(xiàn)了艾滋病病毒傳播途徑上述文檔哪一個會被檢索到？5.2.2布爾模型查詢表示在布爾模型中，所有索引項的權值變量和文檔dj與查詢q的相關度都是二值的查詢q被表述成一個常規(guī)的布爾表達式，為方便計算查詢q和文檔d的相關度，一般將查詢q的布爾表達式轉換成析取范式qDNF

5.2.2布爾模型例如文檔集包含兩個文檔：文檔1：abcfgh文檔2：afbxyz

用戶查詢：文檔中出現(xiàn)a或者b，但一定要出現(xiàn)z。將查詢表示為布爾表達式,并轉換成析取范式文檔1和文檔2的三元組對應值分別為(1,1,0)和(1,1,1)經(jīng)過匹配,將文檔2返回5.2.3布爾模型優(yōu)點到目前為止，布爾模型是最常用的檢索模型，因為：由于查詢簡單，因此容易理解通過使用復雜的布爾表達式，可以很方便地控制查詢結果相當有效的實現(xiàn)方法相當于識別包含了一個某個特定term的文檔經(jīng)過某種訓練的用戶可以容易地寫出布爾查詢式布爾模型可以通過擴展來包含排序的功能，即“擴展的布爾模型〞布爾模型存在問題布爾模型被認為是功能最弱的方式，其主要問題在于不支持局部匹配，而完全匹配會導致太多或者太少的結果文檔被返回非常剛性:“與〞意味著全部;“或〞意味著任何一個很難控制被檢索的文檔數(shù)量原那么上講，所有被匹配的文檔都將被返回很難對輸出進行排序不考慮索引詞的權重，所有文檔都以相同的方式和查詢相匹配很難進行自動的相關反響如果一篇文檔被用戶確認為相關或者不相關，怎樣相應地修改查詢式呢？5.3向量空間模型模型的提出Salton在上世紀60年代提出的向量空間模型進行特征表達成功應用于SMART〔SystemfortheManipulationandRetrievalofText〕文本檢索系統(tǒng)這一系統(tǒng)理論框架到現(xiàn)在仍然是信息檢索技術研究的根底模型的描述文檔D(Document)：泛指文檔或文檔中的一個片段〔如文檔中的標題、摘要、正文等〕。索引項t〔Term〕：指出現(xiàn)在文檔中能夠代表文檔性質的根本語言單位〔如字、詞等〕，也就是通常所指的檢索詞，這樣一個文檔D就可以表示為D(t1,t2,…,tn)，其中n就代表了檢索字的數(shù)量。特征項權重Wk〔TermWeight〕：指特征項tn能夠代表文檔D能力的大小，表達了特征項在文檔中的重要程度。相似度S〔Similarity〕：指兩個文檔內(nèi)容相關程度的大小模型的特點基于關鍵詞(一個文本由一個關鍵詞列表組成)根據(jù)關鍵詞的出現(xiàn)頻率計算相似度例如：文檔的統(tǒng)計特性用戶規(guī)定一個詞項(term)集合，可以給每個詞項附加權重未加權的詞項:Q=database;text;information加權的詞項:Q=database0.5;text0.8;information0.2查詢式中沒有布爾條件根據(jù)相似度對輸出結果進行排序支持自動的相關反響有用的詞項被添加到原始的查詢式中例如：Qdatabase;text;information;document模型中的問題怎樣確定文檔中哪些詞是重要的詞？〔索引項〕怎樣確定一個詞在某個文檔中或在整個文檔集中的重要程度？〔權重〕怎樣確定一個文檔和一個查詢式之間的相似度？索引項的選擇假設干獨立的詞項被選作索引項(indexterms)or詞表vocabulary索引項代表了一個應用中的重要詞項計算機科學圖書館中的索引項應該是哪些呢?體系結構總線計算機數(shù)據(jù)庫….XML計算機科學文檔集文檔集中的索引項索引項的選擇這些索引項是不相關的(或者說是正交的)，形成一個向量空間vectorspace實際上，這些詞項是相互關聯(lián)的當你在一個文檔中看到“計算機〞,非常有可能同時看到“科學〞當你在一個文檔中看到“計算機〞,有中等的可能性同時看到“商務〞當你在一個文檔中看到“商務〞，只有很少的時機同時看到“科學〞“計算機”“科學”“商務”計算機科學文檔集該文檔集中的全部重要詞項詞項的權重根據(jù)詞項在文檔(tf)和文檔集(idf)中的頻率(frequency)計算詞項的權重tfij=詞項j在文檔i中的頻率dfj=詞項j的文檔頻率=

包含詞項j的文檔數(shù)量idfj=詞項j的反文檔頻率=log2(N/dfj)N:文檔集中文檔總數(shù)反文檔頻率用詞項區(qū)別文檔Idf計算例如文檔的詞項權重(TFIDF舉例)文本：“俄羅斯頻繁發(fā)生恐怖事件，俄羅斯的平安部門加大打擊恐怖主義的力度。〞TFIDFTFIDFTFIDFTFIDF俄羅斯2較高高安全1中等高恐怖2較高高部門1較低低的2非常低很低加大1較低低頻繁1較低低打擊1中等高發(fā)生1較低低主義1較低低事件1較低低力度1中等高查詢式的詞項權重如果詞項出現(xiàn)在查詢式中，那么該詞項在查詢式中的權重為1，否那么為0也可以用用戶指定查詢式中詞項的權重一個自然語言查詢式可以被看成一個文檔查詢式：“有沒有周杰倫的歌？〞會被轉換為:

<周杰倫,歌>查詢式：“請幫我找關于俄羅斯和車臣之間的戰(zhàn)爭以及車臣恐怖主義首腦的資料〞會被轉換為:

<俄羅斯2,車臣2,戰(zhàn)爭1,恐怖主義1,首腦1>過濾掉了：“請幫我找〞，“和〞，“之間的〞，“以及〞，“的資料〞兩個文檔之間的相似度可以同理計算由索引項構成向量空間2個索引項構成一個二維空間，一個文檔可能包含0,1或2個索引項di=

0,0

(一個索引項也不包含)dj=

0,0.7

(包含其中一個索引項)dk=

1,2

(包含兩個索引項)類似的，3個索引項構成一個三維空間，n個索引項構成n維空間一個文檔或查詢式可以表示為n個元素的線性組合文檔集

–

一般表示向量空間中的N個文檔可以用一個矩陣表示矩陣中的一個元素對應于文檔中一個詞項的權重。“0〞意味著該詞項在文檔中沒有意義，或該詞項不在文檔中出現(xiàn)。

T1T2….

TtD1d11d12…d1tD2

d21d22…d2t

::::

::::Dndn1dn2…dnt圖示舉例:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T37325D1比D2更接近Q嗎？怎樣衡量相似程度？夾角還是投影相似度計算相似度是一個函數(shù)，它給出兩個向量之間的相似程度，查詢式和文檔都是向量，各類相似度存在于：兩個文檔之間〔文本分類，聚類〕兩個查詢式之間〔常問問題集〕一個查詢式和一個文檔之間〔檢索〕人們曾提出大量的相似度計算方法，因為最正確的相似度計算方法并不存在。通過計算查詢式和文檔之間的相似度可以根據(jù)預定的重要程度對檢索出來的文檔進行排序可以通過強制設定某個閾值，控制被檢索出來的文檔的數(shù)量檢索結果可以被用于相關反響中，以便對原始的查詢式進行修正。(例如：將文檔向量和查詢式向量進行結合)相似度度量

–

內(nèi)積(InnerProduct)文檔D

和查詢式Q

可以通過內(nèi)積進行計算:sim(D

,Q)=

(dik

qk)dik

是文檔di中的詞項k

的權重，qk是查詢式Q中詞項k的權重對于二值向量,內(nèi)積是查詢式中的詞項和文檔中的詞項相互匹配的數(shù)量對于加權向量,內(nèi)積是查詢式和文檔中相互匹配的詞項的權重乘積之和內(nèi)積

–

舉例二值〔Binary〕:D=1,1,1,0,1,1,0Q=1,0,1,0,0,1,1sim(D,Q)=3retrievaldatabasearchitecturecomputertextmanagementinformation向量的大小=詞表的大小

=70意味著某個詞項沒有在文檔中出現(xiàn)，或者沒有在查詢式中出現(xiàn)加權D1=2T1+3T2+5T3D2=3T1+7T2+T3

Q=0T1+0T2+2T3 sim(D1

,Q)=2*0+3*0+5*2=10 sim(D2

,Q)=3*0+7*0+1*2=2內(nèi)積的特點內(nèi)積值沒有界限不象概率值，要在(0,1)之間對長文檔有利內(nèi)積用于衡量有多少詞項匹配成功，而不計算有多少詞項匹配失敗長文檔包含大量獨立詞項，每個詞項均屢次出現(xiàn)，因此一般而言，和查詢式中的詞項匹配成功的可能性就會比短文檔大。余弦(Cosine)相似度度量余弦相似度計算兩個向量的夾角余弦相似度是利用向量長度對內(nèi)積進行歸一化的結果

2t3t1t2D1D2Q

1CosSim(Di,Q)=D1=2T1+3T2+5T3CosSim(D1

,Q)=5/38=0.81D2=3T1+7T2+T3CosSim(D2

,Q)=1/59=0.13

Q=0T1+0T2+2T3用余弦計算，D1

比

D2

高6倍；用內(nèi)積計算，D1

比

D2

高5倍其它相似度度量方法存在大量的其它相似度度量方法JaccardCoefficient:D1=2T1+3T2+5T3Sim(D1

,Q)=10/(38+4-10)=10/32=0.312D2=3T1+7T2+T3Sim(D2

,Q)=2/(59+4-2)=2/61=0.033

Q=0T1+0T2+2T3D1

比

D2

高9.5倍例如二值化的相似度度量InnerProduct:Cosine:Jaccard:diandqkherearesetsofkeywordsdi

和

qkherearevector向量空間優(yōu)點術語權重的算法提高了檢索的性能局部匹配的策略使得檢索的結果文檔集更接近用戶的檢索需求可以根據(jù)結果文檔對于查詢串的相關度通過CosineRanking等公式對結果文檔進行排序缺乏標引詞之間被認為是相互獨立隨著Web頁面信息量的增大、Web格式的多樣化，這種方法查詢的結果往往會與用戶真實的需求相差甚遠，而且產(chǎn)生的無用信息量會非常大隱含語義索引模型是向量空間模型的延伸5.4擴展的布爾模型布爾檢索例如“飛碟〞AND“小說〞：只能檢索出D4，無法顯現(xiàn)D1,D2,D3的差異“飛碟〞OR“小說〞：可以檢出D1,D2,D4，但無法顯現(xiàn)它們的差異布爾模型和向量空間模型相結合布爾模型可以和向量空間模型相結合，先做布爾過濾，然后進行排序：首先進行布爾查詢將全部滿足布爾查詢的文檔聚集成一個文檔用向量空間法對布爾檢索結果進行排序布爾過濾排序文檔向量空間表示的查詢式結果布爾查詢式如果忽略布爾關系的話，向量空間查詢式和布爾查詢式是相同的先“布爾〞，后“排序〞存在的問題如果“與〞應用于布爾查詢式,結果集可能太窄,因而影響了后面的排序過程如果“或〞應用于布爾查詢式,就和純向量空間模型沒有區(qū)別了在第一步，如何最正確地應用布爾模型呢？提出擴展布爾模型擴展布爾模型中的“或〞關系給定一個或關系的查詢式：xy假設文檔di中x和y的權重被歸一化在(0,1)區(qū)間內(nèi):wx,j=〔tfx,j/maxltfl,j〕〔idfx/maxiidfi〕 sim(qor,dj)=[(x2+y2)/2]0.5wherex=wx,jandy=wy,j(1,1)wx,jwy,j(1,0)(0,1)(0,0)最不期望的點dx

y一個文檔在(1,1)處獲得最高的權重，此時意味著文檔包含了全部兩個查詢詞，并且查詢詞在文檔中的權重也是最高的函數(shù)sim()度量了從原點出發(fā)的文檔向量長度擴展布爾模型中的“與〞關系給定一個聯(lián)合的查詢式

x

ysim(qand,dj)=1

{[(1

x)2+(1

y)2]/2}0.5函數(shù)sim()表示從(1,1)

出發(fā)到d的向量長度(1,1)wx,jwy,j(1,0)(0,1)(0,0)最期望的點dx

y擴展的布爾檢索相似度計算例如觀察如果權值是布爾型的，x出現(xiàn)在文檔dj中，那么x在文檔dj中具有權重1，否那么為0當dj包含x和y時

sim(qand,dj)=sim(qor,dj)=1當dj既不包含x也不包含y時

sim(qand,dj)=sim(qor,dj)=0當dj包含x和y二者之一時

sim(qand,dj)=11/20.5=0.293

sim(qor,dj)=1/20.5=0.707(1,1)wx,jwy,j(1,0)(0,1)(0,0)觀察一個詞項的存在將對“或〞關系查詢式提供0.707的增益值，但對“與〞關系查詢式僅提供0.293的增益值一個詞項不存在，將給“與〞關系的查詢式提供0.707的罰分當x和y有權值0.5,sim(qand,d)=sim(qor,d)=0.5在一個“與〞關系查詢中，兩個詞項的權重均為0.5，那么相似度為0.5。其中一個權重為1，另一個為0，相似度為0.293。在“或關系〞查詢中，情況恰好相反在“與關系〞查詢中，如果一個詞項的權重低于0.5，將給相似度奉獻一個較大的罰分p-norm模型擴展布爾模型可以被泛化為m

個查詢項:

sim(qor,d)=[(x12+x22+...+xm2)/m]0.5

sim(qand,d)=1

{[(1

x1)2+(1

x2)2+...+(1

xm)2]/m}0.5它可以被進一步地

泛化為p-normmodel:

sim(qor,d)=[(x1p+x2p

+...+xmp

)/m]1/p

sim(qand,d)=1

{[(1

x1)p+(1

x2)p+...+(1

xm)p]/m}1/p當p=1時,sim(qor,d)=sim(qand,d)=(x1+x2

+...+xm

)/m通過語詞-文獻權值的和來求合取和析取查詢的值，和向量空間中的內(nèi)積相似當p=

,sim(qor,d)=max(xi);sim(qand,d)=min(xi)模糊邏輯模型(Fuzzylogicmodel)5.5基于本體論的信息檢索模型本體論本體論〔Ontology〕最早是哲學的分支，研究客觀事物存在的本質。本體〔ontology〕的含義是形成現(xiàn)象的根本實體(常與“現(xiàn)象〞相對)。從哲學的范疇來說，本體是客觀存在的一個系統(tǒng)的解釋或說明，關心的是客觀現(xiàn)實的抽象本質。它與認識論〔Epistemology〕相對，認識論研究人類知識的本質和來源。本體論研究客觀存在，認識論研究主觀認知。各種關于本體的定義在人工智能界，最早給出本體定義的是Neches等人，將本體定義為“給出構成相關領域詞匯的根本術語和關系，以及利用這些術語和關系構成的規(guī)定這些詞匯外延的規(guī)那么的定義〞。1993年，Gruber給出了本體的一個最為流行的定義，即“本體是概念模型的明確的標準說明〞。后來，Borst在此根底上,給出了本體的另外一種定義：“本體是共享概念模型的形式化標準說明〞。Studer等對上述兩個定義進行了深入的研究，認為“本體是共享概念模型的明確的形式化標準說明〞。本體的分類和內(nèi)容本體的分類本體是采用某種語言對概念化的描述，本體的分類按照表示和描述的形式化的程度不同，可以分為：完全非形式化的、半形式化的、嚴格形式化的，形式化程度越高，越有利于計算機進行自動處理。本體的內(nèi)容從概念化對象的定義來看，一個領域的術語、術語的定義以及各個術語之間的語義網(wǎng)絡，應是任一個領域本體論所必須包含的根本信息。概念之間的關系同