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

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

2、0drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010Inverted 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->4treatment >3注意：倒排索引中的詞表

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

4、 AND p2 != 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)造新的剩余列表Endl 面向?qū)ο箫L(fēng)格的偽代碼：注：為一個(gè)數(shù)據(jù)結(jié)構(gòu)（對(duì)象）定義方法，通過方法操作自己的內(nèi)部

5、數(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.currentItem

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

7、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í)list1已遍歷到結(jié)尾）insert(answer, p2)；p

8、2=p1->next；ENDl 面向?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().getDocId() < list2.currentItem().get

9、DocId()answer.insert(list1.currentItem();list1.moveToNext();Elseanswer.insert(list2.currentItem();list2.moveToNext();EndWhile list1.currentItem() != null answer.insert(list1.currentItem();list1.moveToNext();ENDWhile list2.currentItem() != null answer.insert(list2.currentItem();list2.moveToNext();END

10、補(bǔ)充習(xí)題2若一個(gè)文集有1000篇文檔，有40篇是關(guān)于信管專業(yè)建設(shè)的。我的信息需求是了解信管專業(yè)的專業(yè)建設(shè)情況，用某搜索引擎在這個(gè)文集上搜索，查詢?cè)~為“信管”，搜出100篇包含“信管”的文檔，這其中有20篇是信管專業(yè)建設(shè)方面的，其它80篇是關(guān)于信管的其它情況。請(qǐng)問該查詢的正確率和召回率是多少正確率=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ì)。c. 詞干還原會(huì)增加詞項(xiàng)詞典的大小。錯(cuò)。d. 詞干還原應(yīng)

11、該在構(gòu)建索引時(shí)調(diào)用，而不應(yīng)在查詢處理時(shí)調(diào)用。錯(cuò)；應(yīng)同時(shí)做才能保證索引中和查詢?cè)~的匹配。習(xí)題2-2請(qǐng)給出如下單詞的歸一化形式（歸一化形式也可以是詞本身）。a. Cos -> cosb. Shiite -> shiite（'是隔音號(hào)）c. contd ->contd（contd. 可表示contained 包括；continued 繼續(xù)）d. Hawaii ->hawaiie. ORourke ->orourke習(xí)題2-3如下詞經(jīng)過Porter詞干還原工具處理后會(huì)輸出同樣的結(jié)果，你認(rèn)為哪對(duì)（幾對(duì)）詞不應(yīng)該輸出同樣的結(jié)果？為什么？a. abandon/aband

12、onment b. absorbency/absorbent c. marketing/markets d. university/universe e. volume/volumes按Porter詞干還原算法，這幾組詞都可以被還原為相應(yīng)的詞干。但是這里問的是哪些組做詞干還原不合適，原因是某組的兩個(gè)詞雖然來源于同一個(gè)詞干，但是它們的意思不同，如果做詞干還原處理會(huì)降低正確率。c組不做詞干還原。marketing表示營(yíng)銷，market表示市場(chǎng)。d組不做詞干還原。university表示大學(xué)，universe表示宇宙。習(xí)題2-6對(duì)于兩個(gè)詞組成的查詢，其中一個(gè)詞（項(xiàng)）的倒排記錄表包含下面16個(gè)文檔 I

13、D：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)要地說明計(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是列表長(zhǎng)度）。P=16。也就說第一個(gè)列表的跳

14、表指針往后跳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: （1,17,74,222

15、）; 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）; 7: （199,319,599,709）; tr

16、ead: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）; 那么哪些文檔和以下的查詢匹配？其中引號(hào)內(nèi)的每個(gè)表達(dá)式都是一個(gè)短語(yǔ)查詢。a. “fools rush in”；文檔2、4、7。b. “fools rush in” AND “angels fear to tread”。文檔4。補(bǔ)充習(xí)題1k詞鄰近AND合并算法前提：考慮位置索引。要求查找這樣的文檔，它同時(shí)包含詞A和詞B，且兩詞文中的距離在k個(gè)詞以內(nèi)。給定兩個(gè)指針p1和

17、p2，分別指向兩個(gè)詞A和B的兩倒排列表（鏈表實(shí)現(xiàn)）的首元素；令pi->doc表示pi所指向文檔對(duì)象的結(jié)構(gòu)體。對(duì)于一個(gè)文檔對(duì)象，該詞出現(xiàn)的各個(gè)位置的列表為posList。用q1（q2）表示詞A（詞B）當(dāng)前指向文檔對(duì)象指向的posList指向的位置。用qi->pos表示該位置。查詢結(jié)果存放在answer列表里。算法：While p1 != null AND p2 != nullIf p1->docId = p2->docId /對(duì)兩（剩余）列表的首元素進(jìn)行比較While q1 != null AND q2 != nullIf q1->posq2->pos<

18、=k OR q2->pos q1->pos <= kinsert(answer, p1);break; /跳出這個(gè)循環(huán)，找到一個(gè)k臨近即可ElseIf q1->pos q2->pos> k /q2不可能被匹配上，忽略它q2= q2->next;/生成新的剩余列表Else If q2->pos q1->pos > k /q1不可能被匹配上，忽略它q1=q1->next;/生成新的剩余列表End IfEnd Whilep1=p1->next; /構(gòu)造新的剩余列表，迭代執(zhí)行p2=p2->next;Else if p1-&g

19、t;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è)文檔來說所有可能的不同得分有多少？得分1: 0得分2：g1=0.2得分3：g2=0.31得分4：g3=0.49得分5：g1+g2=0.51得分6：g1+g3=0.69得分7：g2+g3=0.8得分8：g1+g

