【www.zhangdahai.com--国旗下演讲稿】
摘 要：为在中文网页分类时降低特征向量的维度、提高分类的精度，采用一种基于关联的特征选择（Correlation�basedFeatureSelection，CFS）与遗传算法（GeneticAlgorithm，GA）相结合的方法进行特征选择.在该算法中，特征子集被当作GA中的一个染色体进行二进制编码；利用CFS启发值作为GA的适应度函数对个体进行评价；CFS值越大的个体遗传到下一代的概率越大.结合GA的全局搜索特性，该算法可保证所得特征子集是全局最优的.利用weka平台，对搜狗实验室提供的中文网页数据集进行实验.结果表明，该算法能有效降低特征空间的维度、提高分类精度.
关键词：中文网页分类；特征选择；基于关联的特征选择算法；遗传算法
中图分类号：TP393.092；TP183 文献标志码：A
ChineseWebpageclassificationbasedonCFS�GA featureselectionalgorithm
YUChunping，HUANGXiaoxia
（InformationEngineeringCollege，ShanghaiMaritimeUniv.，Shanghai201306，China）
Abstract：ToreducethedimensionofthefeaturespaceandimprovetheprecisionofChineseWebpage classification，amethodbasedonCorrelation�basedFeatureSelection（CFS）andGeneticAlgorithm（GA）isusedintheprocessoffeatureselection.IntheCFS�GAalgorithm，afeaturesubsetisregarded asachromosomewhichisthenperformedinbinaryencode，andCFSisusedasGA’sfitnessfunctionto evaluatethechromosome.ThegreatertheCFSvalueis，thegreatertheprobabilitythatindividualsinherit tothenextgenerationwillbe.CombiningwithGA’sglobalsearchcharacter，thealgorithmcanensure thatthefeaturesubsetisglobaloptimum.ExperimentisdoneonwekaplatformwiththeChineseWeb pagedatasetprovidedbytheSougoulab.Theresultshowsthatthisalgorithmcanreducethedimensionof thefeaturespaceeffectivelyandimprovetheprecisionoftheclassification.
Keywords：ChineseWebpageclassification；featureselection；correlation�basedfeatureselection；ge�neticalgorithm
0 引 言
自进入信息化时代以来，因特网上的网页数量增长迅猛.为了提高信息的检索效率，很有必要对因特网上的一些网页进行分类.尽管目前有Google，Yahoo，搜狐等分类目录式的中文网站目录，但由于其均为人工编纂，效率低下，而且更新速度慢，无法满足当前因特网对信息实时性的要求.［1］因此，网页自动分类的研究对基于内容的信息检索、Web数据挖掘具有深远的意义.
中文网页分类一般包括预处理、特征选择和构造分类器等3个阶段.［2］预处理包括文本标记（html标签和JavaScript代码）的处理、分词处理和停用词处理.对中文网页中的海量信息进行预处理后所形成的特征向量的维数高达几万、甚至几十万，这无疑会造成维灾难.这些高维数据中含有大量的噪声以及与类别不相关的信息，用其直接进行分类既降低分类效率又影响分类的精确度，因此特征选择成为中文网页分类中的一项关键技术.［3］特征选择是一个NP难题.［4］按照分类算法评价标准可以将特征选择算法分成两大类：过滤型（filter）和封装型（wrapper）.过滤型不考虑具体的学习算法，而是直接从原始数据出发得到各个特征的贡献评价；封装型则考虑具体的学习算法，由分类器的结果评价特征好坏.过滤型算法可以很快从原始特征集合中选出较优的特征子集，但是该特征子集并不是最小的，且其中还可能含有与类别信息不相关的噪声，从而与后续的分类算法产生较大偏差.封装型算法具有很好的降维效果，选择结果较好，但因其与特定的学习算法有关，特征选择过程耗时较长.［5�6］
常用的文本分类算法有信息增益（IG）、χ2统计（CHI）、互信息（MI）和文档频率（DF），其中IG和CHI的性能较好［7�8］.基于关联的特征选择（Correla�tion�basedFeatureSelection，CFS）作为一种过滤型算法，是以属性与类别之间的相关性以及属性与属性之间的冗余度为衡量依据的［9�11］，该算法虽然具有较好的降维能力，但其所得到的解不一定是全局最优的.在文本分类中，遗传算法（GeneticAlgorithm，GA）因其具有全局搜索特性常被作为一种封装型算法对特征进行降维处理.［12�14］本文将CFS与GA相结合，以CFS的相关度度量作为GA的适应度函数评价遗传算法中的每个新个体.实验证明，利用该算法进行特征选择，可以有效降低特征向量的维度、减少学习分类器所需的数据量，具有泛化能力强、可找到全局最优解等优点.
1 基于CFS�GA的中文网页分类
1.1 CFS
CFS是一种经典的过滤型特征选择算法，其启发式地评价单一特征对应于每个类别的作用，从而得到最终的特征子集.其评估方法如下：
1.2 基于CFS�GA的中文网页分类
在运用GA进行特征选择时，常将其自身设计成封装型特征选择算法.GA在运行中基本上不需要外界信息，只需要依据适应度函数控制种群的更新，因此适应度函数的设计对特征子集的选择至关重要，关系到特征选择时的收敛速度和找到的最优解.在基于GA的封装型特征选择中，常采用学习算法的分类精度和最终选择出的特征子集的大小作为适应度函数.尽管该方法可以利用GA的全局搜索能力找到全局最优解，但是在处理大规模数据时效 率极其低下，且复杂度较大.因此，考虑将GA设计成一种过滤型的特征选择算法，即将适应度函数设置成一种过滤型的算法，从而使其具有GA的全局最优特性和过滤性算法的高效率特性.接着就是考虑选用何种过滤型算法进行特征选择.
在遗传算法的遗传操作中，比较优秀的个体需要满足两个特性：（1）个体对分类的贡献要尽可能大；（2）个体中包含的特征数要尽可能小（要使这样的个体能够遗传到下一代，就要使其适应度值比较大）.因此，需要选择满足上述两个特性的过滤型算法作为适应度函数.
在常用的文本特征选择算法中，IG和CHI的性能较好，且两者性能大体相当.［7�8］IG通过信息增益度量属性与属性之间的相关性，尽管能起到一定的降维作用，但其所选特征未必对分类的贡献大，且其分类性能受样本分布的影响；而CHI只统计某个特征项是否出现，却不考虑该特征项出现的次数，因此该算法对低频词有一定的夸大作用.综合看，这两种效果好的过滤型算法都不能满足上述两个特性.
文献［9］提出的CFS通过计算属性与属性之间的冗余度以及属性与类别之间的相关度来度量所选特征的优劣.属性与类别的相关度越大（即对分类的贡献越大）、属性与属性的冗余度越小（即所选特征数量越小），CFS的启发值就越大.从CFS的特性来看，它完全满足比较优秀个体的特性.因此，本文将GA与CFS相结合（CFS�GA），将特征子集看作GA中的个体，利用CFS的启发值作为GA的适应度函数.启发值越大的个体被遗传到下一代的概率就越大，而CFS启发值越大表明特征与类别的平均相关性越大、特征与特征之间的平均冗余度越小，因此将CFS启发值大的个体遗传到下一代就可保证所选个体中特征与类别的相关性大、特征维度小.结合GA的全局搜索特性，本文算法可以得到全局最优解.
CFS�GA算法设计主要包括编码方案、选择算子、交叉算子和变异算子等4个问题.编码方案中采用经典的二进制编码：假设有n个候选特征，则染色体长度为n，用n位的0和1构成的字符串表示一种特征组合；第i位为1表示存在该词，第i位为0表示不存在该词.对特征子集进行选择时，采用经典的轮盘赌选择算子，每个个体被选中的概率与其适应度值成正比.在进行交叉时，采用单点交叉，即在属性对中随机产生交叉点，然后互换交叉点后的部分结构，产生新个体.变异采用基本位变异算子，即在二进制编码中，0变1，1变0.在交叉率和变异率
2.5 实验结果分析
从表1和2可知：（1）经过特征选择后，分类正确率显著提高，因此特征选择在中文网页分类中意义重大；（2）CFS�GA降维能力好，其分类性能也优于IG和CHI，这是因为在选择特征时，本文算法不仅考虑特征与类别之间的相关性，而且考虑特征与特征之间的冗余性，从而能有效降低最优特征空间的维度；（3）IG与CHI性能大体相当，这与文献［7�8］所得的结论基本一致.总之，本文提出的算法对中文网页自动分类具有一定的实用价值.
3 结束语
特征选择的目的是降低特征向量空间的维度，提高分类效率.本文将CFS与GA相结合，用CFS评价作为GA适应度函数来评价个体.实验证明，这种特征选择算法能有效降低特征空间的维度，且其分类性能与当前比较成熟的特征选择算法相比也有所提高.
进一步工作可以考虑网页的结构特征.网页含有丰富的结构信息，除纯文本之外，还有其他一些对分类有贡献的信息：如用Head和Title标注网页的标题和段落子标题，meta标记中的name属性和content属性值是对网页主题的描述，网页中的超链接指向的内容有可能是与该网页主题相关的内容.在下一步的工作中，可以利用这些信息提高分类的准确率.
参考文献：
［1］刘超.中文网页自动分类研究及分类算法的设计与实现［J］.中国科技论文在线，2003：1�2.
［2］冯是聪，张志刚，李晓明.一种中文网页自动分类方法的实现及应用［J］.计算机工程，2004，30（5）：19�20.
［3］CUIZifeng，XUBaowen，ZHANGWeifeng，etal.CLDA：featureselectionfortextcategorization［C］／／ICSC07′ProcIntConfonSemanticCompu�ting.Washington，DC，USA，2007：703�704.
［4］叶吉祥，龚希龄.一种快速的Wrapper式特征子集选择新方法［J］.长沙理工大学学报：自然科学版，2010，7（4）：69.
［5］ELALAMIME.Afiltermodelforfeaturesubsetselectionbasedongeneticalgorithm［J］.Knowledge�BasedSystems，2009，22（5）：357�358.
［6］HUANGCheenjung，YANGDianxiu，CHUANGYita.Applicationofwrapperapproachandcompositeclassifier［J］.ExpertSystemswithApplica�tion，2008，34（4）：2871.
［7］单松巍，冯是聪，李晓明.几种典型特征选取方法在中文网页分类上的效果比较［J］.计算机工程与应用，2003，39（22）：147.
［8］YANGYiming，PEDERSENJO.Acomparativestudyonfeatureselectionintextcategorization［C］／／ProcACMSIGIRConfonRes＆DevinIn�formRetrieval（SIGIR01），2001.
［9］HALLMA.Correlationbasedfeatureselectionformachinelearning［D］.Hamilton，NewZealand：UnivofWaikato，1999：51�69.
［10］HALLMA，SMITHLA.Featrueselectionformachinelearning：comparingacorrelation�basedfilterapproachtothewrapper［C］／／ProcTwelfth IntFLAIRSConf.Florida，USA，1999：247�254.
［11］孙宁青.基于神经网络和CFS特征选择的网络入侵检测系统［J］.计算机工程与科学，2010，32（6）：38.
［12］郑滨，金永兴.基于属性约简的海事人为失误致因分析［J］.上海海事大学学报，2010，31（1）：92�93.
［13］任江涛，孙婧昊，黄焕宇，等.一种基于信息增益及遗传算法的特征选择算法［J］.计算机科学，2006，33（10）：194.
［14］宋淑彩，庞慧，丁学钧.GA�SVM算法在文本分类中的应用研究［J］.计算机仿真，2011，28（1）：223�225.
［15］熊忠阳，刘道群，张玉芳.用改进的遗传算法训练神经网络构造分类器［J］.计算机应用，2005，25（1）：32�33.
［16］黄晓霞，程论.综合评价与数据挖掘的比较［J］.上海海事大学学报，2007，28（4）：55�56.
（编辑 贾裙平
