文本分类技术范文

文本分类技术范文（精选7篇）

文本分类技术 第1篇

文本分类属于有监督的机器学习,即利用预定义的文本类别和训练文本指导新的测试文本的学习,从而确定新文本的类别。从数学角度来说,文本分类可以这样定义:设文档集D={d1,d2,,di},预定义类集C={c1,c2,,ci},确定任意一个元组映射到集合{True,False}上的值,故文本分类器实际上就是这样一个函数θ:DC{True,False}。图1给出了文本分类的一般处理过程图。

2 文本处理

2.1 分词

在使用向量空间模型表示文本时,是以特征项为基本单位的,而特征项可以取字、词或短语,所以,要对文本进行相应的预处理操作,提取出特征项序列。在汉语中,词是最小的语义基本单位,中文信息处理系统只要涉及句法、语义,就需要以词为基本单位,而文本分类算法也一般采用特征项表示文本。由于中文的表示中词与词之间没有明显的间隔符号,因而自动分词问题是中文信息处理的难点。

2.2 特征选择

文本分类中的特征选择方法主要有:特征词的文档频率法DF(Document Frequency)、信息增益法IG(Information Gain)、互信息法MI(Mutual Information),χ2统计法(CHI)、交叉熵(Cross Entropy)等。

1)特征词的文档频率(DF)

一个特征的文档频率(Document Frequency)是指在文档集中含有该特征的文档数目。采用DF作为特征选择,基于如下基本假设:DF值低于某个阈值的词条是低频词,它们不含或含有较少的类别信息。我们假定很少出现的特征词携带的信息量为0,或者说对分类性能的影响不大。将这样的词条从原始特征空间中除去,不但能够降低特征空间的维数,而且还有可能提高分类的精度。文档频率是最简单的特征抽取技术,由于其相对于训练语料规模具有线性的计算复杂度,它能够很容易被用于大规模语料统计。

2)信息增益方法(IG)

信息增量(Information Gain)表示文档中包含某一特征值时文档类的平均信息量。它定义为某一特征在文档中出现前后的信息熵之差。假设c为文档类变量,C为文档类集合,d为文档,f为特征。对于特征f,其信息增量记为IG(f),计算公式如下:

3)交叉熵(CE)

交叉熵(Cross Entropy)和信息增益相似,不同之处在于信息增益中同时考虑到了特征在文本中发生与不发生时的两种情况,而交叉熵只考虑特征在文本中发生的一种情况。对于特征f,其交叉熵记为CE(f),计算公式如下:

在只考虑单个类的时候,则有:

4)χ2统计量(CHI)

χ2统计也是用于表征两个变量的相关性,但它比互信息更强,因为它同时考虑了特征词存在与不存在时的情况。对于文档类别c和特征f,其χ2统计的计算公式如下:

当c与f相互独立时,χ2(c,f)为0。和互信息类似,取平均值:

5)互信息方法(MI)

互信息是用于表征两个变量间相关性的。对于文档类别c和特征f,其互信息记为M(c,f),计算公式如下:

显然,当f独立于c时,MI(c,f)为0,在应用时一般取平均值:

3 文本表示

文本表示的模型常用的有:布尔逻辑模型(Boolean Model),向量空间模型(VSM,Vector Space Model),潜在语义索引(LSI,Latent Semantic Indexing)和概率模型(Probabilitic Model)。目前文本的表示主要采用的是向量空间模型。向量空间模型的基本思想是使用词袋法(Bag of Word)表示文本,这种表示法的一个关键假设,就是文章中词条出现的先后次序是无关紧要的,每个特征词对应特征空间的一维,将文本表示成欧氏空间的一个向量。在一个文本中,每个特征项都被赋予一个权重,以表示特征项在该文本中的重要程度舍弃了各个特征项之间的顺序信息之后,一个文本就表示成一个向量,即特征空间中的一个点。如文本的表示:V(di)=(wi1,wi2,,wik,,win)。其中,wik=f(tk,ci)为权值函数,反映特征tk决定文档di是否属于类ci的重要性。对于所有的文档都可以映射到此文本向量空间,从而将文档信息的匹配问题转化为向量空间中的矢量匹配问题。n维空间中点的距离用向量之间的余弦夹角来度量,也即表示了文档间的相似程度。假设目标文档为U,未知文档为Vi,夹角越小说明文档的相似度越高。余弦夹角的相似度计算公式如公式(8)所示。

4 文本分类模型评估

文本分类中普遍使用的性能评估指标有召回率(Recall,简记为r)、准确率(Precision,简记为p)。对于文本集中的每一个类别,使用列联表(Contigency Table)来计算召回率和准确率。表1为一个列联表示例。

这时,r和p分别定义为:

常用的将召回率和准确率结合起来的性能评价方法是F测量,其计算公式为:

其中,β是一个用来调节召回率和准确率权重的参数。β一般取值为1,这时公式(11)转化为:

在公式(12)中,当p和r为宏平均值时,那么F1值称为宏平均F1值(Macro-averaging F1);当p和r为微平均值时,那么F1值称为微平均F1值(Micro-averaging F1)。

5 结论

本章主要介绍了三个方面的内容,即文本分类的一般过程,文本处理和文本分类模型评估。在文本处理中介绍了文档频率法DF、信息增益法IG、互信息法MI,χ2统计法、交叉熵等特征选择方法;文本表示中主要介绍了向量空间模型。在分类模型评估这一块列出了常用的分类方法质量评估方法,主要是微平均、宏平均值等。

摘要：该文介绍了文本分类的定义,主要的特征选择方法,文本表示的向量空间模型,分类效果的评价指标。

关键词：文本分类,特征选择,向量空间模型

参考文献

[1]Sebastiani F.Machine learning in automated text categorization.ACM Computing Surveys,2002,34(1):1-47.

[2]李荣陆.文本分类及其相关技术研究[D].上海:复旦大学计算机软件与理论,2005.

[3]Yiming Yang.Jan O Pedersen:A Comparative Study on Feature Selection in Text Categorization,1997.

谈文本分类中的相关技术 第2篇

简单地说, 文本分类系统的任务就是:在给定的分类体系下, 根据文本的内容自动确定文本的类别。从数学角度来看, 文本分类是一个映射的过程, 它将未标明类别的文本映射到已有的类别中, 该映射可以是一对一的映射, 也可以是一对多的映射, 因为通常一篇文本可以同多个类别相关联。文本分类的映射过程是根据映射规则完成的。映射规则是系统根据已经掌握的每类样本的数据信息, 通过总结分类的规律性而建立的判别规则。在遇到新文本时, 根据总结出的判别规则, 确定新文本的类别。

二、文本表示

人类在阅读文章后, 能够根据自身的理解能力和已经掌握的知识对文章内容产生总体的认识, 但计算机并不具有人类这样的智能, 因而它也就不能轻易地“读懂”文章。因此, 文本自动分类的基本问题是如何将文本按照计算机可以“理解”的方式进行有效的表示, 从而在这个表示的基础上进行分类。向量空间模型是目前常用的文本表示模型。

向量空间模型的基本思想是以文本的特征向量来表示文本, 其中wi为第i个特征项的权重。因此, 基于向量空间模型的文本分类方法中, 第一步就是如何从文本中提取出反映文本类别的有效特征。一般可以选择字、词或词组作为文本的特征, 但由于词是信息表示和处理的基本单位, 故选取词作为特征项要优于字和词组。

在向量空间模型中, 文本集合是用词-文本形成的矩阵表示, 矩阵中的每一项表示一个词在某个文本中出现的情况:

这里aik表示词i在文本k中的权重, 因为词不是均匀分布在各个文本中的, 所以A通常为稀疏矩阵。

令fik表示词i在文本k中出现的频率, N为文本集合中文本的数目, ni为词i在文本集合中出现的总次数, 下面介绍几种计算权重的方法。

(1) 布尔权重。这是最简单的一种方法:如果词在文本中出现, 其权重就为1, 否则为0:

(2) 词频权重。该方法直接使用词频作为权重:

(3) t fi df权重。以上两种方法都没有考虑词在文本集合中出现的频率。tfidf权重对此进行了改进:

(4) t f c权重。tfidf权重没有考虑到集合中文本长度的问题, tfc权重将长度归一化因子作为计算词权重的因素:

(5) l t c权重。ltc权重与tfc权重方法稍有不同, 它不是简单的采用词频, 而是使用了词频的对数, 减小了因词频的差异所造成的影响:

(6) 熵权重。熵权重基于信息理论, 被认为是最经典的权重衡量方法, 词i在文本k中的权重按如下公式计算:

三、特征抽取

