向量空间搜索引擎基本理论

向量空间搜索引擎所运用的简单技术源自矩阵代数,它基于字符在文件中出现的频率来比较文件.向量空间搜索引擎中第一个重要的元素是项空间(term space)的概念.简而言之,一个项空间由文件中出现的每个独立的词组成.向量空间搜索引擎中第二个重要的元素是项数(termcounts).项数就是文件中每个字符出现的次数.通常可由表的形式列出.通过将项空间作为坐标空间,项数作为项空间中的坐标,我们可为每个文件生成一个向量.为了了解怎样生成这些向量,我们看一个简单例子.大家可能对笛卡尔坐标比较熟悉,点的刻画沿X,Y,Z轴.类似的,在我们的例子中一个项空间由三个独立项组成,我们把它们分别称作项1轴,项2轴,项3轴.(在向量空间搜索引擎理论中这些轴通常被称作维数.)通过计算文件中各项出现的次数,并沿各项轴画出坐标,我们就可确定出与文件所对应的项空间中的点.由这些点则可生成该文件的向量.一旦在项空间中画出该文件的向量,我们就可计算向量的大小.我们把大小看作是原点(我们的例子中是坐标(0,0,0)点)到当前文件点之间连线的距离.这样就可运用向量的长度通过计算夹角的余旋来比较不同的文件.例如,相同的文件夹角余旋为1,文件中含有类似项的夹角余旋会是正小数,文件中含有截然不同项的夹角余旋会是0.一一一个个个简简简单单单的的的例例例子子子假设我们有三个文件.每个文件分别是三个词猫,狗和老鼠的组合.这三个词猫,狗和老鼠就是项空间.那么我们可以说每个文件分别沿猫维,狗维和老鼠维上有坐标.这些坐标取决于每一项在文件中出现的次数.例如,以下表中的文件1就含有'猫-狗-老鼠向量'的坐标为(3,1,4).我们用勾股定理来计算每个文件向量的大小,在该情况下向量维数高于二维,所以有以下公式:a2+b2+c2=d2kV1k=p32+ 12+ 42=p9 + 1 + 16 = 5:09901kV2k=p12+ 22+ 52=p1 + 4 + 25 = 5:47722kV3k=p22+ 32+ 02=p4 + 9 + 0 = 3:87298注意到无论是多少维向量,我们都将用勾股定理来计算文件向量的大小.例如,如果项空间由1000个词组成,那么是1000维,从而我们的计算公式是a2+b2+c2+d2+e2+ 等等,直至再加995项得到答案.另外,严谨的读者会注意到即使对于不同的文件会有相同大小的文件向量.例如,对于两个文件向量分别为(1,2,3)和(3,2,1)的文件来说,它们的文件向量大小均为3.74165.这并不1项空间n项数文件1文件2文件3猫312狗123老鼠450矛盾.我们会看到,文件的关联值(relevancyscore)是基于要查询的询问项的维数,因此,即便是对于具有相同大小的文件向量的文件,它们的询问项会很不相同.也就是说,项空间中的两条直线具有相同的长度并不一定意味它们指向同一方向.查查查询询询为查询文件的索引,我们把查询向量投影到向量空间上,并计算查询向量与文件集中向量之间的余旋夹角.用英语表达就是,我们将查询向量投影到向量空间上,然后看它附近有没有文件集中向量.例如,查询项为'老鼠',那么'猫-狗-老鼠向量'就是(0,0,1).查询向量的大小为kQk=p02+ 02+ 10 + 0 + 1 = 1注:一个简单方法是查看询问项是否属于项空间,如果是,那么kQk总为1.但这只对单项询问有效.对于多个查询项,计算它们在项空间出现的次数,然后对次数取方根.由于查询项的值总大于1,kQk将会是某个整数的方根.但前提是每项在询问项中只出现一次.由于本文将要讨论的词干问题,该假设未必是个好假设.为计算查询向量与一文件向量的余旋夹角,我们用查询向量与文件向量的点积除以查询向量大小与文件向量大小的乘积,即Q V1kQk kV1k点积是文件向量的项数与相对应的查询向量的项数的乘积之和.例如,我们在查询'老鼠',查询项的坐标为(0,0,1),因为词'猫','狗'没有出现在查询项中,'老鼠'出现了一次位于项空间的第三维上.基于上述表中的项数,我们例子中的文件1的文件向量为(3,1,4).如果要计算查询向量与文件1的向量点积,我们有:查询向量:(0;0;1)文件1向量:(3;1;4)点积: (0 3)+ (0 1)+ (1 4) = 4现在将点积4除以查询向量大小与文件向量大小的乘积.前面已算出文件1向量的大小为5.09901,查询向量大小为1,因此余旋值为4/5.09901b我们来试一下,查询项'老鼠'与文件1的向量之间的余旋夹角为:Q V1kQk kV1k=(0 3)+(0 徰喕 4)1 5:09901=0:784462如果对其他两个文件做同样的计算,得到以下余旋值:文件1=0:78446文件2 = 0:91287文件3=0:00000我们为文件按余旋值递减排序:文件2=0:91287文件1 = 0:78446文件3=0:00000可以看出文件2是和查询项'老鼠'最相关的,该结论可从上面的列表中得到快速验证.文件1有些相关,文件3因其不含老鼠这一项,与查询项完全无关.一个简单的考虑方法是越接近余旋值1,文件与查询项越相关.如果余旋值为0,那么文件向量与查询向量正交且完全无关.文文文件件件集集集索索索引引引处处处理理理文件集的索引处理对于被索引的文件是很特殊的.向量空间搜索技术可用于任何有一定结构的信息中,因此它对文字,图像,密码钥匙,甚至DNA同样有效.但是,用户必须对所处理的信息做适当的构建,并可将其优化以提高索引处理效率.我们用检索一个小网站为例.首先每个HTML文件必须先做预处理,然后索引为文件集合的一部分.(集合只能整体索引.在索引后添加额外的文件会改变项空间的维数并且否定已存文件向量的大小.)我们先拆解所有HTML文件的内容,诸如空格,回车键直到只留有单个词组成的项为止.然后,我们把间歇字(stopword)从正文中移出.间歇字是那些在英语中常用但总体上不对正文产生任何语义的词.比如,'the','and','of'和'or'这些词和实际的语义没什么关系,如不去掉它们会增加项空间的维数,从而加常处理时间.另外,象'quickly'(通常以'ly'结尾)这样的副词因和实际的语义没什么关系也可去掉.下一步,我们词干化(stem)文件中剩余的项.词干化是将每项简化成词根的形式.例如,词'runner','running','runs'都将被简化成'run'.PorterStemmingAlgorithm的目的就是词干化.这进一步简化了项空间并保持了语义.完成这三步后我们(期望)留下保持原文件语义的最少项.我们现在可以开始通过建立项空间和计算每个文件向量的大小来索引文件集.步骤1!步骤2!步骤3!步骤4拆解HTML去掉间歇字词干化生成项空间生成文件项数计算文件向量大小步骤1{拆解HTML文件,诸如逗号,空格,回车键直到只留有单个词组成的项.3步骤2{将间歇字(如'the')从正文中移出以降低项空间的维数.步骤3{词干化文件中剩余的项(如'runner'和'running')以简化项空间并保持语义.PorterStemming Algorithm的目的就是词干化.步骤4A{从文件集的每个文件中选出每项的一个代表,扩张成整个项空间,使所有可能的项都包含在内.步骤4B{计算和记录每一项在文件中出现的次数.步骤4C{计算和记录每个文件的向量大小,kVnk.注:我们要注意的是剖析器如何分解信息将直接影响查询结果.例如,如果你索引的是一本书,那么索引时间和查询结果将取决于如何对书进行分割,是按章,页还是段落.你需要对数据进行一定的试验以找到最优的分割.向向向量量量空空空间间间搜搜搜索索索引引引擎擎擎的的的局局局限限限尽管向量空间搜索技术很酷,但它存在着严重的局限性.首先,它需要海量计算,因此计算速度极慢.由于是浮点运算,因此需要极长的处理时间,从而导致表现失常.高性能的表现需要在内存中执行优化过的代码.我们期望随着处理器速度的提高,这将不再成为障碍.其次,动态的文集对每一次文件的添加都需要再索引.这是由于当每次在项空间中引进一个新项时,对应的新矩阵会增加一维从而所有的文件都要进行再索引使得文件向量与新维数相对应.这样做使得实时查询变得几乎不可能,这可能是使该项技术被广泛采用的最严重障碍.第三,为了能发觉有潜在语义索引(LatentSemanticIndexing)的文件之间的额外联系,我们需对文件集做额外的数学变换.LSI可使文件之间在语义层上找到彼此之间的额外联系.它超出了本文的讨论范围,但对向量空间搜索技术的下一步研究具有重要意义,同时也为实时查询增加了新的障碍.相相相关关关文文文献献献http://www.perl.com/pub/a/2003/02/19/engine.html - Excellent article about buildingavectorspacesearchengineincludingopensourcePERLcode.http://www.chuggnutt.com/stemmer.php - Open source implementation of the PorterstemmingalgorithminPHPhttp://www.nitle.org/semantic-search.php - Open source Latent Semantic Indexing pack-agewritteninPerl.VerymuchinBeta,notyetsuitableforproduction."Using Linear Algebra for Information Retrieval" - Berry, M. W.; Dumais, S. T.; andO'Brien,G.W.1995.4"Indexing by latent semantic analysis." Journal of the Society for Information Science,41(6),391-407.| rsttechnicalLatentSemanticIndexingpaper;goodbackground."Enhancing Performance in Latent Semantic Indexing Retrieval" - Susan Dumais, TM-ARH-017527TechnicalReport,Bellcore,19905 相关资源：Office2016专业增强版中文免费正式版(附安装教程)64位