（教育技术学专业论文）基础教育搜索引擎中的网页文档特征提取研究.pdf

摘要 i n t e m e t 的快速发展使得网络上基础教育资源数量快速增长，越来越多的人开始利用互 联网进行学习，搜索引擎已成为获取教育资源的一条重要渠道。为了向用户提供更有效的教 育信息，提高搜索的准确性，需要对海量的网页进行自动分类处理，而自动分类的前提又在 于网页的特征提取。本文围绕网页文档特征提取展开，对其中包含的若干关键问题进行了系 统研究。 前一部分简要介绍了本文的研究背景并对与特征提取相关的文档表示理论、自动分类技 术等进行了概述：后一部分重点研究了针对网页文档的特征提取方法：首先阐述了网页文档 标记预处理及中文分词的方法，接着构建了一个基础教育文档集，并在此基础上对特征提取 所包含的特征选择和权重计算两部分做了重点探索，其中，特征选择部分比较研究了文档频 率、信息增益、期望交叉熵、互信息、z 统计、文本证据权等算法，在分析实验结果的基 础上提出了增加词频因子尸f 一的改进型互信息算法，实验证明，改进型互信息算法要明显 优于原来的互信息算法；权重计算部分比较研究了t f i d f 以及其他六种基于熵函数的算法， 得出了在基础教育资源分类体系下，t f i d f 算法要优于其他算法的结论，晟后本文还设计开 发了一个包含上述特征选择和权重计算算法的网页特征提取系统，并投入到了基础教育搜索 引擎的实际应用中。 关键词：基础教育资源搜索引擎，特征选择，改进型互信息，权重计算 l i i a b s t r a c t t h ef a s td e v e l o p m e n to fi n t e r n e ti n c r e a s e ss i g n i f i c a n t l yt h en u m b e ro fb a s i ce d u c a t i o n a l r e s o u r c e si nw e b s m o r ea n dm o r ep e o p l ea r eu s i n gi n t e r n e tt os t u d ya n ds e a r c he n g i n eh a sb e e n p l a y i n gap i v o t a lr o l ei na c q u i r i n ge d u c a t i o n a lr e s o u r c e sa u t o m a t i cs o r t i n go fl a r g en u m b e ro f w e b si sd e s i r e di no r d e rt op r o v i d eu s e r sw i t hm o r ee f f e c t i v ee d u c a t i o n a ld a t aa n di n c r e a s i n g p r e c i s e i ns e a r c h m e a n w h i l e ，a u t o m a t i cs o r t i n gr e s t so nf e a t u r ed i s t i l l a t i o n t h i sa r t i c l ei s d e v e l o p e da c c o r d i n gt ow e b p a g ef e a t u r ed i s t i l l a t i o na n ds e v e r a lk e yp r o b l e m si n v o l v e da r e d i s c u s s e ds y s t e m i c a l l y m o r ed e t a i l so f t h ef i r s tp a r ta r ea b o u tt h eb a c k g r o u n do f t h es t u d y , a n ds a ys o m e t h i n ga b o u t t h ec o r r e l a t i v ed o c u m e n tf o rt h ef e a t u r es e l e c t i o no ft h et h e o r y , a n da u t o m a t ec l a s s i f i c a t i o ni n s u m m a r y f o rt h es e c o n dp a r t ，w ep a ym o r ea t t e n t i o no nt h ef e a t u r es e l e c t i o no ft h ew e b d o c u m e n t s ：f i r s to f a l l ，w ee x p a t i a t et h es i g np r e t r e a t m e n to f t h ew e bd o c u m e n ta n de x p a t i a t et h e m e t h o do f w o r ds e g m e n t ，a f t e rt h a t ，w eb u i l dad o c u m e n tc o l l e c t i o nf o r t h eb a s i ce d u c a t i o n ，t h e n ， d om o r es e a r c ho nt h ef e a t u r es e l e c t i o na n dw e i g h tc a l c u l a t i o nw h i c ha r ei n c l u d e di nt h ef e a t u r e d i s t i l l a t i o na c c o r d i n gt ot h i sg r o u n d w o r k d u r i n gt h er e s e a r c ho f f e a t u r es e l e c t i o nw ec o m p a r et h e d f 、i g 、e c e 、m i 、x 2 、w e ta n dm a k ean e wa l g o r i t h mn a m e dm i p wb a s e do nt h ee x p e r i m e n t a l r e s u l t ，b yt h er e s u l to f e x p e r i m e n tw ef i n dt h a tm i p wi sm o r ev a l i dt h a nm i i nt h ep a r to f w e i g h t c a l c u l a t i o n ，w ec o m p a r et f i d fa n da l g o r i t h mb a s e do ne n t r o p ya n df i n dt h a tt f i d fi sm o r ev a l i d t h a no t h e r s f i n a l l y , w ed e s i g na n dd e v e l o paw e b p a g e f e a t u r ed i s t i l l a t i o ns y s t e mw h i c hi n c l u d e t h ea b o v ea l g o r i t h mo ff e a t u r es e l e c t i o na n dw e i g h tc a l c u l a t i o n ，n o w , t h es y s t e mi su s i n gi nt h e b a s i ce d u c a t i o nr e s o o r c e ss e a r c he n g i n e k e y w o r d s ：b a s i ce d u c a t i o n a lr e s o u r c e ss e a r c he n g i n e ，f e a t u r es e l e c t i o n ，m i p w , w e i g h t c a l c u l a t i o n 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子 版和纸质舨；有权将学位论文用于非赢利目的的少量复制并允许论文 进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行 检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解 密后适用本规定。 作者签名： 日 期： 1 1 研究背景 第一章前言 一、研究撼础教育搜索引擎的必要性 随麓i n t e r n e t 的普及和发展，网络已经成为人们日常生活中不可娥缺的一个重要组成 部分，壤撂我国互联臻接崽中心( c n n i c ) 第十六次中鬻趸联网发展欹凝统诗报告鬣示， 截止2 0 0 5 年6 月3 0 日，我国上网用户总人数为1 0 3 0 0 万人，在被调查者当中，选择“。e 网 最主要的爨的”是“获取信息”的达3 7 8 9 6 ；“学习与知识浏览”的选1 0 3 ；“经常使用的 网络务功能”选择“搜索；i 擎”的入迭羁了6 4 。骗 “弼户褥知薪潮站豹主要途径”逸拜 “搜索引擎”的人则商选8 4 5 。从以上数据看出，随着我国互联网的发展，越来越多的人 在利用互联网获取信息和学习知识，搜索s l 擎已成为学习的重要工具，成了获取教育资源的 一条重要浆遵。逛众多酶援索；| 擎都是藤陪牡会大众静。在援索教育信息时，捡素结巢倍惠 量过大，避回太多的无关内容，若干个关键词构成的查询组合可能返回上万个相关页面链接， 很多检索结果和用户查询毫无关系，黻丽鸯准率较低：b 的覆盖蕊肖限，根据s t e v e l a w r e n c e 的搬告。，强翦经何搜索；l 擎索g | 的部分不超过熬个w e b 静3 0 ，由于缺乏钟辩牲， 查全率较低，网上大量优秀教育资源检索不到；内容杂乱，且充斥大量诱惑信息，容易转移 用户注意力；需要一定的搜索技巧，大多用户难以掌握。因此。研究并野发出一款适含广大 中小学簿艇的基础教育瓷源搜索；i 擎j # 常有必要。 2 0 0 1 年6 月教育部颁布基础教育课程改革纲要( 试行) ，提出了基础教育课程改革 的目标之一是要培养学擞援集和处理信感的能力、获取新知识的能力、分橱和解决闯题的能 力鞋及交流与合作的能力，并把这些毖力作为与读、写、算一样重要的基础能力进行培养。 当前，新课改正在全国部分试点逐渐展开，为配合新谍改的执行，贯彻新课改的理念，开发 基础教育瓷源搜索s l 擎不仅具有必要性，甄且具有追甥性。 二、骚究掰页文档特征撬取的必要经 i n t e r n e t 无论从信息数量方面还是倍息种类方面衡鬣都是一个巨烈的信息库，但由于 稠页数量爆炸式地增长，现有搜索g l 擎掰提供的信息往镰远多于用户瓒鼹要静信息，躐闲是 。中国互联网络信息中心，第十六次中国互联嘲发展状况统计报告，2 0 0 5 7 2 s ，l a w r e n c e ，c l ，g i l e s ，a c c e s s i b i l i t yo fi n f o r m a t i o no nt h ew e b ，n a t u r e 。4 0 0 ：1 0 7 1 0 9 1 9 9 9 基于关键词的搜索会返回包含该关键词的所有网页，而这些网页经常是跨越多个领域，其中 许多内容根本不属于用户感兴趣的范围。为了得到真正有用的信息，用户只能按照搜索引擎 列出的页面顺序，花费很多的时间来浏览大量网页。为了向用户提供更有效的信息，提高搜 索的准确性，有必要研究网页的分类技术，利用计算机对海量的网页进行自动分类，网页分 类技术中特征提取又是其研究的核心之一。特征提取3 ( f e a t u r es e l e c t i o n ) 从广义来讲是指 一种变换，原始特征的数量一般都很大，也就是说它们处于高维空间。通过映射或变换将它 们用低维空问来表示。特征提取主要借助统计学、信息论等方法对特征与类别之间的关系进 行分析，选择与包含相关类别信息较多，对分类贡献较大的若干特征项。因此特征提取对于 网页文档分类有着重要的影响，特别是在当前这种网页文档资源种类繁多，内容混杂、包含 大量“噪音”信息的情况下，特征提取的结果将会直接影响到网页文档自动分类的精度和效 度，进而最终影响这个搜索引擎的质量。 虽然现在已经有了很多关于文档特征提取方法的研究，但是由于本文研究对象自身存在 的特殊性，本文通过调研发现，现有的方法并不能够很好的满足实际需求。首先现有的文档 特征提取方法大多是针对文本文档，而本文所针对的是存在于w e b 上的网页文档，与文本 文档相比，网页文档还存在许多h t m l 格式信息以及其他干扰信息；其次由于国内对于特征 提取的研究起步相对较晚，到目前为止还没有形成一个相对统一的标准中文数据集；另外虽 然国内外有很多关于特征选择和权重计算的算法研究，但由于实验环境以及语种的差异，并 没有形成一个统一的观点。因此，如何研究出一套适合于基础教育网页资源的特征提取方案 并将之付诸实旆对整个基础教育搜索引擎具有非常重要的意义。 1 2 本文的研究方法 本文试阻对基础教育搜索引擎中的网页文档特征提取从理论和应用两个层面展开，在具 体的研究方法上主要采用了文献法、试验法、统计分析法和系统法等。 一、文献法 在本课题的研究过程中，笔者广泛搜集研读了现有的国内外关于搜索引擎、特征提取、 自动分类方法与理论的文献，尽可能的吸收前人的精华，并在此基础上进行总结与反思，为 探索实现适合基础教育搜索引擎系统的网页文档特征提取提供了一条可行的思路。 二、试验法 z i p f sl a w h t t p ：m n s l i j g e n e t i c s o r g w l i z i p f ，浏览时问：2 0 0 5 6 - 4 2 在研究前人关于文本特征提取算法的过程中，笔者运用数学中提供的理论和方法对所研 究的对象进行了实际的推导和计算，并根据系统需求进一步的改造优化，建立相关数学模型。 三、统计分析法 为了更加有效的观察和验证相关算法的效果，本文在研究相关方法理论、建立数学模型 的基础之上，设计开发了“基础教育搜索引擎中网页文档特征提取系统”，并通过不断试验， 统计分析试验结果，优化改进相关算法。 四、系统法 特征提取系统是基础教育搜索引擎系统中的一个子模块，与其他模块之间存在紧密联 系。特征提取需调用网页预处理模块对训练集中的网页文档进行文本信息的抽取，还需要调 _ l = j 分词模块对抽取出的文本信息进行分词处理，另外特征提取模块本身所提取出的特征信息 是提供给网页分类模块使用的，因此必须用系统的方法进行考察分析，建立好与各个模块之 间数据交换的接口。 1 3 本文的主要工作 本文主要着眼点在于提出一个适合于基础教育资源领域的网页文档特征提取实用方法 并在此基础上开发相关原型系统，其主要研究内容包括以下几个方面： 一、网页文档的预处理 本文所研究的是网页文档的特征提取，其研究对象是各种形式的网页文档，与普通的文 本文档相比，网页文档除了包含其所要表达的相关语义信息外，还附加了大量的h n i l 格式 信息、s c r i p t 脚本信息以及注释信息等等，因此如何过滤掉这些与网页所要表达语义无关 的干扰信息是本文要关注的一个问题。另外由于特征提取是针对一个个词条来进行处理的， 而中文表达中词条与词条之间并没有明显的分隔，由此中文信息的分词又是另一个需要考虑 的问题了，此两点统一为网页文档的预处理，这虽不是本文研究的重点所在，但却是一个必 须关注的前提性工作。 二、网页文本文档的特征选择与权重计算方法研究 网页文本文档的特征选择与权重计算是本文研究的重点，其研究内容主要在于以下几 点：第一、训练测试数据集的选择和组织，由于国内还没有一个相对统一的标准中文数据 集可供使用，因此首先需要研究如何在大规模的网页文档中挑选出最佳数量的文档组合形成 针对基础教育资源分类体系的数据集；第二、网页文档的特征选择，主要研究如何对训练文 档包含的大量词条进行初步处理和特征选择，实现由高维空间到低维空间的转换，降低非特 征项对特征项权重计算的干扰，减少系统计算所需开销；第三、特征的权重赋值，主要研究 如何在基础教育资源各类别之间界限模糊，词条交叉较多的情况下，选择合适的算法对各类 特征项的重要性进行评估，赋予适当的权重，从而更好地辅助文档自动分类。 三、基础教育搜索引擎中的文档特征提取模块原型系统的设计与开发 在相关理论及算法研究的基础上，本文还试图开发出一个开放的基础教育网页文本特征 提取系统，以服务于基础教育搜索引擎这个大的系统。从系统开发的角度来看，作为整个搜 索引擎系统的一个子模块，一方面，特征提取部分需要处理好与其他各个模块之间的接口， 以便整个系统能够高效流畅的协同工作，另一方面，作为一个开放的系统，特征提取模块又 需要具有相对的独立性和可移植性。因此基础教育网页文档特征提取模块原型系统的设计与 开发又是本文需要研究的一个重要内容。 综上所述，网页文档的特征提取是网页自动分类系统的核心技术之一，也是基础教育搜 索引擎整个大的体系中极其重要的一个组成部分，本文将对其中所涉及到的各项关键技术进 行研究，并在此基础上设计开发个开放的基础教育网页文档特征提取系统。 1 4 本文的主要成果 在上述研究的基础上，本文主要取得了以下几点成果： 首先、本文围绕网页文档的预处理，从标记预处理和中文分词两个点展开，标记预处理 部分研究了通过构建标签树，抽取文本信息的标记过滤方法；中文分词部分研究了目前常用 的几类中文分词方法，并对本系统采用的逆向最大匹配分词法做了详细的理论阐述和算法描 述。 其次、本文重点研究了网页文档的特征提取方法。首先构建了一个包含7 4 1 2 篇训练文 档、1 8 6 7 篇测试文档的网页数据集，并通过实验得出t n 练集与分类效果之间的关系，接 着研究了目前常用的特征提取算法，对这些算法进行了实验比较，并在此基础上对互信息算 法进行改进，提出了改进型的互信息算法0 v f l p w ) ，实验结果表明，改进型的互信息算法要 远优于传统的互信息算法，并且与其他算法相比，改进型互信息算法也是表现最好的，最后 研究了目前常用的权重计算算法，并将t f i d f 算法和其他六种基于熵函数的权重计算算法 进行实验比较，得出了t f i d f 在基础教育资源分类体系下效果最佳的结论。 最后、本文在上述理论阐述和算法研究的基础之上设计并实现了一个基于网页的文档特 4 征提取系统，该系统集成了第四章所描述的几种特征选择算法和权重计算算法，使用c # n e t 作为开发工具，采用面向对象的体系结构，后台数据库采用s q l s e r v e r 2 0 0 0 ，具有较好的移 植性和扩展性，可作为特征提取系统在实际环境中使用，也可作为比较各种算法效果的实验 工具。 1 5 本文的组织结构 本文以网页文档的特征提取研究为核心，从理论和应用两个层面出发讨论相关技术及算 法。 第二章首先阐述了与特征提取相关的几个领域及相关知识，主要包括文档表示理论、自 动分类技术系统结构、自动分类体系的评价标准等，此外本章还简单介绍了国内外关于特征 提取中特征选择和权重计算这两部分的研究现状。 第三章简单介绍了网页文档预处理的相关理论及方法，主要包括网页标记的过滤过程及 方法、网页中文文本信息的分词。 第四章是本文的重点所在，此章主要是针对网页文档中文本内容的特征提取进行研究， 首先对训练集的选取和组织进行了相关研究，并通过实验找出了训练集规模与特征提取效果 之间的关系：接着介绍了目前常用的几种特征选择算法，并对各种算法进行了实验比较，分 析实验结果在此基础之上对的互信息算法做了相关改进，进一步实验，并分析改进后的实验 结果，总结改进后的效果。特征选择分析之后本章又详细介绍了文档特征项权重赋值的相关 算法，对常用的算法进行实验比较，分析实验结果，得出相对最适应于当前基础教育资源特 点的权重赋值算法。 第五章是在第四章实验分析的基础上，设计开发基础教育搜索引擎文档特征提取系统， 本章主要是从系统结构、逻辑单元、后台数据库以及系统交互界面等几个方面出发，阐述其 具体设计与实现。 第六章对本文的工作进行了总结，对研究中的创新点和不足之处做了说明，并制定下一 步的工作计划。 2 1 文档表示理论 第二章相关研究概述 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对文章内 容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识o 和l ，所以必 须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成文本的字或词在确 定文本类别的作用上相互独立，这样- t u a 使用文本中出现的字或词的集合来代替文本，不言 而喻，这将丢失大量关于文章内容的信息，但是这种假设可以使文本的表示和处理形式化， 并且可以在文本分类中取得较好的效果。 目前，在信息处理方向上，常用的文档表示模型有布尔模型( b o o l e a nm o d e l ) 、向量空 间模型( v e c t o rs p a c em o d e l ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 、概念模型( c o n c e p t m o d e l ) 、 案例模型( c a s e - b a s e dm o d e l ) 、神经网络模型( n e u r a ln e t w o r k s ) ，以及在此基础上延伸形 成的扩展模型与混合模型。而在这其中，最富想象力、最具创造性的模型当属向量空间模型， 这种模型也是目前文本自动分类、信息检索、自动摘要等领域使用晟广泛的模型之一。向量 空间模型4 是由美国的g s a l t o n 于2 0 世纪7 0 年代中期提出，并在康奈尔大学( c o r n e l l u n i v e r s i t y ) 开发的s m a r t 信息检索系统中成功运用，其基本思想是以向量来表示文本，在向 量空间模型中文本泛指各种机器可读的记录，用d ( d o c u m e n t ) 表示；特征项是指出现在文档 口中且能够代表该文档内容的基本语言单位，用 ( t e r m ) 表示，主要是由词或短语构成。文 本可以用特征项集表示为口亿，乃，r n ) ，其中露是特征项，1 k n 例如一篇 文档中有a 、b 、e 、d 四个特征项，那么这篇文档就可以表示为口国岛bd ) o 对任一特 征项而言，由于在文本中出现的位置和出现的词频不同，对文本内容的价值也是不同的，所 以，对含有n 个特征项的文本而言，应该给每个特征项赋予一定的权重表示其重要程度。即 口= 刀亿，历，乃，矿? ，7 n ，砌j ，简记为口= dm ，肥，肠j ，这就是 文本d 的向量表示，其中厩是五的权重，l k n 。 庞剑锋h 东波白硕，基于向量空间模型的文本自动分类系统的研究与实现，计算机应用研究，2 0 0 1 9 6 2 2 自动分类技术 网页文档特征提取模块是网页自动分类系统的一个子模块，本节将简要描述一下自动分 类系统的组成结构以及相关评价标准。 2 2 i 自动分类系统结构 网页自动分类是指利用计算机系统代替人：【对网络蜘蛛抓取下来的网页文本等对象进 行分类，一个完整的网页自动分类过程主要包括以下几个部分：训练集和测试集的组织，网 页预处理，特征选择，权重计算，分类器，分类结果评价。其结构如图2 - 1 ，其中虚线部分 是本文重点要研究的一个模块。 图2 一l 网页文本自动分类系统结构图 一、构建训练集和测试集 训练集用于前期提取特征项，测试集用于后期测试分类系统精度，测试集包含两种：开 放测试集和封闭测试集，开放测试集中的文档不包含在训练集中而封闭测试集中的文档是从 训练集中挑选出来的。 二、网页文档预处理 由于人工搜集的是网页文本，其中包含很多h t m l 标记、乱码、非文本内容等与分类无 关的信息，因此网页分类器需要有一个预处理模块将训练集和测试集的网页内容按照一种计 算机能够理解的格式用特征项的形式描述出来，使机器能够对文本进行处理和运算。网页文 档预处理部分通常由网页标记的预处理和网页文本的分词两个子模块构成。 三、特征选择 构成网页文本的词汇数量是相当大的，表示文本的向量空间维数也相当大，中文环境下 7 通常可以达到几万维之多。如此高维的特征空间会使一些分类算法无法进行或效率非常低， 因此我们需要进行维数约减的工作，将高维特征空间映射到一个低维的特征空间，并且要求 基于该低维特征空间进行文本分类时，分类效果不会下降，或者下降很小。这就是特征选择 部分需要完成的工作。 四、权重计算 经过特征选择部分以后，高维特征空间已转换为一个相对低维的特征空问，但这其中各 个特征项对于所属类别的重要程度和区分度是不一样的，为了更准确地描述特征项在其类别 中的重要性，还需要计算各特征项的权重。 五、构建分类器 分类器是网页分类系统的重要组成部分，目前常用的分类器主要有：概率分类器 ( p r o b a b i l is t i cc l a s s i f i e r ) 、决策树决策规则分类器( d e c is i o nt r e e r u l e s c l a s s i f i e r ) 、r o c c h i o 分类器、类中心向量分类器( c l a s s - c e n t r a lv e c t o rc l a s s i f i e r ) 、 k 近邻分类器( k - n e a r e s tn e i g h b o u rc l a s s i f i e r ) 、支持向量机分类器( s u p p o r tv e c t o r m a c h i n e ) 以及将多个分类器混合使用的组合分类器等等。 六、分类结果评价 通过分类结果的评价我们可以客观的考察整个分类系统的优劣，从而进一步指导训练 集，特征选择，权重计算等各个部分的改进，以期形成一个高性能的分类系统。要想完成这 些评测，分类器需要对测试例进行分类，并将分类器得到的分类结果与正确结果进行比对。 统计出该分类系统的各种指标，进而通过相关标准进行评价。关于分类准确度有很多标准， 这些标准本文将在下一节中详细介绍。 2 2 2 评价标准 由于特征提取部分是为网页文档的自动分类服务的，因此特征提取效果的好坏与否需要 通过测评使用相关特征进行分类后的结果来获得，目前常用的文档自动分类的评价标准主要 有以下几种5 ： 、t r e c 评价标准 t r e c 文本过滤比赛对分类效果给出了比较全面的评价方法。首先是对分类结果的定义， 对于给定的一个主题，分类结果可以被归纳放入下面的表格当中。对于每一个待分类的文本， 5 谭金波李艺杨晓江，文本自动分类的测评研究进展，现代图书情报技术，2 0 0 5 5 8 有两种情况，此文本可能是属于此主题的，也可能是不属于此主题的；对于属于此主题的文 本，分类系统可能将之分到此主题，也可能将之不分到此主题，对于不属于此主题的文本， 分类系统同样可能将之分到此主题，也可能将之不分到此主题，于是可以建立如下的四分表 相关不相关 检出r + an + b 未检出 r cn 。d 最2 1 检索结果分布表 检出相关文本和未检出不相关文本都是过滤正确的情况。而未检出相关文本意味着遗 漏，检出不相关文本意味着错检。对这四种情况赋以相应的权重a ，b ，c ，d 后，t r e c 采用 下面的一个线性u t i l i t y 函数来评价整个系统： u t i l i t y = a 十r + + 叶n 十c * r 一十d * n 一 这里的r + r 一n + 盯指的是每个主题四种文本的数量。参数a ，b ，c ，d 决定了每种情况 的代价。显然a ，d 0 ，b ，c o 。又由于检出相关文本是最重要的，所以a d 。u t i l i t y 值越大，系统的过滤性能就越好。 u t i l i t y = 2 * ( r + ) 一( n + ) 二、通用评价标准 在进行分类实验时，常采用的方法是将机器的分类结果与通过专家思考判断后对文本的 分类结果( 这里假设人工分类完全正确弗且排除个人思维差异的因素) 相比较，与人工分类结 果越相近，分类的准确程度就越高。这里隐含了评估文本分类系统的两个指标：准确率和查 全率。 准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率，其数学公式如下： 准确率( p r e c i s i o n ) = 慕 查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率，其数学公式如 下： 查全率c ”c a l l ) = 垄 兰襻 准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废。因此， 存在一种新的评估指标一f ，测试值，其数学公式如下： 五测试值= 黑鬻 9 另外，有微平均和宏平均两种计算准确率、查全率和f ，值的方法。 微平均：计算每一类的准确率、查全率和f ，值。 宏平均：计算全部类的准确率、查全率和尸，值。 三、商业评价标准 在实际商业应用中，除了分类正确率外，最重视算法的分类速度。以北大举办的文本分 类比赛为例，仅考察分类器的分类查准率( 没有考察查全率) 和分类效率( 没有考察训练时 间) 。中文网页分类器的质量计算式为： s ， s ：! ! 1 7 矗：每个网页的分类得分： f l ：为测试网页数： 为分类花费的时间，以秒计算：& 分类器最后得分 本文主要是通过自动分类结果的测评来考察特征提取部分的实验效果，而并不注重自动 分类系统本身的相关指标，因此采用通用的评价标准，即通过由分类的准确率和查全率两个 参数得出的f 1 值来确定分类的效果，进而考察与之相对应的特征提取模块的效果。 2 3 特征提取目前研究现状 2 3 1 特征项选择 特征项选择是指从一篇文档中自动选择可以表征文档所涵盖内容的关键词集，它具有降 低向量空间维数、简化计算、防止过分拟合等作用。目前常用的特征选择算法有文档频率 ( d f ) 、信息增益( i g ) 、互信息( m i ) 、r 统计( c h i ) 、文本证据权( w e t ) 、期望交叉熵( e x p e c t e d c r o s se n t r o p y ) 、几率比( o d d s ) 等几种。这些方法各有优缺点，已经有很多研究者对特征选择 问题进行了探讨，其中最常被引用的是c m u 大学y i m i n gy a n g 所做的降维实验6 ，实验环境： 分类方法采用k n n ，特征项为英文词，特征降维采用了i g 、d f 、w e t 、m i 和x 2 五种方法，权 重函数采用的是s m a r t 系统的l t c 。其实验结论是：除了互信息以外的降维算法，分类正确 率都随着特征项的减少而增加，但到达一个阈值后，大约在1 6 0 0 维之后，分类正确率会急 剧降低。而采用互信息降维的话，分类正确率总是在不断降低。另外d u n j am t a d e m n i c 7 做 。y i m i n gy a n g ，j a n0p e d e r s e n ac o m p a r a t i v es t u d yo nf e a t u r es e l e c t i o ni nt e x tc a t e g o r i z a t i o n i n ：p r o c e e d i n g so ft h ef o u r t e e n t hi n t e r n a t i o n a lc o n f e r e n c eo nm a c h i n el e a r n i n g ( c m l 9 7 ) 。1 9 9 7 m l a d e m n i cd g r o b e l n i km f e a t u r es e l e c t i o nf o ru n b a l a n c e dc l a s sd i s t r i b u t i o na n dn a i v eb a y e s p r o c e e d i n g so ft h es i x t e e n t hi n t e r n a t i o n a lc o n f e r e n c eo nm a c h i n el e a r n i n g ，b l e d ：m o r g a nk a u f n n 1 0 的降维实验也比较有代表性，在他的实验中，分类算法采用的是n a i v eb a y e s ，实验结论是 o d d s 是最好的测度，e x p e c t e dc r o s se n t r o p y 和d f 是较好的，较差的是m i ，最差的是i g 。 这一差异可能源于双方的学习算法和对数据域定义的不同。y a n g 采取的是平面文本分类， 使用具有多个类值的分类器；而d u n j a m l a d e m n i c 采取的是等级文本分类，将数据域划分成 许多子问题，每个子问题对应一个只有两类值的分类器。 2 3 2 特征项权重计算 特征项权重计算是指通过考察词条在文本中出现次数等相关信息，确定其对文本内容的 价值，国内外许多科学家对权重函数进行了测试。比如，意大利科学家f a b r i z i os e b a s t i a n i ， 他所采用的权重实验环境是8 ：分类方法采用s v m ，特征项为英文词，测试数据为 r e u t e r s 一2 1 5 7 8 数据集，权重函数采用t f * i d f ，t f * c h i ( g ) ，t f * c h i ( 1 ) ，t f * i g ( g ) ，t f * i g ( 1 ) ， t f * g r ( g ) 和t f * g r ( 1 ) 共7 种方式，结论是：不同的权重函数对分类正确率影响很大：在1 0 类情况一f ，f 。值从9 2 到8 7 ，相差5 ：在9 0 类情况下，f ，值从8 6 到8 1 ，也相差5 ；t f * i d f 整体得分最高。 国内更多的研究倾向是对t f * i d f 的改进，如鲁松9 等为了解决t f * i d f 文档表示方法无 法涉及词语在不同文档中分布比例的问题，引入信息增益的概念，提出了改进的文档表示方 法t f * i d f * i g 来弥补t f * i d f 的缺陷。实验验证，性能要好于传统的方法。陆玉昌”等提出利 用特征降维中的评估函数代替i d f 函数进行权值调整的方法，通过实验比较得出结论：互信 息进行权值调整时分类精度最高，在对5 类测试中达到8 0 。景丽萍等”也提出了用互信息 算法对t f * i d f 进行调整，采用n a i v eb a y e s 分类器对1 3 5 类测试，结果分类正确率由t f * i d f 的7 6 上升到8 8 从以上分析可以看出，权重函数对分类有很大影响，但各位学者的研究结果不同，说明 文本分类问题是涉及到文本表示、相似度计算和算法决策等多种复杂技术的综合应用，也许 不同的权重函数适合不同的分类算法，所以选择权重函数时，需要考虑多种因素，从实验中 得到最优方法。 。f r a n e ad e b o l e ，f a b r i z i os e b a s f i a n i ，s u p e r v i s e dt e r mw e i g h t i n gf o ra u t o m a t e dt e x tc a t e g o r i z a t i o n 2 0 0 3 h t t p ：e i t e s e e r i s t p s u e d u 5 7 2 6 6 1 h t m l ，( a c c e s s e ds e p 1 0 ，2 0 0 4 ) 鲁松李晓黎白硕王实文档中词语权重计算方法的改进，中文信息学报，2 0 0 0 0 6 ”陆玉昌鲁明羽李凡周立柱，向量空间法中单词权重函数的分析和构造计算机研究与发展，2 0 0 2 1 0 ”景丽萍黄厚宽石洪波，用于文本挖掘的特征选择方法t f i d f 及其改进，广西师范大学学报( 自然科学 版) 2 0 0 3 1 第三章网页文档的预处理 网页文档是一种由格式标记和文本内容构成的半结构化数据。网页中包含大量h t m l 格 式信息、s c r i p t 脚本信息以及注释信息等等与主题无关的数据，这些信息被视为噪声信息 应进行清除，清除网页噪声的过程称为网页标记的预处理。经过处理后的网页接近于纯文本， 因此，此过程也可称为网页的纯文本化。由于特征提取是针对词条进行的操作，而中文表达 中词条与词条之间并没有明显的分隔，因此还需要考虑对处理出来的纯文本信息进行分词处 理。网页标记预处理和网页文本内容的分词是将网页文档转换为词的集合的操作，统称为网 页文档的预处理。 3 1 网页标记预处理 h t m l ( h y p e rt e x tm a r k u pl a n g u a g e ) 是一种标识语言，它定义了一套标签来刻画网页 显示时的页面布局，因此，目前对于网页标记预处理最常用的方法就是首先根据h t m l 标记 构造出网页的标签树，然后根据标签树一层层的进行文本内容的抽取，最后组装成不包含 h t m l 标记的纯文本文档。 一、相关h t m l 标记介绍： ( 1 ) 标签：h t m l 文本起始元素，通知浏览器该文档为h t m l 文档。 ( 2 ) ( h e a d ) 标签：出现在文档的起始部分，标明文档的题目或介绍。 ( 3 ) ( t i t l e ) 标签：此标签存在于( h e a d ) 标签内部，用于标识网页的标题。 ( 4 ) ( b o d y ) 标签：描述文档主体的开始和结束。 ( 5 ) ( t a b l e ) 标签：定义一张表格。用t r 、t d 、t h 元素定义行、列和单元，用c a p t i o n 、t b o d y 、 t f o n t 等可选元素来组织表格以及对列、列组属性进行处理。 ( 6 ) ( t r 标签：此标签存在于( t a b l e ) 标签内部，用于定义表格中的行信息。 ( 7 ) 标签：此标签存在于 标签内部，用于定义表格中的列信息。 ( 8 ) 标签：表示一个连接到指定u r l 的超级链接。 ( 9 ) ( p 标签：表示一个段落。 ( 1 0 ) ( f o r m ) 标签：表示一个包含控件的表单。 以上介绍的只是几种常见的h t t l l 标签，其他还有许多如 标签、 标签等等， 2 ”张志刚陈静李晓明，一种h t m l 网页净化方法情报学报，2 0 0 4 4 图3 - 1h t m l 标签树 标签树构造完毕以后，网页标记的预处理就转化成了对标签树结点的剪裁，只需编历标 签树的各个树叶即可完成文本信息的抽取，将网页文档转换为文本文档。 3 2 中文分词 经过标记预处理以后，网页文档己转化为文本文档，由于特征提取是针对词的操作，因 此下一个面临的问题就是针对文本文档的分词。中文文档中词与词之间没有自然的切分标 志，而且语言学中对于词的定义也是多种多样，这都给自动分词带来了很大的困难。 3 2 1 常用中文分词方法 近年来，语言学界、人工智能领域和情报检索界的学者们在汉语自动分词方面进行了大 量的研究，找到了许多种解决汉语分词的方法。常用自动分词方法有：晟大匹配法、逆向最 大匹配法、逐词遍历法、设立切分标志法、最佳匹配法、有穷多层次列举法、二次扫描法、 高频优先分词法、基于期望的分词法、联想回溯法、双向扫描法、邻接约束法、扩弃转移 网络分词法、语境相关法、全自动词典切词法、基于规则的分词法、多遍扫描联想法、部件 词典法、链接表法、最少分词词频选择法、专家系统分词法、基于神经网络的分词方法等2 2 1 4 种。归纳起来，目前常用的中文分词方法可以分为三种类型： 一、机械分词法 机械分词法主要有晟大匹配法( 删法) 、逆向最大匹配法( r 删) 、逐词匹配法、部件词典 法、词频统计法、设立标志法、并行分词法、词库划分和联想匹配法等。 其基本思想是：先建立词库，对给定的待分词汉字串，以某种方法切取其子串，如该子 串与词典某项匹配成功，则该子串是词，继续切分其余部分；否则该子串不是词，重新切取 给定汉字串的子串进行匹配。机械匹配法根据切取方向的不同，又可分为正向匹配法和逆向 匹配法，以及二者结合的双向匹配法。 二、语义分词法 语义分词法引入了语义分析，对自然语言自身的语言信息进行更多的处理，如扩充转移 网络法、知识分词语义分析法、邻接约束法、综合匹配法、后缀分词法、特征词库法、约束 矩阵法、语法分析法等。 以约束矩阵法为例，其基本思想是：先建立一个语法约束矩阵和一个语义约束矩阵，其 中元素分别表明具有某词性的词和具有另一词性的词相邻是否符合语法规则、属于某语义类 的词和属于另一语义类的词相邻是否合乎逻辑，机械切词时以之约束分词结果。约束矩阵法 和语法分析法实质上就是机械匹配法增加了歧义处理功能，更多的侧重于分词的准确性。 三、人工智能法 人工智能法又称理解分词法，人工智能是对信息进行智能化处理的一种模式，主要有两 种处理方式：一种是基于心理学的符号处理方法。模拟人脑的功能，像专家系统，即希望模 拟人脑的功能，构造推理网络，经过符号转换，从而可以进行解释性处理。一种是基于生理 学的模拟方法。神经网络旨在模拟人脑的神经系统机构的运作机制来实现一定的功能。以上 两种思路也是近年来人工智能领域研究的