bab ii tinjauan pustaka tinjauan teoritis 2.1.1 usadha taru 2.pdf · jarak sekitar 2 jam sebelum...
Post on 21-Mar-2019
216 Views
Preview:
TRANSCRIPT
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)
top related