大样本高维数据下基于进化多目标优化的特征选择算法研究

发布时间：2020-06-12 22:54

【摘要】：特征选择作为机器学习和数据挖掘任务的重要数据预处理技术之一,其目的在于从原始特征中选择相关特征子集,以获得更好的预测结果,更低的计算成本和更好的模型解释性。然而,在实际应用中,如信息检索、生物特征识别中广泛存在大样本数据和高维数据给现有的特征选择算法带来巨大挑战。现有的特征选择算法将特征数和所选特征子集上的精度加权为一个目标,利用梯度法求解,虽然可以获得好的效果,但是需要有先验知识,并且要求优化函数是凸和光滑的。本文将特征数目和该特征子集上的精度作为两个独立的目标,以多目标的方式求解,并采用具有良好全局搜索能力的进化算法作为优化工具。本文针对性的提出了两种特征选择算法,分别用于解决大样本数据和高维数据下的特征选择问题。本文的主要工作包括以下两个部分:(1)大样本数据下的特征选择问题。由于样本数目大,导致计算代价昂贵。本文以训练数据量为O(n2)的Pairwise排序问题为例提出基于进化多目标优化的特征选择算法MOFSRank,该算法包括三个策略:1、多目标实例选择策略:该策略从训练实例中选择具有代表性的实例,通过消除训练实例中可能存在的冗余数据,给后续的特征选择选取数目少、代表性强的实例;2、多目标特征选择策略:在上述工作的基础之上,同时为了进一步提升算法在特征选择中的性能,本文采用了一个自适应的变异概率,以得到排序精度高、冗余度低的特征子集;3、Pareto集成策略:该策略采用了一个混合集成思想,利用集成的思想,将策略2的所得Pareto最优集中的非支配个体加以集成,以产生更好的特征组合。实验结果表明,MOFSRank算法可以在选取较少特征的情况下达到很好的排序结果。(2)高维数据下的特征选择问题。由于存在巨大的搜索空间,需要大量的评价次数从而使优化过程付出巨大的计算代价。本文针对此问题提出基于进化多目标优化的指导模型算法GMA。该算法包括两个策略:1、自适应缩减策略:该策略可以快速剔除不相关和冗余特征,降低搜索空间。同时,实验结果表明当数据维度越高,其优势更为明显;2、指导模型预筛选策略:该策略利用已有的函数适应度值训练指导模型,并让指导模型帮助筛选种群个体,因此能减少真实评价次数,加速算法搜索。在多个高维数据集上的实验结果表明,GMA算法可以在高维数据集中,以较低的计算代价获得更好的特征子集。
【图文】：

混合编码,非支配解

其中／表示ＭＯＦＳ的非支配解中不同特征的数量，第ｉ位对应于第ｉ个特逡逑征，如果该位为Ｉ，则表示此特征被选中，０表示不选。第：部分使用实数编码，逡逑其长度等于｜ｒｓｅｔｘ／｜，其中丨ｒｓｅｔ｜是第：阶段的Ｐａｒｅｔｏ解的数量。图３．３提供了逡逑混合编码方案的示例。逡逑ｂｉｎａｒｙ邋ｅｎｃｏｄｉｎｇ逦ｒｅａｌ邋ｅｎｃｏｄｉｎｃ逡逑ｓｕｂ－ｐａｒｔｌ逦ｓｕｂ－ｐａｒｔ２逦ｓｕｂ－ｐａｒｉ３逡逑ｉｎｄ逡逑ｐａｒｔｉ逦ｐａｒｔ２逡逑图３．３举例解释混合编码逡逑Ｆｉｇ．邋３．３邋Ａｎ邋Ｅｘａｍｐｌｅ邋ｔｏ邋Ｉｌｌｕｓｔｒａｔｅ邋ｔｈｅ邋Ｓｕｇｇｅｓｔｅｄ邋Ｍｉｘｅｄ邋Ｅｎｃｏｄｉｎｇ邋Ｓｃｈｅｍｅ．逡逑在图３．３中，＃一个单独的Ｚ？ｉｄ。ｉｎｄ的第一部分有４位，这意味着ＭＯＦＳ逡逑的非支配解中有４个不同的特征。第二部分由３个子部分组成，表示特征子集的逡逑数量为３。假设它们是Ｆ＆，／＝＾２和／＾３，因此第／个子部分表示ＲＳ，？的集成权重逡逑丨１，２，３丨）。在优化期间，对于个体ｉｍｆ，需要计算其两个目标。从ｉｎｄ的逡逑ｐａｒｑ很容易获得第一个目标的值（所选特征的数景）。为了得到第二个目标的逡逑值（所选特征的１邋－邋／Ａｃｃｕｒａｃｙ的值），首先，应该得到与Ｚｎｄ对应的分类器ｅｎｒ。逡逑为此，本节利用第二阶段的非支配解和ｅｎｒ第２部分中的权重。具体而言，针对逡逑某一个分类器ｅｎｒ，每个６逦＝邋１，．．．，／）通过以下公式获得

特征数,数据集,精度,最佳平衡

表３．３和３．４已经验证了邋ＭＯＦＳＲａｎｋ的优势。逡逑这里进一步研究了邋ＬＥＲＯＲ数据集中不同特征选择算法的性能，本文详细比逡逑较了不同数量的特征（ｘ轴）情况下Ｎ＠１０邋（ｙ轴）的值，，结果如图３．４所示。需逡逑要注意的是，三个比较算法不能选择指定的特征个数，本文采取了邋ＦＳＭＲａｎｋｌ—逡逑中的方法，它可以从整个特征中选择前Ａ：邋（Ａ：邋２邋１）个最佳特征。图中可以看出，逡逑尽管不同算法的ＮＤＣＧ精度随所选特征的数量而变化，但本文的ＭＯＦＳＲａｎｋ始逡逑终可以在精度和所选特征数量之间取得最佳平衡，这表明了其优势。逡逑“７，逦ｄｐ７逡逑！Ｊ逦＾ＦｃｎｃｈｄＲａｎｋ逦｜邋ｊｊ逦ＦｅｎｃｈｅｌＲａｎｋ邋Ｉ邋ｉ逡逑｜逦－＾－ＦＳＭＩＵｎｆｃ逦ｎｆｉ．ｔ逦？逦－ｅ－ＦＳＭＲａｎｋ逡逑０６邋ｆ逦＋丨－逦0６５ｆ逡逑Ｊ逦１￣？－ＭＯＦＳＲａｎｋ逦／逦＾ＭＯＦＳＲａｎｋ邋｜逡逑０．５５邋＾逦逦逦逦逦邋０邋６邋逦＇逦逦逦１逦逦逦逦逦逡逑０邋Ｓ邋１０逦１５逦２０逦２５逦３０逦３５邋４0邋４５逦０逦２逦４逦６逦８逦１０
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18;TP311.13

【相似文献】