BAB II TINJAUAN PUSTAKA

BAB II TINJAUAN PUSTAKA

Untuk menunjang pelaksanaan penelitian ini dilakukan tinjauan pustaka mengenai tinjauan studi yang berisi penelitian-penelitian terkait dengan pengenalan kualitas buah, median filtering, segmentasi menggunakan threshold, fitur warna, fitur bentuk, fitur tekstur, dan klasifikasi metode Support Vector Machine (SVM). 2.1.

Tinjauan Studi Penelitian pertama adalah membahas mengenai kontrol otomatis kualitas

tomat yang dianalisis berdasarkan 3 metode yang berbeda, yaitu LVQ, MLP, dan SVM (Mehrdad et al, 2012). Gambar pertama kali diambil oleh kamera digital dan kemudian data tersebut diproses dengan mengurangi noise dan perbaikan kontras. Lalu dilakukan ekstraksi fitur pada dataset. Fitur yang digunakan adalah derajat kemerahan dan kekuningan yang diperoleh dalam bentuk fuzzy, tingkat kehijauan, moment pertama, moment kedua, moment ketiga, rata-rata tiga moment yang disebutkan sebelumnya, nilai kebulatan, dan luas permukaan. Fitur yang telah didapat, lalu digunakan pada 3 pengklasifikasi yang berbeda dan hasil akhir dibandingkan dan di evaluasi. Hasil penelitian menunjukkan bahwa SVM memiliki kinerja yang lebih baik dibandingkan dengan dua metode alternatif. Penelitian kedua membahas mengenai analisis awal dari sistem klasifikasi kualitas untuk buah Jonagold dan Apel Golden Delicious (Unay dan Gosselin, 2002)). Fitur yang digunakan adalah fitur warna, tekstur, dan wavelet yang di ekstrak dari gambar apel tersebut. Lalu fitur tersebut dijadikan sebgai inputan dalam metode Multi Layer Perceptron - Neural Network. Penelitian ketiga membahas identifikasi dan klasifikasi dari berbagai jenis gambar buah menggunakan jaringan syaraf tiruan (Savakar, 2012). Skema untuk klasifikasi visual yang biasanya dilanjutkan dalam 2 tahap. Tahap pertama, fitur yang diambil mewakili gambar. Tahap kedua, dilakukan klasifikasi dengan inputan yang digunakan dari hasil ekstraksi fitur. Jenis buah yang digunakan 14

15

adalah Apel, Chickoo, Mangga, Jeruk, dan Lemon. Metode Back Propagation Neural Network digunakan untuk mengklasifikasikan dan mengenali sampel gambar buah, menggunakan berbagai jenis fitur yaitu warna, tekstur, kombinasi dari kedua warna dan fitur tekstur. Penelitian ini mengungkapkan bahwa kombinasi fitur warna dan tekstur memiliki performa secara individu dalam identifikasi dan klasifikasi dengan jenis buah yang berbeda. Penelitian keempat membahas klasifikasi buah menggunakan Multikelas SVM (Zhang dan Wu, 2012). Langkah pertama gambar buah diakuisisi oleh kamera digital. Lalu dilakukan proses pengolahan citra yaitu segmentasi menggunakan algoritma split and merge. Kemudian dilakukan proses ekstraksi fitur dengan fitur bentuk, fitur tekstur, dan histogram warna. Pengurangan fitur dilakukan menggunakan metode PCA. Kemudian proses klasifikasi dilakukan menggunakan SVM dengan 3 multikelas dan menggunakan kernel. Hasil yang didapatkan adalah dengan tingkat akurasi terbaik 88.2% menggunakan kernel RBF.

2.2.

Pre-Processing Dataset Pre-processing adalah sebuah operasi awal yang digunakan untuk

memproses sebuah gambar (Sonka, M, et al, 2008). Pre-processing tidak menambahkan informasi pada gambar. Tujuan dari Pre-processing adalah untuk meningkatkan informasi pada gambar yang seharusnya terdistorsi. Informasi pada gambar yang seharusnya bisa di ekstraksi terkadang terhalang oleh gangguan atau noise, sehingga informasi tersebut gagal didapatkan. Beberapa contoh masalah yang terjadi pada gambar yang menyebabkan kualitas gambar menurun adalah contrast yang buruk, berbagai noise, distorsi geometri, dan tingkat fokus yang buruk (Menotti, et al, 2008). Pada penelitian ini, prosedur pre-processing ini dilakukan pada seluruh dataset adalah sebagai berikut : 1. Menghilangkan noise menggunakan metode median filter. 2. Menghilangkan latar belakang menggunakan metode segmentasi.

