78 上海海事大学学报第 33 卷 0 引言自进入信息化时代以来, 因特网上的网页数量增长迅猛. 为了提高信息的检索效率, 很有必要对因特网上的一些网页进行分类. 尽管目前有 Google, Yahoo, 搜狐等分类目录式的中文网站目录, 但由于其均为人工编纂, 效率低下, 而且更新速度慢, 无法

Size: px

Start display at page:

Download "78 上海海事大学学报第 33 卷 0 引言自进入信息化时代以来, 因特网上的网页数量增长迅猛. 为了提高信息的检索效率, 很有必要对因特网上的一些网页进行分类. 尽管目前有 Google, Yahoo, 搜狐等分类目录式的中文网站目录, 但由于其均为人工编纂, 效率低下, 而且更新速度慢, 无法"

验斋华
5 years ago
Views:

1 第 33 卷第 1 期 2012 年 3 月上海海事大学学报 JournalofShanghaiMaritimeUniversity Vol.33 No.1 Mar.2012 文章编号 : (2012) 基于 CFS GA 特征选择算法的中文网页自动分类喻春萍, 黄晓霞 ( 上海海事大学信息工程学院, 上海 ) 摘要 : 为在中文网页分类时降低特征向量的维度提高分类的精度, 采用一种基于关联的特征选择 (Corelation basedfeatureselection,cfs) 与遗传算法 (GeneticAlgorithm,GA) 相结合的方法进行特征选择. 在该算法中, 特征子集被当作 GA 中的一个染色体进行二进制编码 ; 利用 CFS 启发值作为 GA 的适应度函数对个体进行评价 ;CFS 值越大的个体遗传到下一代的概率越大. 结合 GA 的全局搜索特性, 该算法可保证所得特征子集是全局最优的. 利用 weka 平台, 对搜狗实验室提供的中文网页数据集进行实验. 结果表明, 该算法能有效降低特征空间的维度提高分类精度. 关键词 : 中文网页分类 ; 特征选择 ; 基于关联的特征选择算法 ; 遗传算法中图分类号 :TP ;TP183 文献标志码 :A ChineseWebpageclasificationbasedonCFS GA featureselectionalgorithm YUChunping,HUANGXiaoxia (InformationEngineeringColege,ShanghaiMaritimeUniv.,Shanghai201306,China) Abstract:ToreducethedimensionofthefeaturespaceandimprovetheprecisionofChineseWebpage clasification,amethodbasedoncorelation basedfeatureselection(cfs)andgeneticalgorithm (GA)isusedintheprocesoffeatureselection.IntheCFS GAalgorithm,afeaturesubsetisregarded asachromosomewhichisthenperformedinbinaryencode,andcfsisusedasga sfitnesfunctionto evaluatethechromosome.thegreaterthecfsvalueis,thegreatertheprobabilitythatindividualsinherit tothenextgenerationwilbe.combiningwithga sglobalsearchcharacter,thealgorithm canensure thatthefeaturesubsetisglobaloptimum.experimentisdoneonwekaplatform withthechineseweb pagedatasetprovidedbythesougoulab.theresultshowsthatthisalgorithmcanreducethedimensionof thefeaturespaceefectivelyandimprovetheprecisionoftheclasification. Keywords:ChineseWebpageclasification;featureselection;corelation basedfeatureselection;ge neticalgorithm 收稿日期 : 修回日期 : 基金项目 : 国家自然科学基金 ( ) 作者简介 : 喻春萍 (1988 ), 女, 湖北武汉人, 硕士研究生, 研究方向为数据挖掘与知识发现,(E mail)tracy8891@126.com; 黄晓霞 (1968 ), 女, 上海人, 副教授, 博士, 研究方向为数据挖掘与知识发现人工智能,(E mail)lhuangxiaoxia@163.com

