（计算机应用技术专业论文）基于粒计算的智能搜索引擎技术研究.pdf

摘要 随着互联网的发展与普及，搜索引擎的使用已经成为人们学习工作中获取 信息的重要手段之一因此，要提高搜索引擎的搜索效率，除了向人们普及正 确的使用方法和技巧外，对搜索引擎本身的搜索原理改进也势在必行。 智能搜索是人工智能中的一个重要研究领域。众所周知，人工智能所面对 的问题通常是不确定的、模糊的、不完整的、海量的信息，无法便捷的找到一 条常规问题求解路径，但是如果搜索问题的规模不是很大，使用盲目穷举的搜 索策略在某种程度上能够发挥作用，如广度优先搜索和深度优先搜索，由于它 们计算复杂度相对比较容易控制，因此被广泛应用在小规模的专家系统中。 而反观实际的人工智能应用，问题的求解规模一般都非常大，可供选择的 求解方案也比较多，此时仍然采用单纯的穷举搜索策略就不能解决问题了，而 启发式搜索通过使用经验性的知识指导搜索的方向，克服了搜索的盲目性，提 高了系统运行效率。但是目前所有的启发式搜索算法都未能克服计算量的指数 爆炸问题。 粒计算是专门针对人工智能中的复杂问题求解而产生的理论，属于软计算 科学的一个分支，是信息处理的一种新的概念和范式，覆盖了所有有关粒度的 理论、方法、技术和工具的研究，其思想实质是用简单易求、低成本的满足近 似精度的解替代精确解，专门针对不精确、不完整、不确定和海量的信息来实 现智能系统控制的易处理性、鲁棒性、低代价性。 本文尝试将商空间粒度的原理应用到智能搜索引擎中，提出了粒聚类和粒 统计启发式搜索算法，着重对数据的粒度原理与使用进行深入的剖析研究。这 两种算法的关键在于运用了商空间的分层思想，也就是粒度的划分方式，基于 这种划分的思想，不但减少了算法中很多不必要的操作，而且降低了运算的复 杂度。在文章的最后，本文对粒聚类算法与粒统计启发式搜索算法进行了验证， 实验将其应用于一个类别散乱的小型论文库中，对库中数据进行重构并在此基 础上进行检索，获得了比经典算法更好的查找效果。 关键词：商空间；粒计算；智能搜索引擎；粒聚类；粒统计启发式搜索。 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r a c t ，s e a r c he n g i n ea l r e a d yb e c o m e so n eo ft h e i m p o r t a n tm e a n s t oo b t a i ni n f o r m a t i o ni nt h ep e o p l e ss t u d ya n dw o r k t h e r e f o r e ，i t s i m p e r a t i v et oi m p r o v et h ee f f i c i e n c yo fs e a r c he n g i n e ，o nt h eo n eh a n d ，w en e e dt o p o p u l a rt h ec o r r e c t l yw a ya n ds k i l l so nt h eu s eo fs e a r c he n g i n e s ，o nt h eo t h e rh a n d , t oi m p r o v es e a r c he n g i n e so p e r a t em o d ei sa l s oi m p o r t a n t a r t i f i c i a li n t e l l i g e n c es e a r c hi sa ni m p o r t a n ta r e ao fr e s e a r c h ，a sw ea l lk n o w , t h ep r o b l e m sa b o u ta r t i f i c i a li n t e l l i g e n c ei su s u a l l yu n c e r t a i n ，a m b i g u o u s ，i n c o m p l e t e ， m a s s i v ea n do f t e nc a nn o tf i n dac o n v e n t i o n a ls o l v i n gp a t h ，b u ti ft h es c a l eo ft h e p r o b l e mi sn o tt o ol a r g e ，a tt h i st i m ew ec a nu s et h ee x h a u s t i v es e a r c hs t r a t e g y , s u c h a sb r e a d t h - f i r s ts e a r c ha n dd e p t h f i r s ts e a r c h ，b e c a u s et h e i rr e l a t i v ec a l c u l a t i o nt i m e c o n s u m p t i o ni se a s yt oc o n t r o l ，s oi ti sw i d e l yu s e di ns m a l l s c a l ee x p e r ts y s t e m s i nt h ea c t u a la is y s t e m a t i ca p p l i c a t i o n ，t h es o l u t i o ns c a l eo fp r o b l e mf i n d i n g v e r yb i ga n da v a i l a b l es c h e m ei sa l s om o r t t h e r e f o r e ，i tc a nn o tt oo b t a i no u ra i mi f w es t i l lu s eas i m p l ee x h a u s t i v es e a r c hs t r a t e g y , a tt h i st i m e ，h e u r i s t i cs e a r c hb yu s i n g e m p i r i c a lk n o w l e d g et og u i d et h ed i r e c t i o no ft h en e x ts e a r c hm a yd oo u rf a v o r t h i s w a yi sn o to n l yr e d u c i n gt h ep o s s i b i l i t yo fb l i n d n e s ss e a c h i n g ，b u ta l s oi m p r o v i n gt h e e f f i c i e n c y a l t h o u g hh e u r i s t i cs e a r c hi sa d v a n c e d ，i ts t i l lh a sn o to v e r c o m et h e e x p l o s i o np r o b l e mi nt h ec o m p u t i n gi n d e x g r a n u l a rc o m p u t i n gi st h e o r yw i t ht h et a r g e ta ts o l v i n gt h ec o m p l e x p r o b l e m so f a r t i f i c i a li n t e l l i g e n c e ，i tb e l o n g st oab r a n c ho fs o f tc o m p u t i n gs c i e n c e ，i t san e w c o n c e p ta n dp a r a d i g m ，c o v e r i n ga l lo ft h et h e o r ya b o u tm e t h o d s ，t e c h n i q u e sa n dt o o l s o fr e s e a r c h ，i t si d e o l o g i c a le s s e n c ei s s i m p l ed e m a n d ，t om e e tt h ea p p r o x i m a t e a c c u r a c yo fe x a c ts o l u t i o n sw i t hl o w - c o s ta l t e r n a t i v e ，u s i n gi m p r e c i s e ，i n c o m p l e t e ， u n c e r t a i n ，a n dv a s ta m o u n t so fi n f o r m a t i o nt oa c h i e v et h ei n t e l l i g e n ts y s t e mc o n t r o l e a s i l y t h i sp a p e ra t t e m p t sc o m b i n et h et h e o r yo f q u o t i e n ts p a c ew i t hi n t e l l i g e n ts e a r c h e n g i n e ，r a i s e dt h eg r a n u l a rp a r t i c l ec l u s t e r i n ga n dt h eg r a n u l a rs t a t i s t i c a lh e u r i s t i c s e a r c ha l g o r i t h m ，m a k ed i s c u s s i o no ft h e o r ya n dr e s e a r c hf o c u s i n go nt h eg r a n u l a r i t y o ft h ed a t a t h e s et w oa l g o r i t h m sa r ea l lm a k ef u l lu s eo fh i e r a r c h i c a lt od i v i d e p a n i c l es i z e b a s e do nt h eh i e r a r c h i c a l ，i tr e d u c i n ga m o u n to fu n n e c e s s a r yo p e r a t i o n s a n dt h ec o m p u t a t i o n a lc o m p l e x i t y a tt h ee n do ft h i sp a p e r , t h e s et w oa l g o r i t h m sw a s v e r i f i e db yae x p e r i m e n t ，t h e ya p p l i e dt oac a t e g o r yo fi t ss c a t t e r e dp a p e rl i b r a r yo n t h er e c o n s t r u c t i o no ft h ed a t ar e p o s i t o r ya n dr e t r i e v a l ，b a s e d0 1 1t h i st h e o r y ，w ec a n o b t a i n e dab e t t e rs e a r c ha l g o r i t h mt h a nt h ec l a s s i c a lr e s u l t s k e y w o r d s ：q u o t i e n ts p a c e ；g r a n u l a rc o m p u t i n g ；i n t e l l i g e n ts e a r c he n g i n e ； g r a n u l a rp a r t i c l ec l u s t e r i n g ；g r a n u l a rs t a t i s t i c a lh e u r i s t i cs e a r c h 1 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说 明并表示了谢意。 签名：这蛆墼：e t 期：到竺： 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：雌导师( 签名) ：醢日期：丝f 里：量：石 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 网络应用技术的快速发展，使得互连网已经成为如今各类信息的主要来源， 而搜索引擎以高效率的搜索策略在互联网上发现信息，收集信息，进而显示信 息，然后对这些信息进行理解、提取、分类和处理，为用户提供快捷的检索服 务和信息导航作用。因此，对于互联网用户使用网络获取信息的过程，搜索引 擎已成为不可或缺的工具。调查表明，在当前所有的互联网应用中，网络信息 检索已经成为人们仅次于电子邮件服务的第二大应用。 粒计算( g r a n u l a rc o m p u t i n g ) 是一种信息处理的新范式，并已成为与模糊 集、粗糙集理论，神经网络等软计算理论类似的智能求解策略【引，它涵盖了所有 关于粒度的理论推导和技术探索，就粒计算现阶段的发展状况而言，其已成为 对于模糊的、残缺的、不精确的及海量信息处理的重要理论方法与工具。 本文主要内容是将粒计算这种智能化的问题处理方法与常规搜索引擎的设 计理念相结合，利用并改进得到高效的智能算法完成数据信息的聚类合并和分 类搜索，尽量规避传统搜索算法的缺陷，实现提高搜索效率的目的。 1 2 课题背景 2 1 世纪以来，以人工智能【1 ，2 l 为主导的信息技术日益显示出强大的生命力。 仅仅在过去的1 0 年中，人工智能技术无论是理论方面还是应用方面的发展都取 得了长足的进步，其应用大大缩短了很多高难度科研项目的研究周期，以至本 来需要数十年的研究而在今天看来可以在智能系统的中迅速得以解决。许多庞 大的数学定理证明能够快速就得到证明；各种物理、化学、生物及历史、社会 和自然现象很快会得到合理的解释；各种复杂应用软件的开发工作可逐步系统 化等等，这都是人工智能快速发展的结果。 智能搜索是人工智能中的一个基本问题，尼尔逊曾把智能搜索功能列为人 工智能领域亟待研究中的四个核心之一，因为搜索在今后的人工智能领域中有 武汉理工大学硕士学位论文 着更加广泛的应用1 3 5 1 。智能搜索引擎借助模拟人的思维方式，针对分析用户以 自然语言甚至方言表达的检索请求，自动形成检索策略并进行快速、高效的信 息检索；与此同时，其还可以对用户的查询计划、意图、兴趣方向进行合理推 断，自动进行信息搜索、索引、过滤，进而向用户反馈有用的信息【l 。要实现 此类功能又必须依赖智能知识库的建立，以及智能知识库具有不断自学习、自 适应的能力【8 1 。因此，智能化的搜索引擎追求的是让用户享受尽可能方便、快捷、 准确的个性化搜索服务，这即是今后搜索引擎的发展主流趋势。 在实际应用中，智能搜索引擎的开发还存在诸多技术难关，比如，当我们 需要在一个非常专业化的知识领域搜索相关知识、文献和数据时，传统的搜索 引擎无法很好的完成这一点，因为传统的搜索引擎提供的是大量庞杂，凌乱并 且有缺失的信息。用户必须也只能依靠自己的判断能力去对这些信息进行再次 筛选，这样既浪费了大量的人力，同时搜索的准确性也得不到有效保障。设想 如果能够借助数学中集合范围切分的思维范式去构建一种智能化知识数据库， 那么这可以极大的发挥系统人性化服务的特点，快速方便的帮助用户去获取他 们想要的信息，所以实现这一系统设想的实际意义则是不言而喻的。 粒计算f 2 7 1 是一门正在飞速发展的理论，它的关键是对人类智能的模拟，所以 它才能成为人工智能领域的研究热点之一，众多学者就粒计算的基本理论和应 用方法做了大量的细致研究，已经从问题求解的实践中抽象出解决一般问题的 基本规律【2 7 l 。但从宏观面上来看，人们对粒计算的描述仍然只是停留在对它的 直觉认识上的，所以这还需要对粒计算进行长期的探索。 本课题一方面尝试利用粒度原理解释搜索引擎的分类、搜索、分析策略， 又针对性地实现问题求解的若干方法。另一方面，也借此课题的研究机会，提 升作者的科研能力，完善现有的知识结构，实现知识网络化，并期望在实际工 作中学以致用，为以后的实际工作奠定基础。 1 3 搜索引擎技术的发展现状 搜索引擎( s e a r c he n g i n e ) 是指根据某种特定的策略、运用计算机程序搜集互 联网上的信息，在对得到信息进行组织和处理后，将信息反馈给用户，为用户 提供信息检索服务的系统【9 1 。 目前搜索引擎的研究和应用已经取得了重大的进展，不过从当前实际应用 2 武汉理工大学硕士学位论文 来看，以下几个问题仍然有待深入研究： ( 1 ) 随着网络信息资源日新月异，其数量每天都是以几何级倍数增长，目 前世界上最大的搜索引擎公司g o o g l e 公司的总页面大概在8 0 亿左右，但是这仅 占整个网络上资源总量的3 0 - 4 5 ，而且由于互联网上网络资源的增长速度远 远超过g o o g l e 公司页面爬虫引擎所搜集页面增长的速度，这个比例有快速扩大 的趋势，标志着互联网上有超过7 0 的资源可能是无法通过搜索引擎检索到的 1 1 0 1 。这个问题从第一代搜索引擎开始就一直存在，而且会持续以后的相当长的 一段时间，但是这并不意味着科技对此无能为力，已经提出来很多年的粒计算 理论将能够给这个问题解决带来曙光。 ( 2 ) 目前人们对搜索引擎依赖程度越来越高，但同时也带来一系列问题。 搜索引擎的基本工作原理是通过对用户输入的关键字在自己的索引数据库中进 行模糊查询，然后将结果返回给用户，但由于互联网上信息数据量爆炸式的激 增，反馈的信息已无法满足用户的实际需求【9 1 。另外，对不同类型的用户、不同 需求的用户来说相同关键字检索结果是完全一样的，这也不符合当今人们追求 个性化的特点1 w 。 以上两个问题，就是智能搜索引擎目前亟待解决的关键问题，所以说智能 搜索引擎作为新一代搜索引擎，其智能关键体现在检索的相关性、快速性，以 及对用户不同兴趣的正确识别、理解、推理以及信息过滤等多种功能f 9 j 。 1 4 国内外关于粒计算技术的发展现状 如前文所述，粒计算是模拟人类智能的一种操作，体现了人类智能中善于 针对问题的不同层次进行求解的特性。美国数学家z a d e h 于1 9 7 9 年又首次提出 了提出模糊集合论，推动了模糊逻辑推理的发展p ”，直至9 0 年代末，z a d e h 总 结以前模糊粒度理论，进一步提出了“词计算理论”，词计算理论的主要研究的目 的是为了对自然化的语言进行模糊识别。 1 9 8 2 年，粗糙集理论【z 7 j 诞生，由于其较强的定性分析能力和对不精确的知 识的表达能力，并善于利用不确定、不完整的经验知识进行推理等性能。让粗 糙集理论在数据挖掘、机器学习、决策分析、智能控制领域获得了广泛应用。 加拿大r e g i n a 大学的著名教授y a o y y 在前人的研究基础上，提出了邻域系统 基础上的粒计算模型，并在知识发现领域获得了突破【2 7 1 。 3 武汉理工大学硕士学位论文 国内，清华大学的张拔院士提出了基于商集的粒计算模型【2 7 1 ，该模型使用 不同集合表示不同粒度等级的概念，不同簇就构成空间的不同知识基划分，也 就是我们后面要深入讨论的商空间，而商空间粒度的理论是基于集合簇的构成 的，也就相当于研究在给定集合上的各种子集之间的关系变换法则。因此，这 种思想很好的应用在了动态规划等方面。 目前，粒计算己经成功应用于智能中的多个领域，在国际上也已形成了专 门的研究团队。1 9 9 8 年1 0 月在美国召开的第六届粗糙集及粒度计算研讨会，成 为第一个以粒度为研究主题的国际会议【3 。以此同时，我国的清华大学于2 0 0 4 年9 月召开了第一届粒计算国际会议，就粒计算的定义方式、亟待解决的问题 和拓展方向进行了深入交流【3 1 j 。 1 5 粒计算研究的意义 众所周知，人类智能的一个最大的特点就是人类能从极不相同的粒度 ( g r a n u l a r ) 世界观察、分析和求解问题，而且能够自如的在不同粒度世界之间切 换，这显示出人类对待不同粒度世界问题强有力的处理能力。因此，对人类智 能的模拟是实现系统智能控制的重要路径。当今粒计算主要的研究问题集中在 两个方面：一是粒度的结构之间各种的关系，如依赖性、封闭性等。二是人们 需要为粒计算的实际应用设计合适的工具，如近似计算、逻辑推理等【4 引。 粒计算摒弃了数学上的精确求解的思维定势，即：需要的是准确地理解和描 述一个问题，而不是专注于信息的细枝末节上。粒计算的实践方法对目标与约 束函数的连续性与凸性没有要求，有的甚至没有解析表达式，但是对计算中各 类数据的异样性有较强的适应能力。站在问题求解的角度看，面对现实世界的 许多复杂问题，我们需要将问题分解为规模小、易处理的子问题；站在应用领 域的角度看，搜索已经广泛的应用在图像、语音与字符识别处理等方面，因为 这些信息处理质量的好坏与效率的高低直接依赖于粒度划分的效果。总之，信 息科学的发展需求是研究粒计算的最根本动机。 1 6 粒计算的学科属性 粒计算如今已发展成为一个独立的学科，对粒计算的研究主要可以从模糊 4 武汉理工大学硕士学位论文 集、词计算、商空间这三个方向进行，它们是完全结构化的思维、结构化求解 和信息处理方式，这三个方向可以简化表述为粒计算的三角形模型。 模糊集理论模型 词计算模型商空间模型 图1 - 1 粒计算三大理论逻辑图 如图1 - 1 所示，根据三个观点的内在联系，也可以用层次结构或三维结构来 描述对粒计算的研究，针对粒计算的这些研究领域，现有的研究对粒计算的哲 学理论思想及方法论的探讨并不深入，而主要局限在对其信息处理技术的挖掘 上，尤其是以计算机为基础的信息处理的数学模型的探索。著名数学家b l o t o n 曾指出：对于一项研究，如果不能首先正确理解和定义相关概念和范围，技术 的严密性就不能避免片面的、平凡的，甚至错误的结果，虽然他的观点就是概 念形成这一研究而言的，但也同样适用于粒计算研究。所以粒计算是集哲学思 想、计算模型、方法论为一体的研究，并不局限于某一方面的研究，一方面， 应该深入探索粒计算的数学理论模型；另一方面，应该对这个学科有全局的认 识，不能偏废任何一个方向。一个完美的数学模型是非常重要的，但是并不一 定能保证对它的理解和应用都绝对正确的。因此，构建数学模型并不是最终目 的，而是解决问题的一种手段而已，仅有数学模型是远远不够的，还需要清楚 地认识这个数学模型在整个科学研究中所扮演的重要角色。关于数学在研究中 的两重性，这里可以引用王玉德阐述：数学不是万能的，没有数学史万万不能 的。 1 7 论文研究内容 1 7 1 研究目标 首先利用粒计算中商空间粒度分层的分析方法，探讨与改进传统智能搜索 引擎知识库的聚类算法；以此为基础，重点提出统计推断理论下的粒启发式搜 5 武汉理工大学硕士学位论文 索方式；最后利用以上两种技术进行相关的技术试验。 1 7 2 研究内容 ( 1 ) 商空间粒度分析方法：基于商空间的粒度计算理论是粒计算最主要 的三大理论之一，它包括商集概念的引入，商空间模型的建立，商空间粒度的 获取方式，商空间分层方式以及模糊商空间的推断理论。 ( 2 ) 粒启发式搜索算法：粒启发式搜索方法是利用对问题的先验知识机 型初步分析，从而获取启发式信息来协助进行搜索的一种智能技术。对它的研 究启发式搜索包括b f ( 最好优先) 算法，粒度的划分方式与判定方式研究。 ( 3 ) 粒度聚类算法：分析传统聚类分析有很多方法，归纳这些方法各自 的特点，本文需要分析传统聚类的优劣并进行改进得到新的聚类算法，提出的 基于粒度的聚类能够通过高效途径实现对大规模数据信息的聚类。 1 7 3 拟解决的关键问题 ( 1 ) 建立基于粒度分层方法的推理模型设计启发式搜索算法，并将其与传 统的启发式搜索方式进行分析比较。 ( 2 ) 合理的选取并改进聚类方式完成对大规模数据样本分类。 ( 3 ) 通过实验证明提出理论算法的可行性。 1 8 本章小结 本章主要回答了粒计算的几个基本问题，包括粒计算的描述，粒计算的粒 结构及其特点、使用方式、任务和贡献及粒计算与诸多相关学科的关系。同时 简单介绍了搜索引擎的发展现状，下一章我们将主要讨论智能搜索引擎中的搜 索理论与具体的技术。 6 武汉理工大学硕士学位论文 第2 章智能搜索技术在智能搜索引擎中的发展 2 1 智能化搜索引擎 智能搜索引擎是结合了人工智能技术的新一代搜索引擎。它既能够迅速准 确完成搜索，又能为用户提供个性化的角色记录、用户特点的自动识别、所要 查找内容的语义识别、各种信息传送及过滤等功能，提升用户在实时搜索过程 中的参与度。 2 1 1 智能型搜索引擎的逻辑模型 智能搜索引擎在实际运作过程中是将整个网络作为一个巨型的、完整的、 实时动态的数据库进行处理【5 1 。其主要实现5 大基本功能：搜索请求提交、信息 反馈提交、搜索调度管理、搜索接口代理转化和搜索结果处理。其中，搜索请 求提交和信息反馈提交功能组成用户接口部件，其它各功能分别由信息过滤部 件、提交信息检索部件、搜索引擎查询系统部件、知识挖掘部件5 大模块构成。 7 图2 1 智能搜索引擎系统逻辑模型 ( 1 ) 用户接1 3 部件：是搜索系统的人机交互界面，负责接收用户请求，并根据 需要将用户的实际操作与系统能够识别的标准请求进行转换。 ( 2 ) 提交信息检索部件：根据用户请求信息中的关键词、学科类别及所涉数 据的广泛程度等情况的差异，综合运用成员搜索调度信息向数据挖掘管理部件请 求本次搜索引擎代理管理策略。 ( 3 ) 搜索引擎查询系统部件：是若干搜索引擎知识库代理的集合体。它把用 户输入的搜索请求转化为对应搜索引擎知识库的本地请求信息，为下一步的搜 索提供支持。 ( 4 ) 信息过滤部件：系统接受到用户的请求之后，根据搜索的反馈内容难易 程度自动过滤一些杂质性的信息，同时评价该策略的好坏并把这些信息反馈给 搜索引擎工作日志。 ( 5 ) 知识挖掘部件：该模块是体现系统智能化的核心模块，它负责实现搜索 引擎知识库的预处理功能，综合运用搜索引擎调用策略，统计整理本次搜索中 发送的记录，根据策略数据库指导的具体算法调整接下来的搜索策略。 8 武汉理工大学硕士学位论文 2 1 2 智能化搜索引擎的优点及存在问题 智能搜索引擎在实际应用中越来越多的显示出其特有的优点，但随着 i n t e m e t 信息量的猛增，智能化的搜索技术也不可避免存在一些局限性。 ( 1 ) 优点： 能够搜集和识别用户相关信息，提取并分析用户重要信息，创建适合用 户个性化需求的访问方式。 用户能够与系统进行充分交互，系统也能根据用户的交互数据调整与之 对应服务方式。 依据用户兴趣对搜索结果进行优先级排序，使得用户可以从搜索引擎得 到真正需要的信息，从而实现个性化搜索要求。 ( 2 ) 缺陷： 信息丢失：普通用户输入的查询信息一般都是口语化的信息，由于口语 语法的随意性，使得系统无法直接理解其内容，所以查询结果往往不能符合用 户的本意，有时甚至与期待的结果相距甚远。 返回信息庞杂：当客户输入某一关键词后，系统返回的检索信息数量异 常非常庞大，用户无法在较短时间内找出合适的反馈信息。 无关的信息混杂：现有的智能搜索引擎仍然是以是否包含了关键字作为 返回信息的判断准则，这可能包含许多无价值的数据，无形中加大了用户的工 作量。 ( 3 ) 原因分析： 造成上述信息检索低效的实质原因在于智能化的搜索引擎在关键词匹配方 面的方式仍然和传统的搜索引擎类似，存在缺乏有效知识处理能力和高度理解 能力的缺陷i 更无法准确处理大量个性化的用户需求。因此，智能化搜索引擎 需要追求更加高效的知识型，更加完善的智能型搜索策略。 2 2 人工智能中的搜索技术 搜索技术中的问题求解是人工智能领域的一个重要课题，大量的科学家多 年来付出了巨大的精力，试图给出人工智能问题中完整的问题求解模式，下面 我们来具体看一看： 9 武汉理工大学硕士学位论文 2 2 1 状态空间 在智能系统中，问题求解( p r o b l e m s o l v i n g ) 处理问题的方式包括推断、归约、 决策、规划、常识推理、定理证明等相关过程，但经过科学家对大量问题求解 方法的研究后，我们发现大多数问题的求解本质还是基于试探法的，换句话说， 该方法的核心仍然是在某个可能存在最终解的范围内进行穷举查找【1 3 l 。其中最 为常见的是状态空间法，它主要是根据解空间中的状态信息和符号来推理求解 的，其中“状态”是用来描述问题在不同状况下的结果集；而“符号”则表示对该状 态下的操作，所以，当达到目标状态后，从初始态到最终态这个过程中的所有“符 号”序列即为该问题的求解路径。 基于以上结论，本文归纳出状态空间的基本搜索思想：第一步先分析问题 的初始状态( 初始结点) ，第二步再选择合适的“符号”对论域进行变换，得到若 干中间状态，然后迅速核查目标状态是否在这些已知中间状态中。若存在，则 搜索成功；否则根据适当的推理方式选择最有可能包含解的一个中间态作为初 态，重复上述推到过程，直至抵达目标态或无可供继续操作的状态“符号”时为 l e 。 初始 图2 2 状态空间搜索示意图 在图2 2 中，矩形内表示的是问题所涉及到的所有可能状态集，矩形中的结 点分别表示初状态集、中间临时状态集和目标结果状态集，由一系列的推理箭 头引导出的一条求解路径即代表了最后的搜索方案。在此搜索中涉及到的所有 1 0 武汉理工大学硕士学位论文 状态集合构成了搜索空间，我们期望在保证找到最优的解答路径的同时，应尽 可能的缩小查找范围，降低搜索代价。 2 2 2 智能搜索原理 人工智能问题通常是专门针对那些完全非结构化的状态空间，并且存在复 杂的不确定性，因此解决这类问题必需采取搜索求解空间的方法而非直接获取 问题求解的路径。当问题规模不太大，并且缺少相关背景知识，理论上是采用 穷举搜索法，像广度、深度优先搜索法这一类，这样做耗费的计算时间一般也 是能够接受【1 引。但是对于一个实际中的人工智能系统，其问题的求解空间一般 都非常大，空间中中间状态数量众多，对于每个中间状态，验证其是否包含候 选解方案也有多种，此时再依靠穷举的搜索方案则很难奏效。为了避免穷举搜 索的盲目性，我们定义一种能反映求解路径优劣的数值函数“) ，作为比较选择 的参考值，称为评价函数( e v a l u a t i o nf u n c t i o n ) l l 州。 使用评价函数来指导搜索路径的的理论最初是由p e h a r t ，n j n i l s o n 和 b r a p h a l 等人提出的，根据以往经验式知识、直观的启发式知识确定评价函数， 因此这类搜索方法又称为启发式搜索法( h e u r 括t i cs e a r c h ) 1 1 j 。 2 3 启发式搜索理论 如果运用穷举的搜索策略求解，面对复杂问题时需要扩展的结点数目可能 非常大，同时这些结点的扩展方向也不确定，而且搜索过程中无法有效利用已 知问题的任何信息。因此处理这类问题的时间复杂度和空间复杂度都是非常大， 同时这也是产生组合爆炸的直接原因之一。 启发式搜索最为关键的地方在于搜索过程中参考了根据已知问题推导出的 的启发信息，用这些信息引导搜索向最有可能包括解或最优解的方向前进，具 有很强针对性，同时我们还发现这类搜索上一般只需要对部分状态空间进行查 找，回避了盲目搜索中对全部结点的查找，所以搜索效率也比较高。 2 3 1 启发式信息与评价函数的构造 在搜索过程中，启发式信息的主要作用是进行指导和控制问题的求解方向。 武汉理工大学硕士学位论文 所以，在启发式搜索过程中，关键的步骤是如何确定下一个要考察的结点，目 前在该领域有许多成熟的搜索策略，但基本上都是综合考虑了问题各方面的特 征信息，推出具备概率较大候选解的结点。 用于评价结点重要性的函数称为评价函数i 勰1 ，其一般形式为： ( 丹) 一g ( 以) + 办( 刀) 其中厂( 刀) 是结点1 1 的估价函数，g ( n ) 表示状态空间中从初始结点到n 节点 的代价，办( 功是从1 1 到目标结点最佳路径的估计代价，它集中体现了搜索的启 发性，因此又被称为启发性函数。 设计高效的评价函数的关键，是充分利用启发式信息，找出最优解( 最小路 径代价l ，并尽可能减少搜索代价。但是，由于人工智能等问题的非结构化、不 确定性的特点，使得设计一个优秀的启发式函数异常困难。 2 3 2 启发式搜索算法的使用原则 在启发式搜索技术中，启发式信息通常在下列3 种情况下使用： ( 1 ) 能够运用可行的方法尽可能选择少的待扩展结点，避免像广度优先与深 度优先搜索算法中那样针对所有结点进行扩展分析。 ( 2 ) 用于决定是从搜索树中抛弃还是保留拆分该结点。 ( 3 ) 在结点的扩展过程中，能够准确产生子结点的正确的方法，同时能够避 免产生海量的候选结点。 与此同时，对于公式f ( n ) ；9 0 ) + 办( 行) ，在复杂问题的求解中，要得出g ( n ) 和而( 行) 是十分困难的。实际求解过程中，g ( 力) 的值表示的是已经耗费的代价， 通常可以从已知的搜索树中直接推导出来，不必专门定义计算函数；而对启发 函数h ( n ) 的设计，要最终确定评价函数就必须依靠启发式信息的正确使用了。 可以证明，如果能够对启发函数h ( n ) ，进行适当改进，则能极大提高搜索的效 率。 2 3 3 启发式估价函数的改进策略 在实际操作过程中，设计一个优秀的启发式函数的代价可能大到超过了搜索 过程所需代价，因此，对于有些问题应该用性能稍低的评价函数，来减少设计 评价函数的代价。在对于具体的启发函数h ( n ) 的构造，本文尝试使用一个系数 1 2 武汉理工大学硕士学位论文 因子( o ) ，重新构造评价函数为 厂( 刀) 一g ( n ) + t o h ( n ) 我们利用控制因子值的可调整性，使搜索是向深度或广度方向进行【2 1 i 。当 o j - 0 时，则j l z ( 以) _ o ，从而对整个评价函数影响减弱，使搜索向广度方向进 行：当时，办( 力) 一0 0 ，从而使函数t o h ( n ) 对评价函数影响变的很强，使 搜索向深度方向进行，一般情况下，的值不可能去无穷大，应为其设置一个 阀值。 对于一般的搜索，我们可以制定以下策略：在搜索的初始阶段，应让t o 值偏 大，使搜索为尽快接近目标而向深度方向进行；当搜索进行到一定阶段后，应 及时调小t o 值，控制搜索更偏向于广度方向，也就是避免错过了目标结点，直 至成功的完成搜索。比如说在登山旅行中，从山脚到山腰的过程中，应当以高 速行进( 调大t o 的值) ，当接近顶峰时，为了欣赏沿途的风景，应当把速度放慢( 调 小的值) ，不要因为速度过快，而错过了美丽的风景( 错过了目标结点) 。 2 4 常见的启发式搜索算法 常见的启发式搜索算法有很多，比如：爬山搜索法、最好优先搜索法 ( b e s t f i r s t ，b f ) 【1 1 、a 宰算法等等【1 1 ，虽然这些方法的搜索结点选取策略存在差 异，但都是基于评价函数的，像爬山法，是在搜索的中选取“最佳结点”后舍弃别 的兄弟结点，但我们也应看到，在舍弃了其他结点的同时，极有可能也把一些 最优的结点也舍弃掉了，因为此时最佳结点只是在该阶段下的最佳结点，并非 全局状态下的最佳结点。b f 算法则注意到了这一点，它在搜索时如果确定该结 点是死结点，否则不会轻易的舍弃这些结点，并且在每一步的搜索中都把当前 评价的结点和以前的结点的评价值进行比较，这样可以有效的防止“最佳结点” 的丢失。 2 4 1 最好优先算法 设有向图g ，s o 是g 中的结点，称为起始结点，s n 是g 的目标结点。现在 要在g 中寻找一条由s o 到s n 的路径，下面来看一看以点之间的距离数值作为 启发式信息的推理方法。 1 3 武汉理工大学硕士学位论文 设g ( 甩) 一七( s o ，) ， ( 刀) 一k ( n ，s ) 存在任意n e g 。其中k ( s o ，1 ) 表示由s o 到 结点n 的最短距离，k ( n ，最) 表示由1 1 到结点s n 的最短距离。 令( 厅) - g ( 以) + ( 疗) ，存在任意n eg ，设f ( n ) 、g ( n ) 、h ( n ) 分别是、p ( n ) 、 g ( 力) 和矗q ) 的评价函数值，可以得出f ( n ) tg ( 疗) + 办( 力) ，对( 刀) 的值进行量化 后能够方便求解。 b f 算法依然没有充分利用全局信息，所以难以避免指数爆炸，另外，b f 的计算效率取决于评价函数的精度，因此该算法十分关注评价精度的高低。其 实，在搜索过程中通常需要的只是确定各类结点之间的差异，无需精确的得出 结点数值，比如，在面对通向同一目的地的两条岔路时，要选取最短最优路径， 并不需要精确地估计出这两条路径的实际长度，而只需要正确的判断出两条路 径的优劣即可。 2 4 2 统计启发式算法( s a 算法) 针对b f 算法基本上未能克服计算量的指数爆炸的情况，启发式搜索的研究 学者j p e a r l 将平均计算量的概念引入到概率模型中【堋，就启发式搜索与统计推 断的相似性而言，可以将每次搜索方向的确定看成是统计推断的过程，于是在 启发式搜索中就产生了一种新的较成熟的理论工具，把这个新的搜索方法称为 统计启发式搜索( s t a t i s t i c a lh e u r i s t i cs e a r c h ) ，简称s a 算法【2 7 l 。 s a 搜索过程总体上分两步，先利用统计推断的方法判断图中哪些部分最有 可能包含有目标，而将包含目标的可能性( 概率) 很低的部分删去，然后用一 般启发式搜索方法继续展开剩下的结点，直到一定程度后，再来判断具体目标 在哪，如此交叉操作直到找到目标为止。在序贯概率统计推断操作中，对于给 定原数据量x 及其统计量y ( n ) ，需要对每次生成的新结点的统计量y ( n ) 进行一 次新的统计推断，依此在分层过程中多次推断直至假设h o 被接受或拒绝为止【2 7 l 。 由于在搜索过程中的全局判断是基于统计推断方法，也就是利用搜索空间 中不同部分之间统计量的差异，而不是利用统计量的绝对值，这样对于避免指 数爆炸是有益的。 2 5 本章小结 本章详细介绍了人工智能领域中问题求解的基本方法和分析问题的重要思 1 4 武汉理工大学硕士学位论文 想分层递阶，并且还描述了搜索引擎中的工作原理与发展概况，着重分析搜 索技术特别是启发式搜索的基本原理，并对其运用和评价函数的设计进行了研 究，最后深入探讨了启发式搜索中的s a 算法，为后文使用s a 算法并引进粒度 做好了铺垫。 1 5 武汉理工大学硕士学位论文 第3 章商空间粒度计算理论 3 1 问题求解理论中的人类智能 人工智能( a r t i f i c i a li n t e l l i g e n 0 发展至今，其最重要的成果都归功于“算符 ( s y m b o l i c i s m ) 思想的产生，它大大简化了人类的思维模式，进而推动人工智能理 论的发展i 。 人类曾深入研究人类智能的这种自生的特殊能力，并为其建立了许多标准 化的模型，并利用计算机能再现这种能力，那么人类智能究竟是什么呢? 人的 智能主要表现为对事物的分类与抽象能力【3 ，比如我们常说的伯乐相马的故事， 就伯乐能从各种马匹的外观、习性等特征中，正确地识别马匹的能力水平，这 就是他的分类能力强。 3 2 粒度问题的描述方法 目前，人工智能问题的一般描述方法包括规约问题法( r e d u c t i o n p r o b l e m r e p r e s e n t a t i o n ) 及空间状态法( s p a c e s t a t er e p r e s e n t a t i o n ) ，但粒度世界的描述问 题并未因为这些理论而解决e 刀。“人类智能所拥有的最突出特点，就是人类能在 不同粒度的世界上对同一问题进行求解，而且能够在不同粒度世界之间任意切 换，这种处理不同粒度世界的能力，说明了人类智能强有力的表现1 2 7 1 。”正是由 于这个原因，一种基于商结构的理论体系商空间理论应运而生，并迅速发展成 为一套表示信息集成、工作筹划和逻辑运算推理等方面的理论和方法，并在相 关实际领域得到应用。 3 3 粒计算的研究模型 粒计算是一种依靠信息粒度，在不精确的和部分已知的信息环境中做出合 理决策的方法。如第一章所说，至今已有三个主要的研究方向，这三条重要理 论是互相补充的，从思考问题的出发点和解决问题的要求来看，它们对于模糊 1 6 武汉理工大学硕士学位论文 信息的处理有各自独立的方法，但由一个最关键的相同点就是都充分考虑了人 类智能，即从不同粒度分层思考问题。 3 4 商空间粒度原理 商空间粒计算中的“等价关系”变换，主要通过对同一问题从不同的粒度角度 进行分析判断，以及在给定知识基上对这些粒度集合之间的关系进行转换，综 合获取原问题的解。它的实质就是