数据挖掘中的文本挖掘的分类算法综述

数据挖掘中的文本挖掘的分类算法综述 摘要 随着Internet上文档信息的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析；最后对全文工作进行了总结和展望。 关键词：数据挖掘，文本挖掘，文本分类算法 ABSTRACT With the development of Web 2.0, the number of documents on the Internet increases exponentially. One important research focus on how to deal with these great capacity of online documents. Text classification is one crucial part of information management. In this paper we first introduce the basic information of data mining, including the methods, contents and the main existing problems in data mining fields; then we discussed the text mining, one active field of data mining, to provide a basic foundation for text classification. And several common algorithms are analyzed in Chapter 3. In chapter 4 thorough research of KNN text classification algorithms are illustrated including the statistical and dimension reduction based on LSA and in chapter 5 we make some predictions for data mining, text mining and text classification and finally we conclude our work. KEYWORDS： data mining, text mining, text classification algorithms，KNN 目录 摘要    1 ABSTRACT    1 目录    2 第一章 数据挖掘概述    3 1.1 数据挖掘介绍    3 1.2 数据挖掘常用方法    4 1.3 数据挖掘的功能    5 1.4 数据挖掘的主要问题    5 第二章 文本挖掘概述    8 2.1 文本挖掘介绍    8 2.1.1 文本挖掘的历史演化    8 2.1.2文本挖掘的定义    8 2.1.3文本挖掘的研究现状    9 2.2 文本挖掘主要内容    9 2.3 文本挖掘技术    10 2.3.1 数据预处理技术    10 2.3.2 数据挖掘分析技术    11 2.4 文本挖掘热点难点问题    12 第三章 文本分类算法    14 3.1 文本分类概述    14 3.1.1 文本分类的研究现状    14 3.1.2 文本分类模型    15 3.1.3 文本分类面临的挑战    17 3.1.4 文本分类亟需解决的问题    18 3.2 常用文本分类算法    18 3.2.1 文本分类中的特征选择方法    19 3.3.2 支持向量机文本分类算法    22 3.3.3 朴素贝叶斯文本分类算法    23 第四章 KNN文本分类算法研究    27 4.1 KNN文本分类算法介绍    27 4.2 基于统计的KNN文本分类算法研究    27 4.3 基于LSA降维的KNN文本分类算法研究    30 4.4 其他改进的KNN文本分类算法    31 第五章 文本挖掘应用    34 5.1 数据挖掘应用    34 5.1.1 数据挖掘解决的典型商业问题    34 5.1.2 数据挖掘在市场营销的应用    34 5.1.3 数据挖掘在企业危机管理中的应用    35 5.2 文本挖掘应用    37 5.3 文本分类应用    37 第六章 结论    39 参考文献    40 第一章 数据挖掘概述 1.1 数据挖掘介绍 需要是发明之母。近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理，生产控制，市场分析，工程设计和科学探索等[1]。 数据挖掘出现于20世纪80年代后期，是数据库研究中一个很有应用价值的新领域，是一门交叉性学科，融合了人工智能、数据库技术、模式识别、机器学习、统计学和数据可视化等多个领域的理论和技术．数据挖掘作为一种技术，它的生命周期正处于沟坎阶段，需要时间和精力去研究、开发和逐步成熟，并最终为人们所接受。20世纪80年代中期，数据仓库之父W．H．In-mon在《建立数据仓库》(Building the Data Warehouse)一 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 中定义了数据仓库的概念，随后又给出了更为精确的定义：数据仓库是在企业管理和决策中面向主题的、集成的、时变的以及非易失的数据集合。与其他数据库应用不同的是，数据仓库更像一种过程—对分布在企业内部各处的业务数据的整合、加工和分析的过程。传统的数据库管理系统(database management system，DBMS)的主要任务是联机事务处理(on-line transaction processing，OLTP)；而数据仓库则是在数据分析和决策方面提供服务，这种系统被称为联机分析处理(on-line analytical processing，OLAP)．OLAP的概念最早是由关系数据库之父E．F．Codd于1993年提出的。当时，Codd认为OLTP已不能满足终端用户对数据库查询分析的需要，结构化查询语言(structured query language，SQL)对数据库进行的简单查询也不能满足用户分析的需求．用户的决策分析需要对关系数据库进行大量计算才能得到结果，因此Codd提出了多维数据库和多维分析的概念。 数据挖掘(Data Mining)，就是从存放在数据库，数据仓库或其他信息库中的大量的数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现(Knowledge Discovery in Database, KDD)， 也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程以下三个阶段组成：(1) 数据准备，(2)数据挖掘，(3) 结果表达和解释。数据挖掘可以与用户或知识库交互。 并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索（information retrieval）领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。 数据挖掘利用了来自如下一些领域的思想：(1) 来自统计学的抽样、估计和假设检验，(2) 人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。一些其他领域也起到重要的支撑作用。特别地，需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能（并行）计算的技术在处理海量数据集方面常常是重要的。分布式技术也能帮助处理海量数据，并且当数据不能集中到一起处理时更是至关重要。因此，数据挖掘被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科。 1.2 数据挖掘常用方法 利用数据挖掘进行数据分析常用的方法主要有分类、回归分析、聚类、关联规则、特征、变化和偏差分析、Web页挖掘等， 它们分别从不同的角度对数据进行挖掘。 (1) 分类。分类是找出数据库中一组数据对象的共同特点并按照分类模式将其划分为不同的类，其目的是通过分类模型，将数据库中的数据项映射到某个给定的类别。它可以应用到客户的分类、客户的属性和特征分析、客户满意度分析、客户的购买趋势预测等，如一个汽车零售商将客户按照对汽车的喜好划分成不同的类，这样营销人员就可以将新型汽车的广告手册直接邮寄到有这种喜好的客户手中，从而大大增加了商业机会。 (2) 回归分析。回归分析方法反映的是事务数据库中属性值在时间上的特征，产生一个将数据项映射到一个实值预测变量的函数，发现变量或属性间的依赖关系，其主要研究问题包括数据序列的趋势特征、数据序列的预测以及数据间的相关关系等。它可以应用到市场营销的各个方面，如客户寻求、保持和预防客户流失活动、产品生命周期分析、销售趋势预测及有针对性的促销活动等。 (3) 聚类。聚类分析是把一组数据按照相似性和差异性分为几个类别，其目的是使得属于同一类别的数据间的相似性尽可能大，不同类别中的数据间的相似性尽可能小。它可以应用到客户群体的分类、客户背景分析、客户购买趋势预测、市场的细分等。 (4) 关联规则。关联规则是描述数据库中数据项之间所存在的关系的规则，即根据一个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系。在客户关系管理中，通过对企业的客户数据库里的大量数据进行挖掘，可以从大量的记录中发现有趣的关联关系，找出影响市场营销效果的关键因素，为产品定位、定价与定制客户群，客户寻求、细分与保持，市场营销与推销，营销风险评估和诈骗预测等决策支持提供参考依据。 (5) 特征。特征分析是从数据库中的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征。如营销人员通过对客户流失因素的特征提取，可以得到导致客户流失的一系列原因和主要特征，利用这些特征可以有效地预防客户的流失。 (6) 变化和偏差分析。偏差包括很大一类潜在有趣的知识，如分类中的反常实例，模式的例外，观察结果对期望的偏差等，其目的是寻找观察结果与参照量之间有意义的差别。在企业危机管理及其预警中，管理者更感兴趣的是那些意外规则。意外规则的挖掘可以应用到各种异常信息的发现、分析、识别、评价和预警等方面。 (7) Web页挖掘。随着Internet的迅速发展及Web 的全球普及， 使得Web上的信息量无比丰富，通过对Web的挖掘，可以利用Web 的海量数据进行分析，收集政治、经济、政策、科技、金融、各种市场、竞争对手、供求信息、客户等有关的信息，集中精力分析和处理那些对企业有重大或潜在重大影响的外部环境信息和内部经营信息，并根据分析结果找出企业管理过程中出现的各种问题和可能引起危机的先兆，对这些信息进行分析和处理，以便识别、分析、评价和管理危机。 1.3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能。 （1）自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。 （2）关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 （3）聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和数学分类学。80年代初，Mchalski提出了概念聚类技术牞其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些片面性。 （4）概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 （5）偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。 1.4 数据挖掘的主要问题 数据挖掘的主要问题，涉及挖掘方法、用户交互、性能和各种数据类型。这些问题介绍如下： 1. 数据挖掘技术和用户交互问题：这反映所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知识的使用、临场即席挖掘和知识可视化。 a) 挖掘数据库中不同类型的知识：由于不同的用户可能对不同类型的知识感兴趣，数据挖掘应当涵盖范围很广的数据分析和知识发现任务，包括数据特征化、区分、关联与相关分析、分类、预测、聚类、离群点分析和演变分析（包括趋势和相似性分析）。这些任务可能以不同的方式使用相同的数据库，并需要开发大量数据挖掘技术。 b) 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交互的。对于包含海量数据的数据库，首先应当使用适当的抽样技术，进行交互式数据探查。交互式挖掘允许用户聚焦搜索模式，根据返回的结果提出和精炼数据挖掘请求。特别，类似于OLAP对数据立方体所做的那样，应当通过交互地在数据空间和知识空间下钻、上卷和旋转来挖掘知识。用这种方法，用户可以与数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发现模式。 c) 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过程，并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发现的模式的兴趣度。 d) 数据挖掘查询语言和特定的数据挖掘：关系查询语言（如SQL）允许用户提出特定的数据检索查询。类似地，需要开发高级数据挖掘查询语言，使得用户通过说明分析任务的相关数据集、领域知识、所挖掘的知识类型、被发现的模式必须满足的条件和约束，描述特定的数据挖掘任务。这种语言应当与数据库或数据仓库查询语言集成，并且对于有效的、灵活的数据挖掘是优化的。 e) 数据挖掘结果的表示和可视化：发现的知识应当用高级语言、可视化表示或其他表示形式表示，使得知识易于理解，能够直接被人们使用。如果数据挖掘系统是交互的，这一点尤其重要。这要求系统采用有表达能力的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 f) 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况或不完全的数据对象。在挖掘数据规律时，这些对象可能搞乱分析过程，导致所构造的知识模型过分拟合数据。其结果是，所发现的模式的准确性可能很差。需要处理数据噪声的数据清理方法和数据分析方法，以及发现和分析异常情况的离群点挖掘方法。 g) 模式评估即兴趣度问题：数据挖掘系统可能发现数以千计的模式。对于给定的用户，所发现的许多模式都不是有趣的，因为它们表示常识或缺乏新颖性。关于开发模式兴趣度的评估技术，特别是关于给定用户类，基于用户的信念或期望，评估模式价值的主观度 量仍然存在一些挑战。使用兴趣度度量或用户指定的约束指导发现过程和压缩搜索空间是又一个活跃的研究领域。 2. 性能问题：这包括数据挖掘算法的有效性、可伸缩性和并行处理。 a) 数据挖掘算法的有效性和可伸缩性：为了有效地从数据库的海量数据中提取信息，数据挖掘算法必须是有效的和可伸缩的。换一句话说，数据挖掘算法在大型数据库中的运行时间必须是可预计的和可接受的。从数据库的知识发现角度，有效性和可伸缩性是数据挖掘系统实现的关键问题。上面讨论的挖掘方法和用户交互的大多数问题，也必须考虑有效性和可伸缩性。 b) 并行、分布和增量挖掘算法：许多数据库的巨大规模、数据的广泛分布和一些数据挖掘算法的计算复杂性是促使开发并行和分布式数据挖掘算法的因素。这种算法将数据划分成若干部分，并行处理，然后合并每部分的结果。此外，有些数据挖掘过程的高开销导致了对增量数据挖掘算法的需要。增量算法与数据库更新结合在一起，而不必“从头开始”挖掘全部数据。这种算法增量地进行知识修改、修正和加强业已发现的知识。 3. 关于数据库类型的多样性问题： a) 关系的和复杂的数据类型的处理：由于关系数据库和数据仓库已经广泛使用，为这样的数据开发有效的数据挖掘系统是重要的。然而，其他数据库可能包含复杂的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据。由于数据类型的多样性和数据挖掘的目标不同，指望一个系统挖掘所有类型的数据是不现实的。为挖掘特定类型的数据应当构造特定的数据挖掘系统。因此，对于不同类型的数据，期望有不同的数据挖掘系统。 b) 从异构数据库和全球信息系统挖掘信息：局域网和广域网（如因特网）连接了许多数据源，形成了庞大的分布和异构数据库。从具有不同数据语义的结构化的、半结构化的和非结构化的不同数据源发现知识，对数据挖掘提出了巨大挑战。数据挖掘可以帮助发现多个异构数据库中的高层数据规律，这些规律多半难以被简单的查询系统发现，并可以改进异构数据库信息交换和互操作性能。Web挖掘发现关于Web内容、Web结构、Web 使用和Web动态情况的有趣知识，已经成为数据挖掘的一个非常具有挑战性和快速发展的领域。 以上问题是数据挖掘技术未来发展的主要需求和挑战。在近来的数据挖掘研究和开发中，一些挑战已经在一定程度上受到关注，并且现在认为是必需的，而另一些仍处于研究阶段。 第二章 文本挖掘概述 2.1 文本挖掘介绍 2.1.1 文本挖掘的历史演化 数据挖掘技术本身就是当前数据技术发展的新领域,文本挖掘则发展历史更短。传统的信息检索技术对于海量数据的处理并不尽如人意,文本挖掘便日益重要起来,可见文本挖掘技术是从信息抽取以及相关技术领域中慢慢演化而成的。 一篇重要的关于文本挖掘的 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 讲述在赫尔辛基大学进行的研究试验。因为出现越来越多的非结构化文本资源,他们将数据挖掘技术应用于文本资源这个小组成功地运用数据库中的知识发现技术( KDD) 。他们曾经发表了试图将数据挖掘技术直接应用于经过预处理的文本信息的论文。他们将预处理过程看作是一个至关重要的环节,从而有效地改变了数据挖掘依赖于文本最初是如何被处理的这一法则。沿着知识发现这条路,Feldman考虑使用信息抽取中最简单的形式来获取知识:通过为一篇文本建立一个有意义的概念集合来看清概念的层次结构,从而在文本和概念之间挖掘他们的关。这种方法主要应用领域就是文本分类，系统Document Explorer是目前比较先进的文本挖掘系统, 该系统构建于以上所提到的KDT 基础之上。Feldman 的Document Explorer 则用文本集合来创建数据库,然后基于概念图的数据挖掘技术。这套系统可以使用不同的模板来创建数据库以适应各种类型的文本集合,包括Web 文本。 从网上抽取信息来看，Etzioni着眼于将数据挖掘技术应用于互联网上大量的超文本资源。这大概是第一篇将数据挖掘技术应用于万维网上信息资源的文章,并将该技术命名Web 挖掘。近期Soderlan在从互联网上抽取信息的方面作了许多工作,利用自然语言处理技术从不同的html 资源来解释天气预报。应该说万维网上的数据已经成为文本挖掘的重要研究方向[2]。 2.1.2文本挖掘的定义 文本挖掘作为数据挖掘的一个新主题，引起了人们的极大兴趣，同时，它也是一个富于争议的研究方向，目前其定义尚无统一的结论，需要国内外学者开展更多的研究以便进行精确的定义。 一般来说，文本挖掘(Text Mining，TM)和文本数据库中的知识发现(Knowledge Discovery in Textual Database，简称KDT)被认为是具有相同含义的两个词， 最早由Ronen Feldman 等人提出：The Process of extracting interesting Patterns from very large text collections for the purpose of discovering knowledge”。 在维基百科上文本挖掘是这样定义的，文本挖掘有时也被称为文字探勘、文本数据挖掘等，大致相当于文字分析，一般指文本处理过程中产生高质量的信息。高质量的信息通常通过分类和预测来产生，如模式识别。文本挖掘通常涉及输入文本的处理过程（通常进行分析，同时加上一些衍生语言特征以及消除杂音，随后插入到数据库中） ，产生结构化数据，并最终评价和解释输出。'高品质'的文本挖掘通常是指某种组合的相关性，新颖性和趣味性。典型的文本挖掘方法包括文本分类，文本聚类，概念/实体挖掘，生产精确分类，观点分析，文档摘要和实体关系模型（即，学习已命名实体之间的关系） 。 2.1.3文本挖掘的研究现状 国外对于文本挖掘的研究开展较早，50 年代末，H.P.Luhn 在这一领域进行了开创性的研究， 提出了词频统计思想用于自动分类。1960 年，Maron发表了关于自动分类的第一篇论文，随后，众多学者在这一领域进行了卓有成效的研究工作。研究主要有围绕文本的挖掘模型、文本特征抽取与文本中间表示、文本挖掘算法(如关联规则抽取、语义关系挖掘、文本聚类与主题分析、趋势分析)、文本挖掘工具等，其中首次将KDD 中的知识发现模型运用于KDT。 我国学术界正式引入文本挖掘的概念并开展针对中文的文本挖掘研究是从最近几年才开始的。从公开发表的有代表性的研究成果来看，目前我国文本挖掘研究还处在消化吸收国外相关的理论和技术与小规模实验阶段，还存在如下不足和问题: 1)没有形成完整的适合中文信息处理的文本挖掘理论与技术框架。目前的中文文本挖掘研究只是在某些方面和某些狭窄的应用领域展开。在技术手段方面主要是借用国外针对英文语料的挖掘技术，没有针对汉语本身的特点，没有充分利用当前的中文信息处理与分析技术来构建针对中文文本的文本挖掘模型，限制了中文文本挖掘的进一步发展[3]。 2)中文文本的特征提取与表示大多数采用“词袋”法，“词袋”法即提取文本高频词构成特征向量来表达文本特征。这样忽略了词在文本(句子)中担当的语法和语义角色，同样也忽略了词与词之间的顺序，致使大量有用信息丢失。而且用“词袋”法处理真实中文文本数据时，特征向量的维数往往是高维的，这将使挖掘算法效率大大降低。 3)知识挖掘的种类和深度有限，一般只是进行文本的分类、聚类或者信息抽取，而且针对开放语料的实验结果也不是很理想。 2.2 文本挖掘主要内容 存储信息使用最多的是文本,所以文本挖掘被认为比数据挖掘具有更高的商业潜力. 当数据挖掘的对象完全由文本这种数据类型组成时,这个过程就称为文本数据挖掘. 事实上,最近研究表明公司信息有80 %包含在文本文档中。 (1) 文本分类 文本分类指按照预先定义的主题类别,为文档集合中的每个文档确定一个类别. 这样用户不但能够方便地浏览文档,而且可以通过限制搜索范围来使文档的查找更容易、快捷. 目前,用于英文文本分类的分类方法较多,用于中文文本分类的方法较少,主要有朴素贝叶斯分类(Naive Bayes) ,向量空间模型(Vector Space Model) 以及线性最小二乘LLSF(Linear Least Square Fit)。 (2) 文本聚类 聚类与分类的不同之处在于,聚类没有预先定义好的主体类别,它的目标是将文档集合分成若干个簇,要求同一簇内文档内容的相似度尽可能的大,而不同簇之间的相似度尽可能的小。 (3) 文本结构分析 其目的是为了更好地理解文本的主题思想,了解文本所表达的内容以及采用的方式. 最终结果是建立文本的逻辑结构,即文本结构树,根结点是文本主题,依次为层次和段落。 (4) Web 文本数据挖掘 在Web 迅猛发展的同时,不能忽视“信息爆炸”的问题,即信息极大丰富而知识相对匮乏. 据估计,Web已经发展成为拥有3 亿个页面的分布式信息空间,而且这个数字仍以每4～6 个月翻1 倍的速度增加. 在这些大量、异质的Web 信息资源中,蕴含着具有巨大潜在价值的知识. 人们迫切需要能够从Web 上快速、有效的发现资源和知识的工具。 文本挖掘目前面临的问题有挖掘算法的效率和可扩展性、遗漏及噪声数据的处理、私有数据的保护与数据安全性等[4]。 2.3 文本挖掘技术 文本挖掘不但要处理大量的结构化和非结构化的文档数据, 而且还要处理其中复杂的语义关系, 因此, 现有的数据挖掘技术无法直接应用于其上。对于非结构化问题, 一条途径是发展全新的数据挖掘算法直接对非结构化数据进行挖掘, 由于数据非常复杂, 导致这种算法的复杂性很高; 另一条途径就是将非结构化问题结构化, 利用现有的数据挖掘技术进行挖掘, 目前的文本挖掘一般采用该途径进行。对于语义关系, 则需要集成计算语言学和自然语言处理等成果进行分析。我们按照文本挖掘的过程介绍其涉及的主要技术及其主要进展。 2.3.1 数据预处理技术 预处理技术主要包括Stemming( 英文) / 分词( 中文) 、特征表示和特征提取。与数据库中的结构化数据相比, 文本具有有限的结构, 或者根本就没有结构。此外, 文档的内容是人类所使用的自然语言, 计算机很难处理其语义。文本信息源的这些特殊性使得数据预处理技术在文本挖掘中更加重要。 (1) 分词技术 在对文档进行特征提取前, 需要先进行文本信息的预处理, 对英文而言需进行Stemming 处理, 中文的情况则不同, 因为中文词与词之间没有固有的间隔符( 空格) , 需要进行分词处理。目前主要有基于词库的分词算法和无词典的分词技术两种。 基于词库的分词算法包括正向最大匹配、正向最小匹配、逆向匹配及逐词遍历匹配法等。这类算法的特点是易于实现, 设计简单; 但分词的正确性很大程度上取决于所建的词库。因此基于词库的分词技术对于歧义和未登录词的切分具有很大的困难。杨斌等在分析了最大匹配法的特点后, 提出了一种改进的算法。该算法在允许一定的分词错误率的情况下, 能显著提高分词效率, 其速度优于传统的最大匹配法。邹涛等采用了基于词典的正向逐词遍历匹配法, 取得了较好的效果。 基于无词典的分词技术的基本思想是: 基于词频的统计,将原文中任意前后紧邻的两个字作为一个词进行出现频率的统计, 出现的次数越高, 成为一个词的可能性也就越大, 在频率超过某个预先设定的阈值时, 就将其作为一个词进行索引。这种方法能够有效地提取出未登录词。 (2) 特征表示 文本特征指的是关于文本的元数据, 分为描述性特征( 如文本的名称、日期、大小、类型等) 和语义性特征( 如文本的作者、机构、标题、内容等) 。特征表示是指以一定特征项( 如词条或描述) 来代表文档, 在文本挖掘时只需对这些特征项进行处理, 从而实现对非结构化的文本处理。这是一个非结构化向结构化转换的处理步骤。特征表示的构造过程就是挖掘模型的构造过程。特征表示模型有多种, 常用的有布尔逻辑型、向量空间模型( Vector Space Model, VSM) 、概率型以及混合型等。W3C 近来制定的XML , RDF 等规范提供了对Web 文档资源进行描述的语言和框架。 (3) 特征提取 用向量空间模型得到的特征向量的维数往往会达到数十万维, 如此高维的特征对即将进行的分类学习未必全是重要、有益的( 一般只选择2% ～5% 的最佳特征作为分类依据) , 而且高维的特征会大大增加机器的学习时间, 这便是特征提取所要完成的工作。 特征提取算法一般是构造一个评价函数, 对每个特征进行评估, 然后把特征按分值高低排队, 预定数目分数最高的特征被选取。在文本处理中, 常用的评估函数有信息增益( Information Gain) 、期望交叉熵( Expected Cross Entropy) 、互信息( Mutual Information) 、文本证据权( The Weight of Evidence for Text)和词频。 2.3.2 数据挖掘分析技术 文本转换为向量形式并经特征提取以后, 便可以进行挖掘分析了。常用的文本挖掘分析技术有: 文本结构分析、文本摘要、文本分类、文本聚类、文本关联分析、分布分析和趋势预测等。 (1) 文本结构分析 其目的是为了更好地理解文本的主题思想, 了解文本所表达的内容以及采用的方式。最终结果是建立文本的逻辑结构,即文本结构树, 根节点是文本主题, 依次为层次和段落。 (2) 文本摘要 文本摘要是指从文档中抽取关键信息, 用简洁的形式对文档内容进行解释和概括。这样, 用户不需要浏览全文就可以了解文档或文档集合的总体内容。 任何一篇文章总有一些主题句, 大部分位于整篇文章的开头或末尾部分, 而且往往是在段首或段尾, 因此文本摘要自动生成算法主要考察文本的开头、末尾, 而且在构造句子的权值函数时, 相应的给标题、子标题、段首和段尾的句子较大的权值, 按权值大小选择句子组成相应的摘要。 (3) 文本分类 文本分类的目的是让机器学会一个分类函数或分类模型,该模型能把文本映射到己存在的多个类别中的某一类, 使检索或查询的速度更快, 准确率更高。训练方法和分类算法是分类系统的核心部分。用于文本分类的分类方法较多, 主要有朴素贝叶斯分类( Native Bayes) 、向量空间模型、决策树、支持向量机、后向传播分类、遗传算法、基于案例的推理、K -最临近、基于中心点的分类方法、粗糙集、模糊集以及线性最小二乘( Linear Least Square Fit, LLSF) 等。 厉宇航等指出传统特征提取的方法是基于词形的, 并不考察词语的意义, 忽略了同一意义下词形的多样性、不确定性以及词义间的关系, 尤其是上下位关系。该文的方法在向量空间模型( VSM) 的基础上, 以“概念”为基础, 同时考虑词义的上位关系, 使得训练过程中可以从词语中提炼出更加概括性的信息, 从而达到提高分类精度的目的。 (4) 文本聚类 文本分类是将文档归入到己经存在的类中, 文本聚类的目标和文本分类是一样的, 只是实现的方法不同。文本聚类是无教师的机器学习, 聚类没有预先定义好的主题类别, 它的目标是将文档集合分成若干个簇, 要求同一簇内文档内容的相似度尽可能大, 而不同簇间的相似度尽可能小。Hearst 等人的研究已经证明了“聚类假设”, 即与用户查询相关的文档通常会聚类得比较靠近, 而远离与用户查询不相关的文档。 (5)    关联分析 关联分析是指从文档集合中找出不同词语之间的关系。Feldman 和Hirsh研究了文本数据库中关联规则的挖掘 ,提出了一种从大量文档中发现一对词语出现模式的算法, 并用来在Web 上寻找作者和书名的出现模式, 从而发现了数千本在Amazon网站上找不到的新书籍; Wang Ke等以Web 上的电影介绍作为测试文档, 通过使用OEM模型从这些半结构化的页面中抽取词语项, 进而得到一些关于电影名称、导演、演员、编剧的出现模式。 (6) 分布分析与趋势预测 分布分析与趋势预测是指通过对文档的分析, 得到特定数据在某个历史时刻的情况或将来的取值趋势。Feldman R等使用多种分布模型对路透社的两万多篇新闻进行了挖掘, 得到主题、国家、组织、人、股票交易之间的相对分布, 揭示了一些有趣的趋势。Wuthrich B等通过分析Web 上出版的权威性经济文章对每天的股票市场指数进行预测, 取得了良好的效果。 (7) 可视化技术 数据可视化( Data Visualization) 技术指的是运用计算机图形学和图像处理技术, 将数据转换为图形或图像在屏幕上显示出来, 并进行交互处理的理论、方法和技术。它涉及到计算机图形学、图像处理、计算机辅助设计、计算机视觉及人机交互技术等多个领域。国内外学者已经对信息可视化技术进行了大量的研究, 运用最小张力计算、多维标度法、语义分析、内容图谱分析、引文网络分析及神经网络技术, 进行了信息和数据的可视化表达[4]。 2.4 文本挖掘热点难点问题 显然，目标不同，文本挖掘的过程也不尽相同。但不论何种目标，都不可忽视如下几个方面的研究: (1). 文本建模 向量空间模型，也称为“词袋”法，是目前文本处理的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 模式。简单讲，就是提取文本高频词构成特征向量来表达文本特征的方法，该方法有效描述了词一文档间的频率关系。面对复杂繁琐的自然语言文本，向量空间模型是目前最为简便有效的文本表示方法。 但向量空间模型建模方法最大的问题就是忽略了词在文本中承担的语法和语义上的作用，同时忽略了词与词之间的顺序关系，丢失了大量有用信息，从而减弱了高频词向量表达文本特征的可信度。 同时，向量空间模型在处理真实文本数据时形成的特征向量的高维性也严重影响了后续文本挖掘的效率和结果的准确性。 此外，建模前的文本预处理工作作为整个文本挖掘过程的基础尤为重要。而不同的语言的处理又常常不同。如何解决多语言混合如中英文混合情况下的文本处理和建模工作日益重要。同时，不同的语言有不同的切词处理方式。并且存在着大量多词同义、一词多义的现象。 (2). 特征降维 文本模型的高维特性制约了文本挖掘的效果。不论何种语种，由于语言本身的非结构特性以及建模后的高维特性，使得后续挖掘过程中都面临严重的效率问题。因此有效的降维是进行后续文本挖掘的重要一环。 目前的文本降维方法主要采用基于奇异值分解的潜在语义分析技术。该技术通过分析特征词之间的语义相关性来减少特征向量的维数，通过将词一文档的高维表示投影在低维潜在语义空间中，降低空间的维数，进而得到词一文档的不再稀疏的低维表示。并且，由词袋模型在进行奇异值分解后得到的子空间不再是仅仅反映出词汇出现的频率和分布关系，而进一步揭示了词汇或文档之间的语义联系。 然而，基于奇异值分解的潜在语义分析技术有两大突出的问题:一是得到的分解矩阵具有正交的特性，导致无法更好的描述文本数据空间的特点，从而使得对降维后的子空间进行进一步的文本分析时结果并不准确。这一问题在面对大规模文本数据时显得更加突出。另一方面，由于潜在语义分析得到的分解矩阵存在负数，而难以直观地做出与实际情况一致的语义上的解释。 非负矩阵分解方法有效解决了上述问题。借鉴人类思维中“局部构成整体”的概念，非负矩阵分解将由词袋法构造的向量空间模型分解成两个非负、非正交的子矩阵，从而可以更有效的降维及进行进一步的聚类、分类分析。 (3). 挖掘算法的选择 模型创建成功并且进行了有效的降维处理之后，就可以进行具体的挖掘操作了。从狭义的角度理解，也可以说这部分才是真正的挖掘。而广义上来说，整个过程才一构成文本挖掘的全部过程。 文本挖掘算法并不是一个新的领域，通常就是数据挖掘方法在文本数据上的应用。因此多数挖掘方法来自机器学习、统计学习、自然语言处理、信息抽取、信息检索以及知识管理等领域，最终目标就是对建模后的文本数据进行分析和处理，找到其中潜在的有用信息。 根据不同的应用目标，挖掘出的知识种类不尽不同，由此可以对文本挖掘的技术和算法进行如下的分类:如根据发现关联规则、聚类、趋势、差异等知识的不同，分别对应不同领域的算法选择。 任何算法技术的研究和设计都离不开始实验的仿真和具体实例的验证。文本数据挖掘过程亦是如此。由于文本数据的复杂多样性，导致文本数据的挖掘过程相对其他结构化数据要复杂繁琐的多，对数据的敏感性更为严重，在很多情况下，面临对开放语料的实验结果不理想的问题。因此选择更好的评价方法，克服现有语料手工分类不准确带来的误差，以更好地对算法作出评价，同样重要。本文也将在后续仿真的具体过程中对所研究的方法进行有意义的评价。 (4). 模式的理解及可视化表达 多数文本挖掘应用实例的目标同数据挖掘类似，通常是要辅助用户的决策和判断，因此从用户的角度来看，文本挖掘所发现结果的可理解至关重要。而对于各种方法挖掘出的模式、规则等结果，提高其可理解性的解决方法通常有两种:一种是以生成人类易于理解的自然语言的方式进行呈现，如对文档进行摘要的方法;另一种方式则是以图形界面方式展示结果，通过提供相对少量的规则，利用计算机图形学、图像处理等可视化技术将结果更加直观的呈现给用户。 近年来，可视化技术作为展示结果的关键一环逐渐成为文本挖掘过程中日益重要的一个分支。大量的研究结合语义分析、内容图谱分析、最小张力计算、神经网络技术、多维标度法等数据分析和处理方法进行了结果的可视化表达[5]。 第三章 文本分类算法 3.1 文本分类概述 3.1.1 文本分类的研究现状 文本分类的理论研究可以追溯到20世纪60年代初，其发展过程大致可以划分为三个阶段: 第一阶段是20世纪60年代前。在这一时期，主要是分类理论的研究，并将文本分类应用于信息检索。在这一时期，提出了很多经典文本分类的数学模型。如Maron和Kuhns提出概率标引(Probabilistic Indexing)模型，并将其应用于信息检索中;Salton提出利用向量空间模型(Vector Space Model, VSM)对文本进行描述等等。 第二阶段是20世纪80年代。这一阶段主要是采用传统的知识工程技术，根据专家提供的知识形成规则，手工建立分类器。这一时期，信息检索技术逐渐成熟应用，为文本分类提供了许多技术支持，最著名的信息检索系统是Salton的SMART系统。Rocchio在1971年也提出了在用户查询中不断通过用户的反馈来修正类权重向量，来构成简单的线性分类器。Van Rijsbergen提出了信息检索的评估标准如准确率、查全率等。 第三阶段是20世纪90年代以后。在这一时期，文本分类的主要特点是采用统计机器学习方法，自动建立分类器，学习和分类过程来自于机器对训练文本的自主学习，从而不需要领域专家的支持，不需要人工干预，而分类效率和准确率得以提高。如1992年，Lewis在他的博士论文中提出T标准数据集Reuters22173，并在此数据集上进行了实验测试;Yang Yiming对各种特征选择算法进行了分析比较，讨论了文档频率(Document Frequency, DF)、信息增益(Information Gain, IG),互信息(Multi-information, MI)和CHI等方法，结合KNN分类器，得出IG和CHI方法分类效果相对较好的结论，对后来的研究起到了重要的参考作用。新加坡的Hwee Tou NG等人研究了用Perceptron Learning的方法进行文本分类，使用了一种树状的分类结构，其准确率达到73. 3%。 文本特征描述一般采用基于内容的向量空间模型表示。它是从文本中抽取信息来表示文本内容，并从大规模语料库中发现能表示文本类别的词汇，利用统计原理和文本在一些特征项集合上的分布规律，对文本进行分类。对文档分类来说，关键问题之一就是降维，降维技术是利用某种评价函数来保留这些具有分类能力和描述能力的特征词，过滤掉弱信息特征词，并提取出最少的、最能表达文章主题的词作为特征词汇。 文本分类是按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。这样用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查找更容易、快捷。文本分类可以在较大程度上解决目前文本以及网络上信息杂乱的现象，方便用户准确地定位所需的信息和分流信息。因此，文本自动分类己成为一项具有较大实用价值的关键技术，是组织和管理数据的有力手段，可被用于垃圾邮件过滤、邮件自动分类、网页搜索、网页分类、信息组织、信息推送、数字图书馆的数字化管理等领域中。 目前，分类器的构造方法有多种，主要有机器学习方法、基于规则的方法等。基于机器学习的英文自动分类己经取得了很好的成绩，如回归模型、K近邻、贝叶斯、决策树、推导规则、神经网络、支撑向量机等。 国外对文档分类技术的应用研究也己经开展了多年，其中较为成功的系统有麻省理工学院为白宫开发的邮件分类系统、卡内基集团为路透社开发的Construe系统，Salton的SMART系统，Lewis采用了一个线性分类器，建立了OHSUMED,Reuters等标准的分类熟语料和统一的评价方法等。 国内在中文文本分类领域也进行了大量的研究，如中科院计算所的李晓黎、史忠植等人应用概念推理网进行文本分类，召回率达到94. 296，准确率达到99. 4960中国科技大学的范众等人在KNN, Bayes和文档相似性研究的基础上提出了一个超文本协调分类器，正确率接近80%，它的一个特色是适当考虑了HTML文本中的结构化信息，并且将文本分类器和超文本结构信息分类器结合起来，从而达到更好的效果。但由于语料和评价方法各不相同，很难对它们做出严格的比较。在国内文本分类和过滤领域里，复旦大学黄营著等人设计的文本过滤系统很值得一提，它主要针对英文，能够通过特征抽取和伪反馈建立初始的过滤模板，并设置初始闲值，在过滤阶段，则根据用户的反馈信息自适应地调整模板和闭值，并且该系统在2000年举行的第9次文本检索会议(Text Retrieval Conference, TREC)的评测中取得了很好的效果，自适应过滤和批过滤的平均准确率分别为26. 596和31. 796，在来自多个国家的15个系统中名列前茅，获得自适应过滤第3名和批过滤第1名的好成绩。 关于文本分类算法KNN，目前，大多学者主要从三个方面进行改进，分别是减少训练样本的存储量、加快K个最近邻的搜索速度和调整K值的选择。      当训练样本集过大时，为了减小计算开销，可以对训练文本进行编辑处理，即从原始训练样本集中选择最优的参考子集进行K个最近邻寻找，从而提高计算效率。这种途径主要的方法是Hart的Condensing算法、Wi1Son的Editing算法和Devijver的Multi-Edit算法，另外Kuncheva使用遗传算法在这方面也进行了一些研究。 有的学者是采用加快KNN搜索速度的算法，使之在尽量短的时间内找到K个最近邻文本。在进行搜索时不是盲目迭代，而是采用一定的方法加快搜索速度或减小搜索范围，例如构造交叉索引表，利用匹配成功与否的历史来修改样本库的结构，使用样本和概念来构造层次或网络来组织训练样本。此类方法主要可分为三类:空间/数据分区方法、以扫描作为基础的方法和线性化方法。如香港中文大学的Wai Lam等人将KNN方法和线性分类器结合，取得了较好效果。 K值的选择主要有两种方法:(1)通过大量独立的测试数据、多个模型来验证最佳K值的选择;(2) K值可以事先确定，也可以动态变化，例如采用固定的距离指标，只对小于该指标的样本进行分析。本文针对KNN算法的样本数量不平衡的情况，提出对KNN算法进行优化，使K值能够自适应与文本分类规模[6]。 3.1.2 文本分类模型 大多数文本分类采用词袋( bags-of-words)表示法，即记录每个单词在文档中出现的次数，或仅记录出现与否。加入语义信息或语言信息对分类器的精度都提高不大13x1。分类算法一般基于“词袋”模型，即文档被看成是由相互无关的单词构成的词的集合，不考虑单词之间的上下文关系，单词出现的顺序，位置以及文章的长度等。统计出每个单词在每篇文档中出现的频率是进行算法建模的基础，统计所有单词在所有文档中出现的频率得到单词对于文档的词频统计矩阵。词频统计矩阵是文本分类算法建立分类器模型的数据基础，训练集通过文法分析统计出词频矩阵，矩阵中的某一元素就是某个单词在某篇训练文档中出现的频率。下面介绍建立文本分类器模型的过程。 第一步，对文档进行预处理过程。按照文本文档数据集(一般分目录放置文本文档)路径对所有训练文档扫描，分析出不同的单词。对待英文，文法分析的步骤为:按空格分出一各个单词，去掉其中禁用词，如the，that等，如果是第一次遇到的新词，就存入单词列表，也称词库，否则这个单词的统计次数加1，其中包括词干提取，如将played, playing变为play;还包括保存文档的文件名，类别等工作。此外，把算法运用到中文分类时，关键问题就是中英文的单词在句子中的出现方式不一样，对待中文要增加切词的工作。因为中文不象英文有空格将词与词区分开，中文文本中词与词之间没有明确的分隔标记，而是连续的汉字串。汉语中存在大量多义词，语义模糊，歧义性大，识别词的边界很难。常用的中文分词算法有:基于词表的分词，基于统计的分词，基于规则和基于统计相结合的分词。我们将采用基于词表匹配的分词方法，这种切分方法，需要语言资源(仅需一个词表，不需要任何词法、句法、语义知识)最少，程序实现简单。(后面的实验中，我们将中文的词法分析器代替原有的英文词法分析器，将词法分析模块插入到Rainbow系统中，得到需要的词频矩阵，测试不同的算法在分类中的性能。) 第二步，建立词频矩阵。预处理之后，将文章变为一个词集，单词也称为特征项或属性。把文档看成是一个词向量(word vector )，它的维数是所有不同的单词个数，词集中可以有数万个不同的单词。对于特定的文章，它包含的单词数一般从几百到几千，一篇文档对应一个词向量，而一个词也在不同的文档中出现，所有出现这个单词的文档构成了文档向量，所以整个文档与词集形成一个稀疏矩阵，矩阵中点的值就是单词在文档中出现的频率。在系统中，矩阵以二维链表的形式保存。 第三步，构造文本分类器。词频统计矩阵是算法建模的基础。在词频统计矩阵的基础上根据特定的算法构造分类器。主要任务是根据不同分类算法，计算词向量的权值。 词向量的权值按不同的算法有不同的计算方法和意义。在第一类算法中，权值按TFIDF公式计算，权值越大，表示这个词对文档越重要。TF(Term frequency)是词在文档中出现的次数，如果一个词在一篇文档中经常出现，那么说明这个词对文档具有代表性。如“计算机”这个词在计算机类的文档中出现的频率显然要高于政治类的文档。但如果一个单词在一篇文档中出现，但同时它也出现在很多文档中，则降低了这个单词的重要性，如“科学”在社会科学类与自然科学类的文档中都出现，对区别两类文档的帮助就不大，这就是反比文档频率IDF ( inverse document frequency)的作用。把两项相乘得到的权值，就代表了单词对文档的整体重要程度。 对于另一类概率算法，如纯粹贝叶斯算法，则通过词频统计矩阵计算每个词属于每个类的概率，权值越大，表示单词在这个类中出现的概率大，得到了词到类别的概率分布。贝叶斯算法认为新的文档满足建立的概率模型的单词的类概率分布，把文档中的单词在每个类上的概率按类相乘，由此计算出文档属于每个类别的概率。 最后，用分类器测试未分类文档。构造好分类器后，当对一篇测试文档分类时，首先利用建立的分类器模型给测试文档的词向量赋于相应的权值，然后由算法根据分类器和文档向量计算此文档的类别。 上面所提的两类算法代表了两种基本文本分类模型。一类是由TFIDF公式定义单词的权值，由cosine相似度距离公式计算样本点之间的相似度。一类是概率权值，计算单词在类别上的概率分布，然后求得文档属于每个类别的概率[7]。 3.1.3 文本分类面临的挑战 现在既是文本分类最为蓬勃发展的时代，又是其面临巨大挑战的时代: 1)文本分类处理内容日趋复杂化和多元化。随着时代的发展，文本分类和聚类技术发生了天翻地覆的变化。其“内涵”仍然涵盖有效地组织和管理文本信息，并快速、准确、全面地从中找到、分流、定位和形成用户所需要的信息等核心内容。但是其“外延”却极大的丰富处理对象己经由简单的纯文本对象，发展到包括web网页、邮件/讨论组、短信、即时通信、BBS论坛等等，不一而足。这使得从各式各样文本形式中抽取处理内容本身也成为了一门学问，即信息抽取（CIE: Information Extraction)，受到人们的广泛关注。而且文本分类和聚类处理的对象也不再局限于文本领域，还逐渐和语音分类及检索，图像分类及检索，机器视觉/视频分类及检索等技术结合在一起，如通过语一文转换以及建立图像舰频的描述(profile)将语音、图像/视频分类及检索问题转换为文本分类及索问题。种种发展，均使得文本分类和聚类技术发生了质的变化，提升到前所未有的水平。同时也使得研究中遇到的一些老问题还没有得到解决时，新的问题又不断涌现，层出不穷。 2)海量信息处理。信息大爆炸，一方面使得人们很容易获取巨量的信息，使文本信息以前所未有的速度传播，发展。然而，事物总是有两面性的，另外一方面，这也使得如何处理这些海量数据成为了摆在人们面前的难题。这里的处理包含两个方面的含义: 第一，如何进行海量数据实时处理的问题。一般来说，现有的算法只是在中小数据集上显示出优势，大都是因为速度瓶颈无法成功应用于海量数据挖掘。而处理海量数据挖掘的算法一般来说精度都不高。如何达到速度和精度的折衷，需要进行深入的研究。 第二，如何进行无标签样本学习的问题。信息化使得我们能够轻松获得大量的信息(无标注背景信息)，但是这些信息只是原始语料，一般来说，只有经过整理标注才能投入实际应用。而手工标注大量高质量的训练样本的工作是极端枯燥和代价巨大的。因此如何整合有标签数据和无标签数据的学习，成为了一个现实的问题。 3)人性化/个性化处理。我们无论是对文本进行分类和聚类，还是进行其它深层次的处理，其最终目的始终都要面对人的需求，因此人性化/个性化处理是大势所趋，不可避免。这里的人性化/个性化处理也包含两个方面的含义:  第一，如何开发增量式自适应更新的算法，跟踪捕获用户的需求。因为算法的开发一般面对的是通用的情况，即针对最一般的情况进行处理。而实际中碰到的总是具体的问题，如何使通用框架适合每个用户的需求，我们必须开发增量式自适应更新的算法，通过不断学习，跟踪捕获用户的需求。 第二，如何从更高的层次，即从“理解”的层次处理用户需求。具有理解并自动处理文本信息能力的机器，才算是智能文本信息处理机器，也才可以替代人类劳动者工作。这样，传统上人类劳动者依靠简单的“控制指令”来同机器合作的局面就可以大为改观，从而可以做到人和机器之间的合理分工和默契合作。这对于整个社会生产力和促进人类劳动者从自然力的束缚下获得越来越多的解放具有伟大的意义。 4)对更高处理精度的追求。对信息处理更高、更快、更强的追逐是人类永恒的追求。如何开发分类精度更高，更鲁棒，速度更快的文本和聚类技术，也是我们作为文本信息处理领域研究者的永恒追求。 3.1.4 文本分类亟需解决的问题 现代文本分类和聚类领域面临巨大的挑战，而且随着研究的深入，其中的一些深层次问题也逐渐暴露出来，其中的一些己成为本学科进一步发展的阻碍。但是，从另一个方面来看，它们也揭示了文本分类和聚类领域下一步应该着重研究的内容。 本文认为，目前函需解决以下几个问题: 1)设计出易于使用的工程化文本分类方法。文本分类工作缺少统一的理论框架，经验性成分相当高。虽然针对具体问题，可以迅速给出一般处理方法，但是如果要使得系统获得良好的性能，只能具体问题具体分析，通过大量费力耗时的实验摸索，确定出适合的处理模型、算法以及参数设置，其应用效果极大依赖于使用者的经验。即使采用同样的方法解决同样的问题，由于操作者不同，其结果很可能大相径庭。在实际应用中，操作者往往是缺乏文本处理经验的普通工程技术人员，如果没有易于使用的工程化文本分类处理方法，文本分类技术的应用效果将很难得到保证。 2)开发适用于海量信息处理的文本分类算法。这包含两个方面的问题: 第一，设计性能和效率兼备的海量数据的实时处理算法; 第二，充分利用无标签样本进行学习。通过整合有标签数据和无标签数据的学习，提升文本分类技术的应用性能。 3)提高文本分类技术的处理精度。一般来说，精度问题往往是文本分类处理技术从理论走向实际的最大障碍。因此开发分类精度更高，更鲁棒，速度更快的文本分类技术成为文本信息处理领域重要的研究目标。 4)将传统的文本聚类提升到理解的层次。文本聚类是“文本信息处理”领域的一个重要分支。文本信息处理的根本目标是使机器能够“一定程度上理解并自动处理”文本信息。而文本聚类的目的也不外乎是使机器能够在“一定程度上理解并自动组织”文本信息。换言之，处理只是手段，理解并自动组织才是目的。具有理解并自动处理文本信息能力的机器，才算是智能文本信息处理机器，也才可以替代人类劳动者工作。但是，如何使得使机器能够在“一定程度上理解并自动组织”文本信息。国内外关于这方面的研究，长期专注于“语法”层次的研究。如何从“语法”上升至“语义，，乃至“语用”的层次，最终达到对内容的理解，这仍然是研究者努力工作的方向[8]。 3.2 常用文本分类算法 文本自动分类是指将一篇文本自动指定到一个或几个预定义的文本类别中。文本分类在文本检索、信息获取、信息过滤、数据组织、信息管理及互联网上 的搜索都有十分广泛的应用, 有效地提高了信息服务的质量。研究表明, 公司信息有80%包含在文本文档中。所以, 文本自动分类及其相关技术的研究正日益 成为一项研究热点。目前较为著名的文本分类算法包括支持向量机(Support Vector Machine,SVM), K 近邻法(K- Nearest Neighbour,KNN), 朴素贝叶斯法(NaiveBayes,NB), 神经网络法(Neural Network,NNet), 线性最小二乘法( Linear Least Squares Fit,LLSF) 等。其中, 多数方法采用向量空间模型(Vector Space Model, VSM)表示文本, 即将文本表示成向量, 作为向量空间的一个点, 然后通过计算向量间的距离决定文本所属类别。VSM在表示方法上有巨大的优势, 在文本分类中被广泛使用。 3.2.1 文本分类中的特征选择方法 3.2.1.1 文本的特征表示 特征表示是指以一定特征项（如词条或描述）来代表文档[10]。在文本挖掘时只需要对这些特征项进行处理，即可实现对非结构化的文本的处理。这是一个非结构化向结构化转换的处理步骤。特征表示方法有很多种，常用的有布尔逻辑法、概率法、向量空间等。现有的绝大部分的文本分类器都是使用向量空间模型中的“词袋法”来表示文本。这种方法有一个关键的假设，就是文章中出现的词条的次序是无关紧要的，不考虑词条的位置信息以及文本结构，把文本看成是一系列无序词的集合。文本的特征就可以采用文本中的词条Token作为特征项。 表示文档内容的特征项，可以看成是一个n维的坐标系，权值 为对应的坐标值。所以每篇文档d可以映射成为特征空间的一个特征向量V(d)=( )。 在所有的权值函数中，最常用的是前面两种，它们在特征空间中一般可以获得比较高的分类精度。这两个公式都基于以下的指导思想：在一个文本中出现次数很多的单词，在另一个同类文本中出现的次数也会很多，反之亦然。而且认为一个单词出现的额外文本频数越小，它区分不同类别文本的能力就越大。公式的表达式也可以看出词条重要性正比于词条的文档内频数，反比于文本集内出现该词条的文档频数。 3.2.1.2 文档预处理 进行文本特征选择以前可以先进行一些初始化的筛选，一般通用的做法有： (1)停用词表(stop-list) 将一些在文本中出现频率高但是含义虚泛的词放入停用词表。这些词在不同的语言环境有不同的表示。例如在英语中的a,an,the,this,for,at,on，中文中的“的，得，地，这，尽管，但是”等，保证出现在停用词表中的词不能选作文档特征。 (2)稀有词处理 有些词条在整个文档集中出现的频率都很低，它们也不适合作为文本的特征项。通过对文档集进行词条频率统计并设计一个词频阈值，只要是词条频度低于这个词频阈值的词就被删除。主要运用zip法则来删除低频词。 (3)单词归并 为了提高分类效果，采取单词归并和同义词归并的策略，把表达形式不同而含义相同的或是含义相似的词作为同一个词条处理。如英文中的football 和soccer，中文的“电脑”和“计算机”等。 (4)同根词处理 在英文中，还可以进行strip header 和Stemming 的操作来对文本进行初始化。例如：talker,talking,talked它们同属于一个词根talk。 3.2.1.3 文档特征选择 文本数据的半结构化甚至于无结构化的特点，使得用词袋法表示待测文档集时，特征向量会达到几万维甚至于几十万维。即使经过上述初始化筛选处理（使用停用词表、稀有词处理、单词归并以及同根词处理），还会有很多高维数的特征向量留下。高维的特征对分类机器学习未必全是至关重要的，有益的。高维的特性可能会大大增加机器学习的时间而仅产生与小得多的特征子集相关的学习分类结果。因此，在进行文本分类中，特征选择显得至关重要。 特征选择的主要方法是利用有关数学工具降低模式维数，寻找最有效的特征构成较低维数的模式向量。统计学、模式识别和机器学习中都有许多进行特征选择的方法，一般分有filter方法和wrapper 方法两种，两种方法的过程如图，实际上它们并没有本质的差别，它们的不同仅仅在于filter方法采用一些度量指标来评价特征子集的优劣，而wrapper方法直接用学习算法的准确率作为评判的指标。 图3.2 filter方法和wrapper 方法示意图 特征选择主要用于排除确定的特征空间中那些被认为无关的或是关联性不大的特性。于是经常会使用特征独立性假设以简化特征选择，以达到计算时间和计算质量的折衷。因此，目前在对文本的特征空间所采取的特征选择算法一般是构造一个评价函数，对特征集中的每个特征进行独立的评估。这样每个特征都获得一个评估分，然后对所有的特征按照其评估分的大小进行排序，选取预定数目的最佳特征作为结果的特征子集。所以，选取多少个最佳特性以及采用什么评价函数，都需要针对某一个具体的问题通过试验来决定。 在文本分类的特征选择中的评估函数有文档频数(document frequency)，信息增益(information gain)，期望交叉熵(expected cross entropy)，互信息(mutual information)，文本证据权(the weight of evidence for text)，几率比(odds ratio)，单词权(term strength)，其效果和原因分析如下： (1) 文档频数(document frequency) DFTxt(W)= 单词出现的文档数/训练集的文档总数 它是最简单的评估函数，其值为训练集合中此单词发生的文本数在总的文本数的概率。DF评估函数的理论假设是稀有单词要么不含有用信息，要么太少而不足以对分类产生影响，要么是噪音，所以可以删去。虽然它在计算量上比其它的评估函数小得多，但是在实际运用中它的效果却是出奇地好。DFTxt也有缺点，因为稀有单词可能在某一类文本中并不稀有，而且包含着重要的判断信息。在实际运用中一般并不直接使用DFTxt，常把它作为评判其它评估函数的标准。 (2) 信息增益(information gain) 其中P(Ci|W)表示文本中出现单词W时，文档属于Ci的概率，同样P(Ci| )表示文中不出现单词W时文本属于Ci的概率，P(Ci)表示类别出现的概率，P(W)表示W在整个文本训练集中出现的概率。 信息增益是一种在机器学习领域应用较为广泛的特征选择方法。它从信息论角度出发，用各特征取值情况来划分学习样本空间，根据所获信息增益的多寡，来选择相应的特征。 (3) 期望交叉熵(expected cross entropy) 期望交叉熵没有考虑单词未出现的情况。如果词条和类别强相关，P(Ci|W)就大，若P(Ci)又很小的话，则说明该词条对分类的影响大。此时相应的函数值就大，就有可能被选中作为特征值。交叉熵反映了文本类别的概率分布和出现了某种特定词的条件下文本类别的概率分布之间的距离。词条的交叉熵越大，对文本类别分布的影响也就越大。 (4) 互信息(mutual information) 词条和类别的互信息体现了词条与类别的相关程度，是一种广泛用于建立词关联统计模型的标准。在某个类别Ci中出现的概率高，而在其它类别中出现的概率低的W将获得较高的互信息，也就有可能被选取为类别的Ci的特征。 (5) 文本证据权(the weight of evidence for text) 其中P(Ci|W) 和P(Ci)的意义同上。文本证据权比较了P(Ci)与P(Ci|W)之间的差别。其中P(Ci)为类出现的概率，P(Ci|W)为给定特征下类出现的条件概率。如果W和类别强相关，即P(Ci|W)大，并且相应类别出现的概率小，说明W对分类的影响大，计算出来的函数值就大，可以选取作为特征项；反之，就不选取作为特征项。文本证据权的精度是相当高的。 (6) 单词权(term strength) 它和其它的评估函数完全不同，与类别信息无关。TS 方法基于W在邻近相关文档中出现的概率来测试W的强度。利用文本向量间的余弦夹角找出相似度大于某一有限值的文本对，x和y 即是找出的任意不同但相关的文本对。W的权值即为上式的TS(W)。 信息增益方法的不足之处在于它考虑了单词未发生的情况特别是在类分布和特征值分布高度不平衡的情况下，绝大多数类都是负类，绝大多数特征值都是“不出现”的，即P( )>P(W) 此时得到信息增益大的特征，主要因为信息增益公式中后一部分（代表单词不出现情况）计算结果大，而非前一部分（代表单词出现情况）计算结果大，信息增益的效果就会大大降低了。恰恰相反的是期望交叉熵没有考虑单词未出现的情况，在大多数的实验结果中，不管在哪种数据集中，期望交叉熵的特征选择都要优于信息增益。互信息(MI)与期望交叉熵本质的不同在于它没有考虑单词发生的频度,这是它一个致命的弱点，会导致互信息评估函数不选择高频的有用单词而有可能选择稀有词作为文本的最佳特征。然而在二元分类器中，几率比对于其它评估函数来说有其独特的优势。 3.3.2 支持向量机文本分类算法 3.3.2.1 文档特征表示 文本的特征表示是指用文本的特征信息集合来代表原来的文本[11]。文本的特征信息是关于文本的元数据,可以分为外部特征和内容特征两种类型。其中外部特征包括文本的名称、日期、大小、类型、文本的作者、标题、机构等信息,文本的内容特征包括主题、分类、摘要等特征。目前,在信息处理领域, 文本的表示方法主要采用向量空间模型(VSM) 。在该模型中,文档被看作是由一组正交词条向量所组成的向量空间,每个文档表示为其中的一个规范化特征向量: V ( d) = ( t1 ,ω1 , t2 ,ω2 , ?, tn ,ωn ) 式中: ti —特征项,ωi —ti 在d 中的权重。通常选择词作为特征项,用词频来表示特征项对应的向量分量。词频分为绝对词频和相对词频两种:绝对词频是指词在文本中出现的频率;相对词频是规范化的词频,即要求所有向量分量的平方和为1 。相对词频的计算方法常用的有布尔函数、平方根函数、对数函数、TFIDF 函数等。