. BAB II LANDASAN TEORI
2.1
Pengenalan Jenis Kendaraan Menggunakan Statistical Algorithm dan Support Vector Machine [11] Dalam penelitian tersebut dibangun sistem pengenalan jenis kendaraan
otomatis. Jenis kendaraan yang dapat dikenali yaitu sedan/city car, SUV/MPV, bus, dan truk. Sejumlah tahap yang dilakukan oleh sistem yaitu ekstraksi background, segmentasi objek bergerak, pemrosesan awal (preprocessing), pelabelan komponen, menghilangkan bayangan, dan klasifikasi jenis kendaraan. Statistical algorithm digunakan untuk mencari background melalui analisis terhadap semua piksel pada frame masukan. Analisis dilakukan untuk mengelompokkan informasi warna yang hampir sama pada tiap piksel berdasarkan batas (threshold) yang ditentukan. Analisis tersebut dilakukan pada 30 frame pertama pada video masukan hingga didapatkan piksel dari background dengan probabilitas kemunculan melebihi 0,6. Jika tidak ditemukan maka piksel background dicari kembali pada 30 frame selanjutnya. Tahap
selanjutnya
yaitu
segmentasi
objek
bergerak
dilakukan
menggunakan metode background subtraction, yaitu mengurangkan citra background terhadap frame yang dibaca dari video masukan. Setelah objek ditemukan kemudian dilakukan sejumlah tahap permrosesan awal untuk menghilangkan noise dan memperbaiki hasil segmentasi. Kemudian dilakukan pelabelan terhadap objek dan penghilangan bayangan. Objek yang telah dideteksi melalui sejumlah proses sebelumnya kemudian diklasifikasikan menggunakan dua metode. Metode pertama yaitu membedakan jenis kendaraan berdasarkan panjang visual. Dimana rentang panjang jenis kendaraan sedan/city car 3.5-4.2 meter, SUV/MPV 4.2-5.2 meter, bus dan truk lebih dari 5.2 meter. Jika dari metode pertama didapat kendaraan jenis besar (panjang lebih dari 5.2 meter), maka dilakukan klasifikasi lebih lanjut dengan metode kedua.
4
5
Dengan metode kedua jenis kendaraan dibedakan berdasarkan tekstur dengan menggunakan gabor filter. Ciri yang diekstrak yaitu rata-rata, standar deviasi, dan kemencengan dari output operasi konvolusi dengan gabor filter. Ciri tersebut kemudian dijadikan sebagai parameter pembelajaran algoritma SVM. Dari tahap pembelajaran akan didapat fungsi pemisah yang digunakan sebagai model pengenalan jenis kendaraan bus dan truk. Pada penelitian tersebut metode Statistical Algorithm dan SVM dalam pengenalan jenis kendaraan memiliki performa yang cukup baik. Hal ini dibuktikan dengan rata-rata akurasi pengenalan jenis kendaraan sedan/city car sebesar 92.11%, SUV/MPV sebesar 82.44%, bus sebesar 86.11%, dan truk sebesar 67.86%. 2.2
Visual Categorization with Bag of Keypoints [12] Pada penelitian tersebut dicoba untuk membuat model klasifikasi objek
visual yang generik, dalam arti model dapat mengatasi variasi pandangan, pencitraan, pencahayaan, seperti layaknya di dunia nyata. Metode yang digunakan yaitu klasifikasi citra dengan menggunakan bag of keypoint. Bag of keypoint berkoresponden dengan histogram kemunculan pola citra yang diberikan. Csurka, dkk melakukan ekstraksi fitur citra menggunakan Scale Invariant Feature Transform (SIFT). SIFT digunakan karena pada penelitian terdahulu diketahui bahwa SIFT memiliki performa terbaik. Hasil ekstraksi kemudian dikuantisasi menggunakan algoritma k-means untuk membentuk kamus visual, yang merupakan histogram kemunculan fitur pada citra. Histogram kemudian dijadikan parameter pembelajaran menggunakan algoritma Naive Bayes dan SVM. Pada penelitian dilakukan beberapa percobaan, mula-mula dicari pengaruh jumlah klaster terhadap akurasi dan evaluasi performa klasifikasi menggunakan Naive Bayes. Kemudian eksplorasi performa dilakukan juga pada SVM terhadap problem yang sama. Pada dua percobaan diatas data yang digunakan adalah data yang dikumpulkan oleh Csurka, dkk. Data terdiri dari 1776 citra dengan tujuh kelas: wajah, bangunan, pepohonan, mobil, telepon, sepeda, dan buku. Pada percobaan terakhir digunakan data Fergus, dkk [13] yang terdiri dari 3751 citra dengan lima kelas: wajah, pesawat (samping), mobil (depan), mobil (samping), dan motor (samping).
6
Pada percobaan pertama digunakan jumlah klaster k = 1000 dan k = 2500. Diketahui dengan k = 1000 dihasilkan performa akurasi dan kecepatan yang lebih baik. Pada percobaan kedua kemudian diketahui bahwa dengan kasus yang sama SVM lebih baik dibandingkan Naive Bayes. Persentase rata-rata kesalahan dengan SVM yaitu sebesar 15% sedangkan Naive Bayes sebesar 28%. Pada percobaan terakhir menggunakan data [13] didapatkan hasil yang lebih baik dibandingkan dengan dua percobaan pertama. Namun hasil tersebut tidak dapat langsung dibandingkan secara langsung karena pada penelitian Fergus, dkk [13], problem klasifikasi yang dilakukan adalah klasifikasi dua kelas antara objek dengan latar belakang. Sedangkan pada percobaan dengan data yang dikumpulkan Csurka, dkk merupakan problem klasifikasi multi kelas. 2.3
Computer Vision Computer vision adalah cabang ilmu komputer dan rekayasa yang memiliki
tujuan untuk membuat komputer yang dapat melihat dan mengerti kejadian di dunia luar [14]. Computer vision dikhususkan untuk menemukan algoritma, representasi data, dan arsitektur komputer yang mewujudkan prinsip-prinsip yang mendasari kemampuan visual [15]. Computer vision merupakan kombinasi antara pengolahan citra dan pengenalan pola. Berikut adalah bagian dari computer vision : 1. Pengolahan Citra : bidang yang berhubungan dengan proses transformasi citra/gambar. Proses ini bertujuan untuk mendapatkan kualitas citra yang lebih baik. 2. Pengenalan Pola : bidang yang berhubungan dengan proses identifikasi objek pada citra atau interpretasi citra. Proses ini bertujuan untuk mengekstrak informasi/pesan yang disampaikan oleh gambar/citra. 2.3.1
Tahapan yang terjadi pada Computer Vision Tahapan yang terjadi pada computer vision umumnya dimulai dari image
aquisition, image preprocessing, image analysis, dan image undestanding. Berikut penjelasan dari empat tahapan dalam computer vision.
7
2.3.1.1 Image Acquisition Image Acquisition pada manusia dimulai dengan mata kemudian informasi visual diterjemahkan ke dalam suatu format yang kemudian dapat dimanipulasi oleh otak. Senada dengan proses di atas, computer vision membutuhkan sebuah mata untuk menangkap sebuah sinyal visual. Umumnya mata pada computer vision adalah sebuah kamera video, menerjemahkan sebuah scene atau gambar kemudian sinyal listrik ini diubah menjadi bilangan biner yang akan digunakan oleh komputer untuk pemrosesan. Keluaran dari kamera adalah berupa sinyal analog, dimana frekuensi dan amplitudonya (frekuensi berhubungan dengan jumlah sinyal dalam satu detik, sedangkan amplitudo berkaitan dengan tingginya sinyal listrik yang dihasilkan) merepresentasikan detail kecerahan (brightness) pada scene. Kamera mengamati sebuah kejadian pada satu jalur dalam satu waktu, memindainya dan membaginya menjadi ratusan garis horizontal yang sama. Tiap‐tiap garis membuat sebuah sinyal analog yang amplitudonya menjelaskan perubahan brightness sepanjang garis sinyal tersebut. Karena komputer tidak bekerja dengan sinyal analog, maka sebuah analog‐to‐digital converter (ADC), dibutuhkan untuk memproses semua sinyal tersebut oleh komputer. ADC ini akan mengubah sinyal analog yang direpresentasikan dalam bentuk informasi sinyal tunggal kedalam aliran sejumlah bilangan biner data raw yang akan diproses. 2.3.1.2 Image Processing Tahapan berikutnya computer vision akan melibatkan sejumlah manipulasi utama (initial manipulation) dari data binary tersebut. Image processing membantu peningkatan dan perbaikan kualitas image, sehingga dapat dianalisa dan di olah lebih jauh secara lebih efisien. Image processing akan meningkatkan perbandingan sinyal terhadap noise (signal‐to‐noise ratio = s/n). Sinyal‐sinyal tersebut adalah informasi yang akan merepresentasikan objek yang ada dalam image. Sedangkan noise adalah segala bentuk interferensi, kekurang pengaburan, yang terjadi pada sebuah objek.
8
2.3.1.3 Image Analysis Image analysis akan mengeksplorasi scene ke dalam bentuk karateristik utama dari objek melalui suatu proses investigasi. Sebuah program komputer akan mulai melihat melalui bilangan biner yang merepresentasikan informasi visual untuk mengidentifikasi fitur‐fitur spesifik dan karekteristiknya. Lebih khusus lagi program image analysis digunakan untuk mencari tepi dan batas‐batasan objek dalam image. Sebuah tepian (edge) terbentuk antara objek dan latar belakangnya atau antara dua objek yang spesifik. Tepi ini akan terdeteksi sebagai akibat dari perbedaan level kecerahan pada sisi yang berbeda dengan salah satu batasnya. 2.3.1.4 Image Understanding Ini adalah langkah terakhir dalam proses computer vision, yang mana objek spesifik dan hubungannya diidentifikasi. Pada bagian ini akan melibatkan kajian tentang teknik-teknik artificial intelligent. Understanding berkaitan dengan template matching yang ada dalam sebuah scene. Metoda ini menggunakan program pencarian dan teknik penyesuaian pola (pattern matching techniques). 2.3.2
Klasifikasi Citra Klasifikasi citra adalah salah satu tugas utama di bidang computer vision
dan pengolahan citra. Berbagai aplikasi computer vision melibatkan klasifikasi citra mulai dari mesin pencarian gambar, pendaftaran citra, pengenalan objek dan lokalisasi tempat dalam sistem navigasi [16]. Pada dasarnya, tugas klasifikasi citra terdiri dari membentuk representasi yang tepat dari gambar dan kemudian membandingkan representasi ini dalam rangka untuk menemukan korespondensi. Klasifikasi citra adalah masalah yang menantang dalam menemukan kesamaan diantara gambar yang mewakili objek yang sama secara reliabel berdasarkan deskripsi benda atau dengan kata lain menggambarkan sebuah gambar berdasarkan adegan semantik yang diwakilinya [17], [18]. Sejumlah teknik klasifikasi citra yang didasarkan pada deskriptor fitur diantaranya yaitu SIFT, SURF, FAST dan ORB. Klasifikasi citra menggunakan deskriptor fitur terdiri dari tiga tahap yaitu deteksi fitur, ekstraksi fitur dan pencocokan fitur.
9
Tabel 2.1 Pratinjau berbagai macam feature detector [4]
2.3.2.1 Deteksi Fitur Fitur adalah poin unik atau lokasi khas pada sebuah citra yang mudah untuk dibandingkan, seperti tepian (edge), sudut (corner), blob, dan lainnya. Fitur tersebut dapat berupa titik (point), kurva kontinu (continous curve), atau daerah yang saling terhubung (connected regions). Jadi, deteksi fitur dapat didefinisikan sebagai: metode yang digunakan untuk menemukan fitur pada citra dengan membuat keputusan di setiap titik pada citra apakah dapat dipilih sebagai fitur yang dimaksud. Deteksi fitur merupakan langkah dasar dalam kesuksesan klasifikasi citra. Hal ini disebabkan fakta bahwa detektor fitur harus menemukan interest point yang sama secara reliable ketika kondisi melihat berubah. 2.3.2.2 Ektraksi Fitur Setelah fitur telah terdeteksi, daerah sekitar setiap fitur diekstrak dan menghasilkan sebuah vektor fitur (feature vector/feature desciptor). Vektor fitur adalah vektor berdimensi n yang mewakili dan menjelaskan suatu objek berdasarkan pada beberapa pengukuran pada fitur gambar. Pengukuran ini bisa menjadi simbolik (seperti warna), numerik atau keduanya. 2.3.2.3 Pencocokan fitur Karena vektor fitur mewakili objek, dua gambar dapat dibandingkan kesamaan atau perbedaannya dengan membandingkan dua vektor fitur untuk melakukan klasifikasi citra. Pada dasarnya ada dua metode untuk membandingkan gambar, baik dengan mengukur jarak antara dua vektor fitur atau dengan mengukur kesamaan. Sebagai contoh, dua gambar yang dibandingkan dengan menghitung jarak antara dua vektor fitur, semakin pendek jarak berarti semakin besar kesamaan
10
dan lebih kecil perbedaannya. Ukuran jarak yang umum digunakan adalah jarak Euclidean. 2.4
Bag-of-Words (BoW) Paradigma Bag-of-Words merupakan konsep yang diambil dari analisis
teks, yaitu merepresentasikan dokumen sebagai sebuah kantung informasiinformasi penting tanpa mengurutkan setiap katanya. Ide yang sama diterapkan pada computer vision dengan merepresentasikan objek sebagai kantung potonganpotongan kata visual yang merupakan hasil deskripsi suatu deskriptor fitur.
Gambar 2.1 Ilustrasi model Bag-of-Words pada citra [19]
Bag-of-Words dapat digunakan dalam pengkategorian objek dengan membangun sebuah kamus besar dari banyak kata visual dan merepresentasikan setiap citra sebagai sebuah histogram frekuensi kata yang ada pada citra. Paradigma Bag-of-Words telah menunjukkan kemampuan yang baik dalam mengenali logo pada citra [20]–[22].
Gambar 2.2 Representasi citra sebagai histogram frekuensi kata [19]
11
2.5
Speeded Up Robust Feature (SURF) SURF [17], [23] telah diusulkan oleh Herbert Bay, dkk merupakan detektor
fitur yang invarian terhadap skala. SURF menggunakan aproksimasi matriks Hessian dalam mendeteksi fitur. Citra integral yang dipopulerkan oleh Viola dan Jones [24] juga diimplementasikan pada SURF untuk dapat mengurangi waktu komputasi secara drastis. Pada gambar 2.3 terlihat hasil deteksi fitur dengan menggunakan matriks Hessian.
Gambar 2.3 Deteksi fitur di kebun bunga matahari dengan menggunakan matriks Hessian [23]
Proses ektraksi fitur SURF terdiri dari dua tahap. Tahap pertama, setiap keypoint diberi orientasi yang ditentukan dengan menghitung respon Haar wavelet untuk setiap set piksel. Tahap kedua yaitu membuat jendela persegi disekitar keypoint dan memberi orientasi sepanjang orientasi keypoint. Kemudian jendela di bagi menjadi 4x4 sub-persegi dan respon Haar wavelet dihitung untuk 5x5 grid sampel di setiap sub-persegi seperti terlihat pada gambar 2.4 (untuk ilustrasi hanya ditampilkan 2x2 sampel grid pada gambar sebelah kiri).
Gambar 2.4 Komponen deskriptor SURF [25]
12
Untuk setiap sub-persegi, jumlah dari dx, |dx|, dy, |dy| dihitung berdasarkan orientasi dari grid sampel. Dimana dx adalah respon Haar wavelet dari x pada posisi horizontal dan dy adalah respon Harr wavelet dari y pada posisi vertical. Jadi vektor empat dimensi (V) dihitung berdasar sub-perseginya seperti berikut : =
,
,
|
|,
|
|
Operasi tersebut diproses untuk setiap 4x4 sub-persegi dan vektor digabungkan, menghasilkan vektor dengan panjang 64 (4x4x4) secara keseluruhan. SURF telah dilaporkan memiliki hasil klasifikasi yang baik pada berbagai dataset. Percobaan menunjukkan bahwa deskriptor 64-SURF memberikan hasil yang sama sebagai deskriptor 128-SIFT untuk klasifikasi citra dengan waktu proses yang lebih cepat [16]. Hal ini disebabkan bahwa SURF mengandalkan teknik gambar integral dan menggunakan vektor 64-dimensi yang merupakan setengah ukuran SIFT [23]. 2.6
K-Means K-Means adalah algoritma yang populer digunakan dalam analisis klaster
(clustering) dan diaplikasikan pada berbagai bidang seperti pembelajaran mesin, pengenalan pola, analisis citra, temu kembali informasi, dan bioinformatics. Ide dari k-means adalah mengelompokan sejumlah n data kedalam k klaster, dimana n merupakan bagian dari klaster dengan nilai jarak atau mean terdekat [26]. Pada gambar 2.3 dapat dilihat data dengan bentuk yang sama terkumpul dalam klaster yang sama pula. Pusat klaster (centroid) ditandai dengan tanda plus (+).
Gambar 2.5 Contoh hasil klaster dengan menggunakan k-means [26]
13
Algoritma dasar k-means adalah sebagai berikut : 1. Set nilai awal centroid (titik tengah) dari klaster yang akan dibentuk 2. Memasukkan setiap elemen data terhadap klaster dengan jarak terdekat 3. Menentukan centroid baru dari setiap klaster 4. Ulangi langkah 2 dan 3 hingga mencapai kondisi konvergen (tidak ada elemen data yg berpindah klaster) 2.7
Support Vector Machine (SVM) [27] Pada tahun 1979 Vladimir Vapnik mengembangkan SVM yang konsep
dasarnya adalah digunakannya sebuah fungsi linear atau hyperplane yang dapat memisahkan data latih kedalam dua kelas dengan memaksimalkan margin diantara kedua kelas tersebut. SVM termasuk kedalam golongan supervised learning, yaitu proses pembelajaran yang akan menghasilkan suatu fungsi pemisah dari input-ouput berdasarkan sejumlah data latih. Walaupun telah sejak lama dikembangkan namun implementasi SVM baru mulai dilirik pertama kali pada tahun 1992 pada masalah pengenalan digit angka yang memberikan hasil cukup baik. Dan hingga sekarang penggunaan SVM sudah banyak digunakan dalam analisa data, pengenalan pola, klasifikasi, dan regresi data. 2.7.1
Two-Class Support Vector Machine Pada dasarnya SVM dikembangkan untuk masalah klasifikasi linier pada
dua kelas. Dimana sejumlah data dipisahkan oleh beberapa fungsi pemisah (hyperplane). Fungsi pemisah tersebut dipilih berdasarkan margin paling optimal diantara fungsi pemisah lainnya, sehingga SVM memiliki kemampuan generalisasi terhadap data latih. Sedangkan pada masalah klasifikasi dengan data nonlinier digunakan kernel trick yang dapat memetakan data latih kedalam feature vector yang memiliki dimensi lebih tinggi. 2.7.1.1 Hard Margin SVM pada Data Linier Sekumpulan data dikatakan dapat dipisahkan secara linier (lineary separable) jika terdapat minimal satu fungsi pemisah (wT x+b) yang dapat memisahkan data tersebut menjadi dua kelas yang berbeda. Misal diberikan suatu
14
data latih yang terdiri dari sekumpulan data xi, (i = 1, ... , n) dimana n adalah jumlah data latih. Data tersebut akan diklasifikasikan kedalam dua kelas {+1,-1}. Pada gambar 2.6 dapat dilihat ada sejumlah fungsi yang dapat memisahkan data tersebut menjadi dua kelas yang berbeda. Dari sejumlah fungsi tersebut akan dipilih fungsi pemisah dengan margin paling besar yang kemudian disebut sebagai optimal hyperplane. Sehingga SVM dikenal memiliki kemampuan generalisasi yang cukup baik.
Gambar 2.6 Optimal hyperplane pada dua dimensi
Maka dari fungsi pemisah D(x) = wT xi + b dimana w terdiri atas m dimensi vektor, b adalah bias term, serta i = 1...M (jumlah data latih). Dapat ditentukan kelas dari data tersebut : ( )=
+
> 0,
1
( )=
+
< 0,
2
Dari contoh diatas fungsi pemisah D(x), dapat dirubah menjadi persamaan yi (wxi + b) ≥ 1, sehingga fungsi pemisah optimal didapat dengan mencari nilai w dan b yang dapat meminimalkan |w|. Pencarian nilai w dapat dilakukan dengan mengubah permasalahan diatas menjadi permasalahan pemrograman kuadratik (quadratic programming), dengan mengganti nilai |w| menjadi nilai ||w||2. Menggunakan lagrangian variable masalah optimasi QP diatas menjadi : ( , , )=
1 2
−
{ (
+ ) − 1}
Permasalahan QP di atas dapat dioptimasi menjadi bentuk dual form sebagai berikut
15
( , , )=
1 2
−
,
dengan batasan =0;
≥0;
= 1, … ,
2.7.1.2 L1 Soft Margin SVM pada Data Linier Sedangkan untuk memberikan toleransi terhadap noise dimana pada permasalahan klasifikasi linier diatas data tidak selalu dapat diklasifikasikan kedalam dua kelas. Maka pada permasalahan pemrograman kuadratik ditambahkan variabel C dan εi, yang kemudian disebut sebagai L1 Soft Margin SVM. ( , , )=
1 | | + 2
Gambar 2.7 Variabel Slack pada L1 Soft Margin SVM
Dimana εi adalah toleransi terhadap noise seperti ditunjukan pada gambar 2.7, dan C adalah variabel kontrol terhadap error. Sehingga persamaan bentuk dual dari L1 Soft Margin SVM menjadi : ( )=
−
1 2
,
dengan batasan =0; C≥
≥0;
= 1, … ,
16
Dapat dilihat bahwa perbedaan antara Hard Margin SVM dan L1 Soft Margin SVM hanya terletak pada nilai C yang merupakan variabel kontrol terhadap error. Dimana variabel εi akan hilang ketika dilakukan penurunan rumus. 2.7.1.3 Support Vector Machine pada Data Non Linier Pada SVM data dipisahkan secara linier menggunakan sebuah fungsi pemisah optimal. Namun terkadang data masukan dapat berupa data nonlinier, dimana data tersebut tidak dapat dipisahkan secara langsung menggunakan fungsi pemisah. Maka SVM harus dimodifikasi agar masalah data nonlinier diatas dapat dipecahkan. Untuk itu pada SVM dikenal istilah kernel trick dimana data awal dipetakan kedalam ruang berdimensi tinggi yang disebut feature space, sehingga terdapat bidang pemisah yang dapat memisahkan data sesuai dengan kelasnya. Dengan ruang berdimensi tinggi tersebut data memiliki kemungkinan lebih besar untuk dapat dipisahkan secara linier (teorema cover). Salah satu keuntungan dari kernel trick adalah bahwa data secara implisit dapat dipetakan kedalam ruang berdimensi tinggi. Yaitu cukup dengan mengganti semua operasi dot product dengan sebuah fungsi kernel H(x,x’) tanpa harus memetakan tiap titik kedalam ruang berdimensi tinggi. Berikut adalah beberapa kernel yang biasa digunakan : 1. Kernel Linier ( ,
)=
′
2. Kernel Polinomial ( ,
)= (
+ 1)
3. Kernel Gaussian ( ,
)=
(|| 2
′||)
2.7.1.4 Kelebihan SVM Kelebihan metode SVM dibandingkan dengan metode multilayer neural network adalah sebagai berikut : 1. Generalisasi. Karena pada SVM penentuan bidang pemisah adalah memilih bidang dengan margin optimal maka generalisasi pada SVM dapat terjaga dengan sendirinya. Generalisasi sendiri adalah kemampuan dalam mengklasifikasikan data-data yang tidak termasuk pada data latih atau biasa disebut unseen data.
17
2. Curse of dimensionality. Permasalahan pada pengenalan pola dimana dengan jumlah dimensi data yang cukup besar dibutuhkan jumlah data latih yang besar pula agar dapat mengklasifikasikan data dengan baik. Namun telah dibuktikan bahwa tingkat generalisasi pada SVM tidak dipengaruhi oleh jumlah data latih. 3. Feasibility. Implementasi SVM dapat dilakukan dengan mudah dengan merumuskan permasalahan pencarian fungsi pemisah optimal menjadi pencarian nilai minimum w kedalam quadratic problem. Maka dalam menyelesaikan SVM jika kita memiliki librari penyelesaian masalah quadratic
problem
maka
dengan
sendirinya
SVM
dapat
diimplementasikan. 4. Robustness to noise. Pada tahap klasifikasi terkadang data tidak dapat dipisahkan secara sempurna, data latih umumnya dipisahkan dengan noise. Pada L1 Soft Margin SVM, noise dapat dikontrol dengan menentukan nilai parameter C, dimana C adalah parameter tambahan yang berfungsi sebagai pembatas terhadap parameter αi. Makin besar nilai C, maka makin besar pula penalti yang dikenakan terhadap error pada klasifikasi, dan pelatihan yang terjadi akan semakin ketat. 2.7.1.5 Kekurangan SVM Adapun kekurangan dari metode klasifikasi menggunakan SVM adalah sebagai berikut : 1. Tidak seperti multilayer neural network, SVM menggunakan fungsi pemisah dalam mengklasifikasikan data kedalam dua kelas, sehingga dalam permasalahan yang memiliki lebih dari dua kelas dibutuhkan modifikasi. 2. Karena permasalahan pada SVM dipecahkan pada dual problem maka variabel pada SVM sama dengan jumlah data latih. Dimana ketika data latih sangat besar makan akan mempengaruhi lama waktu pelatihan dan ukuran memori yang dibutuhkan. 3. Walaupun termasuk kedalam metode non-parametric namun pada SVM tetap dibutuhkan pemilihan model seperti kernel dan parameter kernel,
18
serta penentuan nilai margin C dan model klasifikasi multikelas.Hal ini hampir sama dengan permasalahan pada multilayer neural network. 2.7.2
Multiclass Support Vector Machine Karena SVM menggunakan fungsi keputusan langsung (direct decission
function), ekstensi terhadap permasalahan multi kelas tidak mudah. Kurang lebih ada empat tipe SVM yang dapat mengatasi masalah klasifikasi multi kelas : 1. One-against-All SVM, 2. Pairwise SVM, 3. Error-Correcting Output Code (ECOC) SVM, dan 4. All-at-Once SVM. Berdasarkan formulasi Vapnik [28], pada One-againts-All SVM, problem n-kelas dikonversi kedalam n buah problem 2-kelas dan untuk setiap problem 2kelas ke-i, kelas i dipisahkan dari kelas yang tersisa. Tetapi dengan formulasi tersebut muncul bidang yang tidak dapat diklasifikasikan (unclassified regions) ketika menggunakan fungsi keputusan diskrit (discrete decision functions).
Gambar 2.8 Klasifikasi multi kelas dengan One-againts-All SVM
Untuk menyelesaikan masalah tersebut, pada Pairwaise SVM, Kreβel [29] mengkonversi masalah problem n-kelas kedalam n(n-1)/2 buah problem 2-kelas yang mencakup keseluruhan kelas, tetapi unclassified regions masih tetap muncul namun berhasil dikurangi.
19
Gambar 2.9 Klasifikasi multi kelas dengan Pairwise SVM
Masalah unclassified regions dapat diatasi dengan menggunakan fungsi keanggotaan (membership function), pohon keputusan [30], [31], error-correcting output code [32], atau dengan menentukan fungsi keputusan secara sekaligus [33], [34]. Khususnya pada One-against-All SVM, jika digunakan fungsi keputusan kontinu (continous decision function) dibanding fungsi keputusan diskrit, masalah unclassified regions dapat diatasi.
