BAB II LANDASAN TEORI

BAB II LANDASAN TEORI

2.1. Data Data adalah bentuk jamak dari datum. Data merupakan keteranganketerangan tentang suatu hal, dapat berupa sesuatu yang diketahui atau dianggap. Jadi, data dapat diartikan sebagai sesuatu yang diketahui atau yang dianggap atau anggapan. Data juga merupakan sejumlah informasi yang dapat memberikan gambaran tentang suatu keadaan, atau masalah baik yang berbentuk angka-angka maupun yang berbentuk kategori atau keterangan (Supardi, 2013). Sesuai dengan macam atau jenis variabel, maka data atau hasil pencatatannya juga mempunyai jenis sebanyak variabel. Data dapat dibagi dalam kelompok tertentu berdasarkan kriteria yang menyertainya, misalnya menurut susunan, sifat, waktu pengumpulan,

sumber pengambilan dan skala

pengukurannya (Supardi, 2013). a. Pembagian Data Menurut Susunannya 1) Data Acak atau Data Tunggal Data acak atau data tunggal adalah data yang belum tersusun atau dikelompokkan kedalam kelas-kelas interval. 2) Data Berkelompok Data berkelompok adalah data yang sudah tersusun atau dikelompokkan kedalam kelas-kelas interval. Data berkelompok disusun dalam bentuk distribusi frekuensi atau tabel frekuensi.

Universitas Sumatera Utara

10

b. Pembagian Data Menurut Sifatnya 1) Data Kualitatif Data kualitatif adalah data yang tidak berbentuk bilangan. Data kualitatif berbentuk pernyataan verbal, simbol, atau gambar. Contoh data kualitatif adalah data gender, data golongan darah, data tempat tinggal atau data jenis pekerjaan. Agar dapat dilakukan proses pada data kualitatif atau non metric, data tersebut harus diubah ke dalam bentuk angka, proses ini dinamakan kategorisasi. Data kualitatif dibedakan menjadi dua jenis, yaitu data nominal dan data ordinal. 2) Data Kuantitatif Data kuantitatif adalah data yang berbentuk bilangan, atau data kualitatif yang diangkakan. Data kuantitatif dapat disebut sebagai data berupa angka dalam arti sebenarnya. Jadi, berbagai jenis operasi matematika dapat dilakukan pada data kuantitatif. Data kuantitatif merupakan data yang didapat dengan jalan mengukur sehingga bisa mempunyai nilai desimal. Contoh data kuantitatif adalah tinggi badan, usia, penjualan barang, dan sebagainya. Sebagai contoh, tinggi badan seseorang bisa bernilai 165 cm atau 165.5 cm. Seperti pada jenis data kualitatif, jenis data kuantitatif juga terbagi menjadi dua, yaitu data interval dan data rasio. c. Pembagian Data Menurut Waktu Pengumpulannya 1) Data Berkala (Time Series)


11

Data berkala adalah data yang terkumpul dari waktu ke waktu untuk memberikan gambaran perkembangan suatu kegiatan. 2) Data Cross Section Data cross section adalah data yang terkumpul pada suatu waktu tertentu untuk memberikan gambaran perkembangan keadaan atau kegiatan pada waktu itu. d. Pembagian Data Menurut Sumber Pengambilannya 1) Data Primer Data primer adalah data yang diperoleh atau dikumpulkan oleh orang yang melakukan penelitian atau yang bersangkutan yang melakukannya. Data primer disebut juga data asli atau data baru. 2) Data Sekunder Data sekunder adalah data yang diperoleh atau dikumpulkan dari sumbersumber yang telah ada. Data itu biasanya diperoleh dari perpustakaan atau dari laporan-laporan/dokumen peneliti yang terdahulu. Data sekunder disebut juga data tersedia. e. Pembagian Data Menurut Skala Pengukurannya 1) Data Nominal Data nominal adalah data yang diberikan pada objek atau kategori yang tidak menggambarkan kedudukan objek atau kategori tersebut terhadap objek atau kategori lainnya, tetapi hanya sekedar label atau kode saja. Data ini hanya mengelompokkan objek/kategori kedalam kelompok tertentu. Data nominal memiliki ciri hanya dapat dibedakan antara data satu dengan


12

lainnya dan tidak bisa diurutkan/dibandingkan. Data ini memiliki ciri yaitu kategori data bersifat saling lepas dan kategori data tidak disusun secara logis. 2) Data Ordinal Data ordinal adalah data yang penomoran objek atau kategori disusun menurut besarnya, yaitu dari tingkat terendah ke tingkat tertinggi atau sebaliknya dengan jarak/rentang yang tidak harus sama. Data ini memiliki ciri seperti ciri data nominal ditambah satu ciri lagi, yaitu kategori data dapat disusun/diurutkan berdasarkan urutan logis dan sesuai dengan besarnya karakteristik yang dimiliki. 3) Data Interval Data interval adalah data dengan objek/kategori yang dapat dibedakan antara data satu dengan lainnya, dapat diurutkan berdasarkan suatu atribut dan memiliki jarak yang memberikan informasi tentang interval antara tiap objek/kategori sama. Besarnya interval dapat ditambah atau dikurangi. Data ini memiliki ciri sama dengan data ordinal ditambah satu ciri lagi, yaitu urutan kategori data mempunyai jarak yang sama. 4) Data Rasio Data rasio adalah data yang memiliki sifat-sifat data nominal, data ordinal, dan data interval, dilengkapi dengan kepemilikan nilai atau titik nol absolut/mutlak dengan makna empirik. Data rasio dapat dibagi atau dikali.


