Web信息检索复习题2011 word打印版 - 图文

基于Web的信息检索和知识发现(复习题2011)

去年的重点 1 、2、 4 、5 、6 、7 、11 、12 、15 、19 、22 一、问答题 （70分 10题*7分） 1、 2、 4 、5 、6、15、22 二、算法题 （30分 3题*10分） 7 、8 、11、12、14、19

1、web 搜索引擎一般有哪3个部分组成（Web网页收集，中间的索引处理和对用户查询的检索排序）,能叙述各自的主要功能。

答：搜索引擎一般有信息搜集模块、预处理模块和检索服务三部分组成。

信息搜集模块负责以合适的策略漫游网络搜集网页数据，填充本地原始网页库和网页结构库。

预处理模块负责对搜集到的原始网页进行净化、消重、正文抽取、分词和关键词提取等处理，建立网页的倒排索引；进行链接分析，计算网页的Page Rank值。

检索服务模块负责与用户交互，根据用户的查询在索引库中快速检索文档，计算各检出文档与查询的相关度，对结果进行排序后展示给用户。

2、信息检索系统的数学模型是怎么描述的，能给出数学模型中的参数的含义？ < D, Q, F, R(qi,dj) >

答：信息检索模型（IR model），依照用户查询，对文档集合进行相关排序的一组前提假设和算法。 IR模型可形式地表示为一个四元组 < D, Q, F, R(qi,dj) >

其中D是一个文档集合，Q是一个查询集合，F是一个对文档和查询建模的框架，R(qi,dj) 是一个排序函数，它给查询qi和文档 dj 之间的相关度赋予一个排序值。

3、信息检索的两种不同检索形式及含义。

答：a) 特别检索(ad hoc retrieval)，用户可以不断地提出新的检索需求或新组合，检索系统中的文献不变；如Google，Baidu，Bing? b) 用户的检索需求描述是固定不变的，当得到新的文档后，把与用户需求相关的文档留下，并分类和排序后提交给用户；如股票，新闻，天气，航班

4、简述布尔与向量空间模型 (VSM) ,向量是如何产生的，其中包括文挡的向量表示方式, tf, idf的含义 （看课件）,以及如何计算向量之间的相似度的方法。这种方法的优缺点是什么？

当维数比较大时，利用隐性语义索引模型降维的方法是什么？其数学原理是什么？(见课件)

附：基本符号解释，便于理解，答案中不用写 a) ki 表示一个标记词 b) dj 表示一个文档

c) t 表示所有文档的数目

d) K = (k1, k2, ?, kt) 表示所有标记词的集合 e) wij >= 0 表示关键词 ki 相对文档 dj 的权重 f) wij = 0 若ki 不在dj 中。

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相关，否则为不相关。

例

?1 if ?qcc|(qcc?qdnf)?(?ki,gi(dj)?gi(qcc))sim(dj,q)???0 otherwise

dj?{0,1,0},q?(ka?kb)?(ka?not kc) 虽然文献包含了kb, 但 sim(dj,q) = 0.

优点：简单、易理解、简洁的形式化。

缺点：准确匹配，信息需求的能力表达不足。不能输出部分匹配的情况，无法排序，用户必须会用布尔表达式提问，一般而言，

检出的文档或者太多或者太少。

向量空间模型(Vector Space Model, VSM)

相比于布尔模型要求的准确匹配, VSM模型采用了“部分匹配”的检索策略（即：出现部分索引词也可以出现在检索结果中） 通过给查询或文档中的索引词分配非二值权值来实现

优点：帮助改善了检索结果。部分匹配的文档也可以被检索到。可以基于向量cosine 的值进行排序，提供给用户。 缺点：这种方法假设标记词是相互独立的，但实际可能不是这样，如同义词、近义词等往往被认为是不相关的词

（2）向量是如何产生

去停用词(stop word):指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a, it等；在中文中常见的有“是”，“的”，“地”等

选索引词(标引词/关键祠):可以用于指代文档内容的预选词语,一般为名词/名词词组 词干提取:在英文中，countries => country，interesting => interest

中文切词/分词(word segmentation):主要在中文信息处理中使用，即把一句话分成一个词的序列。如“网络与分布式系统实验室”分词为“网络/与/分布式/系统/实验室/”。

（3）tf, idf的含义

tf: the term frequency within a document这个词在一个文件的频率 idf: the inverse document frequency文档频率 定义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）计算向量之间的相似度的方法

相似度计算公式为：

sim(dj,q)??wi?1ti?1ti,j?wi,q?wi2,q

（5）当维数比较大时，利用隐性语义索引模型降维的方法

隐性语义索引模型Latent Semantic Indexing 问题描述：

一般文档的特征表示维数都很高，对文本常是上万维，对图像也常是50-60多维，带来问题： 1）向量中0很多，即稀疏性 2）存储空间要求很大

3）虽然说维数也多，似乎对文档的特征描述越全面，但由于数据的稀疏性，有时维数大，计算的效果不一定比维数小的好 能否去掉一些线性相关的向量来减少维数 (线性代数中的矩阵特征向量！)

?w2i,j（6）数学原理

矩阵向量的乘积

?300??1??0??0??2??????????x?S??020v?0v?1v?01?4???2??3?????6??0??0??1???? ?000?? 具有特征值3，2，0；对应的向量有 ?? ?? ??

例如向量可以看出是特征向量的组合x = 2v1 + 4v2 + 6v3

这样矩阵-向量乘积可以用特征值和特证向量表示出来

Sx?S(2v1?4v2?6v3)虽然向量x是任意的，但Sx则是也是由特征值和特征向量的组合所决定的 矩阵的奇异值分解

对任意m n矩阵A，A的秩为r，均可分解为两个正交矩阵和一个对角矩阵的乘积 (Singular Value Decomposition SVD) A?U?V ?是r r的对角阵 U 的列向量是由AAT的相互正交的特征向量组成(m r) V 的列向量是由ATA的相互正交的特征向量组成(r n) Eigenvalues 1 ? r of AAT are the eigenvalues of ATA

