基于多层聚类的多分类SVM快速学习方法
- 格式：pdf
- 大小：1.12 MB
- 文档页数：6
下载文档原格式
合集下载
SVM方法步骤
SVM 方法步骤彭海娟 2010-1-29看了一些文档和程序，大体总结出SVM 的步骤，了解了计算过程，再看相关文档就比较容易懂了。
1. 准备工作1) 确立分类器个数一般都事先确定分类器的个数，当然，如有必要，可在训练过程中增加分类器的个数。
分类器指的是将样本中分几个类型，比如我们从样本中需要识别出：车辆、行人、非车并非人，则分类器的个数是3。
分类器的个数用k2) 图像库建立SVM 方法需要建立一个比较大的样本集，也就是图像库，这个样本集不仅仅包括正样本，还需要有一定数量的负样本。
通常样本越多越好，但不是绝对的。
设样本数为S3) ROI 提取对所有样本中的可能包含目标的区域（比如车辆区域）手动或自动提取出来，此时包括正样本中的目标区域，也包括负样本中类似车辆特征的区域或者说干扰区域。
4) ROI 预处理包括背景去除，图像滤波，或者是边缘增强，二值化等预处理。
预处理的方法视特征的选取而定。
5) 特征向量确定描述一个目标，打算用什么特征，用几个特征，给出每个特征的标示方法以及总的特征数，也就是常说的特征向量的维数。
对于车辆识别，可用的特征如：车辆区域的灰度均值、灰度方差、对称性、信息熵、傅里叶描述子等等。
设特征向量的维数是L 。
6) 特征提取确定采取的特征向量之后，对样本集中所有经过预处理之后的ROI 区域进行特征提取，也就是说计算每个ROI 区域的所有特征值，并将其保存。
7) 特征向量的归一化常用的归一化方法是：先对相同的特征（每个特征向量分别归一化）进行排序，然后根据特征的最大值和最小值重新计算特征值。
8) 核的选定SVM 的构造主要依赖于核函数的选择，由于不适当的核函数可能会导致很差的分类结果，并且目前尚没有有效的学习使用何种核函数比较好，只能通过实验结果确定采用哪种核函数比较好。
训练的目标不同，核函数也会不同。
核函数其实就是采用什么样的模型描述样本中目标特征向量之间的关系。
如常用的核函数：Gauss 函数21),(21x x x p e x x k --=对样本的训练就是计算p 矩阵，然后得出描述目标的模板和代表元。
如何使用支持向量机进行多类别分类
如何使用支持向量机进行多类别分类支持向量机（Support Vector Machine，SVM）是一种常用的机器学习算法，广泛应用于分类和回归问题。
在分类问题中，SVM可以有效地处理二分类任务。
但在面对多类别分类问题时，需要采取一些特殊的策略来适应多类别情况。
本文将介绍如何使用支持向量机进行多类别分类。
1. 一对多（One-vs-Rest）策略一对多策略是最常用的多类别分类方法之一。
它将多类别问题转化为多个二分类问题。
对于有N个类别的问题，我们需要训练N个SVM模型，每个模型都将一个类别作为正例，其他类别作为负例。
在预测时，将样本输入到这N个模型中，选择输出概率最高的类别作为最终的分类结果。
这种策略的优点是简单易懂，容易实现。
同时，由于每个模型只需要区分一个类别和其他类别，相对于直接使用多类别分类模型，计算量较小。
然而，这种方法可能会出现类别不平衡的问题，即某些类别的样本数量较少，导致模型对这些类别的预测效果较差。
2. 一对一（One-vs-One）策略一对一策略是另一种常用的多类别分类方法。
它将多类别问题转化为多个二分类问题，每个二分类问题只涉及两个类别。
对于有N个类别的问题，我们需要训练N*(N-1)/2个SVM模型，每个模型都将两个类别作为正例和负例。
在预测时，将样本输入到这些模型中，通过投票或者加权投票的方式确定最终的分类结果。
相对于一对多策略，一对一策略的优点是可以避免类别不平衡的问题。
每个模型只需要区分两个类别，相对于直接使用多类别分类模型，计算量较小。
然而，这种方法的缺点是需要训练大量的模型，计算复杂度较高。
当类别数量较多时，训练时间和内存消耗可能会成为问题。
3. 多类别扩展除了以上介绍的一对多和一对一策略，还有一些其他方法可以用于多类别分类。
例如，多类别扩展方法将多类别问题转化为二分类问题，但是通过一些技巧将多个二分类模型组合起来。
常见的多类别扩展方法有Error-Correcting Output Codes （ECOC）和Directed Acyclic Graph（DAG）等。
SVM的原理和代码实现
SVM的原理和代码实现SVM（Support Vector Machine，支持向量机）是一种常用的机器学习算法，用于二分类和回归问题。
SVM的核心思想是找到一个最优的超平面，将不同类别的数据样本分开。
这个超平面由支持向量（样本）确定，使得支持向量到超平面的距离最大化。
本文将介绍SVM的原理及其代码实现。
一、SVM原理：1.线性可分情况：对于线性可分的数据集，SVM的目标是找到一个超平面，使得所有正例样本都位于超平面的一侧，负例样本都位于另一侧。
超平面的方程可以表示为：w^T*x+b=0，其中w是一个向量，表示法向量，b是偏置。
2.间隔最大化：SVM的关键是最大化两个不同类别样本之间的几何间隔。
间隔是沿着超平面的宽度，因此离分类超平面最近的实例点，即两个最靠近超平面的支持向量(x1和x2)，满足w^T*x1+b=1和w^T*x2+b=-1、它们满足w^T*(x1-x2)=2/(，w，)。
因此，SVM的优化问题转化为求解最大化2/(，w，)的最小化问题。
也就是求解以下优化问题：minimize ，w，^2/2，其中y_i*(w^T*x_i + b) >= 13.引入松弛变量：当数据不是完全线性可分时，引入松弛变量xi，使得一些样本可以处于错误的一侧。
此时优化问题转化为：minimize ，w，^2/2 + C*Σξ_i，其中y_i*(w^T*x_i + b) >= 1 - ξ_i，ξ_i >= 0。
C是一个超参数，用于控制错误样本的惩罚程度。
当C越大，对错误样本的惩罚越重；C越小，则对错误样本的惩罚越轻。
4.对偶问题：为了方便求解SVM的优化问题，引入拉格朗日乘子，将SVM的原始问题转化为对偶问题。
通过求解对偶问题，可以得到最优解。
对偶问题如下：maximize Σα_i - 1/2*ΣΣ α_i*α_j*y_i*y_j*x_i*x_j，其中Σα_i*y_i = 0，0 <= α_i <= C。
SVM的常用多分类算法概述
SVM的常用多分类算法概述SVM是一种经典的机器学习算法，常用于二分类问题。
然而，通过一些技巧和扩展，SVM也可以用于解决多分类问题。
本文将概述一些常用的SVM多分类算法。
1. One-vs-One (OvO) 方法：OvO 是一种常见的SVM多分类方法。
它的思想是，对于每对类别，训练一个二分类SVM模型。
然后，通过投票或者计算置信度来选择最终的分类结果。
这种方法的优点是分类器之间的训练数据更少，计算速度较快。
然而，对于有大量类别的问题，训练时间可能会很长。
2. One-vs-Rest (OvR) 方法：OvR 是另一种常见的SVM多分类方法。
它的思想是，对于每个类别，训练一个二分类SVM模型，该模型将该类别作为正例，将其他类别作为负例。
然后，通过比较这些二分类模型的置信度来选择最终的分类结果。
这种方法的优点是训练速度较快，特别适用于具有大量类别的问题。
然而，分类器之间的训练数据不平衡可能会导致结果不准确。
4. Directed Acyclic Graph (DAG) 方法：DAG 是一种基于有向无环图的SVM多分类方法。
它的思想是，将多类别问题转化为多个二分类子问题，并通过有向无环图连接这些子问题。
然后，通过在整个图上使用动态规划来选择最优路径，该路径对应于最终的分类结果。
这种方法的优点是可以处理复杂的类别关系和类别不平衡问题。
然而，构建和优化DAG可能比较困难。
5. Kernel Trick 方法：Kernel Trick 是一种将低维特征空间映射到高维特征空间的技术。
在多分类问题中，可以使用Kernel Trick来扩展SVM模型。
通过引入多个核函数或组合多个模型，可以构建更复杂的决策边界来处理多类别问题。
这种方法的优点是可以灵活地处理不同类型的数据和问题。
然而，选择合适的核函数和模型组合可能需要一定的经验和调试。
总之，SVM可以通过多种方法来解决多分类问题。
选择适当的方法取决于数据的特点和问题的复杂性。
使用支持向量机进行多分类问题的技巧(Ⅰ)
支持向量机(Support Vector Machine, SVM)是一种用于解决二分类和多分类问题的机器学习算法。
它在处理多分类问题时，有一些技巧和方法可以提高模型的性能和准确度。
首先，对于多分类问题，最常见的方法是使用一对一(OvO)和一对其余(OvR)的策略。
OvO策略是将每个类别之间的所有可能的组合进行训练，然后通过投票来确定最终分类结果。
OvR策略则是将每个类别分别与其他所有类别进行训练，然后选取得分最高的类别作为最终的分类结果。
在实际应用中，通常OvR策略更常用，因为它的计算复杂度更低。
其次，对于SVM模型的参数选择也是非常重要的。
在处理多分类问题时，需要选择合适的核函数和惩罚系数。
常用的核函数包括线性核函数、多项式核函数和高斯核函数。
选取合适的核函数可以帮助提高模型的分类性能。
而惩罚系数则是用来控制模型的复杂度，过大或者过小的惩罚系数都会影响模型的泛化能力，因此需要进行合理的选择。
另外，特征工程在多分类问题中也是非常重要的一步。
合适的特征工程可以帮助提高模型的性能。
对于SVM模型来说，常用的特征工程包括特征选择、特征变换和特征组合。
这些方法可以帮助提取出更加有用的特征，从而提高模型的分类准确度。
此外，在处理不平衡数据集时，需要考虑使用合适的方法来处理。
在多分类问题中，很可能会出现类别之间的样本数量不平衡的情况。
对于这种情况，可以采用过采样或者欠采样的方法来平衡样本数量，从而提高模型的性能。
另外，交叉验证也是非常重要的一步。
在处理多分类问题时，需要使用合适的交叉验证方法来评估模型的性能。
常用的交叉验证方法包括K折交叉验证、留一交叉验证和自助法。
合适的交叉验证方法可以帮助评估模型的性能，选择合适的参数和核函数。
最后，在模型训练和评估过程中，需要注意避免过拟合和欠拟合的情况。
可以使用正则化方法来避免过拟合，选择合适的模型复杂度可以避免欠拟合的情况。
对于SVM模型来说，需要注意选择合适的惩罚系数和核函数，以及进行合适的特征工程和交叉验证方法，来避免过拟合和欠拟合的情况。
SVM的常用多分类算法概述
SVM的常用多分类算法概述摘要：SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能，是一种非线性分类器。
最初SVM是用以解决两类分类问题，不能直接用于多类分类，当前已经有许多算法将SVM推广到多类分类问题，其中最常用两类：OAA和OAO算法，本文主要介绍这两类常用的多分类算法。
关键词：SVM；多分类；最优化自从90年代初V. Vapnik提出经典的支持向量机理论（SVM），由于其完整的理论框架和在实际应用中取得的很多好的效果，在模式识别、函数逼近和概率密度估计领域受到了广泛的重视。
SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能。
SVM是一种非线性分类器。
它的基本思想是将输入空间中的样本通过某种非线性函数关系映射到一个特征空间中，使两类样本在此特征空间中线性可分，并寻找样本在此特征空间中的最优线性区分平面。
它的几个主要优点是可以解决小样本情况下的机器学习问题，提高泛化性能，解决高维问题、非线性问题，可以避免神经网络结构选择和局部极小点问题。
1. SVM方法若样本集Q={（x i，y i）|i=1,……,L}∈R d*{-1,+1}是线性可分的。
则存在分类超平面w T x+b=0,x∈R d对样本集Q中任一（x i，y i）都满足：在空间R d中样本x=（x1，…, x d）r到分类超平面的距离d=|w T*x+b|/||w||，其中||w||= .当存在x 使得w T x i+b=±1, 则图1中超平面的分类间隔margin = 2/ ‖w ‖。
使分类间隔margin 最大的超平面即为最优分类超平面。
寻找最优分类超平面的问题将转化为求如下一个二次规划问题:minΦ( w) =1/2‖w ‖满足约束条件：y i ( w T x i + b) ≥1 , i = 1 ,2 , ⋯, L采用Lagrange 乘子转换为一个对偶问题,形式如下:满足约束条件:0≤a i，i=1,……,L ）其中a i为每一个样本对应的Lagrange 乘子, 根据Kuhn2Tucker 条件,这个优化的解必须满足:a i (y i [w T x i +b]-1)=0,i=1,……,L因此多数样本对应 a i将为0 ,少部分不为0 的a i对应的样本就是支持向量。
基于多实例学习的模型训练和预测加速方法
基于多实例学习的模型训练和预测加速方法多实例学习（Multiple Instance Learning, MIL）是一种特殊的机器学习方法，适用于训练数据以包（bag）的形式出现的情况。
在多实例学习中，训练数据被组织成一组袋子，每个袋子包含一个或多个实例。
而与传统的单实例学习不同，多实例学习中标签是以袋子为单位标注的。
这种特殊性使得多实例学习在一些领域具有广泛应用，比如目标检测、图像分类、文本分类等。
然而，由于每个袋子中包含不同数量和类型的实例，传统的机器学习算法无法直接应用于多实例问题。
为了解决这个问题，研究者们提出了许多基于多实例学习的模型和算法。
这些方法主要可以分为两类：基于转换（transformation-based）和基于判别（discriminative-based）。
基于转换的方法通过将每个袋子转换成单独的样本来解决多实例问题。
其中最常用的方法是将每个袋子中所有样本进行平均或求和操作得到一个代表性样本，并将其作为输入进行训练。
这种方法简单直观，但会丢失袋子内部实例的信息。
因此，研究者们提出了一些改进方法，如选择最具代表性的实例或使用聚类算法来提取袋子的特征。
这些方法在一定程度上改善了模型的性能，但仍存在一些问题，如对实例选择过于依赖或聚类算法对于复杂数据集的适应性不足。
基于判别的方法则直接对袋子进行建模，并通过学习一个判别函数来预测袋子的标签。
这种方法不需要对袋子进行转换，能够更好地利用袋子内部实例之间的关系。
最常用的基于判别的方法是使用支持向量机（Support Vector Machine, SVM）进行分类。
通过将每个袋子视为一个样本，并将每个样本标签视为一个类别，可以将多实例问题转化为传统单实例分类问题。
然而，在处理大规模数据集时，传统SVM 算法存在训练和预测速度慢且内存消耗大等问题。
针对上述问题，研究者们提出了一系列基于多实例学习模型训练和预测加速方法。
首先，在模型训练方面，研究者们提出了一些加速算法来减少训练时间和内存消耗。
如何使用支持向量机进行多标签分类问题解决
如何使用支持向量机进行多标签分类问题解决支持向量机（Support Vector Machine，SVM）是一种常用的机器学习算法，广泛应用于分类和回归问题。
在分类问题中，SVM能够有效地解决多标签分类问题，本文将介绍如何使用支持向量机进行多标签分类问题的解决。
一、多标签分类问题简介多标签分类问题是指一个样本可能同时属于多个类别的分类问题。
例如，对于一张包含猫、狗和鸟的图片，我们需要将其同时分类为“猫”、“狗”和“鸟”。
传统的分类算法通常只能处理单标签分类问题，无法应对多标签分类问题。
二、支持向量机的基本原理支持向量机是一种二分类模型，其基本原理是通过构建一个超平面，将不同类别的样本分开。
对于多标签分类问题，我们可以采用一对多（One-vs-Rest）的方法，将每个标签作为一个二分类问题进行处理。
三、数据预处理在使用支持向量机进行多标签分类问题解决之前，我们需要对数据进行预处理。
首先，需要将数据集划分为训练集和测试集。
其次，对数据进行特征提取和特征选择，以便提取出最能表征样本的特征。
四、特征编码在多标签分类问题中，标签通常是以二进制形式表示的，每个标签对应一个二进制位。
例如，对于三个标签的问题，可以用000、001、010、011等方式表示不同的标签组合。
因此，我们需要对标签进行编码，将其转化为二进制形式。
五、训练模型在训练模型之前，我们需要选择一个合适的核函数。
核函数在支持向量机中起到了非常重要的作用，能够将低维的特征映射到高维空间，从而使得样本更容易被分开。
常用的核函数包括线性核函数、多项式核函数和高斯核函数等。
六、模型评估在训练完成后，我们需要对模型进行评估。
常用的评估指标包括准确率、精确率、召回率和F1值等。
通过这些评估指标，我们可以了解模型的性能，并对其进行调优。
七、模型调优在使用支持向量机解决多标签分类问题时，我们可以通过调整参数来提高模型的性能。
常见的参数包括正则化参数C、核函数参数gamma等。
svm聚类原理
svm聚类原理
SVM（支持向量机）是一种常用的机器学习算法，主要用于分类问题。
虽然SVM本身并不是一种聚类算法，但可以通过一些技巧将其应用于聚类分析。
这种方法被称为基于SVM的聚类（SVM-based clustering）。
基于SVM的聚类方法基于以下原理：
1. 支持向量：SVM的核心思想是找到能够最好地将不同类别的样本分隔开的超平面。
在这个过程中，SVM识别出一些重要的样本，称为支持向量。
这些支持向量位于不同类别之间的边界上，它们的位置和数量对分类结果起着关键作用。
2. 核函数：SVM通过将数据映射到高维特征空间来处理非线性问题。
核函数是一种数学函数，它可以计算两个样本之间在高维特征空间中的相似度。
常用的核函数有线性核、多项式核和径向基函数（RBF）核等。
基于这些原理，可以将SVM应用于聚类分析的方法如下：
1. 数据转换：将原始数据转换为高维特征空间，可以使用线性或非线性的核函数进行转换。
2. 超平面划分：在高维特征空间中，通过SVM寻找一个超平面，将样本分隔开。
3. 支持向量聚类：基于找到的超平面和支持向量，将样本进行聚类。
根据样本与超平面的距离或相似度，可以将样本分配到不同的聚类簇中。
4. 聚类评估：根据聚类结果，可以使用一些评估指标（如轮廓系数、DB指数等）来评估聚类的质量。
需要注意的是，基于SVM的聚类方法在处理大规模数据时可能会面临计算复杂度高的问题。
此外，SVM本身更适合于二分类问题，而在多类别聚类中需要进行适当的修改和扩展。
因此，在选择聚类方法时，还需要考虑数据特征和问题的性质，以确定最合适的算法。
svm 原理
svm 原理
SVM(支持向量机)是一种用于分类和回归分析的机器学习方法，其基本原理是寻找一个最优的超平面（在二维情况下是一条直线，多维情况下是一个高维平面），将不同类别的样本点有效地分开。
其思想是将样本点映射到高维空间中，使得样本点在高维空间中可以线性可分。
SVM的目标是找到一个最优的超平面，使得最靠近超平面的
样本点到该超平面的距离最大。
这些最靠近超平面的样本点被称为支持向量，因为它们对于决策超平面的位置起到了关键作用。
SVM通过最大化支持向量到决策边界的间隔，使得分类
边界更加稳健。
在学习阶段，SVM通过构建一个约束最优化问题来寻找最优
的超平面。
这个问题的目标是最小化模型误差和最大化间隔。
其中，模型误差基于不同类别样本点到超平面的距离计算，间隔则是支持向量到超平面的距离。
通过求解这个优化问题，可以得到一个优秀的分类超平面。
SVM的优点是可以处理高维度的数据和非线性的决策边界。
它在解决小样本、非线性和高维度的分类问题上表现出色。
然而，SVM也有一些缺点，例如对于大规模数据集的训练需要
较长的时间，并且对于噪声和异常值比较敏感。
总结来说，SVM基于找到一个最优的超平面，通过最大化支
持向量到决策边界的间隔来实现分类。
它是一种非常强大的机器学习方法，在不同领域的分类和回归问题中都有广泛的应用。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2017年2月计算机工程与设计 Feb. 2017第 38 卷第 2 期COMPUTER ENGINEERING AND DESIGN Vol. 38 No. 2基于多层聚类的多分类S V M快速学习方法张春艳，倪世宏，张鹏，查翔(空军工程大学航空航天工程学院，陕西西安710038)摘要：针对S V M大规模多类样本学习效率较低的问题，提出一种基于多层聚类的多分类S V M快速学习方法。
采用自下 而上的方式构建二叉树层次结构，#•据所得层次结构，对每个节点对应的样本进行学习。
学习时对训练样本进行首次聚类 得到若干类簇，对其中只有一类样本的类簇提取中心点；对有两类样本的类簇，根据其混合度，对其正负类样本设定不同 的聚类数，进行二次聚类，提取所得类簇中心点。
整合上述步骤中提取的中心点作为约简后的样本，学习并得到子分类 器。
仿真结果表明，基于多层聚类的多分类S V M快速学习方法能够在保证较高分类准确率的前提下，大幅约简训练样本, 有效提高学习效率。
关键词：支持向量机；大规模训练集；多分类；多层聚类；二叉树中图法分类号：TP181 文献标识号：A文章编号：1000-7024 (2017) 02-0522-06doi：10. 16208/j. is s n l000-7024. 2017. 02. 045Multi-classification SVM multi-clustering fast learning methodZHANG Chun-yan, NI Shi-hong, ZHANG Peng, ZHA Xiang(C ollege o f A eronautics and A stro n a u tics E n gineering, A ir Force E ngineering U n iv e rs ity, X i’an 710038，C hina) Abstract：A m u lti-cla ssifica tio n S V M fast learning m ethod based on m u lti-c lu s te rin g was presented to solve its lo w learning e fficiency problem when using S V M processing large scale m ulti-class samples. B ottom-up m ethod was used to set up b in a ry tree h ierarchy s tru c tu re, according to achieved hierarchy s tru c tu re, sub-classifier le a rn t fro m corresponding samples o f each node. D u ring the learning process? several class clusters were generated after the fir s t clustering o f the tra in in g samples. C entral points were extracted fro m those class clusters w h ich ju s t had one type o f samples. F o r those w h ich had tw o types o f samples? cluster num bers o f th e ir positive and negative samples were set respectively according to th e ir m ix tu re degree, secondary clustering was undertaken afterw ards. Central points were extracted from achieved sub-class clusters. By learning from the reduced samples formed by the integration of extracted central points above, sub-classifiers were obtained Simulation results show th a t, this fast learning method can guarantee higher classification accuracy, greatly reduce sample numbers and effectively improve learning efficiency. Keywords：S V M；large scale tra in in g s e t；m u lti-c la s s ific a tio n；m u lti-c lu s te rin g；b in a ry-tre e〇引言单个支持向量机（S V M)只能解决二分类问题，对于 多分类，需要将多个分类器进行组合以实现多类可分。
国内外学者对多分类进行了诸多研究，基本算法有“一对 一”、“一对多”[1]，以及在这两种类型上的改进算法，其中 基于二叉树的S V M多分类法[2_4]是目前解决多类识别问题 方法中效果比较好的一种，采用二叉树构建方法解决了多 分类S V M向二分类S V M的转换问题，但仍有一个问题不 能回避，目卩：在实现S V M多分类时，若训练集规模较大,则S V M学习速度会非常缓慢，甚至会因内存过小而导致程 序难以执行。
为了提高S V M的学习速度，研究人员做了大量的工 作：①在不改变训练集规模的前提下，通过减小二次规划 中子问题的求解规模，来减少学习时间。
如王越的CS- M O®。
②预选取支持向量约简训练样本集。
例如，文献[6]提出利用边缘样本检测技术来提取潜在支持向量，移 除远离分类边界的样本，从而达到缩减训练样本提高训练 速度的目的。
文献[7]提出在训练每个子分类器时，用两 类交界处的相对边界向量来代替全部训练样本，减少训练收稿日期：2016-01-14;修订日期：2016-03-22作者简介：张春艳（1987-)，女，山东青岛人，硕士研究生，研究方向为飞机状态监控与健康管理；倪世宏（1963 -)，男，江苏南京人，教授，博士生导师，研究方向为飞机状态监控与健康管理；张鹏（1982-)，男，四川成都人，讲师，研究方向为飞机状态控与健康管理; 查翔（1988-)，男，山东新泰人，博士研究生，研究方向为飞机状态监控与健康管理。
E-mail: zhangchyl25@第38卷第2期张春艳，侃世宏，张鹏，等：基于多层聚类的多分类SVM快速学习方法•523 •样本数，缩短学习时间。
③构建多策略融合的多分类决策 树。
例如，文献[8]针对海量文本多分类问题，提出了 S V M决策树构建算法，可在一定程度上提升分类效果，同时大幅度减少学习和测试时间。
文献[9]提出了基于粒分 布的支持向量机加速学习方法，最大限度地降低分类器泛 化能力的损耗。
文献[10]中，将局部类簾考虑在内，提出了一*种基 于有效相对距离矩阵的自下而上二叉树构建方法，依照此 方法学习得到的多分类器，具有较快的学习速度以及分类 速度。
受文献[9]的启发，结合文献[10]中自下而上的 二叉树构建方法，提出一种多分类S V M快速学习方法，通 过约简训练样本，在保证分类准确率不显著下降的基础上，提高多分类S V M的学习速度。
1二叉树SVM层次结构设计二叉树S V M多分类与其它多分类方法相比，对于N 分类问题，学习阶段所需要构造的分类器数目最少，在对 样本进行测试时，不需要遍历所有分类器，不会出现一个 测试样本同时属于多个类的情况，也不会出现一个测试样 本没有类别归属的情况。
构造二叉树层次结构主要包括两 部分：有效相对距离矩阵的构建以及利用有效相对距离矩 阵进行二叉树层次结构设计。
1.1有效相对距离矩阵的构建二叉树S V M层次结构使用相对距离来衡量两类样本之 间的混叠程度，相对距离由两个指标确定[1°]:两个类中心之间的绝对距离，以及两类在空间中的分布范围。
设对于 包含N个类别的样本，q为第z类样本的中心，力是第z类 的样本，每两个类别之间的相对距离定义如下：=R^R (D,,6 [0，°°))，其中，4 =||q —c；I I 表示第 z•类和第7类样本中心的欧式距离，R为每类样本的最小超球半 径：兄=m a x{||q —x」|}。
构建有效相对距离矩阵的步骤如下：(1)计算每两类样本的相对距离，按照距离由小到大 排列，形成N X(N—1) /2行3列的相对距离矩阵A，矩 阵前2列为类别，第3列为两类之间的相对距离。
⑵选择有效相对距离：判断A的秩是否大于0,若 大于〇,则表示矩阵中包含有效的类别对，选择第一行的两 个类别（即类别对），保存到有效相对距离矩阵中，并将较大的类别值赋值给m a x，较小的类别值赋值给m in，将A的后续所有行中与m a x相同的值改为m in，删除A中的第一行，并删除前两列中类别值相同的行。
重复上述 步骤，当矩阵的秩为〇,表示矩阵中类别对是无效的，则有 效相对距离选择结束。
1.2二叉树层次结构设计步骤在有效相对距离矩阵形成之后，依据以下步骤进行二叉树层次结构的设计。
步骤1从有效相对距离矩阵中选择第一行的两个类别，将两者结合生成一个新的非叶子结点，设定左右 支，保存新的非叶子结点及左右支节点信息。
步骤2判断第二行的两个类别，若两类别在之前已有 的节点中没有出现过，则将此两类别结合成一个新的非叶 子节点；若只有一个类别在之前的节点中出现过，则将已 经出现过的类别所在的节点和没出现过的类别结合，得到 新的非叶子节点；若两个类别在之前得到的节点中都出现 过，则将两个类别各自所在的节点进行结合，得到新的非 叶子节点。
设定左右支，并保存新的非叶子节点及左右支 节点信息。
步骤3重复步骤2,直至最后一行。
二叉树层次结构 建造完毕。
下面以四分类的二叉树构造为例，阐述二叉树层次结 构的设计步骤。
设某个四分类问题中，类别为1，2, 3, 4,_120. 1_其有效相对距离矩阵为 3 4 0.2 ，则其二叉树-1 3 0. 5-层次结构设计步骤如下：步骤1从中选择第一行的两个类别1和2，令1与2结合形成l v2节点，左支为1，右支为2。