13

2.2. Data Mining Menurut Han & Kamber (2006), data mining adalah kegiatan yang meliputi pengumpulan dan pemakaian data historis yang menemukan keteraturan, pola dan hubungan dalam set data berukuran besar. Maksud dari pengertian ini yaitu proses pencarian informasi yang tidak diketahui sebelumnya dari sekumpulan data besar. Karakteristik Data mining sebagai berikut (Kusrini & Luthfi, 2009) : a) Data mining berhubungan dengan penemuan sesuatu yang tersembunyi dan pola data tertentu yang tidak diketahui sebelumnya. b) Data mining biasa menggunakan data yang sangat besar. Biasanya data yang besar digunakan untuk membuat hasil lebih dipercaya. c) Data mining berguna untuk membuat keputusan yang kritis, terutama dalam strategi. Secara umum ada dua jenis metode pada data mining (Kusrini & Luthfi, 2009), yaitu: a) Metode Prediktive Proses untuk menemukan pola dari data yang menggunakan beberapa variabel untuk memprediksi variabel lain yang tidak diketahui jenis atau nilainya. Teknik yang termasuk dalam predikative mining antara lain klasifikasi, regresi, dan deviasi. b) Metode Descriptive


14

Proses untuk menemukan suatu karakteristik penting dari data dalam suatu basis data. Teknik data mining yang termasuk dalam descriptive mining adalah clustering, association, dan secuential mining. 2.3. Klasifikasi Data Klasifikasi data adalah suatu proses yang menemukan properti-properti yang sama pada sebuah himpunan obyek di dalam sebuah basis data, dan mengklasifikasikannya ke dalam kelas-kelas yang berbeda menurut model klasifikasi yang ditetapkan. Tujuan dari klasifikasi adalah untuk menemukan model dari training set yang membedakan atribut ke dalam kategori atau kelas yang sesuai, model tersebut kemudian digunakan untuk mengklasifikasikan atribut yang kelasnya belum diketahui sebelumnya (Zaki & Meira, 2014). Klasifikasi dan prediksi adalah dua bentuk analisis data yang bisa digunakan untuk mengekstrak model dari data yang berisi kelas-kelas atau untuk memprediksi trend data yang akan datang. Klasifikasi memprediksi data dalam bentuk kategori, sedangkan prediksi memodelkan fungsi-fungsi dari nilai yang kontinyu. Misalnya model klasifikasi bisa dibuat untuk mengelompokkan aplikasi peminjaman pada bank apakah berisiko atau aman, sedangkan model prediksi bisa dibuat untuk memprediksi pengeluaran untuk membeli peralatan komputer dari pelanggan potensial berdasarkan pendapatan dan lokasi tinggalnya. Prediksi bisa dipandang sebagai pembentukan dan penggunaan model untuk menguji kelas dari sampel yang tidak berlabel, atau menguji nilai atau rentang nilai dari suatu atribut. Dalam pendangan ini, klasifikasi dan regresi adalah dua jenis masalah prediksi, dimana klasifikasi 10 digunakan untuk memprediksi nilai-nilai diskrit atau


15

nominal, sedangkan regresi digunakan untuk memprediksi nilai-nilai yang kontinyu. Untuk selanjutnya penggunaan istilah prediction untuk memprediksi kelas yang berlabel disebut classification, dan penggunaan istilah prediksi untuk memprediksi nilai-nilai yang kontinu sebagai prediction (Zaki & Meira, 2014). a)

Model Klasifikasi Data input untuk klasifikasi adalah koleksi dari record. Setiap record dikenal sebagai instance atau contoh, yang ditentukan oleh sebuah tuple (x,y), dimana x adalah himpunan atribut dan y adalah atribut tertentu, yang dinyatakan sebagai label kelas (juga dikenal sebagai kategori atau atribut target). Klasifikasi adalah tugas pembelajaran sebuah fungsi target f yang memetakan setiap himpunan atribut x ke salah satu label kelas y yang telah didefinisikan sebelumnya. Fungsi target juga dikenal secara informal sebagai model klasifikasi.