TSx?2Sv1?4Sv2?6Sv3?2?1v1?4?2v2?6?3v3

?i??i2r 满足 1

SVD can be used to compute optimal low-rank approximations. Approximation problem: Find Ak of rank k such that

??diag??1...?r?????...???0Ak? 其中F为Frobenius范数，形式为

A and X are both m n matrices. Typically, want k << r.

通过SVD实现Low-rank approximations.

X:rank(X)?kminA?XFAF???ai?1j?1mn2ij Ak?U diag(?1,...,?k,0,...,0)VT set smallest r-k singular values to zero

LSI 是在SVD的基础上,只保留最大的k个奇异值, 而忽略较小的奇异值,从而达到进一步降维,即前面讲的近似方法。

Ak??i?1?iuiviTk具体做法是:SVD得到的 ,只保留最大的k个奇异值得到 ’,进行奇异分解的反运算, 得到 A 的近似矩阵

5、因为字符串操作是信息检索的关键性计算，能掌握常用的对字符串处理的算法，包括字符串匹配算法，k-近似匹配算法和求两字符串A,B之间的最大公共子串的算法。能写出具体的算法以及这些算法在文本和图像检索中的应用。 答：（1）字符串匹配算法 1） Simple String Matching

Input: P and T, the pattern and text strings; m, the length of P. The pattern is assumed to be nonempty. Output: The return value is the index in T where a copy of P begins, or -1 if no match for P is found. 具体算法描述：

Notation for patterns and text P the pattern being search for; T the text in which P is sought; m the length of P n the length of T, not known to the algorithm; m <= n; j current position within in T k current position within in P

