（计算机应用技术专业论文）模糊聚类在搜索引擎自动分类上的应用.pdf

模糊聚类在搜索引擎自动分类上的应用中文摘要 模糊聚类在搜索引擎自动分类上的应用 中文摘要 w e b 上的信息资源呈爆炸式的增长，人们查找信息越来越难。搜索引擎是其信息 利用的主要工具，然而当前搜索引擎存在不足：基于关键字匹配的搜索引擎排序网页 时仅仅考虑评价网页的重要性，而忽视分类；基于分类目录的搜索引擎很难动态分析 w e b 信息。本文在分析它们不足的前期下，提出建立具有自动分类功能的搜索引擎， 并尝试对这方面的部分关键技术进行研究。 文中首先从分析搜索引擎的种类和工作原理入手，分析当前搜索引擎存在的问 题。然后分析了w e b 文档模糊聚类和w e b 超链分析技术，在此研究的基础上，进一步从 下面三个方面对网页的自动分类技术做了深入研究： 1 ) 模糊聚类方法应用于w e b 网页的自动分类，通过计算网页与网页之间的相似 度建立分类类别，动态确定网页分类划分。 2 ) 提出通过提取源网页的扩展锚文本，进行目标网页特征识别，具体分析了不 同位置的锚文本扩展，以及利用x p a t h 提取网页特征的方法，并通过实验分 析其性能。 3 ) 利用模糊聚类方法结合超链分析算法对搜索引擎的检索结果自动分类，设置 调节值，值的取值变化兼顾考虑分类和p r 值的影响，返回的结果可以使用户 比较快速地定位到所需要的高质量信息。 关键词模糊聚类超链分析搜索引擎w e b 聚类 作者：严海兵 指导老师：崔志明 a b s t r a c tt h e a p p l i c a t i o no ff u z z yc l u s t e r i n gi na u t o - c a t e g o r i z i n gw e b p a g e s t h e a p p l i c a t i o no ff u z z yc l u s t e r i n gi n a u t o - c a t e g o r i z i n gw e b p a g e s a b s t r a c t w i t ht h ee x p l o s i v ei n c r e a s eo ft h en e t w o r ki n f o r m a t i o n ，i tb e c o m e sm o r ea n dm o r e d i f f i c u l tf o rp e o p l et of m dt h ei n f o r m a t i o nt h e yn e e d e d s e a r c he n g i n e sa r et h ek e yt o o l st o g e tt h ei n f o r m a t i o nu s i n gw h i l et h e ye x i ts o m es h o r t a g e s i to n l yt a k e si n t oa c c o u n tt h e s i g n i f i c a n c eo fe s t i m a t i n gt h ep a g e s a u t h o r i t yb ys e a r c he n g i n e so ns t r i n gm a t c h ，b u t i g n o r i n gw e bp a g e sc a t e g o r i z i n g i ti sd i f f i c u l tf o rt h ee n g i n e so nd i r e c t o r yc a t e g o r i e st o a u t o c a t e g o r i z ew e bp a g e si nt h ei n t e m e t f o rt h e s ed e f i c i e n c yo fd i s p l a y i n gt h er e s u l t si n t h ec u r r e n ts e a r c he n g i n e s ，t h i sp a p e ra t t e m p t st oi m p r o v et h ea r c h i t e c t u r eo fs e a r c he n g i n e s b a s e do na u t o c a t e g o r i z i n g ，a n dr e s e a r c h e sm a n yk e yt e c h n o l o g i e so ft h i sa r c h i t e c t u r e t h et y p e sa n dw o r kp r i n c i p l e so fs e a r c he n g i n e sa n dt h e l i m i t a t i o n sa r ed i s c u s s e d f l r s t l y - b a s e do nt h er e l a t e dr e s e a r c h ，t h i sp a p e rd i s c u s s e sw e bf u z z yc l u s t e r i n gt h e o r ya n d a l g o r i t h mo nh y p e d i n ka n a l y s i s f i n a l l yt h r e ek e yt e c h n o l o g i e sa r ed i s c u s s e do nw e bp a g e s a u t o c a t e g o r i z i n g 1 f u z z yc l u s t e r i n gt h e o r yi sa p p l i e dt ow e bp a g e sa u t o c a t e g o r i z i n g c a t e g o r yi s c o n s t i t u t e db yc o m p u t i n gt h es i m i l a r i t yb e t w e e nw e bp a g e sa n dw e bp a g e s t h ec a t e g o r yi s d y n a m i c 2 p r o p o s e st h a tt a r g e tw e bp a g ef e a t u r ei d e n t i f i c a t i o ni se x t r a c t e df o r ma n c h o rt e x t s n e i g h b o ro fs o u r c ew e bp a g e i ta n a l y s e st h ea n c h o rt e x t sn e i g h b o ro fd i f f e r e n t p o s i t i o na n dt h em e t h o dt oe x t r a c tw e bp a g ef e a t u r ei d e n t i f i c a t i o nb yx p a t h f i n a l l yt h ep e r f o r m a n c eo fs e a r c hi sa n a l y z e db ye x p e r i m e n t s 3 a t t e m p t st oi m p r o v ep a g e sr a n k i n ga l g o r i t h mo nh y p e r l i n ka n a l y s i si na n o t h e r p o i n to fv i e w b yi n t e g r a t i n gt h et r a d i t i o n a lh y p e r l i n ka n a l y s i s a n df u z z y c l u s t e r i n gt h e o r y , t h ea u t h o r sp r e s e n ta na l g o r i t h mb a s e do na u t o c a t e g o r i z i n g ， t h e r e b yac o e f f i c i e n ti sg o tt oa d j u s tt ot h ep r a c t i c a lc o n d i t i o n s a n dt h ea u t h o r s e x p e r i m e n ts h o w st h a tt h i sa l g o r i t h mh a sb e t t e rp e r f o r m a n c e k e y w o r d sf u z z yc l u s t e r i n g ，h y p e d i n ka n a l y s i s ，s e a r c he n g i n e ，w e bc l u s t e r w f i r e nb y ：y a nh a i b i n g s u p e r v i s e db y ：c u iz h i r u i n g l i 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：要逸兰2 日期：兰! 竺乏! 竺： 2 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名 导师签名 模糊聚类在搜索引擎自动分类上的应用第l 章绪论 第1 章绪论 本章主要介绍了“模糊聚类在搜索引擎自动分类上的应用”这一课题研究的背景， 在分析搜索引擎的分类和工作原理的基础上，提出目前搜索引擎存在的主要问题。 1 1 研究背景 随着i n t e r n e t 的发展，w e b 上的信息资源呈爆炸式的增长。根据研究公司 n e t c r a f t 在2 0 0 7 年7 月发布的w e bs e r v e r 的调查报告，全球i n t e r n e t 网站数达到1 2 6 亿多，l ：p , 6 月份增2 h 3 6 2 万。图1 1 - 1 是1 9 9 5 年8 月至2 0 0 7 年7 月的全球i n t e r n e t 网站总数 的变化统计图 t l ”! 0 一 ；0 i 一 ：i 臻冀专 ，“一；一 ：i ；| ； i | t 中“ ! ；i ”彳? ；| ； 卜t 专 母 i | ； ；”f f 下 ”甘专竹p 时 ，。；0 ；一 l l ； o 口口日叼m 了o 忙n 口o t n 口口口、口口) o c ) o c ) o c k o o c h 0 0 c k ) o c ) o c ) c c ) o o o 七巾卡t 扣f r 卜h r 朴n n r 、r 、n n f 、n n n f 、n n n n n n r 、r 、h n n n f 、n i h r 、r 、n n p co p c o q j c o p c l _ c o 叫c o p c o q je - o q j c o p v - o 叫c l c ，! u 邢o 町q j o 町q j o 吁c j 叮c 口。仍q 3 u 幛丑3 0 吧丘3 0 町o j o 町口u 巾q 3 u 吧 i h 6 掌h a m 一r c i 图1 i - i 国内i n t e r n e t 网站总数统计( 1 9 9 5 年8 月- 2 0 0 7 年7 月) 根据中国i n t e r n e t 网络信息中心( c n n i c ) 的一组统计数据：截止蛰 2 0 0 5 年1 2 月3 1 日，全国网站总数约为6 9 4 ，2 0 0 个，一年内净增j j 1 2 5 ，3 0 0 个。图1 1 - 2 是2 0 0 1 年至2 0 0 5 年国内i n t e r n e t 网站总数及发展情况统计。 q o o o q o o o o o o o o o o o o o o 9 o o o o o o o o o o o q q q q q q q q q q o o o o o o o o o o o 4 0 z 5 o 4 e 2 5 6 3 q e 5 3 o 7 亭 2 2 t q 8 7 6 5 3 2 土 土 土 l 第l 章绪论 模蝴聚类在搜索引擎自动分类t 的麻用 2 0 0 1 年 22 0 2 年2 8 0 挥 2 0 0 4 年2 0 2 5 年 匡亟亟苤三亘垂习 图1 卜2 国内i n t e r n e t 网站总数及发展情况统计( 2 0 0 1 年2 0 0 5 年 全国网页总数约有2 40 亿个。一年内增长1 75 亿个，年增长率高达2 6 9 ，其中动 态网页的增长量占总增长量的7 16 。对于此次网页数量的大幅增加，百度方面认为， 这比较客观地反映t 2 0 0 5 年中国t n t e r n e t 的实际发展情况。网页增加可能与网民的增 加、w e b 20 的发展使得由网民产生的内容大量产生、i n t e r n e t 得到更广泛的重视等因 素有关。图1 1 32 0 0 1 年至2 0 0 5 年国内网页总数及发展情况。 。 蓁 一揣 蓁 | | | | | 2 0 0 1 年一l 2 碍0 0 1 2 年2 0 0 3 年2 0 0 4 年2 瞬 口静卷阿页教日动卷阿页靛+ 年增长率 图l - 卜3 历年网页数及发展情况( 2 0 0 1 年一2 0 0 5 年) 上述数据显示i n t e r n e t 上的信息数据量大、内容繁杂而且处于不断变化之中，如 2 跏耄耋獬哪哺叫螂 模糊聚类在搜索引擎自动分类上的应用 第l 章绪论 何充分有效地利用这一丰富的资源，一直是人们努力研究的方向。 根据国内一些机构调查，约有8 5 的用户是通过搜索引擎在i n t e r n e t 上进行查询 自己需要的信息。然而又有超过4 5 的用户表示使用i n t e r n e t 的最大问题在于找到自 己真正需要的信息。 有许多因素导致搜索引擎还难以令人满意。首先，搜索引擎无法覆盖整个 i n t e r n e t 信息。实际上没有一个搜索引擎能够索引超过1 6 的i n t e r n e t 信息。而且由 于i n t e r n e t 的动态性，搜索引擎的索引中包含许多“断连接 和“过时网页”，更加 削弱了搜索引擎的作用。另外，搜索引擎的搜索结果缺乏清晰明了的结构，也是令人 感到“不好用”的一个重要原因。对于当前搜索引擎的现状，a t & t 香农实验室的b r i a n a m e n t o 指出，用重要性来评价网页的质量时，各种超链接分析算法的结果在大多数的 情况下差别很小且都不够完美。在某些查询下，结果可能很好，在另外一些查询下， 结果可能很差。所以应该根据不同查询的情况，选择不同的合适算法。查询的分类很 重要，每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求 获得最好的结果。 目前的搜索引擎一般将找到的相关i n t e r n e t 信息按照与查询的相关度从高到低 排成一个线性列表，但是一个查询得到的搜索结果往往包含成千上万的i n t e r n e t 信 息，所以搜索引擎最后产生的线性列表一般很长。虽然搜索引擎已采用了各种方法来 提高搜索精度，但是搜索结果中仍然包含了大量与用户的查询无关的信息，其比例高 达7 5 以上。搜索结果中相关信息和无关信息混杂在一起，用户不得不逐个浏览，查 找到自己真正需要的信息。为解决这个问题，许多学者努力改进检索排序算法，由于 在多数的情况下，用户提出的查询往往不能清楚表达自己的需要，尤其是当他对所搜 索的领域不熟悉时，仅仅靠改进排序算法是不够的。 1 2 搜索引擎分类 按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三大类n 1 ： 1 2 1 目录式搜索引擎 目录式搜索引擎( 又称目录索引) ：以人工方式或半自动方式搜集信息，由编辑 查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多 第l 章绪论模糊聚类在搜索引擎自动分类上的应用 面向网站，提供目录浏览服务和直接检索服务。该类搜索引擎因为加入了人的智能， 所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息更新 不及时。这类搜索引擎的代表是：y a h o o 、l o o k s m a r t 、o p e nd i r e c t o r y 、g og u i d e 等。 与机器人式搜索引擎相比，目录索引有许多不同之处。 首先，机器人式搜索引擎属于自动网站检索，而目录索引则依赖手工操作。用户 提交网站后，目录编辑人员会亲自浏览你的网站，然后根据一套自定的评判标准甚至 编辑人员的主观印象，决定是否接纳你的网站。 其次，机器人式搜索引擎收录网站时，只要网站本身没有违反有关的规则，一般 都能登录成功。而目录索引对网站的要求则高得多，有时即使登录多次也不一定成功。 尤其象y a h o o ! 这样的超级索引，登录更是困难。 最后，在登录机器人式搜索引擎时，我们一般不用考虑网站的分类问题，而登录 目录索引时则必须将网站放在一个最合适的目录。 目录索引是将网站分门别类地存放在相应的目录中，因此用户在查询信息时，可 选择关键词搜索，也可按分类目录逐层查找。如以关键词搜索，返回结果的排序和机 器人式搜索引擎一样，也是根据信息关联程度排列网站，只不过其中人为因素要多一 些。如果按分层目录查找，某一目录中网站的排名则是由标题字母的先后顺序决定。 目前，目录索引与机器人式搜索引擎有相互融合渗透的趋势。原来一些纯粹的机 器人式搜索引擎现在也提供目录搜索，如g o o g l e 就借用o p e nd i r e c t o r y 目录提供分类 查询。而象y a h o o ! 这些老牌目录索引则通过与g o o g l e 等搜索引擎合作扩大搜索范 围。在默认搜索模式下，一些目录类搜索引擎首先返回的是自己目录中匹配的网站， 如国内搜狐、新浪、网易等；而另外一些则默认的是网页搜索，如y a h o o 。 1 2 2 机器人式搜索引擎 机器人式搜索引擎( 又称搜索引擎) ：由一个称为蜘蛛( s p i d e r ) 的机器人式程序 以某种策略自动地在i n t e r n e t 中搜集和发现信息，由索引器为搜集到的信息建立索 引，由检索器根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式 是面向网页的全文检索服务。该类搜索引擎的优点是信息量大、更新及时、毋需人工 干预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类搜 索引擎的代表是：a l t a v i s t a 、n o r t h e r nl i g h t 、e x c i t e 、i n f o s e e k 、i n k t o m i 、f a s t 、 4 模糊聚类在搜索引擎自动分类上的应用第l 章绪论 l y c o s 、g o o g l e ；国内代表为i 天网、百度等。 用户在使用搜索引擎时并不真正搜索i n t e r n e t ，它搜索的实际上是由索引器预先 整理好的网页索引数据库。通常搜索引擎收集了i n t e r n e t 上几千万到几十亿个网页并 对网页中的每一个词( 即关键词) 进行索引，建立索引数据库的全文搜索引擎。 由索引器程序对收集回来的网页进行分析，提取相关网页信息( 包括网页所在 u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网 页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对 页面内容中及超链中每一个关键词的相关度( 或重要性) ，然后用这些相关信息建立 网页索引数据库。现在的搜索引擎普遍使用的是超链分析技术建立索引，如g o o g l e 的 p a g e r a n k 。 当用户输入关键词搜索后，由搜索器程序从网页索引数据库中找到符合该关键词 的所有相关网页。因为所有相关网页针对该关键词的相关度早已算好，所以只需按照 现成的相关度数值排序，相关度越高，排名越靠前。最后，由页面生成系统将搜索结 果的链接地址和页面内容摘要等内容组织起来返回给用户。 搜索引擎的s p i d e r - - 般要定期重新访问所有网页( 各搜索引擎的周期不同，可能 是几天、几周或几个月，也可能对不同重要性的网页有不同的更新频率) ，更新网页 索引数据库，以反映出网页内容的更新情况，增加新的网页信息，去除死链接，并根 据网页内容和链接关系的变化重新排序。这样，网页的具体内容和变化情况就会反映 到用户查询的结果中。i n t e r n e t 虽然只有一个，但各搜索引擎的能力和偏好不同，所 以抓取的网页各不相同，排序算法也各不相同。 1 2 3 元搜索引擎 元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个 搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返 回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息 量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多的筛 选。这类搜索引擎的代表是w e b c r a w l e r 、i n f o m a r k e t 、d o g p i l e 、v i v i s i m o ；国内代 表为：搜星搜索引擎等。 在搜索结果排列方面，有的直接按来源引擎排列搜索结果，女h d o g p i l e ，有的则 按自定的规则将结果重新排列组合，如v i v i s i m o 。 5 第1 章绪论模糊聚类在搜索引擎自动分类上的应用 1 3 搜索引擎工作原理 根据搜索引擎的分类，可以了解到搜索引擎的工作原理应该主要设计两种类型的 搜索引擎：机器人搜索引擎和目录索引的原理。 1 3 1 目录索引的分类原理 i n t e r n e t 网络信息成海量增长，各个搜索引擎根据自身的需要建立了不同的分类 体系，对于我们网站服务定位限定了一个框架。准确利用这一框架可以提高我们在相 应分类目录中的排名；忽视它的存在将可能造成我们建立的网站有类无法入的尴尬局 面。 下面我们分析以下搜索引擎目录索引分类的原n - 1 基本大类的设置 大类是分类体系的大纲，是支撑整个分类体系的总体框架，也是用户的检索入口。表 1 3 1 - 1 是国内外几个比较典型的分类搜索引擎的大类体系，从中可以分析出目前搜 索引擎分类体系在大类设置方面的一些特点。 表1 3 1 1 6 模糊聚类在搜索引擎自动分类上的应用第l 章绪论 大类的设置大多采用以主题为中心或主题与学科相结合的方式。以搜狐为例，在 搜狐的1 8 个大类中，按主题立类的有1 2 个， 分别是：娱乐休闲、工商经济、公司企业、体育健身、卫生健康、生活服务、社 会文化、国家地区、电脑网络、新闻媒体、旅游交通、个人主页等；而按学科立类的 有6 个，分别是：文学、社会科学、教育、艺术、科学技术、政治法律军事等。 大类的设置突出了娱乐、旅游、教育等与生活密切相关、普通用户普遍关注的类 目，更多地考虑到了信息量、信息内容的重要性及其使用频率，而相对地弱化科学技 术、学术性类目的设置。绝大多数搜索引擎将“科学技术 和“社会科学 分别设置 为一个大类，而不再细分。同时将用户使用频率高的内容从“科学技术 、“社会科 学”类目中分离出来，单独列类。如搜狐分类体系中的“电脑网络 、“新闻媒体”、 “教育培训”等，将这几个类提升为一级类目就是考虑到其使用频率，应该说这样的 设置是与传统文献分类的用户保证原则是一致的。 大多数大类体系提供多途径的检索方式。除了从信息资源的主题学科角度进行检 索外，一般还可以从地区、资料类型、机构等角度进行查询，女h y a h o o 分类体系列有 “r e g i o n a l ”一类，搜狐也设有“国家与地区 类目。 2 类目体系的展开与类间关系的揭示 按事物对象设类。搜索引擎分类体系多采用直接按照特定的事物对象设类。如搜 狐的“电脑网络类下设有“手机铃声 、“桌面壁纸 等二级类。这种类目设置 方式可以减少常用类目的显示等级，增加分类体系的直接性和易用性。同时搜索引擎 分类体系还为受广泛关注的间题设类，如搜狐的“卫生与健康类下设有“心理 、 “性教育 、“减肥 等二级类目。 多元划分。搜索引擎分类体系的类目展开，往往在一些类下同时采用两个或两个 以上标准，大类下的进一步划分标准通常是多元的。运用链接技术并结合屏幕显示的 特点采用多重列类的方法组织信息，使得分类搜索引擎在类目展开时各层次下的类目 类型多、数量大、范围广，同时减少了类目展开的层次，增加类目的直接性，为从不 同角度展开类目体系提供了条件。 多维展开。多维展开是指使用不同的引用次序列类，多维地展开类目体系。通过 超文本链接在相关类下重复反映，使整个类目体系成为一个分别从主题内容、地区、 资源类型等多角度展开的网络结构。多维展开最典型的例子是国内外众多的搜索引擎 7 第1 章绪论模糊聚类在搜索引擎自动分类上的应用 对文学作品类的设置。不少搜索引擎对文学作品根据其体裁、国别、时代、题材等不 同属性，同时采用多种引用次序来组织类目，增加系统的检索人口，方便用户选择合 适的路径进行检索。 类间横向关系的揭示。在网络环境下，由于超文本技术白运用，类间横向关系的 揭示比在纸质环境下方便得多。目前搜索引擎分类体系对这类关系的反映主要是将横 向关系在相关类下重含反映，同时采用 符号加以表示。 3 类目的排列 目前的英文搜索引擎一般采用主题字顺方式组织类目体系。这种方式比较符合英 语地区用户的检索习惯，也易于排列同位类。国内中文分类搜索引擎对同位类的排列 主要采用以下几种方式：一是系统排列，它是根据类目之间的内在联系排列，列类次 序反映了客观事物本身的发展和联系。二是按使用频率排列，在同位类排列时，把使 用频率高的类目排列在前，使用频率低的类目排列在后。这种排列方式比较实用。三 是按字顺排列。汉字的字顺不如西文直观，字顺检索也不如西文便捷。汉字字顺排列 虽然有着严格的顺序，但在揭示类目之间学科相关性及类目的重要性方面不具备优 势。 1 3 2 机器人搜索引擎的工作原理 一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成，如图 1 3 2 1 所示。 8 模糊聚类在搜索引擎自动分类上的应用第1 章绪论 图1 3 2 1 机器人搜索引擎的工作原理图 1 搜索器 搜索器的功能是在i n t e r n e t 中漫游，发现和搜集信息。它常常是一个计算机程序， 日夜不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为 i n t e r n e t 上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接 和无效连接。目前有两种搜集信息的策略： 从一个起始u r l 集合开始，顺着这些u r l 中的超链( h y p e r l i n k ) ，以宽度优先、 深度优先或启发式方式循环地在i n t e r n e t 中发现信息。这些起始u r l 可以是 任意的u r l ，但常常是一些非常流行、包含很多链接的站点( 如y a h o o ! ) 。 将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责一个子空间 的穷尽搜索。 搜索器搜集的信息类型多种多样，包括h t m l 、x m l 、n e w s g r o u p 文章、f t p 文件、 字处理文档、多媒体信息。搜索器的实现常常用分布式、并行计算技术，以提高信息 发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。 2 索引器 9 第l 章绪论模糊聚类在搜索引擎自动分类上的应用 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于生成索引表 数据。 索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关，如作者 名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等等；内容索引项 是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以分为 单索引项和多索引项( 或称短语索引项) 两种。单索引项对于英文来讲是英语单词，比 较容易提取，因为单词之间有天然的分隔符( 空格) ；对于中文等连续书写的语言，必 须进行词语的切分。 在搜索引擎中，一般要根据“超链分析技术“给索引项赋与一个权值，以表示该 索引项对文档的区分度，同时用来计算查询结果的相关度，用于决定结果的排序。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现 即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速度。索引算法对 索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。一个搜索引擎的有效 性在很大程度上取决于索引的质量。 3 检索器 检索器的功能是根据用户的查询在索引表数据中快速检出文档，进行文档与查询 的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。 4 用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主 要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时 的信息。用户接口的设计和实现使用人机交互的方法，以充分适应人类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询 串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算( 与、或、非) 、相近 关系( 相邻、n e a r ) 、域名范围( 如e d u 、c o m ) 、出现位置( 如标题、内容) 、信息时间、 长度等等。 1 4 目前搜索引擎存在的主要问题 搜索引擎是目前w e b 信息利用的主要工具，传统上搜索引擎分为基于关键字匹配 1 0 模糊聚类在搜索引擎自动分类上的应用第1 章绪论 的机器人式式搜索引擎和基于分类目录技术的目录式搜索引擎两种。它们在w e b 信息 的利用上各有利弊。 基于关键字匹配的搜索引擎检索出的结果往往太多、太乱而使得查准率和查全率 不高。近几年的研究发现，通过分析w e b 页的重要性，主要是超链结构的分析，可以 提高检索的质量。如，在1 9 9 8 年，s e r g e rb r i n 和l a w r e n c ep a g e 提出了p a g e r a n k 算法， j k l e i n b e r g 提出了h t t s 算法，使得检索结果的质量得到了极大的提高，然而检索结 果依然是无分类杂乱的，不便于信息检索的利用。 基于分类目录的搜索引擎传统上是部分人工参与的，面对每时每刻都在变化的 i n t e r n e t 往往是分类不够及时，又由于一些主观因素的影响，对于检索结果排序的合 理性是缺乏统一尺度的。 对于当前搜索引擎的现状，a t & t 香农实验室的b r i a na m e n t o 在也指出，用重要性 来评价网页的质量各种超链接分析算法的结果在大多数的情况下差别很小且都不够 完美。在某些查询下，结果可能很好，在另外的查询下，结果可能很差。所以应该根 据不同查询的情况，选择不同的合适的算法。查询的分类很重要，每种算法都有自身 的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果乜1 。 为了解决上述现有w e b 信息的利用不足，本文进行了一些改进性的研究，利用模 糊聚类的方法对搜索引擎的检索结果进行自动化生成类别和分类，依据超链分析算法 和w e b 文档隶属程度相结合进行分类排序，以结合两种w e b 信息检索利用的优点，提高 检索效率。 第2 章w e b 网页模糊聚类模糊聚类在搜索引擎自动分类上的应用 第2 章w e b 网页模糊聚类 由于一个w e b n 页的主题特征往往有多个，网页的归属分类的界限是不明确的， 存在着大量的模糊类别划分的现象，作者试图利用文本文档的模糊聚类方法应用于网 页。本章节主要介绍了模糊聚类的基本概念和方法。 尽管搜索引擎采用了各种方法来提高检索结果的精度，但是结果中仍然包含了与 用户查寻请求不相关的文档，其比例高达7 5 以上。此外，搜索引擎返回给用户的通 常是一个线性的文档列表，虽然经过了相关度排序，但是相关文档和不相关文档仍然 混杂于其中，用户必须逐个地浏览以找到相关文档，花费了大量的精力。当返回的结 果数目众多时，这个问题更为突出。在信息检索工作中，通过聚类对检索结果进行访 问若干个组，用户可以定位到相关的组并从中找到所需文档，大大缩小了所浏览的结 果数量。 传统上聚类分析有系统聚类法、分解法、加入法、动态聚类法、有序样品聚类和 有重叠聚类等，它们对于w e b 信息的分类应用不是很好。w e b 信息是多样性和大量性的， 一个给定的网页往往可能分属于多个类口1 ，例如一个关于旅游经济主题的网页，既属 于旅游类，又属于经济类。模糊聚类分析针对于一些w e b 文档分类隶属界限不分明， 利用模糊集合理论和模糊划分对w e b 信息进行分类。 2 1 模糊集概念 2 1 1 模糊集定义与隶属函数【3 】 经典集合论中，利用特征函数c ( x ) 表示元素x 是否属干集合s ，即： 但不能很好地描述一个模糊概念。美国计算机与 控制论专家扎德从表示经典集合的特征函数得到启发，提出了隶属函数的概念，用以 刻画模糊集合，以便很好地描述模糊现象。 1 2 念概的叨确述 s s 晤 仨参瞄蒜 l 0 台厅 治 一 集 对 典 ，k 一 “ 经 模糊聚类在搜索引擎自动分类上的应用第2 章w e b 网页模糊聚类 定义2 1 - 1 - 1论域u 上的一个模糊集合a 通过一个隶属函数刻画： p a ( x ) ：u 一【o ，1 】 x u 对任意x u ，都指定一个数u ( x ) o ，1 与之对应，称为x 对a 的隶属度，u 称 为a 的隶属函数。若p ( x ) = 0 ，则x 完全不属于a ；若u 。( x ) = 1 ，则x 完全属于a ；若o o ，v h m c 称为对象集x 被分成c 类的硬划分空间。m c 包含了x 被分成c 类的所有可能结果， 这种分类称为硬划分。 2 2 1 模糊划分( 软划分) 在硬划分的基础上，j c b e z d e k 利用模糊集合的概念提出了模糊划分( 软划分) 问题，认为被分类对象集合中x 中的对象x 。，以一定的隶属度属于某一类，也就是说， 所有对象都分别以不同的隶属度隶属于某一类。因此，每一类就被认为是对象集x 上 的一个模糊子集，于是每一种这样的划分结果所对应的分类矩阵，就是一个模糊矩阵 r 。 1 6 模糊聚类在搜索引擎自动分类上的应用 第2 章w e b 网页模糊聚类 矩阵r 具有如下的性质： 1 ) r h i 0 ，1 ，即划分矩阵元素在0 与1 之间取值； 2 ) = l ，即每一列中分别属于各类的隶属度之和为1 ，对一个对象而言它对 h = l 各类的隶属度之和为l ； 3 ) o ； 重复上述步骤，直至c 中剩下一个簇为止。 该过程构造出一棵生成树，其中包含了簇的层次信息，以及所有簇内和簇间的相 似度。层次聚类方法是最为常用的聚类方法，它能够生成层次化的嵌套族且准确度 较高。但是，在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的 两个簇，因此运行速度较慢，不适合于大量文档的集合。 平面划分法与层次凝聚法的区别在于，平面划分法将文档集合水平地分割为若下 个蔟，而不是生成层次化的嵌套簇。对了给定文档集合d = d 1 , , d i , - - - , d n ) ，平面划分 法的具体过程如下： 确定要生成的簇的数目k ； 按照某种原则生成k 个聚类中心作为聚类的种子s = s l ，s i ，s k ) ； 对d 中的每个文档d j ，依次计算它与各个种子s j 的相似度s i m ( d i ，s j ) ； 选取具有最大相似度的种子a r g m a x s i m ( c i ，s j ) ，将d i 归入以s j 为聚类中心的聚类 s j e s 中心的簇c i ，从而得到d 的一个聚类c = c l ，c k ； 重复上述步骤若干次，以得到较为稳定的聚类结果。 该方法的运行速度较快，但是必须事先确定k 的取值，且种子选取的好坏对聚类 结果有较大影响。 2 4 模糊相似系数的标定 基于模糊相似关系的模糊聚类首先是建立模糊相似矩阵，建立模糊相似矩阵的关 键是标定相似系数。相似系数反映了样本之间相对于某些属性的相似程度、确定相似 1 8 模糊聚类在搜索引擎自动分类上的应用第2 章w e b 网页模糊聚类 系数有很多方法，这里列出常用的一些方法阳1 。 设x = x 。，x 。，x 。) 是全体对象的集合，每一对象有m 个特征，以x i - x n ，x 伽， x 。) 表示第i 个对象。建立模糊相似矩阵r = ( r 。，) 。的过程称为标定，r ；，表示对象x 。和x ， 的相似程度，称为相似系数。标定的关键在于合理地求出相似系数r 。，。 1 数量积法 r li = j 整。 r i j = 弋 l 击善v 业 滓j 其中，m = n 攀 善x m x 皿 。若“中出现负值，可采用下面的方法对所有r - ，进行调 方法1 ：取= 丁r i j + l ，则r ：| ；【o ，l 】。 方法2 ：取= 备三詈( i c j ) ，其中m = m 。i n r ，m = m 。a x q ，则毛【o ，l 】。 2 夹角余弦法 x # x , j k n = 罕= = k = = l = = = = = = i 朋埘 、x 三x 磊 yk = lk = l 若r 。，中出现负值，可采用上述方法调整。 3 相关系数法 ( x 址一- i ) ( x 挑) 其岷= 击喜 4 最大最小法 ( x 址a x i k ) 岛= 鼍l 一 ( x 址v x 业) 一1 x j2 i 备x 业。 1 9 第2 章w e b 网页模糊聚类 模糊聚类在搜索引擎自动分类上的应用 5 算术平均最小法 ( x 北a x j k ) 铲赫i k ， 么一、。j k 7 6 几何平均最小法 = 上1 _ 一 ( x i k x i k ) k = l 7 绝对值指数 一阻一x 重l r 葶= e b 1 8 指数相似系数法 吒= 去善产一曲2 ，鞋 9 绝对倒数法 r i j - 1 = j l 下li j l i x m a x 业l 1 0 绝对值减数法 r i i = 1 一c l x 址一x 业i 1 1 参数法 令x 缸= x 址一- - ，n ；- - 与r q 分别为x ；，x i ：x 一，x 乙x 知) 中正数个数和负数个数。 b = 如糍 1 2 贴近度法 先对x t ，x j ，做归一化处理，使x 址，x 血【o ，l 】