通常情况下, 构成文本的词汇数量是相当大的, 这样表示文本的向量空间的维数也会非常大, 因此需要进行维数压缩的工作。这样做的目的主要有两个:第一, 提高分类效率;第二, 提高分类精度。不同词汇对文本分类的意义是不同的:通用的、在各个类别中都普遍存在的词汇对分类的贡献小;在某一类中出现的比重大而在其他类中出现的比重小的词汇对文本分类的贡献大。因此, 我们应去除那些对分类贡献小的词汇, 筛选出每一类文本的特征项集合。下面简单介绍几种提取特征词的方法:

(1) 文本频度阈值。这是最简单的特征提取方法, 包含某词条的文本的数目被定义为该词条的文本频度。给定一文本频度阈值, 去掉文本频度小于该阈值的词条, 剩余词条即为特征词。

(2) 互信息。互信息衡量的是词和类别之间的统计独立关系, 考虑词t和类别c, 互信息定义如下:

式中p (t∧c) 表示t和c同时出现的概率;p (t) 为t出现的概率;p (c) 为c出现的概率。

(3) 信息增益。信息增益需要已知某个词在文本中是否出现及出现的情况。假设C1∪C2∪∪Ck为已知的k个类别, 对每个词w, 通过以下公式求出其IG值:

式中P (Cj) 表示Cj类文本占文本总数的比重;P (w) 表示包含词w的文本占文本总数的比重;P (Cjw) 表示Cj类中包含词w的文本占Cj类文本总数的比重;P (Cjw) 表示Cj类中不包含词w的文本占Cj类文本总数的比重。

通过计算得到每个词的IG值, 再选取适当的阈值, 只保留IG值大于此阈值的词作为向量空间的特征项, 即可达到降维的目的。

四、文本分类流程

在文本分类过程中, 首先将文本表示成以某种形式的元素 (通常用词) 表示的向量, 然后按照某种方法进行特征提取, 并用权值对提取的特征元素进行描述, 这样就可以对元素-权值表示的文本向量进行训练, 得到向量模型 (即分类器) 。在对新文本进行分类时, 同样要将待分类的文本表示成元素-权值文本向量, 然后将其与训练得到的向量模型进行比较, 最终判断其类别。图1给出了文本分类的流程。 (图1)

本文主要对文本分类中的一些相关技术进行了总结。从整体上介绍了文本分类系统的任务, 简单描述了文本分类的流程, 并对文本表示、特征抽取几个关键环节常用的技术进行了介绍。

参考文献

[1]Salton G, Wang A, Yang C.A Vector Space Model for Information Retrieval[J].Journal of the America Society for Informa-tion Science, 1975.18.

[2]宫秀军, 孙建平, 史忠植.主动贝叶斯网络分类器[J].计算机研究与发展, 2002.39.5.

文本分类检索技术在工程中的应用 第3篇

各类电子文本处理部门每天都要处理大量文本,用户每天工作中,若对一篇文本内容比较感兴趣时,如报告当前热点问题的文本,用户可能想查阅与此相关的更多文本。基于此用户需求,根据工程项目应用领域文本的特点以及用户的业务习惯,研究实现了示例检索技术[1,3],将用户感兴趣的文本作为示例文本,检索更多与该示例文本相关的文本。

但将示例检索技术应用到工程项目中时,遇到许多实际问题:不断积累形成的文本库很庞大,一一计算示例文本与每篇文本的相似度速度很慢;另一方面,提取在文本集中出现的所有词作为特征项,使特征空间的维数巨大,大大占用系统内存,向量之间相似度的计算也很慢,大大占用系统资源,并使整个系统的运行速度很慢。

另外,文本处理部门每天都会接收到大量文本,不断有新文本加入文本集,过时文本从文本集中删除,因此必须适应文本集的动态变化,使特征空间能及时反映系统文本集的真实情况,保证当天接收到新文本也能被检索到。

针对实际应用中遇到的这些问题,经过分析与实验后,提出了解决方案,设计实现了能满足工程应用需求的文本分类检索系统。

1文本分类检索系统设计

本系统采用基于向量空间模型的文本示例检索与分类检索方法:将用户提供的示例文本作为用户的查询需求;采用分类检索技术,缩小检索范围,从而大大提高检索的效率;采用特征提取技术降低特征向量维数,大大缩小了预处理时间与向量空间更新时间并减小了处理过程中对系统内存的占用,提高了检索响应速度,但对检索查全率与查准率影响不大;采用定时更新文本向量空间的方法,使系统能及时反映文本集的真实情况。

文本分类检索系统功能组成与处理流程如图1所示,由新文本预处理、更新向量空间与示例检索3部分组成。工作流程如下:

① 用户每天工作中,当接收到新文本时,用户浏览后可对其指派类别,系统自动进行后台预处理;

② 当更新特征向量时间到时,若库存文本都为新文本,则建立特征向量空间,生成每个文本的特征向量,并生成类中心向量。若已建立特征向量空间,则根据新增文本更新特征向量空间,并根据新特征向量空间生成所有文本的特征向量与类向量。这部分功能在计算服务器完成,不影响前台用户操作;

③ 用户在日常工作中对某篇文本比较感兴趣时,想查看更多与该篇文本主题相关的文本时,将该篇文本作为示例文本,执行示例检索,系统对示例文本进行预处理后,生成查询向量,计算与查询向量最相似的类,然后计算相似类中与查询向量最相似的文本,将相似度大于阈值的文本输出即为检索出的文本。

2相关技术介绍

2.1向量检索

本系统基于向量空间模型进行分类与检索。向量空间模型(Vector Space Model,VSM) 是关于文档表示的一个统计模型,可以统一描述文档表示、类别表示和查询表示过程,比较简便,而且它是目前应用比较广泛且效果较好的检索模型。

2.1.1 向量空间模型的基本概念

文本的内容特征常常用它所含有的基本语言单位(字、词及词组等)来表示,这些基本的语言单位统称为特征项。本系统中特征项为文本分词后提取的特征词。文本可以用特征项表示为D(T1,T2 ,,Tn)。对于含有n个特征项的文档,每一特征项Ti都根据其在文档中的重要程度赋予一定的权重Wi,简记为D(W1,W2,,Wn)。

给定一文档D(T1,W1;T2,W2;;Tn,Wn),将T1,T2,,Tn看成一n维坐标系中的坐标轴,W1,W2,,Wn为对应的坐标值。这样由(T1,T2 ,,Tn)分解而得到的正交特征项向量组就张成了一个文档向量空间,所有文档和文档类都可映射到此文档向量空间。称D(W1,W2,,Wn)为文档的向量表示或向量空间模型。

2.1.2 特征项的提取与降维

当提取文本集中出现的所有词作为特征项时,特征空间的维数巨大,大大占用系统内存,向量的更新与向量之间相似度的计算很慢,使整个系统的运行速度很慢,无法在工程中使用。

经过对工程应用领域中文本特征进行研究,采用了一些特征提取技术进行特征向量降维,大大较少了系统的存储空间,并提高了运行速度。

首先采用词性筛选方式对特征词进行筛选,只提取有实际意义的名词、动词、缩略词、专用词、外文词及惯用词等作为特征词,然后采用词频过滤方法,将词频小于设定阈值的特征词过滤掉。这2种做法大大降低了特征向量维数,但问题是过滤阈值设置较大时,会损失文档内容信息。

经过对应用领域的文本特征进行研究后,考虑将文本中的标题与主题词的出现频率进行加权(即在标题或主题词中出现一次相当于在正文内容中出现n次),因为实际应用中大部分文本都已标引好,有标题与主题词,而标题与主题词更能代表文本的主题。这样过滤阈值设置较大时,很少损失文档内容信息。

以上采用的特征提取方法大大减少了特征词的数量,降低了向量维数,大大缩减了预处理时间与检索时间,但不影响系统的查准率与查全率。

2.1.3 特征项的权重

不同的特征项对于文档的重要程度和区分度是不同的,因此需要对特征进行加权。本文利用特征项的统计信息,采用目前被广泛采用的,效果较好的TFIDF方法计算权重,考虑到文本长度的影响,进行归一化,采用的权重计算为:

undefined。

式中,TFik(Term Frequency)为第k个特征项在第i个文档中的出现频率;IDFk(Inverse Document Frequency)为第k个特征项的逆文档频率,一般采用IDFk=log(N/Fk);N为文档集中的文档数量;Fk为文档集中包含有第k个项的文档数。

2.1.4 文本之间的相似度

