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

更新时间：2023-04-27 09:21:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

路漫漫其修远兮，吾将上下而求索 - 百度文库

11 《信息组织与检索》作业答案

第一章布尔检索

习题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:

1234

approach0010

breakthrough1000

drug1100

for1011

hopes0001

new0111

of0010

patients0001

schizophrenia1111

treatment0010

Inverted 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->4

treatment >3

路漫漫其修远兮，吾将上下而求索 - 百度文库

注意：倒排索引中的词表（dictionary）和每个词项的倒排列表（posting list）需要排序，便于查找。这里我们暂不考虑词的正规化处理（如hopes->hope）。

补充习题1

写出AND查询的伪代码

●面向过程风格的伪代码：

给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId查询结果存放在answer列表里。

这里应用了“化归”思想（将新问题转化归为旧问题来解决）。这里，比较两排序列表的首元素，排除较小的docId（不可能有匹配）后，我们构造出新的剩余列表，再次进行两列表的首元素的比较。

While p1 != null AND p2 != null

If p1->docId==p2->docId //对两（剩余）列表的首元素进行比较

insert(answer, p1)；

p1=p1->next；//构造新的剩余列表，迭代执行

p2=p2->next；//

Else if p1->docId < p2->docId

p1=p1->next；//p1->docId不可能有匹配；构造新的剩余列表

Else

p2=p2->next；//p2->docId不可能有匹配；构造新的剩余列表

End

●面向对象风格的伪代码：

注：为一个数据结构（对象）定义方法，通过方法操作自己的内部数据（List对象里隐含包含了一个成员变量，它是真正的链表或变长数组）。

While list1.currentItem() != null AND list2.currentItem() != null

If list1.currentItem().getDocId() == list2.currentItem().getDocId()

answer.insert(list1.currentItem());

list1.moveToNext();

list2.moveToNext();

Else if list1.currentItem().getDocId() < list2.currentItem().getDocId()

list1.moveToNext();

Else

list2.moveToNext();

路漫漫其修远兮，吾将上下而求索 - 百度文库

33 End

习题1-10

写出OR查询的伪代码

●面向过程风格的伪代码：

给定两个指针p1和p2，分别指向两倒排列表list1和list2（链表实现）的首元素；令docId(p1)表示p1所指向的元素的docId；查询结果存放在answer列表里。

While p1 != null AND p2 != null

If p1->docId == p2->docId

insert(answer, p1)；

p1=p1->next；

p2=p2->next；//构造新的剩余列表，迭代执行

Else if p1->docId < p2->docId

insert(answer, p1)；

p1=p1->next；//构造新的剩余列表，迭代执行

Else

insert(answer, p2)；

p2=p2->next；//构造新的剩余列表，迭代执行

End

While p1 != null//条件为真时，加入list1的剩余元素（此时list2已遍历到结尾）insert(answer, p1)；

p1=p1->next；

END

While p2 != null//条件为真时，加入list2的剩余元素（此时list1已遍历到结尾）insert(answer, p2)；

p2=p1->next；

END

●面向对象风格的伪代码：

While list1.currentItem() != null AND list2.currentItem() != null

If list1.currentItem().getDocId() == list2.currentItem().getDocId()

answer.insert(list1.currentItem());

list1.moveToNext();

list2.moveToNext();

路漫漫其修远兮，吾将上下而求索 - 百度文库

44 Else if list1.currentItem().getDocId() < list2.currentItem().getDocId() answer.insert(list1.currentItem());

list1.moveToNext();

Else

answer.insert(list2.currentItem());

list2.moveToNext();

End

While list1.currentItem() != null

answer.insert(list1.currentItem());

list1.moveToNext();

END

While 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-1

a.在布尔检索系统中，进行词干还原从不降低正确率。

错；相当于扩充出同一个词干表示的多个词，会降低正确率。

b.在布尔检索系统中，进行词干还原从不降低召回率。

对。

c. 词干还原会增加词项词典的大小。

错。

