向量空间模型

向量空间模型《网络信息内容安全》讲义/张华平/2010-10第1页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型向量空间模型是最常用的检索模型（Salton等人，1975年）思想：文章的语义通过所使用的词语来表达方法:每一篇文档用一个向量来表达，查询用一个向量来表达，通过向量的方式来计算相似度。第2页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10查询文档1文档2文档3<q0,q1,q2,…qn,><d1,0,d1,1,d1,2,…d1,n,><d2,0,d2,1,d2,2,…d2,n,><d3,0,d3,1,d3,2,…d3,n,>向量空间模型第3页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型主要涉及两方面的工作：（1）如何构建一个向量来表示文档中的词项，构建另一个向量来表示查询中的词项.（2）如何来度量任意文档向量和查询向量的相似度第4页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量对于文档集中每一个不同的词项（或概念），我们在向量中只记录一个分量。当词项出现时，就在对应向量的分量处记1；如果词项未出现，就在对应的分量处记0。第5页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量

文档：D1D3D2QAA,IIA,I文档向量：D2=<1,0>D3=<0,1>Q

=<1,1>D1=<1,1>D1,Qxy1D2D31第6页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10二值表示方法并没有考虑一个词项在文档中出现的次数。通过扩展这种表示形式，我们将词项在文档中出现的频率作为向量中各个分量的值。在上例中，如果文档D2中A出现了两次，向量可以表示为<2,0>。

向量空间模型

——构建向量第7页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10除了简单地给出查询词列表外，用户通常还会给出权重，该权重表示一个词项比另外一个词项更重要。思想：不频繁出现的词的权重应该比频繁出现的词的权重更高。方法：人工赋值—在初始查询中用户人工指定词项权重来实现的。

自动赋值—通过基于词项在整个文档集中出现的频率。

向量空间模型

——构建向量第8页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量我们采用稍大一些的例子来展示如何使用基于数据集频率的权重。

t —— 文档集中不同词项的个数。 —— 词项tj在文档Di中出现的次数，也就是词频。 —— 包含词项tj的文档的篇数。—— ，其中d表示所有文档的篇数。这就是逆文档频率。

第9页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10对于每一篇文档向量，都有n个分量。向量中的每个分量为在整个文档集中计算出来的每个词项的权重。在每篇文档中，词项权重基于词项在整个文档集中出现的频率情况以及词项在某一个特定文档中出现的频率自动赋值。

向量空间模型

——构建向量第10页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量对于文档中词项的权重因素，主要综合考虑词频和逆文档频率。文档i对应的向量中第j个词条的值：查询Q和文档Di的相似度可以简单地定义为两个向量的内积。

第11页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10Q：“goldsilvertruck”D1：“Shipmentofgolddamagedinafire”D2：“Deliveryofsilverarrivedinasilvertruck”D3：“Shipmentofgoldarrivedinatruck”在这个文档集中，d=3。lg(d/dfi)=lg(3/1)=0.477lg(d/dfi)=lg(3/2)=0.176lg(d/dfi)=lg(3/3)=0向量空间模型

—构建向量（举例）第12页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10三篇文档的每个词项的IDF值如下所示：idfa=0 idfin=0idfarrived=0.176 idfof=0idfdamaged=0.477 idfsilver=0.477idfdelivery=0.477 Idfshipment=0.17615idffire=0.477 idftruck=0.176idfgold=0.176向量空间模型

—构建向量（举例）第13页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

—构建向量（举例）docidaarriveddamageddeliveryfiregoldinofshipmentsilvertruckD1000.47700.4770.176000.17600D200.17600.477000000.9540.176D300.1760000.176000.17600.176Q000000.1760000.4770.176SC(Q,D1)=0×0+0×0+0×0.477+0×0 +0×0.477+0.176×0.176+0×0+0×0 +0×0.176+0.477×0+0.176×0 =0.17620.031类似地：SC(Q,D2) =0.954×0.477+0.17620.486SC(Q,D3) =0.1762+0.17620.062因此，检索结果顺序为D2,D3,D1。第14页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

—倒排索引term1term2term3termitermnd1,1d10,2dj,tfi,j第15页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量新问题：在已知的查询和文档中，词频很高的匹配词项淹没了其他匹配词项的效果。为了避免这种现象，科研人员提出使用lg(tf)+1来缩小词频的范围。

新的权重：

第16页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10基于该思想的修订版本是在查询和文档中的词项使用不同的权重。lnc.ltc词项权重计算模式非常有效。标签lnc.ltc是如下形式：qqq.ddd，其中qqq指查询权重，ddd指文档权重。这三个字母：qqq或ddd是xyz的形式。向量空间模型

