`
blueyanghualong
  • 浏览: 227628 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

one-versus-rest和one-versus-one的不同

 
阅读更多

SVM算法最初是为二值分类问题设计的,当处理多类问题时,就需要构造合适的多类分类器。

目前,构造SVM多类分类器的方法主要有两类:一类是直接法,直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单,但其计算复杂度比较高,实现起来比较困难,只适合用于小型问题中;另一类是间接法,主要是通过组合多个二分类器来实现多分类器的构造,常见的方法有one-against-oneone-against-all两种。

a.一对多法(one-versus-rest,简称1-v-r SVMs, OVR SVMs)。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类,这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

假如我有四类要划分(也就是4个Label),它们是A、B、C、D。于是我在抽取训练集的时候,分别抽取A所对应的向量作为正集,B,C,D所对应的向量作为负集;B所对应的向量作为正集,A,C,D所对应的向量作为负集;C所对应的向量作为正集, A,B,D所对应的向量作为负集;D所对应的向量作为正集,A,B,C所对应的向量作为负集,这四个训练集分别进行训练,然后的得到四个训练结果文件,在测试的时候,把对应的测试向量分别利用这四个训练结果文件进行测试,最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x).于是最终的结果便是这四个值中最大的一个。

p.s.: 这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased.因而不是很实用.

b.一对一法(one-versus-one,简称1-v-1 SVMs, OVO SVMs, pairwise)。其做法是在任意两类样本之间设计一个SVM,因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时,最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

投票是这样进行的.
A=B=C=D=0;
(A, B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
(A,C)-classifer 如果是A win,则A=A+1;otherwise, C=C+1;
...
(C,D)-classifer 如果是A win,则C=C+1;otherwise,D=D+1;
The decision is the Max(A,B,C,D)

p.s.: 这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的.

c.层次支持向量机(H-SVMs)。层次分类法首先将所有类别分成两个子类,再将子类进一步划分成两个次级子类,如此循环,直到得到一个单独的类别为止。

d.其他多类分类方法。除了以上几种方法外,还有有向无环图SVM(Directed Acyclic Graph SVMs,简称DAG-SVMs)和对类别进行二进制编码的纠错编码SVMs。

对c和d两种方法的详细说明可以参考论文《支持向量机在多类分类问题中的推广》(计算机工程与应用。2004)

最后,推荐两篇对多元分类策略的文章:A Comparison of Multiclass SVM MethodsA Comparison of Methods for Multi-class Support Vector Machines

分享到:
评论

相关推荐

    LIBSVM工具箱下载地址,LIBSVM-FarutoUitimate工具箱下载地址

    其中,一对多(one-versus-rest)法是训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类,这样 k 个类别的样本就构造出了 k 个 SVM。分类时将未知样本分类为具有最大分类函数值的那类。 一对一(one-...

    libsvm-2.84.rar_LibSVM_支持向量基

    4. **多分类支持**:通过一对多(one-versus-one)或一对多(one-versus-rest)策略实现多类分类。 5. **稀疏数据处理**:对于大型数据集,可以利用稀疏矩阵存储,有效减少内存占用。 6. **网格搜索**:自动进行参数...

    svm.rar_kernel matlab_svm 分类_核函数_核函数 支持向量机

    对于多类分类问题,SVM通常采用一对一(one-versus-one,OVO)或一对多(one-versus-rest,OVR)策略。在OVO策略中,对每一对类别,都会训练一个二分类SVM,最终的分类结果是所有二分类SVM预测的综合。OVR策略则为每...

    libSVM 3.22

    4. **多分类支持**:除了二分类,libSVM也支持多分类任务,如一对多(one-versus-one, OVO)和一对一(one-versus-rest, OVR)策略。 5. **高效训练**:采用优化算法如SMO(Sequential Minimal Optimization),在...

    支持向量机多类分类方法(pdf)

    一类对余类法(One-Versus-Rest, OVR) - **原理**:OVR 方法是最直观的多类扩展方式之一。对于一个含有 \(K\) 类别的分类任务,OVR 方法会构建 \(K\) 个二分类支持向量机模型,其中每个模型都将一个类别视为正类,...

    支持向量机多类分类方法

    1. **一对余类法(One-Versus-Rest, OVR)** - 在OVR方法中,每一个类别与其他所有类别的组合被视为一个二分类问题。例如,如果有C个类别,则会训练C个SVM模型,每个模型负责区分其中一个类别与其他所有类别。最终...

    svm多分类模块流程图

    2. **一对多(One-vs-All, OVA)**:也称为one-versus-rest,我们为每一个类别训练一个SVM,该SVM会将数据点分类到该类或其对立的“其余”类。在这个例子中,我们会训练9个SVM,每个针对一类。 流程图的描述似乎...

    机器学习简明原理(DOC47页).docx

    SVM 可以很好地解决二分类问题,对于多分类情况,可以使用 one-versus-rest 法解决。 SVM 的优点是可以解决线性不可分的情况,计算复杂度仅取决于少量支持向量,对于数据量大的数据集计算复杂度低。然而,SVM 也有...

    机器学习简明原理.docx

    但其缺点也明显,如不直接支持多分类任务,需要通过策略如one-versus-rest进行扩展,并且不适用于类别型数据,需要预先转换为数值形式。此外,SVM的优化问题通常通过拉格朗日对偶和序列最小优化(SMO)等方法解决,...

    管理信息化人工智能机器学习简明原理.pdf

    如 one-versus-rest 法,这种方法每次选择一个类别作为正样本,剩下其他类别作为负样本,假设一共有 3 个类别,这样相当于训练出了 3 个不同的 SVM。然后将测试数据分别带入 3 个 SVM 模型中,得到的 3 个结果中的...

    acpi控制笔记本风扇转速

    semaphore was inadvertently created with one unit instead of zero units. (BZ 464) Fiodor Suietov. Fixed a possible memory leak and fault in AcpiExResolveObjectToValue during a read from a buffer or ...

    世界上最快的VP9视频解码器

    TLDR (see rest of post for details): as a codec, VP9 is quite impressive – it beats x264 in many cases. However, the encoder is slow, very slow. At higher speed settings, the quality gain melts ...

    微软内部资料-SQL性能优化3

    In our example, if one transaction (T1) holds an exclusive lock at the table level, and another transaction (T2) holds an exclusive lock at the row level, each of the transactions believe they have ...

    基于OVR-CSP的情绪认知重评脑电信号晚正成分研究

    本文研究的核心是利用OVR-CSP(One Versus the Rest Common Spatial Patterns,一对其余共空间模式)算法来处理和分析情绪认知重评脑电图(EEG)信号的晚期正成分(LPP)。LPP是事件相关电位(ERP)的一个重要组成...

Global site tag (gtag.js) - Google Analytics