doc 一种统计降维和Kohonen网络相结合的文本聚类方法.doc

一种统计降维和Kohonen网络相结合的文本聚类方法第25卷第10期2005年10月计算机应用ComputerApplicationsVol_25No.10Oct.2005文章编号:10019081(2005)10232803一种统计降维和Kohonen网络相结合的文本聚类方法王智勇,王正欧(天津大学系统工程研究所,天津300072)(wzhyon)摘要:提出了一种基于词条互信息(WMI)值的统计降维和Kohonen网络(SOFM网)相结合的文本聚类方法,WMI值的方法侧重考虑文本特征项之间的互信息进行降维,可提高特征选择的效率,并使其更趋实用化.采用Kohonen网络进行文本聚类,其学习率函数是随时间单调下降的退火函数,实验结果表明了这种结合方法较一般的降维方法得到的聚类结果具有较高的聚类精度.关键词:词条互信息;统计降维;Kohonen网络;文本聚类中图分类号:TP18文献标识码:ANewtextclusteringmethodbasedonstatisticalreductiondimensionandKohonennetworkWANGZhiyong,WANGZhengOU(InstituteofSystemsEngineering,Tianjinuniversity,Tianfin300072,China)Abstract:AnewtextclusteringmethodbasedonWMI(WOrdsmutualinformation)statisticalreductiondimensionapproachandKohonennetwork(SOFMnetwork)wasproposed.Thismethodconsideredthemutualinformationbetweentextfeaturesandimprovedtheefficiencyofreductiondimensionlargely.TextclusteringusedKohonennetworkwhoselearningratewasdroppedwithtime.Theexperimentsindicatethattheclusteringresultobtainedusingthiscombinedmethodhasmuchhigherprecisionthanthatusinggeneralreductiondimensionapproach.Keywords:WMI;statisticalreductiondimension;Kohonennetwork;textclustering0引言文本自动聚类研究成为当前数据挖掘的一个重要课题,是文本有效管理和检索海量Iintemet文本信息的基础.文本在通常的向量空间模型VSM(VectorSpaceMode1)中表示的向量维数一般为几千维,甚至几万,几十万维,这样无论从空间还是从时间考虑,计算的复杂度相当大,实现聚类有很大的困难,因此,需要进行有效的降维方法的研究.整个降维的过程也就是特征选择的过程,是从文档的一组特征中选择出一部分最具代表性的特征,以实现维数约简,并降低计算的复杂度.同时由于高维数据通常带有大量冗余的带噪声的数据,适当降维后也可提高聚类的准确率.对于文本这类维数非常高的矢量空间,常规的维数降低方法往往代价过于昂贵,如多元统计分析中的主成成分分析方法和LSI(隐含语义索引)方法.LSI方法虽然可以凸现文本中的隐含语义联系,可以过滤噪声和对检索结果影响不大的因素,但是对于像文本这一类的高维的矩阵,有文献推导出其计算复杂性为:O(mac),其中m和n是文档矩阵的行和列的维数,c为文档矩阵每行非零元的个数,因而其计算量也是很高的.基于上述问题,本文提出了一种基于词条之间互信息(WordsMutualInformation,WMI)的统计的文本特征降维与Kohonen网络相结合的文本聚类新方法.基于WMI的降维方法是Sahami提出来的J.该方法应用统计方法进行特征向量的选择,采用特征词条之间的互信息作为评价函数,可有效地减少向量空间的维数,提高文本聚类的速度和精度.Kohonen网络采用的学习率函数是随时间单调下降的函数,使权值的调整更加有利于选择出相对于某一模式的获胜结点,进一步地提高了文本聚类的速度和精度.1基于wMI的统计降维方法1.1理论基础定义1设和是MI(X,)表示.定理1在由树形关系结构定义的概率分布中,由最大生成树MST定义的概率分布P()使D(P(X),P(X)收稿日期:20050412基金项目:国家自然科学基金资助项目(60275020)作者简介:王智勇(1980一),男,河北唐山人,硕士研究生,主要研究方向:神经网络,数据挖掘,文本挖掘;itigt(1938一),男,上海人教授,博士生导师,主要研究方向:神经网络,系统辨识,系统优化,控制决策及智能系统.第10期王智勇等:一种统计降维和Kohonen网络相结合的文本聚类方法2329最小.注:这里指图G的最大生成树MST(MaximalSpanningTree);P()指树形关系结构的实际概率分布.定理2l设森林F中结点之问边的权值用结点之间的互信息表示,森林F修剪掉一条边”得到森林F,满足V=rain(,J)的边”使得D(PF(x),P,(x)最小.表示结点i和结点的连接权值,E(1,2,i一1,i+1,1).推论3设最大生成树MST中结点之间边的权值用结点之问的互信息表示,MST修剪掉一条边得到森林F,满足=min(ViJ)的边”使得D(PF,PMST)最小.定理4t设图G中的一个结点代表文本的一个特征项,如果图G中的一个结点是孤立的,那么删除该结点并不会改变由Pc(.)?D(P.(.Ixi),Pc(一.)定义的边界相对熵.定理561边际相对熵等于条件互信息的和,即:_Pc(x.)?D(PG(x一.1xi),Pc(一.)=MI(X.;lX1,一,)1.2基于WM的统计降维算法1.2.1基于树形结构关系模型的MST算法.在MST算法中,首先根据定义2计算任意两个词条之间的互信息,然后建立文档特征项的完全图G,再根据定理1建立图G的最大生成树,结点之间边的连接权值等于MI(X.,),根据定理2和推论3修剪MST树,根据定理4去掉一部分特征项,从而达到特征选择的目的.在一篇文档中,执行MST算法的步骤如下:1)对于所有的词条.,()计算互信息,(,)2)建立图G的最大生成村MST,结点之间的连接权等于MI(.,)3F哪一MST,Rx4)While(IRI>K)doIF对于任意的结点,和其他的结点之间没有权向量连接.代表的特征项是ThenRR一X,l,F椰rF椰relse修剪掉,中的最小权值边K为需要保留的特征项的数目,是需要设定的闭值参数.1.2.2PIL(PairwisenteractionLimited)算法此算法不利用树形结构,而是考虑任意一个特征项对其他特征项的影响力,这种影响力可以用边际相对熵来度量.考虑到当特征项数目n比较大时,MI(;I一,一,.)计算的复杂度很大,因此,可以考虑一个相对简单的估计算法:MI(X.;lXl,.一-,+l,.1)=lJMI(X;)实际上,当每一对词条与剩余的其他词条独立时,上式是一个完全成立的等式.基于上述假设,可以提出另外一种特征选择的方法,因为假设任何一对特征项和其他的特征项是相互独立的,我们称基于这种假设的算法为关联限制(PairwiseInteractionLimited,PIL)算法.1)对于所有的词条,(i)计算互信息(,)2R3)While(IRI>K)do对于所有的R中的词条,计算MI(X.,x),结果赋R-I值给.一最小的的词条RR一X为需要保留的特征项的数目,是需要设定的阙值参数.1.2.3PIL算法的改进考虑到PIL算法中需要计算词条X和其他所有词条的互信息之和,然后选取阈值K进行特征选择.因为文档中的词条很多,我们只是考虑与词条互信息最大的6个词条的互信息之和,然后选取阂值进行特征选择.PIL算法的这种改进算法称为PIL一6算法.2自组织特征映射(SOFM)神经网络自组织特征映射网络(SerfOrganizingFeatureMap)又称Kohonen网络,这种网络模拟大脑的自组织映射的功能,是一种竞争式学习网络.自组织的过程实际上就是一种无指导的学习,一个Kohonen网络接受外界输入模式时,将会分为不同的对应区域,各区域对输入模式具有不同的响应特征,它通过自身训练,自动对输人模式进行聚类.Kohonen网络分为输人层和输出层两层.输人层接受输人模式,输人层神经元的个数与样本维数相等.输出层也是竞争层,神经元的排列有多种形式,如一维线阵,二维平面阵.定义3输入向量和输出结点q之间的余弦距离称为输出结点q和的相似度,记为Sire.即:s=产兰=(j=l)+()由于输人向量和神经元之问的连接权向量都是经过归一NN化的向量,即()=().=1,所以Sire=J1J1=/=1=?,即Sire-和G厂围的神经元进行权值调整,权值调整的范围即为最佳匹配结点的邻域,用来表示神经元和获胜神经元之间的拓扑距离.3结合S0FM和统计降维的文本聚类文本聚类是一种将文本集分组的全自动处理过程,是一种典型的无教师的机器学习问题,聚类的结果是使同组内的文本相似度最大,不同组内的文本相似度最小.SOFM网是一种较好的数据聚类工具,将其与统计降维方法相结合可以快速有效地进行文本聚类.2330计算机应用2005正SOFM文本聚类算法步骤如下:1)网络的构造.设定输入层神经元个,为文本集经过降维处理后的词条矩阵的维数,输出层神经元m个,采用m×1的二维平面阵结构.2)初始化.对输出层各权向量赋予0,1之间的小随机数并进行归一化处理,得到初始权向量矩阵W(0);建立初始优胜邻域,.(0)和学习率o(0),计数器置t=0.3)接受输入.从训练集中随机选取一个输入模式并进行归一化处理,得到输入向量.4)寻找最佳匹配结点w(j)?Vr计算,从中选择点积最大的获胜结点,.5)定义优胜邻域.(t),以为中心确定t时刻的获胜邻域,一般.(0)比较大,训练过程中,.(t)随着训练时间的延长逐渐收缩,最后只是对获胜结点的权值矩阵进行细微的调整,从而保证获胜结点对这一类输入模式具有最大的响应.6)权值调整.对获胜邻域,.(t)内的所有结点调整权值:(t+1)=W(t)+0(t,N(d)Wi.,(t)i:1,2,3,m;E.(t)o(t,N(d)是训练时间t和和N(d)的函数,N(d)是获胜邻域,.(t)内第个神经元与获胜神经元,之间的拓扑距离d的函数.采用0(t,N(d)=0(t)%e”,0(t)采用单调1下降的退火函数0()=lg(1+.÷).0(,N(d)是一种T,可变的学习速率,随着时间而衰减,随着拓扑距离的变大而减小,意味着在一次权值调整过程中,越接近最佳匹配结点的神经元的调整幅度越大,在同样的拓扑距离下随着时间神经元的调整幅度逐渐变小,最终获胜结点所连接的权向量便可以代表模式的本质属性.7)结束检查.SOFM网的训练结束是以学习率o(t)是否消减到某个预定的阈值为条件的,或者选定最大的训练次数,达到最大的训练次数,网络即停止训练.不满足停止条件返回2),每次调整的权值都需要进行归一化处理才可以进行寻找最佳匹配结点的点积操作.4买马令文本的结构化表示采用空间向量模型VSM,VSM中的向量采用常用的TFIDF(TermFrequencyInverseDumentFrequency)方法构造.实验的VSM模型矩阵是M×N的矩阵,其中M是指文本集的文档数目,N是指经过统计降维得到的文本的特征词条的集合,矩阵的每一个行向量代表一篇文档的输入模式.我们对VSM模型矩阵应用Kohonen网络进行文本聚类.文本集的一共包括300篇文档,分为教育,经济,军事,娱乐,体育五个子类,经过ZIPS法则处理后的词条是30870个.文章来源于http:/,w.sohu.corn.实验】:对于初始的词条矩阵D,采用ZIPS法则对词条进行修剪得到词条矩阵D,去掉一些停用词,应用T兀DF方法构造VSM模型,应用无监督的Kohonen网络进行聚类.实验2:对于初始的词条矩阵D,采用统计降维的MST算法对词条Ds进行维数约减得到词条矩阵DMsT,应用TnDF方法构造VSM模型,应用无监督的Kohonen网络进行聚类.实验3:对于初始的词条矩阵D,采用统计降维的PIL一6算法对词条D.进行维数约减得到词条矩阵DPII_一,应用TFIDF方法构造VSM模型,应用无监督的Kohonen网络进行聚类.实验4:对于初始的词条矩阵D,采用统计降维的PIL算法对词条D进行维数约减得到词条矩阵DPn,应用TFIDF方法构造VSM模型,应用无监督的Kohonen网络进行聚类.实验5:对于初始的词条矩阵D,采用目前认为较好的一种文本降维方法CHI算法对词条D.进行维数约减得到词条矩阵D,应用TFIDF方法构造VSM模型,应用无监督的Kohonen网络进行聚类.D的维数为200,画成直线只是用来作为评价的可见指标,85%和83%是在200维下的聚类结果.实验结果示于图1和图2.jNumberofFeatures图1样本准确度NUtuberofFeatures图2样本召回率图中BaseLine是实验1数据,MST是实验2数据,PIL一6是实验3数据,PIL是实验4数据,CHI是实验5数据.聚类评价指标采用准确率和召回率.图1和图2分别表示样本经过特征选择,特征项在50至500之间的聚类准确率和召回率.Bdine的数据不表示任何的特征选择的结果,画成直线只是用来作为评价的可见指标.实验结果表明MST算法和PIL_6算法表现出很好的降维质量,与前者比较,PIL算法的结果要逊色很多.在PIL_6算法中只是选择与词条互信息最大的六个词条加和作为指标函数,却表现出良好的结果,因此可以得出结论,选择有限的关联词条更有利于凸现文本特征项,同时从图中也可看出MST和PIL一6法降维性能高于通常采用的CHI值降维的性能.5结语本文提出了一种新的基于WMI值的统计降维法与Kohonen网络相结合的文本聚类方法,解决了由于文本维数过高而导致的Kohonen网络收敛速度慢,聚类准确度低的缺点,并且聚类结果表明这种降维方法较一般常用的降维方法(下转第2333页)第lO期吴勤等:基于Kohonen网络的软件可靠性模型选择2333的教学数据包.这20组数据记为D1,D2,.D20.其中D1,D2,D3是定义的基准数据,编码为DI:I,I,I,I,I,D2=2,2,2,2,2D3=3,3,3,3,3首先将给定的原始数据编码,编码后用Kohonen网络进行分析.为了说明聚类的效果,表2给出了本文的方法与工程上应用成熟的累加排序方法对这20组数据分析的结果对比,只有D7与DI7出现不一致,其错误率为10%,说明该方法是可行的.在实际使用的过程中可以结合多种选择模型的方法综合得出结论.本仿真采用了Matlab中的神经网络工具箱,通过运算发现,当训练70次左右的时候,其准确性最好.为了比较算法的优劣,除了利用Kohonen网络,还与目前对可靠性模型选择研究的高斯混合模型方法及比较误差系数法两种主要方法相比较.同样用上述20组数据与工程上应用成熟的累加排序方法进行比较.采用高斯混合模型方法计算错误率约为15%,采用比较误差系数方法的错误率为23%.证明了此方法的有效性与准确性.表2实验数据分类结果编号编码结果累加排序结果Kohonen网络分类结果编号编码结果累加排序结果Kohonen网络分类结果D111111JM(1)JM(1JD1113333YO(3)YO(3)D222222GO(2)GO(2)D1221211JM(1)JM(1)D333333YO(3)YO(3JD1333322YO(3)YO(3)D433312YO(3)YO(3)D1422311GO(2)GO(2)D521131JM(1)JM(1)D1512312GO(2)GO(2)1)621131JM(1)JM(1)D1612131JM(1)JM(1)D731213JM(1)GO(2)D1721213GO(2)JM(1)D823111JM(1)JM(1)D1823333YO(3)YO(3)13922221GO(2)GO(2)D1911123JM(1)JM(1)D1033l31YO(3)YO(3)D2013332YO(3)YO(3)4结语关于软件可靠性模型选择问题的研究已经有了一定的发展.本文提出的基于Kohonen网络的模型选择方法,是综合利用多种模型评价准则进行模型选择的一种尝试.该方法具有结构简单,计算速度快和计算精度高等特点,通过仿真试验证明了该方法的有效性和可行性,可适用于软件可靠性模型的选择,从而为软件模型的选择提供了一条新的思路.参考文献:1】汪浩,刘超,金茂忠.基于聚类思想的软件可靠性模型选择J】.计算UL32程与应用,2002,21(4):2124.【2】ELEWASA.DevelopmentofanEnvironmentforSoftwareReliabilityModelSelectionD】.Doctoralthesis.SchoolofEngineeringoftheAirForceinstituteofTcchnologyAirUniversity,ADA256609,1992:225.3】丛爽.神经网络,模糊系统及其在运动控制叶I的应用M】.合肥:中国科学技术大学出版社,2001.4】自瑞祥,惠鸿忠,宋辉.基于自组织映射神经网络的聚类分析系统研究J】.化工自动化及仪表,2004,31(5):2931.【5】LYUMR.HandbookofsoftwarereliabilityEngineering【M】.McGrawHillpublishing,1995.6】徐仁佐.软件可靠性模型与应用【J】.质量与可靠性,1994,18(31:2731.7】MUSSAJD.SoftwareReliabilityData.DACS,RADC【DB/OL1.ht.tp:/www.dacs.dtic.Mil/databases/sled/swre1.shtml,1980.【8】FlorinPOPENTIUYLADICESCU.PerformanceEvaluationofCom.putemCourses.TechnicalUniversityofDenmarklnformaticsandMathematicalModelling【EB/OL】.http:/ww.imm.dtu.dk./po.pentiu/pee/pec.html,2005.f9】宋晓秋.软件可靠性及维修性评估工具JJ.电子产品可靠性与环境试验,1999,24(3):1621.lO】黄智伟.软件测试和可靠性评估模型选择J】.电子计算机,1999,4(6):2426.l1】徐仁佐,袁凌,陈波.软件可靠性模型应用中的不一致性与软件可靠性专家系统J】.计算机应用与软件,2001,21(4):3641.l2】田涛,张凤呜,王听.一种基于模糊综合评判的软件可靠性模型选择方法J】.空军工程大学,2002,3(2):5659.l3】邹丰忠,徐仁佐.软件可靠性多模型综合评估【J】.同济大学学报,2002,30(10):11831185.【l4魏长春,张诤敏.趋向性分析在软件可靠性模型中的应用【J】.质量与呵靠性,2004,18(6):3841.(上接第2330页)(如CHI值法)有高得多的聚类精度,因而本文提出的方法较现有同类方法具有更大的优越性.本法较适用于文本数较多,互信息较充分的场合,是一种较为实用的文本聚类方法.参考文献:1】PALSK,eta1.Webmininginsoftcomputingframework:rele.vance,stateoftheartandfuturedirections【J1.IEEETransactionsonNeuralNetworks,2002,13(5):11631177.2】KASKIS.DimensionalityReductionbyRandomMapping:Eastsimi.1arityComputationforClustering【A】.ProceedingsofinternationalJointConferfenceonNeuralNetworks(IJCNN98)C】.IEEEServiceCenter,Piscataway,NJ,1998.413418.【3】KURIMOM.Fastlatentsemanticindexingofspokendocumentsbyusingself-organizingmapsA】.IEEEinternationalCmfferenceonA.45】6】7】8】coustics,SpeechandsignalProcessing(ICASSPO0)C】.IstanbuTurkey,2000.24252428.钱晓东,王正欧.基于SOM网络的随机映射文本降维方法fJ】.计算机应用,2004,24(5):5659.DAGANI,MARCUSS.Contextualwordsimilarityandestimationfromsparsedata【J】.ComputerSpeechandLanguage,1995,9:123152.SAHAMIM.UsingmachinelearningtoinformationaccessDJ.ADissertationofStandforduniversity,1998.KOHONENT.self-organizingmaps【M】.Springer,Berlin,1995.王明春,王正欧,张楷,等.一种基于CHI值特征选取的粗糙集文本分类规则抽取方法J】.计算机应用,2005,25(5):10261028