2个文档D1和D2之间的(内容)相关程度(Degree of Relevance)常常用它们之间的相似度Sim(D1,D2)来度量。当文档被表示为VSM时,可以用向量之间的夹角余弦或向量内积来计算,本系统采用夹角余弦效果较好,即用2个向量之间夹角的余弦来表示文本之间的相似度,夹角越小,距离越近,余弦越大,相似度越大,反之相似度越小,计算公式为:

simundefined。

2.2示例检索方法

示例检索就是基于文档实例进行信息检索,即基于示例文本获取用户信息需求模型,因为一篇样本文档包含了比若干关键词丰富得多的信息,能够更全面地代表用户的检索要求。示例检索要求用户以示例文本的方式提出自己的信息需求,通过提取示例文本的特征向量得到用户信息需求模型,计算示例文本特征向量与文本集中其他文本特征向量的相似度,即可找出与示例文本内容相关的文本。

2.3文本分类与分类检索

本文的文本分类采用基于向量空间模型的类中心分类法。文本集中每个文本入库前都由用户指派了类别(即有指导的分类),经过预处理后,都统一表示为特征向量,根据算术平均为每类文本集生成一个代表该类的中心向量。

在基于向量空间模型的分类检索中,文本和类别都被表示为空间中的一个点向量,文本向量和类别向量之间在空间上的距离可以采用向量间夹角的余弦来度量,与2.1.4类似,这里D2为类别特征向量。计算出文本与所有类别的相似度后,将其归入相似度值最大的类别中,即为文本分类,若要检索,则取最相似的类,类中包含的文本即为相似文本。

2.4向量空间更新方法

在建立文本向量空间一段时间之后,由于文本数量的不断增加,原始的向量空间可能已经发生偏移,据此生成的特征向量将不能反应文本的真实特征。为适应文本集的动态变化,本系统采用定时更新特征向量空间的方法。当接收到新文本时,先进行预处理,当特征向量空间更新时间到时或新文本中出现的新特征词达到一定数量时,进行特征向量空间更新,不再重新对所有文本进行特征提取,只提取新增文本中的特征项,将新文本集中包含的所有特征词进行多路归并,并与旧文本集原先的多路归并结果进行归并,得到新的特征向量空间,并更新库存所有文本的特征向量与类中心向量。更新间隔时间的配置可根据文本新增频度确定或根据新增特征词的个数确定。

3文本分类检索系统实现

3.1类图

采用面向对象的分析与设计方法,文本分类检索系统设计与实现类图如图 2所示,主要包括6个类:文件检索控制类、文本分类控制类、文本集类、向量空间类、文本类与特征向量类。下面介绍主要的类及主要类成员函数。

3.2文本检索控制类

文本检索控制类封装了文本检索各接口函数,供外部应用软件调用,主要完成新文本预处理、更新特征向量、示例检索等功能。下面分别介绍各函数。

3.2.1 新增文本预处理

提取每个新文本的正文内容、标题与主题词,进行分词,提取特征词。将每个文本提取的特征词进行快速排序,统计每个词在文本中的出现频率。

若已建立特征向量空间,根据向量空间的特征词向量及文档频率向量,计算特征词在新文本中的权重,得到新文本的特征向量。根据新文本类别标识,将新文本归类。

3.2.2 更新特征向量空间

首次执行该函数时为建立文本向量空间,以后为归并新文本特征词进行向量空间更新。

将形成特征向量空间之后新增的所有文本作为新增文本集,将该文本集中包含的所有特征词进行多路归并,并与旧文本集原先的多路归并结果进行归并,得到新的向量空间。若是首次建立向量空间,则新增文本集的多路归并结果即为最终归并结果。

基于向量空间与每个文本中特征词的词频,计算权重,生成每个文本的特征向量。

最后根据每个类中包含的所有文本权重向量,计算获得每个类中心向量。

3.2.3 示例检索

首先对示例文本进行预处理与特征向量生成,然后计算示例文本特征向量与各类中心向量的相似度,取最相似的类,再计算示例文本与相似类包含的所有文本的相似度,排序输出相似度大于指定阈值的文本。

3.3其他类

① 文本分类控制类。

文本分类控制类封装了文本分类功能,供文本检索控制类使用,主要完成文本类别标识、文本分类与类中心向量更新功能;

② 文本集类。

文本集类封装了文本集特征向量更新需要使用的各内部函数以及特征向量空间属性,供文本检索控制类使用,主要完成特征词归并、特征项提取、生成文本特征向量等功能;

③ 向量空间类。

向量空间类封装了向量空间各属性,提供给文本集类使用;

④ 文本类。

文本类为文本集类的类成员,由一系列文本列表组成文本集。文本类封装了文本预处理功能,提供给文本集类使用,主要包括文本分词、特征词提取与词频统计、特征词快速排序与生成文本特征向量等功能;

⑤ 特征向量类。

特征向量类为文本类的类成员,每一个文本对象都对应一个向量对象。特征向量类封装了特征向量计算功能,提供给文本类使用,主要包括向量赋值、向量复制与向量相似度计算等。

4结束语

本系统基于经典的向量空间模型,把对文档内容和查询要求的处理简化为向量空间中向量的运算,而权重的计算通过统计方法自动完成,基于同一模型实现文本特征表示、分类与检索,使问题的繁杂性大为减低。另外基于示例样本进行分类检索,即能满足用户的使用要求,又能适应用户的工作方式。

本系统在实际应用到工程项目中时,考虑到文本库的动态变化,定期更新特征向量空间,并且采用增量更新,提高后台处理速度,另一方面,采用各种方法提高后台处理速度,缩小前台检索响应时间,一系列解决方法的使用使该系统得以实用化。

本系统已成功用于实际工程项目的文本处理系统中,并通过了各种实验与测试,但仍有许多需要改进的方面,有待在下一步工作中完善。

参考文献

[1]刘晓丽.中文军事报告文本的示例检索[D].河北:通信测控技术研究所,2001:7-31.

[2]李彦平.文本挖掘技术在示例检索中的应用[D].河北:通信测控技术研究所,2005:7-22.

[3]刘晓丽,张佳骥.基于n-Gram的中文文本示例检索方法研究[J].无线电通信技术,2001,27(6):24-26.

[4]李彦平,张佳骥.文本聚类中的降维技术研究[J].无线电工程,2005,35(6):51-53.

[5]陈治纲,何丕廉,孙越恒,等.基于向量空间模型的文本分类系统的研究与实现[J].中文信息学报,2005,19(1):36-41.

文本分类技术 第4篇

随着互联网技术的快速发展,互联网中的文本数量巨增,对这些海量文本进行有效分类,从中采集有价值信息,成为相关人员分析的重点问题[1,2,3]。当前的文本分类方法无法较好地处理海量文本以及文本特征空间数据,不能打破计算机处理性能和内存的约束、实现文本混沌性分类。而云计算平台可向用户提供需要的运算能力和存储空间。云计算环境下的文本混沌性分类方法成为分析的热点[4,5,6]。

传统的文本分类方法存在一定的缺陷,文献[7]提出基于Map Reduce的分布式潜在语义搜索方法,采用并行化K-means算法将文档矩阵划分成不同分块,再采用潜在语义搜索方法对不同分块进行文本分类,该方法的运算量大,需要消耗大量的资源。文献[8]依据统计模型完成文本分类,但需要假设训练数据和检测数据具有相同的分布规律,但当文本数据量瞬间增加或降低时,会导致分类的文本数据丢失。文献[9]通过聚类采集可信方法以及主动学习塑造分类器的方法,从待分类文本数据汇总过滤可信正例,将剩下的文本当成可信反例,实现文本的有效分类。该方法分类精度高,但容易受到文本混沌性的干扰,存在一定的局限性。文献[10]采用非线性流形学习方法对文本降维,获取文本特征规律,但该方法获取的文本特征单一、扩展性差。

针对上述方法的弊端,提出一种优化SVM的云计算环境下文本混沌性分类方法,其Hadoop开源云计算系统,通过Map Reduce数据处理模型对文本进行分类,采用优化SVM分类方法提高海量文本混沌性分类精度。

1 云计算环境下HDFS的结构分析

云计算环境下的海量文本在进行分类时,对计算机处理性能以及内存量提出较高的要求,需要塑造云计算平台,为用户提供所需计算能力以及存储空间。因此,需要了解云计算系统的结构,再通过Map Reduce模型完成文本分类。Hadoop为开源云计算系统,是一种分布式运算框架,该系统的关键模块是HDFS和Map Reduce。Map Reduce也是一种并行简化的并行计算模型,由Map和Reduce过程组成,分别进行任务的分解和结果的汇总。采用该模型可以方便用户开发出分布式的并行程序,完成海量文本数据的计算。HDFS分布式文件系统是Hadoop分布式计算的存储基础,该系统具有高容错性,适合云计算环境下大数据集文本的分类应用。HDFS包括一个Name Node和很多个Data Node。Name Node管理云计算环境中的云数据,并将云数据反馈给客户端。Data Node对实际文本数据进行保存,完成文件的I/O处理,HDFS的结构示意图如图1所示。

