模式识别7-特征选择和提取

特征选择和提取特征选择和提取特征选择和提取是模式识别中的一个关键问题前面讨论分类器设计的时候，一直假定已给出了特征向量维数确定的样本集，其中各样本的每一维都是该样本的一个特征；这些特征的选择是很重要的，它强烈地影响到分类器的设计及其性能；假若对不同的类别，这些特征的差别很大，则比较容易设计出具有较好性能的分类器。特征选择和提取特征选择和提取是构造模式识别系统时的一个重要课题在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制，不能对它们进行有效的测量；因此在测量时，由于人们心理上的作用，只要条件许可总希望把特征取得多一些；另外，由于客观上的需要，为了突出某些有用信息，抑制无用信息，有意加上一些比值、指数或对数等组合计算特征；如果将数目很多的测量值不做分析，全部直接用作分类特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难”问题。特征选择和提取为了设计出效果好的分类器，通常需要对原始的测量值集合进行分析，经过选择或变换处理，组成有效的识别特征；在保证一定分类精度的前提下，减少特征维数，即进行“降维”处理，使分类器实现快速、准确和高效的分类。为达到上述目的，关键是所提供的识别特征应具有很好的可分性，使分类器容易判别。为此，需对特征进行选择。应去掉模棱两可、不易判别的特征；所提供的特征不要重复，即去掉那些相关性强且没有增加更多分类信息的特征。特征选择和提取说明实际上，特征选择和提取这一任务应在设计分类器之前进行；从通常的模式识别教学经验看，在讨论分类器设计之后讲述特征选择和提取，更有利于加深对该问题的理解。特征选择和提取所谓特征选择，就是从n个度量值集合{x1,x2,…,xn}中，按某一准则选取出供分类用的子集，作为降维（m维，mn）的分类特征；所谓特征提取，就是使(x1,x2,…,xn)通过某种变换，产生m个特征(y1,y2,…,ym)(mn)，作为新的分类特征（或称为二次特征）；其目的都是为了在尽可能保留识别信息的前提下，降低特征空间的维数，已达到有效的分类。特征选择和提取以细胞自动识别为例通过图像输入得到一批包括正常细胞和异常细胞的图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些细胞是异常的；首先找出一组能代表细胞性质的特征，为此可计算细胞总面积总光密度胞核面积核浆比细胞形状核内纹理……特征选择和提取以细胞自动识别为例这样产生出来的原始特征可能很多（几十甚至几百个），或者说原始特征空间维数很高，需要降低（或称压缩）维数以便分类；一种方式是从原始特征中挑选出一些最有代表性的特征，称之为特征选择；另一种方式是用映射（或称变换）的方法把原始特征变换为较少的特征，称之为特征提取。7.1模式类别可分性的测度距离和散布矩阵[点到点之间的距离][点到点集之间的距离][类内距离]7.1模式类别可分性的测度距离和散布矩阵[类内散布矩阵]对属于同一类的模式样本，类内散布矩阵表示各样本点围绕其均值周围的散布情况，这里即为该分布的协方差矩阵。[类间距离和类间散布矩阵][多类模式集散布矩阵]以上各类散布矩阵反映了各类模式在模式空间的分布情况，但它们与分类的错误率没有直接联系。（若与分类错误率联系起来，可采用散度作为类别可分性的度量，在此不详细介绍）类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则理想准则：某组特征使分类器错误概率最小实际的类别可分离性判据应满足的条件：度量特性：与错误率有单调关系当特征独立时有可加性：单调性：常见类别可分离性判据：基于距离、概率分布、熵函数0,if;0,if;ijijijjiJijJijJJ121(,,...,)()dijdijkkJxxxJx12121(,,...,)(,,...,,)ijdijddJxxxJxxxx类间可分性:=所有样本间的平均距离：()()111111()(,)2jinnccijdijklijklijJPPnnxxx(8-1)()()()()()()(,)()()ijijTijklklklxxxxxxsquaredEuclidian()11iniikkinmx1ciiiPmm()111()(,)(,)incidikiiikiJPnxxmmm(8-5)类内平均距离类间距离1111(,)(,)2ccciiijijiijPPPmmmm(8-6)1()()cTbiiiiSPmmmm()()111()()inciiTwikikiikiSPnxmxm()tr()dwbJSSx基于距离的准则概念直观，计算方便，但与错误率没有直接联系样本类间离散度矩阵样本类内离散度矩阵类间可分离性判据7.2特征选择设有n个可用作分类的测量值，为了在不降低（或尽量不降低）分类精度的前提下，减小特征空间的维数以减少计算量，需从中直接选出m个作为分类的特征。问题：在n个测量值中选出哪一些作为分类特征，使其具有最小的分类错误？特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。从D个特征中选取d个,共CdD种组合。若不限定特征选择个数，则共2D种组合－典型的组合优化问题特征选择的方法大体可分两大类：Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。Wrapper方法：将特征选择和分类器结合在一起，在学习过程中表现优异的的特征子集会被选中。dDC经典特征选择算法许多特征选择算法力求解决搜索问题，经典算法有：􀂄分支定界法:最优搜索，效率比盲目穷举法高。单独最优特征组合法：次优搜索。顺序后退法顺序前进法模拟退火法Tabu搜索法遗传算法特征选择单独最优特征组合计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果不一定是最优结果当可分性判据对各特征具有(广义)可加性，该方法可以选出一组最优的特征来，例：各类具有正态分布各特征统计独立可分性判据基于Mahalanobis距离1()()()TDijijJxμμμμ121(,,...,)()dijdijkkJxxxJx特征选择顺序前进法自下而上搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直至特征数增加到d为止。该方法考虑了所选特征与已入选特征之间的相关性。特征选择顺序后退法该方法根据特征子集的分类表现来选择特征搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率依次迭代，直至识别率开始下降为止特征选择遗传算法从生物进化论得到启迪。遗传，变异，自然选择。基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。群体：若干个个体的集合，即问题的一些解的集合。交叉：由当前两个个体的链码交叉产生新一代的个体。变异：由一个链码随机某基因使其翻转。特征选择遗传算法适应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均适应度比父代高。遗传算法的基本框架：Step1:令进化代数t=0。Step2:给出初始化群体P(t)，令xg为任一个体。Step3:对P(t)中每个个体估值，并将群体中最优解x’与xg比较，如果x’的性能优于xg，则xg=x’Step4:如果终止条件满足，则算法结束，xg为算法的结果。否则继续。Step5:从P(t)中选择个体并进行交叉和变异操作，得到新一代群体P(t+1)。令t=t+1,转到Step3。特征选择6.5讨论特征的选择与提取是模式识别中重要而困难的一步模式识别的第一步：分析各种特征的有效性并选出最有代表性的特征降低特征维数在很多情况下是有效设计分类器的重要课题三大类特征：物理、结构和数学特征物理和结构特征：易于为人的直觉感知，但难于定量描述，因而不易用机器判别数学特征：易于用机器定量描述和判别7.2特征选择从n个测量值中选出m个特征，一共有中可能的选法。一种“穷举”办法：对每种选法都用训练样本试分类一下，测出其正确分类率，然后做出性能最好的选择，此时需要试探的特征子集的种类达到种，非常耗时。需寻找一种简便的可分性准则，间接判断每一种子集的优劣。对于独立特征的选择准则一般特征的散布矩阵准则7.2特征选择对于独立特征的选择准则类别可分性准则应具有这样的特点，即不同类别模式特征的均值向量之间的距离应最大，而属于同一类的模式特征，其方差之和应最小。假设各原始特征测量值是统计独立的，此时，只需对训练样本的n个测量值独立地进行分析，从中选出m个最好的作为分类特征即可。[例：对于i和j两类训练样本的特征选择]7.2特征选择讨论：上述基于距离测度的可分性准则，其适用范围与模式特征的概率分布有关。三种不同模式分布的情况(a)中特征xk的分布有很好的可分性，通过它足以分离i和j两种类别；(b)中的特征分布有很大的重叠，单靠xk达不到较好的分类，需要增加其它特征；(c)中的i类特征xk的分布有两个最大值，虽然它与j的分布没有重叠，但计算Gk约等于0，此时再利用Gk作为可分性准则已不合适。因此，假若类概率密度函数不是或不近似正态分布，均值和方差就不足以用来估计类别的可分性，此时该准则函数不完全适用。7.2特征选择一般特征的散布矩阵准则[类内、类间和总体的散布矩阵Sw、Sb和St]Sw的行列式值越小且Sb的行列式值越大，可分性越好。[散布矩阵准则J1和J2形式]使J1或J2最大的子集可作为所选择的分类特征。注：这里计算的散布矩阵不受模式分布形式的限制，但需要有足够数量的模式样本才能获得有效的结果。作业设有如下三类模式样本集ω1，ω2和ω3，其先验概率相等，求Sw和Sbω1：{(10)T,(20)T,(11)T}ω2：{(-10)T,(01)T,(-11)T}ω3：{(-1-1)T,(0-1)T,(0-2)T}7.3基于类内散布矩阵的单类模式特征提取对某类模式：压缩模式向量的维数。对多类分类：压缩维数；保留类别间的鉴别信息，突出可分性。特征提取的目的：若}{X是iω类的一个n维样本集，将X压缩成m维向量*X——寻找一个nm矩阵A，并作变换：特征提取操作方法：AXX*m×1m×nn×1(mn)注意：维数降低后，在新的m维空间里各模式类之间的分布规律应至少保持不变或更优化。讨论内容：*根据类内散布矩阵如何确定变换矩阵A；*通过A如何进行特征提取。1．根据类内散布矩阵确定变换矩阵设iω类模式的均值向量为M，类内散布矩阵(协方差矩阵)为C：XMET))((MXMXCE式中，X为n维向量，C为n×n的实对称矩阵。设矩阵C的n个特征值分别为nλλλ,,,21。任一特征值是满足0CI的一个解。假定n个特征值对应的n个特征向量为nk,,2,1,ku。则ku是满足kkuCuk的一个非零解。ku是n维向量，可表示为T21],,,[knkkuuuku。若ku为归一化特征向量，根据实对称矩阵的性质，有ijij,0,1Tjiuu——n个特征向量相互正交。若选n个归一化特征向量作为A的行，则A为归一化正交矩阵：TTTnuuuA21nuuuA21TIAAT利用A对iω类的样本X进行变换，得AXX*。式中，X和*X都是n维向量。考察变换前后的分布规律：均值向量*M、协方差矩阵*C和类内距离2D的变化。}))({(T*****MXMXCE}))({(TAMAXAMAXETT}))({(AMXMXAETACAAMXAAXXM}{}{}{**EEE(1)(