特征选择中B&B算法的改进及比较

B&B(Branch & Bound)算法是特征选择中的一种全局最优算法,其固有缺点是运行时间太长.用B&B算法构造一棵搜索树,在树中搜索最优的特征子集.对B&B算法的研究集中在化简搜索树从而降低搜索复杂度上,提出了几种改进的B&B算法.从原理上分析了B&B算法及其各种改进的优缺点,将这一系列算法纳入到同一个算法框架,并在此基础上提出了一种针对BBPP算法的改进算法,BBPP+算法.通过比较各种实验数据,发现改进后的BBPP+算法的运行效率比已有的B&B算法更好.

Improvement and comparative analysis of B&B algorithm in feature selection

B&B is an optimal algorithm of feature subset selection. The high computational complexity of this algorithm is its inherent problem. B&B algorithm constructs a search tree, and then searches for the optimal feature subset in the tree. The previous research on B&B algorithm focused on simplifying the search tree in order to reduce the search complexity, and several improvements have already existed. A theoretical analysis of basic B&B algorithm and the previous improvements are given under a common framework in which all the algorithms are compared. Based on this analysis, an improved B&B algorithm--BBPP+--is proposed. Experimental comparison shows that BBPP+ is more efficient than all previous algorithms.