非線性可分離數(shù)據(jù)的SVM

目標(biāo)

在本教程中，您將學(xué)習(xí)如何：

• 當(dāng)不可能對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行線性分離時(shí)，定義SVM的優(yōu)化問(wèn)題。
• 如何配置參數(shù)以適應(yīng)您的SVM的這一類(lèi)問(wèn)題。

動(dòng)機(jī)

為什么要擴(kuò)展SVM優(yōu)化問(wèn)題以處理非線性可分離的訓(xùn)練數(shù)據(jù)呢？在計(jì)算機(jī)視覺(jué)中使用SVM的大多數(shù)應(yīng)用需要比簡(jiǎn)單的線性分類(lèi)器更強(qiáng)大的工具。這源于事實(shí)，在這些任務(wù)中，訓(xùn)練數(shù)據(jù)很少使用超平面分離。

考慮這些任務(wù)之一，例如面部檢測(cè)。在這種情況下的訓(xùn)練數(shù)據(jù)由一組圖像組成，這些圖像是面部和另一組圖像，這些圖像是非面部（世界上除了面部之外的其他事物）。該訓(xùn)練數(shù)據(jù)太復(fù)雜，以便找到每個(gè)樣本（特征向量）的表示，可以使整個(gè)面的整個(gè)面線與整組非面線線性分離。

擴(kuò)展優(yōu)化問(wèn)題

記住，使用SVM我們獲得一個(gè)分離超平面。因此，由于訓(xùn)練數(shù)據(jù)現(xiàn)在是非線性可分的，所以我們必須承認(rèn)，發(fā)現(xiàn)的超平面將錯(cuò)誤分類(lèi)某些樣本。這種錯(cuò)誤分類(lèi)是必須考慮的優(yōu)化中的一個(gè)新變量。新模式必須既包含找到提供最大利潤(rùn)的超平面的舊要求，又包括通過(guò)不允許太多分類(lèi)錯(cuò)誤正確地推廣訓(xùn)練數(shù)據(jù)的新要求。

我們從制定找到最大化邊距的超平面的優(yōu)化問(wèn)題開(kāi)始，這在前面的教程（SVM簡(jiǎn)介）中有介紹：

可以通過(guò)多種方式修改此模型，以便考慮錯(cuò)誤分類(lèi)錯(cuò)誤。例如，人們可以想到將訓(xùn)練數(shù)據(jù)中的錯(cuò)誤分類(lèi)錯(cuò)誤的數(shù)量減少到相同的數(shù)量加一個(gè)常數(shù)，即：

然而，這不是一個(gè)很好的解決方案，因?yàn)樵谄渌恍┰蛑?，我們不區(qū)分錯(cuò)誤分類(lèi)的樣本與其適當(dāng)?shù)臎Q策區(qū)域或不適合的決策區(qū)域的小距離。因此，更好的解決方案將考慮到錯(cuò)誤分類(lèi)樣本與其正確決策區(qū)域的距離，即：

對(duì)于訓(xùn)練數(shù)據(jù)的每個(gè)樣本，一個(gè)新的參數(shù)ξ被定義。這些參數(shù)中的每一個(gè)包含從其對(duì)應(yīng)的訓(xùn)練樣本到其正確決策區(qū)域的距離。下圖顯示了來(lái)自?xún)蓚€(gè)類(lèi)別的非線性可分離訓(xùn)練數(shù)據(jù)，分離超平面以及與錯(cuò)誤分類(lèi)的樣本的正確區(qū)域的距離。

注意

圖中只顯示了錯(cuò)誤分類(lèi)的樣品的距離。其余樣本的距離為零，因?yàn)樗鼈円呀?jīng)處于正確的決策區(qū)域。

圖片上出現(xiàn)的紅色和藍(lán)色線條是每個(gè)決策區(qū)域的邊距。認(rèn)識(shí)到每一個(gè)ξ都是非常重要的一世 從錯(cuò)誤分類(lèi)的培訓(xùn)樣本到其適當(dāng)?shù)貐^(qū)的邊緣。

最后，優(yōu)化問(wèn)題的新方法是：

如何選擇參數(shù)C，很明顯，這個(gè)問(wèn)題的答案取決于如何分配培訓(xùn)數(shù)據(jù)。雖然沒(méi)有一般答案，但考慮到這些規(guī)則是有用的：

• C的大值給出具有較少錯(cuò)誤分類(lèi)錯(cuò)誤但更小裕度的解決方案。考慮到在這種情況下，錯(cuò)誤分類(lèi)錯(cuò)誤是很昂貴的。由于優(yōu)化的目的是最小化參數(shù)，因此允許錯(cuò)誤分類(lèi)錯(cuò)誤。
• C的小值給出具有更大裕度和更多分類(lèi)誤差的解決方案。在這種情況下，最小化并不考慮這個(gè)總和的這個(gè)術(shù)語(yǔ)，所以它更側(cè)重于找到一個(gè)具有大邊距的超平面。

源代碼

您還可以在samples/cpp/tutorial_code/ml/non_linear_svmsOpenCV源庫(kù)的文件夾中找到源代碼，或從這里下載。