b) Pemodelan Deskriptif Model klasifikasi dapat bertindak sebagai alat penjelas untuk membedakan objek-objek dari kelas-kelas yang berbeda. Sebagai contoh untuk para ahli Biologi, model deskriptif yang meringkas data. 2.4. Teori Graf Secara informal, suatu graf adalah himpunan benda-benda yang disebut verteks (atau node) yang terhubung oleh sisi (atau edge atau arc). Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai


16

noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis (Didit Budi Nugroho, 2008). Secara formal, Graf G didefinisikan sebagai pasangan himpunan (V,E), yang dalam hal ini: o V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn } o E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en} atau dapat ditulis singkat notasi G = (V, E). Definisi diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial. Sedangkan garis yang hanya berhubungan dengan satu simpul disebut loop (Didit Budi Nugroho, 2008). 2.5. Struktur Pohon Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit. Berikut adalah beberapa sifat pohon (Adiwijaya, 2014) :


17

a) Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon. b) Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi. c) Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal. d) Misalkan G adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit. 2.5.1 Pohon Berakar Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun. Pada Gambar 1 dibawah, a merupakan akar, c, d, f, g, h, i, dan j merupakan daun (Adiwijaya, 2014).

Pohon Berakar

Pohon Berakar setelah tanda panah pada sisi dibuang Gambar 1. Pohon Berakar


18

2.5.2 Terminologi Pohon Berakar

Gambar 2. Terminologi Pohon Berakar a. Anak (child atau children) dan Orangtua (parent) b, c, dan d adalah anak-anak simpul a, a adalah orangtua dari anak-anak itu b. Lintasan (path). Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3. f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda. c. Subtree

Gambar 3. Subtree Pohon Berakar d. Derajat (degree) Derajat sebuah simpul adalah jumlah anak pada simpul tersebut. Contohnya : o

Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m.

o

Simpul yang berderajat 1 adalah simpul d dan g.


19

o

Simpul yang berderajat 2 adalah simpul b dan k.

o

Simpul yang berderajat 3 adalah simpul a dan e.

Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar. Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di atas berderajat 3 e. Daun (leaf) Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun. f. Simpul Dalam (internal nodes) Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam. g. Aras (level) atau Tingkat

Gambar 4. Level dalam Pohon Berakar h. Tinggi (height) atau Kedalaman (depth) Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4. Pohon berakar yang urutan anak-anaknya penting (diperhatikan) maka pohon yang demikian dinamakan pohon terurut (ordered tree). Sedangkan, pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak


20

disebut pohon n-ary. Jika n = 2, pohonnya disebut pohon biner (binary tree) (Adiwijaya, 2014). 2.5.3 Pohon Keputusan (Decision Tree) Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Decision tree merupakan metode klasifikasi yang paling popular digunakan. Selain karena pembangunannya relatif cepat, hasil dari model yang dibangun mudah untuk dipahami. Pada decision tree terdapat 3 jenis node (Munir, 2009), yaitu : a.

Root Node, merupakan node paling atas, pada node ini tidak ada input dan bisa tidak mempunyai output atau mempunyai output lebih dari satu.

b.

Internal Node , merupakan node percabangan, pada node ini hanya terdapat satu input dan mempunyai output minimal dua.

c.

Leaf node atau terminal node , merupakan node akhir, pada node ini hanya terdapat satu input dan tidak mempunyai output.

Gambar 5. Struktur Decision Tree


21

2.6. Probabilitas Bila suatu percobaan mempunyai N(S) hasil percobaan yang berbeda dan masing-masing mempunyai kemungkinan yang sama untuk terjadi, dan bila tepat n(A) diantara hasil percobaan itu menyusun kejadian A, maka peluang kejadian A adalah

Menurut Walpole dan Myers (1986) kaidah-kaidah probabilitas ada beberapa macam, antara lain : 1. Kaidah penjumlahan a. Kaidah penjumlahan dua kejadian yang saling terpisah.

b. Kaidah penjumlahan dua kejadian yang tidak saling bebas.

c. Kaidah penjumlahan n buah kejadian yang saling terpisah. Bila

1

,

2,

⋯,

d. Bila A dan

kejadian-kejadian yang saling terpisah, maka

′ adalah dua kejadian yang satu merupakan komplemen

lainnya maka

2. Kaidah peluang bersyarat Peluang bersyarat B, bila A diketahui dilambangkan dengan ( | ). didefinisikan sebagai


22

3. Kaidah Penggandaan a. Kaidah penggandaan khusus Bila kejadian A dan B saling bebas maka

b. Jika kejadian-kejadian

1,

2,

3,

⋯,

saling bebas, maka

4. Kaidah Bayes Jika kejadian-kejadian

1,

2,

⋯,

S dengan ( ) ≠ 0 untuk = 1, 2, ⋯ ,

merupakan partisi dari ruang sampel maka untuk sembarang kejadian A

yang bersifat ( ) ≠ 0 maka untuk 𝑘 = 1, 2, ⋯ , ∑

∑

