（模式识别与智能系统专业论文）基于查询词聚类的信息检索系统排序模型.pdf

摘要 随着万维网信息的急速膨胀，人们需要在以几何速度增长的冗繁信息中寻找 自己所需要的信息。搜索引擎逐渐成为人们日常生活中网络搜索的必备工具，而 且用户越来越关注网络搜索引擎的搜索性能和反馈结果。为了提高信息检索系统 的整体性能，研究者需要完善和研究信息检索系统的评价方法和排序模型，使得 信息检索系统反馈给用户文档更为相关。 排序学习理论( l e a r n i n g t or a n k ，l e t o r ) 是结合信息检索技术和机器学习 理论的一种新领域。l e t o r 理论目的是利用机器学习理论通过对训练集的自我 学习，建立一个文档集相关度的排序模型。目前存在的几种信息检索系统排序方 法都采用单一训练模型，其排序结果在几种传统的评估准则下表现出的性能还有 待提高。针对这个问题，本文提出一种基于伪相关反馈扩展的查询词聚类算法， 和基于查询词关键字的聚类算法相比，能够更好地解决查询词的简短性和模糊性 影响聚类效果的问题。该算法可以获得更加可靠的查询词之间的潜在联系，基于 这种潜在联系，本文进而提出一种新颖的基于查询词聚类的信息检索系统排序模 型，并对查询词采用分而治之的训练方法，其要点是将查询词分为多个训练模型 分别进行排序学习。使用该排序模型在o h s u m e d 公开数据集上做了四种模型 的实验，结果表明，这种分而治之的信息检索排序模型显著地提高了信息检索系 统的反馈性能，较基本的排序算法在p r e e i s i o n k 和n d c g k 的评价指标上有 了近5 1 0 的提高。 关键词：信息检索伪相关反馈查询词聚类排序模型排序学习理论分而治之 a b s t r a c t w i t ht h ee x p l o s i o no fi n f o r m a t i o no nt h ew o r l dw i d ew 曲，p e o p l eh a v et os e a r c h u s e f u li n f o r m a t i o na m o n gm a s s i v ed a t aw h i c hi si n c r e a s i n ga tag e o m e t r i c a lr a t e s i n c ew e bs e a r c he n g i n eh a sb e c o m et h em o s tp o p u l a rt o o lo fi n f o r m a t i o ns e a r c h i n g ， i t sp e r f o r m a n c ea n df e e d b a c kr e s u rh a v eb e e np a i dm o r ea n dm o r ea t t e n t i o nt h a n b e f o r e i no r d e rt od e v e l o pi n f o r m a t i o nr e t r i e v a lt e c h n i q u e st o t h i sd i r e c t i o n ，i ti s d e s i r a b l et od e v e l o pe v a l u a t i o na p p r o a c h e sa n dr a n k i n gm o d e l st h a tc r e d i ti rm e t h o d s f o rt h e i ra b i l i t yt or e t r i e v eh i g h l yr e l e v a n td o c u m e n t s l e a r n i n gt or a n kh a se m e r g e da sa na c t i v ea n dg r o w i n ga r e ao fr e s e a r c hb o t hi n i n f o r m a t i o nr e t r i e v a la n dm a c h i n el e a r n i n g t h eg o a lo fl e a r n i n gt or a n ki st o a u t o m a t i c a l l yl e a r nar a n k i n gm o d e lf r o mt r a i n i n gd a t a ，s u c ht h a tt h em o d e lc a ns o r t d o c u m e n t sa c c o r d i n gt ot h e i rd e g r e e so fr e l e v a n c e ，h o w e v e r , a si n d e n t i f i e di n t h i s p a p e r , w h e na l lt h eq u e r i e sa r el e a r n t w i t has i n g l em o d e l ，t h e r ea les i g n i f i c a n t v a r i a t i o n sa c r o s sq u e r i e si nt e r m so fap e r f o r m a n c em e a s u r e m e n t i nt h i sp a p e r , w e p r o p o s eaq u e r yc l u s t e r i n ga l g o r i t h mb a s e do nt h ee x p a n s i o no fp s e u d o - r e l e v a n c e f e e d b a c kd a t aw h i c hc a na u t o m a t i c a l l yl e a r nt h er e l a t i o n sb e t w e e nq u e r i e s t h e nw i t h t h er e l a t i o n so fq u e r i e s ，w ed e m o n s t r a t et h a ti ti sh i g h l yb e n e f i c i a lt od i v i d eq u e r i e s i n t om u l t i p l eg r o u p sa n dc o n q u e rs e a r c hr a n k i n gb a s e do nq u e r ys e p a r a t i o n w e c o n d u c tf o u rs i g n i f i c a n te x p e r i m e n t so nt h ep u b l i cd a t ao h s u m e dw i t ht h ed i v i d e a n dc o n q u e rs e a r c hr a n k i n gm o d e l ，a n dt h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h e a l g o r i t h mw ep r o p o s e dp e r f o r m sw e l lo nt h ei n f o r m a t i o nr e t r i e v a ls y s t e mr a n k i n g m o d e la n dd r a w i n gad r a m a t i c a l l yi n c r e a s i n gi ni rs y s t e mp e r f o r m a n c em e a s u r e s ， e s p e c i a l l ya5 - p e r c e n tt o 10 一p e r c e n ti m p r o v e m e n to np r e c i s i o n ka n db d c g k m e t r i c s k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，p s e u d o r e l e v a n c ef e e d b a c k , q u e r yc l u s t e r i n g ， r a n k i n gm o d e l ，l e a r n i n gt or a n k , d i v i d ea n dc o n q u e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丕鲞盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 靴敝储群：锄擀嗍：叩引肘日 学位论文版权使用授权书 本学位论文作者完全了解：苤鲞盘茔有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：万励 签字日期：1 “月，日 导师躲i 矬之 签字吼呷年月日 第一章绪论 1 1 研究背景与目的 第一章绪论弟一早三百记 在互联网发展早期，以雅虎( y a h o o ) 为代表的网站分类目录查询非常流行。 由于网站分类是有很大程度人工干预的，致使分类的结果并非让人满意：同时当 用户查询相关网页时，也只能通过一层层的点击来查找自己想要的网站，这样的 搜索效果和速度无法让人接受，直到一种新互联网信息模型的出现改变了用户搜 索信息的习惯，它就是“搜索引擎”。 搜索引擎( s e a r c he n g i n e ) 是指根据一定的策略、运用特定的计算机程序搜 集互联网上的信息，在对信息进行组织和处理后，为用户提供检索服务的系统。 目前国内外有b a i d u ：g o o g l e 、y a h o o 等著名的搜索引擎，从使用者的角度看， 搜索引擎提供了一个搜索框的网络页面，在搜索框输入要查询的词语( q u e r yo r k e y w o r d ) ，通过浏览器提交给搜索引擎后，搜索引擎会给用户反馈一份和搜索 词语相关的信息列表。 在当今的信息时代，搜索引擎已经成为了人们生活中不可或缺的重要工具。 随着互联网的蓬勃发展，互联网信息数据以几何速度增长，并且信息渐渐的多元 化，导致搜索引擎面对海量数据时，对用户提交的搜索词语反馈的结果往往不尽 人意。因此，在搜索引擎技术领域中，找到一种合理、有效并且高效的排序学习 方法成为当今搜索引擎技术的一大难题。目前流行的几种信息检索排序方法都采 用了单一训练模型，其排序结果在几种性能评估准则下并不令人满意。为了解决 此问题，本文提出一种基于查询词聚类的信息检索排序模型，此模型采用分而治 之的训练方法，大大提高了信息检索系统的反馈性能，并且在p r e c i s i o n k 和 n d c g k 的评价指标上有了显著的提高。 1 2 研究现状 1 2 1 信息检索 信息检索( i n f o r m a t i o nr e t r i e v a l ) 【1 ，2 ，3 ，4 1 是一门在海量数据文档中搜索相关 信息的技术。通常是用户在网络上提交一个要查询的短语或者句子，信息检索系 统通过一系列的算法，最终给用户展示出一份相关的信息列表。在信息检索系统 第一章绪论 中，每个对象是一个储存信息的实体，在用户提交查询短语或者句子后，信息检 索系统会对这个检索词语在整个数据库中进行匹配，返回系统认为最相关的一系 列信息。通常的搜索方式有：文本信息、图片信息和视频信息。网络搜索引擎是 最典型的信息检索系统。 大部分网络搜索引擎是由四部分组成： 一页面抓取器 世界上第一个网页抓取器( s p i d e r ) 程序是由m i tm a t t h e wg r a y 编写的w o r l d w i d ew e bw a n d e r e r ，用于追踪互联网发展规模。随着网页抓取器的改善，它已 经成为了搜索引擎一个重要的组成部分，主要的功能是抓取万维网( w w w ) 上 的网页信息，并且下载到资源服务器上。 二页面分析器 页面分析器的主要功能是分析网页抓取器抓取下来的网页内容信息。其中最 关键的是“分词技术”，所谓分词技术是根据自然语言的特点，把复杂的较长的 短语或句子分解成容易理解，并且有特殊含义的词语。目前主流的算法有三类： 基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。信息 检索系统利用分词技术更加深入的理解被抓取的网页信息从而为索引系统提供 丰富的信息资源。 三索引系统 信息检索系统中的索引系统是根据网页分析器的分析结果，建立一个关于词 语的倒排索引系统，该系统利用统计学理论知识，分析了网页与词的关联关系， 为信息检索系统的排序模型提供了充分的数据支持。 四查询检索器 查询检索器的主要目的是当用户提交某个查询词时，反馈给用户一份相关文 档集合。其中最核心的部分是基于文档和查询词相关度分析的排序模型，此排序 模型的优劣在很大程度上反映了整套信息检索系统的性能。 本篇论文主要讨论的是搜索引擎系统中第四部分的排序模型，本文利用查询 词的聚类算法提出一种分而治之的排序模型，从而提高信息检索系统性能。 1 2 2 数据挖掘 数据挖掘( d a t am i n i n g ) 【5 ，6 ，7 1 是从海量数据中获取有效的、新颖的、潜在有 用的模式的非平凡过程，其典型的结构如图1 1 所示。数据挖掘的广义观点：数 据挖掘是从存放在数据库，数据仓库或其他信息库里大量的数据中“挖掘”有意 义知识的过程。数据挖掘又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 。近年来，数据挖掘引起了信息产业的极大关注，主要原因是 第一章绪论 在当今的信息时代，数据量以几何速度增长，人们需要将这些海量数据转化成有 用的信息和知识。获取的信息和知识可以广泛的应用于各个领域，例如搜索引擎、 电子商务、市场分析、科学调研等等。 数豁露醇孵辑誓 漆# p 二 两1 _ ， _ j 一 戢弼，翱霉赢船遘事畴 图1 - 1 典型数据挖掘系统的结构 数据挖掘技术利用了传统的概率统计模型( 如抽样、估计和假设检验等) 、 人工智能、模式识别和机器学习等领域的相关知识，同时也迅速采纳了来自进化 计算、信息论嘲、信号处理、可视化和信息检索领域的重要结论。 网络数据挖掘( w e bm i n i n g ) 是一种将传统数据挖掘技术应用在互联网模式 发现中的一种研究方向。根据其分析数据的目的可以分为内容相关性挖掘、结构 相关性挖掘和日志挖掘三个部分： 一内容相关性挖掘( w e bc o n t e n tm i n i n g ) 内容相关性挖掘是在互联网中应用数据挖掘技术，从网络的文本信息、 图片信息和视频信息中挖掘出所需要的知识。其中文本数据挖掘应用最 为广泛，此技术通常在自然语言处理( 9 ，( n a t u r a ll a n g u a g ep r o c e s s i n g ， n l p ) 和信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 领域中应用。 二结构相关性挖掘( w e bs t r u c t u r em i n i n g ) 结构相关性挖掘通常是利用图论知识分析互联网中每个网站之间的关 系。其中最常见的两种分析手段是：a ) 通过网页上的超链接( h y p e r l i n k s ) 来分析页面与页面之间的关系；b ) 利用文档的标签( t a g ) 构造一个树 玮 第一章绪论 型的文档结构，分析网页之间结构的相关性。 三日志挖掘( w e bl o gm i n i n g ) 日志挖掘是一种商业性很强的数据挖掘应用领域，它利用用户在网络上 商业系统使用时留下的日志文件来分析用户的行为习惯，例如在网络搜 索引擎的日志中分析用户对于每个查询词反馈结果的满意度，在电子商 务平台的日志中分析用户对各类商品的喜好程度】。 1 3 本文结构 依据本论文的研究内容和相关知识的结构性。论文结构如下： 第一章介绍课题的研究背景、目的和意义，综述信息检索技术和数据挖掘技 术在互联网的应用。 第二章介绍与本文相关的信息检索领域基础知识。 第三章提出基于伪相关反馈的查询词聚类算法和信息检索系统排序模型，进 而对一套分而治之的信息检索系统排序模型框架进行详细的设计。 第四章阐述信息检索系统排序模型的实验数据、实验设置和实验结果，分析 实验结果，验证算法的可行性。 第五章总结本论文的研究工作，并且对未来研究工作的方向提出建议和展 望。 第二章信息检索技术理论基础 第二章信息检索技术理论基础 2 1 信息检索系统的评价方法概述 信息时代，互联网发展飞速，搜索引擎技术是利用关键字组合，在网络上查 找相关信息，并按照它们与关键字的匹配程度进行排序，然后返回给用户查看的 技术。随着互联网的迅速发展，使用搜索引擎己成为网络用户获取网络资源的最 主要途径。近几年来，全球出现了各种各样的搜索引擎。这些搜索引擎在人们对 信息的获取过程中起到了很重要的作用，但是目前搜索引擎给出的信息质量仍然 不高，即搜索结果往往与用户需要的不是很符合，需要用户继续在结果列表中人 工查找自己需要的信息。 目前主要的搜索引擎可分为目录式搜索引擎和基于关键字的搜索引擎： 目录式搜索引擎的思路是对网页库预分类j 然后由用户选择自己需要哪一类 的网页，并到相应的目录下去查找，目前最具代表性的分类目录式搜索引擎是 y a h o o ( h t t p ：l l w w w y a h o o c o r n ) 。但是，为了提交给用户一组最好的搜索结果往 往需要很细的类别划分尺度，而对于现有的手工和自动分类技术应用于海量的网 络信息是不现实的，另外即使搜索引擎提供了很细的类别，用户的选择过程也将 变的非常复杂，而且不能保证用户的判断与搜索引擎已有的分类是完全吻合的。 基于关键字的搜索引擎，目前互联网上的搜索引擎大多数采用了基于关键字 的查询技术，其典型代表有g o o g l e ( h t t p ：w w w g o o g l e c o r n ) ，l i v es e a r c h ( h t t p ：t w w w 1 i v e c o m ) 和b a i d u ( h t t p ：w w w b a i d u c o r n ) 。这类搜索引擎通过程 序收集并索引的信息资源量极其庞大，而用户的提问语句却大多由几个词组成， 由于词语本身的多义性导致搜索引擎很难确定用户的需求，这种情况会导致数量 庞大的搜索结果且不能保证相关度，用户需要花费巨大的精力在搜索引擎的结果 中进行浏览筛选。 鉴于用户对搜索引擎的使用越来越频繁，要求也就越来越高，建立一套合理 的搜索引擎评价标准是当今很热的一个研究论题。信息检索系统( i n f o r m a t i o n r e t r i e v a ls y s t e m ) 的评价方法一直是信息检索方向研究的重点。直观上讲信息检 索系统的检索速度、反馈结果的精确度是评价信息检索系统的重要标准。通常对 于一个信息检索系统做出评价需要如下信息： a ) 一份文档集合( ad o c u m e n tc o l l e c t i o n ) 第二章信息检索技术理论基础 b ) 一组用来测试的查询短语( a t e s ts u i t eo f q u e r i e s ) c ) 一组人工标定的数据( a s e to f r e l e v a n c ej u d g m e n t ) ，如4 1 1 节介绍的显 相关反馈数据( e x p l i c i tf e e d b a c k ) 整套评价标准围绕着相关( r e l e v a n t ) 和不相关( i r r e l e v a n t ) 文档的定义进行 展开。文档的相关性可以从人工标定的数据中得到，通过对测试文档集合的统计， 计算出一种描述信息检索系统优劣的分数。 目前最著名的测试文档集有： 1 ) t r e c 1 2 】( t e x tr e t r i e v a lc o n f e r e n c e ) 它是文本检索领域人气最旺、最权威的评测会议，由美国国防部和美国 国家技术标准局( n i s t ) 联合主办。自从1 9 9 1 年举办第一届会议起，每年 的参与者包括m i t 、s t a n f o r d 、u c b 、北京大学、微软研究院、g o o g l e 、i b m 研究院、新加坡国立大学、台湾大学、清华犬学、复旦大学、加拿大q u e e n s 大学、日本东京大学、香港中文大学、英国城市大学等当今i t 界一流学府 和企业科研机构，并且在不断增加。该会议细分为几大主要方向：问题回答 ( q a ) 、特定领域检索( l e g a l 、g e n o m i c s 、e n t e r p r i s e 、b l o g ) 、传统w 曲检 索等。会议负责组织收集并向与会者提供标准的语料库( c o r p u s 八检索条 件和问题集( q u e r ys e t ) 、以及评测办法( e v a l u a t i o n ) ，与会者则被要求在规 定的时间内构造检索系统并提交检索结果( r u n s ) ，由会议负责评测各个检 索结果的优劣，最终依据评测结果召开大会进行学术交流，发表会议论文。 2 ) n e w s g r o u p s 1 3 】 2 0n e w s g r o u p s 数据集是最早由k e nl a n g 搜集的n e w s g r o u p s 的文档，共 有2 0 个不同的类别。目前2 0 n e w s g r o u p s 数据集已经在机器学习、信息检索 和文本分类等领域广泛被应用。 3 ) r e u t e r s 2 15 7 8 和r e u t e r s r c v l 州 r e u t e r s 2 1 5 7 8 数据集搜集了路透社2 1 ，5 7 8 篇文章，r e u t e r s r c v l 则搜集 了8 0 6 ，7 9 1 篇文章，这两套r e u t e r s 数据集同样适用于机器学习、信息检索和 文本分类领域。 4 ) 商业用途的搜索引擎数据 现在被广泛使用的搜索引擎，如b a i d u 、g o o g l e 、y a h o o 和l i v es e a r c h 等， 由于每天都有超大规模的用户群体在使用网络搜索引擎，其用户的点击行为都作 为搜索引擎日志进行保留，此日志数据是分析信息检索系统最佳的实验数据。 第二章信息检索技术理论基础 2 2 聚类算法 2 2 1 聚类算法简介 将由一组实体组成的集合按照实体之间的某种相似性分成多个类别的过程 称为聚判”】( c l u s t e r i n g ) 。由聚类所生成的簇是一组数据对象的集合，这些对象 与同一个簇中的对象彼此相似，但与其他簇中的对象相异。聚类算法是一种经典 的非监督学习方法，它与监督学习方法的根本区别在于，聚类算法在训练分类器 时并没有标定数据作为训练指导。 聚类分析方法是数据统计分析学中常见的一门技术，此技术已经成功的应用 于机器学习、数据挖掘、信息检索、模式识别、图像分析和生物学等重要领域。 传统的聚类分析计算方法主要有如下几种： 1 ) 划分方法( p a r t i t i o n i n gm e t h o d s ) 2 ) 层次方法( h i e r a r c h i c a lm e t h o d s ) 3 ) 基于密度的聚类方法( d e n s i t y - b a s e dc l u s t e r i n gm e t h o d s ) 4 ) 基于网格的聚类方法( g r i d b a s e dc l u s t e r i n gm e t h o d s j 5 ) 基于模型的聚类方法( m o d e l b a s e dc l u s t e r i n gm e t h o d s ) 2 2 2k - m e a n s 聚类算法 在统计学理论和机器学习理论中，k m e a n sf 1 6 ，”1 算法是一种基于期望最大化 ( e x p e c t a t i o n m a x i m i z a t i o n ，e m ) 框架的聚类分析算法，它利用迭代的思想寻 找出k 个簇的中心点。 给出一组样本点集合( 五，x 2 ，矗) ，用刀维向量表示。k m e a n s 聚类算法的目 的在于寻找一种方法将样本点集合分为k 个部分s = 瓶，是，& ，使得每个部 分内部样本点到其中心点的距离最小， 鹕p i n 善k 到_ 一以u 2 其中鸬是墨的均值。 由于k m e a n s 算法中k 值的选取对于数据集有很强的依赖性，这样就导致在 不同的k 值下，k - m e a n s 算法的聚类结果具有不稳定性，因此在实验时往往都采 用不同的k 值来观察数据的聚类结果。 第二章信息检索技术理论基础 2 3 支持向量机 2 3 1 支持向量机简介 随着人工智能理念深入人心，模式识别、机器学习等领域的技术更受广大研 究者关注。支持向量机【1 8 l9 】( s u p p o r t v e c t o r m a c h i n e ，s v m ) 是建立在统计学基 础之上发展起来的一种新型机器学习方法。支持向量机在模式识别、回归分析、 函数逼近、分类问题上有很广泛的应用。 支持向量机( s v m ) 理论的核心内容在1 9 9 2 年由v a p n i k 2 0 】等人开始提出的， 是到目前为止统计学习理论中最成功的著作之一，但它的研究仍处于不断发展的 阶段。支持向量机同时也是数据挖掘( d a t am i n i n g ) 中经常使用的方法，能非常 有效的处理线性回归问题( 时间序列分析) 和文本( 图像，视频) 分类问题，判 别分析问题等。 支持向量机的基本工作原理是基于统计学理论中的监督学习，在经典的分类 和回归问题中，支持向量机通过对训练数据( t r a i n i n gd a t a ) 的观察与学习，对盯 维的测试数据( t e s t i n gd a t a ) 反馈出一个标定( 1 a b e l ) 集合。在实际操作中，支 持向量机在盯维的训练样本空间中，找到一个合理的位置划定超平面 ( h y p e r - p l a n e ) ，在此过程中尽量满足超平面到两类数据的距离最大。 数据分类在机器学习理论中常见的一个问题。假设现给定一些分成两类的样 本点集，现要考虑的是把一个新的点分到哪类之中? 在支持向量机模型中，一组 数据( d a m ) 被表示为一个p 维的向量，现在要判断的是这些数据集是否能被一 些p 一1 维的点集分开，这就是所谓的线性分类器( 1 i n e a r c l a s s i f i e r ) 。然而在分类 中，一般会有很多超平面可以将原数据集分开，支持向量机更关注的是能不能找 到一个超平面使得两个数据最大程度的分开，也就是找到一个离两类数据的距离 和最大的超平面。在这条准则下，需要找到两个平行的超平面，使得每个超平面 离训练数据最近。如果这样的超平面是现实存在的，那么称它为最大边际超平面 ( m a x i m u m m a r g i nh y p e r - p l a n e ) ，而此时构造的分类器叫做最大边际分类器 ( m a x i m t t m m a r g i nc l a s s i f i e r ) 。 2 3 2 分类基本原理分析 文本分类是信息学中一个基础问题，文本分类的目的将一个文档集合基于文 档内容，通过分类器分成多种类别。文本分类方法可以粗略的分为两种方法：监 督学习方法【2 1 1 ( s u p e r v i s e dl e a r n i n g ) 和非监督学习方法【2 2 ，2 3 1 ( u n s u p e r v i s e d l e a r n i n g ) 。前者在分类学习的过程中提供了一份含有标定的数据集，分类器根据 第二章信息检索技术理论基础 标定数据集的指导对测试数据集进行分类，而后者在分类的过程中没有任何标定 数据。随着专家、学者近年来的研究，一种介于两者之间的半监督学习方法 ( s e m i s u p e r v i s e dl e a r n i n g ) 对文本分类问题也有了新的突破。 支持向量机是根据典型的监督学习方法进行文本分类的，在文本分类任务中 最为基础的是二分类问题( b i n a r yc l a s s i f i c a t i o n p r o b l e m ) ，图2 1 形象了描述了二 分类问题中支持向量机对训练数据集的训练过程。如图2 1 所示，要想将c l a s s l 和c l a s s 2 的样本数据点分开，超平面a 和b 都是合理的分类线。 图2 1 二分类问题 下面以二分类问题为例，详细介绍支持向量机分类原理： 在二分类问题中，设训练样本集为( 薯，”) ，i = 1 ，2 ，以，n 为训练样本的数 量，五r d 为训练样本，” + l ，一l 是要输入的样本x 的类标记。支持向量机i 的根本目的是寻找一个最优的划分超平面( 如图2 2 ) ，即最大区分两类样本的超 平面，也就是构造上述提到的最大边际分类器。最优分类超平面不但能将所有样 本正确分开，使得在训练数据中错分率为0 ，而且还能够使样本中两类样本的边 际最大，也就是最大化分开原始的两类数据。 若给定的样本数据集是线性可分的，d 维空间中的线性判别函数为 g ( x ) = 国x + b ，分类平面的方程为国x + b = 0 。将判别函数归一化，使离分类平 面最近的样本点满足ig ( x ) i _ 1 。若分类面对所有样本都能正确的分类，则必须满 足： 第二章信息检索技术理论基础 只( 缈一+ 6 ) 1 i = 1 ，2 ，玎 容易证明出来，两个超平面的方程为h j ：功x + 6 = 1 和h ：国x ，+ b = 一1 ，它 ， 们之间的边际宽度为d = 二l 。通过边际的表达式可以推出，为了使超平面成为 0 3 边际最大的超平面，也就是使d 值最大化，相当于使l | 缈i i ( 或者l l 缈1 1 2 ) 最小。 因此，分类的超平面h ：缈x + 6 = 0 为最优，当且仅当( 缈，6 ) 是下面最优问题的可 行解： m i n ：迎 2 s t ： y i ( c o x i + 6 ) 1 i = 1 ，2 ，? 图2 - 2 分类问题中的超平面 通过拉格朗日乘数、法【2 4 1 ( l a g r a n g em u l t i p l i e r ) ，可以将最优化方程变形为： 。= 三1 怕1 1 2 一喜q 【巾 垆1 】 其中c t , ( i = l ，2 ，哟为正l a n g r a n g e 乘子，需要对国和b 求l a n g r a n g e 函数的极 小值。 因为上述问题是一个凸二次规划问题，等价于它的对偶( d u a l ) 问题： 第二章信息检索技术理论基础 m x k = 主q 一1 1 圳2 一主q 口，埘一z ， r ie ，i s t ：主q _ = 0 q 扎j - l 卫n 上述方法是在训练样本数据是线性可分的前提下推导出来的，也称为“线性 分界面硬间隔”。当训练样本中只有少部分点不是线性可分时，可以采用惩罚的 办法，做出一个“线性分界面软间隔”其基本的最优化模型为： m i n 恻i + c ； j 7 f r b ) + 1 一f 其中c 为某个固定的常数，它实际上起控制对错分样本惩罚程度的作用 用拉格朗日乘数法及对偶原理，得到线性不可分情况下的对偶问题： 2 3 3 核方法 一k = 喜q 一扣f 一毫q q y j y j x ，一 s ， 喜q h = 。，c z q = 仉z = ，z ，一 尽管如此依然会有很多训练样本集线性不划分，其主要原因是该训练集的大 部分数据是线性不可分的，例如图2 3 所示的两组数据。 器霸+ 遮 蜓霉 “：受盖血二；：塞1 图2 3 线性不可分 辔。一 t ： 一 第二章信息检索技术理论基础 对于非线性可分的数据集，超平面的分类能力是有限的，为此支持向量机对 分类数据进行了非线性特征映射，即( x ) ：r j e ，将数据映射到某一更高维度 特征空间中，从而能够线性可分，然后在特征空间中构造一个线性可分的分 类器。 由于优化函数和分类函数都涉及到样本间的内积运算( 誓x ，) ，因此在变换 后的高维空间e 中也需要进行内积运算( 矽( 誓) ( x ，) ) 。根据泛函理论，如果核函 数k ( x 。x ，) 满足m e r c e r 条件，则它对应某变换空间中的内积也可以表示为 ( 薯) 矽( x ，) = k ( 五，x ，) 。因此采用适当的核函数k ( 薯，x ，) 就可以代替向高维空间 的非线性映射，实现某一线性变换后的线性分类。此时该问题的最优化模型可以 表示为： m a x ：厶= 喜一扣炉一毫q 哆 盼调) s z y o ! i y i = 0 ，c a i 0 ， i = 1 2 ，玎 。j ；_ _ _ 相应的支持向量机决策函数为：g c x ，= s g n ( x 倒咒k c 薯，一，+ 6 在支持向量机的核方法【2 5 , 2 6 t ：卢，要求所述驯仫困烈必、刎z 俩* 4 4 - 足m e r c e r 定理， m e r c e r 定理( m e r c e r1 9 0 9 ) 对称核函数k ( 而y ) 具有h i l b e r t 空间中内积形式的充要条件是： ，k ( x ，y ) g ( x ) g ( y ) d x d y 0 对任何平方可积函数g 成立，则k ( x ，y ) 称为m e r c e r 核。 在支持向量机的一般使用中，通常使用如下满足m e r c e r 条件的核函数： 多项式核： k ( x ，y ) = o ) ，+ 1 ) ” r b f 核： k ( x e x - v ( x - q ，1 1 2 ) 2 层n n s( 只对某些参数 ，f 成立) ： k ( x , y 笋i i 蒜 第二章信息检索技术理论基础 2 3 4 支持向量机小结 支持向量机是近年来统计学习理论中一项重大的突破，鉴于支持向量机模型 强有力的理论背景，高度的准确度，支持向量机模型广受学者欢迎。先后应用在 文本分类、手写字符识别、人脸识别、语音识别和搜索引擎等技术领域，例如图 2 - 4 是一张普通的照片，为了抽取照片中的人像，则可以利用支持向量机模型的 分类技术将照片中的人和景分开，从而达到预期的目的。 图2 4 支持向量机模型的应用 当有如下条件时支持向量机对于数据的处理有独到的优势 数据丰富，模型信息缺乏经典的数值模型无能为力时 非线性可分，高维数据经典的线性分类法无能为力时 但支持向量机模型也具有自身的弱点 支持向量机的学习是高度依赖于参数的 当线性不可分时适当的核函数的选择是个大问题 在选择核函数后，支持向量机很难确定适合模型的核参数 第三章算法模型设计 第三章算法模型设计 在信息高速发展的时代，互联网信息也随着飞速更新，信息量以几何速度增 长，随之而来的是互联网信息大爆炸，在错综复杂的互联网中，如何能找到自己 需要的信息知识点成为了每位用户的难题。 但在海量数据中，能够检索出令用户完全满意的结果并不是一件容易的工 作，尤其是有些查询词有很多不同的含义。例如在网络搜素引擎中搜索“a p p l e ” 查询词，它可以表示一种大家熟知的水果，也可以认为是一种电子产品的商标： 再比如在网络搜索引擎中搜索“f i f a 2 0 0 6 ”，它可以表示世界足球组织，2 0 0 6 年足球世界杯，也可以理解为一款经典的电脑游戏。从上面的例子看得出来，一 个查询词( q u e r y ) 的含义非常丰富，含义的多种多样性增大了信息检索系统对 反馈精度的控制难度。还有另一种与时俱进的查询词，例如查询词“b a r c e l o n a ”， 以前人们可以认为它是西班牙的一个著名城市，或者是欧洲的一个知名足球俱乐 部，但在近期的计算机硬件发展下，它又是a m d 公司新推出的一款原生四核 c p u ，类似于这样的查询词还有很多，如果一个搜索引擎能够把这些查询词的反 馈结果做的更好，则需要实时的更新自己的文档集合，更重要的是需要优化搜索 引擎中使用的排序算法模型。 上述的查询词之所以有难度，归根到底的原因是由于它们的含义多种多样， 但还有一种比较偏僻的查询词或者含义复杂的查询词同样对网络搜索引擎是一 种冲击，例如查询词“n o d 3 2 是免费的吗”。对于这种有“难度”的查询词搜索 结果，是当今信息检索技术面临的一项重大的挑战。 本文从上述的问题角度分析，提出一种基于伪相关反馈的查询词聚类算法， 此算法能够有效的分析出查询词之间的潜在联系。根据这种潜在的联系，本文进 而提出一种新颖的分而治之的信息检索系统排序模型，该模型从本质上减轻了偏 僻、较“难”的查询词对于信息检索系统排序结果的影响，提高了信息检索系统 的反馈性能。 本章将对基于伪相关反馈扩展的查询词聚类算法和信息检索系统排序模型 算法进行详细的设计，并给出一套分而治之的信息检索系统排序模型算法框架。 此框架中利用伪相关反馈数据对查询词的含义进行扩展，然后用聚类方法分析查 询词之间的潜在联系，并将查询词训练模型分组进行学习训练，进而提高网络搜 索引擎的排序结果。 第三章算法模型设计 3 1 基于伪相关反馈的查询词聚类算法设计 3 1 1 伪相关反馈 伪相关反馈( p s e u d o f e e d b a c k 又称b l i n df e e d b a c k ) 1 2 7 1 是一种特殊的反馈 信息。在信息检索技术中，伪相关反馈数据可以看作是查询词含义上的一种拓展 和延伸。 建立伪相关反馈的重要前提是，它认为在某一个性能和精度较高的搜索引擘 中反馈的前岸篇文档就是相关的。通过这个假设，可以简单的将一个查询词提 交刊搜索引擎上，将其反馈的前置篇文档都认为是这个查询词的相关文档，这样 第三章算法模型设计 就可以建立出一个完整的伪相关反馈数据集。 图3 - 1 的例子中，在b a i d u 网络搜索引擎上搜索“n o d 3 2 是免费的吗”关键 字，其搜索结果中并没有任何一个文档直接回答了该问题，而是更多的n o d 3 2 的 相关信息，可见搜索引擎更看重了“n o d 3 2 ”这个关键字，而忽略掉了“免费”。 在网络搜索引擎的反馈数据中，位置靠前的文档都是与该查询词息息相关 的，通常在实验中取k = 5 或k = 1 0 。例如图3 1 中前五篇文档：“n o d 3 2 防病 毒软件”，“n o d 3 2p p l i v e 专用版”，“n o d 3 2 新闻资讯”，“p p l i v r 免费试用 1 8 0 天e s e tn o d 3 2 防病毒软件9 9 “n o d 3 2 升级”，这些文档所组成的集合就形 成了一组描述这个查询词关键字的反馈信息，称它为伪相关反馈数据。 伪相关反馈数据的重要应用在于对查询词的扩展( q u e r ye x p a n s i o n ) 。查询 词扩展是为一些较为偏僻、意义较“难”理解的查询词寻找同类词或者代替词的 技术，它合理的解决一些生僻查询词使得搜索精度下降的问题，例如图3 1 中， 搜索引擎关于查询词“n o d 3 2 是免费的吗”的结果中含有大量的“防病毒软件” 和“试用”等相关词语，这些含义上的扩展也为查询词分类聚类等技术做了强有 力的支持。 3 1 2 查询词聚类算法设计 文本聚类问题【2 8 】( t e x t c l u s t e r i n gp r o b l e m ) 是数据挖掘领域中一个常见的问 题，其主旨在于将一组文档按照某种相似度进行非监督学习分类。例如在搜索引 擎中，当用户提交一个查询词后，搜索引擎可能会反馈多类网页，不便于用户查 找自己所需要的相关信息，文本聚类算法则可以将所有反馈网页进行分组，可见 聚类后的网页结果更易于用户使用。 查询词聚类的目的是为了将用户提交的查询词进行非监督学习分类，更重要 的是它可以协调帮助提高信息检索系统的反馈性能，为开发者提供更好的信息检 索系统研发数据。例如当用户输入“a p p l e ”查询词时，搜索引擎或者认为用户 是希望查询常见的水果，或者认为用户查询一类电子产品，或者认为用户在搜索 某一个著名玎企业。这种查询词的模糊性不仅仅扰乱了信息检索系统对于用户 需求的判断，更重要的是干扰了广告服务的投放策略。如果查询词聚类问题能够 合理的解决，信息检索系统则可以通过该查询词的同类词语来判断该查询词的具 体含义。 目前比较流行的查询词聚类算法是直接按照查询词的关键字( 分词结果) 结 合文本聚类的方法进行聚类的。由于用户提交到信息检索系统中的查询词往往都 很简短，但含义非常丰富，有时不同用户对同一个查询词的理解也有很大的差距。 如果只是基于查询词本身的关键字进行本文聚类分析，那么从直观角度上看，这 第三章算法模型设计 样的聚类算法并没有解决查询词简短、含糊的关键问题，因此聚类的效果不会很 理想。所以在查询