烟叶香气风格分类中的特征选择算法研究.doc

烟叶香气风格分类中的特征选择算法研究烟叶香气风格分类中的特征选择算法研究 工程技术 计算机光盘软件与应用 ComputerCDSoftwareandApplications2010年第l4期 烟叶香气风格分类中的特征选择算法研究 刘国强,贺英,王伟 (1.中国海洋大学,山东青岛266071;2.青岛大学,山东青岛266071) 摘要:烟叶香气风格分类是利用烟叶外观质量,理化成分判定其香型,香气质量的类别.为了提高分类能力,通过 特征选择发现最佳属性集是一种有效的方法.本文对比研究了信息增益率(GainRatio),RehefF,CFS,Wrapper四种特征选 择方法改善烟叶香气分类器性能的差异.实验结果表明:基于遗传算法的Wrapper方法优于其他三种方法,所得最佳属性 集的特征维数低,而且使分类精确率大大提高. 关键词:特征选择;分类;信息增益率;RelietF;CFS 中图分类号:TP301.6文献标识码:A文章编号:10079599(2010)14003602 TheFeatureSelectionAlgorithm ResearchontheTobaccoLeafAromaStyleClassification LiuGuoqiang, HeYing2, WangWei f1.ChinaOceanUniversity,Qingdao266071,China;2.QingdaoUniversity,Qingdao266071,China) Abstract:Theclassificationofthetobaccoaromaflavorisevaluatedaccordingtothetobaccophysicalandchemical compositions.InordertOimprovetheclassificationperformance,itisaneffectivemethodthatfmdthebestfeaturesetbasedon featureselection.Thediff-erenceoftheclassificationperformanceoftobaccoaromamodelisfoundbycomparingfourfeature selectionmethods.suchasGainRatio.ReliefF,CFSandWrappermethods.TheexperimentresultshaveshownthattheWrapper methodbasedonthegeneticalgorithmiSsuperiortootherthreemethods.andthecharacterdimensioniSthelowest,SOitcan greatlyimprovedtheclassificationaccuracy. Keywords:Featureselecti0n:Classificati0n:InformationGainRatio;ReliefF;CFS 一 ,引言 烟叶的香气风格是人对烟叶的一种感官评价,是受烟叶特定 的生态条件,栽培技术,遗传因素等因素的影响.近年来,不少 学者利用统计分析,机器学习技术建立烟叶感官质量评价模型 11,2 试图利用计算机建立一种快速评价烟叶香气风格的手段,有 .助于实现卷烟配方数字化设计.由于建立分类器的输入属性维数 较多,其中存在一部分无关特征或冗余特征,导致分类器的精度 和时间效率难以提高.一些学者试图通过改进一些分类算法来改 善分类器性能,但效果并不明显. 特征选择是机器学习领域的热点研究问题之一特征选择是 从原始特征集中按照评估标准选择满足最优的特征子集J.目前 特征选择已在文本分类,数据挖掘,基因工程,计算机视觉,信 息检索等领域中得到了广泛应用研究.本文研究了四种典型的特 征选择算法:ReliefF,信息增益率(GainRatio),相关度量(CFS), Wrapper的基本原理,以及对分类器性能的改善能力,并应用于烟 叶香气风格分类问题. 二,特征选择 特征选择主要有四个步骤,首先按照一定的搜索策略产生候 选特征子集,再通过某个评价函数评估特征子集的优劣,然后根 据预先指定的特征数目等条件决定特征选择算法什么时候停止, 最后验证最终所选的特征子集的有效性.Dash和Lju将特征选择算 法主要分为三类:Filter算法族,Wrapper算法族以及混合算法J. 下面针对典型的特征选择算法简单介绍. (一)RiliefF算法 Relief算法是由Kira提出的一种特征权重算法j.Kononenko 提出了一种改进的ReliefF算法,它能处理多类问题.对属性的数 据类型没有要求,是一种比较有效的特征选择算法I6】.算法的主 要步骤如下: 1.从训练集D中随机选择一个样本R; 2.从和R同类的样本集中找出R的k个近邻样本H,(,=l,2,),从 每个R的不同类的样本集中找出k个近邻样本M(=l,2,-,); 3.根据规则更新每个特征的权重:如果R和最近邻样本H在某 个特征上的距离小于R和最近邻样本M上的距离,则说明该特征对 区分同类和不同类的最近邻是有益的,则增加该特征的权重;反 之,则降低该特征的权重; 4.输出:特征权重大于阈值6的特征组成的特征子集T. (二)信息增益率(GainRatio)算法 信息增益率算法是根据评价每个特征对整体样本分类所贡献 的信息增量多少作为衡量特征重要性的标准,信息越多,特征越 重要.假设所研究的分类问题数据集S=,X,c,包含m个 特征,类别c共有n个类别,每一个类别出现的概率为P,则分类 系统的信息熵为:()=一?P.1ogzPl(1) 某,属性x.对类属性c的信息增益如下: IG(C,Xf)=H(c)一H(CIX.)=H(c)一H(CIX.=)(2) 本文采用信息增益率:GainRatio(X)=IG(C,X)/H(X.)(3) 其中,H(c)是类属性C的信息熵,特征x.共有p个取值,公式 (2)的第2项是特征x对数据集s进行分类后的熵的期望值. (三)相关度量CFS算法 相关度量CFS特征选择算法是基于相关性的启发式评价函 数,度量每个属性与类属性是高度相关还是不相关,将不关联的 冗余属性去除,最终对特征属性进行降序排序获得特征子集.评 价函数(式4)中Ms是属性子集中k个属性的启发式价值.ksr为属 性与类之间相关性的均值,是属性间交互相关性的均值】. M=(4)? +(一1)rz 在对离散数据进行相关度量时,利用对称不确定方法(式5)计 算属性与类属性之间的相关性大小和属性x与属性Y之间的相关 性大小. UC.2丽面I(5)5H(y)+H(x)l(J (三)Wrapper方法 2010年第14期 计算机光盘软件与应用 ComputerCDSoftwareandApplications工程技术 Wrapper方法是一种使用归纳算法结合重复抽样技术来评价 特征准确性的特征选择算法f8】.本文采用基于遗传算法的wrapper 方法.算法主要步骤如下: 1.编码:采用二进制编码,1表示该位代表的特征被选中,0 表示特征未被选中. 2.种群初始化:随机生成m个染色体,每个染色体含有n个基 因,代表n维特征属性. 3.对种群中每个染色体包含的特征属性,作为训练数据,训 练分类器,以分类器最大准确率为评价函数计算评估值,取出最 优个体; 4.如果循环次数等终止条件满足,则算法结束,以最优个体 为输出,否则,转步骤5; 5.从种群中选择个体并进行交叉,变异操作,得到下一代个 体,返回步骤3; ,实验研究 三(一)实验数据及方法 为了找到适合烟叶香气风格分类的有效的特征选择方法,下 面从特征子集维数,分类器性能两方面开展对比实验.实验数据 集来自于山东中烟提供的全国主要产区原烟质量数据,22个属性 包括基本信息(产地,等级,品种),生态条件(海拔高度,地块) 外观质量(成熟度,叶片结构,身份,油份,色泽,发育状况), 理化指标(总烟碱,总糖,还原糖,总氮,氯,钾),香气风格指 标(香型,香气质,香气量).选用153个实验样本,香型分为7类: 清香型,清偏中,中偏清,中间香,中偏浓,浓偏中,浓香. 本实验在机器学习的开源平台Weka的KnowledgeFlow中运 行.针对烟叶香气风格样本,将数据离散化后,分别运行ReliefF, GainRatio,CFS,Wrapper四种算法,计算各统计度量值,根据设 定的阈值过滤冗余信息,将特征选择前后的数据集进行K近邻分 类,采用十折交叉验证法学习.四种特征选择算法的参数设置如 表1. (二)实验结果及分析 通过对比实验结果中所得四种特征选择方法得到的不同特征 子集维数以及分类器性能,可以评价适合解决烟叶香气风格分类 问题的特征选择方法.如表2所见,ReliefF方法所选择特征子集维 数最高,CFS方法得到的特征子集维数最低. 表2特征子集大小对比 方法名未特征选择RelietFGainRatioCFSWrapperl 属性个数2210(rank>0.1)9(rank>0.1)34I ReliefF方法所选择的烟叶香气风格特征子集包括品种,产地, 身份,海拔高度,叶片结构,色泽,油份,发育状况,等级,氯. GainRatio方法所选择的烟叶香气风格特征子集包括品种,总糖, 还原糖,产地,海拔高度,总烟碱,钾,总氮.CFS方法所选择 的烟叶香气风格特征子集包括品种,总糖,还原糖.Wrapper方法 选择的最佳烟叶香气风格特征子集包括产地,品种,叶片结构, 成熟度. 表3中对比了四种特征选择算法和未使用特征选择算法的烟 叶香气风格分类器的准确率.分类器的分类准确率都比原始特征 集所建模的性能高,说明原始特征集中存在一定的冗余特征.其 中基于遗传算法的Wrapper算法选择的特征子集,能够使K近邻分 类器分类准确率达到84%,明显优于CFS,GainRafio,RefiefF算 法,比原始特征集的分类器准确率超出23%. 方法名未特征选择ReliefF法GainRatioCFSWrapper 分类准确率%61.46669.373.884.35 TPrate0.5040.4830.7410.5730.8l8 Precision0.6050.5700.7430.7680.841 Gmean0.590.550.7450.550.838 Fmeasure0.5150.5030.7400.6060.828 四,结束语 通过对四种特征选择算法进行对比研究,可以得知ReliefF与 GainRatio算法只能对所有特征按权重排序,不能直接去除冗余特 征,还需要人为考虑用权重阈值来筛选特征.CFS算法通用性强, 时间短.但这些Filter方法所选的特征子集在分类准确率方面通常 低于Wrapper方法.说明在解决实际的高维分类问题时,选择合适 的特征选择算法是非常必要的,通过剔除冗余特征,降低输入维 数,既缩短分类器建模时间,又能大幅提高分类器精度.另外, 实验也发现Wrapper方法虽然能得到较好的特征子集,但是需要先 确定分类器算法,使其通用性降低,而且搜索策略使其特征选择 时间稍长,今后将在这些方面做深入研究. 参考文献: 【1】高妍方,赵青松,陈英武.基于代价敏感贝叶斯网络的烟叶感官鹰 量评价lJ】.计算机工程,2008,34(21):187189 【2】赵青松.基于支持向量机的烟叶感官品质评价.计算机工程及 应用,2007,43(10):236237 3LiuHuan,YuLei.Towardintegratingfeatureselectionalgorithms forclassificationandclusteringJ.IEEETransactionsonKnowledge andDataEngineering,2005,17(4):491502 【4DashM,LiuH.Featureselectionforclassifications.IntelligentData Analysis:AnInternationalJournal,1997:131156 【5KiraK,RendellL.A.Thefeatureselectionproblem:Traditional methodsandanewalgorithm.In:ProceedingsofNinthNional ConferenceonArtificialIntellence,1992.129134 6KononenkoI.Estimationattributes:analysisandextensio