模式识别 第6章 特征的选择和提取学习资料

模式识别:特征的选择和提取第6章特征的选择和提取目录6.1引言6.2类别可分离性判据6.3特征选择(重点)6.1

引言特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步降低特征维数在很多情况下是有效设计分类器的重要课题特征的选择与提取简述两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取

(extraction)：用映射（坐标变换）的方法把原始特征变换为较少的新特征特征选择(selection)

：从原始特征中挑选出一些最有代表性，分类性能最好的特征目的：降维特征的选择与提取举例细胞自动识别：原始测量：细胞的数字图像原始特征：细胞面积，胞核面积，形状系数，光密度，核内纹理，和浆比压缩特征：原始特征的维数很高，需压缩以便于分类特征选择：挑选最具分类信息的特征挑选两个好的特征：胞核面积、光密度特征提取：坐标变换产生两个新的特征，它们由原始特征的变换得到特征选择？特征提取？哪种方法更适用于我们专业？生物相关的问题，往往需要真实的特征。例如：基因芯片中的特征为基因：特征选择将得到有代表性的重要基因，这些特征基因是真实的。特征提取将从原始特征得到新的特征，这些特征不能称为特征基因。特征选择特征选择？特征提取？哪种方法更适用于我们专业？提取选择目录6.1引言6.2类别可分离性判据6.3特征选择(重点)6.2类别可分离性判据类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则理想准则：某组特征使分类器错误概率最小实际的类别可分离性判据应满足的条件：度量特性：与错误率有单调关系当特征独立时有可加性：单调性：常见类别可分离性判据：基于距离、概率分布、熵函数准则函数例子准则函数例子其它可分性判据基于概率的可分性判据：用概率密度函数间的距离来度量正态分布的散度Mahalanobis基于熵函数的可分性判据Shannon熵：平方熵：目录6.1引言6.2类别可分离性判据6.3特征选择(重点)目录6.1引言6.2类别可分离性判据6.3特征提取6.4特征选择(重点)经典特征选择算法许多特征选择算法力求解决搜索问题，经典算法有单独最优特征组合法、后退法、前进法(重点)分支定界法模拟退火法(重点)Tabu禁忌搜索法遗传算法(重点)穷举法由原始的D维空间降到d维空间问题。一共有q=CDd种特征组合结果。D=20，d=10时，q=D=100，d=10时，q=

穷举法（最优方法）：一定能找到最优解如果计算每组特征组合的J值，然后选择J值最优的特征组合，往往非常耗时。计算量上无法承受。耗时!1847561013怎样减少计算时间？使用一些次优方法，以大大减少计算时间。为什么有如此多的特征选择算法？没有哪个算法能够保证兼顾运算时间又能得到更优的解。单独最优特征组合计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果特征选择结果（取前d个）不一定是最优结果当可分性判据对各特征具有可加性（各特征独立），该方法可以选出一组最优的特征来，例：顺序前进法（SequentialForwardSelection，SFS）顺序前进法是一种自下而上的搜索方法，它从0个特征开始每次增加一个特征，所增加的特征应使它与已入选的特征组合在一起所得J值为最大，直到特征数增加到d为止。设已选入了k个特征构成了一个大小为k的特征组Xk，把未入选的D-K个特征xj，j=1,2,…,D-k,按与已入选特征组合后的J值大小排列：若则下一步的特征组选为Xk+1=Xk+x1顺序前进法考虑了所选特征与已入选特征之间的相关性，一般来说比单独方法好。主要缺点是一旦某特征已选入，即使由于后加入的特征使它变为多余，也无法再把它剔除。广义顺序前进法（GeneralizedSequentialForwardSelection,GSFS）把SFS法推广为每次不止增加一个特征而是增加L个特征，就成为广义顺序前进法（GeneralizedSequentialForwardSelection,GSFS）。即每次从未入选的特征中选择出L个特征，使得这r个特征加入后J值达最大。GSFS法计算量大（每步有CLD-k

