当前位置:文档之家› 降维方法

降维方法

国内当前流行的文本分类算法有最大熵(MaximumEntropy,ME),K近邻法(KNN),朴素贝叶斯法(NB),支持向量机法(SVM),线性最小平分拟合法(LLSF),神经网络法(Nnet)等,其中KNN、NB和SVM的分类效果相对较好。

文本分类由文本表示,特征降维和分类器训练组成,分类算法只是其中的一个环节,另外两个环节也非常重要。

目前普遍采用向量空间模型来表示文本,常见的特征词加权方法有:布尔权重、词频权重、TF—IDF权重等,常见的特征选择方法有文档频率,互信息和统计等。

基于机器学习文本分类的基础技术由文本的表示(representation) 、分类方法及效果(effectiveness)评估3 部分组成。

Sebastiani对文本分类发展历程及当时的技术进行了总结,主要内容包括:(1)文本关于项(term)或特征的向量空间表示模型(VSM)及特征选择(selection)与特征提取(extraction)两种表示空间降维(dimensionality reduction)策略,讨论了χ2,IG,MI,OR 等用于特征过滤的显著性统计量及项聚类和隐含语义索引(LSI)等特征提取方法;(2) 当时较成熟的分类模型方法,即分类器的归纳构造(inductiveconstruction)或模型的挖掘学习过程;(3) 分类效果评估指标,如正确率(precision) 召回率(recall) 均衡点(BEP) Fβ(常用F1)和精度(accuracy)等,以及之前报道的在Reuters 等基准语料上的效果参考比较。

1、中文评论语料的采集利用DOM 构建网页结构树,对结构树的分析实现了中文评论的自动采集的方法。

以及对情感语料进行情感标注,利用中文分词技术对情感语料进行分词等基础性研究。

2、情感词典的构建利用PMI 算法,在基础情感词典和中文宾馆评论语料库的基础上构建宾馆评论领域情感词典的方法。

3、文本处理中的特征选择、特征权值和向量表示CHI 统计方法和采用情感词典作为情感特征选择的方法,以及降维的维度选择等相关问题。

研究了3 种特征权值计算方法和特征权值的意义,以及使用矩阵文本表示文本向量的方法。

4、朴素贝叶斯分类器的构建研究如何利用朴素贝叶斯方法构建中文文本情感分类器,估计先验概率和后验概率的方法,以及后验概率平滑技术参数设置等问题。

实验对比了不同方法构建的分类器的性能,并进行了相关分析。

5、朴素贝叶斯文本情感分类实验系统的设计与实现开发了一个基于朴素贝叶斯的中文文本情感分类器,简要介绍了其系统构架、主要功能和工作流程,这个分类器是本文进行分类实验所使用的分类器。

语料的中文分词处理虽然表示语言的最小粒度是字,但单个字并不能代表所有的语义,一般认为可表示语义的最小粒度为词。

本文使用了传统的最大匹配算法对语料库中的中文文本进行分词,该方法属于基于字符串匹配的分词方法,需要分词词典支持。

分词词典采用了国家语言文字工作委员会发布的《现代汉语常用词表(草案)》(LCWCC)[49],该词典搜集了现在日常生活中使用频率较高的56008 个词汇,基本能够满足分词的需要。

在特征选择步骤,本文采用了情感词典作为特征选择的依据,所以在分词时,实际是采用了LCWCC 和情感词典的并集作为了分词词典。

其中最大匹配的步长设置为4 个汉字,只对中文内容进行分词处理。

用统计的方法对文本进行分类的关键步骤可以分为以下几步:1)文本表示2)文本的特征选择3)特征对分类的贡献度量计算4)分类算法选择文本的表示文本表示模型主要有布尔模型,向量空间模型和概率模型,最常用的是向量空间模型。

在向量空间模型中,每个文本都被表示为一组规范化正交特征矢量所组成的空间向量的一个点。

该向量中每一维的值表示了一该特征项在文本中的权重。

也就是说向量空间模型将文本特征集视为一个高维的空间,特征集中的每一个元素t,都是高维空间中的一维,文档在该维上的值为哄这样一篇文档就表示成在特征向量空间上的一个向量。

向量空间模型中向量间的相似程度可以根据向量之间的夹角大小来反映。

在实际应用中常常通过计算向量夹角的余弦来得到相似度。

虽然空间向量模型是一个很好的模型但它也存在着不容忽视的缺点,集合是没有顺序的概念的,所以用空间向量模型来表示文本时丢掉了许多除词的信息以外的所有重要的信息,比如词语与词语之间的相对位置关系、上下文信息等。

在语言中这种关系通常含有重要的意义。

例如:“联合国/n维和部队/n遭到八反/d政府/n武装/nv人员/n袭击/v”“反/d政府/n武装/nv人员/n遭到八联合国/n维和部队/n袭击八”这两句话用空间向量模型来表示是等价的,但恰恰相反这两句话意思完全不同。

这使得向量空间模型所能表达的信息量存在上限,也直接导致了基于这种模型构建的文本分类系统,很难达到人类的分类能力。

