。
按照这样的要求，可以定义出多种可分性判据，这里我们只介绍其中一种散度。
现在考虑i和j两类之间的可分性，取其对数似然比：
lij
X

l

pX
pX
i
j
则i类对j类的平均可分性信息可以定义为：
fIij
X

E
lij
X

X
pX
il

pX
pX
i
j
dX
同样j类对i类的平均可分性信息：
IjiXEljiX
p
X
Xj
l
pXjpXi
dX
散度JP定义为区分i类和j类的总平均信息：
JPIijIji
Xp
Xi
p
Xj
l

pp
XiXj
dX
从JP的定义可以看出，当两类分不完全性同pXipXj时，JP0；当两
类完全可分时，JP。
基于概率的可分性判据优点是直接与识别的错误率相联系，缺点是需要已知各个类别类概率密度函数，只有当我们预先已知各类别的概率分布时，才可以利用训练样本集合估计出概率密度函数，但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的。
53特征选择
所谓特征选择，就是从一组数量为N的特征中选择出一组数量为M的最优特征，（NM）这里有两个问题要解决，1、选择一种可分性判据作为最优特征选择的标准；2、
找到一个好的算法，来选择出这组最优特征。下面我们就来介绍几种特征选择的算法。
一个最简单的思路是：我们假设N个特征之间相互独立，并且使用的可分性判据满足
N
可加性：JXJxi，这时候我们只要把N个特征每个单独使用时的可分性判据i1
Jxi计算出来，然后从大到小排序：Jx1Jx2LJxN，选择出前M个特征
就是一组最优的特征。然而问题往往没有这么简单，这种特征独立性假设多数情况下并不成立，并且可分性判据也不一定满足可加性。
另外一个简单的思路是穷举法：对从N中选择出M个特征的所有组合情况都计算其可分性判据，然后选择出其中的最大者作为解决方案。当N的数值比较小时，这种方法一定是可行的，然而当N比较大时，这个组合数会非常大，比如N100，M10时，组合
数的数量级是103，当N20，M10时，组合数为184756。将所有的组合都计算一遍
显然是不现实的。因此我们需要有一个搜索算法来进行特征选择。
一、最优搜索算法分支定界算法
到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据
f中的单调性质：Jijx1x2LxNJijx1x2LxNxN1，我们前面定义的各种判据都满
足这个性质。1分支定界的思想
分支定界算法实际上是对一个特征选择的搜索树进行搜索，下面先以N6，M2的
情况来说明一下搜索树。X0
1
2A
3
2
3
4
B3
44
3
4
5
4
55
4
555
C456566566656666
在搜r