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

摘要

随着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 目录 ................................................................................................................................ 1

第一章 数据挖掘概述 .................................................................................................. 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)一书中定义了数据仓库的概念，随后又给出了更为精确的定义：数据仓库是在企业管理和决策中面向主题的、集成的、时变的以及非易失的数据集合。与其他数据库应用不同的是，数据仓库更像一种过程—对分布在企业内部各处的业务数据的整合、加工和分析的过程。传统的数据库管理系统(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). 文本建模

向量空间模型，也称为“词袋”法，是目前文本处理的标准模式。简单讲，就是提取文本高频词构成特征向量来表达文本特征的方法，该方法有效描述了词一文档间的频率关系。面对复杂繁琐的自然语言文本，向量空间模型是目前最为简便有效的文本表示方法。

但向量空间模型建模方法最大的问题就是忽略了词在文本中承担的语法和语义上的作用，同时忽略了词与词之间的顺序关系，丢失了大量有用信息，从而减弱了高频词向量表达文本特征的可信度。 同时，向量空间模型在处理真实文本数据时形成的特征向量的高维性也严重影响了后续文本挖掘的效率和结果的准确性。

此外，建模前的文本预处理工作作为整个文本挖掘过程的基础尤为重要。而不同的语言的处理又常常不同。如何解决多语言混合如中英文混合情况下的文本处理和建模工作日益重要。同时，不同的语言有不同的切词处理方式。并且存在着大量多词同义、一词多义的现象。 (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 函数等。

3.3.2.2 文本的特征提取

采用一定的文本表示模型对文本进行建模后,还要根据不同的目标采用特征选取的方法来降低维度。文本的特征提取一般是构造一个评价函数,对特征集中的每个特征进行的评估,提取的方法有多种,可以使用不同的评价函数,如:词频DF ( document f requency threshold) 、信息增益IG( information gain) 、互信息MI ( mutual information) 、期望交叉熵(expected cross ent ropy) 、文本证据权(the weight of evidence for text) 等,其中词频和互信息应用较广。词频就是文档集合中出现某个特征项的文本数目,词频是最简单的特征降维方法,易用于线性计算的集 合,但是不适用于回归词语的排除。

通过这些公式,可以计算出文本中出现的所有词的权重,并将之排序,根据需要可以有两种选择方式:

(1) 选择权值最大的某一固定数n 个关键词; (2) 选择权值大于某一阈值的关键词。

根据实验对比这两种方法各有优缺点,第一种方式将能保证关键词的覆盖度,但有时可能不能选择最合适数量的关键词,因为不同文本内容所涉及的主题概念不同,主题的分散度亦不同;第二种方式选择的主题词和内容间的关系相对紧密,但对于主题比较分散的文本,选择的主题词可能过少可能过多。 3.3.2.3 文档的相似度

通过特征选取可以获得文本对应的特征词向量,也可以获得文本对应的特征

词相对词频向量。一般认为,相似的文本具有相似的特征词或相对词频,因此可以基于特征词向量或特征词相对词频向量计算一组文本的相似度。计算相似度的方法有很多:向量测距法、简单乘积法、相对乘积法、最大最小系数法、算术平均最小法、余弦系数法。其中,余弦系数法最为常用:向量空间模型表示的文本D1 和D2 的相似度sim ( D1 , D2 ) 可使用余弦系数法度量：

3.3.2.4 支持向量机算法

支持向量机(SVM) 是建立在统计学习理论的VC 维理论和结构风险最小化原理基础上的,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以获得最好的推广能力。SVM 方法不同于常规的统计和神经网络方法,它不是通过减少特征的个数来控制模型的复杂性。SVM 提供了一个与问题维数无关的刻画函数复杂性的方法,它引入高维特征空间,将输入空间的非线性决策边界转 化为高维特征空间的线性决策边界,利用线性函数的对偶核,解决了数值优化的二次规划求解问题。目前常用的核函数主要有三类:多项式核函数、径向基形式核函数、S核函数。根据不同的分类问题, 可以选用不同的核函数。支持向量机最初是为了解决两类分类问题的,其基本思路如下。

设线性可分样本集为( xi , yi ) , i = 1 , ⋯, n , x ∈Rd , y ∈{ + 1 , - 1} 是类别标号。n 维空间中线性判别函数的一般形式为g ( x) =ω*x + b,分类面方程为ω* x + b = 0 。将判别函数进行归一化,使两类所有样本都满足| g ( x) | ≥1 ,使离分类面最近的样本的| g ( x) | = 1 , 这样分类间隔就等于2/‖ω‖,因此,使间隔最大等价于使‖ω‖最小;要求分类面对所有样本正确分类,即满足

yi [ (ω*xi ) + b] - 1 ≥0 , i = 1 , ⋯, n

满足上述条件且使‖ω‖最小的分类面就是最优分类面。最优分类面问题可以看成约束优化问题进行求解,即在上述公式的约束下,求函数的最小值

(ω) = ‖ω‖/ 2 = (ω*ω) / 2

可以使用Lagrange 乘数法求解。

对于多类分类问题,解决的方式大概有下面两种:

(1) 通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类;

(2) 将多个分类面的参数求解合并到一个最优化问题中,通过求解该最优化问题“一次性”地实现多类分类。第二种方法尽管看起来简洁,但是在最优化问题求解过程中的变量远远多于第一种方法,训练速度不及第一种方法,而且在分类精度上也不占优。当训练样本数非常大时,这一问题更加突出。正因如此, 第一种方法更为常用。

3.3.3 朴素贝叶斯文本分类算法 3.3.3.1 贝叶斯公式

设A、B是两个事件，且P(A)>0，称

为在事件A发生的条件下事件B发生的条件概率。 乘法公式：

P(XYZ)=P(Z|XY)P(Y|X)P(X) 全概率公式：

P(X)=P(X|Y1)+ P(X|Y2)+…+ P(X|Yn) 贝叶斯公式 ：

3.3.3.2 贝叶斯定理在分类中的应用

在分类（classification）问题中，常常需要把一个事物分到某个类别[12]。一个事物具有很多属性，把它的众多属性看做一个向量，即x=(x1,x2,x3,…,xn)，用x这个向量来代表这个事物。类别也是有很多种，用集合Y={y1,y2,…ym}表示。如果x属于y1类别，就可以给x打上y1标签，意思是说x属于y1类别。这就是所谓的分类(Classification)。

x的集合记为X，称为属性集。一般X和Y的关系是不确定的，你只能在某种程度上说x有多大可能性属于类y1，比如说x有80%的可能性属于类y1，这时可以把X和Y看做是随机变量，P(Y|X)称为Y的后验概率（posterior probability），与之相对的，P(Y)称为Y的先验概率（prior probability）。

在训练阶段，我们要根据从训练数据中收集的信息，对X和Y的每一种组合学习后验概率P(Y|X)。分类时，来了一个实例x，在刚才训练得到的一堆后验概率中找出所有的P(Y|x)， 其中最大的那个y，即为x所属分类。根据贝叶斯公式，后验概率为：

在比较不同Y值的后验概率时，分母P(X)总是常数，因此可以忽略。先验概率P(Y)可以通过计算训练集中属于每一个类的训练样本所占的比例容易地估计。

3.3.3.3 朴素贝叶斯分类器 1、条件性

给定类标号y，朴素贝叶斯分类器在估计类条件概率时假设属性之间条件。条件假设可以形式化的表达如下：

其中每个训练样本可用一个属性向量X=(x1,x2,x3,…,xn)表示，各个属性之间条件。

比如，对于一篇文章，

Good good study,Day day up.

可以用一个文本特征向量来表示，x=(Good, good, study, Day, day , up)。一般各个词语之间肯定不是相互的，有一定的上下文联系。但在朴素贝叶斯文本

分类时，我们假设个单词之间没有联系，可以用一个文本特征向量来表示这篇文章，这就是“朴素”的来历。 2、朴素贝叶斯如何工作

有了条件假设，就不必计算X和Y的每一种组合的类条件概率，只需对给定的Y，计算每个xi的条件概率。后一种方法更实用，因为它不需要很大的训练集就能获得较好的概率估计。 3、估计分类属性的条件概率

P(xi|Y=y)怎么计算呢？它一般根据类别y下包含属性xi的实例的比例来估计。以文本分类为例，xi表示一个单词，P(xi|Y=y)=包含该类别下包含单词的xi的文章总数/ 该类别下的文章总数。 4、条件概率的m估计

假设有来了一个新样本 x1= (Outlook = Cloudy,Temprature = Cool,Humidity = High,Wind = Strong)，要求对其分类。我们来开始计算，

P(Outlook = Cloudy|Yes)=0/9=0 P(Outlook = Cloudy |No)=0/5=0

计算到这里，大家就会意识到，这里出现了一个新的属性值，在训练样本中所没有的。如果有一个属性的类条件概率为0，则整个类的后验概率就等于0，我们可以直接得到后验概率P(Yes | x1)= P(No | x1)=0，这时二者相等，无法分类。

当训练样本不能覆盖那么多的属性值时，都会出现上述的窘境。简单的使用样本比例来估计类条件概率的方法太脆弱了，尤其是当训练样本少而属性数目又很大时。

解决方法是使用m估计(m-estimate)方法来估计条件概率：

n是类yj中的样本总数，nc是类yj中取值xi的样本数，m是称为等价样本大小的参数，而p是用户指定的参数。如果没有训练集（即n=0），则P(xi|yj)=p, 因此p可以看作是在类yj的样本中观察属性值xi的先验概率。等价样本大小决定先验概率和观测概率nc/n之间的平衡。 3.3.3.4 朴素贝叶斯文本分类算法 (1) 文本分类问题

在文本分类中，假设我们有一个文档d∈X，X是文档向量空间(document space)，和一个固定的类集合C={c1,c2,…,cj}，类别又称为标签。显然，文档向量空间是一个高维度空间。我们把一堆打了标签的文档集合作为训练样本，∈X×C。例如：

={Beijing joins the World Trade Organization, China}

对于这个只有一句话的文档，我们把它归类到 China，即打上china标签。 我们期望用某种训练算法，训练出一个函数γ，能够将文档映射到某一个类别：

γ:X→C

这种类型的学习方法叫做有监督学习，因为事先有一个监督者（我们事先给出了一堆打好标签的文档）像个老师一样监督着整个学习过程。

朴素贝叶斯分类器是一种有监督学习，常见有两种模型，多项式模型(multinomial model)和伯努利模型(Bernoulli model)。 (2) 多项式模型

在多项式模型中， 设某文档d=(t1,t2,…,tk)，tk是该文档中出现过的单词，允许重复，则

先验概率P(c)= 类c下单词总数/整个训练样本的单词总数

类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/(类c

下单词总数+|V|)

V是训练样本的单词表（即抽取单词，单词出现多次，只算一个），|V|则表示训练样本包含多少种单词。在这里，m=|V|, p=1/|V|。

P(tk|c)可以看作是单词tk在证明d属于类c上提供了多大的证据，而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。 (3) 伯努利模型

P(c)= 类c下文件总数/整个训练样本的文件总数

P(tk|c)=(类c下包含单词tk的文件数+1)/(类c下单词总数+2) (4)两模型的区别

二者的计算粒度不一样，多项式模型以单词为粒度，伯努利模型以文件为粒度，因此二者的先验概率和类条件概率的计算方法都不同。

计算后验概率时，对于一个文档d，多项式模型中，只有在d中出现过的单词，才会参与后验概率计算，伯努利模型中，没有在d中出现，但是在全局单词表中出现的单词，也会参与计算，不过是作为“反方”参与的。

第四章 KNN文本分类算法研究

4.1 KNN文本分类算法介绍

KNN 法最初由Cover 和Hart 于1968 年提出, 是一个理论上比较成熟的方法。该算法的基本思想是:根据传统的向量空间模型, 文本内容被形式化为特征 空间中的加权特征向量, 即D=D( T1,W1; T2,W2; ⋯; Tn,Wn) 。对于一个测试文本, 计算它与训练样本集中每个文本的相似度, 找出K个最相似的文本, 根据加权距离和判断测试文本所属的类别[9]。具体算法步骤如下: ( 1) 对于一个测试文本, 根据特征词形成测试文本向量。

( 2) 计算该测试文本与训练集中每个文本的文本相似度, 计算公式为:

式中: di 为测试文本的特征向量,dj 为第j 类的中心向量;M为特征向量的维数;Wk 为向量的第k 维。K值的确定一般先采用一个初始值, 然后根据实验测试的结果调整K 值, 一般初值定为几百到几千。

( 3) 按照文本相似度, 在训练文本集中选出与测试文本最相似的k 个文本。 ( 4) 在测试文本的k 个近邻中, 依次计算每类的权重, 计算公式如下:

式中: x 为测试文本的特征向量; Sim( x,di) 为相似度计算公式; b 为阈值, 有待于优化选择; 而y(di,Cj)的取值为1 或0, 如果di 属于Cj, 则函数值为1, 否则为0。

( 5) 比较类的权重, 将文本分到权重最大的那个类别中。

KNN方法基于类比学习, 是一种非参数的分类技术, 在基于统计的模式识别中非常有效, 对于未知和非正态分布可以取得较高的分类准确率, 具有鲁棒性、概念清晰等优点。但在文本分类中, KNN 方法也存在不足, 如KNN 算法是懒散的分类算法, 其时空开销大; 计算相似度时, 特征向量维数高, 没有考虑特征词间的关联关系; 样本距离计算时, 各维权值相同, 使得特征向量之间的距离计算不够准确, 影响分类精度。针对这些不足, 分别提出了相应的改进算法。下面将详细介绍。

4.2 基于统计的KNN文本分类算法研究

1. 文档相似度的定义

在VSM中，每个文档

d

被表示成矢量中的一点，

V(d)=((t1,w1),(t2,w2),...,(tn,wn))，其中n为特征空间中所有特征数目，ti是文档d

中出现的特征项，wi是ti在d中的权重，常用tfidf权重函数，目前存在多种tfidf公式，本文采用了一种比较普遍的计算公式：

其中，tf(ti,d)是特征ti在文档d中的词频，|D|是整个训练集D中的文档数，

df(ti)是D中包含特征ti的文档数。

VSM模型中文档以向量的形式定义到了实数域，使得文档之间相似度的计算变成了向量之间相似度的计算．向量相似度的度量方式有多种，普遍应用的是余弦相似度，它定义两个文档特征向量的相似度为向量之间夹角的余弦：

由于文档集合中特征数量很大，通常达到数万或数十万之多，即便经过特征选择，特征空间维数相对于一篇文档中的有效的特征数量而言仍然很大，使得文档的特征向量具有稀疏性，即其中大部分的元素为0．在大规模的文本训练测试中这对系统的空间分配能力是一个考验。为了解决特征矢量维数过大的问题，本文使用文档中的tfidf最高的n’个词汇，形成一个n’维特征向量

V(d)=((t1,w1),(t2,w2),...,(tn,wn))来代表一篇文档，其中wi是ti在对应的文档d中

的tfidf值，ti是d中tfidf第i高的词汇，这样每篇文档的特征向量就缩小为了n’维，这大大减少了 系统的空间复杂度，但是考察两篇文档之间的相似度时，由于两个向量中相应位置的词不一定相同，因而不能直接使用余弦相似度来计算[15]。

考虑到有些特征虽然不同，但是它们在分类中的作用却十分相似，不少特征词的CH1分布曲线是相似的甚至重合的，而对文档的CHI曲线分布而言，相同类别的文档之间的CHI曲线分布较为相似，不同类别的文档之间的CHI曲线分 布则差异较大．因此本文将文档向量a，b之间的相似度定义为向量a，b之间的CHI向量之间夹角的余弦：

2. 利用类别特征集进行初次类别判断

模式分类方法中，类中心向量法是最简单直观的，它使用类内所有文档的中心向量作为类的代表向量，测试时计算待分类样本与各类中心向量之间的距离，并将其划分为与之距离最小的类．中心向量通常取类内所有文档向量的几何平均值．和kNN算法中每一个测试文档要和所有训练文档计算相似度比起来，类中心向量法分类时每一个测试文档只需和m个类别特征集计算相似度，计算量大大降低，可以在很短的时间内得到分类结果．但对于一对一的分类而言，在这种方式建立的中心向量含有的类别特征信息不够丰富，分类器性能不够理想．我们在实验中发现，若扩充分类器为多类分类，返回m个可能的类别，当m取总类

别数的1/4时，绝大多数的测试文档的人工分类结果就会在此结果集中．在返回的结果集中运用kNN算法，就能在比较短的时间内找到测试样本的最近邻． 受上述事实的启发，本文采取了两次类别判定的方法，在kNN算法中引入了初次类别判断机制，并修改类中心向量为类的类别持征集，以获得更丰富的类别信息．如果在特征t的CHI向量中，第i维的值明显大于其他维的值，那么我们认为t和第i个类别的相关性很强，t成为该类的一个特征．把该类所有的类似特征集中起来，组成该类的类别特征集。 从直观上说，如果文档属于类别C，，它和Ci对应的类别特征集中词相同的概率也应该越大，和C，的距离就应该越小．同时我们认为，在文档和类别特征集同出现的特征中，文档中权值大的特征相比权值小的特征更能表征二者内容的相似性．因此，本文定义距离公式如下：

设a(x1,x2,...xm)是类别特征集，b(y1,y2,...yn)是文档特征向量，则a和b

之间的距离为：

其中(x,y)w(y),w是特征分量的权值，利用所有类的类别特征集，对测试

文档进行类别的初次判断，选出其最有可能的m个类别，然后计算测试文档和训练集中类别在那m个类别范围的文档之间的相似度，找出与测试文档相似度最大的k个邻居，并根据这k个邻居判定测试文档的类别．类别的初次判断机制能在小范围的训练集中快速搜索测试文档的最近邻，避免了和所有训练集文档计算相似度所带来的巨大计算量，并避免了和大量的无关的类的训练文档之间的相似度计算给分类带来的噪声．类别初次判断算法如下：

输人：类别集C，测试集Te，类别特征数n，可能类别数m，所有特征的CHI向量．

输出：各测试集文档的可能类别集合

1)求每个类的类别特征集V：逐个扫描特征集的CHI向量，若该特征和某类别ci明显相关，则将该特征加入Ci的类别特征集V 中； 2)新测试文本到来后，将文本表示为特征向量；

