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

1、信息組織與檢索作業(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. 畫出文檔集對應(yīng)的詞項文檔矩陣；b. 畫出該文檔集的倒排索引（參考圖 1-3中的例子）。Term-Documentmatrix:1234approach0010breakthrough1000drug1100for1

2、011hopes0001new0111of0010patients0001schizophrenia1111treatment0010Inverted 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注意：倒排索引中的詞表（dictionary）和

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

4、llIf p1->docId=p2->docId etDocId() = ().getDocId()();();();Else if ().getDocId() < ().getDocId()();Else();End習(xí)題1-10 寫出OR查詢的偽代碼l 面向過程風(fēng)格的偽代碼：給定兩個指針p1和p2，分別指向兩倒排列表list1和list2（鏈表實現(xiàn)）的首元素；令docId(p1)表示p1所指向的元素的docId；查詢結(jié)果存放在answer列表里。While p1 != null AND p2 != nullIf p1->docId = p2->docIdinse

5、rt(answer, p1)；p1=p1->next；p2=p2->next； etDocId() = ().getDocId()();();();Else if ().getDocId() < ().getDocId()();();Else();();EndWhile () != null ();();ENDWhile () != null ();();END補充習(xí)題2若一個文集有1000篇文檔，有40篇是關(guān)于信管專業(yè)建設(shè)的。我的信息需求是了解信管專業(yè)的專業(yè)建設(shè)情況，用某搜索引擎在這個文集上搜索，查詢詞為“信管”，搜出100篇包含“信管”的文檔，這其中有20篇是信管專業(yè)建設(shè)

6、方面的，其它80篇是關(guān)于信管的其它情況。請問該查詢的正確率和召回率是多少正確率=20/100=召回率=20/40=第二章 詞項詞典及倒排記錄表習(xí)題2-1a. 在布爾檢索系統(tǒng)中，進行詞干還原從不降低正確率。錯；相當(dāng)于擴充出同一個詞干表示的多個詞，會降低正確率。b. 在布爾檢索系統(tǒng)中，進行詞干還原從不降低召回率。對。c. 詞干還原會增加詞項詞典的大小。錯。d. 詞干還原應(yīng)該在構(gòu)建索引時調(diào)用，而不應(yīng)在查詢處理時調(diào)用。錯；應(yīng)同時做才能保證索引中和查詢詞的匹配。習(xí)題2-2請給出如下單詞的歸一化形式（歸一化形式也可以是詞本身）。a. Cos -> cosb. Shiite -> shiite（

7、'是隔音號）c. contd ->contd（contd. 可表示contained 包括；continued 繼續(xù)）d. Hawaii ->hawaiie. ORourke ->orourke習(xí)題2-3如下詞經(jīng)過Porter詞干還原工具處理后會輸出同樣的結(jié)果，你認(rèn)為哪對（幾對）詞不應(yīng)該輸出同樣的結(jié)果為什么a. abandon/abandonment b. absorbency/absorbent c. marketing/markets d. university/universe e. volume/volumes按Porter詞干還原算法，這幾組詞都可以被還原為

8、相應(yīng)的詞干。但是這里問的是哪些組做詞干還原不合適，原因是某組的兩個詞雖然來源于同一個詞干，但是它們的意思不同，如果做詞干還原處理會降低正確率。c組不做詞干還原。marketing表示營銷，market表示市場。d組不做詞干還原。university表示大學(xué)，universe表示宇宙。習(xí)題2-6對于兩個詞組成的查詢，其中一個詞（項）的倒排記錄表包含下面16個文檔 ID：4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180 而另一個詞（項）對應(yīng)的倒排記錄表僅僅包含一個文檔ID：47 請分別采用如下兩種策略進行倒排記錄表合并并計算所需要的比較次數(shù)，同時簡

9、要地說明計算的正確性。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是列表長度）。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)