个候选特征组需要逐个计算）。另外它也无法剔除已入选的特征。顺序后退法（SequentialBackwardSelection,SBS）顺序后退法是一种自上而下的方法，它从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的J值最大，直到特征数减少到d为止。设已剔除了k个特征，剩下的特征组为，将中的各特征xj按上述J值大小排序，j=1,2,…,D-k。若则顺序后退法的优点在计算过程中可以估计每去掉一个特征所造成可分性的降低，缺点是由于顺序后退法的计算是在高维空间进行，所以计算量比顺序前进法要大。同样，该方法也可推广为广义顺序后退法（GeneralizedSequentialBackwardSelection,GSBS).增L减r法（L-r法）为了避免前面方法一旦被选入（或剔除）就不能再剔除（或选入）的缺点，可在选择过程中加入局部回溯过程。例如，在第k步可先用SFS法一个个加入特征到k+L个，然后再用SBS法一个个剔除r个特征，我们把这样一种算法叫增L减r法。增L减r法（L-r法）步骤一：用SFS法在未入选特征组中逐个选入L个特征，形成新特征组Xk+L，设置k=k+L，步骤二：用SBS法从特征组Xk中逐个剔除r个最差的特征，形成新特征组Xk-r，设置k=k-r，若k=d，则终止算法，否则设置xk=xk-r，转向第一步。（1）当L>r时，L-r法是一种自下而上的算法，先执行第一步，然后执行第二步，开始时，设置k=0，x0=空（2）当L<r时，L-r法是一种自上而下的算法，此时先执行第二步，然后执行第一步，开始时设置k=0，x0={x1，…,xD}

（ZL，Zr）法：广义L-r法Li,i=1,2,…,ZLrj,j=1,2,…,Zr

（ZL，Zr）法：广义L-r法模拟退火算法1982年，Kirkpatrick(译名：科克派特瑞克)等人将退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP完全组合优化问题的有效近似算法——模拟退火算法（simulatedannealingalgorithm)。他源于对固体退火过程的模拟；采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。模拟退火的原理也和金属退火的原理近似：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。模拟退火算法应用的一般形式从选定的初始解开始，借助于控制温度t递减时产生的一系列Mapkob（马尔科夫）链，利用一个新解产生装置和接受准则,重复进行包括“产生新解­——计算目标函数——判断是否接受新解（或舍弃）新解”这三个阶段，不断对当前解迭代，从而达到使目标函数最优（最大或最小）的执行过程。书中用于特征选择的模拟退火算法initilaize(i0,T0,L0)k:=0;i:=i0repeatforL:=1toLkdobegin

generate(jfromSi);iff(i)<f(j)i:=jelseiftheni:=j;endk:=k+1calculate-length(Lk)calculate-control(Tk)untilstopcriterionMetropolis接受准则对应的转移概率冷却进度表参数选择方案冷却进度表是一组控制算法进程的参数。温度T的初值；控制参数T的衰减函数；Mapkob链的长度；停止准则；冷却进度表是影响模拟退火算法试验性能的重要因素，其合理选取是算法应用的关键。温度T的初值T0的选取原则

T0值的选取基于“Tk值只要选的充分大，就会立即达到准平衡”的论证，为使算法进程一开始就达到准平衡，应让初始接受率为

Metropolis准则，可推知T0值很大。例如取，则在时T0

>949。经验法则要求算法进程在合理时间里搜索尽可能大的空间范围，只有足够大的值才能满足这个要求。温度T的衰减函数衰减函数(k＝0，1，2，...)。其中是一个接近1的常数。这个衰减函数是Kirkpatrick等人首先提出来的，他们取。Bonomi以及Lutton等许多研究者研究，认为值一般在0.5-0.99范围内取值为宜。Mapkob链的长度直接指定方式n为循环次数此外，Skiscim和Nahar等人提出用单个Mapkob链的终止准则去产生Lk，Lk的值与Tk值相关。这类方法便于控制最终解的质量，却难以把握算法进程的时间。在Mapkob链的终止准准则选择不当时，甚至可能危及模拟退火算法的收敛性。而用限定Lk的方法和他相反，它便于直接控制算法进程的CPU时间。停止准则停止准则1:循环n次停止。停止准则2:在若干个相继的Mapkob链无任何优化就停止算法。这种停止准则（准则2）兼顾了最终解的质量和CPU时间。在T，L等参数的配合下，可得到高质量最终解。模拟退火算法与初始值无关，算法求得的解与初始解状态无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法

。习题：叙述用于特征选择的增l减r搜索算法的算法步骤。并考虑l值大于（或小于）r值时，增l减r算法步骤应做出怎样的修改，以及该情况下，增l减r搜索算法的特点？为什么分类器设计中的最近邻法可以适用于线性不可分的样本集？为什么最近邻法又称为分类器设计的非参数方法？它与fisher等参数方法在训练和预测阶段效率上有什么不同？遗传算法的运算过程主要分四个阶段，包括编码阶段、___________、交叉阶段、___________。叙述怎样利用模拟退火算法是进行特征选择。模拟退火算法采用___________准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近