3)利用公式(6)计算新文本特征向量和每类类别特征集间的距离；

4)比较每个类别特征集与新文本的距离，将文本分到距离最小的前m个类别中； 5)若所有测试文档均已分类，算法结束；否则转2)． 3. 基于统计的KNN文本分类算法流程

输人：类别集C，测试集Te，训练集Tr，最近邻居数k，初次类别判断的可能类别数m

输出：各测试集文档的类别

1)根据公式(1)计算训练集中各特征的CHI向量；

2)根据特征的CHI向量进行特征选择，得到有效的特征空间子集； 3)根据公式(2)计算训练集中各文档的CHI向量；

4)取新的测试文档d，计算d的特征向量和CHI向量；

5)运用初次类别判定算法，得到d的m个可能的类别集合；

6)根据公式(5)计算d与训练集中类别在该m个类别集中的训练文档之间的相似度；

7)对相似度进行排序，找出d的k个最近邻居，并判定d的类别；

8)若所有测试文档均已分类，算法结束；否则转4)

4.3 基于LSA降维的KNN文本分类算法研究

KNN方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别中非常有效，对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰等诸多优点．但同时在文本分类中，KNN也存在着一定的不足：首先是对于高维文本向量活样本级规模较大时，算法的时间和空间复杂度较高，其时间复杂度为0(m*n)， 为VSM空间特征维数，m为样本集大小；其次是对于文本的高维向量，对于分类起主要作用的维数远远小于文本本身的维数，相当多的维数对于文本分类意义不大甚至成为噪声数据，对分类的准确性产生负面的影响[16]．

