中的单调性质:Jn(x,x2…,x)≤J(x1,x,…x,x+),我们前面定义的各种判据都满 足这个性质 1.分支定界的思想 分支定界算法实际上是对一个特征选择的搜索树进行搜索,下面先以N=6,M=2的 情况来说明一下搜索树 3 4o5o5 456566566656666 在搜索树中根节点x0代表全部特征的集合{x,x2,…,x},每向下一级节点代表从集 合中删除一个特征,节点边上的数字表示在这一级中删除的特征,比如A节点表示删除x,特 征,代表{x,x…,x},因为最后要保留2个特征,因此树的级数为N-M=4。每一个 叶节点代表一种组合,比如C节点代表{x1,x}。 由于可分性判据具有单调性,因此在搜索树中的节点具有这样的性质:每个节点代表的 特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据,比如 J(4)≥J(B)≥J(C) 根据这样的性质,我们就可以有如下的搜索算法 2.分支定界算法(不严格) 1)搜索从右向左进行,首先设置一个界值B,初始化为B=0: 2)如果当前节点没有分支,则向下搜索,直到叶节点为止,计算叶节点代表的特征集合的 可分性判据,如果大于界值B,则将B替换为这个判据值,并记录这个特征集合,作 为当前的最优选择;向上回溯,直到有节点有未搜索过的分支为止,按照从右向左的顺 序搜索其子节点; 3)如果当前节点有分支,则计算当前节点代表的特征集合的可分性判据,如果小于界值 B,则中止该节点向下的搜索,因为其子节点的可分性判据已经不可能大于B了。否 则按照从右向左的顺序搜索其子节点。 分支定界算法的计算时间是不确定的,同最优解分支所在位置有关,如果最优解分支在 最右端,并且去掉x1或x2的可分性判据均小于最优解,则搜索时间最短,只需计算3组可49 中的单调性质： J x x x J x x x x ij N ij N N ( 1 2 1 2 1 , , , , , , , )  ( + ) ，我们前面定义的各种判据都满 足这个性质。 1. 分支定界的思想 分支定界算法实际上是对一个特征选择的搜索树进行搜索，下面先以 N = 6，M = 2 的 情况来说明一下搜索树。 4 5 6 5 6 6 5 6 6 6 5 6 6 6 6 3 4 5 4 5 5 4 5 5 5 2 2 3 3 3 4 4 4 A B C X0 1 在搜索树中根节点 X0 代表全部特征的集合 x x x 1 2 6 , , ,  ，每向下一级节点代表从集 合中删除一个特征，节点边上的数字表示在这一级中删除的特征，比如 A 节点表示删除 2 x 特 征，代表 x x x 1 3 6 , , ,  ，因为最后要保留 2 个特征，因此树的级数为 N M− = 4 。每一个 叶节点代表一种组合，比如 C 节点代表 x x 1 4 ,  。 由于可分性判据具有单调性，因此在搜索树中的节点具有这样的性质：每个节点代表的 特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据，比如： J A J B J C ( )   ( ) ( ) 根据这样的性质，我们就可以有如下的搜索算法。 2. 分支定界算法（不严格） 1) 搜索从右向左进行，首先设置一个界值 B ，初始化为 B = 0 ； 2) 如果当前节点没有分支，则向下搜索，直到叶节点为止，计算叶节点代表的特征集合的 可分性判据，如果大于界值 B ，则将 B 替换为这个判据值，并记录这个特征集合，作 为当前的最优选择；向上回溯，直到有节点有未搜索过的分支为止，按照从右向左的顺 序搜索其子节点； 3) 如果当前节点有分支，则计算当前节点代表的特征集合的可分性判据，如果小于界值 B ，则中止该节点向下的搜索，因为其子节点的可分性判据已经不可能大于 B 了。否 则按照从右向左的顺序搜索其子节点。 分支定界算法的计算时间是不确定的，同最优解分支所在位置有关，如果最优解分支在 最右端，并且去掉 1 x 或 2 x 的可分性判据均小于最优解，则搜索时间最短，只需计算 3 组可