[发明专利]基于部落进化竞争的特征选择方法

摘要

本发明公开了一种基于部落进化竞争的特征选择方法，用于解决现有特征选择方法中高维特征分类时特征选择数目在排列组合中偏置的技术问题。技术方案是根据特征的维度将特征划分成多个部落，部落内部所选择的特征个数在统计上服从高斯分布；采取改进的遗传算法，在保证最优个体得以保留的前提下，确保部落内部的特征选择数目的分布情况不发生变化；当各个部落进化到一定程度后开始竞争，每个部落提供部落内适应度最高的精英个体，所有部落的精英个体根据适应度进行排序。由于将特征空间划分为多个高斯部落，部落内部所选择的特征个数在统计上服从高斯分布，并且高斯分布始终保持不变，能够有效的改善偏置问题，最终能够搜索到全局最优子集。

主权项

一种基于部落进化竞争的特征选择方法，其特征在于包括以下步骤：步骤一、将整个种群划分成K个部落，每个部落初始化时含有P个个体，表示第i个部落中所选特征维度为j的个数，表示选择j个特征的所有可能的个体的集合；其中在第i个部落中服从高斯分布，使第i个部落中的个体初始时选择的特征个数以95.45％的概率落在区间；初始化完成后，形成所选特征个数呈高斯分布的K个部落；步骤二、部落内部进化；每个部落内部的进化是基于一个改进的遗传算法进行的，分为以下四个步骤迭代的执行；1)适应度计算；对于部落中的每个个体，首先将其解码为所表示的所选特征集合，然后采用支持向量机对该所选特征集进行分类，并使用10折交叉验证，得到分类正确率，作为该个体的适应度；依此方法，计算每个个体的适应度，并将适应度最高的精英个体直接保存入下一代；2)选择；轮盘赌选择是从部落中选择一批成员，被选中的概率和它们的适应度分数成比例，个体的适应度愈高，被选中的概率也越高；选择过程中，个体适应度高的个体有很大的几率会被重复选择，而适应度低的个体则有可能从未被选择；3)交叉；在交叉过程中，个体用集合表示，集合中的元素是个体二进制编码中1的下标位置；当个体的二进制编码为1010010，表示选择第1，3，6个特征；则它的集合形式表示为X＝{1，3，6}；发生交叉的个体，一个是来自经过轮盘赌选择后生成的种群，另一个来自原始的高斯部落；交叉过程中，通过集合形式表示的个体交换相同数量的元素，保证在交叉前后个体所选特征的个数不发生变化；这样交叉后形成的两个种群仍和其父母种群在所选特征的数目的分布上一致，原始高斯部落的分布特性能够在交叉之后得到保留；4)变异；变异会随机修改个体二进制编码的某一位置的编码；在变异过程中，如果一个体中的某一位的原始编码从0变异成1，得到的新个体,则从部落中选择任一个体，随机选择一位从1变异成0，使得得到的新个体作为补偿；步骤三、部落之间的竞争；部落经过选择、交叉和变异的进化后，个体的最高适应度会单调递增，进入部落竞争阶段；在竞争阶段，各部落提供部落内部适应度最高的精英个体，再根据适应度的大小对这些精英个体进行排序；适应度越高的精英个体所在的部落就获得扩大部落规模的权利，而那些适应度较差的精英个体所在的部落则相应的削减部落规模；扩大或削减规模的具体数量和排序的结果呈线性关系；完成一次部落竞争后，各部落的规模会发生变化，其中最优个体所在部落的规模很可能会变得很大，但部落内部个体所选特征数目的高斯分布不会发生变化；各部落再次进入内部的进化过程，进行部落之间的竞争；如此往复，直到无法找到更优个体或达到指定的循环次数。