文本特征提取如何有效的降低维数并尽可能的减少噪声数据对分类效果的影响是文本特征提取的关键问题。

对于大量的文本在分词后的词汇量是数以万计或者更高的,在分类器中这就表现为数以万计的维数。

要处理这么多的数据,需要大量的时间,在对时间复杂度要求较高的系统(比如:在线服务的系统)中这是无法忍受的。

这就要求所选用的分类器时间复杂度要低,尽可能的做到线性,但这是不现实的因为现有的机器学习分类算法很少有随着数据维数的增长时间线性增长的,这种非线性增长对海量数据而是就造成了所谓的“维数灾难”。

所以有效的降低数据维数,去除噪音数据是数据降维的主要目的。

在文本分类中常用特征选择来进行降维,选取那些对分类贡献高的词作为特征丢掉噪声和对分类贡献低的词。

特征的选取可以有基于人工的方式和基于统计学的方式。

基于人工的方式也就是人工选择那种重要的词来作为特征,这需要一定的经验。

而基于统计学的方式又可以分为:基于文档频率的特征选择法,信息增益法,χ2统计量等多种方法。

国内外很多学者对各种特征选择方法进行研究。

结果表明在英文文本分类中表现比较好的方法在不加修正的情况下,并不适合中文文本分类。

分类器经过许多学者的努力提出了一些经典的算法。

比如:Rocchio算法、K近邻算法(KNN)、贝叶斯分类器、支持向量机、最大嫡、决策树、人工神经网络等。

和规则的方法相比统计的方法需要有较强的数学基础,但是统计的方法在普适性方面要比规则的方法要好。

1)Rocchio算法Rocchio算法的基本思想是使用训练语料为每个类别构造一个原型向量。

构造的过程如下:给定一个类,训练集中所有属于这个类加的分量用正数表示,所有不属于这个类别的文档对应向量的分量用负数表示,然后把所有的向量加起来,得到的和向量就是这个类的原型向量,定义两个向量的相似度为两个向量夹角的余弦,逐一计算训练集中所有文档所表示成的向量和原形向量之间的相似度,然后按一定的算法从中挑选某个相似度作为闽值。

给定一篇文档与原型向量的相似度较大,则这篇文档属于这个类别,否则这篇文档不属于这个类别。

Rocchio算法的突出优点就是容易实现,并且计算特别简单,它通常用来实现衡量分类系统性能的对比系统,而实际应用的分类系统很少采用这种算法解决具体的分类问题。

2)K近邻算法KNN(KNearestNeighbors,KNN)原理是计算每个样本数据到待分类数据的距离。

KNN算法又叫k最近邻方法,总体来说KNN算法是相对比较容易理解的算法之一,它通过计算待分类文档与所有训练文档的距离来进行分类的。

假设每一个类包含多个样本数据,而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类,KNN就是计算每个样本数据到待分类数据的距离,取和待分类文本最近的K各样本数据,那么这K个样本数据中哪个类别的样本数据占多数,则待分类数据就属于该类别。

具体的算法步骤如下:<1>根据特征集将训练文本表示成向量<2>用类似于第1)步的方法将待测文本也表示成向量<3>选取K个与待测文本相似度最大的训练文本,相似度计算公式为:其中,K是经验值并不固定,需要在实验中反复试验,以求效果在测试集上效果达到最佳。

<4>在新文本的K个近邻中,依据的算法确定待分类文本的类别。

3)贝叶斯分类器朴素贝叶斯是贝叶斯方法中使用最为普遍的一种。

作为一种简单而有效的概率分类器,朴素贝叶斯分类器被广泛应用文本分类中,并且取得了不错的效果。

朴素贝叶斯分类算法假设构成文本d的多个特征之间相互独立。

可以通过先验概率和类别的条件概率来估计文档d对类别c,的后验概率,以实现对文档d所属类别的判断。

由于文本的多个特征之间相互独立,对每个参数就可以分别估计,这样就大大简化了计算,使它尤其适合属性数量非常大的文本分类问题。

尽管词语在文本中的分布是条件独立的朴素贝叶斯假设在实际语一言中并不成立。

然而朴素贝叶斯分类器在实际应用中却能够取得良好的效果。

4)支持向量机支持向量机SVM是由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术。

支持向量机是在统计学习理论框架下产生的一种机器学习算法。

它建立在统计学习理论的VC维理论和结构风险最小化原理的基础上,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以获得最好的推广能力。

SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,现在己经在许多领域(生物信息学,文本和手写识别等)都取得了成功的应用。

SVM是从线性可分情况下的最优分类超平面发展而来的,其基本思想可用图1的二维平面的情况来说明。

在多维的情况下支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。

在分开数据的超平面的两边建有两个互相平行的超平面。

分隔超平面使两个平行超平面的距离最大化。

假设数据点是n维实空间中的点。

我们希望能够把这些点通过一个n-1维的超平面分开。

我们希望找到最佳的分类平面,即使得属于两个不同类别的数据点间隔最大的那个超平面,该超平面亦称为最大间隔超平面。

相关主题