（计算机应用技术专业论文）基于knn及相关链接的中文网页分类研究.pdf

哈尔滨t 程大学硕十学何论文 摘要 随着i n t e m e t 的飞速发展，网上信息正在呈指数级增长。面对杂乱的网 页信息资源，人们需要对海量的网页信息进行分类整理，从而可以快速检索 到期望的目标及其关联信息。网页自动分类提供了处理和组织大规模网页的 关键技术，是使信息资源得以合理有效组织的重要方法。如何提高网页分类 的准确率和召回率，是研究人员不懈追求的目标。 本文通过中文网页正文提取方法，较好地提取出中文网页中的正文文本， 将网页标记的处理、噪音信息过滤和网页正文提取三个方面结合起来。网页 中的链接主要分为两类，与本页主题相关的链接称为相关链接，与本页主题 无关的链接称为无关链接，例如导航条和广告链接等等。本文提出的相关链 接提取算法，能够较好地抽取出中文网页中的相关链接，该算法时间复杂性 低，准确率和召回率都令人满意。本文基于向量空间模型，采用词频法选择 网页中的特征词，采用机器学习算法k n n 对中文网页进行分类，设计实现 了一个中文网页分类器。比较了基于网页标题分类、基于网页j 下文分类、基 于网页相关链接分类，以及将正文与相关链接结合分类、将标题与相关链接 结合分类的分类效果，印证了中文网页中相关链接对网页分类具有积极影响 的设想，同时也提出了一种分类方法。 通过开放测试，实验数据表明，本文提出的网页正文和相关链接结合分 类的方法所需的训练集较小，各个类别的分类f 1 值均在9 2 以上，比传统 的网页分类效果有了一定的提高。 关键词：中文网页分类；网页提取；相关链接；k n n ；向量空间模型 哈尔滨丁程大学硕十学位论文 i i iii_ _i a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，o n l i n ei n f o r m a t i o ni sg r o w i n g e x p o n e n t i a l l y f a c e dw i t hc l u t t e r e dw e bi n f o r m a t i o n ，w en e e dc l a s s i f yt h e s e i n f o r m a t i o n ，s ot h a tw ec a nq u i c k l yr e t r i e v et h ed e s i r e do b j e c t i v ea n dr e l e v a n t i n f o r m a t i o n t h ea u t o m a t i cw e b p a g ec l a s s i f i c a t i o np r o v i d e st h ek e yt e c h n o l o g yo f d e a l i n gw i t ht h el a r g e s c a l ew e b p a g e ，a n di t i sa ni m p o r t a n tm e t h o d st oo r g a n i z e t h ew e bi n f o r m a t i o ne f f e c t i v e l y h o wt oi m p r o v et h ep r e c i s i o na n dr e c a l lo ft h e w e b p a g ec l a s s i f i c a t i o ni sag o a lf o rt h er e s e a r c h e r st op u r s u i t b yc h i n e s ew e b p a g e t e x te x t r a c t i o nm e t h o d s ，w ee x t r a c tt h eb o d yo f c h i n e s ew e b p a g e ，a n dm a k eag o o dc o m b i n a t i o nw i t hd e a l i n gw i t ht h et a g ， g e t t i n gr i do fn o i s ea n dt e x te x t r a c t i o n l i n k si nw e b p a g ea r ed i v i d e di n t ot w o c a t e g o r i e s ，w i t ht h et h e m eo ft h i sp a g ew i t hal i n kc a l l e dr e l a t i v el i n k s ，h a s n o t h i n gt o d o w i t ht h et h e m eo ft h ep a g ec a l l e di r r e l e v a n tl i n k s ，s u c ha s n a v i g a t i o nb a r sa n da d v e r t i s i n gl i n k s ，a n d s oo n t h i st h e s i s p r o p o s e s a n a l g o r i t h mb a s e do nb l o c k i n gt h ew e b p a g e sl i n k st or e t r i e v et h er e l a t i v el i n k sw i t h g o o dp r e c i s i o n ，t h ec o m p l e x i t yo ft h ea l g o r i t h mh a st h ec h a r a c t e ro f t i m el o w ，a n d p r e c i s i o na n dr e c a l la r es a t i s f a c t o r y b a s e do nt h ev e c t o rs p a c em o d e l ，w ec h o o s e t h ef e a t u r ew o r d sw i t ht h ew o r d 行e q u e n c y ，u s em a c h i n el e a r n i n ga l g o r i t h mk n n t oc l a s s i f yt h ec h i n e s ew e b p a g e ，d e s i g na n di m p l e m e n tac h i n e s ew e b p a g e c l a s s i f i c a t i o ns y s t e m w ec o m p a r e dt h er e s u k so fc l a s s i f i c a t i o nb a s e do nt h et i t l e ， c l a s s i f i c a t i o nb a s e do nt e x tc l a s s i f i c a t i o n ，c l a s s i f i c a t i o nb a s e do nr e l a t i v el i n k s ，a s w e l la st e x ta n dr e l a t i v el i n k sc l a s s i f i c a t i o nt o g e t h e r ，t i t l ea n dr e l a t i v el i n k s c l a s s i f i c a t i o n t o g e t h e r i t i st r u et h a tt h er e l a t i v ei i n k si sh e l p f u lt ot h e c l a s s i f i c a t i o no fw e b p a g e ，a n dw ep r o p o s eac l a s s i f i c a t i o nm e t h o dm e a n w h i l e t h r o u g ht h eo p e nt e s t s ，t h ee x p e r i m e n t a ld a t as h o wt h a tt h ea p p r o a c ho fb o d y o ft h ew e b p 马g ea n dr e l a t i v el i n k sc l a s s i f i c a t i o nt o g e t h e rn e e d ss m a l lt r a i n i n gs e t ， 哈尔滨工程大学硕+ 学位论文 t h ef1v a l u eo ft h ev a r i o u sc a t e g o r i e sa r ea l lm o r et h a n9 2p e r c e n t ，i ti sb e t t e r t h a nt h et r a d i t i o n a lw e b p a g ec l a s s i f i c a t i o na p p r o a c h e s k e yw o rd s ：c h i n e s ew e b p a g e sc l a s s i f i c a t i o mw e b p a g et h e m ee x t r a c t i o n ； r e l a t i v eh y p e r l i n k s ；kn e a r e s tn e i g h b o r ：v e c t o rs p a c em o d e l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：金二室 日期：刀口乎年z 月) 7 日 哈尔滨工程大学硕十学位论文 第1 章绪论 1 1 研究的背景及意义 随着i n t e m e t 的飞速发展，网上信息正在呈指数级增长。仅就中国而言， 截至2 0 0 7 年6 月，中国网站数量已经达到1 3 1 万个，半年内增加了4 7 万个， 比2 0 0 6 年同期增加了5 2 万个，增长非常迅速u 。面对杂乱的网页信息资源，人 们无法在其中准确、充分、快速地获取有用的信息，往往花费了很多时间却所 获甚少，形成了“r i c hd a t a , p o o ri n f o r m a t i o n 的现状。因此我们需要对海量的网 页信息进行分类整理，从而可以快速检索到期望的目标及其关联信息。网页自 动分类提供了处理和组织大规模网页的关键技术，是使信息资源得以合理有效 组织的重要方法，在数字图书馆、主题搜索、个性化信息检索、搜索引擎的目 录导航、信息过滤等领域得到了广泛的应用恻。网上信息的分类目录组织可以 提供信息的良好组织结构，各种信息按照不同类别加以组织存放和标识可以提 高检索效率和检索精度，如在利用搜索引擎对网页数据进行检索时，若能提供 查询的类别信息，必然会缩小与限制检索范围，从而提高查准率，更加便于用 户快速准确地查找信息。 中文网页相对于英文网页有许多不同的特点和处理难点。例如中文文本的 词与词之间没有空格分隔，使得分词难以处理；又如中文的字符数目众多，仅 常用的汉字就大约在6 0 0 0 至8 0 0 0 左右，其数目远远超过了英文字母，处理起 来难度增大了很多”1 。以中文网页为对象进行分类技术研究，是近些年的研究 热点，其中，如何提高中文网页分类的分类准确率，一直都是科研人员重点研 究和追求的。 中文网页中除了网页文本外，还有大量的超链接。其中，与网页内容相关的 超链接中含有重要的分类信息。因此，充分利用相关超链接信息对中文网页分类 将具有积极的意义。本课题基于机器学习算法k n n ( k 最近邻) ，根据中文网页训 练集对测试网页进行分类。在分类时考虑中文网页中所含相关超链接信息对分类 的帮助，将网页中的正文分类结果与网页中相关链接的分类结果综合考虑，以提 哈尔滨丁程大学硕士学位论文 高中文网页分类的查准率和查全率。由于目前对中文网页分类的研究多是基于网 页正文进行的，也有完全基于网页相关超链接进行的h “，但较少有将二者结合起 来进行中文网页分类，本课题尝试综合应用二者进行分类，研究出提高中文网页 分类准确率和召回率的新方法。就目前的研究来看，中文网页自动分类的准确率 还不高，所以，本课题的研究若能提高中文网页的分类准确率，就将是一项有应 用价值和现实意义的工作。本文的研究结果表明，将中文网页正文分类和相关链 接分类结合起来进行分类的方法是可行的，而且与传统的网页文本分类方法相 比，较大地提高了准确率和召回率。 1 2 网页分类和超链接分析方面的国内外研究现状 1 2 1 网页分类的发展与研究现状 网页分类的基础是文本自动分类。文本分类研究始于5 0 年代末，h pl u h n 在 这一领域进行了开创性的研究。1 9 6 0 年，m a r o n 在j a c m 上发表了有关自动分类的 第一篇题为“o nr e l e v a n c ep r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ”的论文， 随后许多著名的情报学家，如k s p a r c l l ，g s a l t o n 以及r m n e e d h a m 等都在这一领 域进行了卓有成效的研究。 到目前为止，文本自动分类在国外经历了三个发展阶段：第一阶段 ( 1 9 5 8 1 9 6 4 ) 主要进行自动分类的可行性研究；第二阶段( 1 9 6 5 1 9 7 4 ) 进行自 动分类的实验研究；第三阶段( 1 9 7 5 至今) 进入实用化阶段。 文本自动分类的方法分为两大类：一是基于规则的分类方法；二是基于统计 的分类方法。基于规则的分类方法多应用于某一具体领域，需要该领域的知识和 规则库作为支撑。但是，对知识和规则的制定、更新、维护以及自我学习等方面 存在种种问题，使得应用面比较窄。基于统计的分类方法是现在普遍使用的方法。 在准备输入学习机器的向量时会结合到自然语言处理的方法，把文本表示成向 量。这是机器学习和自然语言处理结合的一个很好的应用。在这个方法体系下， 把文本分类的任务分为两个步骤来完成：第一步是文本的处理，把文本表示成下 一步进行分类计算所需要的向量形式；第二步是对这些代表文本的向量进行分 类。这是一个典型的模式识别问题，可以采用多种机器学习的方法处理这个问题。 基于统计的方法采用纯粹的数学运算，不苛求复杂的语言学知识和领域知识，同 2 哈尔滨工程大学硕十学位论文 时具有较高的准确率，因而日益受到人们的重视。 文本自动分类的统计模型主要有向量空间模型、概率模型、线性模型以及非 线性模型等。 在向量空间模型中，一种方法是计算文本与代表某一文本类别的中心向量之 间的相似度，如r o c c h i o 公式m ，。另一种方法不需要建立描述文本类别的中心向量， 而是依赖于测试文本与训练文本之间的相似度，如、j n 算法。概率模型中典型 的算法是朴素贝叶斯算法“。线性模型有支持向量机n ”。非线性模型可以分为层次 模型和网络模型，如决策树和神经网络n 甜。 我国的文本自动分类工作始于8 0 年代初期，大体上经历了从可行性探讨辅 助分类系统一自动分类系统三个发展阶段。对中文文本进行自动分类，需要首先 分词。中文分词系统在上个世纪九十年代就有人在研究。现在比较成熟的分词系 统有中科院的i c t c l 峪、哈尔滨工业大学信息检索研究室的分词系统、海量智能 计算技术研究中心的中文智能分词系统等。其中海量分词系统准确率可达到 9 9 6 以上，切分速度为3 3 3 万字秒。早期的文本分类系统主要特点是结合主题 词表进行分析分类，人工干预的成分很大，如南京大学开发的系统，分类准确率 在8 0 左右，上海交通大学开发的系统，准确率为8 9 ；此后，基于统计学的思 想，以及分词、语料库等技术被不断应用到分类中。刘少辉等利用向量空间模 型进行层次分类，准确率达到9 0 以上；孙丽华i - ”等提出了将规则作为自动分类 的补充，针对不同的情况，采用不同的分类器进行分类，准确率也达到9 0 左右； 周水庚“6 提出了一种领域独立的、时间无关性的、可扩展性强的无需分词和词典 支持的分类系统n g r a m ，准确率也达到9 0 以上；樊兴华n 7 】等提出了一种高性能 的两类中文文本分类方法，准确率高达9 7 ；还有神经网络在分类中的应用等等。 这些都是近年研究的新发展，并且都取得了很不错的分类效果。 网页自动分类研究自上世纪8 0 年代互联网兴起以后才逐渐发展。由于文本自 动分类的研究相对较早，而且拥有比较成熟的技术，因此有不少研究工作试图使 用纯文本分类技术实现网页分类。f u m k r a n z 用指向该网页所有链接周围的文本、 链接所在段落的标题以及上级标题文本表示网页，并用r i p p e r 算法对文本进行分 类，准确率比使用网页局部文本提高了2 0 ”。，；o h 等人结合网页局部文本和链接 网页的文本表示网页，但没有引入所有链接网页的文本，而是基于文本相似性选 择了部分跟原网页较接近的网页文本，试验结果f 1 值比使用所有链接网页提高了 3 哈尔滨工程大学硕士学位论文 7 m 1 。y a n g 构造了一个专家网络，其分类效果也比较理想m 一。 在中文网页分类上，香港和台湾的起步较早，水平相对要高一些，国内在这 个方面起步较晚，基本上还处于跟踪研究的地步。国外主要的研究单位如c m u 、 斯坦福等，在理论研究上有很高的水平。国内主要的研究单位有北大、复旦大学、 哈工大、中科院计算所等，北大s e w m ( s e r c he n g i n ea n dw e bm i n e ) 小组每年组 织一次中文网页分类比赛，对中文网页分类技术起到推进作用。上海交通大学的 韩客松等对从w 曲页面中自动提取其文本主题的研究嘲，、南京大学的王继成、潘 金贵等研究的基于w e b 的文本挖掘技术研究等也是一些有代表性的相关研究成 果。 用组合网页分类器的方法进行网页分类，是近期应用较多的方法。例如北京 大学的税敏等将k n n 分类与s v m 分类结合起来，分类准确率提高了大约7 。试 验结果证明组合后的分类器性能都有一定程度的提高。 1 2 2 超链接的研究现状 超链接是从文本或图像指向互联网上其他页面或文件的一种指针，它是在网 页或站点之间导航的基本方法。常用的超链接有文本和图像超链接。当用户点击 超链接到某一页面的超链接时，w e b 浏览器读取相应的w e b 服务器上的页面并且 显示它，如果超链接的目标是其它类型的文件，则浏览器会提示用相应的程序打 开它。超链接技术用于实现w e b 站点的页面之间或者页面内部的链接，还可以完 成基于数据库访问的动态画面间的高级链接。w w w 采用超文本技术将信息资源 连接成一个信息网，信息网由节点和超链接组成。w w w 的结构不同于文件系统 的线型结构，w w w 中的节点的链接关系是相互交叉的网状结构，可以以各种方 式与另外的节点相链接。 随着对网络信息研究的深入，超链接分析已经成为该领域的热点之一，例如 华盛顿大学的s o u m e nc h a k r a b a r t i n 用超链接信息提高超文本分类技术的研究旧一。 目前来讲，对链接信息的研究大部分都致力于对超链接的拓扑结构的研究，如著 名的p a g e r a n k 算法及k l e i n b e r g 提出的h i t s 算法。为了获取更高的查准率，国 内华中科技大学的王天江等提出了s w m t s 算法等等例。还有一些学者也已经开 始着重研究如何利用链接文本和上下文信息，例如国内清华大学的张敏等提出的 “基于链接描述文本及其上下文的w e b 信息检索方法，哈工大的陈丽等提出 4 哈尔滨工程大学硕士学位论文 jmmmilm 的“基于文本内容的超链接分类”方法等等旧，。 1 3 本论文的工作及论文结构 在已有的中文网页分类的研究中，多数是基于中文网页的正文进行分类， 分类准确率一般在7 0 - - 0 0 之间。为了提高中文网页分类效果，本文拟在以下 几个方面开展研究： ( 1 ) 研究分析中文网页分类的各个环节的相关知识以及分类算法。比较三 种互联网信息描述语言的特点，指出不同文本表示模型的优缺点和分类算法的 优缺点。介绍了评价网页分类的评价体系。 ( 2 ) 提出了一种中文网页正文提取算法，将正文提取与去噪结合起来。提 出一种中文网页相关链接提取算法，在准确率、召回率以及算法的复杂性等方 面都比较理想。 ( 3 ) 在分类算法k n n 的基础上将网页正文分类与网页中相关链接分类结 合起来，提出了种新的中文网页分类方法，并设计了一个中文网页分类的原 型系统对分类效果进行评测。 ( 4 ) 设计了五组中文网页分类实验，对网页正文分类与网页中相关链接分 类结合进行分类的新方法进行测试并与传统网页分类方法进行比较。实验数据 表明，网页正文结合网页相关链接进行分类的方法较大幅度地提高了中文网页 分类的准确率和召回率，达到了预期的设想。 论文组织结构内容如下： 第1 章绪论简要介绍课题研究的背景及意义、网页分类的发展史、国内 外研究现状和网页超链接分析的研究与现状。 第2 章网页分类技术研究主要介绍了网页分类各个环节的主要知识和相 关算法，并对其中的数据模型和分类算法进行了比较。 第3 章中文网页内容的提取算法研究主要介绍了我们提出的中文网页正 文、标题、相关链接的提取方法并给出了相关链接提取算法的测试结果。 第4 章基于k n n 的组合分类算法研究主要介绍基于k n n 分类算法构造 的组合分类算法，以及中文网页分类器的设计与实现。 第5 章中文网页分类实验设置与结果分析主要介绍实验数据、实验设置、 实验的结果与分析。 5 哈尔滨工程大学硕+ 学位论文 第2 章网页分类技术研究 网页是由互联网信息描述语言编写的，网页分类的核心技术是文本自动分 类，下面首先介绍三种互联网信息描述语言，然后围绕文本分类介绍中文网页 分类的基础理论及相关技术。 2 1 互联网信息描述语言 互联网信息描述语言主要有s g m l 、h t m l 、x m l 三种。目前大多数网页 都是以h t m l 标记语言来描述的，本文研究的中文网页均属于采用h t m l 标 记语言生成的网页。本节将简要介绍一下s g m l 、 i n ，、x m l 这三种标记性 语言“，并把重点放在h t m l 标记语言的分析上。 2 1 1s g m l 标记语言 s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，通用标准标记语言) 作为 国际标准( i s 0 8 8 7 9 ) ，于1 9 8 6 年首次公布。它利用通用方式和元标识语言对 电子文件的结构和内容进行标记，实现各类文献结构和内容的系统化标准化描 述，从而建立起通用数字化文献。s g m l 文献由s g m l 前言和s g m l 实例组 成，其中s g m l 前言包括s g m l 陈述和文献类型定义。s g m l 有很多优点， 比如说，它可以创建自己习惯的标识语言；能将各种结构化文献译成密码，并 且不依附于任何专有的硬件或软件；能在不同系统之间处理文献等等。但是， 由于s g m l 标记语言极其精密和复杂，编程实现难度大，所以没有被广泛地应 用，现在只用于网上传递。 2 1 2h t m l 标记语言 h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本链接标记语言) 是网上权威的 基于s g m l 语法的语言，它采用了标头、标尾和属性定义，是s g m l 的一个子 集。h t m l 的长处是简单、统一，具有可操作性。它的概念和执行都很简单， 命令和命令类型都较少，在任何计算机上都可以理解。h t m l 是由d t d 通过在 纯文本文件中加上标签( t a g ) ，使其在被浏览时以一定格式显示文件的内容。 6 哈尔滨工程大学硕士学位论文 除此之外，h t m l 提供了链接的定义。通过将链接指向声音、图像甚至动画， 使多媒体用户置身于栩栩如生的虚拟环境中；通过将链接指向其它机器上的网 页，可以使用户实现网上冲浪。h t m l 较之其它的程序设计语言简单易学并可 在许多不同的平台上运行。它的源文件生成器可以是所见即所得的基本h t m l 编辑器。h t m l 源程序由普通文字和标签组成。其中，标签是非字符敏感型， 它被用来定义网页的显示方式、链接方式，是h t m l 的主要成份。h t m l 的 标签大致可分为以下几类：基本结构标签、链接标签、列表标签、字属性标签、 水平线标签、表标签以及块标签、表格标签、帧标签。 h t m l 页面由三个部分组成：网页正文、网页所含的超文本标记和网页间 的超链接。超文本是一种半结构化的数据，它是由标记起始符、所标记的内容、 标记结束符等标记构成，在标记起始符中含有标记元素的属性。例如删，网 页源代码中用 和 标记来给出网页的标题，用 和 标记来表示一个超链接等等。利用这些标记，我们可以提取出相关内容， 其中有三项内容是本文最为关注的： ( 1 ) 标题：即在实际浏览的时候它会出现在浏览器界面最上方的标题栏中。 标题中的内容与网页主题的关系非常密切，起着概括全篇的重要作用。根据相 关资料显示的统计结果，对2 0 0 0 多网页的实际统计中，如果标题中出现了与某 个主题相关的关键词，则其主要内容与该主题也相关的网页达到了全部网页的 9 7 8 9 6 ，由此可见标题的重要作用。 ( 2 ) 链接：链接元素用来描述两个文档或者文档和u r l 之间的关系。整个 w o r l dw i d ew e b 世界就是通过这样的链接连起来的一张网。通常，一个页面上 的一些链接所指向的页面都是和本页内容有一定关系的。 ( 3 ) 网页的正文部分：除了少数的专业网站外，大部分主要用自然语言书 写。正文是对标题的具体内容的进一步阐述，信息内容也非常丰富，是网页分 类重点研究的部分。 2 1 3x m l 标记语言 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展标记语言) 是一种新兴的标记 语言，是s g m l 的一个应用文档或限制格式，本身不仅仅是一个标记语言，而 且也是一个元语言，允许用户设计自己的标记语言。x m l 是一个基于s g m l 7 哈尔滨r 1 = 程大学硕十学位论文 lm 上的简单的、灵活的文本格式，是s g m l 简化了的子集。它不仅继承了一些 s g m l 的特征，而且还增加了比s g m l 本身功能更新更强的特点。x m l 设计 的目标是：使得在w e b 上使用s g m l 更加容易直接，即易于定义文件类型； 易于创建和管理s g m l 文件：易于在w e b 之间传递和共享。为了更广泛地用 于网络和作为数据内部交换格式，x m l 被简化了，使之更容易使用。 2 2 文本分类的基本概念及特点 2 2 1 文本分类的基本概念 文本分类是指按照预先定义的分类体系，根据文本的内容自动地将文本集 合的每个文本归入某个类别，系统的输入是需要进行分类处理的大量文本，而 系统的输出是己标好类的文本集。简单地说，文本分类就是对文本标以合适的 类标签。 下面给出文本分类的形式化定义：文本分类就是将一个二元组( d i ，c i ) ed c 映射到一个布尔值的任务旧，。该映射用数学公式表示如下： 西：d x c 一 t ，f ) ，其中d = ( d l d 2 ，d f i ) ，c = ( c l ，c 2 ，c m ) 这里d 为待分类的文本集合，c 为给定分类体系下所有预先定义的类别的集 合，d 可以是无限集合，而c 必须是有限集合。如果将二元组( d i ，q ) 映射为值 t ( t r u e ) ，则认为文本d i 属于类别q ，否则认为文本d i 不属于类别q 。 文本分类的关键就是要找到一个函数：d c - - t ，f ) ，使得通过该函数能够 将任意一个文本尽可能准确地分类。这里是根据已掌握的每类若干样本的信息， 总结出分类的规律而建立的判别公式和判别规则。根据系统使用的学习方法的不 同，这些判别公式和判别规则也有所不同。在己经确定的映射规则的基础上，系 统在遇到新文本时，通过计算和判断，最终确定文本相关的类别。因而，从数学 角度看，可以说文本分类就是一个映射过程，它将未标明类别的文本映射到分类 体系下已有的类别中。 2 2 2 文本分类的特点 文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以应用到 文本分类中。但是，文本分类同时又是模式分类和自然语言处理的一个交叉学科， r 哈尔滨t 程大学硕士学位论文 是和文本的语义紧密相关的，所以与普通的模式分类任务相比有许多独特之处“。 ( 1 ) 高维特征空间 在文本特征提取的时候，存在大量的候选特征。如果使用词语作为文本特征， 即使一个1 0 0 0 篇左右的训练文本集，一般也会产生上万的候选特征。 ( 2 ) 特征语义相关 一种避免特征维数过大的解决方法是，假设大部分特征之间是相互独立的， 使用特征选择方法选取那些彼此无关的特征但是，文本分类中很少特征之闻是 彼此无关的。很多特征与上下文之间存在较强的关联性。 ( 3 ) 特征存在多义和同义现象 文本分类中一般使用词、短语和咐g r a m 等作为表征语义的文本特征。但是， 这些特征往往无法清晰地表达一种含义。一个特征可能有多种含义，即多义现象。 如：“教授”既可以表示一种职称的含义，也可以代表一种传授知识的含义o 同 时，许多相同的含义又可以用不同的特征来描述，即同义现象。如：“计算机” 和“电脑”这两个特征都表示相同的含义。 ( 4 ) 特征分布稀疏 对于一篇不是很长的文本来说，特征空间中多数特征词的出现频率都为0 ， 导致文本向量中多数特征值都为0 ，特征的分布非常稀疏。 相对于纯文本，网页中含有丰富的信息元素，更增加了网页处理的难度。 2 3 文本表示模型 文本表示所采用的模型有很多种，目前通常采用的有布尔模型、概率模型 和向量空间模型。 2 3 1布尔模型 布尔模型就是采用布尔表达式对文本进行表示。布尔模型在传统的信息检索 中有着广泛的应用，它通过与用户给出的检索式进行逻辑比较来检索文本，是一 种基于关键词的匹配。在标准的布尔模型中，文本采用如下的表达形式： d i ( 、i l ，w i 2 ，w i k , ，、，k = 1 ，2 ，n 其中n 为特征项的个数，w i k 为o 或1 ，表示第k 个特征项在文本i 中是否出现。 布尔模型易于实现，但在文本分类领域，它的准确率和召回率较差。 o 哈尔滨丁程大学硕士学位论文 2 3 2 概率模型 概率模型考虑词与词的相关性，把文本集内的文本分为相关文本和无关文 本。以数学理论中的概率论为原理，通过赋予特征词某种概率值来表示这些词在 相关文本和无关文本之间出现的概率，然后计算文本间相关的概率，系统据此概 率作出决策。 概率模型有多种形式，常见的一种是贝叶斯概率模型。贝叶斯概率模型是用 概率架构来表示特征项，将训练实例分解为特征向量和决策类别变量。该模型假 定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作 用于决策变量。尽管这个假定在一定程度上限制了贝叶斯模型的适用范围，然而 在实际应用中，以指数级降低了贝叶斯网络构建的复杂性。在很多领域即使违背 这种假定的条件下，贝叶斯概率模型也表现出相当的健壮性和高效性，己经成功 地应用到分类、聚类中。 2 3 3 向量空间模型 向量空间模型是最简便有效的文本信息表示模型之一一，。向量空间模型是 s a l t o n 等人于6 0 年代末首先提出的，并在著名的s m a r t ( s y s t e mf o rt 1 1 e m a n i p u l a t i o na n dr e t r i e v a lo f t e x t ) 系统得到成功的应用，从此以后，该模型及 其相关技术，包括项的选择、加权策略，以及采用相关反馈进行优化查询等在 文本分类、自动索引、信息检索等许多领域得到广泛的应用。特别是随着网上 信息的迅速膨胀，还被广泛地应用到搜索引擎、个人信息代理、网上新闻发布 等信息索引领域新的应用中，并且取得了较好的效果。 首先对v s m 用到的基本概念作一下说明： 文档( d o c u m e n t ) ：泛指一般的文本或者文本中的片段( 段落、句群或句 子) ，一般指一篇文章。尽管文档可以是多媒体对象，但是以下讨论中我们只认 为是文本对象，并对文本与文档不加以区别，并且认为网页是基于w e b 的文本。 项( t e r m ) ：文本的内容特征常常用它所含有的基本语言单位( 字、词、 词语或短语等) 来表示，这些基本的语言单位被统称为文本的项，即文本可以 用项集( t e r ml i s t ) 表示为d ( t l , t 2 ，a ，t n ) ，其中t l c 是项，1 k n 。 项的权重( t e r mw e i g h t ) ：对于含有n 个项的文本d ( t l , t 2 ，轧轴) ，项t i ( 1 0 哈尔滨 _ 程大学硕士学位论文 常被赋予一定的权重w k ，表示它们在文本d 中的重要程度，即 d = d o i ，w l ；t 2 ，w 2 ； ，w k ；t s ，w n ) ，简记为d ：d i ，w 2 ，w k ，w n ) 。这时 我们说项k 的权重为w k ，l k n 。 基于以上概念，v s m 的具体定义如下：给定一个文本 d = d ( h ，w l ；t 2 ，w 2 ；氪，w k ；t n ，w n ) ，由于t l ( 在文档中既可以重复出现又应该有 先后顺序，分析起来仍有一定的难度。为了简化分析，可以暂不考虑k 在文档 中的先后顺序并要求t l ( 互异。这时，可以把t l & ， ，t n 看成一个n 维的坐标 系，而w i ，w 2 ，w k ，w n 为相应的坐标值，因而d = d ( w i ，w 2 ，w k ，w n ) 被看成是n 维空间中的一个向量。我们称d = d ( w l ，w j ，w k ，w n ) 为文本d 的向量表示或向量空间模型。如图2 1 中的d l ，d 2 所示。 ) 图2 1 文档的向量空间模型 利用v s m 可以计算两个文本的相似度( s i m i l a r i t y ) ：两个文本d l 和d 2 之 间的( 内容) 相关程度( d e g r e eo f r e l e v a n c e ) 常常用它们之间的相似度s i m f d l ，d 2 ) 来度量。当文本被表示为向量空间模型时，我们可以借助于向量之间的某种距 离来表示文本间的相似度，常用向量之间的内积进行计算，即式( 2 1 ) 所示： & 朋( d l ，d ：) = 。木( 2 1 ) k = i 或者用夹角余弦值来表示为式( 2 - 2 ) ： 哈尔滨 _ 程大学硕士学位论文 s i m ( d l ，d 2 ) = c o s o = 。 k = 1 否n 暇t 2 荟n t 2 ( 2 - 2 ) 向量空间模型的最大优点在于它在知识表示方法上的巨大优势。在该模型 中，把文档内容简化为特征项及其权重的向量表示，即文本内容被形式化为多 维空间中的一个点，通过向量的形式给出，把对文本内容的处理简化为向量空 间中的向量运算，使问题的复杂性大为降低。而权重的计算既可以用规则的方 法手工完成，又可以通过统计的办法自动完成，便于融合统计和规则两种方法 的优点。也正是因为把文本以向量的形式定义到实数域中，才使得模式识别和 其他领域中的各种成熟的计算方法得以应用，极大提高了自然语言文本的可计 算性和可操作性。所以说，文本的形式化表示方法一向量空间模型是基于文 本处理的各种应用得以实现的基础和前提。 向量空间模型是一种不考虑特征项出现顺序的词袋( b a go f w o r d s ) 文本表 示模型，这种模型虽然带来了计算和操作上的方便，但是却损失了大量的文本 结构信息。而这些信息在自然语言中是至关重要的( 如句子中词序信息等) 。另 外，在权重和相似度的计算中也做了许多简化工作：一是对不同的语言单位构 成的特征项大都只考虑其统计信息并采用统一的权重计算方法，而这种计算只 是经验公式并没有很好的理论基础，所以计算出的权重未必能真实反映各项的 重要性。二是向量空间模型是建立在所有项两两正交这一假设基础之上的( 即 w 矿w f 0 ，当k t 时) ，没有考虑特征项之间的相关性，这显然是不太合理的。 对于自然语言这种有着非常丰富语言现象的研究对象来说，这种假设显然是过 于严格的，不能很好地反映自然语言的特征。目前己经有许多改进项权重计算 的方法，但是效果并不明显，原因在于语义关系实际上是一个很复杂的运算， 采用简单的初等运算代替它，误差势必存在。 2 4 汉语分词 汉语分词是是汉语自然语言理解、机器翻译、电于词典等信息处理中的基础 性工作，己成为众多中文信息处理任务的一项基础共性的研究课题。中文分词是 1 2 哈尔滨丁程大学硕士学位论文 mmmm 使用自然语言处理的各种应用系统几乎都会使用到的基本模块。所谓分词，就是 把一句话，一篇文档甚至一部著作中的词逐个切分出来，中文不象英文那样有自 然切分标志，且词长短不一，词的定义也不统一，造成切分的多样性，这自然会 给自动分词的统性带来很大因难。中文中词本身的字、词、词组无明显的区分 界限，没有一个统一的标准，许多东西都是靠经验和语感来划分。这项工作如果 全部交给计算机来做，就没有那么简单了。 汉语分词一般分为基于词典的分词方法和无词典的分词方法。 基于词典的分词方法大多数是以机械分词为基础，同时引入语法知识和 规则降低分词歧义。常见的机械分词方法有正向最大匹配法( m m 法) 和逆向最 大匹配法( r m m 法) 等。正向最大匹配法是最早提出的自动分词方法，它的基 本思想是先取一句话的前六个字查词典，若不是个词，则删除六个字的最后 一个字再查，这样一直查下去，直到找到一个词为止。对句子剩余部分重复此 工作，直到把所有的词都分出为止。逆向最大匹配法和正向最大匹配法基本上 一样，不同的是它是从句子的最后六个字开始的，每次匹配不成功时去掉汉字 串中最前面的一个字。两法思路清晰，易于计算机实现。机械分词的质量和速 度由分词方法本身以及词典的组织结构所决定。词典分词是建立在词典完备的 理想假设下，但是语言中的词汇是一个动态的开放的集合，任何常用词典和专 业词典都不可能涵盖所有词汇。因此词典分词法难以克服的最大问题是词典的 不完备性。目前词典分词法的应用主要局限在受限领域。对于非受限领域、实 时性要求高的应用，词典分词法存在很多尚待解决的难题，例如处理切分歧义 等。尽管如此，由于词典分词方法比较成熟，且在受限领域内有较好的分词准 确率，因此大部分中文文本分词仍然采用词典分词法。目前歧义切分问题与未 登录词识别问题仍然是影响分词准确率的主要因素，也是学者们研究的热点问 题。 无词典分词法不依赖词典，通过统计学习方法对文本进行分词，难点是词条 的发现。目前比较常见的方法是根据汉字结合的频率来判断汉字组合是否属于一 个词条。由于汉字的结合具有很多偶然性的因素，而且通过词频来判定汉字结合 是否属于一个词条，显然会遗漏掉大量低频词，导致查全率大大降低，因此对于 机器翻译这类位置敏感性应用来说，这种方法几乎是不可用的。目前无词典分词 方法主要作为词典分词方法的一种辅助方法存在。然而如果对于不关心词条位置 1 3 哈尔滨t 程大学硕士学位论文 的词条频度敏感应用，采用无词典分词法显然优于基于词典的分词方法。 2 5 文本特征选择及权值计算 特征表示是指以一定特征项( g a 词条或描述) 来代表文档，在文本分类时只需 对这些特征项进行处理，从而实现对非结构化的文本的处理，这是一个非结构化 向结构化转化的处理步骤。在基于文本的分类中，一般认为某个词在某个文本 类别中出现的频次较高，而在其他类别中不经常出现，就说明该词对该文本类别 的识别有较大的贡献。由于在分类问题中，文本集合的特征( 索引项) 的维数都很 高，通常达到几万维。对于n 维的空间向量，仅仅按照特征出现与否，其各维特 征的组合就有2 “种，其计算量是非常巨大的。此外，由于一些噪声特征的存在， 会导致分类性能的下降。因此需要进行特征选择，剔除无用的和分类参考价值较 小的特征，以达到降低特征空间维数和减小计算复杂度的目的。 在特征选择时，通常的做法是根据在训练数据集合上统计得到的特征分布 情况，采用一些权值计算方法对各维特征进行加权处理，从中选择权值较高的 一些特征，来实现特征的选择和降维。常用的特征选择方法包括文档频率 ( d o c u m e n tf r e q u e n e y , d f ) ，信息增益( i n f o r m a t i o ng a i n , i g ) 、互信息( m u t u a l i n f o r m a t i o n , m i ) 、t f - i d f 等等。在中文网页数据集中测试的结果是d f 、i g 性 能大体相当，明显优于m p ，而且，d f 具有算法简单、质量高的优点，可以 用来代替i g 。t f i d f 虽然是一种经验公式，没有坚实的理论基础。但是，多 年