BAB II DASAR TEORI
Pada bab ini akan dibahas teori-teori pendukung yang digunakan sebagai acuan dalam merancang algoritma. 2.1. Deteksi Bola 2.1.1. Colorspace Colorspace adalah model abstraksi matematis [3,4] untuk menggambarkan representasi warna dalam angka-angka, dan biasanya terdiri dari tiga atau empat unsur warna, seperti RGB, CMYK, HSV, HSL [5], atau YUV. Masing-masing komponen dasar dalam colorspace adalah penyusun warna. YUV colorspace mendefinisikan warna dengan menggunakan elemen luminans (Y) dan dua elemen warna komponen krominans (UV). Ini merupakan perbaikan dari informasi warna yang digunakan dalam televisi hitam putih tua yang hanya menggunakan elemen Y. Elemen Y adalah tingkat kecerahan, lalu komponen U dan V merupakan informasi warna. Smartphone Android Sony Xperia Mini st15i membuat gambar yang diambil oleh kamera dalam YUV420 colorspace[6]. Hal ini dapat dilihat pada Gambar 2.1 bahwa YUV420sp colorspace yang berperforma lebih baik dibandingkan RGBA colorspace. Ketika lampu intensitas berkurang, kinerja deteksi bola dari kedua colorspace akan terdegradasi, tetapi pada RGBA colorspace ini mengurangi tingkat akurasi warna[6]. 2.1.2. Segmentasi Warna Segmentasi warna digunakan untuk memisahkan warna bola oranye serta titik pinalti berwarna putih dengan warna lingkungan lainnya. Segmentasi dilakukan dengan mengatur batas atas dan bawah untuk nilai-nilai elemen dalam gambar. Sebagai hasil, citra biner yang terdiri dari 0 untuk hitam dan 1 untuk putih. 2.1.3. Metode Pusat Masa Pusat massa atau pusat gravitasi pada gambar adalah titik di mana objek gambar tersebar merata. Setelah segmentasi warna telah dilakukan, pusat gravitasi pada gambar biner atau grayscale dapat dihitung [6]. 5
2.2. Penjaga Gawang Seorang penjaga gawang merupakan suatu hal yang utama dalam permainan sepakbola. Untuk menjadi seorang penjaga gawang (kiper), ada beberapa hal yang harus diperhatikan. Pada dasarnya seorang kiper diharuskan memiliki kemampuan dasar pengamatan terhadap bola, serta refleks yang cukup baik, selain itu ada kemampuan individual seorang kiper yang perlu diperhatikan, diantaranya[7] : 2.2.1. Daya Jangkau Kemampuan kiper dalam menjangkau bola sangatlah penting untuk dikuasai. Kiper harus tahu dimana kemampuan menjangkau bola, sehingga dapat menentukan kapan bola akan ditangkap, ditinju, ditangkis, ataupun lompat serta kapan harus menjatuhkan diri untuk menyelamatkan gawang. 2.2.2. Penempatan Posisi Semakin baik posisi kiper berada, semakin mudah pula kiper menghalau serangan lawan. Kiper haruslah paham dimana kedua kaki harus berpijak. Sejauh apa dari gawang, berada pada sudut berapa dan dimana kira-kira lawan membidik tendangannya. Titik ini menjadi awal pengambilan keputusan ketika kiper memutuskan untuk tetap di tempat atau maju keluar sarang untuk menggagalkan usaha penyerang lawan. Disini pula berawal pikiran untuk memutuskan untuk lompat, terbang, menangkis, menyergap. 2.2.3. Refleks Poin penting untuk seorang kiper. Kecepatan bereaksi terhadap bola yang sering berubah arah. Karena apabila seorang kiper tidak memiliki refleks yang bagus, ia akan selalu terlambat dalam menangkis ataupun menghalau bola yang datang. 2.2.4. Konsentrasi Seorang kiper, secara kasat mata seolah tidak selalu bekerja setiap menitnya. Ketika bola berada di area pertahanan lawan, kiper akan cenderung diam. Namun sebenarnya, ketika dalam situasi seperti ini, seorang kiper akan lebih baik jika berkonsentrasi penuh dalam permainan. Konsentrasi sejak serangan lawan belum dibangun akan lebih memudahkannya mengambil keputusan ketika serangan datang. 2.3. Format Lapangan Lapangan sepak bola memiliki ukuran yang akan diuraikan sesuai dengan Gambar 2.1 dan Tabel 2.1
6
Gambar 2.1 Dimensi lapangan
Tabel 2.1 Keterangan dimensi lapangan
A B C D E F G H I
Ukuran Kecil (cm) 900 600 50 225 60 345 180 150
Panjang lapangan Lebar lapangan Kedalaman gawang Lebar gawang Panjang Goal area Lebar Goal area Jarak titik pinalti ke gawang Diameter lingkar tengah lapangan lebar luar lapangan(min.)
Ukuran Besar (cm) 900 600 60 300 100 500 210 150 70
2.4. Metode Decision Tree Decision tree adalah salah satu metode klasifikasi yang menggunakan representasi suatu struktur tree yang yang berisi alternatif-alternatif untuk pemecahan suatu masalah. Tree ini juga menunjukkan faktor-faktor yang mempengaruhi hasil alternatif dari keputusan tersebut disertai dengan estimasi hasil akhir bila kita mengambil keputusan tersebut. Peranan pohon keputusan ini adalah sebagai alat untuk membantu manusia dalam mengambil suatu keputusan[8].
7
Manfaat dari decision tree adalah melakukan proses pemecahan persoalan dalam pengambilan keputusan yang kompleks menjadi lebih sederhana sehingga orang yang mengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan. Konsep yang digunakan oleh decision tree adalah mengubah data menjadi suatu keputusan pohon dan aturan-aturan keputusan(rule), selain itu metode ini juga digunakan untuk memilih atribut mana yang didahulukan dengan menghitung information gain dan juga untuk menyediakan struktur data pada saat pengambilan keputusan ketika robot (objek yang mendapat penerapan dari decision tree di sini adalah robot) menerima data baru seperti kamera atau sensor lainnya. 2.4.1. Entropy Untuk mengimplementasikan pemilihan suatu atribut A dalam decision tree diperlukan informasi yang terkandung dalam suatu konteks atau permasalahan. Informasi yang terkandung di dalam suatu permasalahan tersebut dinamakan entropy. Selain itu entropy juga dapat diartikan sebagai suatu pengukuran dari jumlah ketidakpastian dalam suatu rangkaian peristiwa. Kita asumsikan variable H adalah suatu rangkaian kejadian dan akan dihitung entropy dari kejadian tersebut sehingga suatu entropy dari H dapat dirumuskan[14]
H pi log pi Dan entropy dari sebuah kejadian yang menggambarkan 2 buah probabilitas yang dimisalkan dengan p dan q di mana q = 1-p adalah[14]: H ( p log p q log q)
Sebagai contoh kasus yang pertama, jika robot mempertimbangkan untuk jatuh atau tidak, ini bisa diilustrasikan sebagai suatu bilangan biner 1(jatuh) atau 0(tidak jatuh), dan bilangan 1 atau 0 ini mencakup 1 bit entropy. Contoh lain kasus yang kedua, misalkan robot mempertimbangkan untuk jatuh, tidak jatuh, geser kiri, atau geser kanan. Dengan adanya 4 kemungkinan ini berarti dalam kasus ini memiliki 2 bit entropy, karena pengambilan keputusan ini mencakup 2 bit untuk mendeskripsikan satu dari empat peluang pengambilan keputusan yang ada. Kemudian perhatikan dari kasus pertama, jika ada pengambilan keputusan yang tidak adil di mana robot selalu akan mengambil keputusan untuk jatuh 99% dalam sekali waktu. Kasus ini memiliki ketidakpastian yang sangat kecil dibandingkan dengan kasus pertama yang sudah dijabarkan di awal tadi, yang masih memiliki peluang yang
8
sama untuk jatuh ataupun tidak jatuh. Sehingga dari kasus ini kita membutuhkan entropy yang mendekati 0, tetapi memiliki nilai positif. Sehingga dalam penerapannya, entropy dari suatu variable acak I dengan nilai Vi, masing-masing memiliki peluang P(Vi) dan jumlah sampel positif dimisalkan p dan jumlah sampel negatif dimisalkan dengan n di mana n = 1-p kita gunakan persamaan sebelumnya untuk menghitung entropy dari 2 buah probabilitas. Selain itu kita gunakan log berbasis 2 karena log basis 2 merupakan logaritma biner di mana kita akan merepresentasikan hasilnya dalam sebuah satuan bit. Sehingga perhitungannya dapat didefinisikan sebagai berikut:
I(
p n p p n n , ) ( log 2 log 2 ) pn pn pn pn pn pn
Hasil yang didapat dari suatu entropy berupa suatu bilangan bit dari suatu informasi yang kita dapatkan dari suatu probabilitas[11]. 2.4.2. Information Gain Suatu atribut A yang terpilih membagi suatu set E ke dalam subset-subset E1, … , Ev Sesuai nilai-nilai yang terdapat dalam atribut A, di mana A memiliki sejumlah v nilai-nilai yang berbeda. Di mana nilai-nilai yang berbeda tersebut menjadi pereduksi dari nilai informasi yang didapat (Entropy). Pereduksi atau remainder inilah yang menjadi faktor pengurang untuk diperolehnya nilai information Gain yang akan dihitung. Di mana remainder ini dapat dirumuskan sebagai berikut: v
remainder ( A) i 1
pi ni pi ni , ) I( p n pi ni pi ni
Sehingga Information Gain (IG) atau reduksi dari suatu entropy dari suatu atribut yang diuji dapat dirumuskan sebagai berikut[12]: IG( A) entropy ( A) remainder ( A)
IG( A) I (
p n , ) remainder ( A) pn pn
Nantinya rumus inilah yang akan diterapkan untuk menghitung information gain dari hasil pengujian yang dilakukan penulis. Contoh dari perhitungan akan ditunjukan pada bagian pengujian di tiap mode.
9
2.5. Latar Belakang Pemilihan Metode Decision Tree Penulis memilih decision tree ini disebabkan untuk mengantisipasi perkembangan robot, di mana robot dapat mengalami perkembangan-perkembangan kedepannya entah penambahan modul kamera, sound recognition, sensor-sensor lain, dsb sehingga membutuhkan trial and error serta penambahan data yang makin banyak. Untuk itulah penulis memilih metode decision tree dalam menyusun algoritma sebagai suatu alat bantu dalam pengambilan keputusan. Ada dua algoritma lain yang tergolong juga ke dalam supervised learning, di mana supervised learning ini memanfaatkan data-data dari sejumlah training set. Di mana sejumlah training set didapat dari proses trial and error yang dilakukan. Dua algoritma lain tersebut akan dibandingkan sebagai pertimbangan penulis yang menjadi dasar terpilihnya decision tree sebagai alat bantu dalam pengambilan keputusan, algoritma-algoritma tersebut yaitu Naïve Bayes model, serta jaringan syaraf tiruan. Ketiga algoritma akan dibandingkan dengan menggunakan Tabel 2.2[13]. Tabel 2.2. Tabel perbandingan antara decision tree, Naïve Bayes, serta jaringan syaraf tiruan Attribut Pemodelan
Naïve bayes Sebuah
metode
Decision tree
yang Sebuah metode yang Sebuah
menerapkan teorema Bayes memiliki (probability terhadap
sebuah
metode
yang
struktur memiliki struktur seperti
condition) tree/graph
yang jaringan syaraf pada otak,
kejadian memiliki simpul dan di mana sekumpuan neuron
dengan menerapkan asumsi cabang, independen.
Jaringan syaraf tiruan
di
simpul
dalam ke neuron lain. Bisa terdiri
merupakan cabang
mana terhubung dengan sinapsis
atribut, dari tiga lapisan kumpulan
merupakan neuron,
yaitu
layer
nilai dari atribut, dan masukan, tersembunyi dan simpul
luar/akhir keluaran.
Neuron-neuron
merupakan
antar
klasifikasi akhir
berdekatan terhubung
kedua
layer saling
oleh
sinapsis
yang merupakan pemberi bobot. Metode
Sebagai suatu alat bantu Sebagain suatu alat Sebagain suatu alat bantu 10
pengambilan
keputusan, bantu
pengambilan pengambilan
naïve bayes menggunakan keputusan, decision jaringan perhitungan teorema bayes, tree
keputusan,
syaraf
tiruan
menggunakan menggunakan
model
di mana dalam prosesnya perhitungan entropy, backpropagation,
selama
dihitung probabilitas pada kemudian
dengan proses trial and error yang
tiap
entropy dilakukan
kategori,
menentukan kemunculan diinginkan
lalu nilai frekuensi tersebut
kondisi pada
dapat tersebut
bobot-
bobot
diatur sehingga
yang dihitung
nilai nantinya akan diperoleh
kategori information
gain bobot yang baik dengan
tersebut, dan pada akhirnya yang menghasilkan error yang sekecil mungkin dilakukan pengklasifikasian sebuah nilai bobot dari untuk
mendapatkan
pada
keluaran
nilai dari masing-masing dengan target yang ingin
maksimal dari kondisi yang atribut diinginkan
selisih
dicapai.
kategori
tersebut. kompleksitas
Untuk data kecil perhitungan Decision tree dapat model
backpropagation
dengan teorema bayes lebih digunakan
untuk biasanya digunakan untuk
mudah
bobot menghitung
dilakukan
karena menghitung
data
yang
teorema ini menghitung 2 prioritas
atribut kompleks sehingga kurang
atribut
dalam efektif untuk menggunakan
yang
saling untuk
data
independen. Dan jika data jumlah
yang model ini dengan data yang
yang tersedia banyak maka fleksibel,
meski kecil
perhitungan dengan teorema dengan
sedikit
bayes akan lebih rumit untuk masukkan tetap bisa dilakukan
dihitung
keluaran
atau bobotnya.
11
