Konferensi Nasional Sistem dan Informatika 2010; Bali, November 13, 2010 KNS&I10-036

212

PENDEKATAN ALGORITMA GENETIKA PADA PENYELESAIAN MASALAH OPTIMASI UNTUK MODEL SUPPORT VECTOR MACHINE

(SVM) CLASSIFIER STUDI KASUS: HARD MARGIN SVM

Deni Saepudin dan Z.K. Abdurahman Baizal

Institut Teknologi Telkom dns@ittelkom.ac.id, zka@ittelkom.ac.id

ABSTRACT

An alternative formulation for the optimization problem of support vector machine (SVM) classifier model is discussed in this paper. The proposed formulation is constructed based on the original concept of SVM to find the best hyperplane which has maximal margin. Although the objective function of the optimization problem is not differentiable and moreover discontinuous, the optimization problem for hard margin SVM case could be solved by genetic algorithm approach. Different from existing approach, here the optimization problem is solved without changing the primal problem into the dual problem. Keywords: Support Vector, Margin, Constrained Optimization, Genetic Algorithm, Objective Function. 1. Pendahuluan Support Vector Machine (SVM) adalah metode yang umum digunakan untuk mengklasifikasikan data, diterapkan pada banyak permasalahan nyata seperti pada data mining, machine learning, dan pengenalan pola. Prinsip kerja dari metoda SVM adalah menentukan model classifier terbaik (biasanya berupa hyperplane) yang memisahkan data dari kelas yang berbeda. Koefisien-koefisien dari hyperplane classifier dipilih sehingga jarak hyperplane ke titik-titik terdekat dari kedua kelas paling jauh. Dari kajian literature yang dilakukan, penentuan hyperplane classifier akan membawa kita pada masalah optimasi berkendala dengan fungsi tujuan berupa fungsi kuadrat. Dalam pendekatan yang biasa dilakukan, solusi masalah optimasi berkendala selanjutnya dicari dari masalah dual melalui pendekatan metode pengali Lagrange. Selanjutnya solusi dari masalah dual dicari dengan beberapa cara, di antaranya dengan metode sequential minimal optimization atau SMO[4], perbaikan SMO[3], gradient projection[9], cross entropy[8], dan lain-lain. Sejauh ini dari kajian literatur yang telah dilakukan, penulis belum menjumpai pendekatan penyelesaian masalah penentuan model SVM classifier melalui penyelesaian masalah primal. Kesulitan yang dihadapi dalam penyelesaian masalah primal adalah penanganan kendala (constraint) berupa sistem pertidaksamaan linear. Dalam pendekatan yang dilakukan penulis dalam paper ini, penanganan kendala dilakukan dengan melibatkan kendala ke dalam fungsi tujuan, sehingga diperoleh masalah optimasi tanpa kendala. Akan tetapi, fungsi tujuan dari masalah optimasi diperoleh berupa fungsi yang tidak differensiable dan bahkan tidak kontinu. Oleh karena itu, metode-metode penyelesaian masalah optimasi yang berdasarkan kalkulus seperti metode gradient atau metode nonlinear programming menjadi sulit diterapkan. Metode metode alternatif penyelesaian masalah optimasi yang lebih fleksible, kokoh (robust) dan mempunyai kinerja yang cukup baik untuk menyelesaikan masalah optimasi yang kompleks, sudah banyak dikembangkan. Umumnya metode-metode tersebut diadopsi dari proses-proses yang terjadi di alam. Salah satu metode yang sudah cukup dikenal adalah algoritma genetika[2]. Cukup banyak penelitian yang mendukung kehandalan algoritma genetika untuk penyelesaian masalah optimasi yang cukup kompleks, seperti pada masalah optimasi dalam proses produksi minyak bumi dengan teknik gas lift[5, 7, 6], di mana fungsi tujuan hanya dinyatakan secara implisit melalui persamaan-persamaan aliran fluida pada sumur minyak bumi. Fleksibilitas algoritma genetika untuk penyelesaian masalah optimasi yang tidak menuntut persyaratan yang ketat, seperti kekontinuan dan keterdifferensialan fungsi tujuan, memungkinkan metode ini untuk penyelesaian masalah optimasi dalam pendekatan ini. 2. Formulasi Masalah Optimasi Untuk Hard Margin SVM Diberikan himpunan data (x1,y1), (x2,y2), …, (xN,yN)∈ N x yang dapat dipisah secara linear ke dalam kelas A (dinotasikan dengan indeks 1) dan kelas B (dinotasikan dengan indeks -1). Hyperplane terbaik yang memisahkan kedua data tersebut dapat diperoleh berupa hyperlane.