2 78 上海海事大学学报第 33 卷 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]. 基于关联的特征选择 (Corela tion basedfeatureselection,cfs) 作为一种过滤型算法, 是以属性与类别之间的相关性以及属性与属性之间的冗余度为衡量依据的 [9 11], 该算法虽然具有较好的降维能力, 但其所得到的解不一定是全局最优的. 在文本分类中, 遗传算法 (GeneticAlgorithm, GA) 因其具有全局搜索特性常被作为一种封装型算法对特征进行降维处理. [12 14] 本文将 CFS 与 GA 相结合, 以 CFS 的相关度度量作为 GA 的适应度函数评价遗传算法中的每个新个体. 实验证明, 利用该算法进行特征选择, 可以有效降低特征向量的维度减少学习分类器所需的数据量, 具有泛化能力强可找到全局最优解等优点. 1 基于 CFS GA 的中文网页分类 1.1 CFS CFS 是一种经典的过滤型特征选择算法, 其启发式地评价单一特征对应于每个类别的作用, 从而得到最终的特征子集. 其评估方法如下 : kr - cf M S = (1) 槡 k+k(k 1)r - ff 式中 :M S 为对一个包含有 k 个特征项的特征子集 S 的一个评价 ;r - cf 为属性与类别之间的平均相关度 ; r - ff 为属性与属性之间的平均相关度. 由式 (1) 可知, CFS 评价方法是一种基于相关性的特征子集评价方法. 由该方法计算得到的各个子集中每个属性与类属性的关联度越大或属性之间的冗余度越小则评价值越高. 在 CFS 中, 利用信息增益计算属性之间的相关性大小, 下面给出信息增益的计算方法. 假设属性为 Y,y 为 Y 的每一个可能的取值, 则 Y 的熵的计算方法为 H(Y)=- p(y)log 2 (p(y)) (2) y Y 已知属性 X, 计算 Y 的熵的方法为 H(Y X)= - p(x) p(y x) x X y Y log 2 (p(y x)) (3) 差值 H(Y)-H(Y X)( 即特征 Y 的熵的减少量 ) 可反映特征 X 提供给特征 Y 的附加信息, 被称为信息增益. 信息增益可反映属性 X 提供给属性 Y 的信息的多少, 因此信息增益值越大, 那么 X 与 Y 的相关度就越高. 由于信息增益是一种对称性的测量方法, 其缺点是倾向于选择那些有更多取值的属性. 因此, 为确保各个属性可相互比较, 使不同的属性选择产生相同的效果, 需要对信息增益进行归一化. 这里使用对称不确定性方法将其归一到 [0,1]. U XY =2.0 H(Y)-H(Y X) (4) H(Y)+H(X) 1.2 基于 CFS GA 的中文网页分类在运用 GA 进行特征选择时, 常将其自身设计成封装型特征选择算法.GA 在运行中基本上不需要外界信息, 只需要依据适应度函数控制种群的更新, 因此适应度函数的设计对特征子集的选择至关重要, 关系到特征选择时的收敛速度和找到的最优解. 在基于 GA 的封装型特征选择中, 常采用学习算法的分类精度和最终选择出的特征子集的大小作为适应度函数. 尽管该方法可以利用 GA 的全局搜索能力找到全局最优解, 但是在处理大规模数据时效

3 第 1 期喻春萍, 等 : 基于 CFS GA 特征选择算法的中文网页自动分类 79 率极其低下, 且复杂度较大. 因此, 考虑将 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 之间选取, 变异率一般在 ~ 之间选取.CFS GA 算法描述和基于 CFS GA 的分类模型流程见图 1 和 2. 算法 :CFS GA 算法输入 : 已经经过二进制编码的文本数据集 ; 选择算子 ; 交叉率 p c 和交叉算子 ; 变异率 p m 和变异算子 ; 种群迭代次数 g; 初始化种群规模 p; 输出 :CFS GA 算法选择出来的特征描述 :(1) 初始化种群 P, 随机产生 p 个特征子集 ; (2) 对种群进行评价, 对种群中每一个个体 h, 利用 CFS 算法计算其 Fitnes 值 ; (3)while( 不是最优解或者没有达到迭代次数 g){ 1 选择, 根据 Fitnes 值从父代中选择最优个体直接遗传到下一代 ; 2 交叉, 根据 Fitnes 值, 从父代中按轮盘赌方法选择配对的特征子集, 对每对特征子集随机设置交叉点, 然后互换该点前或后的结构, 生成两个新个体 ; 3 变异, 应用变异率和变异算子对交叉后的特征子集对随机选择变异位进行变异, 产生两个新个体 ; 4 将所有的新个体加入到种群中形成新种群 ; 5 对新种群中的个体利用 Fitnes 进行评价.} 图 1 CFS GA 算法描述图 2 基于 CFS GA 的分类模型流程基于 CFS GA 的特征选择算法的网页分类的时间复杂度是由特征选择算法的复杂度和分类算法的复杂度两部分组成的 ( 这里没有考虑预处理部分 ). 若原始特征数为 s, 经过特征选择后的特征数为 t(t s), 那么特征选择的时间是一个关于 s 的函数

