第9卷第4期 智能系统学报 Vol.9 No.4 2014年8月 CAAI Transactions on Intelligent Systems Agu.2014 D0I:10.3969/i.issn.1673-4785.201305044 基于遗传算法优化综合启发式的中文网页特征提取 沈高峰1，谷淑敏 (1.郑州轻工业学院计算机与通信工程学院，河南郑州450002：2.中原工学院信息商务学院基础学科部，河南郑州450007) 摘要：特征提取是信息检索、文本分类，文本聚类以及自动文摘生成等技术的基础。针对传统的特征提取方法不 能全面有效地考查待选特征词的缺点，提出了一种基于遗传算法优化综合启发式的中文网页特征提取方法。该方 法通过词频、关联度、词性以及位置等多种启发式来综合考查待选特征，并利用遗传算法来优化各启发式的权重参 数。通过在不同测试集上进行对比，实验结果表明，与传统方法相比，该方法能够有效避免传统特征提取方法产生 的偏差，获得具有代表性的特征集，从而使得该方法具有一定的实用价值。 关键词：特征提取：遗传算法：文本分类：文本聚类：词频：关联度 中图分类号：TP391.1文献标志码：A文章编号：1673-4785(2014)04-474-06 中文引用格式：沈高峰，谷淑敏.基于遗传算法优化综合启发式的中文网页特征提取[J].智能系统学报，2014,9(4)：474479. 英文引用格式：SHEN Gaofeng,GU Shumin.Chinese Web page feature extraction by optimizing comprehensive heuristics based on GA[J].CAAI Transactions on Intelligent Systems,2014,9(4):474-479. Chinese Web page feature extraction by optimizing comprehensive heuristics based on GA SHEN Gaofeng',GU Shumin2 (1.School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China;2.De- partment of Basic Subjects,College Information Business,Zhongyuan University of Technology,Zhengzhou 450007,China) Abstract:Feature extraction is the basis of such technologies as information retrieval,text classification,text clus- tering and automatic summarization.Aiming at the shortcomings of the traditional feature extraction methods which make it difficult to test feature words comprehensively and effectively,this paper proposes a method for extracting Chinese web page features by optimizing the comprehensive heuristic features based on GA.This proposed method employs comprehensive heuristics of word frequency,word correlation,parts of speech (POS)and position features to comprehensively test selected features and uses GA to optimize the weight of each heuristic parameter.The exper- imental results of the different test sets show that the proposed method can effectively avoid the derivations of the traditional extraction methods and obtain more representative features,and therefore it has a certain practical value. Keywords:feature extraction;GA;text classification;text clustering;word frequency;word correlation 特征提取在自然语言处理领域有着非常广泛的具有一定的主观性，因此快速准确地实现中文特征 应用，是信息检索、文本分类、文本聚类以及自动文 提取成为中文文本处理的关键。 摘生成等技术的关键。由于互联网资源时刻都在不 目前，国内外学者已提出3类特征提取方法：基 断更新，中文文本呈现出“爆炸式”增长。然而，采 于概率统计的特征提取方法、基于传统机器学习理 用传统人工方式进行特征提取的方法耗时较长，且 论的特征提取方法以及基于自然语言理解的特征提 取方法。基于概率统计的特征提取方法利用文本特 收稿日期：2013-05-10. 征的统计信息进行关键词提取，如TFIDF)、词共 基金项目：河南省基础与前沿技术研究计划项目(102300410266)：郑 州轻工业学院博士科研基金资助项目. 现]等，该类方法具有简单、通用的特点，不需要复 通信作者：沈高蜂.E-mail:45125301@q4.com. 杂的训练过程，但准确率不高。基于传统机器学习
第 怨 卷第 源 期摇摇摇摇摇 摇摇摇 摇摇摇 摇摇摇 智 能 系 统 学 报摇摇摇摇摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 灾燥造援怨 翼援源 圆园员源 年 愿 月摇摇摇摇摇摇摇摇摇摇摇摇 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 粤早怎援 圆园员源 阅韵陨院员园援猿怨远怨 辕 躁援蚤泽泽灶援员远苑猿鄄源苑愿缘援圆园员猿园缘园源源 基于遗传算法优化综合启发式的中文网页特征提取 沈高峰员 袁谷淑敏圆 渊员援郑州轻工业学院 计算机与通信工程学院袁河南 郑州 源缘园园园圆曰 圆援中原工学院信息商务学院 基础学科部袁河南 郑州 源缘园园园苑冤 摘 要院特征提取是信息检索尧文本分类尧文本聚类以及自动文摘生成等技术的基础遥 针对传统的特征提取方法不 能全面有效地考查待选特征词的缺点袁提出了一种基于遗传算法优化综合启发式的中文网页特征提取方法遥 该方 法通过词频尧关联度尧词性以及位置等多种启发式来综合考查待选特征袁并利用遗传算法来优化各启发式的权重参 数遥 通过在不同测试集上进行对比袁实验结果表明袁与传统方法相比袁该方法能够有效避免传统特征提取方法产生 的偏差袁获得具有代表性的特征集袁从而使得该方法具有一定的实用价值遥 关键词院特征提取曰遗传算法曰文本分类曰文本聚类曰词频曰关联度 中图分类号院栽孕猿怨员援员 摇 文献标志码院粤摇 文章编号院员远苑猿鄄源苑愿缘渊圆园员源冤园源鄄源苑源鄄园远 中文引用格式院沈高峰 袁谷淑敏援 基于遗传算法优化综合启发式的中文网页特征提取咱允暂援 智能系统学报袁 圆园员源袁 怨渊源冤 院 源苑源鄄源苑怨援 英文引用格式院杂匀耘晕 郧葬燥枣藻灶早袁 郧哉 杂澡怎皂蚤灶援 悦澡蚤灶藻泽藻 宰藻遭 责葬早藻 枣藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶 遭赠 燥责贼蚤皂蚤扎蚤灶早 糟燥皂责则藻澡藻灶泽蚤增藻 澡藻怎则蚤泽贼蚤糟泽 遭葬泽藻凿 燥灶 郧粤咱允暂援 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽袁 圆园员源袁 怨渊源冤 院 源苑源鄄源苑怨援 悦澡蚤灶藻泽藻 宰藻遭 责葬早藻 枣藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶 遭赠 燥责贼蚤皂蚤扎蚤灶早 糟燥皂责则藻澡藻灶泽蚤增藻 澡藻怎则蚤泽贼蚤糟泽 遭葬泽藻凿 燥灶 郧粤 杂匀耘晕 郧葬燥枣藻灶早员 袁 郧哉 杂澡怎皂蚤灶圆 渊员援杂糟澡燥燥造 燥枣 悦燥皂责怎贼藻则 葬灶凿 悦燥皂皂怎灶蚤糟葬贼蚤燥灶 耘灶早蚤灶藻藻则蚤灶早袁 在澡藻灶早扎澡燥怎 哉灶蚤增藻则泽蚤贼赠 燥枣 蕴蚤早澡贼 陨灶凿怎泽贼则赠袁 在澡藻灶早扎澡燥怎 源缘园园园圆袁 悦澡蚤灶葬曰 圆援 阅藻鄄 责葬则贼皂藻灶贼 燥枣 月葬泽蚤糟 杂怎遭躁藻糟贼泽袁 悦燥造造藻早藻 陨灶枣燥则皂葬贼蚤燥灶 驭 月怎泽蚤灶藻泽泽袁在澡燥灶早赠怎葬灶 哉灶蚤增藻则泽蚤贼赠 燥枣 栽藻糟澡灶燥造燥早赠袁 在澡藻灶早扎澡燥怎 源缘园园园苑袁 悦澡蚤灶葬冤 粤遭泽贼则葬糟贼院云藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶 蚤泽 贼澡藻 遭葬泽蚤泽 燥枣 泽怎糟澡 贼藻糟澡灶燥造燥早蚤藻泽 葬泽 蚤灶枣燥则皂葬贼蚤燥灶 则藻贼则蚤藻增葬造袁 贼藻曾贼 糟造葬泽泽蚤枣蚤糟葬贼蚤燥灶袁 贼藻曾贼 糟造怎泽鄄 贼藻则蚤灶早 葬灶凿 葬怎贼燥皂葬贼蚤糟 泽怎皂皂葬则蚤扎葬贼蚤燥灶援 粤蚤皂蚤灶早 葬贼 贼澡藻 泽澡燥则贼糟燥皂蚤灶早泽 燥枣 贼澡藻 贼则葬凿蚤贼蚤燥灶葬造 枣藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶 皂藻贼澡燥凿泽 憎澡蚤糟澡 皂葬噪藻 蚤贼 凿蚤枣枣蚤糟怎造贼 贼燥 贼藻泽贼 枣藻葬贼怎则藻 憎燥则凿泽 糟燥皂责则藻澡藻灶泽蚤增藻造赠 葬灶凿 藻枣枣藻糟贼蚤增藻造赠袁 贼澡蚤泽 责葬责藻则 责则燥责燥泽藻泽 葬 皂藻贼澡燥凿 枣燥则 藻曾贼则葬糟贼蚤灶早 悦澡蚤灶藻泽藻 憎藻遭 责葬早藻 枣藻葬贼怎则藻泽 遭赠 燥责贼蚤皂蚤扎蚤灶早 贼澡藻 糟燥皂责则藻澡藻灶泽蚤增藻 澡藻怎则蚤泽贼蚤糟 枣藻葬贼怎则藻泽 遭葬泽藻凿 燥灶 郧粤援 栽澡蚤泽 责则燥责燥泽藻凿 皂藻贼澡燥凿 藻皂责造燥赠泽 糟燥皂责则藻澡藻灶泽蚤增藻 澡藻怎则蚤泽贼蚤糟泽 燥枣 憎燥则凿 枣则藻择怎藻灶糟赠袁 憎燥则凿 糟燥则则藻造葬贼蚤燥灶袁 责葬则贼泽 燥枣 泽责藻藻糟澡 渊孕韵杂冤 葬灶凿 责燥泽蚤贼蚤燥灶 枣藻葬贼怎则藻泽 贼燥 糟燥皂责则藻澡藻灶泽蚤增藻造赠 贼藻泽贼 泽藻造藻糟贼藻凿 枣藻葬贼怎则藻泽 葬灶凿 怎泽藻泽 郧粤 贼燥 燥责贼蚤皂蚤扎藻 贼澡藻 憎藻蚤早澡贼 燥枣 藻葬糟澡 澡藻怎则蚤泽贼蚤糟 责葬则葬皂藻贼藻则援 栽澡藻 藻曾责藻则鄄 蚤皂藻灶贼葬造 则藻泽怎造贼泽 燥枣 贼澡藻 凿蚤枣枣藻则藻灶贼 贼藻泽贼 泽藻贼泽 泽澡燥憎 贼澡葬贼 贼澡藻 责则燥责燥泽藻凿 皂藻贼澡燥凿 糟葬灶 藻枣枣藻糟贼蚤增藻造赠 葬增燥蚤凿 贼澡藻 凿藻则蚤增葬贼蚤燥灶泽 燥枣 贼澡藻 贼则葬凿蚤贼蚤燥灶葬造 藻曾贼则葬糟贼蚤燥灶 皂藻贼澡燥凿泽 葬灶凿 燥遭贼葬蚤灶 皂燥则藻 则藻责则藻泽藻灶贼葬贼蚤增藻 枣藻葬贼怎则藻泽袁 葬灶凿 贼澡藻则藻枣燥则藻 蚤贼 澡葬泽 葬 糟藻则贼葬蚤灶 责则葬糟贼蚤糟葬造 增葬造怎藻援 运藻赠憎燥则凿泽院枣藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶曰 郧粤曰 贼藻曾贼 糟造葬泽泽蚤枣蚤糟葬贼蚤燥灶曰 贼藻曾贼 糟造怎泽贼藻则蚤灶早曰 憎燥则凿 枣则藻择怎藻灶糟赠曰 憎燥则凿 糟燥则则藻造葬贼蚤燥灶 收稿日期院圆园员猿鄄园缘鄄员园援 摇 基金项目院河南省基础与前沿技术研究计划项目渊 员园圆猿园园源员园圆远远冤 曰 郑 州轻工业学院博士科研基金资助项目援 通信作者院沈高峰援耘鄄皂葬蚤造院源缘员圆缘猿园员岳 择择援糟燥皂援 摇 摇 特征提取在自然语言处理领域有着非常广泛的 应用袁是信息检索尧文本分类尧文本聚类以及自动文 摘生成等技术的关键遥 由于互联网资源时刻都在不 断更新袁中文文本呈现出野爆炸式冶增长遥 然而袁采 用传统人工方式进行特征提取的方法耗时较长袁且 具有一定的主观性袁因此快速准确地实现中文特征 提取成为中文文本处理的关键遥 目前袁国内外学者已提出 猿 类特征提取方法院基 于概率统计的特征提取方法尧基于传统机器学习理 论的特征提取方法以及基于自然语言理解的特征提 取方法遥 基于概率统计的特征提取方法利用文本特 征的统计信息进行关键词提取袁如 栽云陨阅云咱员暂 尧词共 现咱圆暂等袁该类方法具有简单尧通用的特点袁不需要复 杂的训练过程袁但准确率不高遥 基于传统机器学习
第4期 沈高峰，等：基于遗传算法优化综合启发式的中文网页特征提取 .475 理论的特征提取方法通过对大规模语料库进行学 1{(号e):(,y)∈E(:,)∈E,,,∈V}I 习，采用决策树)、贝叶斯算法[4)、最大熵模型)等 (3) 方法对训练集进行训练，从而得到相关模型，然后再 顶点的聚集度系数C:为 利用该模型对关键词进行提取，但该类方法较为复 2K, 杂。基于自然语言理解的特征提取方法通常需要对 C:= D(D-1) (4) 中文文本从词、句、语义、篇章等层级进行分析，从而 2」 获得相关关键词，这类方法更加符合关键词提取的 由式(3)和式(4)可得特征关联度为 标注过程，但如何对文章进行准确的语言学分析还 没有得到有效解决，该方法的抽取性能非常有限。 CF:=aC/ ∑C+(1-)D,/N (5) 针对上述传统特征提取方法的特点和不足，提 根据式(3)~(6)，词语网络中节点的度和聚集 出了一种基于遗传算法优化综合启发式的中文网页 度系数可以描述特征在文本中的连接特性，处于重 特征提取方法。该方法首先对文本文档的分词结果 要位置的特征往往具有较高的关联度。 进行词性标注，然后计算文档词语的词性、位置、 1.3词性 T℉DF以及聚集特征等综合启发式，并用遗传算法 词性是一种浅层语言学知识的表示，该因素的 优化各启发式的权重参数，最终提取获得中文网页 获取不需要对文本进行复杂的语言学标注和分析， 特征词。 从而能有效避免传统采用语言学方法的缺陷。一般 1 基础知识简介 而言，中文文本特征的词性往往集中在名词、动词 形容词等实词中。根据人工标注结果，对特征的词 1.1频率 性分布进行了统计分析，其结果如表1所示。 TFIDF是一种常用的信息检索方法[6)。设N 表1特征词性分布 表示给定文档集合2中的总文档数目。对于给定 Table 1 Characteristics distribution 文档d,采用T℉IDF算法得到该文档中词条t的权 词性 名词动词形容词副词其他 重心，为 数目 843134051830659 675 (w,=TF x IDF (1) 百分比/%56.2 22.7 12.2 4.4 IDF log(N/n) 4.5 式中：TF表示t在文档d中出现的频率。IDF表示 从特征词性统计分布可以看到，词性能够有效表 文档d在文档集中出现的文档数目，n表示文档集 征文档的中文特征。排名前4位的名词、动词、形容词 中出现特征t的文档数目。 和副词达到关键词总数的95.5%。因此，论文引人词性 从式(1)可知，如果特征t在文档d出现的次数 作为特征提取的重要因素之一。该因素能够有效区分 较多而在其他文档中出现次数较少的话，那么特征t 停用词等，克服了传统基于统计方法无法解决高频但 的权值就较大，表明该特征对文档d的区分能力就 无实际意义的中文词语，从而提高特征提取的性能。 较强，就可以作为文档特征的候选之一。 1.4位置 1.2关联度 位置是文本特征提取的一个重要因素。根据特征 词语的关联表现为词与词之间构成的复杂网 所在的位置，主要包括标题、摘要和正文3种。根据词 络[)。复杂网络方面的研究表明，汉语语言的词语 语所在的具体位置，还可细分为小标题、起始段、中间 之间的关联度具有高度的局部聚集性和全局连接 段、末尾段、起始句、中间句、末尾句等9。由于网络文 性，能够用于表征文本特征)。 本一般不存在摘要，本文主要考虑特征位于标题、起始 设V={1,2,…,n}表示文档特征的集合， 段以及其他3种情况。通常特征位于标题和起始段的 (:,)表示特征"：和特征之间的一条边。 概率较高，因此根据文本中特征所在的位置，按照标 G(V,E)表示的是一个图，其中V为图的顶点集合， 题、起始段、其他的顺序分别赋给不同的权重。 EC{(:,)::,∈V}为图的边集。对于顶点：， 其度定义如下： 2论文所提方法 D=l{(e:,):(:,)∈E,,y∈V}I(2) 2.1综合启发式 顶点v,的聚集度K为 仅仅根据单词频率进行特征提取的T℉DF方 K= 法虽然简单，但是也存在一定的缺陷，如数据集偏
理论的特征提取方法通过对大规模语料库进行学 习袁采用决策树咱猿暂 尧贝叶斯算法咱源暂 尧最大熵模型咱缘暂 等 方法对训练集进行训练袁从而得到相关模型袁然后再 利用该模型对关键词进行提取袁但该类方法较为复 杂遥 基于自然语言理解的特征提取方法通常需要对 中文文本从词尧句尧语义尧篇章等层级进行分析袁从而 获得相关关键词袁这类方法更加符合关键词提取的 标注过程袁但如何对文章进行准确的语言学分析还 没有得到有效解决袁该方法的抽取性能非常有限遥 针对上述传统特征提取方法的特点和不足袁提 出了一种基于遗传算法优化综合启发式的中文网页 特征提取方法遥 该方法首先对文本文档的分词结果 进行词性标注袁然后计算文档词语的词性尧位置尧 栽云陨阅云 以及聚集特征等综合启发式袁并用遗传算法 优化各启发式的权重参数袁最终提取获得中文网页 特征词遥 员摇 基础知识简介 员援员摇 频率 摇 摇 栽云陨阅云 是一种常用的信息检索方法咱远暂 遥 设 晕 表示给定文档集合 赘 中的总文档数目遥 对于给定 文档 凿袁采用 栽云陨阅云 算法得到该文档中词条 贼 的权 重 憎贼为 憎贼 越 栽云 伊 陨阅云 陨阅云 越 造燥早渊晕辕灶冤 渊员冤 式中院栽云 表示 贼 在文档 凿 中出现的频率遥 陨阅云 表示 文档 凿 在文档集中出现的文档数目袁灶 表示文档集 中出现特征 贼 的文档数目遥 从式渊员冤可知袁如果特征 贼 在文档 凿 出现的次数 较多而在其他文档中出现次数较少的话袁那么特征 贼 的权值就较大袁表明该特征对文档 凿 的区分能力就 较强袁就可以作为文档特征的候选之一遥 员援圆 摇 关联度 词语的关联表现为词与词之间构成的复杂网 络咱苑暂 遥 复杂网络方面的研究表明袁汉语语言的词语 之间的关联度具有高度的局部聚集性和全局连接 性袁能够用于表征文本特征咱愿暂 遥 设 灾 越 喳 增员 袁 增圆 袁噎袁 增灶 札 表示文档特征的集合袁 增蚤袁增躁 表示特征 增蚤 和特征 增躁 之间的一条边遥 郧 灾 袁耘 表示的是一个图袁其中 灾 为图的顶点集合袁 耘 哿 喳 增蚤袁增躁 院增蚤袁增躁 沂 灾札 为图的边集遥 对于顶点 增蚤袁 其度定义如下院 阅蚤 越渣 喳 增蚤袁增躁 院 增蚤袁增躁 沂 耘袁增蚤袁增躁 沂 灾札 渣 渊圆冤 顶点 增蚤的聚集度 运蚤为 运蚤 越 渣 喳渊增躁 袁增噪冤 院渊增蚤袁增躁 冤 沂 耘渊增蚤袁增噪冤 沂 耘袁增蚤袁 增躁 袁 增噪 沂 灾 札 渣 渊猿冤 顶点 增蚤的聚集度系数 悦蚤为 悦蚤 越 运蚤 阅蚤 圆 越 圆运蚤 阅蚤 渊阅蚤 原 员冤 渊源冤 由式渊猿冤和式渊源冤可得特征关联度为 悦云蚤 越 琢悦蚤 辕移 晕 躁 越 员 悦躁 垣 渊员 原 琢冤阅蚤 辕 晕 渊缘冤 摇 摇 根据式渊猿冤 耀 渊远冤袁词语网络中节点的度和聚集 度系数可以描述特征在文本中的连接特性袁处于重 要位置的特征往往具有较高的关联度遥 员援猿摇 词性 词性是一种浅层语言学知识的表示袁该因素的 获取不需要对文本进行复杂的语言学标注和分析袁 从而能有效避免传统采用语言学方法的缺陷遥 一般 而言袁中文文本特征的词性往往集中在名词尧动词尧 形容词等实词中遥 根据人工标注结果袁对特征的词 性分布进行了统计分析袁其结果如表 员 所示遥 表 员摇 特征词性分布 栽葬遭造藻 员摇 悦澡葬则葬糟贼藻则蚤泽贼蚤糟泽 凿蚤泽贼则蚤遭怎贼蚤燥灶 词性 名词 动词 形容词 副词 其他 数目 愿 源猿员 猿 源园缘 员 愿猿园 远缘怨 远苑缘 百分比辕 豫 缘远援圆 圆圆援苑 员圆援圆 源援源 源援缘 摇 摇 从特征词性统计分布可以看到袁词性能够有效表 征文档的中文特征遥 排名前 源 位的名词尧动词尧形容词 和副词达到关键词总数的 怨缘援缘豫遥 因此袁论文引入词性 作为特征提取的重要因素之一遥 该因素能够有效区分 停用词等袁克服了传统基于统计方法无法解决高频但 无实际意义的中文词语袁从而提高特征提取的性能遥 员援源摇 位置 位置是文本特征提取的一个重要因素遥 根据特征 所在的位置袁主要包括标题尧摘要和正文 猿 种遥 根据词 语所在的具体位置袁还可细分为小标题尧起始段尧中间 段尧末尾段尧起始句尧中间句尧末尾句等咱怨暂 遥 由于网络文 本一般不存在摘要袁本文主要考虑特征位于标题尧起始 段以及其他 猿 种情况遥 通常特征位于标题和起始段的 概率较高袁因此根据文本中特征所在的位置袁按照标 题尧起始段尧其他的顺序分别赋给不同的权重遥 圆摇 论文所提方法 圆援员摇 综合启发式 仅仅根据单词频率进行特征提取的 栽云陨阅云 方 法虽然简单袁但是也存在一定的缺陷袁如数据集偏 第 源 期摇摇摇摇摇摇摇摇摇摇 沈高峰袁等院基于遗传算法优化综合启发式的中文网页特征提取 窑源苑缘窑
·476 智能系统学报 第9卷 斜[o],类间、类内分布偏差)等。而单纯依靠复杂 TFIDF、关联度、位置和词性等启发式。 网络中词语之间关联度的特征提取方法，则忽略了 3)启发式融合。根据多启发式融合模型，对词 特征本身的频率，容易造成特征提取聚集到某些无 语的4个启发式进行融合，并计算得到综合得分。 意义的高频词，如“的”等，从而导致特征提取出现 4)输出结果。最后根据各特征得分的大小进 偏差。研究显示，融合频率和关联特征[)]能够有效 行排序，选择最优的特征并输出。 避免单一方法的缺陷，从而提高特征提取的效率。 2.3遗传算法优化权重参数 此外，仅仅依靠统计知识容易造成特征提取偏 本文方法中各启发式的参数权重选择是一个典型 差，特别是一些高频词如“是”、“和”等容易成为特 的组合优化问题。由于遗传算法简单、易理解、易实 征的候选。尽管这些词可以通过建立“停词表”对 现，且在解决组合优化问题有强大的优势)，因此，论 其进行过滤，但是构建合适的词表非常困难，因此引 文采用遗传算法对式(6)中的参数权重进行优化，从而 入特征的词性以及位置对特征进行进一步选取。 得到一定范围的最佳组合参数权重。这里限定4个参 综合以上因素，论文采用特征的频率、关联度 数权重的取值范围为(0,1)，并且满足α+B+y+8= 词性以及位置4个因素来衡量待选特征。对于文本 1。然后根据经验选取适当的初始值，并经过迭代计 中的每个特征，其权重计算公式为 算，得到每个启发式的参数权重。利用遗传算法获取 各特征参数权重具体过程描述如下： score(w)=a x WFre +B x WLe+ 1)依据经验，初始化各特征参数权重α=0.2， y×Wcs+8×Wos (6) 式中：Wm表示特征的TFIDF启发式，Wos表示特征 B=0.2,y=0.4,8=0.2; 2)采用十进制编码对染色体进行编码。首先 的词性启发式，W表示特征的关联度启发式，W 把各参数都乘以10或100使它们变成整数，然后再 表示特征的位置启发式。每个启发式的具体描述如 对它们进行编码，具体格式如下：L=ayδ。其中 表2所示。 各参数均用3位十进制数来表示，例如：α=0.2，B= 表2特征各启发式描述 0.2,y=0.4,8=0.2,则先把它们转化为a=020,B= Table 2 Description of feature heuristics 020,y=040,8=020,则相应染色体编码为：L= 类型 表示 描述 020020040020。 词性 POS 特征的词性信息，如名词、动词、形容词等 3)利用各参数权重计算相应召回率，以召回率 作为染色体的适应度函数，召回率计算公式为 位置 根据特征位置，分为标题、起始段和其他 Loc 3个部分： recall n/N 频率 Freq 采用TFDF值表示特征的频率信息： 式中：n代表同所标注的特征相符的特征的数目，N 关联度 CF 表征特征网络之间的链接关系： 代表文档集中所标注的特征总数目。 4)交叉和变异操作：遗传算法的收敛速度以及 2.2特征提取流程 解的质量在很大程度上取决于交叉概率和变异概 特征提取的基本流程如图1所示，其中虚线部 率。为了防止算法陷于局部最优以及加快算法搜索 分为训练模块。对于给定的输入本文，特征提取具 效率，仅让种群中较优个体参与交叉和变异，而当前 体过程如下。 种群最优个体则不参与。具体交叉概率和变异概率 、1片6. 计算公式如下： 经 上· P。 /,sin( 2 ),f≥fg =t.白 (8) 中小数专“ 后左午 分1·小 世心 T assin( 柱N出： P 2 f-),.≥fm(9) 图1 本文方法特征提取基本流程 Fig.1 Flow of feature extraction in this paper 式中：a1、a2、a3、a4为0~1的随机数，fm是当前群 1)预处理。将网络文本去除HTML格式，保留文 体中最优个体的适应度值，f是当前群体的平均 本词语的位置信息，并对文本进行分词和词性标注。 适应度值，∫是参加交叉操作的个体中较大的适应 2)各启发式计算。计算文本中每个词语的 度值，f是变异个体的适应度值。 5)终止条件：当代种群最佳染色体适应度值和前
斜咱员园暂 袁类间尧类内分布偏差咱员员暂 等遥 而单纯依靠复杂 网络中词语之间关联度的特征提取方法袁则忽略了 特征本身的频率袁容易造成特征提取聚集到某些无 意义的高频词袁如野的冶等袁从而导致特征提取出现 偏差遥 研究显示袁融合频率和关联特征咱员圆暂 能够有效 避免单一方法的缺陷袁从而提高特征提取的效率遥 此外袁仅仅依靠统计知识容易造成特征提取偏 差袁特别是一些高频词如野是冶尧野和冶等容易成为特 征的候选遥 尽管这些词可以通过建立野停词表冶 对 其进行过滤袁但是构建合适的词表非常困难袁因此引 入特征的词性以及位置对特征进行进一步选取遥 综合以上因素袁论文采用特征的频率尧关联度尧 词性以及位置 源 个因素来衡量待选特征遥 对于文本 中的每个特征 憎袁其权重计算公式为 泽糟燥则藻渊憎冤 越 琢 伊 宰云则藻择 垣 茁 伊 宰蕴燥糟 垣 酌 伊 宰悦云 垣 啄 伊 宰孕韵杂 渊远冤 式中院宰云则藻择表示特征的 栽云陨阅云 启发式袁宰孕韵杂表示特征 的词性启发式袁宰悦云表示特征的关联度启发式袁宰蕴燥糟 表示特征的位置启发式遥 每个启发式的具体描述如 表 圆 所示遥 表 圆摇 特征各启发式描述 栽葬遭造藻 圆摇 阅藻泽糟则蚤责贼蚤燥灶 燥枣 枣藻葬贼怎则藻 澡藻怎则蚤泽贼蚤糟泽 类型 表示 描述 词性 孕韵杂 特征的词性信息袁如名词尧动词尧形容词等 位置 蕴燥糟 根据特征位置袁分为标题尧起始段和其他 猿 个部分曰 频率 云则藻择 采用 栽云陨阅云 值表示特征的频率信息曰 关联度 悦云 表征特征网络之间的链接关系曰 圆援圆摇 特征提取流程 特征提取的基本流程如图 员 所示袁其中虚线部 分为训练模块遥 对于给定的输入本文袁特征提取具 体过程如下遥 图 员摇 本文方法特征提取基本流程 云蚤早援员摇 云造燥憎 燥枣 枣藻葬贼怎则藻 藻曾贼则葬糟贼蚤燥灶 蚤灶 贼澡蚤泽 责葬责藻则 员冤预处理遥 将网络文本去除 匀栽酝蕴 格式袁保留文 本词语的位置信息袁并对文本进行分词和词性标注遥 圆冤 各启发式计算遥 计算文本中每个词语的 栽云陨阅云尧关联度尧位置和词性等启发式遥 猿冤启发式融合遥 根据多启发式融合模型袁对词 语的 源 个启发式进行融合袁并计算得到综合得分遥 源冤输出结果遥 最后根据各特征得分的大小进 行排序袁选择最优的特征并输出遥 圆援猿摇 遗传算法优化权重参数 本文方法中各启发式的参数权重选择是一个典型 的组合优化问题遥 由于遗传算法简单尧易理解尧易实 现袁且在解决组合优化问题有强大的优势咱员猿暂 袁因此袁论 文采用遗传算法对式渊远冤中的参数权重进行优化袁从而 得到一定范围的最佳组合参数权重遥 这里限定 源 个参 数权重的取值范围为渊园袁员冤袁并且满足 琢 垣 茁 垣酌 垣 啄 越 员遥 然后根据经验选取适当的初始值袁并经过迭代计 算袁得到每个启发式的参数权重遥 利用遗传算法获取 各特征参数权重具体过程描述如下院 员冤依据经验袁初始化各特征参数权重 琢 越 园援圆袁 茁 越园援圆袁酌 越 园援源袁啄 越 园援圆曰 圆冤采用十进制编码对染色体进行编码遥 首先 把各参数都乘以 员园 或 员园园 使它们变成整数袁然后再 对它们进行编码袁具体格式如下院 蕴 越 琢茁酌啄遥 其中 各参数均用 猿 位十进制数来表示袁例如院琢 越 园援圆袁茁 越 园援圆袁酌 越 园援源袁啄 越 园援圆袁则先把它们转化为 琢 越 园圆园袁茁 越 园圆园袁酌 越 园源园袁啄 越 园圆园袁 则相应染色体编码为院蕴 越 园圆园园圆园园源园园圆园遥 猿冤利用各参数权重计算相应召回率袁以召回率 作为染色体的适应度函数袁召回率计算公式为 则藻糟葬造造 越 灶辕晕 式中院灶 代表同所标注的特征相符的特征的数目袁晕 代表文档集中所标注的特征总数目遥 源冤交叉和变异操作院遗传算法的收敛速度以及 解的质量在很大程度上取决于交叉概率和变异概 率遥 为了防止算法陷于局部最优以及加快算法搜索 效率袁仅让种群中较优个体参与交叉和变异袁而当前 种群最优个体则不参与遥 具体交叉概率和变异概率 计算公式如下院 责糟 越 葬员 泽蚤灶渊 仔 圆 伊 枣皂葬曾 原 枣糟 枣皂葬曾 原 枣葬增早 冤袁摇 枣糟 逸 枣葬增早 葬圆 袁摇 枣糟 约 枣葬增早 渊愿冤 责皂 越 葬猿 泽蚤灶渊 仔 圆 伊 枣皂葬曾 原 枣皂 枣皂葬曾 原 枣葬增早 冤袁摇 枣皂 逸 枣葬增早 葬源 袁摇 枣皂 约 枣葬增早 渊怨冤 式中院 葬员 尧葬圆 尧葬猿 尧葬源 为 园耀员 的随机数袁 枣皂葬曾 是当前群 体中最优个体的适应度值袁 枣葬增早 是当前群体的平均 适应度值袁 枣糟 是参加交叉操作的个体中较大的适应 度值袁 枣皂 是变异个体的适应度值遥 缘冤终止条件院当代种群最佳染色体适应度值和前 窑源苑远窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 沈高蜂，等：基于遗传算法优化综合启发式的中文网页特征提取 .477. 代种群最佳染色体适应度值之差绝对值不超过10。 得分最高的前10个词语作为最后的关键词。表4 采用遗传算法优化选择各启发式的参数权重，能 为实验对比结果。其中，基于频率的方法用TFDF 够有效避免通过主观经验来确定参数的主观性，从而 来表示，基于关联度的方法用C℉来表示，本文方法 实现参数能够依据训练数据自适应地调优。下面的 用Muli来表示。 实验验证结果表明，采用该遗传算法获得参数权重能 表33种方法下召回率对比结果 够使本文特征提取方法获得良好的提取效果。 Table 3 Comparison results of recall rate on three methods 3 实验验证 方法 关键词 召回率/% 3.1实验总体设置 负增长、收入、中央、降、季度、 以Intel Core2 Duo CPU T6500、2.4GHz、2GB 参考答案 财政、利润、降低、涨幅、增长 内存和Windows XP2SP2操作系统的PC机作为实 负增长、收人、中央、季度数据 验平台，以MATLAB7.0为仿真工具，进行2组实验： TFIDF 50 降、影响、进口、今年、同比 第1组实验数据来自互联网抓取的1500个中 文文档，论文根据该数据集的来源将这些文档分为 负增长、收入、中央、财政、季度、 CF 60 5个类别，分别包括新闻、财经、科技、体育和娱乐， 降低、都、进口、随后、做 各类文档数目分布均匀，都包含300篇文档。实验 负增长、收入、中央、财政，降低 Multi 70 中选择每个类别的200篇文档作为训练集，剩下的 进口、利润、季度、累计、财政部 100篇作为测试集。 从表4可以看出，对于“都”、“随后”这类词，本 第2组实验数据采用复旦大学计算机信息与技术 文方法能够有效地滤除。由于这类单词在文本中通 系国际数据库中心自然语言处理小组构建的中文文本 常具有较高的频率，很难通过统计的方法有效去除。 分类语料库作为实验数据，其下载网址为： 而且本文方法召回率能够达到70%，表现出较好的 http://www.nlp.org.cn/categories/default.php?cat_id= 提取性能。此外，比较特征词自动提取和人工选择， 16。该语料库由20个类别的14378篇文档组成，其中 3种提取方法都得到了“进口”这个特征词，但人工 6164篇为测试文本，8214篇为训练文本：各类别的测 标注却忽略了这个词语。通过查看原文，“进口”确 试文本集和训练文本集之间互不重叠，也即一篇文档 实应该标注为特征词，反映出人工选择带有较强的 仅属一个文本集并且每篇文本仅属于一个类别。该语 主观性，这种主观性很容易产生实验误差。同样也 料库各类别训练文档数分布极其不均匀，其中训练文 反映出特征词自动提取能够在一定程度上克服这种 档数较小的类别占大多数，约为11个类别，它们的训 主观性的缺点。 练文档数均少于100篇，如通信类文档数仅有25篇。 3.2.2召回率实验结果 由于所选语料库是中文性质的，所以这2组实 针对测试集的不同类别，论文分别对比不同特 验都采用中科院计算技术研究所的“汉语词法分析 征词提取方法的性能。由于不同类别的多启发式融 系统ICTCLAS”对它进行分词处理；分类工具软件 合参数不同，论文利用每个类别的训练语料分别训 都采用纽西兰的Waikato大学开发的Weka工具：因 练得到各个类别的多启发式融合参数。各特征词提 KNN分类器简单、易实现而被广泛应用，这2组实 取方法性能采用该类别测试集上的平均召回率表 验选它作为实验分类器（其中距离采用向量夹角余 示，实验结果如图2所示。 弦来度量，K=20)。 70 为了对论文所提方法性能进行全面考查，论文 对这2组实验分别做了不同方面的实验内容：第1 组实验主要做特征词选择和召回率方面的实验：第 C 2组主要做耗时和分类性能方面的实验。 --下」入ig在方 3.2第1组实验（各类别数据分布均匀） ·+论的万 在该组实验中，论文对比了基于频率的特征提取 1投 什 方法、基于关联度的特征提取方法以及本文方法性能。 w品 3.2.1特征词选择实验结果 图2 各特征提取方法在各类别下的召回率对比结果 分别采用上面3种方法计算全部词语的4个启 Fig.2 Comparison results of recall rate on feature ex- traction methods 发式值，并根据不同启发式权重进行排序，最后提取
代种群最佳染色体适应度值之差绝对值不超过 员园原缘 遥 采用遗传算法优化选择各启发式的参数权重袁能 够有效避免通过主观经验来确定参数的主观性袁从而 实现参数能够依据训练数据自适应地调优遥 下面的 实验验证结果表明袁采用该遗传算法获得参数权重能 够使本文特征提取方法获得良好的提取效果遥 猿摇 实验验证 猿援员摇 实验总体设置 以 陨灶贼藻造 悦燥则藻圆 阅怎燥 悦孕哉 栽远缘园园尧圆援源 郧匀扎尧 圆 郧月 内存和 宰蚤灶凿燥憎泽 载孕 圆杂孕圆 操作系统的 孕悦 机作为实 验平台袁以 酝粤栽蕴粤月苑援园 为仿真工具袁进行 圆 组实验院 第 员 组实验数据来自互联网抓取的 员 缘园园 个中 文文档袁论文根据该数据集的来源将这些文档分为 缘 个类别袁分别包括新闻尧财经尧科技尧体育和娱乐袁 各类文档数目分布均匀袁都包含 猿园园 篇文档遥 实验 中选择每个类别的 圆园园 篇文档作为训练集袁剩下的 员园园 篇作为测试集遥 第 圆 组实验数据采用复旦大学计算机信息与技术 系国际数据库中心自然语言处理小组构建的中文文本 分类语料库作为实验数据袁 其下载网址为院 澡贼贼责院辕 辕 憎憎憎援灶造责援燥则早援糟灶 辕 糟葬贼藻早燥则蚤藻泽 辕 凿藻枣葬怎造贼援责澡责钥 糟葬贼赃蚤凿越 员远遥 该语料库由 圆园 个类别的 员源 猿苑愿 篇文档组成袁其中 远 员远源 篇为测试文本袁愿 圆员源 篇为训练文本曰各类别的测 试文本集和训练文本集之间互不重叠袁也即一篇文档 仅属一个文本集并且每篇文本仅属于一个类别遥 该语 料库各类别训练文档数分布极其不均匀袁其中训练文 档数较小的类别占大多数袁约为 员员 个类别袁它们的训 练文档数均少于 员园园 篇袁如通信类文档数仅有 圆缘 篇遥 由于所选语料库是中文性质的袁所以这 圆 组实 验都采用中科院计算技术研究所的野汉语词法分析 系统 陨悦栽悦蕴粤杂冶对它进行分词处理曰分类工具软件 都采用纽西兰的 宰葬蚤噪葬贼燥 大学开发的 宰藻噪葬 工具曰因 运晕晕 分类器简单尧易实现而被广泛应用袁这 圆 组实 验选它作为实验分类器 渊其中距离采用向量夹角余 弦来度量袁 运 越 圆园冤遥 为了对论文所提方法性能进行全面考查袁论文 对这 圆 组实验分别做了不同方面的实验内容院第 员 组实验主要做特征词选择和召回率方面的实验曰第 圆 组主要做耗时和分类性能方面的实验遥 猿援圆摇 第 员 组实验渊各类别数据分布均匀冤 在该组实验中袁论文对比了基于频率的特征提取 方法尧基于关联度的特征提取方法以及本文方法性能遥 猿援圆援员摇 特征词选择实验结果 分别采用上面 猿 种方法计算全部词语的 源 个启 发式值袁并根据不同启发式权重进行排序袁最后提取 得分最高的前 员园 个词语作为最后的关键词遥 表 源 为实验对比结果遥 其中袁基于频率的方法用 栽云陨阅云 来表示袁基于关联度的方法用 悦云 来表示袁本文方法 用 酝怎造贼蚤 来表示遥 表 猿摇 猿 种方法下召回率对比结果 栽葬遭造藻 猿 摇 悦燥皂责葬则蚤泽燥灶 则藻泽怎造贼泽 燥枣 则藻糟葬造造 则葬贼藻 燥灶 贼澡则藻藻 皂藻贼澡燥凿泽 方法 关键词 召回率辕 豫 参考答案 负增长尧收入尧中央尧降尧季度尧 财政尧利润尧降低尧涨幅尧增长 要 栽云陨阅云 负增长尧收入尧中央尧季度尧数据尧 降尧影响尧进口尧今年尧同比 缘园 悦云 负增长尧收入尧中央尧财政尧季度尧 降低尧都尧进口尧随后尧做 远园 酝怎造贼蚤 负增长尧收入尧中央尧财政尧降低尧 进口尧利润尧季度尧累计尧财政部 苑园 摇 摇 从表 源 可以看出袁对于野都冶尧野随后冶这类词袁本 文方法能够有效地滤除遥 由于这类单词在文本中通 常具有较高的频率袁很难通过统计的方法有效去除遥 而且本文方法召回率能够达到 苑园豫袁表现出较好的 提取性能遥 此外袁比较特征词自动提取和人工选择袁 猿 种提取方法都得到了 野进口冶这个特征词袁但人工 标注却忽略了这个词语遥 通过查看原文袁野进口冶确 实应该标注为特征词袁反映出人工选择带有较强的 主观性袁这种主观性很容易产生实验误差遥 同样也 反映出特征词自动提取能够在一定程度上克服这种 主观性的缺点遥 猿援圆援圆摇 召回率实验结果 针对测试集的不同类别袁论文分别对比不同特 征词提取方法的性能遥 由于不同类别的多启发式融 合参数不同袁论文利用每个类别的训练语料分别训 练得到各个类别的多启发式融合参数遥 各特征词提 取方法性能采用该类别测试集上的平均召回率表 示袁实验结果如图 圆 所示遥 图 圆摇 各特征提取方法在各类别下的召回率对比结果 云蚤早援圆摇 悦燥皂责葬则蚤泽燥灶 则藻泽怎造贼泽 燥枣 则藻糟葬造造 则葬贼藻 燥灶 枣藻葬贼怎则藻 藻曾鄄 贼则葬糟贼蚤燥灶 皂藻贼澡燥凿泽 第 源 期摇摇摇摇摇摇摇摇摇摇 沈高峰袁等院基于遗传算法优化综合启发式的中文网页特征提取 窑源苑苑窑
·478 智能系统学报 第9卷 从图2可以看出，采用本文方法在各个测试集 5 上的平均召回率均高于基于关联度的方法和基于频 圳 率的方法的性能，这说明该方法提取特征词的性能 8i 4年9 稳定，在各个类别的提取效果均得到明显提高。 iu 3.3第2组实验（各类别数据分布极其不均匀）》 75 --大…米·二次 e年 广学 在这组实验中，采用宏平均F,值和微平均F 7H. 值作为分类性能评价标准，使用3种经典的特征提 5 取方法：信息增益(IG)、x2统计量(CH)、互信息 6 (M)与本文所提特征提取方法作比较。 时 250 城r : 3.3.1耗时实验结果 图5微平均F,实验结果 在实验中，记录了各特征提取方法从开始执行 Fig.5 Comparison results of micro-average F 到执行结束整个过程所消耗的时间，其结果如图3。 利用特征数目的变化来考查分类器的性能，可 以比较准确地反映出该分类器数对据样本变化是否 敏感。图4表明：随着特征数目的递增，宏平均F 值不断增加，但是由于实验数据中各类别样本分布 ÷1 极其不均匀而有所波动：图4表明：随着特征个数的 不断增加，微平均F,值也递增并趋于一个相对较稳 定的值。 书之1冰1.小*汀%护心方出 从图4和图5可以看出：在本文方法所选的前 图3各方法消耗的时间 1500个特征上KNN分类器性能最佳，宏平均F,值 Fig.3 Comparison results of consuming time 约为84%，微平均F,值约为92%：在CHⅢ方法所选 由于本文方法采用了多个指标以及组合方 的前1500个特征上KNN分类器性能最佳，宏平均 法，耗时有所增加。从图3可以看出，在该组实 F,值约为74%，微平均F,值约为86%：在M方法 验中，本文方法在消耗时间方面劣于互信息方法 所选的前1500个特征上KNN分类器性能最佳，宏 和信息增益方法，但优于最耗时的x2统计量方 平均F值约为70%，微平均F,值约为84%：在1G 法，但它们耗时相差不大，这也使得本文方法有 方法所选的前2O00个特征上KNN分类器性能最 一定的实用价值。 佳，宏平均F,值约为61%，微平均F,值约为67%。 3.3.2宏平均和微平均实验结果 这表明在该组实验中，这4个特征提取方法的优劣 从各个特征提取方法所获得的特征集（其中的 依次为本文方法、CH、MI、IG。原因在于：本文方法 特征已按权重逆序进行了排序)中，分别选取相应 在选择特征时，不但考查了特征的词性和词频还考 数目的特征对实验数据进行宏平均F,和微平均F, 查了特征的位置和关联度，从而有效地对待选特征 计算，具体结果如图4和图5所示。 进行全面考查，这使得本文方法受类别分布影响较 小，因此所选特征集较具代表性。CHⅢ方法在选择 特征时不但考查了特征在文档中存在的情况而且还 考查了特征不在文档中的情况，MI方法仅考查了特 征在文档中存在的情况，但它们都没能有效地消除 a 。b以 冗余特征。因此，这2个方法要劣于本文方法，但是 CHⅢI方法要优于MI方法：由于实验中所用语料库中 -5芯， 各类别样本分布相差较大，而IG方法对类别样本分 4 10 A 三74方出 布极其敏感，因此，在此情况下G方法所选择的特 vi 征集代表性最差。 l 图4 宏平均F,实验结果 4结束语 Fig.4 Comparison results of macro-average F 基于统计方法和基于语言学的特征提取方法已
从图 圆 可以看出袁采用本文方法在各个测试集 上的平均召回率均高于基于关联度的方法和基于频 率的方法的性能袁这说明该方法提取特征词的性能 稳定袁在各个类别的提取效果均得到明显提高遥 猿援猿摇 第 圆 组实验渊各类别数据分布极其不均匀冤 在这组实验中袁采用宏平均 云员 值和微平均 云员 值作为分类性能评价标准袁使用 猿 种经典的特征提 取方法院信息增益渊 陨郧冤 尧 曾圆 统计量渊 悦匀陨冤 尧互信息 渊酝陨冤与本文所提特征提取方法作比较遥 猿援猿援员摇 耗时实验结果 在实验中袁记录了各特征提取方法从开始执行 到执行结束整个过程所消耗的时间袁其结果如图 猿遥 图 猿摇 各方法消耗的时间 云蚤早援猿摇 悦燥皂责葬则蚤泽燥灶 则藻泽怎造贼泽 燥枣 糟燥灶泽怎皂蚤灶早 贼蚤皂藻 由于本文方法采用了多个指标以及组合方 法袁耗时有所增加遥 从图 猿 可以看出袁在该组实 验中袁本文方法在消耗时间方面劣于互信息方法 和信息增益方法袁但优于最耗时的 曾圆 统计量方 法袁但它们耗时相差不大袁这也使得本文方法有 一定的实用价值遥 猿援猿援圆摇 宏平均和微平均实验结果 从各个特征提取方法所获得的特征集渊其中的 特征已按权重逆序进行了排序冤 中袁分别选取相应 数目的特征对实验数据进行宏平均 云员 和微平均 云员 计算袁具体结果如图 源 和图 缘 所示遥 图 源摇 宏平均 云员 实验结果 云蚤早援源摇 悦燥皂责葬则蚤泽燥灶 则藻泽怎造贼泽 燥枣 皂葬糟则燥鄄葬增藻则葬早藻 云员 图 缘摇 微平均 云员 实验结果 云蚤早援缘摇 悦燥皂责葬则蚤泽燥灶 则藻泽怎造贼泽 燥枣 皂蚤糟则燥鄄葬增藻则葬早藻 云员 利用特征数目的变化来考查分类器的性能袁可 以比较准确地反映出该分类器数对据样本变化是否 敏感遥 图 源 表明院随着特征数目的递增袁宏平均 云员 值不断增加袁但是由于实验数据中各类别样本分布 极其不均匀而有所波动曰图 源 表明院随着特征个数的 不断增加袁微平均 云员 值也递增并趋于一个相对较稳 定的值遥 从图 源 和图 缘 可以看出院在本文方法所选的前 员 缘园园 个特征上 运晕晕 分类器性能最佳袁宏平均 云员 值 约为 愿源豫袁微平均 云员 值约为 怨圆豫曰在 悦匀陨 方法所选 的前 员 缘园园 个特征上 运晕晕 分类器性能最佳袁宏平均 云员 值约为 苑源豫袁微平均 云员 值约为 愿远豫曰在 酝陨 方法 所选的前 员 缘园园 个特征上 运晕晕 分类器性能最佳袁宏 平均 云员 值约为 苑园豫袁微平均 云员 值约为 愿源豫曰在 陨郧 方法所选的前 圆 园园园 个特征上 运晕晕 分类器性能最 佳袁宏平均 云员 值约为 远员豫袁微平均 云员 值约为 远苑豫遥 这表明在该组实验中袁这 源 个特征提取方法的优劣 依次为本文方法尧悦匀陨尧酝陨尧陨郧遥 原因在于院本文方法 在选择特征时袁不但考查了特征的词性和词频还考 查了特征的位置和关联度袁从而有效地对待选特征 进行全面考查袁这使得本文方法受类别分布影 响较 小袁因此所选特征集较具代表性遥 悦匀陨 方法在选择 特征时不但考查了特征在文档中存在的情况而且还 考查了特征不在文档中的情况袁酝陨 方法仅考查了特 征在文档中存在的情况袁但它们都没能有效地消除 冗余特征遥 因此袁这 圆 个方法要劣于本文方法袁但是 悦匀陨 方法要优于 酝陨 方法曰由于实验中所用语料库中 各类别样本分布相差较大袁而 陨郧 方法对类别样本分 布极其敏感袁因此袁在此情况下 陨郧 方法所选择的特 征集代表性最差遥 源摇 结束语 基于统计方法和基于语言学的特征提取方法已 窑源苑愿窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 沈高峰，等：基于遗传算法优化综合启发式的中文网页特征提取 ·479· 经被广泛应用于特征词提取。本文结合2种方法的 [6]LEE S,PARK C,KOO J Y.Feature selection in the Lapla- 优点，提出了一种基于遗传算法优化综合启发式的 cian support vector machine[J].Computational Statistics 中文网页特征提取方法。该方法能够有效利用词语 and Data Analysis,2011.55(1):567-577. 的内在属性和词语之间的链接关系，通过多种启发 [7]SONG Qinbao,NI Jingjie,WANG Guangtao.A fast cluste- 式表征中文文本的特征，对特征词进行较全面的考 ring-based feature subset selection algorithm for high-dimen- 查。实验结果表明该方法能够有效融合不同因素的 sional data[J].IEEE Transactions on Knowledge and Data Engineering.2013.25(1):1-14. 优点，与传统方法相比，该方法具有一定的优势，从 [8]CHUANG L Y,YANG C H,LI J C.Chaotic maps based on 而使得该方法在文本挖掘方面有一定的实用价值。 binary particle swarm optimization for feature selection[]. 由于不同类别的文档的因素分布不尽相同，论 Journal of Applied Soft Computing,2011,11 (1):239- 文接下来的工作将继续研究不同领域内采用该方法 248. 的特征词提取的性能。另外通过实验发现，对于人 [9]李纲，戴强斌.基于词汇链的关键词自动标引方法[J] 工标注的结果，主观性因素的影响依然存在。论文 图书情报知识，2011,12(3)：67-71. 还将进一步研究合理的标注方式，对现有网页数据 LI Gang,DAI Qiangbin.Keywords automatic indexing based 进行处理，减少主观因素带来的实验误差。 on lexical chains[J].Document,Information and Knowl- 另外，本文方法虽然采用了十进制编码以及自适 edge,2011,12(3):67-71 应交叉变异操作等措施来确保遗传算法的性能，进而 [10]朱颢东，李红婵.基于互信息和粗糙集理论的特征选择 保证本文特征抽取方法的性能，但是目前有些智能优 [J].计算机工程，2011,37(15)：181-183. 化算法比遗传算法优秀，例如粒子群优化算法、蜂群 ZHU Haodong,LI Hongchan.Feature selection based on 优化算法等，如果把它们用于本文方法的参数权重优 mutual information and rough set theory[J].Computer En- gineering,2011,37(15):181-183. 化，效果可能会优于遗传算法。为此，作者下一步研 [11]JEONG Y S,KANG I H,JEONG M K.A new feature se- 究工作就是尝试把其他智能优化算法用于本文方法 lection method for one-class classification problemsJ. 的参数权重优化，以进一步提高本文方法的性能。 IEEE Transactions on Systems,Man,and Cybernetics, 参考文献： Part C:Applications and Reviews,2012,42(6):1500- 1509. [1]GHEYAS I A,SMITH L S.Feature subset selection in large [12]LIU Z,LIU Q.Balanced feature selection method for Inter- dimensionality domains[J].Pattern Recognition,2010,43 net traffic classification[]]Networks,2012,1 (2):74- (1):5-13. 83. [2]NGUYEN M H,TORRE F D.Optimal feature selection for [13]MAHROOGHY M.YOUNAN N H,ANANTHARAJ V G. support vector machines[J].Pattern Recognition,2010,43 On the use of the genetic algorithm filter-based feature se- (3):584-591 lection technique for satellite precipitation estimation[J]. [3]ZHAO Zheng,WANG Lei,LIU Huan.On similarity preser- Geoscience and Remote Sensing Letters,2012,9(5): ving feature selection[J].IEEE Transactions on Knowledge 963-967. and Data Engineering,2013,25(3):619-632. 作者简介： [4]JAVED K,BABRI H A,SAEED M.Feature selection 沈高峰，男，1978年生，讲师，主要 based on class-dependent densities for high-dimensional bi- 研究方向为数据库应用、数据挖掘。通 nary data[].IEEE Transactions on Knowledge and Data 过省级成果鉴定8项，先后发表学术论 Engineering,2012,24(3):465-477. 文11篇，参与编写教材4部。 [5]WU Xindong,YU Kui DING Wei.Online feature selection with streaming features[].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(5):1178- 1192
经被广泛应用于特征词提取遥 本文结合 圆 种方法的 优点袁提出了一种基于遗传算法优化综合启发式的 中文网页特征提取方法遥 该方法能够有效利用词语 的内在属性和词语之间的链接关系袁通过多种启发 式表征中文文本的特征袁对特征词进行较全面的考 查遥 实验结果表明该方法能够有效融合不同因素的 优点袁与传统方法相比袁该方法具有一定的优势袁从 而使得该方法在文本挖掘方面有一定的实用价值遥 由于不同类别的文档的因素分布不尽相同袁论 文接下来的工作将继续研究不同领域内采用该方法 的特征词提取的性能遥 另外通过实验发现袁对于人 工标注的结果袁主观性因素的影响依然存在遥 论文 还将进一步研究合理的标注方式袁对现有网页数据 进行处理袁减少主观因素带来的实验误差遥 另外袁本文方法虽然采用了十进制编码以及自适 应交叉变异操作等措施来确保遗传算法的性能袁进而 保证本文特征抽取方法的性能袁但是目前有些智能优 化算法比遗传算法优秀袁例如粒子群优化算法尧蜂群 优化算法等袁如果把它们用于本文方法的参数权重优 化袁效果可能会优于遗传算法遥 为此袁作者下一步研 究工作就是尝试把其他智能优化算法用于本文方法 的参数权重优化袁以进一步提高本文方法的性能遥 参考文献院 咱员暂郧匀耘再粤杂 陨 粤袁 杂酝陨栽匀 蕴 杂援 云藻葬贼怎则藻 泽怎遭泽藻贼 泽藻造藻糟贼蚤燥灶 蚤灶 造葬则早藻 凿蚤皂藻灶泽蚤燥灶葬造蚤贼赠 凿燥皂葬蚤灶泽咱 允暂援 孕葬贼贼藻则灶 砸藻糟燥早灶蚤贼蚤燥灶袁 圆园员园袁 源猿 渊员冤 院 缘鄄员猿援 咱圆暂晕郧哉再耘晕 酝 匀袁 栽韵砸砸耘 云 阅援 韵责贼蚤皂葬造 枣藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 枣燥则 泽怎责责燥则贼 增藻糟贼燥则 皂葬糟澡蚤灶藻泽咱 允暂援 孕葬贼贼藻则灶 砸藻糟燥早灶蚤贼蚤燥灶袁 圆园员园袁 源猿 渊猿冤 院 缘愿源鄄缘怨员援 咱猿暂在匀粤韵 在澡藻灶早袁 宰粤晕郧 蕴藻蚤袁 蕴陨哉 匀怎葬灶援 韵灶 泽蚤皂蚤造葬则蚤贼赠 责则藻泽藻则鄄 增蚤灶早 枣藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶咱 允暂援 陨耘耘耘 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 运灶燥憎造藻凿早藻 葬灶凿 阅葬贼葬 耘灶早蚤灶藻藻则蚤灶早袁 圆园员猿袁 圆缘渊猿冤 院 远员怨鄄远猿圆援 咱 源 暂 允粤灾耘阅 运袁 月粤月砸陨 匀 粤袁 杂粤耘耘阅 酝援 云藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 遭葬泽藻凿 燥灶 糟造葬泽泽鄄凿藻责藻灶凿藻灶贼 凿藻灶泽蚤贼蚤藻泽 枣燥则 澡蚤早澡鄄凿蚤皂藻灶泽蚤燥灶葬造 遭蚤鄄 灶葬则赠 凿葬贼葬咱 允暂援 陨耘耘耘 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 运灶燥憎造藻凿早藻 葬灶凿 阅葬贼葬 耘灶早蚤灶藻藻则蚤灶早袁 圆园员圆袁 圆源渊猿冤 院 源远缘鄄源苑苑援 咱缘暂宰哉 载蚤灶凿燥灶早袁 再哉 运怎蚤 袁阅陨晕郧 宰藻蚤援 韵灶造蚤灶藻 枣藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 憎蚤贼澡 泽贼则藻葬皂蚤灶早 枣藻葬贼怎则藻泽 咱 允暂援 陨耘耘耘 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 孕葬贼贼藻则灶 粤灶葬造赠泽蚤泽 葬灶凿 酝葬糟澡蚤灶藻 陨灶贼藻造造蚤早藻灶糟藻袁 圆园员猿袁 猿缘 渊 缘冤 院 员员苑愿鄄 员员怨圆援 咱远暂蕴耘耘 杂袁 孕粤砸运 悦袁 运韵韵 允 再援 云藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 蚤灶 贼澡藻 蕴葬责造葬鄄 糟蚤葬灶 泽怎责责燥则贼 增藻糟贼燥则 皂葬糟澡蚤灶藻 咱 允 暂援 悦燥皂责怎贼葬贼蚤燥灶葬造 杂贼葬贼蚤泽贼蚤糟泽 葬灶凿 阅葬贼葬 粤灶葬造赠泽蚤泽袁 圆园员员袁 缘缘渊员冤 院 缘远苑鄄缘苑苑援 咱苑暂 杂韵晕郧 匝蚤灶遭葬燥袁 晕陨 允蚤灶早躁蚤藻袁 宰粤晕郧 郧怎葬灶早贼葬燥援 粤 枣葬泽贼 糟造怎泽贼藻鄄 则蚤灶早鄄遭葬泽藻凿 枣藻葬贼怎则藻 泽怎遭泽藻贼 泽藻造藻糟贼蚤燥灶 葬造早燥则蚤贼澡皂 枣燥则 澡蚤早澡鄄凿蚤皂藻灶鄄 泽蚤燥灶葬造 凿葬贼葬咱 允暂援 陨耘耘耘 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 运灶燥憎造藻凿早藻 葬灶凿 阅葬贼葬 耘灶早蚤灶藻藻则蚤灶早袁 圆园员猿袁 圆缘渊员冤 院 员鄄员源援 咱愿暂悦匀哉粤晕郧 蕴 再袁 再粤晕郧 悦 匀袁 蕴陨 允 悦援 悦澡葬燥贼蚤糟 皂葬责泽 遭葬泽藻凿 燥灶 遭蚤灶葬则赠 责葬则贼蚤糟造藻 泽憎葬则皂 燥责贼蚤皂蚤扎葬贼蚤燥灶 枣燥则 枣藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶咱 允暂援 允燥怎则灶葬造 燥枣 粤责责造蚤藻凿 杂燥枣贼 悦燥皂责怎贼蚤灶早袁 圆园员员袁 员员 渊 员冤 院 圆猿怨鄄 圆源愿援 咱怨暂李纲袁戴强斌援 基于词汇链的关键词自动标引方法咱允暂援 图书情报知识袁 圆园员员袁员圆渊猿冤 院 远苑鄄苑员援 蕴陨 郧葬灶早袁 阅粤陨 匝蚤葬灶早遭蚤灶援 运藻赠憎燥则凿泽 葬怎贼燥皂葬贼蚤糟 蚤灶凿藻曾蚤灶早 遭葬泽藻凿 燥灶 造藻曾蚤糟葬造 糟澡葬蚤灶泽 咱 允暂援 阅燥糟怎皂藻灶贼袁 陨灶枣燥则皂葬贼蚤燥灶 葬灶凿 运灶燥憎造鄄 藻凿早藻袁 圆园员员袁 员圆渊猿冤 院 远苑鄄苑员 咱员园暂朱颢东袁 李红婵援 基于互信息和粗糙集理论的特征选择 咱允暂援计算机工程袁 圆园员员袁 猿苑 渊员缘冤 院 员愿员鄄员愿猿援 在匀哉 匀葬燥凿燥灶早袁 蕴陨 匀燥灶早糟澡葬灶援 云藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 遭葬泽藻凿 燥灶 皂怎贼怎葬造 蚤灶枣燥则皂葬贼蚤燥灶 葬灶凿 则燥怎早澡 泽藻贼 贼澡藻燥则赠咱 允暂援 悦燥皂责怎贼藻则 耘灶鄄 早蚤灶藻藻则蚤灶早袁 圆园员员袁 猿苑 渊员缘冤 院 员愿员鄄员愿猿援 咱员员暂 允耘韵晕郧 再 杂袁 运粤晕郧 陨 匀袁 允耘韵晕郧 酝 运援 粤 灶藻憎 枣藻葬贼怎则藻 泽藻鄄 造藻糟贼蚤燥灶 皂藻贼澡燥凿 枣燥则 燥灶藻鄄糟造葬泽泽 糟造葬泽泽蚤枣蚤糟葬贼蚤燥灶 责则燥遭造藻皂泽 咱 允 暂援 陨耘耘耘 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 杂赠泽贼藻皂泽袁 酝葬灶袁 葬灶凿 悦赠遭藻则灶藻贼蚤糟泽袁 孕葬则贼 悦院 粤责责造蚤糟葬贼蚤燥灶泽 葬灶凿 砸藻增蚤藻憎泽袁 圆园员圆袁 源圆渊 远冤 院 员缘园园鄄 员缘园怨援 咱员圆暂蕴陨哉 在袁 蕴陨哉 匝援 月葬造葬灶糟藻凿 枣藻葬贼怎则藻 泽藻造藻糟贼蚤燥灶 皂藻贼澡燥凿 枣燥则 陨灶贼藻则鄄 灶藻贼 贼则葬枣枣蚤糟 糟造葬泽泽蚤枣蚤糟葬贼蚤燥灶咱 允暂援 晕藻贼憎燥则噪泽袁 圆园员圆袁 员 渊 圆冤 院 苑源鄄 愿猿援 咱员猿暂酝粤匀砸韵韵郧匀再 酝袁再韵哉晕粤晕 晕 匀袁 粤晕粤晕栽匀粤砸粤允 灾 郧援 韵灶 贼澡藻 怎泽藻 燥枣 贼澡藻 早藻灶藻贼蚤糟 葬造早燥则蚤贼澡皂 枣蚤造贼藻则鄄遭葬泽藻凿 枣藻葬贼怎则藻 泽藻鄄 造藻糟贼蚤燥灶 贼藻糟澡灶蚤择怎藻 枣燥则 泽葬贼藻造造蚤贼藻 责则藻糟蚤责蚤贼葬贼蚤燥灶 藻泽贼蚤皂葬贼蚤燥灶 咱 允暂援 郧藻燥泽糟蚤藻灶糟藻 葬灶凿 砸藻皂燥贼藻 杂藻灶泽蚤灶早 蕴藻贼贼藻则泽袁 圆园员圆袁 怨 渊 缘 冤 院 怨远猿鄄怨远苑援 作者简介院 沈高峰袁男袁员怨苑愿 年生袁讲师袁主要 研究方向为数据库应用尧数据挖掘遥 通 过省级成果鉴定 愿 项袁先后发表学术论 文 员员 篇袁参与编写教材 源 部遥 第 源 期摇摇摇摇摇摇摇摇摇摇 沈高峰袁等院基于遗传算法优化综合启发式的中文网页特征提取 窑源苑怨窑