(1)T +w x b = 0

(1)

Konferensi Nasional Sistem dan Informatika 2010; Bali, November 13, 2010 KNS&I10-036

213

sehingga jarak hyperplane ke titik terdekat dari kedua kelas bernilai maksimal. Ilustrasi dalam dua dimensi dapat dilihat pada Gambar 1.

Gambar 1. Ilustrasi Hyperplane Classifier Terbaik

Agar hyperplane (1) memisahkan data ke dalam kedua kelas, maka dapat dipilih vektor w dan b sehingga: jika (2)

danjika (3)

Ti i

Ti i

A

B

+ ∈

+ ∈

w x b > 0, x

w x b < 0, x

Untuk suatu titik x0 yang diberikan, jarak hyperplane ke titik tersebut diberikan oleh

0

2

(4)T b

J+

=w x

w

Jarak hyperplane ke titik terdekat dari kedua kelas disebut margin. Dalam pendekatan yang biasa[1], pencarian hyperplane classifier dilakukan dengan langkah-langkah berikut: • Andaikan +x dan -x masing-masing adalah titik pada himpunan A dan B yang terdekat ke hyperplane. Maka

tanpa mengurangi keumuman, dapat ditetapkan (5)T + =+w x b 1

dan

(6)T + = −-w x b 1 Sehingga

wTxi + b ≥ 1, untuk semua xi ∈A (7) dan

wTxi + b ≤ -1, untuk semua xi ∈B (8).

Jarak antara hyperplane dengan titik +x dan -x dapat dituliskan menjadi

1/22 2 2

1 1 (9),

T T

J+ −+ +

= = = =w x b w x b

w w w w w

• Definisikan 1, untuk

( ) (10)1, untuk

ii i

i

Ay h

B∈⎧

= = ⎨− ∈⎩

xx

x Maka (wTxi + b)yi ≥ 1 , i = 1, 2, …, N • Koefisien hyperplane classifier terbaik diperoleh dari solusi yang masalah optimasi berkendala

1/2,

1,

. . (11)( ) 1, untuk 1,2,...,

b

Ti i

Maks

s tb y i N+ ≥ =

w w w

w x

Yang ekivalen dengan solusi masalah optimasi 

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

Konferensi Nasional Sistem dan Informatika 2010; Bali, November 13, 2010 KNS&I10-036

214

,

12

. . (12)( ) 1, untuk 1,2,...,

T

b

Ti i

Min

s tb y i N+ ≥ =

ww w

w x 

• Dengan pendekatan metode pengali Lagrange, solusi masalah optimasi berkendala (12) dicari dari solusi masalah dual

1 1 1

1

12

. . (13)

0, 0, 1, 2,...,

N N NT

i i j i j i ji i j

N

i i ii

Maks y y

s t

y i N

α α α

α α

= = =

=

−

= ≥ =

∑ ∑∑

∑

x xα

Dalam pendekatan yang akan dilakukan dalam penelitian ini, penentuan hyperplane pemisah terbaik akan dicari dengan langkah-langkah berikut: • Jarak hyperplane ke titik xi dapat didefinisikan sebagai berikut

( ) ( )1/2

2

(14)12

T Ti i i i

i

b y b y+ += =J

w x w x

w w,w

• Berdasarkan definisi dari margin, maka nilai margin untuk hyperplane (1) dapat dituliskan menjadi

( ), 1/2

(15)12

i i

Ti i

y

b yMin

+=J

x

w x

w,w

• Oleh karena itu, hyperplane classifier dengan margin terbesar dapat diperoleh dari solusi masalah optimasi tanpa kendala

( ), , 1/2

(16)12

i i

Ti i

b y

b yMaks Min

+=

w x

w x

w,wJ

Keuntungan dari pendekatan di atas dibandingkan pendekatan yang biasa digunakan adalah 1. Lebih sederhana, karena hanya berupa masalah optimasi tanpa kendala. 2. Dapat langsung diselesaikan dengan algoritma penyelesaian masalah optimasi yang ada seperti algoritma genetika.

Pada metode yang biasa digunakan, penyelesaian masalah optimasi berkendala dicari dari penyelesaian masalah dual-nya melalui pendekatan metode pengali Lagrange. Ini seringkali menyulitkan dalam memahami metode support vector machine.

3. Pendekatan yang dilakukan lebih fleksible untuk dikembangkan pada masalah support vector machine non linear dan potensial untuk dikembangkan untuk penyelesaian masalah klasifikasi multi kelas.

