Web信息抽取中的文本分类

1、摘要摘 要在机器学习理论中支持向量机（SVM）有着重要的地位，无论是求解分类问题还是求解回归问题，SVM 都有着广泛的应用。本文简单的介绍了 SVM 的基本原理，讨论了 SVM 在文本分类中的应用，并详细的分析了如何利用 SVM 构造文本分类器。这里说明了文本分类的详细处理过程，并介绍了这些过程中的关键技术，如：分词技术、向量空间模型（VSM） 、特征选取技术和 SVM 的交叉验证技术等等。结合着分析和讨论又概略的说明了利用 Microsoft Visual C+ 6.0 创建文本分类系统的过程，介绍了重要的类和关键处理函数的实现和优化，以及如何利用动态链接库来实现 C+到 Java 的迁移。

2、最后给出了由本系统得到的实验数据和结论。关键字： 机器学习 文本分类 支持向量机（SVM）ABSTRACTABSTRACTSupport Vector Machines (SVM) has an important position in Machine learning theory, whether it is to solve the classification problem or request for the reunification issue, SVM has a wide range of applications. In this paper, a short intr

3、oduction into the basic principles of SVM, a detailed discussion of the SVM in the text classification, and a careful analysis of how to make use of SVM to construct classifier for a text classification. Heres the text of the detailed classification process and introduced in the course of these key

4、technologies, such as: segmentation technology, vector space model (VSM), features selection technology, cross-verification technology of the SVM and so on. With the analysis and discussion also briefly described the process of making use of Microsoft Visual C+ 6.0 to create the text classification

5、system, introduced the realization and optimization of the key class and important functions, and how to use of dynamic link library to achieve the migration from C+ to Java. Finally, the experimental data and conclusions produced by this system are shown.Keywords: machine learning text classificati

6、on SVM(support vector machine)目录目 录第一章第一章 引言引言.11.1 总体项目背景 .11.1.1 基于 Web 的信息集成系统.11.1.2 基于 Web 的信息集成系统的需求和系统结构.21.2 文本分类系统的任务和目标 .31.3 本文主要研究内容 .4第二章第二章 相关理论相关理论.72.1 文本自动分类 .72.3 支持向量机(SVM).82.4 SVM 的原理.92.4.1 线性支持向量机.92.4.2 非线性支持向量机.112.5 SVM 文本分类.13第三章第三章 需求分析需求分析.153.1 SVM 的两个阶段.153.2 训练阶段目标 .1

7、63.3 测试阶段目标 .183.4 外部接口 .18第四章第四章 总体设计与实现工具的选择总体设计与实现工具的选择.214.1 总体结构 .214.2 训练阶段 .214.2.1 分词及词频统计.214.2.2 文本向量空间模型(VSM)及文本特征选取.274.2.3 文本向量化.314.2.4 文本分类器.324.3 测试阶段 .364.3.1 分词及词频统计.36目录4.3.2 文本向量化.364.3.3 分类处理.374.4 实现工具的选择与跨语言迁移 .37第五章第五章 详细设计与实现详细设计与实现.395.1 界面设计 .395.2 配置文件 config.xml.405.3 LI

8、ST 类.405.4 Frequency 类 .425.5 partition 函数.435.6 SORT 类.465.7 预处理与文本特征的选择策略的设计 .475.8 scale 方法与 Matrix.txt 文件的生成.495.9 libsvm 调用 .515.10 动态链接库 SVMDLL.dll 的实现和接口定义.54第六章第六章 测试及结果测试及结果.576.1 二分测试 .576.2 多分测试 .596.3 测试总结 .616.3.1 二分情况.616.3.2 多分情况.62致谢致谢.63参考文献参考文献.65第一章 引言 1第一章 引言1.11.1 总体项目背景总体项目背景本文

9、主要讨论基于 Web 的信息集成系统中的一个子系统文本分类系统的设计与实现，但这里有必要介绍一下基于 Web 的信息集成系统的基本情况以及文本分类系统在整个项目中的位置与调用关系。1.1.11.1.1 基于基于 Web 的信息集成系统的信息集成系统基于 Web 的信息集成系统通过统一平台将松散的 Web 信息以统一的规范和编码集成于统一系统平台中，去除平台与系统的差异，提供统一的界面与接口，提高信息的共享与可用性。伴随着互联网技术的发展和大规模的应用，网络已经越来越深刻的影响到人们的生活和社会。人们正快步走进“网络生活”的时代，从学习、工作到生活购物，无一不深深的依赖着互联网。在过去的几年中，