针对上述缺点，应用潜在语义分析(Lantent Semantic Analysis，LSA)可得到有效解决．LSA通过将原来的文本和词的向量矩阵进行奇异值分解，将文本的关键词空间用更小的语义空间进行表示．LSA生成的新语义空间中相关文档更为接近，而且对解决降低分类精度的同义词和多义词问题更为有效． 1. LSA的基本思想

潜在语义分析是一种用于知识获取和战士的计算理论和方法。其隐含的思想是，通过语义处理给定词的所有上下文，同时提供了决定词含义的相似性的相互。在LSA处理中，文档首先被抽词，表示成词频的集合，一个文档库可以表示成一个m*n词的文档矩阵A，这里每个不同的词对应矩阵A的每一行；而每一个文档则对应与矩阵A的一列。A表示为：A=[aij],其中aij为非负值，表示第i个词在第j个文档中的权重。在实验中，，对于单个词的权重主要考虑其对文本的表征程度和所带的文本的信息量，所以对权重的处理主要考虑了两方面的贡献，即局部权值和全局权值，局部权值和全局权值有不同的取值方法，取值方法的不同会对最后分类的结果产生一定的影响．我们选用了如下方法：

其中Wi表示该词条在矩阵中的权重，tfi表示该词条在文本初夏你的频率；idfi表示该词条的反比文本频率，N是整个文档的文档个数，n是包含该词条的文档的个数。