1.1 Map Reduce模型逻辑架构的设计

采用Hadoop开源云计算系统中的Map Reduce模型,可以完成海量文本数据的并行运算架构,如图2所示。

Map Reduce框架包括一个Master,Reducer和多个Mapper,其实现文本混沌性分类的过程包括分割过程、Map塑造基本分类器过程以及Reduce集成过程。分割过程采用变换的抽样手段,将文本混沌数据D分割成m个子集{D1,D2,⋯,Dm};在Map塑造基本分类器过程中,各Map任务采用优化SVM分类算法在文本数据集Di中塑造基本的分类器Ci,其中在Reduce合并过程中,将m个基本分类器集合成生成分类器C。

1.2 Map Reduce模型分类过程实现

云计算平台下利用Map Reduce模型对文本进行分类处理,以提高文本分类的效率。Map Reduce执行文本分类的流程如图3所示。

图3所示的Map Reduce模型对海量文本数据集的运算包括映射(Map)过程和集成(Reduce)过程。

1.3 Map Reduce分类模型的优化设计

云计算环境下的文本训练集间无关联性,进行文本分类训练前后间相互独立,以此完成对文本分类训练过程的并行操作。采用Map Reduce数据处理模型对混沌文本进行分类过程,只进行宏观的数据分类,但为了增强文本分类精度,还需采用优化SVM算法对文本进行分类。

该算法是一种求解松弛变量以及限制因子的过程:将文本分类的二次规划不等限制过程,变换成等式变换过程,极大提高了文本分类精度,优化SVM文本混沌性分类算法示意图如图4所示。

图4处于支持向量H2下方的全部样本点都为正类,而处于支持向量H1上方的全部样本点都为负类,这种状态下的文本样本几何间隔的运算公式为:

式中:w和r用于描述待分类文本样本数据变量;M用于描述文本样本的几何间隔。

优化SVM分类方法将文本混沌分类二次规划过程中的不等限制转化为等式变换,可利用下式的数学模型描述:

式中:p表示惩罚因子,其值越高,多目标函数的损失越大;ς表示松弛变量。

将式(1)代入式(2)中,可得:

根据式(3)可得:

用矩阵以及向量的形式描述运算过程:

式中:Q表示对角线上的元素为1的m乘m阶的对角矩阵;D用于描述m乘m阶测试集矩阵;e用于描述单位向量;w表示n维列向量;w′表示n维行向量。分析式(5)可知,云计算环境下的文本混沌性分类过程可转化成求极值过程,对于文本分类训练集的分类器中的变量为w和r,可通过式(5)计算这两个变量:

设置I表示原始为1的单位矩阵,则有QQ=I,对式(5)进行求解可得:

设置:

将式(8)代入式(7)中,可得:

根据上述分析,最终文本混沌性分类过程即是对式(9)进行求解的过程。该过程极大提高了文本混沌性分类精度。

1.4 优化分类的实现过程

进行文本混沌性分类时要编写Map函数和Reduce函数,其中:

Map函数的输入是in_view和in_foucs,用于描该函数待操作的初始数据;该函数的输出结果为(view,foucs),依据view值对这些结果进行分类,将分类结果作为Reduce函数的输入。Reduce函数对具有一致view的foucs值进行分类,输出结果(view,final_foucs)。Map函数可以采用默认的File Input Format类分块,还可采用Multi File Input Format类设置符合用户需求的输入分块。

(1)Map函数需要定义输入输出的数据格式,该函数的详细规划内容为:

文本预处理过程Map函数伪代码:

(2)Reduce函数在全部Map函数运行后,由Master节点进行调控,详细的规划内容为文本预处理过程Reduce函数伪代码:

2 实验结果与分析

仿真实验在6台计算机构成的集群上设置Hadoop模拟云计算平台,通过该平台检测本文文本分类方法的性能优劣。将其中1台计算机当成Name Node以及Job Tracker服务主节点,其他5台计算机当成Date Node和Task Tracker服务从节点。根据Hadoop项目标准部署手段设置Hadoop 0.2版本的集群,如图5所示。

2.1 不同方法的分类时间对比

设置云计算平台中map.tasks.maximum和reduce.tasks.maximum的值为2,确保每个节点上执行两个Map过程或两个Reduce过程。本文数据集来自百度实验室资料库,大小为195 MB。其中有娱乐、房产、时尚、体育、影视、教育、文化、政务8种类型文档,不同类别文档数为1 850。采用Imdict-chinese-analyzer分词工具,将实验语料库中的文本依据3∶1的比例划分成训练集合检测集,并对非线性流形分类方法和本文方法在云计算平台上的文本分类效果进行对比实验。两种方法对于不同数量节点的分类时间如表1所示。

ms

分析表1可得,本文方法对同一实验文本进行分类过程汇总,分类时间远远低于非线性流形分类方法,因为本文方法将处于两个支持向量间的样本,也就是对模糊性的样本点的运算进行忽略,极大提高文本分类效率。

2.2 分类测试混淆矩阵建立

表2为本文方法测试输出的混淆矩阵的详细分类结果,并提供了分类的准确率和召回率。

分析表2可知,本文方法的分类总识别率是86.3%。其中,文化类的文本分类精度最低,被误判成教育类;其他类别文本的分类精度都较高。说明本文方法取得了较好的分类效果。

2.3 不同算法下小数据量与大数据量分类时间性能消耗比对

为了验证云计算平台下本文方法文本分类性能,实验检测本文方法和非线性流形分类方法小数量和大数据量两组数据的分类情况,结果分别如图6和图7所示。

分析图6可知,对小数据量文本进行分类时,本文方法的分类略低于非线性流形分类方法,但随着数据量的增加,两种方法间的差距不断增大,因为在数据量较低情况下,总体文本数据分类的预操作消耗时间低,Map节点和Reduce节点间的通信和调控消耗时间低,两种方法都可实现文本的高速分类,但是随着数据量的增加,本文方法在处于大数据文本分类上的优势逐渐显现出来。

分析图7可知,在对大数据量文本进行分类时,随着文本量的大幅度增加,非线性流形分类方法的分类时间消耗逐渐增加,几乎无法完成运算任务;而本文方法的分类时间远远低于非线性流形分类方法,具有较高的处理效率。

仿真实验证明,随着文本输入的逐渐增加,本文方法的文本分类效果不断增强,对云计算环境下的大数据量的输入文本具有更好的分类效果。

3 结论

本文提出一种优化SVM的云计算环境下文本混沌性分类方法,并通过仿真实验证明,所设计分类方法具有更高的处理效率和精度,可以对海量文本数据准确的分类。

参考文献

[1]刘露,彭涛,左万利,等.一种基于聚类的PU主动文本分类方法[J].软件学报,2013(11):2571-2583.

[2]庄福振,罗平,何清,等.迁移学习研究进展[J].软件学报,2015(1):26-39.

[3]Fengmei W,Jianpei Z,Yan C,et al.FSFP:Transfer learning from long texts to the short[J].Appl.Math,2014,8(4):2033-2040.

[4]富震.基于SVM主动学习技术的PU文本分类[J].计算技术与自动化,2014(1):127-131.

[5]张倩,李明,王雪松,等.一种面向多源域的实例迁移学习[J].自动化学报,2014(6):1176-1183.

[6]贺飞艳,何炎祥,刘楠,等.面向微博短文本的细粒度情感特征抽取方法[J].北京大学学报(自然科学版),2014(1):48-54.

[7]刘智,杨宗凱,刘三女牙,等.采用动态特征选择的中文情感识别研究阴[J].小型微型计算机系统,2014,35(2):358-364.

[8]WEI F M,ZHANG J P,CHU Y,et al.FSFP:Transfer learning from long texts to the short[J].Applied mathematics&information sciences,2014,8(4):2033-2044.

[9]SAMANTA S,TIRUMARAI S A,DAS S.Cross-domain clustering performed by transfer of knowledge across domains[C]//Proceedings of the 2013 IEEE 4th National Conf.on Computer Vision,Pattern Recognition,Image Processing and Graphics(NCVPRIPG).[S.l.]:IEEE,2013:1-4.

文本分类及分类算法研究综述 第5篇