10、有很多的技术与网络事物涌现并应用于现在的网络中，如：网络微应用程序、个人网页、VoIP、网络化桌面、Web2.0 技术、Ajax、网络视频等等。从学习网络到网络生活，互联网给生活带来极大方便的同时，其承载的信息却以几何基数增长着，随着网络社区化的推进和电子商务悄然兴起，快速准确的找到可用信息已越来越有其现实意义。Web 信息和服务有着分散、庞杂、大量重复、系统差别大等特点，如何能有效的屏蔽平台与系统的差异，将散乱的信息聚合成统一界面与接口的信息系统，更具有现实应用价值。但仅将信息简单聚合并不能满足用户对信息准确定位与获取的需求，而互联网信息又存在着信息概念与含义的多态性，对准确定位可用信息增加

11、了很大的难度。无论是从现在的电子商务、网络新闻还是到网络信息检索、网络信息共享，都有 Web 信息的集成需求与需要。2 Web 信息抽取中的文本分类1.1.21.1.2 基于基于 Web 的信息集成系统的需求和系统结构的信息集成系统的需求和系统结构基于 Web 的信息集成系统有着以下的需求：（1）实现多信息源信息的抽取、清洗和合并；（2）对多个信息源进行包装，去除信息源本身特征，提供统一访问接口；（3）实现数据源与系统的松耦合；（4）为用户提供统一的查询界面与结果显示；（5）根据用户的语义进行数据源的准确定位和查询优化；（6）根据用户的偏好进行信息筛选；（7）根据用户的兴趣域进行信息过滤。综合

12、上述需求提出了如图 1.1 所示的系统结构。1、用户界面用户界面层为用户提供统一、清晰的查询接口及结果呈现模式。用户通过选择领域（或兴趣区域）对结果进行领域过滤，提高查询准确度。用户同样可以通过偏好设置来选择不同的全局模式，只抽取感兴趣的信息。2、中介器中介器的功能是接收针对全局模式生成的查询，根据数据源描述信息（元数据）及映射规则将接收的查询分解为针对于每个数据源的子查询，再根据数据源描述信息进行查询计划的优化。最后将子查询发送到每个数据源的包装器。3、包装器包装器将数据源包装成 Web Service 并发布，包装器与中介器绑定之后，接受中介器发来的子查询并将这些子查询翻译成符合每个数据源

13、模型或模式的查询，并把查询结果返回给中介器。4、支持库为中介器、包装器提供数据及算法支持。5、数据源可产生结构化和半结构化的数据。第一章 引言 3查询及结果领域设置偏好设置查询分解抽取结果的合并和清洗模式映射查询分发查询分词算法库模式映射表页面生成结果VSM算法库页面向量MD5信息指纹机器学习算法库查询计划及查询语句生成网站一HTML到XML信息抽取领域过滤查询计划及查询语句生成网站二HTML到XML信息抽取领域过滤查询计划及查询语句生成网站三HTML到XML信息抽取领域过滤领域模型抽取规则库用户界面中介器包装器数据源支持库图 1.1 基于 Web 信息集成系统模型及文本分类系统的位置1.21

14、.2 文本分类系统的任务和目标文本分类系统的任务和目标文本分类系统位于基于 Web 的信息集成系统的包装器中，如图 1.1 所示，实现领域过滤功能，根据领域的需求选择相应的领域模型进行领域过滤。例如：在4 Web 信息抽取中的文本分类一个图书销售的 Web 信息集成系统中，当用户键入关键字“计算机” ，需要得到计算机领域中有关“计算机”的图书信息的时候，系统应该能够较为准确地过滤掉非计算机领域的图书信息，因为很多领域（如化学领域）的图书都会涉及到“计算机” 。文本分类系统在整个信息集成系统中仅作为一个较为独立的功能模块，所以在实现这个子系统的时候，需要做到：（1） 功能完整（2） 封装完整（3

15、） 可独立运行（4） 调用方便（5） 运行高效作为一个插件式的子系统，必须要有完整的功能来保证这个子系统的正常运行并为整个系统提供良好的支持；另一方面讲也需要将完善的功能加以封装，这样才能快速的调整和修改子系统内部的资源和工作模式。文本分类系统被设计成一个子系统而不是一个简单功能函数，这样做的一个好处就是它可以脱离总系统来调试和修改，这一点对于整个系统的开发和集成都是至关重要的。一个子系统最终要被整个系统调用，不能希望一个完全不了解文本分类系统的人完全弄懂这个子系统后再来调用，所以必须提供很好的接口，使调用者能够快速的理解和方便的调用。一个接口的好坏直接影响着整个系统集成的效率和质量。效率也是

16、一个子系统需要重点考虑的问题，一个子系统必须能够高效的完成本模块的任务，这样才成保证整个系统的响应时间，任一个模块的效率低下都有可能成为整个系统的瓶颈致使整个系统失败。1.31.3 本文主要研究内容本文主要研究内容本文主要研究基于 Web 的信息集成系统中的文本分类系统的设计与实现。下面将简要介绍后边各章节所要讨论的内容，第二章将简单的介绍文本分类所需要的理论和技术，进而研究支持向量机的理论以及这种理论如何应用于文本第一章 引言 5分类当中。在做好理论和技术的准备后，第三章将讨论 SVM 分类器的两个阶段在文本分类的过程中如何应用的问题，最后将分析外部接口定义和如何实现的问题。第四章将详细讨论

