阅读(1069) 赞(1)

非线性可分离数据的SVM

2017-10-19 10:29:48 更新

目标

在本教程中，您将学习如何：

当不可能对训练数据进行线性分离时，定义SVM的优化问题。
如何配置参数以适应您的SVM的这一类问题。

动机

为什么要扩展SVM优化问题以处理非线性可分离的训练数据呢？在计算机视觉中使用SVM的大多数应用需要比简单的线性分类器更强大的工具。这源于事实，在这些任务中，训练数据很少使用超平面分离。

考虑这些任务之一，例如面部检测。在这种情况下的训练数据由一组图像组成，这些图像是面部和另一组图像，这些图像是非面部（世界上除了面部之外的其他事物）。该训练数据太复杂，以便找到每个样本（特征向量）的表示，可以使整个面的整个面线与整组非面线线性分离。

扩展优化问题

记住，使用SVM我们获得一个分离超平面。因此，由于训练数据现在是非线性可分的，所以我们必须承认，发现的超平面将错误分类某些样本。这种错误分类是必须考虑的优化中的一个新变量。新模式必须既包含找到提供最大利润的超平面的旧要求，又包括通过不允许太多分类错误正确地推广训练数据的新要求。

我们从制定找到最大化边距的超平面的优化问题开始，这在前面的教程（SVM简介）中有介绍：

SVM

可以通过多种方式修改此模型，以便考虑错误分类错误。例如，人们可以想到将训练数据中的错误分类错误的数量减少到相同的数量加一个常数，即：

SVM

然而，这不是一个很好的解决方案，因为在其他一些原因之中，我们不区分错误分类的样本与其适当的决策区域或不适合的决策区域的小距离。因此，更好的解决方案将考虑到错误分类样本与其正确决策区域的距离，即：

SVM

对于训练数据的每个样本，一个新的参数ξ被定义。这些参数中的每一个包含从其对应的训练样本到其正确决策区域的距离。下图显示了来自两个类别的非线性可分离训练数据，分离超平面以及与错误分类的样本的正确区域的距离。

SVM

注意: 图中只显示了错误分类的样品的距离。其余样本的距离为零，因为它们已经处于正确的决策区域。

图片上出现的红色和蓝色线条是每个决策区域的边距。认识到每一个ξ都是非常重要的一世从错误分类的培训样本到其适当地区的边缘。

最后，优化问题的新方法是：

SVM

如何选择参数C，很明显，这个问题的答案取决于如何分配培训数据。虽然没有一般答案，但考虑到这些规则是有用的：

C的大值给出具有较少错误分类错误但更小裕度的解决方案。考虑到在这种情况下，错误分类错误是很昂贵的。由于优化的目的是最小化参数，因此允许错误分类错误。
C的小值给出具有更大裕度和更多分类误差的解决方案。在这种情况下，最小化并不考虑这个总和的这个术语，所以它更侧重于找到一个具有大边距的超平面。

源代码

您还可以在samples/cpp/tutorial_code/ml/non_linear_svmsOpenCV源库的文件夹中找到源代码，或从这里下载。

注意: 以下代码已经通过OpenCV 3.0类和函数实现。可以在此页面中找到使用OpenCV 2.4的代码的等效版本。