2.7. Algoritma CART Algoritma CART termasuk dalam anggota analisis klasifikasi yang disebut decision trees karena proses analisis dari CART digambarkan dalam bentuk atau struktur yang menyerupai sebuah pohon, lebih tepatnya pohon klasifikasi yang berbentuk biner. Biner di sini berarti bahwa setiap pemecahan parent node menghasilkan 2 child nodes. Proses pemecahan node didasarkan pada Indeks Gini (indeks keragaman), yaitu sebuah formula yang menghitung probablitas bahwa sebuah objek adalah anggota kelas j yang berada dalam node t (Damayanti, 2011).


23

2.7.1. Partisi Berulang Biner (Binary Recursive Partitioning) Teknik atau proses kerja dari CART dalam membuat sebuah pohon klasifikasi dikenal dengan istilah Binary Recursive Partitioning. Proses disebut binary karena setiap parent node akan selalu mengalami pemecahan ke dalam tepat dua child node. Sedangkan recursive berarti bahwa proses pemecahan tersebut akan diulang kembali pada setiap child nodes hasil pemecahan terdahulu, sehingga child nodes tersebut sekarang menjadi parent nodes. Proses pemecahan ini akan terus dilakukan sampai tidak ada kesempatan lagi untuk melakukan pemecahan berikutnya. Dan istilah partitioning mengartikan bahwa learning sample yang dimiliki dipecah ke dalam bagian-bagian atau partisi-partisi yang lebih kecil (Damayanti, 2011). Kriteria pemecahan didasarkan pada nilai-nilai dari variabel independen yang dimiliki. Misalkan dimiliki variabel dependen 𝑦 yang bertipe kategorik dan variabel-variabel independen 𝑥1, 𝑥2, ⋯ , 𝑥𝑝 . Proses binary recursive partitioning bisa diilustrasikan sebagai proses pembagian dari ruang berdimensi 𝑝 dari variabel-variabel independen 𝑥 ke dalam partisi-partisi yang berbentuk persegi panjang dan tidak saling bertumpang tindih. Idenya adalah membagi ruang berdimensi 𝑝 dari variabel-variabel independen tadi ke dalam beberapa partisi yang mana masing-masing partisi berisi objek-objek yang homogen atau seragam. Homogen di sini maksudnya adalah objek-objek tersebut merupakan anggota satu kelas yang sama. Walaupun pada kenyataannya keadaan seperti ini tidaklah mutlak diperoleh. Proses splitting akan berlanjut sampai didapatkan pohon


24

klasifikasi yang paling besar atau maksimal (proses splitting tidak bisa dilakukan lagi) (Damayanti, 2011). 2.7.2. Langkah Kerja CART Menurut Lewis (2000) pada dasarnya dalam membuat sebuah pohon klasifikasi, CART bekerja dalam empat langkah utama. Langkah pertama adalah tree building process yaitu proses pembentukan dan pembuatan pohon klasifikasi. Terdiri dari proses splitting nodes yaitu proses pemecahan parent nodes menjadi dua buah child node melalui aturan pemecahan tertentu dan dilakukan secara berulang-ulang serta proses pelabelan kelas yaitu proses mengidentifikasi nodenode yang terbentuk pada suatu kelas tertentu melalui aturan pengidentifikasian. Langkah kedua adalah proses penghentian pembuatan atau pembentukan pohon klasifikasi (stopping the trees building process). Pada tahap ini pohon terakhir atau maximal tree (𝑇𝑚𝑎𝑥 ) telah terbentuk. Langkah ketiga adalah pruning yaitu proses pemangkasan atau pemotongan 𝑇𝑚𝑎𝑥 menjadi pohon yang lebih kecil (T). Sehingga proses tersebut menghasilkan optimal tree atau pohon klasifikasi yang optimal. a. Proses Pemecahan Node Proses pemecahan pada masing-masing parent node didasarkan pada goodness of split criterion (kriteria pemecahan terbaik). Kriteria pemecahan terbaik ini dibentuk berdasarkan fungsi impurity (fungsi keragaman). Fungsi impurity adalah sebuah fungsi 𝜙 yang didefinisikan ⋯

dengan ⋯

dengan ∑

, dimana

.


25

Impurity measure (ukuran impurity)

dari beberapa node t sebagai

berikut (Breiman, et al., 1993) : 𝜙

⋯

maka Gini Diversity Index (Indeks Keragaman Gini) adalah : ∑ Dalam sebuah node t, andaikan terdapat n kelas (1, 2 ⋯ , ). Untuk n = 1 dan i adalah kelas-kelas lainnya maka (2.1) dapat dituliskan sebagai berikut : ∑

[

∑

Karena ∑

⋯

]

, sehingga (2.2) menjadi

[

⋯

]

[

⋯

]

[

⋯

]

( ∑

)

Begitu pula untuk n = 2 dan i adalah kelas-kelas lainnya maka (2.1) dapat dituliskan : ∑

∑


26

Untuk j = 3 dan i adalah kelas-kelas lainnya maka (2.1) dapat dituliskan : ∑

∑