——构建向量第17页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——构建向量第一个字母x可以是n、l或a。n表示原始词频或指tf。l表示通过取对数来降低权重，所以可以使用1+lg(tf)。a表示加强权重，所以权重为:第二个字母y表示是否使用idf。n表示不使用idf，t表示使用idf。第三个字母z表示是否使用文档长度归一化。通过归一化文档长度，我们试着减小检索中文档长度的影响（见公式2-1）。在文献[Singhal,1997]中，n表示不使用归一化，c表示使用标准的余弦归一化，u表示使用临界点长度（pivotedlength）归一化。第18页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度文档向量：查询向量：(1)内积（InnerProduct）问题：通过内积方法，一个比较长的文档可能会得到一个比较高的分数，仅仅因为文档比较长，因此有更多的机会包含查询词——并不一定因为文档是相关的。

第19页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度(2)余弦(Cosine)条件假设：余弦方法中假定文档长度对查询没有影响。余弦方法通过将向量内积除以文档向量的长度来实现不同文档长度的归一化。除以文档向量长度就是不考虑文档长度。第20页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度Dice系数：Jaccard系数：第21页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10然而这种简单的假设是不正确的（至少对于TREC数据）。拿50个TREC查询集所有查找到的相关文档来说，Singhal发现实际上在长文档集中更多文档被判断为相关的[Singhal，1997]。原因可能是长文档仅仅是有更多的机会包含那些与给定查询确实相关的词项。向量空间模型

——相似度第22页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度(3)临界点余弦（PivotedCosine）第23页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度相似度为：这种方法有两个变量：分别为斜率s和临界点p。我们也有可能将斜率s表示为临界点的函数。Singhal在纠正和调整相应的斜率之前，将整个文档集上统计计算出来的平均归一化因子选定为临界点。同时，将归一化因子除以(1.0-s)p。第24页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度计算相似度的等式如下：

（2-1）其中avgn是在任何纠正前的平均文档归一化因子，s值凭经验得到。临界点模式对于短文档和中等长度的文档还算有成效，但是与归一化前相比，整个算法会更有利于特别长的文档。

第25页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度最后一种调整是针对在特别长文档中出现的词频特别高的情况。首先，使用1+lg来限制词频。为了应对长文档，将每个词项权重除以平均词项权重。新的权重dij为：使用新权重，并且除以调整因子的新公式如下：(2-2)第26页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10向量空间模型

——相似度然后我们计算给定文档集中每篇文档的词项的平均数量，并且将其作为临界点p。一旦计算完成，就可以使用文档集就上训练出一个很好的斜率。公式（2-2）被称为临界点唯一归一化（pivoteduniquenormalization）。实验表明，在公式（2-1）临界点余弦归一化的基础上检索效果得到了提高。修改后的归一化因子使得更可能检索到长文档，并且对于TREC查询，性能可以提高10%。第27页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10概率检索模型

ProbabilisticRetrievalModel第28页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10概率模型概率模型通过计算文档与查询相关的概率来作为文档和查询的相似度。这就使相关性排序问题降为概率论应用问题。

起源思想：基于一个词项分别在相关文档和不相关文档中出现的频率来估计该词项的权重。条件：独立性假设——词项间是独立的方法：查询中的词项可以看做文档相关的指示器。经过观察，我们发现词项A同时在文档和查询中出现时，文档相关的概率为x%。这样我们就为词项A赋值这个概率。所有权重的乘积是文档相关的概率。第29页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10简单词项权重估计给定词项在相关文档中的概率假设D1和D2是相关文档，D3、D4和D5是非相关文档词项t1使文档Dj相关的概率：第30页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10给定一篇文档di，它包含t个词项(w1,w2,…,wt)对于文档中一个已知的词项，它对估计整篇文档相关的贡献可以计算为：文档di相关的权重或者“可能性”基于文档中每个词项相关的概率。基于已知的独立性假设，我们可以将文档中每个词项出现的概率相乘来得到文档相关的概率，最后将乘积取对数：简单词项权重第31页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10两个相互排斥的独立性假设：[Robertson和SparkJones，1976]

I1：词项在相关文档中的分布是独立的并且在所有文档中的分布是独立的。I2：词项在相关文档中的分布是独立的并且它们在非相关文档中的分布也是独立的。排序原则：O1：相关的可能性仅仅基于文档中出现的查询词项。O2：相关的可能性基于文档中出现的查询词项和未出现的查询词项。简单词项权重第32页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10在不同的排序原则和独立性假设的组合下，可以得出4种权重。给出一个词项t，考虑以下变量：N —— 文档集中文档的数量；R —— 对于已知查询q对应的相关文档的数量；n —— 包含词项t的文档数目；r —— 包含词项t的相关文档数目。选择I1和O1组合：

简单词项权重第33页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10选择I2和O1组合：选择I1和O2组合：

选择I2和O2组合：