16

Pengurangan noise atau Noise Reduction termasuk pada kategori khusus pengolahan citra yaitu image restoration atau pemulihan citra. Citra yang diplihkan adalah citra yang rusak, yaitu citra yang nilai intensitas pixelnya berubah. Contohnya adalah dikarenakan blur atau buram yang disebabkan oleh sebab alamiah, tercemar oleh noise atau derau, dan distorsi geometris lensa. Noise merupakan informasi yang tidak diinginkan yang mencemari citra. Noise tersebut berbentuk titik-titik atau pixel-pixel yang memiliki intensitas berbeda yang mengganggu citra. Biasanya noise terjadi pada saat akuisisi citra, seperti sebuah kamera yang memotret, proses scan gambar, dan yang lain-lain. Terdapat banyak filter yang dapa digunakan untuk menghilangkan noise, tetapi pada penelitian ini, filter yang digunakan untuk menghilangkan noise adalah Median Filter. Order-statistic filter adalah filter spasial yang hasilnya didasarkan dari pengurutan atau perangkingan nilai pixel yang merupakan isi daerah citra yang diterapkan oleh filter. Dimana hasil rangking menentukan hasil filter. Orderstatistic yang paling terkenal adalah median filter. Median filter mengganti nilai pixel dengan median dari level intensitas dalam tetangga pixel yang telah dilakukan pengurutan. Nilai pixel pada titik (x,y) dimasukkan dalam komputasi median. Median filter sangat terkenal karena untuk jenis random noise tertentu memberikan kemampuan pengurangan noise yang sangat baik dengan memperhatikan pengurangan blurring filter smoothing linier pada ukuran yang sama. Median filter efektif tertentu menunjukkan adanya noise bipolar dan unbipolar.

2.3.

Fitur Warna Menggunakan Histogram Pada ekstraksi fitur warna, gambar RGB akan dikonversi menjadi HSV.

Kemudian nilai Value akan dihitung kemunculannya menggunakan histogram warna.

17

Gambar 2.1 Ruang Warna HSV

Citra dengan ruang HSV (Hue Saturation Value) menunjukkan ruang warna dalam bentuk tiga komponen utama yaitu Hue, Saturation, dan Value (Ford dan Roberts, 1998). Hue adalah sudut 0 sampai 360 derajat, biasanya 0 adalah merah, 60 adalah kuning, 120 adalah hijau, 180 adalah cyan, 240 adalah biru, dan 300 adalah magenta. Hue menunjukkan jenis warna ditemukan dalam spectrum warna. Saturation adalah ukuran seberapa besar kemurnian warna tersebut. Value adalah seberapa besar kecerahan dari suatu warna atau seberapa besar cahaya dating dari suatu warna. Perhitungan konversi RGB menjadi HSV dapat dirumuskan sebagai berikut : 1.

Normalisasi terlebih dahulu nilai r, g, dan b dengan rumus : 𝑅=

𝑟 𝑟+𝑔+𝑏

(2.1)

𝐺=

𝑔 𝑟+𝑔+𝑏

(2.2)

𝐵=

𝑏 𝑟+𝑔+𝑏

(2.3)

2.

Tentukan nilai max dan min dari nilai R, G, dan B.

3.

Menentukan nilai Saturation dengan rumus : 𝑆=

4.

𝑚𝑎𝑥 − 𝑚𝑖𝑛 𝑚𝑎𝑥

Menentukan nilai Value dengan rumus :

(2.4)

18

𝑉 = 𝑚𝑎𝑥 5.

(2.5)

Menentukan nilai Hue dengan rumus : 𝑅′ =

𝑚𝑎𝑥 − 𝑅 𝑚𝑎𝑥 − 𝑚𝑖𝑛

(2.6)

𝐺′ =