4 80 上海海事大学学报第 33 卷 g(s), 分类的时间是一个关于 t 的函数 h(t), 则整个分类模型的时间为 g(s)+h(t). 1.3 分类评估标准网页分类中一般采用的性能指标是准确率 P (precision) 和召回率 R(recal) [15]. 准确率为分类的正确网页数与应有网页数的百分比, 即该类样本被分类器正确识别的概率. 准确率体现系统分类的准确程度. 召回率为分类的正确网页数与分到该类的网页数的百分比. 召回率体现系统分类的完备性. 准确率和召回率分别反映分类质量的两个不同的方面, 是互补的. 为了获得比较高的召回率通常要牺牲准确率 ; 同样, 为了获得较高的准确率就要牺牲召回率. 因此, 需要有一种综合考虑召回率和准确率的方法对分类器进行评价.F 1 值是常用的一种组合评价方式 :F 1 =2RP/(R+P). 2 实验 2.1 实验数据实验的数据集采用搜狗实验室提供的中文网页数据集. 由于原数据集总的大小达 500G, 且其中含有词性标注等信息, 本文使用该数据集的 mini 版. 考虑到实验机器的性能问题, 从原语料库中抽取 5 个类共 288 篇文档, 其中 :IT 类 59 篇, 教育类 61 篇, 医学类 53 篇, 体育类 56 篇, 交通类 59 篇. 2.2 实验环境与参数设置硬件平台为 : 操作系统 WindowsXPProfesional SP3,CPU Intel Celeron M procesor1.30ghz, 512MB 内存,80G 硬盘. 实现语言为 Java, 实现平台为 eclipse+jdk1.6, 在代码中分类调用开源的数据挖掘平台的 weka 中的分类算法 ( 由新西兰的 Waikato 大学开发的一款开源的数据挖掘平台, 集成一系列的机器学习算法, 实现语言是 Java) 分词工具为中国科学院的 imdict chinese analyzer, 它是开源项目 ICTCLAS 的 Java 版本, 其算法是基于隐马尔科夫模型, 其开源代码可以在开源中国社区获得.GA 中的相关参数 : 初始化种群规模为 20; 交叉率为 0.6; 变异率为 0.033; 种群迭代次数为实验步骤 (1) 对原始数据集进行初步整理后, 调用 im dict chinese analyzer 中的 ChineseAnalyzer 类进行分词, 并扩充停用词表, 对特征集合进行粗降维. (2) 调用 weka.jar 中的 TextDirectoryLoader, 将.txt 文件转化成 weka 能接受的.arf 文件, 然后利用 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 各特征选择算法的分类正确率特征维度比较特征选择算法特征维度分类正确率 /% 无 CFS GA IG CHI 表 2 各特征选择算法所得到的 P,R,F 1 值比较特征选择算法交通医疗教育 IT 体育平均值 P 无 R F P IG R F P CFS GA R F P CHI R F 实验结果分析从表 1 和 2 可知 :(1) 经过特征选择后, 分类正确率显著提高, 因此特征选择在中文网页分类中意义重大 ;(2)CFS GA 降维能力好, 其分类性能也优于 IG 和 CHI, 这是因为在选择特征时, 本文算法不仅考虑特征与类别之间的相关性, 而且考虑特征与特征之间的冗余性, 从而能有效降低最优特征空间的维度 ;(3)IG 与 CHI 性能大体相当, 这与文献 [7 8] 所得的结论基本一致. 总之, 本文提出的算法对中文网页自动分类具有一定的实用价值.