17、文本分类的 SVM 方法，经过第三章的研究和讨论，这一章提出了文本分类系统的总体结构，并分别分析了 SVM 方法在训练阶段的四个处理过程和测试阶段的工作流程。由于文本分类系统的设计和开发语言是 C+，但总系统的设计和开发语言是 Java，所以在这一章的最后一部分分析了如何实现跨语言调用的问题。第五章讨论详细设计与实现的问题，包括 LIST 类、Frequency 类和 SORT 类三个主要功能类的设计与实现，重要文件和函数的设计与实现，SVMDLL 动态链接库的实现及 Java 接口的定义等。第六章将对整个文本分类系统进行相应的测试，并以图表形式总结出测试的结论。6 Web 信息抽取中的文本分

18、类第二章 相关理论 7第二章 相关理论2.12.1 文本自动分类文本自动分类文本自动分类(Automatic Text Categorization)也就是用电脑对文本集按照一定的分类体系或标准进行自动分类标记的过程。对于总系统来说，文本的来源为 Web 文本，这种文本有着来源分散、结构松散、文本内容复杂等特点，所以对这种文本进行分类与对来源单一、结构完整、文本内容相对稳定的文献、论文等进行分类有着更多难点。首先来源分散，这使这些文本的格式或者文章涉及的内容复杂多变，很难用文章的来源或者目录索引来进行相应的分类，所以分类器或者分类方法只能根据内容进行分类。其次结构松散，这使得文本的结构不完整，

19、无法获得全部文本的题目、关键字等信息以进行分类，这就要求分类器或者分类方法能够过滤出一定的语义信息并根据这些语义信息进行分类，从某种意义说就是能够提取出区分性很好的，并且代表这篇文章的语义关键字。再次文本内容复杂，Web 文本提及的内容不一定为专业性文章，虽然谈论的主题不变，但所涉及的内容多变，比如一篇军事文章可能还会提及政治经济的内容，这要求分类器具有很强的抗干扰能力，不会因为一些非重要的内容而严重影响分类精度。综上，可以明确一点就是硬性的分类标准很难做到以上三点的分类要求，所以分类时不能简单的规定某种硬性的标准如：某个词是否出现、文章的字数、是否有数学公式等等。文本分类最容易想到使用人工的

20、方法，但面对海量的文本信息人是无能为力的，但是可以通过某种机制来模仿人的分类过程，首先人是需要经验的，没读过文章的人是无法分类文章的，所以分类器也需要学习需要训练，统计学习的理论正好满足要求，另外人是需要一套很模糊的评价标准和推理依据的，所以分类器也需要这样的逻辑过程和模糊机制，人工神经网络算法也正好满足要求。目前，常用的文本分类算法有决策树(decision tree)、人工神经网络、贝叶斯、8 Web 信息抽取中的文本分类KNN、SVM 等。综合考虑了性能、分类效果、抗干扰能力等方面的因素，决定使用 SVM 进行文本分类，SVM 算法的特性使它成为一种基于模型的分类方法，它基于统计学习的理

21、论又有人工神经网络的特点，并且在决策树(decision tree)、人工神经网络、贝叶斯等众多分类算法中，SVM 是第一个达到 KNN 分类精度的分类算法。2.32.3 支持向量机支持向量机( (SVM) )SVM 方法于 20 世纪 90 年代初由 V. Vapnik 提出。这种方法采用了结构风险最小化的思想，并完全基于超平面的方法，利用核函数进行扩展。支持向量机是数据挖掘中的一个新方法，能非常成功地处理回归问题(时间序列分析)和模式识别(分类问题、判别分析)等诸多问题，并可推广于预测和综合评价等领域，因此可应用于理科、工科和管理等多种学科。目前国际上支持向量机在理论研究和实际应用两方面都

22、正处于飞速发展阶段。它广泛的应用于统计分类以及回归分析中。支持向量机属于一般化线性分类器，他们也可以被认为是提克洛夫规则化（Tikhonov Regularization）方法的一个特例。这一族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。分类的过程是一个机器自动学习的过程这是所希望的。数据通常是 n 维实空间中的点，这里希望能够把这些点通过一个 n-1 维的超平面分开，这个分类器被称为线性分类器。有很多分类器都符合这个要求，但是这里还希望能够找到分类最佳的平面，即使得属于两个不同类别的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果