pi ti the ith characters in P and T are denoted with lowercase letters and subscripts int simpleScan(char[] P,char[] T,int m){ int match; //value to return. int i,j,k; /*i is the current guess at where P begins in T;*/ match = -1; /*j is the index of the current character in T */ j=1;k=1; i=j; // k is the number of chars compared // while(endText(T,j)==false){ /*not reach the end of T*/ if( k>m ){ /* m is the length of P*/ match = i; //match found. // success case // break; /*exit the loop here*/ }

if(tj == pk) { j++; k++;} else{

//Back up over matched characters.

int backup=k-1; //从本次查询点的下一个顶点开始// j = j-backup; k = k-backup;

//Slide pattern forward,start over. j++; i=j; } }

return match; }

算法复杂度分析：最差

?(mn) 例如P=aaab, T=aaaaaaaaaaaaaaaaaaaaaaaaaaaaab时

（2）k-近似匹配算法

KMP算法：

首先求fail数组，fail[i]=j，第i个字符匹配失败，则回退到第j个字符。

?(m?n)void kmpSetup(char[] P, int m, int[] fail){ //m是P的长度 int k,s; fail[1]=0; /*start point*/ for(k=2;k<=m;k++){ s=fail[k-1];

P: Fail: Index: A 0 1 B 1 2 A 1 3 B 2 4 A 3 5 B 4 6 C 5 7 B 1 8 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

int kmpScan(char[] P,char[] T,int m,int[] fail){ int match,j,k; match= -1; j=1; k=1; while(endText(T,j)= =false){ if(k>m){ //success match = j-m; break; } if(k= =0) //the point of T moves ahead, and rescan// j++; k=1; else if(tj= =pk) // success at position k of P j++;k++; else //Follow fail arrow. k=fail[k]; // fail and go back to the point of P // //continue loop. } return match; }

（3）求两字符串A,B之间的最大公共子串的算法

PK算法 O(m+n)

设∑代表字符集合,?x??， 定义函数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

The name of the difference is the operation needed on T to bring it closer to P. Revise: The corresponding characters in P and T are different; Delete: T contains a character that is missing from P Insert: T is missing a character that appears in P Difference table

D[i][j]=the minimum number of difference between P1,?,Pi and a segment of T ending at tj. 1≤i ≤m, 1≤j≤m. 定义：D[0][j]=0; D[i,0] = i;

There will be a k-approximate match ending at tj for any j such that D[m][j]≤k, so we can stop as soon as we find an entry less than or equal to k in the last row of D, which is the first

k-approximate match. The rules for the computation of D D[i][j]取运算得到四个数字中的最小值

D[i][j] = D[i-1][j-1] if pi = tj /*no error*/ D[i][j] = D[i-1][j-1]+1 if pi <> tj and revise both i and j increase; D[i][j] = D[i-1][j]+1 if insert into T, only i increase.

D[i][j] = D[i][j-1]+1 if delete a letter from T only j increase.

LCS最大公共字串 Longest-Common-Subsequence

Let F[i,j] denote the length of the longest common subsequence of the first i elements of A and the first j elements of B. The objective of the LCS problem is to find F[n,m].

0if i?0 or j?0??F[i,j]??F[i?1,j?1]?1 if i,j?0 and xi?yj?max{F[i,j?1],F[i?1,j]} if i,j?0 and x?yij?

（4）算法在文本和图像检索中的应用

6、能给出信息检索中常用的测度，如查全率、查准率和F1计算公式。知道11个标准查准率是如何规定的，查准率直方图、E测度指标的含义是什么？面向用户的测试集合及信息检索系统的性能是如何确定的？对目前常用的MRR, NDCG 的测度又是怎样定义的？它们考虑的评测要点是什么？

答：对某个测试参考集,信息查询实例为I，I对应的相关文档集合为R。假设用某个检索策略对I进行处理后，得到一个结果集合A。令Ra表示R与A的交集。

查全率(Recall)：检出的相关文档个数与相关文档集合总数的比值，即R=|Ra|/|R|

Ra 查准率(Precision)：检出的相关文档个数与检出文档总数的比值，即P=|Ra|/|A|

F1标准则综合了精度和查全率，将两者赋予同样的重要性来考虑。F1的计算由下面的公式决定

R A F(i,j)?2?recall(i,j)?precision(i,j)recall(i,j)?precision(i,j)

F?211?rp 查准率与查全率的调和

平均数

查准率/查全率曲线

11点标准查全率下的查准率曲线，计算查全率分别为(0%,10%, 20%,?, 100%)下的查准率。即利用查全率，限制一下文档数，以此计算查准率。

多个查询下的查准率/查全率曲线，可通过计算其平均查准率得到，公式如下

MAP?P(r)??i?1Nq (Nq为查询的数量)

P(r) 是指查全率为r时的平均查准率, Pi(r)指查全率为r时的第i个查询的查准率

由于每个查询的查全率值不一定就是这11个标准查全率，因此需要对查准率进行插补。第j个标准查全率水平的查准率是介于第j个和第j+1个查全率之间任意一个查全率所对应的查准率的最大值。 R-查准率 p@R，计算序列中第R个位置文献的查准率。R是指与当前查询相关的文档总数。 查准率直方图

用于快速比较两个检索算法的性能

多个查询下，分别计算每一查询下的R-查准率，计算其差值，并用直方图表示。

1.51.0Pi(r)NqR-Precision A/B0.50.012345678910-0.5-1.0-1.5Query Number

具体地：用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；

1?b2b>1表明用户对查准率更感兴趣 E?1?2b1b<1表明用户对查全率更感兴趣

?

rpMRR (第1个相关结果位置的倒数平均，Mean Reciprocal Ranking)：所有查询的第一个相关结果位置倒数的

平均；MRR=0.5,意味着检索列表中前2项有相关文档。

MRR?1?q?1rankqnn ranki 第i个查询所排的位置

NDCG (Normalized discounted cumulative gain)

NDCG方法在实际计算中分为三个步骤，分别为CG、DCG以及NDCG Cumulative Gain(CG)：位于位置1到p的检索结果的相关度之和

reli表示第i个文档与查询语句的相关度，缺点：未考虑位置关系

Discounted Cumulative Gain(DCG) 基本思想，若搜索算法把相关度高的文档排在后面，则应该给予惩罚。一般用log 函数表示这种惩罚

CGp??relii?1p另一种计算公式为：更强调前面的文档重要性

reliDCGp?rel1??i?2log2i

ppNDCG(Normalizing DCG) 检索结果与具体查询以及序列的长度有关。为了规范化，我们把检索结果进行从大到小排序得到理想的输出序列。在这个理想的序列上计算DCG, 得到在位置p的ideal DCG(IDCG)

2reli?1DCGp??i?1log2(1?i)

nDCGp?DCGpIDCGp

面向用户的测度方法

一篇文档是否具有相关性，很大程度上取决于用户的主观评价，为此产生了面向用户的测度方法。定义：文档集合为C，查询为q，q对应的标准文档集合为R，系统检出的文档集合为A，U是用户已知的相关文档集R的子集。设Rk为A与U的交集，就是已检出的用户已知的相关文档，Ru为检出的用户以前未知的相关文档集，如下图 相关文档|R| 检出的文档|A| 用户已知的相关文档|U| 检出的用户已知的相关文档|Rk| 检出的用户未知的相关文档|Ru|

覆盖率(coverage)：实际检出的相关文档中，用户已知的相关文档所占的比例。原理如同查全率。区别是分母是用户自己的估计，而不是公认的数据。coverage=|Rk|/|U|

新颖率(novelty)： 检出的相关文档中，用户未知的相关文档所占的比例。 novelty = |Ru|/(|Rk|+|Ru|)

相对查全率：系统检出的相关文档的数量与用户期望检出的相关文档的数量之比。若用户全部找到，则相对查全率为1。 查全率负担：用户期望检出的相关文档的数量与要检出这些文档所需检索文档的总数。

7、能写出web 爬虫( crawler) 的深度、广度优先对网页的算法。 答：DFS: PROCEDURE SPIDER(G, {SEEDS})

Initialize COLLECTION //结果存储 Initialize VISITED //已访问URL列表 For every ROOT in SEEDS Initialize STACK //待爬取URL栈 Let STACK := push(ROOT, STACK) While STACK is not empty, Do URLcurr := pop(STACK) Until URLcurr is not in VISITED

insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr)//爬取页面 STORE(, COLLECTION) For every URLi in PAGE,//链接提取 push(URLi, STACK) Return COLLECTION

BFS:

PROCEDURE SPIDER(G, {SEEDS})

Initialize COLLECTION //结果存储 Initialize VISITED //已访问URL列表 For every ROOT in SEEDS Initialize QUEUE //待爬取URL队列 Let QUEUE := EnQueue(ROOT, QUEUE) While QUEUE is not empty, Do URLcurr := DeQueue(QUEUE) Until URLcurr is not in VISITED insert-hash(URLcurr, VISITED) PAGE := look-up(URLcurr)//爬取页面 STORE(, COLLECTION) For every URLi in PAGE,//链接提取 EnQueue(URL, QUEUE) Return COLLECTION

8、能给出Google PageRank 算法和HITs 算法的思想，其中包括基本概念和计算公式。 答：（1）Google PageRank 算法

基本思想：基于\从许多优质的网页链接过来的网页，必定还是优质网页\的回归关系，来判定所有网页的重要性 PageRank算法1

PR(A)?(1?d)?d(PR(T1)/C(T1)???PR(Tn)/C(Tn))?(1?d)??i?1PR(Ti)/C(Ti)nPR(A)表示页面A的级别，页面Ti链向页面A， C(Ti) 是页面Ti链出的链接数量

d取值在0到1之间，d也称为阻尼系数，由于用户不可能无限的单击下去，常常因劳累而随机跳入另一个页面 d则是页面本身所具有的网页级别。 PageRank算法2

PR(A)?(1?d)/N?d(PR(T1)/C(T1)???PR(Tn)/C(Tn)) 其中N是互联网上所有网页数量

矩阵形式：

Aij＝1 if (页面i链接页面j) otherwise 0

计算PageRank值：其中R是将A转置后各个数值除以该列的非零元素个数

?nTTA(j,i)?C(T) S(i,j)?A(i,j)/C(Tj)ij?1R0?S

Loop：

T

- initialize vector over web pages

- new ranks sum of normalized backlink ranks - compute normalizing factor - add escape term

- control parameter

Ri?1?ARi

d?Ri1?Ri?11Ri?1?Ri?1?dE

while

??Ri?1?Ri

???

- stop when converged

（2）HITs 算法

可见平均的分布权值不符合链接的实际情况，由此产生了HITS算法。

权威网页：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种网页称为权威(Authoritive)网页。

Hub网页：提供指向权威网页的链接集合的WEB网页，它本身可能并不重要，或者说没有几个网页指向它，但是它提供了指向就某个主题而言最为重要的站点的链接集合，比如一个课程主页上的推荐参考文献列表。 在HITS算法中,对每个网页都要计算两个值:权威值(authority)与中心值(hub)

计算过程有两个步骤：I步骤和O步骤。在I步骤中每个页面的Authority值为所有指向它的页面的Hub值之和。在O步骤中每个页面的Hub值为所有指向它的页面的Authority值之和。定义如下：

ai?I步骤： O步骤： 初始时: h(v)＝a(u)＝1

HITS算法迭代计算这两个步骤，直到两个数值最后收敛为止。HITS算法是在线计算的，算法的开销比较大，对每次的查询都需要临时的计算。 HITS算法的评价

若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和) 若一个网页指向许多好的权威页，则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)

j?B(i)?hjhi?j?F(i)?ajHITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。

（3）

9、给出Trie的定义，并能根据给定的文档集合，画出相应的Trie，以及如何利用Trie计算tf值；能给出Trie上的搜索算法。

答：Trie，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 令S是取自∑的n个串的集合，d = |∑|,满足S中任意串不是另一串的前缀。S的一个标准trie是一有序树，满足： 除根外，每个定点的标记是∑中的字符 T中的内部顶点的排序按∑的顺序(字典序)

T有n个叶子顶点，从根到叶子的路径的顶点标记对应S中的一个串。 它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 每个节点的所有子节点包含的字符都不相同

Trie搜索算法：给定一个单词，从根节点开始，顺着可以匹配单词字符序列的路径走。如果能够到达一个叶子且字符序列也刚好匹配完，则搜索成功返回叶子上的信息即可；否则Trie中无此单词。 伪代码：

Starting at the root, follow the path that matches the chars of the word in a trie.

if a leaf node is reached, success else there is no the word in the trie

在拼音输入法，中文分词，汉语词典等很多方面可以用到Trie。 标准Trie的构造：

空间复杂度O(n)，支持在O(dm)时间内的搜索、插入和删除

n是S中字符串的总长度，m是操作中字符串参数的长度，d是字典的大小

10、给出利用signature和倒排文档建立文档索引方法的原理性说明和举例说明。

答：索引是基于未来可能查询的“项”（terms）,来自文本中的所有词

Signature

对每个项，给出长度为s的向量（hash函数值）

把一篇文档中的所有词的向量进行OR操作，得到的向量为文档的签名。 长文档肯定成为问题，解决的方法是分块签字。

倒排文档：

由于原理十分简单，建议举例子。涉及到两个表，词汇表和记录表。词汇表是所有Term的集合，记录表是Term在文档中出现的位置。

先将文档分词，去掉停用词等，得到关键词，然后按照（关键词-文档ID）建立索引

表，可以更具体的将词频加入索引表中。对于长文档的处理：1：分成若干块(chunk)处理 ；2：利用归并算法形成最后的索引 构建索引的算法：In-memory Inversion Algorithm Create an empty lexicon

For each document d in the collection, Read document, parse into terms For each indexing term t fd,t = frequency of t in d If t is not in lexicon, insert it

Append to postings list for t Output each postings list into inverted file For each term, start new file entry Append each to the entry Compress entry

Write entry out to file.

倒排文档查询策略：使用Trie树等数据结构，对每个Term记录所有它出现的位置。查询时可以快速地获得每个查询词的位置列表，然后在此基础上就可以完成查询指定的逻辑运算和匹配分数的计算等等。

11、能简述常见的2种以上对文本的分类/聚类算法，能给出聚类和分类的主要的异同点是什么？能说出K-means,

K-NN, SVM, 朴素贝叶斯和决策树的算法，能给出有代表性的核函数和训练与测试的步骤。能说明为什么K-means算法的初值的选取对算法聚类结果又较大的影响。 能说出上述方法中那个计算复杂性比较大，有些方法存在的问题是什么？ 答：（1）分类/聚类算法

聚类和分类的主要的异同点

分类：设C1, C2?Cn是给定的K个类，把文档集合{d1d2?dn}按距离分别放入K个类别的过程。

聚类：给定整数K，按照某种距离测度，把文本集合分成K个类和簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中文本的差别较大。

在分类中，要划分的类别是已知的，是一种“监督学习”，需要训练数据。而聚类所要划分的类别是未知的，是一种无监督学习，不需要训练数据，倾向于数据的自然划分。

（2）

①k-means

k-means是一种聚类算法，它采用一种迭代的方式，每次迭代前计算出当前聚类结果中每个类的类中心，作为新类的代表，在重新聚类时将每个文档赋给与其距离最近的那个类。迭代直至聚类结果稳定。初始的类中心通过随机挑选k个文档确定。

k-means的优点：它尝试找到使平方误差函数值最小的K个划分，当结果簇是密集的，而簇与簇之间区分明显时，效果较好；复杂度低，对大数据集有较高的效率。复杂度为O(N*K*I*D)，其中N是样本个数，K是簇数，I是迭代次数，D是特征数目。

k-means的缺点：k-means只有在簇的平均值被定义的情况下使用，要求用户必须事先给出K。不适合发现非凸面状的簇；不适合大小差别较大的簇；对于噪声和孤立点敏感。

k-means的改进方案：优化初始K个中心点的选择，先用一种方法（如层次聚类）探测数据集内的密集区域，再采用k-means来迭代优化。 ② K-NN

kNN将文档表示成为特征向量的形式，对于一篇待分类的文档，算法找到k个与其距离最近的样例文档，通过这k个邻居的投票（可按距离加权）确定此文档的类别。

score(c|x)?

其中x是未分类的新数据点；c表示类别；d是x的k个已经被分类过的近邻；sim(x,d)表示x与d的相似度；d属于类c时，I(d,c)为1，反之为0；I也可取作各类的权重。

kNN的优点：简单有效，重新训练代价低。

kNN的缺点：时空复杂性与训练集以及特征维数成正比，不适合于特别复杂或实时性要求较高的分类任务。

kNN改进：针对特征维数问题，可以对特征进行聚类，属于同一类的特征词看作是一个特征维，可以有效地提高算法的速度，且有助于区别出稀有词和低效词。 ③ SVM

对于线性分类问题，最优分类超平面要求不但可以将两类样本正确的开，而且应该使分类间距最大。假设分类超平面形式为wT·x+b=0，对wT和b进行放缩，使得每个样本(xi,yi)满足yi[(wT·xi)-b]≥1且||w||最小，此时分类间隔等于2/||w||（欧氏距离）。使间隔最大等价于求一个最小的||w||，满足这个条件的分类面叫最优分类面，间隔平面上的训练样本点就称作支持向量。分类函数由支持向量与分类实例的内积构成，表示为：

非线性可分的分类问题，总是可以通过某些变换转化为某个高维空间的线性可分问题。只是这种变换难于寻找。但由于线性SVM中的寻优函数和分类函数都只涉及样本之间的內积运算，我们只要找到一个拟合向量xi'和xj'的内积运算的函数K(xi,xj)，就可以用线性SVM的解法解答此非线性可分的分类问题，而没有必要知道变换的形式，其中x'是x在合适的高维特征空间的表示。函数K(xi,xj)就是核函数。将线性分类函数中的内基函数用和函数代替，则变为：

iiij

常用的核函数有多项式核函数，径向基函数(RBF)，Sigmoid函数。

SVM优点：具有全局优化性和较好的泛化能力。SVM缺点：计算量大复杂度高。 ④Na?ve Bayes 朴素贝叶斯分类 Na?ve Bayes方法假设实例的各个特征属性是相互独立的，训练时统计每个类别中每个属性的属性值分布情况，分类时根据统计值计算出实例属于各个类别的概率，取其中概率最大者，实际计算式为：

d?kNN of x?sim(x,d)I(d,c)f(x)?sgn(??iyixiTx?b)f(x)???yK(x,x)?bvNB?argmaxP(vj)?P(ai|vj)

其中P(ai|vj)表示类别vj中属性Ai的取值为ai的概率。 Na?ve Bayes方法对噪音数据和不相关属性都有很好的鲁棒性，可以很好地处理属性缺失情况，在某些应用中效果很好。但当属性之间近似相互独立的假设不成立时，NB方法效果不好。 ⑤ 决策树

决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。给定一个实例，决策树会将它划分到一个叶子上，就给叶子确定了类标号或类分布。决策树算法一般会使用某些启发式函数优先选取最有效的特征，以期生成的决策树能够最短。

决策树算法优点：可以生成可以理解的规则；计算量相对来说不是很大；决策树可以清晰的显示哪些字段比较重要；

决策树算法缺点：对连续性的字段比较难预测；当类别太多时，错误可能会增加的比较快，一般的算法分类的时候，只是根据一个属性来分类。不是全局最优。 （3）对于k-means

算法的初值选取不好容易使算法收敛到一个效果很差的局部最优解。

vj?Vi算法初值的选取可用以下几种方法： 随机选

分段，从每一段中随机选

最小最大原则，首先选取相距最远的两个样品为前两个聚点，而其余聚点的选取准则如下：假设已经选取了m个聚点，第m+1个聚点与前m个聚点的距离的最小值应该是剩余点中最大的。

可以首先用层次聚类方法帮助找到初始的聚类。层次聚类簇间相似度可以用Group-Average方法或Ward's Method，因其对噪音和边界点较为不敏感，也较好地保证了簇的内聚性，作为初值较为合理。

12、知道层次聚类算法大体有哪两类,并能举例说明其中有代表性的算法，知道Agglomerative Clustering Algorithm 的一般算法框架是什么以及计算两个簇之间距离的方法。能给出由上而下（Divisive）算法中有代表性的方法，如最小生成树。能否利用最小森林计算求解非层次聚类呢？

答：一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底向上的还是自顶向下形成的，层次的聚类方法可以进一步分为凝聚的（agglomerative）和分裂的（divisive）层次聚类。

凝聚的层次聚类：这种自底向上的策略首先将每个对象作为单独的一个簇，然后和并这些原子簇为越来越大的簇，直到所有的对像都在一个簇中，或者达到某个终止条件。

分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类相反，它首先将所有的对象置于一个簇中。然后逐渐细分为越来越小的簇，直到每个对象在单独的一个簇中，或者达到一个终止条件，例如达到了某个希望的簇数目或者两个簇之间的距离超过了某个阈值。 Agglomerative Clustering Algorithm 凝聚的层次聚类算法框架

1. Compute the proximity matrix 2. Let each data point be a cluster 3. Repeat

4. Merge the two closest clusters 5. Update the proximity matrix 6. Until only a single cluster remains

关键在于计算两个簇之间的距离，具体方法有： ‐ MIN 两个簇中抽取的每对样本间的最小距离 ‐ MAX 两个簇中抽取的每对样本间的最大距离

‐ Group Average 两个簇中抽取的所有样本对之间的距离的均值 ‐ Distance Between Centroids 质心间的距离

‐ Other methods driven by an objective function Ward’s Method uses squared error MST聚类是一种分裂的层次聚类方法(自上而下) Build MST (Minimum Spanning Tree)

‐ Start with a tree that consists of any point

‐ In successive steps, look for the closest pair of points (p, q), such that one point (p) is in the current tree but the other (q) is not ‐ Add q to the tree and put an edge between p and q Use MST for constructing hierarchy of clusters MST Divisive Hierarchical Clustering Algorithm

1. Compute a minimum spanning tree for the proximity graph 2. repeat

3. Create a new cluster by breaking the link corresponding to the largest distance(smallest similarity) 4. until Only singleton clusters remain

13、评价聚类的测度（如 SSE）有哪些，能给出具体的计算公式。知道如何利用相似度矩阵的可视化方法来比较和评价聚类的效果（即说明如何利用色谱在矩阵不同点的显示说明聚类的特点）。

答：Sum of Squared Error(SSE), 平方差和，点到聚类中心的距离之和。

SSE???dist2(ci,x)

设c是所有顶点的中心，并且距离计算是欧式距离，定义总的SSB

i?1x?CiKK mi表示簇i的顶点个数。SSB越大，说明簇之间的分离度越好。

若共有K个簇，并且满足mi = m/K, m为所有顶点的总数，则可定义

SSB??midist2(ci,c)i?1若定义总的平方数TSS为

K1KkmSSB?dist2(ci,cj)??2Ki?1j?1k

TSS???dist2(xi,ci) 可以证明，TSS = SSE + SSB 非监督簇评估：使用邻近度矩阵

如果给定数据集的相似度矩阵和聚类标号。显然，在理想情况下，簇内的任两顶点的相似度为１，而不同簇中的两点相似度为０.若我们将顶点按簇标号排序，则对应的相似度矩阵应为对角矩阵。在具体实现时，可以取相似度的值。我们可以把相似度的值作为图像的色彩值，这样可以通过可视化的方法评价聚类效果。

Order the similarity matrix with respect to cluster labels and inspect visually

i?1xi?Ci

14、能叙述MST, BASCAN聚类算法的思想和具体算法步骤。

答：MST聚类是一种分裂的层次聚类方法(自上而下) Build MST (Minimum Spanning Tree)

‐ Start with a tree that consists of any point

‐ In successive steps, look for the closest pair of points (p, q), such that one point (p) is in the current tree but the other (q) is not ‐ Add q to the tree and put an edge between p and q Use MST for constructing hierarchy of clusters MST Divisive Hierarchical Clustering Algorithm

5. Compute a minimum spanning tree for the proximity graph 6. repeat

7. Create a new cluster by breaking the link corresponding to the largest distance(smallest similarity) 8. until Only singleton clusters remain DBSCAN 一种基于密度的聚类算法

? Density = number of points within a specified radius(半径) (Eps)，特定半径之内点的数目表示密度

? A point is a core point if it has more than a specified number of points (MinPts) within Eps. These are points that are at the interior of a

cluster. 以它为中心如果有多于MinPts的点，那么这个点就是core，所以通常在内部。

? A border point has fewer than MinPts within Eps, but is in the neighborhood of a core point. 边界点是core点的邻居，但是以它为中心

的点的数目要小于MinPts。

? A noise point is any point that is not a core point or a border point. 噪声点 DBSCAN算法步骤：

输入：eps, minpt; 输出：聚类

‐ 根据eps, minpt，把每个顶点标记为核心、边界和噪音 ‐ 删除噪音点

‐ 为距离在eps 之内的所有核心点建立一条边 ‐ 计算图的连图分支，每个连图分支为一个簇 ‐ 对所有的边界点，随机地指派一个与之关联的簇

15、能给出XML文档的基本概念，如DOM Tree，Xpath, XML schema, NEXI, XML 能简述XML文档检索与对一般文本检索的不同。（XML是半结构化文档,而一般文本文档是无结构的，XML检索是检索出可以匹配的部分，而不是整个文档）。半结构化文档在表示方法上和无结构文本的表示有什么区别，为什么it,idf表示不能简单地应用？你认为如何对XML文档进行索引，对XML文档的检索排序应该考虑那些因素？ 对XML等半结构化文档，如何计算文档之间的相似度？

答：(1)XML文档的基本概念，如DOM Tree，Xpath, XML schema, NEXI, XML

XML文档是一棵有向标记树，树的结点被称作XML元素(Element)，每个元素可以有一个或多个属性(attribute)。我们称XML Retrieval为结构化检索或半结构化检索。

DOM Tree是一种标准的访问和处理XML文档的方法，它把XML文档表示成树的形式，XML文档中的每个元素、元素的属性和元素中的文本都表示成树中的节点。

XPath是一种标准的XML路径。例如：act/scene会选择出所有act元素下的scene元素。 XML schema针对特定的应用对XML文档的结构加上一些约束。XML schema存在两个标准：XML DTD(document type definition)和XML Schema。

NEXI(Narrowed Extended XPathI)是通用的XML查询方式，使用类似XPath的语法表示结构信息。例如：//article[.//yr=2001 or .//yr=2002]//section[about(.,summer holiday)]表示从2001年和2002年的articles中选择出和summer holiday有关的sections。 (2)XML文档检索与对一般文本检索的不同

1. 在普通的IR系统中检索返回整个文档，而XML检索中返回文档中与查询最接近的一部分 2. 建立索引时，不是以文档为单位，而是以文档中的一个unit作为基本的单元

(3)半结构化文档在表示方法上和无结构文本的表示有什么区别

(4)为什么不能用tf*idf ？？

XML中没有document unit，基于全局文本计算出的tf*idf没有实际意义，每个词出现的位置不同具有不同的意义。

Vector spaces and XML：不仅仅考虑内容，还应该将XML的结构位置等信息考虑进去，如：按路径的分解表示XML文档，还可以利用子树或路径表示文档和查询，在XML查询中利用树/路径的匹配。 (5)XML文档的索引方法

索引单元：对XML文档中的节点进行分组，各组不相交叠，将每个组看作一个文档建立索引。如上页图中books, chapters and sections均被当作无重合的索引单元。 四种不同的索引方式

? 对XML文档中的节点进行分组，各组不相交叠，将每个组看作一个文档建立索引 ? 将最大的元素作为索引单元

? 利用DOM中所有叶子节点建立索引 ? 将所有元素建立索引 索引中的一些限制策略

? discard all small elements

? discard all element types that users do not look at (this requires a working XML retrieval system that logs this information) ? discard all element types that assessors generally do not judge to be relevant (if relevance assessments are available) ? only keep element types that a system designer or librarian has deemed to be useful search results (6)对XML文档的检索排序应该考虑那些因素

(7)对XML等半结构化文档，如何计算文档之间的相似度？ XML文档之间相似度的计算

可以使用改造的向量空间模型来计算XML检索中文档的相似度。首先将查询和文档都表示成树或者路径集合的形式，定义查询树中路径cq 和文档树中路径cd 的相似度如下：

?1?|cq|?CR(cq,cd)??1?|cd|?0??ifcqmatchescd?? 其中|cq | 和 |cd |是相应路径中的节点数 ??查询和文档的相似度可以采用一种余弦相似度的变体，计算公式如下：

Sim(q,d)???CR(ck,cl)?weight(q,t,ck)ck?Bcl?Bt?Vweight(d,t,cl)?c?B,t?Vweight(d,t,c)2 其中V 是非结构化词项词典；B 是所有可能的路径集合；weight(q,t,c)和weight(d,t,c)分别表示结构化词项在查询q 和文档d 中的权重。

(半)结构化文档的相似度计算：

? 基于路径匹配 ? 基于树的匹配

? 基于树之间的子树匹配

首先XML文档是结构化，文档中的每个节点都有特定的语义，传统的Bag-Of-Words模型不能直接使用在文档上。第二，XML检索应该返回与用户查询相匹配的文档片段，而不是整个XML文档。第三，XML检索中的查询应该允许包含目标的结构信息。

对XML文档中的节点进行分组，各组不相交叠，将每个组看作一个文档建立索引。简单地可以把DOM中的每个叶子节点当作一个分组。索引中还应包含有路径信息，可以快速地计算节点间的关系。

16、能给出两种以上的色彩空间的定义及转换方法，能说明对彩色图像转换成灰度图的公式；能说明如何利用颜色直方图进行图像检索色的思路和算法。

答：两种颜色空间：

A. RGB颜色空间：RGB对应红绿蓝三种原色光，自然界的所有颜色都可以用这三种光混合而成。在描述时，用R、G、B作为

相互垂直的坐标轴来表示，是一种加光模式。不符合人对颜色相似性的视觉感知。

B. HIS颜色空间：原理是人的视觉对亮度的敏感 程度远强于对颜色浓淡的敏感程度。色调(Hue)是从物体反射或透过物体传播

的颜色。在0°到360°的标准色轮上，按位置度量色相。饱和度(Saturation)是指颜色的强度或纯度。饱和度表示色相中灰色分量所占的比例，它使用从0%(灰色)至100%(完全饱和)的百分比来度量。在标准色轮上，饱和度从中心到边缘递增。亮度(Intensity)是颜色的相对明暗程度，通常使用从0%(黑色)至100%(白色)的百分比来度量。

RGB图像转换为灰度图：灰度值Y = 0.299 * R + 0.587 * G + 0.114 * B

颜色直方图 横坐标是颜色区间，纵坐标是这种颜色的像素在图像中占的比例。

颜色直方图检索的基本思路：将用户输入的图像和图像库中的图像都表示成K 级颜色直方图，然后根据某种相似度度量方法计算查询图像和库中图像的相似度，对结果进行排序，用一个阈值进行截尾，将最终结果返回给用户。相似度度量方法有直方图交叉值，直方图欧氏距离等。 算法描述：

? selection of a color space选择颜色空间

? quantization of the color space量化颜色空间

– Gray value images – one histogram – RGB : three histograms

– HSI : three histograms, but I is often ignored

? computation of histograms计算直方图

? choose a histogram distance function and similarity computation formula 相似度计算

17、如何把用户的反馈引入到计算用户需求与图像之间的相似度计算的？其计算公式是什么？你能否给出更合理的公式？

答：用Q表示用户检索的目标，用g表示到目前为止用户变换使用的输入图像的个数，qj为第j个输入图像，那么在当前一幅图像x与目标Q的相似度计算如下：

Dist(x,Q)?g?gj?11/dist(x,qj)2

排序选择前K个作为输出

18、简述图像的纹理是什么概念，能给出1种方法对纹理进行描述的方法？知道图像的灰度共现矩阵的定义和计算方法，以及基于共现共现矩阵中的几个统计量所表示的图像纹理特征。

答：纹理一般是指图像中反复出现的局部模式和它们的排列规则，可以作为图像的特征来计算图像的相似度。已存的纹理分析的方法有基于马尔可夫随机场的方法、基于统计特征的方法、灰度共现矩阵（GLCM）等。 纹理特征的描述

1. 基于灰度共现矩阵的纹理特征

常用统计量：对比度、相关度、方差、熵等

多尺度：改变方向和步长生成不同尺度的共现矩阵 2. 基于邻域灰度差别矩阵的纹理特征

包括稀疏度、繁忙度、纹理力度等5个特征 3. Tamura纹理特征

稀疏度、对比度、方向性、线状性、规则性及粗糙度 这是一组与人类视觉特性对应的纹理特征

灰度共现矩阵Gray-level co-occurrence matrix(GLCM)

思想：用不同邻接level灰度值的个数刻画图像的纹理特征，用有限的矩阵关系(number of level)，表现纹理特征，并能在此基础上给出更多的统计量，来刻画图像的纹理。

它是一个二维的矩阵，若把灰度分成n阶，GLCM是n×n矩阵G，分量cij表示灰度值i和灰度值j以某种空间关系(四种方向{(0,1) (1,0)(0,-1)(-1,0})共现的次数。其中空间关系可以用一个位移向量的形式给出。在此矩阵上，可以计算纹理的对比度、同质性和关联性等特征。

基于灰度共现矩阵中的统计量所表示的图像纹理特征

能量(Energy)：是灰度共生矩阵元素值的平方和，所以也称能量，反映了图像灰度分布均匀程度和纹理粗细度。如果共生矩阵的所有值均相等，则ASM值小；相反，如果其中一些值大而其它值小，则ASM值大。当共生矩阵中元素集中分布时，此时ASM值大。ASM值大表明一种较均一和规则变化的纹理模式。

熵(Entropy)：当共生矩阵为稀疏矩阵（大部分为0时），熵趋向于0;反之，若矩阵中的元素几乎相等时，说明图像中有许多细纹理，熵较大。

对比度(Contrast)：反映了图像的清晰度和纹理沟纹深浅的程度。纹理沟纹越深，其对比度越大，视觉效果越清晰；反之，对比度小，则沟纹浅，效果模糊。灰度差即对比度大的像素对越多，这个值越大。灰度共生矩阵中远离对角线的元素值越大，CON越大。 关联性(Correlation)：它度量空间灰度共生矩阵元素在行或列方向上的相似程度，当矩阵元素值均匀相等时（灰度分布比较均匀），相

关值就大;相反，如果矩阵元素值相差很大则相关值小。如果图像中有水平方向纹理，则水平方向矩阵的COR大于其余矩阵的COR值。

19、能给出Split-and-Merge Algorithm。若得到区域（region）描述，你能否转换成轮廓描述？若可以，请给出具体的算法，并说明轮廓线是如何表示的。

答：区域(region)是满足以下两个条件的相连像素集：

‐ 同质性：区域内任意两个像素的差值不大于指定的域值ε ‐ 不可再扩大：相邻两个区域的像素点的集合必定不满足同质性 Split-and-Merge Algorithm

第一步是分裂操作：开始，整个图像被看作是候选区，如果候选区不满足同质标准，将他分为四个更小的候选区，重复过程直到没有候选区可以分割。由上而下的，通过对图像进行划分来发现同质的区域

第二步是合并：检查每两个相邻的候选区，如果将之合并成一个候选区不违反同质条件，则将它们合并。由下而上地，通过对邻近同质的区域的合并满足第2个性质。 具体的算法描述：

– 首先，执行分割

– 算法开始，把整个图片看做候选区域

– 如果候选区域不满足同质性，则将其分割成为四个更小的候选区 – 重复执行直至候选区域不能再被分割 – 执行合并

– 检查每对邻接的区域，若合并两个区域不违反同质性则执行合并操作 转换为轮廓描述

用Chain Codes可以把区域转化成轮廓描述。顺时针遍历轮廓上所有像素，从一个像素到下一个像素可能的方向只有八种，用一个数字串记录遍历所走的方向序列即可。

20、能给出具体利用chain Codes对给定的轮廓线进行描述的实施方法（如对方向的确认），以及利用Chain Code进行对象之间相似度计算的方法。

答：Chain Code是轮廓线上局部方向的有序排列，每个像素点的邻居节点有8中可能的位置，所以像素点有8种可能的局部方向。 沿着轮廓线顺时针移动，确定每一个点的Code值，最终得到Chain Code. 下图依次为：Code-方向对应表，轮廓线，对应的Chain Code

相似度计算 此处计算dissimilarity(差异性) (Chap. 17 P32)

对于两个Chain Code，A=a1a2…an, B=b1b2…bm，将A变成B需要三种操作，即字符的插入、删除和替换。 Dissimilarity = minimum number of edit steps 最小操作数

21、在对基于空间关系的图像表示中，对给定的n个对象，会用2-D字符串表示它们的位置关系，以及如何计算相似度的方法。

答：答：一个2D字符串由一个u串和一个v串表示，u串表示了对象在横轴上的投影的位置关系，v串表示对象在纵轴上的投影的位置关系。其中用‘<’表示‘有序’，用‘=’表示‘重叠’，用‘：’表示‘在同一个集合里’。2D字符串间的相似度可以用其最长公共子串的长度来衡量，计算方法见第6题(字符串的匹配)。 空间关系：(x方向，y方向)

空间关系的相似性度量

2D String的最大公共字串(LCS) 详细见第6题 利用面积计算基于位置的图像相似度

area (O?R) O: a query region；R: a segmented region

area RThe similarity measure should be larger than 0.25.

22、能说明什么是对图像的文本标注，能给出一种对图像的标注的具体方法，能说明所给方法适用的前提和存在的难点。当图像都有标注时，你认为图像之间的相似度应怎么计算？若把已经正确标注的图像作为训练集合时，你能否给出一种学习方法，为新图像自动产生标注？

答：答：图像的文本标注是能够描述图像内容的一组词汇，回答了“what’s in the picture” 图像标注的方法(协同标注的方法) ‐ 建立适当规模的训练集合 T-Set

? 目前Web上有多个公共标注好的图像集合，图像的标注是正确的。

‐ 把新图像p计算和训练集中的图像一样的视觉特征描述（如图像的颜色直方图，纹理其他编码方式）；

‐ 利用k-近邻算法计算p在T-Set中的k近邻，从k近邻图像的标注中，利用标识词的词频和相关关系产生p的标注。 图像之间相似度的计算：已知图像的标注词向量，类似第5题中文档的相似度计算方法 图像语义自动标注的方法

CBSA分三个步骤实现。首先，人工对训练集中的图像进行标注，从预先定义的K个关键词中选择与图像匹配的关键词。然后，利用已标注好的示例图像集合，应用Bayes Point Machine(BPM)和SVM训练K个分类器。最后，使用分类器自动地标注未标注的图像。每幅图像由K个分类器分类并赋一个概率值，以用来表示图像与该关键词的关联程度。最终完成对图像库的初始标注。