注意

以下代碼已經(jīng)通過(guò)OpenCV 3.0類(lèi)和函數(shù)實(shí)現(xiàn)?？梢栽?a rel="external nofollow" target="_blank" rel="external nofollow" target="_blank" target="_blank">此頁(yè)面中找到使用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);
}

說(shuō)明

• 設(shè)置訓(xùn)練數(shù)據(jù)該練習(xí)的訓(xùn)練數(shù)據(jù)由屬于兩個(gè)不同類(lèi)之一的一組標(biāo)記的2D點(diǎn)形成。為了使運(yùn)動(dòng)更具吸引力，使用統(tǒng)一的概率密度函數(shù)（PDF）隨機(jī)生成訓(xùn)練數(shù)據(jù)。我們將訓(xùn)練數(shù)據(jù)的生成分為兩個(gè)主要部分。在第一部分中，我們?yōu)榭煞蛛x的兩個(gè)類(lèi)生成數(shù)據(jù)。
  

    // 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));

在第二部分，我們?yōu)椴豢删€性分離的兩個(gè)類(lèi)創(chuàng)建數(shù)據(jù)，數(shù)據(jù)重疊。

    // 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));

• 設(shè)置SVM的參數(shù)
  

注意

在前面的教程“SVM簡(jiǎn)介”中，我們將對(duì)在訓(xùn)練SVM之前配置的cv :: ml :: SVM類(lèi)的屬性進(jìn)行說(shuō)明。

    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));

我們?cè)谶@里做的配置與上一個(gè)教程（Support Vector Machines簡(jiǎn)介）中所做的配置之間只有兩個(gè)區(qū)別，我們用作參考。

    1、C我們?cè)谶@里選擇了這個(gè)參數(shù)的一個(gè)小值，以便不優(yōu)化優(yōu)化中的錯(cuò)誤分類(lèi)錯(cuò)誤。這樣做的想法源自于獲得一個(gè)直觀預(yù)期的解決方案的意愿。但是，我們建議通過(guò)調(diào)整此參數(shù)來(lái)更好地了解問(wèn)題。

注意：在這種情況下，類(lèi)之間的重疊區(qū)域中只有很少的點(diǎn)。通過(guò)給FRAC_LINEAR_SEP一個(gè)較小的值，可以增加點(diǎn)的密度，深入探索參數(shù)C的影響。

     2、終止終止標(biāo)準(zhǔn)的算法。為了正確解決非線性可分離訓(xùn)練數(shù)據(jù)的問(wèn)題，迭代次數(shù)的最大值必須大大增加。特別是我們這個(gè)價(jià)值增加了??五個(gè)數(shù)量級(jí)。

• 訓(xùn)練SVM
  

我們稱(chēng)之為方法cv :: ml :: SVM :: train來(lái)構(gòu)建SVM模型。請(qǐng)注意，培訓(xùn)過(guò)程可能需要相當(dāng)長(zhǎng)的時(shí)間。當(dāng)你的程序運(yùn)行時(shí)Have patiance。

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

• 顯示決策區(qū)域
  

方法cv :: ml :: SVM :: predict用于使用經(jīng)過(guò)訓(xùn)練的SVM對(duì)輸入樣本進(jìn)行分類(lèi)。在這個(gè)例子中，我們使用這種方法來(lái)根據(jù)SVM所做的預(yù)測(cè)來(lái)對(duì)空間進(jìn)行著色。換句話說(shuō)，遍歷圖像將其像素解釋為笛卡爾平面的點(diǎn)。每個(gè)點(diǎn)根據(jù)SVM預(yù)測(cè)的類(lèi)別著色; 如果是帶有標(biāo)簽1的課程，則為深綠色，如果是帶有標(biāo)簽2的課程，則為深藍(lán)色。

    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
  

我們?cè)谶@里使用幾種方法來(lái)獲取有關(guān)Support vectors的信息。方法cv :: ml :: SVM :: getSupportVectors獲取所有Support vectors。我們?cè)谶@里使用這種方法來(lái)找到Support vectors的訓(xùn)練示例并突出顯示。

    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);
    }

結(jié)果

• 該代碼打開(kāi)一個(gè)圖像并顯示兩個(gè)類(lèi)的訓(xùn)練示例。一個(gè)類(lèi)的點(diǎn)用淺綠色表示，淺藍(lán)色用于另一個(gè)類(lèi)。
• SVM被訓(xùn)練并用于對(duì)圖像的所有像素進(jìn)行分類(lèi)。這導(dǎo)致在藍(lán)色區(qū)域和綠色區(qū)域中的圖像的劃分。兩個(gè)區(qū)域之間的邊界是分離超平面。由于訓(xùn)練數(shù)據(jù)是非線性可分的，可以看出，這兩個(gè)類(lèi)的一些例子被錯(cuò)誤分類(lèi); 一些綠點(diǎn)位于藍(lán)色區(qū)域，一些藍(lán)點(diǎn)位于綠色區(qū)域。
• 最后，訓(xùn)練示例周?chē)褂没疑渲革@示支持向量。