7
BAB II LANDASAN TEORI
2.1. Sistem Penciuman Manusia Alat indra merupakan bagian tubuh yang di khususkan untuk menerima rangsangan yang berasal dari luar tubuh. Didalam alat indra terdapat ujung-ujung saraf reseptor yang yang peka terhadap rangsangan yang bersifat khusus. Pada dasarnya, ada tiga macam alat reseptor pada alat indra manusia, yaitu reseptor yang peka terhadap rangsangan cahaya (fotoreseptor), reseptor yang peka terhadap rangsangan tekanan (mekanoreseptor ), dan reseptor yang peka terhadap rangsangan kimia (kemoreseptor). Alat indara pada manusia adalah indra penglihatan (mata), indra pembau (hidung), indra pengecap (lidah), indra pendengar (telinga), dan indra peraba (kulit). Hidung mendeteksi zat yang melepaskan molekul-molekul diudara. Diaatap rongga hidung terdapat olfactory epithelium yang sangat peka terhadap ransangan kimia berupa gas atau uap, karena pada bagian ini ada bagian pendeteksi bau(smell receptors). Ketika partikel bau tertangkap oleh receptor, sinyal akan di kirim ke olfactory bulb melalui saraf olfactory (Gambar 2.1). Bagian inilah yang mengirim sinyal ke otak dan kemudian di proses oleh otak bau apakah yang telah tercium oleh hidung kita.
8
Gambar 2.1 Ilustrasi Sistem Penciuman Manusia (Sumber: Buck dan Axel, 2004).
2.2. Electronic Nose (e-nose) E-nose meniru tindakan hidung mamalia dengan mengenali pola respon terhadap aroma. e-nose telah dibahas oleh beberapa penulis, dan dapat diterapkan untuk pemantaan lingkungan serta pengedalian kualitas seperti pada bidan pengolahan makanan dan pemantauan industri. Pada tahun 1920, Zwaardemaker dan Hogewide (Zwaardenmaker dan Hogewind 1920) mengusulkan bahwa bau dapat dideteksi dengan mengukur muatan listrik yang dikembangkan dari penyemprotan air, tetapi mereka tidak berhasil dalam mengembangkan konsep ini
9
menjadi sebuah instrumen. Pada tahun 1964, Hartman dan rekan memperkenalkan penggunaan sensor elektrokimia untuk mendeteksi bau (Hartman, 1954) . Instrumen mereka terdiri dari dari delapan rangkaian sel elektrokimia yang berbeda. Pada akhir 1980-an, istilah hidung elektronik pertama kali muncul dalam literatur oleh Gardner (Gardner 1999). Setelah itu, kemajuan e-nose menjadi lebih cepat. Selama dekade terakhir, banyak lembaga penelitian dan organisasi komersial di seluruh dunia telah mengembangkan teknologi baru untuk membuat e-nose menjadi lebih kecil dan lebih cerdas.
E-noseadalah sebuah instrument yang menggabungkan rangkaian sensros sensor gas dan teknik pengenalan pola untuk aroma sederhana dan kompleks (Gardner dan Bartlett, 1999). Secara umum rangkaian sensor dirancang sedemikian rupa agar masing-masing sensor merespon bahan kimia dengan dengan tingkat sensitifitas yang unik terhadap sensor lain.Oleh karena itu e-nose terdiri dari rangkaian sensor gas yang tidak spesifik. E-nose mampu memberikan analisis kualitatif dan analisis kuantitatif yang sederhana atau kompleks terhadap suatu gas, uap, atau aroma bau. Pengolahan data (pengukuran denoising dan ekstraksi fitur) dan klasifikasi pola adalah dua komponen penting dari sistem enose. Sinyal yang dihasilkan oleh rangkaian sensor aroma harus diproses dengan cara yang cangih. Penelitian e-nose telah menggunakan berbagai pola parametik dan non-parametrik, hal ini termask penggunaan teknik linear dan non-linear. sepertti analisis fungsi diskriminan, analisis cluster, algoritma genetik, fuzzy logic, dan model-model adaptif. Aroma terdiri dari molekul yang masing-masing memiliki ukuran dan bentuk tertentu. Masing-masing molekul memiliki ukuran
10
dan bentuk pada reseptor di hidung manusia. Keteika reseptor menangkap suatu molekul, kemudian mengirimkan sinyal ke otak dan otak mengidentifikasi aroma yang terkait dengan molekul tersebut. Dasar dari e-nose adalah model biologis. meskipun reseptor diganti dengan sensor dan sinyal dikirim kesebuah program untuk diproses. E-nose merupakan daerah penelitian yang berkembang di area biomimetika atau biomikri. Gambar 2.2 menggambarkan sebuah blok diagram e-nose. Sistem hidung elektronik terdiri dari empat blok fungsional utama, yaitu Odour Handling and Delivery System, Sensors and Interface Electronics, Signal Processing and Intelligent Pattern Analysis and Recognition. Rangkaian sensor terkena uap aroma yang mudah menguap melalui penanganan aroma yang sesuai dan sistem membuat tingkat paparan masing-masing sensor tetap konstan. Respon sinyal dari rangkaian sensor dikondisikan dan diproses melalui sirkuit yang cocok dan diproses ke mesin pengenalan pola untuk klasifikasi, analisis dan deklarasi.
Gambar 2.2 Bentuk rancangan dasar E-nose
11
2.3. Wavelet Sebuah gelombang (wave) biasanya didefinisikan sebagai sebuah fungsi osilasi dari waktu (space), misalnya sebuah gelombang sinusoidal. Sebuah wavelet merupakan gelombang singkat (small wave) yang energi nya terkonsentrasi pada suatu selang waktu untuk memberikan kemampuan analisis transient, ketidak-stasioneran, atau fenomena berubah terhadap waktu (timevarying). Wavelet adalah fungsi matematis yang dapat memecahkan atau menguraikan data kedalam potongan-potongan yang berbeda dari komponen-komponen frekuensi. Secara konsep, Wavelet adalah bentuk gelombang yang memiliki durasi terbatas dan memiliki nilai rata-rata nol (Misiti, dkk. 2004). Persamaan (2.1) menentukan sebuah wavelet dan persamaa ψ(t) (2.2) merupakan karakteristik umum dari wavelet ψ L2(R) dan ,
∞ ∞
0
(2.1) (2.2)
√
dimana : L2 (R) adalah fungsi energi
∞ | ∞
|
∞
j adalah faktor sekala k adalah waktu translasi Sebuah gelombang (wave) biasanya didefinisikan sebagai sebuah fungsi osilasi dari waktu (space), misalnya sebuah gelombang sinusoidal. Sebuah wavelet
merupakan
gelombang
singkat
(small
wave)
yang
energinya
terkonsentrasi pada suatu selang waktu untuk memberikan kemampuan analisis transien,
ketidakstasioneran,
atau
fenomena
berubah
terhadap
waktu
12
(timevarying). Karakterisktik daripada Wavelet antara lain adalah berosilasi singkat, translasi (pergeseran) dan dilatasi (skala). Pada gambar 2.3 diperlihatkan sebuah sinyal biasa dan sinyal wavelet.
(a)
(b)
Gambar 2.3 (a)Bentuk Gelombang Sinyal Sinus (b) Sinyal Wavelet
2.3.1. Analisis Wavelet Analisis wavelet dapat mengungkapka data dari berbagai aspek yaitu teknik analis sinyal, kecenderungan, titik breakdown, diskontinuitas, dan bentuk kesamaan(Misiti, dkk. 2004). Dikarenakan data dapat direpresentasikan dalam bentuk yang berbeda-beda, wavele analisis dapat memperkecil sinyal gangguan tanpa adanya degradasi. Analisi wavelet memiliki berhubungan dengan analisis Fourier. Didalam analis Fourier , sinusoids pada gambar 2.4(b) digunakan sebgai basis fungsi dengan variasi frekuensi dan perluasan dari ∞ sampai
∞. Dengan katalain,
kelompok wavelet families have batas seperti yang digambarkan pada gambar 2.4(b,c,d).
13
(a)
(c)
(b)
(d)
Gambar 2.4 llustration basis Fourier basis and basis wavelet
Sebuah sinyal atau fungsi f(t) dari ruan S dapat di analisa dan diproses dari berbagai aplikasi yang berbeda jika bisa direpresentasikan sebagai kombinasi linear (Burrus, 2003), seperti diperlihatkan pada persamaan (2.3). ∑ Dimana
(2.3) αadalah koefisien expansi adalah fungsi expansi t i adalah index integer
Tahap pertama analisis wavelet adalah menentukan tipe wavelet, yang disebut dengan mother wavelet atau analyzing wavelet, yang akan digunakan. Hal ini perlu dilakukan karena fungsi wavelet sangat bervariasi dan dikelompokkan berdasarkan fungsi dasar wavelet masing-masing.Contoh keluarga wavelet adalah wavelet Daubechiec.
14
Setelah pemilihan mother wavelet, tahap selanjutnya membentuk basis wavelet yang akan digunakan untuk mentransformasikan sinyal. Suatu basis dapat dibentuk dengan mengubah nilai translasi dan dilatasi dari mother waveletnya.Analisis temporal dilakukan dengan menggunakan basis wavelet frekuensi tinggi, sedangkan analisis frekuensi dilakukan dengan menggunakan basis wavelet frekuensi rendah.Operasi terhadap suatu sinyal hanya dapat dilakukan dengan menggunakan koefisien-koefisien wavelet yang berhubungan.
2.3.2. Transformasi Wavelet Transformasi sinyal merupakan bentuk lain dari penggambaran sinyal yang tidak mengubah isi informasi dalam sinyal tersebut. Transformasi wavelet ( wavelet transform ) menyediakan penggambaran frekuensi waktu dari sinyal. Pada awalnya, transformasi wavelet digunakan untuk menganalisis sinyal bergerak ( non-stationary signals ). Sinyal bergerak ini dianalisis dalam transformasi wavelet dengan menggunakan teknik multi- resolution analysis. Secara umum teknik multi-resolution analysis adalah teknik yang digunakan untuk menganalisis frekuensi dengan cara frekuensi yang berbeda dianalisis menggunakan resolusi yang berbeda. Resolusi dari sinyal merupakan ukuran jumlah informasi di dalam sinyal yang dapat berubah melalui operasi filterisasi. Transformasi wavelet memiliki dua seri dalam pengembangan nya yaitu Continuous Wavelet Transform (CWT) dan Discrete Wavelet Transform (DWT) Semua fungsi yang digunakan dalam transformasi CWT dan DWT diturunkan dari mother wavelet melalui translasi/pergeseran) dan penskalaan/kompresi. Mother wavelet merupakan fungsi dasar yang digunakan dalam transformasi
15
wavelet. Karena mother wavelet menghasilkan semua fungsi wavelet yang digunakan dalam transformasi melalui translasi dan penskalaan, maka mother wavelet juga akan menentukan karakteristik dari transformasi wavelet yang dihasilkan. Oleh karena itu, perlu pencatatan secara teliti terhadap penerapan wavelet dan pemilihan yang tepat terhadap mother wavelet harus dilakukan agar dapat menggunakan transformasi wavelet secara efisien. Fungsifungsi yang termasuk di dalam keluarga wavelet dipaparkan pada Gambar 2.5.
Gambar 2.5 Keluarga Wavelet (a) Haar, (b) Daubechies4, (c) Coiflet1, (d) Symlet2, (e) Meyer, (f) Morlet, (g) Mexican Hat. (Sripathi 2003).
Gambar 2.5 menggambarkan beberapa fungsi wavelet yang umum digunakan. Haar wavelet adalah salah satu wavelet tertua dan paling sederhana. Oleh karena itu, setiap pembahasan tentang wavelet dimulai dengan wavelet Haar. Daubechies wavelet adalah wavelets paling populer. Mereka mewakili dasar-dasar pemrosesan sinyal wavelet dan digunakan dalam berbagai aplikasi. Daubechies disebut juga wavelet Maxflat memiliki respon frekuensi maksimum pada
16
frekuensi 0 dan π. Hal tersebut adalah properti yang sangat diinginkan dalam beberapa aplikasi. Wavelet Haar, Daubechies, Symlets dan Coiflets didukung oleh wavelet ortogonal. Wavelet Meyer mampu membentuk rekonstruksi sempurna. Wavelet Meyer, Morlet dan Mexican Hat simetris dalam bentuk. Wavelet dipilih berdasarkan bentuk dan kemampuan mereka untuk menganalisa sinyal. CWT disajikan dengan persamaan 2.4, dimana x(t) adalah signal yang ingin dianalisa. ψ(t) adalah mother wavelet atau fungsi dasar yang dipilih. τ merupakan parameter translasi yang berhubungan dengan informasi waktu pada transformasi wavelet. Parameter skala s didefinisikan sebagai |1/frekuensi| dan berhubungan dengan informasi frekuensi. Dengan adanya penskalaan ini sinyal dapat diperbesar atau dikompresi. Penskalaan besar (frekuensi rendah) menyebabkan sinyal diperbesar dan dapat memberikan informasi detil yang tersembunyi di sinyal, sedangkan penskalaan kecil (frekuensi tinggi) menyebabakan kompresi sinyal dan memberikan informasi global dari sinyal. Seri pengembangan kedua dari transformasi wavelet adalah Discrete Wavelet Transform ( DWT ). Seri pengembangan ini merupakan seri CWT yang didiskritkan. Dengan pendiskritan CWT ini maka perhitungan dalam CWT dapat dibantu dengan menggunakan komputer. ,
| |
.
(2.4)
2.3.3. Discrete Wavelet Transform ( DWT ) Dasar dari DWT dimulai pada tahun 1976 dimana teknik untuk dekomposisi sinyal waktu diskrit ditemukan.Di dalam CWT, sinyal dianalisis menggunakan seperangkat fungsi dasar yang saling berhubungan dengan
17
penskalaan dan transisi sederhana.Sedangkan di dalam DWT, penggambaran sebuah skala waktu sinyal digital didapatkan dengan menggunakan teknik filterisasi digital. Secara garis besar proses dalam teknik ini adalah dengan melewatkan sinyal yang akan dianalisis pada filter dengan frekuensi dan skala yang berbeda. Filterisasi sendiri merupakan sebuah fungsi yang digunakan dalam pemrosesan sinyal. Wavelet dapat direalisasikan menggunakan iterasi filter dengan penskalaan. Resolusi dari sinyal, yang merupakan rata-rata dari jumlah detil informasi dalam sinyal, ditentukan melalui filterasi ini dan skala nya didapatkan dengan up sampling dan down sampling (sub sampling). Sebuah sinyal harus dilewatkan dalam dua filterisasi DWT yaitu highpass filter dan lowpass filter agar frekuensi dari sinyal tersebut dapat dianalisis. Analisis sinyal dilakukan terhadap hasil filterisasi highpass filter dan lowpass filter di mana highpass filter digunakan untuk menganalisis frekuensi tinggi dan lowpass filter digunakan untuk menganalisis frekuensi rendah. Analisis terhadap frekuensi dilakukan dengan cara menggunakan resolusi yang dihasilkan setelah sinyal melewati filterisasi. Analisis frekuensi yang berbeda dengan menggunakan resolusi yang berbeda inilah yang disebut dengan multi-resolution analysis, seperti yang telah disinggung pada bagian Transformasi Wavelet. Pembagian sinyal menjadi frekuensi tinggi dan frekuensi rendah dalam proses filterisasi highpass filter dan lowpass filter disebut sebagai dekomposisi. Proses dekomposisi dimulai dengan melewatkan sinyal asal melewati highpass filter dan lowpass filter. Misalkan sinyal asal ini memiliki rentang frekuensi dari 0 sampai dengan π rad/s. Dalam melewati highpass filter dan lowpass filter ini, rentang frekuensi di- subsample menjadi dua, sehingga rentang frekuensi tertinggi pada
18
masing-masing subsample menjadi π/2 rad/s. Setelah filterisasi, setengah dari sample atau salah satu subsample dapat dieliminasi berdasarkan aturan Nyquist. Sehingga sinyal dapat selalu di-subsample oleh 2 (↓2 ) dengan cara mengabaikan setiap sample yang kedua. Proses dekomposisi ini dapat melalui satu atau lebih tingkatan. Dekomposisi satu tingkat ditulis dengan ekspresi matematika pada persamaan 2.5 dan 2.6.
2.5
2.6 d [n]dan a[n] adalah hasil dari highpass filter dan lowpass filter, x[n] merupakan sinyal asal, H0 adalah highpass filter, dan G0 adalah
lowpass filter. DWT
menghitung sinyal diskrit domain waktu menggunakan highpass filter dan lowpass filter. Pada gambar 2.6 signal dinotasikan dengan x[n], dimana n adalah bilangan bulat. Disetiap level, highpass filter menghasilkan detail informasi d[n], sementara lowpass filter merupakan taksiran kasar dari fungsi pensakalaan.
Gambar 2.6 Dekomposisi Wavelet Tiga Tingkat
19
Dengan menggunakan koefisien DWT ini maka dapat dilakukan proses Inverse Discrete Wavelet Transform (IDWT) untuk merekonstruksi menjadi sinyal asal. DWT menganalisis sinyal pada frekuensi berbeda dengan resolusi yang berbeda melalui dekomposisi sinyal sehingga menjadi detil informasi dan taksiran kasar. DWT bekerja pada dua kumpulan fungsi yang disebut fungsi penskalaan dan fungsi wavelet yang masingmasing berhubungan dengan lowpass filter dan highpass filter. Seperti yang telah dijelaskan sebelumnya dekomposisi ini didasarkan pada aturan Nyquist yang salah satunya mengatakan bahwa frekuensi komponen sample harus kurang atau sama dengan setengah dari frekuensi sampling. Jadi diambil frekuensi sample π/2 dari frekuensi sampling π dalam subsample oleh 2 pada dekomposisi wavelet. Gambar 2.7 menunjukkan rekonstruksi sinyal asli dari koefisien wavelet. Pada dasarnya, rekonstruksi adalah proses kebalikan dari dekomposisi. Pendekatan dan koefisien di setiap tingkatan melewati lowpass filter dan highpass sintesis. Proses ini terus berlanjut sampai jumlah yang sama tingkat seperti dalam proses dekomposisi untuk mendapatkan sinyal asli.
Gambar 2.7 Rekonstruksi Wavelet Tiga Tingkat
20
2.4. SupportVectorMachine SupportVectorMachine(SVM)merupakansalahsatu
tekniksupervised
learning dimanapembelajaran dilakukan dengan menggunakan data-data yang sudahjelaskelas
nya
(Vapink).SVMmerupakannamauntuksuatuhimpunanmetodeyang dapatdigunakanuntukmelakukanklasifikasidan regresi.Dalampenelitianini, metode SVM
yang
didasarkanpada
digunakanadalahmetodeuntukmelakukanklasifikasi.SVM konsepbidangkeputusan.Bidangkeputusanberfungsiuntuk
memisahkan obyek-obyek yang memiliki kelas yang berbeda. Gambar 2.8 memberikan ilustrasi mengenai satu bidang keputusan yang memisahkan dua kelas,yaituhijaudanmerah.
Gambar2.8BidangKeputusanyangMemisahkanDuaKelas.
Ide
dasardariSVMadalahmenemukanfungsihyperplaneyangmampu
memisahkanantaraduakelasdenganoptimal.Optimaldi hyperplanetersebut mampumemisahkan maksimal.Marginadalahjarakantaragaris
siniartinyaadalah
kedua kelas dengan margin yang hyperplanedengananggota-anggota
terdekatdarikeduakelas.Halinidiilustrasikanpadagambar2.9.
21
Gambar2.9HyperplanedenganMarginMaksimal.
2.4.1. MengapaSVM? Walaupun
hinggasekarangsudahbanyakteknikklasifikasiyang
dikembangkan,danbeberapadi dalamaplikasiyang masihterusditelitidan
antaranyasudahberhasildiimplementasikanke
digunakandalam
kehidupansehari-hari,metodeklasifikasi
dikembangkan.SVMmerupakansalahsatumetode
klasifikasiyangmasihdapatdigolongkansebagaimetodebaru.Menurutsurvey yangdilakukanterhadapmetode-metodeklasifikasiyangadasaatini, menempatiurutan
pertamasebagaimetode
tertinggi(Kotsiantis,2007).Ditambahlagi, didasarkan
SVM
klasifikasidengantingkatakurasi SVMmerupakansuatumetodeyang
pada statistikdan outputnya dapat dibuktikan
secara matematis
(berbedadenganmetodesejenisartificialneuralnetworkyangmerupakanblack boxdantidakdapatdijelaskansecaramatematiskebenarannya). Untuklebihmenjelaskanmengenaialasan
penggunaanSVM,maka
bagianberikutakandijabarkankeuntungan-keuntungan itusendiri.
pada
yangdimilikiolehSVM
22
a. Dengandata
yangterbatas,SVMtetapmampumelakukanklasifikasi
denganbaik.Halinidisebabkankarenapencariansolusioptimalyang dilakukan oleh SVM bertujuan untuk mencari solusi optimal berdasarkan data yang dimiliki
sekarang
ini,
dan
bukan
bertujuan
mencarisolusiyangoptimaluntukdatayangtidakterbatas. b. MasalahyangdihadapiolehSVMadalahmasalahoptimasiquadratic, sehingga SVMpada akhirnya mampu memberikan nilai optimasi global. c. SVM memiliki kemampuan
generalisasi
yang cukup baik. SVM
memilikikemampuanuntuk
memecahkanmasalahnon-lineardengan
caramemetakandatake
dimensiyanglebihtinggiyangkemudian
dipecahkandenganmenggunakanfungsidiskriminanlinear. d. SVM merupakansuatu teori yang berbasis pada statistik sehingga dapatdianalisalebihlanjut. e. SVM dapat diimplementasikan dengan mudah karena tergolong sebagaipermasalahanquadraticprogramming,yaitu minimaldari
suatu
pencariantitik
persamaandenganmemperhatikankonstrainyang
dimilikiolehpersamaantersebut. f. Biaya komputasilebih efisien apabila dibandingkan dengan teknik klasifikasilainnya. g. Masalah
over-fitting,
yaitu
keadaan
dimana
suatu
pengklasifikasianmampu mengklasifikasikan data-data pelatihan dengan baik
namun
datapengujian,tidakterjadipada SVM.
gagaldalammengklasifikasikandata-
23
2.4.2. SVMLinear Gambar 2.10menunjukkan suatu hyperplane yang berbentuk garis.Hyperplanetersebutdapatdikatakansebagaipengklasifikasianlinear.
Gambar2.10HyperplaneLinear.
Gambar2.10menggambarkanhyperplanelineardanpersamaan nya.Didalamgambartersebutterdapatduakelasyaituhitamdanputih.Secaraumum,per samaanhyperplaneadalahsebagaiberikut. w.x–b=0
(2.7)
Dimana w adalah normal bidang dan b adalah posisi relatif hyperplane terhadap titik pusat koordinat. Dalam persamaan tersebut, nilai w dan b harus ditentukan untuk mendapatkan margin yang maksimal. Hyperplane yang terdekat dengan anggota kelas hitam, namun tetap dapat memisahkan kedua kelas tersebut dapat dirumuskan dengan persamaan sebagai berikut. w.xi – b >= 1, untuk yi = 1
(2.8)
Persamaan yang sama juga dimiliki oleh hyperplane yang dimiliki oleh kelas
24
p putih. Deng gan melakuukan eliminnasi, makaa didapatkan bahwa jarak j dari h hyperplane h hitam dan putih p tersebuut adalah
sehingga diketahui baahwa jarak
m margin antaara hyperplan ne pembatass dengan ked dua kelas tersebut dapatt diperoleh d dengan
memaksim malkan
y yangkemudi iandapatdiseetarakandengganmeminim malkan
Selanjutnya,
p persamaan
w.xi
–
b
>=
1
dapat
dim modifikasi
sehingga
m menghasilka anpersamaan nberikut y yi(wi.x – b) - 1 >= 0
(2.9)
S Selanjutnya, , untuk meenyelesaikann persoalann ini akan digunakan langrange m multiplier, sehingga s perrsamaan terssebut dapat diterjemahkan menjadi persamaan s sebagai berik kut.
(2.1) D Dimana
mumLpakan (nnilaikoefisiennlangrange).Selanjutnyaa,nilaiminim
t terhadapwda apatdiperolehhdenganmennurunkan p persamaandi iatasterhadappw,sehinggaadiperolehpeersamaanberrikut.
(2.1) D Danuntukme endapatkanm minimumLp
terhadapbbdapatdiperoolehdengan
m menurunkan npersamaanddiatasterhadaapb,yangmen nghasilkanpeersamaanberrikut.
(2.1)
K Kemudian,p persamaan
disubstituusikankeLp
25
danmembentukdualproblemLD yangmemilikiconstrainberbeda.
(2.1)
Dimana Sehingga
persoalan
pencarian
hyperplane
dengan margin yang
maksimal dapat dirumuskan dengan persamaan berikut.
(2.1)
Dengan demikian, nilai mencari
nilaiw.Nilai
dimanadatadengan
dapat ditentukan, yang kemudian digunakan untuk nanti nya
akandiperoleh untuksetiapdatapelatihan,
>0merupakansupportvector,dandatadengan
=0
bukanmerupakansupportvector.Setelahmasalahtersebutberhasildipecahkan, maka
langkahselanjutnya
adalah
melakukan
pengujian.
dilakukanterhadapdatayangingindiklasifikasi(xd)
Pengujian
tersebut
denganberdasarkanpada
persamaanberikut.
(2.1) Dimanaxiadalahsupportvector,nsadalahjumlahsupportvector.
2.4.3. SoftMargin Softmarginditujukanuntukmeningkatkan
toleransiSVMterhadapdata
yangtidakdapatsecaratepatdipisahkan kedalamsalahsatukelas.Tujuan nyaadalah melakukanpemisahan data dengan sebaik mungkin. Hal inidilakukandengan menambahkan elemen terhadapdataxi.
, yang melambangkan derajat misklasifikasi Denganpenambahanelementersebut,makapersamaanyang
digunakansebelumnyauntukkelaspertamadapatdiubah.
26
w.xi–b>=1-
(2.1)
Danpersamaanuntukkelaskeduadapatdiubahsebagaiberikut. w.xi–b<=-1+
Dengan
(2.1)
demikian,permasalahanpencarianbidang
pemisahterbaik
dapat
dimodifikasisebagaiberikut.
(2.1)
Dimana C adalah sebuah konstanta yang menentukan nilai pinalti yang diakibatkanolehmisklasifikasidata.NilaiC
iniditentukanolehsi
pengguna.PersamaantersebuthampirsamadenganpersamaanyangdigunakanpadaS VM
linear,namundenganpenambahanaturanbahwameminimalkan
berarti
meminimalkanerrorpadadatapelatihan.Karenanya,permasalahantersebutjuga dapat
dipecahkandengan menggunakan Langrange Multiplier, sehingga
bentuknyamenjadisebagaiberikut. (2.1)
Kemudian, permasalahan tersebut dapat dipecahkan dengan cara yang sama dengancarapemecahanSVMlinear,sehinggadatatetapdapatdipisahkansecara linear.Disinirentangnilai
diperkecilmenjadi0>=
>=C.
27
Gambar2.11HyperplanedenganSoftMargin.
2.4.4. SVMNon-Linear Dalampenerapan
nyadilapangan,seringkaliditemukankasus-kasusyang
tidakdapatdipecahkanolehSVMlinear.Salahsatupemecahanterhadapmasalah tersebutadalahpenggunaansoftmarginnamun,dalambeberapakasussoft
margin
kurang tepatuntuk diterapkan. Suatu modelSVM yang lebih dikenal sebagai SVMnon-linearkemudiandikembangkanuntukmemecahkanmasalahini.Sesuai dengannamanya,SVMinimampumenghasilkanhyperplanedenganpersamaan nonlinear,sepertiyangterlihatpadagambar2.12.
Gambar2.12ContohPenyebaranDatadanHyperplaneNon-linear.
Ide
dasardarimodelSVMnon-lineariniadalahmemetakandatadarisuatu
bidang dengan dimensi tertentu, ke dalam bidang dengan dimensi yang lebih tinggi.Bidangtersebutkemudiandikenaldengannamabidanginputdanbidang Pemetaan
dari
bidang
input
matematikadilambangkan dengan
dilambangkandenganxÆФ(x).
ke
bidang
fitur
(F)
ini
fitur. secara
. Data hasilpemetaan tersebut
28
Gambar2.13PemetaanDatadariBidangInputkeBidangFitur,Disertaideng anHyperplane-nya.
DenganmensubstitusikanlambangpadaxÆФ(x)persamaanklasifikasi padaSVMlinear,akandiperolehpersamaanbarusebagaiberikut.
(2.1)
Namun,
bidangfitur
biasanya
memiliki
dimensi
yang
sangat
tinggi,
bahkanbisamencapaitidakterhinggadanseringkalitidakdiketahuisebelumnya. ini menimbulkan permasalahan baru,
Hal
yaitu
perhitungan yang sangat
rumityangperludilakukan untukmemperoleh nilai
.Daripadamelakukan
perhitunganrumittersebut, akhirnya digunakan jalan pintas lain yang disebut
dengankerneltrickyangdilambangkandenganK(xi,xd).Fungsikerneltersebut memiliki
kesetaraandengan
dot
produk
sehingga
dapat
dituliskandenganformulasebagaiberikut. K(xi,xd)=
(2.2)
Sehingga denganmensubstitusikanpersamaan tersebut ke dalam persamaan
29
klasifikasiSVMnon-linear,akandiperolehpersamaanbaru.
(2.2)
Fungsikerneltersebutkemudiandapatdisubstitusikandenganimplementasi
riil-
nya.Adapun,tabel2.1mendaftarkanfungsi-fungsikernelyangumumdigunakan untukmemecahkanpermasalahanSVMnon-linear.
Tabel2.1DaftarFungsi-fungsiKernel. NamaKernel
Persamaan
,
Linear
,
Polynomial Sigmoid
,
RadialBasisFunction
,
Gaussian
.
,
0
.
,
,
0
|
|2 ,
0
|
| 2
,
0
2.4.5. SVMMulti-Kelas Pada dasarnya,SVMdirancanghanyauntukmasalahklasifikasibiner, dimana data yang terdapat di dalam suatu model SVM hanya mungkin terklasifikasi ke
dalam dua
kelas saja. Dalam kasus dunia nyata, kemampuan untuk
melakukan klasifikasi hanya kedalam dua kelas seringkali tidak cukup karena banyaknya
variasi
yang
mungkin
ditemui.
Karenanya,
digunakancara
tertentuuntukmemungkinkanSVMmampumelakukanklasifikasiterhadaplebih dari dua
kelasdimanacaranyaadalahdenganmenggunakanlebihdari
persamaanhyperplane.Hinggasaatini,
adatiga
satu
pendekatanyangdapatdigunakan
untukmemecahkan masalahSVMmultikelas ini,yaitumetodeone-against-all, one-
30
against-one,dan directedacyclicgraph.Pembahasanberikutnyaakanmembahaslebihdalammengenai SVMmultikelasdenganmenggunakancontoh3 kelas(A,B,danC)kemungkinanklasifikasi.
2.4.5.1. One-against-all Pada metode ini, sesuai dengan namanya, setiap data yang terdapat di dalamsalahsatukelasSVMakandiadu/dibandingkandengangabungandaridatadatayangbukanmerupakananggotakelastersebut.Haliniberartibahwamodel
SVM
dibuatterhadapmasing-masingkelas.Dalamcontohyangdiberikan sebelumnya,setiapkelasA,B,danC,akanmemilikipersamaanhyperplane-nya masing-masing,
yaitu hyperplaneA (data A dibandingkan
hyperplaneB
(dataB
data bukan A),
dibandingkandatabukanB),danhyperplaneC(dataC
dibandingkandatabukanC).Haliniberartibahwapengujianterhadapdatainput harusdilakukanminimal1kali(terhadapsalahsatukelas)denganmaksimum3 kali(terhadapkeseluruhan
kelas),tergantung
kepadaurutanpengujiandandata
inputitusendiri.
2.4.5.2. One-againts-one Padametodeini,setiapdatayangterdapatdalamsalahsatukelasSVM akandiadu/dibandingkandengandatadarisalahsatukelaslainnya,dimanaproses
ini
dilakukanterhadapsetiapkelasyangada.Halinimenyebabkansetiapmodel
SVM
harusdibuatterhadapsetiaprangkaiankelas
satu-
satuyangmungkinterjadi.Dalamcontohyangdiberikansebelumnya,setiaprangkaiank
31
elasAB,BC,dan
ACakanmemilikipersamaan
hyperplanemasing-masing,
yaituhyperplaneAB (dataAdibandingkandataB),hyperplaneBC(dataBdibandingkandataC),dan hyperplaneAC(dataAdibandingkan
dataC).WalaupunjumlahmodelSVM
yang
dimilikijumlahnya sama dengan model one-against-all, seiring dengan bertambahnyajumlah kelas maka semakin bertambah banyak juga jumlah modelnya.Pengujianselalu
dilakukanterhadapsemuamodel,dimanahasil
keanggotaan datainputpadaakhirnya diperoleh berdasarkan outputdarisetiap modeldenganjumlahterbanyak(voting).
2.5. Principal Component Analysis (PCA) Di dalam analisis banyak variabel,
kita dihadapkan pada data yang
berdimensi tinggi. Operasi-operasi matriks berdimensi tinggi membutuhkan biaya komputasi yang sangat besar, dan seringnya tidak seluruh variabel di dalam matriks benar-benar dibutuhkan. Padahal pemasalahan utamanya adalah, mencari variabel-variabel yang memiliki efek yang signifikan terhadap variabel tertentu. Principal Component Analysis (PCA) adalah sebuah metode untuk mengurangi dimensi dari suatu data tanpa kehilangan banyak informasi signifikan yang ada di dalamnya. Principal Component Analysis (PCA) adalah suatu metode yang melibatkan prosedur matematika yang mengubah dan mentransformasikan sejumlah besar variabel yang berkorelasi menjadi sejumlah kecil variabel yang tidak berkorelasi, tanpa menghilangkan informasi penting di dalamnya. Sejumlah citra dua dimensi dari setiap objek tiga dimensi yang akan dikenali, dikumpulkan
32
untuk mewakili objek tersebut sebagai citra acuan. Dari sekumpulan citra acuan tersebut, kemudian akan dilakukan ekstraksi ciri untuk memperoleh informasi karakteristik (ciri) dari objek tersebut. Hasil ekstraksi ciri digunakan untuk dalam proses pengenalan objek multiorientasi. Analisis Komponen Utama banyak digunakan untuk memproyeksikan atau mengubah suatu kumpulan data berukuran besar menjadi bentuk sajian data dengan ukuran yang lebih kecil. Transformasi PCA terhadap sebuah ruang data yang besar akan menghasilkan sejumlah vektor basis ortonormal dalam bentuk kumpulan vektor eigen dari suatu matriks kovarian tertentu yang dapat secara optimal menyajikan distribusi data. Sasaran dari PCA adalah menangkap variasi total dari citra yang ada di dalam basis data yang dilatihkan. Untuk kemudian mereduksinya sehingga menjadi variabel-variabel yang lebih sedikit. Dengan reduksi ini maka waktu komputasi dapat dikurangi dan kompleksititas dari ciri yang tidak perlu dapat dihilangkan. Dengan mereduksi sehingga dimensinya menjadi lebih kecil, maka vektor mana yang harus direduksi dan mana yang tidak direduksi dapat ditentukan dengan mengurutkan nilai eigen terbesar ke nilai eigen terkecil dan vektor eigennya diurutkan sesuai dengan nilai eigen yang bersangkutan. Vektor yang direduksi adalah vektor yang mempunyai nilai eigen yang kecil, karena nilai eigen yang kecil menandakan informasi yang dibawa tidaklah seberapa penting, sehingga dapat direduksi tanpa mempengaruhi ruang citra. Secara singkat langkah-langkah dari proses pembentukan ruang eigen menggunakan Analisis.
2.5.1. Matriks Kovarian
33
Kovarian selalu diukur antara 2 dimensi (Smith, 2002). Perhitungan Kovarian antar dua dimensi (variabel), dalam ilmu statistik, menunjukkan besarnya korelasi dari kedua variabel tersebut. Berikut ini adalah rumus dari kovarian. ∑
,
1
Apabila dibuat matriks kovarian untuk sebuah himpunan data khayalan berdimensi 3, menggunakan dimensi yang biasa, x, y, dan z, maka matriks kovariannya akan memiliki 3 baris dan 3 kolom, dan nilainya adalah sebagai Berikut
, , ,
, , ,
, , ,
Beberapa hal yang patut dicatat, adalah: Pada diagonal utama, dapat dilihat kovarian dari suatu dimensi terhadap dimensi itu sendiri, dan ini artinya variansi dalam dimensi itu. Poin lainnya adalah karena cov (x,y) = cov (y,x), maka matriks berbentuk simetriks terhadap diagonal utama.
2.5.2. Vektor Eigen dan Nilai Eigen Pada setiap matriks persegi, misalkan matriks A, yang dapat dibalik, maka dapat dibuat dimana x adalah sebuah vektor baris, yang disebut sebagai vektor eigen, sedangkan λ adalah sebuah bilangan rasional, yang disebut sebagai nilai eigen.
34
Sebuah vektor eigen selalu datang berpasangan dengan sebuah nilai eigen (Smith, 2002). Sebagai contoh, matriks kovarian di atas dijadikan sebagai A, maka darinya dapat dihasilkan 3 buah nilai eigen, yang dinyatakan sebagai berikut
Setiap nilai eigen, λi, akan berpasangan dengan sebuah vektor eigen, eigi, dalam hal ini berupa vektor kolom berukuran 3*1. Jadi, dari nilai-nilai eigen tersebut, didapatkan sekumpulan vektor-vektor eigen, yang dinyatakan sebagai berikut
2.5.3. Principal Component Menurut Smith (Smith, 2002), vektor eigen dengan nilai eigen yang besar memiliki peranan paling penting dalam proses transformasi dimensi. Hal tersebut dikarenakan semakin tinggi nilai eigen maka makin tinggi pula lebar distribusi data pada vektor basis tersebut. Oleh karena itu, mereduksi dimensi dengan cara membuang vektor basis dengan nilai eigen mendekati nol (bernilai rendah) tidak akan membuat kita kehilangan informasi data. Vektor-vektor eigen dengan nilainilai eigen yang
terbesar, disebut sebagai principal components dari sebuah
matriks. Misalkan kita memilih K buah vektor eigen dengan nilai eigen terbesar dari eigenvectors matriks kovarian yang ada di atas. Maka terbentuklah matriks transformasi
FeatureVectors (berukuran
3*K) yang merupakan subset dari
35
eigenvectors, dengan K < 3. Apabila λ2 > λ3 > λ1, maka FeatureVectors dapat berbentuk Penggunaan seluruh vektor eigen yang ada sebagai
FeatureVectors juga
diperbolehkan, namun hal itu berarti tidak adanya pengurangan dimensi dari matriks kovarian. Principal Component dari suatu matriks kovarian menunjukkan korelasikorelasi yang kuat dari variabel-variabel, dan menghilangkan korelasi-korelasi yang lemah. Hasilnya, PCA akan dapat mereduksi dimensi dari matriks dengan hanya menyertakan variabel-variabel yang memiliki hubungan (korelasi) kuat dengan variabel-variabel lain, dan menghilangkan variabel-variabel yang kurang signifikan keberadaannya dalam sebuah matriks.