随着互联网在社会中的大规模应用, 网络上的信息资源正在以指数级爆炸增长, Web已经成为一个规模十分庞大的信息资源库。在各种形式的信息中, 非结构化的文本信息仍然是十分重要的信息资源之一。在海量的文本信息中, 获取最有效的信息资源是信息处理的基础, 而文本分类能更好地帮助人们组织管理好海量的文本信息, 快速准确地获取所需信息, 实现个性化的信息。文本分类在众多领域中均有应用, 常见的应用包括:邮件分类、网页分类、文本索引、自动文摘、信息检索、信息推送、数字图书馆以及学习系统等。

2 文本分类

2.1 文本分类的发展进程

文本分类是指根据预先定义的主题类别, 按照一定的规则将文档集合中未知类别的文本自动确定一个或几个类别的过程[1]。回顾文本分类的相关研究, 可追溯到20世纪60年代, 那个时期Maron开创性的提出了概率索引模型, 采用了贝叶斯公式来进行文本分类[2]。到了20世纪80年代, 主要通过各领域专家提供的知识形成规则, 手工建立文本分类器, 在这个时期采用的文本自动分类方法主要是基于传统的知识工程。直到20世纪90年代, 以机器学习和统计方法为基础的文本分类技术逐步发展起来并不断完善了人工建立分类器的不足, 使得文本分类更加准确、有效。目前, 文本分类也已经开始应用于对国内中文文本的研究, 在Web文档自动分类、自动文摘、数字图书馆等诸多领域开始了应用。

2.2 文本分类的一般流程

文本分类是根据已被标注的训练文本集, 通过特征选择、特征提取等方法得到特征项或者根据文本表示方法通过训练得到文本类别间的关系模型即文本分类器, 然后用训练得到的关系模型对测试文本集进行文本表示得到文本分类结果的一个有指导的学习过程。文本分类的过程可分为训练和分类两个过程, 大致分为文本表示、分类器构建和效果评估三个步骤。文本分类的一般流程如图1所示:

2.3 文本的分类

在具体的研究中, 根据文档的特征不同可以将文本按不同的方式进行分类, 如按文本标题、文本内容、情感倾向性、文本风格等方式进行分类。

1) 按文本标题分类

按文本标题分类顾名思义即根据文本的标题信息进行文本分类的一种方法。标题中蕴含了文本的主要信息, 是对文本内容的高度概括, 并且标题有着简洁、语句简单等特征, 使得对文本标题的分析更准确有效。葛文镇等 (2016) [3]提出了基于层级类别信息的双向特征选择算法, 并实现了标题分类, 能有效提高分类效率。杨敏, 谷俊 (2012) [4]构建了基于混合特征矩阵的支持向量机算法对中文书目进行分类的书目自动分类系统。缪建明等 (2008) [5]通过标题信息蕴含的领域信息激活对应的HNC领域, 对文本进行了自动分类, 测试速度、分类的准确度有了明显的提升。

2) 按文本内容分类

按文本内容进行分类, 是最常见的一种分类, 其关注点在于能区别不同文本内容的关键性词语。按文本内容分类是对根据文档主题进行自动分类, 在教育学、法学等领域研究中都十分有用。吴昊 (2009) [6]阐述了基于Web信息挖掘的英语阅读自动选篇的分类研究方法, 将按文本内容分类应用于教育研究中。在法学研究中, 熊小梅等 (2007) [7]基于LSA的二次降维法以及改进的互信息特征提取通过文本分类对中文法律案情文本进行自动分流, 加快了分类系统的处理速度, 减轻工作人员的负担。

3) 按情感倾向性分类

按情感倾向性分类是指根据文档中作者对所表达的事物所持有的观点、态度, 如正面、负面、积极、消极、中性等。在研究中也被称作情感分析、观点挖掘或是文本意见挖掘等。按情感倾向性的分类中, 情感特征的选择与抽取对分类的性能有比较大的影响。目前的文本情感分析在网络舆情分析、政策文件分析、问卷调查等方面应用较多。朱建平等 (2016) [8]结合词云、关联规则、文本倾向性分析等技术对中国房地产网络舆情做了实证分析与研究并给出了相关的政策建议。邓雪琳 (2015) [9]采用文本分析法, 使用文本挖掘软件对政府文件中的关键词等做计量, 测量了中国政府职能的转变并给出了中国政府职能的转变逻辑和发展趋向。张珍珍, 李君轶等 (2014) [10]主要采用问卷调查与网络评论的方式获取游客对旅游的形象感知数据, 通过文本挖掘对比分析研究两种途径的旅游形象问题。夏火松等 (2013) [11]通过对商品具体属性情感倾向的分析将情感分类分为初分类和细分类两个过程, 构建的细分类模型缩短了购买决策的时间, 降低了决策的复杂度, 并经过特征算法的测试发现情感细分类中互信息达到了更高的准确度。

4) 按文本风格分类

按文本风格分类主要是指在文本语言特色方面的分类, 是对文本作者在词语使用、句式使用等方面的特色进行分类。针对这种分类方式可以应用于文本作者身份识别、文学作品流派等的研究中。施建军 (2011) [12]运用支持向量机技术对《红楼梦》进行了分类研究, 更有效地区分了古典文学作品的作者。年洪东, 陈小荷等 (2010) [13]利用支持向量机统计机器学习模型对中国现当代文学作品做了作者身份识别研究。张云良等 (2009) [14]利用向量空间模型及混合句类分解等技术构建了作者写作风格分类器研究了《红楼梦》的作者问题。

3 常见文本分类算法

分类是数据挖掘中的重要方法之一, 在文本分类中常见的算法有朴素贝叶斯算法、支持向量机、K近邻算法、Rocchio算法等。朴素贝叶斯算法是在文档自动分类中应用概率模型的一种简单而有效的方法, 关注的是文档属于某类别的概率。支持向量机是通过构造一个分类超平面, 使得分类间隔达到最大, 最大限度地分开两类训练样本的一种方法。K近邻算法是为待分类文本找出最为相似的K个样本, 统计这些样本所属的类别, 待分类文本的类别就是包含样本最多的类别。Rocchio算法是对一个类别里的所有样本文档各项计算平均值, 得到一个称为质心的新向量, 若需要对新文档作判断时就通过计算距离比较新文档和质心的相似程度。下面主要对朴素贝叶斯算法、支持向量机、K近邻算法、Rocchio算法等四种算法进行比较分析, 见表1所示。

4 结束语

文本分类算法研究 第6篇

文本分类是指在带有类别标签的文本集合中, 根据每个类别的文本子集合的共同特点, 找出一个分类模型, 以便在后续过程中将未标识文本映射到已有类别的过程。文本分类是一种文本处理手段, 能较好地解决大量文档信息归类的问题进而应用到很多场景中, 如基于受控词典的文档自动索引、文档过滤、元数据的自动生成、词义辨别、资源层次分类等, 同时, 它也是很多信息管理任务的重要组成部分[1]。

自动分类的研究可以追溯到上世纪50年代;上世纪80年代末之前, 自动分类问题大多采用知识工程的方法, 即利用专家规则来进行分类;上世纪90年代以后, 统计方法和机器学习的方法被引入到文本自动分类中, 取得了丰硕的成果并逐渐取代了知识工程方法。

文本分类的一般流程为文本预处理、特征抽取、构建分类器和分类结果评价。目前, 针对文本分类的算法主要集中在特征抽取和分类器构建这两个方面。本文主要介绍文本分类中的几种常用算法。对于分类算法的分类方式目前没有统一的结论[1,2], 鉴于各分类算法对文本语义信息的利用程度不同, 可以考虑将其分为基于词形的文本分类和基于语义的文本分类两大类别。

1 基于词形的文本分类

基于词形的方法倾向于将文本视为无意义无联系的字或词的集合, 几乎没有利用文本的语义信息。

1.1 贝叶斯分类

贝叶斯分类算法以贝叶斯理论为基础, 是一种利用先验概率与条件概率进行文本分类的算法, 具有实现简单、准确率高、速度快的特点。贝叶斯算法基于独立性假设, 即一个属性对给定类的影响独立于其它属性的值。独立性假设的约束过于强, 在实际应用中经常是不成立的, 因此在很多情况下其分类准确率并不能保证[3]。

1.2 决策树

本文将决策树视为一种基于规则学习的算法, 其目的是学习一系列分类规则, 即属性与类别的关系。在决策树算法中, 分类规则可用从根节点到任一叶节点的路径表示, 具有很强的可理解性和可用性。该算法涉及两个核心问题:决策树的建立和决策树的剪枝。

常见决策树算法包括CART、ID3、C4.5、CHAID等。其中影响最大的是ID3[4], 该算法由Quinlan于1986年提出, 算法的理论清晰、方法简单, 但只对较小的数据集有效, 且对噪声敏感, 在测试属性选择时, 它倾向于选择取值较多的属性。C4.5算法是对ID3的改进, 主要解决了ID3算法选择偏向取值较多的属性问题。

