Makalah_klasifikasi_decision_tree_fix(2).docx

MAKALAH KLASIFIKASI (DECISION TREE)

Oleh : Fandi Pratama (14.01.53.0116) Alfun Adam (14.01.53.0109) Riva Ayu G (14.01.53.0104)

FAKULTAS TEKNOLOGI INFORMASI UNIVERSITAS STIKUBANK (UNISBANK) SEMARANG 2018

BAB I PENDAHULUAN

1.1 LATAR BELAKANG 1.1.1 Klasifikasi Klasifikasi merupakan proses untuk menemukan sekumpulan model yang menjelaskan dan membedakan kelas-kelas data, sehingga model tersebut dapat digunakan untuk memprediksi nilai suatu kelas yang belum diketahui pada sebuah objek.

Gambar 1. Klasifikasi sebagai suatu tugas memetakan atribut x ke dalam label kelas y Klasifikasi adalah proses untuk menempatkan objek tertentu (konsep) dalam satu set kategori, berdasarkan sifat masing-masing objek (konsep) (Gorunescu, 2011). Klasifikasi tergolong dalam supervised methods. Proses klasifikasi didasarkan pada empat komponen dasar (Gorunescu, 2011) : 1) Kelas (class) atau label kelas yaitu variabel dependen dari model yang merupakan variabel kategori yang menjelaskan sebuah 'label' pada objek setelah proses klasifikasi. Contoh : loyalitas pelanggan (label : loyal / tidak loyal), kelas bintang (galaksi), dll. 2) Prediktor (predictor) atau atribut (attribute) yaitu variabel independen dari model yang diwakili oleh karakteristik (atribut) dari data yang akan diklasifikasikan dan berdasarkan klasifikasi yang dibuat. Contoh prediktor tersebut adalah: merokok, konsumsi alkohol, tekanan darah, frekuensi pembelian, status perkawinan, dan kecepatan angin, musim, dll. 3) Training set atau dataset latihan (training dataset) yaitu merupakan kumpulan data yang berisi nilai-nilai atau record untuk dua

komponen sebelumnya (kelas dan prediktor / atribut) dapat berupa variabel kontinyu maupun kategoris, dan digunakan untuk 'pelatihan' atau pembangunan model untuk menyesuaikan dengan kelasnya berdasarkan prediktor yang tersedia. Contoh set tersebut adalah: kelompok pasien diidentifikasi pada kasus serangan jantung berdasarkan faktor-faktor yang mempengaruhinya, kelompok pelanggan dari supermarket, dll. 4) Dataset pengujian (testinging dataset) yaitu berisi data baru yang akan diklasifikasikan oleh model klasifikasi (classifier) dan untuk mengukur tingkat akurasi klasifikasi (kinerja model) sehingga performansi model klasifikasi dapat dievaluasi. Model dalam klasifikasi antara lain yaitu (Bertalya, 2009) : 1)

Pemodelan Deskriptif Sebagai alat penggambaran yang bersifat menjelaskan untuk membedakan objek-objek dari kelas yang berbeda.

2)

Pemodelan Prediktif Pemodelan prediktif digunakan untuk memprediksi label kelas untuk record yang belum diketahui.

1.1.2 Algoritma Klasifikasi Pada teknik klasifikasi terdapat beberapa algoritma klasifikasi yang dapat digunakan, antara lain: pohon keputusan (decision tree), rule based, neural network, support vector machine, naive bayes, rough set, dan nearest neighbour. 1.1.3 Decision Tree Salah satu metode teknik klasifikasi data mining yang umum digunakan adalah decision tree. Decision tree adalah struktur flowchart yang menyerupai tree (pohon), dimana setiap simpul internal menandakan suatu tes pada atribut, setiap cabang merepresentasikan hasil tes, dan simpul daun merepresentasikan kelas atau distribusi kelas. Alur pada decision tree di telusuri dari simpul akar ke simpul daun yang memegang prediksi kelas untuk contoh tersebut. Decision tree mudah untuk dikonversi ke aturan klasifikasi. Teknik pohon keputusan lebih mudah digunakan, karena beberapa alasan:

a) Dibandingkan dengan classifier JST atau bayesian, sebuah pohon keputusan mudah diinterpretasi/ ditangani oleh manusia. b) Sementara training JST dapat menghabiskan banyak waktu dan ribuan iterasi, pohon keputusan efisien dan sesuai untuk himpunan data besar. c) Algoritma dengan pohon keputusan tidak memerlukan informasi tambahan selain yang terkandung dalam training data (yaitu, pengetahuan domain dari distribusi-distribusi pada data atau kelas-kelas). d) Pohon

keputusan

menunjukkan

akurasi

klasifikasi

yang

baik

dibandingkan dengan teknik- teknik yang lainnya.

1.2 RUMUSAN MASALAH Berdasarkan uraian pada latar belakang dapat dirumuskan permasalahannya yaitu bagaimana memahami konsep dan menerapkan salah satu algoritma klasifikasi yaitu decision tree.

BAB II TINJAUAN PUSTAKA

2.1 KAJIAN DEDUKTIF 2.1.1

Asumsi Dalam Klasifikasi Pembuatan model menguraikan sebuah set dari penentuan kelas-kelas sebagai: 1. Setiap record diasumsikan sudah mempunyai kelas yang dikenal seperti ditentukan oleh label kelas atribut, 2. Kumpulan record yang digunakan untuk membuat model disebut kumpulan pelatihan (training set), 3. Model direpresentasikan sebagai classification rules, decision tree atau formula matematis. Penggunaan model menguraikan pengklasifikasian masa yang akan datang atau obyek yang belum diketahui, yaitu taksiran keakuratan dari model yang terdiri dari: 1. Label yang telah diketahui dari contoh tes dibandingkan dengan hasil klasifikasi dari model, 2. Nilai keakuratan adalah prosentase dari kumpulan contoh tes yang diklasifikasikan secara tepat oleh model, 3. Kumpulan tes tidak terikat pada kumpulan pelatihan, 4. Jika akurasi diterima, model dapat digunakan untuk mengklasifikasikan data record yang label kelasnya belum diketahui. Untuk mengevaluasi performansi sebuah model yang dibangun oleh algoritma klasifikasi, dapat dilakukan dengan menghitung jumlah dari testing record yang diprediksi secara benar (akurasi) dan salah (error rate) oleh model tersebut. Akurasi dan error rate didefinisikan sebagai berikut :

Model di klasifikasi dapat dikatakan baik untuk digunakan apabila mempunyai akurasi yang tinggi atau error rate yang rendah ketika model diterapkan pada testing set.

2.1.2

Klasifikasi Decision Tree 1. Konsep Decision Tree Mengubah data menjadi pohon keputusan (decision tree) dan aturanaturan keputusan (rule).

Gambar 4. Konsep Decision Tree 2) Tipe Simpul Pada Tree Tree mempunyai 3 tipe simpul, yaitu: 1. Simpul akar dimana tidak ada masukan edge dan 0 atau lebih keluaran edge (tepi), 2. Simpul internal, masing-masing 1 masukan edge dan 2 atau lebih edge keluaran, 3. Simpul daun atau simpul akhir, masing-masing 1 masukan edge dan tidak ada edge keluaran. Pada decision tree setiap simpul daun menandai label kelas. Simpul yang bukan simpul akhir terdiri dari akar dan simpul internal yang terdiri dari kondisi tes atribut pada sebagian record yang mempunyai karakteristik yang berbeda. Simpul akar dan simpul internal ditandai dengan bentuk oval dan simpul daun ditandai dengan bentuk segi empat.