Sehingga untuk n kelas secara umum, didapatkan : ∑

∑

∑

∑

∑

∑

∑

Sehingga berdasarkan (2.1) Gini Diversity Index dapat dituliskan sebagai berikut (Breiman, et al., 1993) : ∑

Jika sebuah split s dalam node t dibagi ke dalam proporsi banyaknya objek yang masuk dalam

𝑅

adalah

proporsi banyaknya objek yang masuk dalam

𝐿

𝑅

, dan

adalah

dengan

𝑅

dengan

𝐿 𝐿

, maka

didefinisikan decrease impurity (pengurangan keragaman) :

Nilai

digunakan sebagai uji goodness of split criterion

(kriteria uji pemecahan terbaik). Suatu split s akan digunakan untuk memecah node t menjadi dua buah node yaitu node

𝑅

dan

𝐿

jika s

memaksimalkan nilai :


27

𝑚𝑎𝑥 Hal ini berarti splitting (pemecahan) dilakukan untuk membuat dua buah node

baru

yang

keragamannya

lebih

kecil

(homogen)

apabila

dibandingkan dengan node awalnya (parent node). Misalkan sebuah pohon klasifikasi telah terbentuk dan memiliki sekumpulan atau himpunan terminal nodes 𝑇̃ , didefinisikan impurity node I(t), dengan

Didefinisikan pula tree impurity (𝑇) , dengan 𝑇

∑

∑

̃

̃

sehingga didapatkan hasil sebagai berikut

b. Pelabelan Kelas Pelabelan kelas adalah proses pengidentifikasian tiap nodes pada suatu kelas tertentu. Pelabelan kelas tidak hanya diberlakukan untuk terminal nodes saja, non-terminal nodes bahkan root node mengalami proses ini. Hal ini dikarenakan setiap non-terminal nodes memiliki kesempatan untuk menjadi terminal nodes. Sehingga proses pelabelan kelas akan terus dilakukan selama proses splitting masih berlanjut (Breiman, et al., 1993). Misalkan sebuah pohon klasifikasi telah terbentuk dan memiliki terminal nodes 𝑇̃. Class assignment rule mengidentifikasikan sebuah kelas ⋯

pada

setiap

diidentifikasikan pada node

terminal

node

𝑇̃.

𝑇̃ dinotasikan dengan

Kelas

yang

. Aturan


28

pelabelan kelas sebagai berikut ; apabila

𝑚𝑎𝑥

maka

(Breiman et al, 1993). c. Proses Penghentian Pemecahan Menurut Lewis (2000), proses splitting atau pembuatan pohon klasifikasi akan berhenti apabila sudah tidak dimungkinkan lagi dilakukan proses pemecahan. Proses pemecahan akan berhenti apabila hanya tersisa satu objek saja yang ada dalam node terakhir atau semua objek yang berada di dalam sebuah node merupakan anggota kelas yang sama bernilai 0 atau 1. 𝑅

(homogen). Kemudian

, dan

resubstitution estimate 𝑅(𝑇) untuk nilai misclassification sama dengan 0. Node-node terakhir atau yang tidak mengalami pemecahan lagi sebagai akibat dari kondisi di atas akan menjadi terminal nodes dan diidentifikasikan pada suatu kelas tertentu sesuai dengan class assignment rule yang telah dijelaskan sebelum ini. Pohon klasifikasi yang terbentuk sebagai hasil dari proses ini dinamakan “maximal tree” (𝑇𝑚𝑎𝑥 ). d. Proses Pemangkasan Pohon Resubstitution estimate 𝑅( ) adalah probabilitas terjadinya misclassification yang dialami beberapa objek-objek tersebut pada node t tertentu. Proses splitting pada node t menyatakan 𝑅( ) yang kecil pada kedua node baru yang terbentuk. Hal ini dibuktikan melalui proposisi berikut (Breiman, et al, 1993); untuk setiap pemecahan node t menjadi dan

𝐿

berlaku 𝑅

𝑅

𝑅

𝑅

.


29

Pohon klasifikasi yang terbentuk dapat berukuran besar dan kompleks dalam mengambarkan struktur data. Sehingga perlu dilakukan suatu pemangkasan, yaitu suatu penilaian ukuran sebuah pohon tanpa mengorbankan kebaikan ketepatan melalui pengurangan simpul pohon sehingga dicapai penghematan gambaran. Pemangkasan dilakukan dengan memangkas bagian pohon yang kurang penting sehingga didapat pohon optimal (Breiman, et al., 1993). Proses pemangkasan pohon klasifikasi dimulai dengan mengambil 𝑅

yang merupakan right child node dan

𝐿

yang merupakan left child node

dari 𝑇𝑚𝑎𝑥 yang dihasilkan dari parent node t. Jika diperoleh dua child node dan parent node yang memenuhi persamaan 𝑅 dan

dipangkas. Dimana 𝑅

𝑅

𝑅

maka

hild node

𝑅

𝑚𝑎𝑥