大多数文本只含有一部分词，所以经过处理的矩阵还是典型的稀疏矩阵；同时由于矩阵中的每个词都在每个文章项中有所表示，造成矩阵中含有很多不能表征文本信息的项．通过对此矩阵的奇异值变换可以降低矩阵的纬度，将文档在更少、更能表示其特征的语义空间表示出来．通过奇异值分解，矩阵A可以表示为三个矩阵的乘积：

TUkVkTVkIk，Uk和Vk的列分别被称为矩阵Ak的左右奇异向量，k其中Uk是对角矩阵，对角元素被称为矩阵Ak的奇异值。

Uk矩阵中的行向量对应原矩阵A的词向量．Vk矩阵中的行向量则对应原矩

阵A 的文档向量．这里Uk矩阵和Vk矩阵中的单个项不一定是非负数，词与词以及文档与文档之间的关系是通过整行之间的相关关系来获得的．

k是奇异值按递减排列的对角矩阵．因此，我们可以将k最中最大的k个

奇异值提取出来，同时留下Uk和Vk中相应的奇异向量，构建A的k-维近似矩阵．这里参数忌的选择非常重要，英文文档实验证明，相对较小的k值(100-300)就可以取得有效的结果.

当潜在语义分析用于分类时，分类文本也通过与产生的新矩阵的降维变换用相同的K维表示，其具体数学变换方法如下：

其中，d为初始文档向量，d*为降维变换后的文档向量．

一旦检索项用k维表示出来后，检索项与文档项之间的空间距离就可以通过点积求出。通过点积的大小，我们就可以将相关文档以相关度顺序列出。

2. 基于LSA降维的KNN文本分类算法

在上述分析基础上，可以对KNN文本分类算法进行改进，达到降维目的，提高分类效率和分类精确度．算法可分为以下几个步骤：

(1)采用VSM模型，根据文本特征词形成测试文本特征向量矩阵； (2)运用LSA理论对文本特征矩阵做降维处理；

