模式识别第4章—特征选择和提取

特征选择和提取是模式识别中的一个关键问题：
前面讨论分类器设计的时候，一直假定已给出了特征向量维数确定的样本集，其中各样本的每一维都是该样本的一个特征；
这些特征的选择是很重要的，它强烈地影响到分类器的设计及其性能；
假若对不同的类别，这些特征的差别很大，则比较容易设计出具有较好性能的分类器。
例如：
判断一个人是否是软件工程师？
肤色，体重，身高，工资，工资，编程，受教育程度，性别

特征选择和提取是构造模式识别系统时的一个重要课题
在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制，不能对它们进行有效的测量；
因此在测量时，由于人们心理上的作用，只要条件许可总希望把特征取得多一些；
另外，由于客观上的需要，为了突出某些有用信息，抑制无用信息，有意加上一些比值、指数或对数等组合计算特征；
如果将数目很多的测量值不做分析，全部直接用作分类特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难”问题。
我们应该对特征进行选择。
应去掉模棱两可、不易判别的特征；
所提供的特征不要重复，即去掉那些相关性强且没有增加更多分类信息的特征。

特征选择和提取

所谓特征选择，就是从n个度量值集合{x1, x2,…, xn}中，按某一准则选取出供分类用的子集，作为降维（m维，m<n）的分类特征；
所谓特征提取，就是使(x1, x2,…, xn)通过某种变换，产生m个特征(y1, y2,…, ym) (m<n) ，作为新的分类特征（或称为二次特征）；
其目的都是为了在尽可能保留识别信息的前提下，降低特征空间的维数，已达到有效的分类。

以细胞自动识别为例
通过图像输入得到一批包括正常细胞和异常细胞的图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些细胞是异常的；
首先找出一组能代表细胞性质的特征，为此可计算
细胞总面积
总光密度
胞核面积
核浆比
细胞形状
核内纹理
……
这样产生出来的原始特征可能很多（几十甚至几百个），或者说原始特征空间维数很高，需要降低（或称压缩）维数以便分类；
一种方式是从原始特征中挑选出一些最有代表性的特征，称之为特征选择；
另一种方式是用映射（或称变换）的方法把原始特征变换为较少的特征，称之为特征提取

模式类别可分性的测度-距离和散布矩阵

点到点之间的距离
在n维空间中，a与b两点之间的欧氏距离为：
D(a, b) = || a – b ||
写成距离平方：

其中，a和b为n维向量，其第k个分量分别是ak和bk。

点到点集之间的距离
在n维空间中，点x到点a(i)之间的距离平方为：

因此，点x到点集{a(i)}i=1,2,…,K之间的均方距离为：


类内距离
n维空间中同一类内各模式样本点集{a(i)}i=1,2,…,K，其内部各点的均方距离为
其中

即：

可证明：

其中为{a(i)}在第k个分量上的无偏方差，即：

其中为{a(i)}在第k个分量方向上的均值。

类内散布矩阵
考虑一类内模式点集，其类内散布矩阵为：
其中

类间距离和类间散布矩阵
在考虑有两个以上的类别，如集合{a(i)}和{b(j)}时，类间距离对类别的可分性起着重要作用，此时应计算：。
为简化起见，常用两类样本各自质心间的距离作为类间距离，并假设两类样本出现的概率相等，则：

其中m1和m2为两类模式样本集各自的均值向量， 和为m1和m2的第k个分量，n为维数。
写成矩阵形式：为两类模式的类间散布矩阵。
对三个以上的类别，类间散布矩阵常写成：

其中，m0为多类模式（如共有c类）分布的总体均值向量，即：

多类模式集散布矩阵
多类情况的类内散布矩阵，可写成各类的类内散布矩阵的先验概率的加权和，即：

其中Ci是第i类的协方差矩阵。
有时，用多类模式总体分布的散布矩阵来反映其可分性，即：

其中，m0为多类模式分布的总体均值向量。
可以证明：St = Sw + Sb，即总体散布矩阵是各类类内散布矩阵与类间散布矩阵之和。

特征选择

设有n个可用作分类的测量值，为了在不降低（或尽量不降低）分类精度的前提下，减小特征空间的维数以减少计算量，需从中直接选出m个作为分类的特征。
问题：在n个测量值中选出哪一些作为分类特征，使其具有最小的分类错误？
例题：
设有如下三类模式样本集ω1，ω2和ω3，其先验概率相等，求Sw和Sb
ω1：{(1 0)T, (2 0) T, (1 1) T}

               ω2：{(-1 0)T, (0 1) T, (-1 1) T}

               ω3：{(-1 -1)T, (0 -1) T, (0 -2) T}

离散K-L变换

全称：Karhunen-Loeve变换（卡洛南-洛伊变换）
前面讨论的特征选择是在一定准则下，从n个特征中选出k个来反映原有模式。
这种简单删掉某n-k个特征的做法并不十分理想，因为一般来说，原来的n个数据各自在不同程度上反映了识别对象的某些特征，简单地删去某些特征可能会丢失较多的有用信息。
如果将原来的特征做正交变换，获得的每个数据都是原来n个数据的线性组合，然后从新的数据中选出少数几个，使其尽可能多地反映各类模式之间的差异，而这些特征间又尽可能相互独立，则比单纯的选择方法更灵活、更有效。
K-L变换就是一种适用于任意概率密度函数的正交变换。
离散的有限K-L展开


K-L展开式的根本性质是将随机向量x展开为另一组正交向量j的线性和，且其展开式系数aj（即系数向量a的各个分量）具有不同的性质。

K-L展开式系数的计算步骤
K-L展开式系数可如下求得：
1.求随机向量x的自相关矩阵：R = E{xxT}
2.求出矩阵R的特征值λj和对应的特征向量φj，j = 1,2,…,n，得矩阵：

3.计算展开式系数：
a = ΦTx
总结：
从K-L展开式的性质和按最小均方差的准则来选择特征，应使E[aj]=0。由于E[a]=E[Tx]= TE[x]，故应使E[x]=0。基于这一条件，在将整体模式进行K-L变换之前，应先将其均值作为新坐标轴的原点，采用协方差矩阵C或自相关矩阵R来计算特征值。如果E[x] ≠0，则只能得到“次最佳”的结果。

K-L变换实例

给定两类模式，其分布如图所示，试用K-L变换实现一维的特征提取（假定两类模式出现的概率相等）。

P(ω1)= P(ω2)=0.5，

符合K-L变换进行特征压缩的最佳条件。
因P(ω1)= P(ω2)=0.5，故

解特征值方程|R-λI|=0，求R的特征值。
由(25.4-λ)2 - 25.02 = 0，得特征值λ1=50.4，λ2=0.4
其对应的特征向量可由RФi=λiФi求得：

选λ1对应的变换向量作为变换矩阵，由y=ФTx得变换后的一维模式特征为：