（计算机应用技术专业论文）基于综合评价理论的多分类器容器.pdf

大连理工大学硕士学位论文 摘要 分类是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的是提 出一个分类函数或分类模型( 也常常称做分类器) ，该模型能把数据库中的数据项映射 到给定类别中的某一个。大量的统计方法和机器学习方法被应用于自动文本分类。自动 文本分类分为三个过程：首先对文本进行预处理，将文本数字化；接着构造并训练分类 器：最后用分类器对新文本进行分类。 本文根据对以往传统的分类方法的研究，特别是每一个分类器对于不同类别的区分 程度不同，提出一种基于综合评价理论的多分类器综合方法，旨在利用各个子分类器对 于不同类别的区分度不同，互相取长朴短，评价模型使用了线性加权模型，把多个分类 器综合和在一个容器内。训练过程参照了优化理论中的直接搜索方法。形成一个容纳多 个分类器的容器。文本预处理过程中，首先通过对几种特征抽取方法的比较，选取一种 最适合本系统的方法；其次选取一种合适的权重计算方法，最后把文本表示成向量的形 式。在分类器的训练过程中，首先构造了四个子分类器，利用复旦大学提供的语料进行 测试分析，再根据综合评价理论构造分类容器，对分类容器进行训练时，得出各个子分 类器的类别权值，即权值矩阵。分类器测试时，先用子分类器对文本进行判别，再利用 权值矩阵，运用集值迭代的方法进行加权求和，最后取和最大的类做为类别归属。 这个容器是各个分类器的一个优化的组合，实验结果表明，这个容器确实得到了比 较理想的分类效果。本文中用到的方法有s v m 分类方法、贝叶斯分类方法、简单向量 距离法和多组判别分析法。 关键词：分类：容器：综合评价 基于综合评价理论的多分类器容器 c l a s s i f i e rc o n t a i n e rb a s e do n i n t e g r a t i o ne v a l u a t i n g m e t h o d a b s t r a c t c l a s s i f i c a t i o ni sav e r yi m p o r t a n tt a s ki nd a t a - m i n i n g ，a tp r e s e n ti ti su s e dm o s t l yi i l ： c o m m e r c e r n l ea i mo fc l a s s i f i c a t i o ni st oa d v a n c eac l a s s i f i c a t i o nf u n c t i o no rc l a s s i f i c a t i o n m o d e l ( a l s on a m e dc l a s s i f i e r ) n l i sm o d e lc a nm a p t h ed a t ao f d a t a b a s et oac e r t a i nc l a s s al o t o fs t a t i cm e t h o d sa n dm a c h i n el e a r n i n gm e t h o d sa r eu s e dt oc l a s s i 命t e x t sa u t o m a t i c a l l y a u t o m a t i ct e x tc l a s s i f i c a t i o ni si n c l u d i n gt h r e ec o u r s e s ：f i r s to fa l l ，p r o c e s s i n gt h et e x t sa n d c h a n g e t h et e x t si n t od i g i t s ；n e x t ，c o n s t r u c t i n ga n dt r a i nc l a s s i f i e r ；a tl a s t ，c l a s s i f y i n gn e wt e x t s i nl i g h to ft h em v e s t i g a n o no f e x i s t i n gm e t h o d so fc l a s s i f i c a t i o n ，e s p e c i a l l ya c c o r d i n g t o t h ed i f f e r e n td i s t i n g u i s h i n gd e g r e eo fd i f f e r e n tc l a s s i f i e r ，ai n t e g r a t i o ne v a l u a t i n gm e t h o db a s e d o nd e c i s i o n - m a k i n gi sd e v e l o p e dt ot a k ea d v a n t a g eo f e a c hc l a s s i f i e r sd i s t i n g u i s h i n g d e g r e eo f e v e r yc l a s s a n dt h e y c a i ll e a r nf r o mo t h e r s ss t r o n gp o i n t st oo f f s e tt h e i r sw e a k n e s s o n t r a i n i n g i tr e f e r st oh o o k j e e v e sm e t h o d s e q u e n t i a l l yac l a s s i f i e rc o n t a i n e ri sf o r m e d ，i nt h ec o u i s eo f p r e p r o c e s s i n g , f i r s ti tc o m p a r e sm a n y m e t h o d so fa t t r i b u t ee x 时a c d o nt os e l e c tas u i t a b l eo n e s e c o n di ts e l e c t saf i t t e dw e i g h t - c a l c u l a t i n gm e t h o df o rt h i ss y s t e m ，a n dl a s ti tc h a n g e st e x t si n t o v e c t o r s o n t r a i n i n gt h ec l a s s i f i e r ，i tc o n s t r u c t sf o u rc l a s s i f i e r sf i r s t l y ，a n dt a k e s u s eo f m a t e r i a l s o ff u d a nu n i v e r s i t yt ot e s ta n da n a l y z e ，a n da d v a n c e sac l a s s i f i e rc o n t a i n e ra c c o r d i n gt o i n t e g r a t i o ne v a l u a t i n gt h e o r ys e c o n d l y ，w h e nt h ec o n t a i n e ri st r a i n e d ，i te d u c e s f l lp o w e rm a t r i x w h e nt h ec o n t a i n e ri sb e i n gt e s t 啦e v e r yc h i l d c l a s s i f i e rw i l lg i v ear e s u l t , a n dt h ec o n t a i n e r w i l lc o m p u t et h es l i mi nl i g h to ft h ep o w e rm a r xa n dt h eg i v e nr e s u l t s ，a n di ts e l e c t st h e m a x i m u ms u mo f a l lc l a s s e st ob et h ec l a s s t h i sc o n t a i n e ri sa l lo p t i m i z i n gc o m b i n a t i o no f d i f f e r e n t c l a s s i f i e r s ，g i v i n ga l l b e t t e rr e s u l t i nt h i sp a p e ri tu s e ss v mt e x tc l a s s i f i c a t i o n ，m u l t i - g r o u pd i s t i n g u i s h i n gt e x tc l a s s i f i c a t i o n ， n a a v eb y e st e x tc l a s s i f i c a t i o na n d s i m p l e v e c t o rd i s t a n c et e x tc l a s s i f i c a t i o n k e yw o r d s ：c l a s s i f i c a t i o n ；c o n t a i n e r ；i n t e g r a t e de v a l u a t i o n ， 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：鱼叠金鱼日期： 上毗、专、莎 大连理工大学硕士学位论文 引言 随着i n t e m e t 上文本数据的急剧膨胀，迫切需要- k 十技术帮助人们更好地发现、过 滤和分析文本信息资源。文本分类技术的研究引起了研究人员的极大兴趣。目前英文自 动分类已经取得了丰硕的成果，提出了多种成熟的分类方法，如最近邻分类、贝叶斯分 类、决策数分类方法以及支撑向量机( s v m ) 模型、向量空间模型( v s m ) 、回归模 型和神经网络等方法，但对于中文文本的自动分类技术研究尚不尽人意。目前国内中文 文本分类研究主要集中在朴素贝叶斯、向量空间模型和支撑向量机等技术上【1 】。 我们所说的文本分类都是基于内容的，文本分类是指在给定分类体系下，根据文本 内容自动确定文本类别的过程。2 0 世纪9 0 年代前，占主导地位的文本分类方法一直是 基于知识工程的方法，即由专业人员手工进行分类 2 】。人工分类非常费时，效率过低。 9 0 年代以来，众多的统计方法和机器学习方法应用于自动文本分类。分类体系一般人 工构造，也可以是层次结构，它可以应用在垃圾邮件的判定、新闻出版按照栏目分类、 词性标注、词义排歧、计算机论文的领域等诸多方面 3 】。文本自动分类涉及情报、人工 智能、计算机等诸多领域，迄今为止，分类方法众多。包括自动分类与聚类方法、基于 实例的学习分类方法和基于特征的元学习方法。自动文本分类分为三个过程：首先对文 本进行预处理，在文本分类研究领域，占统治地位的文本表示方式是s a l t o n 等提出的向 量空间模型，还有种表示方式是独立于语言的文本表示方式，即字符串方式( n - g r a m ) 。s a l t o n ( b o w ) 词袋方式表示文本通常包括分词、取词根、去功能词、统计词 频、选择特征、生成频数向量、赋权、规范化等步骤。字符串表示方式与词袋表示方式 的主要区别在于用“取字符串”代替了后者的“分词”、“取词根”和“去功能词”。 这里主要是利用向量空间模型将文本数字化【4 ；接着构造并训练分类器，分类器的表现 形式一般为模板形式；最后用分类器对新文本进行分类，根据不同的分类算法进行计 算，最后确定文本的类别归属。文本分类是中文信息处理的个重要研究领域，它在提 高信息检索的速度和准确率方面显得意义重大 5 】。其目标是在分析文本内容的基础上， 给文本分配一个或多个比较适合的类别，从而提高文本检索、文本存储等应用的处理效 率。目前已经有许多方法应用到该领域。如支撑向量机方法( s v m ) 、k 近邻方法 ( k n n ) 、朴素贝叶斯方法( b a y e s ) 6 ，7 、决策树方法( d e c i s i o nt r e e ) 等等。与这 些方法相比，将粗糙集理论用于分类有以下优点 8 】：能够获得分类所需的最小特征属性 集，可以在不影响分类精度的条件下降低特征向量的维数；可以得到最简的显示表达的 薹王堡垒堡竺墨堡塑童坌耋竖查量 分类规则a 而其他方法则有的无法褥到显示规则 9 】，如朴素贝叶斯方法和k 近邻方 法，有的得到的规则含有大量的冗余条件，如决策树方法。 中文文本分类的方式主要有基于外延和基于语意两种【l o ，后面将会详细介绍，这 里不再赘述。 2 大连理工大学硕士学位论文 1 绪论 1 1 文本分类的发展史 分类是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的是提 出一个分类函数或分类模型( 也常常称做分类器) ，该模型能把数据库中的数据项映射 到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从历史数据记录中自 动推导出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是， 分类的输出是离散的类别值，而回归的输出则是连续数值 1 1 。 自动分类是信息自动化处理中较为活跃的一个领域。早在5 0 、6 0 年代，i b m 的 l u h n 等人就展开了文献信息的自动分类研究。近年，o c l c 的s c o r p i o ne r o j o c t ，欧盟的 d e s i r e 等，利用传统的文献分类方法，如d d c 、u d c 、l c c ，对网络信息资源进行 分类组织和主题识别。国内的自动分类研究工作开始于8 0 年代初，经过2 0 年的发展， 已经有了一些比较有代表性的辅助归类和自动分类系统，如莫少强的计算机辅助图书馆 分类系统、苏新宁等人的汉语档案自动系统、刘开英的金融档案自动分类系统、金巍的 肿瘤学专业文献自动分类系统、王永成的计算机专业文献自动分类系统等等。这些研究 和成果表明，近期自动分类的研究趋向是以传统的文献分类体系为组织框架，构建一个 分类知识库( 或称分类器) 来实现信息的自动归类 1 2 ，1 3 。 长期应用于传统文献组织的文献分类法，经过多年实践已经建立起与其他分类法、 词表之间的兼容互换对应关系，发展成为一种可以有效组织信息的工具，即知识组织系 统( k o s ) 。利用这一知识系统来实现信息的自动标引和自动分类，已经成为目前信息 加工自动化的一个研究热点 1 4 ，1 5 。 根据知识库( 或分类器) 构建方法以及分类算法的不同，目前常用的该类型自动归 类模型可分为基于训练语料和基于人工标引经验两种 1 6 。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或 元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量，此外， 训练样本还有一个类别标记。 不同的分类器有不同的特点。有三种分类器评价的比较尺度：( 1 ) 预测准确度； ( 2 ) 计算复杂度；( 3 ) 模型描述的简洁度。预测准确度是用得最多的一种比较尺度， 特别是对于预测型分类任务，目前公认的方法是1 0 遍分层交叉验证法。计算复杂度依 赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此 3 基于综合评价理论的多分类器容器 空间和时间的复杂度将是非常重要的问题。对于描述型的分类任务，模型描述越简洁越 受欢迎 5 。 另外要注意的是，分类的效果一般和数据的特点有关：有的数据噪声大，有的缺 值，有的稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混合 式的。目前普遍认为不存在某种方法能适合于各种特点的数据。 在文本分类领域，一些多策略学习或综合分类机制的机器学习方法已被提出。如 c h a r t 和s t o l f o 提出的通过归纳学习，对区分数据的简单表决( s i m p l ey o u n g ) 和元学习 方法：l l i y l s r 等提出的层次化的多分类机制系统，执行超光谱数据分析的方法等等。这 些方法都是在合并多个分类机制的基础上提出的，每个分类机制是通过不同的分类学习 算法来实现的。 基于实例的学习分类方法是充分利用学习特定实例和规则来获取分类知识 1 0 ，解 决当前对象的分类问题。基于实例的学习分类系统，如a q l 5 ，该系统基于输入的实例集 合和假设，应用星算法( s t a ra g o r i t h m ) 产生类的最一般描述，它覆盖当前类的所有正面 实例，不包含任何反面实例 9 。然后，根据用户选择的质量评估标准，选择最好的假 设。最后，简化按理所产生的判断规则，以关系表形式输出。基于实例的学习分类方法 的目的就在于从训练集合中构建出一张分类表，或称作分类机制，该训练集合包含实例 文档和它们相应的类别。因为有很多类别，个文档可能被指派到不止一种种类中，此 时就可以把它分别指派到各个种类中。因此，通常会为每个种类建立一张分类表。在训 练阶段，训练集合中的文档通过一个学习算法为每个种类学习一张分类表。从每一种类 的训练集合中产生训练规则，这种学习的过程是可重复的。最终，在完成整个训练阶段 后，每个种类都将有一张通过学习得来的且不同于其它种类的分类表。 在训练阶段结束后，这些分类表将对未知文档进行分类。给定一个待分类的文档， 通过某一种类的分类表计算，可以得出一个分数，该分数用以表征该文档会被指派到该 种类的可信程度。特别地，当该分数高于某一种类的阀值时，该文档就会被归入该类 别；相反，低于阀值将会被拒绝。其它种类的分类表同样会对该文档作类似的计算。最 后，搜集所有分类表的决策结果，该文档就会被指派到若干种类中。 1 2 文本分类常用的方法 文本分类的方法主要包括人工方法和自动分类方法，这里使用的是文本的自动分类 方法，是机器学习的范畴，即训练学习的机制。目前文本的自动分类方法众多，比较流 行的方法有：s v m 方法、贝叶斯方法、人工神经元网络方法等，还有一些比较常用的方 4 大连理工大学硕士学位论文 法包括重心法、k 近邻法等，另外，也有时候用多组判别的方法进行分类。本文中分类 所用到的分类方法有s v m 方法、贝时斯方法、重心法和多组判别法。 ( 1 ) s v m ( 支撑向量机) 方法 支撑向量机建立在计算学习理论的结构风险最小化原则之上。其主要思想是针对两 类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误 率。而且s v m 一个重要的优点是可以处理线性不可分的情况 1 1 。 目前构造s v m 多类分类器的方法主要有两种：一种是以w e s t o n 在1 9 9 8 年提出的多 分类器为代表。该算法在经典s v m 理论的基础上，重新构造分类模型，通过s v 方法对 新模型的目标函数进行优化，实现多分类器，缺点是选择的目标函数过于复杂，计算复 杂度高。 另一种算法是通过多个组合多个二分类器来实现对多类分类器的构造。常见的有 “一对一”和“一对多”两种 1 2 。 + ( 2 ) 贝叶斯分类方法 坝叶斯学习理论利用先验信息和样本数据来获得对未知样本的估计，而概率( 先验 概率和条件概率) 是先验信息和样本数据信息在贝叶斯学习理论中的表现形式。如何获 得这些概率是贝叶斯学习理论的关键。贝叶斯密度估计研究如何根据样本的数据信息和 人类专家的先验知识获得对未知变量的分布机器参数的估计。这里使用的是简单贝叶斯 模型。 简单贝叶斯学习模型将训练实例，分解成特征向量和决策类别变量简单贝叶 斯模型假定特征向量的各分量相对于决策变量是相对独立的，也就是说各分类独立地作 用于决策变量。贝叶斯定理告诉我们如何通过给定的训练样本集预测未知样本的类别， 它的预测依据就是取后验概率最大的类别 1 3 ，1 4 。 ( 3 ) 重心法 重心法又称简单向量距离法。这种分类方法的思路十分简单，根据算术平均为每类 文本集生成一个代表该类的重心向量，然后在新文本到来时，确定新文本向量，计算该 向量与每类重心向量间的距离( 相似度) ，最后判定文本属于与文本距离最近的类 1 5 。 ( 4 ) 多组判别方法 多组判别中，最基础的问题是两组判别，两组判别分析上在费歇准则下为p 维空间 两点群寻找最优分割面。两组判别是在两组间建立一个线性判别函数式，根据两组已知 样本的“重心”求得一个判别指标，然后对待判样品的所属予以判别。而实际采用的多 5 - j ：综合评价理论的多分类器奔器 组判别分析4 ；是矬戎组n i j 判别晒数式，岍足采用贝叶斯m 【i ! | j ，它足把p 维空问划分为 甄不棚交的多个i 并：域，使锵刘的平均损失为最小。就计算方法1 i i 言，贝l i 十斯与费歇准则 略柯_ i 同，f l i 铂：统计蜚水一【：十h 同，即组内观测值分斫j 必须服从多维币态分币j ，备组的 协方差女h 阵没有i i 著差别。 1 3 分类方法的性能评估 如 计价豇过机器、爿办法得剑的义术分类器| j _ h ：能足j i 研究的个方向。般 的机； 学习算法对所学刊的数抛集钉过艘拟合( o v e r l i t t i n g ) 。f i 粜利用训练集评仙所学 列的分类器的准确仁 ：，将会得到。个过分乐规刚县柯误导性n 勺评估结聚。设恕个很简 啦的例子：假设有一纰洲练样小( x ，y ) 的i 瞰似往实数范之内慨r 的耿值和【0 ，1 】之 州。 不沦这j 1 1 样小址依赫”么两数帧，灿。，0 ，只婴定义函数，f x ，a ，= 船吖a 叫去拟合 返4 冀样点( 其中“_ 址待定参数) ，总能够找到个a 使洲缘谈藏为零。融然这样的“缎优 函数”不能j t - l , l 晰地代农原米的函数模型。这利t 模型虽然i ，j 以1 0 0 的拟合训练数损! ；身；， 但并小能对文小玳俩分类。m 为义水分类t 篮自两种贝雅的测试方法：臆交叉骏“e c v t ( kl b l dc r o s sv a l i d a t i o n ) 乖f 1 1 科( h o l d o u t ) 的力法。它们均柱给定数荆集叶f 随机抽取样 本划分数州ij 6 j 。 c k般川仵圾终建阢的分类_ ； | - h 或析数4 i l ；集的胤模很小的t 占况。( h 足指将书u 始数挪 集| 9 f f 机划分成a 个“彳i 相交的子集刷韶“融，州岛厂碗9 几& 一驴。 每个r 集f 门火小j 点木, t ；l l l ； j ，。般墩a 5 或 = l o 。一学习干测试分别进行a 次。在笫， 敬迭代， ? f | j 11 洲试集，l 余盼f 袋椰月n 二洲练分类撩。墩女次迭代i r 确分类数除以仞 始数捌小的样小总数n 勺、卜均“t f t ：为分类器的准确一眦曼爨。( k 一一j 以被重复多次。划 j f 次( 1 心，婴矬j ：f 柑个分类器。增加r e 复的次数意味z f 运行时问的增加_ 手h 分类准硫性的 改善。在独j l ：_ ，：f | 勺( k 小，数j ) l l ：集| j f j 记求次序足, - f l ：i , _ i j f ( , j ，这样褂剑的结果业加鬻观。保髓 ( 1k l l d o u t ) 力法川n 搬仞吱骀。f l - r f j 场合，或者多j 二5 0 0 0 条记录的数槲集中。保斟方法将 数妣集i 她机分为埘个独。啦的绥合：训练数引缘和测试数捌集。通常l k2 朋的数圳作为训 练数粥集。利j 删l l 练数捌架的数捌进行特 i l ! 选择和分炎器洲约；，f 毗i ta , 自l 试数始集列浚分 类器的准确二杠进 j ：评仙。 第，类的准确率( 以) ：准确二缸足所钠输入系统进 j ：分类处弹的文本中与弩家分类 绌姒兜全吻仑的殳小所 的比率【1 7j ，i e 数母公表示蜘i 式( 1 1 ) ： j 1 ) = 上1 0 0 ”， 6 大连理工大学硕士学位论文 其中0 为第j 类分类正确的文本数，而吩为分类系统实际分类为，的文本数。 第，类的召回率( 弓) ：召回率是应有文本中分类系统分类正确的文本所占的比 率，其数学公式表示如式( 1 2 ) ： ( 1 2 ) 其中0 为第，类分类正确的文本数，而协为专家分类为，的文本数。 第，类的日值( f l p ：也称之为综合分类率，其数学公式如式( 1 3 ) ： p r x 2 f 1 ，= 。壬- ( i 3 ) 。p 。+ r ? 4 其中p ，为第，类的准确率，马为第，类的召回率 文本信息检索国际会议t e e c ( t e x tr e t r i e v a lc o l f f e r e n c e ) 每年举办一次文本过滤比 赛 1 6 ，在准确性评估中考虑了各种分类情况的代价( 即权值) 。检出相关的文本和未检 出不相关文本都属于过滤正确的情况。其余两种情况是：检出不相关的文本意味着错 检，而未检出相关文本意味着漏检。不同分类情况对于准确性评估的重要程度不同，对 它们赋予不同的权值。 构建文本分类器的最终目的是商业应用，除了关心分类准确性外，对分类速度也是 应该考虑的。从用户角度看，在尽可能短的时间里准确分类是很重要的。手工分类的准 确性很高，但手工分类的时间也很长。有些分类算法理论上能达到很高的分类准确度， 但其时空开销是超指数次幂的，是一个n p 难问题。如果文本分类花费的时间很长，则 手工分类和自动分类的效果一样，甚至准确性还不如手工分类。例如，利用贝叶斯网 络构建文本分类器，理论上可达到很高的分类精度，但学习完全的贝叶斯网络是n p 难 问题。朴素贝叶斯分类器n b c ( n a i v eb a y e sc l a s s i f i e r ) 和树扩展贝叶斯朴素分类器 t a n c ( t r e ea u g m e n t e dn a c v eb a y e sc l a s s i f i e r ) 是贝叶斯网络分类器b n c ( b a y e s i a n n e t w o r k sc l a s s i f i e r ) 的近似，虽然它们的分类精度有所降低，但时间空间开销也降低 了，在实际中得到了广泛应用。北京大学于2 0 0 3 年3 月举办第一届网页分类比赛，评 估文本分类器性能的指标是查准率和分类效率，没有考察查全率和训练分类器的时间为 根据测试结果所对应的得分，每个给定测试网页最多可分两个类别；，? 为被测试网页总 7 oo x 、一 一一 足 基于综合评价理论的多分类器容器 数目；，为对测试网页分类所花费的时间。现有的准确性评估指标，关心的只是分类准 确率。单从准确性评估的数值上不能武断地评价系统的优劣 1 7 。 有时要用到开放测试和封闭测试来评估文本分类器。封闭测试是指用于训练和测试 的数据集是一样的，而开放测试两者不一样。在实验中本文发现不同的数据集在封闭测 试下，结果相差较大，但开放测试和封闭测试的比值是稳定的。 1 4 课题涉及的主要研究内容 本课题的目的是增加对文本分类的精确度，利用各个分类器的优势，补偿其他分类 器的劣势。掌握国际和国内分类系统研究的新动态，在总结前人工作的基础上，设计和 实现一个基于综合评价的多分类器容器系统模型。 系统的训练和分类都是基于文本的向量空间模型的，对综合评价思想的引入是系统 的一大特色。其基本思想是：对文本库进行预处理构成文本向量空间，在该向量空间上 进行分类器的训练；在钡4 试的时候，仍然把文本转换成向量模型，运用已有的分类器进 行分类。在分类器容器内，这里使用了四个基本的分类器，有s v m 、b a y e s 、多组判别 分类器和重心法分类器，根据综合评价的思想，按照线性加权综合法，训练生成一个综 合的分类器。在分类的时候，按照各个分类器的权值及分类结果，利用集值迭代法进行 判断新样本的类别归属。 在综合评价方法的基础上，各个分类器共同作用，互相取长补短，通过实验证明， 确实得到了一个较各个单一分类器性能高的分类容器。 1 5 论文的组织 全文分六章阐述了基于综合评价理论的多分类器容器的设计与实现： 第一章介绍了课题研究背景和分类系统的发展史，并阐述了分类系统常用的方法。 之后蜕明了本课题的主要研究内容。 第二章介绍了分类系统的通用体系结构，包括文件预处理模块、训练模块、分类模 块和测试模块，并对各个模块进行了详细的阐述和说明。 第三章对本文采用的分类方法进行了详细的介绍，对其实现原理进行了详细的阐 述，并对于其在具体应用过程中的实现进行了描述，同时分析了这种方法的优势。 第四章是系统的总体设计，包括系统的设计目标、设计思想和体系结构，并对整个 系统中的的各个模块进行了简要的说明。 第五章是系统的具体设计和实现，详细地介绍了系统的三个功能模块：文本库预处 理模块、分类器训练模块和分类器测试模块。 8 大连理工大学硕士学位论文 第六章为结束语，总结了课题的一些工作，并对系统的不足和下一步应该进行的改 进工作做了阐述。 9 基于综合评价理论的多分类器容器 2 文本分类过程 这罩所浇的文本分类是对文本的内容进行有指导分类。所谓有指导分类，是指预先 确定好文档的类别，同时对每个文档类都提供一批预先分好类的文档，称为训练文档。 根据训练文档确定文档类的表示。在实际分类的时候，将需要分类的文档依次与每个文 档类比较，确定最相似的一个或多个文档类。分类的标准不同，分成的类别不同。现在 统的分类标准是中图法，即中国图书馆分类法。现在简要列出其所分的类别。如表 1 1 ： 表1 1 中图分类体系 然而，根据实际语料内容，往往只取中图分类标准的一部分。文本分类的过程是一 致的，由于文本分类是属于概念机器学习部分，因此要对各个分类器进行训i 练，生成固 定的分类器，再对新的文本进行分类。具体的实现过程如图2 1 所示： 1 0 大连理工大学硕士学位论文 图2 1 文本分类过程 f i g 2 1c o u r s e o f t e x t c l a s s i f i c a t i o n 这里先简要介绍一下这个分类过程的每一个模块： ( 1 )文本处理：去掉h t m t 中的一些诅g 标记：去除禁用词以及词根还原：而对 于中文的文本，还要进行分词、词性标注和短语识别；词频统计；进行数据清洗即去 掉不合适的噪声文档或文档内垃圾数据。训练集中包括的诸多文本都是文字形式的，这 很难进行数学计算，因此要把文字形式的文本处理成数字表示的文本，也就是把每篇文 本都表示成向量的形式。在进行向量表示的时候，我们首先把文本进行分词，即把一每 篇文本都写成许多词的集合。根据每个词对于文本的重要性决定把哪个词作为该文本的 特征，每个特征都对应一个特征值，这样就把文本表示成了向量的形式。而词对于文本 的重要性和特征值的计算相应的有许多不同的方法。 ( 2 ) 分类器训练过程：利用训练集按照一定的方法进行训练的目的是要得到 一个分类器，而不同的方法得到的分类器的表现形式又各有不同。训练的过程主要是 根据所给定的训练集中样本的特征，确定各个类别的模板，从而生成一个概念，即拥有 哪些特征的文本属于哪一类。而测试时候所用的文本从本质上讲，应该是与训练集中样 本是同质的，否则测试结果将无法令人满意。所谓同质，是说具有相同特征的时候同属 于一个类别。 ( 3 ) 分类过程：文本测试的时候，首先要把文本转化成向量的形式，并与训练集中 各个向量的表现形式相同，即与训练集中所取的特征是相同的。然后送入分类器，进行 基于综合评价理论的多分类器容器 计算，根据各个不同方法的算法不同，计算的结果及判定方法也是各不相同的。在分类 器中进行计算的过程，其实质就是跟各个类别的模板进行比较的过程，从这些模板中找 到与待测文章特征相近的作为此文章的类别归属。 2 1 文本向量化 文本向量化包括三个步骤：文本分词，文本特征抽取和文本表示。 1 处理中文文本过程中，分词是第一步，这是因为： ( 1 ) 西文为拼音文字、汉语是表意文字； ( 2 ) 西文书面语言词与词之间有空格，而汉语词与词之间无空格； ( 3 ) 西方语言的同音词很少，汉语的同音词很多； ( 4 ) 西方语言多有形态变化，汉语缺少形态变化； ( 5 ) 西方语言语法已经形成规范，汉语语法尚未形成规范化： ( 6 ) 汉语的自动处理是多学科和跨学科的，需语言学成果： 由于中文不象西文那样词与词之间有空格，所以首先要对中文文本进行分词处理， 这在中文信息处理中是一个至关重要的工作，分词的准确性直接影响着系统的性能。 分词按一定的规范进行，1 9 9 8 年统一制定了信息处理用现代汉语分词规范，主 要包括： ( 1 ) 空格或标点符号是分词单位的分割标记； ( 2 ) 分词单位包括词和少量结合紧密、使用稳定的词组； ( 3 ) 五字和五字以上的谚语、格言等，分开后若不违背原义应予切分： ( 4 ) 结合紧密使用稳定的词组，分开后若违背原义或影响进一步处理，则不予切 分： ( 5 ) 惯用词、有转义的词或词组、略语、儿化的分词单位、外来词一律为分词单 位； 等等。分词以分词规范为准，还要考虑具体的应用环境等其它因素。 经过分词处理之后的文本是一个词串，而其中的每一个词都可能有多种词性和词 义，如何根据上下文确定每个词的词性就是词性标注所要做的工作。词性标注在分类系 统中是至关重要的，直接影响到分类的结果。词性标注有很多方法，基本上可分为基于 规则的方法和基于统计的方法两种。早期的标注工作多为基于规则的方法，效果一般； 后来采用基于统计的方法，正确率有了很大的提高。近年来，人们试图把两种方法结合 起来，使标注的效率有了更大的提高。 1 2 大连理工大学硕士学位论文 另外，还有一种快速的多模式匹配串算法，它主要是应用在实时汉语文本分类系统 的文本向量化中。多模式匹配串算法处理问题是根据建立在一个确定的分号集合上的 “模式串集合”p 以及“数据符号序列”t 。找出模式串集合p 中每一个模式串在数据 符号序列中所出现的位置。目前主要应用在实时信息检索系统和网络入侵检测系统。对 大量时效索引信息进行快速检索或在用户的工作事件序列或网络传输信息的数据序列中 检测可能出现的入侵行为或可疑信息的关键词 1 8 。 2 文本特征的抽取 6 0 年代末g e r a r ds a l t o n 等提出的向量空间模型( v e c t o rs p a c em o d e l ) ，为了把文本 表示成向量形式，首先要做的就是进行特征项提取，把文本表示成项的集合，然后根据 项的权重把文本表示成向量。 进行特征抽取的方法有很多，每种方法对于分类精度的影响有所不同，在这里做了 多种特征抽取方法的对比实验，包括：d f 方法，词和类别的互信息方法，信息增益 法，t e r m 的某种熵法，k l 距离法。这样抽取出来的词相当于一个词典，即相对于该训 练集的所有训练文本和测试文本所选取的特征都必须是这个词典中的词。 构成文本的词的数量非常之大，导致了表示文本的向量空间的维数也相当多，可以 达到几万维，因此我们需要对文本进行降维。降维技术有两类：特征选择和特征重构。 ( 1 ) 特征选择。它是指去除不能表示信息的词，以提高分类效率和减少计算复杂 度。特征选择有以下几种方法：根据词的文档频度( d f ) 来判断：当词的d f 小于或者 大于某个阈值时都要去掉；根据信息增益( i g ) 来判断：信息增益是指词为整个分类 所能提供的信息量，当信息增益小于某个预定的值时，就要去掉这个词；根据x 7 统计 来判断：x 。越大词和类之间的独立性越小。相关性越大，所以去掉x 。小的词：根 据互信息( m i ) 来判断：互信息越大，两个词之间的共现性就越大；根据词的强度( t s ) 来判断。通过试验证明，前三种更加有效e 1 9 j 。 ( 2 ) 特征重构。它是通过合并或转化原特征构造新特征，以此达到降维的目的。这 里介绍一种特征重构方法：隐性语义索引( l s i ) 。l s i 假设文档中有一些潜在的词结 构，并使用一种统计技术奇异值分解( s v d ) 来估计这个结构。 奇异值分解( s v d ) ：4 = ( a i i ) = u z 矿，其中a 为m x n 的矩阵，m 为单词的个数， 为文档的数目；u 为m 姗，v 为nx r 的正交阵，三为rx 足的对角阵，丑砩 n 似加。取三对角上的前七个元素，得五，a = u k 五7 。u k ，斥分别由u 和v 的前k 列组成。从某种意义上说，a t 有着a 潜在的绝大部分结构，同时去除了噪音和可变性。 矩阵魄三k 加第i 行和矩阵坛互加第k 行的余弦反映了词i 和文本k 之间的相关 1 3 基于综合评价理论的多分类器容器 性。将一个新文本与训练集中的文本做比较后，我们得到文本向量d 对应的重构= d 。己kj x 7 。这样，一x 和圪厶的行之间的余弦就体现了新文本与训练样本之间的 相似度。 采用f o l d i n 9 2 i n 方法和s v d 2u p d a t i n g 方法可避免在已有的s v d 模型中增加新的词 或文本时重新计算词一文档矩阵的s v d ，因为如果重新计算词一文档矩阵的s v d ，会浪 费大量的时间并受到内存的制约。但f o l d i n 9 2 i n 方法容易使新词丢失或被错误地描述， 而s v d 2 u p d a t i n g 方法的时空特性都比前者更复杂 2 0 。 把文本用向量模型表示出来，由于计算机最基本的功能是用来进行数学运算，那 么，对文本的处理之中，必须要把文本用一种数学的方式表达出来，普遍采用的是向量 表达形式。 这里首先介绍几个与向量空间模型相关的概念： ( 1 ) 文档：泛指一般的文献或文献中的片段( 段落、句子组或句子) ，不要指一 篇文章。 ( 2 ) 项( t e r m ) ：当文档的内容被简单地看成是它含有的基本语言单位( 字、 词、词组或短语等) 所组成的集合时，这些基本的语言单位统称为项，即文档可以用项 集( t e r m ) 表示为”d ( 五，正，正) ，其中l 是项，l s k s ”。 ( 3 )项的权重( t e r mw e i g h t ) ：对于含有n 个项的文档d ( 互，墨，瓦) ，项i 常 常被赋予一定的权重暇。表示它们在文档中的重要程度， 即 d = d ( 正，；疋，；，睨) ，简记为d = d ( 彬，k ) 。这时我们说项瓦的权重为 ，1 k ”a ( 4 ) 向量空间模型( v s m ) ：给定一文档d = d ( 正，彬；疋，；7 ： ，) ，由于瓦在 文档中既可以重复出现又应该有先后次序的关系，分析起来仍有一定的难度。为了简化 分析，可以暂不考虑瓦在文档中的先后顺序并要求正互异( 即没有重复) 。这时可以把 正，正，l 看成一个门维的坐标系，而彤，为相应的坐标值，因而 d ( 啊，) 被看成是n 维空间的一个向量。我们称( 彬，呒) 为文档d 的向量 表示 2 1 。 如上定义，文本表示成一串词之后，与抽取出来的特征进行比较，若存在特征，则 计算相应的特征值。这样，那些不在特征词典里的词就被滤掉了，也相应地缩小了文 本。而特征值的计算也有很多方法。包括：布尔权重计算方法，词频权重计算方法以及 t f i d f 权重计算方法等。而布尔权重虽然表示简单，但权重所包含的信息甚少，要想使 1 4 大连理：r 大学硕士学位论文 本。而特征值的计算也有很多方法。包括：布尔权重计算方法，词频权重计算方法以及 t f i d f 权重计算方法等。而布尔权重虽然表示简单，但权重所包含的信息甚少，要想使 分类准确，对于分类器的要求相应就会提高，如果权重包含的信息量大，对分类器的要 求就会减少一些。最后，我们用一连串的特征及对应的特征值所表示，每个文本表示成 一个向量，而整个训练集便形成了一个向量空问。空间的维数就是选取的特征数。 综上所述，文本向量化的过程如图2 2 所示： 图2 2文本的向量化 f i g 2 2c h a n g e t e x t si n t ov e c t o r s 2 2 分类器的训练 从数学角度来说，文本分类可以这样定义：设文档集d = ，d ，如，喀，两剧，预 定义类集c = 心 c 2 , c i , 。c 旧，确定任意一个元组付，c i ) 映射到集合，f ，上 的值，故文本分类器实际上就是这样一个函数中：d c 仃，f ，。按照这个定义，训 练过程就是寻找映射函数中的过程，即形成分类策略 2 2 3 。 分类器的训i 练是充分利用学习特定实例( 训练集) 和规则来获取分类知识，解决当 前对象的分类问题。这种基于实例的学习分类系统，最终将产生类的最一般描述，它覆盖 当前类的所有正面实例，不包含任何反面实例。然后，根据用户选择的质量评估标准， 选择最好的假设。最后，简化整理所产生的判断规则。 基于实例的学习分类方法的目的就在于从训练集合中构建出一个规则或称作分类 机制，该训练集合包含实例文档和它们相应的类别。在训练阶段，训练集合中的文档通 过一个学习算法为每个种类学习个模板。从每一种类的训练集合中产生训练规则这种 学习的过程是可重复的。最终，在完成整个训练阶段后，每个种类都将有一个通过学习 得来的且不同于其它种类的模板。 在训练阶段结束后，这些分类表将对未知文档进行分类。给定一个待分类的文