Gambar 5. Decision tree untuk masalah klasifikasi 3) Konsep Data Dalam Decision Tree a) Data dinyatakan dalam bentuk tabel dengan atribut dan record. b) Atribut menyatakan suatu parameter yang dibuat sebagai kriteria

dalam pembentukan tree. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin dan temperatur. Salah satu atribut merupakan atribut yang menyatakan data solusi per-item data yang disebut dengan target atribut. c) Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan dan hujan.

Customer

Jumlah Beli

Keadaan Barang

Diskon

Cinta

Banyak

Tidak Cacat

Tidak Diskon

Jojo Shinta Lala

Sedikit Sedang Sedikit

Cacat Tidak Cacat Cacat

Diskon Tidak Diskon Diskon

Maya

Banyak

Cacat

Instance

Diskon

Label Kelas

Gambar 6. Contoh data untuk Decision Tree 4) Proses Dalam Decision Tree a ) Proses Mengubah Data Menjadi Tree

Gambar 7. Mengubah Data Menjadi Tree b ) Ukuran untuk Memilih Split Terbaik Dalam membangun sebuah decision tree secara top-down (dari atas ke bawah), tahap awal yang dilakukan adalah mengevaluasi semua atribut yang ada menggunakan suatu ukuran statistik (yang banyak

digunakan adalah information gain) untuk mengukur efektifitas suatu atribut dalam mengklasifikasikan suatu kumpulan sampel data. Atribut yang diletakkan pada root node adalah atribut yang memiliki information gain terbesar. Semua atribut adalah bersifat kategori yang bernilai diskrit. Atribut dengan nilai continuous harus didiskritkan (Zalilia, 2007). Terlebih dahulu kita harus mencari nilai informasi dari data yang merupakan nilai yang diperlukan untuk mengklasifikasikan keputusan akhir. Secara matematis dapat dirumuskan dengan:

c ) Entropy Entropy (S) adalah jumlah bit yang diperkirakan dibutuhkan untuk dapat mengekstrak suatu kelas (+ atau -) dari sejumlah data acak pada ruang sample S. Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas. Semakin kecil nilai Entropy maka semakin baik untuk digunakan dalam mengekstraksi suatu kelas. Entropi adalah suatu parameter untuk mengukur heterogenitas dari suatu data. Panjang kode untuk menyatakan informasi secara optimal adalah p2log− bits untuk messages yang mempunyai probabilitas p. Untuk menghitung information gain, terlebih dahulu kita harus memahami suatu ukuran lain yang disebut Entropy. Entropy biasa digunakan sebagai sautu parameter untuk mengukur heterogenitas (keberagaman) dari suatu kumpulan sampel data. Jika kumpulan sampel data semakin heterogen, maka semakin besar nilai entropy. Secara matematis, nilai entropy masing-masing instance dirumuskan sebagai berikut :

Keterangan : S

= ruang (data) sample yang digunakan untuk training.

P(+) = jumlah yang bersolusi positif (mendukung) pada data sample untuk kriteria tertentu. P(-) = jumlah yang bersolusi negatif (tidak mendukung) pada data sample untuk kriteria tertentu. Sedangkan untuk nilai entropy masing-masing atribut dirumuskan dengan:

d) Information Gain Setelah mendapatkan nilai entropy untuk suatu kumpulan sampel data, maka dapat diukuer efektifitas suatu atribut dalam mengklasifikasikan data. Ukuran efektifitas ini disebut Information Gain. Secara matematis, information gain dari suatu atribut, dituliskan sebagai berikut:

Dengan kata lain, Gain (A) adalah reduksi yang diharapkan dalam entropy yang disebabkan oleh pengetahuan nilai pada atribut A. Algoritma menghitung information gain pada setiap atribut. Atribut dengan nilai gain terbesar dipilih sebagai tes atribut (simpul akar). Simpul A dibuat dan dilabelkan dengan atribut, cabang dibuat untuk setiap nilai atribut. Klasifikasi pada umumnya digunakan untuk kasus-kasus pada kelas-kelas keputusan yang bernilai diskrit dengan keputusan seperti diterima = “ya” atau “tidak”. Namun jika kita menemukan kasus yang mempunyai nilai keputusan kontinyu cara untuk menyelesaikannya adalah dengan mengubah nilai-nilai kontinyu menjadi nilai - nilai diskrit dengan cara mempartisi nilai kontinyu ke dalam interval-interval bernilai diskrit.

