《信息检索导论》课后习题答案

CTRL+A全选可调整字体属性及字体大小-CAL-FENGHAI.NetworkInformationTechnologyCompany.2020YEAR《信息检索导论》课后习答案《信息组织与检索》作业答案布尔检索习题1-2考虑如下几篇文档：文档1breakthroughdrugforschizophrenia文档2newschizophreniadrug文档3newapproachfortreatmentofschizophrenia文档4newhopesforschizophreniapatientsa.画出文档集对应的词项—文档矩阵；b.画出该文档集的倒排索引（参考图1-3中的例子）。Term-Documentmatrix:1234approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010InvertedIndex:approach->3breakthrough->1drug->1->2for->1->3->4hopes->4new->2->3->4of->3patients->4schizophrenia->1->2->3->4treatment>3注意：倒排索引中的词表（dictionary）和每个词项的倒排列表（postinglist）需要排序，便于查找。这里我们暂不考虑词的正规化处理（如hopes->hope）。补充习题1写出AND查询的伪代码面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId查询结果存放在answer列表里。这里应用了“化归”思想（将新问题转化归为旧问题来解决）。这里，比较两排序列表的首元素，排除较小的docId（不可能有匹配）后，我们构造出新的剩余列表，再次进行两列表的首元素的比较。Whilep1!=nullANDp2!=nullIfp1->docId==p2->docIdetDocId()==().getDocId()());();();Elseif().getDocId()<().getDocId()();Else();End习题1-10写出OR查询的伪代码面向过程风格的伪代码：给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId；查询结果存放在answer列表里。Whilep1!=nullANDp2!=nullIfp1->docId==p2->docIdinsert(answer,p1)；p1=p1->next；p2=p2->next；etDocId()==().getDocId()());();();Elseif().getDocId()<().getDocId()());();Else());();EndWhile()!=null());();ENDWhile()!=null());();END补充习题2若一个文集有1000篇文档，有40篇是关于信管专业建设的。我的信息需求是了解信管专业的专业建设情况，用某搜索引擎在这个文集上搜索，查询词为“信管”，搜出100篇包含“信管”的文档，这其中有20篇是信管专业建设方面的，其它80篇是关于信管的其它情况。请问该查询的正确率和召回率是多少正确率=20/100=召回率=20/40=词项词典及倒排表习题2-1在布尔检索系统中，进行词干还原从不降低正确率。错；相当于扩充出同一个词干表示的多个词，会降低正确率。在布尔检索系统中，进行词干还原从不降低召回率。对。c.词干还原会增加词项词典的大小。错。d.词干还原应该在构建索引时调用，而不应在查询处理时调用。错；应同时做才能保证索引中和查询词的匹配。习题2-2请给出如下的归一化形式（归一化形式也可以是词本身）。a.’Cos->cosb.Shi’ite->shiite（'是隔音号）c.cont’d->contd（contd.可表示contained包括；continued继续）d.Hawai’i->hawaiie.O’Rourke->orourke习题2-3如下词经过Porter词干还原工具处理后会输出同样的结果，你认为哪对（几对）词不应该输出同样的结果为什么a.abandon/abandonmentb.absorbency/absorbentc.marketing/marketsd.university/universee.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]请分别采用如下两种策略进行倒排记录表合并并计算所需要的比较次数，同时简要地说明计算的正确性。使用标准的倒排记录表。比较：(4,47),(6,47),(10,47),(12,47),(14,47),(16,47),(18,47),(20,47),(22,47),(32,47),(47,47)。共比较11次。使用倒排记录表+跳表的方式，跳表指针设在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）;那么哪些文档和以下的查询匹配其中引号内的每个表达式都是一个短语查询。“foolsrushin”；文档2、4、7。“foolsrushin”AND“angelsfeartotread”。文档4。补充习题1k词邻近AND合并算法前提：考虑位置索引。要求查找这样的文档，它同时包含词A和词B，且两词文中的距离在k个词以内。给定两个指针p1和p2，分别指向两个词A和B的两倒排列表（链表实现）的首元素；令pi->doc表示pi所指向文档对象的结构体。对于一个文档对象，该词出现的各个位置的列表为posList。用q1（q2）表示词A（词B）当前指向文档对象指向的posList指向的位置。用qi->pos表示该位置。查询结果存放在answer列表里。算法：Whilep1!=nullANDp2!=nullIfp1->docId==p2->docId计算两个系统的MAP值并比较大小。b.上述结果直观上看有意义吗能否从中得出启发如何才能获得高的MAP得分c.计算两个系统的R-precision值，并与a中按照MAP进行排序的结果进行对比。解答：按MAP的定义，这里|Q|=1，m=4。在查询结果中遇到每个相关文档对前面的所有文档计算一个Precision，MAP将这些Precision值求平均。MAP(系统1)=(1/4)*(1+2/3+3/9+4/10)=MAP(系统2)=(1/4)*(1/2+2/5+3/6+4/7)=系统1的MAP值大。相关的查询结果排名越靠前，则MAP越大。按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判断2100200311411510610710810901100111011201a.计算两个判断之间的kappa统计量；b.当两个判断均认为是相关文档时才认为该文档相关，此时计算上述系统的正确率、召回率及F1值；c.只要有一个判断认为是相关文档则认为该文档相关，此时计算上述系统的正确率、召回率及F1值。解答：计算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<，这是一个负数，说明实际的一致性结果还不如随机产生的一致性结果，因此可以判定两人给出的相关性打分不一致。文档集中共有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)=。文档集中共有12篇文档，其中10文档相关，其它2篇都不相关（{1,2}）。查询结果为{4,5,6,7,8}，全部都相关。该查询的Precision,P=1；Recall,R=5/12；F1=2P*R/(P+R)=。注：因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/6P(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)；计算RI：，将一对同类的文档分到相同聚类中的对数。，将一对不同类的文档分到不同聚类中的对数。.（iii）对比N=17时，纯度为，RI为。我们得出节点复制为原先的一倍后，指标几乎不变。习题16-4在K-均值算法中，为什么对同一概念car使用不同词项来表示的文档最后可能会被归入同一簇中解答：考虑两篇文档，一篇含有car和其它词，一篇含有automobile和其它词。虽然第2篇文档不含automobile，但这两篇文档可能含有大量的公共词，它们的文档向量可能是相似的，聚类算法将把它们分配到同一簇中。习题16-5K-均值算法的两个停止条件为：(i)文档的分配不再改变；(ii)簇质心不再改变。请问这两个条件是否等价解答：连续两次迭代，文档到分配簇的情况不再改变，说明簇质心的计算也不再改变。连续两次迭代，簇质心不再改变，按照最近距离原则，文档到分配簇的情况也不再改变。因此，条件(i)和(ii)是等价的。