当前位置:文档之家› Web文档中词语权重计算方法的改进

Web文档中词语权重计算方法的改进

ComputerEngineeringandApplications计算机工程与应用

2007,43(19)向量空间模型

降维

特征抽取

特征选择

权值调整

文本表示图1文本向量优化技术

1引言

网络的发展使网络的信息量高速膨胀。据Lesk(1997)的

报告指出,从1995到1997年,Web上的文本信息以每年10倍递增,预计到1998年已经超过美国国会图书馆,达到20TB,目前已经很难对总的信息量进行准确的估计。网络信息量虽然巨大,但是对99%的用户来说99%的信息都是无用信息,所以要想在网络中通过相关链接来找到所需的信息无异于大海捞针。因此迫切需要研究出更为先进的技术来管理和组织这些信息,而对Web文本进行分类是这些技术中最为重要的技术之一。

要进行Web文本分类,首先要做的就是对Web文本数据进行数学描述,其中最基本的模型就是向量空间模型。在这种模型中,每一个不同的单词都作为特征空间中的一维,每一个文本就是特征空间中的一个向量。但是,这种描述方法引发了一个非常严重的问题,那就是高维稀疏,加之文本数据所特有的近义词﹑多义词等等问题,使得文本分类具有相当高的时间复杂度,而且这些问题也极大地干扰了分类算法的准确性,使得文本分类的性能急剧下降。因此,迫切需要通过其它技术优化文本向量表示以帮助提高文本分类的性能。

如图1所示,这些优化技术总的来说分为两类,首先是权

重调整方法。权重调整方法是通过综合考虑一个单词相对于一个文本﹑一个数据集或者一个类的重要性来调整其在不同文本中的权重,使其值尽可能正确地反映一个单词与一个文本在语义上的关系。另一类优化技术是降维,它指的是通过降低特征空间的维度优化文本的表示。主要包括特征选择和特征抽取两种技术。

本文将把重点放在权重调整的优化技术上。在分析当前所采用的权重计算方案的基础上,结合Web文本的特点,提出了一种新的权重调整方案,经实验验证能够有效提高Web文本的分类性能。

2传统权重计算公式的分析

单词权重的衡量不仅要考虑单词的局部权重,即单词在一

Web文档中词语权重计算方法的改进

初建崇1,刘培玉2,王卫玲2

CHUJian-chong1,LIUPei-yu2,WANGWei-ling2

1.海军航空工程学院训练部,山东烟台264001

2.山东师范大学信息科学与工程学院,济南250014

1.NavalAeronauticalEngineeringInstitute,Yantai,Shandong264001,China

2.CollegeofInformationScienceandEngineering,ShandongNormalUniversity,Ji’nan250014,ChinaE-mail:wangweiling0714@163.com

CHUJian-chong,LIUPei-yu,WANGWei-ling.ImprovedapproachtoweightingtermsinWebText.ComputerEngineeringandApplications,2007,43(19):192-194.

Abstract:ThispaperusesvectorspacemodelasthedescriptionoftheWebtext,analysesandimprovesthetraditionalformulaTF*IDF.First,weexplorethefeatureoftheWebpageswhicharewritteninHTMLanddescribethesituationinformationofthetermsinWebtext.Second,weusegeneralizedinformationtheoryasthetheorybasetointroducethequadraticentropymutualin-formationintotheformula.Theexperimentshowsthefeasibilityandthevalidityofthismethod.Keywords:vectorspacemodel;Webtextclassification;weightadjustment;mutualinformation

要:以向量空间模型作为Web文本的表示方法,对传统的TF*IDF公式进行了改进。首先,结合Web文本中HTML标签的修

饰功能,体现了特征词在Web文本结构中的位置信息;其次,以广义信息论为理论基础,引入了基于二次熵的互信息作为权重计算公式的一项,体现了单词的类区分能力。实验验证了该方法的可行性和有效性。关键词:向量空间模型;Web文本分类;权重调整;互信息文章编号:1002-8331(2007)19-0192-03

文献标识码:A

中图分类号:TP391

作者简介:初建崇(1979-),男,助理工程师,主要研究方向:网络信息安全;刘培玉(1960-),男,教授,博士生导师,主要研究方向:数据库与网络信

息安全;王卫玲(1979-),女,硕士研究生,主要研究方向:Web挖掘、信息检索、信息过滤。

192

ComputerEngineeringandApplications计算机工程与应用2007,43(19)

