论文部分内容阅读
在许多现实的机器学习任务中,经常遇到从一组变量中挑选一个子集的问题,即子集选择问题.对于这类问题的求解是NP难的.最近,一种基于多目标演化算法的子集选择算法POSS被提出;无论是在理论上还是在实验上,POSS方法均获得了目前的最佳性能.然而,当问题规模很大的时候,POSS方法的运行时间变得难以令人满意,这阻碍了其在大规模实际问题中的应用.提出了一种基于分解策略的多目标演化子集选择算法DPOSS.DPOSS方法将整个子集空间分解成多个子空间,并依次调用POSS方法来求解.在理论上,DPOSS方法在获得和POSS方法相同近似性能下界的同时,运行时间随着分解个数的增加超线性下降.实验结果验证了这一理论,并显示出,DPOSS方法的实际性能随着分解个数的增加略有下降,但依然优于以往的贪婪算法.
In many realistic machine learning tasks, the problem of selecting a subset from a set of variables, that is, subset selection, is often encountered. The solution to these problems is NP-hard. Recently, a multi-objective evolutionary algorithm , The POSS method has achieved the best performance at present both in theory and in experiment.However, when the problem scale is large, the running time of POSS method becomes difficult Which hinders its application in large-scale practical problems.A decomposition strategy based multi-objective evolution subsets selection algorithm DPOSS DPDP is proposed to decompose the entire subset into multiple subspaces and then to call the POSS method in turn In theory, the DPOSS method obtains the same lower bound of the approximate performance as the POSS method, while the running time decreases linearly with the increase of the number of decompositions.The experimental results verify this theory and show that the DPOSS method’s real The performance decreases slightly with the increase of the number of decomposition, but still better than the greedy algorithm in the past.