#include <iostream>
#include <opencv2/core.hpp>
#include <opencv2/imgproc.hpp>
#include "opencv2/imgcodecs.hpp"
#include <opencv2/highgui.hpp>
#include <opencv2/ml.hpp>
#define NTRAINING_SAMPLES   100         // Number of training samples per class
#define FRAC_LINEAR_SEP     0.9f        // Fraction of samples which compose the linear separable part
using namespace cv;
using namespace cv::ml;
using namespace std;
static void help()
{
    cout<< "\n--------------------------------------------------------------------------" << endl
        << "This program shows Support Vector Machines for Non-Linearly Separable Data. " << endl
        << "Usage:"                                                               << endl
        << "./non_linear_svms" << endl
        << "--------------------------------------------------------------------------"   << endl
        << endl;
}
int main()
{
    help();
    // Data for visual representation
    const int WIDTH = 512, HEIGHT = 512;
    Mat I = Mat::zeros(HEIGHT, WIDTH, CV_8UC3);
    //--------------------- 1. Set up training data randomly ---------------------------------------
    Mat trainData(2*NTRAINING_SAMPLES, 2, CV_32FC1);
    Mat labels   (2*NTRAINING_SAMPLES, 1, CV_32SC1);
    RNG rng(100); // Random value generation class
    // Set up the linearly separable part of the training data
    int nLinearSamples = (int) (FRAC_LINEAR_SEP * NTRAINING_SAMPLES);
    // Generate random points for the class 1
    Mat trainClass = trainData.rowRange(0, nLinearSamples);
    // The x coordinate of the points is in [0, 0.4)
    Mat c = trainClass.colRange(0, 1);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(0.4 * WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
    // Generate random points for the class 2
    trainClass = trainData.rowRange(2*NTRAINING_SAMPLES-nLinearSamples, 2*NTRAINING_SAMPLES);
    // The x coordinate of the points is in [0.6, 1]
    c = trainClass.colRange(0 , 1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.6*WIDTH), Scalar(WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
    //------------------ Set up the non-linearly separable part of the training data ---------------
    // Generate random points for the classes 1 and 2
    trainClass = trainData.rowRange(  nLinearSamples, 2*NTRAINING_SAMPLES-nLinearSamples);
    // The x coordinate of the points is in [0.4, 0.6)
    c = trainClass.colRange(0,1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.4*WIDTH), Scalar(0.6*WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
    //------------------------- Set up the labels for the classes ---------------------------------
    labels.rowRange(                0,   NTRAINING_SAMPLES).setTo(1);  // Class 1
    labels.rowRange(NTRAINING_SAMPLES, 2*NTRAINING_SAMPLES).setTo(2);  // Class 2
    //------------------------ 2. Set up the support vector machines parameters --------------------
    //------------------------ 3. Train the svm ----------------------------------------------------
    cout << "Starting training process" << endl;
    Ptr<SVM> svm = SVM::create();
    svm->setType(SVM::C_SVC);
    svm->setC(0.1);
    svm->setKernel(SVM::LINEAR);
    svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, (int)1e7, 1e-6));
    svm->train(trainData, ROW_SAMPLE, labels);
    cout << "Finished training process" << endl;
    //------------------------ 4. Show the decision regions ----------------------------------------
    Vec3b green(0,100,0), blue (100,0,0);
    for (int i = 0; i < I.rows; ++i)
        for (int j = 0; j < I.cols; ++j)
        {
            Mat sampleMat = (Mat_<float>(1,2) << i, j);
            float response = svm->predict(sampleMat);
            if      (response == 1)    I.at<Vec3b>(j, i)  = green;
            else if (response == 2)    I.at<Vec3b>(j, i)  = blue;
        }
    //----------------------- 5. Show the training data --------------------------------------------
    int thick = -1;
    int lineType = 8;
    float px, py;
    // Class 1
    for (int i = 0; i < NTRAINING_SAMPLES; ++i)
    {
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point( (int) px,  (int) py ), 3, Scalar(0, 255, 0), thick, lineType);
    }
    // Class 2
    for (int i = NTRAINING_SAMPLES; i <2*NTRAINING_SAMPLES; ++i)
    {
        px = trainData.at<float>(i,0);
        py = trainData.at<float>(i,1);
        circle(I, Point( (int) px, (int) py ), 3, Scalar(255, 0, 0), thick, lineType);
    }
    //------------------------- 6. Show support vectors --------------------------------------------
    thick = 2;
    lineType  = 8;
    Mat sv = svm->getUncompressedSupportVectors();
    for (int i = 0; i < sv.rows; ++i)
    {
        const float* v = sv.ptr<float>(i);
        circle( I,  Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thick, lineType);
    }
    imwrite("result.png", I);                      // save the Image
    imshow("SVM for Non-Linear Training Data", I); // show it to the user
    waitKey(0);
}

说明

设置训练数据该练习的训练数据由属于两个不同类之一的一组标记的2D点形成。为了使运动更具吸引力，使用统一的概率密度函数（PDF）随机生成训练数据。我们将训练数据的生成分为两个主要部分。在第一部分中，我们为可分离的两个类生成数据。

    // Generate random points for the class 1
    Mat trainClass = trainData.rowRange(0, nLinearSamples);
    // The x coordinate of the points is in [0, 0.4)
    Mat c = trainClass.colRange(0, 1);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(0.4 * WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));
    // Generate random points for the class 2
    trainClass = trainData.rowRange(2*NTRAINING_SAMPLES-nLinearSamples, 2*NTRAINING_SAMPLES);
    // The x coordinate of the points is in [0.6, 1]
    c = trainClass.colRange(0 , 1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.6*WIDTH), Scalar(WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));