20、2+g3=1.0習(xí)題 6-10考慮圖6-9中的3篇文檔Doc1、Doc2、Doc3中幾個(gè)詞項(xiàng)的tf情況，采用圖6-8中的idf值來計(jì)算所有詞項(xiàng)car、auto、insurance及best的tf-idf值（這里改為df值的計(jì)算就假設(shè)用Doc1, Doc2 Doc3的這個(gè)文集）。解答：wt,d=max(1+log10(1+tf),0)Doc1Doc2Doc3Car2.43141.60212.3802Auto1.47712.51850insurance02.51852.4624Best2.146102.2304 dftidftcar30auto20.1761insurance20.1761best

21、20.1761這里N=3。tf-idft,d= wt,d*idftDoc1Doc2Doc3car000auto0.26010.44350insurance00.44350.4336best0.377900.3928例6-4假設(shè)文檔集中的文檔數(shù)目N=，詞表為auto, best, car, insurance ，這四個(gè)詞的df值分別為5000, 50000, 10000, 1000。設(shè)某文檔d的raw tf向量為1,0,1,2，對(duì)查詢q=”best car insurance”，問該文檔-查詢的相似度打分score(q,d)是？ 解答：dftidftauto50002.3010best50000

22、1.3010car100002.0000insurance10003.0000這里N=。文檔d的tf-idf向量：raw tft,dwt,d=max(1+log10(1+tf),0)tf-idft,d= wt,d*idftv(d)=歸一化tf-idft,dauto11.00002.30100.4646best0000car11.00002.00000.4038insurance21.30103.90310.7881查詢q的tf-idf向量（wt,d =1）raw tft,qwt,q=max(1+log10(1+tf),0)tf-idft,q= wt,q*idftv(q)=歸一化tf-idft,

23、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é)果排名靠前），相關(guān)性判定的情況如下所示： 系統(tǒng)1 R N R N N N N N R R 系統(tǒng)2 N R N N R R R N N N a. 計(jì)算兩個(gè)系統(tǒng)的MAP值并比較大小。 b. 上述結(jié)果直觀上看有意義嗎？能否從中得出啟發(fā)如何才能獲得高的MAP得分？ c. 計(jì)算兩個(gè)系統(tǒng)的R-precision

