Support Vector Machine

Ide dasar Support Vector Machine (SVM) adalah memaksimalkan batas hyperplane (maximal margin hyperplane), seperti yang diilustrasikan pada Gambar 2.1 (a) ada sejumlah pilihan hyperplane yang mungkin untuk set data, dan 2.1 (b) merupakan hyperplane dengan margin yang paling maksimal. Meskipun 2.1 (a) sebenarnya juga bisa menggunakan hyperplane sembarang, hyperplane dengan margin yang maksimal akan memberi generalisasi yang lebih baik pada metode klasifikasi.

Konsep klasifikasi dengan SVM dapat dijelaskan secara sederhana sebagai usaha untuk mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah kelas data pada ruang input (Nugroho, 2007). Gambar 2.1 memperlihatkan beberapa pola yang merupakan anggota dari dua buah kelas data: +1 dan -1. Data yang tergabung pada kelas -1 disimbolkan dengan bentuk lingkaran, sedangkan data pada kelas +1 disimbolkan dengan bentuk bujur sangkar.

Hyperplane (batas keputusan) pemisah terbaik antara kedua kelas dapat ditemukan dengan mengukur margin hyperplane tersebut dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane tersebut dengan data terdekat dari masing-masing kelas. Data yang paling dekat ini disebut support vector. Garis solid pada Gambar 2.1 (b) sebelah kanan menunjukkan hyperplane terbaik, yaitu yang terletak tepat pada tengah-tengah kedua kelas, sedangkan data lingkaran dan bujur sangkar yang dilewati garis batas margin (garis putus-putus) adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pelatihan pada SVM.

Berikut ini merupakan contoh aplikasi pemrograman matlab untuk mengklasifikasi bentuk objek dalam suatu citra. Pada contoh ini, bentuk yang diklasifikasikan adalah bentuk lingkaran dan bentuk hati. Masing-masing bentuk tersebut kemudian diekstraksi cirinya berdasarkan parameter metric dan eccentricity. Metric merupakan nilai perbandingan antara luas dan keliling objek. Sedangkan eccentricity merupakan nilai perbandingan antara jarak foci ellips minor dengan foci ellips mayor suatu objek. (Materi mengenai ekstraksi ciri citra dapat dilihat pada halaman berikut: Ekstraksi Ciri). Langkah-langkah klasifikasi bentuk objek menggunakan algoritma Support Vector Machine yaitu:

1. Mempersiapkan data latih untuk pelatihan, pada proses ini digunakan 30 citra yang terdiri dari 15 citra dengan objek berbentuk lingkaran dan 15 citra dengan objek berbentuk hati.

2. Mempersiapkan data uji untuk pengujian, pada proses ini digunakan 10 citra yang terdiri dari 5 citra dengan objek berbentuk lingkaran dan 5 citra dengan objek berbentuk hati.

3. Mengekstraksi ciri bentuk pada citra data latih berdasarkan parameter metric dan eccentricity

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

clc;clear;close all;   image_folder = 'Pattern Recognition\data latih'; filenames = dir(fullfile(image_folder, '*.gif')); total_images = numel(filenames);   area = zeros(1,total_images); perimeter = zeros(1,total_images); metric = zeros(1,total_images); eccentricity = zeros(1,total_images);   for n = 1:total_images     full_name = fullfile(image_folder, filenames(n).name);     our_images = logical(imread(full_name));     our_images = bwconvhull(our_images,'objects');     stats = regionprops(our_images,'Area','Perimeter','Eccentricity');     area(n) = stats.Area;     perimeter(n) = stats.Perimeter;     metric(n) = 4*pi*area(n)/(perimeter(n)^2);     eccentricity(n) = stats.Eccentricity;     trainset = [metric;eccentricity]'; end

4. Nilai metric dan eccentricity yang telah diekstrak kemudian digunakan sebagai data masukan dalam proses pelatihan SVM. Pada contoh ini, nilai metric digunakan sebagai sumbu-x, sedangkan nilai eccentricity digunakan sebagai sumbu-y. Kernel SVM yang digunakan adalah kernel linier.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

% prepare class label for first run of svm class=cell(30,1); class(1:15,1)={'Circle'}; class(16:30,1)={'Heart'};   % perform run of svm figure, SVMModel = fitcsvm(trainset,class); sv = SVMModel.SupportVectors; gscatter(trainset(:,1),trainset(:,2),class) grid on hold on plot(sv(:,1),sv(:,2),'ko','MarkerSize',10) legend('circle','heart','Support Vector') hold off xlabel('Metric') ylabel('Eccentricity')   save SVMModel.mat SVMModel

5. Sehingga hasil dari proses pelatihan adalah sebagai berikut

6. Setelah dilakukan proses pelatihan, maka diperoleh hyperplane grafik antara metric dan eccentricity. Pada grafik di atas, tampak bahwa hyperplane mampu untuk memisahkan dua kelas (lingkaran dan hati) dengan akurasi 100% (tidak ada data yang berada pada kelas yang salah). Hyperplane tersebut kemudian digunakan sebagai garis pemisah untuk mengklasifikasi pada proses pengujian. Pemrograman untuk proses pengujian yaitu:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

clc;clear;close all;   image_folder = 'Pattern Recognition\data uji'; filenames = dir(fullfile(image_folder, '*.gif')); total_images = numel(filenames);   area = zeros(1,total_images); perimeter = zeros(1,total_images); metric = zeros(1,total_images); eccentricity = zeros(1,total_images);   for n = 1:total_images     full_name = fullfile(image_folder, filenames(n).name);     our_images = logical(imread(full_name));     our_images = bwconvhull(our_images,'objects');     stats = regionprops(our_images,'Area','Perimeter','Eccentricity');     area(n) = stats.Area;     perimeter(n) = stats.Perimeter;     metric(n) = 4*pi*area(n)/(perimeter(n)^2);     eccentricity(n) = stats.Eccentricity;     testset = [metric;eccentricity]'; end   load SVMModel Group = predict(SVMModel,testset)

7. Sehingga dihasilkan kelas keluaran berikut ini:

8. Kelas keluaran tersebut 100% sesuai dengan kelas keluaran pada data uji sebenarnya, sehingga proses pengenalan pola bentuk lingkaran dan hati menggunakan algoritma SVM menghasilkan akurasi yang sangat baik