1、 本科 毕业 设计 (论文 ) （二零 届） 文本表示模型的研究与实现 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 0 摘要： 随着信息技术的不断发展，特别是 Internet 应用的普及，电子文本信息急剧增加。如何有效地组织和管理这些海量信息，并且能够快速 、准确地获得用户所需要的信息是当今信息技术领域的一大挑战。文本分类作为处理和组织大量文本数据的关键技术可以在较大程度上解决信息杂乱的现象，方便用户准确地定位所需的信息。本文分析了文本自动分类的关键理论及技术 ,给出一个已实现的基于向量空间模型 (VSM)的文本自动分类系统的框架模型 ,重点描述此
2、系统的实现算法 .此算法在训练阶段通过部分训练集确定向量的特征提取维数 ,并提出一种“平均值”匹配阈值调整方法 ,从而在精度和效率方面优于传统的分类算法。文本分类技术在生活中起着越来越重要的作用，成为信息检索领域中最前沿的研究 热点之一。 关键词 ： 向量空间模型；文本分类；特征抽取算法；特征抽取 0 Text Representation Model Research and Implementation Abstract： With the continuous development of information technology, especially the populariza
3、tion of Internet applications, electronic text message has increased dramatically.It is a big challenge in current information technology of how to organize and manage these huge amounts of information effectively, and can be quickly and accurately acquire the information of user need . Text classif
4、ication as a key technology about process and organize text data.It can solve disorderly phenomenon,and convenient information user to accurately position the required information. This paper analyzes the key automatic text categorization theory and technology, given a realized based on vector space
5、 model (the VSM) automatic text categorization framework, the system were described emphatically algorithm. This algorithm in training phase through part of training sets sure vector feature extraction dimension, and puts forward a kind of “average“ matching threshold adjustment method, thus in the
6、accuracy and efficiency of classification algorithm is superior to traditional. Text classification technology in life plays a more important role in our life, become one of cutting-edge research hotspot. Key words: Vector space model; Text classification; Feature extraction algorithms; Feature extr
7、action 1 目录 1 绪论 . 2 1.1 课题背景 . 2 1.2 文本分类的定义 . 2 1.3 文本分类技术的分类 . 2 1.4. 文本分类在国内 外的发展及现状 . 3 2 基于向量空间的文本分类技术 . 5 2.1 文本表示 . 5 2.2 向量空间模型 . 5 2.3 特征项的抽取 . 6 2.4 文本分类算法 . 7 2.4.1 类中心分类法 . 7 2.4.2 贝叶斯算法 . 8 2.4.3 KNN (K 最邻近 )算法 . 8 2.4.4 支持向量机法 . 9 2.4.5 其它分类算法 . 9 2.5 阈值的确定 . 10 3 系统的结构框架 . 11 3.1 结构框
8、架 . 11 3.2 系统测试 . 12 3.2.1 主界面 . 12 3.2.2 训练过程 . 13 3.2.3 分类过程 . 15 3.3 系统实现及运行环境 . 20 4 总结 . 22 参考文献 . 23 致谢 . 错误 !未定义书签。 2 1 绪论 1.1 课题背景 Internet 已被公认为是 20 世纪末人类科技史的里程碑，它作为一个开放的、分布式的信息空间，近年来得到了飞速发展。随着 Internet 上信息量爆炸性的增长，人们很难从大量的信息中迅速有效地提取出所需信息，出现所谓的“信息迷向”的现象。如果计算机能够在信息 的辨识和处理方面，对用户提供适当的支持和帮助，那将能够
9、极大地改善目前用户面临的困境和提高信息使用效率。 基于这种需求，人们对利用计算机进行智能化信息处理进行了大量研究。根据侧重点不同，大致包括信息检索、信息抽取、文本分类、文本摘要等研究领域，这些研究都旨在帮助用户对 Internet 上的大量信息加以辨识、分类，按用户兴趣加以筛选、排序，甚至提炼出要点形成摘录。这些研究成果和搜索引擎相结合，构成智能化搜索引擎，极大地提高了用户搜寻信息的能力。另外，这些技术也应用在电子商务、数据库、 web 页分类管理、信息 过滤、个性化人机界面、个人信函助理等领域，有效地提高了信息服务的质量。 1 1.2 文本分类的定义 文本分类就是对一篇文本，根据其内容，从预
10、先定义好的标记集中找出一个或者多个最适合于该文本的标记。文本分类技术从开始出现到现在，经历了从基于规则到基于统计分类，再到规则和统计相结合的一个过程。 简单地说，文本分类系统的任务是 :在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到己有的类别中，该映射可以是一一映射，也可以是一对 多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下 : f:A B 其中， A 为待分类的文本集合， B 为分类体系中的类别集合， f 是建立 A 和 B 映射的函数或模型。 文本分类的映射规则是系统根据已经掌握的每类若
11、干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据判别规则，确定文本相关的类别。 1.3 文本分类技术的分类 按照人们解决文本分类问题的切入点的不同，文本分类可分为基于自然语言理 解的文本分类和基于统计数学的文本分类。当然在实际应用中使用的方法大都是这两种方法的结合。文本分类的处理对象是文本，而文本是以自然语言的形式出现的，因此，试图把文本分类建立在自然语言理解的基础之上是很自然的事情。然而事实并非如此，由于自然语言的复杂性，3 想把自然语言中的一切规则用知识的形式表示出来几乎不可能，这条途径事实上困难是相当大的。 1因此，一方面，人们继续跟随着自然语言处
12、理技术的发展，试图建立更为理想的基于知识库的分类系统 ;另一方面，人们另辟蹊径开拓了一条新的文本分类的途径，即把文本分 类建立在统计数 学的基础之上，用统计的方法从文本的字频、词频等相关元素中提取文本的特征，再建立相应的数学模型以实现分类。尽管此类方法的分类效果不太理想，但作为一种辅助工具，仍然具有积极的意义。 按文本语料的性质和应用需求的不同，文本分类可分为基于分类体系的分类和基于信息过滤和用户兴趣的分类。基于分类体系的分类一般要经过抽取主题词，计算权值，根据分类体系对主题词分析定类几个步聚，目前国内对分类的研究多是基于分类体系的系统。网上信息多如牛毛，人们没有必要而且也没有足够的时间和精力
13、去阅读所有的信息，因此，越来越多的用户只希望看到 自己感兴趣的信息，基于信息过滤的分类显得越来越重。 1.4. 文本分类在国内外的发展及现状 国外对文本分类的研究始于 20 世纪 50年代末， H.P.Luhn首先将词频统计思想用于分类，在该领域进行了开创性的研究。 1960 年， Maron 在 Journal of ASM 上发表了有关自动分类的第一篇论文 On relevance, probabilistic indexing and information retrieval，其后许多学者在这一领域进行了卓有成效的研究工作。 2 从 20 世纪 60 年代直到 20 世纪 80 年代末
14、，这期间最有效的文本分类系统一直是由专家人工构建的基于知识工程技术的分类系统。其典型应用就是卡内基集团为路透社开发的Construe 系统 fill，它主要是由专业人员编写了一些分类规则来指导分类，在 Reuters 的部分语料库上它的效果非常好，平均准确率和召回率大约都可达到 90%，但是在其他的应用领域采用 Construe 系统将会消耗大量的人力和物力。这种自动分类器构造方法的缺点是知识获取瓶颈的存在。它必须要为领域专家获取的知识和知识工程师的知识表示之间架起桥梁，二者缺一不可，如果这种分类器被转到完全不同的 领域，工作必须得重新开始。 90 年代初期，基于机器学习的分类技术开始取代基于
15、知识工程的方法成为文本分类的主流技术。这种算法通过归纳文本集的特征自动创建一个分类器，这些文本集合事先被领域专家人工地分类到类集 C=(c1, c2, cm)的各个类 ci 中，分类器可作为一个规则决定文本 dj 是否属于类 ci 。如果类集 C 被更新，或者系统要应用于其他不同的领域，只需要重新构造一个人工分类文本集合，通过机器学习，自动地构造一个分类器。显然由于这种分类方法不再需要知识工程师和领域专家的介入，节约了大量的专家人力资源，同时加 快了分类系统的建立速度。 自从文本分类的概念在国内出现以来，该技术在国内得到了长足的发展。然而和国外的发展状况相比，发展水平仍相对滞后。一方面由于国内
16、起步较晚，另一方面则由于国内的工作主要是针对中文文本。由于汉语有许多不同于英语的特点，使得中文文本分类的难度更大。比如，汉语的书面形式是连续书写的，词与词之间没有自然的界限，在进行文本分类之前，4 首先要对文本进行分词。另外，在不同的语言的研究工作中，句法分析和语义分析所占的比例是不同的。在英语中，句法分析比语义分析的比例要大，而汉语是一种分析型语言，语义分析在汉 语研究中起着举足轻重的作用，其所占的比例比句法分析要大得多。这使得在中文文本分类中，通过句法分析等基于语法的手段把握文本的内容变得更加困。 3就发展历史而言，国内的文本分类的发展经历了三个阶段 :国外研究成果引进阶段、分类技术完善阶
17、段以及面向汉语分类技术的发展阶段 ;而就发展方向来看，则有基于外延的分类方法和基于概念的分类方法之分。中国科学院、清华大学、上海交通大学、复旦大学、南京大学、一些大学的著名学者在该领域做出了一些研究成果，研制出一批基于词典法和基于专家系统的分类系统。由于中文与英文存在较大的差异，不 能照搬国外的研究成果，中文文本分类的研究基本上是在英文文本分类的研究策略上，结合中文文本的特点，继而形成中文文本分类研究体系。 5 2 基于向量空间的文本分类技术 2.1 文本表示 至今，计算机还不能象人类那样阅读完文章后，根据自身的理解能力对文章内容产生一定的认识。更何况大规模文本处理的对象是大量的真实文本，要使
18、计算机能够高效率、高性能的处理自然文本，就必须找到一种理想的文本表示方法。文本表示最理想的境界就是模拟人所理解的语义，通过函数 F，使得 : 人所理解的语义 =F(文本 ) 一旦找到了合适的函数来表示人所理解的语义，那么由计算机处理文本的问题就变得简单了。对于文本分类来说，其过程就可以转化为一个搜索问题，即寻找和新文本函数值差异最小的文本类。 4 但是不幸的是，这种精确反映人所理解语义的函数是很难定义的，或者更极端一点说，也许根本就是不存在的。对于形式语言而言，语义还可以通过机器状态的改变来描述，人们也正是通过这种方法来学习和掌握机器语言的 ;可是对于自然语言而言，由于涉及到人这个认知主体的思
19、维活动，不同的认知主体往往会有不同的理解，自然 语言的形式及其意义之间是多对多的关系，很难合理地定义一个反映语义的函数。 因此，我们只好退而求其次，寻求一种能够量化、能够形式化、最终可以计算和操作的表示方法。一种可行的方案就是走统计的路线，研究从大规模语料库中发现出来的统计规律，利用文本在字集合或词集合上的分布来近似表示语义，并且做如下的假设 : I.两个分布完全一致的文本被认为是语义相同的。 II.两个分布相近的文本被认为是语义相近的。 自然，仅仅采用这种分布是不能精确反映人所理 解的语义的，然而这种方案却能够很方便地计算和操作，对于信息处理等应用领域，其表达效果还是可以接受的。 5 根据以
20、上思路，我们来考察文本。众所周知，文本是字词等代表特定含义的符号按顺序连接的字符串。文本有两个基本的特征 :一是组成文本的所有字词符号出现的频率，二是这些符号间的连接顺序，即文本可以由特征项的频率及其相互关系来完整表达。要表示文本中特征项的顺序信息，就必然要用到有向的指针结构，这样，整个文本就变成了一个复杂的图或网。而表示文本中特征项的频率信息，仅仅使用一个向量就够了。信息检索和文本分类等信息处理 技术要求定义一种距离函数，以表示文本间的相似程度。数学中有很多种定义距离的方式可以供使用，例如欧式距离、相关系数等等。 2.2 向量空间模型 在向量空间模型 (Vector Space Model)
21、中 ,文档空间被看作是由由一组正交词条向量所组成的向量空间 ,文档中的词称作特征 ,文档表示为由特征组成的向量空间中的一个特征矢量。通过向量空间模型把文本表示成一个由词条向量组成的向量空间 ,每个文本 d 都可以映射为6 空间的一个特征向量 V(d)= (T1,W1， (d),T2,W2,(d), Tn,Wn(d),),其中 Ti 表示 特征项 ,Wi(d)表示对应分量的权重。提取每类文档的特征向量建立向量空间模型 ,文本转化为向量形式并经过特征提取以后 ,便很容易进行分类挖掘了。虽然 VSM 模型不考虑语义信息并且部分丢失了文本中词和词的相互关联 ,但它简单易处理 , 并且对文本处理 (主要
22、是分类 )可以得到很好的效果 ,因此是目前最常用的方法。 向量空间检索模型可以描述为 I=(D, T, Q, F, R)，其中 : D=dl,d2 , ,dn为文本集合， n 为集合中的文本数 ; T=t1,t2, ,tm为特征项集合， m 为所有的特征项数。 m 个特征项标 引的某一文本可以表示为空间中的一个向量 ,d 21ii ）（ imi i=1,2, n, ij 是特征项 jt 对于文本 id的权重，如果权重值 ij 为 0,则表示 jt 没有在 id 中出现 ; Q= mqqq , 21 为查询集，某一查 询 rq 可以由向量 ),( 21 rmrrr qqqq 表示，是特征项 jt
23、 对于查询 qr 的权重，如果权重值 rjq 为 0,则表示 jt 没有在 rq 中 出现 ; F= TtDddtd jiijji ,|, 为 文 本 一 特 征 项 的 描 述 关 系 ，i=1,2, ,n,j=1,2 ,m,其中 ;10 ijd R 为检索函数， R(是系统响应，由查询向量 iq 与文本向量 id 经过相似性计算得出，系统响应 R( rq =a( iq , id ),i=1,2, ,n。 6 2.3 特征项的抽取 构成文本的词汇 ,数量是相当大的 ,所以 ,表示文本的向量空间的维数也相当大 ,可以达到几万维。因 此我们需要进行维数压缩的工作 ,这样做的目的主要有两个 :第一
24、 ,为了提高程序的效率 ,提高运行速度 ;第二 ,所有几万个词汇对文本分类的意义是不同的 ,一些通用的、各个类别都普遍存在的词汇对分类的贡献小 ;在某特定类中出现比重大而在其它类中出现比重小的词汇对文本分类的贡献大。 7为了提高分类精度 ,对于每一类 ,我们应去除那些表现力不强的词汇 ,筛选出针对该类的特征项集合 ,存在多种筛选特征项的算法 ,如下所列： (1) 根据词和类别的互信息量判断 (2) 根据词熵判断 (3) 根据 KL 距离判断 下面来解释一下词和类别的互信息 量进行特征项抽取的判断标准 ,其算法过程如下 : 初始情况下 ,该特征项集合包含所有该类中出现的词。 对于每个词 ,计算词
25、和类别的互信息量 7 log WP CWP j() )|( 其中 , P( W|Cj ) =),(|),(11|11|iSDIVjDidWNVdWN P( W| Cj ) 为 W 在 Cj 中出现的比重 , | D| 为该类的训练文本数 , N (W,di 为词 W 在 di 中的词频 ,|V| 为总词数 ),(1|1 iSDIV dWN N ( Ws , di) 为该类所有词的词频和。 而 P( W) 同上面的计算公式相同 , 只是计算词在所有训练文本中的比重 , 其中 , | D| 为全体训练文本数。 对于该类中所有的词 ,依据上面计算的互信息量排序。 抽取一定数量的词作为特征项。具体需要
26、抽取多少维的特征项 ,目前无很好的解决方法 ,一般采用先定初始值 ,然后根据实验测试和统计结果确定最佳值。一般初始值定在几千左右。 将每类中所有的训练 文本 ,根据抽取的特征项进行向量维数压缩 ,精简向量表示。 8 其它抽取特征项的算法 ,除判断函数上有所差别外 ,主要过程类似。 2.4 文本分类算法 文本分类算法就是一个建立从文本属性到文本类别空间的映射过程。一个好的文本分类算法能够和特征抽取算法相得益彰，取得满意的分类效果。基于向量空间模型的文本分类算法有类中心分类法、贝叶斯算法、 KNN 算法和支持向量机算法等等，下面分别对各种文本分类算法加以论述。 2.4.1 类中心分类法 该方法的分类思路十分简单，根据算术平均值为每类文本集生成一个代表 该类的中心向量，然后在新文本来到时，确定新文本的向量，计算该向量与每类中心向量间的距离 (相似度 )，最后判定文本属于哪个与文本距离最近的类，具体步骤如下 : STEPl：计算每类文本集的中心向量，即所有训练文本向量的简单算术平均 ; STEP2：新文本到来后，分词，将文本表示为特征向量 ; STEP3：计算新文本特征向量和每类中心向量间的相似度，用向量间夹角的余弦来度量，公式如下 : Sim(di , jd )=)( 21211jkMkikMkjkikMkWWWW
