《信息检索导论》课后习题答案(共13页).docx

精选优质文档-倾情为你奉上信息组织与检索作业答案第一章 布尔检索习题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. 画出文档集对应的词项文档矩阵；b. 画出该文档集的倒排索引（参考图 1-3中的例子）。Term-Documentmatrix:1234approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010Inverted 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）和每个词项的倒排列表（posting list）需要排序，便于查找。这里我们暂不考虑词的正规化处理（如hopes->hope）。补充习题1写出AND查询的伪代码l 面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId查询结果存放在answer列表里。这里应用了“化归”思想（将新问题转化归为旧问题来解决）。这里，比较两排序列表的首元素，排除较小的docId（不可能有匹配）后，我们构造出新的剩余列表，再次进行两列表的首元素的比较。While p1 != null AND p2 != nullIf p1->docId=p2->docId /对两（剩余）列表的首元素进行比较insert(answer, p1)；p1=p1->next；/构造新的剩余列表，迭代执行p2=p2->next；/Else if p1->docId < p2->docIdp1=p1->next； /p1->docId不可能有匹配；构造新的剩余列表Elsep2=p2->next； /p2->docId不可能有匹配；构造新的剩余列表Endl 面向对象风格的伪代码：注：为一个数据结构（对象）定义方法，通过方法操作自己的内部数据（List对象里隐含包含了一个成员变量，它是真正的链表或变长数组）。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().getDocId()list1.moveToNext();Elselist2.moveToNext();End习题1-10 写出OR查询的伪代码l 面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId；查询结果存放在answer列表里。While p1 != null AND p2 != nullIf p1->docId = p2->docIdinsert(answer, p1)；p1=p1->next；p2=p2->next； /构造新的剩余列表，迭代执行Else if p1->docId < p2->docIdinsert(answer, p1)；p1=p1->next； /构造新的剩余列表，迭代执行Elseinsert(answer, p2)；p2=p2->next； /构造新的剩余列表，迭代执行EndWhile p1 != null/条件为真时，加入list1的剩余元素（此时list2已遍历到结尾）insert(answer, p1)；p1=p1->next；ENDWhile p2 != null/条件为真时，加入list2的剩余元素（此时list1已遍历到结尾）insert(answer, p2)；p2=p1->next；ENDl 面向对象风格的伪代码：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().getDocId()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补充习题2若一个文集有1000篇文档，有40篇是关于信管专业建设的。我的信息需求是了解信管专业的专业建设情况，用某搜索引擎在这个文集上搜索，查询词为“信管”，搜出100篇包含“信管”的文档，这其中有20篇是信管专业建设方面的，其它80篇是关于信管的其它情况。请问该查询的正确率和召回率是多少正确率=20/100=0.2召回率=20/40=0.5第二章 词项词典及倒排记录表习题2-1a. 在布尔检索系统中，进行词干还原从不降低正确率。错；相当于扩充出同一个词干表示的多个词，会降低正确率。b. 在布尔检索系统中，进行词干还原从不降低召回率。对。c. 词干还原会增加词项词典的大小。错。d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。错；应同时做才能保证索引中和查询词的匹配。习题2-2请给出如下单词的归一化形式（归一化形式也可以是词本身）。a. Cos -> cosb. Shiite -> shiite（'是隔音号）c. contd ->contd（contd. 可表示contained 包括；continued 继续）d. Hawaii ->hawaiie. ORourke ->orourke习题2-3如下词经过Porter词干还原工具处理后会输出同样的结果，你认为哪对（几对）词不应该输出同样的结果？为什么？a. abandon/abandonment b. absorbency/absorbent c. marketing/markets d. university/universe e. volume/volumes按Porter词干还原算法，这几组词都可以被还原为相应的词干。但是这里问的是哪些组做词干还原不合适，原因是某组的两个词虽然来源于同一个词干，但是它们的意思不同，如果做词干还原处理会降低正确率。c组不做词干还原。marketing表示营销，market表示市场。d组不做词干还原。university表示大学，universe表示宇宙。习题2-6对于两个词组成的查询，其中一个词（项）的倒排记录表包含下面16个文档 ID：4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180 而另一个词（项）对应的倒排记录表仅仅包含一个文档ID：47 请分别采用如下两种策略进行倒排记录表合并并计算所需要的比较次数，同时简要地说明计算的正确性。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是列表长度）。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: （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）; 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合并算法前提：考虑位置索引。要求查找这样的文档，它同时包含词A和词B，且两词文中的距离在k个词以内。给定两个指针p1和p2，分别指向两个词A和B的两倒排列表（链表实现）的首元素；令pi->doc表示pi所指向文档对象的结构体。对于一个文档对象，该词出现的各个位置的列表为posList。用q1（q2）表示词A（词B）当前指向文档对象指向的posList指向的位置。用qi->pos表示该位置。查询结果存放在answer列表里。算法：While p1 != null AND p2 != nullIf p1->docId = p2->docId /对两（剩余）列表的首元素进行比较While q1 != null AND q2 != nullIf q1->posq2->pos<=k OR q2->pos q1->pos <= kinsert(answer, p1);break; /跳出这个循环，找到一个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; /构造新的剩余列表，迭代执行p2=p2->next;Else if p1->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得分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的这个文集）。解答：wt,d=max(1+log10(1+tf),0)Doc1Doc2Doc3Car2.43141.60212.3802Auto1.47712.51850insurance02.51852.4624Best2.146102.2304 dftidftcar30auto20.1761insurance20.1761best20.1761这里N=3。tf-idft,d= wt,d*idftDoc1Doc2Doc3car000auto0.26010.44350insurance00.44350.4336best0.377900.3928例6-4假设文档集中的文档数目N=，词表为auto, best, car, insurance ，这四个词的df值分别为5000, 50000, 10000, 1000。设某文档d的raw tf向量为1,0,1,2，对查询q=”best car insurance”，问该文档-查询的相似度打分score(q,d)是？ 解答：dftidftauto50002.3010best500001.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,dauto0000best111.30100.3394car112.00000.5218insurance113.00000.7827score(q,d) = v(q)*v(d)=0.8275第八章 信息检索的评价习题 8-8考虑一个有4篇相关文档的信息需求，考察两个系统的前10个检索结果（左边的结果排名靠前），相关性判定的情况如下所示： 系统1 R N R N N N N N R R 系统2 N R N N R R R N N N a. 计算两个系统的MAP值并比较大小。 b. 上述结果直观上看有意义吗？能否从中得出启发如何才能获得高的MAP得分？ c. 计算两个系统的R-precision值，并与a中按照MAP进行排序的结果进行对比。解答：a. 按MAP的定义，这里|Q|=1，m=4。在查询结果中遇到每个相关文档对前面的所有文档计算一个Precision，MAP将这些Precision值求平均。MAP(系统1)= (1/4)*(1+2/3+3/9+4/10) = 0.6MAP(系统2)= (1/4)*(1/2+2/5+3/6+4/7)=0.49系统1的MAP值大。b. 相关的查询结果排名越靠前，则MAP越大。c. 按R-precision的定义，假设总共有|Rel|篇相关文档，在查询结果中取前|Rel|个文档，计算其precision。R-precision(系统1)=2/4=1/2R-precision(系统1)=1/4系统1的R-precision值大。与MAP给出系统打分排序的结果一致。习题 8-10下表中是两个判定人员基于某个信息需求对12个文档进行相关性判定的结果（0=不相关，1=相关）。假定我们开发了一个IR系统，针对该信息需求返回了文档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统计量； b. 当两个判断均认为是相关文档时才认为该文档相关，此时计算上述系统的正确率、召回率及F1值；c. 只要有一个判断认为是相关文档则认为该文档相关，此时计算上述系统的正确率、召回率及F1值。解答：a. 计算kappa统计量：P(A)就是实际观察到的一致意见的概率，总共12篇文档，其中2篇两人一致选Yes，2篇两人一致选No。因此，P(A)=(2+2)/12=1/3。P(E)是随机情况下的一致意见的概率。假设每个人对每个文档的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<0.67，这是一个负数，说明实际的一致性结果还不如随机产生的一致性结果，因此可以判定两人给出的相关性打分不一致。b. 文档集中共有12篇文档，其中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统计量认为两人打分不一致，所以修正方法b比较合理，而c非常不合理。第十三章 文本分类与朴素贝叶斯方法习题 13-3位置独立性假设的基本原则是，词项在文档的位置k上出现这个事实并没有什么有用的信息。请给出这个假设的反例。提示：可以考虑那些套用固定文档结构的文档。解答：如果一个词出现在不同域中，它的重要性不同。比如出现在标题中的词一般很重要。习题 13-9基于表13-10中的数据，进行如下计算： (i) 估计多项式NB分类器的参数； (ii) 将(i)中的分类器应用到测试集；P(China)=2/4=1/2; P(非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/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(非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类。第十六章 扁平聚类习题 16-3 对于图16-4，同一类中的每个点d都用两个同样的d的副本来替换。(i) 那么，对于新的包含34个点的集合进行聚类，会比图 16-4中 17个点的聚类更容易、一样难还是更难？(ii) 计算对 34个点聚类的纯度、RI。在点数增加一倍之后，哪些指标增大？哪些指标保持不变？(iii) 在得到(i)中的判断和(ii)中的指标之后，哪些指标更适合于上述两种聚类结果的质量比较？解答：（i）我认为更难，因为34个点比17点的计算量增大了。（ii）节点复制为原先的一倍后，簇1：10个x类文档，2个o类文档；簇2：2个x类文档，8个o类文档，2个 类文档；簇3：4个x类文档，6个 类文档。共有N=34篇文档。计算纯度=(1/34)*(10+8+6)0.71； 计算RI：TP=102+22+22+82+22+42+62=97 ，将一对同类的文档分到相同聚类中的对数。TN=10*8+10*2+2*2+2*2+10*6+2*4+2*6+2*6+8*4+8*6+2*4=288，将一对不同类的文档分到不同聚类中的对数。RI=(TP+TN)/342=(97+288)/5610.69.（iii）对比N=17时，纯度为0.71，RI为0.68。我们得出节点复制为原先的一倍后，指标几乎不变。习题 16-4 在K-均值算法中，为什么对同一概念car使用不同词项来表示的文档最后可能会被归入同一簇中？ 解答：考虑两篇文档，一篇含有car和其它词，一篇含有automobile和其它词。虽然第2篇文档不含automobile，但这两篇文档可能含有大量的公共词，它们的文档向量可能是相似的，聚类算法将把它们分配到同一簇中。习题16-5 K-均值算法的两个停止条件为：(i) 文档的分配不再改变； (ii) 簇质心不再改变。请问这两个条件是否等价？解答：连续两次迭代，文档到分配簇的情况不再改变，说明簇质心的计算也不再改变。连续两次迭代，簇质心不再改变，按照最近距离原则，文档到分配簇的情况也不再改变。因此，条件(i)和(ii)是等价的。专心-专注-专业