Web信息检索复习题word打印版Word下载.docx
- 文档编号:7774592
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:40
- 大小:954.06KB
Web信息检索复习题word打印版Word下载.docx
《Web信息检索复习题word打印版Word下载.docx》由会员分享,可在线阅读,更多相关《Web信息检索复习题word打印版Word下载.docx(40页珍藏版)》请在冰点文库上搜索。
g)vec(dj)=(w1j,w2j,…,wtj):
文档dj的加权重的向量表示。
h)gi(vec(dj))=wij:
得到分量的函数。
(1)布尔与向量空间模型
布尔检索模型
一种简单的检索模型,它建立在经典的集合论和布尔代数的基础上。
遵循两条基本规则:
每个索引词在一篇文档中只有两种状态:
出现或不出现,对应权值为0或1。
查询是由三种布尔逻辑运算符and,or,not连接索引词组成的布尔表达式。
对于布尔模型而言,索引词权值变量都是二值的,wij∈{0,1}.用qdnf表示查询q的析取范式,qcc表示qdnf的任意合取分量,二值变量gi(dj)是表示索引项ki是否在文档dj中出现的值,二值变量gi(qcc)是表示索引项ki是否在合取分量qcc中出现的值
sim(dj,q)为该模型的匹配函数:
文献为dj与查询q的相似度为:
如果sim(dj,q)=1,则表示文献dj与q相关,否则为不相关。
例
虽然文献包含了kb,但sim(dj,q)=0.
优点:
简单、易理解、简洁的形式化。
缺点:
准确匹配,信息需求的能力表达不足。
不能输出部分匹配的情况,无法排序,用户必须会用布尔表达式提问,一般而言,检出的文档或者太多或者太少。
向量空间模型(VectorSpaceModel,VSM)
相比于布尔模型要求的准确匹配,VSM模型采用了“部分匹配”的检索策略(即:
出现部分索引词也可以出现在检索结果中)
通过给查询或文档中的索引词分配非二值权值来实现
帮助改善了检索结果。
部分匹配的文档也可以被检索到。
可以基于向量cosine的值进行排序,提供给用户。
这种方法假设标记词是相互独立的,但实际可能不是这样,如同义词、近义词等往往被认为是不相关的词
(2)向量是如何产生
去停用词(stopword):
指文档中出现的连词,介词,冠词等并无太大意义的词。
例如在英文中常用的停用词有the,a,it等;
在中文中常见的有“是”,“的”,“地”等
选索引词(标引词/关键祠):
可以用于指代文档内容的预选词语,一般为名词/名词词组
词干提取:
在英文中,countries=>
country,interesting=>
interest
中文切词/分词(wordsegmentation):
主要在中文信息处理中使用,即把一句话分成一个词的序列。
如“网络与分布式系统实验室”分词为“网络/与/分布式/系统/实验室/”。
(3)tf,idf的含义
tf:
thetermfrequencywithinadocument这个词在一个文件的频率idf:
theinversedocumentfrequency文档频率
定义N为所有文档的个数,ni为包含标记词ki的文档个数,freq(i,j)为文档dj中标记词ki出现的个数
范式化的tf定义为tf(i,j)=freq(i,j)/max(freq(l,j)),其中max(freq(l,j))是文档dj中出现最高频率词的频率。
idf定义为idf(i)=log(N/ni),使用log主要为了更好地使tf和idf匹配,因为N可能很大。
(4)计算向量之间的相似度的方法
相似度计算公式为:
(5)当维数比较大时,利用隐性语义索引模型降维的方法
隐性语义索引模型LatentSemanticIndexing
问题描述:
一般文档的特征表示维数都很高,对文本常是上万维,对图像也常是50-60多维,带来问题:
1)向量中0很多,即稀疏性
2)存储空间要求很大
3)虽然说维数也多,似乎对文档的特征描述越全面,但由于数据的稀疏性,有时维数大,计算的效果不一定比维数小的好
能否去掉一些线性相关的向量来减少维数(线性代数中的矩阵特征向量!
)
(6)数学原理
矩阵向量的乘积
具有特征值3,2,0;
对应的向量有
例如向量可以看出是特征向量的组合x=2v1+4v2+6v3
这样矩阵-向量乘积可以用特征值和特证向量表示出来
虽然向量x是任意的,但Sx则是也是由特征值和特征向量的组合所决定的
矩阵的奇异值分解
对任意mn矩阵A,A的秩为r,均可分解为两个正交矩阵和一个对角矩阵的乘积
(SingularValueDecompositionSVD)
是rr的对角阵
U的列向量是由AAT的相互正交的特征向量组成(mr)
V的列向量是由ATA的相互正交的特征向量组成(rn)
Eigenvalues1…rofAATaretheeigenvaluesofATA
满足
SVDcanbeusedtocomputeoptimallow-rankapproximations.
Approximationproblem:
FindAkofrankksuchthat
其中F为Frobenius范数,形式为
AandXarebothmnmatrices.
Typically,wantk<
<
r.
通过SVD实现Low-rankapproximations.
setsmallestr-ksingularvaluestozero
LSI是在SVD的基础上,只保留最大的k个奇异值,而忽略较小的奇异值,从而达到进一步降维,即前面讲的近似方法。
具体做法是:
SVD得到的,只保留最大的k个奇异值得到’,进行奇异分解的反运算,得到A的近似矩阵
5、因为字符串操作是信息检索的关键性计算,能掌握常用的对字符串处理的算法,包括字符串匹配算法,k-近似匹配算法和求两字符串A,B之间的最大公共子串的算法。
能写出具体的算法以及这些算法在文本和图像检索中的应用。
(1)字符串匹配算法
1)SimpleStringMatching
Input:
PandT,thepatternandtextstrings;
m,thelengthofP.Thepatternisassumedtobenonempty.
Output:
ThereturnvalueistheindexinTwhereacopyofPbegins,or-1ifnomatchforPisfound.
具体算法描述:
Notationforpatternsandtext
Pthepatternbeingsearchfor;
TthetextinwhichPissought;
mthelengthofP
nthelengthofT,notknowntothealgorithm;
m<
=n;
jcurrentpositionwithininT
kcurrentpositionwithininP
pititheithcharactersinPandTaredenotedwithlowercaselettersandsubscripts
intsimpleScan(char[]P,char[]T,intm){
intmatch;
//valuetoreturn.
inti,j,k;
/*iisthecurrentguessatwherePbeginsinT;
*/
match=-1;
/*jistheindexofthecurrentcharacterinT*/
j=1;
k=1;
i=j;
//kisthenumberofcharscompared//
while(endText(T,j)==false){
/*notreachtheendofT*/
if(k>
m){
/*misthelengthofP*/
match=i;
//matchfound.//successcase//
break;
/*exittheloophere*/
}
if(tj==pk){j++;
k++;
}
else{
//Backupovermatchedcharacters.
intbackup=k-1;
//从本次查询点的下一个顶点开始//
j=j-backup;
k=k-backup;
//Slidepatternforward,startover.
j++;
}
}
returnmatch;
算法复杂度分析:
最差
例如P=aaab,T=aaaaaaaaaaaaaaaaaaaaaaaaaaaaab时
(2)k-近似匹配算法
KMP算法:
首先求fail数组,fail[i]=j,第i个字符匹配失败,则回退到第j个字符。
voidkmpSetup(char[]P,intm,int[]fail){
//m是P的长度
intk,s;
fail[1]=0;
/*startpoint*/
for(k=2;
k<
=m;
k++){
s=fail[k-1];
while(s>
=1){/*p1,…,ps与pk-s+1,…,pk-1比较*/
if(ps==pk-1)/*就是它!
break;
s=fail[s];
/*否则递归向下找*/
}
fail[k]=s+1;
我们可以假设在计算fail[k]时,所有fail[t],t<
k已经被计算了。
若当前字符(k)匹配失败,则退回到和自己有相同前继字符(k-1)的字符(j,j<
k)。
intkmpScan(char[]P,char[]T,intm,int[]fail){
intmatch,j,k;
match=-1;
k=1;
while(endText(T,j)==false){
if(k>
m){//success
match=j-m;
break;
if(k==0)//thepointofTmovesahead,andrescan//
j++;
elseif(tj==pk)//successatpositionkofP
k++;
else
//Followfailarrow.
k=fail[k];
//failandgobacktothepointofP//
//continueloop.
returnmatch;
(3)求两字符串A,B之间的最大公共子串的算法
PK算法O(m+n)
设∑代表字符集合,
,定义函数ord(x),d=|∑|,ord(x):
∑→{0,1,2,…,d-1}
对任意的模式P,|P|=m,利用多项式指纹
Q(P)=ord(P1)dm-1+ord(P2)dm-2+…+ord(Pm-1)d+ord(Pm)代表P
同样对文本T=T1,T2,….,Tn
从左到右计算长度为m的连续子串的指纹,如Q(i)=ord(Ti)dm-1+ord(Ti+1)dm-2+…+ord(Ti+m-2)d+ord(Ti+m-1)
并和Q(P)相比较。
若相同,则找到匹配的子串。
起始位置为i,0<
i<
n-m,否则右移一位
Q(i+1)=(Q(i)-ord(Ti)dm-1)d+ord(Ti+m)O
(1)时间
字符串的近似匹配
ThenameofthedifferenceistheoperationneededonTtobringitclosertoP.
Revise:
ThecorrespondingcharactersinPandTaredifferent;
Delete:
TcontainsacharacterthatismissingfromP
Insert:
TismissingacharacterthatappearsinP
Differencetable
D[i][j]=theminimumnumberofdifferencebetweenP1,…,PiandasegmentofTendingattj.
1≤i≤m,1≤j≤m.定义:
D[0][j]=0;
D[i,0]=i;
Therewillbeak-approximatematchendingattjforanyjsuchthatD[m][j]≤k,sowecanstopassoonaswefindanentrylessthanorequaltokinthelastrowofD,whichisthefirst
k-approximatematch.TherulesforthecomputationofD
D[i][j]取运算得到四个数字中的最小值
D[i][j]=D[i-1][j-1]ifpi=tj/*noerror*/
D[i][j]=D[i-1][j-1]+1ifpi<
>
tjandrevisebothiandjincrease;
D[i][j]=D[i-1][j]+1ifinsertintoT,onlyiincrease.
D[i][j]=D[i][j-1]+1ifdeletealetterfromTonlyjincrease.
LCS最大公共字串Longest-Common-Subsequence
LetF[i,j]denotethelengthofthelongestcommonsubsequenceofthefirstielementsofAandthefirstjelementsofB.TheobjectiveoftheLCSproblemistofindF[n,m].
(4)算法在文本和图像检索中的应用
6、能给出信息检索中常用的测度,如查全率、查准率和F1计算公式。
知道11个标准查准率是如何规定的,查准率直方图、E测度指标的含义是什么?
面向用户的测试集合及信息检索系统的性能是如何确定的?
对目前常用的MRR,NDCG的测度又是怎样定义的?
它们考虑的评测要点是什么?
对某个测试参考集,信息查询实例为I,I对应的相关文档集合为R。
假设用某个检索策略对I进行处理后,得到一个结果集合A。
令Ra表示R与A的交集。
Ra
查全率(Recall):
检出的相关文档个数与相关文档集合总数的比值,即R=|Ra|/|R|
查准率(Precision):
检出的相关文档个数与检出文档总数的比值,即P=|Ra|/|A|
F1标准则综合了精度和查全率,将两者赋予同样的重要性来考虑。
F1的计算由下面的公式决定
查准率与查全率的调和平均数
查准率/查全率曲线
11点标准查全率下的查准率曲线,计算查全率分别为(0%,10%,20%,…,100%)下的查准率。
即利用查全率,限制一下文档数,以此计算查准率。
多个查询下的查准率/查全率曲线,可通过计算其平均查准率得到,公式如下
(Nq为查询的数量)
P(r)是指查全率为r时的平均查准率,Pi(r)指查全率为r时的第i个查询的查准率
由于每个查询的查全率值不一定就是这11个标准查全率,因此需要对查准率进行插补。
第j个标准查全率水平的查准率是介于第j个和第j+1个查全率之间任意一个查全率所对应的查准率的最大值。
R-查准率p@R,计算序列中第R个位置文献的查准率。
R是指与当前查询相关的文档总数。
查准率直方图
用于快速比较两个检索算法的性能
多个查询下,分别计算每一查询下的R-查准率,计算其差值,并用直方图表示。
具体地:
用RPA(i)和RPB(i)分别表示使用检索算法A和检索算法B检索第i个查询时得到的R-查准率,它们之间的差值:
RPA-B(i)=RPA(i)-RPB(i)
意义:
RPA/B(i)>
0时,算法A(对第i个查询)比算法B好,反之B(对第i个查询)好.可以看出算法A在其中的8次比算法B好.
E测度指标允许用户指出他更关心查准率或查全率
b=1,E=1-F;
b>
1表明用户对查准率更感兴趣
b<
1表明用户对查全率更感兴趣
MRR(第1个相关结果位置的倒数平均,MeanReciprocalRanking):
所有查询的第一个相关结果位置倒数的平均;
MRR=0.5,意味着检索列表中前2项有相关文档。
ranki第i个查询所排的位置
NDCG(Normalizeddiscountedcumulativegain)
NDCG方法在实际计算中分为三个步骤,分别为CG、DCG以及NDCG
CumulativeGain(CG):
位于位置1到p的检索结果的相关度之和
reli表示第i个文档与查询语句的相关度,缺点:
未考虑位置关系
DiscountedCumulativeGain(DCG)基本思想,若搜索算法把相关度高的文档排在后面,则应该给予惩罚。
一般用log函数表示这种惩罚
另一种计算公式为:
更强调前面的文档重要性
NDCG(NormalizingDCG)检索结果与具体查询以及序列的长度有关。
为了规范化,我们把检索结果进行从大到小排序得到理想的输出序列。
在这个理想的序列上计算DCG,得到在位置p的idealDCG(IDCG)
面向用户的测度方法
一篇文档是否具有相关性,很大程度上取决于用户的主观评价,为此产生了面向用户的测度方法。
定义:
文档集合为C,查询为q,q对应的标准文档集合为R,系统检出的文档集合为A,U是用户已知的相关文档集R的子集。
设Rk为A与U的交集,就是已检出的用户已知的相关文档,Ru为检出的用户以前未知的相关文档集,如下图
覆盖率(coverage):
实际检出的相关文档中,用户已知的相关文档所占的比例。
原理如同查全率。
区别是分母是用户自己的估计,而不是公认的数据。
coverage=|Rk|/|U|
新颖率(novelty):
检出的相关文档中,用户未知的相关文档所占的比例。
novelty=|Ru|/(|Rk|+|Ru|)
相对查全率:
系统检出的相关文档的数量与用户期望检出的相关文档的数量之比。
若用户全部找到,则相对查全率为1。
查全率负担:
用户期望检出的相关文档的数量与要检出这些文档所需检索文档的总数。
7、能写出web爬虫(crawler)的深度、广度优先对网页的算法。
DFS:
PROCEDURESPIDER(G,{SEEDS})
InitializeCOLLECTION<
bigfileofURL-pagepairs>
//结果存储
InitializeVISITED<
bighash-table>
//已访问URL列表
ForeveryROOTinSEEDS
InitializeSTACK<
stackdatastructure>
//待爬取URL栈
LetSTACK:
=push(ROOT,STACK)
WhileSTACKisnotempty,
DoURLcurr:
=pop(STACK)
UntilURLcurrisnotinVISITED
insert-hash(URLcurr,VISITED)
PAGE:
=look-up(URLcurr)//爬取页面
STORE(<
URLcurr,PAGE>
COLLECTION)
ForeveryURLiinPAGE,//链接提取
push(URLi,STACK)
ReturnCOLLECTION
BFS:
bigh
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Web 信息 检索 复习题 word 打印
![提示](https://static.bingdoc.com/images/bang_tan.gif)