(3)利用余弦定理计算测试文本与训练集中每个文本的文本相似度，根据相似度，在训练文本集中选出与新文本最相似的忌个文本； (4)在测试文本的忌个邻居中，依次计算每类的权重； (5)比较类的权重，将文本分到权重最大的那个类别中．

4.4 其他改进的KNN文本分类算法

(1) 提高分类效率的改进算法

KNN 算法的主要缺点是, 当训练样本数量很大时将导致很高的计算开销。KNN 算法是懒散的分类算法, 对于分类所需的计算都推迟到分类时才进行, 在其分类器中存储有大量的样本向量, 在未知类别样本需要分类时, 再计算和所有存储样本的距离, 对于高维文本向量或样本集规模较大的情况, 其时间和空间复杂度较高。针对这个缺点, 提出了一些改进算法: 如基于Fuzzy ART 的K- 最近邻分类改进算法,该算法用模糊自适应共振理论( Fuzzy ART) 对K- 最近邻的训练样本集进行浓缩, 以改善K- 最近邻的计算速度。该算法首先用Fuzzy ART 将训练样本集中的每一类样本进行聚类, 减少了训练样本集的数据量, 提高了算法的计算速度, 保持了预测精度, 从而使该算法适用于海量数据集的情况。试验表明, 该算法适用于对复杂而数据量较大的数据库进行分类。提出了一种基于K- 近邻方法的渐进式中文文本分类技术, 利用文本的标题、摘要、关键词、重点段落进行渐进式的分类处理。这样, 不用分析全文就能将部分待分类文本成功分类, 从而提高了文本分类的效率。试验结果表明, 该方法在保证分类准确率的基础上能够有效地提高分类效率。对于减少KNN 计算量的优化而做的研究主要是如何

从原始数据集中选取代表实例集, 大部分仅对低维的情况适用, 而且在代表实例集每增加或删除一个代表实例时, 都要对样本进行一次测试, 工作量大, 为此, 根据测试文档在各个样本类中的分布情况,提出了基于KNN 分类的两个有助于减少大量计算的重要算法:排类算法和归类算法。从而构建了一个基于KNN 的快速文档分类方法。理论与实验证明, 这种方法可以在不影响原有准确率的条件下, 提高文档的分类速度。

(2) 基于模式聚合和特征降维的改进算法

在计算相似度时, 不考虑特征词间的关联关系。针对这一不足进行的改进有: 主要考虑文档间特征词属性关联与共现对相似度的作用, 用一个匹配系数调整两文档间的距离。它实质上是强化了文本中语义链属性因子的作用, 修正了次要因素的噪声影响, 使文本分类结果更加理想, 已有的测试结果证明了这一点, 尤其在测试文本与训练文本集中的某些文本直观上较相似时, 结果更佳。通过分析特征词对分类贡献的大小, 提出了一种应用向量聚合技术的KNN 文本分类方法, 很好的解决了关联特征词的提取问题, 该方法根据每个特征词的CHI 分布曲线来确定它们在分类中的贡献, 应用向量聚合技术很好地解决了关联特征词的提取问题。其特点在于: 聚合文本向量中相关联的特征词作为特征项, 从而取代传统方法中一个特征词对应向量一维的做法, 这样不但缩减了向量的维数, 而且加强了特征项对文本分类的贡献。试验表明, 该方法明显提高了分类的准确率和召回率。

(3) 基于特征加权的改进算法

KNN 方法是建立在VSM模型上的, 其样本距离的测度使用欧式距离或余弦距离, 各维权值相同, 也就是以为各维对于分类的贡献是相同的, 这是不符合实际情况的, 同等的权重使得特征向量之间距离或夹角余弦的计算不够准确, 进而影响分类精度。针对这一不足, 提出了基于神经网络和CHI 的改进KNN 方法, 应用SOM神经网络进行VSM模型各维权重的计算。该方法首先运用CHI 概率统计方法进行初步特征提取和模式聚合, 其特征权重的计算原理为: 如果某一维在各个类别中取值基本相同, 那么此维对于文本分类的贡献率就相对较低, 如果在各个类别中取值有较大的差异, 那么就具有较强的文本分类能力, 而方差正好是反应变量分布均匀状态的主要指标。该方法有效地提高了文本分类的精度。提出了利用SVM来确定特征的权重, 即基于SVM特征加权算法( FWKNN,feature weighted KNN) 。试验表明, 在一定的条件下,FWKNN 能够极大地提高分类准确率。该方法利用SVM 可以定量确定样本的每个特征与分类的相关度———由分类函数的权重向量给出:

其中为每个样本对应的Lagrange 乘子。特征权重确定后, 就可以修改样本之间的距离函数以便更好地反映实际问题。

(4) 其它改进算法

此外, 还提出了一些其它的改进算法, 如改进的KNN 与SVM相融合的文本分类算法。该算法利用文本聚类描述KNN 算法中文本类别的内部结构, 用sigmoid函数对SVM输出结果进行概率转换, 同时引入CLA(Classifier’s Local Accuracy) 技术进行分类可信度分析以实现两种算法的融合, 试验表明该算法综合了KNN 与SVM在分类问题中的优势, 既有效地降低了分类候选的数目, 又相应地提高了文本分类的精度,具有较好的性能。提出了LSI( 隐含语义索引) 和

KNN相结合的文本分类模型研究。该方法既充分利用了向量空间模型在表示方法上的巨大优势, 又弥补了其忽略语义的不足, 具备一定的理论和现实意义。

第五章 文本挖掘应用

5.1 数据挖掘应用

5.1.1 数据挖掘解决的典型商业问题

需要强调的是，数据挖掘技术从一开始就是面向应用的。目前，在很多领域，数据挖掘(data mining)都是一个很时髦的词，尤其是在如银行、电信、保险、交通、零售（如超级市场）等商业领域。数据挖掘所能解决的典型商业问题包括：数据库营销（Database Marketing）、客户群体划分（Customer Segmentation & Classification）、背景分析（Profile Analysis）、交叉销售（Cross-selling）等市场分析行为，以及客户流失性分析(Churn Analysis)、客户信用记分(Credit Scoring)、欺诈发现(Fraud Detection)等等。 5.1.2 数据挖掘在市场营销的应用

