基于潜在语义分析的网页文本分类研究

基于潜在语义分析的网页文本分类研究

王剑锋,乔󰀁冬,麻丽娜,李新叶

(华北电力大学科技学院信息工程系,河北保定071051)

摘󰀁要:传统的基于词空间的文本分类方法很难处理文本的高维特性,提出基于潜在语义空间的网页文本分类方法,将文本数据由高维空间映射到低维空间,通过奇异值分解提取文本的潜在语义空间。在潜在语义空间中利用支持向量机方法实现文本分类;实验表明该方法对于改进文本分类的性能具有较好的效果。

关键词:潜在语义分析;网页文本分类;支持向量机

中图分类号:TP334.2󰀁󰀁文献标识码:B󰀁󰀁文章编号:1009-3230(2009)11-0041-04

WebTextCategorizationBasedonLatentSemanticAnalysis

WANGJian-feng,QIAODong,MALi-na,LIXin-ye

(DepartmentofCommunicationEngineering,NorthChinaElectricPower

UniversityScienceandTechnologyCollege,Baoding071051)

Abstract:Traditionaltextcategorizationmethodsaredifficulttodealwiththehighdimensionalitycharacteristicofthetextdocumentbasedonsemanticconceptofthewords.ThispaperproposedamethodtoWebtextcategorizationbasedonlatentsemanticanalysis.Textualdatawasmappedintoalowerspace.Theproposedapproachusedthesingular-valuedecompositiontoderivealatentsemanticspace.TheSVMisusedtotextcategorizationinthesemanticspace.Experimentalresultsshowthatthemethodiseffectiveontheperformanceofthetextcategorization.

Keywords:Latentsemanticanalysis;Webtextcategorization;Supportvectormachine

0󰀁引言

随着网络的发展与普及,数以亿记的用HT󰀁ML和XML编写的静态网页包含了大量的信息。这些信息大部分都是以非结构化的方式存在的,网页的复杂性远远超过任何文本文档。因此,要从这些大量的非结构化的网页中发现知识难度是

收稿日期:2009-10-11󰀁󰀁修订稿日期:2009-10-25基金项目:华北电力大学青年教师科研基金项目(200811036)

作者简介:王剑锋(1980~),男,硕士,华北电力大学科技学

院,助教。很大的。网页文本挖掘是解决上诉问题的重要方法。网页文本挖掘是指从大量非结构化、异构的网页文档的集合D中发现有效的、新颖的潜在可用的及最终可理解的知识的过程,其中针对文本内容的分类是文本挖掘的重点。

󰀁󰀁分类中一个重要的问题就是高维的特征空间,这些特征空间是由文本中的词或词组构成的,许多传统算法难以处理,因此降低文本空间的维度是有必要的。󰀁󰀁42󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁应用能源技术󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁2009年第11期(总第143期)

1󰀁潜在语义分析(LatentSemanticAn󰀁alysis,LSA)

潜在语义分析是一种用于知识获取和展示的计算理论和方法,它使用统计计算的方法对大量的文本集进行分析,从而提取和表示出词的语义,这种潜在语义,是词语所有的上下文语境信息的总和。这是因为,上下文环境对其中的事物提供了一组相互联系和制约,在很大程度上决定了词语之间语义上的相关性

[2]

[1]

2󰀁支持向量机(SupportVectorMachine,SVM)

支持向量机是根据统计学习理论,以结构风险最小化原则为理论基础的一种新的机器学习方法。支持向量机的学习问题就是寻找这样的最优超平面,它使不同类别数据之间的分类间隔最大,并且使位于这个平面上的数据x到平面w∀x-b(w是平面的法向量,b是平面到原点的距离)的距离为零。

假定训练数据:

S={xi,yi}(1#i#l),Li∃R,yi∃{+1,-1}

对于线性分类平面,样本集S满足约束条件:yi(xi∀w-b)-1!0,i=1,2, ,l

(3)

n

[4]

。

潜在语义分析出发点就是文本中的词与词之间存在某种联系,即存在某种潜在的语义结构。这种潜在的语义结构隐含在文本中词语的上下文使用模式中。因此采用统计计算的方法,对大量的文本中进行分析来寻找这种潜在的语义结构,它不需要确定的语义编码,仅依赖于上下文中事物的联系,并用语义结构来表示词和文本,达到消除词之间的相关性,简化文本向量的目的。

潜在语义分析的关键思想是将文档和词汇映射到一个低维的向量空间,即潜在语义空间。潜在语义分析利用奇异值分解(SingularValueDecomposition,SVD)

[3]

容易验证,最优超平面就是满足约束条件(3)式并且使得󰀂(w)=%w%最小化的超平面。求最优超平面是一个二次规划问题,可以用拉格朗日方法求解得到:

2

L=1%w%-2

i

i

2

i=1

& y(x

ii

i

i

∀

(4)

的方法实现降维。SVD是一

󰀁󰀁w-b)+

种是处理矩阵分解的强有力的方法,经过理论证明任何一个m󰀂n阶的矩阵X,X的秩为r,均可以分解成两个正交矩阵和一个对角矩阵的乘积:

X=TSD

T

i=1

&

其中 i是拉格朗日乘子,每个 i>0所对应的样本称为∋支持向量(。支持向量是训练样本中

(1)

的关键元素,如果只保留支持向量样本,而删除所有其他训练样本重新进行训练,所得到的最优超平面保持不变。

[5]

Tm󰀂n=(t1,t2, ,tr)为正交矩阵,其中t1,t2, ,tr为X的左奇异向量,并且是XX的特征向量;Sm󰀂n=diag(󰀁1,󰀁2, ,󰀁r)为对角阵,󰀁1,󰀁2, ,󰀁或r为X的所有奇异值,同时也是XXXX所有特征值的平方根,并且满足关系󰀁1!󰀁2! !󰀁r>0;Dm󰀂n=(d1,d2, ,dr)为正交矩阵,其中d1,d2, ,dr为X的所有奇异向量,并且是XTX的特征向量。因此,矩阵X可以表示为:

X=󰀁1t1d1+󰀁2t2d2+ +󰀁rtdrT

T

T

T

T

T

3󰀁网页文本分类

对于词条-文本矩阵,通过潜在语义分析提取出k维语义空间。在保留大部分信息的同时使得K∀min(m,n),这样用低维词条、文本向量代替原始的空间向量。可以有效地处理大规模的文本库。

3.1󰀁文本特征表示

与数据库中的结构化数据相比,网页文本具(2)2009年第11期(总第143期)󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁应用能源技术󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁43󰀁󰀁有有限的结构,或者根本就没有结构。即使具有一些结构也是着重于格式而非文本内容。不同类型文本的结构也不一致。

此外,文本的内容是人类所使用的自然语言,计算机很难处理其语义。文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。我们需要对文本进行预处理,将文本表示为向量空间进行文本分词处理。在文本分类中,与单个字、词相比用词组表示文档能够获得更好的分类效果,用词组来表示文本能够获得更好的分类效果,因此我们用词组为基本词条单位来表示文本的内容语义

[6]

󰀁1t1d1+󰀁2t2d2+ +󰀁rtrdr,LSA在此基础之上保留最大的k个奇异值,而忽略其他较小的奇异值,k就是低维空间的维数。然后进行奇异值分解反运算,得到原始矩阵的近似阵。k应当足够小,除掉不该保留的噪声,要足够大以保留语义空间中的主要框架,通常根据经验来说,当X的秩为几千的时候,k的取值为几百。LSA降秩的过程可以近似认为去除了语义空间中代表低信息量(即噪声)的自由度,而保留了代表语义空间中主要信息的自由度。

令󰀁Sk=diag(󰀁1,󰀁2, ,󰀁r),Tk=(t1,t2, ,tr),Dk=(d1,d2, ,dr)

则:󰀁Xk=TkSkDk

^^

T

TTT

。传统的空间向量方法假设词

语语义是相互独立的,每个词语都被看作向量空间中的一个正交基本向量。实际上,词语之间存在很强的关联性,即出现∋斜交(现象

[7]

(5)

为X的秩为k的近似矩阵。经过降秩得到近似矩阵Xk=

doc1,doc2, ,docn)=(term1,

T

,影响了文

本处理的效果。潜在语义分析利用奇异值分解降秩的方法达到信息过滤和去除噪声的目的。潜在语义分析不同于向量空间模型(VSM)中文档的高维表示,而是将文本的高维表示投影在低维的潜在语义空间中,缩小了问题的规模。并且使得原本稀疏的数据变得不再稀疏,从而呈现出一些潜在的语义结构。得到的新的低维的语义空间,如图1。

term2, ,termm),可以比较任意两个文本、任意两个词汇间的相似度。常用的方法是求两文本向量间(或两词汇向量间)的点乘、夹角余弦值或是相关系数。也可以将Xk写成:

Xk=󰀁1t1d1+󰀁2t2d2+ +󰀁ktkdk

^

T

T

T

^

(6)

对于其中的每一个文本向量,可以用下式表示:

doci=󰀁1d1,i󰀁t1+󰀁2d2,i󰀁t2+ +󰀁󰀁󰀁kdk,i󰀁tk

(7)

其中dh,i表示向量dh的第i个分量。可以将doc)i=(󰀁1d1,i+󰀁2d2,i+ +󰀁kdk,i)视为文本i在k维向量空间中的表示,因为t1,t2, ,tk是正

图1󰀁三维潜在语义空间示例

T

交向量,这样就得到了文本在低维空间中的向量表示。

3.3󰀁利用支持向量机进行文本分类

在K维空间中利用SVM进行文本分类,一组支持向量可以唯一地确定一个分类超平面。对于线性可分的问题,可假定训练集中的向量满足:

yi[(w󰀁xi)+b]-1!0,i=1,2, ,n

(8)

3.2󰀁文本空间降维

与普通分类问题的数据空间相比,文本空间是一个高维,稀疏空间,文本中包含的不同词条数以万计,但对每个具体的文本而言,真正出现在文本中的词条只有上千个。文本中的维数过高会降低分类速度与准确度,因此需要对文本向量空间进行降维。对于一个∋词汇-文本(矩阵X=此时分类间隔为2󰀁%w%,使分类间隔最大󰀁󰀁44󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁应用能源技术󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁2009年第11期(总第143期)等价于使%w%最小,此构造最优分类面的问题就转化为在式(8)的约束下求%w%󰀁2的最小值。可以看出这是一个二次优化问题,采用拉格朗日乘数法可将该问题转化为对偶问题,即在约束条件:

[8]2

5󰀁结语

潜在语言分析提取出k维语义空间,在保留大部分信息的同时降低了空间维度,这样用低维词、文本向量代替原始的空间向量,可以有效地处理大规模的文本库。但是潜在语言分析仍然是一

i=1

&y =

ii

n

0(9)

种∋bag󰀁of󰀁word(方法,简单地通过所有词向量的线性总和来产生文本向量,表示文本的含义,没有考虑句子语法结构中所包含词语之间更深层次的语义关联信息,从而影响了潜在语言分析对文本

i!0,i=1, ,n

下对 求解下列函数的最大值:Q( )=

n

n

i=1

&

1 i-i jyiyj(xixj)2i,&j=1

(10)

内容的把握能力。因此,需要研究如何将潜在语言分析思想和语法信息有效地结合起来,以提高网页文本分类的性能。

参考文献

[1]󰀁LandauerTK,FoltzPWLathamD.IntroductiontoLatent

SemanticAnalysis.DiscourseProcesses,1998,(25):259

这是一个在不等式约束下二次函数的寻优问题,存在唯一解。解中不为零的 i为最优解,记为 ,则 对应的样本就是支持向量,得到的最优分类函数是:

f(x)=sgn{W󰀁X+b}=sgn{󰀁󰀁(xi󰀁x)+b}

*

*

*

i

*i

i=1

& y

*i

n

-284.

i

[2]󰀁WalterKintsh.Predication[J].CognitiveScience,2001,

25:173-202.

[3]󰀁DeerwesterS,DumaisST,GW,etal.Indexingbylatent

semanticanalysis.JournaloftheAmericanSocietyforIn󰀁formationScience,1990,4(1).

[4]󰀁Vapink.TheNatureofStatisticalLearningTheory[M].

NewYork:Springer1995.

[5]󰀁JoachimsT.Textcategorizationwithsupportvectorma󰀁

chines:learningwithmanyrelevantfeatures[C].Proceed󰀁ingsofECML-98,10thEuropeanConferenceonMachineLearning,1998:137-142.

[6]󰀁JFurnkranz,TMitchell,ERiloff.ACaseStudyinUsing

LinguisticPhrasesforTextCategorizationontheWWW[Z].WorkingNotesofthe1998AAAI󰀁ICMLWorkshoponLearningforTextCategorization.

(11)

b是分类阈值,可通过两类中任意一对支持向量取中值求得。对于给定的未知样本x,需带入(5)式计算,即可判定x所属的类别。

4󰀁实验结果

分类常用的评价标准是准确檬(Precision)和查全率(Recall)

[9]

。本实验选择计算机、数学、物

理学、化学、文学、社会学、天文学和地质学8个类别共1680篇中文文档进行分类。较传统的基于向量空间(VSM)的分类方法有一定的提高。实验结果如表1。

󰀁表1类别计算机数学物理学化学文学社会学天文学地质学

实验结果

基于VSM方法准确率0.790.800.830.810.630.670.830.82

查全率0.800.810.870.830.710.730.860.89

基于LSA方法准确率0.850.850.900.870.690.710.860.85

查全率0.900.890.920.950.780.830.890.87

[7]󰀁林鸿飞,姚天顺.基于潜在语义索引的文本流浏览

机制[J].中文信息学院,2000,14(5):49-56.[8]󰀁ChristopherJCBurges.ATutorialonSupportVectorMa󰀁

chinesforPatternRecognition[J].DataMiningandKnowl󰀁edgeDiscovery,1998,2(2):955-974.

[9]󰀁FabrizioSebastiani.Machinelearninginautomatedtext

categorization[J].ACMComputingSurveys,2002,34(1):11-12,32-33.