23、能够找到这个面，那么这个分类器就称为最大间隔分类器。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其假定为，平行超平面间的距离或差距越大，分类器的总误差越小。下边将详细说明一下支持向量机的原理。充分的理解支持向量机的原理可以有效的帮助分析和理解哪些因素能够决定 SVM 的分类精度，以及在中文文本分第二章 相关理论 9类中这些决定性的因素表现为什么。2.42.4 SVM 的原理的原理本节中出现的部分公式引自 Usama Fayyad 的A Tutori

24、al on Support Vector Machines for Pattern Recognition或者基于此文中的定义方式，并配以本人解释和简要说明。2.4.12.4.1 线性支持向量机线性支持向量机如图 2.1 所示，对于可分离的情况，图中黑点和白点为需要分离的两类点，一个超平面将两类点分开，并且在两侧有平行且等距于的超平面和，HHH1H2H和将两类点分隔在它们之外。一些临界点就位于和之上。1H2H1H2H对于支持向量机来说，它的分类过程是分两个阶段的：训练阶段和测试阶段。在训练阶段，支持向量机的目标就是要寻找到这样的一个超平面，它到H和的距离最大，使得和之间有最大的分类间隔。这时的

25、超平面被1H2H1H2HH成为最大可分离超平面，根据结构风险最小化的思想，可以知道，和之间1H2H的分类间隔越大，SVM 的经验风险就越小，所以可以通过最大化和之间的1H2H分类间隔来最小化实际风险，这也就体现出了 SVM 结构风险最小化的思想。图中为超平面的法线，为原点到超平面的距离，在实际的wH()/ |bwH求解过程中，可以将这个求解最优化的问题利用拉格朗日乘数法转变为相应的拉格朗日表达式进行求解，为了求解方便一般还要将拉格朗日表达式转化为对偶形式（这也就是 SVM 会被认为是提克洛夫规则化方法的一个特例的原因） ，这个对偶式连同 KKT 条件就可以求解到最优条件下的和。伴随着和的确定也

26、就wbwb将最大可分离超平面确定了，但这里还得到计算过程的一些副产品支持向H量，由于支持向量位于和上，所以支持向量对分类来说更有实用价值。1H2H综上，一个明确的事实是：有了支持向量，其它点的意义已经不大了，因为10 Web 信息抽取中的文本分类仅依靠支持向量就足以重新构造。H在测试阶段，由于有了前边得到的支持向量，可以很容易的找到最大可分离超平面，所以只要检验测试数据位于哪侧即完成分类工作。HH图 2.1 可分离情况下的线性可分离超平面 圆环是支持向量1上边算法用于可分离数据，对于不可分离的数据来说，可以引入一个正的松弛变量来解决问题，如图 2.2，这里出现了一个不可分离的黑点，为此()/

27、|w黑点到的距离。2H图 2.2 不可分离情况下的线性可分超平面1求解的思想和方法与可分离的情况基本相同，唯一不同的是，在不可分类情况下会多一个 KKT 补充条件，因为这里也多了一个变量。图 2.3 展示了两类模式识别或分类的问题，一个可分离一个不可分离。待分的两类分别由黑点和暗点表示，而支持向量被多加了一个小环。不可分离情况下的错分点被多加了一个叉形来标识。第二章 相关理论 11图 2.3 线性情况下可分离(左)不可分离(右) 背景色表明了决策面的形状12.4.22.4.2 非线性支持向量机非线性支持向量机如何将上边的方法推广到决策函数是非线性函数的情况仍然是个问题。训练问题中数据都是以点积

28、的形式出现。所以可以假设使用叫做的ijx x映射，映射数据到某个其他的（可能是无限维）欧式空间：H 式（2-:d R H1）于是训练算法也就只依靠数据在上的点积，即的形式。现在H ijxx如果有个“核函数”使，就只需要在训练算法中使用K ,ijijK x xxx而不需要明确的知道是什么。K由于是无限维的，所以明确知道是什么是不可能的。但是，如果将训H练算法中的每个都由代替，那么就会产生一个无限维空间中的支,ijx x,ijK x x持向量机，此外这样做消耗的时间和训练没有映射的数据所消耗的时间大体上是一样的。所有需要考虑的仍然是在做线性分离，只不过是在不同的空间。在测试阶段，只要以同样的方式进

29、行计算就可以了。 ,iiK s xsx需要明确的是不是所有函数都存在这样的二元组使它成为核函数，但,H可以通过 Mercer 条件来进行判断(Vapnik, 1995;Courant and Hilbert, 1953)：如果存在一个映射和一个展开式 式（2- ,iiiKx yxy12 Web 信息抽取中的文本分类2）当且仅当对于任何都有 g x是有限的 式（2- 2gdxx3）那么 式（2- ,0Kggd d x yxyx y4）如果使用不满足 Mercer 的条件的核函数对于二次规划的问题是无解的。但是在这种情况下训练过程仍然是收敛的可以完成的。三个最常用的核函数如下： 式（2- ,1pK