10、, (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,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,

11、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: （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）;

12、那么哪些文檔和以下的查詢匹配其中引號內(nèi)的每個表達式都是一個短語查詢。a. “fools rush in”；文檔2、4、7。b. “fools rush in” AND “angels fear to tread”。文檔4。補充習(xí)題1k詞鄰近AND合并算法前提：考慮位置索引。要求查找這樣的文檔，它同時包含詞A和詞B，且兩詞文中的距離在k個詞以內(nèi)。給定兩個指針p1和p2，分別指向兩個詞A和B的兩倒排列表（鏈表實現(xiàn)）的首元素；令pi->doc表示pi所指向文檔對象的結(jié)構(gòu)體。對于一個文檔對象，該詞出現(xiàn)的各個位置的列表為posList。用q1（q2）表示詞A（詞B）當(dāng)前指向文檔對象指向的posLi

13、st指向的位置。用qi->pos表示該位置。查詢結(jié)果存放在answer列表里。算法：While p1 != null AND p2 != nullIf p1->docId = p2->docId 計算兩個系統(tǒng)的MAP值并比較大小。 b. 上述結(jié)果直觀上看有意義嗎能否從中得出啟發(fā)如何才能獲得高的MAP得分 c. 計算兩個系統(tǒng)的R-precision值，并與a中按照MAP進行排序的結(jié)果進行對比。解答：a. 按MAP的定義，這里|Q|=1，m=4。在查詢結(jié)果中遇到每個相關(guān)文檔對前面的所有文檔計算一個Precision，MAP將這些Precision值求平均。MAP(系統(tǒng)1)= (1

14、/4)*(1+2/3+3/9+4/10) = MAP(系統(tǒng)2)= (1/4)*(1/2+2/5+3/6+4/7)=系統(tǒng)1的MAP值大。b. 相關(guān)的查詢結(jié)果排名越靠前，則MAP越大。c. 按R-precision的定義，假設(shè)總共有|Rel|篇相關(guān)文檔，在查詢結(jié)果中取前|Rel|個文檔，計算其precision。R-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個文檔進行相關(guān)性判定的結(jié)果（0=不相關(guān)，1=相關(guān)）。假定我們開發(fā)了一個IR

15、系統(tǒng)，針對該信息需求返回了文檔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. 計算兩個判斷之間的kappa統(tǒng)計量； b. 當(dāng)兩個判斷均認(rèn)為是相關(guān)文檔時才認(rèn)為該文檔相關(guān)，此時計算上述系統(tǒng)的正確率、召回率及F1值；c. 只要有一個判斷認(rèn)為是相關(guān)文檔則認(rèn)為該文檔相關(guān)，此時計算上述系統(tǒng)的正確率、召回率及F1值。解答：a. 計算kappa統(tǒng)計量：P(A)就是實際觀察到的一致意見的概率，總共12篇文檔，其中2篇兩人一致選Yes，2篇兩人一致選

16、No。因此，P(A)=(2+2)/12=1/3。P(E)是隨機情況下的一致意見的概率。假設(shè)每個人對每個文檔的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)2+(1/2)2=1/2。Kappa=(P(A)-P(E)/(1-P(E)=(1/3-1/2)/(1-1/2)=-1/3<，這是一個負(fù)數(shù)，說明實際的一致性結(jié)果還不如隨機產(chǎn)生的一致性結(jié)果，因此可

17、以判定兩人給出的相關(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)=。c. 文檔集中共有12篇文檔，其中10文檔相關(guān)，其它2篇都不相關(guān)（1,2）。查詢結(jié)果為4, 5, 6, 7, 8，全部都相關(guān)。該查詢的Precision, P=1；Recall, R=5/12；F1=2P*R/(P+R)=。注：因Kappa統(tǒng)計量認(rèn)為兩人打分不一致，所以修正方法b比較合理，而c非常不合理。第十三章 文本分類

18、與樸素貝葉斯方法習(xí)題 13-3位置獨立性假設(shè)的基本原則是，詞項在文檔的位置k上出現(xiàn)這個事實并沒有什么有用的信息。請給出這個假設(shè)的反例。提示：可以考慮那些套用固定文檔結(jié)構(gòu)的文檔。解答：如果一個詞出現(xiàn)在不同域中，它的重要性不同。比如出現(xiàn)在標(biāo)題中的詞一般很重要。習(xí)題 13-9基于表13-10中的數(shù)據(jù)，進行如下計算： (i) 估計多項式NB分類器的參數(shù)； (ii) 將(i)中的分類器應(yīng)用到測試集；P(China)=2/4=1/2; P(非China)=2/4=1/2.詞典中有7個詞Japan, Macao, Osaka, Sapporo, Shanghai, Taipei, Taiwan.測試集中，C

19、hina類共有5個詞；非China類共有5個詞。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按單字詞語言模型，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(非

20、China類)* P(Taiwan|非China類)2* P(Sapporo|非China類)=1/2*(1/6)2*1/4=1/288.由于P(非China類|d5)> P(China類|d5)，d5屬于非China類。第十六章 扁平聚類習(xí)題 16-3 對于圖16-4，同一類中的每個點d都用兩個同樣的d的副本來替換。(i) 那么，對于新的包含34個點的集合進行聚類，會比圖 16-4中 17個點的聚類更容易、一樣難還是更難(ii) 計算對 34個點聚類的純度、RI。在點數(shù)增加一倍之后，哪些指標(biāo)增大哪些指標(biāo)保持不變(iii) 在得到(i)中的判斷和(ii)中的指標(biāo)之后，哪些指標(biāo)更適合于上述兩種聚