（计算机应用技术专业论文）web文档性质分类的研究与应用.pdf

摘要 w w w 是一个开放性的全球分布式网络，网上的资源没有统一的结构和管理，导致了 信息查找和使用的困难。网页的自 动分类可以在较大程度上消除网上信息杂乱的现象， 并方便用户准确地定位所需的信息和分流信息， 已 成为一项具有较大实用价值的关键技 术。同时， 互联网络的发展对网络信息发现服务提出了更高的要求， 仅按内 容对网页进 行分类的技术己不再适应人们的需要， 因此需要开发适合我国国情的中文w e b 文档分劣 技术，更好地帮助用户使用和管理网络信息。 本文就是针对以上情况对w e b 信息分类技术所进行的深入研究， 在总结和分析文本 分类技术和基于内容的w e b 文档分类技术的基础上， 提出性质分类的新概念， 并分析性 质分类的意义、 可行性、 具体算法以 及该技术在搜索引 擎结果优化中的 应用。 主要研究 内容包括: 1 . 总结文本分类的过程和w e b 文档的结构特点， 在此墓础上阐述基于内容的w e b 文 档分类算法， 其中包括基于网页文本的分类、 基于超链接的分类和基于查询目 志的分类 等， 详细描述了k n n 算法、 s v m 算法、贝叶斯算法和决策 树算法，并比 较和分析各种分 类方法的优缺点。 2 . 提出w e b 文档性质分类的新概念， 通过对大量网页的结构特点 研究， 分析该技术 的可行性和必要性，并在文本分类和内 容分类算法的 荃础上提出 性质分类的具体算法， 如 基于 超文本的 分类、 基于 超链 接的 分类和基于 文件 格式的 分 类等等。 3 . 比 较内容分类和性质分类的相同点和不同点， 如二者在意义、处理对象、 算法思 想、发展领域等方面基本相似， 而在含义、具体过程、发展状况等方面则大不相同， 通 过比 较有助于 更好地理解和使用w e b 文档的内 容分类算法和性质分类算法。 4 . 提出并实现性质分类技术在搜索引擎结果优化中的应用， 设计两种不同结构的 搜 索引 擎结果分类代理: 一 种是基于查询优化的结果分 类代理， 另一种是基于结果优化的 结果分类代理。并比较二者的优缺点，进而提出它们不同的应用范围。 关键词:文本分类;内 容分类; 性质分类;结果分类代理;查询优化; 结果优化 ab s t r a c t w o r l d wi d e w e b i s a n o p e n g l o b a l d i s t r i b u t e d n e t w o r k . r e s o u r c e s o n t h e n e t d o n o t h a v e u n i f o r m s t r u c t u r e s a n d c a n n o t b e m a n a g e d e a s i l y . s o i t i s d i f f i c u l t t o f i n d s o m e i n f o r m a t i o n f r o m t h e i n t e rn e t . w e b p a g e c l a s s i f i c a t i o n c a n a v o i d t h e d i s o r d e r o f w e b i n f o r m a t i o n g r e a t l y . i t c a n h e l p u s e r t o lo c a t e t h e n e e d e d i n f o r m a t i o n a n d s o r t i n f o r m a t i o n . a t t h e s a m e t i m e , t h e d e v e l o p m e n t o f t h e i n t e rn e t r e q u i r e s h i g h e r q u a l i t y i n f o r m a t i o n s e a r c h s e r v i c e s , a n d i t d o e s n o t m e e t u s e r s n e e d o n l y b a s e d o n t h e c o n t e n t o f w e b p a g e . s o i t i s n e c e s s a r y t o d e v e l o p c h in e s e w e b p a g e c l a s s i f i c a t i o n t o o l s t h a t a r e f i t f o r o u r c o u n t r y , a n d i t c a n a s s i s t u s e r s t o m a n a g e a n d c o n t r o l w e b i n f o r m a t i o n b e t t e r . t h i s d i s s e r ta t i o n s t u d i e s w e b p a g e c l a s s i fi c a t i o n d e e p l y a i m e d a t a b o v e c o n d i t i o n s . i t s u m m a r i z e s t e x t c l a s s i fi c a t i o n a n d w e b p a g e c l a s s i f i c a t i o n b a s e d o n t h e c o n t e n t , a n d c o m e s u p w i t h a n e w c o n c e p t t h a t i s c h a r a c t e r c l a s s i f i c a t io n . a t t h e s a m e t i m e , t h i s d i s s e r t a t i o n a n a l y s e s t h e c h a r a c t e r c l a s s i fi c a t i o n s u c h a s t h e s e n s e , t h e f e a s i b i li t y , t h e c o n c r e t e a l g o r i t h m s a n d s o o n . f i n a l l y , i t i n t r o d u c e s a k i n d o f a p p l i c a t i o n t o r e s e a r c h e n g i n e . t h e c o n t r i b u t i o n s o f t h i s d i s s e rt a t i o n a r e a s f o l l o ws ; 1 . i t s u m m a r i z e s t h e p r o c e d u r e o f t e x t c l a s s if i c a t i o n a n d t h e s t r u c t u r a l c h a r a c t e r o f w e b p a g e , a n d e l a b o r a t e s t h e a l g o r i t h m s o f w e b p a g e b a s e d o n t h e c o n t e n t i n c l u d i n g k n n , s v m, b a y e s , d e c i s i o n - m a k i n g t r e e a n d s o o n . 2 . a n e w c o n c e p t t h a t i s c h a r a c t e r c l a s s i f i c a t i o n o f w e b p a g e i s p r e s e n t e d . i t a n a l y s e s t h e f e a s i b i l i t y a n d n e c e s s i t y o f t h i s t e c h n o lo g y a f t e r s t u d y i n g a l o t o f s t r u c t u r a l c h a r a c t e r o f w e b p a g e a n d c o m e s u p w i t h t h e c o n c r e te a l g o r i t h m s o f c h a r a c te r c la s s i fi c a t i o n i n c l u d in g h y p e rt e x t , h y p e r l i n k , fi l e f o r m a t a n d s o o n . 3 . t h i s d i s s e r ta t i o n c o m p a r e s c o n t e n t c l a s s i fi c a t i o n a n d c h a r a c t e r c l a s s i f i c a t i o n , a n d p o i n t s o u t t h e i r s a m e n e s s a n d d i ff e r e n c e s . f o r e x a m p l e , b o t h a r e s a m e a t s e n s e , m a n a g i n g o b j e c t , a l g o r i t h m s i d e a , d e v e l o p m e n t fi e l d , a n d a r e d i ff e r e n t i n i m p l i c a t i o n , d e t a i l p r o c e d u r e , d e v e l o p m e n t s t a t u s a n d s o o n . 4 . t h e a p p l i c a t i o n o f o p t i m i z i n g r e s e a r c h o u t c o m e i s r e a l i z e d i n t h is d i s s e r t ay t i o n b y t w o k i n d s o f r e s u l t c l a s s i f i c a t i o n a g e n t s o f d i ff e r e n t f r a m e . o n e i s a n a g e n t b a s e d o n i n q u i r y o p t i m i z a t i o n , a n d t h e o t h e r i s a n a g e n t b a s e d o n r e s u l t o p t i m i z a t i o n . t h e y a r e c o m p a r e d t o p o i n t o u t t h e p r o p e r s c o p e k e y w o r d s : t e x t c l a s s i f i c a t i o n ; c o n t e n t c l a s s i f i c a t i o n ; c l a s s i f ic a t i o n ; i n q u i r y o p t i m i z a t i o n ; r e s u l t o p t i m i z a t i o n 1 1 c h a r a c t e r c l a s s i f i c a t i o n ; a g e n t o f r e s u l t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地力外， 论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为 获得东 北师范大学或其 他教育 机构的学 位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意. 学 位 论 文 作 者 签 名 : 立 .鑫 、未 日 期 : * 砂 、 .， 、 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定， 即: 东北师范大学 有权保留 并向国 家有关部门或 机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检 索， 可以 采用影印、缩 印或其 它复制手 段保 存、汇 编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 日期: 3 a . 夕 叮一 5 . 雨 指导教师签名: 日期: 学位论文作者毕业后去向: 二 作单位: 通讯地址 : 电话: 邮编: 引言 随着计算机和通信技术的飞速发展， 特别是因特网的快速发展， 使人类真正迎来了 信息时代。人们可以获得越来越多的数字化信息，据统计，搜索引擎g o o g l e 索引的网 页已经超过了几十亿， 而且仍然在呈指数增长。 面对如此浩瀚的信息海洋， 人们往往需 要投入更多的时间对信息进行组织 和整理。 为了帮助人们有效地组织和管理海量的w e b 信息，w e b 文档分类技术应运而生。它 是在文本分类的 基础七 发展起来的， 是通过利用w e b 文档的正文文本信息和h t m l 语言 结构信息， 针对w e b 文档的内容进行相似度的分类， 例如将文档分为计算机科学、 军事、 体育、政治等类别。 利用w e b 文档的分类系统， 人们可以就某一方面的内容进行更方便的查询、 使用以 及w e b 文档管理。由于分类可以 在较大程度上解决网上信息杂乱的现象， 并方便用户准 确地定位所需的信息和分流信息， 因此， 网页自 动分类已成为一项具有较大实用价值的 关键技术。 但是， 现在的w e b 文档分类系统都只能区分文档的内 容， 是针对网页的内 容进行分 类的系统， 而不能对文档的性质进行区分。 文档的 性质就是指网页中 所包含的文件的性 质， 据此可将网页分为新闻页、 广告页、 论坛页、影音页等类别。传统的w e b 文档分类 系统无法具体区分有关某一内 容的文档属于什么性质类型， 比如当 某一 用户 想要查找有 关计算机学科人工智能 方面的学术论文时， 这种分类系统就会无能为力， 这就使用户浪 费大量的时间和精力自 行查找。 到目 前为止， 尚 未出 现专门 用于 把文档按照性质分类的任何方法和软件。 本论文就 是针对这种情况对于w e b 文档性质分类进行的 研究， 并提出几种方法实 现对文档性质的 分类， 如分为综合页、 新闻面、 论坛页、 文章页等， 进而详细介绍这种技术的 在搜索引 擎结果分类中的应用。 w e b 文档性质分类技术是一种组织和 管理 信息的有效方法， 属于文 本挖掘技术范畴， 是文本分类技术的一个分支。 它能够将文档按性质特征分门别类地组织在一起， 使用户 可以 方便地获取所需求的某一类信息， 节省了 用户对w e b 文档的查找与处理时间。 另外， 性质分类可以 和内 容分类有机地结合在一 起， 形成更加详细的分类系统， 将浩瀚的w e b 信息海洋描述成具有二维特征的文档的 集合， 即 性质特征和内 容特征， 使用户对文档的 属性一目了然。 这对未来规范使用成指数增长的网络信息具有深远的意义。 信息的多元化， 复杂化为信息分类和检索的研究和发展提出了 新的挑战， 本论文的 研究工作源于上述背景， 主要是对网页分类技术进行深入的研究， 提出性质分类的新概 念，并对网页的性质分类进行了简单的实现口 第一章首 先讨论文本分类技术， 对文 本分类进行简单 的总结和评述，分 析 一 w e b 文档 的结构特点，为性质分类技术的产生奠定理论基础。 第二章详细介绍多种基于内容的分类算法， 如基于网页文本的内容分类技术、 基于 超链接的内 容分类技术、 基于网 络日 志的内 容分类等技术， 并对它们进行比 较、 分析各 自的优缺点。 第三章主要提出性质分类概念， 分析性质分类技术出现的必然性和可行性。 然后在 现有的文本分类技术和内 容分类技术的 基础上构建性质分类算法， 提出多种方法， 如基 于超文本的性质分类、 基于超链接的性质分类、 基于文件格式的性质分类等， 初步分析 各种方 法的适用范围， 并指出可以 将各种算法综合在一起，以 提高性质分类的准确性。 第四章主要对内 容分类和性质分类进行比 较， 以 便更好地理解性质分类技术的含义 和算法。 第五章详细描述性质分类方法在搜索引 擎结果分类中的应用， 提出 两种不同结构的 代理实 现对搜索结果的性质分类。 第六章是对本文的总结以及对性质分类技术的展望。 第一章w e b 文档分类技术概述 1 . 1 文本分类技术 w e b 文档分类算法是在文本分类算法的基础上结合h t m l 语言结构特点发展起来的， 由于网上大多文档所包含的信息都是文本信息， 因此本论文主要讨论w e b 文档中的文本 信息的分类技术。 这种技术的基础就是文本分类， 其中可以再结合网页自 身的结构特点 对w e b 文档进行更准确、 更详细的分类。 因此， 我们首先要讨论文本分类技术的含义和 方法。 1 . 1 . 1文本分类概述 分类是人类一 种最基本的认知形式。所谓文本分类 ( t e x t c a t e g o r i z a t i o n ) 就是 指在给定的分类体系下， 根据文本的内 容自 动地确定文本关联的 类别。由 于事先已 存在 某些文本信息的可以 使用的分类表， 此分类表一般是由领域专家事先制定 的， 或者也可 以 通过聚类处理来获取， 所以， 文本的分类处理常被研究人员看作是一种“ 有监督的学 习 ， ( s u p e r v i s i o n l e a r n i n g ) ， 它的 特点 可以 概 括为“ 先 有 类 后 有 文 档” 。 从数学角度来 看， 文 本分类是一个映射的过程， 它将未标明 类别的文本映射到已 有 的 类别中。 该映射可以是一一映射， 也可以是一对多的 映射，因为通常一 篇文本可以同 多个类别相关联， 用数学公式可表示为 : f : a - - b，其中， a为待分 类的文本集合，b 为分类体系中的 类别集合。 文本分类的映射规则是系统根据已 经掌握的每类若干样本 的数据信息， 总结出分类的规律性而建立的判别公式和判别规则。当遇到新文本时， 根 据已 经总结出的判别规则，确定文本相关的类别。 长期以 来， 文 本分 类都 是自 然语言处 理的 一个重要的 应用 领域。 直到8 0 年代末， 在 文 本 分 类 方 面占 主 导 地 位的 一 直是 墓于 知识 工 程的 分 类方 法， 即 由 专 业 人员 手 工 编 写 分类规则来指导 分类， 其中 最著名的系统是为路透社开发的c o n s t r u e 系 统rlj 。 上世纪9 0 年代以 来，随粉信息存储技未和通信技术的 迅猛发展， 大 !的文字信息 开始以 计算机可读的形式存在， 并且其数t每天仍在急剧增加。 这一方面增加了 对于快 速、自 动的文本分类的迫切播要， 另一方面又为基于机器学习的文本分类方法准备了充 分的资源。 在这种情况下， 荃于机器学习的文本分类方法产生了，该方法通常由训练和 分类两个阶段组成。 在训练阶段， 从训练文本学习分类知识， 建立分类器; 在分类阶段， 根据分类器将输入文本分到最可能的类别中。 文本分类作为组织和管理 数据的一种有力 手 段 ， 可 被 用 于抽 取符 号 知识 川 、 新闻 发 布( 、 排 序电 子 邮 件(41 、 学习 用 户兴 趣(+ 1等 方 面。 . 2文本自 动分类问题的一般性描述 文本自 动分类是一个有监督的学习 过程。 一般地， 它根据一个己 经被标注 ( 即分好 类) 的 训练文档集合， 找到文档特征和文档类别 之间的关系模型， 然后利用这种学习得 到的关系模式对新的文档进行类别判断。 总体上，文本自 动分类主要有以下五个问题需要解决。 ( i ) 获取 训练文 档集合 训练文档集合选择是否合适， 对文本分类器的性能有较大影响。 训练文档集合应该 能够广泛地代表分类系统所要处理的、实际存在的各个文档类别中的文档。 一般地， 训 练文档集合应该是公认的、 经人工分类的语料库。 ( 2 ) 建 立 文 档表 示 模型 建立文档表示一个重要的技术问 题，它将决定 选用什么样的文档特征来表征文档。 目 前的文本分类系统， 绝大多数都是以词语来表征文档的， 至于具体形式， 则可能是关 键词或短语、主题词、概念等。当然， 不同语言的文本， 在获取文档的词语属性时， 需 要采用不同技术， 例如抽词或切分词。 鉴于中文文本信息的 特殊性， 有些中 文文本分类 系统采用了 基于统计的n - g r a m 属性，以 避开词语切分的困 扰。 ( 3 文档特征抽取 对于使用自 然语言表达的文档集合来说， 系统对于所获取的特征必须进行筛选和优化， 文档特征是开放的、 无限制的。 一个分类 从特征的全集中抽取一个最优的特征子 集。准 有如此， 才能保证分类算法的效率， ()选择或设计分 类模型 选择分类模型实际上就是要使用某种方法，建立从文档特征到文档类别的映射关 系， 是文本分类的核心问题。 现有的分类方法主要来自 两个方面:统计和机器学习。 基 于 机器学习的英文自 动分类已经取得了很好的成绩，提出了多种特征抽取方法和分类 器。 如 回归 模 型 (6)最近邻 分 类(e) 、 朴 素贝 叶 斯 分 类171 、 决 策 树171 、 支 持向 量 机(8 ) 、 规 则 学习 算 法 (s 1 、 相 关 反 馈 ( f01选 举 分 类 1 .11 、 神 经网 络 1121 、 纠 错 输出 编 码(13 1 、 最 大 嫡 ( 41 、 休 眠专 家y 1 等。国内 在中文分类领域也进行了 大量的 研究，但由 于语料和评价方法各不相 同， 很难对它们做出严格的比较。 ( 5 ) 性能评测模型 文本分类系统的建立， 需要对系统使用的分类方法或分类器进行性能评价分析， 性 能 评测是分类处理流程中的重要一环。 同时， 寻找能 够真正反映文档分类内 在特征的性 能评估模型，对改进和完善分类系统也具有指导意义。 文本的自 动分类算法的结构如图1 所示: 图 i 文本分类算法结构图 1 . 1 . 3 文本 分类的意义 对大 量文 本资料进行 管理的 方法之 一是 将它 们系统地 分类。 传统的 人工 分类过 程需 要专家 参与 指导，期间猫 要分 类人员 具有 较多的 经毅 和知识， 分类质皿 不一定 有保证， 而且周期长、费用高、效率低、不易满足实际播要，由于上述手工分类的缺点，在自动 分类发 展走 过 4 0 余年历史的 今天， 它 才其 正显示出了 迅 速、 快 掩、 有效 等手工 分类 无 可比拟的应用价值。 自 动分 类也可以 成为自 动 检索 任务的 前期 处理， 若 先对文 档进行自 动分 类， 在此 基 础 之上进 行自 动检 索将大大 加决 检索的 速度 和准确 度. 该 项技术 可以 应用 在诸多 领域， 如信 息档案 管理、 网上邮 件过滤 网 上内 容分类 定义等。 另 外， 从学术 角度上 讲，自 动 分 类基于 对文章内 容的理 解， 属 于自 然语言 理解的范 嘀。自 然 诱育理 解是一门 涉及 计算 机科学、 语言学 、 数学、 心 理学以 及社 会学 等多种 学科的 综合 性科学。自 动 分类的 研究 也将推动整个自 然语言处理领域的发展。因此是一个很有理论价值的研究课题。 2 w e b文档分类技术 2 , 1 w e b 信息的基本特点 w e b 信息是由 庞大的、 分布 在世界各 地 的资 源集合。 这些w e b 信息资 源通常以 页面 形式出 现，每一 页面 又可以 包 含指向 世界 上任 何地方的 其他 相关w e b 信息资 源的 链接， 我 们可以 跟 随一个 链接到其所 指向的 其 他w e b 页面或w e b 站 点， 并且 这一过程 可无限 次 重复，从而提供源源不尽的w e b 信息。 w e b 信息均采用超文本和超媒体的， e b页面形式来表现。1 9 6 7 年出现了一套正式的 超文 本编辑系 统， 以 后逐步形 成了 超文 本 标注 语言 ( h y p e r t e x t m a r k u p l a n g u a g e , 通 常简 称为h t m l ) . 严格来说， h t m l 不 是一门 编 程语言， 因为它 没有自己 的 数据类型， 也 没有分 支 、循环等控制结构， 只是由一系列标记构成，每个标记可以具有一个或几个控 制属性，由h t m l 语言编写的文档就是我们通常所说w e b 页面文档或网页。 一 般来说，w e b 信息具有如下基本特点: ( 1 ) 非结构化 w e b 是一个集文字、 图 像、 图 形、 声音、 视频为一体的 包罗万象的综合性信息环境。 w e b 页面是非结构化的( 或称半结构化的) ， 而w e b 页面中包含的多媒体数据更是复杂类 型的非结构化数据。 ( 2 ) 动态性 由于 i n t e r n e t的开放性，人们可以随时方便地将需要发布的信息放到网上去，同 时也可以 方便容易地删去或移动信息， 导致整个网络上的w e b 信息处于高度动态变化的 状态。据统计，工 n t e r n e t 每个月变化的信息量约占总信息的4 0 % . ( 3 ) 复杂性 就 单 个 信 息 提 供 者 来 说， 井所 提 供 的 信 息 是 按 照 一 定 的 规 划 来 组 织 的 ， 是 有 序的 。 但由于 i n t e r n e t 是完全开放的， 数以 亿计的网络使用者都可能成为信息提供者， 这样 又形成了 一个无序而复杂的信息源，因 此必 然造成整个 i n t e r n e t 上信息的无序状态和 复杂性。 1 . 2 . 2 w e b 文档分类方法概述 文 本分类 和w e b 文档分类归根到 底都 是对文本 信息的 分类， 都 存在着文本信息的 表 示， 分类信息的获取等。 正是基于这样的共性， 我们可以借鉴文本分类中的技术来处理 页面分类问 题。 但文本分类和网页分类又有所不同， 如: 网 页信息相对于文本信息更开 放， 并 且数量巨 大、 格式又非常灵活， 有h t m l , a s p , x m l 等多 种格式并 存， 风格不固 定; 网页分类的 类别比文本分类的类别更多， 为了 便于用户浏览 和选择， 一般要求类别 有层次关系; 网页的分类体系随着信息的变化会做一些变动， 并且很难有一个统一的标 准。 自 动网页分类技术跟传统的文本分类一样， 包括很多技术环节， 如特征抽取、 特征 选择、 分类算法等。 许多专家学者在这些技术上已 经开展了 大量的 研究工作。 但网页分 类与 文本分类的一个根本的区别在于两者处理对象的不同。 网页自身的特点和网页之间 的关系为网页分类提供了一些线索。 由于w e b 信息自 身的特点，网页中除了包含纯文本内容， 还包含一定的标记( t a g s ) 和许多 指向 其它页面的链接( h y p e r l i n k s ) o h t m l 标记语言 包含了 丰富的信息， , 等标记都表明了 其与众不同的信息。 超链接 ( h y p e r l i n k ) 提供了网页间内在关系 的 信息 同【 .目 ， 很明 显， 如果网 页a 指向 网 页b ， 那么网 页a 的 作 者 会认为网 页b 包含有 价值的 信息或者它们之间存在某些关系.已 经有一些分类工作涉及用超链接及h t m l结 构 来提高网 页分 类的 精确率d i dal 191 (m l 2 u n ; 一 些其他网 络资 源如查 询日 志也 为网 页分类 提供作了有利的信息。 1 . 2 . 3 特征抽取 网页包含了丰富的 信息， 合理有效的利用这些信息可以帮助分类， 相反则会降低分 类的效果. 在本文中， “ 特征抽取“ 被定义为如何从网页中抽取出有价值的特征来表示网 页， 帮助分类. f 面给出了一些可能的特征抽取方法。 ( 1 ) 用网页内的文本来表示网页 我们可以 用网 页中 所包括的纯本文来表示网 页。 所谓纯文本是指将网页中的 各种标 记去掉后所留下的文本: 或者用网页内不同域中的文本来表示网页， 这些包括网页标题 ( t i t l e ) ,网页内的小标题( h e a d i n g s ) 、元数据中的描述文本( d e s c r i p t i o n i n m e t a d a t a ) 、元数据中的关键词( k e y w o r d i n m e t a d a t a ) 。这种方法是现今比较流行的特征 抽取方法，因为它可以直接引用文本分类的一些现有方法，更加方便使用。 ( 2 ) 用网页内图 像， 音频， 视频的信息来表示网页 不同类别的网页中所包括的多媒体内容从数童到内容上都有所不同，如” 娱乐 ( e n t e r t a i n m e n t ) 类中图像、音频、视频相对于” 计算( c o m p u t i n g ) 类要丰富得多。有 人曾经针对这个特征做过一个实脸， 实验结果显示， 在分类中考虑此类特征， 分类效果 可以有 1 % 的提高。 ( 3 ) 用网页中存在的模式来表示网页 所谓模式是指特定形式的组合如“ $ 十 数字+ 、 十 数字”即是一个代表价格的模式。 如 果一 个网页中包含一些由 价格组成的表格，那么这个网页就更有可能属于 “ 购物” 类， 而不是其他类。 ( 4 ) 用网页间的链接信息来表示网页 网页之间的超链接关系是网页与其他纯文本的一个重要区别， 合理利用这些超链接 关系 对提高分类性能会有明 显帮助n)24)251。 利用超链接的 方式包括: 利用具有超链接关 系的网页的类别信息:利用具有超链关系的网页中的文本 ( 如:锚文本( a n c h o r t e x t ) , 锚文本的上下文、标题、甚至全文) 。 ( 4 ) 用网页的u r l 信息来表示网页 u r l 是万维网上网页的一个标识。具有相同u r l 前缀的网页有可能属于同一个类， 而且 这部分相同的前缀越长，他们属于同一类的可能性越大。 ( 5 ) 用网页的布局来表示网页 网页的布局是网页的一个特征之一。 在这里网页的 布局是指网页中根据不同功能划 分的模块的分布情况。 ( 6 ) 用网页的摘要来表示网页 摘要是指从一段文本中摘取出来或根据一段文本生成的能够反映这段文本主要内 容的文本。 一般来讲， 摘要能更集中的体现文本的内 容， 而且包括了 较少的噪音，因此 对于 提高分类性能应该有很大帮助。 1 . 2 . 4特征选择 根据2 . 2 中讨论的方法， 我们可以 给出网页的一种表示。目 前的表示方式卜 要是用 向量( v e c t o r ) ， 向量中的每 一 维元素被称为一个， 特征” 。 在一个数百万网页的数据集 匕 表示网页的向量的维度通常会高达数十 万甚至百万，这些特征对分类的贡献相差很大。 如果用全部特征进行分类，不但会影响分类的效率，甚至会降低分类的精度。因此，特 征选择成为 一 个不容忽视的步骤。 下面给出一些在文本/ 网页分类中可能会有效的方法。 ( 1 ) 传统的特征选择方法 传统且比较常用的特征选择方法包括文档频率( d f , d o c u m e n t f r e q u e n c y ) 、 信息增 益( i g , i n f o r m a t i o n g a i n ) 、 互信息( m i , m u t u a l i n f o r m a t i o n ) 、 卡方统计( x 2 s t a t i s t i c s ) 等e ti ( 2 ) 根据特征和类别的关联关系来进行特征选择 关联规则是数据挖掘领域一个很成熟的方向。它可以 用来找出事物之间的依赖关 系。如a - - b 表示如果a出现，那么b 也会以某种概率出现，而且这种关联关系以某种 概率成立。 这里提到的两个概率实际上是关联规则中用到的两个度量即支持度和信任 度。 据此， 我们可以从训练集中挖掘出 所有的t ( t e r m ) -c ( c a t e g o r y ) ， 并从中选出支持 度和信任度都高于特定闽值的关联规则， 这些规则的前件所形成的集合即可作为特征选 择的结果。 ( 3 ) 词聚类方法 根据特定的 方法先把特征( 词) 聚类， 然后在每一个类中 选出 一个( 些) 特征作为这个 聚类的 代表， 这样同 样可以 达到特征选择的效果。 1 . 2 . 5分类器 分类器是网页分类的核心，也是“ 分类“ 一 一 这一传统的机器学习领域的研究重点， 目 前已 经得到了 长足的发展。 现在大量的 基于统计、 规则等方法的 分类器被应用到文本 / 网 页 分 类 中 来 。 如 : v a p n i k 提 出 的 支 持 向 量 机 ( s v m ) e7) ; 在 文 本 分 类 研 究 一 开 始 就 引 起 关 注的k 近 邻( k n n ) ; y a n g 提出 的 一 种 线性 最小 二 乘 拟 合 法( l l s t ) : 决 策 树 分 类方 法d o 。 另 外， 人工神经网 络( a n n ) 和朴素贝叶斯方法( n b ) (: ) 也 被广泛 地 应用到文本分 类 中。 1 . 3 本章小结 本章主要对分类技术进行了简单的综述， 诸如对文档进行预处理、分词、 特征提取等， 总结了分类技术所包括的几个技术环节， 并分析了w e b 文档的结构特点，为w e b 文 档分类技术的产生和实现奠定了理沦基础。 本章还分析了w e b 文档分类技术中包括的几 个重要部分， 尤其详细描述了w e b 文档分类技术的特征抽取和特征选择部分。 为下文的 分类算法的分析和性质分类算法的提出提供了重要基础。 第二章 基于内容的we b 文档分类 2 . 1 内容分类的含义 内 容分类是指按照预先定义的基于内 容的主题类别c ( c = ( c ,c 2 ,， ， 讨， 理 这里的r , 可 以 是并列的， 也可以 是分层次组织起来的) ，为文档集合中的每个文档 d ; ( i = 1 , - , m ) 确定所属的类别。例如文档描述的是关于计算机学科方面的内容就把它归为计算机类， 是国际政局方面的内 容则一般归为政治类等等。 现有的w e b 文档分类技术都是基于内容 分类方面的研究。 早期文档是通过人工分类， 其过程是首先由 人类专家将它们分类， 然后以 适合的形 式存储。 本文 所讲的 文本分类是自 动文本分 类( a u t o m a t i c t e x t c l a s s i f i c a t i o n , a t c ) , 是指借助于某种控制程序，由 计算机来完成那些原来为人们熟知的人工分 类的操作过 程。 2 . 2 基干内容分类的具体算法 2 . 2 . 1 基于网页文本分类的算法 根据网页中的各种标记去掉后所留下的纯文本进行分类， 实际上就是对文档进行分 类，完全可以借鉴文本分类的算法。 从算法机制上来看， 文档分类方法大致可分为基于统计学习和基于知识工程两种类 型。 基于知识工程的文档分类系统， 例如:卡内基路透社开发的稿件自 动分类系统，需 要知识工程师手工针对具体领域或应用编制大量的推理规则， 因此较少使用。 与此相反， 统计学习方法由 于具有坚实的理论基础、 简单的实现机制和良 好的实用效果， 而为目 前 的大多数文档分类系统所采用。 这类方法的典型例子包括: k 近邻、 贝叶斯、 神经网 络、 支持向量机，以及决策树方法等。 统计学习方法的基本假设是: 文章的内容与其中的词汇有着必然的联系，同一类文 章总有很多共同的词; 相反，不同类的文章用词差异则很大。因此， 这些方法通常忽略 文档的语言学结构， 而用词条来表示文档。同时， 这些方法都要求事先给出一批带有类 别标记的训练文档， 在此基础上通过有导师的智能化学习来生成分类器， 进而对测试文 档集中的待分类文档进行分类。 下面介绍几种常用的分类方法: 1 . 最近邻分类( n e a r e s t n e i g h b o r ) 该方法是通过查询已知类似的例子的情况， 来判断新例子与已知例子是否属于同一 类。尽管近邻算法存在许多变种， 但其一般思路是: 首先存储全部或部分训练例子， 对 于 测试例子， 通过相似性函数计算它与所存储的训练例子的距离以决定类别的归属。 也 就是说，近邻学习算法在训练过程中并不产生概念描述。 on 是 近邻学习算法的一 个例子， 采用k n n 方法进行文档分类的 过程如下: 对于某一给定的测试文档d ，在训练文档集中，通过相似度找到与之最相似的k 个 训练 文档。 在此基 础上， 给每一个文 档类别打 分， 分值为k 个训 练文档中 属于 该 类的文 档与测试文档之间的相似度之和。 也就是说， 如果在这k 个文档中， 有多个文档同 属于 一个类， 则该类的分值为这些文档与测试文档之间的相似度之和。 对这k 个文档所属类 的分值统计完毕后，即按分值进行排序。 还应当 选定一个阐值， 只有分值超过闽值的 类 别才予以 考虑。 测试文档属于超过阐 值的 所有类o k n n 的决策规则可以 形式化表示为3 2 1 , s c o r e ( d , c )( d , d ; )y ( d ; , c ) 一 6 l( 2 - 1 ) 其中， y ( d , , c 1) e 0 , 1 : 如果文档d , 属于类别c , ， 则y ( d , c 1 ) = 1 : 否则y ( d ; , c ,) = = o . s i m ( d , 勾为测试文档d 到训练文档d , 之间的距离 b ， 为闽 值。 对于某一特定类来说， b ， 是一个有待优化选择的值。一般， b 。 可以通过一个验证文档集来进行调整。 k n n 分 类算 法的 优点 是 易 于 快速 实 现， 分 类效 果 好(3e) 。 同 时 它 也 存 在 一些 限 制: ( 1 ) 应存储训练例子的数量:如果存储全部例子，分类器的分类速度可能太慢且不 实用。较为理想的是存储可以概括重要信息的典型例子。 ( 2 ) 相似性度量问题:如果属性是连续的，则可以 通过欧氏 距离计算。一般情况下 应该考虑消除无关属性，不要让无关属性导致距离计算不准确。 2 . 朴 素 贝 叶 斯 分 类( n a i v e b a y e s ) 贝叶斯3 1) 3 3 ) 3 9 分类方法是一种简单而又非常有效的 分类方法。 该方法的一个前提假 设是: 在给定的文档类语境下， 文档属性是相互独立的。 假设d 为一任意文档， 它属于文档类c = i c i, c 3, . . . , c k 7中的 某一类c ; 。 根据贝 叶斯 分类法有: ，户忆 2.r2 k p (d +， 一 著 p (ci)p (d , /ci) p ( c ; / d ) 二 p ( c i ) p ( d i / c i ) p ( d i ) 对文档d 进行分类，就是按( 2 - 3 ) 式计算所有文档类在给定 值最大的那个类就是d ; 所在的类，即: d , e c j i p ( c ; / d +) 1= - a x p ( c ; l d i) i d 情况下的概率，概率 ( 2 - a ) 由( 2 - 2 ) , ( 2 - 3 ) 和( 2 - 4 ) 可知， 对于给定分类背景和测试文档， 用n b 方法分类的关 键就是计算p ( c 1 ) 和p ( d l / c l ) 。计 算p ( c ;) 和p (dl/c,) 的过程就是建立分类过程。 文档可以 看作是文档属性事件的有序序列， 假定 每个属性事件在文档中发生的 概率 与文档长度无关， 则一个文档就相当于一串符合多项式概率分布的独立试验。 而每个试 验相当于随机地从文档属性表中重复抽取一个属性， 抽取次数为该属性在文档中出 现的 次数。文档中的每一属性都对应于这样的一次独立实验。定义n , 。 为文档属性w在文档 d 。 中出 现的次数，则给定文档类别条件下文档的概率为; p (di /c ) = p (i d,。 ， .，彝 p ( w i l c j ) nd 使用l a p l a c e a n 先验概率估算，p ( w , / c , ) 可以 表示为: l + 呈 n bp (c, l di) p ( w i l c ,) 下 下 百a i v + 石 石 n y (c i l d i) ( 2 - s ) ( 2 - 6 ) 在这里，文档类别的先验概率按( 2 - 7 ) 估算: p rca _ 一 签 座 (c; /di) 一 、一 c 鬓 f n i.p (c i di) ( 2 - 乃 贝叶斯方法假设一个单词在一个分 类文档中的 发生 概率与该文档中的 其它单词无 关， 从而使得计算复杂度简单， 具有较高的