d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。

错；应同时做才能保证索引中和查询词的匹配。

路漫漫其修远兮，吾将上下而求索 - 百度文库

习题2-2

请给出如下单词的归一化形式（归一化形式也可以是词本身）。

a. ’Cos -> cos

b. Shi’ite -> shiite（'是隔音号）

c. cont’d ->contd（cont

d. 可表示contained 包括；continued 继续）

d. Hawai’i ->hawaii

e. O’Rourke ->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。

补充习题1

k词邻近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 != null

If p1->docId == p2->docId //对两（剩余）列表的首元素进行比较

While q1 != null AND q2 != null

If q1->pos–q2->pos<=k OR q2->pos –q1->pos <= k

路漫漫其修远兮，吾将上下而求索 - 百度文库

insert(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 If

End While

p1=p1->next; //构造新的剩余列表，迭代执行

p2=p2->next;

Else if p1->docId < p2->docId

p1=p1->next；//p1->docId不可能有匹配；构造新的剩余列表

Else

p2=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的这个文集）。

路漫漫其修远兮，吾将上下而求索 - 百度文库

w t,d=max(1+log10(1+tf),0)

Doc1Doc2Doc3

Car 2.4314 1.6021 2.3802

Auto 1.4771 2.51850

insurance0 2.5185 2.4624

Best 2.14610 2.2304

df t idf t

car30

auto20.1761

insurance20.1761

best20.1761

这里N=3。

tf-idf t,d= w t,d*idf t

Doc1Doc2Doc3

car

auto0.26010.44350

insurance00.44350.4336

best0.377900.3928

例6-4

假设文档集中的文档数目N=1000000，词表为{auto, best, car, insurance} ，这四个词的df值分别为5000, 50000, 10000, 1000。

设某文档d的raw tf向量为[1,0,1,2]，对查询q=”best car insurance”，问该文档-查询的相似度打分score(q,d)是？

df t idf t

auto5000 2.3010

best50000 1.3010

car10000 2.0000

路漫漫其修远兮，吾将上下而求索 - 百度文库

insurance1000 3.0000

文档d的tf-idf向量：

raw tf t,d w t,d=max(1+log10(1+tf),0)tf-idf t,d= w t,d*idf t v(d)=归一化

tf-idf t,d

auto1 1.0000 2.30100.4646

best0000

car1 1.0000 2.00000.4038 insurance2 1.3010 3.90310.7881

raw tf t,q w t,q=max(1+log10(1+tf),0)tf-idf t,q= w t,q*idf t v(q)=归一化

tf-idf t,d

auto0000

best11 1.30100.3394

car11 2.00000.5218 insurance11 3.00000.7827

第八章信息检索的评价

习题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.6

MAP(系统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/2

R-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）打分的概率p y（或p n ）是独立同分布的(i. i. d.)，则P(E)= p y*p y + p n*p n。其中，p y是2*12次打分中为Yes的比例，p y=12/24=1/2；p n是2*12次打分中为No的比例，p n=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。

1010

路漫漫其修远兮，吾将上下而求索 - 百度文库

1111 c. 文档集中共有12篇文档，其中10文档相关，其它2篇都不相关（{1,2}）。查询结果为

{4, 5, 6, 7, 8}，全部都相关。

该查询的

Precision, P=1；

Recall, R=5/12；

F 1=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/12

P(Sapporo|非China 类)= (2 + 1)/(5 + 7)= 1/4

按单字词语言模型，

P(China 类|d 5) ∝ P(China 类)* P(Taiwan|China 类)^2* P(Sapporo|China 类)=1/2*(1/4)^2*1/12=1/384.

P(非China 类|d 5) ∝ P(非China 类)* P(Taiwan|非China

类)^2* P(Sapporo|非China 类)=1/2*(1/6)^2*1/4=1/288.

路漫漫其修远兮，吾将上下而求索 - 百度文库

1212 由于P(非China 类|d 5)> P(China 类|d 5)，d 5属于非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 ：