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

基于半贪心策略的特征子集选择算法 摘 要 本文引入了一种基于半贪心策略的特征子集选择算法（SGFS），用它来改进NFS 1 算法在构造特征子集时所采取的绝对贪心的策略。算法求解时每一轮循环基本上是由两个阶段构成的：构造可行解阶段和搜索优化阶段。构造可行解阶段的作用就是产生一个可行解，然后在它的基础上进行搜索优化以产生局部最优解。我们把在给定的循环次数内找到的那个最好的局部最优解当作全局最优解。测试结果表明本文提出的算法选出的特征代表性强、求解速度较快。关键词 特征子集选择，NFS，搜索优化 Semi-greedy based feature subset selection algorithmAbstract A kind of feature subset selection algorithm SGFS was proposed here, which is based on semi-greedy strategy, other than the absolute greedy strategy used in the algorithm of NFS. Each iteration of SGFS consists basically of two phases：construction and search optimization. On the construction, it builds a feasible solution, and the feasible solution was optimized until a local minimum is found during the search optimization phase. The best overall solution is kept as the result. The test shows this algorithm can select more representative feature effectively. Keywords Feature subset selection, NFS, search optimization1 引言特征子集选择问题是指从一个给定的候选特征集合中，根据一定的评价标准，选出一个特征子集，使其能够一致地描述给定的例子集合。很明显通过特征子集选择，可以减少描述原数据集合的特征（属性）的数目，进而可以减少原数据集合的例子数。而在实际应用中，数据挖掘或模式识别所处理的对象是大型的数据库。其中每个记录都包含了许多特征（属性），由于在数据的采集过程中，可能会因为某些特征提取费用或设备和人为等原因，造成了属性集合中包含了一些未知的、无关的或冗余的特征（属性）。这些特征（属性）的存在会给数据挖掘或模式识别算法带来很多麻烦。近年来，随着机器学习和数据挖掘在实际领域中的不断应用，特征子集选择算法研究逐渐成为人工智能领域的一个研究热点 2-6 。因为，通过特征子集选择：a. 可以大大减少数据的存储量并使存储错误率降低。b. 加快了数据挖掘的进度。c. 使得生成的规则简化，增强规则的可理解性。然而不幸的是最优特征子集选择问题是NP难题 7 ，就是说求解最优特征子集选择问题目前不存在一个多项式时间算法，我们只能用启发式算法来求得一个近似最优的解。本文引入了一种基于半贪心策略的特征子集合选择算法，用它来改进NFS 1 算法在构造特征子集时所采取的绝对贪心的策略。测试结果表明本文提出的算法选出的特征代表性强、求解速度较快，所选的特征子集也较具有代表性。在本文余下的部分中，先介绍本文中涉及到的一些基本概念，接着对NFS算法的思想作一些介绍，然后详细介绍本文所提出的算法，最后就本文的算法在一些实际领域的应用进行了实验比较。2 一些基本概念设集合为当前训练例子集合，为描述的特征集合。例子，其中表示第个例子中的第个特征的取值，且，为的值域，。假设集合S依其类别特征取值的不同可以分为 C个类别，即，其中C为S中的类别数，为第个类别的例子集合。 定义1 若例子集合之间不包含相同的例子，即我们称S在特征集合F的描述下是一致的，否则是不一致的。定义2 特征子集选择是指从F中选出一个由尽可能少的特征所组成的集合M，且S在特征集合M的描述下也是一致的。定义3 特征集合F有个可能的特征子集，我们把这些子集中能够一致地描述训练例子集合S的子集称为可行解。把在所有可行解中包含特征数目最少的那个可行解称为最优解。根据定义1可知，原训练例子集合S在特征集合F的描述下可能是不一致的，对此应在特征子集选择算法开始之前把S中不一致的例子删掉，使其成为一致的例子集合。3 NFS算法简介容忍噪音的特征子集选择算法（noise-tolerant algorithm for feature subset selection，NFS 1 ）将聚类的思想引入到噪音的处理，时将Gini系数和墨西哥帽函数应用于特征选取，实现了对含有噪音数据集的特征子集选择。本节首先依次给出NFS算法对噪音的分类和处理方法、特征评价函数和噪音终止评价函数，然后给N FS算法的基本思想。3.1 噪音的产生 在实际应用领域中往往存在着噪音数据，其表现形式可分为如下3 种，即个别特征值错误型噪音、未知特征值型噪音和冗余特征值型噪音。这些噪音产生原因是多方面的，例如在数据获取过程中，由于某些特征提取费用代价等原因，而导致该特征空缺，形成未知特征值型噪音; 另外由于设备和人为的原因，数据在获取、存储和转录的过程中会出现偏差或错误而形成个别特征值错误型噪音。从这些噪音产生的因素来看，实际应用领域中存在噪音数据是不可避免的。噪音数据的存在给现有特征子集选择算法带来了很大难度，有时甚至不得不多选取一些额外的不必要特征用于区分少数几个噪音数据，这样便导致这些算法求得的结果不够理想。为了减小所选择的特征子集，使其更具有代表性，必须在特征选择过程中对这些噪音予以处理。3.2 未知特征值和冗余特征值型噪音的处理方法从聚类的角度来讲，数据集中同一类别数据一般都具有较好的内聚性，也就是说同类数据在特征空间中多聚集在一起，而就个别特征而言，则表现为取值的相同或相近，因此，可以根据这种聚类的思想利用例子间的相似性来实现对未知特征的处理。因此，NFS算法中定义一个相似度函数用以衡量同一类别中例子的相似性。设当前噪音为，且属于第个类别，其中的取值未知，对于，且为已知值，定义与的相似度为：其中 这里，分别为特征的最大取值和最小取值，由相似度定义可知：取值越大，与的相似性越大。NFS算法在对未知特征进行处理时，首先利用相似度函数求得与当前未知特征值型噪音最相近且该特征为已知特征的例子，然后将该未知特征转换成最相近例子相应特征的特征值，从而实现对未知特征值型噪音的处理。对于冗余特征值型噪音中的冗余特征，NFS算法将使用全部非训练例子集中相应特征取值个数最少的特征值取代该冗余特征。3.3 特征评价函数 NFS算法引入Gini系数来构造特征评价函数，利用该评价函数对当前所有没有被选择的特征进行评价，并选取评价值最小的特征加入到当前所选择的特征子集; 然后，根据该特征对当前的所有例子子集(算法运行之初只有一个例子子集,即S ) 进行划分，在删除噪音数据(将在第3.4节讨论) 和一致例子子集后，把不一致例子子集加入到例子子集队列中。如此对新生成的全部例子子集再进行下一次的特征评价和选取，直到例子子集队列空为止。对于连续特征，NFS算法在划分之前采用类别分割离散化方法对其进行离散化处理。NFS算法所定义特征评价函数为: 。其中，K为当前所要评价的特征的取值个数，由下面公式计算:。这里，为第个例子子集中第个类别的例子所占的比例。的大小反映了当前例子子集的一致性情况，其值越小，当前例子子集越趋于一致。而的大小反映了对当前例子集根据特征划分后的各个子集的一致性情况，其值越小，划分后各个子集就越趋向于一致性。3.4 个别特征值错误型噪音的处理方法 NFS算法利用墨西哥帽函数构造噪音终止评价函数，以求消除个别特征值错误型噪音的影响。所定义噪音终止评价函数为：其中， E i，Emax 和E avg分别为当前例子集中属于第i个类别的例子总数、最大类别例子数和平均例子数。 由于噪音(特别是个别特征值错误型噪音) 数据的存在，使得当前例子集中包含有仅由少量噪音数据组成的类别，恰恰是这些噪音数据对最终的特征子集选择造成了较大的影响， 因此应该尽早消除这些噪音。因为噪音数据所组成类别对应的终止函数评价值一般都小于最大类别对应的评价值，而其它的类别所对应的评价值远大于最大类别对应的评价值。所以NFS算法在特征选择过程中可以利用噪音终止评价函数，把当前例子子集中最大类别对应的评价值作为一个标准，去衡量同一子集的其它类别中的例子是否为噪音数据判断并删除当前的例子子集中的噪音数据。3.5 NFS算法的基本思想NFS算法在选择特征子集时，首先利用特征评价函数对当前没有被选取的特征进行评价，选取区分能力最强的特征加入到当前所选择的特征子集，在特征评价前根据聚类的思想进行未知特征值型噪音和冗余特征值型噪音处理。然后，利用当前所选择的特征对例子子集队列中的每一个子集进行划分，删除每一个新划分子集中的个别特征值错误型噪音，并把不一致例子子集加入到例子子集队列中。如此重复，直到例子子集队列为空算法结束，并输出所选择的特征子集。4 基于半贪心策略的特征子集选择算法从3.5节对NFS算法的基本思想的论述中，可以看出NFS算法在选取特征方面所采取的策略是一种绝对贪心策略，而在实际问题中可能会存在这种情况：由区分能力最强的特征所组成的特征集合的区分能力未必会是最强。所以，本文在此将NFS算法在选取特征方面所采取的绝对贪心策略改成半贪心策略。以下是对本文所采用的基于半贪心策略的特征子集选择算法的详细介绍。4.1 算法的主体框架本文算法的处理过程是一个反复迭代的过程，迭代的次数由参数Max-Iterations决定。这些迭代过程之间是相互独立的。并且每一轮迭代过程由两个阶段构成：构造可行解阶段和搜索优化阶段。构造可行解阶段的作用就是产生一个可行解，然后在它的基础上进行搜索优化以产生局部最优解。我们把在给定的循环次数内找到的那个最好的局部最优解当作全局最优解。算法框架如下：Procedure SGFS(Max-Iterations，) Read_Input(); For k=1,.,Max-Iterations do SolutionSemi_Greedy_Construction(); / 产生一个可行解。 Solution search_optimization(Solution); /进行搜索优化以产生局部最优解。 Update_Solution(Solution,Best_Solution); /更新最优解。 End; Return Best_solution; End SGFS.算法的输入：训练例子集合S、算法迭代次数Max-Iterations、（控制算法的贪心程度）。算法的输出：全局最优解Best_solution。4.2 构造可行解阶段本文在这一阶段将NFS算法在选取特征方面所采取的绝对贪心策略改成半贪心策略。其基本处理过程为：首先根据选定的特征评价函数来对当前所有未被选取的特征（F-M）进行评价，用Cmin 来记录最小的评价值、Cmax记录最大的评价值。并将评价值满足条件：= Cmin + (Cmax- Cmin)的所有特征加入到一个数组L中，然后从L中随机选出一个特征加入到当前所选择的特征子集（M）里。在特征评价前根据聚类的思想进行未知特征值型噪音和冗余特征值型噪音处理。然后，利用当前所选择的特征对例子子集队列中的每一个子集进行划分，删除每一个新划分子集中的个别特征值错误型噪音，并把不一致的的例子子集加入到例子子集队列中。如此重复，直到例子子集队列为空算法结束，并输出所选择的特征子集。以下是这一阶段的详细算法： procedure Semi_Greedy_Construction() 初始化; Q1=S，Q2 =,M=; /* 初始化队列Q1里面包含一个元素即训练例子集合S，队列Q2为空，M用来存储可行解。*/ ProcessNoises(); /处理未知特征值和冗余特征值型噪音。 while (Q1!=) Evaluate the effectness() of all F-M; /对当前没有被选择的特征进行评价，其中F为描述训练例子集合S的特征集合。 Cminmin | F-M ; /记录所有被评价的特征的最小评价值。 Cmaxmax | F-M ; /记录所有被评价的特征的最大评价值。 LF-M | 0) Q1.Enqueue(Q2.Dequeue();/将Q2中的元素全部移入Q1中，并将Q2清空。 Return M ; End Semi_Greedy_Construction.数组L是由那些区分能力较强的特征组成的集合，其构造方法是：只要当前某个没有被选取的特征（F-M）的评价值满足条件：Cmin ，Cmin + (Cmax- Cmin)，就可以将该特征加入到数组L中。其中参数0，1决定了这一阶段的贪心或随机化程度。当=0时该阶段算法属于贪心算法， 当=1时该阶段算法属于纯粹的概率算法，所以的取值应根据实际的应用的不同进行调整。4.3 搜索优化阶段由构造可行解阶段产生的可行解M并不一定是最优的，所以有必要通过搜索优化技术对M进行优化。本文采用的搜索优化方法是：在第一阶段产生的可行解M的基础上，依次测试M中的每一个特征（），若删除后由剩下的特征所组成的特征集合仍能够一致性地描述训练例子集合S，则可以从M中将特征删掉。如此往复直到M中的每个特征都被测试过为止，我们把由最后剩下的特征所组成的集合当作局部最优解：Procedure search_optimization(M) For(k=1; k=; k+) If(feature k can be deleted) Delete feature k; / 如果从M里删除特征k后，余下的特征组成的集合仍然能够一致地描述当前例子集合S，则删除特征k； Return solution;End search_optimization;算法的输入; 可行解M。算法的输出; 局部最优解solution。5 算法实现 下面我们给出本文的基于半贪心策略的特征子集选择算法的伪代码，并对该算法的运行过程进行说明。5.1 基于半贪心策略的特征子集选择的算法步骤如下： begin Read_Input(S); /输入训练例子集合S; Preprocess(S); /预处理，删除训练例子集合S中不一致的例子。 For k=1,.，Max-Iterations do 初始化：Q1 =S，Q2 =，M=，solution=，bestsolution=; / 初始化队列Q1里面包含一个元素即训练例子集合S，队列Q2为空，M用来存储可行解，solution用来存储对M进行搜索优化的结果，bestsolution用来存储最优解。 while (Q1!=) Evaluate the effectness() of all F-M; /对当前没有被选择的特征进行评价，其中F为描述训练例子集合S的特征集合。 Cminmin | F-M ; /记录所有被评价的特征的最小评价值。 Cmaxmax| F-M ; /记录所有被评价的特征的最大评价值。 LF-M | 0) Q1.Enqueue(Q2.Dequeue();/将Q2中的元素全部移入Q1中，并将Q2清空。solutionLocal_Search(M); / 对可行解空间进行搜索优化，并将结果放入局部最优解solution里面。Update_Solution(Solution，Best_Solution); /更新全局最优解。End;算法的输入：训练例子集合S。算法的输出：全局最优解Best_Solution。5.2 算法说明该算法的每一轮迭代过程分为两个阶段即构造可行解阶段和搜索优化阶段，在构造可行解阶段中利用特征评价函数对当前没有被选择的特征进行评价，用Cmin 来表示最小的评价值、Cmax表示最大的评价值。并将评价值满足条件：= Cmin + (Cmax- Cmin)的所有特征加入到一个数组L中，此后从数组L中随机选出一个特征加入到可行解集合M中。在特征评价前，根据聚类的思想进行未知特征值型噪音和冗余特征值型噪音处理，并根据当前选中的特征的取值个数，对例子子集合队列Q1中的每个子集合进行划分。删除每一个新划分子集中的个别特征值错误型噪音，并判断所划分出来的子集合中的所有例子是否属于同一个类别，如果不是则将这一子集存入队列Q2中。之后又把Q2中的所有元素回存到Q1中，如此重复直到Q1为空。由这一阶段选出的可行解M并不一定是最优的，所以有必要通过搜索优化技术对其进行优化，经过搜索优化阶段得到的解就是局部最优解solution，我们将每一轮迭代过程所得到的局部最优解进行比较，把其中包含特征个数最少的局部最优解当作全局最优解Best_Solution。6 实验结果根据以上提出的算法的步骤，进行编程实验，用C#语言实现，编译环境为Microsoft Visual Studio .NET 2003，1200MH时钟频率，128MB内存。测试的数据来源为：UCI 数据库。本文运行SGFS算法分别对不同的数据集进行测试，并将结果与文献1中的NFS算法、文献2中的LVF算法和文献7中的GFS算法的相应结果进行比较，结果如表1所示：表1数据集特征数目特征子集数目SGFSNFSLVFGFS Breast_cancer104.04.05.24.0Monks_163.03.03.03.0Monks_266.06.06.06.0Monks_364.04.04.04.0Tic_Tac_Toe96.07.08.08.0Zoo55.05.08.69.0本文还针对不同的数据集，分别让输入参数取不同的值，并且去掉SGFS算法的搜索优化阶段，只对其构造可行解阶段进行实验，其结果如表2所示:表2数据集特征数目特征子集数目=001=1Monks_165.03.03.0Monks_266.06.06.0Monks_364.04.04.0Breast_cancer55.04.04.0从以上表1和表2的结果可以看出，SGFS算法所选出的特征数目较少，且在某些情况下该算法所取得的结果要比NFS算法好。并且在构造可行解阶段中，参数的取值对产生的可行解集合(M)的大小也有影响。7 结束语本文引入了一种基于半贪心策略的特征子集合选择算法，在构造可行解阶段用半随机化方法改进了NFS 1 算法在构造特征子集合时采用的绝对贪心的思想。测试结果表明本文提出的算法选出的特征代表性强、求解速度较快，