（信号与信息处理专业论文）基于二叉树的lswsvm模型在早期火灾分类上的研究.pdf

汕头大学工学院 2010 届硕士学位论文 i 摘 要 火灾已成为我国常发性、破坏性和影响力最强的灾害之一，一旦发生将造成人员和财 产的巨大损失，因此开展对火灾的预警研究，具有非常重要的意义。为了及早的发现和控 制火灾的蔓延， 采用由气体传感器构成的电子鼻系统对火灾阴燃状态的信息进行采集， 并 对采集到的特征信息进行分析识别，从而实现对早期火灾类型的判别，并判断起火原因， 为有的放矢、 尽快扑灭火灾提供支持与帮助。 课题的研究在总结国内外早期火灾预警的基 础上，针对其不足之处，提出了基于二叉树的最小二乘小波支持向量机多类分类模型。通 过电子鼻传感器阵列采集早期火灾的气体信息， 采用主成分分析方法对火灾信息进行特征 提取， 最后通过多类分类模型对提取的特征信息进行识别， 实现了早期火灾的判别以及分 类，从而达到了火灾早期预警的目的。 本文首先介绍了支持向量机原理，以及最小二乘小波支持向量机的构造。其次，研究 了非线性映射方法，将其与二叉树结构、最小二乘小波支持向量机相结合，提出了基于二 叉树的最小二乘小波支持向量机模型。 针对早期火灾信息特征， 提出用主成分分析方法对 早期火灾信息进行特征提取。 最后， 将基于二叉树的最小二乘小波支持向量机模型应用于 早期火灾的分类实验，并与 bp 神经网络、k 近邻法和决策树方法进行比较，结果表明该 模型对早期火灾的识别率更高； 而采用小波核函数的最小二乘支持向量机比采用径向基核 函数的最小二乘支持向量机所需的训练时间和分类时间要少， 识别率更高； 基于平衡二叉 树的分类模型具有较高的训练速度和分类速度。 早期火灾的分类实验表明， 基于二叉树的 最小二乘小波支持向量机模型具有更好的识别效果和更快的分类速度， 更适合于早期火灾 分类上的应用。 关键词：早期火灾；二叉树；最小二乘小波支持向量机；多类分类；主成分分析 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 ii abstract fire has been one of the common destructive and most influencing disasters in our country, when fire happens, people will be hurt and treasure will be loss hugely. so it is very significant to study fire fore-warning. in order to discover fire earlier and control fire spreading, we use electronic nose combining with gas sensors to collect the fire information when fire is in smoldering situation. and then we recognize the characteristic information and achieve the goal of distinguishing the early fire classes, we estimate the cause of fire and it can help us to know how to put out the fire efficiently and quickly. this papers study is based on summarizing early fire fore-warning home and abroad. least squares wavelet support vector machine multi-class classification model based on binary tree was proposed to avoid the shortage of algorithm before. we use principal component analysis method to extract the feature of early fire information which was collected by electronic nose sensors array, at last the feature information was recognized by multi-class classification model, the distinguishing and classification of fire is come true, and then we achieve our purpose of fire early fore-warning. this paper first introduces the theory of support vector machine and how to structure least squares wavelet support vector machine. second, we study the method of nonlinear mapping and combine it with binary tree structure and least squares wavelet support vector machine, then least squares wavelet support vector machine model based on binary tree was proposed. to consider the characteristics of early fire information, principal component analysis method was proposed to extract the characteristics of early fire information. finally, least squares wavelet support vector machine model based on binary tree was used to the experiment of early fire classification, and compared with bp neural network, k-nearest neighbor algorithm and decision tree algorithm, the results show the model has higher recognition rate in the early fire classification. support vector machine using wavelet kernel function has lower training time, classification time and higher recognition rate compared with support vector machine using radial basis kernel function. the classification model based on balanced binary tree has higher training speed and classification speed. the early fire classification experiments show least squares wavelet support vector machine model based on binary tree has better recognition effect and faster classification speed; it is fitter for the application of early fire classification. 汕头大学工学院 2010 届硕士学位论文 iii key words: early fire; binary tree; least squares wavelet support vector machine; multi-class classification; principal component analysis 学位论文原创性声明 本论文是我个人在导师指导下进行的工作研究及取得的研究成果。论文 中除了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或 撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在论文中以 明确方式标明。本人完全意识到本声明的法律责任由本人承担。 作者签名： 日期： 年 月 日 学位论文使用授权声明 本人授权汕头大学保存本学位论文的电子和纸质文档， 允许论文被查阅和 借阅；学校可将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其它复制手段保存和汇编论文；学校可以向国家有关部 门或机构送交论文并授权其保存、借阅或上网公布本学位论文的全部或部分 内容。对于保密的论文，按照保密的有关规定和程序处理。 作者签名： 导师签名： 日期： 年 月 日 日期： 年 月 日 汕头大学工学院 2010 届硕士学位论文 1 第一章 绪 论 1.1 早期火灾预警的背景及其意义 火灾作为一种发生频率较高的灾害，受到国内外的普遍关注，它在任何时间、任何地 区都可能发生。火灾已成为我国常发性、破坏性和影响力最强的灾害之一1，一旦发生将 造成人员和财产的巨大损失，因此开展对早期火灾的预警研究，具有非常重要的意义。由 于现在高层楼宇建筑装饰采用了许多不同的材料， 发生火灾的类型也非常繁多， 所有火灾 而产生的气体构成也十分复杂， 在火灾早期阴燃阶段就已经产生大量气体， 利用火灾监测 电子鼻系统能迅速感知， 并识别阴燃气体的种类， 因而及早发现火灾类型， 判断起火原因， 对尽快扑灭火灾是非常重要的。 火灾预警可以归结为火灾各种状态空间的识别。一般来说，火灾的状态空间分为无火 状态、阴燃状态和火灾状态，实现火灾早期预警的实质是对火灾阴燃状态信息的识别。为 了实现对火灾准确的、早期的预报，必须严格识别火灾阴燃过程中产生的气体，而光电烟 感温复合式火灾探测器只有在火灾状态下才能实现预报，在无火、阴燃状态下，由于烟雾 浓度不大、温度上升不明显，实现不了预报。为了及早的发现和控制火灾的蔓延，采用由 气体传感器构成的电子鼻系统对火灾阴燃状态的信息进行采集， 并对采集到的特征信息进 行分析识别，从而实现对早期火灾类型的判别，并判断起火原因，为有的放矢、尽快扑灭 火灾提供支持与帮助2。 1.2 国内外早期火灾预警的发展动态 进行火灾的早期预警监测，一直是国内外众多研究者关注的热点。隶属于美国国家标 准和技术研究院(national institute of standards and technology, nist)的美国建筑与火灾研 究实验室(building and fire research laboratory，bfrl)一直在进行着火灾的早期预报研 究， 在火灾的现代测量与预测方法(advanced measurement and predictive methods， ampm) 领域开展了大量的研究； 中国科技大学的火灾科学国家重点实验室在范维澄院士主持下开 展了多项火灾早期预测的研究， 并取得了很多成果； 日本国立山口大学机械电子系的江钟 伟教授带领的研究小组近年来一直在开展火灾早期图像探测与定位、 火灾早期的多信息融 合感知与识别的研究， 国内外的其他大学及相关部门也在积极开展火灾的早期预警监测方 面的研究3。 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 2 特别是近年来，随着计算机技术、电子技术、信息技术、人工智能技术和网络技术的 发展， 我国火灾探测报警技术进入了快速发展阶段， 特别是和人工嗅觉系统相结合实现火 灾的早期预警监测。基于电子鼻的信息处理通常采用决策树、k 近邻法、神经网络、欧式 聚类分析法(eca)、偏最小二乘法(pls)等模式识别的方法，但它们普遍是基于线性的分 析方法，存在着实用性差、精度低等缺点。人工神经网络具有非线性映射能力，能够抑制 传感器的漂移与噪声， 并具有较高的预测精度， 但是人工神经网络采用经验风险最小化原 则(empirical risk minimization, erm)，虽然可以使训练误差最小，但由于过学习问题存 在，反而会导致学习机器泛化能力的下降。因此，经验风险最小并不一定代表实际风险最 小， 经验风险最小化原则在样本有限时并不合理。 而支持向量机4(support vector machine, svm)是根据统计学习理论提出的一种学习方法，是建立在统计学习理论的 vc 维理论和 结构最小化原则上的，是针对有限样本情况下的一种学习算法，它避免了局部极小点，并 能有效地解决过学习问题，因而近年来在人工嗅觉领域倍受重视。 1.3 本文的主要内容和章节安排 本文分五章，所做的主要工作如下： 第一章主要介绍早期火灾预警的研究背景、国内外的研究现状，最后引出本文的主要 工作内容。 第二章对 svm 的原理进行了深入的介绍，针对其不足之处，研究了最小二乘小波支 持向量机(least squares wavelet support vector machine, ls-wsvm)的基本原理以及数学 方法的实现。 第三章针对实际中的多类分类问题，把 ls-wsvm 的二值分类问题转换成多类分类问 题。介绍了非线性映射方法和二叉树结构，考虑样本的空间分布情况，并与 ls-wsvm 相结合，提出了基于二叉树的 ls-wsvm 多类分类模型，该模型的参数通过基于浮点数 编码的遗传算法进行优化选择。 第四章将基于二叉树的 ls-wsvm 多类分类模型应用于早期火灾的分类实验中，取得 了较好的识别效果和较快的分类速度， 实现了对早期火灾的多类分类， 从而达到了早期火 灾预警的目的。 第五章是全文工作的总结，提出一些有待进一步研究的方法。 汕头大学工学院 2010 届硕士学位论文 3 第二章 最小二乘小波支持向量机理论 人工神经网络进行非线性函数逼近的能力已经被证明并得到广泛的应用， 但神经网络 存在局部极小点问题，存在过学习问题，即用于训练的样本误差已达到很小甚至为零，但 网络系统对未来新的样本并不是总能达到好的预测效果。另外，神经网络的结构问题，如 如何选择隐层数和隐层节点数一般是凭经验确定， 并没有一个好的理论加以指导， 尤其当 用于训练的样本数较少时，预测精度更会受到影响。 svm 是 vapnik 等人根据统计学习理论提出的一种学习方法4，是建立在统计学习理 论的 vc 维理论和结构风险最小原理基础上的，避免了局部极小点，并能有效地解决过学 习问题， 根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷， 以期获得最 好的泛化能力5。svm 算法最终将转化为一个二次型寻优问题，得到的将是全局最优解， 能有效地解决神经网络方法中无法避免的局部极值问题，此外，svm 将实际问题通过非 线性变换转换到高维的特征空间， 在高维空间中构造线性判别函数来实现原空间中的非线 性判别函数， 在保证机器较好的泛化能力基础上巧妙地解决了维数问题， 其算法复杂度与 样本维数无关。svm 在解决小样本、非线性及高维模式识别问题中表现出的许多特有的 优势，使它成为一种优秀的机器学习算法。目前，svm 算法在模式识别、回归估计、概 率密度函数估计等方面都有应用， 例如， 在模式识别方面， 对于手写汉字识别、 语音识别、 人脸图像识别、文章分类等问题，svm 算法在识别精度上已经超过传统的学习算法或与 之不相上下。一些学者认为，svm 正成为继神经网络研究之后新的研究热点，并将推动 机器学习理论和技术的重大发展。 2.1 支持向量机原理 svm 是从线性可分情况下的最优分类面发展而来的， 基本思想如图 2-1 所示的二维两 类线性可分情况。图中，实心点和空心点分别代表两类样本，h为把两类没有错误地分 开的分类线，h1、h2分别为过各类中离分类线最近的样本且平行于分类线的直线，它们 之间的距离叫做两类的分类空隙或分类间隔(margin)。所谓最优分类线就是要求分类线不 但能将两类正确分开，而且使分类间隔最大。前者是保证经验风险最小，而分类间隔最大 实际上就是使推广性的界中的置信范围最小，从而使真实风险最小。推广到高维，最优分 类线就成为最优分类超平面。 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 4 h1 h h2 margin 图 2-1 支持向量机最优分类面 fig.2-1 support vector machine optimization classification plane 对线性可分的样本集 ii yx ,，1,in， d rx，1, 1y ，线性判别函数的一般 形式为 g xw xb，分类超平面方程6为： 0 w xb (2-1) 其中，w为分类超平面的法线，是可调的权值向量；b为偏置，决定相对原点的位置。将 判别函数进行归一化， 使两类所有样本都满足 1g x， 即使离分类超平面最近的样本的 1g x，则对于所有样本有： 1 i w xb，1 i y (2-2) 1 i w xb，1 i y (2-3) 从图 2-1 可知，超平面1 i w xb距离原点的垂直距离为 1b w ，而超平面 1 i w xb距离原点的垂直距离为 1 b w ，这样分类间隔就等于 11 2 bb w w ， 因此使间隔最大等价于使w（或 2 w）最小。若要求分类线对所有样本正确分类，则要 求它满足： 10 ii yw xb，1,in (2-4) 因此， 满足上述条件且使 2 w最小的分类超平面就是最优分类超平面。 上面的方法是在保 汕头大学工学院 2010 届硕士学位论文 5 证训练样本全部被正确分类， 即经验风险为 0 的前提下， 通过最大化分类间隔来获得最好 的推广性能。 但如果希望在经验风险和推广性能之间求得某种均衡， 可以通过引入正的松 弛因子 i 来允许错分样本的存在。这时，约束就变为： 10 iii yw xb ，1,in (2-5) 且使 1 1 2 n i i w wc 最小的分类面就是最优分类面，其中， 2 w起着最大化分类间隔的 作用， 1 n i i 起着最小化分类错误的作用，c为某个指定的常数，它实际上起控制对错分 样本惩罚的程度的作用，表示错分样本数与模型复杂度之间的折衷。c值越大，表示主要 把重点放在减少分类错误上，c值越小，表示主要把重点放在分离超平面，避免过学习问 题。 利用 lagrange 函数把上述最优分类面问题转化为其对偶问题7-8，即在条件： 1 0 n ii i y (2-6) 0 i c，1,in (2-7) 下对 i 求解下列函数的最大值： 1,1 1 2 nn iijijij ii j qy yx x (2-8) i 为 lagrange 乘子， 可以看出， 对偶问题完全是根据训练数据来表达的， 而且， 函数 q 的最大化仅依赖于输入模式点积的集合， 这是一个不等式约束下二次函数极值问题， 存在 唯一解。 依据 svm 的稀疏性特征， 解中只有一部分 i 不为零， 对应的样本就是支持向量。 解上述问题后得到的最优分类函数是： 1 sgn n iii i f xyx xb (2-9) 对于非线性问题，可以通过非线性映射把样本空间映射到一个高维空间，从而非线 性问题就转化为高维空间的线性问题， 在高维空间求最优分类面。 在高维空间构造最优超 平面时，训练算法仅使用空间中的点积，只要能找到一个函数,( ) ijij k x xxx满足 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 6 mercer 定理，那么这种内积运算就可以在原空间中实现，而不需知道映射函数的形式。 采用不同的内积核函数将导致不同的支持向量机算法， 目前最常用的内积核函数主要有以 下三类： 采用多项式形式的内积核函数： ,1 q ii k x xx x (2-10) 采用径向基核函数： 2 2 ,exp 2 i i xx k x x (2-11) 采用 s 形函数作为内积核函数： ,tanh ii k x xv x xc (2-12) 因此，在保证计算复杂度没有增加情况下，最优分类面中可以通过适当的内积函数 , ij k x x来实现非线性变换后的线性分类。在 svm 中，构造分类函数的复杂程度取决于 支持向量的个数，而不是特征空间的维数。在构造判别函数时，不是对输入空间的样本作 非线性变换， 然后在特征空间中求解， 而是在输入空间比较向量， 对结果再作非线性变换， 这样， 大量工作在输入空间而不是在高维空间中完成， 这一特点能有效地解决 “维数灾难” 问题。此时相应的分类函数变为： 1 sgn, n iii i f xy k x xb (2-13) svm 的基本思想可以概括为：首先通过非线性变换将输入空间变换到一个高维空间， 然后在这个高维空间中求取最优线性分类超平面，而这种非线性变换9是通过定义适当的 内积核函数来实现的。svm 求得的分类函数形式上类似于一个神经网络，其输出是若干 中间层节点的线性组合， 而每一个中间层节点对应于输入样本与一个支持向量的内积， 如 图 2-2 所示。 汕头大学工学院 2010 届硕士学位论文 7 x(1)x(2) x(s) k(x(1),x)k(x(2),x)k(x(s),x) a(1)y(1) a(2)y(2) a(s)y(s) y 输入向量x(1),x(2),x(s) 基于s个支持向量的非线性变换 权值 输出 图 2-2 支持向量机示意图 fig.2-2 support vector machine schematic diagram 2.2 小波理论和小波核函数 小波分析10-15作为时频分析方法中一种新的信号处理技术，是近年来迅速发展起来的 新学科， 被认为是傅里叶分析方法的突破性进展。 它具有对信号同时在时间域和频率域进 行表征的能力，小波变换可将信号分解成多个具有不同时间分辨率和频率分辨率的信号， 从而揭示信号在不同尺度上的时域行为特征， 小尺度的变换对于高频信号将有较好的时间 分辨率， 大尺度的变化对于低频信号有较高的频率分辨率， 从而反映信号从细节到大轮廓 的变化过程，因此，小波变换能根据高低频信号特点自适应的调整时频窗，有着“数学显 微镜” 的美称。 近年来，小波分析取得了飞速的发展并在信号分析、语音识别、电子对抗、 计算机识别、图像处理等许多领域中获得了广泛的应用。 信号分析的主要目的是寻找一种简单有效的信号变换方法， 使信号所包含的重要特征 能显示出来。在小波变换兴起之前，fourier 级数展开和 fourier 分析是刻画函数空间、求 解微分方程、进行数值计算的主要方法和有效的数学工具。fourier 变换是域变换，它把 时间域和频率域联系起来， 在时间域内难以观察的现象和规律， 在频率域往往能十分清楚 地显示出来。fourier 变换是作为平稳信号分析的最重要的工具。然而，在实际应用中， 所遇到的信号大多数并不是平稳的， 而是时变频率信号， 这时人们需要知道信号在突变时 刻所对应的频率成分，显然 fourier 变换的积分作用平滑了非平稳过程的突变成分，也就 是说，fourier 变换是整体刻画，只能反映信号的整体特征，而对信号的局部特征反映不 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 8 敏感，因此不能用于局部化时间-频率分析。为了克服 fourier 变换不能进行局部化时间- 频率分析，曾经出现过许多改进的方法，其中比较有成效的是 gobor 变换，它是一种有 效的信号分析方法，在非平稳信号的分析中起过很好的作用。但 gobor 变换的时间-频率 窗口大小固定不变，只适合分析所有特征尺度大致相同的各种过程，窗口没有自适应性， 不适合用于分析同时包含高频和低频信息的信号， 即不适合分析多尺度信号过程和突变过 程；另外，对于 gobor 变换来说，无论怎样离散化均不能使其成为一组正交基，即其离 散形式没有正交展开，难于实现高速算法。正因为如此，使 gobor 变换在理论分析和数 值计算方面都带来了很大困难，从而限制了其应用范围。 gobor 变换和时间-频率分析反映了信号分析处理过程中一个共同的基本要求，就是 具有自适应窗口特性和平移功能， 为了快速算法的需要， 对函数或信号进行变换处理的积 分核应属于正交函数族或正交基。归纳起来，变窗口、平移和正交性是作为信号分析最有 效的数学工具的主要条件。与 fourier 变换、gobor 变换相比，小波变换是时间和频率的 局域变换， 它能有效地从信号中提取信息， 通过伸缩和平移等运算功能对函数或信号进行 多尺度细化分析，另外小波变换通过适当的离散化，可以获得能与快速 fourier 变换相比 的快速算法，所以小波变换是时间-频率分析的一种有效工具。 对 21 ll，如果( ) x的 fourier 变换( ) 满足容许条件： 2 ( ) cd (2-14) 则称( ) x是一个基本小波或小波母函数，而称 1 2 , ( )() a c xc xa a ，,0,ar acr (2-15) 为由小波母函数( ) x生成的依赖于参数a和c的连续小波，其中a是尺度因子，c是平移 因子。 对于 2 ( )( )f xl r，其连续小波变换为： 1 2 ( , )( ) () f r xc wa caf xdx a (2-16) 其中，( )x是( ) x的复共轭函数。 小波变换是一种时频变换， 尺度参数a决定了() xc a 汕头大学工学院 2010 届硕士学位论文 9 的谱的变化， 即小波变换就是用具有相同形状、 不同带宽和主频的滤波器对信号进行滤波。 改变尺度参数a值，对函数( )x具有伸展(1a)或收缩(1a)的作用，对( ) 的作用正 好相反。所以改变尺度参数a，将影响对信号( )f x的时间分辨率和频率分辨率。改变平 移参数c值，则影响函数( )f x围绕c点的分析结果。0c，小波函数( )f x右移；0c， 小波函数( )f x左移。所以改变平移参数c，可以选取对信号( )f x进行分析的区域。 连续小波的反变换为： , 2 1 ( )( , )( ) fa c dadc f xw a cx ca (2-17) 小波变换的基本思想就是利用一簇小波的叠加实现任意函数( )f x的表示。 利用张量积 理论，可以得到一个d维的分离的小波函数的乘积： 12 1 ( )( ,)( ) d dddi i xx xxx (2-18) 设( ) x是一个母小波，a、c分别为伸缩、平移尺度因子，那么小波核函数为： 1 ( ,)() () d iiii i ii xcxc k aa x x， ,;, , ,;,0 d iiiiiiii rx x c c a ar a ax x (2-19) 本文选用 morlet 小波函数： 2 0 ( )cos()exp() 2 x xx， 0 是常数 (2-20) 来构造小波核函数，如下： 2 0 2 11 ( ,)()()cos()exp() 2 dd ii iiii ii iii xx xxxx kk aaa x xxx (2-21) 可以证明，morlet 小波核函数满足 mercer 条件16。 2.3 最小二乘小波支持向量机 svm 采用不等式约束条件的二次寻优算法是费时并且不易用于实时数据处理的，一 般只适用于离线批处理的工作方式，这种算法的复杂性限制了 svm 的应用范围。 ls-wsvm 是 svm 的改进17-22，一方面，它采用最小二乘线性系统，把 svm 算法中的不 等式约束转化为等式约束， 且将误差平方和损失函数作为训练集的经验损失， 从而将解二 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 10 次规划问题转化为求解线性方程组问题，大大提高了求解速度和收敛精度。另一方面，其 核函数采用小波核函数，小波核函数不仅是近似正交的，而且适用于信号的局部分析、信 噪分离和突变信号的检测，从而提高了支持向量机的泛化能力。 对于样本集 ii yx ,，1,in， d rx，ls-wsvm 的优化问题为： 在约束 t iii yxb w，1,in下 min 2 1 1c , 22 n i i ww w (2-22) 引入 lagrange 乘子法，得： t2t 11 11 ()c 22 nn iiiii ii lxby www (2-23) 根据 kkt 条件，把式(2-23)分别对w，b， i 和 i 求偏微分并令它们等于 0，得到： 1 ( ) n ii i x w (2-24) 1 0 n i i (2-25) 1 c ii (2-26) t ( ) iii yxb w (2-27) 由式(2-24)(2-27)得： t t 000 0000 00c0 0 b iw e ii eiy (x)(x) (x)(x) (2-28) 因此，得到： t t1 (1) (1) 00 c nn b e yei (x)(x)(x)(x) (2-29) 其 中 ， t 1 1, 1 n e， 1 ( ), () n xx (x)(x)， t 1, , n ， t 1, , n yyy， t 1 , n 。 式(2-29)为优化问题所对应的线性方程组，可求得 ，b，则决策函数为： 汕头大学工学院 2010 届硕士学位论文 11 1 ( )( , ) n ii i f xk x xb (2-30) 为了减少计算量和减少优化时间，把式(2-21)的小波核函数的伸缩因子 i a都用同一常 数 0 a代替，代入式(2-30)，可得 ls-wsvm 的决策函数为： 2 , , 0 2 11 00 ( )cos()exp() a2a dn i jj i jj i ij xxxx f xb (2-31) 其中， , i j x是第i个训练样本的第j个分量， j x是x的第j个分量，d是输入向量的维数。 通过式(2-31)可以得到 ls-wsvm 的分类函数为： 2 , , 0 2 11 00 ( )sgncos()exp() a2a dn i jj i jj i ij xxxx f xb (2-32) 2.4 本章小结 ls-wsvm 是标准 svm 的一种改进，它采用最小二乘线性系统和小波核函数，将解 二次规划问题转化为求解线性方程组问题， 不仅大大提高了求解速度和收敛精度， 而且提 高了泛化能力。但是在实际的分类应用中，往往遇到的是多类的分类问题，上述的 ls-wsvm 二值分类器仅仅是针对两类情况，因此，需要把两类分类问题转换成多类分类 问题。 通过非线性映射把样本投影到高维空间，可以充分考虑样本的空间分布情况，使容易 区分的类别首先分类出来，有效地克服了盲目分类和错分积累情况。此外，采用二叉树结 构，避免了不可分情况。因此本文把非线性映射、二叉树和 ls-wsvm 相结合，提出了 基于二叉树的 ls-wsvm 多类分类模型。下一章将介绍非线性映射方法和二叉树的构造。 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 12 第三章 基于二叉树的 ls-wsvm 多类分类模型 利用 svm 处理多类样本分类是 svm 研究的热点问题之一。 目前已提出的 svm 多类 分类方法可分为一次性求解法和分解重构法两类。1998 年 weston 等人23提出了一次性求 解法，它在所有训练样本上求解一个大型二次规划问题，同时将所有样本分开。但由于该 方法变量个数多，计算复杂度高，尤其是在类别数目多时，其训练速度低，分类精度也不 高，其实用性并不强。分解重构法是一种将多类分类问题转化为多个两类分类问题，并采 用某种策略将多个两类分类器组合起来实现多类分类的方法。 实验证明， 这是一种比一次 性求解法更适合于实际应用的方法24。 3.1 常用的 svm 多类分类方法 “一对多”方法25、 “一对一”方法26、有向无环图(directed acyclic graph，dag)27 分类算法、以及纠错编码方法28-29是最常用的四种采用分解重构法的 svm 多类分类方法， 但都存在一定的缺点。 “一对多” 方法把训练样本中的某一类样本和其他类的样本分解开来作为一个二类分 类问题，对于有k类的样本，需要训练k个分类器，得到k个最优超平面分类规则的指示 函数结果， 用每个分类器来预测测试样本， 取指示函数结果最大者为测试样本的所属类别。 这种方法的优点是，只需要训练k个两类分类支持向量机，故其所得到的分类函数的个数 较少，其分类速度相对较快。但该算法的缺点是：(1)每个分类器的训练都是将全部的样 本作为训练样本，这样需要求解k个n个变量的二次规划问题，因为每个支持向量机的训 练速度随着训练样本的数量的增加急剧减慢，因此，这种方法训练时间较长；(2)如果以 两类分类器的输出取符号函数， 则有可能存在测试样本同时属于多类或不属于任何一类的 区域。如果最后的输出是两类分类器输出为最大的那一类，则人为地将分类超平面偏转， 之所以发生这种情况是因为分类器的输出是一个相对距离，同一分类器的输出具有可比 性，而不同分类器由于其相对的标准不同，其输出不具有可比性。 “一对一”方法是由 knerr 提出24的，该算法把训练样本中的每两类作为一个二类分 类问题，对于k类样本，需要训练1 2kk个分类器，用每个分类器来预测测试样本， 得到1 2kk个预测结果， 根据结果对k类进行投票， 得票最多的为测试样本所属类别。 这种算法的缺点是：(1)生成的分类器模型太多，如果训练样本类别较多时则更严重，训 汕头大学工学院 2010 届硕士学位论文 13 练速度会较慢；(2)要对测试样本应用1 2kk个分类器，导致预测速度很慢；(3)由于 在决策时采用了投票法， 有可能存在多个类投票相同的情况， 即有可能存在一个样本同时 属于多个类的情况，而使得此方法无法进行很好的决策，结果就不可分。 dag 分类算法的训练阶段采用“一对一”svm 方法的任意两两组合训练方式，需要 构造1 2kk个分类器，但在分类过程中，dag 将所用子分类器构造成有向无环图， 如图 3-1 所示，具有1 2kk个内部节点以及k个叶子节点，每个内部节点都是一个两 类分类器，叶子节点为最终的类值。对未知测试样本，从根节点开始根据分类器的输出值 决定其走左侧或右侧路径，如此一直到叶子节点为止，得到样本所属的类值，只需1k步 就可完成分类。其优点是决策速度显著比“一对多”或“一对一”方法快。但该算法的缺 点是：(1)存在“一对一”方法的第一个缺点；(2)根节点的选择直接影响着分类的结果， 不同的分类器作为根节点可能产生不同的预测结果，从而产生分类结果的不确定性。 1vs5 2vs5 1vs4 2vs43vs51vs3 3vs42vs31vs24vs5 45321 2,3,4,51,2,3,4 3,4,51,2,3 图 3-1 dag 结构图 fig.3-1 dag structure diagram 纠错编码方法是 dietterich 等人28在 1995 年提出的对类别进行二进制编码将多类分类 问题转化为多个两类分类问题。对于k类分类问题，给每个类别赋予一个长度为l的二进 制编码，形成一个k行l列由 1 和 0 组成的一个码矩阵，设为 kl m，其中l为待训练的分 类器数， 当1 il m(0 il m)时表示该样本相对于第i类而言是作为正例 （负例） 来训练第l个 分类器 l f的。在测试过程中，对于样本x，计算l个分类器的输出向量与各类别向量的汉 明距离，使其距离最小的类即为x所属的类。该算法的训练速度较“一对多”方法有明显 基于二叉树的 ls-wsvm 模型在早期火灾分类上的研究 14 的改进，且当类别数大时仅需要少量的分类器，然而如何根据具体问题确定码本、选择排 列顺序以达到最优的分类性能依然有待研究，且其分类效果受错误码的相关性影响很大， 另外对类别超过 10 的大类问题效果不佳。 3.2 非线性映射方法 针对常用多类 svm 分类方法的缺点， 本文采用非线性映射方法30-33， 将样本投影到高 维空间，充分考虑样本的空间分布情况，使容易区分的类别首先分类出来，其与二叉树结 构相结合，不仅避免了不可分情况，而且有效地克服了盲目分类和错分积累情况。 对于训练样本 1 112 , n x xxx和 2 212 , n x xxx， 通过映射函数映射到高维空 间h，那么它们在空间h的欧几里德距离为： 2 1212111222 ,()()(,)2 (,)(,) h lkkkx xxxx xx xxx (3-1) 其中，(, )k 是核函数。 在空间h中， 1 m和 2 m分别为 1 x和 2 x的类中心， 1 1 1 1 1 ( ) n i i mx n ， 2 2 1 2 1 ( ) n i i mx n ， 那么 1 m与 2 m之间的距离为： 111222 12 22 111111 1122 121 ,( ,)( ,)( ,) nnnnnn h ijijij ijijij lm mk x xk x xk x x nnnn (3-2) 对于训练样本 12 , n x xx，训练样本x和类中心m在空间h的距离为： 2 111 21 ,( , )( ,)( ,) nnn h iij iij lx mk x xk x xk x x nn (3-3) 那么样本与类中心的距离的方差为： 1 1 ( ,) 1 n hh i i rlx m n (3-4) 因此，得到类i与j之间的可分性度量函数为： , (,) () h ijh i j hh ij lm m rr (3-5) 其中， 在高维空间h上， i m， j m分别是第i类和第j类的中心，, h ij lm m为第i类和第j 汕头大学工学院 2010 届硕士学位论文 15 类的类中心距离， h i r为第i类样本与 i m的距离方差， h j r为第j类样本与 j m的距离方差。 当 , 1 h i j 时，表明第i类和第j类没有相交区域。 , h i j 的值越大说明第i类和第j类的可分 性越强， , h i j 的值越小说明两类越相似。 在式(3-5)的可分性度量函数中，非线性映射核函数采用 morlet 小波核函数： 2 0 2 11 000 ( ,)()()cos()exp() aa2a dd ii iiii ii xx xxxx kk x xxx (3-6) 3.3 二叉树结构的构造 二叉树结构分类器可以把一个复杂的多类别问题转化为多个两类问题来解决。 一个多 类别分类问题转化为两类问题的形式是多种多样的， 对应的二叉树的结构也各不相同， 不 同的二叉树结构对分类精度有很大的影响。 二叉树方法34-38将所有类别分为两个子类，每个子类又划分为两个子子类，如此循环 下去，直到所有的节点只含有一个类别为止，每次划分后两类分类问题的规模逐级下降， 这样得到一个倒立的二叉