6

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.

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.

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

Pengolahan

Citra

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 ciri-

ciri 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 :

111

591

301 BGRgrayscale ++=

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 sub-

iterasi 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 sinyal-

sinyal 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 komponen-

komponen 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) bxxf +⋅= ω)( sehingga kita dapat menggunakan classifier tersebut untuk

mengklasifikasi data. Training set: { }liii yxset 1, = , di mana n

ix ℜ∈ berperan sebagai

input dan { }11+−∈iy menjadi output, mengindikasikan kelas. Formulasi SVM dimulai

dari asumsi bahwa kasus yang dapat dipisahkan secara linear adalah:

⎩⎨⎧

−=−≤++=+≥+

1 if ,11 if ,1

yibxyibx

iT

iT

ωω

(3)

Untuk kasus yang tidak dapat dipisahkan

( )( )⎩

⎨⎧

−=−≤++=+≥+

1 if ,11 if ,1

yibxyibx

iT

iT

φωφω

(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 � sebagai berikut :

� : x → � (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

ii

T C12

1min ξωω   (5) 

  s.t   )(( ) libxy iiit

i ,...1,0,1 =≥−=+ ξξφω    

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

iiii xy

1φαω , dimana ix bukan nol dan iα adalah support vector. Decision

boundary hanya ditentukan oleh support vector. Diketahui t , ( j 1, ..., s) menjadi titik-

titik dari s support vector. Maka kita dapat menuliskan kembali fungsi yang ada menjadi

:

  ( )∑=

=s

jtjtjtj xy

1

φαω   (6) 

Masalah Quadratic Programming dipecahkan dengan menambahkan Dual Problem

( ) ( )ji

l

jijiji xxKyyQ ,

21max

1,∑=

−= αααα   (7) 

(8)

dengan kernel trick (mercer theorem):

  ( ) ( ) ( )jT

iji xxxxK φφ=,   (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

iiii bxxKysignxy

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  

 Class +1 Class -1

w.x + b = 0

w.x + b <= -1

w.x + b >= +1

S1

H

S2

Margin

 

 

(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 (v-

SVR). 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 Newton-

KKT 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 :

MAX (or MIN): f0(X1, X2, …, Xn)

Subject to: f1(X1, X2, …, Xn)<=b1

:

fk(X1, X2, …, Xn)>=bk

:

fm(X1, X2, …, Xn)=bm

Perhitungan solusi Optimal :

Contoh :

X1 + X2 = 200 (1)

Dan 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. Syarat-

syarat 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 nilai-

nilai 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

menggunakan ( )∑=

=l

iiii xy

1φαω , dimana ix bukan nol dan iα adalah

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

learning.

Para

met

er

Feat

ure

vect

or

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

.)),(),...,(()(),...,( 121 ndxxxxxx d <≡→≡ φφφ Sehingga fungsi penentu berubah menjadi :

1. Kernel Linear

 

Gambar 2.8 Contoh pemetaan Kernel Linear

2. Kernel Polynomial

reecoefxxxxk deg)'()',( += γ

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

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −−= 2

2

2'

exp)',(σ

xxxxk

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.

,,0, ℜ∈∈=+ bHwwherebxw (19)

Berhubungan dengan fungsi keputusan

),,sgn()( bxwxf += (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

2

, 21)(minimize ww

bHw=

ℜ∈∈τ (21)

mengacu kepada 1),( ≥+ bxwy ii untuk semua i = 1,…,m. (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  

∑=

−+−=m

iiii bwxywbwL

1

2 ).1),((21),,( αα (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,

,0),,(0),,( =∂∂

=∂∂ αα bwL

wdanbwL

b (24)

mengarah ke

∑=

=m

iii y

10α (25)

dan

∑=

=m

iiii xyw

1α (26)

Vektor solusi yang dijelaskan dengan maksud dari sebuah subset dari pola

pelatihan, disebut Support Vectors. Dengan kondisi KKT,

( )[ ] 01, =−+ bwxy iiiα 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  

∑ ∑= =ℜ∈

−=m

i

m

jijijijii xxyyW

m1 1,

,21)(maximize αααα

α (28)

Mengarah ke αi ≥ 0 untuk setiap i = 1,…,m dan ∑=

=m

iii y

10α (29)

Dengan menggunakan (28), fungsi keputusan hyperplane dapat ditulis sebagai

berikut

,,sgn)(1

⎟⎠

⎞⎜⎝

⎛+= ∑

=

m

iiii bxxyxf α

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)

Dengan metode ini, dibangun buah model klasifikasi biner (k

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(k-

1)/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  

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 Bukan Kelas 2 f2(x) Kelas 3 Bukan Kelas 3 f3(x) Kelas 4 Bukan Kelas 4 f4(x)

xi

Kelas 1  Kelas 1 Kelas 1 Kelas 2 Kelas 4  Kelas 4

f12(x)  f13(x)  f14(x) f23(x) f24(x)  f34(x)

46  

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)

 

xi

unknown 

Kelas 1 

Kelas 2

Kelas 3

Kelas 4

f1(x)

f2(x) 

f3(x) 

f4(x) 

47  

 

 

 

 

 

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,

Not 3Not 4Not 1 Not 4Not 2Not 4Not 3 Not 4 

Not 1Not 3 Not 3Not 2 

Not 2Not 1

xi

Kelas 3  Kelas 4  Kelas 2 Kelas 4 Kelas 1 Kelas 4  Kelas  3 Kelas 4

f12(x) 

f23(x) 

f34(x)  f12(x)  f14(x) 

f13(x) 

f34(x) 

48  

dan sebaliknya kelas –, apabila f(x) <= -1. Karena adalah fungsi linear, maka

dapat lebih lanjut ditulis sebagai:

f(x) = (w,x) + b

= bxwn

i ii +∑ −1

= (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 ( )( )xfsgn .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 1900-

an 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.