BAB II LANDASAN TEORI
2.1 Decision Tree Definisi Decision tree adalah sebuah diagram alir yang berbentuk seperti struktur pohon yang mana setiap internal node menyatakan pengujian terhadap suatu atribut, setiap cabang menyatakan output dari pegujian tersebut dan leaf node menyatakan kelas–kelas atau distribusi kelas. Node yang paling atas disebut sebagai root node atau node akar. Sebuah root node akan memiliki beberapa edge keluar tetapi tidak memiliki edge masuk, internal node akan memiliki satu edge masuk dan beberapa edge keluar, sedangkan leaf node hanya akan memiliki satu edge masuk tanpa memiliki edge keluar. Decision tree digunakan untuk mengklasifikasikan suatu sampel data yang belum diketahui kelasnya ke dalam kelas–kelas yang sudah ada. Jalur pengujian data adalah pertama melalui root node dan terakhir adalah melalui leaf node yang akan menyimpulkan prediksi kelas bagi data tersebut. Atribut data harus berupa data kategorik, bila kontinu maka atribut harus didiskretisasi terlebih dahulu. Pemilihan Atribut dan Pembentukan tree Pemilihan atribut untuk menjadi rootnode atau internal node sebagai atribut test berdasarkan atas ukuran impurity dari masing–masing atribut. Ukuran–ukuran impurity yang umumnya digunakan adalah information gain, gain ratio dan gini index. Atribut yang memiliki nilai impurity tertinggi akan dipilih sebagai atribut test.
Information Gain atribut A (Gain(A)) Information Gain merupakan suatu ukuran korelasi pada model parametrik yang menggambarkan ketergantungan antara dua peubah acak X dan Y. Information Gain memiliki rumus :
4
5
.......................................(Rumus 2.1.1) adalah informasi harapan (split info) yang memiliki rumus :
........................................(Rumus 2.1.2) Dengan m
: Banyaknya nilai yang berbeda atribut label kelas yang akan mendefinisikan kelas yang berbeda, Ci (i = 1,2,...,m)
si
: Jumlah sampel dalam himpunan sampel S (berisi s sampel) yang masuk kelas Ci
pi
: Peluang bahwa suatu sampel akan masuk ke kelas Ci dan diestimasi dengan
𝑠 𝑠𝑖
E(A) : Entropy A Secara statistik, entropy menyatakan ukuran ketidakpastian secara probabilistik. Entropy A memiliki rumusan :
..........(Rumus 2.1.3)
v
: Banyaknya nilai/kategori yang berbeda yang dimiliki atribut A
sij
: Banyaknya sampel pada atribut A yang masuk kategori ke j dan kelas Ci
menyatakan proporsi jumlah sampel atribut A kategori j terhadap jumlah sampel total
Gain Ratio Gain Ratio merupakan modifikasi dari information gain untuk mengurangi bias atribut yang memiliki banyak cabang. Gain ratio memiliki sifat :
6
• Bernilai besar bila data menyebar rata • Bernilai kecil bila semua data masuk dalam satu cabang Gain ratio memiliki rumus :
.................................................(Rumus 2.1.4)
Dimana rumus split info seperti pada (Rumus 2.1.2) dengan m menyatakan banyaknya split. Jenis split yang dipilih adalah split yang memiliki nilai Gain Ratio yang terbesar.
Gini index Gini index merupakan suatu ukuran ketidaksamaan pada distribusi pendapatan dan memiliki nilai antara 0 sampai 1. Semakin rendah nilai Gini index maka semakin besar pula ukuran kesamaannya. Gini index atribut t untuk data dengan m kelas didefinisikan sebagai berikut :
.........................................................(Rumus 2.1.5) Bila data dipecah terhadap A menjadi 2 subset D1 dan D2, maka Gini index didefinisikan sebagai berikut :
..................(Rumus 2.1.6) Jenis split terbaik yang dipilih adalah split yang memiliki Gini index terkecil.
Ukuran–ukuran tersebut biasanya hanya digunakan pada algoritma tertentu, jadi penentuan ukuran untuk digunakan dalam memilih atribut test sangat dipengaruhi algoritma yang dipilih. Berdasarkan banyaknya edge keluar dari suatu atribut, maka terdapat dua jenis pemisahan yaitu binary split yang menghasilkan dua buah edge keluar dan multyway split yang menghasilkan lebih dari dua edge keluar.
7
Algoritma - algoritma dalam Decision Tree Ada banyak algoritma pada klasifikasi decision tree ini. Suatu algoritma biasanya dikembangkan untuk meningkatkan kinerja algoritma yang sudah ada. Penentuan algoritma yang terbaik dalam decision tree tentunya tidak bisa ditentukan secara mutlak tetapi sangat tergantung dengan karakteristik training set-nya. Beberapa algoritma decision tree yang cukup populer antara lain : ID3, C4.5, dan CART.
Algoritma C4.5 Algoritma ini dikembangkan untuk memperbaiki algoritma
ID3.
Algoritma ini berbasiskan keputusan biner seperti yang terlihat dalam CLS. Jadi selain memiliki karakteristik seperti ID3, C4.5 juga memiliki beberapa karakteristik yang berbeda yang merupakan perbaikan dari karakteristik ID3. Berikut ini beberapa karakteristik C4.5 yang juga merupakan perbaikan terhadap ID3 : • Dapat menangani atribut numerik • Dapat menangani missing value • Melakukan pruning untuk memperoleh model yang paling efisien • Menggunakan kriteria gain ratio untuk menentukan jenis split yang terbaik.
Karakteristik Decision Tree Berikut ini adalah beberapa karakteristik decision tree secara umum : • Decision tree merupakan suatu pendekatan nonparametrik untuk membangun model klasifikasi • Teknik yang dikembangkan dalam membangun decision tree memungkinkan untuk membangun model secara cepat dari training set yang berukuran besar. •
Decision tree dengan ukuran tree yang kecil relatif mudah untuk
menginterpretasinya.
8
• Decision tree memberikan gambaran yang ekpresif dalam pembelajaran fungsi nilai diskret. • Algoritma decision tree cukup robbust terhadap munculnya noise terutama untuk metode yang dapat menangani masalah overfitting. • Adanya atribut yang berlebihan tidak terlalu mengurangi akurasi decision tree . • Karena sebagian algoritma decision tree menggunakan pendekatan topdown, yaitu partisi dilakukan secara rekursif maka jumlah record menjadi lebih kecil. Pada leaf node, jumlah record mungkin akan terlalu kecil untuk dapat membuat keputusan secara statistik tentang representasi kelas dari suatu node. • Sebuah subtree dapat direplikasi beberapa kali dalam decision tree tetapi ini akan menyebabkan decision tree menjadi lebih kompleks dan lebih sulit untuk diinterpretasi. (Sibaroni, 2008:8).
2.2 Basis Data Basis data adalah kumpulan data, yang dapat digambarkan sebagai aktifitas dari satu atau lebih organisasi yang berelasi (Kristanto, 2008:79). Database adalah kumpulan file-file yang saling berelasi, relasi tersebut biasa ditunjukan dengan kunci dari tiap file yang ada (Kristanto, 2004:1). Menurut Kusuma (2006:7), database adalah sebuah lokasi di mana pada tempat tersebut berkumpul tabel-tabel. Database adalah kumpulan dari datadata yang membentuk suatu berkas (file) yang saling berhubungan (relation) dengan tatacara yang tertentu untuk membentuk data baru atau informasi (Supriyanto, 2007:190) (dalam Kurniawan, 2013:38). Menurut Jogiyanto (1997:265) Basis data (database) merupakan kumpulan dari data yang saling berhubungan satu dengan yang lainnya, tersimpan di perangkat
keras
komputer
dan
digunakan
perangkat
lunak
untuk
memanipulasinya. Database merupakan salah satu komponen yang penting dalam sistem informasi, karena merupakan batas dalam menyediakan informasi disebut dengan database system (dalam Puspitasari, 2013:2).
9
2.3 Sistem Peminatan Siswa SMAK Harapan Secara Manual Berikut ini adalah tahapan yang dilakukan oleh pihak sekolah (SMAK Harapan) dalam melakukan peminatan siswa :
Pendaftaran siswa baru
Psikotes / Tes IQ
Tes Numerik
Pengambilan Keputusan Peminatan Tahap pendaftaran, pada tahap ini yang dilakukan meliputi pencatatan
biodata siswa, nilai mata pelajaran Matematika, IPA dan IPS semester terakhir, bidang minat siswa, serta nilai NUN (Nilai Ujian Nasional). Kemudian dilakukan perangkingan berdasarkan nilai NUN. Tahap Psikotes / Tes IQ, pada tahap ini yang dilakukan meliputi pencatatan nilai dari tes IQ yang telah dilaksanakan. Tahap Tes Numerik, pada tahap ini yang dilakukan meliputi pencatatan nilai tes numerik yang telah dilaksanakan. Kemudian dilakukan perangkingan terhadap nilai tes tersebut. Tahap Pengambilan keputusan, pada tahap ini yang dilakukan meliputi pembandingan dari semua nilai yang sudah didapatkan. Pertama, nilai tes numerik dijadikan acuan untuk menentukan bidang minat, berdasarkan nilai ini akan didapatkan bidang minat sementara. Selanjutnya, bidang minat sementara dibandingkan dengan nilai Matematika, IPA, IPS, nilai ujian nasional, minat, dan IQ, apakah nilai - nilai tersebut menunjukkan kesesuaian antara bidang minat sementara dengan nilai - nilai dimaksud. Apabila bidang minat sementara sesuai dengan nilai - nilai tersebut di atas, maka akan diperoleh peminatan siswa. Tetapi, jika bidang minat sementara tidak sesuai dengan nilai - nilai tersebut, dipertimbangkan peminatan siswa dengan menggunakan nilai - nilai tersebut. Artinya, peminatan siswa dalam hal ini tidak berdasarkan nilai tes numerik melainkan berdasarkan kecenderungan dominan dari nilai - nilai (Matematika, IPA, IPS, nilai ujian nasional, minat dan IQ). Pelaksanaan tahap ini melibatkan beberapa tenaga operator atau guru, sehingga keputusan yang diperoleh cenderung tidak konsisten.
10
2.4 Teknik Pengujian Sistem Pengujian sistem dilakukan pada saat sistem telah selesai dibuat, tujuan pengujian ini adalah untuk mengetes kualitas dari sistem yang telah dibuat. Terdapat 4 jenis pengujian (Everett, 2007) (dalam Saputra, 2014:8), yaitu Pengujian Statis, Pengujian Blackbox, Pengujian Whitebox dan Pengujian performa. Dalam Penelitian ini digunakan Blackbox Testing dan Pengujian Performa :
Pengujian Blackbox (Blackbox Testing) Blackbox Testing adalah test yang dilakukan
saat tester tidak
memiliki source code, hanya code yang bisa dijalankan. Testing blackbox dilakukan dengan menjalankan aplikasi dan melakukan apa yang bisa dikerjakan oleh aplikasi, apa yang dilakukan dan bagaimana hasil yang diberikan aplikasi adalah hal yang diteliti. Hal penting yang harus dilakukan pada testing ini adalah, apakah tester mengetahui hasil (benar) apa yang diharapkan dan apakah tester melakukan test dengan benar. Dari kedua hal tersebut maka bisa dilihat apabila terjadi kesalahan, apakah kesalah tersebut dikarenakan kesalahan aplikasi atau kesalahan implementasi.
Pengujian Performa (Performance Testing) Testing performa merupakan testing yang dilakukan apabila perangkat lunak telah berjalan dengan benar. Pengetesan ini dilakukan bukan untuk mengetes kebenaran dari sistem namun hasil dan waktu respon dari perangkat lunak. Pengetesan performa dilakukan dengan menyiapkan peralatan test. Pengetestsan menguji aplikasi mulai dari saat ia tidak bekerja (idle) hingga kesaat sedang puncak sibuk bekerja. Pengujian performa ini berbeda dengan whitebox ataupun blackbox testing, apabila kecacatan ditemukan oleh testing whitebox atau blackbox maka akan dilakukan koreksi program, namun Pengujian performa akan lebih memeriksa aplikasi untuk kemampuannya terhadap hardware, dimana kecacacatan dalam test performa akan membuat developer menyarankan pembelian hardware yang lebih memadai untuk aplikasinya.
11
2.5 Evaluasi Hasil Dalam proses evaluasi hasil penelitian akan digunakan confusion matrix. Confusion matrix adalah merupakan sebuah metode untuk evaluasi yang menggunakan tabel matrix seperti berikut :
Gambar 1 Confusion Matrix
Evaluasi dengan menggunakan confusion matrix menghasilkan nilai accuracy, precision, dan recall. Dalam Andriani, 2013:4, nilai accuracy merupakan presentase jumlah record data yang diklasifikasikan secara benar oleh sebuah algoritma. Nilai precision atau dikenal juga dengan nama confidence merupakan proporsisi jumlah kasus yang diprediksi positif yang juga positif benar pada data yang sebenarnya. Sedangkan nilai dari recall atau sensitivity merupakan proporsi jumlah kasus positif yang sebenarnya diprediksi positif secara benar. Pada tabel confusion matrix diatas, True Positive adalah jumlah record positif yang diklasifikasikan sebagai positif, false positive adalah jumlah record negative yang diklasifikasikan sebagai positif, false negative adalah jumlah record positif yang diklasifikasikan sebagai negative, true negative adalah jumlah record negative yang diklasifikasikan sebagai negatif, kemudian masukkan data uji. Setelah data uji dimasukkan ke dalam confusion matrix, hitung nilai-nilai yang telah dimasukkan tersebut untuk dihitung jumlah sensitivity (recall), Specifity, precision, danaccuracy. Sensitivity digunakan untuk membandingkan jumlah t_pos terhadap jumlah record yang positif sedangkan Specifity, precision adalah perbandingan jumlah t_neg terhadap jumlah record yang negatif. Untuk menghitung digunakan persamaan dibawah ini (Han dan Kamber). ..............................................................(Rumus 2.5.1)
12
...............................................................(Rumus 2.5.2)
...............................................(Rumus 2.5.3)
..(Rumus 2.5.4)
Keterangan : t_pos
: jumlah true positif
t_neg : jumlah true negatif pos
: jumlah record positif
neg
: jumlah tupel negatif
f_pos : jumlah false positif