5 第 1 期喻春萍, 等 : 基于 CFS GA 特征选择算法的中文网页自动分类 81 3 结束语特征选择的目的是降低特征向量空间的维度, 提高分类效率. 本文将 CFS 与 GA 相结合, 用 CFS 评价作为 GA 适应度函数来评价个体. 实验证明, 这种特征选择算法能有效降低特征空间的维度, 且其分类性能与当前比较成熟的特征选择算法相比也有所提高. 进一步工作可以考虑网页的结构特征. 网页含有丰富的结构信息, 除纯文本之外, 还有其他一些对分类有贡献的信息 : 如用 Head 和 Title 标注网页的标题和段落子标题,meta 标记中的 name 属性和 content 属性值是对网页主题的描述, 网页中的超链接指向的内容有可能是与该网页主题相关的内容. 在下一步的工作中, 可以利用这些信息提高分类的准确率. 参考文献 : [1] 刘超. 中文网页自动分类研究及分类算法的设计与实现 [J]. 中国科技论文在线,2003:1 2. [2] 冯是聪, 张志刚, 李晓明. 一种中文网页自动分类方法的实现及应用 [J]. 计算机工程,2004,30(5): [3] CUIZifeng,XUBaowen,ZHANGWeifeng,etal.CLDA:featureselectionfortextcategorization[C]//ICSC07 ProcIntConfonSemanticCompu ting.washington,dc,usa,2007: [4] 叶吉祥, 龚希龄. 一种快速的 Wrapper 式特征子集选择新方法 [J]. 长沙理工大学学报 : 自然科学版,2010,7(4):69. [5] ELALAMIM E.Afiltermodelforfeaturesubsetselectionbasedongeneticalgorithm[J].Knowledge BasedSystems,2009,22(5): [6] HUANGCheenjung,YANGDianxiu,CHUANGYita.Applicationofwrapperapproachandcompositeclasifier[J].ExpertSystemswithApplica tion,2008,34(4):2871. [7] 单松巍, 冯是聪, 李晓明. 几种典型特征选取方法在中文网页分类上的效果比较 [J]. 计算机工程与应用,2003,39(22):147. [8] YANGYiming,PEDERSENJO.Acomparativestudyonfeatureselectionintextcategorization[C]//ProcACMSIGIRConfonRes&DevinIn formretrieval(sigir01),2001. [9] HALLM A.Corelationbasedfeatureselectionformachinelearning[D].Hamilton,NewZealand:UnivofWaikato,1999: [10]HALLM A,SMITHLA.Featrueselectionformachinelearning:comparingacorelation basedfilterapproachtothewrapper[c]//proctwelfth IntFLAIRSConf.Florida,USA,1999: [11] 孙宁青. 基于神经网络和 CFS 特征选择的网络入侵检测系统 [J]. 计算机工程与科学,2010,32(6):38. [12] 郑滨, 金永兴. 基于属性约简的海事人为失误致因分析 [J]. 上海海事大学学报,2010,31(1): [13] 任江涛, 孙婧昊, 黄焕宇, 等. 一种基于信息增益及遗传算法的特征选择算法 [J]. 计算机科学,2006,33(10):194. [14] 宋淑彩, 庞慧, 丁学钧.GA SVM 算法在文本分类中的应用研究 [J]. 计算机仿真,2011,28(1): [15] 熊忠阳, 刘道群, 张玉芳. 用改进的遗传算法训练神经网络构造分类器 [J]. 计算机应用,2005,25(1): [16] 黄晓霞, 程论. 综合评价与数据挖掘的比较 [J]. 上海海事大学学报,2007,28(4): ( 编辑贾裙平 ) 檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿 ( 上接第 76 页 ) [5] VAHDATA,BECKERD.EpidemicrouteingforpartialyconnectedAdHocnetworks[D].Durham,UK:DukeUniv,2000. [6] LINDGRENA,DORIAA,SCHELENO.Probabilisticrouteinginintermitentlyconnectednetworks[J].LectNotesinComputSci,2004: [7] PANH,CROWCROFTJ,YONEKIE.BubbleRap:social basedforwardingindelay tolerantnetworks[c]//proc9thacm IntSymponMobi HOC.NewYork:ACM Pr,2008: [8] EAGLEN,PENTLANDA,LAZERD.Inferingsocialnetworkstructureusingmobilephonedata[C]//ProcNationalAcadofSci(PNAS).Mas sachusets:masachusetsinstoftechnol,2009: ( 编辑廖粤新 )

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位自然科学版文章编号视网膜图像中视盘的快速自动定位方法赵晓芳林土胜李碧摘要基于眼底视网膜血管的分布结构及视盘本身的特点提出一种快速自动定位视盘的方法首先根据视网膜血管的网络分布结构大致定位视盘的垂直坐标然后根据视盘的亮度信息及视盘与血管的关系来定位视盘的水平坐标最后把视盘限定在以粗定位的视盘为中心的一个小窗口内用变换精确定位视盘中心该方法不需要事先分割视网膜血管也不需要对算法进行训练