サポートベクトルマシン(SVM)の紹介

18151 ワード

SVM サポートベクトルマシン

変換元:
http://www.opencv.org.cn/opencvdoc/2.3.2/html/doc/tutorials/ml/introduction_to_svm/introduction_to_svm.html
ターゲット
このドキュメントでは、次の問題について説明します.

OpenCV関数CvSVM::trainを使用してSVM分類器を訓練し、CvSVM::predictを使用して訓練結果をテストします.

サポートベクトルマシン(SVM)とは?
サポートベクトルマシン(SVM)はクラス分類器であり、正式な定義は異なる種類のサンプルをサンプル空間で区切ることができる超平面である.言い換えれば、いくつかのタグ(label)の良い訓練サンプル(監督学習)が与えられ、SVMアルゴリズムは最適化された分離超平面を出力する.
どのようにして超平面が最適かどうかを定義しますか?次の点を考慮します.
2つのクラスに属する2次元の点をいくつか与えると仮定すると、これらの点は直線的に分割することができ、最適な分割線を見つけることができる.

Note
この例では,高次元のベクトルと超平面ではなく,カディル平面内の点と線を考慮した.この簡略化は,SVM概念の理解をより直感的に確立するためであるが,その基本原理は,より高い次元のサンプル分類の場合にも同様に適用できる.
上の図では、サンプルを分離できる可能性のある複数の直線を直感的に観察することができます.それはある直線が他の直線より適切ではないでしょうか.直感で直線の良し悪しを評価する基準を定義することができます.
試料に近すぎる直線は最適ではない.このような直線はノイズに対する感度が高く,汎化性が悪いからである.そのため、私たちの目標はすべての点から最も遠い直線を見つけることです.
これにより、SVMアルゴリズムの本質は、ある値を最大化できるスーパープレーンを見つけることであり、この値は、すべてのトレーニングサンプルからのスーパープレーンの最小距離である.この最小距離をSVM用語では間隔(margin)と呼ぶ.要約すると,最適分割超平面最大化訓練データの間隔である.

最適なスーパープレーンをどのように計算しますか?
次の式は、スーパープレーンの式を定義します.
$f(x) = \beta_{0} + \beta^{T} x,$
$\beta$ を重みベクトル、 $\beta_{0}$ をバイアス(bias)と呼ぶ.
See also
超平面に関するより詳細な説明は、T.Hastie,R.TibshiraniおよびJ.H.Friedmanの書籍Elements of Statical Learning,section 4.5(Seperating Hyperplanes)を参照することができる.
最適スーパープレーンは、任意のスケール $\beta$ および $\beta_{0}$ によって表現されることができる.最良の超平面を表現するには
$|\beta_{0} + \beta^{T} x| = 1$
式中の

は、超平面に最も近い点を表す.これらの点はサポートベクトル**と呼ばれます.このスーパープレーンは、**canonicalスーパープレーンとも呼ばれる.
幾何学の知識によって、点

から超平面 $(\beta, \beta_{0})$ までの距離は以下の通りであることが分かった.
特に、canonicalスーパープレーンの場合、式中の分子は1であるため、サポートベクトルからcanonicalスーパープレーンまでの距離は
$\mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}.$
先ほどは間隔(margin)を紹介しましたが、ここでは

と表示され、その値は最近の距離の2倍です.
$M = \frac{2}{||\beta||}$
最後に、最大化

は、追加の制約条件の下で関数 $L(\beta)$ を最小化するように変換される.制限条件は超平面がすべての訓練サンプル $x_{i}$ を正確に分類する条件を隠す.
式中 $y_{i}$ は、サンプルのカテゴリタグを示す.
これはラグランジュ最適化問題であり,最適超平面の重みベクトル $\beta$ とバイアス $\beta_{0}$ をラグランジュ乗数法により得ることができる.

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/ml/ml.hpp>

using namespace cv;

int main()
{
    // Data for visual representation
    int width = 512, height = 512;
    Mat image = Mat::zeros(height, width, CV_8UC3);

    // Set up training data
    float labels[4] = {1.0, -1.0, -1.0, -1.0};
    Mat labelsMat(3, 1, CV_32FC1, labels);

    float trainingData[4][2] = { {501, 10}, {255, 10}, {501, 255}, {10, 501} };
    Mat trainingDataMat(3, 2, CV_32FC1, trainingData);

    // Set up SVM's parameters
    CvSVMParams params;
    params.svm_type    = CvSVM::C_SVC;
    params.kernel_type = CvSVM::LINEAR;
    params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);

    // Train the SVM
    CvSVM SVM;
    SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);
    
    Vec3b green(0,255,0), blue (255,0,0);
    // Show the decision regions given by the SVM
    for (int i = 0; i < image.rows; ++i)
        for (int j = 0; j < image.cols; ++j)
        {
            Mat sampleMat = (Mat_<float>(1,2) << i,j);
            float response = SVM.predict(sampleMat);

            if (response == 1)
                image.at<Vec3b>(j, i)  = green;
            else if (response == -1) 
                 image.at<Vec3b>(j, i)  = blue;
        }

    // Show the training data
    int thickness = -1;
    int lineType = 8;
    circle( image, Point(501,  10), 5, Scalar(  0,   0,   0), thickness, lineType);
    circle( image, Point(255,  10), 5, Scalar(255, 255, 255), thickness, lineType);
    circle( image, Point(501, 255), 5, Scalar(255, 255, 255), thickness, lineType);
    circle( image, Point( 10, 501), 5, Scalar(255, 255, 255), thickness, lineType);

    // Show support vectors
    thickness = 2;
    lineType  = 8;
    int c     = SVM.get_support_vector_count();

    for (int i = 0; i < c; ++i)
    {
        const float* v = SVM.get_support_vector(i);
        circle( image,  Point( (int) v[0], (int) v[1]),   6,  Scalar(128, 128, 128), thickness, lineType);
    }

    imwrite("result.png", image);        // save the image 

    imshow("SVM Simple Example", image); // show it to the user
    waitKey(0);

}

