Search…

Giới Thiệu về Mô Hình SVM

04/11/20207 min read
Giới thiệu tổng quan mô hình SVM và sử dụng SVM trong OpenCV.

Bài viết giới thiệu tổng quan về mô hình SVM và ví dụ về SVM trong OpenCV.

SVM là gì?

SVM (Support Vector Machine) là 1 thuật toán học máy thuộc nhóm Supervised Learning (học có giám sát) được sử dụng trong các bài toán phân lớp dữ liệu (classification) hay hồi qui (Regression).

SVM là 1 thuật toán phân loại nhị phân, SVM nhận dữ liệu vào và phân loại chúng vào hai lớp khác nhau. Với 1 bộ các ví dụ luyện tập thuộc hai thể loại cho trước, thuật toán luyện tập SVM xây dựng 1 mô hình SVM để phân loại các ví dụ khác vào hai thể loại đó.

Ví dụ về SVM tuyến tính

Có 1 không gian có nhiều điểm và các kí hiệu như sau:

Svm separating hyperplanes
  • yi: là các lớp (bản lề) chứa các điểm dữ liệu xi, ví dụ này mang giá trị 1 và -1.
  • xi: là 1 vector thực nhiều chiều (p chiều). 
  • Nhiệm vụ là cần phải tìm 1 siêu phẳng (Optimal hyperplane) có lề lớn nhất chia tách các điểm dữ liệu có ban đầu để huấn luyện và các điểm sau này. Mỗi siêu phẳng (Optimal hyperplane) đều có thể được viết dưới dạng 1 tập các điểm thỏa mãn w.x-b = 0
Svm_max_sep_hyperplane_with_margin
  • w: là 1 vector pháp tuyến của siêu phẳng (optimal hyperplane).
  • b/||w||: xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo hướng vectơ pháp tuyến w.
  • Giả sử có tới 3 siêu phẳng (Optimal hyperplane) là H1 (Xanh dương), H2 (Đỏ), H3 (Xanh lá). H3 sẽ bị loại đầu tiên vì không thể phân loại các điểm huấn luyện cho trước. H1 bị loại vì khoảng cách từ các điểm Support Vector đến siêu phẳng (Optimal hyperplane) chưa phải là cực đại. H2 là siêu phẳng cần tìm. Lúc này các siêu phẳng đó được xác định: w.x - b = 1  và w.x - b = -1
  • Các điểm dữ liệu cho trước nằm trên các siêu phẳng song song được gọi là Support Vector.

Tổng quan:

  • SVM là mô hình xây dựng 1 siêu phẳng hoặc 1 tập hợp các siêu phẳng trong 1 không gian nhiều chiều hoặc vô hạn chiều, có thể được sử dụng cho phân loại, hồi quy, hoặc các nhiệm vụ khác. Để phân loại tốt nhất thì phải xác định siêu phẳng (Optimal hyperplane) nằm ở càng xa các điểm dữ liệu của tất cả các lớp (Hàm lề) càng tốt, vì nói chung lề càng lớn thì sai số tổng quát hóa của thuật toán phân loại càng bé.
  • Muốn các điểm dữ liệu có thể được chia tách 1 cách tuyến tính, thì bạn phải cần chọn hai siêu phẳng của lề sao cho không có điểm nào ở giữa chúng và khoảng cách giữa chúng là tối đa.
  • Trong nhiều trường hợp, không thể phân chia các lớp dữ liệu 1 cách tuyến tính trong 1 không gian ban đầu được dùng để mô tả 1 vấn đề. Vì vậy, nhiều khi cần phải ánh xạ các điểm dữ liệu trong không gian ban đầu vào 1 không gian mới nhiều chiều hơn, để việc phân tách chúng trở nên dễ dàng hơn trong không gian mới. 

Với các điểm tổng quan ở trên thì nhiệm vụ chính là phân loại thống kê.

  1. Thuật toán được cho trước 1 số điểm dữ liệu cùng với nhãn của chúng thuộc các lớp cho trước (Huấn luyện).
  2. Mục tiêu của thuật toán là xác định xem 1 điểm dữ liệu mới sẽ được thuộc về lớp nào (Phân loại).

SVM trong OpenCV

Source code

#include <opencv2/core.hpp>
#include <opencv2/imgproc.hpp>
#include "opencv2/imgcodecs.hpp"
#include <opencv2/highgui.hpp>
#include <opencv2/ml.hpp>

using namespace cv;
using namespace cv::ml;

