使用优化模拟退火算法的文本特征选择.pdf

82010，46（4）ComputerEngineeringandApplications计算机工程与应用

使用优化模拟退火算法的文本特征选择

朱颢东1，2，钟勇1，2
ZHUHao-dong1，2，ZHONGYong1，2

1.中国科学院成都计算机应用研究所，成都610041
2.中国科学院研究生院，北京100039
1.ChengduInstituteofComputerApplication，ChineseAcademyofSciences，Chengdu610041，China
2.TheGraduateSchooloftheChineseAcademyofSciences，Beijing100039，China
E-mail：[e-mail]

ZHUHao-dong，ZHONGYong.Textfeatureselectionbasedonimprovedsimulatedannealingalgorithm.ComputerEngi－
neeringandApplications，2010，46（4）：8-11.

Abstract：Intextcategorization，oneproblemisusuallyconfrontedwithfeaturespacescontaining10，000dimensionsandmore，
evenexceedingthenumberofavailabletrainingsamples.Inordertoenhanceoperatingspeedandreducememoryspaceoccu－
pied，afeatureselectionmethodbasedonanimprovedSimulatedAnnealingAlgorithmispresented.Inordertoavoidmissingcur－
rentoptimalsolution，thepresentedmethodisincreasedmemoryfunctiontorememberthecurrentbeststatesothatitbecomes
anintelligentalgorithm.Anadaptivetemperatureupdatefunctionandadual-thresholdaresetuptoreduceamountofcalcula－
tion，socanacquirequicklythefeaturesubsetswhicharemorerepresentative.Experimentalresultsshowthatpresentedmethodis
effective.
Keywords：textcategorization；featurespace；featureselection；simulatedannealingalgorithm

摘要：在文本分类中，特征空间维数通常高达几万，甚至远远超出训练样本的个数，这是一种十分普遍的现象。为了提高文本挖
掘算法的运行速度，降低占用的内存空间，提出了一种基于优化的模拟退火算法的特征选择方法。在该方法中，为避免遗失当前最
优解，增加了记忆功能，将当前最好的状态记忆下来，从而使得模拟退火算法成为一种智能化算法；设计了一个自适应温度更新函
数，并设置双阈值使得在尽量保持最优性的前提下减少计算量，从而较快地获得较具代表性的特征子集。实验结果表明该方法是
有效的。
关键词：文本分类；特征空间；特征选择；模拟退火算法
DOI：10.3778/j.issn.1002-8331.2010.04.003文章编号：1002－8331（2010）04-0008-04文献标识码：A中图分类号：TP301

在文本分类中，文本通常是以向量形式来表示的，其特点是局优化问题的目的，已广泛应用在函数优化、组合优化和数据
高维性和稀疏性[1-2]。而在中文文本分类中，通常采用词条作为最挖掘等领域。该文提出了一种基于优化的模拟退火算法的特征
小的独立语义载体，原始的特征空间可能由出现在文章中的全选择方法，该方法利用模拟退火算法极强的搜索能力以及优化
部词条构成。由于中文的词条总数有二十多万条，这使得其高维策略，来较快地获得较具代表性的特征子集。实验结果表明该
性和稀疏性更加明显，这样就大大限制了分类算法的选择空间，算法是有效的。
降低了分类算法的效率和精度。为此，寻找一种高效的特征选择
方法，以降低特征空间维数、避免维数灾难，提高文本分类的效1粗糙集基本理论
率和精度，成为文本自动分类中亟待解决的重要问题[3-5]。在设计适用于特征选择的模拟退火算法时要用到一些粗
模拟退火算法[6]是20世纪80年代初期发展起来的一种