信息檢索導(dǎo)論課后習(xí)題答案

1、信息組織與檢索作業(yè)答案第一章布爾檢索習(xí)題12考慮如下幾篇文檔：文檔 1breakthrough drug for schizophrenia文檔 2new schizophrenia drug文檔 3 new approach for treatment of schizophrenia 文檔 4 new hopes for schizophrenia patientsa. 畫出文檔集對應(yīng)的詞項一文檔矩陣：b. 畫出該文檔集的倒排索引（參考圖1-3中的例子）。Term-Documentmatrix:1234approach0010breakthrough1000drug1100for1011h

2、opes0001new0111of0010patients0001schizophrenia1111treatment0010Inverted Index: approach -> 3 breakthrough ->1 drug->1->2 for ->1->3->4 hopes- >4 new >2->3->4 of ->3 patients ->4 schizophrenia ->1->2->3->4 treatment >3注意：倒排索引中的詞表(dictionary)和每個詞項的

3、倒排列表(posting list)需要排序，便于查找。這里我們暫不考慮詞的正規(guī)化處理(如hopes->hope)o補充習(xí)題1寫出AND查詢的偽代碼面向過程風(fēng)格的偽代碼：給定兩個指針pl和P2,分別指向兩倒排列表listl和Iist2(鏈表實現(xiàn))的首元素：令docld(pl) 表示pl所指向的元素的docld查詢結(jié)果存放在answer列表里。這里應(yīng)用了 “化歸”思想(將新問題轉(zhuǎn)化歸為舊問題來解決)。這里，比較兩排序列表的首 元素，排除較小的docld (不可能有匹配)后，我們構(gòu)造出新的剩余列表，再次進(jìn)行兩列表 的首元素的比較。While pl != null AND p2 != null

4、If pl->docld=p2->docld /對兩(剩余)列表的首元素進(jìn)行比較insertfanswer; pl)；pl=pl->next： 構(gòu)造新的剩余列表，迭代執(zhí)行p2=p2->next： /Else if pl->docld < p2->docldpl=pl->next； /pl->docld不可能有匹配;構(gòu)造新的剩余列表Elsep2=p2->next： /p2->docld不可能有匹配：構(gòu)造新的剩余列表Cnd面向?qū)ο箫L(fēng)格的偽代碼：注：為一個數(shù)據(jù)結(jié)構(gòu)(對象)定義方法，通過方法操作自己的內(nèi)部數(shù)據(jù)(List對象里隱 含包含了

5、一個成員變景，它是真正的鏈表或變長數(shù)組)。While listl.currentltem() != null AND Iist2.currentltem() != nullIf listl.currentltem().getDocld() = list2.currentltem().getDocld()answer.insert(listl.currentltem();listl.moveToNextf);Hst2.moveToNext();Else if listl.currentltem().getDocld() < list2.currentltem().getDocld()lis

6、tl.moveToNextf);Elselist2.moveToNext();End習(xí)題1-10寫出OR查詢的偽代碼而向過程風(fēng)格的偽代碼：給定兩個指針pl和p2,分別指向兩倒排列表listl和Iist2(鏈表實現(xiàn))的首元素；令docld(pl) 表示pl所指向的元素的docld：查詢結(jié)果存放在answer列表里。While pl != null AND p2 != nullIf pl>docld = p2->docldinsertfanswec pl)：pl=pl->next：p2=p2->next；構(gòu)造新的剩余列表，迭代執(zhí)行Else if pl->docld &

7、lt; p2->docldinsert(answec pl)：pl=pl->next： 構(gòu)造新的剩余列表，迭代執(zhí)行Elseinsert(answer, p2)：p2=p2->next： 構(gòu)造新的剩余列表,迭代執(zhí)行EndWhile pl != null/條件為真時，加入listl的剩余元素(此時Iist2已遍歷到結(jié)尾)insert(answec pl)：pl=pl->next：ENDWhile p2 != null/條件為真時，加入Iist2的剩余元素此時listl已遍歷到結(jié)尾)insert(answec p2)：p2=pl->next；END面向?qū)ο箫L(fēng)格的偽代碼：

8、While listl.currentltem() != null AND Iist2.currentltem() != nullIf listl.currentltem().getDocld() = list2.currentltem().getDocld()answer.insert(listl.currentltem();listl.moveToNext();list2.moveToNext();Else if listl.currentltem().getDocld() < list2.currentltem().getDocld()answer.insert(listl.cur

9、rentltem();listl.moveToNext();Elseanswer.insert(list2.currentltem();list2.moveToNext();EndWhile listl.currentltem() != nullanswer.insert(listl.currentltem();listl.moveToNext();ENDWhile Iist2.currentltem() != nullanswer.insert(list2.currentltem();list2.moveToNext();END補充習(xí)題2若 個文集有1OOO篇文檔，有40篇是關(guān)于信管專業(yè)建設(shè)

10、的。我的ft息需求是了解信管專業(yè) 的專業(yè)建設(shè)情況,用某搜索引擎在這個文集上搜索，查詢詞為“信管”，搜出100篇包含“信 管”的文檔，這其中有20篇是信管專業(yè)建設(shè)方面的，其它80篇是關(guān)于信管的其它情況。請 問該查詢的正確率和召回率是多少正確率=20/100=0.2召回率=20/40=0.5第二章 詞項詞典及倒排記錄表習(xí)題2.1a. 在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低正確率。錯：相當(dāng)于擴充出同-個詞干表示的多個詞，會降低正確率。b. 在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低召回率。對。c. 詞干還原會增加詞項詞典的大小。錯。d. 詞干還原應(yīng)該在構(gòu)建索引時調(diào)用，而不應(yīng)在查詢處理時調(diào)用。錯；應(yīng)同時做

11、才能保證索引中和查詢詞的匹配。習(xí)題2.2清給出如卜單詞的歸一化形式（歸一化形式也可以是詞本身）。a. 'Cos -> cosb. Shi'ite -> shiite （'是隔音號）c. cont'd->contd （contd.可表示 contained 包括：continued 繼續(xù)）d. Hawai'i >hawaiie. O'Rourke ->orourke習(xí)題2.3如下詞經(jīng)過Porter詞干還原工具處理后會輸出同樣的結(jié)果，你認(rèn)為哪對(幾對)詞不應(yīng) 該輸出同樣的結(jié)果？為什么？a. abandon/abandon

12、mentb. absorbency/absorbentc. marketing/marketsd. university/universee. volume/volumes按Porter詞干還原算法，這幾組詞都可以被還原為相應(yīng)的詞干。但是這里問的是哪些組做詞 干還原不合適，原因是某組的兩個詞雖然來源于同一個詞干，但是它們的意思不同，如果做 詞干還原處理會降低正確率。c組不做詞干還原。marketing表示營銷，market表示市場。d組不做詞干還原。university表示大學(xué)，universe表示宇宙。習(xí)題2.6對于兩個詞組成的查詢，其中一個詞(項)的倒排記錄表包含下面16個文檔ID：4,6

13、,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一個詞(項)對應(yīng)的倒排記錄表僅僅包含一個文檔ID：47請分別采用如卜兩種策略進(jìn)行倒排記錄表合并并計算所需要的比較次數(shù)，同時簡要地說明計算的正確性。a. 使用標(biāo)準(zhǔn)的倒排記錄表。比較：(4,47), (6,47), (10,47), (12,47), (14,47), (16,47), (18,47), (20,47), (22,47), (32,47), (47,47)。共比較11次。b, 使用倒排記錄表+跳表的方式，跳表指針設(shè)在PS處(P是列表長度)。P=16。也就說第一個列表的跳表指針往后跳4個元

14、素。卜圖藍(lán)色表示安裝了跳表指針的元素，其中120跳到180上。4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180比較：(4,47), (14,47), (22,47), (120,47), (32,47), (47,47)共比較 6 次。習(xí)題2.9下面給出的是一個位置索引的一部分，格式為：詞項：文檔1:(位置1,位置2,)；文檔2:(位置1,位置2,)；angels： 2： (36.174,252.651) ； 4： (12.22.102,432) ； 7： (17): fools：2： (1.17.74.222) ； 4： (8,78,108,

15、458) ； 7： (3,13,23,193)； fear：2： (87.704,722.901) ； 4： (13,43,113,433) ； 7： (18,328.528)； in：2： (3,37.76.444.851) ； 4： (10.20.110,470,500) ； 7： (5,15.25.195):rush：2： (2,66,194.321,702) ； 4： (9,69.149.429,569) ； 7： (4.14.404)； to：2：(47,86,234,999) ； 4： (14.24,774,944)； 7： (199,319,599,709)； tread：2：

16、(57,94,333) : 4： (15,35.155) ； 7： (20,320)；where：2： (67.124,393.1001) ； 4： (11,41.101,421.431) ； 7： (16.36,736)； 那么哪些文檔和以下的查詢匹配？其中引號內(nèi)的每個表達(dá)式都是一個短語查詢。a. “fools rush in"；文檔2、4、7ob. “ fools rush in " AND " angels fear to tread "<> 文檔4。補充習(xí)題1A詞鄰近AND合并算法 前提：考慮位置索引。要求查找這樣的文檔，它同時包含詞

17、A和詞B,旦兩詞文中的距離在k個詞以內(nèi)。給定兩個指針pl和P2,分別指向兩個詞A和B的兩倒排列表(鏈表實現(xiàn))的首元素: 令pi->doc表示pi所指向文檔對象的結(jié)構(gòu)體。對于一個文檔對象，該詞出現(xiàn)的各個位置的列表為posList。用ql(q2)表示詞A(詞B) 當(dāng)前指向文檔對象指向的posList指向的位置。用qi->pos表示該位置。查詢結(jié)果存放在answer列表里。算法：While pl != null AND p2 != nullIfpl->docld = p2->docld/對兩(剩余)列表的首元素進(jìn)行比較While ql != null AND q2 != nu

18、llIf ql->pos-q2->pos<=k OR q2->pos-ql->pos <= kinsert(answec pl);break;/跳出這個循環(huán)，找到一個k臨近即可Elself ql->pos - q2->pos> k q2不可能被匹配上，忽略它 q2= q2->next;/生成新的剩余列表Else If q2->pos -ql->pos > k ql不可能被匹配上，忽略它 q l=ql->next;/生成新的剩余列表End IfEnd Whilepl=pl->next; 構(gòu)造新的剩余列表，迭

19、代執(zhí)行p2=p2->next;Else if pl->docld < p2->docldpl=pl->next： /pl->docld不可能有匹配：構(gòu)造新的剩余列表Elsep2=p2->next： /p2->docld不可能有匹配：構(gòu)造新的剩余列表End第六章文檔評分、詞項權(quán)重計算及向量空間模型習(xí)題6.2上面的例6-1中，如果gl = 0.2z g2 = 0.31及g3 = 0.49,那么對于一個文檔來說所有可能的不同得分有多少？得分1： 0得分 2： gl=0.2得分 3： g2=0.31得分 4： g3=0.49得分 5： gl+g2=0.5

20、1得分 6： 81+83=0.69得分 7： g2+g3=0.8得分 8： gl+g2+g3=1.0習(xí)題6-10考慮圖69中的3篇文檔Docl、Doc2、Doc3中幾個詞項的tf情況，采用圖68中的idf 值來計算所有詞項car、auto、insurance及best的tfidf值（df值的計算就假設(shè)用Docl, Doc2 Doc3的這個文集Doc1Doc2Doc3car27424auro3330insurance03329best14017圖6.9習(xí)題6.10中所使用的If M解答:Wt 妒 max(l+logio(l+tf)，°)DoclDoc2Doc3Car2.43141.60

21、212.3802Auto1.47712.51850insurance02.51852.4624Best2.146102.2304dftidftcar30auto20.1761insurance20.1761best20.1761這里N=3otf-idfs=wt(d*idftDoclDoc2Doc3car000auto0.26010.44350insurance00.44350.4336best0.377900.3928例6-4假設(shè)文檔集中的文檔數(shù)目N=1000000»詞表為auto, best, car, insurance),這四個詞的df值 分別為 5000, 50000, 10

22、000,1000。設(shè)某文檔d的raw tf向量為1,0,1,2,對查詢q='best car insurance",問該文檔-查詢的相似度打分score(q,d)是？解答：dftidftauto50002.3010best5000013010car100002.0000insurance10003.0000這里 N=1000000o文檔d的tf-idf向M：raw tf”Wt,d=max( 1+logH 1+tf ),0)tf-idf妒 wjidftv(d)=歸一化 tf-idft,dauto11.00002.30100.4646best0000car11.00002.000

23、00.4038insurance21.30103.90310.7881查詢q的tf-idf向量（Wqd =1）raw tft>qwt/q=max(l+logio(l+tf)/0)tf-idft,q= Wt,q*idftv(q)=歸化 tf-idfx(dauto0000best111.30100.3394car112.00000.5218insurance113.00000.7827score(q,d) = v(q),*v(d)=0.8275第八章信息檢索的評價習(xí)題8-8考成一個有4篇相關(guān)文檔的信息需求，考察兩個系統(tǒng)的前10個檢索結(jié)果（左邊的結(jié)果排名靠前），相關(guān)性判定的情況如下所示：系統(tǒng)

24、1RNRNN NNNRR系統(tǒng) 2NRNNR RRNNNa. 計算兩個系統(tǒng)的MAP值并比較大小。b. 上述結(jié)果直觀上看有意義嗎？能否從中得出啟發(fā)如何才能獲得高的MAP得分？c. 計算兩個系統(tǒng)的R-precision值，并與a中按照MAP進(jìn)行排序的結(jié)果進(jìn)行對比。解答：a. 按MAP的定義，這里|Q|=L m=4。在查魂結(jié)果中遇到每個相關(guān)文檔對前面的所有文檔 計算一個Precision* MAP將這些Precision值求平均。MAP（系統(tǒng) 1）= （1/4）*（1+2/3+3/9+4/10） = 0.6MAP（系統(tǒng) 2）= （1/4）*（1/2+2/5+3/6+4/7）=0.49系統(tǒng)1的MAP值大

25、。b. 相關(guān)的查詢結(jié)果排名越靠前，則MAP越大。c. 按R-precision的定義，假設(shè)總共有|Rel|篇相關(guān)文檔，在查詢結(jié)果中取前|Rel|個文檔，計算其 precision 9R-precision（系統(tǒng) 1）=2/4=1/2R-precision（系統(tǒng) 1 ）=1/4系統(tǒng)1的R-precision值大。與MAP給出系統(tǒng)打分排序的結(jié)果一致。習(xí)題8-10下表中是兩個判定人員基于某個信息需求對12個文檔進(jìn)行相關(guān)性判定的結(jié)果（0=不相關(guān)，1=相關(guān)）。假定我們開發(fā)了一個IR系統(tǒng),針對該信息需求返回了文檔4, 5,6,7,8。docID判斷1判斷21002003 114 115 106 107 1

26、08 109 0110 0111 0112 01a. 計算兩個判斷之間的kappa統(tǒng)計量：b. 當(dāng)兩個判斷均認(rèn)為是相關(guān)文檔時才認(rèn)為該文檔相關(guān)，此時計算上述系統(tǒng)的正確率、召回 率及F值；c. 只要有一個判斷認(rèn)為是相關(guān)文檔則認(rèn)為該文檔相關(guān)，此時計算上述系統(tǒng)的正確率、召回 率及R值。解答：a. 計算kappa統(tǒng)計量：P(A)就是實際觀察到的一致意見的概率，總共12篇文檔，其中2篇兩人一致選Yes, 2 篇兩人一致選 N。因此,P(A) = (2+2)/12=l/3«P(E)是隨機情況卜.的一致意見的概率。假設(shè)每個人對每個文檔的Yes (或No)打分的概 率Py (或pn )是獨立同分布的(

27、i.i.d.),則P(E)= p/py+pn*pno其中，Py是2*12次打分中 為Yes的比例，py=12/24=l/2； p。是2*12次打分中為No的比例，pn=12/24=l/2.代入P(E), 得：P(E)=(l/2)A2+(l/2)A2=l/2oKappa=(P(A)-P(E)/(l-P(E)=(l/3-l/2)/(l-l/2)=-l/3<0.67,這是一個負(fù)數(shù)，說明實際的一致 性結(jié)果還不如隨機產(chǎn)生的一致性結(jié)果，因此可以判定兩人給出的相關(guān)性打分不一致。b. 文檔集中共有12篇文檔，其中2文檔相關(guān)(3, 4),其它10篇都不相關(guān)。查詢結(jié)果為4,5, 6,7,8,其中只有1篇文檔

28、相關(guān)(4)o該查詢的Precision, P=l/5；Recall R=l/2；F1=2P*R/(P+R)=0.28oc. 文檔集中共有12篇文檔，其中10文檔相關(guān)，其它2篇都不相關(guān)(1,2)。查詢結(jié)果為 4, 5, 6, 7, 8,全部都相關(guān)。該查訕的Precision, P=l：Recall, R=5/12；Fi=2P*R/(P+R)=0.67o注：因Kappa統(tǒng)計量認(rèn)為兩人打分不一致，所以修正方法b比較合理，而c非常不合理。第十三章文本分類與樸素貝葉斯方法習(xí)題13-3位置獨立性假設(shè)的基本原則是，詞項在文檔的位置k上出現(xiàn)這個事實并沒有什么有用的信息。 請給出這個假設(shè)的反例。提示：可以考慮那

29、些套用固定文檔結(jié)構(gòu)的文檔。解答：如果一個詞出現(xiàn)在不同域中，它的重要性不同。比如出現(xiàn)在標(biāo)題中的詞一般很重要。習(xí)題13-9基于表13-10中的數(shù)據(jù)，進(jìn)行如卜計算：(i) 估計多項式NB分類器的參數(shù)；(ii) 將(i)中的分類器應(yīng)用到測試集：表1310用于參數(shù)估計的數(shù)摳文檔ID文檔中的詞扈干oCMia類？訓(xùn)M1Taipci Taiwanyes2Macao Taiwan Shanghaives3Japan Sapporono4Sapporo Osaka Taiu anno測試集5Taiwan Taiwan SapporoP(China)=2/4=l/2; P(非 China)=2/4=l/2.詞典中有

30、 7 個詞 Japan, Macao, Osaka, Sapporo, Shanghai, Taipei, Taiwan.測試集中，China類共有5個詞：非China類共有5個詞。P(Taiwan | China 類)=(2 + 1)/(5 + 7)= 1/4 (加一平滑，下同)P(Taiwan| 非 China 類)=(1 + 1)/(5 + 7)= 1/6P(Sapporo| China 類)=(0 + 1)/(5 + 7)= 1/12P(Sapporo| 非 China 類)=(2 + 1)/(5 + 7)= 1/4按單字詞語言模型，PfChina 類 |d5) « PfChina 類)* P(Taiwan| China 類)八2* P(Sapporo| China 類)=1/2 * (1/4)A2 1/12=1/384.P(非 China 類 |d5) « P(非 China 類)* P(Taiwan| 非 China 類)入2* P(Sapporo| 非 China 類)=l/2*(l/6)人2*1/4=1/288.由于P(非China類血)> P(China類|d$), d5屬于非Chi