int main(int, char**)
{
	int width = 512, height = 512;
	Mat image = Mat::zeros(height, width, CV_8UC3);

	int labels[4] = { 1, 1, 1, -1 };
	Mat labelsMat(4, 1, CV_32SC1, labels);

	float trainingData[4][2] = { { 501, 10 }, { 255, 10 }, { 501, 255 }, { 10, 501 } };
	Mat trainingDataMat(4, 2, CV_32FC1, trainingData);

	Ptr<ml::SVM> svm = ml::SVM::create();
	svm->setType(ml::SVM::C_SVC);
	svm->setKernel(ml::SVM::LINEAR);
	svm->setTermCriteria(cv::TermCriteria(CV_TERMCRIT_ITER, 100, 1e-6));

	svm->train(trainingDataMat, ml::ROW_SAMPLE, labelsMat);

	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) << j, i);
		float response = svm->predict(sampleMat);

		if (response == 1)
			image.at<Vec3b>(i, j) = green;
		else if (response == -1)
			image.at<Vec3b>(i, j) = blue;
	}

	int thickness = -1;
	int lineType = 8;
	circle(image, Point(501, 10), 5, Scalar(0, 0, 0), thickness, lineType); // black
	circle(image, Point(255, 10), 5, Scalar(255, 255, 255), thickness, lineType); // white
	circle(image, Point(501, 255), 5, Scalar(0, 0, 255), thickness, lineType); // red
	circle(image, Point(10, 501), 5, Scalar(0, 255, 0), thickness, lineType); // green

	imshow("SVM Simple Example", image); 
	waitKey(0);
}

Phân tích

Thiết lập dữ liệu huấn luyện

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

Dữ liệu được huấn luyện được tạo thành bởi 1 tập điểm có giá trị 2D. Ở đoạn code trên:

  • 2 lớp: Lớp thứ nhất mang giá trị -1, và lớp thứ hai mang giá trị 1 (labels).
  • 4 điểm dữ liệu (điểm được dùng để huấn luyện mô hình SVM) cho trước ứng với giá trị của lớp: (501, 10) thuộc lớp thứ hai, và 3 điểm còn lại thuộc lớp thứ nhất. 

Chú ý: Số lượng phần tử của ma trận labels bằng với số cột của ma trận của trainingData.

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

Chú ý: hàm CvSVM::train() sử dụng kiểu dữ liệu truyền vào là kiểu Mat.

Thiết lập thông số của SVM

// Set up SVM's parameters
Ptr<ml::SVM> svm = ml::SVM::create();
svm->setType(ml::SVM::C_SVC);
svm->setKernel(ml::SVM::LINEAR);
svm->setTermCriteria(cv::TermCriteria(CV_TERMCRIT_ITER, 100, 1e-6));

Phân tích:

  • Type SVM: chọn ml::SVM::C_SVC để có thể được sử dụng để phân loại nhiều lớp (n > 2). Tham số này được xác định trong thuộc tính ml::SVM::Params.svmType.
    • Lưu ý: Chức năng quan trọng của loại SVM CvSVM::C_SVC là tách hoàn hảo của các lớp học (khi dữ liệu đào tạo không bị phân chia qua các lớp khác).
  • Type SVM kernel: được xác định trong thuộc tính ml::SVM.KernelType.
  • Termination criteria: được định nghĩa trong 1 cấu trúc cv::TermCriteria.

Chú ý: Với các phiên bản khác của OpenCV, để thiết lập thông số cho SVM có thể sẽ có cách hiện thực khác.

Huấn luyện SVM

Để xây dựng mô hình huấn luyện SVM, sử dụng phương thức CvSVM::train().

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

Phân loại lớp (Bản lề)

Phương pháp CvSVM::predict() được sử dụng để phân loại 1 mẫu đầu vào bằng cách sử dụng 1 SVM được huấn luyện. 

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;
    } 
}
Capture
  • Với các điểm tròn nhỏ màu đen, trắng, đỏ, xanh lá cây: Đây chính là các điểm dữ liệu cho trước.
  • Ranh giới giữa màu xanh lá cây và xanh dương: Đây chính là siêu phẳng (Optimal hyperplane) của mô hình SVM. Khoảng cách giữa điểm tròn xanh lá cây tới siêu phẳng (Optimal hyperplane) sẽ bằng khoảng cách giữa điểm tròn màu đỏ tới siêu phẳng (Optimal hyperplane) (Tương tự với điểm tròn màu trắng).
  • Dòng 6: Là 1 cách khởi tạo 1 ma trận, nó sẽ có giá trị như sau: sampleMat = [i, j]. Ví dụ: Mat M = (Mat_(2,4) << 1, 0, 0, 0, 1, 0, 0, 0;. Kết quả: M =  [1, 0, 0, 0, 1, 0, 0, 0])
  • Vậy là đoạn code ở trên sẽ phân loại các điểm dữ liệu thuộc vào lớp nào trên mô hình SVM đã huấn luyện ở trên.

Support Vector

Trong OpenCV 3.0, để có thể lấy được các điểm Support Vector thì sử dụng phương thức SVM::getSupportVectors(). Kiểu trả về ở đây là 1 Mat, với số hàng Rows chính là số lượng của các điểm Support Vector.

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024