30、x yx y5） 式（2-22| /2( , )Kex yx y6） 式（2-,tanh()Kkx yx y7）等式（2-5）被称为多项式核函数，等式（2-6）被称为高斯径向基核函数，等式（2-7）被称为 Sigmoid 核函数。图 2.4 展示了与图 2.3 中相同的分类问题的结果，但是这里的核函数选择了三次多项式。注意到对于线性可分的情况（左侧图）尽管三次多项式核函数的自由度更高，但结果还是粗略的为一条直线，说明分类能力是受到限制的；但是对于线性不可分的情况（右侧图），它已经变得可分了。第二章 相关理论 13图 2.6 度为 3 的多项式核函数 背景色展示了决策边界的形状1最后，尽管上边描

31、述SVM分类器都是二分分类器，但它们是很容易联合起来解决多分的情况的。一个简单的联合方法就是为一个N类的分类问题训练N个one-vs-rest分类器（也就是说，“一个”为正向的，“其余”都为负向），然后将测试数据分入到具有最大的正向距离的一类中，这个方法与决策树工作方法极为类似。2.52.5 SVM 文本分类文本分类前边已经说过 SVM 在分类方面的表现相当优秀，通过 2.4 节的说明，知道SVM 是数学上的一套方法，所以 SVM 是无法处理非数字的东西的，比如文字、图片和声音等等，但有时又有必要对这些集合进行分类。对于计算机中的图片和声音而言，这一点是很容易转换或者解释的，那就是这些图片和声

32、音在计算机中的存储形式就是数字化，这就提供了应用 SVM 进行图片和声音分类的数字基础，所以在经过滤波、降噪等等一系列预处理后，就可以通过训练来训练出一个需要的 SVM 分类模型。当需要分类的时候只需要把数据经过相同的预处理，就可以应用这个分类模型来分类了！而对于计算机中的文字来说，其存储形式虽然也是数字化的，比如ANSII、Unicode 等等，但这些是无法直接拿来用 SVM 处理的，这是为什么？首先，可以明确的是图片和声音的数字化是能够直接反应这些图片或者声音本质的，也就是说这些数字可以说明或者表达出这个图片或者声音中有什么，而单纯的 ANSII 或者 Unicode 序列是不能的，因为不

33、能通过这样的一个单纯的序列来断定文本的意思，文本中意思的传达是通过词语实现的，离散的单字是无法表14 Web 信息抽取中的文本分类达出文本的语义信息的，这就像盲人摸象一般。其次，如果采用这种 ANSII 或者 Unicode 序列来进行文本分类，得到的结果就是，这两篇文章在外表上很像，也就是说字符串的序列差别很小，这类似于说两个人长得很像，却没有说明两个人的职业相同。再次，在中文中存在着一字或一词多词性和多语义的问题，如果仅仅依靠字符而不考虑词性的问题，同样也会影响分类精度，同时有些词语如介词、助词、副词等对语义的表达无关紧要，所以一并处理不但浪费时间而且会降低分类精度。综上，SVM 在文本分

34、类中，必须要对文本进行某种特殊数字化的处理，这种处理是基于词语的语义和词性的，可以将一篇文章以某种向量化的形式表现出来，这个过程称之为文本向量化的过程。这个过程也就是决定 SVM 文本分类精度的关键因素，其目标就是尽量降低文本不可分的程度。只有经过向量化的文本才能使用 SVM 进行训练和测试。具体怎样进行向量化以及如何通过提高特征的选取的质量来降低文本不可分的程度都将在第四章中讨论。第三章 需求分析 15第三章 需求分析3.13.1 SVM 的两个阶段的两个阶段SVM 在使用的过程中是分两个阶段的，一个是训练阶段也可以被称为学习阶段，另一个是测试阶段也可以称为使用阶段。图 3.1 为 SVM

35、两个阶段的模型。训练阶段实际上就是利用统计学习的理论来总结经验的过程，SVM 基于结构风险最小化的思想，寻找训练数据分界面，也就是“分离超平面” 。首先 SVM将这些低维空间线性不可分的数据利用满足 Mercer 的条件的核函数映射到高维空间来实现线性可分，然后利用拉格朗日乘数法求解这个最优化的过程，为了降低运算难度将拉格朗日表达式转化为其对偶形式，利用梯度表达式进行支持向量的求解，并利用支持向量和 KKT 条件推导的不等表达式求解出最优超平面。训练模型训练数据集测试测试数据集结果图 3.1 SVM 处理过程的两个阶段在测试阶段 SVM 重新载入训练阶段所保存下来的支持向量，还原最优超平面，将