𝑚𝑎𝑥 − 𝐺 𝑚𝑎𝑥 − 𝑚𝑖𝑛

(2.7)

𝐵′ =

𝑚𝑎𝑥 − 𝐵 𝑚𝑎𝑥 − 𝑚𝑖𝑛

(2.8)

𝐻 = 𝑢𝑛𝑑𝑖𝑓𝑖𝑛𝑒𝑑, 𝑆=0 𝐻 = 5 + 𝐵′ , 𝑅 = max 𝑑𝑎𝑛 𝐺 = 𝑚𝑖𝑛 𝐻 = 1 − 𝐺 ′, 𝑅 = max 𝑑𝑎𝑛 𝐺 ≠ 𝑚𝑖𝑛 𝐻 = 𝐻 = 𝑅′ + 1, 𝐺 = max 𝑑𝑎𝑛 𝐵 = 𝑚𝑖𝑛 𝐻 = 3 − 𝐵′ , 𝐺 = max 𝑑𝑎𝑛 𝐵 ≠ 𝑚𝑖𝑛 ′ 𝐻 =3+𝐺 , 𝑅 = 𝑚𝑎𝑥 { 𝐻 = 5 − 𝑅′ , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

(2.9)

𝐻 = 60×𝐻

(2.10)

Histogram warna merupakan fitur yang paling banyak digunakan untuk merepresentasikan ciri warna suatu citra. Citra pada umumnya dikonversi ke dalam suatu ruang warna tertentu, kemudian setiap komponen ruang warna dibuat histogramnya (Putra, 2010).

Gambar 2.2 Citra 4 x 4

Contoh berikut memberikan ilustrasi dalam memperoleh fitur histogram warna. Gambar 2.2 Menunjukkan suatu citra 4 x 4 pixel dengan asumsi citra

19

tersebut mewakili suatu komponen dari suatu ruang warna. Sehingga histogramnya dapat dilihat pada Gambar 2.3 . Berdasarkan histogram warna pada Gambar 2.3 , maka fitur warna citra tersebut adalah 150.

Gambar 2.3 Histogram Warna dari Citra Gambar 2.2

2.4.

Fitur Tekstur Analisis tekstur lazim dimanfaatkan sebagai proses antara untuk

melakukan klasifikasi dan interpretasi citra. Fitur tekstur yang digunakan adalah Entropy, Energy, Contrast, Homogeneity, Correlation, Mean, dan Variance. Untuk pencarian nilai Entropy, Energy, Contrast, Homogeneity, Correlation, dan Variance menggunakan Matriks Kookurensi, sedangkan pencarian nilai Mean menggunakan histogram citra. 1. Entropy Ciri entropy menunjukkan sifat ketidakteraturan suatu image. Ciri entropy diekstrak menggunakan persamaan : 255

𝑒𝑛𝑡𝑟𝑜𝑝𝑦 = − ∑ 𝑝(𝑓𝑛 ). 2log 𝑝(𝑓𝑛 )

(2.11)

𝑛=0

dengan :

p( f n ) = jumlah kemunculan suatu nilai intensitas (nilai histogram suatu nilai intensitas keabuan).

20

fn

= nilai intensitas keabuan dalam suatu image, berada dari rentang 0 hingga 255.

2. Energy Ciri energy menunjukkan sifat homogenitas suatu image, dibagi dengan besar dimensi image tersebut. Ciri energy diekstrak menggunakan persamaan : 𝐸𝑛𝑒𝑟𝑔𝑦 = ∑ 𝑝(𝑖, 𝑗)2

(2.12)

𝑖,𝑗

dimana p(i,j) menyatakan nilai pada baris i dan kolom j pada matriks kookurensi.

3. Contrast Menunjukkan ukuran penyebaran (momen inersia) elemen-elemen matriks citra. Jika letaknya jauh dari diagonal utama, nilai kekontrasan besar. Secara visual, nilai kekontrasan adalah ukuran variasi antar derajat keabuan suatu daerah citra. 𝑐𝑜𝑛𝑡𝑟𝑎𝑠𝑡 = ∑|𝑖 − 𝑗|2 𝑝(𝑖, 𝑗)

(2.13)

𝑖,𝑗

4. Homogeneity Secara matematis, homogenitas GLCM (Gray Level Co-occurrence Matrix) adalah invers dari kontras GLCM, yaitu keseragaman intensitas keabuan pada citra. ℎ𝑜𝑚𝑜𝑔𝑒𝑛𝑒𝑖𝑡𝑦 = ∑ 𝑖,𝑗

𝑝(𝑖, 𝑗) 1 + |𝑖 − 𝑗 |

(2.14)

5. Correlation Menunjukkan ukuran ketergantungan linear derajat keabuan citra sehingga dapat memberikan petunjuk adanya struktur linear dalam citra. 𝐶𝑜𝑟𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛 = ∑ 𝑖,𝑗

(𝑖 − 𝜇𝑖 )(𝑗 − 𝜇𝑗 ) 𝑝(𝑖, 𝑗) 𝜎𝑖 𝜎𝑗

(2.15)

21

𝜎𝑖 = √𝜎𝑖 2 dan 𝜎𝑗 = √𝜎𝑗 2

(2.16)

6. Mean Menunjukkan ukuran dispersi dari suatu citra. 𝜇 = ∑ 𝑓𝑛 𝑝(𝑓𝑛 )

(2.17)

𝑛

dimana fn merupakan suatu nilai intensitas keabuan, sementara p(fn) menunjukkan nilai histogramnya (probabilitas kemunculan intensitas tersebut pada citra).

7. Variance Menunjukkan variasi elemen pada histogram dari suatu citra. 𝜎𝑖 2 = ∑ 𝑝(𝑖, 𝑗)(1 − 𝜇𝑖 )2

(2.18)

𝑖,𝑗

𝜎𝑗 2 = ∑ 𝑝(𝑖, 𝑗)(1 − 𝜇𝑗 )2

(2.19)

𝑖,𝑗

2.5.

Fitur Bentuk Analisis bentuk adalah bentuk suatu objek berkaitan dengan profile dan

struktur fisik dari objek tersebut. Kode rantai atau Chain Code sering digunakan untuk mendeskripsikan atau mengkodekan bentuk atau counter suatu objek.

Gambar 2.4 Arah Kode Rantai

Urutan dalam pembacaan arah satu pixel ke pixel yang lain berdasarkan arah jarum jam. Pembentukan kode rantai dimulai dengan menentukan pixel

22

pertama dari objek. Berdasarkan pixel tersebut kode rantai objek dibentuk dengan mengikuti aturan arah kode rantai. Berdasarkan kode rantainya, analisis terhadap suatu objek dapat dilakukan dengan menghitung keliling (perimeter) dan area.

Gambar 2.5 Objek dengan Kode Rantai 000 007 766 554 444 433 2211

Perimeter menyatakan panjang dari kerangka yang dihasilkan (Putra, 2010). Perimeter dapat dihitung dengan rumus sebagai berikut: 𝑃 = 𝑗𝑢𝑚𝑙𝑎ℎ 𝑘𝑜𝑑𝑒 𝑔𝑒𝑛𝑎𝑝 + √2×𝑗𝑢𝑚𝑙𝑎ℎ 𝑘𝑜𝑑𝑒 𝑔𝑎𝑛𝑗𝑖𝑙

(2.20)

Masuknya faktor √2 pada penentuan perimeter untuk kode ganjil adalah kaena kode ganjil memiliki arah diagonal. Area menyatakan luas dari suatu objek (Putra, 2010). Untuk menghitung area suatu objek, maka hitung terlebih dahulu area setiap kode rantai tersebut dengan aturan sebagai berikut : 𝐾𝑜𝑑𝑒 0 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 + 𝑌

(2.21)

𝐾𝑜𝑑𝑒 1 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 + (𝑌 + 0.5)

(2.22)

𝐾𝑜𝑑𝑒 2 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎

(2.23)

𝐾𝑜𝑑𝑒 3 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 − (𝑌 + 0.5)

(2.24)

𝐾𝑜𝑑𝑒 4 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 − 𝑌

(2.25)

23

𝐾𝑜𝑑𝑒 5 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 − (𝑌 − 0.5)

(2.26)

𝐾𝑜𝑑𝑒 6 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎

(2.27)

𝐾𝑜𝑑𝑒 7 ∶ 𝐴𝑟𝑒𝑎 = 𝐴𝑟𝑒𝑎 + (𝑌 − 0.5)

(2.28)

Setelah perhitungan luas area untuk setiap kode rantai selesai, maka dapat dihitung area objek tersebut dengan rumus : 𝑛

𝐴 = ∑ 𝐴𝑟𝑒𝑎

(2.29)

𝑖=1

2.6.

Support Vector Machine (SVM) Support Vector Machine (SVM) pertama kali diperkenalkan oleh Vapnik

pada tahun 1992 sebagai rangkaian harmonis konsep-konsep unggulan dalam bidang pattern recognition (Satriyo et al, 2003). Sebagai salah satu metode pattern recognition, usia SVM terbilang masih relatif muda. Walaupun demikian, evaluasi kemampuannya dalam berbagai aplikasinya menempatkannya sebagai state of the art dalam pattern recognition, 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 class pada input space.

Gambar 2.6 Alternatif Bidang Pemisah (kiri) dan Bidang Pemisah terbaik dengan Margin (m) Terbesar (kanan)

24

Linearly separable data merupakan data yang dapat dipisahkan secara linier. Misalkan {𝑥1 , … , 𝑥𝑛 } adalah dataset dan yi ∈{+1,−1} adalah label kelas dari data xi. Pada gambar 2.6 dapat dilihat berbagai alternatif bidang pemisah yang dapat memisahkan semua data set sesuai dengan kelasnya. Namun, bidang pemisah terbaik tidak hanya dapat memisahkan data tetapi juga memiliki margin paling besar. Adapun data yang berada pada bidang pembatas ini disebut support vector. Dalam contoh di atas, dua kelas dapat dipisahkan oleh sepasang bidang pembatas yang sejajar. Bidang pembatas pertama membatasi kelas pertama sedangkan bidang pembatas kedua membatasi kelas kedua, sehingga diperoleh: 𝑥𝑖 . 𝑤 + 𝑏 ≥ +1

𝑢𝑛𝑡𝑢𝑘 𝑦𝑖 = +1

(2.30)

𝑥𝑖 . 𝑤 + 𝑏 ≤ −1

𝑢𝑛𝑡𝑢𝑘 𝑦𝑖 = −1

(2.31)

w adalah normal bidang dan b adalah posisi bidang relatif terhadap pusat koordinat. Nilai margin (jarak) antara bidang pembatas (berdasarkan rumus jarak garis ke titik pusat) adalah 𝐷=

|𝑏 − 1 − 𝑏 − 1 | 2 = ‖𝑤‖ ‖𝑤‖

(2.32)

1 ‖𝑤‖

(2.33)

𝑑=

Nilai margin ini dimaksimalkan dengan tetap memenuhi (2.32). Dengan mengalikan b dan w dengan sebuah konstanta, akan dihasilan nilai margin yang dikalikan dengan konstanta yang sama. Oleh karena itu, konstrain (2.32) merupakan scaling constraint yang dapat dipenuhi dengan rescaling b dan w. Selain itu, karena memaksimalkan

1 ‖𝑤‖

sama dengan meminimumkan ‖𝑤‖ 2 dan

jika kedua bidang pembatas pada (2.30) dan (2.31) di representasikan dalam pertidaksamaan (2.34) : 𝑦𝑖 (𝑥𝑖 . 𝑤 + 𝑏) − 1 ≥ 0

(2.34)

Maka pencarian bdang pemisah terbaik dengan nilai margin terbesar dapat dirumuskan menjadi masalah optimasi konstrain, yaitu min‖𝑤‖2

(2.35)

25

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑦 𝑖 (𝑥𝑖 . 𝑤 + 𝑏) − 1 ≥ 0

(2.36)

Persoalan ini akan lebih mudah diselesaikan jika diubah ke dalam formula lagrangian yang menggunakan lagrange multiplier. Lagrangian L harus diminimalkan dengan memandang primal variable w dan b dan memaksimaljan dengan ke dual variable ∝𝑖 , dengan kata lain poin penentu harus sudah ditentukan. Pernyataan bahwa pada poin penentu, yang derivative dari L dengan primal variable harus dihilangkan : 𝜕𝐿 =0 𝜕𝑏

(2.37)

𝜕𝐿 =0 𝜕𝑤

(2.38)

∑ ∝𝑖 𝑦𝑖 = 0

(2.39)

Mengarah ke : 𝑙

𝑖=1 𝑙

𝑤 = ∑ 𝛼𝑖 𝑦𝑖 𝑥𝑖

(2.40)

𝑖=1

Sehingga proses perhitungan dual probelmnya adalah sebagai berikut : 𝑙

1 𝐿(𝑤, 𝑏, 𝛼 ) = ‖𝑤‖2 − ∑ 𝛼𝑖 (𝑦𝑖 (𝑥𝑖 . 𝑤 + 𝑏) − 1) 2

(2.41)

𝑖=1

𝑙

𝑙

𝑙

1 = (𝑤. 𝑤) − (∑ 𝛼𝑖 𝑦𝑖 𝑥𝑖 𝑤 + ∑ 𝑥𝑖 𝑦𝑖 𝑏 − ∑ 𝛼𝑖 ) 2 𝑖=1

𝑖=1

(2.42)

𝑖=1

𝑙

𝑙

𝑙

𝑙

𝑙

𝑖=1

𝑗=1

𝑖=1

𝑗=1

𝑖=1

1 = (∑ 𝛼𝑖 𝑦𝑖 𝑥𝑖 . ∑ 𝛼𝑗 𝑦𝑗 𝑥𝑗 ) − (∑ 𝛼𝑖 𝑦𝑖 (𝑥𝑖 . ∑ 𝛼𝑗 𝑦𝑗 𝑥𝑗 ) + 0 − ∑ 𝛼𝑖 ) 2 𝑙

𝑙

𝑙

1 = ( ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 . 𝑥𝑗 ) − ( ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 . 𝑥𝑗 + 0 − ∑ 𝛼𝑖 ) 2 𝑖,𝑗=1 𝑙

𝑖,𝑗=1

𝑙

𝑖,𝑗=1

(2.44)

𝑖=1

𝑙

1 = ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 . 𝑥𝑗 − ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 . 𝑥𝑗 + ∑ 𝛼𝑖 2 𝑖,𝑗=1

(2.43)

𝑖=1

(2.45)

26

Sehingga didapatkan rumus dual problem adalah 𝑙

𝑙

1 𝐿(𝑤, 𝑏, 𝛼 ) = ∑ 𝛼𝑖 − ∑ 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝑦𝑗 𝑥𝑖 . 𝑥𝑗 2 𝑖=1

(2.46)

𝑖,𝑗=1

Dengan demikian, dapat diperoleh nilai ∝𝑖 yang nantinya digunakan untuk menemukan w. terdapat nilai ∝𝑖 untuk setiap data pelatihan. Data pelatihan yang memiliki nilai ∝𝑖 > 0 adalah support vector sedangkan sisanya memiliki nilai ∝𝑖 = 0. Dengan demikian fungsi keputusan yang dihasilkan hanya dipengaruhi oleh support vector. Formula pencarian bidang pemisah terbaik ini adalah permasalahan quadratic programming, sehingga nilai maksimum global dari ∝𝑖 selalu dapat ditemukan. Dengan menggunakan Quadratic Programming didapatkan nilai alpha (∝). Bila data 𝑥𝑖 memiliki nilai ∝= 0, maka data tersebut bukanlah support vector. Sedangkan bila ∝> 0, maka data tersebut merupakan support vector. Apabila nilai ∝ telah diperoleh, maka 𝑤 ⃗⃗ dan 𝑏 dapat diperoleh dengan menggunakan persamaan (2.47) dan (2.48) . Setelah itu, dapat melakukan proses testing dengan persamaan (2.49). 𝑙

𝑤 ⃗⃗ = ∑ 𝛼𝑖 𝑦𝑖 𝑥𝑖

(2.47)

𝑖=1

1 𝑏 = − (𝑤 ⃗⃗ . 𝑥−1 + 𝑤 ⃗⃗ . 𝑥+1 ) 2

(2.48)

𝑛

𝑓(𝑡) = 𝑠𝑔𝑛 (

∑

𝛼𝑖 𝑦𝑖 𝑡. ⃗⃗⃗ 𝑥𝑖 + 𝑏 )

(2.49)

𝑖=1,𝑥𝑖 ∈ 𝑆𝑉

2.7.

Metode Kernel SVM Banyak teknik data mining atau machine learning yang dikembangkan

dengan asumsi kelinieran. Sehingga algoritma yang dihasilkan terbatas untuk kasus-kasus yang linier. Karena itu, bila suatu kasus klasifikasi memperlihatkan

27

ketidaklinieran, algoritma seperti perceptron tidak bias mengatasinya. Secara umum, kasus-kasus dunia nyata adalah kasus yang tidak linier. Sebagai contoh, perhatikan Gambar 2.7. Data tersebut sulit dipisahkan secara linier. Metode kernel adalah salah satu solusinya. Dengan metode kernel suatu data x di input space di mapping ke feature space D dengan dimensi yang lebih tinggi melalui 𝑚𝑎𝑝 𝜙 sebagai berikut 𝜙: 𝑥_ → 𝜙(𝑥). Karena itu data x di input space menjadi 𝜙(𝑥) di feature space. Sering kali fungsi 𝜙(𝑥) tidak tersedia atau tidak bias dihitung. Tetapi dot product dari dua vector dapat di hitung baik di dalam input space maupun di feature space. Dengan kata lain, sementara 𝜙(𝑥) mungkin tidak diketahui, dot product < 𝜙(𝑥1), 𝜙(𝑥2) > masih dapat dihitung pada feature space. Untuk dapat menggunakan metode kernel, pembatas (constraint) perlu diekspresikan dalam bentuk dot product dari vector data 𝑥𝑖 . Sebagai konsekuensi, pembatas yang menjelaskan permasalahan dalam klasifikasi harus diformulasikan kembali sehingga menjadi bentuk dot product. Dalam feature space ini, dot product < . > menjadi < 𝜙(𝑥 ), 𝜙(𝑥 )′ >. Suatu fungsi kernel, 𝐾(𝑥, 𝑥 ′ ), bias untuk menggantikan dot product < 𝜙(𝑥 ), 𝜙 (𝑥)′ >. Kemudian di feature space, dapat membuat suatu fungsi pemisah yang linier yang mewakili fungsi nonlinier di input space. Gambar 2.7 mendeskripsikan suatu contoh feature mapping dari ruang 2 dimensi ke feature space 2 dimensi.

Gambar 2.7 Contoh Feature Mapping

28

Dalam input space, data tidak dapat dipisahkan secara linier, tetapi dapat dipisahkan di feature space. Karena itu, dengan memetakan data ke feature space menjadikan tugas klasifikasi menjadi lebih mudah. Terdapat beberapa fungsi kernel yang biasa digunakan : Kernel Linier : 𝐾(𝑥, 𝑥 ′ ) = 𝑥 𝑇 ∙ 𝑥′

(2.50)

Kernel Homogeneous Polynomial : 𝐾 (𝑥, 𝑥 ′ ) = (𝑥 ∙ 𝑥′)𝑑

(2.51)

Kernel Gaussian Radial Basis : 𝐾( 𝑥, 𝑥′ ) = exp (−

‖𝑥−𝑥′‖2 2𝜎 2

)

Kernel Hyperbolic Tangent : 𝐾(𝑥, 𝑥 ′ ) = tanh(𝜅𝑥 ∙ 𝑥 ′ + 𝑐)

(2.52) (2.53)

Sepanjang fungsi kernelnya legitimate, SVM akan beroperasi secara benar meskipun tidak diketahui seperti apa map yang digunakan. Fungsi kernel yang legitimate diberikan oleh Teori Mercer, dimana fungsi tersebut harys memenuhi syarat, yaitu continuous dan positive definite. Lebih mudah menemukan fungsi kernel daripada mencari 𝑚𝑎𝑝 𝜙. Pada penerapan metode kernel, tidak perlu mengetahui map apa yang digunakan untuk satu per satu data, tetapi lebih penting mengetahui bahwa dot product dua titik di feature space bias digantikan oleh fungsi kernel.

Gambar 2.8 Representasi Data Kernel