简单词项权重第34页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10当使用不完整的相关性信息时，由于估计相关性的不确实性，我们将权重都加0.5，新的权重公式为：简单词项权重第35页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10Q：“goldsilvertruck”D1：“Shipmentofgolddamagedinafire.”D2：“Deliveryofsilverarrivedinasilvertruck.”D3：“Shipmentofgoldarrivedinatruck.”我们假定这三篇文档是训练数据，并且认为文档D2和文档D3与该查询相关。为了计算相似度，首先计算出查询词项的权重，然后计算出匹配词项的权重的和。简单词项权重—举例第36页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10简单词项权重—举例

每个查询词项的频率

使用以上公式进行计算，我们得出以下权重：gold：goldsilvertruckN333n212R222r112第37页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10silver：truck：简单词项权重—举例第38页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10简单词项权重—举例词项权重文档权重w1w2w3w4gold-0.079-0.176-0.176-0.477silver0.0970.3010.1760.477truck0.1430.5230.5231.176w1w2w3w4D1-0.079-0.176-0.176-0.477D20.2400.8240.6991.653D30.0640.3470.3470.699第39页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10实验结果：第三种权重和第四种权重的性能相当，但是优于第一种权重和第二种权重。科研人员在UKCIS文档集（包含27361篇文档）上研究第一种权重和第四种权重衡量方式上的不同[SparckJones，1979a]。研究发现，使用第四种权重性能提高很多。研究者还使用了其他两组对比实验。第一组只是简单地依据匹配词项的个数排序，第二组使用IDF来估计权重。实验表明，这些方法都次于这四种权重的任何一种，但是使用IDF比简单地使用匹配词项的频率要好一些。在所有的情况中，文档的排序为D2,D3,D1简单词项权重第40页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10简单词项权重问题：原始概率模型并没有引入词频和文档长度，其效果还不如向量空间模型。引入词频:

在原始的概率模型中并没有使用词频。Croft和Harper在概率模型中引入了词频[Croft和Harper，1979]。相关度是通过词项在一篇给定文档中出现的概率来估计的，而不是简单地看词项在文章中出现与否。新的相似度:第41页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10P(dij)表示词项i在文档j中出现的概率，并且可以只通过词项i在文档j中出现的频率来估计。归一化词频可以通过下式计算：引入词频后的效果：Croft和Harper在克兰菲尔德文档集和NPL文档集的11429篇文档上比较了归一化后的词频、未归一化的词频和一个未使用词频的对比系统。和对比系统相比，实验结果表明，使用归一化词频后的系统效果有统计性的显著提升。在大多数情况下，未归一化词频的系统比对比系统的效果还要差。简单词项权重第42页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10非二值独立模型

（Non-BinaryIndependenceModel）思想：在词项权重计算中引入了词频和文档长度[Yu等人，1989]。一旦计算出词项权重，就可以使用向量空间模型计算内积来获得最终的相似度。方法：权重为词项在相关文档中出现tf次与词项在非相关文档中出现tf次的比率，公式如下：P(di|R)表示相关文档中第i个词项的出现频率为di的概率，P(di|N)表示非相关文档中第i个词项的出现频率为di的概率。

第43页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10非二值独立模型——举例Q：“goldsilvertruck”D1：“Shipmentofgolddamagedinafire.”D2：“Deliveryofsilverarrivedinasilvertruck.”D3：“Shipmentofgoldarrivedinatruck.”词项到文档的映射表docidaarriveddamageddeliveryfiregoldinofshipmentsilvertruckD110101111100D211010011021D311000111101Q00000100011第44页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10非二值独立模型——举例因此，我们有三篇文档和一个查询，总共11个词.我们假设文档2和文档3是相关的，文档1是不相关的.通过文档长度进行归一化后，如下表：归一化文档长度

第45页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10我们没有对查询进行归一化。查询中出现的词项是：“gold”、“silver”和“truck”。对于文档D1,“gold”的权重是：对于D1中的“silver”，我们得到：我们可以通过这种方法来计算文档中每个词项的权重和已知词频的权重。我们可以构造出对应向量，然后以此计算查询和每个文档的相似度。非二值独立模型——举例第46页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10泊松模型

Robertson和Walker研究出一种使用泊松分布来估计相关性概率，并且引入了词频和文档长度的概率模型[Robertson和Walker，1994]。我们使用ptf来引入词频。已知相关性下，ptf表示词频为tf的词出现的概率，qtf表示对应的非相关的概率。下标0表示未出现的词项。权重计算为：研究人员假定：词在文档中随机出现，且符合泊松分布：第47页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10泊松模型当前文档所阐述的语义内容是否与查询词所表示的概念相同？参数m随着不同的语义情况而变化。这导致权重计算如下：式中——与词t有关的文档的泊松分布参数；——与词t无关的文档的泊松分布参数；j——； ——已知词t相关的文档是相关文档的概率；——与已知词t无关的文档是不相关文档的概率。第48页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10这种权重计算的难点在于如何在实际中应用：实际应用中并没有关于4个参数、、和的直接依据。为了引入词频，我们使用以下函数：

