（计算机应用技术专业论文）基于相对特征的文本分类算法研究.pdf

摘要 随着计算机技术、通讯技术和网络技术的飞速发展，i n t e m 武应用的日益普及，电 子文档的数量逐日剧增。为了更好地利用这类非结构化数据资源，人们迫切需要构建高 效的文本检索、查询和过滤系统，而文本挖掘正是实现这些系统的关键技术。 文本分类作为文本挖掘的一个重要问题，其研究一直受到关注。目前已经有许多方 法应用到该领域，如朴素贝叶斯、支持向量机、k 近邻、神经网络等。其中，朴素贝叶 斯利用先验信息，能够在不确定性的推理中提供一种模式和处理方法，它易于实现、工 作效率高，有着广泛的应用。神经网络具有学习能力和容错特性并且无须就概率模型作 出假定，是目觚较为流行的方法。然面，在应用到文本分类上时，基于朴素贝叶斯的分 类算法无法体现语义关系，普通神经网络的准确率不高。针对上述情况，本文主要做了 下面的工作： ( 1 ) 介绍文本分类中常见的几种算法之后，重点研究两种经典的算法朴素贝叶 斯和自组织特征映射网络。通过查阅文献和实验对这两种算法进行详细的分析和比较。 ( 2 ) 本文基于“分而治之”的双层聚类的思想，结合这两种算法各自的特点，提出 相对特征和相对闽值的概念，从而进一步提出一种新的文本分类算法基于相对特征 的文本分类算法，详细的介绍了该算法的分析、设计和实现过程。 ( 3 ) 分析并比较汉语语料库和英语语料库各自的特点，以及预处理时需要解决的问 题，并且详细的给出英语语料库预处理过程的方法以及预处理的结果，与此同时，对3 种算法应用到这两种语料库得到的不同结果，进行了比较与分析。 ( 4 ) 本文在汉语库和英语库上对三种算法进行实验分析，将本文新提出的基于相对 特征的文本分类算法与传统的朴素贝叶斯分类算法和自组织特征映射网络分类算法进 行了有效的比较。 实验证明，基于相对特征的文本分类算法取得了令人满意的效果，是一种高效的文 本分类算法。 关键词：文本分类：朴素贝叶斯；自组织特征映射网络：相对特征；相对闽值 东北师范大学硕士学位论文 引言 近十年来，报纸、电视、杂志、h l t 咖e t 等多种传播媒体将大量的、各种各样的信 息呈现在人们面前，特别是随着计算机技术、通讯技术、网络技术的飞速发展以及h l t e 卜 n e t 应用的f 益普及，以电子形式存在的数据总量急剧增长。i n t e m e i 卜- 的网页数量是考 察h l t e m e t 上的信息量的一项重要指标。根据不完全统计，当前1 1 1 t e m e t 上的网页数量 已经达到1 0 0 亿张至4 0 0 亿张左右，仅g 0 0 宙e 数据库存有的网页就高达4 2 ，8 亿张。根 据约翰罗斯提出的“新摩尔定律”，i m e m e t 上的信息量正以每六个月翻一番的速度爆炸 性地增眭。 目前，随着社会的日益信息化、电子化、自动化，越来越多的传统信息将以数字的 形式转化并保存起来，随之也就产生了大规模数据存储技术、数据仓库技术、数据挖掘 技术。为了更好地研究、开发这类电子信息处理的技术，首先需要认识其需要处理的对 象，即电子数据。总的来说，这些数据具有很强的异质性、多变性、无序性。有来自于 传统媒介的报纸、广播文本，有i t e m e t 上的超文本，也有企业、政府部门多年积累下 来的运行数据等等，形式多种多样。然而，根据其结构化程度的不同，仍可以将它们归 为以下三类： ( 1 ) 结构化数据：这类数据能够用统一的结构加以表示。例如在关系数据库中，可 以用不同的字段来表示一个事物的各种属性，然后将多个字段组织在一起构成表，而表 中的记录可以用来表示具有确定属性值的事物。不仅如此，人们还可以通过关键词来表 达各个表之间，即各个具体事物之间的多种关系。总之，这类数据具有定义良好的语法 和明确的语义。 ( 2 ) 半结构化数据：这类数据既不是完全结构化的，也不是完全无结构的。例如当 前得到广泛研究的x m l ( e x t e n s i o n a lm a r k u pl a n g u a g e ) 文档就是一种半结构化数据； 本文提到的r 肌t e r s 一2 1 5 7 8 语料库也是半结构化文档。 ( 3 ) 非结构化数据：这类数据是完全无结构的。例如：自由文本文档、音频数据、 视频数据等。非结构化数据处理起来难度较大。 从信息的存在形态来看，现实世界中，人们可以获取的大部分信息是存储在半结构 化或非结构化的文本文档中的。在现有的电子信息中，文本类信息就占8 0 以上，再 将大量的文本文档组织在一起，就构成所谓的文本数据库【2 j 。文本数据库中的文本文档 可以来自各种数据源，如新闻文章、研究论文、书籍、数字图书馆、电子邮件消息和 w e b 页面等等。当前，在h t e m e t 上已经出现为数众多的文本数据库，其中，对于结构 化的数据人们可以用结构化的查询语言查询得到所需要的数据和信息。例如，在关系数 据库中，人们可以使用s o l 结构化查询语言来查询所需的数据。然而，文本数据库中 东北师范大学硕士学位论文 1 1 文本挖掘简介 第一章文本挖掘中的分类简介 从海量的结构化信息中抽取、挖掘隐含信息和知识的方法以及途径，即数据挖掘技 术，现在已经相当成熟。而在实际生活中，随着i n t e m e t 的发展，在数字化信息中更多 地存在大量自由、半结构化或非结构化的文本信息，如，新闻文章、w e b 页面内容、e m a i l 等，手工处理几乎是不可能完成的，因而从文本中发现知识( k n o w l e d g ed i s c o v e r yi n t e x t s ，简称) t ) 的技术出现成为了必然，文本挖掘就是一种专门为解决这一问题而出 现的k d t 方法。 1 1 1 文本挖掘技术的演化 传统的信息检索技术对于海量数据的处理并不尽如人意，文本挖掘便日益重要起 来。可见文本挖掘技术是从信息抽取以及相关技术领域中慢慢演化而成的。早先的信息 抽取的例子是f r u m p 项目，由g e r a l dd e j o n g 【6 】于1 9 8 2 年设计。这个系统包含一系列 脚本，这些脚本能够扫描新闻专线网络，处理新的存档，以期提供对于主题的事件描述。 一篇重要的关于文本挖掘的论文 】，讲述在赫尔辛基大学进行的研究试验。因为出 现越来越多的非结构化文本资源，他们将数据挖掘技术应用于这种文本资源。这个小组 成功地运用了数据库中的知识发现技术，他们曾经发表了试图将数据挖掘技术直接应用 于经过预处理的文本信息的论文 ”。论文中提到需将预处理过程看作是一个至关重要的 环节，从而有效地改变了数据挖掘依赖于文本最初是如何被处理的这一法则。沿着知识 发现这条路，f e l d m a n 【2 考虑使用信息抽取中最简单的形式来获取知识：通过为一篇文本 建立一个有意义的概念集合来看清概念的层次结构，从而在文本和概念之间挖掘它们的 关系，这种方法主要应用领域就是文本分类。系统d o c u m e n te x p l o r e r 【9 】是目前比较先进 的文本挖掘系统，该系统构建于以上所提到的k d t 基础之上。f e l d m a n 的d o c u m e n t e x p l o r e r 则用文本集合来创建数据库，然后基于概念图的数据挖掘技术。这套系统可以 使用不同的模板来创建数据库以适应各种类型的文本集合，包括w e b 文本。 e t z i o n j 着眼于将数据挖掘技术应用于互联网上大量的超文本资源，这是第一篇将 数据挖掘技术应用于万维网上的信息资源的文章，并将该技术命名为w e b 挖掘。 s o d e r l a i l 【“】在从互联网上抽取信息的方面作了许多工作，利用自然语言处理技术从不同 的h l m l 资源来解释天气预报。应该说万维网上的数据已经成为文本挖掘的重要研究方 向。 东北师范大学硕士学位论文 1 1 2 文本挖掘的定义 文本挖掘( t e x tm i n i n g ) 是一个从非结构化文本信息中获取用户感兴趣或者有用的 模式的过程。文本挖掘涵盖多种技术，包括信息抽取、信息检索、自然语言处理和数据 挖掘技术1 1 2 j ，它的主要用途是从原本未经使用的文本中提取出未知的知识。文本挖掘也 是一项非常困难的工作，因为它必须处理那些本来就模糊而且非结构化的文本数据，所 以它是一个多学科混合的领域，涵盖信息技术、文本分析、模式识别、统计学、数据可 视化、数据库技术、机器学习以及数据挖掘等技术。 文本挖掘作为数据挖掘的一个新主题，引起了人们的极大兴趣。同时，它也是一个 富于争议的研究方向，目前其定义尚无统一的结论，需要国内外学者开展更多的研究以 便进行精确的定义。 借鉴c h o o ny a l l gq u e k 对w 。b 挖掘的定义，给出文本挖掘的定义【1 4 】： 文本挖掘是指从大量文本的集合c 中发现隐含的模式p 。如果将c 看作输入，将p 看作输出，那么文本挖掘的过程就是从输入到输出的一个映射：f c 斗p 。 文本挖掘是应用驱动的，它在商业智能、信息检索、生物信息处理等方面都有广泛 的应用。例如，客户关系管理、自动邮件回复、垃圾邮件过滤、自动简历评审、搜索引 擎等等。 文本挖掘可以通过图1 1 来理解。它由三部分组成：底层是文本挖掘的基础领域， 包括机器学习、数理统计、自然语言处理；在此基础上是文本挖掘的基本技术，有五大 类，包括文本信息抽取、文本分类、文本聚类、文本数据压缩、文本数据处理；在基本 技术之上是两个主要应用领域，包括信息访问和知识发现。信息访问包括信息检索、信 息浏览、信息过滤、信息报告；知识发现包括数据分析、数据预测。 i信息访问，知识发现 i fffff i 文本信息抽取 文本分类文本聚类文本数据压缩文本数据处理 fffff 机器学习，数理统计，自然语言处理 图1 1 文本挖掘 1 1 3 文本挖掘的过程 文本挖掘的主要处理过程是对大量文档集合的内容进行特征集的建立、特征集的缩 减、学习和知识模式的提取、模式质量评价等。如图1 2 所示： 4 东北师范大学硕士学位论文 文 本 集 特征集il 特征集ll 学习和知识il 模式质l1 知识 的建立l j 的缩减l j 模式的提取u 量评价l j 模式 图1 2 文本挖掘的过程 ( 1 ) 特征集的建立 由于处理的是非结构化的文本，使得现有的数据挖掘技术无法直接应用，因此要从 文本中提取适当的代表其特征的元数据特征项，将这些特征用结构化的形式保存起来， 从而实现对非结构化的文本处理。 ( 2 ) 特征集的缩减 自然语言文本集中往往包含大量的词汇，如果把这此词都作为特征，其特征维数会 相当高，这些特征对将要进行的分类学习未必全是重要、有益的，而且高维的特征会大 大增加机器学习的时间，因此需要去掉冗余词汇，以降低维数。 ( 3 ) 学习和知识模式的提取 在进行完特征集的缩减后，就可以利用机器学习的各种方法来实现面向特定应用目 的的知识模式提取，通常是进行文本分类或文本的聚类等。 ( 4 ) 模式质量评价 为了客观地评价文本挖掘的效果，经研究提出很多评测方法，比较常用的有准确率 ( p r e c i s i o n ) ，召回率( r c c a l l ) 。准确率是检索出的相关文档数与检索出的文档总数的 比率，衡量的是检索系统( 搜索引擎) 的查准率；召回率是检索出的相关文档数和文档 库中所有的相关文档数的比率，衡量的是检索系统( 搜索引擎) 的查全率。 1 2 文本分类 文本分类是文本挖掘工作中非常重要的部分，下面将简单介绍一下文本分类问题。 1 2 1 文本分类的背景 从汁算机诞生起，人们就希望计算机不仅能够进行数值运算而且能够处理人类的信 息和知识，替代人进行各项复杂的工作，人工智能就是在这一背景下诞生的，这其中就 包括对自然语言进行分类、理解、摘抄、检索等各方面的问题。1 9 5 0 年图灵提出著名的 图灵测试，图灵测试是让人类考官通过键盘向一个人和一个机器发问，这个考官不知道 他现在问的是人还是机器，如果在经过定时间的提问以后，这位人类考官不能确定谁 是人谁是机器，那这个机器就有智力了，这一测试的背后依然是计算机对于自然语言的 信息处理问题。可以说，对自然语言信息的机器处理问题的研究从来就没有间断过，当 然，这其中大量的研究是针对机器翻译问题来进行的。随着科技和信息的发展，特别是 近年来网络的高速发展，人类的信息出现雪崩式的增长，当前每天在网络中出现的文本 东北师范大学硕士学位论文 数量在1 0 9 以上，传统的人工处理信息的方法已经远远无法适应人类对于信息的需求。 信息摘抄、信息分类、信息检索等问题也越来越受到人们的重视，这其中机器学习扮演 着重要的角色。 机器学习( m a c h i n el e a r i l i n g ) 是研究计算机怎样模拟或实现人类的学习行为，以 获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能，它是人工智 能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域，它主要 使用归纳、综合而不是演译【”】。目前，机器学习的最主要应用领域有：专家系统、认知 模拟、规划和问题求解、数据挖掘、网络信息服务、图象识别、故障诊断、自然语言理 解、机器人和博弈等领域。 从机器学习的执行部分所反映的任务类型上看，目前大部分的应用研究领域基本上 集中于以下两个范畴：分类和问题求解。 ( 1 ) 分类任务要求系统依据己知的分类知识对输入的未知模式( 该模式的描述) 作 分析，以确定输入模式的类别。相应的学习目标就是学习用于分类的准则( 如分类规则) 。 ( 2 ) 问题求解任务要求对于给定的目标状态，寻找一个将当前状态转换为目标状态 的动作序列。机器学习在这一领域的研究工作大部分集中于通过学习来获取能提高问题 求解效率的知识( 如搜索控制知识，启发式知识等) 。 从是否需要训练样本的角度考虑，机器学习方法可区分为无监督学习方法、监督学 习方法利半监督学习算法： ( 1 ) 无监督学习方法是从样本的特征向量出发，研究通过某种算法将特征比较相似 的样本聚集在一起，从而达到区分具有不同特征的样本的目的。无监督学习方法的优点 是可以发现样本中隐含的共性和规律，但是由于没有专家知识的监督，分类的准确性有 限。 ( 2 ) 监督学习方法是通过对已知类别的训练样本的学习，实现对未知样本的分类判 断。监督学习方法的优点是准确率高，但获得已知类别样本的代价较昂贵，且算法需要 进行训练。 ( 3 ) 半监督学习算法是介于无监督学习和监督学习之间的一一种新的较为流行的方 法。它主要关注当训练数据的部分信息缺失的情况下，如何获得具有良好性能和推广能 力的学习方法，这里的信息缺失涵盖数据的类别标签缺失或者存在噪声，数据的部分特 征维缺失等多种情况。 1 2 2 文本分类的研究现状 文本分类指按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。这 样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查找更为容 易。文本分类是通过训练一定的文本集合得到类别与未知文本的映射规则，即计算出文 本与类别的相关度，再根据训练的分类器来决定文本的类别归属。 1 文本分类模型 文本分类一般基于“词袋”模型，即文档被看成是由相互无关的单词构成的集合， 6 东北师范大学硕士学位论文 不考虑单词之间的上下文关系，单词出现的顺序、位置以及文章的长度等，仅记录每个 单词在文档中出现的次数，或仅记录单词出现与否。通过对训练集进行文法分析统计出 所有单词在所有训练文档中出现的频率，得到词频矩阵，矩阵中的某一元素就是某个单 词在某篇训练文档中出现的频率。词频矩阵是文本分类算法建立分类器模型的数据基 础。下面介绍文本分类系统的体系结构，如图1 3 所示。 固 - n 五耳一恒曰厦硒 倒 恒母囱圆 面 丽升商一 文本 预处理 特征选择训练、分类 图1 3 文本分类系统的体系结构 ( 1 ) 预处理模块 预处理模块对训练语料库及待分类文本实行预处理，通过对文档进行扫描，分析出 文档中的单词。对待英文文本，文法分析的步骤为：按空格切分出各个单词，过滤掉其 中的停用词，如a ，t h e ，t h a t 等：然后进行词干提取。如将p l a y e d ，p l a y i n g 变为p l a y ； 将文档对应的词频向量中该单词的频率增1 ，如果这是训练语料集中第一次遇到的新词， 就存入单词列表，也称为词库，该模块中还包括保存文档的文件名、类别等工作。如果 对中文文本进行预处理，需要增加切词的工作，因为中文与英文不同，英文有空格符将 词与词进行间隔，而中文文本是连续的汉字串，词与词之间没有明确的分隔标记，汉浯 中存在大量多义词，语义模糊，歧义性大，识别词的边界很难。常用的中文分词算法有： 基于词表的分词，基于统计的分词，基于规则和基于统计相结合的分词，其中基于词表 匹配的分词方法需要语言资源，仅需一个词表( 分词词典) ，不需要任何词法、句法、 语义知识最少，程序实现简单。 ( 2 ) 特征选择模块 经过预处理模块的处理，训练语料集文本及待分类文本均被表示为词频向量，如图 1 4 所示，同时训练语料集中所有文本的词频向量构成词频矩阵，如图1 5 所示。由于词 库中存在大量的词汇，把所有单词都作为特征将带来一系列问题。首先是向量的维数太 大，给计算带来非常大的压力，且存储空间大，处理速度慢。其次是这些词中实际上有 很大一部分是与类别无关的，对分类作用不大。因此，本文要降低向量的维数，采用某 种特征选择方法选择词库中那些有代表意义的单词作为特征，从而得到降维的词频矩阵 和待分类文本词频向量。 7 东北师范大学硕士学位论文 0 i e a m l n g 一；幸 3 j o u n l a l 2 i n t e l l i g e n c 多4 0 t e x t 0 a g e n t j a i r 蚴r e f c 删j o “掣至多碗a a 佗竺一 一 li n t e r n e t 蠢篡鍪蒜著 ow e b w a t c h e r 0d e r l 5 。 1v o l u m e 图1 4 “词袋”模型中文档的词频向量示意图 、r o f d lw o r d 2 、】l ，o r d 3w o r d n f i l e l a l ia 1 2a 1 3 - a l n f i i e 2 a 2 l赴2a 2 3 a 2 n f i l e m 钆l la m 2a m ba 砌 图1 5 词频矩阵示意图 ( 3 ) 训练、分类模块 词频矩阵是算法建模的基础，在词频矩阵的基础上根据特定的分类算法构造分类 器，对待分类文本进行分类。比如，t f i d f 分类算法计算待分类文本词频向量与各类向 量的相似度，将其归入相似度最大的类别中去；朴素贝叶斯计算待分类文本属于各类的 概率，将其分配到概率最大的类别中去。 2 文本分类过程 文本分类是一种有指导机器学习问题，它需要事先定义一些主题类别，然后根据文 本的内容自动将每篇文档归入其中的某个类别，这样用户就可以根据自己的所需来选择 信息。从数学角度来看，文本分类其实就是一个映射的过程，它将未标明类别的文本映 射到已有的一个或多个类别中。分类系统一般分为训练和分类两个阶段，具体过程如下： 训练阶段：首先需要确定类别的集合c ，这些类别可以是层次式的，也可以是并列 式的；再选择适量具有代表性的文档组成训练文档集合s ，确定训练文档集s 中的每个 训练文档所属的类别c f ：然后抽取训练文档s ，特征，得到特征向量y ( s ，) ；最后，统计 训练文档集s 中所有的文档特征向量矿( s ，) ，以此确定代表c 中每个类别的特征矢量 矿( c ，) a 分类阶段：对于测试文档集合丁的每个待分类文档以，计算特征矢量矿( 以) 与每个 r 东北师范大学硕士学位论文 向量机【2 3 】、基于中心点的分类方法【2 4 】、决策树【2 5 、k 一近邻【2 6 j 、神经网络算法【2 7 】、粗糙 集【2 8 】、模糊集以及线性最小二乘3 0 1 等。 2 1 文本分类算法概述 下面简单介绍一下几种经典的文本分类算法： 2 1 1n a i v eb a y e s 算法 贝叶斯概率算法在机器学习领域中得到了广泛的研究。该算法将文章看作独立的单 词集合，通过训练集，由贝叶斯理论得到每个单词在不同类的概率大小，构造出贝叶斯 模型，模型由参数日决定。贝叶斯算法假设文档由混合模型产生，每个类别对应混合模 型的一个分量。模型目由以下参数组成： 扫= h wl c ，；回，f l ，i 矿i ) ，c ，c 雌，i 印，c ，c )( 2 1 ) 算法假设模型分量与类别一一对应文档由模型产生，先选择一个类别，然后按这 个类别的模型分量产生一篇文档。那么一篇文档属于这个模型的概率即可根据式2 2 得 到，则一篇文档的类别由概率最大的模型决定。( 算法详见2 2 节) 且 p ( d fl 目) = p ( c ，i 口) p ( d f c ，；曰) ( 2 2 ) 2 1 2 支持向量机 支持向量机( s u p p o nv c c t o r m a c l l i n e ，简称s v m ，也叫做支撑向量机) 是在二十世 纪9 0 年代以来发展起来的一种统计学习方法，在解决小样本学习、非线性及高维模式 识别问题中表现较好。s v m 算法不仅具有扎实的理论基础，而且在应用到文本分类时 取得了很好的效果。 支持向量机的基本思想是，对于一个给定的具有有限数量训练样本的学习任务，如 何在准确性( 对于给定训练集) 和机器容量( 机器可无错误地学习任意训练集的能力) 之间进行折衷，以得到最佳的推广性能。 s v m 就是通过某种非线性映射够将输入向量x 映射到一个高维空间z ( 又称特征空 间) 并在z 中构造最优分类超平面。假定非线性映射为：驴：r 。斗z ( 特征空问是一个 h i l b e f t 空间) ，将原空间中的向量x 映射成空间z 的向量z = ( x ) 。设输入向量 z = ( 工1 ，x 2 ，j 4 ) ，权值w l ：嘶y ，贝4 ： 上 y = s g n ( c i x 东北师范大学硕士学位论文 厂o ) s g n ( ：y ，k ( 葺，工) + 6 。) i ：1 其中口；为下述函数最大值的最优解 k ( _ ，x ) = 成为核函数，通常取如下形式： ( 1 ) 线性函数： 足“，_ ) ：t 7 - ( 2 4 ) ( 2 5 ) ( 2 ) 多项式核函数：足瓴，曲= 水而，z 斗t 6 ) ”，c 为常数，n 为多项式次数 ( 3 ) 径向基核函数：k ( x ) ：e 。p ( 一c 生纠) ，c 为常数，盯为方差 盯 ( 4 ) s i g m o i d 函数：五( 葺，功= t a i l l l ( 6 0 而) 一c ) ，b ，c 为常数。 2 1 3t f i d f 算法 t f i d f 文本分类算法是基于向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 的。 该算法将每个单词作为一个特征项f 。，将每篇文档看作由单词组成的向量 d v = ( w ，w 。，w 。) ，其中为“的权重，表示单词“( ”为单词总数) 在文档中的 重要程度。同时，算法将属于同一类的所有文档向量加起来，得到每一个类 c ，( c ，c ，c 表示所有类别的集合) 的特征向量删= ( ，：，) 。在测试一篇文档的 所属类别时，通过计算这篇文档的向量咖和每个类特征向量c v 的相似度距离 s 拥( 咖，c ，相似度距离最大的类向量c v 所属的第j 类就是测试文档的类别，如式2 6 、 式2 7 所示： ( 州，= ( 删， 如o ( 2 6 ) c 肠船( 西。) = a r g m a 】( s 砌( 西f ，删) ，c ，c 咖嘛咿尚2 悬 ) 2 1 4l ( n n 算法 k n n ( kn e a r e s tn e i 曲b o r ) 是当k = l 时的一种特定的n n ( n e a r e s tn e i 曲b o r ) 。n n 强调最近点的重要性，而k i n 则从整体考虑，是一种更为普遍的方法，理论认为它的 1 2 、， 石茗 ，l k yy 口口 ，州 ，一2 一口 。m = ) 口 烈 东北师范大学硕士学位论文 2 2 贝叶斯分类算法 如上一节所说，贝叶斯概率算法在机器学习领域中得到了广泛的研究。贝叶斯分类 器分为两种：一种是朴素贝叶斯分类器，它假设一个属性对给定类的影响独立于其他属 性，即特征独立性假设。当假设成立时，与其他分类算法相比，朴素贝叶斯分类器是最 精确的，但是，文本属性之间的依赖关系是可能存在的。另一种是贝叶斯网络分类器， 它可以考虑属性之划的依赖程度，其计算复杂度比朴素贝叶斯高得多，但更能反映真实 文本的情况。然而，贝叶斯网络分类器实现十分复杂且分类速度较慢。若文本采用向量 空间模型( v s m ) 表示，则每个文本有特定的特征项组成，分别计算每个文本属于每个 类的概率，最大概率所对应的类别即是这个文本所属的类别。朴素贝叶斯的分类模型采 用最简单的贝叶斯网络结构，在该模型中，假设所有的属性w i ( 卜l ，2 ，n ) 都条件独 立于类变量c ，即每一个属性变量都以类变量作为唯一的父节点。由于结构简单，有时 将其与严格的贝叶斯网络分类器相区别，仅称之为朴素贝叶斯分类器( n a i v eb a y e s c l a s s m e r ) 。图2 1 直观地描述了朴素贝叶斯的分类模型的结构特点： a l 图2 1 朴素贝叶斯的分类模型 朴素贝叶斯( n a i v eb a y e s ) 学习文本分类的一般原理：已知训练文档集：d = d l ，d 2 ，d n ) 和它的词汇集：w = w l ，w 2 ，w n ) 。每一训练样本是一个m + l 维向量： 谚= 其中c ，c = ( q ，c 2 ，q ) 是类别变量。每类的先验概率为：p ( c ) j = 1 ，2 ，k ：未 知类别样本为：d = 。分类的任务就是对未知类别样本预测它的类别。 对于新样本d ，其属于c j 类的条件概率是p ( d c ) 。根据贝叶斯定理，c j 类后验概率为 p ( c id ) ： 蚂旧= 警 ( 2 - 8 ) 为避免朴素贝叶斯分类器( n a i v eb a y e sc l a s s i f i e r ，n b c ) 的另一个缺陷偏斜误差， 本文使训练集中各个类别的训练集包含的文本数目相等，即：p ( c 1 ) = p ( c 2 ) = = p ( c k ) 。 对于一个选定的样本d ，p ( d ) 为固定值。因此，式2 8 可简化为： p ( c ，l d ) 虻p ( d i c ，)( 2 9 ) 东北师范大学硕士学位论文 2 3 自组织特征映射网络 2 3 1 神经网络简介 由于数据挖掘过程中数据集的性质往往非常复杂，且非线性、持续性及噪音等普遍 存在，因此需要一种全新的不同于传统算法的理论和方法来解决数据挖掘中的问题。神 经网络作为一种非线性自适应动力学系统，具有通过自学习提取信息内部特征的优点， 非常适合解决数据挖掘中的问题。经过实验证明，应用神经网络抽取数据挖掘中的分类 规则是一一条行之有效的途径。神经网络近来越来越受到人们的关注，因为它为解决复杂 度高的问题提供了一种相对来说比较有效的简单方法。神经网络可以很容易的解决具有 上百个参数的问题，当然实际生物体中存在的神经网络要比这里所说的程序模拟的神经 网络要复杂得多。神经网络常用于两类问题：分类和回归。用来建模神经网络系统的网 络结构和信号处理系统大致可分为三类，每一类都基于不同的体系。 ( 1 ) 前馈式神经网络：将输入信号集变换到输出信号集，期望的输出变换经常由外 部有监督的修正系统参数来决定。 ( 2 ) 反馈式神经网络：将输入信息定义为反馈系统初始的活动状态，经过状态转换， 由渐进的最终状态确定计算结果。 ( 3 ) 自组织映射神经网络：神经网络中相邻的神经元通过相互的侧向作用在它们的 活动中相互竞争，并且自适应的发展成为不同信号模式的特殊探测器。它的学习称为竞 争、无监督学习或自组织学习。 2 3 2 自组织特征映射网络 在人工神经网络所提出的各种算法和结构中，自组织映射网络具有能够快速、有效 地建立输入信号不同特征的内部表示的特殊属性，除此之外更具新颖性的是，自组织过 程还能发现自然语言句子中的语义关联。从这些方面看，作为结果产生的自组织映射与 高级动物大脑皮层中发现的拓扑组织映射非常相象。自组织映射网络经过优化修正模型 向量，能像具有智能的生命体一样在各种含有大量噪声信号的模式识别领域中进行工 作。这些映射的应用十分广泛，特别是在语音识别领域中已经应用到了实际中，并且在 数据挖掘、机器人、过程控制和电信等领域中的应用也正在进一步向前推进。白组织特 征映射是一个2 维空间排列的人工神经网络，其中每个神经元通过无监督学习过程进行 调整，使之对应于特定的不同输入信号模式或模式分类。从根本上而言，在同一时刻只 有一个中心神经元或一组局部神经元会对当前输入产生积极的h 向应，并且，响应的位置 区域倾向于越来越固定，就像通过网络建立了某种与不同输入特征对应的，具有意义的 坐标系统。因此，神经元在网络中的空间位置或坐标就对应于特定域的输入信号模式， 每个神经元或局部神经元组就像是对相同输入模式的一个单独的解码器。所以，与其说 神经元在某个位置是否对输入有积极的响应是对输入输出信号进行了精确的变换，不如 说它其实是对输入信号提供的各种模式信息进行了不同的解释。目前对人脑的研究说 明：大脑皮层中神经元是呈2 维空间排列的。它的输入信号很明显来自两个部分，外部 1 6 东北师范大学硕士学位论文 区域的输入和同一区域的反馈输入。神经元之间的信息交互方式有很多种，不过研究表 明：相邻近的神经元之间的局部交互的方式是侧向交互。这种侧向交互方式遵从下列有 关规则： ( 1 ) 以发出信号的神经元为圆心，对近邻的神经元的交互作用表现为兴奋性侧反馈； ( 2 ) 以发出信号的神经元为圆心，对远邻的神经元的交互作用表现为抑制性侧反馈。 这种规则说明近邻者相互激励，远邻者相互抑制。一般而言，近邻是指从发出信号 的神经元为圆心，半径约为5 0 w m 5 0 0 w m 左右的神经元；远邻是指半径为2 0 0 w m 一2 m m 左右的神经元，比远邻更远的神经元则表现的是弱激励作用。这样，这种局部交互方式 如图2 2 所示。由于这种交互作用的曲线类似于墨西哥人带的帽子，所以也称这种交互 方式为“墨西哥帽”。 图2 2 侧向交互模式 侧尚距离 自组织特征映射神经网络中，邻近的各个神经元之间通过相互的侧向交互作用，从 而产生相互竞争的过程，自适应地形成了针对特殊信息的组织结构，很明显，这种结构 可以成为检测特殊信息的特殊检测器。神经网络的这种自组织过程和行为，可以成为一 种检测各种不同信息模式的检测识别器，这也是自组织持征映射的意义所在。 tk o h o n e n 于1 9 8 1 年提出了自组织特征映射网络模型 ( s e l f _ o r g a i l i z i n gf e a t u r e m a p ，s o f m ) 【”3 ”。s o f m 模型可以用二维阵列表示。这种结构如图2 3 所示： x 1x 2 x m 1 7 争层 m 屡) 东北师范大学硕士学位论文 图2 3 二维阵列s o f m 模型 二维阵列s o f m 模型由输入层和竞争层组成，输入层是一维的神经元，竞争层是二 维的神经元。输入层的神经元和二维阵列竞争层的神经元每个都相互连接，二维阵列竞 争层也称输出层。s o f m 网络是全连接的，每个输入结点都同所有的输出结点相连接。 在神经网络的s o f m 模型中，每个权系数的有序序列w i - ( w i j ，w 2 j ，w t 。，) 都 可以看作是神经网络的一种内部表示，它是有序的输入序列x = ( x t ，x 2 ，x n ) 的相对 应映象。s o f m 模型实现自组织的目的就是通过调整权系数w ，使神经网络收敛于一 种表示形态，在这一表示形态中的一个神经元只对某种输入模式特别匹配或特别敏感。 换而言之，自组织映射的目的就是使神经元的权系数的形态表示可以间接模仿输入的信 号模式。自组织特征映射网络的学习算法主要是由两部分组成的，这两部分如下： ( 1 ) 最优匹配神经元的选择； ( 2 ) 网络中权系数的自组织过程。 这两部分是相辅相成的，它们共同作用才能完成自组织特征映射的学习过程。选择 最优匹配神经元实质是选择输入模式对应的中心神经元c ，权系数的自组织过程则是以 “墨两哥帽”的形态来使输入模式得以存放。每执行一次学习，则s o f m 网络中就会对 外部输入模式执行次自组织适应过程，其结果是强化现行模式的映射形态，弱化以往 模式的映射形态。 在计算机中可以采取一定的恰当步骤对自组织特征映射模型s o f m 进行学习。这 些步骤介绍如下： ( 1 ) 连接权值的初始化：f = o ：o 觋 l ，f 1 ，2 ， ，( 1 ，2 ，聊 ，其中”为特 征词个数，聊为输出层节点数； ( 2 ) 对网络输入一个样本西：x f ( x l ，x 2 ，x 。) ； ( 3 ) 计算x k 与全部输出节点问的权值向量的距离： 2 嘭( f ) = ( 置一( f ) ) ， 1 ，2 ，聊) ( 2 1 4 ) l = i ( 4 ) 选择有最小距离的节点d j + 为竞争获胜节点： = m i l l ( 嘭) ， l ，2 ，所 ( 2 1 5 ) ( 5 ) 调整权值： = 口( f ) 卢( m ，巧) ( 置一( f ) ) ，_ ，吖( f ) ( 2 1 6 ) = o ；( f ) 其中，o 口( f ) 代表当前文本 属于打a d e 和a c q 类别；订r r l e u k g r o w gi m p a t i e n tw hj a p a n t h a t c h e r 刮t i t l e 表示该篇文章的题目为u k g r o w g 肼p a t l e n tw i t h 2 2 东北师范大学硕士学位论文 j a p a n t h a t c h e r ：而r e u t e r s 则是一篇文章的结束标志符。首先，本文按照 结束标志符，将2 2 个s g m 文件分割成独立的文本的集合；然后，通过 l e w i s s p l i t = - ，t r a i n ”和l e w i s s p l i t = ”t e s t ”标志符将测试集和训练集分开：最后， 通过 ， 和 标志符将文本的类别，标题和文本主体分别取 出，并对文本做适当的标记对于属于多个类别的文本，本文针对不同的类别都产生一个 该类别的样本；对于无类别标记的文本，则不生成文本样本。下面是将一个属于a c q 类 别的示例文本按照上述方法从s g m 文件中剥离出来后的文本样本： c i st e c h n o l o g i e s & l t ；c i 王l t os e ns h a r c st os w i s sc o c i s t e c l l n o l o g i e s i n cs a i di te x e c u t e daf o r n l a ls h a r ep u r c h a s ea g r e e m e n tw i t hs w i s s r e i n s u r i 皿c ec oo fz u r i c h ，s w i t z e r l a n d u n d e r t e m so ft h ea 掣e e m 锄t ，s w i s sr cw i l la c q u i r c5 ，5 m l nn e w l yi s s u e dc i ss t o c ka t2 5 0d l r sas h a r e ，o r1 3 8m l nd l