数据挖掘技术在企业市场营销中得到了比较普遍的应用，它是以市场营销学的市场细分原理为基础，其基本假定是“消费者过去的行为是其今后消费倾向的最好说明”。

通过收集、加工和处理涉及消费者消费行为的大量信息，确定特定消费群体或个体的兴趣、消费习惯、消费倾向和消费需求，进而推断出相应消费群体或个体下一步的消费行为，然后以此为基础，对所识别出来的消费群体进行特定内容的定向营销，这与传统的不区分消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了营销效果，从而为企业带来更多的利润。

商业消费信息来自市场中的各种渠道。例如，每当我们用信用卡消费时，商业企业就可以在信用卡结算过程收集商业消费信息，记录下我们进行消费的时间、地点、感兴趣的商品或服务、愿意接收的价格水平和支付能力等数据；当我们在申办信用卡、办理汽车驾驶执照、填写商品保修单等其他需要填写表格的场合时，我们的个人信息就存入了相应的业务数据库；企业除了自行收集相关业务信息之外，甚至可以从其他公司或机构购买此类信息为自己所用。

这些来自各种渠道的数据信息被组合，应用超级计算机、并行处理、神经元网络、模型化算法和其他信息处理技术手段进行处理，从中得到商家用于向特定消费群体或个体进行定向营销的决策信息。这种数据信息是如何应用的呢？举一个简单的例子，当银行通过对业务数据进行挖掘后，发现一个银行帐户持有者突然要求申请双人联合帐户时，并且确认该消费者是第一次申请联合帐户，银行会推断该用户可能要结婚了，它就会向该用户定向推销用于购买房屋、支付子女学费等长期投资业务，银行甚至可能将该信息卖给专营婚庆商品和服务的公司。数据挖掘构筑竞争优势。

在市场经济比较发达的国家和地区，许多公司都开始在原有信息系统的基础上通过数据挖掘对业务信息进行深加工，以构筑自己的竞争优势，扩大自己的营业额。美国运通公司(American Express)有一个用于记录信用卡业务的数据库，数据量达到54亿字符，并仍在随着业务进展不断更新。运通公司通过对这些数据进行挖掘，制定了“关联结算(Relation ship Billing)优惠”的促销策略，即如果一个顾客在一个商店用运通卡购买一套时装，那么在同一个商店再买一双鞋，就可以得到比较大的折扣，这样既可以增加商店的销售量，也可以增加运通卡在该商店的使用率。再如，居住在伦敦的持卡消费者如果最近刚刚乘英国航空公司的航