36、测试数据带入最优超平面的表达式得到分类结果。对于总系统来说，并不需要关心训练阶段怎样完成，也不需要关心训练用了多少数据和时间，它所需要关心的就是如何调用实现好的接口来完成测试阶段。所以可以这样说，训练阶段的效率高低并不重要，但测试阶段的效率就要重要的多，如果太慢它将成为整个系统的瓶颈。16 Web 信息抽取中的文本分类对于本子系统来说，训练阶段则要重要的多，因为测试阶段是依赖于训练阶段的，训练阶段为测试阶段提供所需要的文件和分类模型，没有训练阶段测试阶段就无法完成；另外训练阶段的训练质量也严重地影响到测试阶段的分类精度，如训练数据集的代表性、分类器的参数选择、训练数据集的数据模式等等。3.23

37、.2 训练阶段目标训练阶段目标文本分类系统在训练阶段对文本要利用向量空间模型（VSM）的方法进行向量化。首先利用分词和词频统计的方法将文本分解，然后利用一定的特征词选择策略进行特征选择，并将文本分词相对于文本特征集进行向量化，而这个过程也就是文本向量化的过程。从某种意义上说这种文本向量就反应出了文本描述的主题内容，而按照策略选择出的文本特征集是很具有区分性和代表性的，所以文本向量在一定程度上是可以反应出文本相似度的。如下结论也是成立的：相同文本其相对于同样的文本特征集的文本向量必然相同，不同的文本其文本向量的相似度越大，文本向量的差值就越小。由于文本分类系统的训练阶段相对独立且处理过程和策略很

38、多，所以在这个子系统中应该达到以下几个目标：（1）准确、快速、稳定的分词系统。这要求分词系统能够有效的识别词语的词性并正确处理文本的二义性进行准确的分词，分词系统还必须具有良好的数据结构和高效的算法能够高速的处理海量的分词请求，在处理的过程中不会因为外界的因素而引起分词的不确定，也不会因为文本格式的问题而产生任何的异常，能够处理任意复杂的文本环境。另外分词系统还必须能够过滤一些无用词语并增加一些用户自定义的词语。分词处理的开销将占本系统开销的 60%，所以分词系统好坏直接影响到系统成败。（2）高速的词频统计功能。词频统计必须能够同步的伴随分词处理进行高效准确的词频统计。（3）较为健全的特征选择

39、策略。由于待分类的文本的多样性，必须要提供较为健全的特征选择策略。不同的文本在不同的策略下所达到的分类效率和精度将会不同。第三章 需求分析 17图 3.2 经过 scale 后的分类精度由 66.925%提高到 96.15% （4）高速稳定向量化方式。在文本向量化的过程中必须能对向量进行 scale操作，也就是要能将向量映射到某个范围空间中，如（0.1）空间，这样可以降低SVM 的运算复杂度提高运行效率，一定程度上也能提高分类精度，如图 3.2 所示。（a）训练数据和过度拟合分类器 （b）在测试数据上使用过度拟合分类器（c）训练数据和更好的分类器 （d）在测试数据上使用更好的分类器18 Web

40、 信息抽取中的文本分类图 3.3 一个过度拟合的分类器和一个更好的分类器（和：训练数据 和：测试数据）（5）能够对 SVM 的参数进行自动的优化。对 SVM 的分类参数进行优化不但可以提高 SVM 的分类精度而且可以极大的提高 SVM 的工作效率。通过交叉验证的方式对参数进行优化，可以对分类器进行全局最优化防止过度拟合情况的发生，如图 3.3。（6）由于上述操作涉及内容加多，可控可变的参数也很多，所以必须提供图形化的界面工具方便训练阶段的完成。（7）训练阶段完成后必须能够向测试阶段提供特征文件和分类模型。3.33.3 测试阶段目标测试阶段目标测试阶段的基本处理过程与训练阶段极为相似，所以在这个

41、阶段可以大量复用训练阶段的数据结构和方法。在测试阶段不进行文本特征的筛选，仅利用训练阶段保存的文本特征文件重新载入文本特征，并参照文本特征进行文本向量化，SVM 载入训练阶段生成的分类模型对文本向量进行分类并保存分类结果。在这个阶段需要达到一下几个目标：（1）快速的载入文本特征；（2）准确、快速、稳定的分词系统；（3）高速的词频统计；（4）快速的对文本进行向量化和 scale 操作；（5）SVM 载入分类模型快速分类。测试阶段的效率关系到总系统的效率，而在这个阶段分词及词频统计的开销将占到总开销的 80%左右，所以无论在训练阶段还是在测试阶段分词系统的好坏至关重要。3.43.4 外部接口外部接