个特定文本中的重要性,还要考虑单词的全局权重,即单词在整个文本数据集中的重要性。将这两个因素结合在一起,就得到了单词权重的通用公式:

id

=local(t,d)*global(t)(1)其中,local(t,d)代表局部权重,global(t)代表全局权重。

单词权重最为有效的实现方法就是TF*IDF,它是由Salton在1988年提出的。其中TF称为词频,用于计算该词描述文档内容的能力;IDF称为反文档频率,用于计算该词区分文档的能力。TF*IDF的指导思想建立在这样一条基本假设之上:在一个文本中出现很多次的单词,在另一个同类文本中出现次数也会很多,反之亦然。所以如果特征空间坐标系取TF词频作为测度,就可以体现同类文本的特点。另外还要考虑单词区别不同类别的能力,TF*IDF法认为一个单词出现的文本频率越小,它区别不同类别的能力就越大,所以引入了逆文本频度IDF的概念,以TF和IDF的乘积作为特征空间坐标系的取值测度。

TF-IDF初看上去似乎合理,然而如果深入研究的话,发现这种权值计算方法对Web文本的分类并不是那么有效,其主要原因包括以下两个方面:

(1)在Web文本中,处于不同位置的单词的重要性是不同的,如果忽略单词的位置信息,仅仅以单词出现的频度作为单词重要性的衡量显然是不合理的;

(2)TF*IDF是局部权重和全局权重的综合,它仅仅表达了一个单词对一个文本的区分能力,而并没有包含这个单词区分一个类和其它类的能力。但是显然,对于文本分类来说,更为重要的是一个单词的类区分能力。

针对这些问题,近来的一些研究也提出了其它一些专门针对文本分类的单词权重调整算法,比如Shankar&Karypis提出了一种快速的迭代权重调整算法[1],它通过在TF*IDF的基础上使用单词纯度来对单词的权重进行不断调整,使分类性能提高了2%~5%;陆玉昌等人提出了一种利用特征选择中的评估函数来代替IDF进行权值调整的方法[2],使越具有类区分能力的单词在权值调整后具有越高的权重,从而使分类精度有所提高。

为了很好地解决上述问题,本文提出了一种综合考虑Web网页特点及其类别信息的权重调整方案。下面将对这种权重调整方案进行详细的介绍。

3改进的权重计算方案

针对第2章中所提出的在TF*IDF权重计算公式中所存在的问题,本文主要采用了以下两种方法予以解决:

(1)分析了HTML标签的修饰功能,对于不同标签下的单词赋予不同的权重,改进了传统的方法中仅仅以单词频度作为衡量标准的片面性;

(2)为了尽量提高具有类区分能力的单词的权重,同时降低缺乏类区分力的单词的权重,将式(1)中的通用公式作了如下调整,扩展了一项单词的类区分能力:

id

=local(t,d)*global(t)*classDisc(t)(2)其中classDisc(t)表示的就是单词t的类区分能力。

3.1基于HTML标签的加权

首先假设用户在使用HTML标签创建网页时,其使用标签的目的和标签所起的修饰作用是一致的。如:当创建者使用〈EM〉标签时,确实是为了强调该标签所修饰的内容。据此,本节根据标签的修饰作用对单词加权。

根据HTML标签对Web页面物理显示所产生的影响将其分为4类:

(1)标签本身及其所修饰的内容均不在浏览器中显示。有:<!—…—>(注释)。

(2)标签修饰的内容在浏览器上显示,绝大多数标签属于这一类。又可分为4个子类:

①改变文本的物理显示,如<B>(粗体显示)﹑<I>(斜体显示)。

②改变文本的内容样式,通过改变文本的物理显示来实现,如<H1>﹑<EM>。

③物理显示没有变化(同不加标签相比),但这些标签反映其修饰内容的属性。有:<CODE>﹑<DL>﹑<DT>﹑<DD>。其中<CODE>表明其修饰的内容为一段程序代码;<DL>﹑<DT>﹑<DD>则分别指出,下面是一列术语﹑术语词内容以及对这个术语的解释。

④当鼠标放在上面时,显示提示内容。主要是标签的一些属性,如title属性。

(3)标签本身在浏览器上显示。包括:<LI>﹑<OL>﹑<UL>。这些标签用于定义列表项。