班去过巴黎，那么他可能会得到一个周末前往纽约的机票打折优惠卡。 基于数据挖掘的营销，常常可以向消费者发出与其以前的消费行为相关的推销材料。卡夫(Kraft)食品公司建立了一个拥有3000万客户资料的数据库，数据库是通过收集对公司发出的优惠券等其他促销手段作出积极反应的客户和销售记录而建立起来的，卡夫公司通过数据挖掘了解特定客户的兴趣和口味，并以此为基础向他们发送特定产品的优惠券，并为他们推荐符合客户口味和健康状况的卡夫产品食谱。美国的读者文摘(Reader's Digest)出版公司运行着一个积累了40年的业务数据库，其中容纳有遍布全球的一亿多个订户的资料，数据库每天24小时连续运行，保证数据不断得到实时的更新，正是基于对客户资料数据库进行数据挖掘的优势，使读者文摘出版公司能够从通俗杂志扩展到专业杂志、书刊和声像制品的出版和发行业务，极大地扩展了自己的业务。

基于数据挖掘的营销对我国当前的市场竞争中也很具有启发意义，我们经常可以看到繁华商业街上一些厂商对来往行人不分对象地散发大量商品宣传广告，其结果是不需要的人随手丢弃资料，而需要的人并不一定能够得到。如果搞家电维修服务的公司向在商店中刚刚购买家电的消费者邮寄维修服务广告，卖特效药品的厂商向医院特定门诊就医的病人邮寄广告，肯定会比漫无目的的营销效果要好得多。

5.1.3 数据挖掘在企业危机管理中的应用

危机管理是管理领域新出现的一个热点研究领域，它是以市场竞争中危机的出现为研究起点，分析企业危机产生的原因和过程，研究企业预防危机、应付危机、解决危机的手段和策略，以增强企业的免疫力、应变力和竞争力，使管理者能够及时准确地获取所需要的信息，迅速捕捉到企业可能发生危机的一切可能事件和先兆，进而采取有效的规避措施，在危机发生之前对其进行控制，趋利避害，从而使企业能够适应迅速变化的市场环境，保持长久的竞争优势。但是由于危机产生的原因复杂，种类繁多，许多因素难以量化，而且危机管理中带有大量不确定因素的半结构化问题和非结构化问题，很多因素由于没有历史数据和相应的统计资料，很难进行科学地计算和评估，因此需要应用其它技术和方法来加强企业的危机管理工作。

随着计算机技术、网络技术、通讯技术、Internet技术的迅速发展和电子商务、办公自动化、管理信息系统、Internet 的普及等，企业业务操作流程日益自动化，企业经营过程中产生了大量的数据，这些数据和由此产生的信息是企业的宝贵财富，它如实地记录着企业经营的本质状况。但是面对如此大量的数据，传统的数据分析方法，如数据检索、统计分析等只能获得数据的表层信息，不能获得其内在的、深层次的信息，管理者面临着数据丰富而知识贫乏的困境。如何从这些数据中挖掘出对企业经营决策有用的知识是非常重要的，数据挖掘便是为适应这种需要应运而生的。

数据挖掘是一种新的信息处理技术，其主要特点是对企业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助经营决策的关键性数据，它在企业危机管理中得到了比较普遍的应用，具体可以应用到以下几个方面。

1.利用Web页挖掘搜集外部环境信息

信息是危机管理的关键因素。在危机管理过程中，可以利用Web 页挖掘技术对企业外部环境信息进行收集、整理和分析，尽可能地收集政治、经济、、科技、金融、各种市场、竞争对手、供求信息、消费者等与企业发展有关的信息，集中精力分析处理那些对企业发展有重大或潜在重大影响的外部环境信息，抓住

转瞬即逝的市场机遇，获得企业危机的先兆信息，采取有效措施规避危机，促使企业健康、持续地发展。

2.利用数据挖掘分析企业经营信息

利用数据挖掘技术、数据仓库技术和联机分析技术，管理者能够充分利用企业数据仓库中的海量数据进行分析，并根据分析结果找出企业经营过程中出现的各种问题和可能引起危机的先兆，如经营不善、观念滞后、产品失败、战略决策失误、财务危机等内部因素引起企业人、财、物、产、供、销的相对和谐平衡体遭到重大破坏，对企业的生存、发展构成严重威胁的信息，及时做出正确的决策，调整经营战略，以适应不断变化的市场需求。 3.利用数据挖掘识别、分析和预防危机

危机管理的精髓在于预防。利用数据挖掘技术对企业经营的各方面的风险、威胁和危险进行识别和分析，如产品质量和责任、环境、健康和人身安全、财务、营销、自然灾害、经营欺诈、人员及计算机故障等，对每一种风险进行分类，并决定如何管理各类风险；准确地预测企业所面临的各种风险，并对每一种风险、威胁和危险的大小及发生概率进行评价，建立各类风险管理的优先次序，以有限的资源、时间和资金来管理最严重的一种或某几类风险；制定危机管理的策略和方法，拟定危机应急计划和危机管理队伍，做好危机预防工作。 4.利用数据挖掘技术改善客户关系管理

客户满意度历来就是衡量一个企业服务质量好坏的重要尺度，特别是当客户的反馈意见具有广泛效应的时候更是如此。目前很多企业利用营销中心、新闻组、 BBS以及呼叫中心等收集客户的投诉和意见，并对这些投诉和意见进行分析，以发现客户关系管理中存在的问题，如果有足够多的客户都在抱怨同一个问题，管理者就有理由对其展开调查，为企业及时捕捉到发生危机的一切可能事件和先兆，从而挽救客户关系，避免经营危机。

5.利用数据挖掘进行信用风险分析和欺诈甄别

客户信用风险分析和欺诈行为预测对企业的财务安全是非常重要的，使用企业信息系统中数据库的数据，利用数据挖掘中的变化和偏差分析技术进行客户信用风险分析和欺诈行为预测，分析这些风险为什么会发生？哪些因素会导致这些风险？这些风险主要来自于何处？如何预测到可能发生的风险？采取何种措施减少风险的发生？通过评价这些风险的严重性、发生的可能性及控制这些风险的成本，汇总对各种风险的评价结果，进而建立一套信用风险管理的战略和监督体系，设计并完善信用风险管理能力，准确、及时地对各种信用风险进行监视、评价、预警和管理，进而采取有效的规避和监督措施，在信用风险发生之前对其进行预警和控制，趋利避害，做好信用风险的防范工作。 6.利用数据挖掘控制危机

危机一旦爆发，来势迅猛，损失严重，因此危机发生以后，要采取有力的措施控制危机，管理者可以利用先进的信息技术如基于Web 的挖掘技术、各种搜索引擎工具、E－mail自动处理工具、基于人工智能的信息内容的自动分类、聚类以及基于深层次自然语言理解的知识检索、问答式知识检索系统等快速地获取危机管理所需要的各种信息，以便向客户、社区、新闻界发布有关的危机管理信息，并在各种媒体尤其是公司的网站上公布企业的详细风险防御和危机管理计划，使全体员工能够及时获取危机管理信息及危机最新的进展情况。这样企业的高层管理人员、公关人员、危机管理人员和全体员工就能随时有准备地应付任何复杂情况和危急形势的压力，对出现的危机立即做出反应，使危机的损失降到最低。

5.2 文本挖掘应用

文本挖掘具有广泛的应用前景，它不仅可以用于企业的有决策需求的业务部门，而且可以用于提供综合信息服务的网站。从企业角度来看，在当今社会任何一个企业都不能再只关注企业内部的情况，必然要关心竞争对手、合作伙伴、市场变换等企业外部环境，而WWW是获取这些信息的最好途径。但是它们大多是非结构化或半结构化的文档和Web页面，数据分散、结构多样，难于综合分析。文本挖掘便可帮助企业员工(尤其是需要实时有效信息的决策部门)获取最新的、来自世界范围的和自己所感兴趣的Web文档信息，并在此基础上进行分析和进一步的利用[13]。具体说来，文本挖掘的应用可以概括成以下几个方面：

(1)在电子邮件管理中的应用

利用文本挖掘构造的电子邮件路由，可以在对电子邮件进行文本挖掘以后，确定由哪个部门、哪个人来处理这些电子邮件，并且可以根据电子邮件的内容进行相关统计

(2)在文档管理中的应用

文档管理是许多组织中十分烦琐而又非常重要的工作，通过文本挖掘可以帮助组织对成千上万的文档实现有效的管理，可以使组织很快地了解需要查询的文档的所在位置，以及其包含的内容。

(3)在客户自动问答系统中的应用

企业可以用文本挖掘来建立一个客户自动问答系统，对客户所寄的信件、电子邮件进行文本挖掘以后，根据其反映的主要问题，能够在确定客户的需求置信度以后，自动给客户发送合适的回信。

(4)在市场研究中的应用

企业可以用连机文本挖掘系统对因特网上所出现的特定词、概念和主题进行挖掘统计，进而对市场进行客观的统计分析。

(5)在情报收集中的应用

企业可以用一些具有文本挖掘功能的自动智能网络爬虫，收集与企业有关的市场、竞争对手以及市场环境的信息，并给出总结性的分析报告。

5.3 文本分类应用

当然，目前真正大量使用文本分类技术的，仍是依据文章主题的分类，而据此构建最多的系统，当属搜索引擎[14]。内里的原因当然不言自明，我只是想给大家提个醒，文本分类还不完全等同于网页分类。网页所包含的信息远比含于其中的文字（文本）信息多得多，对一个网页的分类，除了考虑文本内容的分类以外，链入链出的链接信息，页面文件本身的元数据，甚至是包含此网页的网站结构和主题，都能给分类提供莫大的帮助（比如新浪体育专栏里的网页毫无疑问都是关于体育的），因此说文本分类实际上是网页分类的一个子集也毫不为过。当然，纯粹的文本分类系统与网页分类也不是一点区别都没有。文本分类有个重要前提：即只能根据文章的文字内容进行分类，而不应借助诸如文件的编码格式，文章作者，发布日期等信息。而这些信息对网页来说常常是可用的，有时起到的作用还很巨大！因此纯粹的文本分类系统要想达到相当的分类效果，必须在本身的理论基础和技术含量上下功夫。

除了搜索引擎，诸如数字图书馆，档案管理等等要和海量文字信息打交道的

系统，都用得上文本分类。 (1)电子政务

随着我国信息技术水平的提高和“金字工程“ 建设的不断深人, 如何利用现代化互联网络加强电子政务建设已经成为一个值得广泛调研的课题。目前各级及其职能部门基本上都有门户网站和内部办公系统, 通过建立电子政务专用词典和基于内容的公文知识库, 应用文本分类技术就可以快速准确的对各类信息进行类别判断和分类管理, 对提高相关部门的管理水平和办公效率将起到一定的促进作用。 (2)搜索引擎

搜索引擎的使用为洲门上网寻找相关信息提供了便利,目前基于中文的搜索引擎技术也取得了很多先进的研究成果。搜索引擎可分为目录分类式和全文检索式, 一般包括六个部分= 网页抓取器、分析器、索引器、检索器、分类器和用户接口。中文搜索引擎不仅要具有很高的准确度, 而且结果反馈也必须迅速, 这就对中文文本分类算法提出了更高的要求, 也为中文文本分类提供了更广泛的应用平台。 (3)信息过滤

互联网上的信息良蔫不齐, 有时还会次到垃圾邮件, 信息安全特别是网络信息内容安全越来越受至关注。信息过滤是大规模内容处理的一种典型应用, 即将持续的信息进行过滤操作, 将符合需求的信息保留, 不需要的信息屏蔽, 而且可以对过滤策略进行调整。信息过滤的关键是过滤器的设计, 可以采用某种文本分类算法完成, 这样就将过滤器的设计转化成文本分类器的设计。

第六章 结论

随着网络的迅猛发展，网上的网页，电子邮件，数据库，聊天室和数字图书馆等电子信息成指数级不断增长，如何自动处理这些海量信息成为目前重要的研究课题。自动处理信息的主要环节包括信息抽取、信息分类和信息检索。信息分类处于中间环节，主要将抽取到的信息自动有效地分成一定的类别，以便于信息的检索。通过智能的方法，有效的自动分类与日俱增的信息成为信息处理的重要研究趋势之一。本文主要介绍了信息分类中的文本信息分类相关算法和文本挖掘的应用前景，并针对所存在的一些问题，提出一些新的思想对有关算法进行改进和提高。

本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析。

自动信息分类是随着网络的发展而兴起的研究领域。对于网上丰富和便利的未标记数据，我们将在现有的基础上，结合聚类的思想，归总有效的改进分类方法，实现一个满足市场应用需求的高效网络化的信息分类系统是我们一个努力的方向。

参考文献

[1] http://baike.baidu.com/view/73.htm [2] 梅馨, 邢桂芬 ．文本挖掘技术综述[J]．江苏大学学报(自然科学版)，第24 卷

第5 期，2003 年9 月．

[3] 湛燕,陈昊．文本挖掘研究进展[J]．河北大学学报(自然科学版)，第23 卷第

2 期，2003 年6 月．

[4] 袁军鹏，朱东华．文本挖掘技术研究进展[J]．计算机应用研究，2006 年第2

期．

[5] 李芳．文本挖掘若干关键技术研究[D]. 北京：北京化工大学，2010. [6] 张俊丽.文本分类中的关键技术研究[D]．武汉：华中师范大学，2008． [7] 彭雅.文本分类算法及其应用研究[D]. 湖南：湖南大学，2004.

[8] 杨震．文本分类和聚类中若干问题的研究[D]. 北京：北京邮电大学，2007. [9] 杨丽华，戴齐．KNN文本分类算法研究[J]. 微计算机信息, 2006 年第22 卷

第7-3 期.

[10] 程泽凯, 陆小艺. 文本分类中的特征选择方法[J]. 安徽工业大学学报,第21卷

第3期，2004年7月．

[11] 马金娜, 田大钢．基于支持向量机的中文文本自动分类研究[J]．系统工程与

电子技术，第29卷第3期，2007年3月．

[12] http://www.yanjiuyanjiu.com/2010/05/28/naive-bayes-text-classification. [13] 蒋良孝，蔡之华.文本挖掘及其应用[J]. 应用技术,2003年2月．

[14] 马忠宝，刘冠蓉.中文文本分类在信息技术中的应用研究[J].中国水运，第06

卷第02期，2006年2月． [15] 印鉴，谭焕元. 基于2统计量的KNN文本分类算法[J]. 小型微型计算机系统，2007年6月第6期．

[16] 李良俊，张斌等. 基于LSA降维的KNN文本分类算法[J]. 东北师大学报(自

然科学版)，2007年6月第39卷第2期.