42、口在训练阶段的处理中需要一个完善的图形化的工具来辅助完成训练任务，但在测试阶段必须将整个工作流程封装在一起能够自动的完成，对于总系统来说，它并不关心是否有训练阶段还是有测试阶段，唯一需要的就是方便的调用提供的第三章 需求分析 19方法来完成分类处理。提供一个良好的接口（如图 3.4）对于后期的集成同样至关重要：（1）完好的封装性，封装完整有效地屏蔽了实现细节并实现了保密性。图 3.4 接口模型（2）简单，封装好的接口相对简单，函数名称和参数名称直观易懂。（3）方便，接口函数的数量有限且功能完善，调用时有足够的返回，能够有效的定位错误。（4）对于跨语言的调用提供良好的调用接口，不需要在接口外部进

43、行跨语言平台的处理。20 Web 信息抽取中的文本分类第四章 总体设计与实现工具的选择 21第四章 总体设计与实现工具的选择4.14.1 总体结构总体结构在综合考虑了第三章中提出的各种需求的情况下，这里提出了文本分类系统的总体结构如图 4.1。以下将分析各个过程的作用和其中使用的关键技术。文本特征选取文本特征词频统计表文本向量化支持向量机分类模型训训练练阶阶段段格式化文本集停用词分词词频统计词频统计表文本向量化支持向量机分类结果分分类类阶阶段段文本向量矩阵文本向量矩阵分类设置分词词频统计训练文本集图 4.1 文本分类系统的整体工作模型4.24.2 训练阶段训练阶段4.2.14.2.1 分词及词

44、频统计分词及词频统计在本系统中时间复杂度是最大的挑战，所以必须在设计的过程中尽量降低时间的消耗。分词与词频统计绝对是可以分开实现的，但如果这样在分词处理后还要经过词频统计的处理消耗了双份的时间，这样做并不高效。所以在 3.2 节中提22 Web 信息抽取中的文本分类出的使用快速高效的词频统计方法伴随分词处理一并完成词频统计的工作更为高效一些。这里也有必要说明一下中文分词技术，它对这一步处理以及整个分类的系统来说都是至关重要的。4.2.1.14.2.1.1 中文分词技术中文分词技术对中文分词技术有所了解，可以明白分词好坏的评价标准，进而有助于对分词系统的选择。中文分词技术属于自然语言处理技术范畴

45、，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解18的分词方法和基于统计的分词方法。1、基于字符串匹配的分词方法这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词） 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的

46、一体化方法。常用的几种机械分词方法如下：正向最大匹配法（由左到右的方向）逆向最大匹配法（由右到左的方向）最少切分（使每一句中切出的词数最小）还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为 1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高

47、切分的准确率。第四章 总体设计与实现工具的选择 23一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。2、基于理解的分词方法这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子

48、系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。3、基于统计的分词方法从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字 X、Y 的相邻共现

49、概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一” 、 “之一” 、 “有的” 、 “我的” 、 “许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识

50、别生词、自动消除歧义的优点。到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。笔者了24 Web 信息抽取中的文本分类解，海量科技的分词算法就采用“复方分词法” ，所谓复方，相当于用中药中的复方概念，即用不同的药材综合起来去医治疾病，同样，对于中文词的识别，需要多种算法来处理不同的问题。有了成熟的分词算法，是否就能容易的解决中文分词的问题呢？事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。（1）歧义识别歧义是指同样的一句话，可能有两种或者更多的切分

51、方法。例如：表面的，因为“表面”和“面的”都是词，那么这个短语就可以分成“表面 的 ”和“表 面的 ” 。这种称为交叉歧义，这种交叉歧义十分常见。 “化妆和服装”可以分成“化妆和服装 ”或者“化妆 和服 装 ” 。由于没有人的知识去理解，计算机很难知道到底哪个方案正确。交叉歧义相对组合歧义来说还算比较容易处理，组合歧义就必须根据整个句子来判断了。例如，在句子“这个门把手坏了”中， “把手”是个词，但在句子“请把手拿开”中， “把手”就不是一个词；在句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三年中将增长两倍”中， “中将”就不再是词。如果交叉歧义和组合歧义计算机都能解决的话，在

52、歧义中还有一个难题，是真歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应该不是词。例如：“乒乓球拍卖完了” ，可以切分成“乒乓 球拍 卖完 了 ” 、也可切分成“乒乓球 拍卖 完 了 ” ，如果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一个词。（2）新词识别新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了”中， “王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎”作为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录

53、这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的”中， “王军虎”还能不能算词？第四章 总体设计与实现工具的选择 25新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。4.2.1.24.2.1.2 实现工具实现工具 ICTCLAS 3.1正是由于中文分词技术存在着上述固有的难题所以目前并没有一套十全十美的解决方案。而较为成功的中文分词系统也不多见，尽管这样也有必

