(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf_第1页
(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf_第2页
(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf_第3页
(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf_第4页
(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf_第5页
已阅读5页,还剩129页未读, 继续免费阅读

(交通信息工程及控制专业论文)搜索引擎智能行为的研究及实现.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

西南交通大学博士研究生学位论文第i 页 摘要 当前搜索引擎面临着i n t e r n e t 网络信息更新快,用户查询结果要求越来越精 确的严重挑战,智能搜索引擎的研究已经成为w e b 数据挖掘领域研究的重要内 容。为了解决搜索引擎中用户查询结果诸多问题,如信息查询的不准确等,发展 了目录搜索引擎、全文搜索引擎和元搜索引擎,在这些i n t e r n e t 信息搜索理论、 技术、方法上,人们开始引入人工智能。本文综合现有搜索引擎的成果,将人对 图书资料检索的智能行为应用到搜索引擎中,进行了如下内容的研究: 1 分析了人们在图书馆查阅资料的智能行为包括:记忆能力、理解能力、感 知能力。推理能力,实践能力。分析了图书资料查阅与i n t e r n e t 中信息检索的相似 性。系统地分析和总结了现在全文搜索引擎实现方式上的五种智能能力的表现, 提出了三网智能行为模型( o u t e r n e t ( 外网) _ i n t e r n e t ( 万维网) _ i n n e r n e t ( 内网) ) ,阐述了实现该模型的关键问题,通过一个具体的应用实例,说明了三 网智能行为模型的实现是可行的。 2 从网页和用户查询关键词的“概念与意义”匹配的角度,借助了形式概念 分析这一工具对网页的形式概念表示、关联规则的获取、网页匹配中的不确定性 推理三个方面进行了研究: ( 1 ) 在定义用户查询词的下接近与上接近的基本概念基础上,研究了下接 近网页集形成的多值形式背景的形式概念表示方法,该方法以单个属性等价类为 出发点,采用概念格形式概念对象之间的相等、包含、相交关系,建立了形成概 念格的算法。与现有概念格建立算法相比,其时间复杂度有了较大的降低。 ( 2 ) 结合用户查询词与网页匹配的特点,把现有概念格上的关联规则扩充 为“与规则”和“或规则”,研究了从概念格中获取这两种关联规则的方法、算法。 同现有概念格上无冗余规则获取算法相比,其时间复杂度有了显著的下降。 ( 3 ) 从形式概念分析的角度出发,研究了利用关联规则,对上接近网页集 中的网页与用户查询词进行不确定性匹配的模型、方法、算法,其算法复杂度是 比较低的。 3 使用线性归结方法研究了英文网页的词法分析,认为归结过程本身就是 一个线性归结,得出非正规文法都可以转换为正规文法的结论,并给出了转换算 法;在正规文法的基础上研究了一个基于线性归结的词法分析方法的原理,证明 了该方法的完备性,并予以算法和程序的实现。 关键词:搜索引擎,智能行为,概念格,规则提取,不确定性推理,网页匹配 第i i 页西南交通大学博士研究生学位论文 a b s t r a c t n o w a d a y s ,t h ei n f o r m a t i o no ni n t e r n e ti su p d a t e dw i t he a c hp a s s i n gs e c o n d ;a n d t h es e a r c h i n gr e s u l ti se x p e c t e dt om e e tm o r ea n dm o r ep r e c i s er e q u i r e m e n t so fu s e r s a l lt h e s ei n v i t ec h a l l e n g e st ot h ec a p a c i t yo fs e a r c he n g i n e t h e r e f o r e ,t h es t u d yo ni n t e l l i g e n ts e a r c he n g i n ed e s e r v e sm u c ha t t e n t i o ni nt h ec u r r e n tw e bd a t am i n i n gr e s e a r c h f i e l d i no r d e rt os o l v em a n yp r o b l e m se x i s t i n gi nt h es e a r c he n g i n e s u c ha si n a c c u - r a t e n e s se t c ,v a r i o u ss e a r c he n g i n e sh a v eb e e nd e v e l o p e d ,i n c l u d i n gt h ed i r e c t o r ys e a r c h e n g i n e ,t h ef u l l c o n t e x ts e a r c he n g i n ea n dt h em a t es e a r c he n g i n e a n di nt h i sw a y , a r t i f i c i a li n t e l l i g e n c et h e o r i e s ,t e c h n o l o g i e sa n dm e t h o d sa r ea p p l i e dt ot h i sf i e l d t h i s p a p e ra p p l i e dt h ei n t e l l i g e n ta c t i o na d o p t e di nb o o k ss e a r c h e st ot h ec u r r e n tr e s e a r c ho f s e a r c he n g i n e ,a n da c h i e v e dt h ef o l l o w i n gr e s u l t s : 1 i n t e l l i g e n ta c t i o no f l i b r a r y i n f o r m a t i o ns e a r c h e s i s i n c l u d e d i n f i v ea s p e c t s :m e m o r y ,c o m p r e h e n s i o n ,p e r c e p t i o n ,l o g i cr e a s o n i n g ,a n dp r a c t i c e sb ya n a l y s i n gs i m i l a r i t i e s b e t w e e nl i b r a r yi n f o r a m t i o ns e a r c h e sa n di n t e r n e ti n f o r m a t i o ns e a r c h e s ,f i v ek i n d so fi n - t e l l i g e n ta c t i o n so ft h ef u l l - c o n t e x ts e a r c he n g i n ea r ef o u n d ,a n dt h et h r e e - n e ti n t e l l i g e n t a c t i o nm o d e l ( o u t e r n e t - - + i n t e r n e t _ i n n e r n e t lw a sp r o p o s e d a ne x a m p l ep o i n t so u t t h a tt h em o d e li su s e f u l 2 f o rt h es a k eo fm a t c h i n gt h ec o n c e p ta n dm e a n i n gb e t w e e nt h eq u e r ya n dw e b p a g e s ,s o m er e s e a r c h e sa b o u tt h ew e bp a g eo fk n o w l e d g ee x p r e s s i o n ,a n dk n o w l e d g e r e t r i e v a la n dk n o w l e d g ei n f e r e n c ew e r ec o n d u c t e dw i t hf c a ( f o r m a lc o n c e p ta n a l y s i s ) t h e yi n c l u d et h r e ep a r t s :( 1 ) i tw a sb a s e do nt h ed e f i n i t i o no ft h el o wa d j a c e n c e s e ta n du p p e ra d j a c e n c es e ti nw h i c hw o r d so fe v e r yw e bp a g ec o n t a i na l lo r a tl e a s tp a r t so ft h ek e yw o r d si nu s e r sq u e r y b e s i d e s ,s t a r t i n gf r o mt h ee q u i v a l e n c e c l a s sb yt h e = ,na n dco fa t t r i b u t e sa n do b j e c t so ft h ef o r m a lc o n c e p t ,t h em e t h o d a n da l g o r i t h mc o n s t r u c t i n gt h ec o n c e p tl a t t i c eo fl o wa d j a c e n c ew e r es t u d i e d o nm a n y - c o n t i n u o u s v a l u e df o r m a lc o n t e x t ( 2 ) t h em e t h o da n da l g o r i t h mr e t r i e v i n g o r r u l e sa n da n d - r u l e sb e t w e e nu s e rq u e r ya n dn o n - u s e rq u e r yw e r ea n a l y z e df r o mt h e c o n c e p tl a t t i c eo ft h el o wa d j a c e n c e ( 3 ) a c c o r d i n ga st h eb a s i ct h e o r i e so f f o r m a l c o n c e p tl a t t i c e ,t h em a t c hm o d e l ,m e t h o da n da l g o r i t h mb e t w e e nt h eu s e rq u e r ya n d w e bp a g e si nu p p e ra d j a c e n c es e tb a s e do nu n c e r t a i n t yr e a s o n i n gw e r ep r e s e n t e d b yo r r u l e sa n da n d r u l e s t h et i m ec o m p l e x i t yo ft h e s ea l g o r i t h m si sa n a l y z e d 3 i nt h ep e r s p e c t i v eo fm o r p h o l o g y , s y n t a x ,s e m a n t i c so fn a t u r a ll a n g u a g e ,a r e s e a r c hw o r kt om a t c ht h ee n g l i s hw e bp a g ea n dt h eu s e rq u e r yw a sd i s c u s s e d t h i s p a p e rp u t sf o r w a r dt h a tt h ed e r i v a t i o np r o c e s sf o ri d e n t i f y i n gw o r d sb yr e g u l a rg r a m m a r 西南交通大学博士研究生学位论文第i i i 页 i sal i n e a rr e s o l u t i o ns u b s t a n t i v e l y f u r t h e r m o r e ,i nc e r t a i nc o n d i t i o n ,i r r e g u l a rg r a m m a r c a nb ec o n v e r t e dt or e g u l a ro n ea n dt h ea l g o r i t h mi sg i v e n i nt h el i g h to fr e g u l a r g r a m m a r w es t u d i e dam e t h o do fm o r p h o l o g ya n a l y s i s ,p r o v e di t sc o m p l e t e n e s s ,a n d o f f e r e dt h ea l g o r i t h mt or e a l i z et h ep r o g r a m k e yw o r d s :s e a r c he n g i n e ,i n t e l l i g e n ta c t i o n ,c o n c e p tl a t t i c e ,r u l er e t r i e v e d , u n c e r t a i n t yr e a s o n i n g ,w e bp a g em a t c h 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本 人授权西南交通大学可以将本学位的全部或部分内容编人有关数据库进行检索, 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口,在年解密后适用本授权书; 2 不保密团,适用本授权书。 学位论文作者签名:高仑矽辱 日期:a d “f 年r 房月【( ;h 指导教师签名:l ? 留 b 期:踟5 年,2 ai 7b 第页西南交通大学博士研究生学位论文 西南交通大学 学位论文创新性声明 本人郑重声明:所呈交的学位论文,是本人在导师指导下独立进行研究工作 所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下: 1 本文第三章第一节提出用户查询上接近与下接近的基本概念、第二节提出 的概念格对网页形式概念的表示方法和算法。 2 本文第四章第一节结合网页匹配具体应用背景提出的无冗余规贝u 获取方 法、第二节提出的规则获取算法。 3 本文第五章第二节提出的网页与用户查询匹配中的晒、m 2 、m 3 三个 匹配模型,第二节提出的“与”、“或”匹配方法和匹配算法。 4 以及本文第六章第一、二、三、四节提出的基于归结原理的词法分析方法 的形成以及算法。 学位论文作者签名: 允今谚 西南交通大学博士研究生学位论文第1 页 第1 章绪论 随着i n t e r n e t 的飞速发展,人们越来越依靠计算机网络来查找他们所需要的 信息,网络已成为人类生活中的主要信息来源之一。但是,网上的信息源多不胜 数,且每天都在以成倍的速度增加。如何有效地去发现我们所需要的信息,就成 了一个很关键的问题。搜索引擎( s e a r c he n g i n e ) 是随着w e b 信息的迅速膨胀 而发展起来的网上信息检索工具。仅靠用户手工方式,要在如此浩瀚的信息海洋 里寻找信息,必然会“大海捞针”无功而返。如何有效、合理、实时地利用网络的 信息? 人们自然会想到搜索引擎这一工具。在数据挖掘和信息检索中,搜索引擎 是关键技术之一,因而对搜索引擎中搜索、索引、查询等技术的研究在数据库和 信息科学等领域中变成了一个重要的研究方向。搜索引擎正是为了解决这些问题 而出现的技术。智能搜索引擎以一定的策略在互联网中搜集、发现信息,对信息 进行理解、提取、组织和处理,并为用户提供检索服务,提供有用的信息,从而起 到智能信息查询导航的目的。搜索引擎如何融入人的智能,以及在获取有价值网 页中如何体现人的智能搜索行为已经成为计算机工业界和学术界竟相研究、开发 的对象。 人们对信息的搜索活动,离不开人的智能活动。本选题将人在图书馆中查阅 图书的智能活动分为:知觉行为、记忆行为、学习行为、思维行为、理解行为。借 鉴这些行为,将它们用于智能搜索引擎的实现过程中,模拟人工对信息需求的分 析、推理、判断、决策过程,建立智能化信息搜索技术。 1 1搜索引擎发展简况 搜索引擎的出现与计算机的硬件速度和计算机网络、信息技术的发展是密切 相关的,从1 9 9 0 年开始到现在十多年的发展历史,取得了较大的成就f 1 - 6 1 。 ( 1 ) 1 9 9 0 年,m c g i l lu n i v e r s i t y 学生m o n t r e a l 开发的a r c h i ef a q 系统, 主要技术特点是:用户必须输入正确的文件名,该系统在f t p 主机上查找,最终 提供能下载文件f t p 地址列表。 ( 2 ) 1 9 9 3 年,( a ) n e v a d as y s t e mc o m p u t i n gs e r v i c e s 大学开发的v e r o n i c a f a q 系统、s c o t l a n d 大学开发的j u m p s t a t i o n 系统、c o l o r a d o 大学开发的t h e w o r l dw i d ew e bw o r m 系统,这些搜索工具在数据库中匹配用户检索的信息,按 检索的先后次序排列搜索结果,这些软件使用到一个相同s p i d e r 程序,用于统计 第2 页西南交通大学博士研究生学位论文 w 曲服务器数量,后来则发展成为捕获网址( u r l ) 的主要工具;( b ) c o l o r a d o 大学开发的( r b s e ) s p i d e r 程序,是第一个索引h t m l 文件正文的搜索引擎,也 是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎; ( c ) s t a n f o r d 大 学学生开发的e x c i t e 系统能分析网页中字词关系。 ( 3 ) 1 9 9 4 年,( a ) s t a n f o r d 大学美籍华人j e r r yy a n g ( 杨致远) 和d a v i d f i l o 共同创办的y a h o o ,支持简单的数据库搜索、其中w a n d e r e r 程序只用于抓 取u r l 、提供给用户的摘要主要采用手工方式加入系统。成为第一个成熟的商业 化搜索引擎的雏形;( b ) w a s h i n g t o n 大学w e b c r a w l e r 系统是第一个全文搜索引 擎;c a r n e g i em e l l o n 大学m i c h a e lm a u l d i n 教授开发的l y c o s ,实现了搜索关键 词与搜索信息相关性排序、提供了前缀匹配和字符相近限制、网页自动摘要等功 能;( c ) i n f o s e e k 系统,用户通过一个可视化界面输入查询词,该系统将查询结果 在可视化界面上返回给用户。 ( 4 ) 1 9 9 5 年,( a ) w a s h i n g t o n 大学硕士生e r i cs e l b e r g 和o r e ne t z i o n i 开 发的m e t a c r a w l e r 系统,实现了用户提交一次搜索请求,由元搜索引擎负责转换 处理后提交给多个预先选定的独立搜索引擎,并将从各独立搜索引擎返回所有查 询结果,经过聚合处理后再返回给用户;( b ) d e c 公司的a l t a v i s t a ,是第一个支 持自然语言搜索的搜索引擎、同时还能搜索图片名称中的文字;加州伯克利分校 助教e r i cb r e w e r 、博士生p a u lg a u t h i e r 开发的i n k t o m i ,大量运用c o o k i e 储存 用户的个人搜索喜好设置;搜索与用户历史记录有关的信息;( c ) n o r t h e r n l i 曲t 公司的n o r t h e r n l i g h t 软件,支持对搜索结果进行简单的自动分类。 ( 5 ) 1 9 9 8 年,( a ) s t a n f o r d 大学博士生l a r r yp a g e 创办了g o o g l e ,再一 次改写了搜索引擎的发展史,在p a g e r a n k 、动态摘要、d a i l y r e f r e s h 、多文档 格式支持、地图股票词典寻人等方面集成搜索、支持多语言查询;r u t g e r s 大学 的t e o m a 系统,简单地实现了提问式搜索;( b ) 台湾中正大学吴升教授开发的 o p e n f i n d 软件,实现了中文搜索、同时为新浪、奇摩、雅虎提供中文搜索服务。 ( 6 ) 1 9 9 9 年,f a s t ( a l l t h e w 曲) 公司的a 1 1 t h e w e b ,利用o d p 自动 分类、支持f l a s h 和p d f 文档搜索、支持多语言搜索、还提供新闻搜索、图像搜 索、视频、m p 和f t p 搜索。 ( 7 ) 2 0 0 0 年,( a ) 北大天网,实现了强大的f t p 搜索;( b ) 北大校友李 彦宏与徐勇开发的b a i d u ,专注于中文搜索、预览全部网页、相关搜索词、错别 字纠正提示、m p 3 搜索、f l a s h 搜索。 ( 8 ) 2 0 0 1 年,y e o g i r ly u n 创立了w i s e n u t 搜索引擎。w i s e n u t 有两个 重要的功能:检索结果自动分类和相关检索词的导航。 西南交通大学博士研究生学位论文第3 页 ( 9 ) 2 0 0 2 年,m a t tw e l l s 创立g i g a b l a s t 搜索引擎。提供网页快照和即 时索引网页的功能。 ( 1 0 ) 2 0 0 4 年,微软推出m s n 搜索引擎测试版,2 0 0 5 年微软终于推出了 m s n 搜索引擎正式版。目前m s n 搜索提供网页、新闻、图象、音乐、微软的百 科全书等搜索功能。 1 2智能信息处理在搜索引擎中的应用研究现状 从实现方式讲,搜索引擎可分为三种形式:目录搜索引擎、全文搜索引擎、 元搜索引擎。本文内容是围绕全文搜索引擎进行研究的。 1 2 1全文搜索引擎的实现原理 搜索引擎实现原理可表示为图1 1 【3 1 3 】。其实现技术可以描述为 1 3 1 5 】: ( 1 ) 用户界面的作用是输入用户查询、显示查询结果、提供反馈机制。 ( 2 ) 搜索器的功能是在互联网中漫游,发现和搜集信息。它常常是一个计算机 程序,日夜不停地运行,周期性地将信息返回给索引器。 ( 3 ) 索引器的功能是理解搜索器所搜索的信息,从中抽取出索引项,用于表示 文档以及生成文档库的索引表。 ( 4 ) 检索器的功能是根据用户的查询在索引库中快速检索出文档,进行文档与 查询的相关度评价,对将要输出的结果进行排序,并实现某种用户相关性反 馈机制。 ( 5 ) 信息资源的提供者i n t e r n e t 。 实现方式上,搜索引擎将上述步骤分为两个阶段,并发展了相应的技术: ( 1 ) 信息获取 搜索器向i n t e r n e t 网寻找信息; i n t e r n e t 向搜索器返回新信息; 将的新信息送入索引器按全文或关键词分类; 将分类的信息写入服务器的索引数据库,即信息库; w e b 网页搜索是否结束。否,转向,是,结束搜索。 ( 2 ) 信息检索与服务 用户提出请求,即输入关键词,送入检索器,形成s q l 查询语句或 相应的自制查询函数; 检索器检索在索引数据库中存在的用户信息; 索引数据库将查询的结果送到检索器; 第4 页西南交通大学博士研究生学位论文 图1h 搜索引擎的工作原理 检索器把查询的结果整理返回给用户。 现有搜索引擎中主要实现技术可归纳为:信息获取、索引技术与检索技术 如表( 1 1 ) 所示。 表1 1 :搜索引擎主要技术 序号部件功能技术 1 用户界面输入查询信息 i n t e r n e te x p l o r e r 2 搜索器信息获取 s p i d e r 、 c r a w l e r 3 索引器加工信息成为知识关系数据库 4检索器查找信息排序查询、s q l 查询 5i n t e r n e t 信息载体计算机网络 6 实现方式b r o w 8 e r s e r v e r 皇占车钮 全文搜索引擎实现的理论基础在于网页的链接结构。1 9 9 1 年,b u t a f o g o 和 s c h n e i d e r m a n 开始着手从图论的观点,研究i n t e r n e t 的链接结构,它们第一次定义 w e b p a g e 图f 1 4 ,1 5 :设y 是一个网页集合,则可以依此生成一个图g = v e ) , 其中v 表示网页结点集若p ,q v ,它们为两个网页,在网页p 中存在一条超 链接( h y p e r l i n k ) 指向网页q ,那么在图中存在一条边e = ,q ) e b u t a f o g o 和s c h n e i d e r m a n 根据图结构中结点的特性,将结点划分成了两大类:( 1 ) 索引 ( i n d e x ) 结点和引用( r e f e r e n c e ) 结点,同时探讨了网页的聚簇性与主题之间 西南交通大学博士研究生学位论文第5 页 的关系1 6 1 。在搜索引擎研究的初期,i n t e r n e t 中网页的链接结构,已经被引起 注意,并在1 9 9 8 年成功地应用于t h ew o r l d w i d ew e bw o r n 系统中 1 7 ,1 8 , 用于统计i n t e r n e t 网络上的服务器数量,在i n t e r n e t 站点不多的背景下,网络上 的网页数量比较少,网页与网页之间的链接结构比较简单,因此研究者主要倾注 于c o m p u t e rr o b o t 程序遍历网络中站点的算法研究,并未注重于其算法本身的 时间和空间复杂性,显然这不适应于当前i n t e r n e t 网络中信息的充分利用。1 9 9 8 年,b r i n 和p a g e 1 9 1 提出了网页权值分析方法( p a g e r a n k 算法) ,并成功的用 于g o o g l e 搜索引擎,在w e bp a g e 获取质量上,取得了前所未有的效果。与此同 时k l e i n b e r g 等提出了著名的h i t s 算法 2 0 ,将网页分为集中网页( h u b ) 和权 威网页( a u t h o r i t i v e ) ,通过权威与集中网页之间的相互关系来计算网页的权威 值和集中值,可用于权威网页的发现和w e b 结构的自动发现。后来在学术界提出 了许多衡量i n t e r n e t 网页重要程度的算法,如2 0 0 3 年p t s a ( 路径树生成) 算法 【2 1 、2 0 0 4 年结构语义树算法 2 2 ,但是这些算法都没有得到广泛使用。 1 2 2智能信息处理的研究简况 智能信息处理是借助现代计算工具模拟人类的智能求解或信息处理过程的理 论与方法,它是人工智能的重要内容。智能信息处理以计算智能为基础,在信息 处理过程中具有分布、并行的特点,强调自学习、自组织和自适应。在智能信息 处理中,最突出的成果和当前的研究热点是: ( 1 ) 基于模拟进化 2 3 】计算的智能信息处理,模拟进化计算是从模拟智能 生成过程发展起来的。通过对实际问题的遗传编码和适应值选取,使用模仿生物 进化过程的所谓选择算子、交叉算子和变异算子,模拟进化计算已成功解决了若 干复杂系统的优化与搜索等问题。 ( 2 ) 基于人工神经网络【2 4 的智能信息处理,人工神经网络是从模拟智能 结构发展起来的。利用神经网络的自学习、自组织和并行计算的特点,神经网络 可以解决海量数据的分类、复杂函数的逼近、复杂系统的控制等实际问题; ( 3 ) 基于自动推理的智能信息处理。逻辑与模拟智能行为关系甚密,逻辑 学从经典的二值逻辑已经发展到各种各样的多值逻辑。现实生活中,不确定性信 息广泛存在,1 9 7 5 年,z a d e h 2 5 】提出了基于模糊集合理论研究人类自然语言 的学术思想,这是形式化表示不确定性信息的有效工具之一借助隶属函数和模 糊推理,能够使计算机处理信息的过程体现出部分人类智能的特点。 1 9 9 4 2 0 0 3 年,徐扬【2 6 研究了一种依据基于格蕴涵代数的格值逻辑的不确定性推理和自动 推理,为解决“不可比较性”和“模糊性”两类问题提供了理论和方法【2 7 】。 第6 页西南交通大学博士研究生学位论文 ( 4 ) 1 9 9 4 年,p a w l a k 2 8 1 提出了粗糙集的概念,并成功的应用在数据库 中的知识发现( k d d ) 领域。粗糙集理论是k d d 的重要工具之一,使用粗糙集 理论可以解决不精确、不确定、不协调、不完备信息系统的属性约简、知识提取 等具有实际应用价值的问题。 ( 5 ) 概念是人类进行思维最基本的单位,是用来组织成为诸如判断、结论 等更为复杂思想的基础,是人类进行知识表述的一种有效手段。w i l l e 2 9 1 在1 9 8 2 年作为一种数学理论首先引入了概念格( c o n c e p tl a t t i c e ) ,奠定了形式概念分析 的理论基础,将哲学的概念进行数学化的描述,实现了概念的一种形式化描述方 法。概念格理论是形式概念分析理论的核心数据结构,被认为是知识发现和数据 分析的有力数学工具,并在信息检索、数字图书馆、软件工程和知识发现等方面得 到了良好的应用:( a ) 1 9 9 8 年e k l u n d 和m a r t i n 3 0 展示了概念层次进行w e b 文 档索引和导航的能力。1 9 9 9 年n e u s s 和k e n t 3 1 1 使用概念格进行i n t e r n e t 上文 档信息的自动分类和分析。1 9 9 9 年c o l e 和e k l u n d 3 2 1 将概念格方法应用于分析 和可视化具有1 9 6 2 个属性和4 0 0 0 个处方摘要的医药数据库。2 0 0 0 年l e n g n i n k 和s t u m m e 等 3 3 1 将v s m 模型中的相似度和距离概念转换到格模型中。2 0 0 1 年 c a r p i n e t o 和r o m a n o 3 4 1 将查询插入文档集的概念格中,用最短路径方法计算文 档与用户查询条件的相似度,以解决词汇不匹配问题。( b ) c o r b e r t t 和b u r r o w 提出了使用概念格表示建筑早期设计软件支持环境( s e e d ) 中的状态图的表示, 使得设计中获得的知识可以重用。s c h m i t t 和s a a k e 等在文献 3 5 设计了一个 有效算法,合并具有相互重叠类型的类继承层次,来导出继承层次。1 9 9 7 年s i f t 和r e p s 3 6 提出可以使用概念格方法识别以往程序代码中的潜在模块 g o d i n 和m i n e a u 等在文献【3 7 中描述了使用概念格方法从现存软件系统中生成和检索 摘要的方法,并通过两个软件的重用过程演示了该方法。文献【3 8 1 将概念格应用 于类层次( c l a s sh i e r a r c h y ) 的设计上。( c ) 已有不少学者讨论了从概念格上提取 规则或函数依赖的问题。同其它分类器相比,概念格上提取的规则具有相当或更 好的分类效果。1 9 9 7 年g o d i n 3 8 1 等提出了一种增量式概念格建造方法,并在其 基础上提出在概念格上提取蕴含规则的算法。其基本思路是系统生成当前节点的 所在幂集,并检查其是否包含在其父节点中,若没有则生成以该集合为前件的规 则。1 9 9 7 年j i w o u s 和n g u i f o 开发的l e g a l 系统【3 9 通过引进两个参数a 和 p ,改进b o r d a t 的算法,将其应用于分类任务算法在构造新节点时,只有至少 由a 个正例所确认的节点才会被加入到候选项集中,而候选项集中的元素只有至 多被p 个反例所确认才会被插入格中。1 9 9 5 年s a h a m i 开发的r u l e l e a r n e r 系统 4 0 采用一种“标记法”从格中提取规则。g a l o i s 系统【4 1 】是意大利c a r p i n e t o 西南交通大学博士研究生学位论文第7 页 建立的,用于概念聚类。t o s c a n a 系统是w i l l e 所在研究所发展的一个基于概念 格的数据分析系统。该系统的特别之处在于它能够对现有的概念格的某个概念进 一步求精,而获得一个嵌套的概念格。这使得对概念的分析更为直观方便。 l 2 3智能信息处理在搜索引擎中的应用 近年来,网络信息智能处理备受学术界的关注网络信息智能处理是依赖于 机器学习、a g e n t 、自动推理、软计算、阿格计算等方法在计算机网络中模拟人 类的智能和智能行为获取加工、检索信息的理论与技术和方法。主要特色在于 将人的智能和智能行为应用于网络信息处理中,在人们赋予计算机网络大量的知 识和经验下,建立知识推理系统为核心,对知识进行组织、再生和再利用,对网 络中的信息进行拟人化地感觉、认知、记忆、学习、联想、计算、推理、决策、抽 象、概括等思维活动。搜索引擎中的智能信息处理就是其中研究方向之一。 根据文献 4 2 所提到的目前搜索引擎存在的主要问题,2 0 0 4 年我们对g o o g l e 中文、百度、天网三大中文搜索引擎智能性问题的判断进行测试1 4 3 ,测试中定 义了三个指标:( 1 ) 用户不能准确地用关键词或关键词串来忠实地表达所真正 需要检索内容的检索,例如用户想查询:数理逻辑误输为数力逻辑。检索结果集与 用户真正表达的意义匹配程度,称之为“容错性”。( 2 ) 在人类的自然语言中, 随着时间、地域或领域的改变,同一概念可以用不同的语言表现形式来表达,检 索结果集与本概念的书面用语表达耦合的程度,称之为“适语性”。例如:当一个 用户需要检索“计算机”这一关键词,由于其习惯地输入“电脑”或“电老虎”, 检索结果与使用“计算机”这一概念检索结果耦合的程度。( 3 ) 不同的用户由 于不同专业、生活环境对同一关键词的检索,其要求检索出不同的信息,称之为 “个性化”。例如计算机工程应用人员与计算机理论研人员都检索计算机教学, 他们对检索的内容就有不同的要求。其测试结果见表1 2 。实验表明基于关键词 的搜索引擎在容错性、适语性、个人化等的智能能力较差。三个搜索引擎在适语 性、个性化上都没处理,只有百度对误输入有判别。其主要原因还得从基于关键 词的搜索引擎的实现方法来分析。诸多关键词的搜索引擎由搜索器、索引器、检 索器和用户接口、i n t e r n e t 网络等五个部件组成,他们之间的关系可见图1 1 。在 提高搜索引擎的智能上,该图一信息获取步骤中以和最为重要,中的 方法主要是s p i d e r 或r o b o t 等w e b 爬行算法,如康柏系统研究中心的m e r c a t o r c r a w l e r 、卡内基梅隆大学的w e b s p h i n x 、斯坦福大学的g o o g l ec r a w l e r 、上海 交通大学的i g l o oc r a w l e r 4 4 ,这些爬行虫的算法主要是如何合理分配u r l 和提 高爬行时间的讨论,爬行虫在网上爬行什么内容的网页是针对大众用户而设计, 第8 页西南交通大学博士研究生学位论文 用户 g o o g l e 中文 百度搜索天网搜索 查询词 n 4s +sns 数理逻辑 6 1 2 00 1 29 0 4 00 1 4 51 8 7 30 1 2 2 容错性数力逻辑 6 4 9 0 00 ,1 89 0 4 00 1 4 500 误输入无相应问用户是否查询无相应 的判别的处理数理逻辑的提示的处理 计算机 1 7 5 0 0 0 0 o 0 611 8 0 0 0 0 0 o 0 0 1 9 6 8 o 3 i 7 适语性电脑 2 1 0 0 0 0 0 o 0 92 1 8 0 0 0 0 0 o 0 0 11 7 30 0 4 8 电老虎 2 4 6 0o 1 66 2 9 0 0 1 8 6 o0 计算机应用 9 7 5 0 0 00 1 83 6 9 0 0 0o 0 0 13o 1 2 2 个性化计算机理论 3 7 7 0 0 0 o 1 9 4 3 5 00 0 9 9 1 o 1 2 1 计算机教学 5 6 5 0 0 0o 3 22 1 5 0 0 00 0 0 1600 9 9 + s 查询时间( s e c o n d ) ,n 查询到的网页数;”( 实验时间2 0 0 3 3 1 9 :1 0 :4 0 ) 并非根据不同的用户而设计,搜索过程在大众化关键词检索中,有较好的结果, 但是并没有考虑用户个人的兴趣,这些是造成容错性、适谮洼、个人化等的智能 能力较差的主要原因。中目前的方法是将爬行虫返回的网页进行关键词切分, 然后放回信息数据库;切词分词的方法主要有基于字典和规则的,用户检索的信 息准确与否在于规则库和字典的好坏,目前这些规则库和字典也是针对大众用户 设计,也并非个性化的。从提高搜索引擎的智能来分析,该图 一 信息检索与 服务的步骤中和是关键性的步骤,各搜索引擎在做这两步的时候主要是使用 关键词( 用户输入) 与信息数据库中信息1 0 0 的匹配办法来实现然而这种方 法对人输入关键词的意义、环境、不同用户的专业知识等没有也无法正确理解。 当然,也有一些文献从提高搜索引擎智能的角度去解决搜索精度的问题。搜 索引擎的智能性探讨的方法可以归结为: ( 1 ) “以网对网”的信息搜索强调了对用户的输入信息的智能分析,在搜 索过程中逐步交互式输入信息,从而实现对查询的智能导航这种逐步求精的策 略解决了信息检索“忠实表达”的难题,然而它又很难解决i n t e r n e t 网络搜索过 程中需要智能分析的问题。例如:用户想获取“数理逻辑方面的论文”,其输入可 能是“数理逻辑”和“论文”两个关键词。在搜索过程中应该以“数理逻辑”为主 进行搜索,哪些是资料哪些是论文呢? 这就需要一个推理过程。即对用户的语言 环境和专业背景的理解,以网对网技术没有解决这一问题。 西南交通大学博士研究生学位论文第9 页 ( 2 ) 关键词搜索引擎的智能问题,在文献【4 5 中,主要把用户的历史点击 和信息的选择记录下来,根据其变化情况来改变和更新检索界面的相关度排列情 况,以此提高搜索引擎的智能。 ( 3 ) 用智能体的方法来提高搜索引擎的智能 4 6 4 8 ,它将人工智能的有关 智能体技术用于搜索引擎的实现技术上,主要思想为:在搜索引擎的爬行过程和 检索过程中提倡搜索过程的多代理体化、学习化,检索过程的个性化。该思想的 主要来源于近几年出现的元搜索引擎 1 7 ,4 9 ,元搜索引擎( 图1 2 ) 5 0 ,5 1 利 用各集中式搜索引擎对i n t e r n e t 的爬行结果,合成生成用户的查询结果。目前元 搜索引擎的研究主要表现以下几个方面:借助于这一思想,在全文搜索引擎智能 化的实现研究中,采用了多智能体技术,将用户查询分配给不同的软件代理,每 一个软件代理负责在i n t e r n e t 中查找特定的信息。然后由搜索引擎分析、判断、 取舍各代理的返回结果,并聚集在一起返给用户。 厂 l l 厂一一一一一一一一一一一一 甲 用户w e bl - a g e 浏览器 , l 学嗲琵t 嚣i j 查锚条件l 匕二二= ,i 文档 l 1分配器ll获取器i s e - ls e 。l 厂 同| | | s e 。 图12 :元搜索引擎的体系结构 用户 界面 ( 4 ) 网络蜘蛛的智能化,网络蜘蛛( s p i d e r ) 的概念起源于1 9 9 0 年,2 0 0 3 年 c h a u 和c h e n 在文献5 2 1 中对其概念第一次定义为一个在w o r l dw i d ew e b 信息 空间中根据网页链接结构,遍历整过i n t e r n e t 和根据h t t p 协议从i n t e r n e t 网络 中获取文本的一个计算机程序。目前能在各种搜索引擎中使用的蜘蛛程序有3 0 多 种,其中著名的网络蜘蛛是:a o ls e a r c hn e t f i n d 、a l t a v i s t a 、w e b c r a w l e r 5 3 1 等,搜索引擎中的网络蜘蛛避开了网页文本内容的研究、以网页链接

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论