BAB II TINJAUAN PUSTAKA

BAB II TINJAUAN PUSTAKA Tinjauan Teoritis 2.1.1

Usadha Taru Ayurveda sudah ada semenjak 2000 tahun yang lalu. Ayurveda adalah ilmu

pengetahuan tentang hidup yang berasal dari kata sangsekerta Ayur dan Veda. Ayur berarti hidup dan Veda yang berati pengetahuan. Ayurveda berasal dari Negeri India, namun sekarang menyebar ke seluruh Asia dan negara barat. Sekarang ini Ayurveda dipraktekkan oleh negara-negara yang berkembang seperti Amerika Serikat, Amerika Latin, Eropa dan negara lainnya. Pengobatan Ayurveda berkembang pesat karena terbukti aman dan efektif. Ramuan obat Ayurveda yang tersedia biasanya berasal dari bahan tanaman, binatang dan bahan dari mineral-mineral. Bahan-bahan yang berasal dari tanaman seperti yang disebutkan dalam pengobatan tradisional (Usadha) Bali dikenal dengan pengobatan Taru Pramana. Taru berarti tanaman dan pramana yang berarti berkhasiat obat. Masyarakat Bali sudah terbiasa memakai tanaman Taru Premana sebagai obat tradisional oleh para Pengusada atau Balian (Healer). Tanaman Taru Premana ini bermanfaat memberikan perlindungan yang terbaik bagi tubuh melawan penyakit, sehingga sangat baik dipakai setiap hari dan sudah menjadikan bagian dari pola hidup sehat. Bahkan, tidak jarang masyarakat memakaiannya saling berdampingan dengan obat modern, hanya saja waktu minumnya diberikan jarak sekitar 2 jam sebelum meminum obat modern. Biasanya obat yang berasal dari tanaman Taru Premana ini dipakai dalam proses mempercepat pemulihan kesehatan. Herbal Taru Premana ini dibuat berupa ekstrak dari tumbuh-tumbuhan atau sari pati dari air tanaman tersebut diolah diberikan pengeras berupa gula tebu atau gula merah menjadi herbal berupa minuman instan, atau digodok untuk diminum air godokannya atau diolah berupa sari pati tanaman, dikeringkan lalu dimasukkan ke dalam kemasan berupa kapsul.

6

7

2.1.2

Daun Daun merupakan suatu bagian tumbuhan yang paling penting pada

tumbuhan, secara umum daun digunakan oleh tumbuhan untuk melakukan fotosintesis maupun melakukan respirasi. Pada umumnya tiap tumbuhan mempunyai sejumlah besar daun. Daun hanya terdapat pada batang saja dan tidak pernah terdapat pada bagian lain pada tubuh tumbuhan. Daun memiliki berbagai bentuk dasar seperti ditunjukan pada gambar 2.1.

Gambar 2. 1 Bentuk Dasar Daun (Bowo, 2011)

8

Dalam Pengenalan jenis tanaman maka tepi daun juga memberikan peranan penting dalam menentukan jenis suatu tanaman. Tepi daun secara umum ada beberapa jenis seperti ditunjukan pada gambar 2.2.

Gambar 2. 2 Jenis Tepian Daun (Bowo, 2011) Serat daun, lebar daun, warna, dan tekstur kerap kali digunakan dalam klasifikasi jenis daun. Gambar 2.3 menunjukan beberapa jenis daun dengan seratnya, warna, bentuk, lebar, dan tepian daun.

Gambar 2. 3 Contoh Daun (Hati, 2013)

9

2.1.3

Pengolahan citra Pengolahan citra adalah pemrosesan citra, khususnya menggunakan

