向量空间模型

《网络信息内容安全》讲义/张华平/2010-10向量空间模型向量空间模型是最常用的检索模型（Salton等人，1975年）思想：文章的语义通过所使用的词语来表达方法:每一篇文档用一个向量来表达，查询用一个向量来表达，通过向量的方式来计算相似度。《网络信息内容安全》讲义/张华平/2010-10查询文档1文档2文档3q0,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,向量空间模型《网络信息内容安全》讲义/张华平/2010-10向量空间模型主要涉及两方面的工作：（1）如何构建一个向量来表示文档中的词项，构建另一个向量来表示查询中的词项.（2）如何来度量任意文档向量和查询向量的相似度《网络信息内容安全》讲义/张华平/2010-10向量空间模型——构建向量对于文档集中每一个不同的词项（或概念），我们在向量中只记录一个分量。当词项出现时，就在对应向量的分量处记1；如果词项未出现，就在对应的分量处记0。《网络信息内容安全》讲义/张华平/2010-10向量空间模型——构建向量文档：D1D3D2QAA,IIA,I文档向量：D2=1,0D3=0,1Q=1,1D1=1,1D1,Qxy1D2D31《网络信息内容安全》讲义/张华平/2010-10二值表示方法并没有考虑一个词项在文档中出现的次数。通过扩展这种表示形式，我们将词项在文档中出现的频率作为向量中各个分量的值。在上例中，如果文档D2中A出现了两次，向量可以表示为2,0。向量空间模型——构建向量《网络信息内容安全》讲义/张华平/2010-10除了简单地给出查询词列表外，用户通常还会给出权重，该权重表示一个词项比另外一个词项更重要。思想：不频繁出现的词的权重应该比频繁出现的词的权重更高。方法：人工赋值—在初始查询中用户人工指定词项权重来实现的。自动赋值—通过基于词项在整个文档集中出现的频率。向量空间模型——构建向量《网络信息内容安全》讲义/张华平/2010-10向量空间模型——构建向量我们采用稍大一些的例子来展示如何使用基于数据集频率的权重。t——文档集中不同词项的个数。——词项tj在文档Di中出现的次数，也就是词频。——包含词项tj的文档的篇数。——，其中d表示所有文档的篇数。这就是逆文档频率。ijtflgjddfjidfjdf《网络信息内容安全》讲义/张华平/2010-10对于每一篇文档向量，都有n个分量。向量中的每个分量为在整个文档集中计算出来的每个词项的权重。在每篇文档中，词项权重基于词项在整个文档集中出现的频率情况以及词项在某一个特定文档中出现的频率自动赋值。向量空间模型——构建向量《网络信息内容安全》讲义/张华平/2010-10向量空间模型——构建向量对于文档中词项的权重因素，主要综合考虑词频和逆文档频率。文档i对应的向量中第j个词条的值：查询Q和文档Di的相似度可以简单地定义为两个向量的内积。jijijidftfdijtjqjidwDQSC1),(《网络信息内容安全》讲义/张华平/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向量空间模型—构建向量（举例）《网络信息内容安全》讲义/张华平/2010-10三篇文档的每个词项的IDF值如下所示：idfa=0idfin=0idfarrived=0.176idfof=0idfdamaged=0.477idfsilver=0.477idfdelivery=0.477Idfshipment=0.17615idffire=0.477idftruck=0.176idfgold=0.176向量空间模型—构建向量（举例）《网络信息内容安全》讲义/张华平/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。《网络信息内容安全》讲义/张华平/2010-10向量空间模型—倒排索引term1term2term3termitermnd1,1d10,2dj,tfi,j《网络信息内容安全》讲义/张华平/2010-10向量空间模型——构建向量新问题：在已知的查询和文档中，词频很高的匹配词项淹没了其他匹配词项的效果。为了避免这种现象，科研人员提出使用lg(tf)+1来缩小词频的范围。新的权重：tjijjijijidftfidftfw12])0.1[(lg)0.1(lg《网络信息内容安全》讲义/张华平/2010-10基于该思想的修订版本是在查询和文档中的词项使用不同的权重。lnc.ltc词项权重计算模式非常有效。标签lnc.ltc是如下形式：qqq.ddd，其中qqq指查询权重，ddd指文档权重。这三个字母：qqq或ddd是xyz的形式。向量空间模型——构建向量《网络信息内容安全》讲义/张华平/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）归一化。max5.05.0tftf《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度文档向量：查询向量：(1)内积（InnerProduct）问题：通过内积方法，一个比较长的文档可能会得到一个比较高的分数，仅仅因为文档比较长，因此有更多的机会包含查询词——并不一定因为文档是相关的。ijtjqjidwDQSC1),(),,,(21itiiidddd),,,(21qtqq《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度tjtjqjijtjijqjiwddwDQSC11221)()(),((2)余弦(Cosine)条件假设：余弦方法中假定文档长度对查询没有影响。余弦方法通过将向量内积除以文档向量的长度来实现不同文档长度的归一化。除以文档向量长度就是不考虑文档长度。《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度Dice系数：Jaccard系数：21121)()(2),(tjtjqjijtjijqjiwddwDQSCtjtjtjijqjqjijtjijqjidwwddwDQSC111221)()(),(《网络信息内容安全》讲义/张华平/2010-10然而这种简单的假设是不正确的（至少对于TREC数据）。拿50个TREC查询集所有查找到的相关文档来说，Singhal发现实际上在长文档集中更多文档被判断为相关的[Singhal，1997]。原因可能是长文档仅仅是有更多的机会包含那些与给定查询确实相关的词项。向量空间模型——相似度《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度(3)临界点余弦（PivotedCosine）《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度tjijtjijqjidspsdwDQSC121)()()0.1(),(相似度为：这种方法有两个变量：分别为斜率s和临界点p。我们也有可能将斜率s表示为临界点的函数。Singhal在纠正和调整相应的斜率之前，将整个文档集上统计计算出来的平均归一化因子选定为临界点。同时，将归一化因子除以(1.0-s)p。《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度计算相似度的等式如下：（2-1）其中avgn是在任何纠正前的平均文档归一化因子，s值凭经验得到。临界点模式对于短文档和中等长度的文档还算有成效，但是与归一化前相比，整个算法会更有利于特别长的文档。avgndssdwDQSCtjijtjijqji121)()()0.1(),(《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度最后一种调整是针对在特别长文档中出现的词频特别高的情况。首先，使用1+lg来限制词频。为了应对长文档，将每个词项权重除以平均词项权重。新的权重dij为：使用新权重，并且除以调整因子的新公式如下：(2-2)jijidfatftfd)lg(1lg11(,)(1.0)()(||)tqjijjiiwdSCQDspsd《网络信息内容安全》讲义/张华平/2010-10向量空间模型——相似度然后我们计算给定文档集中每篇文档的词项的平均数量，并且将其作为临界点p。一旦计算完成，就可以使用文档集就上训练出一个很好的斜率。公式（2-2）被称为临界点唯一归一化（pivoteduniquenormalization）。实验表明，在公式（2-1）临界点余弦归一化的基础上检索效果得到了提高。修改后的归一化因子使得更可能检索到长文档，并且对于TREC查询，性能可以提高10%。《网络信息内容安全》讲义/张华平/2010-10概率检索模型ProbabilisticRetrievalModel《网络信息内容安全》讲义/张华平/2010-10概率模型概率模型通过计算文档与查询相关的概率来作为文档和查询的相似度。这就使相关性排序问题降为概率论应用问题。起源思想：基于一个词项分别在相关文档和不相关文档中出现的频率来估计该词项的权重。条件：独立性假设——词项间是独立的方法：查询中的词项可以看做文档相关的指示器。经过观察，我们发现词项A同时在文档和查询中出现时，文档相关的概率为x%。这样我们就为词项A赋值这个概率。所有权重的乘积是文档相关的概率。《网络信息内容安全》讲义/张华平/2010-10简单词项权重估计给定词项在相关文档中的概率假设D1和D2是相关文档，D3、D4和D5是非相关文档词项t1使文档Dj相关的概率：2/33/12/1)|1()|1()1|(nonreltpreltptDpJ《网络信息内容安全》讲义/张华平/2010-10给定一篇文档di，它包含t个词项(w1,w2,…,wt)对于文档中一个已知的词项，它对估计整篇文档相关的贡献可以计算为：文档di相关的权重或者“可能性”基于文档中每个词项相关的概率。基于已知的独立性假设，我们可以将文档中每个词项出现的概率相乘来得到文档相关的概率，最后将乘积取对数：简单词项权重(|rel)(|nonrel)iiPwPw11(|rel)(|rel)lglg()|nonrel)()|nonrel)ttiiiiiiPPwwPwPw《网络信息内