《信息檢索導論》課后習題答案

1、信息組織與檢索作業(yè)答案第一章 布爾檢索習題 1-2考慮如下幾篇文檔：文檔1breakthrough drug for schizophrenia文檔2new schizophrenia drug文檔3new approach for treatment of schizophrenia文檔4new hopes for schizophrenia patientsa. 畫出文檔集對應的詞項文檔矩陣；b. 畫出該文檔集的倒排索引（參考圖 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 ）和每個詞項的倒排列表（

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

4、 nullIf p1 ->docId=p2->docId /對兩(剩余)列表的首元素進行比較insert(answer, p1) ；p1=p1 ->next ； / 構造新的剩余列表，迭代執(zhí)行p2=p2 ->next ； /Else if p1 ->docId < p2->docIdp1=p1 ->next ； /p1 ->docId 不可能有匹配；構造新的剩余列表Elsep2=p2 ->next ； /p2 ->docId 不可能有匹配；構造新的剩余列表End面向對象風格的偽代碼：注：為一個數(shù)據(jù)結構(對象)定義方法，通過方法操

5、作自己的內部數(shù)據(jù)( List 對象里隱含包含了一個成員變量，它是真正的鏈表或變長數(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習題 1-10寫出OR 查詢的偽代碼面向過程風格的偽代碼：給定兩個指針pl和p2,分別指向兩倒排列表listl和list2(鏈表實現(xiàn))的首元素；令docld(pl) 表示pl所指向的元素的docId;查詢結果存放在 answer列表里。While p1 != null AND p2 != nullIf p1 ->docId = p2->docIdinsert(answer, p1) ；p1=p1 ->next ；p2=p2->next；/

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

8、ist1 已遍歷到結尾)insert(answer, p2) ；p2=p1 ->next ；END面向對象風格的偽代碼：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補充習題2若一個文集有1000篇文檔，有40篇是關于信管專業(yè)建設的。我的信息需求是了解信管專業(yè)的專業(yè)建設情況，用某搜索引擎在這個文集上搜索，查詢詞為“信管”，搜出100篇包含“信管”的文檔，這其中有20篇是信管專業(yè)建設方面的，其它80篇是關于信管的其它情況。請問該查詢的正確率和召回率是多少 正確率=20/100=0.2召回率=20/40=0.5第二章詞項詞典及倒排記錄表習題2-1a.在布爾檢索系統(tǒng)中，進行詞干還原從不降低正確率。錯；相當于擴充出同一個詞干表示的多個詞，會降低正確率。b.在布爾檢索系統(tǒng)中，進行詞干還原從不降低召回率。對

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

12、出同樣的結果？為什么？a. abandon/abandonmentb. absorbency/absorbentc. marketing/marketsd. university/universee. volume/volumes按Porter詞干還原算法，這幾組詞都可以被還原為相應的詞干。但是這里問的是哪些組做詞干還原不合適，原因是某組的兩個詞雖然來源于同一個詞干，但是它們的意思不同，如果做詞干還原處理會降低正確率。c組不做詞干還原。marketing表示營銷，market表示市場。d組不做詞干還原。university 表示大學， universe表示宇宙。習題2-6對于兩個詞組成的查詢，

13、其中一個詞(項)的倒排記錄表包含下面16個文檔ID:4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一個詞(項)對應的倒排記錄表僅僅包含一個文檔ID:47請分別采用如下兩種策略進行倒排記錄表合并并計算所需要的比較次數(shù)，同時簡要地說明計算的正確性。a.使用標準的倒排記錄表。比較：(4,47), (6,47), (10,47), (12,47), (14,47), (16,47), (18,47), (20,47), (22,47), (32,47), (47,47)。共比較11次。b.使用倒排記錄表+跳表的方式，跳表指針設在P1/2處(P是列

14、表長度)。P=16。也就說第一個列表的跳表指針往后跳4個元素。下圖藍色表示安裝了跳表指針的元素，其中 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 次。習題2-9下面給出的是一個位置索引的一部分，格式為：詞項：文檔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 );那么哪些文檔和以下的查詢匹配？其中引號內的每個表達式都是一個短語查詢。a. ”fools rush in "文檔2、4、7。b. ”fools rush in " AND " angels fear to tread ”。文檔4。補充習題1k詞鄰近AND合并算法前提：考慮位置索引。要求查

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