説明する

訓練サンプル

を確立する
この例のトレーニングサンプルは、2つのカテゴリに属する2次元点からなり、1つのクラスは1つのサンプル点を含み、もう1つのクラスは3つの点を含む.

float labels[4] = {1.0, -1.0, -1.0, -1.0};
float trainingData[4][2] = {{501, 10}, {255, 10}, {501, 255}, {10, 501}};

関数CvSVM::trainは、floatタイプのMat構造にトレーニングデータを格納する必要があるため、次の行列を定義します.

Mat trainingDataMat(3, 2, CV_32FC1, trainingData);
Mat labelsMat      (3, 1, CV_32FC1, labels);

SVMパラメータを設定このチュートリアルでは、線形分割可能な2種類のトレーニングサンプルでSVMの基本原理を簡単に説明します.しかしながら、SVMの実際の応用状況は、より複雑である可能性がある(例えば、非線形分割データ問題、SVMコア関数の選択問題など).要するに、トレーニングの前にSVMにいくつかのパラメータを設定する必要があります.これらのパラメータはクラスCvSVMParamsに保存されます.

CvSVMParams params;
params.svm_type    = CvSVM::C_SVC;
params.kernel_type = CvSVM::LINEAR;
params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);

SVMタイプ.ここではCvSVM::C_を選択しましたSVCタイプであり、nクラス分類問題(n $\geq$ 2)に用いることができる.このパラメータはCvSVMParamsで定義.svm_type属性で.
Note
CvSVM::C_SVC型の重要な特徴は,非完全分類の問題(および訓練データの完全な線形分割が不可能)を扱うことである.この例では、この特徴の意味は大きくありません.私たちのデータは線形に分割できるので、ここで最もよく使用されるSVMタイプであるため、これを選択します.

SVMコアタイプ.本例の試料では核関数の議論は必要ないので,核関数を議論しなかった.しかしながら,訓練サンプルをより線形分割に有利なサンプルセットにマッピングすることを目的とするコア関数の背後にある主な考え方を簡単に述べる必要がある.マッピングの結果は,核関数によって達成される試料ベクトルの次元を増加させた.ここで選択したコア関数のタイプはCvSVM::LINEARはマッピングを必要としないことを示します.このパラメータはCvSVMParams.kernel_typeプロパティ定義.

アルゴリズム終了条件.SVMトレーニングのプロセスは,制約条件における二次最適化問題を反復的に解決することであり,ここではアルゴリズムが適切な条件下で計算を停止できるように最大反復回数と許容誤差を指定する.このパラメータはcvTermCriteria構造で定義される.

訓練はベクトルマシン呼び出し関数CvSVM::trainをサポートしてSVMモデルを構築する.

CvSVM SVM;
SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);

SVM領域分割

関数CvSVM::predictは、訓練済みのサポートベクトルマシンを再構築することによって、入力されたサンプルを分類します.この例では、この関数を使用してベクトル空間をシェーディングし、画像内の各ピクセルをカディル平面上の点として使用します.各点のシェーディングは、SVMの分類カテゴリに依存します.緑は1とマークされた点を表し、青は-1とマークされた点を表します.

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

サポートベクトルここでは、サポートベクトルの情報を取得するためにいくつかの関数が使用される.関数CvSVM::get_support_vector_count出力サポートベクトルの数、関数CvSVM::get_support_vectorは、入力されたサポートベクトルのインデックスに基づいて、指定された位置のサポートベクトルを取得する.この方法により,訓練サンプルのサポートベクトルを見つけ,それらを強調表示した.

int c     = SVM.get_support_vector_count();

for (int i = 0; i < c; ++i)
{
const float* v = SVM.get_support_vector(i); // get and then highlight with grayscale
circle(   image,  Point( (int) v[0], (int) v[1]),   6,  Scalar(128, 128, 128), thickness, lineType);
}

結果

プログラムは、訓練サンプルが表示され、1つのクラスが白い円で表示され、もう1つのクラスが黒い円で表示される画像を作成した.

訓練によりSVMが得られ、画像の各画素が分類される.分類の結果,画像を青緑の2つの部分に分け,中間線が最適分割超平面である.

は、最後に、灰色の枠線でベクトルを強調表示することをサポートする.

SSL証明書の期限取得

JavaScript-オブジェクト配列にオブジェクトが存在するかどうかを判断します(1次元/多次元配列判断)