Algoritma Support Vector Machine (SVM)

Contoh implementasi Data Mining Algoritma Support Vector Machine (SVM) menggunakan PHP dan MySQL untuk menentukan penerima beasiswa

Support Vector Machine (SVM) adalah metode klasifikasi yang bekerja dengan cara mencari hyperplane dengan margin terbesar. Hyperplane adalah garis batas pemisah data antar-kelas. Margin adalah jarak antara hyperplane dengan data terdekat pada masing-masing kelas. Adapun data terdekat dengan hyperplane pada masing-masing kelas inilah yang disebut support vector (J. Yunliang, et al., 2010).

[ author : cahya dsn, published on : Nov 16, 2018 ]

minerva minerva donasi donation

Mau lihat artikel lainya? Dapatkan artikel-artikel lain seputar pemrograman website di sini, dan dapatkan ide-ide baru

Support Vector Machine (SVM) adalah sistem pembelajaran yang menggunakan ruang hipotesis berupa fungsi-fungsi linier dalam sebuah ruang fitur (feature space) berdimensi tinggi, dilatih dengan algoritma pembelajaran yang didasarkan pada teori optimasi dengan mengimplementasikan learning bias yang berasal dari teori pembelajaran statistik (Christianini 2000).

Teori yang mendasari SVM sendiri sudah berkembang sejak 1960-an, tetapi baru diperkenalkan oleh Vapnik, Boser dan Guyon pada tahun 1992 dan sejak itu SVM berkembang dengan pesat. SVM adalah salah satu teknik yang relatif baru dibandingkan dengan teknik lain, tetapi memiliki performansi yang lebih baik di berbagai bidang aplikasi seperti bioinformatics, pengenalan tulisan tangan, klasifikasi teks dan lain sebagainya (Chang, 2001).

Pre-requisites

  • Pemahaman terhadap dasar-dasar Data Mining
  • Pemahaman terhadap dasar-dasar teknologi web,HTML dan CSS
  • Pemahaman terhadap dasar-dasar basis data/database, terutama query SQL pada MySQL/mariaDB
  • Pemahaman terhadap dasar-dasar pemrograman PHP, terutama fungsi-fungsi koneksi database dan pengelolaan tipe data array

1.1 Structural Risk Minimization (SRM)

Proses pembelajaran pada SVM bertujuan untuk mendapatkan hipotesis berupa bidang pemisah terbaik yang tidak hanya meminimalkan empirical risk yaitu rata-rata error pada data pelatihan, tetapi juga memiliki generalisasi yang baik. Generalisasi adalah kemampuan sebuah hipotesis untuk mengklasifikasikan data yang tidak terdapat dalam data pelatihan dengan benar. Untuk menjamin generalisasi ini, SVM bekerja berdasarkan prinsip Structural Risk Minimization (SRM)

SRM bertujuan untuk menjamin batas atas dari generalisasi pada data pengujian dengan cara mengontrol "kapasitas" (fleksibilitas) dari hipotesis hasil pembelajaran. Untuk mengukur kapasitas ini digunakan dimensi Vapnik-Chervonenkis (VC) yang merupakan properti dari ruang hipotesis ${f (α )}$. Nilai dari dimensi VC ini, berdasarkan teori pembelajaran statistik akan menentukan besarnya nilai kesalahan hipotesis pada data pengujian. Lebih jelasnya, besar kesalahan pada data pengujian/actual risk $R(α)$ dengan probabilitas sebesar $1−η,0 ≤η ≤ 1$, pada dataset yang terdiri dari $n$ data dapat dilihat pada persamaan (SVM-001). $R_{emp}(α)$ adalah kesalahan pada data pelatihan dan $h$ adalah dimensi VC.

$$R(α)≤R_{emp}(α)+\sqrt(\frac{h(log\frac{2l}{h}+1-log(\frac{η}{4}))}{l})$$
.. [SVM-001]