komputer untuk mengubah suatu citra menjadi citra dengan format yang berbeda. Klasifikasi citra tidak dapat langsung dilakukan, karena itu diperlukan prosesproses preprocessing seperti grayscale, black and white, smoothing, morphology ,dan edge ditection guna mendapatkan fitur sesuai dengan format yang diinginkan. 2.1.3.1 Citra Grayscale Citra grayscale merupakan citra digital yang hanya memiliki sebuah nilai kanal pada setiap pixelnya. Nilai tersebut digunakan untuk menunjukan tingkat intensitas citra. Grayscale dapat dihitung dengan persamaan berikut (Lee, 2013) : 𝐺𝑟𝑎𝑦 = 0.299 ∗ 𝑅 + 0.587 ∗ 𝐺 + 0.114 ∗ 𝐵 ................................................... (2.1) Keterangan : 𝑅 ∶ 𝑘𝑜𝑚𝑝𝑜𝑛𝑒𝑛 𝑟𝑒𝑑 𝐺 ∶ 𝑘𝑜𝑚𝑝𝑜𝑛𝑒𝑛 𝑔𝑟𝑒𝑒𝑛 𝐵 ∶ 𝑘𝑜𝑚𝑝𝑜𝑛𝑒𝑛 𝑏𝑙𝑢𝑒 2.1.3.2 Citra Biner Citra Biner adalah citra digital yang hanya memiliki dua kemungkinan nilai pixel yaitu hitam dan putih. Citra biner juga disebut sebagai citra BW (black white) atau citra monokrom. Berikut persamaan untuk mengubah citra keabuan menjadi citra biner dengan nilai ambang T (Munir, 2013): 𝑓(𝑥, 𝑦) = {

0, 𝑓(𝑥, 𝑦) < 𝑇 ................................................................................. (2.2) 1, 𝑓(𝑥) ≥ 𝑇

Keterangan : 𝑓(𝑥, 𝑦) ∶ 𝑛𝑖𝑙𝑎𝑖 𝑝𝑖𝑘𝑠𝑒𝑙 𝑑𝑖 𝑡𝑖𝑡𝑖𝑘 𝑥, 𝑦 𝑇

∶ 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑

2.1.3.3 Smoothing Pelembutan citra (image smoothing) bertujuan untuk menekan gangguan (noise) pada citra. Gangguan pada citra umumnya berupa variasi intensitas suatu

10

piksel yang tidak berkolerasi dengan piksel-piksel tetangganya. Piksel yang mengalami gangguan umumnya memiliki frekuensi tinggi. Operasi pelembutan citra dilakukan untuk menekan komponen yang berfrekuensi tinggi dan meloloskan komponen yang berfrekuensi rendah. 2.1.3.3.1 Mean Filter Mean filter bekerja dengan meratakan piksel citra keabuan, sehingga citra yang diperoleh tampak lebih kabur dari kontrasnya. Berikut matrik mean filter 3x3 (elemen bertanda * menyatakan posisi (0,0) dari piksel yang di-konvolusi). 1 1 1 9 9 9 1 1 1 ∗ 9 9 9 1 1 1 [9 9 9] Matrix ini digunakan untuk melakukan smooting dengan melakukan perkalian dengan nilai-nilai tetangga dari citra biner dan mengganti hasil konvulsi dengan nilai tengah matrik citra biner. 2.1.3.4 Diteksi Tepi Diteksi tepi merupakan pendekatan yang paling sering digunakan untuk untuk segmentasi citra berdasarkan perubahan intensitas yang terjadi secara tibatiba, dalam diteksi tepi terdapat 3 langkah dasar yang harus dilakukan (Gonzales, 2008): 1. Image smoothing 2. Ditection of edge point 3. Edge localization 2.1.3.4.1 Dasar Diteksi Tepi Perubahan intensitas yang besar dalam jarak yang singkat dipandang sebagai fungsi yang memiliki kemiringan yang besar. Kemiringan fungsi biasanya

11

dilakukan dengan menghitung turunan pertama (gradien). Berikut persamaan gradien dalam notasi vector (Gonzales, 2008) : 𝜕𝑓

𝑔𝑥 𝜕𝑥 ∇𝑓 = 𝑔𝑟𝑎𝑑(𝑓) = [𝑔 ] = [𝜕𝑓 ] .......................................................................... (2.3) 𝑦 𝜕𝑦

Dalam hal ini, 𝑔𝑥 = 𝑔𝑦 =

𝜕𝑓(𝑥,𝑦) 𝜕𝑥 𝜕𝑓(𝑥,𝑦) 𝜕𝑦

= =

𝑓(𝑥+∆𝑥,𝑦)−𝑓(𝑥,𝑦) ∆𝑥 𝑓(𝑥,∆𝑦+𝑦)−𝑓(𝑥,𝑦) ∆𝑦

........................................................................... (2.4) .......................................................................... (2.5)

Umumnya ∆𝑥 = ∆𝑦 = 1, sehingga persamaan turunan pertama menjadi (Munir, 2013): 𝑔𝑥 = 𝑔𝑦 =

𝜕𝑓(𝑥,𝑦) 𝜕𝑥 𝜕𝑓(𝑥,𝑦) 𝜕𝑦

= 𝑓(𝑥 + 1, 𝑦) − 𝑓(𝑥, 𝑦) ............................................................... (2.6) = 𝑓(𝑥, 1 + 𝑦) − 𝑓(𝑥, 𝑦) ............................................................... (2.7)

Kedua turunan diatas dapat dipandang sebagai dua buah mask konvulsi berikut (Munir,2013): 𝑔𝑥 = [−1 1] ................................................................................................... (2.8) 1 𝑔𝑦 = [ ] ......................................................................................................... (2.9) −1 Berdasarkan konvolusi dengan kedua mask tersebut, kita menghitung kekuatan tepi, G[f(x,y)], yang merupakan magnitudo dari gradien, dan arah tepi 𝛼(𝑥, 𝑦), untuk setiap piksel (Gonzales, 2008): 𝑀(𝑥, 𝑦) = 𝑚𝑎𝑔(∇𝑓) = √𝑔𝑥 2 + 𝑔𝑦 2 ............................................................ (2.10) 𝑀(𝑥, 𝑦) ≈ |𝑔𝑥 | + |𝑔𝑦 | ................................................................................... (2.11) 𝑔𝑦

𝛼 = 𝑡𝑎𝑛−1 (𝑔 ) ............................................................................................... (2.12) 𝑥

Keputusan apakah suatu piksel merupakan tepi atau bukan tepi dinyatakan dengan operasi pengambangan berikut (Munir, 2013): 𝑔(𝑥, 𝑦) = {

1, 𝑗𝑖𝑘𝑎 𝑀(𝑥, 𝑦) ≥ 𝑇 ..................................................................... (2.13) 0, 𝑙𝑎𝑖𝑛𝑛𝑦𝑎

Keterangan : 𝑔(𝑥, 𝑦) ∶ 𝑛𝑖𝑙𝑎𝑖 𝑝𝑖𝑘𝑠𝑒𝑙 𝑑𝑖 𝑡𝑖𝑡𝑖𝑘 𝑥, 𝑦 𝑀(𝑥, 𝑦): 𝑚𝑎𝑔𝑛𝑖𝑡𝑢𝑑𝑜 𝑝𝑎𝑑𝑎 𝑡𝑖𝑡𝑖𝑘 𝑥, 𝑦

12

𝑇

∶ 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑

𝛼

∶ 𝑎𝑟𝑎ℎ 𝑡𝑒𝑝𝑖

dalam hal ini T adalah nilai ambang, piksel tepi dinyatakan putih sedangkan piksel bukan tepi dinyatakan hitam. 2.1.3.4.2 Operator Sobel Suatu pengatuan piksel di sekitar piksel (x,y) : 𝑎𝑜 𝑎1 𝑎2 [𝑎7 (𝑥, 𝑦) 𝑎3] 𝑎6 𝑎5 𝑎4 Operator Sobel adalah magnitude dari gradient yang dihitung dengan : 𝑀 = √𝑆𝑥 2 + 𝑆𝑦 2 ........................................................................................... (2.14) Turunan parsial dihitung dengan : 𝑆𝑥 = (𝑎2 + 𝑐𝑎3 + 𝑎4) − (𝑎𝑜 + 𝑐𝑎7 + 𝑎6 ................................................... (2.15) 𝑆𝑦 = (𝑎𝑜 + 𝑐𝑎1 + 𝑎2) − (𝑎6 + 𝑐𝑎5 + 𝑎4) ................................................. (2.16) Dengan konstanta c adalah 2, dalam bentuk mask, Sx dan Sy dapat dinyatakan sebagai : −1 0 𝑆𝑥 = [−2 0 −1 0

1 2] 1

1 2 1 𝑆𝑦 = [ 0 0 0] −1 −2 −1

Arah tepi dihitung dengan persamaan : 𝑆𝑦

𝛼(𝑥, 𝑦) = 𝑡𝑎𝑛−1 (𝑆𝑥 ) ..................................................................................... (2.17) 2.1.3.5 Structuring Elements (SE) Operasi morphologi menggunakan dua input himpunan yaitu suatu citra (pada umumnya citra biner) dan suatu kernel. Khusus dalam morphologi, istilah kernel biasa disebut dengan structuring elements. SE merupakan suatu matrik dan pada umumnya berukuran kecil, yang digunakan dalam proses morphology. Berikut contoh SE berbentuk disk. 0 1 [1 1 0 1

0 1] 0

13

2.1.3.6 Opening Operasi opening merupakan operasi erosi yang diikuti oleh operasi dilasi. Operasi ini mencegah penurunan ukuran objek secara keseluruhan. Pada citra grayscale operasi ini memberikan efek penurunan intensitas bagian citra yang terang yang berukuran lebih kecil dari SE. Sedangkan untuk bagian terang yang lebih besar dari SE tidak berubah. Adapun perubahan yang terjadi setelah proses opening.

(a) Gambar 2. 4 (a) Citra RGB

(b) (b) Citra Hasil Opening Morphology

2.1.3.7 HU Invariant Moment Citra daun memiliki ukuran ruang vektor yang besar, asumsikan memiliki citra berukuran 100x100 piksel dan akan menghasilkan vector pengamatan dengan dimensi 100x100 = 10000, jika dilakukan proses komputasi akan memerlukan waktu komputasi yang lama. Oleh karena itu perlu dilakukan transformasi ruang vector menjadi dimensi yang lebih rendah namun memiliki kualitas citra yang sama baiknya dengan citra asli. Metode HU Invariant Moment merupakan metode yang umum digunakan pada citra agar memperoleh dimensi yang lebih rendah dan memiliki kualitas citra yang baik dan lebih bervariasi. Citra 2D dengan fungsi f(x,y) dan berordo (p+q) didefinisikan sebagai (Huang, 2010): ∞

∞

𝑀𝒑𝒒 = ∫−∞ ∫−∞ 𝑥 𝑝 𝑦 𝑞 𝑓(𝑥, 𝑦)𝑑𝑥𝑑𝑦 ................................................................ (2.18) Untuk p,q=1,2,… citra dengan intensitas piksel I(x,y), maka raw moments dihitung dengan : 𝑴𝒊𝒋 = ∑𝑥 ∑𝑦 𝑥 𝑖 𝑦 𝑗 𝐼(𝑥, 𝑦) ............................................................................... (2.19)

14

Sedangkan untuk central moments didefinisikan sebagai (Huang, 2010): ∞

∞

𝜇𝑝𝑞 = ∫−∞ ∫−∞(𝑥 − 𝑥̅ )𝑝 (𝑦 − 𝑦̅)𝑞 𝑓(𝑥, 𝑦)𝑑𝑥𝑑𝑦 .............................................. (2.20) Untuk citra digital maka persamaan diatas menjadi : 𝜇𝑝𝑞 = ∑𝑥 ∑𝑦(𝑥 − 𝑥𝑜 )𝑝 (𝑦 − 𝑦𝑜 )𝑞 𝑓(𝑥, 𝑦) (𝑝, 𝑞 = 0,1,2, … ) ......................... (2.21) Dengan 𝑚

10 𝑥𝑜 = 𝑚𝑜𝑜 ......................................................................................................... (2.22)

𝑚

𝑦𝑜 = 𝑚01 ......................................................................................................... (2.23) 𝑜𝑜

Untuk Rotation Invariant Moments dihitung dengan (Fang, 2014): 𝐼1 = 𝜂20 + 𝜂02 ................................................................................................ (2.24) 𝐼2 = (𝜂20 + 𝜂02 )2 + 4𝜂11 2 ............................................................................ (2.25) 𝐼3 = (𝜂30 + 3𝜂12 )2 + (3𝜂21 + 𝜂03 )2 ............................................................ (2.26) 𝐼4 = (𝜂30 + 𝜂12 )2 + (𝜂21 + 𝜂03 )2 ................................................................. (2.27) 𝐼5 = (𝜂30 + 3𝜂12 )(𝜂30 + 𝜂12 )[(𝜂30 + 𝜂12 )2 − 3(𝜂21 + 𝜂03 )2 ] + (3𝜂21 − 𝜂03 )(𝜂21 + 𝜂03 )[3(𝜂30 + 𝜂12 )2 − (𝜂21 + 𝜂03 )2 ] ............................ (2.28) 𝐼6 = (𝜂20 + 𝜂02 )[(𝜂30 + 𝜂12 )2 − (𝜂21 + 𝜂03 )2 ] + 4𝜂11 (𝜂30 + 𝜂12 )(𝜂21 + 𝜂03 ) ......................................................................................................................... (2.29) 𝐼7 = (3𝜂21 + 𝜂03 )(𝜂30 + 𝜂12 )[(𝜂30 + 𝜂12 )2 − 3(𝜂21 + 𝜂03 )2 ] + (𝜂12 + 𝜂30 )(𝜂21 + 𝜂03 )[3(𝜂30 + 𝜂12 )2 − (𝜂21 + 𝜂03 )2 ] .............................. (2.30) Dengan 𝜂𝑝𝑞 =

𝜇𝑝𝑞 𝑖+𝑗 (1+ ) 𝜇00 2

.................................................................................................. (2.31)

Keterangan : 𝐼𝑛 ∶ 𝑚𝑜𝑚𝑒𝑛 𝑖𝑛𝑠𝑒𝑟𝑠𝑖𝑎 𝑥𝑜 ∶ 𝑝𝑢𝑠𝑎𝑡 𝑚𝑜𝑚𝑒𝑛 𝑥 𝑦𝑜 ∶ 𝑝𝑢𝑠𝑎𝑡 𝑚𝑜𝑚𝑒𝑛 𝑦 2.1.4

Pengenalan Pola Pola adalah entitas yang terdefinisi dan dapat diidentifikasi melalui ciri-

cirinya (features). Ciri-ciri tersebut digunakan untuk membedakan suatu pola dengan pola lainnya. Ciri yang bagus adalah ciri yang memiliki daya pembeda yang

15

tinggi, sehingga pengelompokan pola berdasarkan ciri yang dimiliki dapat dilakukan dengan keakuratan yang tinggi. 2.1.4.1

SVM (Support Vector Machine) SVM merupakan salah satu metode klasifikasi yang umum digunakan saat

ini oleh banyak peneliti, karena memiliki kemampuan yang baik dalam banyak aplikasi. Ide dasar SVM adalah memaksimalkan batas hyperplane, yang diilustrasikan seperti gambar berikut :

Hyperplane optimal

Hyperplane Nonoptimal

(a) Gambar 2. 5 (a) hyperplane non optimal

(b) (b) hyperplane optimal (Han, 2006)

Pada gambar 2.5 (a) ada sejumlah pilihan hyperplane yang mungkin untuk set data, sedangkan gambar 2.5 (b) merupakan hyperplane dengan margin yang paling maksimal. Meskipun sebenarnya pada gambar 2.5 (a) bisa juga menggunakan hyperplane sembarang, tetapi hyperplane dengan margin yang maksimal akan memberikan generalisasi yang lebih baik pada metode klasifikasi. Konsep klasifikasi dengan SVM dapat dijelaskan secara sederhana sebagai usaha untuk mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah kelas data pada input space. Data yang tergabung pada kelas -1 disimbolkan dengan bentuk lingkaran keabuan, sedangkan data pada kelas +1, disimbolkan dengan bentuk lingkaran berwarna putih.

16

2.1.4.1.1 SVM Linier Setiap data latih dinyatakan oleh (𝑥𝑖 , 𝑦𝑖 ) dengan i=1, 2, …, N, dan 𝑥𝑖 = {𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑞 }𝑇 merupakan atribut (fitur) set untuk data latih ke-i. Untuk 𝑦𝑖 ∈ {−1, +1} menyatakan label kelas. Hyperplane dapat dinotasikan (Prasetyo, 2014): 𝒘. 𝒙𝒊 + 𝑏 = 0 ................................................................................................. (2.32) w dan b adalah parameter model. 𝒘. 𝒙𝒊 merupakan inner-product antara w dan 𝑥𝑖 . Dengan memberikan label -1 untuk kelas pertama dan +1 untuk kelas kedua, maka untuk prediksi semua data uji menggunakan formula (Prasetyo, 2014): 𝑦={

+1, 𝑗𝑖𝑘𝑎 𝑤. 𝑧 + 𝑏 > 0 ........................................................................... (2.33) −1, 𝑗𝑖𝑘𝑎 𝑤. 𝑧 + 𝑏 < 0

Untuk support vector memenuhi persamaan (Prasetyo, 2014): 𝒘. 𝒙𝒂 + 𝑏 = −1 ............................................................................................. (2.34) 𝒘. 𝒙𝒃 + 𝑏 = +1 ............................................................................................. (2.35) Dengan mengurangkan kedua persamaan support vector maka diperoleh jarak antara dua hyperplane dari dua kelas tersebut, dinyatakan dengan persamaan berikut (Prasetyo, 2014): 2

𝑑 = ‖𝑤‖ ........................................................................................................... (2.36) Margin optimal dihitung dengan memaksimalkan jarak antara hyperplane dan data terdekat.

Permasalahan

ini

selanjutnya

diselesaikan

dengan

Quadratic

Programming (QP) dengan meminimalkan invers. Berikut permasalahan QP dalam persamaan matematis (Krisantus, 2007) : Min 1 2

‖𝒘‖2 ............................................................................................................ (2.37)

Subject to 𝑦𝑖 (𝒘. 𝒙𝒊 + 𝑏) ≥ 1, 𝑖 = 1, 2, … , 𝑁 ................................................................... (2.38)

17

Permasalahan ini sulit untuk diselesaikan untuk itu perlu dirubah terlebih dahulu dalam bentuk Lagrange Multipliers (Prasetyo, 2014): 1

𝐿𝑝 = ∑𝑁 𝑖=1 𝛼𝑖 − 2 ∑𝑖,𝑗 𝛼𝑖 𝛼𝑗 𝑦𝑖 𝒙𝑖 𝒙𝑗 ................................................................... (2.39) 𝒙𝑖 . 𝒙𝑗 merupakan dot-product dua buah data dalam data latih. Syarat 1: ∑𝑁 𝑖=1 𝛼𝑖 𝑦𝑖 = 0 ................................................................................................. (2.40) Syarat 2: 𝛼𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑁 ...................................................................................... (2.41) Keterangan : 𝐿𝑝 ∶ 𝐿𝑎𝑔𝑟𝑎𝑛𝑔𝑒 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝛼𝑖 ∶ 𝐿𝑎𝑔𝑟𝑎𝑛𝑔𝑒 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟 𝑘𝑒 − 𝑖 𝑦𝑖 ∶ 𝑡𝑎𝑟𝑔𝑒𝑡 𝑥𝑖 ∶ 𝑑𝑎𝑡𝑎 𝑘𝑒 − 𝑖 𝑥𝑖 ∶ 𝑑𝑎𝑡𝑎 𝑘𝑒 − 𝑗 2.1.4.1.2 SVM Nonlinier Jika dalam ANN ada perceptron dan MLP, maka dalam SVM terdapat SVM Linier dan SVM Nonlinier (kernel trick). Seperti halnya Perceptron, SVM sebenarnya adalah hyperplane linier yang hanya bekerja pada data yang dapat dipisahkan secara linier. Untuk data yang distribusi kelasnya tidak linear biasanya menggunakan pendekatan kernel pada fitur data awal set data. Kernel dapat didefinisikan sebagai suatu fungsi yang memetakan fitur data dari dimensi awal (rendah) ke fitur baru dengan dimensi yang relatif lebih tinggi (Prasetyo, 2014). Pendekatan ini berbeda dengan metode klasifikasi pada umunya yang justru mengurangi dimensi awal untuk menyederhanakan proses dan memberikan akurasi prediksi yang lebih baik. Berikut gambar permasalahan non-linear :

18

Gambar 2. 6 SVM-Nonlinear (krisantus, 2007) Pemetaan kernel dengan cara menghitung dot product dua buah vector di ruang dimensi baru dengan memakai komponen kedua buah vector tersebut di ruang dimensi asal sebagai berikut (Prasetyo, 2014): 𝐾(𝑥𝑖 , 𝑥𝑗 ) = 𝑥𝑖 . 𝑥𝑗 ............................................................................................ (2.42) Dan untuk prediksi pada data uji (z) dengan dimensi fitur yang baru dapat diformulasikan (Prasetyo, 2014) : 𝑓(𝑧) = 𝑠𝑖𝑔𝑛(𝑤. z + 𝑏) = 𝑠𝑖𝑔𝑛(∑𝑁 𝑖=1 𝛼𝑖 𝑦𝑖 . K(𝑥𝑖 , z) + 𝑏) ............................. (2.43) Keterangan : 𝑓 ∶ 𝑓𝑢𝑛𝑔𝑠𝑖 𝑘𝑒𝑝𝑢𝑡𝑢𝑠𝑎𝑛 𝛼𝑖 ∶ 𝐿𝑎𝑔𝑟𝑎𝑛𝑔𝑒 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟 𝑘𝑒 − 𝑖 𝑦𝑖 ∶ 𝑡𝑎𝑟𝑔𝑒𝑡 𝑘𝑒 − 𝑖 𝑏 ∶ 𝑏𝑖𝑎𝑠 𝐾 ∶ 𝑓𝑢𝑛𝑔𝑠𝑖 𝑘𝑒𝑟𝑛𝑒𝑙 𝑥𝑖 ∶ 𝑠𝑢𝑝𝑝𝑜𝑟𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 𝑘𝑒 − 𝑖 𝑧 ∶ 𝑑𝑎𝑡𝑎 𝑢𝑗𝑖 N adalah jumlah data yang menjadi support vector, 𝑥𝑖 adalah support vector, dan z adalah data uji yang akan dilakukan prediksi. Berikut beberapa pilihan fungsi kernel (Prasetyo, 2014): Tabel 2. 1 Fungsi Kernel Nama Kernel

Definisi Fungsi

Linear

K(x,y)=x.y

19

Polynomial

K(x,y)=(𝑥. 𝑦 + 𝑐)𝑑

Gaussian RBF

K(x,y)=exp(

−‖𝑥−𝑦‖2 2.𝜎2

)

Sigmoid

K(x,y)=tanh(𝜎(𝑥. 𝑦) + 𝑐)

Invers Multiquadric

K(x,y)=

1 √‖𝑥−𝑦‖2 +𝑐 2

Keterangan : 𝑥, 𝑦 ∶ 𝑠𝑒𝑡 𝑑𝑎𝑡𝑎 𝐾 ∶ 𝑓𝑢𝑛𝑔𝑠𝑖 𝑘𝑒𝑟𝑛𝑒𝑙 𝑐 ∶ 𝑘𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑎 2.1.5

Sequential Minimal Optimization (SMO) SMO merupakan algoritma yang diperuntukan untuk mengoptimalkan SVM.

SMO membantu dalam menyelesaikan persamaan QP SVM (2.39) dengan batasan (2.40) dan (2.41). Ide SMO pada setiap langkahnya adalah memilih dua lagrange multipliers untuk dioptimalkan, jika ditemukan maka update SVM untuk merefleksikan nilai optimal yang baru (Platt, 1998). Permasalahan QP diselesaikan dengan memenuhi kondisi KKT (Karush Kuhn Tucker). Berikut kondisi yang mana QP dapat diselesaikan untuk semua i : 𝛼𝑖 = 0 <=> 𝑦𝑖 𝑢𝑖 ≥ 1 ............................................................................ (2.44) 0 < 𝛼𝑖 < 𝐶 <=> 𝑦𝑖 𝑢𝑖 = 1 .................................................................... (2.45) 𝛼𝑖 = 𝐶 <=> 𝑦𝑖 𝑢𝑖 ≤ 1 ............................................................................ (2.46) Permasalahan QP dapat dilihat seperti pada gambar berikut :

Gambar 2. 7 SMO (Platt, 1998)

20

pada gambar 2.6 terlihat 𝛼1 dan 𝛼2 harus berada dalam batasan 0 ≤ 𝛼1 , 𝛼2 ≤ 𝐶, sedangkan ∑𝑁 𝑖=1 𝑦𝑖 𝛼𝑖 menyebabkan 𝛼1 dan 𝛼2 berada dalam garis diagonal, dua batasan tersebut membuat fungsi objective QP menjadi optimum. Hal ini memberikan penjelasan kenapa lagrange multipliers dapat dioptimalkan (Platt, 1998). Pertama akan dihitung 𝛼2 jika 𝑦1 ≠ 𝑦2 maka akan berlaku aturan berikut (Platt, 1998): 𝐿 = max(0, 𝛼2 − 𝛼1 ) .................................................................................... (2.47) 𝐻 = min(𝐶, 𝐶 + 𝛼2 − 𝛼1 ) ............................................................................ (2.48) Jika sama maka berlaku persamaan berikut : 𝐿 = max(0, 𝛼2 + 𝛼1 − 𝐶) ............................................................................ (2.49) 𝐻 = min(𝐶, 𝛼2 + 𝛼1 ) .................................................................................. (2.50) Turunan kedua fungsi objektif sepanjang garis diagonal dapat dinyatakan sebagai berikut (Platt, 1998) : 𝜂 = 2〈𝑥1 , 𝑥 2 〉 − 〈𝑥1 , 𝑥1 〉 − 〈𝑥 2 , 𝑥 2 〉 ............................................................... (2.51) Untuk menghitung 𝛼2 dapat dilakukan sebagai berikut (Platt, 1998): 𝛼2 𝑛𝑒𝑤 = 𝛼2 −

𝑦 2 (𝐸1 −𝐸2 ) 𝜂

................................................................................ (2.52)

E merupakan error training yang dapat dihitung sebagai berikut : 𝑗 𝑗 𝑖 𝑖 𝐸𝑖 = ∑𝑚 𝑗=1(𝛼𝑗 𝑦 〈𝑥 , 𝑥 〉) + 𝑏 − 𝑦 ................................................................ (2.53)

Setelah itu dapat dihitung 𝛼1 sebagai berikut : 𝛼1 = 𝛼1 + 𝑦1 𝑦 2 (𝛼2 𝑜𝑙𝑑 − 𝛼2 𝑛𝑒𝑤, 𝑐𝑙𝑖𝑝𝑝𝑒𝑑) .................................................. (2.54) Dimana 𝛼2 𝑛𝑒𝑤, 𝑐𝑙𝑖𝑝𝑝𝑒𝑑 didapat dengan persamaan berikut : 𝐻, 𝑖𝑓 𝛼2 𝑛𝑒𝑤 ≥ 𝐻 𝛼2 𝑛𝑒𝑤, 𝑐𝑙𝑖𝑝𝑝𝑒𝑑 = {𝛼2 𝑛𝑒𝑤, 𝑖𝑓 𝐿 < 𝛼2 𝑛𝑒𝑤 < 𝐻 ......................................... (2.55) 𝐿, 𝑖𝑓 𝛼2 𝑛𝑒𝑤 ≤ 𝐿 Sedangkan untuk bias yang baru bisa didapatkan dengan persamaan berikut : 𝑏1 = 𝑏 − 𝐸1 − 𝑦1 (𝛼1 − 𝛼1 𝑜𝑙𝑑 )〈𝑥1 , 𝑥1 〉 − 𝑦 2 (𝛼2 − 𝛼2 𝑜𝑙𝑑 )〈𝑥1 , 𝑥 2 〉 ............. (2.56) 𝑏2 = 𝑏 − 𝐸2 − 𝑦 1 (𝛼1 − 𝛼1 𝑜𝑙𝑑 )〈𝑥1 , 𝑥 2 〉 − 𝑦 2 (𝛼2 − 𝛼2 𝑜𝑙𝑑 )〈𝑥 2 , 𝑥 2 〉 ............ (2.57) 𝑏 = 𝑏1, 0 < 𝛼1 < 𝐶 𝑏 = {𝑏 = 𝑏2, 0 < 𝛼2 < 𝐶 ............................................................................ (2.58) 𝑏1 +𝑏2 2

21

𝐾𝑒𝑡𝑒𝑟𝑎𝑛𝑔𝑎𝑛 ∶ 𝜂

∶ 𝑓𝑢𝑛𝑔𝑠𝑖 𝑜𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒

𝛼

∶ 𝑙𝑎𝑔𝑟𝑎𝑛𝑔𝑒 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑒𝑟

𝑏

∶ 𝑏𝑖𝑎𝑠

𝐸

∶ 𝑒𝑟𝑟𝑜𝑟

2.1.6

BDT (Binary Decsision Tree) Pohon biner merupakan pohon yang terdiri atas sebuah akar yang setiap

vertex memiliki maksimal 2 anak, yakni anak sebelah kiri maupun kanan. Berikut aturan mengenai pohon biner : 1. Jika T adalah pohon biner penuh dengan i simpul internal, maka T memiliki i + 1 simpul terminal dan 2i + 1 jumlah simpul. Berikut adalah contoh binary tree :

Gambar 2. 8 BDT Pohon biner diatas merupakan pohon yang digunakan untuk menyimpan setiap proses SVM dalam node tree, yang mana pada gambar 2.7 root tree diatas membagi kelas 1,2,3,4,5 menjadi dua kelas yang dimisalkan dengan kelas + dan - sehingga pada setiap node pada tree dapat dilakukan proses pelatihan SVM secara rekursif sampai semua data telah terbagi sesuai kelasnya masing-masing. 2.1.7

Random Subsampling Metode random subsampling melakukan metode hold-out beberapa kali

(misalkan k kali) untuk meningkatkan perkiraan kinerja classifier. Metode hold out merupakan metode yang memecah set data menjadi dua yakni data latih untuk

22

training dan data uji untuk testing dengan proporsi tertentu. Andaikan 𝑎𝑐𝑐𝑖 menyatakan akurasi model pada iterasi ke-i. Akurasi keseluruhan dapat ditunjukan oleh formula berikut (Prasetyo, 2014): 1

𝑎𝑐𝑐𝑠𝑢𝑏 = 𝑘 ∑𝑘𝑖=1 𝑎𝑐𝑐𝑖 ....................................................................................... (2.59)