BAB 2 LANDASAN TEORI
2.1 Visi Komputer Visi komputer merupakan ilmu yang dideskripsikan sebagai gambar yang diolah, diproduksi oleh kamera dan dianalisis oleh komputer. Kamera dan komputer menyajikan mesin yang setara dengan kemampuan visual manusia, seperti melihat, berpikir, dan merespon. Computer Vision mempunyai tujuan utama untuk menganalisa obyek fisik yang nyata berdasarkan image yang ditangkap dari sensor. Visi komputer diciptakan untuk membangun sebuah mesin pandai yang dapat melihat, berikut merupakan prosesnya meliputi preprocessing dan proses recognition atau pengenalan pola. Tahapan Preprocessing meliputi : 2.1.1 Pengolahan Citra Citra adalah gambar pada bidang dwimatra (dua dimensi). Ditinjau dari sudut pandang matematis, citra merupakan fungsi menerus (countinue) dari intensitas cahaya pada bidang dwimatra. Sumber cahaya menerangi objek, objek memantulkan kembali sebagian dari berkas cahaya tersebut. Pantulan cahaya ini ditangkap oleh alat-alat optik, misalnya mata pada manusia, kamera, pemindai (scanner), dan sebagainya, sehingga bayangan objek yang disebut citra terekam. Meskipun sebuah citra kaya informasi, namun seringkali citra yang kita miliki mengalami penurunan mutu (degradasi), misalnya mengandung cacat atau derau (noise), warnanya terlalu kontras, kurang tajam, kabur (blurring), dan sebagainya. Citra yang seperti ini tentu saja menjadi lebih sulit diinterpretasi karena informasi yang disampaikan oleh citra tersebut menjadi berkurang.
6
7
Agar citra yang mengalami gangguan mudah diinterpretasi (baik oleh manusia maupun mesin), maka citra tersebut perlu dimanipulasi menjadi citra lain yang kualitasnya lebih baik. Bidang studi yang menyangkut hal ini adalah Pengolahan Citra (Image Processing). Pengolahan Citra adalah suatu metode yang digunakan untuk memproses atau memanipulasi image dalam 2 dimensi, segala operasi untuk memperbaiki, penganalisaan, dan pengubahan suatu gambar disebut pengolahan citra. Konsep dasar pemrosesan suatu obyek yang menggunakan pengolahan citra. Diambil dari kemampuan indera penglihatan manusia yang selanjutnya dihubungkan dengan kemampuan otak manusia. Dalam sejarahnya, pengolahan citra telah di aplikasikan dalam berbagai bentuk, dengan tingkat kesuksesan yang cukup besar, seperti berbagai cabang ilmu lainnya, pengolahan citra. Menyangkut pula berbagai gabungan cabang – cabang ilmu, diantaranya optik, elektronik, matematika, fotografi, dan teknologi komputer. Beberapa faktor menyebabkan perkembangan sistem pengolahan citra menjadi lebih berkembang pesat pada saat ini. Salah satu yang utama adalah dibutuhkannya suatu teknologi yang dapat bekerja secara mandiri dalam arti teknologi yang dapat memproses data – data yang diterima dan pada akhirnya teknologi tersebut dapat mengambil keputusan sendiri dari hasil pengolahan data sebelumnya. Selain itu penurunan biaya akan peralatan komputer yang dibutuhkan serta peningkatan tersedianya peralatan untuk proses tampilan gambar juga menjadi salah satu faktor semakin berkembangnya pengolahan citra. Pada umumnya, objektif dari pengolahan citra adalah mentransformasikan atau menganalisis suatu gambar sehingga informasi baru tentang gambar di buat lebih jelas.
8
Ada 4 klasifikasi dasar dalam pengolahan citra., yaitu: berbasis point, berbasis area, berbasis geometric, dan berbasis frame. ¾ Berbasis Point / berbasis piksel yaitu, memproses nilai piksel image berdasarkan nilai atau posisi dari piksel tersebut. Contoh dari proses point adalah adding, subtracting, contrast, stretching, dan lainnya. ¾ Berbasis Area yaitu memproses nilai piksel – piksel suatu image berdasarkan nilai piksel tersebut beserta nilai piksel
tetangga – tetangga (area
sekelilingnya). Contoh dari proses area adalah convolution, blurring, sharpening, filtering dan lainnya. ¾ Berbasis Geometric digunakan untuk merubah posisi dari pixel – pixel. Contoh dari proses geometric adalah scalling, rotation, mirroring, dan lainnya. ¾ Berbasis Frame yaitu memproses nilai pixel berdasarkan operasi dari 2 (dua) buah image atau lebih. Contoh dari proses frame adalah addition, subtraction, and/or, dan lainnya. Perbedaan proses frame disini dengan proses point yaitu pada proses point nilai – nilai pixelnya di proses (ditambahkan, dikurangkan, dan lainnya)
dengan suatu nilai tertentu, sedangkan pada proses frame
pemrosesan nilai-nilai pixelnya dilakukan antara dua image. Operasi-operasi pada pengolahan citra diterapkan pada citra bila : 1. Perbaikan atau memodifikasi citra perlu dilakukan untuk meningkatkan kualitas penampakan atau untuk menonjolkan beberapa aspek informasi yang terkandung di dalam citra 2. Elemen di dalam citra perlu dikelompokkan, dicocokkan, atau diukur 3. Sebagian citra perlu digabung dengan bagian citra yang lain Pengolahan citra bertujuan memperbaiki kualitas citra agar mudah diinterpretasi oleh manusia atau mesin (dalam hal ini komputer). Teknik-teknik
9
pengolahan citra mentransformasikan citra mejadi citra lain. Jadi, masukannya adalah citra dan keluarannya juga citra.
Pengolahan
CITRA
CITRA
Citra Gambar 2.1 Input dan Output untuk proses Pengolahan Citra Pengubahan citra pada gambar 2.2 adalah contoh operasi pengolahan citra. Contoh operasi pengolahan citra lainnya adalah penghilangan derau (noise) pada citra lena (gambar 2.3). Citra lena yang disebelah kiri mengandung derau berupa bintik-bintik putih (derau). Dengan operasi penapisan (filtering) derau pada citra masukan ini dapat dikurangi sehingga dihasilkan citra yang kualitasnya lebih baik.
(a)
(b)
Gambar 2.2 (a) Citra Burung Nuri yang agak gelap, (b) Citra burung yang telah diperbaiki kontrasnya sehingga terlihat jelas dan tajam
10
(a)
(b)
Gambar 2.3 (a) Citra Lena yang mengandung derau, (b) hasil dari operasi penapisan derau (filtering) 2.1.1.1 Visi Komputer dan Hubungannya Dengan Pengolahan Citra Terminologi lain yang berkaitan erat dengan pengolahan citra adalah visi komputer atau machine vision. Pada hakikatnya, visi komputer mencoba meniru cara kerja sistem visi manusia (human vision). Visi manusia sesungguhnya sangat kompleks. Manusia melihat objek dengan indera penglihatan (mata), lalu citra objek diteruskan ke otak untuk diinterpretasi sehingga manusia mengerti objek apa yang tampak dalam pandangan matanya. Hasil interpretasi ini mungkin digunakan untuk pengambilan keputusan (misalnya menghindar kalau melihat mobil melaju di depan). Visi komputer merupakan proses otomatis yang mengintegrasikan sejumlah besar proses untuk persepsi visual, seperti akuisisi citra, pengolahan citra, klasifikasi, pengenalan (recognition), dan membuat keputusan.
11
Visi komputer terdiri dari teknik-teknik untuk mengestimasi ciriciri objek di dalam citra, pengukuran ciri yang berkaitan dengan geometri objek, dan menginterpretasi informasi geometri tersebut. Proses – proses di dalam visi komputer dapat dibagi menjadi tiga aktivitas: 1. Memperoleh atau mengakuisisi citra dijital. 2. Melakukan teknik komputasi untuk memproses atau memodifikasi data citra (operasi – operasi pengolahan citra). 3. Menganalisis dan menginterpretasi citra dan menggunakan hasil pemrosesan untuk tujuan tertentu, misalnya memandu robot, mengontrol peralatan, memantau proses manufaktur, dan lain -lain. Mengklasifikasikan proses-proses didalam visi komputer didalam hirarki sebagai berikut: Hirarki Pemrosesan
Contoh Algoritma
Preprocessing
Noise removal Contrast enhancement
Lowest-level feature extraction
Edge detection Texture detection
Intermediate-level feature identification
connectivity Pattern matching Boundary coding
High-level scene interpretation via images
Model Base Recognition
12
Dari penjelasan di atas, dapat kita lihat bahwa pengolahan citra dan pengenalan pola merupakan bagian dari visi komputer. Pengolahan citra merupakan proses awal (preprocessing) pada visi komputer, sedangkan pengenalan pola merupakan proses untuk menginterpretasi citra. Teknik-teknik di dalam pengenalan pola memainkan peranan penting dalam visi komputer untuk mengenali objek. 2.1.1.2 Citra dijital Citra dijital memiliki informasi berupa gambar dan terdiri dari elemen terkecil yaitu piksel. Citra dijital direpresentasikan dalam bentuk matriks 2 dimensi yang setiap elemen merepresentasikan piksel pada gambar. 2.1.1.2.1 Warna pada Citra Dijital Semua warna yang ada merupakan perpaduan dari 3 macam warna primer yaitu : -
Warna merah
-
Warna hijau
-
Warna biru Perpaduan dari ketiga warna primer ini dipakai pada
sistem warna RGB. Bila ketiga warna primer dicampur, maka akan dihasilkan suatu warna tertentu, tergantung dari komposisi ketiga warna primer tersebut. Gambar pada sistem dijital dapat diwakili dengan format RGB untuk setiap titiknya, dimana setiap komponen R, G, dan B mempunyai variasi dari 0 sampai 255. Total variasi yang dihasilkan untuk sistem warna dijital ini adalah 256 x 256 x 256 atau 16.777.216 jenis warna. Karena setiap warna diwakili dengan satu byte atau delapan bit, maka total bit yang digunakan untuk merepresentasikan warna RGB adalah 8 + 8 + 8 atau 24 bit.
13
Kalkulasi pemrosesan gambar dengan sistem RGB sangatlah memboroskan memory dan juga waktu. Untuk itu diperlukan reduksi warna. Dalam pemrosesan gambar terutama pengenalan obyek, sistem RGB sendiri tidaklah memberikan respon yang baik, sehingga digunakan sistem format grayscale atau gray level, dimana format gambar warna di konversi menjadi format gambar abu-abu. Sistem grayscale memerlukan 1 byte (delapan bit) untuk penyimpanan data, mempunyai kemungkinan warna dari 0 (hitam) sampai 255 (putih) Cara konversi dari sistem warna RGB menjadi grayscale ini ada beberapa macam: ¾
Dengan merata-rata setiap komponen warna pada RGB GRAY = ( R+G+B) 3
¾
Menggunakan nilai maksimal dari komponen RGB GRAY MAX {R, G, B}
Citra akan di konversi menjadi citra grayscale (Grayscaling) Citra yang di masukkan akan diproses menjadi citra grayscale, dengan cara diambil nilai R, G, B dari masing – masing pixel dari citra atau dengan merata – rata setiap komponen warna pada RGB. Perhitungan untuk mendapatkan nilai grayscale untuk masing – masing pixel adalah :
grayscale = R
1 1 1 +G + B 30 59 11
¾
Menggunakan sistem YUV (sistem warna pada NTSC),
yaitu
dengan
cara
mengambil
komponen
Y
(iluminasi).
14
Komponen Y sendiri dapat diperoleh dari sistem warna RGB dengan konversi (Wikipedia, diakses Mei 2009). GRAY = Y = 0,299 * R + 0,587 * G + 0,114 * B Cara yang paling terakhir ini yang paling sering digunakan untuk konversi sistem warna ke sistem grayscale. 2.1.1.2.2 Warna hitam - putih Kompleksitas gambar biner dibatasi oleh nilai threshold. Untuk mendapatkan warna hitam – putih dalam suatu image diperlukan proses thresholding. Proses thresholding digunakan untuk mengubah nilai piksel bergantung pada besar kecilnya nilai piksel tersebut terhadap nilai threshold yang telah ditentukan. Jika suatu nilai piksel lebih besar atau sama dengan nilai threshold maka piksel tersebut akan di-set ke nilai maksimum, dalam grayscale nilai piksel maksimum adalah 255 (warna putih). Sedangkan bila suatu nilai piksel kurang dari nilai threshold maka piksel tersebut akan di-set ke nilai minimum, dalam grayscale nilai piksel minimum adalah 0 (warna hitam) untuk mencari nilai thresholding yaitu digunakan metode otsu algorithm. ¾
Otsu Threshold algorithm
Metode Otsu (Otsu, 1979) adalah metode yang paling populer diantara semua metode thresholding yang ada. Teknik Otsu ini memaksimalkan kecocokan dari sebuah threshold sehingga dapat memisahkan objek dengan latar belakangnya. Semua ini didapatkan dengan memilih nilai threshold yang memberikan pembagian kelas yang terbaik untuk semua piksel yang ada didalam image. Dasarnya adalah dengan menggunakan histogram yang telah dinormalisasi dimana jumlah tiap poin pada setiap level dibagi dengan jumlah total poin pada image.
15
2.1.1.3
Thinning dan Cropping Thinning adalah suatu proses untuk membuat garis pada sebuah
gambar menjadi bentuk yang lebih sederhana. Dengan melakukan proses thinning maka garis – garis yang ada pada gambar akan memiliki ketebalan 1 piksel, proses thinning ini berguna pada saat huruf akan di training maupun di recognize karena akan menghasilkan fitur yang lebih baik (Petra Christian University Library). Tujuan dari thinning adalah menghilangkan piksel tertentu pada objek sehingga tebal objek tersebut menjadi hanya satu piksel. Thinning tidak boleh : ¾ Menghilangkan end-point ¾ Memutuskan koneksi yang ada ¾ Mengakibatkan excessive erosi Salah satu kegunaan thinning adalah pada proses pengenalan karakter / huruf, ada banyak cara mengimplementasikan thinning salah satu diantaranya adalah dengan hit-or-miss transform. Thinning dapat didefinisikan sebagai: Thinning(A,{B}) = A – (A * {B}) = A – ((...(A*B1)*B2)..Bn) Dengan B1, B2, B3..Bn adalah A-(A*B) berarti kebalikan dari A*B Thinning pada pengolahan citra biasanya diaplikasikan pada citra biner, terdapat cukup banyak algoritma untuk image thinning dengan tingkat kompleksitas, efisiensi dan akurasi yang berbeda – beda. Berikut merupakan algoritma thinning yang cukup populer yaitu algoritma zhang suen. Algoritma zhang suen digunakan sebagai suatu basis untuk perbandingan thinning, setiap iterasi dari metode ini terdiri dari dua subiterasi yang berurutan yang dilakukan terhadap contour point dari wilayah
16
citra. Contour point adalah setiap piksel dengan nilai 1 dan memiliki setidaknya satu 8-neighbor dengan nilai 0. Langkah langkah algoritma zhang suen : 1. Menandai contour point p untuk dihapus jika semua kondisi ini dipenuhi (a) 2 ≤ N(p1) ≤ 6; (b) S(p1) = 1; (c) p2 . p4 . p6 = 0; (d) p4 . p6 . p8 = 0; Dimana N(p1) adalah jumlah tetangga dari p1 yang tidak 0 yaitu: N(p1) = p2 + p3 + ... + p8 + p9 P9
P2
P3
P8
P1
P4
P7
P6
P5
Dan S(p1) adalah jumlah dari transisi 0-1 pada urutan p2,p3,....,p8,p9. 2. Kondisi (a) dan (b) sama dengan langkah pertama, sedangkan kondisi (c) dan (d) diubah menjadi : (c’) p2.p4.p8 = 0; (d’) p2.p6.p8 = 0; Langkah pertama dilakukan terhadap semua border piksel di citra. Jika salah satu dari keempat kondisi di atas tidak dipenuhi atau dilanggar maka nilai piksel yang bersangkutan tidak diubah. Sebaliknya jika semua kondisi tersebut dipenuhi maka piksel tersebut ditandai untuk penghapusan. Piksel yang ditandai tidak dihapus sebelum semua border point selesai diproses, setelah langkah 1 selesai dilakukan untuk semua border point maka dilakukan penghapusan untuk titik yang telah ditandai (diubah menjadi 0). Setelah dilakukan langkah 2 pada data
17
hasil dari langkah 1 dengan cara yang sama dengan langkah 1, sehingga dalam satu kali iterasi urutan algoritma nya terdiri dari : (1) Menjalankan langkah 1 untuk menandai border point yang akan di hapus (2) Hapus titik - titik yang ditandai dengan menggantinya mejadi angka 0 (3) Menjalankan langkah 2 pada sisa border points yang pada langkah 1 belum dihapus lalu yang sesuai dengan semua kondisi yang seharusnya di penuhi pada langkah 2 kemudian ditandai untuk dihapus. (4) Hapus titik-titik yang ditandai dengan menggantinya menjadi angka 0. Prosedur ini dilakukan secara iteratif sampai tidak lagi titik yang dapat dihapus. Pada saat algoritma ini selesai maka dihasilkan skeleton dari citra awal. Kelebihan zhang suen : •
Algoritma sederhana
•
Dalam pemrosesan termasuk cepat (untuk memperoleh hasil)
Dalam proses cropping dilakukan, hanya untuk mendapatkan informasi yang penting atau yang nantinya akan digunakan seperlunya dari dalam citra. Metode yang dilakukan adalah dengan menghilangkan space kosong (berwarna putih) yang tidak terpakai di dalam citra.
2.1.1.4
Segmentasi (Segmentation) Dalam visi komputer, segmentasi berarti proses membagi citra
dijital
menjadi
banyak
segmen.
Tujuan
dari
segmentasi
adalah
menyederhanakan dan/atau mengubah representasi dari citra menjadi sesuatu yang lebih berarti dan mudah untuk dianalisa. Segmentasi citra
18
biasanya digunakan untuk mencari lokasi objek dan batas bidang dalam citra. Ada banyak metode – metode segmentasi, beberapa diantaranya adalah : • Metode Clustering Algoritma dasarnya adalah : a. Ambil K pusat cluster, secara acak atau dengan pendekatan heuristic b. Tetapkan masing – masing piksel dalam citra ke dalam cluster yang akan meminimalkan variasi antara piksel dan pusat cluster c. Menghitung ulang pusat – pusat cluster dengan merata – ratakan semua piksel dalam cluster d. Ulangi tahap b dan c sampai tercapai konvergen • Metode Berbasis-Histogram Metode berbasis histogram sangat efisien jika dibandingkan dengan metode segmentasi citra yang lain karena biasanya hanya membutuhkan satu kali melewati piksel. Dalam teknik ini, histogram dihitung dari seluruh piksel dalam citra, dan puncak serta lembah di dalam histogram digunakan untuk mencari cluster dalam citra. Pengembangan dari teknik ini adalah secara rekursif melakukan metode pencarian secara histogram di dalam citra untuk membagi mereka menjadi cluster yang lebih kecil. Ini dilakukan terus – menerus dengan cluster yang lebih kecil hingga tidak ada lagi cluster yang terbuat. • Metode Deteksi Sisi • Metode Pengembangan Daerah
2.1.2 Pengenalan Pola Pengenalan pola merupakan salah satu bidang dalam komputer sains, yang memetakan suatu data ke dalam konsep tertentu yang telah didefinisikan sebelumnya. Konsep tertentu ini disebut kelas atau kategori. Proses pemetaan ini
19
menyangkut inferensi, baik secara eksplisit secara statistik (misalnya dalam aturan bayesian) maupun tak eksplisit dengan suatu jaringan keputusan (misalnya jaringan saraf tiruan atau logika samar). Pengenalan pola memainkan peranan penting dalam berbagai bidang rekayasa salah satunya dalam tugas akhir ini penulis melakukan pengenalan tulisan tangan yang nantinya menggunakan metode jaringan saraf tiruan atau tak eksplisit yang dibandingkan dengan SVM, adapun metode statistik (StatPR) dan metode sintaktik. Dalam metode jaringan syaraf tiruan (NeuroPR), pemilahan dilakukan berdasarkan tanggapan suatu neuron jaringan pengolah sinyal (neuron) terhadap stimulus masukan (pola). Pengetahuan disimpan dalam sambungan antar neuron dan kekuatan sinaptik, NeuroPR dapat dilatih, non-algoritmik, dan memakai strategi Black Box, NeuroPR sangat menarik karena : ¾
Pengetahuan apriori yang diperlukan hanya sedikit
¾
Dengan jumlah lapisan dan neuron secukupnya, JST dapat membentuk semua jenis daerah keputusan yang rumit sekalipun Secara mendasar, suatu sistem pengenalan pola terdiri dari komponen-
komponen berikut: sensor, mekanisme pre-processing, mekanisme pencari fitur (manual/otomatis), algoritma pemilih dan sekumpulan contoh pelatihan yang telah dipilih. ¾
Sensor, berfungsi untuk menangkap objek dari dunia nyata menjadi sinyalsinyal listrik (dan selanjutnya dalam bilangan-bilangan setelah proses dijitasi)
¾
Preprocessing, berfungsi untuk menonjolkan sinyal informasi dan menekan derau dalam sinyal
¾
Pencari fitur, mengambil peranan komponen tertentu dari sinyal yang mewakili sifat utama sinyal, sekaligus mengurangi dimensi sinyal mejadi sekumpulan bilangan yang lebih sedikit tetapi representatif
¾
Algoritma pemilah, melakukan assignment fitur ke kelas yang sesuai
20
¾
Sekumpulan contoh pelatihan, dipakai untuk mendapatkan representasi kelas Pembuatan suatu sistem pengenal pola yang baik mengikuti beberapa
tahap, dimulai dari pengumpulan data, pemilihan fitur, pemilihan teknik pemilah atau model yang sesuai, pelatihan dan pengujian. ¾
Pengumpulan data, bagian paling intensif dalam proyek pengenalan pola
¾
Pemilihan fitur, bagian paling kritis dari keberhasilan sistem PR (Probabilistic Reasoning)
¾
Pemilihan model, memilih model pengenal yang sesuai apakah dengan pendekatan statistik, neural dan struktural.
¾
Pelatihan, diberikan kumpulan fitur dan model kosong, adaptasikan untuk menjelaskan data apakah dengan supervised atau unsupervised
¾
Pengujian, mengevaluasi seberapa bagus kinerja dari model yang sudah dilatih. Setelah melalui tahap preprocessing, Ada dua jenis proses recognition
yang digunakan, yaitu proses image correlation dan proses feature extraction. Pada proses image correlation, template yang digunakan adalah dengan bentuk semua kemungkinan dari objek dan hasil pengenalannya dapat langsung ditentukan dari karakteristik template, sedangkan pada proses feature extraction, template yang digunakan merupakan bentuk fitur dari suatu objek yang akan dikenali dengan tujuan mencari fitur-fitur yang ada pada objek. Keluaran yang dihasilkan berupa keterangan yang menjelaskan arti sebuah objek. Ketepatan pengenalan ditentukan oleh dua parameter yaitu nilai notasi dan tinggi notasi. Kedua hasil pengenalan tersebut akan dibandingkan dengan menggunakan teknik akurasi. Dari hasil perbandingan diperoleh bahwa penggunaan proses feature extraction lebih baik jika dibanding proses image correlation karena pada notasi balok variasi bentuk objeknya sangat banyak, tetapi memiliki fitur yang jauh lebih sedikit.
21
Gambar 2.4 Perbandingan tiga teknik pengenal pola : neural, statistik, struktural/sintaktik 2.1.2.1 Ekstraksi Fitur Ekstraksi fitur merupakan proses mencari nilai karakteristik yang unik dari sebuah image. Dengan adanya nilai-nilai tersebut, maka sebuah image dapat dibedakan dengan image lainnya. Nilai karakteristik yang dihasilkan feature ekstraction selanjutnya akan digunakan sebagai support vector Zoning adalah salah satu metode dari ekstraksi fitur dimana untuk mendapatkan nilai yang unik dari sebuah image, diperoleh dengan cara membagi image menjadi n x n, selanjutnya dari setiap daerah / zone akan dihitung rata-rata jumlah pixel yg terdapat pada daerah / zone tsb. Secara umum metode ini disebut metode zoning n x n.
22
2.2 Support Vector Machine Support Vector Machine pertama kali diperkenalkan oleh Vapnik pada tahun 1992 sebagai rangkaian harmonis konsep – konsep unggulan dalam bidang pengenalan pola. Sebagai salah satu metode pengenalan pola, usia SVM terbilang masih relatif muda. Walaupun demikian, evaluasi kemampuannya dalam berbagai aplikasi menempatkannya sebagai sebuah karya terbaik dalam pengenalan pola, dan dewasa ini merupakan salah satu tema yang berkembang dengan pesat. SVM adalah metode learning machine yang bekerja atas prinsip Structural Risk Minimization (SRM) dengan tujuan menemukan hyperplane terbaik yang memisahkan dua buah kelas pada ruang input. Konsep dasar SVM sebenarnya merupakan kombinasi harmonis dari teori-teori komputasi yang telah ada puluhan tahun sebelumnya, seperti margin hyperplane (Duda & Hart tahun 1973, Cover tahun 1965, Vapnik 1964, dsb.), kernel diperkenalkan oleh Aronszajn tahun 1950, dan demikian juga dengan konsep-konsep pendukung yang lain. Akan tetapi hingga tahun 1992, belum pernah ada upaya merangkaikan komponenkomponen tersebut. Berbeda dengan strategi neural network yang berusaha mencari hyperplane pemisah antar kelas, SVM berusaha menemukan hyperplane yang terbaik pada input space. Prinsip dasar SVM adalah linear classifier, dan selanjutnya dikembangkan agar dapat bekerja pada problem non-linear. Dengan memasukkan konsep kernel trick pada ruang kerja berdimensi tinggi. Perkembangan ini memberikan rangsangan minat penelitian di bidang pengenalan pola untuk investigasi potensi kemampuan SVM secara teoritis maupun dari segi aplikasi. Dewasa ini SVM telah berhasil diaplikasikan dalam aplikasi di dunia nyata dan secara umum memberikan solusi yang lebih baik dibandingkan metode konvensional seperti misalnya artificial neural network. Support vector machines (SVM) telah terbukti sukses diaplikasikan dalam menyelesaikan masalah klasifikasi dan estimasi fungsi setelah pengenalan yang dilakukan oleh Vapnik dalam konteks teori statistical learning dan structure risk
23
minimization. Vapnik mengkonstruksikan SVM standar untuk memisahkan data-data pelatihan menjadi dua kelas. Tujuan dari pelatihan pada SVM adalah untuk menemukan fungsi pemisah (classifier) f ( x ) = ω ⋅ x + b sehingga kita dapat menggunakan classifier tersebut untuk mengklasifikasi data. Training set: set{xi , yi }i =1 , di mana x i ∈ ℜ n berperan sebagai l
input dan yi ∈ {− 1+ 1} menjadi output, mengindikasikan kelas. Formulasi SVM dimulai dari asumsi bahwa kasus yang dapat dipisahkan secara linear adalah:
⎧ω T xi + b ≥ +1, if yi = +1 ⎨ T ⎩ω xi + b ≤ −1, if yi = −1
(3)
Untuk kasus yang tidak dapat dipisahkan
⎧ω T φ (xi ) + b ≥ +1, if yi = +1 ⎨ T ⎩ω φ (xi ) + b ≤ −1, if yi = −1
(4)
Dimana φ (.) menunjukkan sebuah pemetaan dari input menjadi sesuatu yang disebut ruang fitur berdimensi tinggi. Dalam metode kernel suatu data x di input space dipetakan ke kernel feature space yang lebih tinggi melalui map :x→
sebagai berikut :
(x). Karena itu data x di input space, menjadi
(x) di kernel space.
Dalam kernel space ini, dot product dua vektor <x, x> menjadi < (x),
(x)’>. Suatu
fungsi kernel, K(x, x’), bisa digunakan untuk menggantikan dot product < (x), (x)’>. Untuk setiap fungsi yang continuous dan positive definite, akan ada suatu pemetaan sehingga K(x,y)= (
(x),
,
(y) ) untuk semua x,y אԸO, dimana ԸO adalah input space
(Mercer’s Theorem). Dalam ruang ini, permukaan keputusan linear dibangun dengan property unik yang menjamin kemampuan generalisasi yang tinggi dalam jaringan. Ditunjukkan dalam
24
gambar diagram di bawah ini, bahwa fungsi kernel nonlinear memungkinkan untuk menghitung hyperplane pemisah dengan margin maksimum di feature space.
Gambar 2.5 Pemetaan ruang fitur menggunakan fungsi kernel
Kita harus menemukan, di antara semua hyperplane yang memisahkan data-data, sebuah jarak maksimum
2
ω
di antara kedua kelas. Masalah yang ada ditransformasikan
ke dalam bentuk Quadratic Programming (QP) problem l 1 min ω T ω + C ∑ ξ i 2 i =1
(
s.t y i ω t φ ( xi
) + b) = 1 − ξ i ,ξ i
(5)
≥ 0, i = 1,...l
dimana C adalah parameter yang ditransaksikan antara error dengan margin. Quadratic Programming adalah suatu teknik Optimisasi yang meminimalisasi sejumlah n dalam notasi matriks. Masalah Quadratic Programming dapat dipecahkan dengan menggunakan lagrangian multipliers α i ∈ ℜ . Solusi yang dihasilkan memenuhi kondisi Karush-Kuhn-Tucker
(KKT).
ω dapat
dicari
dengan
menggunakan
25 l
ω = ∑ α i y iφ ( xi ) , dimana xi bukan nol dan α i adalah support vector. Decision i =1
boundary hanya ditentukan oleh support vector. Diketahui t , ( j 1, ..., s) menjadi titiktitik dari s support vector. Maka kita dapat menuliskan kembali fungsi yang ada menjadi :
ω = ∑ α tj ytjφ (xtj ) s
(6)
j =1
Masalah Quadratic Programming dipecahkan dengan menambahkan Dual Problem
max α Q(α ) = −
1 l ∑α iα j yi y j K (xi , x j ) 2 i , j =1
(7)
(8) dengan kernel trick (mercer theorem):
K (xi , x j ) = φ (xi ) φ (x j ) T
(9)
Beberapa tipe dari kernel seperti linear, polynomial, splines, RBF, and MLP, dapat di manfaatkan di dalam SVM. Proses ini akhirnya menghasilkan hasil berikut ini:
⎛ l ⎞ y( x ) = sign⎜ ∑ α i yi K ( x, xi + b )⎟ ⎝ i =1 ⎠
(10)
2.2.1 Pengenalan pola dalam Support Vector Machines Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah kelas pada input space. Gambar 2.4a memperlihatkan beberapa pola yang merupakan anggota dari dua buah kelas : +1 dan –1. Pola yang tergabung pada kelas –1 disimbolkan dengan warna merah (kotak), sedangkan pola pada kelas +1, disimbolkan dengan warna biru (lingkaran). Masalah klasifikasi dapat diterjemahkan sebagai usaha menemukan garis (hyperplane) yang memisahkan antara kedua kelompok
26
tersebut. Berbagai alternatif garis pemisah (discrimination boundaries) ditunjukkan pada gambar (a)
(a) Cat : garis-garis di atas merupakan Discrimination Boundaries
27
S1
H
Margin
S2
w.x + b >= +1 w.x + b = 0 w.x + b <= -1
Class +1
Class -1
(b) Gambar 2.6 Kelebihan SVM dalam pembentukan hyperplane terbaik Hyperplane pemisah terbaik antara kedua kelas dapat ditemukan dengan mengukur margin dari hyperplane tersebut. dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane tersebut dengan pola terdekat dari masing-masing kelas. Pola yang paling dekat ini disebut sebagai support vector. Garis solid pada gambar 2.5b menunjukkan hyperplane yang terbaik, yaitu yang terletak tepat pada tengah-tengah kedua kelas, sedangkan titik merah dan biru yang berada dalam lingkaran hitam adalah support vector. Usaha untuk mencari lokasi hyperplane ini merupakan inti dari proses pelatihan pada SVM. 2.2.2
LIBSVM ( Library for Support Vector Machines) LIBSVM merupakan library untuk mendukung vector machine (SVM),
tujuannya adalah agar pengguna dapat dengan mudah menggunakan SVM
28
dimana dikatakan sebagai paket informasi, disini formulasi yang digunakan LIBSVM meliputi : C- Support Vector Classification (C-SVC), Nu-Support Vector. Classification ( v-SVC), Distribution Estimation (one class SVM), €Support Vector Regression (€-SVR), dan Nu-Support Vector Regression (vSVR). Untuk algoritma pelatihan pada SVM guna mempercepat algoritma decomposition digunakan strategi Shrinking dan Caching (Krisantus Sembiring 2007, p19) ¾ Shrinking Abaikan bounded support vector ( α = C ) karena umumnya setelah beberapa iterasi dapat diidentifikasi dan bernilai tetap sampai akhir iterasi, akibatnya jumlah variabel yang harus dioptimasi lebih sedikit. ¾ Caching Simpan nilai output fungsi kernel yang baru digunakan di memori sehingga tidak perlu dihitung ulang setiap iterasi. Parameter parameter dalam model SVM di estimasi dengan teknik LIBSVM selanjutnya parameter tersebut dioptimasi dengan menggunakan Quadratic Programming. Pencarian solusi optimal untuk permasalahan kuadratik dapat dilakukan dengan metode yang sudah ada, yaitu Metode Interior Point. Dimana pergerakkan titik – titiknya berada dalam daerah interior lalu menuju titik solusi optimalnya. Akan tetapi metode tersebut hanya dapat dilakukan pada permasalahan kuadratik yang kondisi matriks pada fungsi tujuannya bersifat positif definite, namun belum dapat mengatasi permasalahan kuadratik jika kondisi matriksnya bersifat indefinite. Sehingga dikembangkan metode NewtonKKT Interior Point untuk mengatasi permasalahan tersebut.
2.2.3
Optimasi Berdasarkan tingkat ketergantungan pada mesin, teknik optimasi dibagi
menjadi: 1. Machine dependent optimizer
29
Kode dioptimasi sehingga optimal dan efisien pada mesin tertetu saja. Optimasi ini memerlukan informasi mengenai feature yang ada pada mesin tujuan, mengambil keuntungan dari mesin tujuan agar kode lebih pendek dan eksekusinya cepat. Yang dioptimasi adalah object code 2. Machine independent optimizer Optimasi ini dapat diaplikasikan tanpa tergantung pada mesin tujuan yang dioptimasi adalah intermediate code. Karakteristik masalah optimasi meliputi : 1. Keputusan (Decisions) 2. Kendala (constraint) 3. Tujuan (objectives) Bentuk umum optimasi :
f0(X1, X2, …, Xn)
MAX (or MIN):
Subject to: f1(X1, X2, …, Xn)<=b1 : fk(X1, X2, …, Xn)>=bk : fm(X1, X2, …, Xn)=bm Perhitungan solusi Optimal : Contoh : Dan
X1 + X2 = 200
(1)
9X1 + 6X2 =1566
(2)
¾ Dari (1) kita dapatkan (2) = 200 – X1
(3)
¾ Substitusi (3) ke dalam (2), dan kita punya : 9X1 + 6 (200 – X1) =1566 Yang menghasilkan X1 = 122
30
¾ Sehingga solusi optimalnya adalah : X1=122, X2= 200 – X1=78
2.2.3.1 Linear Programming Jika seluruh fungsi bersifat linear, maka disebut dengan masalah program
linear
atau
linear
programming
(LP)
problem.
Linear
Programming merupakan salah satu teknik analisis yang memakai model matematika dengan tujuan untuk mencari, memilih, dan menentukan alternatif terbaik dari sekian alternatif yang tersedia. Alokasi optimum dilakukan dengan cara memaksimalkan / meminimumkan fungsi tujuan dengan syarat ikatan (kendala) dalam bentuk ketidaksamaan linear. Syaratsyarat tersebut adalah : ¾ Fungsi tujuan Primal → maksimum → dampak positif , keuntungan, manfaat yang ingin di maksimumkan Dual → minimum → dampak negatif, resiko-resiko, biaya-biaya, jarak dan hal-hal lain yang ingin diminimumkan ¾ Keterbatasan Sumber Daya Keterbatasan waktu, biaya, tenaga, ruangan → kendala (syarat ikatan) ¾ Perumusan Kuantitatif Model matematika → ketidaksamaan ¾ Cara penyelesaian yang bisa digunakan a. Metode Grafis b. Metode Simplex c. Program Komputer Problem dalam linear programming adalah memperhatikan penggunaan atau alokasi yang efisien dari sumberdaya-sumberdaya yang terbatas untuk mencapai tujuan yang diinginkan. (Soekartawi, 1992).
31
Nasendi dan Affendi Anwar (1985) dalam bukunya linear programming dan variasinya menyatakan bahwa ada tiga unsur yang harus dipenuhi yang dapat dirumuskan secara matematis yaitu fungsi tujuan, berbagai kendala fungsional dan kendala yang tidak boleh negatif. (Nasendi dan Affendi Anwar, 1985). Disamping itu ada 5 asumsi – asumsi dasar yang harus dipenuhi yaitu : a. Linieritas b. Proporsionalitas c. Adivitas d. Divisibilitas e. Deterministik Kelebihan-kelebihan yang dimiliki linear programming adalah : a.Mudah dilaksanakan, apabila menggunakan alat bantu komputer. b.Dapat menggunakan banyak variabel, sehingga kemungkinan untuk memperoleh pemanfaatan sumberdaya yang optimum dapat dicapai. c.Fungsi tujuan (objective function) dapat difleksiblekan sesuai dengan tujuan penelitian atau berdasarkan data yang tersedia Metode yang bisa digunakan : 1.
Primal : metode ini digunakan untuk mencari pendapatan Gross Financial Marginal (GFM) dengan keterbatasan sumberdaya, meminimumkan biaya-biaya, risiko-risiko untuk mencari nilai pendapatan maksimum.
2.
Dual : untuk sumberdaya yang langka dan pembatasan terhadap ketentuan nilai output per unit, berapakah sebenarnya jumlah nilainilai tersebut per unit sumber daya yang langka tersebut yang dapat meminimumkan total nilai dari penggunaan sumberdaya yang terbatas.
Masalah Program Linear :
32
MAX (or MIN):
c1X1+ c2X2+ …+ cnXn
Subject to:
a11X1+ a12X2+ …+ a1nXn<= b1 : ak1X1+ ak2X2+ …+ aknXn>=bk : am1X1+ am2X2+ …+ amnXn= bm
2.2.3.2 Quadratic Programming Quadratic Programming adalah program non linear. Data yang tadi nya linear menjadi non linear diselesaikan dengan Quadratic Programming. Pencarian solusi optimal untuk permasalahan kuadratik dapat dilakukan dengan metode yang sudah ada, yaitu Metode Interior Point. Dimana pergerakkan titik – titiknya berada dalam daerah interior lalu menuju titik solusi optimalnya. Akan tetapi metode tersebut hanya dapat dilakukan pada permasalahan kuadratik yang kondisi matriks pada fungsi tujuannya nya bersifat positif definite, namun belum dapat mengatasi permasalahan kuadratik jika kondisi matriks nya bersifat indefinite. Sehingga dikembangkan metode Newton-KKT Interior Point untuk mengatasi permasalahan tersebut. 1.
Metode Interior Point Metode Interior Point pertama diperkenalkan oleh Karmarkar,
adalah merupakan metode untuk menyelesaikan pemrograman linear. Metode ini banyak digunakan dalam operasipenelitian (operation research) karena efisien,reliabel dan akurat. Metode ini kemudian dikembangkan oleh James A. Momoh dkk dengan berdasarkan pada perbaikan kondisi awal sehingga bisa digunakan untuk menyelesaikan permasalahan dengan pemrograman linier maupun kuadratik (non linier) yang dikenal dengan metode EQIP (ExtendedQuadratic Interior Point method). Yang paling penting dalam algoritma ini adalah titik start awal
33
dapat ditentukan dahulu. Kemudian mencari solusi optimal dalam interior polytope yang didefinisikanoleh kendala-kendala sampai dicapai titik optimal. quadratic interior point didefinisikan sebagai berikut :
dimana : X = variabel yang tidak diketahui (unknown) n-vektor a = konstanta n-vektor bmin,bmax = konstanta m-vektor Q = matrik bujursangkar simetris A = matriks koefisien mxn dengan m < n Program linier dapat diperoleh dengan kasus khusus Q=0. Pada umumnya, dua m-vektor baru dibentuk yaitu S1 dan S2, dinamakan variabel slack, diperkenalkan untuk merubah kendala ketidaksamaan (5) menjadi bentuk persamaan:
34
35
Dengan I adalah matriks identitas mxm sehingga permasalahan optimasi quadratic (4) dan (5) mempunyai bentuk minimisasi sebagai :
Masalah optimasi quadratik yang diperlihatkan pada (11) – (13) di atas dengan mengasumsikan memiliki batas titik awal ( bounded interior point ) 2.
Metode Newton-KKT Interior Point Kondisi Karush-Kuhn-Tucker (KKT). ω dapat dicari dengan l
menggunakan ω = ∑ α i y iφ ( xi ) , dimana xi bukan nol dan α i adalah i =1
support vector. Decision boundary hanya ditentukan oleh support vector. Diketahui t , ( j 1, ..., s) menjadi titik-titik dari s support vector. Maka kita dapat melihat persamaan (11) – (18) 2.2.4
Pelatihan dengan Support Vector Machine Penggunaan SVM baik dalam bentuk supervised maupun unsupervised
pada prinsipnya menyelesaikan sebuah permasalahan quadratic programming. Oleh karena itu, proses pelatihannya hampir sama dan tahapannya dapat dilihat pada gambar 2.6, Akan tetapi untuk unsupervised learning dengan SVM data pelatihan dan data pengujian adalah data yang sama. Selain itu, untuk proses pelatihannya dapat juga hanya menggunakan sebagian data dari data pengujian sehingga proses waktu pelatihan menjadi lebih singkat, tetapi hal ini mungkin menurunkan akurasi pada tahap pengujian.Sedangkan untuk supervised learning justru sebaliknya, dapat meningkatkan akurasi pada tahap pengujiannya.
36
Sehingga dalam penulisan skripsi ini, penulis menggunakan metode supervised
Parameter
Feature vector
learning.
Gambar 2.7 Pelatihan dengan SVM
2.2.5 Kernel Batas kemampuan komputasi fungsi linier dibahas pada tahun 1960an oleh Minsky dan Papert. Secara umum, pada kasus dunia nyata, pengklasifikasian domain permasalahan memerlukan ekspresi yang lebih kompleks dibanding fungsi linier (misalnya fungsi polynomial, eksponensial, atau fungsi periodik). Trik kernel menawarkan solusi dengan memproyeksikan data ke dalam ruang dimensi yang lebih tinggi (disebut juga dengan feature space) untuk meningkatkan kemampuan komputasi fungsi linier. Yang dimaksud dengan dimensi di sini merupakan ruang dimensi vektor w berada, yang akan mempengaruhi besar nilai n. Adapun pemetaan ke ruang dimensi yang lebih tinggi dilakukan untuk memetakan input ke ruang dimensi yang baru, di mana diharapkan bahwa pada ruang dimensi yang baru, domain input dapat dipisahkan
37
oleh suatu vektor sederhana, yang tidak dapat dilakukan sebelumnya pada ruang dimensi awal. Adapun salah satu pemetaan ulang data, dapat dicapai dengan memetakan x ≡ ( x1 ,..., x 2 ) → φ ( x) ≡ (φ1 ( x),..., φ d ( x)), d < n. Sehingga fungsi penentu berubah menjadi : 1. Kernel Linear
Gambar 2.8 Contoh pemetaan Kernel Linear 2. Kernel Polynomial
k(x, x') = (γxx'+coef)degree
38
Gambar 2.9 Contoh pemetaan Kernel Polynomial X = Support Vector X’ = Besarnya Vector Fungsi Kernel polynomial adalah directional, yaitu output tergantung pada arah 2 vector dalam ruang dimensi rendah, hal ini disebabkan produksi titik di dalam kernel yang menunjukkan bentuk dua dimensi yang jumlahnya banyak. Semua vector dengan arah yang sama akan lebih tinggi dari output kernelnya, yang besar dari outputnya juga tergantung pada besarnya vektor. 3. Kernel Radial Basis Function
⎛ x − x' k ( x, x' ) = exp⎜ − ⎜ 2σ 2 ⎝
2
⎞ ⎟ ⎟ ⎠
39
Gambar 2.10 Contoh Pemetaan Kernel RBF
Gambar 2.11 Kernel RBF. Kiri : Original space. Kanan : Feature space Fungsi radial basis yang sering digunakan adalah fungsi gaussian karena mempunyai sifat lokal, yaitu bila input dekat dengan rata – rata (pusat), maka fungsi akan menghasilkan nilai satu, sedangkan bila input jauh dari rata – rata, maka fungsi memberikan nilai nol. Ada beberapa fungsi radial basis diantaranya adalah :
40
1. Fungsi Thin Plate Spline f (z) = ( z - m) 2 log(z - m) 2. Fungsi Multikuadratik f (z) =[( z - m) 2 +s 2 ]1/ 2 3. Fungsi Invers Multikuadratik f (z) =[( z - m) 2 +s 2 ]-1/ 2 4. Fungsi Gaussian f (z) = exp[-(z - m)2 / s 2 ] .
4. Kernel Sigmoid
Gambar 2.12 Contoh Pemetaan Kernel Sigmoid
41
2.2.6 Klasifikasi Hyperplane Dalam bagian ini, akan dijelaskan sebuah algoritma pelatihan hyperplane yang dapat dilaksanakan di ruang dot product (seperti ruang fitur yang sudah kami perkenalkan sebelumnya). Seperti yang dijelaskan di bagian sebelumnya, untuk belajar desain algoritma efektivitas statistik yang dapat dikontrol, satu kebutuhan yang akan datang dengan satu kelas fungsi yang dapat menghitung kapasitas.
w, x + b = 0 where w ∈ H , b ∈ ℜ,
(19)
Berhubungan dengan fungsi keputusan
f ( x) = sgn( w, x + b),
(20)
Dan menawarkan sebuah algoritma pelatihan untuk masalah-masalah yang dipisahkan oleh hyperplane (terkadang disebut juga sebagai linearly separable) yang diistilahkan Generalized Potret, untuk membuat f dari data empiris. Dalam kasus ini, kita harus melakukan beberapa tambahan untuk mencari vektor normal yang mengarah ke margin terbesar. Untuk membuat hyperplane yang optimal, kita harus memecahkan minimizeτ ( w) = w∈H ,b∈ℜ
1 w 2
2
mengacu kepada yi ( w, xi + b) ≥ 1 untuk semua i = 1,…,m.
(21) (22)
Fungsi τ di (21) disebut fungsi objektif, sementara (22) disebut inequality constraints. Bersama-sama, mereka membentuk yang disebut masalah optimisasi konstrain. Masalah semacam ini akan berhadapan dengan pengenalan Lagrange multipliers αI ≥ 0 dan sebuah lagrangian
42
L( w, b, α ) =
1 2 m w − ∑ α i ( y i ( xi , w + b) − 1). 2 i =1
(23)
Lagrangian L harus diminimalkan dengan memandang primal variables w dan b dan memaksimalkan dengan memandang ke dual variables αI (dengan kata lain poin penentu harus sudah ditemukan). Pernyataan bahwa pada poin penentu, yang derivatif dari L dengan memandang primal variable harus dihilangkan, ∂ ∂ L( w, b, α ) = 0dan L( w, b, α ) = 0, ∂w ∂b
(24)
mengarah ke m
∑α i =1
i
yi = 0
(25)
dan m
w = ∑ α i y i xi
(26)
i =1
Vektor solusi yang dijelaskan dengan maksud dari sebuah subset dari pola pelatihan, disebut Support Vectors. Dengan kondisi KKT,
α i [yi ( xi , w + b ) − 1] = 0 untuk semua i = 1, … , m ,
(27)
Dengan menggantikan (25) dan (26) ke dalam Lagrangian, pertama hilangkan primal variables w dan b, tiba pada apa yang disebut optimasi dual problem, di mana masalah yang biasanya dipecahkan dalam pelatihan:
43
1 m maximize W (α ) = ∑ α i − ∑ α iα j y i y j xi , x j α ∈ℜ m 2 i , j =1 i =1 m
Mengarah ke αi ≥ 0 untuk setiap i = 1,…,m dan
m
∑α i =1
i
(28)
yi = 0
(29)
Dengan menggunakan (28), fungsi keputusan hyperplane dapat ditulis sebagai berikut ⎛ m ⎞ f ( x) = sgn ⎜ ∑ y iα i x, xi + b ⎟, ⎝ i =1 ⎠
Gambar.2.13 Support Vector Menggunakan Kernel RBF
2.2.7
Multikelas Support Vector Machine Dalam perancangan aplikasi Handwriting Recognition digunakan SVM
sebagai pengklasifikasi atau classifier, untuk mengenali karakter apa yang menjadi input ke dalam aplikasi ini.
44
Pada awalnya SVM dirancang hanya untuk menyelesaikan masalah klasifikasi biner, yaitu dari data – data yang ada, diklasifikasikan menjadi dua kelas. SVM memiliki pendekatan yang berbeda dibanding NN, dimana SVM mencari hyperplane pemisah dua kelas yang paling optimal. Untuk mengklasifikasikan data yang terdiri dari lebih dari dua kelas, SVM tidak dapat langsung digunakan. Ada beberapa metode yang dapat dipakai untuk mengatasi masalah klasifikasi multiclass SVM yaitu : One-vs-One (OVO), One-vs-All (OVA) / One-vs-Rest, dan Directed Acyclic Graph Support Vector Machine (DAGSVM). Untuk menyelesaikan masalah klasifikasi multiclass pada SVM
digunakan
metode One_vs_one (OVO), One_vs_all (OVA) dan Directed Acyclic Graph Support Vector Machine (DAGSVM). 1.
One-vs-One (OVO) buah model klasifikasi biner (k
Dengan metode ini, dibangun
adalah jumlah kelas). Setiap model klasifikasi dilatih pada data dari dua kelas. Untuk data pelatihan dari kelas ke – i dan kelas ke – j, dilakukan pencarian solusi untuk persoalan optimasi konstrain. Terdapat beberapa metode untuk melakukan pengujian setelah keseluruhan k(k1)/2 model klasifikasi selesai dibangun. Salah satunya adalah metode voting.
Table 2.1 Contoh 6 SVM biner dengan metode OVO yi = 1
yi = -1
Hipotesa
Kelas 1
Kelas 2
f12(x)
Kelas 1
Kelas 3
f13(x)
Kelas 1
Kelas 4
f14(x)
Kelas 2
Kelas 3
f23(x)
Kelas 2
Kelas 4
f24(x)
Kelas 3
Kelas 4
f34(x)
45
xi
f12(x)
Kelas 1
f13(x)
f14(x)
f23(x)
f24(x)
f34(x)
Kelas 1
Kelas 1
Kelas 2
Kelas 4
Kelas 4
Gambar 2.14 Contoh klasifikasi dengan metode OVO
Jika data x dimasukkan ke dalam fungsi hasil pelatihan dan hasilnya menyatakan x adalah kelas i, maka suara untuk kelas i ditambah satu. Kelas dari data x akan ditentukan dari jumlah suara terbanyak. Jika terdapat dua buah kelas yang jumlah suaranya sama, maka kelas yang indeksnya lebih kecil dinyatakan sebagai kelas dari data. 2.
One-vs-All (OVA) / One-vs-Rest Dengan metode ini, dibangun k buah model SVM biner (k adalah jumlah
kelas). Setiap model klasifikasi ke-i dilatih dengan menggunakan keseluruhan data, untuk mencari solusi permasalahan. Contohnya, terdapat permasalahan klasifikasi dengan 4 buah kelas. Untuk pelatihan digunakan 4 buah SVM biner seperti pada tabel 1 dan penggunaannya dalam mengklasifikasi data baru dapat dilihat pada Gambar 5. Table 2.2 Contoh 4 SVM biner dengan metode OVA yi = 1
yi = -1
Hipotesa
Kelas 1
Bukan Kelas 1
f1(x)
Kelas 2 Kelas 3
Bukan Kelas 2 Bukan Kelas 3
f2(x) f3(x)
Kelas 4
Bukan Kelas 4
f4(x)
46
f1(x)
xi
f2(x)
Kelas 1 Kelas 2
f3(x) f4(x)
Kelas 3
Kelas 4
unknown
Gambar 2.15 Contoh klasifikasi dengan metode OVA 3.
Directed Acyclic Graph Support Vector Machine (DAGSVM) Dengan metode ini, sama dengan metode OVO, pelatihan dilakukan
dengan membangun
buah model klasifikasi SVM biner. Akan tetapi, pada
saat pengujian digunakan binary directed acyclic graph. Setiap node merupakan model SVM biner dari kelas ke – i dan kelas ke – j. Pada saat memprediksi kelas data pengujian, maka hipotesis dimulai dari simpul akar, kemudian bergerak ke kiri atau ke kanan tergantung nilai output dari hipotesis. Table 2.3 Contoh 6 SVM biner dengan metode DAGSVM
yi = 1
yi = -1
Hipotesa
Bukan Kelas 2
Bukan Kelas 1
f12(x)
Bukan Kelas 3
Bukan Kelas 1
f13(x)
Bukan Kelas 4
Bukan Kelas 1
f14(x)
Bukan Kelas 3
Bukan Kelas 2
f23(x)
Bukan Kelas 4
Bukan Kelas 2
f24(x)
Bukan Kelas 4
Bukan Kelas 3
f34(x)
47
f12(x)
xi
Not 1
Not 2
f13(x)
f 23(x) Not 2 34
Not 4 f
Kelas 3
(x) Not 3 Kelas 4
Not 3
Not 1 f34(x)
Not 3
12
Not 4
f (x)Not 2
Kelas 2
Kelas 4
Not 4
f14(x)
Kelas 1
Not 1
Kelas 4
Not 4
Not 3
Kelas 3
Kelas 4
Gambar 2.16 Contoh klasifikasi dengan metode DAGSVM
Dalam tugas akhir ini, digunakan metode OVO, dikarenakan pustaka LibSVM yang kami pakai sudah built-in dalam pemakaian multiclass SVM dengan metode OVO.
2.2.8 Klasifikasi Linear Dalam proses supervised learning, mesin diberikan kumpulan contoh data (disebut juga input), dan label yang terasosiasi (disebut juga output), dan contoh input dalam bentuk vektor sehingga domain input merupakan himpunan real. Setelah contoh data dan labelnya tersedia, sejumlah metode dapat dipilih untuk melakukan proses klasifikasi pada masalah tersebut. Salah satu metode yang paling dimengerti dan paling sederhana adalah menggunakan metode fungsi linier (1) Linear classifier biasa digunakan untuk klasifikasi biner, yaitu kasus di mana domain outputnya hanya terdiri dari 2 kemungkinan saja (kelas positif dan kelas negatif). Klasifikasi ini biasanya dilakukan menggunakan fungsi
dengan
aturan untuk sembarang input x, akan diberikan label kelas +, apabila f(x) >= 1,
48
dan sebaliknya kelas –, apabila f(x) <= -1. Karena adalah fungsi linear, maka dapat lebih lanjut ditulis sebagai: f(x)
= (w,x) + b =
∑
n
i −1
wi xi + b
= (w1x1) + (w2x2) + (w3x3) + … + (wnxn) + b
(2)
Di sini, w merupakan vektor di ruang dimensi n, sehingga wi (w1 sampai wn) merupakan komponen – komponen nilai penyusun vektor w di ruang dimensi n, dan nilai dari vektor w disinilah yang akan menjadi classifier.
Gambar 2.17 Sebuah vektor sebagai pemisah 2 daerah W dan b merupakan parameter fungsi yang akan ditentukan dari proses pelatihan dari contoh – contoh data yang diberikan ke klasifikasi linear yang bersangkutan, dan hasilnya akan diberikan oleh sgn ( f ( x )) .Dalam proses pengenalan data dan klasifikasi dalam tugas akhir ini kami menggunakan pendekatan algoritma SupportVector Machine.
49
Gambar 2.18 Contoh klasifikasi biner dari yang paling mudah (kiri) ke kanan yang paling kompeks (kanan)
2.3 Machine Learning Machine Learning adalah sebuah bidang dari ilmu kecerdasan buatan yang menaruh perhatian lebih pada penelitian tentang algoritma komputer yang dapat memperbaiki dirinya sendiri secara otomatis melalui pengalaman. Mesin akan belajar dari input-input yang diberikan sebelumnya untuk memperbaiki performa di masa depan. Fokus utama dari machine learning adalah untuk secara otomatis menghasilkan model, seperti rule dan pola, dari data. Algoritma-algoritma pada machine learning dapat dikelompokkan ke dalam dua kelompok, yaitu: •
Supervised Learning
•
Unsupervised Learning
2.3.1 Supervised Learning Supervised learning adalah teknik pelatihan mesin dengan membuat suatu fungsi dari data latihan. Data latihan terdiri dari pasangan nilai input (biasa dalam bentuk vektor), dan output yang diharapkan untuk input yang bersangkutan. Tugas dari mesin supervised learning adalah memprediksi nilai
50
fungsi untuk semua nilai input yang mungkin, setelah melalui sejumlah pelatihan. Contohnya pada pengenalan pola. Tujuan pada pembelajaran supervised learning adalah untuk menentukan nilai bobot-bobot koneksi di dalam jaringan sehingga jaringan dapat melakukan pemetaan ( mapping) dari input ke output sesuai yang diinginkan. Pemetaan ini ditentukan melalui satu set pola contoh atau data pelatihan (training data set). Setiap pasangan pola p terdiri dari vektor input xp dan vektor target tp. Setelah selesai pelatihan, jika diberikan masukan xp seharusnya jaringan menghasilkan nilai output tp. Besarnya perbedaan antara nilai vektor target dengan output aktual diukur dengan nilai error yang disebut juga dengan cost function:
di mana n adalah banyaknya unit pada output layer. Tujuan dari training ini pada dasarnya sama dengan mencari suatu nilai minimum global dari E. Untuk mencapai tujuan ini, mesin harus dapat melakukan proses generalisasi dari data latihan yang diberikan, untuk memprediksikan nilai output dari input yang belum pernah diberikan sebelumnya. Beberapa pendekatan dan algoritma yang umum dipakai adalah system syaraf buatan, backpropagation, dan Support Vector Machine. Pendekatan dan algoritma pada supervised learning, dapat penulis bahas misal nya neural network. Neural network (Jaringan Saraf Tiruan) sudah mulai banyak dimanfaatkan sebagai solusi terhadap berbagai macam kasus yang muncul beberapa dekade terakhir, sejarah ANN (Artificial Neural Network) menunjukan pembahasan terhadap masalah ini muncul sekitar awal tahun 1900an namun implementasinya baru banyak muncul beberapa dekade terakhir. Pemanfaatan ANN juga mulai merambah dunia security khususnya untuk
51
memecahkan masalah-masalah yang sifatnya tidak tetap sehingga sulit untuk di pecahkan dengan menggunakan tehnik pemrograman konvensional yang ada saat ini. Artificial Neural Network merupakan suatu jaringan saraf tiruan yang dibangun untuk meniru cara kerja otak manusia. Dengan jaringan saraf tiruan maka kita dapat memberikan semacam kecerdasan pada sistem, dimana sistem tersebut akan diberikan waktu untuk 'belajar' dan kemudian diharapkan dari proses belajarnya, sistem bisa memberikan solusi dari suatu kasus. Analoginya seperti mengajarkan seorang anak kecil untuk mengetahui bentuk kursi, kita akan menunjukan pada anak tersebut berbagai macam bentuk kursi dan bukan kursi. Kita akan memperlihatkan mana saja yang termasuk kursi dan mana yang bukan, proses ini disebut proses training. Setelah proses training selesai, maka tiba waktunya untuk melakukan test terhadap anak tersebut dengan menunjukan suatu bentuk kursi dan menanyakan apakah itu termasuk kursi atau bukan. Hal yang menarik adalah pada saat kita menunjukan suatu bentuk kursi yang belum pernah diajarkan pada anak tersebut dan apabila itu memang variasi dari kursi (dengan ciri misalnya: kakinya ada 4, ada pegangan tangannya, bentuknya seperti angka 4, dll) maka dia dapat mengambil kesimpulan bahwa benda tersebut adalah kursi, apabila jawaban si anak salah maka kita kembali melatihnya (proses training) dengan memasukan bentuk kursi yang baru tadi kedalam data latih, sehingga si anak dapat mengambil kesimpulan bahwa benda tersebut (dan yang mirip benda tersebut dimasa yang akan datang) adalah kursi. Hal yang sama terjadi pada sistem dimana sistem akan diajarkan dengan berbagai macam contoh (disebut data latih) dan kemudian diharapkan sistem akan dapat mengambil keputusan atas suatu masalah yang berhubungan dengan data latih sistem tersebut. Pemanfaatan ANN sekarang ini sudah cukup banyak dan telah diterapkan pada berbagai bidang, misalnya untuk mengetahui keadaan bursa saham di masa yang akan datang berdasarkan keadaan saat ini, menentukan jenis kelamin seseorang berdasarkan bentuk wajah, dll.
52
Dasar algoritma ANN : Mesin ANN bekerja pada 2 mode yang pertama adalah trainning dan yang kedua adalah execution. Pada saat proses training, kita akan melatih sistem dengan memberikannya sebanyak mungkin contoh data input serta output yang akan dihasilkan oleh data input tersebut. Contoh paling mudah adalah mengajarkan sistem operasi penjumlahan: input ke-1 = 0.1 input ke-2 = 0.2 output = 0.3 pada contoh tersebut, kita mengajarkan pada sistem apabila inputan terdiri dari angka "0.1" dan "0.2" maka outputnya adalah "0.3". Jika hanya diberikan satu contoh maka sistem tidak akan belajar dengan baik, untuk itu sistem sebaiknya diberikan contoh data dengan jumlah yang sangat besar sehingga kecerdasan sistem bisa lebih handal. Konsep pertama yang harus di pahami sebelum masuk pada tahap coding adalah layer. ANN umumnya terdiri dari 3 layer, yaitu "input layer", "hidden layer", dan "output layer". Ketiga layer inilah yang akan membentuk topologi ANN. Tiap layer terdiri dari unit-unit node yang jumlahnya dapat kita tentukan sendiri, bisa dibayangkan bahwa tiap node pada ANN ibaratnya seperti neuron pada otak manusia. Jumlah node pada input layer tergantung pada jumlah data input yang akan masuk pada sistem, misalnya pada operasi penjumlahan diatas maka jumlah node pada input layer sebanyak 2 buah.Jumlah node pada hidden layer bervariasi, dan terdapat banyak teori yang dapat menjelaskan bagaimana mencari jumlah node yang tepat pada hidden layer, namun pada umumnya 5 buah node pada hidden layer suatu ANN sudah mencukupi untuk memecahkan berbagai macam kasus. Node pada output layer tergantung dari jumlah output
53
pada sistem, pada contoh operasi penjumlahan diatas dapat dilihat bahwa jumlah node di output layernya sebanyak 1 buah. Konsep kedua yang penting adalah nilai Error minimum yang diharapkan. Pada saat ANN di inisialisasi akan dibangkitkan nilai random untuk koneksi antar node dari suatu layer dengan layer sesudahnya, jadi antar node-node di hidden layer saling terkoneksi satu sama lain dengan node-node di hidden layer, dan antar node-node di hidden layer akan saling terkoneksi satu sama lain dengan node-node pada output layer. Nilai koneksi antar node tersebut sering disebut 'bobot'. Nilai bobot inilah yang akan menentukan kecerdasan suatu sistem. Pada saat proses training, nilai bobot tersebut akan terus berubah sehingga didapatkan kesesuaian antara input dengan output dengan Error minimum. Dengan kata lain, pada proses training kita akan menentukan nilai minimum error yang bisa di tolerir oleh sistem,seperti yang disampaikan diatas bahwa sistem tidak akan memberikan kepastian jawaban untuk suatu kasus yang tidak pernah dilatihkan kepadanya, pasti ada nilai Error dari jawaban sistem dengan jawaban yang seharusnya, nah nilai Error tersebut yang harus di definisikan oleh kita sebelum melatih sistem sehingga sistem bisa menjawab dengan tingkat kebenaran semaksimal mungkin (misal: tingkat kebenaran sistem 99,9999% dengan nilai Error 0.0001). Arsitektur Komputasi Neural 1.
Memiliki beberapa hal yang menarik komputasi lokal, adaptive interaction between Paralel
2.
Simple processing elements
3.
High degree of interconnections
4.
Masalah sering direpresentasikan dalam struktur
5.
Memungkinkan implementasi hardware (VLSI, optical)
54
Selain NN ada juga Support vector machine, Baik SVM maupun NN pembelajarannya dilakukan dengan menggunakan pasangan data input dan data output berupa sasaran yang diinginkan. Pembelajaran dengan cara ini disebut dengan pembelajaran terarah (supervised learning). Dengan pembelajaran terarah ini akan diperoleh fungsi yang menggambarkan bentuk ketergantungan input dan outputnya. Selanjutnya, diharapkan fungsi yang diperoleh mempunyai kemampuan generalisasi yang baik, dalam arti bahwa fungsi tersebut dapat digunakan untuk data input di luar data pembelajaran. SVM (support vector machine), yang dikembangkan oleh Vapnik.Algoritma ini mentransform input ke dimensi yang lebih tinggi (higher dimensional feature space) dengan menggunakan nonlinear mapping (fungsi kernel). Dengan kernel yang sesuai, SVM menentukan hyperplane yang maksimum atau pembatas (decision boundary) sedemikian hingga jarak antara hyperplane dan objek yang terdekat dalam setiap klas adalah maksimum
2.3.2 Unsupervised Learning Unsupervised learning adalah sebuah teknik pelatihan mesin dimana mesin mencari
bagaimana
data-data
yang
ada
diorganisasikan.
Pada
proses
unsupervised learning, data yang diberikan adalah data yang tidak memiliki label (unlabeled), maksudnya tidak diketahui sebelumnya data yang diberikan termasuk kelompok yang mana contohnya clustering dan fuzzy. Clustering
dapat
didefinisikan
sebagai
proses
mengelompokkan
sekumpulan objek sedemikian hingga objek dalam satu grup lebih serupa karakteristiknya dibandingkan dengan objek-objek di grup-grup yang lain. Clustering juga dikenal sebagai unsupervised learning karena objek-objek dalam database tidak memiliki kelas (tipe) yang membedakan antara satu objek dengan objek yang lain. Analisa grup sangat bermanfaat untuk mengetahui dan memahami distribusi data dan sering sekali digunakan sebagai proses awal sebelum teknik-teknik data mining lain digunakan.Secara garis besar teknik-
55
teknik clustering dapat dikategorikan dalam 3 kelompok. Teknik clustering berdasarkan jarak (distance-based), berdasarkan kepadatan (density-based), and teknik clustering berdasarkan hirarki (hierarchy-based). Hierarchy-based clustering terbagi menjadi 2 jenis yaitu agglomerative dan divisive. Pendekatan secara agglomerative memulai clustering dengan mengambil setiap objek sebagai objek yang terpisah satu sama lainnya dan menggabungkannya satu persatu berdasarkan suatu metric (measurement). Sebaliknya, divisive memulai clustering dengan menganggap bahwa semua objek berada dalam satu cluster kemudian memecahkannya satu persatu sehingga pada akhirnya setiap objek merupakan suatu cluster tersendiri. Unsupervised learning meminta sistem untuk terus melakukan pembelajaran dengan mengevaluasi model, mengukur performansi sistem pada setiap iterasi.
