（计算机应用技术专业论文）基于粗糙集和支持向量机的人脸识别.pdf

摘要 人脸识别技术涉及到图像处理、模式识别和人工智能等多门学科，已成为计 算机视觉和模式识别领域中一个富有挑战性的课题，在国家安全部门和银行密码 系统等领域具有广泛的应用背景。 支持向量机( s v m ) 算法由于过学习问题而导致其泛化性能降低，结合粗集对不 精确数据的处理能力，提出了一种基于粗集边界和v - 支持向量机( r s m v - s v m ) 混 合分类算法。该算法先在训练前采用粗集理论边界区域的不确定性预选出边界集， 替代原始样本作为训练集，减少训练集的数目；然后在v s v m 算法的基础上引入 了粗集理论上下近似集概念改进v s v m 算法，使其训练边界集。实验结果表明， 该算法在分类正确率不受影响的情况下，大大缩短样本的训练时间，从而提高了 改进的v - s v m 的泛化性能和分类速度。为了降低冗余和进一步简化输入空间的维 数达到减少算法求解计算量及处理时间，同时引入了粗糙集的属性简约方法对数 据进行约简。 在人脸识别过程中，人脸图像的特征向量采用核主元分析( k p c a ) 和属性约简 方法联合进行提取，从而该特征向量作为r s m v - s v m 输入。用r s m v - s v m 算 法对人脸图像样本进行训练，生成r s m v - s v m 分类器对人脸进行分类识别。针 对o r l 人脸数据库进行了实验，表明联合特征提取和r s m v - s v m 的入脸识别方 法在识别率不变的情况下，具有很强的泛化性能。 关键词：人脸识别；粗糙集；支持向量机；边界样本集；属性约简 a b s t r a c t f a c er e c o g n i t i o nt e c h n o l o g yi n v o l v e sm a n yf i e l d s ，i n c l u d i n gi m a g ep r o c e s s i n g ， p a t t e r nr e c o g n i t i o n ，a r t i f i c i a li n t e l l i g e n c ea n ds oo n ，w h i c hh a sb e c o m ec h a l l e n g i n g s u b j e c t si nc o m p u t e rv i s i o na n dp a t t e r nr e c o g n i t i o nf i e l d s s oi th a sw i d ea p p l i c a t i o n s p r o s p e c ti nm a n yf i e l d s ，s u c ha si nd e p a r t m e n to fn a t i o n a ls e c u r i t ya n db a n kp a s s w o r d s y s t e m t h eg e n e r a l i z a t i o na b i l i t yo fs v ma l g o r i t h mi sd e c r e a s e dd u et oo v e r - l e a r n i n g ，i n t h e p a p e r ，ah y b r i dc l a s s i f i c a t i o na l g o r i t h mb a s e do nm a r g i no fr o u g hs e t sa n d v - s u p p o r tv e c t o rm a c h i n e ( r s m - v - s v m ) w a sp r o p o s e dw h i c hc o m b i n i n gi m p r e c i s e d a t aa b i l i t yo fr o u g hs e t f i r s t l y ，t h ea l g o r i t h mg e tt h eb o u n d a r ys e tu s i n gu n c e r t a i n t y p r o p e r t i e so fm a r g i nr e g i o no fr o u g hs e tt h e o r yb e f o r et r a i n i n g ，w h i c hs u b s t i t u t et h e o r i g i n a li n p u t sa sat r a i n i n gs u b s e t ，a n dt h es i z eo ft h et r a i n i n gs e tw a ss h o r t e n t h e n ， t h ec o n c e p to fu p p e ra n dl o w e ra p p r o x i m a t i o ns e to fr o u g hs e tw a si n t r o d u c e df o r i m p r o v i n gt h ev - s v m ，w h i c hw a sb a s e do nt h ev - s v ma l g o r i t h m e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea l g o r i t h mc a n ti n f l u e n c er e c o g n i t i o nr a t ea n ds h o r t e nt r a i n i n g t i m ei m p r o v e dv - s v mw h i l ek e e p i n gt h es p e e do fc l a s s i f i c a t i o na n dt h ep e r f o r m a n c e o fg e n e r a l i z a t i o n a l g o r i t h ma t t r i b u t e r e d u c t i o n ( a r ) o fr o u g hs e tt h e o r yw a s i n t r o d u c e dt or e d u c ed a t a sf e a t u r e s ，s ot h ec o m p u t a t i o na n dt h et i m ec o m p l e x i t yi s d e c r e a s e d i nf a c er e c o g n i t i o np r o c e s s ，e x t r a c tt h ef e a t u r e so ff a c ei m a g e sw i t ht h ek e r n e l p r i n c i p a lc o m p o n e n ta n a l y s i s ( k p c a ) a n da r ，t h e ng e tt h ee i g e n v e c t o r so ff a c e i m a g e sa st h ei n p u to fr s m v - s v ma l g o r i t h m ，p r o d u c er s m - v s v mc l a s s i f i e rl a s t f a c ei m a g e sc a nb er e c o g n i z e dw i t hr s m - v - s v mc l a s s i f i e r t h ee x p e r i m e n t so no r l f a c ed a t a b a s es h o wt h a tf a c er e c o g n i t i o np r o c e s so fc o m b i n e df e a t u r ee x t r a c t i o na n d r s m v - s v mh a ss t r o n gg e n e r a l i z a t i o np e r f o r m a n c ew h i l ek e e p i n g r e c o g n i t i o nr a t e k e yw o r d s ：f a c er e c o g n i t i o n ；r o u g h s e t ；v - s u p p o r tm a c h i n e ；b o u n d a r ys e t ； a t t r i b u t er e d u c t i o n i l 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：诱杠痤日期：别。年6 月乡 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。同时授权中国科学技术信息研究所将本论文收录到中国学位论 文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：蔚缸也 导师签名：弓 日期：如，d 年6 月夕 e 1 日期：幻o 年 多月多 日 第1 章绪论 1 1 课题的研究背景与意义 当今社会中，随着计算机技术、网络技术和信息技术的飞速发展，身份识别 已经是一个不争的事实，尤其是在信息安全、涉及到隐私和权限的地方显示出前 所未有的重要性，特别是在网上银行、电子商务、公共安全等领域对身份识别的 可靠性、安全性和认证的方式提出了新的要求，已有的身份识别手段( 如钥匙、身 份证、智能卡、磁卡等) 已经不能满足这些要求。已有的身份识别手段存在容易丢 失、使用过度而损坏、携带不方便和被破解等许多局限性问题，而人脸作为生物 特征识别具有不会遗失、不易被复制、采集方便、唯一性、不被察觉等优点， 正越来越受到人们的重视，已经进入了社会生活的各个领域。与视网膜、指 纹、虹膜、语音、掌纹等其它人体生物特征识别系统相比，人脸识别系统以其 方便、友好等特点，具有的应用前景十分广泛，人脸识别门禁考勤系统、人脸识 别a t m 机智能视频报警系统和人脸识别公安罪犯追逃智能报警系统的身份识别； 视频会议以及医学等方面的应用，因此己成为目前模式识别和基于内容检索领 域的一个研究热点。 人脸识别属于生物识别技术的一种，利用世界上每个人的人脸各不相同来实 现身份识别。人脸图像通过摄像机或视频截图来进行采集，对采集到的图像进行 人脸定位和检测，进而进行人脸图像预处理、特征提取、训练与分类等一系列相 关技术来确认身份，达到识别不同人身份的目的【：】。当前，研究人员对人脸识别技 术的研究尽管取得了可喜的成果，但是由于人脸的不同表情( 如大笑、发怒、眼 的开与闭等) 、人脸的遮挡( 如头发、眼镜和头部饰物以及其他外部物体等) 、光 照的影响( 如图像中的亮度、对比度的变化和阴影等) 、成像角度的不同以及化妆 的多样性等造成人脸的多姿态使得在实际应用中给正确识别率带来了困难【3 】，因此 要使得人脸识别技术在识别正确率和识别速度达到一定的标准，还需要我们不断 做出努力。 这几年来，因在许多应用领域支持向量机( s v m ) 表现出来的良好特性，使得它 已成为模式识别和人工智能等领域的一个研究热点。支持向量机集成了多项关键 理论技术如最优化理论和核技术理论等使它在解决高维数小样本模式识别问题等 方面具有独特的优势，从而具有较高的识别率和泛化能力。尽管基于支持向量机 的识别方法在识别时间、识别率和识别速度等方面都具有其独到的优越性，但是 也有不足之处，它不能辨别数据中那些是有用的或者无用的；数据中那些是多余 的或者起干扰作用的；数据中那些条件相互矛盾或者排斥；数据中那些重要性大 或者贡献微小，数据中那些删除或者保留，即如何得到有用的数据大大节约数据 存储量和提高数据的使用效率，减少识别时间在s v m 算法中没有体现。s v m 一 般输入信息空间维数较大时训练时间会很长，影响到整个识别系统的时间效率。而 粗糙集理论是当前比较热门的处理模糊与不确定信息的工具之一，具有从数据中 获得对分类有用知识的能力。粗糙集方法通过挖掘数据间相互的联系，不仅可以 删掉知识系统中冗余或起干扰作用的信息，而且可以将信息的空间表示维数进行 简化，从而样本的训练时间可以缩短，训练的实效性及准确性所有提高。因此， 本文利用两者的优点将它们结合起来，构造了一种基于粗糙集的v - 支持向量机混 合分类算法用于人脸的识别。所以，对于基于粗糙集的v - 支持向量机混合分类算 法的人脸识别的研究是有意义的。 无论是对于支持向量机理论和粗糙集理论，还是人脸识别技术，都是前沿的 技术，是研究领域中的研究热点，在应用领域的研究中还有待探索和完善。 1 2 人脸识别的发展与现状 计算机人脸识别技术从2 0 世纪才渐渐以展起来的，9 0 年代已经成为研究中的 热点【】。早期人脸识别研究大致可以总结为两个方向：一是基于提取人脸几何特征， 主要针对鼻尖和眼角等人脸部位归一化后所构成的二维拓扑结构进行人脸识别方 法；二是基于模版匹配，包括使用图像灰度和计算模版来进行人脸识别方法。到 9 0 年代初期，人脸识别的方法取得了突破性进展，可以归纳为如下两种方法：一是 把整个人脸看作一个整体属性，其中主要方法有奇异值分解方法、特征脸方法、 弹性图匹配方法、隐马尔可夫模型方法以及神经网络的方法等称为整体的识别方 法例；二是利用人脸脸部各个特征的形状不同( 鼻、眼、嘴) 得到不同的参数构成特 征向量称为特征分析的识别方法。第一种整体的识别可以保持人脸各个部件之间 的相互联系和保持了各个部件自己的信息，而特征分析的识别方法则是通过把各 个部件最有用的特征提取出来设计具体识别算法。两种有各自的特点：整体的识别 把整个人脸图像作为一个整体，但是由于视角、人脸面部表情、光照等对识别有 很大的影响，怎么样处理这些干扰信息又是一个问题。特征分析识别方法对各个 部件如何建立好的模型又是一大挑战。当今的一大趋势是将人的整体和特征分析 的识别方法结合起来，如k i n m a n l a m 提出的基于整体和特征分析的方法和 a n d r e a s l a n i t i s 提出的利用可变形模型来对人脸进行解释和编码的方法等。目前多 姿态人脸识别是目前研究又一大趋势，其主要方法是多视图模板匹配、基于3 d 人 脸模型的姿态补偿等。激光扫描器等高科技特殊设备使用以致可以得到人脸的三 维模型，这样可以得到更多的信息，因此三维人脸识别渐渐成为模式识别研究的 一个前沿方向【6 】。目前人脸识别的研究重点是多姿态识别、基于视频的识别、不 同识别算法的融合、实用系统的设计以及多通道信息融合，要满足实用的要求， 到目前为止还没有比较满意的研究成果【7 t o 】。 2 1 3 本文的工作 通过对人脸识别过程的分析，将粗糙集和支持向量机这两种算法有效结合， 提出了种新的数据分类算法即基于粗糙边界和v 支持向量机( r s m v s v m ) 混 合分类算法。算法分析粗糙集和支持向量机各自的优点，通过粗糙集中的边界区 域预选支持向量用来i ) i i 练改进的v 支持向量机，该改进的算法对人脸进行i j i i 练与 识别。人脸的特征提取采用利用k p c a 和基于属性重要度约简联合提取，可以去掉 那些对分类冗余或起干扰作用的属性，而保留那些能有效区分各个类别的属性， 从而达到了降低输入变量的维数来取得更好的分类精度的目的。联合提取特征和 r s m v s v m 的人脸识别方法取得了较优的分类性能。 1 4 本文的组织 全文的主要内容安排如下： 第一章绪论。首先介绍了人脸识别研究的背景和意义、分析了支持向量机与 粗糙集各自的优点及人脸识别发展与现状。 第二章支持向量机和粗糙集理论基本理论。首先论述了支持向量机的相关理 论基础，包括函数集的v c 维、结构风险最小化等理论。支持向量机基本原理内 容分为线性支持向量机与非线性支持向量机两个方面，特别论述了支持向量的分 布情况及支持向量机的几种改进的算法。然后论述粗糙集理论，关于粗糙集的基 本概念，包括信息系统、不可区分关系、上近似集、下近似集等。在此基础上， 给出了约简与核、属性重要度的概念及信息熵与粗糙集的关系。 第三章基于粗集边界和v 支持向量机( r s m v s v m ) n 合分类算法。先分析 粗糙集和支持向量机的各自的优点，利用粗糙集的边界区域预选出支持向量的样 本集，用这些样本集作为改进的v - s v m 算法的输入并给出了仿真实验。 第四章r s m v - s v m 在人脸识别中的应用。分析了核主元分析( k p c a ) 特征提 取方法，结合k p c a 和基于粗集属性重要度约简理论方法联合提取人脸特征，得 到更有利于分类的特征向量，最后将r s m v - s v m 混合分类算法用于人脸识别的 训练与识别并给出实验结果，证明该算法的可行性及优越性。 最后对全文进行总结，并提出了进一步的研究方向。 参考文献部分列出了本论文参考的主要论文和资料。附录部分给出了攻读硕 士学位期间的主要研究成果。最后的致谢部分对导师和各位师友所提供的帮助表 示衷心的感谢。 第2 章支持向理机与粗糙集理论 2 1 支持向量机理论 2 1 1 支持向量机简介 1 9 9 5 年v a p n i k 教授等人提出了s v m 】，目前它已经成为了很受欢迎的机器 学习方法。s v m 是在统计学习理论的核心理论即v c 维和结构风险最小化理论的 基础上建立的，它将输入样本集合变换到高维空间中使得其分离性状况得到改善， 构造出更好的分类器，这种分类器的特点是他们能够同时最小化经验误差与最大 化几何边缘区，以获得适应性强、全局最优、泛化性能好等优点，在一定程度上 克服了以前机器学习中面临的维数灾难问题、局部最小值问题以及过学习与欠学 习问题等很难克服的障碍，它确实是一种具有较强泛化能力的机器学习方法。s v m 能很好地自动寻找对分类有很好区别能力的支持向量，由它构成的分类器可以在 类与类之间构造一个超平面来作为最优分类面，因此它在处理小样本问题、非线 性及高维模式识别问题中表现出许多特有的优势。由于s v m 具有一系列的优势和 它在一些应用领域中体现出比其它机器学习方法较强的适应能力，因此s v m 己变 成了模式识别领域研究和应用的前沿方向，并且在人脸识别、数字水印技术和指 纹识别等许多模式识别领域有着广泛的应用 1 2 叫 。 2 1 2 支持向量机相关理论背景 1 v c 维理论 到当前为止，v c 维理论已经成为描述机器学习能力的一个重要指标。它是由 v a p n i k 和c h e r v o n e n k i s 在1 9 7 1 年共同提出的一个基于统计学习理论中的核心理论。 一个函数集，假设存在着1 1 个样本可以被函数集中的函数按照所有可能2 ”种 形式分为两类，则1 1 个样本能被这个函数集打散的话，那么最大样本数目1 1 就称 为函数集的v c 维。函数集合分开的最大样本数目体现了v c 维分类样本的能力。 如果我们能找到一个函数集合能够把任意数目的样本集分类，那么就说明了这个 函数集的v c 维就是无穷大。正是因为s v m 关注的是v c 维，s v m 解决问题的时 候，和样本的维数是无关的，甚至样本可以是上万维。以上是我们对于v c 维的 基本描述。 对于任意函数集v c 维理论的计算，到至今为止，仍然没有如何计算的具体算 法，现有的算法只能给出v c 维的结果范围。尽管我们知道一些特殊的函数集v c 维， 但是它还受学习算法等因素的影响。 4 2 结构风险最小化准则 在介绍结构风险最小化时，必须了解期望风险最小化准则和经验风险最小化 准则。理论上来分析，我们通过训练所能得到的最好的分类器应该有最小期望风 险( 误差) ，分类器f ( a ) 的期望风险可以表述如下： r ( a ) = i e ( f ( x ，口) ，y ) d p ( x ，y )( 2 1 ) 通过式( 2 1 ) 能够理论上选择到最好的分类器，但风险函数g ( f ( x ，口) ，y ) 为积分 的形式和概率分布p ( x ，y ) 是未知的，所以我们能够利用到的信息只能通过测试样 本，否则就无法在实际应用中使用该准则。而当我们无法得到最好的分类器时， 只有寻求次优的分类器，即所谓的经验风险最小化准则，可以描述如下： 1 l r e m p ( 口) = 亡s ( 厂( x ，口) ，y ) ( 2 2 ) ，i t = l 即当，- - - ) 0 0 时，r e m p ( 口) 渐进趋向于r ( a ) 。大数定理能够证明，若我们用来训 练的样本足够多时，在实际应用中经验风险最小化准则应该工作的更好。然而对 于很多问题中样本数目离无穷大很远，那么在有限样本下经验风险最小化准则就 不一定能使真实风险较小，特别对于模式识别问题来说，训练样本不够多时，使 用经验风险最小化准则就很容易产生过拟合或过学习问题。 从上述可知，在有限样本情况下，仅仅用经验风险最小化准则来近似真实风 险是不可行的，推广性的界就是在它们之间找到一个平衡点，经验风险r e m p ( a ) 弄f j 真实风险r 位) 之间泛化误差界的公式为： r ( a ) r 唧( 口) + 1n ( 1 n ( 2 1 n ) + 1 ) - i n r 4 ( 2 3 ) y 其中n 是函数集f ( c r ，x ) 的v c 维，表示了复杂性的高低，是训练样本集， r 【o ，1 】是一个参数，上式右边第二项称作置信风险，它与两个量有关，一是样本 数量，显然若给定的样本数量越大，我们的学习结果越有可能正确，此时置信风 险越小；二是分类函数的v c 维，显然v c 维越大，泛化性能越差，作置信风险就 会越大。这一结论说明了学习机器的实际风险由经验风险( 训练误差) 和置信范 围两部分组成。它表明在有限训练样本下，学习机器的v c 维越高( 复杂性越高) 则置信范围越大，以致真实风险与经验风险之间可能的距离越大，这就是为什么 会出现过学习问题的原因。对此，统计学习的目标从经验风险最小化变为了寻求 经验风险与置信风险的和最小，即结构风险最小。在保证分类正确率的同时，结 构风险最小化算法可以降低机器学习的v c 维以缩小置信范围，可以使机器学习在 整个样本集上的期望风险得到控制。 2 1 3 支持向量机的基本方法 1 线性支持向量机 s v m 本质上是在寻求一个超平面，该超平面能最大限度地分开两个类别的训 练样本，同时使每类样本到它的距离尽量的大，超平面称为最优分类超平面。换 一句话说，超平面具有尽可能大的几何边缘，它们之间的距离叫做分类间隔。支 持向量机分类的目标力求寻找一个不但将两类样本正确分开的超平面，而且该超 平面使分类间隔最大。 设给定可分线性样本集 ( x ，y a f _ 1 ，z ) ，x r d , y ， + l ，一1 ) 是类别标号。d 维空 间的线性判别函数一般形式为g ( x ) = w x ，分类面方程为： w x + b = 0 ( 2 4 ) 将判别函数归一化，而要求分类面能够对所有样本正确分类就是要求它满足： y ，( w x f ) + b ) 1 f = 1 ，刀( 2 5 ) 此时两类样本都满足ig ( x ) i 1 ，那么离分类面最近的样本满足lg ( x ) l _ l ，这样 分类间隔为2 州w l l ，原则上s v m 就是要使分类间隔最大化来分开两类训练样本集， 因此使分类间隔最大相当于使0wi i 最小。满足上式条件且使1 2l iw0 2 最小的分类 面叫做最优分类面。 求解最优分类面可表示为下面的二次线性规划函数： m i n i m i z e 矽( w ，b ) = 1 2 | | w1 1 2 s t y ，( w x ，) + b 1 f - 1 ，z ( 2 6 ) 式( 2 6 ) 可利用l a g r a n g e 优化方法求解，使学习问题转化为其对偶函数和约束 条件为： m a x 9 ( 口) = 口，一q 口，y ，y j ( x i x j ) i - l 1 = l 盯 丁和= 。 q _ 【 o ，i = l ，7 解式( 2 7 ) 后得到的最优分类判别函数为： r 卅、 厂( x ) = s g n ( w x ) + 6 ) = s g n 口，y ，( x ，- c ) + 6 ( 2 8 ) lt = lj 口，为式( 2 6 ) 函数中与每个约束条件式( 2 5 ) 对应的l a g r a n g e 乘子，口，存在唯一 解，因为式( 2 6 ) 是一个不等式约束下二次函数寻优的函数。从式( 2 7 ) 解的过程中 可以看出，支持向量( s u p p o r tv e c t o r ，s v ) 是那些使式( 2 5 ) 等号成立且位于分类间隔 平面上的点( 口0 ) 对应的训练样本，s v 在全体样本集中往往占有的比例很少。式 ( 2 8 ) 最优分类判别函数中m 表示支持向量数，即l a g r a n g e 乘子口，0 对应的样本个 数，b + 称为分类阈值，它用任一个口，0 或通过两类中任意一对( 口，口，) 支持向量 6 取中值都可以求得。 在多数情况下，线性可分寻求的最优分类面并不能满足实际应用的需要( 如外 界噪声等影响) ，实际上对于线性不可分的问题，可以通过在条件中增加松弛因子 喜0 及正则化因子c ，则二次规划函数将改变为： m i n i m i z e 如，6 ) = 扣w1 1 2 + c 喜鲁 ( 2 9 ) s j y ，( w x ，) + 6 ) 1 一毒，鼻0 ，i = 1 ，胛 此时对偶函数和约束条件变为： m a x q ( 口) = 口f 一寺口f 口y f y j ( x f x j ) f 一1 ( 2 1 0 ) 盯 善y 成- o 9 一 1 0 c t ，墓c ，f _ 1 ， 其中c 0 是某指定的常数，实现上对错分样本惩罚的程度可以用c 来控制， 使得训练误差与机器学习能力之间达到一个折衷。从式( 2 1 0 ) 看出函数能够满足结 构风险最小化原则，因其考虑了经验风险和置信范围。 2 非线性支持向量机 从上面线性支持向量机的问题中看出，不论是原始函数的对偶问题还是判别 函数只涉及训练样本之间的内积运算。非线性支持向量机的工作原理是通过一个 非线性函数映射：r ”j h 将训练样本从输入空间映射到高维的特征空间日中，再 在特征空间日中构造最优超平面。问题函数只使用空间中的内积，即 k ( ， ) = ( 薯) ( x ，) ，把内积函数k ( x i ，x ，) 称为核函数，核函数可以通过原空间中 的函数在高维空间上实现，不需要知道变换矽的具体形式。根据h i l b e r t s c h m i d t 原 理，只要寻找满足m e r c e r 条件的函数k ( ，) 就可以作为核函数【】。因此，运用适当 的核函数，最优分类面就可以实现从非线性变换后的线性分类，而不增加算法的 计算复杂度，那么函数描述为t m a x q ( o t ) = 口一i 1 口f 吩y f y k ( t x j r a 1 r a ) ，- l，= l 判别函数变为： m 闽印馕如脚，“ 亿 i ，s 矿j 7 0 = d 口 儿 暴 由式( 21 2 ) 可以看出，在函数中只有s v 的内积和求和，因此s v 的个数决定了算 法的计算复杂度。 式( 2 1 1 ) 具有最优解当且仅当要满足k k i ( k a r u s h k u h n t u c k e r ) 条件，令 2 ，( ) 2 善“， k - t + 6 式( 21 1 的k k t 条件为 i 口，= 0 ，1 0 f f , - 1 ) 0 q ( c ， ，= o f f , = - 1 口，= c ，一1 ，1 2 ) 只雹= o ，0 得到一个解口，用它柬计算权重向量为： f 2 13 1 f 2 1 4 、 w + = j h ( ) ( 21 5 ) j e j r 偏移量b 可以计算表示为： b 。= 一h k ( ，x s ) ( 21 6 ) t “ 由式( 2 15 ) 和式( 2 1 6 ) 可知，口? 0 对应的训练样本可以决定w 和b ，那么对 应d + ，0 的样本可以决定最优分类超平面，这就是支持向量。如图2i 中的实心点 所示。 图21 图e e 实心点为s v 从图2l 可以看出，支持向量位于分类函数上。分布在一1 ，( ) 1 区域的样 本对应于口= c ，我们称为边界支持向量，s v m 可能会错分该区域的样本。分布 在，= 1 或f = 一1 上的样本对应于0 口， c ，称为标准支持向量s v m 能够正确分 类。分布在l f ( x ，) b 1 上的样本对应于口，= 0 ，s v m 能够完全正确分类。 2l4 核函数 核函数是s v m 的关键，这也是它最喜人的地方。低维空间向量集通常难于划 分，解决的方法是将它们映射到高维空间。但这个办法带来的困难就是计算复杂 度的增加，而核函数正好巧妙地解决了这个问题。也就是说，只要选用适当的核 函数，我们就可以得到高维空间的分类函数。在s v m 理论中，采用不同的核函数 将导致不同的s v m 算法。 1 核函数理论与性质 对于m e r c e r 定理可以描述如下： 任意函数k ( x ，y ) 可表示成k ( x ，y ) = ( 矽( x ) ，( y ) ) 内积形成当且仅当k ( x ，y ) 是半 正定的。 由m e r c e r 定理可知，两个核函数k l ，k 2 的复合核函数也满足m e r c e r 定理即： k ( x ，y ) = c k l ( x ，y ) ，c 0( 2 1 7 ) k ( x ，y ) = a k l ( x ，y ) + b k 2 ( x ，y ) ，a ，b 0 ( 2 1 8 ) 由式( 2 1 7 ) 和式( 2 1 8 可知，核函数满足加法和乘法的封闭性，这样可以根据 简单的核函数构造复杂的核函数。 2 常用核函数 下面只比较目前常用四种核函数： x f x ，y ) = x y( 2 19 ) x ( x ，少) = b y + 1 ) v( 2 2 0 ) k ( x ，y ) = e x p ( 一i ix y1 1 2 2 0 - 2 )( 2 2 1 ) k 【x ，y ) = t a n h ( b ( x y ) 一c )( 2 2 2 ) 其中，式( 2 1 9 ) 是线性核函数，可以用来解决比较简单的分类问题。；式( 2 2 0 ) 为多项式核函数；式( 2 2 1 ) 为径向基核函数( r b f ) ，事实上，当满足一定条件时， r b f 核函数的一种特例就是线性核函数；式( 2 2 2 ) 为s i g m o i d 核函数，这个算法的优 点是不存在局部极小点的问题。 2 1 5 参数选择方法 下面分别对常用交叉验证技术和网格搜索技术论述。 1 交叉验证 交叉验证在选定参数时，一般将样本集s 随机地分成k 个互不相交的子集，即 s ，s ：，瓯 s ，称为k 折。共进行k 次训练与测试，第i 次迭代的做法是，选择墨 作为测试集，那么训练集为墨，s h ，s 川，瓯，用s ，墨，s 川，瓯训练支持向量机， 然后对s ，进行测试。用，表示错误分类的样本点的个数，进行k 次测试后，可得到 ，：，气，用，表示所有错误分类数，k 用，表示样本集s 总数，那么l ，可以 看作支持向量轨错误率的一个估计，1 ，y ，称为交叉验证误差。 8 1 2 网格搜索 9 1 与随机搜索、遗传搜索相比，网格搜索是一种比较常用的数据搜索方法。对 于支持向量机分类器来说，需要确定的是算法中的惩罚因子c 和核函数中参数， 9 c 和y 作为网格搜索的范围，然后以固定的步长，顺着c 和y 两个参数的不同增长 方向生成网格，c 和y 参数对用网格中的节点表示。具体做法是将训练数据分成门 个大小相同的子集，先用其中刀一1 个子集作为训练样本得到一个判决函数，用它预 测那个没有参加训练的子集。这样循环进行n 次，直到所有的子集都作为测试样本 被预测一遍。取n 次预测所得准确率的平均值作为最终的准确率值。实验表明，按 照指数增长方式生成的网格是一种合理并且高效的搜索方法【1 6 】。例如照 c = 2 4 ，2 ，2 1 0 ，p = 2 ，2 。4 ，2 1 2 1 6s v m 改进算法 1 c s v m 算法 已知两类训练样本集x ，r d , f _ 1 ，即y ， 一1 ，+ 1 ) ，通过选择核函数和参数 c ，就相当于求解下面问题： m 口i n 丢喜荟口，口崩乃k c 即x ，一再i 口， 窆肛，：o 2 0 口，c ，i = l ， 得到一个最好解口。= ( 口i ，口；，口：) 7 ，在口选取的一个分量0 口； c ，算出阈 丹 r 。 1 值6 + = 只一y ，a t k ( x ，x j ) ，构造分类函数厂( x ) = s g n t a , y j k ( x 。x ) + 6 。 j = l lj e ij 其中，c 为正则化因子，是一个可调节的参数，c 的值越大，对错误样本的 分类的惩罚越大。 2 v - s v m 算法 对于c s v m 算法，正则化因子c 选择是困难的，所以选择新的参数v 代替c 控制v - s v m 中支持向量的个数。已知两类训练样本集r d , f - l ，y ， - 1 ，+ 1 ) ， 通过选择核函数和参数c ，就相当于求解下面问题： 3 4 胛i m i z e 1 1w 1 1 2 一叩+ 寺善f ， s 1 y ，( w x ，) + b ) p f ，f ，o ，p 0 ， f = 1 ，l ( 2 2 4 ) 使用l a g r a n g e 函数相当于求解下面问题： l o m 口i n 三圭1 = 1 ；1 叩朋m ，一， 判别函数就变为： r 疗、 厂( x ) = s g n 口，y ，k ( 即x ) + 6 ( 2 2 6 ) lp lj v - s v m 中的参数v 涉及到被y = s g n ( w x + b ) 分错的点和支持向量的问题。用v 代替c 的主要优点是省去了数值计算的麻烦和控制支持向量的个数及误差只用一 个参数v 就可以表示。 3 其它改进算法 c s v m 算法另一种变形是b s v m ( b o u n d e ds v m ) 算法，b s v m 的不同c s v m 在 于在目标函数中加入6 2 2 项，而约束条件少一项y ，= o 等式约束，变为边界约 束条件下的二次规则问题，适合迭代求解【1 7 】。模粝支持向量机f s v m ( f u z z ys v m ) 算法中把一个模糊隶属度值给每一个训练样本，使得样本与样本对判别函数的分 类有不同的贡献，可以达到很好的分类效果【- 。】。 2 2 粗糙集理论 2 2 1 粗糙集理论简介 粗糙集理论是一种处理模糊和不确定性知识的数学工具【侈】。其主要思想是在 保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。1 9 8 2 年，粗糙集理论被波兰数学家z p a w l a k 提出，他把这些无法确认的个体都归属于“边 界线区域”( b o u n d a r yr e g i o n ) 思想，将这种边界线区域定义为上近似集和下近似集 之差集 2 0 】。由于上近似集和下近似集都可通过等价关系给出确定的数学公式描述， 因此不确定元素数目可以被计算出。粗糙集理论是将知识与分类联系在一起，知 识被认为是一种对对象进行分类的能力，它在不可区分关系的基础上引入上、下 近似等概念来刻画知识的不确定性，度量属性的重要性和知识的依赖性，通过属 性约简过程完成不精确、不确定和不完备数据的分析与处理，从原始数据集中获 取规则和知识。由于粗糙集理论的这些固有的优点，目前，它在机器学习、数据 挖掘、决策分析、过程控制、模式识别与等领域中得到了广泛的应用】。 却 口 1一， ” 一 矿 ，一 i ； ( 3 ) 传递性：若 y , z ，则 ； 则0 是【，上的一个等价关系；元素je u 的等价类包含所有y u ，使得 。 对于v 曰，b a ，等价关系i n d ( b ) 可以描述为： j n d ( b ) = ( z ，t 。) u 2 v a b ，a ( x ) = a ( x ) )( 22 7 ) 称i n d ( b ) 为b 的不可区分关系。如果( x ，x ) = i n d ( b ) ，则。和x + 在b 中不u f 区分，口 的不可区分关系可以记【x k 。 3 上下近似集 粗糙集理论中的上下近似集算子可以用来描述不可定义集，它通过上下界逼 近来刻画，如图32 所示。 针对不可定义集，显然不可能构造一个公式来精确描述，只能通过上下界逼 近的方式来刻画，这就是粗糙集理论中的上下近似算子。可以用图32 表示。 厂、 t 【 l； u ：口+ 口+ 垦( y ) 可口+ 一 f p o s o ) = ( y ) - i q e g ( y ) = u f ( r ) ：口 l b r r d ( r ) = 百叮) 一里( y ) 口 图22e 下近似集 假设有信息系统s = ( u ，a ，矿，) ，设y u ，对b a ，x 关于占的下近似与上 近似分别可以描述为： 豇r ) = u 饵u bx y ( 22 8 ) b ( y ) = u x u bi 】，nx 矽) ( 2 2 9 ) 也可以通过集合形式来描述上近似集与下近似集为： 兰( y ) = y ui 【y 】b y ) ，( 2 3 0 ) b ( y ) = y ul 【y 】占ny ) 有了上近似集和下近似集，我们可以将论域空间分成正区域、负区域和边界 域三个区域。 对于信息系统s = ( u ，a ，v ，f ) ，x ，y ，b 为集合，】，u ，b 么，x 相对于b 的 正区域描述为： p o s 8 ( y ) = 垦( 】，) ( 2 31 ) 负区域描述为： n e g b ( 】，) = e o s ( - y ) = u b ( y ) ( 2 3 2 ) 边界域描述为： b n d 月( 】，) = b ( y ) 一旦( 1 ，) ( 2 3 3 ) 根据知识b 判断，烈y ) 是肯定能属于】，的u 中的元素组成的集合；百( y ) 是由 那些可能属于j ，的u 中的元素组成的集合；n e g 。( 】，) 是那些肯定不属于】，的u 中的 元素组成的集合；b n d r ( 】，) 是u 论域的不确定域，所包含的元素是根据知识b 既 不能判断肯定属于y 又不能判断肯定属于y ( 既u y ) 的u 中的元素组成的集合。 边界域的存在引起了粗糙集的不确定性。如果b n d 占( 1 ，) = ，则称集合】，关于 关系b 是清晰的；相反，如果b n d 8 ( 】，) ，则称集合】，关于关系b 粗糙的。集合】， 边界区域越大，其确定性程度就越小。因此粗糙集】，的不确定性程度可以用集合】， 的近似精度和粗糙度这两个概念来描述。集合】，上的关系b 近似精度描述为： 口8 ( 】，) 爿垦( y ) l ib ( r ) i ( 2 3 4 ) 其中l 】， 表示集合】，基数。 精度0 口8 ( 功1 来反映集合y 知识的已知程度。当口8 ( 】，) = 1 时，】，的b 边界域 为空集，集合】，为b 可定义的；当口r 1 时，最优化问题的l a g r a n g e 函数可以描述为： 3 1 1 w l l 2 - v 一，一，- + 喜r ，+ ；喜r ，+ 喜d ，r ，c w + 一c ，+ 6 ，一r ，一；t ，、 一且鼻+ 丑( 岛一成一) 一轨玉一l f l p r p 2 p 。 其中，l a g r a n g e 参数q 0