1.3 k最近邻

k最近邻算法是一种基于实例的消极学习算法。该算法的思想是:统计一个样本在特征空间中的k个最相似的样本类别, 进而采用加权投票的方式确定待分类样本的类别。KNN分类器只存储实例, 对于每个未知输入都要遍历训练样本, 因而在应对大量待分类数据时其算法效率很低。

1.4 Rocchio算法

Rocchio算法是20世纪70年代左右在Salton的SMART系统中引入并广泛流传的一种分类算法, 它通过构造类别的中心向量及相应类域的方式进行分类。该方法的优点是简单且直观, 缺点是对线性不可分的数据及含噪声的数据分类效果差。

1.5 支持向量机

支持向量机 (Support Vector Machines, SVM) 方法是由V.Vapnik与其领导的贝尔实验室小组一起开发出来的一种机器学习技术。SVM是一种线性分类器, 采用结构风险最小化原则, 其特点是能够同时最小化经验误差且最大化几何边缘区, 最终将分类问题转化为求解最优决策超平面问题。该方法属于研究小样本情况下机器学习规律的统计学习理论范畴, 对小样本情况具有较好的适应性, 克服了“过学习”现象, 具有相对优良的性能指标。影响SVM的分类性能最重要的两个因素是误差惩罚参数和核函数。

1.6 神经网络

神经网络是对神经系统的一种模拟。在文本分类中, 神经网络由一组神经元组成, 其输入单元通常代表词项, 输出单元表示类别或类别兴趣度, 神经元的连接权重表示条件依赖关系。对于文本分类, 文档向量权重通常作为输入。其训练通常用BP算法来进行, 时间开销一般很大。

最简单的用于文本分类的神经网络为感知器。感知器实际上是一种线性分类器, 它将分类问题转化为对错误分类的修正问题, 通过对所有训练实例进行多次迭代和更新的方式来使错误分类的数量低于某一阈值, 从而求得各个输入分量连接到感知机的权量。

最近, 一种新兴的多层神经网络学习算法深度学习引起了机器学习领域的广泛关注。深度学习算法通过组合低层特征形成更加抽象的高层表示属性类别或特征, 以发现数据的分布式特征表示。目前, 深度学习已经在计算机视觉、语音识别等领域获得一定程度的应用, 但在自然语言处理方面尚未获得系统性突破。

1.7 线性最小平方拟合

线性最小平方拟合是一种线性模型的参数估计方法, 它将分类问题转为拟合问题。训练数据用输入/输出向量对表示, 其中输入向量用传统向量空间模型表示的文档 (词和权重) , 输出向量则是文档对应的分类 (带有二元权重) 。通过求解这些向量对的线性最小平方拟合, 可以得到一个单词-分类的回归系数矩阵[5]。

1.8 N-gram方法

N-gram是一种依赖于上下文环境的字 (词) 的概率分布的统计语言模型。该方法将文本视为N元字 (词) 链的集合而非“词袋”, 并由马尔可夫链模型来表征。其特征选取方式为:将文本内容视为单词序列并进行大小为N的滑动窗口操作, 形成新的长度为N的单词片断序列, 每个N元单词片断即为一个特征。

由于中英文的不同, 在设计基于N元语言模型的中文文本分类器时, 首要问题是选择基于字级还是基于词级的N元语言模型, 其次是选取合适的N值。基于字级的N-gram算法对拼写错误的容错能力强且不需要词典和规则, 但因其需要选择较大的N值, 算法复杂度较高;而词的表达能力要强于字, 所以基于词级的N-gram可以选取较小的N值, 算法效率相对较高。

1.9 多分类器组合

多分类器组合是一种用来提高弱分类算法准确度的多算法集成框架, 它将强分类器的获取问题转化为多个弱分类器的融合问题, 其核心步骤是基分类器的生成与组合策略的选择。

多分类器组合的思想来源于Valiant在1984年提出的PAC (Probably Approximately Correct) 模型。PAC模型将识别准确率仅比随机猜测略高的算法称为弱学习算法, 而识别准确率很高且能在多项式时间内完成的算法则被称为强学习算法。同时, Valiant也提出了弱学习算法和强学习算法的等价性问题, 即将弱学习算法提升为强学习算法。1990年, Schapire构造出一种多项式算法, 对该问题做了肯定的证明, 这就是经典的Boosting算法[6]。但Boosting算法需要事先知道弱学习算法识别准确率的下限, 因而其在实际应用上存在一定困难。针对这一问题, Freund和Schapire于1995年提出了AdaBoost (Adaptive Boosting) 算法[7], 该算法在实现过程中不需要任何关于弱学习算法的先验知识。

多分类器组合包含两个核心步骤:一个是基分类器的生成阶段, 即如何生成多个不同的基分类器;另外一个是组合阶段, 即如何使用基分类器来对测试实例进行分类, 综合形成一个最终的分类结果。

2 基于语义语法的文本分类

基于语义语法的方法将文本视为有意义有联系的概念集合, 利用知识工程方面的部分内容对特征向量做了不同程度的优化, 从而相对充分地利用了文本的语义信息。

2.1 基于概念的模型

基于概念的模型假设文本是由意义相关的概念串联起来的。与基于词形的方法不同, 基于概念的模型研究是文档中概念的分布, 其思想是利用知识库构造概念空间, 进而从语义层面对文本进行分类。

常用的知识库有WordNet、Cyc、ConceptNet等, 其中WordNet的应用最广泛。WordNet是美国Princeton大学研发的一个英语词汇语义知识库, 或者概念知识库, 它是语义学研究最权威的知识库之一。WordNet中最基本的单位是概念, 概念在WordNet里被抽象为一个同义词集合。因此, WordNet不仅是一部词典, 还是一个同义词词林。

本体是知识库的一种重要表现形式。所谓本体, 是指某一领域的概念化描述, 包括概念及其关系, 在应用中, 本体是结构化的概念集[8]。基于词形的分类器其进化过程主要通过增量学习的方式, 而基于本体的分类模型除了增量学习的方式外, 还可以通过本体进化的方式实现分类器的进化。

文本分类中对知识库的应用主要集中在以下几个方面:①获取分类知识, 分类问题中的类别体系是预先确定的, 而知识库最基本的组织形式正是分类;②识别同义词, 利用词义的等价表达可以简化文本向量空间, 而同义词属于知识范畴;③语义消歧, 在知识层面利用上下文信息确定多义词的准确概念。

2.2 基于主题的模型

在主题模型中, 主题表示一个概念, 其表现形式为一系列相关的单词构成的特征向量。主题模型是从生成的角度看待文本的, 即一篇文档通过一定概率选择某个主题, 又在这个主题中以一定概率选择某个词语。因此, 文本-词汇矩阵可以表示为文本-主题矩阵与主题-词汇矩阵的乘积。主题模型主要分为PLSA (Probabilistic Latent Semantic Analysis) 和LDA (Latent Dirichlet Allocation) 两种。

2.3 基于语法的模型

基于主题的模型是以文档为单位的粗粒度的识别, 而基于语法的模型则是以句子为单位的细粒度的识别。它将文档看作一系列含有中心词的句子集合, 通过词性标注来识别中心词, 因而词性标注与中心词识别是该类算法的核心[9]。

3 结语

分类算法的一般规律是利用训练集的数据特征, 在假设空间中找出或者构建出一个模型或假设, 使其计算结果尽可能地接近文档的真实分类。所构建或学习的模型或假设可以用多种形式表示, 如分类规则、决策树、数学公式或神经网络。在文本分类器的实际应用中往往要面对各种各样的数据, 比如小语种文本、短文本、海量文本、邮件、文献、html文档等。这些数据或者特征提取难度大, 或者对分类器效率要求高, 或者存在语义信息之外的链接和结构信息。因此, 不存在一款通用分类器可以对各种数据都达到很好的分类效果。事实上, 绝大多数应用于实践的分类器都是在常见分类器的基础上针对已有数据特点进行了某种程度的改进。此外, 一些在其它领域已获得成熟运用的方法, 如模糊集、粗糙集、蚁群等, 也在逐渐被用于文本分类问题中。

在算法改进方面有几个相对重要的可选方向, 如特征降维、同义词多义词处理、特征向量的平滑技术、针对特定数据特点的优化等。

参考文献

[1]FABRIZIO SEBASTIANI.Machine learning in automated text categorization[J].ACM Computing Surveys, 2002, 34 (1) :1-47.