Tabel 1. Contoh Data penerimaan karyawan dengan atribut IPK bernilai kontinyu

Untuk menyelesaikannya kita misal atribut IPK kita ubah menjadi 3 nilai diskrit dengan membentuk interval “bagus“=[3,00-4,00], “cukup“=[2,753,00] lalu kembali dengan melanjutkan langkah-langkah selanjutnya. a) Mengubah Tree Menjadi Rules Tahap terakhir dalam algoritma decision tree adalah mengubah tree menjadi rules seperti pada gambar di bawah ini.

Gambar 8. Mengubah Tree Menjadi Rules 2.2 KAJIAN INDUKTIF Supervised methods adalah metode yang berusaha untuk menemukan hubungan antara atribut input (variabel independen) dan atribut target / kelas (variabel dependen). Hubungan yang ditemukan diwakili dalam struktur yang disebut sebagai model. Biasanya model menggambarkan dan menjelaskan fenomena yang tersembunyi dalam dataset dan dapat digunakan untuk memprediksi nilai atribut target mengetahui nilai-nilai atribut masukan (Maimon, 2010). Beberapa penelitian terkait decision tree learning diantaranya; penelitian yang dilakukan oleh Rong Cao dan Lizhen Xu menggunakan Algoritma C4.5 untuk

menganalisa penjualan. Lee (2010) menggunakan algoritma ID3 untuk penentuan penerima beasiswa. Wibowo (2009) menggunakan algoritma ID3 untuk membantu dalam pengambilan keputusan pada penentuan MVP di sebuah pertandingan bola basket. Salah satu jenis dari decision tree learning adalah algoritma ID3. Algoritma ID3 (Iterative Dichotomiser 3) merupakan algoritma decision tree learning (algoritma pembelajaran pohon keputusan) yang menggunakan strategi pencarian hill-climbing, yaitu dimulai dari pohon kosong, kemudian secara progresif

berusaha

menemukan

sebuah

pohon

keputusan

yang

mengklasifikasikan sampel-sampel data secara akurat tanpa kesalahan. Pertumbuhan cabang-cabang pohon keputusan pada algoritma ID3 dilakukan sampai pohon tersebut mampu mengklasisifikasikan sampel data secara akurat dengan tingkat kebenaran 100 % sesuai dengan data latih (Suyanto, 2011). Adapun sample data yang digunakan oleh ID3 memiliki beberapa syarat menurut Setiawan (Setiawan, 2010), yaitu: 1) Deskripsi atribut-nilai. Atribut yang sama harus mendeskripsikan tiap contoh dan memiliki jumlah nilai yang sudah ditentukan. 2) Kelas yang sudah didefinisikan sebelumnya. Suatu atribut contoh harus sudah didefinisikan, karena mereka tidak dipelajari oleh ID3. 3) Kelas-kelas yang diskrit. Kelas harus digambarkan dengan jelas. Kelas yang kontinu dipecah-pecah menjadi kategori-kategori yang relatif, misalnya saja metal dikategorikan menjadi “hard, quite hard, flexible, soft, quite soft”. 4) Jumlah contoh (example) yang cukup. Karena pembangkitan induktif digunakan, maka dibutuhkan test case yang cukup untuk membedakan pola yang valid dari peluang suatu kejadian.

BAB III METODE PENELITIAN

3.1 OBJEK PENELITIAN

3.2 METODE PENGUMPULAN DATA 3.2.1

Preprocessing Data Tahap awal yang dilakukan sebelum proses klasifikasi adalah melakukan