其中w是标准概率权重；k1是未知常量，它的值取决于文档集，并且通过实验获取。该模型同样考虑了文档长度。考虑文档长度因素最简单的方法是修改上式中的w'，可以使用如下公式替换：泊松模型第49页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10式中d——文档长度；——文档平均长度。这样计算w’的公式变为：另外一个参数k3用来衡量查询词频的效果（qtf）。最后，我们引入另外一比例因子k2，可以更好地逼近二元泊松分布估计。k2如下所示：

泊松模型第50页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10其中k2是一个通过实验确定的常量，|Q|是查询词项的个数。这一项允许k2为很高的值来加强比平均长度短的文档的权重。将这些修改应用于相似度后，就是：式中N——文档集中文档的数量；

n——文档集中通过一个已知词索引的文档数量；

R——对于查询相关的文档数量；

r——给定词索引的相关文档数量；

泊松模型第51页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10

tfij —— 文档i中词j的词频；

qtfj —— 查询Q中词j的词频；

dli —— 文档i中词的数量；|Q|—— 查询中词的数量； —— 平均文档长度；

k1,k2,k3 —— 调节参数。问题1：k1和k3取较小的值可能会削弱文档词频和查询词频的影响。k1和k3取较大的值会明显削弱第一项的大小。泊松模型第52页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10措施：分子中引入k1+1和k3+1的因子对全局排序并不起作用。然而这确实允许给k1和k3赋很大的值而不会削减第一项的权重。此外，这样可以归一化调节参数。其思想为：当词频为1时，就没有必要改变原始的权重。问题2：如果仅仅是因为文档长，它给出了关于主题更加具体的细节，那么这是明智的。在这种情况下，长文档的权重不应该比短文档的大。然而，文档长的原因可能是它讨论了更多无关的主题。在这种情况下，长文档就应该受到惩罚。措施：新的调节参数b可以基于文档集的性质调节查询。这个参数是在涉及tfij的因子通过用K代替k1引入的，那么：泊松模型第53页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10泊松模型引入调节参数b。并在分子上加入k1+1和k3+1后：在[Robertson等人，1995]的实验中，这些值分别为k1=1，k2=0，k3=8，b=0.6。

第54页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10同样使用前文中的例子，我们首先计算w4为：gold=-0.477silver=0.477truck=1.176avgdl=22/3=7.33使用同样的参数k1，k2，k3，b，我们计算dli的值：dl1=7dl2=8dl3=7对于D1，唯一匹配查询的是“gold”，其出现的词频tf=1，因此D1的相似度仅仅是“gold”的值（D1的长度dl是7）。

泊松模型第55页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10泊松模型对于文档D2，匹配查询的词项“silver”和“truck”的和为非零值。对于“silver”，tf12=2：第56页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10泊松模型对于“truck”，tf22=1：对于D3，dl=7，所以K=0.973（同D1）。两个词“gold”和“truck”都出现了一次。对于“gold”，tf13=1。第57页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10对于“truck”，tf23=1。通过表2-7，我们再次对比考虑词频的相似度和不考虑词频的相似度，排序结果同样是D2,D3,D1。泊松模型：最终的相似度无tftfD1-0.477-0.484D21.6531.77D30.6990.708泊松模型第58页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10文档片段

思想：一篇文档可以划分成多个段落，并且每一个段落都可以计算相似度。一旦计算完每一个段落的相似度，就需要有种方法来综合每个段落的相似度，从而对整篇文档排序。

把给定片段的基本权重定义为片段相关的概率与片段无关的概率的比值，也就是：rak和sak可以通过以下三种方式的任意一种来计算。

第59页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10(1)使用自相关来初始化参数一个片段与其自身相关，结果是：其中La是文档集中片段的数量，Fk是词项k在文档集中出现的次数。Nw是文档集中不同片段的个数。(2)逆文档集词频（ICTF）

在整个文档集中，词频比较低的词的sik值就比较小。假定rak的最初估值比较差，并且仅仅指定为常量p。使用常量rak导致整个权重大约等于sik。文档片段

第60页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10文档片段

sik是从整个文档集的估计值中去除一篇相关文档dik后计算出来的。也就是通过使用与假定的“相关文档”相匹配的词的数量dik来计算。sik的计算公式如下：

在我们的权重计算中，使用参数p得出下面的权重，这个权重与IDF非常接近：

第61页，共68页，2023年，2月20日，星期五《网络信息内容安全》讲义/张华平/2010-10文档片段(3)综合策略以查询为中心时，查询是已知的，所有的权重都是以与查询的相关性计算的。在求出每一片段的权重后，使用几何平均来计算。这就使权重变为：以