3. Skema Komputasi Penyelesaian masalah optimasi berkendala dengan fungsi tujuan tidak differensiable diselesaikan dengan algoritma genetika. Fungsi fitness yang ingin dimaksimalkan dapat dipilih berupa fungsi margin J pada (16). Berikut adalah langkah-langkah dari skema komputasi i. Bangkitkan populasi awal yang terdiri dari inidividu-individu v1, v2, …, vr yang berpadanan dengan pasangan (w1,b1),

(w2,b2),…,(wr,br). Dalam hal ini, nilai w dipilih agar ||w|| = 1. ii. Untuk setiap pasangan (wk,bk), k=1,2,…,r, evaluasi nilai fitnessnya yaitu nilai ( , )k kw bJ untuk k=1,2,…,r.

iii. Dapatkan individu-individu baru melalui persilangan (cross over) dan mutasi. iv. Melalui proses seleksi, pilih individu-individu yang terbaik agar diperoleh populasi yang baru.

(12)

(13)

(14)

(15)

(16)

Konferensi Nasional Sistem dan Informatika 2010; Bali, November 13, 2010 KNS&I10-036

215

Bila kriteria penghentian belum terpenuhi, kembali ke langkah ii. 4. Hasil Komputasi Untuk kajian permulaan, skema komputasi yang dibangun diterapkan pada himpunan data hipotetik berikut. (-1 0 -1), (-0.5 2.5 -1), (0 -1 -1), (1 0 -1), (1 1 -1), (2 0.5 -1), (1 2.5 1), (3 3 1), (2 2.5 1), (3 0 1), (0 3 1). Komputasi dengan algoritma genetika dilakukan dengan parameter : jumlah populasi 100, peluang crossover 0.9, peluang mutasi 0.1, dan maximum generasi 500. Koefisien hyperplane classifier diperoleh yaitu (w, b) = (0.7071, 0.7071, -1.9445). Ilustrasi himpunan data dan hyperplane classifier dapat dilihat pada Gambar 2.

Gambar 2. Model SVM Hasil Komputasi

5. Kesimpulan dan Riset Lanjutan Berdasarkan hasil yang diperoleh dari kajian pendahuluan dapat disimpulkan bahwa i. Pendekatan algoritma genetika dapat diterapkan untuk penyelesaian masalah optimasi pada penentuan model SVM

untuk data yang linearly separable berukuran kecil. ii. Skema komputasi yang dilakukan dapat menyelesaikan masalah optimasi primal tanpa harus mengubahnya menjadi

masalah dual. iii. Pendekatan yang dilakukan potensial untuk dikembangkan pada model SVM soft margin, non linear dan multi kelas. Daftar Pustaka [1] Cristianini., N, and Taylor., J. S. (2000). An Introduction to Support Vector Machines and other kernel-based

learning methods, Cambridge University Press, UK. [2] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA: Addison-

Wesley. [3] Keerthi, S. S., Shevade., S. K. , Bhattacharyya., C and Murthy., K. R. K. (2001). Improvements to Platt’s SMO

Algorithm for SVM Classifier Design, Neural Computation, 13, 637–649. [4] Platt., J. (1999). Fast training of support vector machines using sequential minimal optimization. In B. Scholkopf, C.

J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods – Support Vector Learning, MIT Press, pp. 185-208.

[5] Saepudin, D., Soewono, E., Sidarto, K. A., Gunawan, A.Y., Siregar, S., dan Sukarno, P. (2007). An Investigation on Gas Lift Performance Curve in an Oil-Producing Well, International Journal of Mathematics and Mathematical Sciences, Volume 2007, Article ID 81519.

[6] Saepudin, D., Sukarno, P., Soewono, E., Sidarto, K. A., and Gunawan, A. Y. (2010). Oil Production Optimization in a Cluster of Gas Lift Wells System, Journal of Applied Sciences, 10(16), pp. 1705-1713.

[7] Sukarno, P., Saepudin, D., Dewi, S., Soewono, E., Sidarto, K. A., and Gunawan, A. Y. (2009). Optimization of Gas Injection Allocation in a Dual Gas Lift Well System, Journal of Energy Resources Technology, Transaction of the ASME, 2009, 131(3), 033101.

[8] Santosa., B. (2009). Application of the Cross Entropy Method for Dual Lagrange Support Vector Machine, Lectures Notes in Artificial Intelligent, Springer, Germany.

[9] Serafini., T, Zanghirati., G, and Zanni., L. (2005). Gradient projection methods for quadratic programs and applications in training support vector machines. Optimization Methods and Software, 20, pp. 353-378.