preprocessing

data,

terdapat

beberapa

langkah

preprocessing data, yaitu : a. Data Integrasi Data Integrasi merupakan penggabungan data dari beberapa sumber. Dalam metode klasifikasi data integrase dilakukan dengan mengumpulkan beberapa data yang berasal dari beberapa departemen di sebuah perusahaan untuk mendapatkan satu database yang akan digunakan untuk pengolahan pada metode klasifikasi. b. Data Cleaning Data cleaning merupakan suatu pemrosesan terhadap data untuk menghilangkan noise dan penanganan terhadap missing value pada suatu record. c. Data Diskretisasi Data diskretisasi merupakan proses membuat kelas – kelas data (range) untuk parameter dalam melakukan transformasi untuk tahapan berikutnya. d. Transformasi Data Pada data dapat dilakukan generalisasi menjadi data dengan level yang lebih tinggi. Misalnya dengan melakukan diskretisasi terhadap atribut dengan nilai kontinyu. Pembelajaran terhadap data hasil generalisasi dapat mengurangi kompleksitas pembelajaran yang harus dilakukan karena ukuran data yang harus diproses lebih kecil. e. Data Reduksi

Data reduksi merupakan proses mengurangi data atau variable yang tidak memiliki hubungan atau korelasi dengan tujuan penelitian. Dalam menggunakan metode klasifikasi, data reduksi dilakukan dengan melakukan uji independensi chi square untuk mengetahui ada tidaknya hubungan atribut dengan label kelas. 3.3 JENIS DATA Konsep Data Dalam Decision Tree • Data dinyatakan dalam bentuk tabel dengan atribut dan record. • Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan tree. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin dan temperatur. Salah satu atribut merupakan atribut yang menyatakan data solusi per-item data yang disebut dengan target atribut. • Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan dan hujan.

3.4 ALUR PENELITIAN

BAB IV HASIL DAN PEMBAHASAN

4.1 IMPLEMENTASI Install package – package yang dibutuhkan sesuai yang ada program install.packages("party") Jalankan juga library nya library(party)

Gambar 1 (R Console)

# Print some records from data set readingSkills. print(head(readingSkills))

# Create the input data frame. input.dat <- readingSkills[c(1:105),]

# Give the chart file a name. png(file = "decision_tree.png")

# Create the tree. output.tree <- ctree( nativeSpeaker ~ age + shoeSize + score, data = input.dat)

Gambar 2 (R Console)

Script Program untuk menampilkan Grafik Emotion Categories (Gambar 6) # Plot the tree. plot(output.tree)

# Save the file. dev.off()

Gambar 3 (R Graphics)

BAB V KESIMPULAN DAN REKOMENDASI

5.1 KESIMPULAN 

Penelitian menggunakan metode klasifikasi decision tree ini cukup efektif untuk mengklasifikasi data sesuai kebutuhan.



Dari pohon keputusan yang ditunjukkan di atas dapat kita simpulkan bahwa siapa saja yang nilai readingSkills kurang dari 38,3 dan usia lebih dari 6 bukanlah Pembicara asli / penutur asli ( bahasa itu ).

5.2 REKOMENDASI 

Untuk perusahaan / instansi / komunitas yang ingin atau sedang mengklasifikasi kan data bisa menggunakan metode decision tree ini, karena untuk hasil cukup mudah dalam pengelompokkan data nya.

DAFTAR PUSTAKA

Lee, Michael. (2010). Perancangan Klasifikasi Penerimaan Beasiswa Menggunakan Algoritma ID3 (Iterative Dichtomizer Three). Salatiga: FTI UKSW. Florin Gorunescu. 2011. Data Mining : Concept, Model and Techniques. Berlin : Springer. https://www.researchgate.net/publication/315904431_DECISION_TREE_LEARNIN G_UNTUK_PENENTUAN_JALUR_KELULUSAN_MAHASISWA