[2]WILLIAM W COHEN, YORAM SINGER.Context-sensitive learning methods for text categorization[J].ACM transactions on information systems, 1999, 17 (2) :141-173.

[3]EITAN GREENSHTEIN, JUNYONG PARK.Application of non parametric empirical bayes estimation to high dimensional classification[J].Journal of Machine Learning Research, 2009 (10) :1687-1704.

[4]QUINLAN R.Induction of decision trees[J].Machine Learning, 1986 (1) :81-106.

[5]YANG Y, CHUTE C G.An example-based mapping method for text categorization and retrieval[J].ACM Trans Inform System, 1994, 12 (3) :252-277.

[6]SCHAPIRE R E.The strength of weak learnability[J].Machine Learning, 1990 (5) :197-227.

[7]FREUND Y, SCHAPIRE R E.A decision-theoretic generalization of online learning and an application to Boosting[J].Journal of Computer and System Sciences, 1997, 55 (1) :119-139.

[8]ROBERT NECHES, RICHARD E.FIKES, TIM FININ, et al.Enabling technology for knowledge sharing[J].AI Magazine, 1991, 12 (3) :36-56.

文本分类及算法综述 第7篇

1 文本分类的一般过程

文本分类是一个有指导的学习过程, 它根据一个已经被标注的训练文本集合, 找到文本属性 (特征) 和文本类别之间的关系模型 (分类器) , 然后利用这种学习得到的关系模型对新的文本进行类别判[1]。文本分类的过程总体可划分为训练和分类两部分。训练的目的是通过新本和类别之间的联系构造分类模型, 使其用于分类。分类过程是跟据训练结果对未知文本进行分类, 给定类别标识的过程。具体流程图如图1:

2 文本预处理

文本预处理是从文本中提取关键词来表示文本的处理过程, 它的主要任务是进行中文分词和去停用词。不同于英文中词与词之间是靠空格隔开, 中文文本的自然语言中词与词间没有明显的切分标志, 所以首先要对文本进行分词处理。中文分词方法主要有基于字符串匹配的方法、基于理解的方法和基于统计的方法[2]。

基于字符串匹配的分词方法是按照一定的策略将待分析的字符串与一个机器词典中的词条进行匹配, 若从词典中找到某个字符串, 则匹配成功。依据不同的扫描方向, 可分为正向匹配和逆向匹配;依据不同长度优先匹配的情况, 可分为最大匹配和最小匹配。

基于理解的分词方法是通过让计算机仿照人对句子的理解方式, 从而达到识别词的效果。其基本思想就是在分词的同时进行句法和语义分析, 利用句法信息和语义信息来处理歧义现象。

基于统计的分词方法是测试字与字相邻共现的频率, 并把它作为成词的可信度评价标准。具体做法是先统计语料库中相邻共现的各个字的组合频度, 计算它们的互信息。因为互信息体现了汉字之间结合关系的关联程度, 当关联程度高于某一个阈值时, 便认为这些字组可能构了一个词。

目前歧义词和新词是中文分词面临的最大困难所在。前者要解决自然语言理解的问题, 根据上下文环境, 在不同切分结果中选择最优解:后者要解决词典中未收录词 (如人名、地名、机构名等) 的识别[2]。

停用词通常指在各类文本中都频繁出现, 因而被认为带有很少的有助于分类任何信息的代词、介词、连词等高频词。通过构造一个停用表, 在特征提取过程中删除停用表中出现的特征词。

3 文本的表示

自然语言文本是非结构化的杂乱无章的数据, 须将它们转换为结构化的计算机可识别处理的信息, 即对文本进行形式化处理, 结果称为文本表示。目前通常采用的文本表示模型有概率模型、潜在语义索引模型和空间向量模型[3]。其中, 向量空间模型是应用最广的文本表示模型。

向量空间模型 (Vector Space Model, VSM) 是Salton等人在20世纪60年代提出的, 初期在信息检索领域应用, 现在已成为文本分类中最广泛采用的一种文本表示。向量空间模型基于如下假设:文章中词条出现的顺序无关紧要, 它们之间是相互独立的而忽略其依赖性, 把文本看作一系列无序词条的集合。在该模型中, 每篇文本表示为特征空间的一个向量, 向量中的每一维对应于文本中的一个词条, 每一个词条称为一个特征项, 每一个特征词的值为该向量维对应的特征在文本集中的权值。其数学描述如下:

假设特征词集合为T={t1, t2, t3, t4, tn) , 文本集合为D={d1, d2, d3, d4, dm) , 文档dj用一个n向量表示为dj= (wj1, wj2, , wjn) , 每一维对应特征词集合中的一个特征项, 其值通过权值计算公式wjk (1kn) 给出。权值一般是特征词在文本集中出现频率的函数。

考虑到词语与词语之间是有语义上的联系的, 图模型[4]利用图来表示文本。图中的节点表示文本中的词语, 边表示词语之间的相互关系。另外, 也有把概念和概念距离引入向量空间模型, 从语义, 概念的角度出发, 以概念作为文本的特征项, 建立基于概念的文本表示模型[5], 解决同义词和多义词的问题而实现对向量空间模型的改进。

4 特征项的选择和特征权重

通常原始特征空间维数非常高, 且存在大量冗余的特征, 因此需要进行特征降维。特征选择是特征降维中的其中一类, 它的基本思路:根据某种评价函数独立地对每个原始特征项进行评分, 然后按分值的高低排序, 从中选取若干个分值最高的特征项, 或者预先设定一个阈值, 把度量值小于阈值特征过滤掉, 剩下的候选特征作为结果的特征子集。

文本分类中常用的特征选择方法有:文档频次、互信息量、信息增益、χ²统计量 (CHI) 等方法[6]。

4.1 文档频率 (DF:Document Frequency)

文档频率指训练集中包含该特征的文本总数。所谓包含特征的文本是指这个特征在该文本中是否出现, 而忽略其出现次数。采用文档频率基于如下假设:文档频率值低于某个阈值的词条是低频词, 可认为它们不包含有类别信息 (不具有分类的能力) , 将这样的词条从原始特征空间中除去, 能够降低特征空间的维数从而提高分类精度。

文档频率是最简单的特征选择技术, 由于其具有相对于训练语集规模的线性计算复杂度, 它能够容易地被用于大规模语料统计。但是在信息抽取研究中却通常认为DF值低的词条相对于DF值高的词条具有较多的信息量, 将这些词条从特征空间中移除会降低分类器的准确率[5]。

4.2 信息增益 (IG:Information Gain)

信息增益在机器学习领域被广泛使用, 它通过特征词在文本中出现和不出现前后的信息量之差来推断该特征词所带的信息量。采用如下公式:

其中P (t) 表示样本集中包含词t的文本的概率, P (ci) 表示类文本在样本集中出现的概率, P (ci|t) 表示文本包含词t时属于ci类的条件概率, 表示文本不包含词t时属于ci类的条件概率, 表示样本集中不包含词t的文本的概率。

4.3 互信息 (MI:Mutual Information)

互信息是信息论中的一个重要概念, 它用来衡量一个消息中两个信号之间的相互依赖程度。在文本分类中, 互信息是用来衡量特征词和类别之间的共现关系, 其类别ci和特征词t之间的互信息定义如下:

其中p (t, ci) 表示特征t与类别ci共现的概率, p (t) 表示特征t在整个训练集中出现的文本频率, p (ci) 表示类别ci在训练集中出现的概率。其I (t, ci) 表示特征项t与类别ci的关联程度。它越大说明t与类别ci的联系越紧密。

4.4 卡方统计法 (CHI)

卡方统计也用于表征两个变量的相关性, 与互信息相比, 它同时考虑了特征在某类文本中出现和不出现时的情况。卡方值越大, 它与该类的相关性就越大, 携带的类别信息也就越多。

4.5 特征权重的计算

在文本中, 每一个特征项赋予一个权重, 表示这一特征项在该文本中的重要程度。特征权值一般都是以特征项的频率为基础进行计算的。特征权重 (term weight) 的计算公式很多, 假定特征tk在文本dj中的词频为fjk、, 特征权值为wjk, N表示文本集中的文本数, M表示所有文档的词汇量, nk表示特征tk在整个文档集中的出现频率, 则常见的权值计算方法包括:

1) 布尔权值法

如果某个词条在一篇文本中出现, 则将其权值wjk定义为1, 否则定义为0。

2) 词频权值法

词频权值法是根据特征词在文本中的出现频率来衡量其重要程度, 即wjk=fjk

3) TF/IDF权值法

