网格网格计算

2006年第23卷·增刊微电子学与计算机收稿日期:2006-04-28基金项目:"985"工程计划项目(0000-X07204)1引言文本分类是指在给定的类别体系下,根据文档的内容自动确定文本分类的技术[1].
它是文本分类挖掘的一个重要组成部分,在提高信息检索的速度和准确度方面有着重要的意义.
在文本分类中,使用最多的文本表示模型是"词袋法",每一个文本d都可以表示成一个关于词条的序列d=(w(1),w(2),w(3),…,w(|d|)),其中|d|为文本中出现的词条总数,而空间向量的测度用w(i)来描述.
对于所有文档d都可表示为n维空间中的一个向量点.
从而文档的匹配问题转化为向量空间中的向量匹配问题.
假设目标文档为U,未知文档为V,则夹角越小表示文档间的相似度越大.
相似度计算公式如下:similarity(V,U)=V*UV·U=mk=1!
wk·wimk=1!
w2kmi=1!
w2k"(1)高维向量的处理通常需要进行大量的计算,特别是当需要处理的文本数目比较多的时候,单靠一台计算机的处理很难在一个可接受的时间内完成.
而网格计算的出现,可以改善这种情况.
2网格计算及其工具2.
1网格计算介绍网格计算来源于分布式计算,它的主要目的是为了获得足够强的运算能力以满足用户的需要[2].
网格计算可以使人们更容易处理基于文本表示的信息.
在现在的文本分类系统中,比如搜索引擎,其处理方式过于集中化,为了索引一个文本,必须先将其下载下来,然后进行处理并储存,所有的工作都在同一个地方处理.
但是在某些情况下,集中化处理的方式并不能提供非常好的效果,比如当需要处理的资源过于分散、文本数据量过大、或者文本是动态的并且随时间变化比较频繁的时候,集中化处理的代价非常昂贵.
因此,为了充分挖掘数据的价值,可使网格计算来改进现有的文本分类系统.
2.
2网格工具本文中实验所采用的网格环境是一个开源的网格计算在文本分类中的应用杜志文曾文华(厦门大学软件学院智能信息技术福建省重点实验室,福建厦门361005)摘要:文本分类,是一种对文档进行自动标记类别的技术.
它是文本挖掘中的一个核心任务,也是近年来数据挖掘中的一个研究热点.
在文章本分类中,所要处理的文档集中包含了很多特征,而分类算法中对于这些特征的处理和识别又需要进行大量的计算,目前尽管分类算法的准确率可以达到很高的水平,但分类算法的速度却因为受到硬件条件的限制而没有得到有效的提高,而网格计算可以弥补这一点缺陷.
文章对传统的向量空间分类算法进行改进,并在Alchemi网格计算平台下测试,发现在网格环境下,文本分类的速度得到很大的提高.
关键词:文本分类,网格计算,并行计算中图分类号:TP391文献标识码:A文章编号:1000-7180(2006)S0-0221-02ApplicationofGridComputinginTextCategorizationDUZhi-wen,ZENGWen-hua(IntelligentInformationTechnologyLaboratory,SchoolofSoftware,XiamenUniversity,Xiamen361005,China)Abstract:TextCategorization(TC)isatechniqueofassigningadocumentintopredefinedclass.
ItisacoretaskofTextMining,andalsoaresearchhotspotindataminingrecently.
ButinTextCategorization,thecorpus(agroupofdoc-uments)isalwayscontainingtoomuchfeatures,whichneedlotsofcomputingtimeincategorizealgorithm.
Althoughtheaccuracyofthecategorizealgorithmcanreachahighlevel,thespeedofthealgorithmislimitedbythehardwaresitua-tion,gridcomputingcancoverthisdisadvantage.
Inthispaper,wedoamodificationtothetraditionalVSMcategorizealgorithm,anddoatestbaseonAlchemigridcomputingenvironment,findthespeedofthealgorithmisboostedhighly.
Keywords:Textcategorization,Gridcomputing,Parallelcomputing221微电子学与计算机2006年第23卷·增刊网格项目Alchemi[5].
Alchemi提供了一组运行库和工具使得网格环境能够部署在微软的.
NET平台下.
它支持传统的任务调度算法并且通过一种多线程的编程方式确保计算任务可从一台计算机发布到网格环境中去.
使用时,需要一台计算机安装Al-chemiManage作为任务调度服务器运行,而其它的计算机安装AlchemiExecutor作为计算资源使用.
3算法描述和改进在文本分类中,使用最多的一类算法是向量空间法.
向量空间分类算法[3]分为训练和分类两个阶段.
在训练阶段中,首先定义类别集合C={c1,c2,…,cm},这些类别可以是层次性型也可以是并列的.
然后给出训练文档集合D={s1,s2,…,sm},每一个训练文档sj被标识上所属类别标识cj.
最后统计D中所有文档的特征矢量V(sj),确定代表C中每一个类别si的特征向量V(cj).
在分类阶段,首先对测试文档集T={d1,d2,…,dn}中每一个待分类文档dk,计算其特征向量与每一个V(cj)之间的相识度similarity(dk,cj),然后选取相似度最大的一个类别argcimaxcjsimilarity(dk,cj)作为dk所属的类别.
在特征权重的计算上,可以采用TF-IDF(TermFrequency-InverseDocumentFrequency)公式作为特征权重的计算公式[2].
Salton在1987提出的TF-IDF公式如下所示:wik=tfk(di)*lgNNk+"#m05.
结合Alchemi工具的特点,在改进后的算法中我们对传统的算法进行划分,将其中可以进行并行处理的部分提取出来,发布到网格中进行计算[4].
可以发现,在计算完每一个类的平均向量以后,可以将接下来测试文本特征向量与类的平均向量的比较操作进行并行化处理.
对于每一个并行化操作,其任务是执行所有测试文本对于某一个具体类别的比较任务,执行完毕后将比较的结果返回,进行统计,并最终确定每一个测试文本所属的类别.
由于在分布式环境下,每一个并行化操作都需要取得所有测试文本的数据才能进行比较,而当测试文本的数量比较多的时候,传送数据会花费很长的时间,因此可以对每一个并行化操作中所处理的测试文本数设定一个阈值,其所处理的文本数不高于该阈值,如果超过的话,便新建一个线程去处理额外的文本.
这样可以将每一个并行化操作按照阈值划分为更小的并行化操作.
改进后的算法流程图如图1所示.
4实验结果实验采用TanCorp-12文本分类语料库作为数据集使用.
该语料库包含14150篇文档,共12个类别.
从中按照3:1的比例划分训练数据集和测试数据集.
使用4台计算机进行网格环境的配置,其中一台作为任务调度服务器,其余三台作为计算资源使用.
每一台计算机均采用Pentium43G处理器,配置1G内存.
实验中,对于两种算法不同维度下的测试结果,都采用三次测试取其平均值的做法,这样可以保证测试的结果接近最真实的情况.
图2为在不同维度下两种算法耗时的对比.
从图2中可以看出,当维度小于2000时,传统向量空间算法花费的时间比改进后的算法时间要小,这是因为网格环境中传输数据需要一定的时间,所以改进后的算法在处理时间上需要耗费比传统算法更长的时间.
但当维度继续增大的时候,改进后的算法效果非常明显,而且随着维度的增大,算法的运行时间呈线性增长的趋势,所消耗的时间比传统的分类算法要少很多.
(下转第225页)2222006年第23卷·增刊微电子学与计算机5结束语文本分类在各个领域都有着广阔的应用前景,但由于文本自身的特点使得文本分类系统的速度一直不能得到有效的提高.
本文对传统的向量空间算法进行改进,将其引入网格环境中进行计算.
实验证明,基于网格环境的文本分类算法可以提高文本分类的速度,在算法的总体时间性能上,网格环境下的文本分类算法有着很明显的优势.
参考文献:[1]韩家炜,孟小峰,等.
Web挖掘研究.
计算机研究与发展,2001,38(4):405~411[2]肖连兵,黄林鹏.
网格计算综述.
计算机工程,2003,28(3):1~3[3]薛为民,陆玉昌.
文本挖掘技术研究.
北京联合大学学报(自然科学版),2005,19(4):59~63[4]SilvaC,etal.
Speed-uptextcategorizationinagridcom-putingenvironment.
ICMLA,2005:6[5]Alchemi.
http://www.
alchemi.
net/作者简介:杜志文男,硕士研究生.
研究方向为Web挖掘、企业信息门户.
曾文华男,教授,博士生导师.
研究方向为网格计算、智能控制及数据挖掘.
用户请求.
GRSUserAgent将用户资源请求数量矩阵R与GRS_D数据库资源数量矩阵D匹配,为用户提供匹配结果信息,由用户决定接受、取消或修改资源请求.
最后,GRSUserAgents根据用户的资源选择确认信息,为用户作业请求资源绑定,以完成本次共享资源访问.
作业完成后,需修改用户资金帐户信息及修改更新GRS资源信息.
一般来说,GRS支持资源信息的动态修改和更新,比如说,可约定GRS的更新周期.
网格的动态特性,决定了用户在网格中的状态可能随时进入或撤消,然而,一旦用户作业与所分配的资源绑定,而资源提供者又要撤消其共享资源,这将引起较大的系统开销.
所以,需要协商一种机制,来制约网格资源提供者的违约行为.
4结束语本文提出了基于GRS的网格资源分配与日俱增管理模型,并给出了模型的形式化描述与模型执行的形式化描述.
同已有的几个模型比较,优点是显而易见的,即网格共享资源用户可根据GRS的共享资源挂牌标价自由选择资源、符合用户消费习惯,支持动态更新、用户选择范围更大,缩短了作业运行周期等.
因此,基于这些优点,本模型也不失为经济模型中较好的一个网格资源分配与管理模型.
参考文献:[1]RBuyya,HStockinger,JGiddyDAbramson.
EconomicmodelsformanagementofresourcesinPeer-to-PeerandgridcomputingproceedingsoftheSPIEinternationalcon-ferenceoncommercialApplicationsforHigh-PerformanceComputing,2001[2]RBuyya,DavidAbramson.
Srikumarvenugopalthegrideconomy.
ProceedingsoftheIEEE.
March2005,93(3):698~713[3]JiadiYu,MingluLi,YingLi,etal.
Aframeworkforprice-basedresourceallocationonthegrid.
PDCAT2004,LNCS3320,2004:341~344[4]KarlCzajkowski,IanFoster,CarlKesselman.
Agreement-basedresourcemanagementproceedingsoftheIEEE.
March2005,93(3):631~643[5]IanFoster,CarlKesselman.
Thegrid2Blueprintforanewcomputinginfrastructure.
publishedbyelsevierInc.
2004[6]JoshyJoseph,CraigFellenstein.
Gridcomputing.
PearsonEducation,Inc.
,publishingasPrenticeHallPTR.
2005:36作者简介:李名标男,副教授.
研究方向为分布与并行计算、网格计算.
(上接第222页)225