BAB II TINJAUAN PUSTAKA
2.1
Fuzzy Local Binary Pattern (FLBP) Fuzzifikasi pada pendekatan LBP meliputi transformasi variabel input
menjadi variabel fuzzy, berdasarkan pada sekumpulan fuzzy rule. Dalam hal ini, digunakan dua fuzzy rule untuk mendapatkan nilai biner dan nilai fuzzy, berdasarkan deskripsi relasi antara nilai pada circular sampling 𝑝! dan piksel pusat 𝑝!"#$"% (Iakovidis 2008), yaitu : Rule R0: Semakin negatif nilai ∆𝑝! maka nilai kepastian terbesar dari 𝑑! adalah 0. Rule R1 : Semakin positif nilai ∆𝑝! maka nilai kepastian terbesar dari 𝑑! adalah 1.
Gambar 1 Membership function m0() dan m1() sebagai fungsi dari Δpi. Dari rules R0 dan R1, dua membership function 𝑚! ( ) dan 𝑚! ( ) dapat ditentukan. Fungsi m0() mendefinisikan derajat dimana 𝑑! adalah 0. Membership function 𝑚! ( ) adalah fungsi menurun (Gambar 1) yang didefinisikan sebagai berikut : 0 𝑚! 𝑖 =
!!!!! ! .!
1
𝑖𝑓 ∆𝑝! ≥ 𝐹 𝑖𝑓 − 𝐹 < ∆𝑝! < 𝐹
(1)
𝑖𝑓 ∆𝑝! ≤ −𝐹
Sementara, membership function 𝑚! ( ) mendefinisikan derajat dimana 𝑑! adalah 1. Fungsi 𝑚! ( ) didefinisikan sebagai berikut (Gambar 1) :
6
1 𝑚! 𝑖 =
!!!!! ! .!
𝑖𝑓 ∆𝑝! ≥ 𝐹 𝑖𝑓 − 𝐹 < ∆𝑝! < 𝐹
0
(2)
𝑖𝑓 ∆𝑝! ≤ −𝐹
dimana 𝐹 𝜖 (0,255] merepresentasikan threshold FLBP yang akan mengontrol derajat ketidakpastian. Metode LBP original hanya menghasilkan satu kode LBP saja, sedangkan dengan metode FLBP akan menghasilkan satu atau lebih kode LBP. Gambar 7 menyajikan contoh pendekatan FLBP, dimana dua kode LBP (A,B) mencirikan ketetanggaan 3x3. Masing-masing nilai LBP yang dihasilkan memiliki tingkat kontribusi (CA, CB) yang berbeda, bergantung pada nilai-nilai fungsi keanggotaan m0() dan m1() yang dihasilkan. Untuk ketetanggaan 3×3, kontribusi CLBP dari setiap kode LBP pada histogram FLBP didefinisikan sebagai berikut (Keramidas 2008): !
𝐶!"# =
𝑚!" (𝑖) !!!
( 3)
Total kontribusi ketetanggaan 3×3 ke dalam bin histogram FLBP yaitu : !""
𝐶!"# = 1 !"#!!
( 4)
Pada Gambar 2 yang menunjukan matriks hasil nilai LBP menggunakan fuzzifikasi. Proses fuzzifikasi satu daerah ketetanggaan 3x3 akan menghasilkan 1 sampai 2n nilai LBP, dimana n merupakan banyaknya nilai Δpi (selisih antara piksel pusat dan piksel tetangga) yang masuk kedalam rentang fuzzy. Proses tersebut dapat mengatasi masalah representasi tekstur yang dihasilkan oleh metode original LBP, yang cenderung memiliki perbedaan rentang nilai LBP yang jauh antara tetangganya.
7
Jatropha curcas Linn. 247
251
253 251 252
240
190
152 211 250
159
130
114 158 219
104
85
96
107 160
74
69
80
89
117
Nilai keabuan piksel 135
143; 1 59
15; 3 1
135; 1 43
143; 1 59; 1 5; 3 1; 1 75; 191; 4 7; 6 3
14; 1 5; 3 0; 3 1
135; 1 43; 1 51; 1 59; 167; 1 75; 1 83; 1 91; 199; 2 07; 2 15; 2 23; 231; 2 39; 2 47; 2 55
5; 7 ; 1 3; 1 5;21; 2 3; 29;31; 3 7;39;45; 4 7;53; 55; 6 1;63; 1 33; 1 35; 141;143;149; 1 51; 1 57; 159; 1 65; 1 67;173; 1 75; 181; 1 83;189; 1 91
15; 3 1; 1 43; 1 59
Nilai FLBP Gambar 2 Skema komputasi FLBP dengan F=19 (Valerina 2012). Valerina (2012) melakukan percobaan setiap nilai threshold FLBP (F) untuk identifikasi tumbuhan, sehingga mendapatkan akurasi identifikasi yang beragam (Gambar 3), akurasi yang tertinggi didapat terlihat pada nilai threshold FLBP, F = 4. Pengambilan nilai threshold FLBP dilihat dalam hal adanya pengaruh besarnya nilai threshold FLBP terhadap komputasi. Semakin besar rentang nilai
Akurasi (%)
parameter, semakin banyak piksel yang harus diproses. FLBP (8,1)
100 90 80 70 60 50 40 30 20 10 0 0
1
2
3
4
5
6
7
8 9 10 11 12 13 14 15 16 17 18 19 20 Parameter fuzzifikasi F
Akurasi (%)
8
FLBP (8,2)
100 90 80 70 60 50 40 30 20 10 0 0
1
2
3
4
5
6
7 8 9 10 11 12 13 14 15 16 17 18 19 20 Parameter fuzzifikasi F
Gambar 3 Hasil akurasi klasifikasi citra menggunakan FLBP. 2.2
Probabilistic Neural Network (PNN) PNN merupakan Artificial Neural Network (ANN) yang menggunakan
teorema probabilitas klasik (pengklasifikasian Bayes). PNN diperkenalkan oleh Donald Specht pada tahun 1990. PNN menggunakan pelatihan (training) supervised. Training data PNN mudah dan cepat. Bobot bukan merupakan hasil training melainkan nilai yang dimasukkan (tersedia) (Wu et al. 2007).
Gambar 4 Struktur PNN. Struktur PNN pada Gambar 4 terdiri atas empat lapisan, yaitu lapisan masukan, lapisan pola, lapisan penjumlahan, dan lapisan keputusan/keluaran. Lapisan masukan merupakan objek 𝑥 yang terdiri atas 𝑘 nilai ciri yang akan diklasifikasikan pada 𝑛 kelas. Proses-proses yang terjadi setelah lapisan masukan adalah:
9
1. Lapisan pola (pattern layer) Lapisan pola menggunakan 1 node untuk setiap data pelatihan yang digunakan. Setiap node pola merupakan perkalian titik (dot product) dari vektor masukan 𝑥 yang akan diklasifiksikan dengan vektor bobot 𝑥!" , yaitu 𝑍! = 𝑥 . 𝑥!" , 𝑍! kemudian dibagi dengan bias tertentu σ dan selanjutnya dimasukkan ke dalam fungsi radial basis, yaitu 𝑟𝑎𝑑𝑏𝑎𝑠 𝑛 = exp (−𝑛)! . Dengan demikian, persamaan yang digunakan pada lapisan pola adalah. 𝑓 𝑥 = 𝑒𝑥𝑝 −
(!!!!" )! (!!!!" )
!
!! !
(5)
𝑘𝑒𝑡 ∶ 𝑥, 𝑚𝑒𝑟𝑢𝑝𝑎𝑘𝑎𝑛 𝑚𝑎𝑡𝑟𝑖𝑘𝑠 𝑜𝑏𝑗𝑒𝑘 𝑑𝑒𝑛𝑔𝑎𝑛 𝑖 𝑏𝑎𝑟𝑖𝑠 𝑑𝑎𝑛 𝑗 𝑘𝑜𝑙𝑜𝑚 2. Lapisan penjumlahan (summation layer) Menerima masukan dari node lapisan pola yang terkait dengan kelas yang ada. Persamaan yang digunakan pada lapisan ini adalah: 𝑝 𝑥 =
! ! (!!)! ! ! !
(!!!!" )! (!!!!" ) ! ! ) !!! exp(− !! !
(6)
3. Lapisan keluaran (output layer) Menentukan kelas dari input yang diberikan. Input x akan masuk ke Y jika nilai 𝑝! 𝑥 paling besar dibandingkan kelas lainnya. 2.3
Algoritme Genetika Algoritme genetika atau genetic algorithm (GA) adalah pengoptimasian dan
teknik pencarian berdasarkan prinsip genetik dan seleksi alam (Haupt & Haupt 2004). GA dapat diaplikasikan untuk menyelesaikan permasalahan optimasi kombinasi, yaitu dengan mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi (Hermawanto 2003). GA digunakan untuk menemukan solusi dalam masalah yang kompleks melalui kumpulan-kumpulan metode atau teknik seperti fungsi evaluasi (fitness function), pindah silang, mutasi, dan seleksi alam (Owais et. al 2005).
10
GA dikarakterisasi dengan 5 komponen dasar yaitu : 1
Representasikan kromosom untuk memudahkan penemuan solusi dalam masalah pengoptimasian.
2
Inisialisasi populasi.
3
Fitness function yang mengevaluasi setiap solusi.
4
Proses genetik yang menghasilkan sebuah populasi baru dari populasi yang ada.
5
Parameter genetika seperti ukuran populasi, probabilitas proses genetik, banyaknya generasi, dan lain-lain. Gen dan Cheng (2000) menjelaskan bahwa algoritme genetika memelihara
populasi dari individu (Pi) pada setiap generasi ke-i. Setiap individu merepresentasikan sebuah solusi potensial yang kemudian dievaluasi untuk dinilai fitness-nya dan setiap individu menjalani transformasi stokastik menggunakan operasi genetik untuk membentuk individu baru. Ada dua jenis transformasi yang digunakan yaitu mutasi dan pindah silang (crossover). Transformasi tersebut akan menghasilkan individu baru C(i) yang akan dievaluasi kembali. Setelah beberapa generasi dilakukan pada setiap individu, hasil akhir yang didapat menjadi konvergen dan terbaik. Individu terbaik inilah yang diharapkan menjadi solusi optimal atau suboptimal dari masalah. Struktur umum dari algoritme genetika dijelaskan sebagai berikut: Prosedur: Algoritme Genetika begin i ← 0; inisialisasi P(i); evaluasi P(i); while (i <= maksimum iterasi) do begin rekombinasi P(i); evaluasi C(i); pilih P(i+1) dari P(i) dan C(i); i ← i + 1; end end
11
2.3.1 Inisialisasi Populasi Algoritme Genetika (GA) dimulai dengan sebuah group dari kromosom yang disebut populasi. Populasi memiliki Npop kromosom dan berbentuk matriks dengan ukuran Npop x Nbits serta diisi dengan bilangan acak (Bagchi 1999). 2.3.2 Fungsi Evaluasi Fungsi Evaluasi atau fitness function adalah ukuran kinerja atau fungsi yang mengevaluasi seberapa baik nilai setiap solusi yang terjadi (Klabbankoh 1999). Nilai evaluasi dari sebuah kromosom tergantung seberapa baik kromosom tersebut memecahkan masalah yang ada (Mitchell 1998). 2.3.3 Seleksi Seleksi adalah proses memilih individu pada populasi yang memiliki nilai evaluasi baik untuk dilanjutkan ke proses pindah silang dan mutasi (Cox 2005). Proses seleksi harus terjadi disetiap iterasi agar kromosom dalam populasi dapat berkembang sehingga mendapatkan anggota kromosom yang paling sesuai dengan fungsi tujuannya (Haupt & Haupt 2004). 2.3.4 Pindah Silang Pindah silang dikenal sebagai recombination dimana dalam prosesnya terjadi pertukaran informasi antara induk dalam mating pool sehingga menghasilkan individu baru yang merupakan solusi (Bagchi 1999). Pindah silang merupakan komponen paling penting dalam GA pada proses genetik (Gen & Cheng 1997). Pindah silang ini bisa juga berakibat buruk jika ukuran populasi sangat kecil. Dalam suatu populasi yang sangat kecil, suatu kromosom dengan gen-gen yang mengarah ke solusi akan sangat cepat menyebar ke kromosomkromosom lainnya. Probabilitas pindah silang Pc digunakan untuk mengatasi masalah penyebaran tersebut. Teknik pindah silang dapat dilakukan dalam berbagai cara mulai dari one point crossover atau disebut satu titik potong, sampai multiple-point crossover (Klabbankoh 1999). Jika struktur direpresentasikan sebagai string biner, crossover dapat diimplementasikan dengan memilih titik secara acak, titik potong yang dipilih akan menyebabkan antar gen dari kromosom induk saling bertukar.
12
Sebagai contoh dua kromosom induk melakukan pindah silang antar posisi 5 sampai posisi 11 (Gambar 5). 1 1
0 0
1 0
1 1
1 1
1 0
1 0
1 1
0 1
0 1
1 1
1 0
1 0
0 0
1 0
1 0
0 0
1 0
Hasil pindah silang menghasilkan kromosom baru 1 1
0 0
1 0
1 1
1 1
0 1
0 1
1 1
1 0
1 0
1 1
1 0
Gambar 5 Ilustrasi pindah silang dua titik potong (two point crossover) 2.3.5 Mutasi Mutasi adalah operator genetik kedua yang digunakan dalam GA. Kromosom yang dihasilkan memiliki kemungkinan bernilai lebih baik atau lebih buruk dari kromosom sebelumnya. Jika kromosom yang terpilih lebih buruk dari kromosom sebelumnya maka kromosom yang terpilih memiliki peluang tereliminasi pada proses seleksi. Mutasi berguna untuk mengembalikan kerusakan akibat proses genetik (Aly 2007). Proses mutasi diimplementasikan pada setiap gen dengan besar probabilitas mutasi Pm. Semakin besar nilai Pm maka proses terjadinya mutasi pada populasi akan semakin banyak. Contoh proses mutasi diperlihatkan pada Gambar 6.
Gambar 6 Proses mutasi kromosom. 2.4
Multi Objective Genetic Algorithm (MOGA) Algoritme genetika multi obyektif merupakan metode baru Algoritme
Genetika (GA) dengan tujuan memecahkan permasalahan multi obyektif (Yandra & Tamura 2007). Permasalah optimasi multi obyektif memiliki beberapa fungsi obyektif, misalnya seperti meminimumkan atau memaksimumkan, dengan bentuk umum sebagai berikut: Minimize/Maximize : fm (x), m = 1, 2, …, M; Ketentuan : gj (x) ≥ 0, j = 1, 2, …, J;
13
hk(x) = 0, k = 1, 2, …, K; xi(L)≤ xi ≤ xi(U), i = 1, 2, …, N; Kumpulan kendala akhir disebut variable batas, yang membatasi setiap variabel keputusan xi untuk mengambil nilai di dalam xi(L) batas bawah dan xi(U)
batas atas.
2.5
Pareto Optimality Optimasi multi-obyektif tidak mungkin memiliki solusi optimal tunggal
yang secara bersamaan mengoptimalkan semua tujuan. Hasil yang dihasilkan adalah seperangkat solusi yang optimal dengan tingkat yang bervariasi dari nilai tujuan yang disebut solusi Pareto Optimality (Goldberg 1989). Sifat Pareto ditunjukan pada Gambar 7 dan dapat diformalkan menggunakan hubungan dominasi antara solusi alternatif. Solusi yang ditemukan melalui konsep ini bukan berupa satu titik melainkan kumpulan beberapa titik disebut pareto frontier atau pareto set. Pareto set adalah kumpulan titik-titik yang kesemuanya memenuhi konsep pareto optimality.
Gambar 7 Pareto Optimality (Goldberg 1989) 2.6
Crowding Distance Crowding distance merupakan cara untuk membandingkan antara solusi
dengan urutan/rank non-domination yang sama. Crowding distance dilakukan dengan sebuah estimasi parameter yang berbentuk kubus antara front solusi sama dan terdekat. Fungsi crowding distance melibatkan fm(i-1) dan fm(i+1) untuk setiap fungsi objektif m dari setiap solusi i dengan fm(i-1) ≤ fmi≤ fm(i+1), fmmax dan fmmin merupakan nilai maksimum dan minimum fungsi objektif m dan M adalah total
14
jumlah objektif. Crowding distance untuk setiap solusi i dihitung menggunakan rumus :
(7) CD(i) = ∞, jika solusi i adalah batas semua solusi dari setiap fungsi objektif. Sebuah solusi i dikatakan mendominasi solusi j dalam ukuran crowding distance jika : rank(i) < rank(j) or (rank(i) = rank(j) and CD(i) > CD(j)) (Deb et. al 2002). 2.7
Elite Strategy Elite Strategy memiliki sejumlah nE individu anggota populasi baru yang
akan diganti dengan sejumlah nE anggota himpunan solusi optimal pareto. Individu yang dibuang dari populasi dipilih secara acak dengan ketentuan individu yang dibuang adalah individu solusi yang tidak ikut menjadi anggota himpunan solusi optimal pareto. Populasi yang sudah mengalami elite strategy siap untuk kembali menjalani proses evaluasi dan seleksi.