. Hasilnya adalah pohon 𝑇1 yang memenuhi kriteria 𝑅(𝑇1) =

𝐿

dan

𝑅(𝑇𝑚𝑎𝑥 ). Proses tersebut diulang sampai tidak ada lagi pemangkasan yang mungkin terjadi. 2.8. Logika Fuzzy Logika fuzzy adalah multi-nilai logika yang diperkenalkan oleh Zadeh untuk berurusan dengan ide-ide jelas dan tegas. Ini telah digambarkan sebagai perpanjangan dengan logika Aristotelian dan Boolean konvensional karena berhubungan dengan "derajat kebenaran" agak dari nilai absolut dari "0 dan 1" atau "benar/salah". Logika fuzzy tidak seperti perangkat lunak komputer yang hanya memahami fungsi biner atau nilai konkret seperti 1.5, 2.8, dan lain-lain, melainkan mirip dengan pemikiran manusia dan interpretasi dan memberikan


30

makna pada ungkapan seperti "sering", "kecil" dan "tinggi". Logika fuzzy memperhitungkan bahwa dunia nyata yang kompleks dan ada ketidakpastian, semuanya tidak dapat memiliki nilai absolut dan mengikuti fungsi linear (Godil & Shamim, 2011) Pada himpunan tegas setiap elemen dalam semestanya selalu ditentukan secara tegas apakah elemen itu merupakan anggota himpunan tersebut atau tidak. Tetapi dalam kenyataanya tidak semua himpunan terdefinisi secara tegas. Oleh karena itu perlu didefinisikan suatu himpunan Fuzzy yang bisa menyatakan kejadian tersebut. Himpunan Fuzzy memiliki dua atribut (Kusumadewi, 2002), yaitu : a. Linguistik, yaitu penamaan suatu kelompok yang mewakili suatu keadaan atau kondisi tertentu dengan menggunakan bahasa alami, seperti: lambat, sedang, cepat. b. Numeris, yaitu suatu nilai (angka) yang menunjukkan ukuran dari suatu variabel, seperti: 40, 50, 60, dan sebagainya. Penerapan logika fuzzy dapat meningkatkan kinerja sistem kendali dengan menekan munculnya fungsi-fungsi liar pada keluaran yang disebabkan oleh fluktasi pada variabel masukan. Pendekatan logika fuzzy secara garis besar diimplementasikan dalam tiga tahapan yaitu : 1. Tahapan pengaburan (fuzzification) yakni pemetaan dari masukan tegas ke himpunan kabur. 2. Tahap inferensi, yakni pembangkitan aturan kabur


31

3. Tahap penegasan (defuzzification), yakni transformasi keluaran dari nilai kabur ke nilai tegas. 2.8.1. Fungsi Keanggotaan Fungsi keanggotaan (member function) adalah suatu kurva yang menunjukkan pemetaan titik-titik input data ke dalam nilai keanggotaannya (sering juga disebut dengan derajat keanggotaan) yang memiliki interval 0 sampai 1. Salah satu cara yang dapat digunakan untuk mendapatkan nilai keanggotaan adalah menggunakan pendekatan fungsi (Kusumadewi & Purnomo, 2010). Ada beberapa fungsi yang bisa digunakan. Di antaranya, yaitu: a. Representasi Linear. Pada representasi linear, pemetaan input ke derajat keanggotannya digambarkan sebagai suatu garis lurus. Bentuk ini paling sederhana dan menjadi pilihan yang baik untuk mendekati suatu konsep yang kurang jelas. Ada dua keadaan himpunan linear, yaitu : 

Representasi Linear Naik

Gambar 6. Representasi Linear Naik Fungsi keanggotaan sebagai berikut :

[𝑥]