Nilai VC confidence (nilai elemen kedua pada ruas kanan (SVM-001) ), ditentukan oleh hipotesis/ fungsi hasil pembelajaran (Burges , 1998). Jadi, prinsip SRM adalah menemukan subset dari ruang hipotesis yang dipilih sehingga batas atas actual risk dengan menggunakan subset tersebut diminimumkan. SRM bertujuan untuk meminimumkan actual risk dengan cara meminimumkan kesalahan pada data pelatihan dan juga VC confidence. Namun, implementasi SRM tidak dilakukan dengan meminimumkan persamaan (SVM-001) karena dimensi VC dari ruang hipotesis ${f(α)}$ sulit untuk dihitung dan hanya terdapat sedikit model hipotesis yang diketahui bagaimana cara menghitung dimensi VC-nya (Osuna , 1997). Selain itu, walaupun dimensi VC dapat dihitung, tidak mudah meminimumumkan persamaan (SVM-001). Implementasi SRM pada SVM menggunakan fungsi linier dan akan dijelaskan pada bagian selanjutnya.

SVM pada Linearly Separable Data

Linearly separable data merupakan data yang dapat dipisahkan secara linier. Misalkan {$x_n ,..., x_1$} adalah dataset dan $y_i ∈${$+1,−1$} adalah label kelas dari data $x_i$. Pada gambar 1 dapat dilihat berbagai alternatif bidang pemisah yang dapat memisahkan semua data set sesuai dengan kelasnya. Namun, bidang pemisah terbaik tidak hanya dapat memisahkan data tetapi juga memiliki margin paling besar.

1.2. Kelebihan dan Kekurangan

This document using Dynamic Content Technology for enrichment sample case and reading experience
  • Data yang digunakan BUKAN merupakan data real, tapi data yang digenerate secara otomatis/random/acak dari sistem
  • Data dan Nilai Perhitungan yang ditampilkan akan SELALU BERBEDA jika halaman di refresh/reload
  • Jumlah Data Alternatif yang diperhitungkan ditentukan secara acak/random antara 5 s.d 10

2.1. Pemilihan Data

2.2. Pre-proses/Pembersihan Data

2.3. Transformasi

2.4. Data Mining

2.5. Evaluasi

3.1. Persiapan Database

Sebagai bahan pembelajaran Algoritma SVM ini; dibuat database (dalam hal ini menggunakan MySQL/MariaDB Database server) sebagai berikut:

CREATE DATABASE IF NOT EXISTS db_dm;
USE db_dm;

Awalnya membuat dulu database dengan nama db_dm jika belum ada database dengan nama tersebut, kemudian gunakan database tersebut dengan memakai sintak USE db_dm;

Dalam hal ini, pembuatan database memakai command console dari database server yang bersangkutan

Sebelum dilakukan perhitungan-perhitungan menggunakan algoritma Support Vector Machines dengan menggunakan PHP, maka terlebih dahulu kita menyiapkan data yang akan diolah dengan mengambil (fetching) data dari database, dan disimpan (assign) ke dalam variabel-variabel PHP.

3.2.1. Koneksi ke Database

Sebelum melalukan operasi dengan data dari database, perlu dibuat script untuk koneksi ke database terlebih dahulu. Dari database yang sudah dibuat, kita bisa membuat script php untuk membuat koneksi ke database server dengan extension mysqli sebagai berikut:

<?php
//-- konfigurasi database
$dbhost 'localhost';
$dbuser 'root';
$dbpass '';
$dbname 'db_dm';
//-- koneksi ke database server dengan extension mysqli
$db = new mysqli($dbhost,$dbuser,$dbpass,$dbname);
//-- hentikan program dan tampilkan pesan kesalahan jika koneksi gagal
if ($db->connect_error) {
    die(
'Connect Error ('.$db->connect_errno.')'.$db->connect_error);
}
?>;

Sesuaikan nilai-nilai $dbhost,$dbuser,$dbpass dan $dbname dengan konfigurasi database yg digunakan.