54、要选择一个高效的分词系统来为本系统服务的。一、海量中文智能分词海量中文智能分词由海量信息技术有限公司推出，这也是目前国内唯一实现商业化服务的中文智能分词系统。海量也是唯一一家专业从事中文智能计算及信息数据挖掘技术的理论研究、技术开发的国内公司。这套分词系统服务方向极为广泛，处理性能优秀。其切分准确率达 99.7%，分词速度为 2000 万字/分钟，操作扩展极为灵活，并支持多平台，多码制，多线程的应用。在歧义识别和新词识别方面有很好的性能和质量，同时也提供了多分词颗粒的选择及语义指纹等特色功能。二、ICTCLASICTCLAS(Institute of Computing Technology,

55、 Chinese Lexical Analysis System)由中国科学院计算技术研究所推出，主要功能包括中文分词、词性标注、命名实体识别、新词识别、同时支持用户词典。ICTCLAS 是目前综合性能最优分词系统，ICTCLAS3.0 分词速度单机 996KB/s，分词精度 98.45%，API 不超过 200KB，各种词典数据压缩后不到 3M。它全方位支持各种环境下的应用开发ICTCLAS 全部采用 C/C+编写，支持 Linux、FreeBSD 及 Windows 系列操作系统，支持C/C+、C#、Delphi、Java 等主流的开发语言。ICTCLAS 为免费系统，在综合考虑分词系统的

56、速度、方便程度和价格等因素后，最终决定采用 ICTCLAS 最新 3.1 版分词系统。表 4.1 为本系统用到 ICTCLAS 3.1 中的几个接口函数和数据结构：26 Web 信息抽取中的文本分类表 4.1 使用到的接口函数函数参数描述bool ICTCLAS_Init(const char * sInitDirPath=NULL)sInitDirPath 初始化目录地址（配置文件和词库）初始化分词系统bool ICTCLAS_Exit()分词系统退出ICTCLAS_API const result_t *ICTCLAS_ParagraphProcessA(const char *sPara

57、graph,int *pResultCount)sParagraph 待分词字符串pResultCount 分词个数进行分词处理并将结果集地址返回给result_t 类型指针图 4.2 ICTCLAS 的分词结果集数据结构在图 4.2 所示的结构中：start 词语在输入句子中的开始位置length 词语的长度POS_id 词性 ID 值，可以快速的获取词性表ID 词语 ID 如果是未登录词，设成 0 或者-14.2.1.34.2.1.3 中文停用词中文停用词在分词和词频统计的时候有比要过滤掉一部分无用的中文词语，比如：的、地、之等大量出现而对文本分类没有好处的词语。实践过程中发现仅通过停用词

58、的过滤方式并不完善，因为这样过滤掉的词语数量较少没有达到提高效率的目的。现代汉语中使用率最高的三类词分别是名词、动词和形容词，而在一个文本中能够反映文本主题或者语义的词语主要都是名词和动词，所以按词性进行过滤第四章 总体设计与实现工具的选择 27的效果会更好更加明显。在分词的结果集中 POS_id 就反映了词语的词性。所以这里的中文停用词仅为辅助的过滤手段，主要的目的是过滤掉名词和动词中需要特别过滤掉的词语。4.2.1.44.2.1.4 英文停用词英文停用词在 ICTCLAS 中字符串或者说英文词都是作为未登陆词处理的，词语的 ID一般是设为-1 的，在 Web 文本中经常出现机构名的缩写、英

59、文中的介词、网址等等这样无关紧要的字符串，而这些字符串往往又大量的出现，这必然引起词频统计工作的浪费，而且也会降低分类精度，所以也有必要将这些词或者字符串过滤掉。4.2.1.54.2.1.5 用户字典用户字典在分词系统中都有未登陆词识别的功能，但它不一定总是能满足的要求，比如将两个未登陆的词分开识别，而需要的词语是两个词语连在一起的新词。这时就有必要让用户自己能够定义一些新词，而户字典的目的就是记录这些用户定义的新词。有时虽然分词分出的两个词都是登陆的词，但是需要的词是两个词连在一起的新词，如：“你好啊” ，你好是一个登陆词， “啊”也是一个登陆词，但希望分词能够将它们分在一起，这时也需要用户

60、字典来定义这样的新词。4.2.24.2.2 文本向量空间模型文本向量空间模型( (VSM) )及文本特征选取及文本特征选取前边分析得出文本是不能直接进行向量化的，是需要进行特殊的向量化处理的。这里使用文本向量空间模型的方法对文本进行向量化，也就是基于特征词的向量化过程。4.2.2.14.2.2.1 文本特征及文本相似度文本特征及文本相似度文本特征就是通过某种选择策略选择出来的若干词语，对于一篇文章来说，它的文本特征的选择策略应该反映了这篇文章主旨或者说是它的主要内容，而对于多篇文章来说，它们文本特征的选择策略则应该反映出了这些文章的共同点，28 Web 信息抽取中的文本分类这种共同点可以是文章