搜索
龙源期刊网平台的文本聚类研究与实现作者：陈嘉勇来源：《中国管理信息化》2009年第21期[摘要]文本聚类是文本挖掘领域的一个重要研究分支,是聚类方法在文本处理领域的应用。本文首先对基于空间向量模型的文本聚类过程做了较深入的讨论和总结。另外,本文回顾了现有的文本聚类算法,以及常用的文本聚类效果评价指标。在研究了已有成果的基础上,本文利用20Newsgroup文本语料库,针对向量空间表示模型,在开源的数据挖掘平台WEKA上实现了文本预处理和k-means聚类算法,并根据实际聚类效果,就文本表示、特征选择、特征降维等方面提出优化方案。[关键词]文本挖掘;文本聚类;向量空间模型;WEKAdoi:10.3969/j.issn.1673-0194.2009.21.003[中图分类号]TP393[文献标识码]A[文章编号]1673-0194(2009)21-0009-041引言近年来,随着互联网的大规模普及和社会信息化程度的提高,非结构化的文本数据成为了信息最重要的载体,研究表明信息有80%包含在文本数据中[1],这使文本挖掘[2]成为数据挖掘领域中一个日益流行且重要的研究方向。在日常工作中,人们经常遇到的一个问题就是,如何对文本进行分类、比较,评估文本的相关性和重要性,以及发现众多文本的模式与趋势。延续数据挖掘的思想,人们自然将解决这一问题的目光投向文本挖掘中与分类相关的技术。要实现对大量文本的自动分类,可以采用文本分类和文本聚类两种方法。在信息瞬息万变的今天,经常会出现新的数据很难用已有的分类体系来处理,如果重新进行分类,就必须重新建立分类好的训练文档集,而获得大量带有类别标注的样本的代价是很大的。这时使用聚类的方法就显得很重要,因为作为一种无监督的机器学习方法,文本聚类由于不需要训练过程,以及不需要预先对文档手工标注类别,具有一定的灵活性和较高的自动化处理能力[3]。据数据挖掘著名网站Kdnuggets的调查,在最近的6个月中,使用开源的数据挖掘工具的人(占使用商业和开源工具总数的36%),其中的5%左右在使用WEKA工具进行数据挖掘,11%左右在使用基于WEKA构建的RapidMiner工具,如图1所示。由此可见,WEKA作为基于Java环境下开源的机器学习和数据挖掘工具的元老,英勇不减当年。本文基于开源的WEKA机器学习平台,探索了利用WEKA进行文本聚类的全过程。龙源期刊网文本聚类的基本思想文本挖掘(TextMining)[4]是指从大量文本数据中抽取事先未知的可理解的最终可用的知识的过程。作为文本挖掘的重要分支,文本聚类主要是依据Hearst等人证明的“聚类假设”:同类的文本相似度较大,而不同类的文本相似度较小[5]。2.2文本聚类的过程目前,文本聚类的途径一般是将非结构化问题结构化,利用现有的数据挖掘技术进行聚类。该途径的基本思路是:首先进行分词、特征表示、提取等处理,将文本用结构化的形式来描述;然后根据应用需求,选择或设计聚类算法;最后将所得到聚类效果进行评估,不断改进聚类过程。具体过程如图2所示。图2文本聚类的过程3文本聚类技术研究3.1文本预处理文本预处理是把文本表示成聚类算法可以处理的形式,包含特征表示和特征提取两个阶段。目前文本特征表示模型有向量空间模型、布尔模型、概率检索模型、语言模型等,其中向量空间模型最为流行。在向量空间模型中,文档集C中的每个文档Dj都是向量空间中的一个特征向量,且所有文档的特征向量都具有相同的维数n,该维数是所有文档中不同特征项的总数目。文档Dj的特征向量可以用文档中的特征项Ti及其权重Wij来表示:V(Dj)={T1,W1j;T2,W2j;…;Tn,Wnj｝龙源期刊网方法的标准定义:Wij=TFij×IDFi=TFij×logN/DFi其中,N为文档集C中的文档总数目,TFij为特征项Ti在文档Dj中出现的次数,DFi为文档集C中包含Ti的文档数目。特征提取也被称为特征降维,分为特征选择和特征抽取两种主要方法。在对文本挖掘过程中,需要考虑多个因素的影响,将特征选择和特征抽取有效地结合起来,联合降低特征维数。3.2文本聚类算法目前有多种文本聚类算法,根据算法的思想大致可分为:3.2.1划分方法(PartitioningMethod)k-means算法是最常见的划分方法,比较著名的算法还有PAM、CLARA、CLARANS和EM等。3.2.2层次方法(HierarchicalMethod)层次聚类可以分为两种:凝聚层次聚类和划分层次聚类。近年来出现的新算法包括CURE、ROCK、Chameleon和BIRCH。3.2.3基于密度的方法(Density-BasedMethod)为了发现任意形状的聚类结果,提出了基于密度的方法,它将簇看作是数据空间中被低密度区域分割开的高密度区域。常见的方法有DBSCAN、OPTICS和DENCLUE等。3.2.4基于网格的方法(Grid-BasedMethod)基于网格的聚类算法是采用一个多分辨率的网格数据结构,将数据空间量化为若干单元,形成一个网格结构,所有的聚类操作都在此网格上进行。典型的基于网格的聚类方法有STING、WaveCluste和CLIQUE等。3.2.5基于模型的方法(Model-BasedMethod)典型的基于模型的聚类方法有统计学方法COBWEB和CLASSIT、AutoClass,神经网络方法SOM、ATR和LVQ。其他常见方法还有基于图论的聚类算法、基于核的聚类算法、模糊聚类算法等。文献[6]对聚类算法做了全面的描述。龙源期刊网文本聚类效果评估在文本聚类算法实施之后,需要对聚类效果进行评估。常用评测指标是查准率、查全率及F值[7]。本文用F值指标来评价文本聚类的效果。F值组合了信息检索中查准率与查全率的思想,需要查准率和查全率都很高时,F值才能得到较高的值。对于一个聚类i和一个分类j的P(precision)与R(recall)定义为:P=Precision(i,j)=Nij/Ni,R=recall(i,j)=Nij/Nj。其中,Nij是在聚类i中分类j的数目;Ni是聚类i中所有对象的数目;Nj是分类j中所有对象的数目。则分类j的F值定义为:F(j)=。对分类j而言,哪个聚类的F值高,就认为该聚类代表分类j的映射。对聚类结果来说,其总F值可由每个分类j的F值加权平均得到:F=。其中,|j|为分类j中所有对象的数目。F值越高,说明聚类的效果越好。4基于WEKA的文本聚类4.1WEKA概述WEKA作为一个开源的数据挖掘工作平台,集合了大量能承担数据挖掘任务的机器学习算法,包括对数据进行预处理、分类、回归、聚类、关联规则以及在新的交互式界面上的可视化。WEKA提供了4种用户界面,分别是Explorer、Experimenter、KnowledgeFlow和SimpleCLI。4.2数据的准备本次实验采用的语料库是20Newsgroups的一部分,从其中选择了3类文本数据,每类中都随机选择了100篇文档。由于本实验是利用WEKA进行文本聚类,因此需将文本数据转换成WEKA所能识别和处理的ARFF格式。ARFF(Attribute-RelationFileFormat)[8]文件是WEKA的文件格式。将文本数据转化为ARFF格式需要用到WEKA中的TextDirectoryLoader转换器。龙源期刊网文件中的文本数据转换为空间向量模型,它同时拥有分词、特征表示、特征提取等功能。在Explorer中的Reprocess界面导入ARFF文件,选择StringToWordVector过滤器,再设置相关参数。本文通过两次实验,设置不同参数,尤其是对特征降维参数的调整,得到两个预处理结果供文本聚类算法使用。将两种参数分别应用到ARFF文件后,就会生成用向量空间模型表示的新的文件。去除类标记后,分别保存。4.4聚类算法本实验尝试用k-means算法进行本文聚类。进入Explorer中的Cluster界面,选择WEKA提供的聚类算法ClustersSimpleKMeans,然后设置参数为SimpleKMeans-N3-Aweka.core.EuclideanDistance-Rfirst-last-I500-S10,应用后,右键点击两次聚类结果的Visualizeclusterassignments分别出现图3和图4所示的结果。图3实验1聚类效果图图4实验2聚类效果图4.5聚类评估用F值对两次实验的聚类结果进行评估,首先计算查准率和查全率,如表1所示。表1查准率和查全率的计算结果然后计算各类的F值,加权平均后得到聚类结果的总F值,如表2所示。表2F值的计算结果5实验结果分析从聚类评估的结果可以看出,实验2在对实验1的文本预处理阶段进行了参数调整,特别是在特征降维上的参数调整,使F值得到了提高,即聚类效果得到了提高。因此,我们基本上验证了文献[9]的结论:用向量空间模型得到的特征向量的维数往往很高,高维的特征对即将进行的文本聚类未必全是重要的和有益的,而且还会加剧机器学习的负担。龙源期刊网结束语文本聚类是文本挖掘中一些关键技术的基础,在文本挖掘领域有着十分重要的作用。将来需要做的工作有:①发展全新的非结构化文本的聚类算法;②对WEKA进行二次开发,探索将新的文本聚类算法嵌入到WEKA,并与平台上原有聚类算法进行性能对比;③将文本挖掘与中文自然语言处理、计算语言学等有效集成,能有效地处理中文文本数据。主要参考文献[1]Ah-HweeTan.TextMining:TheStateoftheArtandtheChallenges[C]//ProceedingsofthePAKDD,1999.[2]FeldmanR,DaganI.KnowledgeDiscoveryinTextualDatabases(KDT)[C]//ProceedingsoftheFirstInternationalConferenceonKnowledgeDiscoveryandDataMining(KDD-95),Montreal,Canada,AAAIPress,1995:112-117.[3]郭建永.聚类分析在文本挖掘中的应用与研究[D].无锡:江南大学,2008.[4]MichaelWBerry,MaluCastellanos.SurveyofTextMiningII:Clustering,Classification,andRetrieval[M].NewYork:Springer,2007.[5]MartiHearstandJanPedersen,ReexaminingtheClusterHypothesis:Scatter/GatheronRetrievalResults[C]//Proceedingsofthe19thAnnualInternationalACM/SIGIRConference,Zurich,August1996.[6]RXu,DWunsch.SurveyofClusteringAlgorithms[J].IEEETransactionsonNeuralNetworks,2005,16(3).[7]AyadH,KamelMS.TopicDiscoveryfromTextUsingAggregationofDifferentClusteringMethods[M].London:Springer,2002.[8]WittenIH,FrankE.DataMiningPractica