6

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.

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

proses 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, 𝑓(𝑥, 𝑦) < 𝑇

1, 𝑓(𝑥) ≥ 𝑇 ................................................................................. (2.2)

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

9

1

9

1

91

9∗

1

9

1

91

9

1

9

1

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

tiba, 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

−1] ......................................................................................................... (2.9)

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, 𝑗𝑖𝑘𝑎 𝑀(𝑥, 𝑦) ≥ 𝑇

0, 𝑙𝑎𝑖𝑛𝑛𝑦𝑎 ..................................................................... (2.13)

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 1−2 0 2−1 0 1

] 𝑆𝑦 = [1 2 10 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 01 1 10 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) (b)

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)

Gambar 2. 4 (a) Citra RGB (b) Citra Hasil Opening Morphology

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

𝜂𝑝𝑞 =𝜇𝑝𝑞

𝜇00

(1+𝑖+𝑗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 :

(a) (b)

Gambar 2. 5 (a) hyperplane non optimal (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.

Hyperplane

Non-

optimal

Hyperplane

optimal

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−1, 𝑗𝑖𝑘𝑎 𝑤. 𝑧 + 𝑏 < 0

........................................................................... (2.33)

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

2∑ 𝛼𝑖𝛼𝑗𝑦𝑖𝒙𝑖𝒙𝑗𝑖,𝑗

𝑁𝑖=1 ................................................................... (2.39)

𝒙𝑖. 𝒙𝑗 merupakan dot-product dua buah data dalam data latih.

Syarat 1:

∑ 𝛼𝑖𝑦𝑖 = 0𝑁𝑖=1 ................................................................................................. (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 + 𝑏) = 𝑠𝑖𝑔𝑛(∑ 𝛼𝑖𝑦𝑖. K(𝑥𝑖, z) + 𝑏𝑁𝑖=1 ) ............................. (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𝑛𝑒𝑤 ≤ 𝐿 ......................................... (2.55)

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

𝑏1+𝑏2

2

............................................................................ (2.58)

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)