24、值，并與a中按照MAP進(jìn)行排序的結(jié)果進(jìn)行對(duì)比。解答：a. 按MAP的定義，這里|Q|=1，m=4。在查詢結(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/4)*(1/2+2/5+3/6+4/7)=0.49系統(tǒng)1的MAP值大。b. 相關(guān)的查詢結(jié)果排名越靠前，則MAP越大。c. 按R-precision的定義，假設(shè)總共有|Rel|篇相關(guān)文檔，在查詢結(jié)果中取前|Rel|個(gè)文檔，計(jì)算其precision。R-precision(系統(tǒng)1)=2/4=

25、1/2R-precision(系統(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)）。假定我們開發(fā)了一個(gè)IR系統(tǒng)，針對(duì)該信息需求返回了文檔4, 5, 6, 7, 8。 docID 判斷1 判斷2 1 0 0 2 0 0 3 1 1 4 1 1 5 1 0 6 1 0 7 1 0 8 1 0 9 0 1 10 0 1 11 0 1 12 0 1 a. 計(jì)算兩個(gè)判斷之間的kappa統(tǒng)計(jì)量； b. 當(dāng)兩個(gè)判斷均認(rèn)為是相關(guān)文檔時(shí)才認(rèn)為該文檔相關(guān)，此時(shí)計(jì)算上述系統(tǒng)的

26、正確率、召回率及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í)際觀察到的一致意見的概率，總共12篇文檔，其中2篇兩人一致選Yes，2篇兩人一致選No。因此，P(A)=(2+2)/12=1/3。P(E)是隨機(jī)情況下的一致意見的概率。假設(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/2

27、4=1/2。代入P(E)，得：P(E)=(1/2)2+(1/2)2=1/2。Kappa=(P(A)-P(E)/(1-P(E)=(1/3-1/2)/(1-1/2)=-1/3<0.67，這是一個(gè)負(fù)數(shù)，說明實(shí)際的一致性結(jié)果還不如隨機(jī)產(chǎn)生的一致性結(jié)果，因此可以判定兩人給出的相關(guān)性打分不一致。b. 文檔集中共有12篇文檔，其中2文檔相關(guān)（3,4），其它10篇都不相關(guān)。查詢結(jié)果為4, 5, 6, 7, 8，其中只有1篇文檔相關(guān)（4）。該查詢的Precision, P=1/5；Recall, R=1/2；F1=2P*R/(P+R)=0.28。c. 文檔集中共有12篇文檔，其中10文檔相關(guān)，其它2篇都不

28、相關(guān)（1,2）。查詢結(jié)果為4, 5, 6, 7, 8，全部都相關(guān)。該查詢的Precision, P=1；Recall, R=5/12；F1=2P*R/(P+R)=0.67。注：因Kappa統(tǒng)計(jì)量認(rèn)為兩人打分不一致，所以修正方法b比較合理，而c非常不合理。第十三章 文本分類與樸素貝葉斯方法習(xí)題 13-3位置獨(dú)立性假設(shè)的基本原則是，詞項(xiàng)在文檔的位置k上出現(xiàn)這個(gè)事實(shí)并沒有什么有用的信息。請(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)

29、式NB分類器的參數(shù)； (ii) 將(i)中的分類器應(yīng)用到測(cè)試集；P(China)=2/4=1/2; P(非China)=2/4=1/2.詞典中有7個(gè)詞Japan, Macao, Osaka, Sapporo, Shanghai, Taipei, Taiwan.測(cè)試集中，China類共有5個(gè)詞；非China類共有5個(gè)詞。P(Taiwan|China類)=(2 + 1)/(5 + 7)= 1/4 （加一平滑，下同）P(Taiwan|非China類) =(1 + 1)/(5 + 7)= 1/6 P(Sapporo|China類)= (0 + 1)/(5 + 7)= 1/12P(Sapporo|非China類)= (2 + 1)/(5 + 7)= 1/4按單字詞語(yǔ)言模型，P(China類|d5) P(China類)* P(Taiwan|China類)2* P(Sapporo|China類)=1/2*(1/4)2*1/12=1/384.P(非China類|d5) P(非China類)* P(