（计算机应用技术专业论文）xml文档分类方法的研究及其应用.pdf

大连理工大学硕士学位论文 摘要 随着网络技术的飞速发展，信息大量膨胀和聚集，儿( e x t e i l s i b l em a r k u p l a l l g u a g e ) 作为一种常用的数据交换和传输标准，蕴含了丰富的信息。因此，对吼 文档的挖掘已经成为w e b 挖掘一个新的研究热点。 本文重点对x m l 文档分类方法进行了研究。删l 文档的结构特征是舭文档分 类区别于文本分类的一个重要方面，这使很多成熟的文本分类算法无法应用到订l 文 档分类中。因此，本文重点对帆文档的结构特征进行了研究。首先，给出一种频率 路径模型来表示x m l 文档的结构，该模型中不但保存了节点的标签信息，同时统计了 相同路径出现的频率，使得在保证不丢失有效信息的前提下大大减小了原来路径模型的 规模。其次，在频率路径模型的基础上，给出一种带位置权重的基于路径的订l 文档 结构相似度计算方法w l c s ( w e i 曲t e dl o n g e s tc o n l i n o ns u b s e q u e n c e ) 。该方法在路径 匹配时，使用最长公共子序列方法，能够捕捉到现有路径匹配方法漏掉的有效信息；在 进行路径相似度计算时，引入位置权重向量，将路径节点的位置信息考虑在内。通过在 真实数据集上做实验表明w l c s 方法召回率和准确率均高于当前存在的基于路径计算 相似度的方法。再次，基于频率路径模型给出一种新的汜文档结构向量化方法。该 方法使用一种基于路径频率的信息增益方法选择特征路径，使用w l c s 方法中的路径相 似度计算方法生成特征路径向量，并通过实验说明该方法的有效性。最后，在本文研究 基础上，结合大连市公安局“全文搜索系统 的实际课题，给出舭文档分类的一个 具体应用。 关键词：x m l 文档分类；结构相似度；位置权重 ) a 咀。文档分类方法的研究及其应用 r e s e a r c ha n d a p p l i c a t i o no fx m l d o c u m e n tc l a s s i f i c a t i o nm e t h o d a b s t r a c t 订l ( e x t e n s i b l em 咖l 觚融g e ) ，a sac o m m o nd a ：t ae x c l 姗g i i l ga n d 饿m s m i t t i n g s t a l l d a r d ，c o n t a i l l sr i c hi n f o 册a t i o n d a ：c a 血1 l i n go n ) 叫lh a sb e c o m ean e wr e s e a r c hf o c u s o f 、e b 岫g 1 w sa r t i c l ef o c u s e so nc l a s s i 丘c a t i o nm e t l l o d so fx m ld o c 啪e n t t h es t m c t u r e c h a r a c t e r i s t i c sa r ev e 秽i i i l p o n m tf e a ：c u r e sw 址c ht e 斌d o c 砌e n t sd on o th a v e ，m e r e f o r em o s t t e c l l l l o l o 百e sa n da j g o r i t l l i i l su s e di 1 1t e 殖m i i l i n ga r en o ts u i t a _ b l et ox m lm i i l i i l gb e c a u s eo f t 1 1 es t n l c t u r ec h a r a c t e r i s t i c so fx 】ld o c 啪e n t s s o ，t h i sa r t i c l ep a y sm o r ea ：t t e n t i o nt ot 1 1 e 咖t u r ec h a r a c t e r i s t i c so fx m ld o c u m e n t f i r 瓯am o d e lc a l l e df r e c q u e n c v p a mm o d e li s p m p o s e dt 0e x p r e s sx m l d o c 吼e n t s t 1 1 i sm o ! d e ln o t0 1 1 l yp r e s e e sla _ b e l so fc o r r e s p o n d e m n o d e s ，b 1 雠a l s op r o v i d e sn 。e q l l e n c yo fs a m ep a 也s ，s oi tc a nd e c r e a s em e 缸c ep 劬m o d e ls c a l e c o n s u m e d l yo nm ec o n d i t i o no fn o t1 0 s i r 培m e a n i l l g 如l 切i b 衄a t i o n s e c o n d ，o nt 1 1 eb a s i so f f r e c q u e n c y - p a t l lm o d e l ，as i 商l a r i 锣c a l c u l a t i o nm e 也o dc a l l e dw l c s ( w e i g h t e dl o n g e s t c o 聊n o ns u b s e q u e n c e ) i sp r o p o s e d t h e1 0 n g e s tc o 删m o ns u b s e q u e n c em e m o di s 劬胁d u c e d f o r 瑚t c gp a l s ；p o s i t i o nw e i g h tv e c t o r sw 量l i c hk e 印1 ep o s i t i o no fn o d e si nm 砌a r e i i i 仃i d d u c e df o rc a l c u l a t i i l gt h es i n l i l a r i t ) ro fp a m s e x p e 洒e n tr e s u l t so n 恤l ed a ：c as e t d e m o n s 廿a l t e dt l l eb e t t e rr e c a l lm t i o 缸da c c u r a c yt 1 1 a i le x s i t e dm e t h o d s n l i r 吐an e w v e c t o r i z a t i o nm 劬o do fm es 协l c n 】r eo fx m ld o c u n l e n ti sp r o p o s e do n 也eb a s i so f f r e c q u e n c y p a t hm o d e l w h e np r o c e s s i n gv e c t o r i z a t i o i l ，趾i i n p r o v e di ga l g o r i t l l l nw 1 1 i c hi s b a s e do np a m 舶q u e n c yi s 劬d u c e dc o m b i r 血g 谢t hw l c s f i i l a l l y ，t h er e s e a r c ho f 舭 ld o c 砌e n tc 1 a s s i f i c a t i o nm e m o di s 印p l i e di n 砌l t e ) 【ts e a r c l l i 】唱s y s t e m 肋md al i a n p u b l i cs e c u r i 够b u r e a u k e yw o r d s ：x m ld 0 c u m e n tc l a s s i f i c a t j o n ；s t r u c t u r es i m i a r i t y ；p o s i t o nw e i g h t v e c t o r i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：上业麴趁遵叠笼鱼歪淳蕉姐一：一一 作者签名：亟哇日期：立4 年丝月上王日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 逊k 毖佥薹幺星凸叠罩垒毽蔓殛彝 作者签名： ! 望，：2 查 日期： 型2年业月j 生日 导师签名：_ 垂乙三孓# 日期：盟年j 三月j 量日 大连理工大学硕士学位论文 1 绪论 1 1研究背景 随着网络技术的飞速发展，信息大量膨胀和聚集，如何快速高效地从大量信息中获 取有效知识在人们生产和生活中变得越来越重要。l ( e x t e n s i b l em a r k u pl a l l g u a g e ， 可标记扩展语言) 、h n 皿( h ) ，p e n e ) 【tm 砌( 1 j pk g u a g e ，超文本标记语言) 等新一代 电子文档描述语言描述的文档已经逐步代替原来的纯文本格式的文档l l 】。舭由于其灵 活性、简明性、易于扩展性等特征，已经成为网络应用( 如数字图书馆、电子商务等) 数据表示和交换的标准i z j 。 儿( 可扩展标记语言) 是一种半结构数据描述语言，它由万维网协会w 3 c ( w o r d w i d ew e bc o n s o r t i u m ) 设计，是专门为w e b 应用服务的s g m l ( 标准通用标记语言， s t a l l d a r dg e n e r a j i z e dm a r k u pl a n g u a g e ) 的一个重要分支吲。s g l 咀。是一种在w e b 发明 之前就早已存在的用标记来描述文档的通用语言，由于其十分庞大，难于学习和使用， 因此，人们提出了h n 他语言来弥补s g m l 的不足1 3 j 。随着w e b 应用的不断壮大和深 入，h 耵儿在实际的应用中已显得捉襟见肘。于是，w 3 c 建议使用一种精简的s g 池 瑚。与删，相比，舳独立于机器平台、提供商和编程语言，使其在不同的 系统、不同的数据库、不同的语言之间搭起沟通的桥梁，因此，舭给基于w e b 的数 据挖掘技术赋予了强大的功能和灵活性，同时它易于实现异构数据的集成、易于传输和 交换数据等特点也使得对异构数据库的查询和搜索变得更加简单。 目前，互联网已经形成了一个巨大的由龇格式的数据构成的数据仓库，蕴含了 丰富的信息，因此，对x m l 文档的挖掘已经成为快速有效地从互联网上获取信息的最 佳途径之一。帆文档挖掘，顾名思义就是对l 文档表示的数据进行数据挖掘。数 据挖掘( d a t a m i n j n g ) 是指从大量的数据中获取有效的、新颖的、潜在有用的、最终可 理解的模式的非平凡过程【4 】。数据挖掘的广义观点为：数据挖掘就是从存放在数据库、 数据仓库或其他信息库中的大量的数据中“挖掘 有趣知识的过程。数据挖掘，又称为 数据库中知识发现( k m o w l e d g ed i s c o v e 巧i nd a t a b a s e ，k d d ) ，也有人把数据挖掘视为 数据库知识发现过程的一个基本步骤【4 】。数据挖掘有四种主要的任务：预测建模、聚类 分析、关联分析和异常检测【5 】。其中，预测建模涉及两类预测建模任务：用于预测离散 的目标变量的分类和用于预测连续目标变量的回归i 引。因此，分类任务是数据挖掘的一 项重要任务。于是，帆文档分类作为皿文档挖掘的一个重要组成部分，也逐渐成 为国内外学者研究和讨论的热点。 v 几文档分类方法的研究及其应用 1 2 国内外研究现状 目前，对l 文档进行分类使用的技术不外乎数据挖掘中几种基本的分类技术， 如决策树法、最近邻分类法、支持向量机等。为了使原有分类技术更好地应用于x m l 文档的分类中，国内外的研究学者们针对帆文档半结构的特点做了大量的研究。不 论使用哪种方法，要解决的一个基本问题就是忸文档的表示。常用的几种表示x m l 文档结构的方法如下所示，其中前三种是专门针对结构的表示方法，后两种是将结构和 内容结合起来的表示方法。 ( 1 ) 元素表示法 提取) ( m l 文档中的标记，以标记的集合来表示x m l 文档，这是最简单的一种表示) ( m l 文档结构的方法。显然，文档中出现的元素集合不能充分反映文档的结构，因此使用该 方法表示结构可靠性不高，优点是算法简单、复杂度低。 ( 2 ) 图表示法 文献 6 中提出了一个基于结构图( s 一笋a p h ) 表示法，结构图是一个由x m l 文档集 合中的元素和有向边组成的有向图。边只反映了文档树中的父子关系，丢失了大量文档 层次结构信息。 ( 3 ) 树模型和路径模型 x m i 文档层次性的嵌套结构使其很容易表示成一棵树，而路径是树从根节点到叶 节点的节点序列，是树的的一种简单有效的表示方法，并且与边比较，路径体现了更多 的文档结构信息，是一种常用的表示方法。 ( 4 ) 结构链接模型( s 乜m 眦dl i l l kv e c t o rm o d e l ，s l v m ) 这是一种综合表儿文档结构和内容的模型。它将儿分为若干结构单元( 如 元素) ，结构单元类似于v s m 模型( v e c t o rs p a c em o d e l ，向量空间模型，将在第二章 中详细介绍) 【8 】的一个文档，为它们分别构造特征向量。这样整个文档被量化为一组向 量，可以用一个矩阵来表示【9 】。这种方法的关键问题之一是结构单元的选择与自动提取， 目前还没有好的通用的方法，只能根据待处理文档集的特点来个性化处理。 ( 5 ) 改进的向量空间模型 这是一种常用的将舢文档结构和内容综合表示的方法。向量空间模型( 将在第 二章中详细介绍) 的基本思想是把文本简化为以特征项的权重为分量的向量表示： ( ，w ：，w 。) ，其中心为第f 个特征项的权重。在普通文本分类中一般可以选择字、词 或词组作为文本的特征，而在对x m i ，文档进行分类时很多种不同的表示方法，文献 1 0 】 是将文本内容中的高频词和文档标记简单合并作为特征向量；文献【1 1 】采用有序对作为， 大连理工大学硕士学位论文 特征项，有序对包括文本内容中的词，以及词出现的位置，用路径表示。这类方法的最 大问题是特征向量维度过高，造成计算复杂性过大。 这五种表示方法各有优缺点，并且适用于不同的分类方法。前三种专门针对结构的 表示方法还可以经过整理加工和文本内容表示方法结合，组成新的方法，如文献 1 2 中 将路径向量化，然后与文本向量结合从丽表示舭文档。 下面结合舭文档的表示模型介绍几种常用的l 分类方法。 ( 1 ) 基于树模型使用编辑距离计算相似度 编辑距离是最常见的舭文档相似度计算方法。基本思想来自树结构之间的编辑 距离，文献 1 3 首次提出了树之间的编辑距离概念，并提供了计算树之间编辑距离的计 算方法。此后的许多工作u 4 j 5 l 进一步改进、丰富了这一方法。编辑距离反映的是树之间 结构方面的差异，编辑距离越小，说明两棵树越相似。文献 1 6 】将编辑距离从单纯计算 结构的编辑距离推广到能够将结构和内容结合计算编辑距离。在使用基于编辑距离计算 的相似度来对、，几文档进行分类时，通常使用的方法是k 近邻分类法( k - n e a r e s t n e i 曲b o r ，k n n ) ，因为其简单并且是基于相似度比较的。 ( 2 ) 基于向量模型计算相似度 v s m 模型( v e c t o rs p a c em o d e l ，向量空间模型) 是表示非结构化数据的一个重要 模型，在文本分类中起到了重要的作用。基于向量模型的表示方法，可以使用多种分类 方法如：支持向量机、最近邻分类、人工神经网络等。由于此种模型维数高的特点，支 持向量机成为了最佳选择。文献 1 0 ，1 1 ，1 2 】就是使用支持向量机进行分类。 ( 3 ) 基于路径模型计算相似度 基于路径模型计算相似度较之前两种方法跟为简单，因此经常被使用。文献 17 】首 次提出以一系列标签的集合来表示龇文档树的路径，并给出了计算相似度的公式。 文献 1 8 ，1 9 】改进和丰富了这一方法。 ( 4 ) 挖掘频繁路径或频繁子模式 这种方法多以路径模型为基础，通过挖掘训练集中的频繁路径和频繁子树为某种类 别建立特征向量或者特征子树等能够代表某类类别的【2 0 捌】，其基本思想还是基于比较相 似度进行分类，因此使用的主要分类方法也是k 近邻分类法，不过在挖掘频繁路径或频 繁子树是可能会用到聚类方面的算法。 ( 5 ) 使用决策树迸行分类 这种方法与前几种大不相同，它跳出了基于比较相似度进行分类的思维定势，使用 决策树法进行分类i 竭，但由于决策树的诸多限制并没有广泛推广开，文献 2 3 提出使用 决策树进行协同训练的方法进行半监督学习，这是使用决策树法的一个新进展。 x l 沮。文档分类方法的研究及其应用 除了上述分类方法外，还有基于层次进行分类的方法等多种。但总的来说，这些方 法主要分属两大类：一类是基于比较以l 文档相似度的计算方法，另一类是不基于比 较舭文档相似度的方法。目前，较多的研究都来自第一类，因为研究舭文档的 相似度不仅可以应用到儿文档的分类中，还可以应用到l 文档聚类等多方面。 本文也是基于这种考虑，重点对帆文档的相似度进行了研究。 1 3 本文主要工作和组织 本文重点对舭文档分类技术进行了研究。舭文档的结构特征是) a l 文档分 类区别于文本分类的一个重要方面，这使很多成熟的文本分类算法无法应用到舳文 档分类中。因此，本文重点对舢文档的结构特征进行了研究。 首先，提出一种频率路径模型来表示舭文档的结构。其次，在频率路径模型 的基础上，提出一种带位置权重的基于路径的舭文档结构相似度计算方法w l c s ( w e i g b t e dl 0 n g e s tc o m m o ns u b s e q u e n c e ) 。通过在真实数据集上做实验表明w l c s 方 法召回率和准确率均高于当前存在的基于路径计算相似度的方法。再次，基于频率路 径模型提出一种新的池文档结构向量化方法。该方法使用一种基于路径频率的信息 增益方法选择特征路径，使用w l c s 方法中的路径相似度计算方法生成特征路径向量。 最后，结合大连市公安局“全文搜索系统”的实际课题，在本文对舭文档结构的研 究基础上，将舭文档的结构特征和文本内容特征整合并将其应用到全文检索系统中。 本文的内容安排如下： 第一章是绪论部分，主要介绍了课题研究背景、儿文档分类的国内外研究现状 以及本文的工作和内容安排。 第二章介绍了文本分类的概念、文本分类过程、常用分类算法以及订l 文档特点 等相关知识。 第三章介绍了舭文档的基本知识和应用、x m l 文档相似度研究进展，以及本文 提出的讧l 文档相似度计算方法和改进的帆文档结构向量化方法，并介绍了订l 文档分类的过程。 第四章结合大连市公安局“全文搜索系统”的实际课题，介绍了全文检索系统的框 架和关键技术，以及儿文档分类在其中的应用。 大连理工大学硕士学位论文 2x m l 文档分类相关技术 儿是一种半结构数据描述语言，皿文档是使用皿语言描述的数据，是一 种带有结构信息的文本，这也是舭文档与纯文本文档的最本质的区别。除了舭 文档具有结构信息这一特征外，垤l 文档的其他特征都与纯文本文档非常相似。因此， 舭文档的分类研究是以文本分类为基础的，l 文档的分类技术大多来自文本分类 的相关技术和经验。 本章将分别介绍文本分类的概念、文本分类主要技术、常用分类算法以及l 文 档特点等相关知识。 2 1 文本分类概念 文本分类的研究可以追溯到上个世纪六十年代，早期的文本分类主要是基于知识工 程( l o w l e d g ee n g i n e e 咖g ，k e ) ，通过手工定义一些规则来进行分类，显然这种方法 费时费力、效率低。到上个世纪九十年代，随着网络的迅猛发展和机器学习的兴起，形 成了各种文本自动分类( a u t o m a t i ct e 氟c a t e g 耐刎。玛a t c ) 技术1 2 4 1 。 文本自动分类是指利用计算机程序，根据指定文本的内容自动地确定其和预先定义 的类别之间的隶属关系阳。文本分类系统首先通过在预先分好类的文本集上进行训练， 建立一个判别规则或分类器，从而对未知类别的新样本进行自动归类。很显然，分类是 一个有监督学习( s u p e 州s e dl e a m i i l g ) 的过程。 从数学角度来看，文本分类是一个映射过程，它将待分类文本映射到已有的类别中， 该映射可以是一对一映射，也可以是一对多的映射，因为一篇文本可以涉及多个主题。 数学描述如下： 厂：彳专曰其中，彳为待分类的文本集合，刀为分类体系中的类别集合，厂是映射 规则f 2 6 1 。 自动文本分类的映射规则厂是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判 别规则，确定文本所属的类别【2 6 】。 如图2 1 所示，文本分类就主要由训练过程( 也叫学习过程) 和分类过程两个主要 步骤构成1 2 6 1 。 x m l 文档分类方法的研究及其应用 2 2 文本分类主要技术 图2 。1 文本分类流程 f i g 2 1t e 嫩c a 绝g o r i z 砸o np r o c e s s 2 2 。1 文本预处理 数据预处理在数据挖掘过程中起着不可替代的作用，在有些情况下，数据预处理甚 至是决定数据挖掘算法表现好坏的关键因素。在文本分类中，数据预处理的主要任务是 剔除文本中所有与分类任务无关的内容，并将文本转化为由其包含的基本语义单位组成 的表列。 文本预处理要完成的主要任务就是分词，分词的关键在于如何选择恰当的基本语义 单位。在西文文本分类研究中，通常将单词作为基本语义单位。以英文文本分类为例， 在预处理时把空格、标点符号等非字母字符作为分隔符，就可以方便地将文本转化为由 单词组成的表列。通常忽略大小写对单词语义的可能影响，如认为a u t h o r 和a u t h o r 是相 同的；有时也会考虑对词根进行处理，去掉单词的前后缀，将同词根的单词映射到一个 特征词属性，可以大大减少特征词的个数，如认为a u t h o r 和a u t h o r s 是相同的；还有些 情况下会对单词的语义进行处理，一种常用的简单方式是使用w o r d n e t 心7 1 定义的同义词 集合来比较单词语义的相似性。 与西文文本相比，中文文本没有类似于空格之类的标示词边界的标志，需要从连续 的汉字串中正确辨认汉语的词语，需要中文分词，而中文分词的结果将直接影响分类的 一6 大连理工大学硕士学位论文 效果。目前中文分词方面做得比较好的机构有哈尔滨工业大学和中国科学院计算机技术 研究所以及北京的海量科技公司，其中前两个机构的软件是开源的。中国科学院计算技 术研究所张华平博士等人开发的分词系统i c t c l a s ( h l s t i n l t eo f c o m p u t i n gt e c h n o l o g y ， c h i l l e s el e x i c 2 l l 锄甜y s i ss y s t e m ) 。该系统是一个具有中文分词、词性标注、未登陆词识别 等功能的软件。它采用统计方法和规则方法相结合的方式，融合了多种分词技术。使用 基于n 最短路径的方法对中文文本进行无歧义文本初切词，然后通过多层马尔可夫模型 算法进行未登陆词识别，取得了非常好的分词效果。系统分词的准确率高达9 7 以上， 未登陆词识别召回率高达9 0 ，分词和词性标注处理速度为3 1 5 k b s 冽。 不论是西文文本还是中文文本，通常一篇文章的内容主要是通过动词、名词和形容 词等实词来体现的，虚词以及在各种文章里都经常出现的高频词对分类来说没有意义。 因此，在特征选择时都要去除常用的停止词，停止词包括虚词、代词、高频词等，目前 已有通用的中英文停止词表可以使用。 2 2 2 文本表示 人通过学习一门语言，就可以具有一定的阅读能力，再结合自身的理解能力和已掌 握的知识就能对阅读内容产生模糊的认识。目前，计算机尚未具有这种智能，它并不能 轻易地“读懂”文章。因此，文本自动分类遇到的基本问题是如何将文本按照计算机可 以材理解”的方式进行有效的表示，从而在这个表示的基础上进行分类。常见的文本表 示模型有很多种，包括向量空间模型、布尔模型和概率模型等。 ( 1 ) 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 向量空间模型是由g s a l t o n 咧于1 9 6 9 年提出的，是目前使用最广泛的文本表示模 型。在第一章中已经提到过它，其基本思想是：将每个特征作为特征空间坐标系的一维， 用特征空间的向量来表示文本，并用两个向量之间的夹角的余弦值来衡量对应的两个文 本间的相似度。在向量空间模型中，每个文本都被形式化为n 维空间中的向量，因此可 以将文本抽象化为公式( 2 1 ) 所示。 y ( d ) = ( w ( f 。) ，w 0 2 ) ，w ( f ，) ，w o 。) ) ( 2 1 ) 其中，矗是特征项，m 为文本空间的维数，w ( 岛) 是函数，其基本功能是计算特征项岛 在文本向量中的权重。近年来，文本自动分类中使用较多的权重计算方法包括布尔权重、 词频权重、万幸尼矿权重、乃权重、上形权重和熵权重等。其中，卵凹旷权重是 在文本处理领域中使用最广泛的数值权重计算方法。该方法基于以下原因：一是特征如 在文档歹中出现次数越多，越重要；二是文档集中含有特征的文档数越多越不重要。 诅。文档分类方法的研究及其应用 弦上d f 方法基于的思想和构造的统计量都很简单，并且在实际应用中表现了很好的性 能。它有多种计算方法，目前较为常用的为式( 2 2 ) 。 f = 厶l o g ( = ) ( 2 2 ) 。 。 其中，f ，表示特征岛在文档，中出现的频率，肌为文本集合中文本的总数，为特征 硅文本集合中出现的总次数。 ( 2 ) 布尔模型( b 0 0 l e a nm o d e l ) 布尔模型在传统的信息检索领域中有广泛的应用，它通过与用户给出的检索进行逻 辑比较来检索文本，是一种基于关键词的匹配。布尔模型采用布尔表达式对文本进行表 示，在标准的布尔模型中，文本采用如下式( 2 3 ) 表达形式： 吐= ( 嵋1 ，m 2 ，w f 一) ，七= l ，2 ，聆 r ，气、 其中：刀为特征项的个数，w 请为0 或1 ，表示第七个特征项在文本f 中是否出现。 布尔模型易于实现，但在文本分类领域，它的准确率和召回率较差。在对舭文档的 路径进行特征表示时，文献 1 2 ，1 7 就是使用的布尔模型。 ( 3 ) 概率模型( p r o b a b i l i s t i cl n o d e l ) s t e p h e nr o b e r t s o n 和s p a r kj 0 n e s 等人1 2 州提出的概率模型也得到了广泛认可。该模 型综合考虑了词频、文档频率和文档长度等因素，把文档和用户兴趣( 查询) 按照一定的 概率关系融合。概率模型有多种形式，常见的一种是贝叶斯概率模型，它用概率架构来 表示特征项，将训练实例分解为特征向量和决策类别向量，并且假定特征向量的各分量 独立地作用于决策变量。虽然这个假设在一定程度上限制了贝叶斯概率模型的适用范 围，然而在很多领域即使违背这种假定的条件下，该模型也表现出相当的健壮性和高效 性，已经成功应用到信息检索、分类和聚类等领域中【2 s 1 。 2 2 3 特征降维 在进行文本预处理后，得到了由文本转化成的基本语义单位组成的表列。虽然在文 本预处理过程中，已经做了去除停用词等剔除文本中所有与分类任务无关内容的一系列 处理，但是特征向量的维数仍然很高。无论采用什么样的文本表示模型，中等规模的文 本分类问题所对应的原始特征集通常都高达几万维、甚至十几万维。高维会大大降低机 器学习的效率，而学习的效果并不比小的多的特征子集的效果更好。因此我们需要进行 特征降维，使得在不显著牺牲分类准确度的情况下，去除文档中信息量小、相关度低的 项以降低特征向量的维数。这样做是基于两个方面的考虑：一是如果直接在这样一个高 大连理工大学硕士学位论文 维特征空间上进行训练和分类，计算量过大，降维可以提高程序的执行效率和运行速度； 二是所有词条对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词条对 分类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词条对文本分类的 贡献大，降维可以提高分类器的推广能力1 2 6 j 。 特征降维主要有两种方法，一种方法是从原有特征词集合中挑出最有效的特征构成 新的特征向量，这个过程叫做特征选择( f e a n 盯es e l e c 廿o n ) ，还有一种方法是将高维特 征向量映射( 一般为线性映射) 到低维空间，这个过程叫特征提取( f e a ：c l l r ee ) 浙a c t i o n ) 。 下面分别介绍着两种方法的具体使用方法。 ( 1 ) 特征提取( f e a ：t i 】r ee x 的c t i o n ) 特征提取也叫特征重参数化。由于自然语言中存在大量的多义词、同义词现象，特 征集无法生成一个最优的特征空间对文本内容进行描述。特征提取是将原始特征空间进 行变换，重新生成一个维数更小、各维之间更独立的特征空间，可以看作从测量空间到 特征空间的一种映射或变换。其主要的方法有特征聚类、主成分分析和潜在语义标引等。 在对l 文档的特征提取时，有很多方法使用的是就是特征聚类的思想，如查找舰 文档结构特征中的频繁路径和频繁子树1 2 0 翔】，将频繁路径和特征子树抽取出来作为要进 行比对的特征，在挖掘频繁路径或频繁子树是可能会用到聚类方面的算法。 ( 2 ) 特征选择 特征选择是从特征集r = 琶，乞，) 中选择一个真子集r = 毡，f 2 ，t t ( s 。s ) ，其中， s 为原始特征集的大小，s 为选择后的特征集大小。选择的依据是特征对分类作用的大 小，通常是一个统计量来度量。特征选择没有改变原始特征空间的性质，只是从原始特 征空间中选择了一部分最有代表性的特征，组成一个新的低维空间【3 0 】。特征选择常用的 方法包括文档频率( d o c 砌e n t 舶q u e n c y ，d f ) 、信息增益( h f o n n a t i o ng a 地i g ) 、z 2 统计 法( z 2 - 钯瓯c h i ) 、互信息( m u n l a l 幽m 撕呱m i ) 、术语强度( t e n ns _ 鼢酏t s ) f 3 l ，3 2 1 。 本文在进行) ( m l 文档结构向量化时使用特征选择进行特征降维。凡是特征选择，总 是在将特征的重要程度量化之后，通过设定一个阀值丁把那些度量值小于阀值丁的特征 过滤掉，剩下的就认为是有效特征。这样，如何量化特征的重要性，就成了各种方法间 最大的不同。下面简单介绍几种常用的方法。 ( 1 ) 文档频率( d o c 嘞e n t 行e q u e n c y d f ) 文档频率是最简单的特征选择方法，它就是统计文档集合中出现某个特征项的文档 数目d f ，然后根据预先设定的阀值删除那些文档频率特别低和特别高的特征项。它是基 于这样的假设：当d f 值小于某个阀值时，该特征就是稀有特征，就认为它们不含或含 有较少的类别信息，对整个分类的效果影响很小，因此可以将这些特征删除来降低特征 一9 一 沮，文档分类方法的研究及其应用 空间维数，并且当这些稀有特征为噪音时，还会有助于提高分类正确率。这种特征选择 方法计算复杂度较低，随训练集的增加而线性增加，因此，能够适用于大规模语料。但 有时稀有特征也可能包含着重要的判断信息，这时就不符合上面的假设，如果简单地舍 弃，就可能会影响分类器的精度。本文在对) ( m l 文档结构基于路径特征向量化时就考虑 到了这个问题，因此将路径特征在某类文档中出现的频率作考虑在内，在第三章将详细 介绍。 ( 2 ) 信息增益( i n f o m a t i o ng a hi g ) 在信息增益中，特征重要性的衡量标准就是看特征能够为分类系统带来多少信息， 带来的信息越多，该特征越重要。它定义为某一特征在文本中出现前后的信息熵之差， 即该特征为该类别提供的信息量的大小。换言之，信息增益就是看一个特征，系统有它 和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即增益。 信息增益评估函数定义如下式( 2 4 ) 。 ： d ic ； 麟。) = 讹) l o g 盹) + 尸也) 以q 川o g 地l 如) ，- lf 1 一盟 一一 i + p o k ) p ( c ，l “) l o g p jl 气) ，- 1 ( 2 4 ) 其中，p ( 气) 为训练集中出现特征攻的文本数除以训练集的文本数，p ( 以) 为训练集 中不出现特征气的文本数除以训练集的文本数，尸( c ，帆) 为类别c j 中出现特征f 。的文本 数除以训练集中出现的文本数，以c ，i 气) 为类别c ，中不出现特征气的文本数除以训练 集中不出现，。的文本数。 从信息增益评估函数中可以看出，信息增益考虑了特征出现和不出现两种情况，是 比较全面的，因而效果不错。但信息增益最大的问题就是它只能考察特征对整个系统的 贡献，而不能具体到某个类别上，这使得它只适合用来做所谓的“全局”特征选择( 指 所有类使用相同的特征集合) ，而无法做“本地”的特征选择( 每个类分别有自己的特 征集合) 。本文在对m 文档结构特征向量化时使用的就是信息增益方法选择特征路 径，这将在第三章中将详细讲述。 ( 3 ) z 2 统计法( z 2 - t e s t ，c ) c h i 的基本思想就是通过观察实际值与理论值的偏差来确定理论的正确与否。它是 使用特征与类别间的关联性来进行特征重要性的量化，关联性越强，特征得分越高，该 特征越应被保留。它是基于这样的假设：认为词条与类别之间符合z 2 分布，词条的z 2 统 大连理工大学硕士学位论文 计量表示词条对某个类别的贡献大小。z 2 统计量越高，词条和类别之间的独立性越小、 相关性越强，即词条对该类别的贡献越大。词条i 对应类别，的z 2 统计量的计算如公式 ( 2 5 ) 。 v2 一 翌兰! 堡! 兰丝2 2 = 刍2 兰丝212 ： “ ( 1 十，z 1 2 ) x ( 以2 l + ，2 2 2 ) ( 甩l l + 吃1 ) x ( 碍2 + 吃2 )( 25 ) 其中甩小，2 小即2 ，和，功分别表示词条f 在类别歹中出现的频数、词条f 在类别外 的其它类别中出现的频数、除词条f 外的其它词条在类别，中出现的频数、除词条f 外 的其它词条在除类别，外的其它类别中出现的频数，刀为所有词条的频数总和。z 2 统计 量用来度量词条和类别间的关联性，使得它在特征削减中非常有用。对每一对词条和 类别都计算石，2 的值，并按照降序排列，去除排在后面的特征勰】。 以上方法各有利弊，文献 3 3 】对文本频度、互信息、信息增益、z2 统计等特征选择 方法进行了比较，结果显示，文本频度、信息增益和z2 统计要优于互信息，而且文本 频度、信息增益和z 2 统计之间存在很大的相关性。文献 3 4 对文本频率、信息增益、互 信息、z2 统计、期望交叉熵、文本证据权、几率比等特征选择方法进行了比较，结果 显示，对几率比方法进行扩展的多类几率比方法分类效果最好。文献 3 5 】对互信息、z 2 统计、期望交叉熵、文本证据权等特征选择方法进行了比较，结果显示，互信息方法效 果最优。从上述研究看，没有哪种方法对分类效果有绝对优势。这是因为文本分类涉及 到训练数据集合本身的特点，同时不同的分类器对文本分类的效果也不尽相同f 2 6 j 。 2 3 常用分类算法 在介绍具体的文本自动分类算法之前，首先应该明确说明一下文本分类体系。分类 体系是指事先确定的类别的层次结构以及文档与这些类别之间的关系，包含以下两个方 面： ( 1 ) 类别之间的关系 一般来说类别之间的关系都可以表示成树形，也就是说一个类有多个子类，而一个 子类唯一属于一个父类，这种类别体系很常用。但是，由于现实世界中一些概念和领域 是交叉的，如“临床心理学 这个类别应该既属于“心理学 的范畴，也同时属于“临 床医学刀的范畴，但在分类系统中却不便于使用这样的结构。 ( 2 ) 文档与类别间的关系 一般情况下，如非特别指明，分类算法都假设一篇文档唯一属于一个类别( 更严格 的说，是在同一层次属于一个类别，显然也属于这个类别的父类别) ，这使得我们只用 沮。文档分类方法的研究及其应用 一个标签就可以标记这个文档的类别。但现实生活中确实存在一个文档属于多种类别的 情况，如“体育明星的新闻 既属于“体育新闻”，也可以划分到“明星的新闻，这 是合情合理的。实际应用中多标号问题非常普遍，并且已有- 定的研究成果。 文本分类的研究可以追溯到上个世纪六十年代，早期的文本分类主要是基于知识工 程( k n o w l e d g ee n 西n e e r i n g ，k e ) ，通过手工定义一些规则来进行分类，显然这种方法 费时费力、效率低，并且需要有较好的专业领域知识。到上个世纪九十年代，随着网络 的迅猛发展和机器学习的兴起，形成了各种文本自动分类( a u t o m a t i c t e x t c a t e g o r i z a t i o 玛 a t c ) 技术【2 4 1 。这类方法是基于统计的方法，其基本思路是先搜集一些与待分类文本同 处一个领域的文档作为训练集，并由专家进行人工分类，保证分类的准确性，然后分析 这些已经分好类的文本，从中挖掘关键词和类之间的联系，最后再利用这些学到的知识 对文本分类。这种方法具有较好的理论基础、简单的实现机制，以及较好的文档分类质 量等优点，目前实用的分类系统基本上都是采用这种分类。根据分类结果的不同，分类 算法还可以分为二分类和多分类两种。 本文研究的) 眦文档分类问题范围是对单标号的) ( m l 文档分类进行研究，并且类别 之间没有交叉。下面就分别介绍几种常用的文本分类算法，这些算法也和本文研究的分 类问题在同范畴之中。 2 3 ，1 k 最近邻法 k 最近邻法( k n n ) 【3 6 】是由c o v e r 和h a n 于1 9 6 8 年提出的，是典型的排序分类 ( r 硼| l ( i n gc a t e g o r iz a _ t i o n ) 算法。排序分类算法在一次判断后可以输出文档属于多个类 别的得分，假设得分越高则越有可能属于这个类别。使用k n n 进行分类时，当一个待 分类文本到达时，计算它与训练样本集中每个文本的相似度，找出k 个最相似的训练文 本，并记录其所属类别。在此基础上给每个文本类打分，分值是k 个训练文本中属于该 类的文本与测试文本之间的相似度之和，然后按分值进行排序。同时选定一个阎值，分 值超过阀值的类才予以考虑。形式化表示为公式( 2 6 ) 幽j 。 ( d ，g ) = 聊( d ，嘭) y ( 办，g ) 一钆 d q ( 2 6 ) 其中，少( j ，c ) = 艺：麓，以为阀值，& 加( 么妙为文本d 和巧的相似度，八玩c 七) 为文本j 属于类别q 的分值。 阳州是目前精度较好的分类器之一，并且实现简单，在第一章也提到过很多基于 相似度对x m l 文档分类时都使用的是k n n 。 大连理工大学硕士学位论文 2 3 2 朴素贝叶斯 朴素贝叶斯分类方法( n a 知eb a y e s ，n b ) 基于贝叶斯定理，其实质仍然是首先利用贝 叶斯条件概率公式，计算在已知文本文档的特征向量的条件下，该文档属于不同文本类 别的条件概率( 即后验概率) ；然后，依据最大似然原理将该文档归结为具有最大后验概 率的那一类。它的前提假设是在给定的文本类语境下，文本属性的分布是相互独立的。 假设d 为一任意文本，它属于文本类别c = ( c l ，c ：，c 埘) 中的某一类，c ，根据朴素 贝叶斯分类法，则有公式( 2 7 ) 和公式( 2 8 ) 【2 引。 t 、，、尸( c f ) p ( d lc f ) 尸ei 刃= = 筇产 ( 2 7 ) p ( d ) = p ( q 妒( d l q ) “ ( 2 8 ) 上式表示在给定的文档d 的条件下，d 属于类别c ，的概率( 即后验概率) 。所以，分 类问题就转化为计算尸( q 忉的值，使p ( g 忉取得最大值的那个类别就是d 所属的类别。 对所有的类别来说，尸( c i ) 是相同的，则分类问题就成为求0 ，如公式( 2 9 ) 所示f 2 8 1 。 尸(