TF/IDF (Term Frequency/Inverse Document Frequency) 方法是应用最为广泛的一种权值法, 其中TF表示特征词在某文本中的出现频率, IDF表示特征词在整个文本集中的出现频率。文本k中词i的TF/IDF权值与其在该文本中的出现频率成正比, 而与其在整个文本集中的出现频率成反比, 用公式表示为:

4) TFC权值法

TF/IDF权值法虽然最常用, 但它没有考虑文本长度对权值的影响。TFC权值法在TF/IDF方法的基础上利用文本长度对其进行规范化。

5 文本分类算法

5.1 朴素贝叶斯分类算

朴素贝叶斯分类算法 (Naïve Bayes) 是一种典型的概率模型算法, 根据贝叶斯公式作, 算出文本属于某特定类别的概率。它的基本思路是计算文本属于类别的概率, 该类别概率等于文本中每一个特征词属于类别的概率的综合表达式, 而每个词属于该类别的概率又在一定程度上可以用这个词在该类别训练文本中出现的次数 (词频信息) 来粗略估计。

假定文本集中每一个样本可用一个n维特征向量dj={tj1, tj2, tj3, tj4, tjk) 表示, 基于贝叶斯理论类计算待定新文本dj的后验概率用p (ci|dj) 表示:

其中p (dj) 对计算结果与影响, 因此可以不计算。贝叶斯方法的基本假设是词项之间的独立性, 于是:

类别的先验概率p (ci) 和条件概率p (tjk|ci) 在文本训练集用下面的公式来估算:

其中, ni表示属于类ci训练文本数目;N表示训练文本总数;nik表示类ci中出现特征词tk的文本数目;r表示固定参数。

朴素贝叶斯算法优点是逻辑简单, 易实现, 分类过程中时空开销小, 算法稳定。它的不足处是它基于文本中各个特征词之间是相互独立的, 其中一词的出现不受另一词的影响, 但是显然不对。

5.2 Rocchio算法

Rocchio算法又称类中心最近距离判别算法, 最早由Hull在1994年引进文本分类, 是基于向量空间模型和最小距离的算法。它的基本思路是用简单的算术平均为每类中的训练集生成一个代表该类向量的中心向量, 然后计算测试新向量与每类中心向量之间的相识度, 最后判断文本属于与它最相似的类。

向量相似性的度量一般常采用:

1) 夹角余弦:

夹角余弦表示一篇文本相对于另一篇文本的相似度。相似度越大, 说明两篇文本相关程度越高, 反之, 相关程度越低

2) 向量内积:

3) 欧氏距离:

距离越小, 两篇文本的相关程度就越高, 反之, 相关程度越低。

在Rocchio算法中, 训练过程是为了生成所有类别的中心向量, 而分类阶段中, 系统采用最近距离判别法把文本分配到与其最相似的类别中从而判别文本的类别。所以, 如果类间距离比较大而类内距离比较小的类别分布情况, 此方法能达到较好的分类效果, 反之, 类中心最小距离算法效果比较差。但由于其计算简单、迅速、容易实现, 所以它通常用来实现衡量分类系统性能的基准系统, 而很少采用这种算法解决具体的分类问题。

5.3 k最近邻算法

K最近邻算法 (KNN) 最初由Cover和Hart于1968年提出[7], 是一种基于实例的文本分类方法, 将文本转化为向量空间模型。其基本思路是在给待定新文本后, 计算出训练文本集中与待定文本距离最近 (最相似) 的k篇文本, 依据这k篇文本所属的类别判断新文本所属的类别。

可以用夹角余弦、向量内积或欧氏距离计算出K篇最相似文本。而决策规则是统计K篇训练样本中属于每一类的文本数, 最多文本数的类即为待分类文本的类。但考虑到样本平衡问题时, 目前应用较广的是SWF决策规则, 该决策规则是对上面DVF规则的改进, 根据K个近邻与待分类文本的相似度之和来加权每个近邻文本对分类的贡献, 这样可以减少分布不均匀对分类器的影响。SWF决策规则数学描述:

其中, SCORE (d, ci) 为文本d属于类ci的分值;Sim (d, dj) 为d与dj之间的相似度;当y (dj, ci) 如果属于类别ci时, 则y (dj, ci) =1, 当y (dj, ci) 不属于类别ci, 则y (dj, ci) =0, ;bi为阈值, 它可在集上通过训练来得到。

KNN的不足处之一是判断一篇新文本的类别时, 需要把它与现存所用训练文本都比较一遍。另一个不足处是当样本不平衡时, 即如果一个类的样本容量很大而其它类很小, 可能导致输入一个新样本时, 该样本的K个邻居中大容量样本占多数。

5.4 决策树

决策树 (Decision Tree) 基本思路是建立一个树形结构, 其中每个节点表示特征, 从节点引出的每个分支为在该特征上的测试输出, 而每个叶节点表示类别[8]。大致需要下面几个步骤:

1) 根据信息增益法在特征集中选取信息增益最高特征项作为当前节点的测试属性;

3) 按测试属性 (特征权重) 不同取值建立分支;

3) 对各子集递归进行以上两步操作建立决策树节点的分支, 直到所有子集仅包含同一类别的数据为止;

4) 对决策树进行剪枝, 生成更紧凑的决策树。

决策树算法的核心问题是选取测试属性和决策树的剪枝。除了常用的信息增益法, 选择测试属性的依据还有熵、距离度量、G统计、卡方统计和相关度等度量方法。从决策树的根节点到每个叶节点的每一条路径形成类别归属初步规则, 但其中一些规则准确率较低, 需要对此决策树进行剪枝。

决策树实际上是一种基于规则的分类器, 其含义明确、容易理解, 因此它适合采用二值形式的文本描述方法。但当文本集较大时, 规则库会变得非常大和数据敏感性增强会容易造成过分适应问题。另外, 在文本分类中, 与其它方法相比基于规则的分类器性能相对较弱。

5.5 人工神经网络

人工神经网络 (Artificial Neural Networks) 是一种按照人脑的组织和活动原理而构造的一种数据驱动型非线性模型。它由神经元结构模型、网络连接模型、网络学习算法等几个要素组成, 是具有某些智能功能的系统。在文本分类中, 神经网络是一组连接的输入输出神经元, 输入神经元代表词条, 输出神经元表示文本的类别, 神经元之间的连接都有相应的权值。训练阶段, 通过某种算法, 如正向传播算法和反向修正算法, 调整权值, 使得测试文本能够根据调整后的权值正确地学习。从而得到多个不同的神经网络模型, 然后令一篇未知类别的文本依次经过这些神经网络模型, 得到不同的输出值, 通过比较这些输出值, 最终确定文本的类别。

6 分类性能评估

分类器性能评估通常采用评估指标来衡量, 评估指标是在测试过程中所使用的一些用来评价分类准确度的量化指标, 文本分类中常用的性能评估指标有查全率又称召回率 (Recall) 、查准率又称准确率 (Precision) 和F1标准。

查全率是衡量所有实际属于某个类别的文本被分类器划分到该类别中的比率, 查全率越高表明分类器在该类上可能漏掉的分类越少, 它体现系统分类的完备性。数学公式如下:

查准率是是衡量所有被分类器划分到该类别的文查本全中率正=确分文类应本的有的正的比确文率文本, 本数准数确率越高表明分类器在该类上出错的概率越小, 它体现系统分类的准确程度。数学公式如下:

Fl标准即考虑了查全率, 又考虑了查准率, 将两者看作同等重要。数学公式如下:

7 总结

本文分析了文本分类的一般过程, 详细介绍文本分类中的文本表示、特征选择和权重计算, 并且讨论几种常见分类算法, 最后叙述分类器性能评价。希望能给该领域感兴趣的读者一些有益的参考。

参考文献

[1]Aas K, Eikvil L.Text Categorization:a survey[Z].Teehnical Report 941, NOwegian Computing Center, 1999:90-100.

[2]龙树全, 赵正华.中文分词算法概述[J].电脑知识与技术, 2009, 5 (10) :2605-2607.

[3]骆昌日.基于统计方法的中文文本自动分类研究[D].武汉:华中师范大学.2004:8-11.

[4]周昭涛, 卜东波, 程学旗.文本的图表示初探[J].中文信息学报, 2005, 19 (2) .

[5]陈龙, 范瑞霞, 高琪.基于概念的文本表示模型[J].计算机工程与应用, 2008, 44 (20) :162-164.

[6]Yank Y.A Comparative Study on Feature Selection in 1'ext Categorization[C]//Proceeding of the Fourteenth International Conference onMachine Learning, 1997:412-420.

[7]Cover T M, Hart P E.Nearest neighbor pattern classification[J].IEEE Transactions on Information Theory, 1967, 13 (3) :21-27.