分枝定界搜索算法

分枝定界搜索算法通过穷举法搜索进行的特征选择会导致计算量过高，而在分枝定界搜索算法帮助下，有可能不需要显示评估所有d个特征的可能组合而确定最优特征集。此算法的应用需假定特征选择准则满足单调性。用jx表示含有j个特征的候选特征集，单调性指的是对于具有下列嵌套关系的特征集jx12jDxxxx其准则函数jJx应满足12DJxJxJx这点由构造特征评判准则的定义可得到保证。为引出分枝定界搜索算法的基本观点，考虑从5个特征中挑选2个特征值的问题。特征中所有可能组合如下图的树表示，顶称为根节点，底称为叶节点，中间称为枝节点，共有1Dd层。图分枝定界搜索算法示意图现假设自底向上，再由上向下的搜索方式从最右节点开始在树的每个节点评估特征，进行特征选择。设初始叶节点的J为0J（为45xx的准则函数），在每个节点处，将节点的准则函数值和目前最优特征集的J值进行比较，如果节点准则函数值大于0J，则还有发现更佳特征集的机会，而且必须继续沿着最右边的未勘探分枝搜索。如果到达了树底的叶节点且相应准则值大于0J，则此结点定义了当前新的最佳特征集，而0J则作为相应更新。另一方面，如果在某节点的准则函数值小于0J，则以此节点为起始点的分支就不需勘探。因为根据单调性，再往下的特征组合将导致准则函数值的进一步减小。如此按这一规律，由底向上，再自上而下，从右向左搜索全树，可获得最佳的二特征组合。此搜索算法特别快捷有效。12345xxxxx1234xxxx1235xxxx123xxx124xxx12xx13xx23xx45xx45xx45xx34xx34xx24xx14xx125xxx25xx15xx35xx35xx