{

𝑥 𝑎

𝑎 𝑥

𝑥


32



Representasi Linear Turun

Gambar 7. Representasi Linear Turun Fungsi keanggotaan sebagai berikut : [𝑥]

{

𝑥 𝑥

b. Representasi Kurva Segitiga. Kurva Segitiga pada dasarnya merupakan gabungan antara dua garis (linear).

Gambar 8. Representasi Kurva Segitiga Dengan fungsi keanggotaan sebagai berikut : 𝑥 𝑎

[𝑥] {

𝑎𝑎 𝑎 𝑥 𝑥 𝑥


33

c. Representasi Kurva Trapesium. Kurva Trapesium pada dasarnya seperti bentuk segitiga, hanya saja ada beberapa titik yang memiliki nilai keanggotaan 1.

Gambar 9. Representasi Kurva Trapesium Dengan fungsi keanggotaan sebagai berikut : 𝑥 𝑎

[𝑥]

𝑎𝑎 𝑎 𝑥 𝑥 𝑥 𝑥

{ d. Representasi Kurva Bahu

Representasi fungsi keanggotaan fuzzy dengan menggunakan kurva bahu pada dasarnya adalah gabungan dari kurva segitiga dan kurva trapesium. Daerah

yang

terletak

di

tengah-tengah

suatu

variabel

yang

direpresentasikan dalam bentuk segitiga, pada sisi kanan dan kirinya akan naik dan turun. Tetapi terkadang pada salah sisi dari variabel fuzzy yang ditinjau ini terdapat nilai yang konstan.


34

Gambar 10. Representasi Kurva Bahu 2.8.2. Operator Dasar Fuzzy Ada

beberapa

operasi

yang

didefinisikan

secara

khusus

untuk

mengkombinasi dan memodifikasi himpunan Fuzzy. Nilai keanggotaan sebagai hasil dari operasi dua himpunan sering dikenal dengan nama fire strength atau α– predikat. Ada tiga operator dasar yang diciptakan oleh Zadeh (Kusumadewi & Purnomo, 2010), yaitu: a. Operator AND Operator ini berhubungan dengan operasi interseksi pada himpunan. α– predikat sebagai hasil operasi dengan operator AND diperoleh dengan mengambil nilai keanggotaan terkecil antar elemen pada himpunanhimpunan yang bersangkutan. [𝑥 ]

[𝑦]

b. Operator NOT Operasi komplemen pada himpunan Fuzzy adalah sebagai hasil operasi dengan operator NOT diperoleh dengan mengurangkan nilai keanggotaan elemen pada himpunan yang bersangkutan.


35

[𝑥 ] c. Operator OR Operator ini berhubungan dengan operasi union pada himpunan. α– predikat sebagai hasil operasi dengan operator OR diperoleh dengan mengambil

nilai

keanggotaan

terbesar

antar

elemen

pada

himpunanhimpunan yang bersangkutan. [𝑥 ]

[𝑦]

2.8.3. Fungsi Implikasi Tiap – tiap aturan (proposisi) pada basis pengetahuan Fuzzy akan berhubungan dengan suatu relasi Fuzzy. Bentuk umum dari aturan yang digunakan dalam fungsi implikasi adalah: IF x is A THEN y is B Proposisi yang mengikuti IF disebut sebagai anteseden, sedangkan proposisi yang mengikuti THEN disebut sebagai konsekuen. Secara umum, ada dua fungsi implikasi yang dapat digunakan, yaitu : a. Min. Pengambilan keputusan dengan fungsi min, yaitu dengan cara mencari nilai minimum berdasarkan aturan ke-i dan dapat dinyatakan dengan : 𝑥

𝑥

𝑥

𝑥

b. Dot. Fungsi ini akan menskala output himpunan Fuzzy. 2.8. Fuzzy Inference System Fuzzy Inferense System (FIS) atau Fuzzy Inference Engine adalah sistem yang dapat melakukan penalaran dengan prinsip serupa seperti manusia


36

melakukan penalaran dengan nalurinya (Alavi, et al., 2010). Langkah pertama dari FIS adalah menetapkan nilai keanggotaan untuk data input dan output (Alidoosti, et al., 2012). Menurut Kusumadewi & Hartati (2010), sistem inferensi fuzzy merupakan suatu kerangka komputasi yang didasarkan pada teori himpunan fuzzy, aturan fuzzy yang berbentuk IF-THEN, dan penalaran fuzzy. IF (x1 is A1) dengan

(x2 is A2)

(x is A1) THEN y is B

adalah operator (misal : OR dan AND) Sistem inferensi fuzzy didasarkan pada konsep penalaran monoton. Pada

metode penalaran secara monoton, nilai crisp pada daerah konsekuen dapat diperoleh secara langsung berdasarkan fire strength pada antesedennya. Salah satu syarat yang harus dipenuhi pada metode penalaran ini adalah himpunan fuzzy pada konsekuennya harus bersifat monoton (baik monoton naik maupun monoton turun). Salah satu inferensi fuzzy adalah Fuzzy Logic Controller. Fuzzy Logic Controller (FLC) adalah pengendali yang mengendalikan sebuah sistem atau proses dengan menggunakan logika fuzzy sebagai cara pengambilan keputusan. Secara garis besar, terdapat empat komponen utama penyusun FLC, yaitu fuzzification, basis aturan (rule base), modul pengambil keputusan (inference engine), dan modul defuzzifikasi. 2.9.1. Komposisi Aturan Apabila sistem terdiri dari beberapa aturan, maka inferensi diperoleh dari kumpulan dan kolerasi antar aturan. Ada 3 metode yang digunakan dalam melakukan inferensi sistem fuzzy (Kusumadewi, 2002), yaitu :


37

a) Metode Max (Maximum). Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara mengambil nilai maksimum aturan, kemudian menggunakannya

untuk

memodifikasi

daerah

fuzzy,

dan

mengaplikasikannya ke output dengan menggunakan operator OR (union). Jika semua proposisi telah dievaluasi, maka output akan berisi suatu himpunan fuzzy yang merefleksikan kontribusi dari tiap-tiap proposisi. Secara umum dapat dituliskan : [𝑥 ]

𝑚𝑎𝑥

[𝑥 ]

[𝑥 ]

dengan : [𝑥 ] = nilai keanggotaan solusi fuzzy sampai aturan ke – i. [𝑥 ] = nilai keanggotaan konsekuen fuzzy aturan ke – i. b) Metode Additive (Sum). Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan boundedsum terhadap semua output daerah fuzzy. Secara umum dapat dituliskan : [𝑥 ]

𝑚

[𝑥 ]

[𝑥 ]

dengan : [𝑥 ] = nilai keanggotaan solusi fuzzy sampai aturan ke – i. [𝑥 ] = nilai keanggotaan konsekuen fuzzy aturan ke – i. c) Metode OR (Probor). Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan product terhadap semua output daerah fuzzy. Secara umum dituliskan : [𝑥 ]

[𝑥 ]

[𝑥 ]

[𝑥 ]

[𝑥 ]

dengan :


38

[𝑥 ] = nilai keanggotaan solusi fuzzy sampai aturan ke – i. [𝑥 ] = nilai keanggotaan konsekuen fuzzy aturan ke – i. 2.9.2. Metode Mamdani Salah satu metode FLC yang dapat digunakan untuk pengambilan keputusan adalah metode Mamdani. Metode Mamdani sering juga dikenal dengan nama metode Max-Min. metode ini diperkenalkan oleh Ebrahim Mamdani pada tahun 1975 (Kusumadewi, 2002). Untuk medapatkan output diperlukan beberapa tahapan, antara lain: a) Pembentukan himpunan fuzzy. Pada metode Mamdani, baik variabel input maupun variabel output dibagi menjadi satu atau lebih himpunan fuzzy. b) Aplikasi fungsi implikasi (aturan). Fungsi implikasi yang digunakan adalah min. c) Komposisi aturan. Metode yang digunakan dalam melakukan inferensi sistem fuzzy pada Mamdani adalah max. 2.9.3. Defuzzifikasi Ada beberapa metode defuzzifikasi pada komposisi aturan Mamdani (Kusumadewi, 2002), antara lain: a) Metode Centroid (Composite Moment). Pada metode centroid solusi crisp diperoleh dengan cara mengambil titik pusat daerah fuzzy. Secara umum dapat dituliskan: 𝑧