在第二部分，我们为不可线性分离的两个类创建数据，数据重叠。

    // Generate random points for the classes 1 and 2
    trainClass = trainData.rowRange(  nLinearSamples, 2*NTRAINING_SAMPLES-nLinearSamples);
    // The x coordinate of the points is in [0.4, 0.6)
    c = trainClass.colRange(0,1);
    rng.fill(c, RNG::UNIFORM, Scalar(0.4*WIDTH), Scalar(0.6*WIDTH));
    // The y coordinate of the points is in [0, 1)
    c = trainClass.colRange(1,2);
    rng.fill(c, RNG::UNIFORM, Scalar(1), Scalar(HEIGHT));

设置SVM的参数

注意: 在前面的教程“SVM简介”中，我们将对在训练SVM之前配置的cv :: ml :: SVM类的属性进行说明。

    Ptr<SVM> svm = SVM::create();
    svm->setType(SVM::C_SVC);
    svm->setC(0.1);
    svm->setKernel(SVM::LINEAR);
    svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, (int)1e7, 1e-6));

我们在这里做的配置与上一个教程（Support Vector Machines简介）中所做的配置之间只有两个区别，我们用作参考。

1、C我们在这里选择了这个参数的一个小值，以便不优化优化中的错误分类错误。这样做的想法源自于获得一个直观预期的解决方案的意愿。但是，我们建议通过调整此参数来更好地了解问题。

注意：在这种情况下，类之间的重叠区域中只有很少的点。通过给FRAC_LINEAR_SEP一个较小的值，可以增加点的密度，深入探索参数C的影响。

2、终止终止标准的算法。为了正确解决非线性可分离训练数据的问题，迭代次数的最大值必须大大增加。特别是我们这个价值增加了五个数量级。

训练SVM

我们称之为方法cv :: ml :: SVM :: train来构建SVM模型。请注意，培训过程可能需要相当长的时间。当你的程序运行时Have patiance。

    svm-> train（trainData，ROW_SAMPLE，labels）;

显示决策区域

方法cv :: ml :: SVM :: predict用于使用经过训练的SVM对输入样本进行分类。在这个例子中，我们使用这种方法来根据SVM所做的预测来对空间进行着色。换句话说，遍历图像将其像素解释为笛卡尔平面的点。每个点根据SVM预测的类别着色; 如果是带有标签1的课程，则为深绿色，如果是带有标签2的课程，则为深蓝色。

    Vec3b green(0,100,0), blue (100,0,0);
    for (int i = 0; i < I.rows; ++i)
        for (int j = 0; j < I.cols; ++j)
        {
            Mat sampleMat = (Mat_<float>(1,2) << i, j);
            float response = svm->predict(sampleMat);
            if      (response == 1)    I.at<Vec3b>(j, i)  = green;
            else if (response == 2)    I.at<Vec3b>(j, i)  = blue;
        }

Support vectors

我们在这里使用几种方法来获取有关Support vectors的信息。方法cv :: ml :: SVM :: getSupportVectors获取所有Support vectors。我们在这里使用这种方法来找到Support vectors的训练示例并突出显示。

    thick = 2;
    lineType  = 8;
    Mat sv = svm->getUncompressedSupportVectors();
    for (int i = 0; i < sv.rows; ++i)
    {
        const float* v = sv.ptr<float>(i);
        circle( I,  Point( (int) v[0], (int) v[1]), 6, Scalar(128, 128, 128), thick, lineType);
    }

结果

该代码打开一个图像并显示两个类的训练示例。一个类的点用浅绿色表示，浅蓝色用于另一个类。
SVM被训练并用于对图像的所有像素进行分类。这导致在蓝色区域和绿色区域中的图像的划分。两个区域之间的边界是分离超平面。由于训练数据是非线性可分的，可以看出，这两个类的一些例子被错误分类; 一些绿点位于蓝色区域，一些蓝点位于绿色区域。
最后，训练示例周围使用灰色戒指显示支持向量。

非线性可分离数据的SVM

← SVM简介

主成分分析（PCA）简介 →

非线性可分离数据的SVM

目标

动机

扩展优化问题

源代码

说明

结果

推荐文章

推荐教程

技术文章