(4)根据浏览器的设置或不同的浏览器,标签所修饰的内容可能显示,也可能不显示。一个很重要的应用是对于标签<IMG>的“ALT”属性说明,用户可以通过浏览器的设置来决定是否下载图像。不可缺省的“ALT”属性表示图像不能显示时的替换文本,通常能够反映图片的内容。因此加权这个标签属性是完全必要的。除了<IMG>外,标签<AREA>(客户方图像映射的链接集合),<APPLET>(JavaApplet),<EMBED>(加入多媒体对象)也有这个属性。

相对于文本文档的单词权重计算,Web页面中的词频计算表示为:

tfw

i,j

k=1

!wk?fk(3)

tfw

i,j

称为单词的加权频率(weightedfrequency)。f

表示词的第k

次出现(暂定f

的值恒为1),w

表示词在第k次出现时修饰它的HTML标签权重。

3.2单词的类区分能力的加权

近年来,一些研究者[3,4]对使用TF*IDF权重函数给特征词加权的合理性提出了异议,因为一个文本中对分类有用的词条只占一小部分,而大部分词条与要判别的类无关,属于“噪音词条”。结果两个文本的相似度在很大程度上是由噪音词条的词频差异,而非有用词条的词频差异决定。这些噪音完全可能淹没有用信息,从而影响分类精度。TF*IDF法中的IDF函数在本质上就是一种试图抑制噪音的加权。然而,IDF函数简单地认为文本频数少的单词就重要,文本频数多的单词就无用,这显然是太武断了。IDF的简单结构使得它不可能很好地反映单词的有用程度。另外,对于文本分类来讲,更为重要的是一个单词的类区分能力,而这一点在TF-IDF公式中没有得到很好的体现。

因此,本文在TF*IDF公式的基础上,又扩展了一项单词的类区分能力,其通用公式如公式(2)所示。新扩展的项class-Disc(t)用于描述单词与各个类别之间的相关程度。在文献[2]中,陆玉昌等人对信息增益﹑信息熵﹑互信息﹑文本证据权等作为权重调整因子的性能进行了比较,发现互信息是效果最好的

初建崇,刘培玉,王卫玲:Web文档中词语权重计算方法的改进193

标签

<TITLE>…</TITLE><H1>…</H1><H2>…</H2><B>…</B><EM>…</EM><I>…</I>

<BLANK>…</BLANK><IMGalt=…

权重

54322222

表1

HTML中标签权重的分配

TF*IDF0.6920.7010.6360.8120.742

TF*IDF改进公式

0.8290.7950.7730.8870.744

政治

经济

军事体育计算机

权重

类别表2

分类结果的F1测试值的比较

一个。但是因为文本向量空间的特征集是高维而且稀疏的,如果能够用互信息通过变量的分布函数及其积分函数,找到一个比较合适的目标函数来选取特征,要比直接使用互信息精度高。在本文中以广义的信息论为理论基础,提出了一种新的基于二次熵的互信息评估函数来衡量特征与类别之间的关系,作为权重计算的classDisc(t)项。

由广义信息论知广义熵定义如下:

Ja

n[p(c1|x),p(c2|x),…,p(cn|x)]=

(2

1-a

-1)

-1

i=1

!pa

(ci|x)-"

#

其中,a是一个正参数,a≠1。不同的a值可以得到不同的熵分离度,当a=2,就得到了二次熵定义。

广义熵具有对称的特点,hn(p1,p2,…,pn)=hn(p2,p1,…,

pn)=…=hn(pn,…,p1)≥0,如果pk=1而且pi=0,1≤i≤n,i≠k,

则hn(p1,p2,…,pn)=0,hm+1(p1,p2,…,pn,0)=hm+1(p1,p2,…,pn)。

对于任意的概率分布pi≥0,(i=1,2,…,n),

i=1

!pi

=1,有

hn(p1,p2,…,pn)≤hn(1n,1n,…,1n

对于所有的事件,熵函数是连续函数。为了评估所选取的特征,向量空间每一点的熵函数都要进行计算,在熵函数值较大的空间部分,不同类的样本必然在较大的程度上互相重叠,所以熵函数的期望值可以表征类别的分离程度,作为选取特征分类性能的评价指标。

综合以上理论,类别和特征的二次熵函数如下:

H(C)=-logn

i=1

!p(ci)

H(X)=-logX

p(xj)2

dx

在互信息中,使用二次摘函数度量互信息量还需要求出度量变量的概率密度函数的分布,将每个特征xi都作为中心点,σ是xi的方差,求其概率密度分布为:

p(xi)=n

i=1

!G(xi-xj,!I)

结合熵函数的期望值等理论,得出基于二次熵的互信息在两个变量ci和xi之间的度量为:

MI′

(C,X)=log

i=1

!X

p(ci

,xj

)2

dxj)(n

i=1

!

’p(ci

)2

p(xj

)2

dxj

i=1

!X

p(ci

,xj

)p(ci

)p(xj

)dxj

)2

