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

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

2、es0001new0111of0010patients0001schizophrenia1111treatment0010Inverted Index:approach -> 3 breakthrough ->1 drug ->1->2for ->1->3->4hopes ->4new ->2->3->4of ->3patients ->4schizophrenia ->1->2->3->4 treatment >3注意：倒排索引中的詞表（dictionary ）和每個(gè)詞項(xiàng)的倒排列表（

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

4、 nullIf p1 ->docId=p2->docId /對(duì)兩(剩余)列表的首元素進(jìn)行比較insert(answer, p1) ；p1=p1 ->next ； / 構(gòu)造新的剩余列表，迭代執(zhí)行p2=p2 ->next ； /Else if p1 ->docId < p2->docIdp1=p1 ->next ； /p1 ->docId 不可能有匹配；構(gòu)造新的剩余列表Elsep2=p2 ->next ； /p2 ->docId 不可能有匹配；構(gòu)造新的剩余列表End面向?qū)ο箫L(fēng)格的偽代碼：注：為一個(gè)數(shù)據(jù)結(jié)構(gòu)(對(duì)象)定義方法，通過(guò)方法操

5、作自己的內(nèi)部數(shù)據(jù)( List 對(duì)象里隱含包含了一個(gè)成員變量，它是真正的鏈表或變長(zhǎng)數(shù)組) 。While list1.currentItem() != null AND list2.currentItem() != nullIf list1.currentItem().getDocId() = list2.currentItem().getDocId()answer.insert(list1.currentItem();list1.moveToNext();list2.moveToNext();Else if list1.currentItem().getDocId() < list2.cu

6、rrentItem().getDocId()list1.moveToNext();Elselist2.moveToNext();End習(xí)題 1-10寫(xiě)出OR 查詢(xún)的偽代碼面向過(guò)程風(fēng)格的偽代碼：給定兩個(gè)指針pl和p2,分別指向兩倒排列表listl和list2(鏈表實(shí)現(xiàn))的首元素；令docld(pl) 表示pl所指向的元素的docId;查詢(xún)結(jié)果存放在 answer列表里。While p1 != null AND p2 != nullIf p1 ->docId = p2->docIdinsert(answer, p1) ；p1=p1 ->next ；p2=p2->next；/

7、 構(gòu)造新的剩余列表，迭代執(zhí)行Else if p1 ->docId < p2->docIdinsert(answer, p1) ；p1=p1 ->next ； / 構(gòu)造新的剩余列表，迭代執(zhí)行Elseinsert(answer, p2) ；p2=p2->next； / 構(gòu)造新的剩余列表，迭代執(zhí)行EndWhile p1 != null/ 條件為真時(shí)，加入 list1 的剩余元素(此時(shí)list2 已遍歷到結(jié)尾)insert(answer, p1) ；p1=p1 ->next ；ENDWhile p2 != null/ 條件為真時(shí)，加入 list2 的剩余元素(此時(shí)l

8、ist1 已遍歷到結(jié)尾)insert(answer, p2) ；p2=p1 ->next ；END面向?qū)ο箫L(fēng)格的偽代碼：While list1.currentItem() != null AND list2.currentItem() != nullIf list1.currentItem().getDocId() = list2.currentItem().getDocId()answer.insert(list1.currentItem();list1.moveToNext();list2.moveToNext();Else if list1.currentItem().getDoc

9、Id() < list2.currentItem().getDocId()answer.insert(list1.currentItem();list1.moveToNext();Elseanswer.insert(list2.currentItem();list2.moveToNext();EndWhile list1.currentItem() != nullanswer.insert(list1.currentItem();list1.moveToNext();ENDWhile list2.currentItem() != nullanswer.insert(list2.curre

10、ntItem();list2.moveToNext();END補(bǔ)充習(xí)題2若一個(gè)文集有1000篇文檔，有40篇是關(guān)于信管專(zhuān)業(yè)建設(shè)的。我的信息需求是了解信管專(zhuān)業(yè)的專(zhuān)業(yè)建設(shè)情況，用某搜索引擎在這個(gè)文集上搜索，查詢(xún)?cè)~為“信管”，搜出100篇包含“信管”的文檔，這其中有20篇是信管專(zhuān)業(yè)建設(shè)方面的，其它80篇是關(guān)于信管的其它情況。請(qǐng)問(wèn)該查詢(xún)的正確率和召回率是多少 正確率=20/100=0.2召回率=20/40=0.5第二章詞項(xiàng)詞典及倒排記錄表習(xí)題2-1a.在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低正確率。錯(cuò)；相當(dāng)于擴(kuò)充出同一個(gè)詞干表示的多個(gè)詞，會(huì)降低正確率。b.在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低召回率。對(duì)

11、。c.詞干還原會(huì)增加詞項(xiàng)詞典的大小。錯(cuò)。d.詞干還原應(yīng)該在構(gòu)建索引時(shí)調(diào)用，而不應(yīng)在查詢(xún)處理時(shí)調(diào)用。錯(cuò)；應(yīng)同時(shí)做才能保證索引中和查詢(xún)?cè)~的匹配。習(xí)題2-2請(qǐng)給出如下單詞的歸一化形式(歸一化形式也可以是詞本身)。a. ' Coscosb. Shi '-Mshiite ('是隔音號(hào))c. cont ->aOntd (contd.可表示 contained 包括；continued 繼續(xù))d. Hawai ->hiawaiie. O ' Rourkeorourke習(xí)題2-3如下詞經(jīng)過(guò)Porter詞干還原工具處理后會(huì)輸出同樣的結(jié)果，你認(rèn)為哪對(duì)(幾對(duì))詞不應(yīng) 逡輸

12、出同樣的結(jié)果？為什么？a. abandon/abandonmentb. absorbency/absorbentc. marketing/marketsd. university/universee. volume/volumes按Porter詞干還原算法，這幾組詞都可以被還原為相應(yīng)的詞干。但是這里問(wèn)的是哪些組做詞干還原不合適，原因是某組的兩個(gè)詞雖然來(lái)源于同一個(gè)詞干，但是它們的意思不同，如果做詞干還原處理會(huì)降低正確率。c組不做詞干還原。marketing表示營(yíng)銷(xiāo)，market表示市場(chǎng)。d組不做詞干還原。university 表示大學(xué)， universe表示宇宙。習(xí)題2-6對(duì)于兩個(gè)詞組成的查詢(xún)，

13、其中一個(gè)詞(項(xiàng))的倒排記錄表包含下面16個(gè)文檔ID:4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一個(gè)詞(項(xiàng))對(duì)應(yīng)的倒排記錄表僅僅包含一個(gè)文檔ID:47請(qǐng)分別采用如下兩種策略進(jìn)行倒排記錄表合并并計(jì)算所需要的比較次數(shù)，同時(shí)簡(jiǎn)要地說(shuō)明計(jì)算的正確性。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è)在P1/2處(P是列

14、表長(zhǎng)度)。P=16。也就說(shuō)第一個(gè)列表的跳表指針往后跳4個(gè)元素。下圖藍(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下面給出的是一個(gè)位置索引的一部分，格式為：詞項(xiàng)：文檔1:(位置1,位置2,);文檔2:(位置1,位置2,);angels : 2:(36,174,252,651) ; 4:(12,22,102,432 ) ; 7:(17);fools: 2:

15、(1,17,74,222 ) ; 4:(8,78,108,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 ) ;

16、7:(199,319,599,709);tread :2:(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 );那么哪些文檔和以下的查詢(xún)匹配？其中引號(hào)內(nèi)的每個(gè)表達(dá)式都是一個(gè)短語(yǔ)查詢(xún)。a. ”fools rush in "文檔2、4、7。b. ”fools rush in " AND " angels fear to tread ”。文檔4。補(bǔ)充習(xí)題1k詞鄰近AND合并算法前提：考慮位置索引。要求查

17、找這樣的文檔，它同時(shí)包含詞A和詞B,且兩詞文中的距離在k個(gè)詞以?xún)?nèi)。給定兩個(gè)指針p1和p2,分別指向兩個(gè)詞 A和B的兩倒排列表(鏈表實(shí)現(xiàn))的首元素； 令pi->doc表示pi所指向文檔對(duì)象的結(jié)構(gòu)體。對(duì)于一個(gè)文檔對(duì)象，該詞出現(xiàn)的各個(gè)位置的列表為posList。用q1 (q2)表示詞A(tB)當(dāng)前指向文檔對(duì)象指向的posList指向的位置。用qi->pos表示該位置。查詢(xún)結(jié)果存放在 answer列表里。算法：While p1 != null AND p2 != nullIf p1 ->docId = p2->docId /對(duì)兩(剩余)列表的首元素進(jìn)行比較While q1 !=

18、 null AND q2 != nullIf q1->pos - q-2>pos<=k OR q2->pos - q1pos <= kinsert(answer, p1);break; /跳出這個(gè)循環(huán)，找到一個(gè)k臨近即可Elself q1->pos - q2pos> k /q2不可能被匹配上，忽略它 q2= q2->next;/生成新的剩余列表Else If q2->pos - qlpos > k /q1不可能被匹配上，忽略它 q1=q1->next;生成新的剩余列表End IfEnd Whilep1=p1->next;

19、構(gòu)造新的剩余列表，迭代執(zhí)行p2=p2->next;Else if pl ->docId < p2->docIdp1=p1->next； /p1->docId不可能有匹配；構(gòu)造新的剩余列表Elsep2=p2->next; /p2->docId不可能有匹配；構(gòu)造新的剩余列表End第六章 文檔評(píng)分、詞項(xiàng)權(quán)重計(jì)算及向量空間模型習(xí)題6-2上面的例6-1中，如果g1 = 0.2, g2 = 0.31及g3 = 0.49,那么對(duì)于一個(gè)文檔來(lái)說(shuō)所有可能的不同得分有多少？得分1: 0得分 2: g1=0.2得分 3: g2=0.31得分 4: g3=0.49得分

20、5: g1+g2=0.51得分 6: g1+g3=0.69得分 7: g2+g3=0.8得分 8: g1+g2+g3=1.0習(xí)題6-10考慮圖6-9中的3篇文檔Doc1、Doc2、Doc3中幾個(gè)詞項(xiàng)的tf情況，采用圖6-8中的idf 值來(lái)計(jì)算所有詞項(xiàng)car、auto、insurance及best的tf-idf值（這里改為df值的計(jì)算就假設(shè)用Doc1, Doc2 Doc3的這個(gè)文集）。Doc1Doc3(At274Ua hi33ftiihurance03419hwMII17圖6-9月購(gòu)6。中所使.用的tf值解答:wt,d=max(1+log10(1+tf),0)Doc1Doc2Doc3Car2.4

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

22、0, 10000, 1000。設(shè)某文檔d的raw tf向量為1,0,1,2,對(duì)查詢(xún)q=" bestcar insurance '；問(wèn)該文檔-查詢(xún)的相似 度打分score(q,d)是？解答:dftidftauto50002.3010best500001.3010car100002.0000insurance10003.0000這里 N=1000000。文檔d的tf-idf向量:raw tf t,dwt,d=max(1+log10(1+tf),0)tf-idft,d= wt,d*idftv(d)=歸一化 tf-idft,dauto11.00002.30100.4646best00

23、00car11.00002.00000.4038insurance21.30103.90310.7881查詢(xún)q的tf-idf向量(wt,d =1)raw tf t,qwt,q=max(1+log10(1+tf),0)tf-idft,q= wt,q*idftv(q)=歸一化 tf-idft,dauto0000best111.30100.3394car112.00000.5218insurance113.00000.7827score(q,d) = v(q) *v(d)=0.8275第八章信息檢索的評(píng)價(jià)習(xí)題8-8考慮一個(gè)有4篇相關(guān)文檔的信息需求，考察兩個(gè)系統(tǒng)的前 10個(gè)檢索結(jié)果（左邊的結(jié)果排名 靠

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

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

26、, 8。docID判斷1判斷21 002 003 114 115 106 107 108 109 0110 0111 0112 01a. 計(jì)算兩個(gè)判斷之間的 kappa 統(tǒng)計(jì)量；b. 當(dāng)兩個(gè)判斷均認(rèn)為是相關(guān)文檔時(shí)才認(rèn)為該文檔相關(guān)，此時(shí)計(jì)算上述系統(tǒng)的正確率、召回率及F1 值；c. 只要有一個(gè)判斷認(rèn)為是相關(guān)文檔則認(rèn)為該文檔相關(guān)，此時(shí)計(jì)算上述系統(tǒng)的正確率、召回 率及F1 值。解答：a. 計(jì)算 kappa 統(tǒng)計(jì)量：P(A) 就是實(shí)際觀察到的一致意見(jiàn)的概率，總共12 篇文檔，其中 2 篇兩人一致選Yes， 2篇兩人一致選 No。因此，P(A)=(2+2)/12=1/3。P(E尾隨機(jī)情況下的一致意見(jiàn)的概率

27、。假設(shè)每個(gè)人對(duì)每個(gè)文檔的Yes(或No)打分的概率Py (或pn )是獨(dú)立同分布的(i. i. d.),則P(E尸py*py + pn*pn。其中，py是2*12次打分中 為Yes的比例，py=12/24=1/2 ; pn是2*12次打分中為 No的比例，pn=12/24=1/2。代入P(E), 得：P(E)=(1/2)A2+(1/2)A2=1/2 。Kappa=(P(A)-P(E)/(1-P(E)=(1/3-1/2)/(1 -1/2)= -1/3<0.67 ，這是一個(gè)負(fù)數(shù)，說(shuō)明實(shí)際的一致 性結(jié)果還不如隨機(jī)產(chǎn)生的一致性結(jié)果，因此可以判定兩人給出的相關(guān)性打分不一致。b. 文檔集中共有12

28、篇文檔，其中 2 文檔相關(guān)( 3,4 ) ，其它 10篇都不相關(guān)。查詢(xún)結(jié)果為4, 5, 6, 7, 8，其中只有1 篇文檔相關(guān)(4) 。該查詢(xún)的Precision, P=1/5 ；Recall, R=1/2；F1=2P*R/(P+R)=0.28。c. 文檔集中共有12 篇文檔，其中 10 文檔相關(guān)，其它 2 篇都不相關(guān)( 1,2 ) 。查詢(xún)結(jié)果為4, 5, 6, 7, 8，全部都相關(guān)。該查詢(xún)的Precision, P=1；Recall, R=5/12；F1=2P*R/(P+R)=0.67。注：因Kappa統(tǒng)計(jì)量認(rèn)為兩人打分不一致， 所以修正方法b比較合理，而c非常不合理。第十三章文本分類(lèi)與樸素

29、貝葉斯方法習(xí)題13-3位置獨(dú)立性假設(shè)的基本原則是，詞項(xiàng)在文檔的位置 k上出現(xiàn)這個(gè)事實(shí)并沒(méi)有什么有用的信息。請(qǐng)給出這個(gè)假設(shè)的反例。提示：可以考慮那些套用固定文檔結(jié)構(gòu)的文檔。解答：如果一個(gè)詞出現(xiàn)在不同域中，它的重要性不同。比如出現(xiàn)在標(biāo)題中的詞一般很重要。習(xí)題13-9基于表13-10中的數(shù)據(jù)，進(jìn)行如下計(jì)算：(i)估計(jì)多項(xiàng)式NB分類(lèi)器的參數(shù)；(ii)將(i)中的分類(lèi)器應(yīng)用到測(cè)試集；13-10用于手?jǐn)?shù)抬汁的身提文檔舊文檔中的同屬于丹槃？訓(xùn)距案LTajpci Teliiui卜4一 *Macao Taiwan Shanghai四3ASjpporu （Xiskg Ti 晴曲）測(cè)試集5Taiwajt Tai w

30、in Seppo fa7P(China)=2/4=1/2; P(4£ China)=2/4=1/2.詞典中有 7 個(gè)詞 Japan, Macao, Osaka, Sapporo, Shanghai, Taipei, Taiwan.測(cè)試集中，China類(lèi)共有5個(gè)詞；非China類(lèi)共有5個(gè)詞。P(Taiwan|China 類(lèi))=(2 + 1)/(5 + 7)= 1/4(加一平滑,下同)P(Taiwan|非 China 類(lèi))=(1 + 1)/(5 + 7)= 1/6P(Sapporo|China 類(lèi)尸(0 + 1)/(5 + 7)= 1/12P(Sapporo| 非 China 類(lèi)尸(2 + 1)/(5 + 7)= 1/4按單字詞語(yǔ)言模型，P(China 類(lèi) |d 5)0c P(China 類(lèi))* P(Taiwan|China 類(lèi))A2*P(Sapporo|China類(lèi))=1/2*(1/442*1/12=1/384.P(非 China 類(lèi) |d 5) 8P(非 China 類(lèi))* P(Taiwan| 非 China 類(lèi))A2* P(Sapporo| 非 China 類(lèi))=1/2*(1/6)人2*1/4=1/288.由于 P(非 China 類(lèi)|d 5)> P(China類(lèi)|d 5), d5屬于非 China 類(lèi)。第