18、 null AND q2 != nullIf q1->pos - q-2>pos<=k OR q2->pos - q1pos <= kinsert(answer, p1);break; /跳出這個循環(huán)，找到一個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、構造新的剩余列表，迭代執(zhí)行p2=p2->next;Else if pl ->docId < p2->docIdp1=p1->next； /p1->docId不可能有匹配；構造新的剩余列表Elsep2=p2->next; /p2->docId不可能有匹配；構造新的剩余列表End第六章 文檔評分、詞項權重計算及向量空間模型習題6-2上面的例6-1中，如果g1 = 0.2, g2 = 0.31及g3 = 0.49,那么對于一個文檔來說所有可能的不同得分有多少？得分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習題6-10考慮圖6-9中的3篇文檔Doc1、Doc2、Doc3中幾個詞項的tf情況，采用圖6-8中的idf 值來計算所有詞項car、auto、insurance及best的tf-idf值（這里改為df值的計算就假設用Doc1, Doc2 Doc3的這個文集）。Doc1Doc3(At274Ua hi33ftiihurance03419hwMII17圖6-9月購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ù)目N=1000000 ,詞表為auto, best, car, insurance,這四個詞的df值分別為 5000, 5000

22、0, 10000, 1000。設某文檔d的raw tf向量為1,0,1,2,對查詢q=" bestcar insurance '；問該文檔-查詢的相似 度打分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查詢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第八章信息檢索的評價習題8-8考慮一個有4篇相關文檔的信息需求，考察兩個系統(tǒng)的前 10個檢索結果（左邊的結果排名 靠

24、前），相關性判定的情況如下所示：系統(tǒng) 1R N R N N N N N R R系統(tǒng) 2N R N N R R R N N Na.計算兩個系統(tǒng)的MAP值并比較大小。b.上述結果直觀上看有意義嗎？能否從中得出啟發(fā)如何才能獲得高的 MAP得分？c.計算兩個系統(tǒng)的 R-precision值，并與a中按照MAP進行排序的結果進行對比。解答：a.按MAP的定義，這里|Q|=1 , m=4。在查詢結果中遇到每個相關文檔對前面的所有文檔計算一個 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.相關的查詢結果排名越靠前，則 MAP越大。c.按R-precision的定義，假設總共有|Rel|篇相關文檔，在查詢結果中取前 |Rel|個文檔, 計算其 precision 0Rprecision（系統(tǒng) 1）=2/4=1/2Rprecision（系統(tǒng) 1）=1/4系統(tǒng)1的R-precision值大。與MAP給出系統(tǒng)打分排序的結果一致。習題8-10下表中是兩個判定人員基于某個信息需求對 12個文檔進行相關性判定的結果（0=不 相關，1=相關）。假定我們開發(fā)了一個IR系統(tǒng)，針對該信息需求返回了文檔 4, 5, 6, 7

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

27、。假設每個人對每個文檔的Yes(或No)打分的概率Py (或pn )是獨立同分布的(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 ，這是一個負數(shù)，說明實際的一致 性結果還不如隨機產(chǎn)生的一致性結果，因此可以判定兩人給出的相關性打分不一致。b. 文檔集中共有12

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

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

30、in Seppo fa7P(China)=2/4=1/2; P(4£ China)=2/4=1/2.詞典中有 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按單字詞語言模型，P(China 類 |d 5)0c P(China 類)* P(Taiwan|China 類)A2*P(Sapporo|China類)=1/2*(1/442*1/12=1/384.P(非 China 類 |d 5) 8P(非 China 類)* P(Taiwan| 非 China 類)A2* P(Sapporo| 非 China 類)=1/2*(1/6)人2*1/4=1/288.由于 P(非 China 類|d 5)> P(China類|d 5), d5屬于非 China 類。第