(4)

用基于二次熵的特征变量集X和类别变量集C之间的互信息评估函数,对每个特征xj,求其二次熵互信息,作为权重因子中的一项classDisc(t)。

综合以上两方面对权值计算公式的调整,改进后的权重计算公式为

Wi=tfw

i,j?idf?MI′

(C,xi)(5)

考虑到文档长度不一样对词频的统计具有一定的影响,一个特征词在长的文档中比在短的文档中更有可能被提取出来,因此采用对每个特征词的权重进行归一化量化的方法来消除

这种影响。处理的方法如下:

W′i=

Wi

i=1

!W

2(

其中,W′i为特征词xi的最后权重值,m为文档中的特征词个数。

4实验与分析

Web文档的权重计算是Web文档处理中的一个基础问题,为了验证本文提出的权重计算方案的优势,选取了对Web

文本分类作为实验问题来考察此改进方案的价值。

4.1分类器的选择

Web文本分类一直是对Web上的海量信息进行组织和管

理的重要手段之一。现今已有诸多新的分类方法被提出来,例如ExpertNetwork,Widrow-Hoff﹑EG﹑支持向量机的文本分类以及神经网络的文本分类等等。

在本文中选取最为常用的基于K-NN的改进方法作为分类方法,并采用cosine距离作为距离计算方法:

sim(D1,D2)=

j=1

!W

D1j*WD2j

j=1

!(W

D1j

)2

*t

j=1

!(W

D2j

)2

(

4.2实验及结果

实验数据是从网上下载的1565篇新闻,包括政治267篇﹑经济200篇﹑军事581篇﹑体育248篇和计算机269篇共5类。简单地对表1中所给出的8种标签进行加权,权值如表中所示。

实验采用的评估指标为F1测试值,它综合考虑了文本分

类的准确率与查全率,其具体计算公式如下:

F1测试值=准确率×

查全率×2准确率+查全率

在实验过程中,分别采用TF*IDF以及改进后的权重计算公式对特征词进行加权,并对Web文本进行了分类,分类结果的F1测试值如表2所示。

(下转198页)

(上接194页)

从表2中可以看出,由于改进后的权值公式能够突出文本中的重要词,抑制次要词语,所以能够明显提高分类的效果。

5结论

TF*IDF公式是文本分类中权值计算的一种有效方法,但

是它只是一种经验公式,并没有很深的理论基础。本文结合

Web文本的特点,提出了一种改进的权重计算公式,同时将

HTML标签的修饰功能以及单词的类区分能力在权值公式中

予以体现。经实验验证,改进的权值公式在实际分类系统中取得了很好的分类效果。(收稿日期:2006年11月)

参考文献:

[1]ShankarS,KarypisG.Afeatureweightadjustmentalgorithmfor

documentcategorization[C]//SIGKDD’00Workshop.

[2]陆玉昌,鲁明羽,李凡,等.向量空间中单词权重函数的分析和构造[J].

计算机研究与发展,2002,39(10):1205-1210.

[3]JoachimsT.AprobabilisticoftheRocchioalgorithmwithTFIDF

fortextcategorization[C]//The14thInt’1ConfonMachineLearning(ICML’97),Nasvile,TN,USA,1997.

[4]李凡,鲁明羽,陆玉昌.文本特征选择新方法的研究[J].清华大学学

报,2001,41(7):98-101.

[5]YangYi-ming.Anevaluationofstatisticalapproachtotextclassi-

ficationCMU-CS-97-127[R].ComputerScienceDepartment,CarnegieMellonUniversity,1997.

[6]陈治平,林亚平,童调生.基于N层向量空间模型的信息检索算法[J].

计算机研究与发展,2002,39(10):1233-1237.

[7]ChenKe-li,ZongCheng-qiang.Anew-weightingalgorithmforlin-

earclassifier[C]//InternationalConferenceonNaturalLanguagePro-cessingandKnowledgeEngineering,Beijing,2003:650-655.[8]RiboniD.Featureselectionforwebpageclassification[C]//Shiraz,

Iran.EURASIA-ICT2002,ProceedingsoftheWorkshop,AustrianComputerSociety,2002:1-5.

1.控制点模型建立,确定相应的游客运送矩阵TRm×n

。本文问题中,游客运送矩阵可表示为:TR6×

3=

TRTRW

TRTRE

!"

2.考虑运载方式对运载游客的最大负载能力等因素,确定相应的约束条件

ST,并对游客运送矩阵TR6×3

进行初始化;3.确定流量控制(Traffic-flowcontrol)优先级矩阵PRITC:

定时检测各特征路径上的游客状态(数量与平均等候时间),并进行优先级排队,得到游客通过该控制点的优先级矩阵PRITR;并对不同的运送通道确定运送的优先级矩阵PRIVa;然后根据所得到的PRITR和PRIVa,确定该节点的游客流量控制优先级矩阵:

PRITC=PRITR×PRIVa=

PRITRW×PRIT

Va_W

PRITRE×PRIT

Va_E

#$$$$$$$%

&

’’’’’’’(6×3

4.在满足约束ST的条件下,根据流量控制优先级矩阵PRITC来更新该控制

节点的游客运送矩阵TR6×3

,从而实现游客流量的定时优化控制;5.重复上述两个步骤,执行下一周期的流量控制指令。

图4节点TR游客流量控制策略实施步骤

Va_BrW=BrW-TRBr

Va_ShW=ShW-TRSh

Va_ChW=ChW-TRCh

)++++*++++,

Va_BrE=BrE-TRBr

Va_ShE=ShE-TRSh

Va_ChE=ChE-TRCh

)++++*++++,

因此,通道空闲优先级为:

PRIVa=

PRIVa_W

PRIVa_E

#

$$$$$$$%

&’’’’’’’(

PRIVa_Br

WPRIVa_Sh

PRIVa_Ch

PRIVa_Br

PRIVa_Sh

PRIVa_Ch

#$$$$$$$$%

&’’’’’’’’(

(9)

根据原则1和原则2,得到节点TR的游客流量控制优先级矩阵为:

PRITC=PRITR×PRIVa=

PRITRW×PRIT

Va_W

PRITRE×PRIT

Va_E

#$$$$$$$$$%

&

’’’’’’’’’(6×3

(10)

(3)节点TR的游客流量控制策略描述

在节点TR的游客运送模型的基础上,通过定时游客流量控制优先级矩阵,以不断更新游客的运送矩阵来控制。节点TR的游客流量控制策略描述如图4所示。

结论

本文以2010年上海世博园区总体规划方案为基础,构建

参观者在园区内部游览路线的基本模型,利用群体智能算法进行路径规划的优化设计的探讨,提出相应的最优方案求解的指导性策略,并对可能出现的典型游客拥塞问题,给出了游客流量的控制策略。(收稿日期:2007年1月)

参考文献:

[1]WangD,MaL,ZhuW.Researchofpedestrianflowintheworld

Expo2010ShanghaibasedonInternetsurvey[J].UrbanPlanning,2006,3:58-63.

[2]XiaoHui,YanYong,XiaoYun-shi.Swarmintelligencebasedtraffic

optimizationstrategyinsideShanghaiExpoArea[C]//RIUPEEEC2006,Macao,China,July,2006:13-14.

[3]KennedyJ,EberhartRC.Particleswarmoptimization[C]//ProcIEEE

InternationalConfonNeuralNetworks.Piscataway:IEEE,Perth,1995:1942-1948.

[4]EberhartRC,ShiY.Particleswarmoptimization:developments,

applicationsandresources[C]//ProcCongressonEvolutionaryCom-putation.Piscataway:IEEE,Soul,2001:81-86.

[5]汪镭,康琦,吴启迪.基于多元最优信息规划的微粒群优化算法[J].

控制与决策,2004,19(12):1364-1367.

[6]EsminA,Lambert-TorresG.Ahybridparticleswarmoptimization

appliedtolosspowerminimization[J].IEEETransactionsonPowerSystems,2005,20(2):859-866.

[7]吴立成,孙富春,孙增圻.柔性空间机器人振动抑制轨迹规划算法[J].

机器人,2003,25(3):250-254.

[8]李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统

工程理论与实践,2004,24(4):130-135.

下载文档原格式(PDF原格式,共4页)
相关文档
  • 权重的三种计算方法

  • 最简单的权重计算方法

  • 权重计算方法

相关文档推荐: