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

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

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

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

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

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

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

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

0,0

(一個(gè)索引項(xiàng)也不包含)dj=

0,0.7

(包含其中一個(gè)索引項(xiàng))dk=

1,2

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

–

一般表示向量空間中的N個(gè)文檔可以用一個(gè)矩陣表示矩陣中的一個(gè)元素對(duì)應(yīng)于文檔中一個(gè)詞項(xiàng)的權(quán)重。“0〞意味著該詞項(xiàng)在文檔中沒有意義，或該詞項(xiàng)不在文檔中出現(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嗎？怎樣衡量相似程度？夾角還是投影相似度計(jì)算相似度是一個(gè)函數(shù)，它給出兩個(gè)向量之間的相似程度，查詢式和文檔都是向量，各類相似度存在于：兩個(gè)文檔之間〔文本分類，聚類〕兩個(gè)查詢式之間〔常問問題集〕一個(gè)查詢式和一個(gè)文檔之間〔檢索〕人們?cè)岢龃罅康南嗨贫扔?jì)算方法，因?yàn)樽钫_的相似度計(jì)算方法并不存在。通過計(jì)算查詢式和文檔之間的相似度可以根據(jù)預(yù)定的重要程度對(duì)檢索出來的文檔進(jìn)行排序可以通過強(qiáng)制設(shè)定某個(gè)閾值，控制被檢索出來的文檔的數(shù)量檢索結(jié)果可以被用于相關(guān)反響中，以便對(duì)原始的查詢式進(jìn)行修正。(例如：將文檔向量和查詢式向量進(jìn)行結(jié)合)相似度度量

–

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

和查詢式Q

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

,Q)=

(dik

qk)dik

是文檔di中的詞項(xiàng)k

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

–

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

=70意味著某個(gè)詞項(xiàng)沒有在文檔中出現(xiàn)，或者沒有在查詢式中出現(xiàn)加權(quá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)積的特點(diǎn)內(nèi)積值沒有界限不象概率值，要在(0,1)之間對(duì)長(zhǎng)文檔有利內(nèi)積用于衡量有多少詞項(xiàng)匹配成功，而不計(jì)算有多少詞項(xiàng)匹配失敗長(zhǎng)文檔包含大量獨(dú)立詞項(xiàng)，每個(gè)詞項(xiàng)均屢次出現(xiàn)，因此一般而言，和查詢式中的詞項(xiàng)匹配成功的可能性就會(huì)比短文檔大。余弦(Cosine)相似度度量余弦相似度計(jì)算兩個(gè)向量的夾角余弦相似度是利用向量長(zhǎng)度對(duì)內(nèi)積進(jìn)行歸一化的結(jié)果

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用余弦計(jì)算，D1

比

D2

高6倍；用內(nèi)積計(jì)算，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)點(diǎn)術(shù)語權(quán)重的算法提高了檢索的性能局部匹配的策略使得檢索的結(jié)果文檔集更接近用戶的檢索需求可以根據(jù)結(jié)果文檔對(duì)于查詢串的相關(guān)度通過CosineRanking等公式對(duì)結(jié)果文檔進(jìn)行排序缺乏標(biāo)引詞之間被認(rèn)為是相互獨(dú)立隨著Web頁面信息量的增大、Web格式的多樣化，這種方法查詢的結(jié)果往往會(huì)與用戶真實(shí)的需求相差甚遠(yuǎn)，而且產(chǎn)生的無用信息量會(huì)非常大隱含語義索引模型是向量空間模型的延伸5.4擴(kuò)展的布爾模型布爾檢索例如“飛碟〞AND“小說〞：只能檢索出D4，無法顯現(xiàn)D1,D2,D3的差異“飛碟〞OR“小說〞：可以檢出D1,D2,D4，但無法顯現(xiàn)它們的差異布爾模型和向量空間模型相結(jié)合布爾模型可以和向量空間模型相結(jié)合，先做布爾過濾，然后進(jìn)行排序：首先進(jìn)行布爾查詢將全部滿足布爾查詢的文檔聚集成一個(gè)文檔用向量空間法對(duì)布爾檢索結(jié)果進(jìn)行排序布爾過濾排序文檔向量空間表示的查詢式結(jié)果布爾查詢式如果忽略布爾關(guān)系的話，向量空間查詢式和布爾查詢式是相同的先“布爾〞，后“排序〞存在的問題如果“與〞應(yīng)用于布爾查詢式,結(jié)果集可能太窄,因而影響了后面的排序過程如果“或〞應(yīng)用于布爾查詢式,就和純向量空間模型沒有區(qū)別了在第一步，如何最正確地應(yīng)用布爾模型呢？提出擴(kuò)展布爾模型擴(kuò)展布爾模型中的“或〞關(guān)系給定一個(gè)或關(guān)系的查詢式：xy假設(shè)文檔di中x和y的權(quán)重被歸一化在(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)最不期望的點(diǎn)dx

y一個(gè)文檔在(1,1)處獲得最高的權(quán)重，此時(shí)意味著文檔包含了全部?jī)蓚€(gè)查詢?cè)~，并且查詢?cè)~在文檔中的權(quán)重也是最高的函數(shù)sim()度量了從原點(diǎn)出發(fā)的文檔向量長(zhǎng)度擴(kuò)展布爾模型中的“與〞關(guān)系給定一個(gè)聯(lián)合的查詢式

x

ysim(qand,dj)=1

{[(1

x)2+(1

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

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

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

sim(qand,dj)=sim(qor,dj)=1當(dāng)dj既不包含x也不包含y時(shí)

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

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)觀察一個(gè)詞項(xiàng)的存在將對(duì)“或〞關(guān)系查詢式提供0.707的增益值，但對(duì)“與〞關(guān)系查詢式僅提供0.293的增益值一個(gè)詞項(xiàng)不存在，將給“與〞關(guān)系的查詢式提供0.707的罰分當(dāng)x和y有權(quán)值0.5,sim(qand,d)=sim(qor,d)=0.5在一個(gè)“與〞關(guān)系查詢中，兩個(gè)詞項(xiàng)的權(quán)重均為0.5，那么相似度為0.5。其中一個(gè)權(quán)重為1，另一個(gè)為0，相似度為0.293。在“或關(guān)系〞查詢中，情況恰好相反在“與關(guān)系〞查詢中，如果一個(gè)詞項(xiàng)的權(quán)重低于0.5，將給相似度奉獻(xiàn)一個(gè)較大的罰分p-norm模型擴(kuò)展布爾模型可以被泛化為m

個(gè)查詢項(xiàng):

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它可以被進(jìn)一步地

泛化為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當(dāng)p=1時(shí),sim(qor,d)=sim(qand,d)=(x1+x2

+...+xm

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

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