基于半贪心策略的特征子集选择算法

《基于半贪心策略的特征子集选择算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于半贪心策略的特征子集选择算法摘要本文引入了一种基于半贪心策略的特征子集选择算法（SGFS），用它来改进NFS[1]算法在构造特征子集时所采取的绝对贪心的策略。算法求解时每一轮循环基本上是由两个阶段构成的：构造可行解阶段和搜索优化阶段。构造可行解阶段的作用就是产生一个可行解，然后在它的基础上进行搜索优化以产生局部最优解。我们把在给定的循环次数内找到的那个最好的局部最优解当作全局最优解。测试结果表明本文提出的算法选出的特征代表性强、求解速度较快。关键词特征子集选择，NFS，搜索优化Semi-greedybasedf

2、eaturesubsetselectionalgorithmAbstractAkindoffeaturesubsetselectionalgorithmSGFSwasproposedhere,whichisbasedonsemi-greedystrategy,otherthantheabsolutegreedystrategyusedinthealgorithmofNFS.EachiterationofSGFSconsistsbasicallyoftwophases：constructionandsearchopt

3、imization.Ontheconstruction,itbuildsafeasiblesolution,andthefeasiblesolutionwasoptimizeduntilalocalminimumisfoundduringthesearchoptimizationphase.Thebestoverallsolutioniskeptastheresult.Thetestshowsthisalgorithmcanselectmorerepresentativefeatureeffectively.Key

4、wordsFeaturesubsetselection,NFS,searchoptimization1引言特征子集选择问题是指从一个给定的候选特征集合中，根据一定的评价标准，选出一个特征子集，使其能够一致地描述给定的例子集合。很明显通过特征子集选择，可以减少描述原数据集合的特征（属性）的数目，进而可以减少原数据集合的例子数。而在实际应用中，数据挖掘或模式识别所处理的对象是大型的数据库。其中每个记录都包含了许多特征（属性），由于在数据的采集过程中，可能会因为某些特征提取费用或设备和人为等原因，造成了属性集合中包含了一

5、些未知的、无关的或冗余的特征（属性）。这些特征（属性）的存在会给数据挖掘或模式识别算法带来很多麻烦。近年来，随着机器学习和数据挖掘在实际领域中的不断应用，特征子集选择算法研究逐渐成为人工智能领域的一个研究热点[2-6]。因为，通过特征子集选择：a.可以大大减少数据的存储量并使存储错误率降低。b.加快了数据挖掘的进度。c.使得生成的规则简化，增强规则的可理解性。然而不幸的是最优特征子集选择问题是NP难题[7]，就是说求解最优特征子集选择问题目前不存在一个多项式时间算法，我们只能用启发式算法来求得一个近似最优的解。本文

6、引入了一种基于半贪心策略的特征子集合选择算法，用它来改进NFS[1]算法在构造特征子集时所采取的绝对贪心的策略。测试结果表明本文提出的算法选出的特征代表性强、求解速度较快，所选的特征子集也较具有代表性。在本文余下的部分中，先介绍本文中涉及到的一些基本概念，接着对NFS算法的思想作一些介绍，然后详细介绍本文所提出的算法，最后就本文的算法在一些实际领域的应用进行了实验比较。2一些基本概念设集合为当前训练例子集合，为描述的特征集合。例子，其中表示第个例子中的第个特征的取值，且，为的值域，。假设集合S依其类别特征取值的不同

7、可以分为C个类别，即，其中C为S中的类别数，为第个类别的例子集合。定义1若例子集合之间不包含相同的例子，即我们称S在特征集合F的描述下是一致的，否则是不一致的。定义2特征子集选择是指从F中选出一个由尽可能少的特征所组成的集合M，，且S在特征集合M的描述下也是一致的。定义3特征集合F有个可能的特征子集，我们把这些子集中能够一致地描述训练例子集合S的子集称为可行解。把在所有可行解中包含特征数目最少的那个可行解称为最优解。根据定义1可知，原训练例子集合S在特征集合F的描述下可能是不一致的，对此应在特征子集选择算法开始之前

8、把S中不一致的例子删掉，使其成为一致的例子集合。3NFS算法简介容忍噪音的特征子集选择算法（noise-tolerantalgorithmforfeaturesubsetselection，NFS[1]）将聚类的思想引入到噪音的处理，时将Gini系数和墨西哥帽函数应用于特征选取，实现了对含有噪音数据集的特征子集选择。本节首先依次给出NFS算法对噪音的分类和处