∫ ∫

atau

𝑧

∑ ∑


39

b) Metode Bisektor. Pada metode bisektor solusi crisp diperoleh dengan cara mengambil nilai pada domain yang memiliki nilai keanggotaan separo dari jumlah total nilai keanggotaan pada daerah fuzzy. Dapat dituliskan : zp sedemikian hingga ∫

𝑧

𝑧

∫

𝑧

𝑧

c) Metode Mean of Maximum (MOM). Pada metode mean of maximum solusi crisp diperoleh dengan cara mengambil nilai rata-rata domain yang memiliki nilai keanggotaan maksimum. d) Metode Largest of Maximum (LOM). Pada metode largest of maximumsolusi crisp diperoleh dengan cara mengambil nilai terbesar dari domain yang memiliki nilai keanggotaan maksimum. e) Metode Smallest of Maximum (SOM). Pada metode smallest of maximumsolusi crisp diperoleh dengan cara mengambil nilai terkecil dari domain yang memiliki nilai keanggotaan maksimum. 2.10. Akurasi Klasifikasi Keakuratan hasil klasifikasi dapat diukur dengan menggunakan confusion matrix. Confusion matrix adalah media yang berguna untuk menganalisis seberapa baik classifier dapat mengenali tupel dari kelas yang berbeda (Tan, Steinbach, & Kumar, 2005). Misalkan terdapat dua kelas, maka akan diistilahkan menjadi tupel positif dan tupel negatif. True positive mengacu pada tupel positif yang diberi label dengan tepat oleh classifier, sementara true negative adalah tupel negatif yang diberi label dengan tepat oleh classifier. False positive adalah tupel negatif yang diberi label dengan tidak tepat. Demikian pula, false negative adalah tupel


40

positif yang diberi label dengan tidak tepat. Istilah-istilah ini berguna ketika menganalisis kemampuan classifier dan diringkas dalam tabel berikut. Tabel 1. Confusion Matrix Prediksi Observasi J1 J2 J1 truepositive falsepositive J2 falsenegative truenegative Misalkan terdapat confusion matrix 2×2 seperti pada tabel di atas, maka rumus yang akan digunakan untuk menghitung akurasi adalah sebagai berikut : 𝑘

𝑎

𝑎

𝑥

𝑎

Rumus di atas dapat juga didefenisikan seperti pada rumus berikut : 𝑘

𝑎

∑ 𝑎𝑎

𝑦𝑎 𝑘𝑎 𝑘𝑎 𝑘𝑎 ∑ 𝑚𝑎 𝑎𝑎

𝑎

𝑝𝑎

𝑥


BAB II LANDASAN TEORI

Recommend Documents