基于CFS-GA 特征选择算法的中文网页自动分类

喻春萍，黄晓霞

(上海海事大学 信息工程学院，上海 201306)

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］.基于关联的特征选择(Correlation-based Feature Selection，CFS)作为一种过滤型算法，是以属性与类别之间的相关性以及属性与属性之间的冗余度为衡量依据的［9-11］，该算法虽然具有较好的降维能力，但其所得到的解不一定是全局最优的.在文本分类中，遗传算法(Genetic Algorithm，GA)因其具有全局搜索特性常被作为一种封装型算法对特征进行降维处理.［12-14］本文将CFS 与GA 相结合，以CFS 的相关度度量作为GA 的适应度函数评价遗传算法中的每个新个体.实验证明，利用该算法进行特征选择，可以有效降低特征向量的维度、减少学习分类器所需的数据量，具有泛化能力强、可找到全局最优解等优点.

1 基于CFS-GA 的中文网页分类

1.1 CFS

CFS是一种经典的过滤型特征选择算法，其启发式地评价单一特征对应于每个类别的作用，从而得到最终的特征子集.其评估方法如下:

假设属性为Y，y为Y 的每一个可能的取值，则Y 的熵的计算方法为

已知属性X，计算Y 的熵的方法为

差值H(Y)-H(Y|X)(即特征Y 的熵的减少量)可反映特征X 提供给特征Y 的附加信息，被称为信息增益.信息增益可反映属性X 提供给属性Y 的信息的多少，因此信息增益值越大，那么X 与Y 的相关度就越高.由于信息增益是一种对称性的测量方法，其缺点是倾向于选择那些有更多取值的属性.因此，为确保各个属性可相互比较，使不同的属性选择产生相同的效果，需要对信息增益进行归一化.这里使用对称不确定性方法将其归一到［0，1］.

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.在交叉率和变异率的选择方面，为了产生较多的新个体，同时不致过多地破坏较好的特征子集，交叉率一般在0.40～0.99之间选取，变异率一般在0.000 1～0.100 0 之间选取.CFS-GA 算法描述和基于CFS-GA 的分类模型流程见图1和2.

图1 CFS-GA 算法描述

图2 基于CFS-GA 的分类模型流程

基于CFS-GA 的特征选择算法的网页分类的时间复杂度是由特征选择算法的复杂度和分类算法的复杂度两部分组成的(这里没有考虑预处理部分).若原始特征数为s，经过特征选择后的特征数为t(t≤s)，那么特征选择的时间是一个关于s 的函数g(s)，分类的时间是一个关于t 的函数h(t)，则整个分类模型的时间为g(s)+h(t).

1.3 分类评估标准

网页分类中一般采用的性能指标是准确率P(precision)和召回率R(recall)［15］.准确率为分类的正确网页数与应有网页数的百分比，即该类样本被分类器正确识别的概率.准确率体现系统分类的准确程度.召回率为分类的正确网页数与分到该类的网页数的百分比.召回率体现系统分类的完备性.准确率和召回率分别反映分类质量的两个不同的方面，是互补的.为了获得比较高的召回率通常要牺牲准确率;同样，为了获得较高的准确率就要牺牲召回率.因此，需要有一种综合考虑召回率和准确率的方法对分类器进行评价.F1值是常用的一种组合评价方式:F1=2RP/(R+P).

2 实 验

2.1 实验数据

实验的数据集采用搜狗实验室提供的中文网页数据集.由于原数据集总的大小达500 G，且其中含有词性标注等信息，本文使用该数据集的mini 版.考虑到实验机器的性能问题，从原语料库中抽取5个类共288 篇文档，其中:IT 类59 篇，教育类61 篇，医学类53 篇，体育类56 篇，交通类59 篇.

2.2 实验环境与参数设置

硬件平台为:操作系统Windows XP Professional SP3，CPU Intel®Celeron®M processor 1.30 GHz，512 MB内存，80 G 硬盘.实现语言为Java，实现平台为eclipse+jdk1.6，在代码中分类调用开源的数据挖掘平台的weka中的分类算法(由新西兰的Waikato 大学开发的一款开源的数据挖掘平台，集成一系列的机器学习算法，实现语言是Java)分词工具为中国科学院的imdict-chinese-analyzer，它是开源项目ICTCLAS 的Java 版本，其算法是基于隐马尔科夫模型，其开源代码可以在开源中国社区获得.GA中的相关参数:初始化种群规模为20;交叉率为0.6;变异率为0.033;种群迭代次数为100.

2.3 实验步骤

(1)对原始数据集进行初步整理后，调用imdict-chinese-analyzer中的ChineseAnalyzer 类进行分词，并扩充停用词表，对特征集合进行粗降维.

(2)调用weka.jar中的TextDirectoryLoader，将*.txt 文件转化成weka 能接受的*.arff 文件，然后利用weka.jar中的StringToWordVector 类构建向量空间模型.考虑到GA中要求文档编码是0-1 编码，在StringToWordVector中设置属性值为0-1 编码形式，即将m_OutputCounts 的值设置为false.

(3)按图1 的算法描述，根据weka 接口利用Java 语言编写GA，然后按图2 进行特征选择，并调用weka中的分类算法进行分类，采用3 折交叉验证的方式得到最终的分类结果.

2.4 对比实验结果

为了验证文中CFS-GA 特征选择算法的有效性，将CFS-GA 与IG和CHI 算法进行比较，分类算法采用weka 的NaiveBayesMultinomial 算法.实验结果见表1和2.

表1 各特征选择算法的分类正确率、特征维度比较

表2 各特征选择算法所得到的P，R，F1值比较

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］CUI Zifeng，XU Baowen，ZHANG Weifeng，et al.CLDA:feature selection for text categorization［C］//ICSC 07＇Proc Int Conf on Semantic Computing.Washington，DC，USA，2007:703-704.

［4］叶吉祥，龚希龄.一种快速的Wrapper 式特征子集选择新方法［J］.长沙理工大学学报:自然科学版，2010，7(4):69.

［5］ELALAMI M E.A filter model for feature subset selection based on genetic algorithm［J］.Knowledge-Based Systems，2009，22(5):357-358.

［6］HUANG Cheenjung，YANG Dianxiu，CHUANG Yita.Application of wrapper approach and composite classifier［J］.Expert Systems with Application，2008，34(4):2871.

［7］单松巍，冯是聪，李晓明.几种典型特征选取方法在中文网页分类上的效果比较［J］.计算机工程与应用，2003，39(22):147.

［8］YANG Yiming，PEDERSEN J O.A comparative study on feature selection in text categorization［C］// Proc ACM SIGIR Conf on Res ＆ Dev in Inform Retrieval(SIGIR01)，2001.

［9］HALL M A.Correlation based feature selection for machine learning［D］.Hamilton，New Zealand:Univ of Waikato，1999:51-69.

［10］HALL M A，SMITH L A.Featrue selection for machine learning:comparing a correlation-based filter approach to the wrapper［C］//Proc Twelfth Int FLAIRS Conf.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.