基于模糊核匹配追寻的特点模式识别.docVIP

PAGE PAGE 16 《计算机学报》2009年8期 基于模糊核匹配追寻的特征模式识别 李青 焦李成 周伟达 (南京电子技术研究所1313信箱100分箱 南京 210013) (西安电子科技大学智能信息处理研究所 西安710071) 摘要：核匹配追寻算法是近年来新兴的模式识别方法，在处理非线性及高维模式识别问题中表现出了突出的优点。传统的核匹配追寻在处理模式识别的问题中平等地对待所有样本，最终的判决函数是针对所有样本的一个平等综合考虑，要求总识别误差尽可能的小，并不能对某一类指定的样本进行针对性地识别，然而实际应用中经常会碰到这样的情况：要求对某一类样本的识别精度很高，尤其是对于非平衡样本中或者对于具有时间属性的样本序列，由于标准核匹配追寻学习机自身的局限性，使其不能有效地处理这些问题。本文针对这些问题，提出了模糊核匹配追寻学习机，预先根据分类的要求对每个样本做出了不同的重要性定义，学习机根据重要性不同，对样本进行程度不同的学习，最终得到基于问题的判决——对重要样本保持很高的分类精度；最后通过实际的仿真实验证明了模糊匹配追寻的有效性及可行性。 关键词 机器学习；核匹配追寻；模糊；时间序列; 特征目标识别 引言 核匹配追寻（Kernel Matching Pursuit，即KMP）是近年来新提出的一种模式识别方法，它首先通过核映射将训练样本映射成为一组基原子字典，通过贪婪算法在基函数字典中寻找一组基原子的线性组合来最小化损失函数，该线性组合即为所要求解的判别函数。核匹配追寻分类器的分类性能几乎可以达到支撑矢量机的分类性能，同时较其他经典的核机器算法相比，具有更为稀疏的解[1]。 然而在实际问题中，存在这样几种情况：1）对指定类别的识别精度有特殊性要求——在识别问题中，一类样本（或某些样本）比另一类样本（或其余样本）更为重要，要求对这些重要样本的识别精度要高（例如对癌细胞的检测、非法入侵的检测）；2）所获得的样本是具有特征时间属性的，也就是说，在某些特定的问题中，某一时间段内的样本相比其他样本具有更为重要的意义，这就需要对处于这一时间段内的样本给予特殊地对待，使得这些样本对最终的判决起到更为重要的贡献；3）非平衡样本的识别，在很多实际的问题中，两类样本的个数是不平衡的，尤其是当所采得的特征样本（或弱势样本）相对于另一类样本很少时，对弱势样本的识别就变得非常困难，由于传统核匹配追寻的最终决策是针对整个样本集做出的综合考虑，这就使得学习机弱势样本识别很难。 虽然核匹配追寻已经成功地应用于许多领域，如人脸识别，手写体识别，笔记身份鉴定，数据挖掘等[3,5]；然而，传统的核匹配追寻在处理模式识别的问题中平等地对待所有的样本，最终的求解是对错分误差和分类间隔进行折中的结果，它可以对两类样本做出平等综合的考虑，要求总识别误差尽可能的小，并不能对某一类或某一些指定的样本进行针对性的识别，这就限制了核匹配追寻在这些有特殊要求问题中的应用。 本文认真分析了核匹配追寻的原理，提出了模糊核匹配追寻，根据样本之间的重要性，对每个样本分别设定不同的模糊因子，使得学习机训练出针对目标样本的决策，进一步扩展了核匹配追寻的应用范围。最后，通过实际的实验证明了模糊核匹配追寻的可行性及有效性。 核匹配追寻 2.1 基本匹配追寻算法 给定个观测点，相应的观测值为。匹配追寻的基本思想是：在一个高度冗余的字典（dictionary）空间D中将观测值为分解为一组基函数的线性组合，其中字典D是定义在希尔伯特空间中的一组基函数[2,3]。假定字典包含M个基函数： （1） 同时，定义损失函数（亦称为重构误差）： （2） 其中，称为残差，是对个观测点的观测值的逼近。匹配追寻算法在每一步的迭代中从字典中寻找一个基函数及其相应的系数，使得当时，当前的残差能量最小，即 （3） 由匹配追寻算法[4]， （4） （5） 其中，表示两个向量的点积，表示向量的二范数。 由上可知，匹配追寻实际上采用了贪婪算法，每次迭代都是从字典中查找与当前残差相关系数最大的基函数分量，随着分解次数的增加，式（5）右端基函数向量的线性组合理论上可以任意的逼近原始观测值，但是通常在满足某种精度条件时就终止了，如残差能量低于某一阈值，或者当基函数的