（计算数学专业论文）查询分析在信息检索中的应用.pdf

i t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期( 。年岁月妇 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 翩虢一 导师签名：玉型二二 日期：年月目 摘要 摘要 为了更精确地检索信息，越来越多的长查询( l o n gq u e r y ) 被用于信息检索中。 但是目前很多搜索引擎并不能很好地处理长查询。这是因为长查询在带来较准确 匹配的同时会带来较多的不相关信息，从而在一定程度上干扰用户的检索。查询 切分就是在此背景下提出的。查询切分的目的是将查询分成有意义的若干个查询 块再进行检索，因为这有利于检索系统根据有意义的查询块来分析用户的搜索意 图，从而反馈给用户更合适的结果。我们在本文中提出了一种基于计算查询词关 系在其主特征空间相似度的切分模型。在本模型中，我们根据查询词的n 元组 叫g r a m ) 之间的频率来建立查询词之间的关系矩阵。并将此关系矩阵映射到其特 征主空间进行查询切分。不仅如此，我们还提出了一种确定主特征空间维数k 的 方法。实验表明我们的算法相对其它算法( 基于m i 、e m 的切分方法) 有着很大的 提高( 在f m e a s u r e 上分别提高了3 5 8 和1 7 7 ) 。 在此查询切分工作基础上，根据查询切分中的不足，比如切分后的某些查询 词( 组) 是没有意义的且切分块上也没有一定的权重，因此，我们提出了对互联网 中的长查询提取其关键短语的做法。同时我们的工作是较早对互联网长查询提取 其关键短语的研究。受到谱聚类以及前面切分工作的启发，我们首先从长查询中 提取为短语，其次对每个短语进行赋予权重，并根据每个短语权重的大小来判定 该短语是否为关键短语。在此工作中，我们进一步深入研究和探讨了查询切分工 作中相关问题，并在如何表示查询词之间的关系、如何确定主特征空间的维数等 方面上给出了更优的解决方案。通过与基于名词短语提取、t f i d f 方法关键短语 提取以及基于k m e a n s 方法的关键短语提取等方法的比较，我们的算法在从长网 络查询中提取关键短语取得了出色的效果。 我们在本文的最后给出查询切分开发工作中的相关细节，并以最大匹配切分 来辅助我们的切分。该实现方法不仅在切分速度上面得到了大幅的提升并且还可 以解决一些特殊长查询切分中遇到的难题。随后，我们就长查询关键短语的提取 在查询建议、目录搜索中给出了具体的分析和应用。 关键词：信息检索，查询切分，关键短语提取 a b s t r a c t a bs t r a c t i no r d e rt oc o n v e ym o r es o p h i s t i c a li n f o r m a t i o ni ni n f o r m a t i o nr e t r i e v a l ( 瓜) ， m a n yl o n gq u e r i e sa r eu s e db yp e o p l et od e s c r i b et h e i rs p e c i a ln e e d s h o w e v e r , m o s t o ft h ec o m m e r c i a la n da c a d e m i cs e a r c he n g i n e sc a n n o th a n d l et h e s el o n gq u e r i e sw e l l q u e r ys e g m e n t a t i o ni se s s e n t i a lt oq u e r yp r o c e s s i n g i ta i m st ot o k e n i z eq u e r yw o r d s i n t os e v e r a ls e m a n t i cs e g m e n t sa n dh e l pt h es e a r c he n g i n et oi m p r o v et h ep r e c i s i o no f r e t r i e v a l i nt h i sp a p e r , w ep r e s e n tan o v e lu n s u p e r v i s e dl e a r n i n ga p p r o a c ht oq u e r y s e g m e n t a t i o nb a s e do np r i n c i p a le i g e n s p a c es i m i l a r i t yo fq u e r yw o r d f r e q u e n c ym a t r i x d e r i v e df r o mw e bs t a t i s t i c s e x p e r i m e n t a lr e s u l t ss h o wt h a t0 1 1 i a p p r o a c hc o u l da c h i e v e s u p e r i o rp e r f o r m a n c eo f3 5 8 a n d1 7 7 i nf - m e a s u r eo v e rt h et w ob a s e l i n e s r e s p e c t i v e l y , i e m i ( m u t u a li n f o r m a t i o n ) a p p r o a c ha n de mo p t i m i z a t i o na p p r o a c h h o w e v e r , q u e r ys e g m e n t a t i o nd o e sn o ti d e n t i f yw h i c hs e g m e n t sa r ek e y - p h r a s e s ， a n dd o e sn o ta s s i g ne x p l i c i t w e i g h t st os e g m e n t s i nt h i sp a p e r , w ed e v e l o pa n d e v a l u a t ean o v e lu n s u p e r v i s e da p p r o a c hf o rk e yp h r a s ee x t r a c t i o nf r o ml o n gn a t u r a l l a n g u a g eq u e r i e s i np a r t i c u l a r , w ef i r s te m p l o yaw e bs t a t i s t i c s - b a s e da f f i n i t ym a t r i x wt oi d e n t i f yt h er e l a t i o n sb e t w e e nq u e r yw o r d s w et h e nc l u s t e rt h eq u e r yw o r d si n t o kc l u s t e r si ni t s s p e c t r a ls p a c e ，a n ds e l e c tt h eh i g h e rr a n k e dc l u s t e r sa sq u e r y k e y - p h r a s e s i np a r t i c u l a r , w ep r o p o s ean e wm e t h o dt oa u t o m a t i c a l l yd e t e r m i n et h e n u m b e ro fc l u s t e r sb a s e do nt h ed i s t r i b u t i o no fe i g e n v a l u e so fw ：o u re x p e r i m e n t s d e m o n s t r a t et h a to u ra p p r o a c hc o u l da c h i e v es i g n i f i c a n ti m p r o v e m e n t si nk e y - p h r a s e e x t r a c t i o na sc o m p a r e dt ot h es t a t e o f - t h e a r t sm e t h o d s ，i n c l u d i n gt h en o u np h r a s e s e x t r a c t i o n ，t h et f i d fw e i g h t i n gb a s e de x t r a c t i o na n dt h ee n h a n c e dk m e a n se x t r a c t i o n m e t h o d s b e s i d e s ，w ea l s og i v et h ed e t a i l so fd e v e l o p m e n to fq u e r ys e g m e n t a t i o n w e a n a l y z et h ec o n d i t i o n so ft h ef o r w a r dm a x i m u mm a t c h i n g ( f m m ) a l g o r i t h mi n s e g m e n t a t i o n a n dc o m b i n ei ti n t oo u r a p p l i c a t i o n s t h i sa p p r o a c h i sn o to n l y i m p r o v i n gt h es p e e di nt h eq u e r ys e g m e n t a t i o n ，a n da l s oh a n d l i n gs o m es p e c i a ll o n g q u e r i e sw e l l i ns e g m e n t a t i o n i nt h el a s t ，w e p r e s e n tt h ea p p l i c a t i o n so fq u e r y k e y - p h r a s e si nq u e r ys u g g e s t i o na n dd i r e c t o r ys e a r c h i i d s ：i n f o r m a t i o nr e t r i e v a l ，q u e r ys e g m e n t a t i o n ，k e y - p h r a s ee x t r a c t i o n 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 2 3 - 3 主特征空间的建立9 2 3 4 参数k 的估计1 0 2 3 5 查询切分1 1 2 4 实验1l 2 4 1 数据1 1 2 4 2 参与比较的算法( b a s e l i n e s ) ：1 2 2 4 3 评价标准( m e t r i c s ) 1 2 2 4 4 实验结果1 2 2 5 总结及未来工作1 4 第三章网络长查询的关键短语抽取。1 5 3 1 简介15 3 2 相关工作1 7 3 3 模型1 7 3 3 1 概要1 8 i v 目录 3 - 3 2a f f i n i t ym a t r i x 的构建18 3 3 3 主特征空间中的查询词聚类1 9 3 3 4 关键短语的提取2 0 3 4 参数k 的确定2 1 3 4 1 主成分累积判定法2 1 3 4 2k a i s e rr u l e 判定法2 2 3 4 3s c r e eg r a p h 判定法2 2 3 4 4 基于查询词长度的综合判定方法2 3 3 5 实验。2 4 3 5 1 参数k 选择的实验2 4 3 5 2 关键短语提取的实验2 5 3 6 分析2 9 3 7 总结3 0 第四章相关应用及实现3 l 4 1 查询切分的实现3 1 4 1 1 查询的清洗3 l 4 1 2 查询的拼写检查3l 4 1 3 基于最大匹配的切分3 2 4 1 4 训练数据3 3 4 1 5 切分算法的实现3 5 4 2 基于网页关键短语抽取的查询建议3 7 4 3 关键短语的抽取在目录搜索中的应用3 8 4 4 总结3 9 第五章结论和展望4 0 致谢4 1 参考文献4 2 在学期间的研究成果4 6 v 第一章引言 第一章引言 随着i n t e m e t 的发展，整个网络正在不断累积成一个前所未有的超级大型数 据集合。面对如此海量存储的信息空间，如何快速获取所需的知识已成为信息时 代最基本的问题。随着i n t e m e t 应用的不断加深，信息检索( i n f o r m a t i o nr e t r i e v a l ， m ) 正成为举足轻重的网络基础设施，而搜索引擎( s e a r c he n g i n e ，s e ) 正是取的一 种优秀的表现形式。近年来除了我们耳熟目睹的g o o g l e 、百度等通用搜索( g e n e r a l s e a r c h ) 弓i 擎，还有大量的垂直搜索引擎走入我们的生活，比如租房搜索、机票酒 店搜索、音乐搜索等等。但是在搜索过程中，由于搜索引擎的返回相关文档数比 较大，用户要查找到需要的信息非常困难。另外，由于大部分搜索引擎用户是普 通网络用户，在检索策略和检索技巧上缺乏必要的知识，提交的查询( q u e r y ) 也不 是很理想。所以，查询分析( q u e r ya n a l y s i s ) 作为沟通用户和搜索引擎的桥梁将在 信息检索中发挥着巨大的作用。在本文中，“查询”( q u e r y ) 的意思就是用户的每 次提交给检索系统的由很多查询词( t e r m ) 构成的一个查询串。 1 1 查询分析的意义 查询分析( q u e r ya n a l y s i s ) 是沟通用户和搜索引擎的有效手段，因为它可以有 效地克服搜索引擎的局限性并助其理解用户的意图。比如它可以根据用户的输入 转化为让搜索引擎更容易理解的方式进行检索，还可以根据用户的输入来进行反 馈，以便帮助用户更加明确自己的搜索目的和方向。因此，在信息检索中，查询 分析对检索结果有着极其重要的作用。我们下面从查询难度( q u e r yd i f f i c u l t y ) 、查 询建议( q u e r ys u g g e s t i o n ) 以查询切分( q u e r ys e g m e n t a t i o n ) 一= 个方面来阐述查询 分析在信息检索中的作用。 查询难度( q u e r yd i f f i c u l t y ) 是用来衡量搜索引擎对用户查询的理解程度，它可 以先计算该查询的歧义性等方面特征，然后做出对该查询的“好”和“坏”之类 的判断。例如用户想知道关于苹果公司的信息，那么他的查询”a p p l e ”并不能很好 的表达用户的搜索意图，这个词对于搜索引擎来说，就是属于“坏 的查询，这 是因为a p p l e 有着多重意思( a p p l ef r u i t , a p p l eb a n k ，a p p l em o v i e ，a p p l e c o m p a n y ) 。不仅如此，由于用户对信息检索的理解的差异导致了用户提供的查询 电子科技大学硕士学位论文 不能很好的表达用户的搜索目标。因此查询建议( q u e r ys u g g e s t i o n ) 以及查询精化 ( q u e r yr e f i n e m e n t ) 成为辅助用户的有效手段。对于刚才提交的查询“a p p l e ， 搜索引擎会分析用户的查询从而给出类似的推荐：a p p l es t o r e ，a p p l ec o m p u t e r s ， a p p l ei p h o n e 等等。查询精化做的事情是如何来优化或者改正用户的查询，比如， 很多文档中都是用“n e wy o r kt i m e s 来表示纽约时报，但是很多用户会输入“n y t i m e s ，这个时候系统就需要查询精化来处理类似问题。 随着用户对检索目标认识的提高，他提供的查询也越来越长，而这些长的查 询是无法从搜索引擎的检索系统中得到精确匹配的，这时候就需要查询切分 ( q u e r ys e g m e n t a t i o n ) 来切分查询，分成一些具有实体意义的小块进行检索。比如 用户输入“f r e es o f t w a r et e s t i n gt o o l sd o w n l o a d ”以期望下载免费的软件测试工具， 那么搜索引擎应该分别出用户找的是“s o f t w a r et e s t i n gt o o l s 而不是诸如“f r e e s o f t w a r e 、“f r e ed o w n l o a d ”类似的网页。切分是整个查询分析的基础工作，而 对于整个搜索引擎来说，查询分析是其整个工作流程中最为关键的一步，也是决 定搜索引擎质量关键性一步。同时，本人的硕士研究工作正是基于查询切分展开 的。在此工作上，根据查询切分中的不足，比如，切分后的某些查询词( 组) 是没 有意义的，并且切分块之间没有一定的权重，所以，在查询切分的基础上，我们 提出了对互联网长查询进行关键短语( k e y p h r a s e ) 的提取。 1 2 查询分析的研究状况 由于查询分析覆盖面比较广，所以本文针对前文所阐述的部分方向进行概括。 它主要包含以下几个方面：查询难度( q u e r yd i f f i c u l t y ) 、查询切分( q u e r y s e g m e n t a t i o n ) 和查询建议( q u e r ys u g g e s t i o n s ) 。 在查询难度( q u e r yd i f f i c u l t y ) 方面，c r o n e n t o w n s e n d 等引入了c l a r i t y s c o r e 【1 1 ，该方法通过比较查询的模型( l a n g u a g em o d e l ) 以及相关文档( r e l e v a n t d o c u m e n t s ) 而得出。高聚合性( h i g h c o h e r e n c e ) 文档对应的查询具有高的c l a r i t y s c o r e ，也就说，该查询返回的结果有较高的准确率。e l a dy o m t o v 等【2 】提出了基 于整个查询返回文档与查询中每个子查询( s u b q u e 呦返回文档重合度( o v e r l a p ) 的分析，“好查询的整个返回相关文档和每个t e r m 返回的相关文档具有高度的 重合特征。在s i g i r 0 6 中，e l a dy o m t o v 等人引入了j s d ( j e n s e n s h a n n o n d i v e r g e n c e ) 来衡量查询、相关性文档( d o c u m e n t s ) 以整个数据集( c o l l e c t i o n ) 之间 的距离【3 1 。 2 第一章引言 查询切分( q u e r ys e g m e n t a t i o n ) 目前还处于起步阶段。文献 4 引入了互信息 ( m u t u a li n f o r m a t i o n ) 来确定查询词与查询词划分，他们认为应该切分在一起的查 询词应该有着较高的互信息。s b e r g s m a 等引入了监督学习( s u p e r v i s e dl e a r n i n g ) 的方法来进行查询切分【5 】，他把切分工作视为对查询词的分类任务。他们首先采 用了p o s ( p a r t o f - s p e e c h ) 标记，位置( p o s i t i o n ) ，w e bc o u n t s 等特征进行学习和训练， 然后利用支持向量机模型( s u p p o r tv e c t o rm a c h i n e ，s v m ) 来进行切分。除此之外， 在w w w 2 0 0 8 中，u i u c 的t a nb i n 在y a h o o ! 实习期间提出了基于语言模型的无 监督分词方法【6 】，他将e m 算法运用到了分词当中来推测未知的查询块出现的概 率，并引入了社会化资源w i k i p e d i a 来指导分词。前面的一些工作有着诸多的缺 点，比如m i 方法不能很好应用在长的查询中，同时这种方法也没有对数据进行 清洗处理导致了切分的效果不是很理想。基于s v m 的切分需要大量的人工标注 数据进行学习，这给工程应用带来很大的难度。e m 算法具有自身的局限性( 长时 间的训练，局部最优1 也影响了基于此算法的分析效果。在此，本人【7 】提出了一个 基于查询词关系矩阵在其特征空间( e i g e n s p a c es i m i l a r i t y ，e s ) 上相似度计算的新 型的算法：我们将查询的数据特征映射到其主特征空间，通过计算词与词之间的 相似性进行查询切分，实验结果表明，该算法极大地提高了切分的精度。在此工 作基础上，我们是较早进行对网络长查询中提取关键短语的研究。受到谱聚类 ( s p e c t r a lc l u s t e r i n g ) 8 ，9 】以及前面切分工作的启发，我们首先将长查询提取为短语， 然后对每个短语进行赋予权重，最后根据权重的大小提取关键短语。在此工作中， 我们进一步深入研究和探讨了查询切分工作中相关问题，并给出了更优的解决方 案。实验结果表明，我们的算法在从长网络查询中提取关键短语取得了出色的效 果。 查询建议( q u e r ys u g g e s t i o n ) 也随着搜索引擎的发展逐渐新兴起来。在各大搜 索引擎的页面上很容易发现搜索引擎对用户的查询建议，由此可见查询建议已经 在沟通用户和搜索引擎之间起到了越来越重要的作用。在研究方面，h u a n g 等人 通过发掘经常共同出现的查询进行相互推荐。f o n s e c a 等【l o 】和j o n e s 等人【4 】抽取 了经常相邻出现的查询对，并把他们用于查询的扩展和替换。查询建议的经典方 法就是挖掘查询日赳1 1 。13 1 ，他们假设在某段时期，多数人对某个方面会感兴趣， 只是用了不同的表现方式。w e ig a o 等【1 2 】提出了基于不同语言间用户日志( u s e r l o g ) 的查询建议。h u a n h u a nc a o 等【1 4 】将鼠标点击与相毗邻数据( s e s s i o nd a t a ) 结 合起来进行推荐。基于查询日志的查询可以很好的帮助用户规范查询，但是其也 有一个明显的问题：即如果某个查询建议很少被用户搜索，那么该建议就很难被 3 电子科技大学硕士学位论文 推荐给其它的用户。在本人工作中，我们介绍了基于关键短语抽取的方法来进行 查询建议。 1 3 本人硕士阶段所解决的问题 通过对信息检索以及查询分析相关理论进行深入的学习和研究，我们提出了 通过计算查询词在其主要特征空间相似度的计算来对查询进行切分。我们首先基 于查询词在互联网中的共现( c o o c c u r r e n c e ) 频率来构建查询词之间的关系矩阵，其 次，通过对关系矩阵特征值的分析而建立其主要特征空间。在此特征空间上，我 们把查询词在关系矩阵中的向量投影在主特征空间上，并通过计算投影之间的相 似度来切分查询。实验结果表明，我们的切分算法极大地提高了切分的效果。不 仅如此，我们根据查询切分中的不足，比如，切分后的某些查询词( 组) 是没有意 义的，并且切分块之间没有一定的权重，因此我们提出了对互联网长查询进行关 键短语的提取。在该工作中，我们受到谱聚类以及前面切分工作的启发，将长查 询首先提取为短语，然后对每个短语上进行赋予权重，并根据权重的大小提取关 键短语。实验结果表明，我们的算法在从长网络查询中提取关键短语取得了出色 的效果。 在查询切分以及查询关键短语研究成果上，我们就该工作在查询建议、目录 搜索中给出了具体的分析和应用。 1 4 文章结构 在本章的结尾，我们给出本论文的组织结构。我们在第二章深入地研究和探 讨了查询切分的相关模型及算法，并在此基础上，在第三章上进行了网络查询的 关键短语的研究。在第四章，我们给出了查询切分的开发细节并针对我们的研究 成果给出了具体应用。第五章综述了我们的研究结论以及在该领域研究的展望。 4 第二章基于主特征空间相似度计算的查询切分 2 1 简介 第二章基于主特征空间相似度计算的查询切分 用户一般是通过提供一些关键词( k e yw o r d s ) 来从搜索引擎中获得相关的反 馈文档，并从中发现自己需要的信息。但是由于用户自身的知识水平等原因提供 的查询往往具有歧义性，不能很好地将用户的搜索意图传递给检索系统。例如： “f r e es o f t w a r et e s t i n gt o o l sd o w n l o a d ( 免费的软件测试工具下载) ，目前基于 b a g - o f - w o r d s 模型的检索系统就不能很好的识别用户的搜索意图，相反，由于 “f r e es o f t w a r e ”、“f r e ed o w n l o a d ”在互联网中大量存在，所以系统将反馈大量 的包含“f r e es o f t w a r e ”、“f r e ed o w n l o a d 的网页，事实上，这些网页并不是用 户所要的。所以，如何通过切分将查询分成有意义的几部分再进行检索将有利于 检索系统来把握用户的搜索意图。 查询切分的作用还不仅仅如此。查询切分是查询分析的基础工作，随着用户 输入的查询长度的增加，查询切分的重要性将越来越突出：比如在返回的相关文 档排序过程中，在对切分后的每个片段上加上一定的权重( q u e r yw e i g h t i n g ) 就可 以很好地计算查询和反馈文档的相关度。随着查询分析的加深，如何从查询中提 取有用的信息也凸显的重要起来。比如“c a f ec i u bn e a rt i a n f us q u a r e ”这个查询， 我们要提取出“c a f ec l u b ”以及“t i a n f us q u a r e ”这两个有用的信息来表达用户 的搜索意图，那么提取的前提就是如何正确的对查询进行切分。 据我们研究得知，目前主要有3 种方法来进行英文查询的切分。它们分别是 基于互信息的查询切分；基于名词短语( n o u np h r a s e s ) 学习的s v m 切分以及基于 e m 训练算法的切分。我们在相关工作中对这三种方法进行了详细地分析和探讨。 在本文中，我们提出了一种无监督的查询切分方法。在主特征空间中，我们根据 查询词在特征空间投影的相似度进行切分。同时在本模型中，我们提出了一种新 的方法来确定主特征空间的维数。实验结果表明对照前人的工作，我们的模型很 大的提高了查询切分的效果。 本章结构如下：我们在2 2 节对前人工作进行了深入地分析和探讨并在2 3 节表述了我们的模型和相关算法。2 4 节为我们的实验部分。我们最后在2 5 节对 本章内容进行了总结和展望。 5 电子科技大学硕士学位论文 2 2 相关工作 尽管查询切分在查询分析中具有很大的重要性，但是至目前为止并没有太多 的相关研究。根据我们的学习了解，目前共计有3 种方法来进行查询切分，它们 分别是：1 基于互信息( m 咖a 1i n f o r m a t i o n ，m i ) 的查询切分【4 】；2 基于s v m 的查询 切分 5 】；3 基于e m 算法切分【6 1 。在详细阐述本算法之前，先介绍一下前面3 种切 分方法： 2 2 1 基于互信息的查询切分 在 4 中，r o s i ej o n e s 提出了利用互信息( p o i n t - w i s em u t u a li n f o r m a t i o n ) 来对查 询进行切分。他认为：如果两个相邻的词( 例如：a 和b ) 之间的互信息比较大， 那么他们就有理由被分到一起，否则他们就是属于不同切分块，即： ! ( 丝! 堡! 万( 2 1 ) p ( 4 ) p ( b ) 其中p ( o ) 表示该词在语料库( c o r p u s ) 出现的概率，它一般通过式2 - 2 估算得到。 p ( 彳) ： 丝! 堕堕丝 ( 2 2 ) n u m b e r o ( a l l w o r d s ) 万为预定的阈值，在该篇论文中，该阈值被经验地设置为8 。 该算法的优点是巧妙的运用了互信息这个物理特征来衡量词与词之间的紧密 程度，运算量也很小，但是这个算法也有与生俱来的缺点。首先该算法不能很好 的作用于长的查询上，比如在一个查询中，判断a 、b 、c 三个词是否应该被分 到一起，该算法只能通过分别计算a 和b 、b 和c 的互信息大小才能判断，即使 a 与b 、b 与c 的互信息都大，也不能说明a 、b 和c 应该被分到一起。其次， 从p ( ) 的估算过程来看，由于在估算过程中存在着大量的噪音和误差，导致了切 分结果不会太理想。 2 2 2 基于s v m 的切分方法 s h a n eb e r g s m a 在 5 中将查询切分看成一个查询词之间的分类任务。同一个 切分块中的查询词在经过分类器的作用下会被分为一类。在这个分类过程中，该 方法采用了如下分类特, 征( f e a t u r e ) - p a r t - o f - s p e e c ht a g s 、查询词的位置信息 6 第二章基于主特征空间相似度计算的查询切分 ( p o s i t i o n ) 、在互联网中出现的次数( w e bc o u n t s ) 等等。当支持向量机模型( s u p p o r t v e c t o r m a c h i n e ，s v m ) 用大量的人工标记好的数据进行训练之后，就可以用来对未 知的查询进行切分。 随着采用分类特征的增多以及训练数据的加大，切分的效果也相应的有所提 高。但是这个模型在切分过程中需要大量的训练数据，这点导致该模型无法大规 模地运用到互联网上，这是因为很难通过人们去标记足够刻画互联网特征的数据 以供算法学习。 2 2 3 基于e m 的切分方法 该方法是t a nb i n 在y a h o o ! 实习的时候提出的一种切分方法 6 1 ，相比较前两 种方法，该方法不仅在切分精度上有所提高，同时由于该方法是一种无监督 ( u n s u p e r v i s e d ) 的切分方法，也为工程运用做好了铺垫。该算法思想如下： 假设q = ，心为一个查询，它由n 个查询词组成。假设该查询有如下切 分：s = s i ) s ：占。现在，机器对语言的识别从某种角度来说，这种切分的可能性 p ( s ) 可以用来表示这种切分是否可取。利用乘法公式，该序列出现的概率等于每 一个词出现的概率相乘，于是尸( s ) 可展开为： p ( s ，q ) = p ( s 1 ) 尸( s 2 i s l ) p ( s 3 ls ls 2 ) p ( s 。i s l s 2 s m - i ) ( 2 - 3 ) 其中p ( s 。) 表示第一个切分块s ，出现的概率；p ( s ：lj 。) 是在已知第一个切分块 的前提下，第二个切分块出现的概率；以次类推。到了切分块s 。，它的出现概率 取决于它前面所有词。从计算上来看，各种可能性太多很难实现。该算法假定任 意一个切分块s ，的出现概率只同它前面的j 卜，有关( 即马尔可夫假设) ，于是s 出现 的概率就变为： p ( s ，q ) = p ( s 1 ) p ( s 2 h ) p ( s 3 is 2 ) p ( s 。i s 。一1 ) ( 2 - 4 ) 如果一个切分能使得该查询出现的概率最大，那么该切分就是正确的切分， 即：p ( g ) 达到最大。不难得到： p ( q ) = p ( s ，q ) ( 2 - 5 ) s 对于有n 个单词的q 来说，它共有2 ”1 种不同的切分。 该方法通过在y a h o o ! 互联网语料库中生成n g r a m s 及其对应的频率，并通过 e m 算法来使得p ( q ) 达到最大。同时该方法也引入了w i k i p e d i a 来辅助切分。 7 电子科技大学硕士学位论文 2 3 基于特征空间相似度的查询切分算法 在本节中，我们提出了通过计算查询词在其主要特征空间相似度的计算来对 查询进行切分。我们首先基于查询词在互联网中的共现( c o o c c u r r e n c e ) 频率来构建 查询词之间的关系矩阵，其次，通过对关系矩阵特征值的分析而建立其主要特征 空间。在此特征空间上，我们把查询词在关系矩阵中的向量投影在主特征空间上， 并通过计算投影之间的相似度来切分查询。 2 3 1 模型概述 在本模型中，我们的输入是一个t w o r d s 的查询q = w t w 2 ，输出是k 个 切分块q = s i s ，s 。首先我们用查询词n g r a m 的频率矩阵来刻画查询词之间的 关系。由于该频率矩阵是对称正定矩阵，所以它一定可以分解成实特征值矩阵和 实特征向量矩阵的乘积。通过选取k 个最大特征值对应的特征向量，我们建立了 主特征空间，并通过计算频率矩阵在主特征空间的投影的相似度来进行查询切分。 流程图及算法如下所示： 肛洳删 eigenvalues吟霉k p r i n c i p a l 图2 一l 切分算法流程图 具体步骤如下表所示。 表2 - 1 切分算法概述 第二章基于主特征空间相似度计算的查询切分 2 3 2 频率矩阵 频率矩阵( 或者称关系矩阵，a f f i n i t ym a t r i x 等) 通过查询词之间的频率来刻画 查询词之间的关系，这是查询切分的基础。在基于m i 以及e m 等相关方法中也 类似地引入了查询词之间的频率来刻画查询词之间的关系。在本模型中，我们用 一个对称正定的频率矩阵m = b “t 。来表达查询词之间的关系，其中m i , j 表示 为： m f ，2 f ( w t )i f i = j f ( w i w f + l ) i f i 歹 在上式中，( w i ) 表示查询词w j 的频率，f ( w iw i + ，叱) 表示查询词序列 w i w i + 1 在语料库中的频率。在这里，我们认为任意两个查询词之间的关系是 等价的，所以频率矩阵为对称矩阵。考虑到不同查询词在语料库中由于频率差异 而带来的影响，所以我们用式( 2 7 ) 对该频率矩阵进行归一化处理： m u 2 而2 x m f , j ( 2 7 ) 在本工作中，为了提高模型的精确度( 使用互联网作为语料库) 并减小计算的 复杂度，我们参考了文献 1 5 的方法，将数据估计基于g o o g l ea p i 返回的查询返 回相关文档的片段( s n i p p e t s ) - _ 进行计算。我们首先通过g o o g l es e a r c ha p i 来获取 查询g 的相关文档的。然后，在此相关文档的片段上来统计查询词序列出现的频 率。 2 3 3 主特征空间的建立 尽管矩阵m 表达了查询词之间的关系，但是如果直接用矩阵m 来进行查询 9 电子科技大学硕士学位论文 词的切分效果并不好。这是因为矩阵m 非常粗糙并且包含了大量的噪声。这些噪 声来自与我们的估计方法。针对这个问题，我们提出了将矩阵m 映射到其特征主 空间进行处理。在特征主空间上，用矩阵m 的投影来表示查询词之间的关系可以 有效的减少噪声，并突出查询词之间的关系。 我们首先对矩阵m 进行特征分解。对于对称正定矩阵似) 棚，他有玎个正特 征值以及对应的实特征向量。在这里特征值不妨表示为：a ( m ) = ，如，以) ， 并且这些特征值满足：t i i t 关系： 如以。这些特征值对应的特征向量被 表示为： v m ) = “，x , 2 ，) 。 我们假设选取前后个特征向量来组建特征空间，即特征空间 m 一= s p a n x i ，而，x k ) 。那么第f 个查询词在主特征空间的投影为： 口f ，口2 t ，口；) r = 2 ：1 ，x 2 ，- x n ) ( 2 - 8 ) 在2 3 5 节中，这些投影被用来计算查询词之间的相似性并对查询进行切分。 接下来，我们给出如何进行k 的选择。 2 3 4 参数k 的估计 参数k 的估计在查询切分中非常重要。因为根据贝叶斯理论不难判断任一个 查询词属于哪个切分块。由于在本模型中，我们引入了主要特征值，受到主成分 分析( p r i n c i p a lc o m p o n e n t sa n a l y s i s ) 的启发，我们根据前k 个特征值在所有特征值 中所占的比例进行选取k 。即：k 是满足下面方程的最小整数： 七 乃 上l 一万 ( 2 9 ) 以 i = 1 其中万为预先设计的阈值，通常范围在7 0 一9 0 期间。同时这种方法一般 在以 五+ 。时有效。但是在本模型中，根据矩阵m 的构造我们得知，主对角线 元素为1 并且非主对角线元素为【0 ，1 ) 之间的数，根据圆盘定理我们知道矩阵m 的 特征值相差不会太大，因此条件 + ，很难成立。因此在本模型中，我们引入 一个关于查询词个数的函数来代替万，即：k 是满足如下方程的最小整数： 1 0 第二章基于主特征空间相似度计算的查询切分 ，l 一1 ，l ( 2 1 0 ) 如果上述的尼个特征值为主要特征值，那么其在比例应该大约5 0 ，并且无 需超过1 - 1 n 。我们经验地选取了b 一1 ) n ) 2 是因为0 5 ( ( 咒一1 ) ，z ) 2 万，说明阈值太大而导致 切分块过多，这个时候万应该相应的减小，否则万应该相应的增加。 2 4 实验 2 4 1 数据 我们在本实验中所选用的数据为由b e r g s m aa n dw a n g 5 1 发布的数据。这个数 甲i ， 电子科技大学硕士学位论文 据集中包含了5 0 0 个互联网查询。这些查询是随机的取自a o l 查询日志。在这 5 0 0 个查询中，每个查询中都包含至少4 个查询词。同时，有3 位标记者( a n n o t a t o r s ) 独立地对这5 0 0 个查询进行切分，我们用a 、b 、c 来表示标记后的结果。不仅 如此，我们同时将a 、b 、c 三个数据集的交集( d