BAB II
TINJAUAN PUSTAKA
2.1 Landasan Teori
2.1.1 Indeks Prestasi Kumulatif dan Lama Studi Mahasiswa yang telah menyelesaikan keseluruhan beban program studi yang telah ditetapkan dapat dipertimbangkan dalam penetapan kelulusan dan predikat studi akhir program. Untuk menentukan kelulusan dan predikat, fakultas menggunakan dokumen/format resmi hasil penilaian studi mahasiswa yang sudah dicek dan disahkan kebenaran isinya oleh ketua jurusan setelah diperiksa oleh tim verifikasi pada masing-masing jurusan. Kelulusan dan predikat
ditetapkan
berdasarkan Indeks Prestasi Kumulatif (IPK) hasil ujian semua matakuliah yang diwajibkan untuk menyelesaikan kebulatan program yang diikuti sesuai dengan ketentuan struktur program dan sebaran Sistem Kredit Semester (SKS) nya, termasuk hasil Ujian Skripsi/Tugas Akhir. Predikat program sarjana dan diploma tercantum dalam tabel dibawah ini. Tabel 2.1 Predikat Program Sarjana dan Diploma Predikat Terpuji Sangat memuaskan Memuaskan
IPK 3,51 – 4,00 2,76 – 3,50 2,00 – 2,75
Sumber : Pedoman Akademik Fakultas Teknik, tahun 2011
Setiap mahasiswa yang akan mengakhiri studinya harus menyelesaikan beban studi yang telah ditetapkan. Beban studi mahasiswa dalam satu semester
4
ditentukan atas dasar kemampuan akademik dan paket waktu yang tersedia bagi masing-masing mahasiswa. Beban studi program sarjana 140 SKS dan maksimal 154 SKS yang dijadwalkan 8 (delapan) semester dan dapat ditempuhkan dalam waktu kurang dari 8 (delapan) semester dan maksimal 14 semester. Beban studi program diploma III (tiga) minimal 110 SKS dan maksimal 120 SKS yang dijadwalkan 6 Semester dan dapat ditempuh minimal 6 semester dan maksimal 10 semester (Pedoman akademik Fakultas Teknik, 2011).
2.1.2 Definisi Data Mining Data mining adalah suatu istilah yang digunakan untuk menguraikan penemuan pengetahuan di dalam database. Data mining adalah proses yang menggunakan teknik statistik, matematika, kecerdasan buatan, dan machine learning untuk mengekstraksi dan mengidentifikasi informasi yang bermanfaat dan pengetahuan yang terkait dari berbagai database besar (Turban E, 2005). Data mining merupakan bidang dari beberapa bidang keilmuan yang menyatukan teknik dari pembelajaran mesin, pengenalan pola, statistik, database, dan visualisasi untuk penanganan permasalahan pengambilan informasi dari database yang besar (Larose, 2005). Tan (2006) mendefinisikan data mining sebagai proses untuk medapatkan informasi yang berguna dari gudang basis data yang besar. Data mining juga dapat diartikan sebagai pengekstrakan informasi baru yang diambil dari bongkahan data besar yang membantu dalam pengambilan keputusan. Istilah data mining kadang disebut juga knowledge discovery.
5
Pencarian Ekstraksi Data (bahasa alami, web, penstrukturan)
Statistik
Informasi Pembelajaran Neural Network, pohon keputusan, fuzzy
Kecerdasan
Data Mining Buatan
Dasar (Seleksi, presentas hasil)
Data yang besar (normalisasi data,transformasi,OLAP)
Database
Gambar 2.1 Bidang ilmu data mining (Kusrini dkk , 2006)
Gambar 2.1 menunjukkan bahwa data mining memiliki akar panjang dari bidang ilmu seperti kecerdasan buatan (Artificial Intelligent), machine learning, statistik, database, dan juga informasi retrieval (Pramurdiono, 2003). Istilah data mining dan knowledge discovery in databases (KDD) sering kali digunakan secara bergantian untuk menjelaskan proses penggalia informasi tersembunyi dalam suatu basis data yang besar. sebenarnya kedua istilah tersebut memiliki konsep yang berbeda, tetapi berkaitan satu sama lain. Salah satu tahapan dalam keseluruhan proses KDD adalah data mining. a. Knowledge Discovery in Database (KDD) Knowledge Discovery in Database (KDD) adalah proses menentukan informasi yang berguna serta pola-pola yang ada dalam data. Informasi ini terkandung dalam basis data yang berukuran besar yang sebelumnya tidak
6
diketahui dan potensial bermanfaat (Han dan Kamber, 2006). Data Mining merupakan salah satu langkah dari serangkaian proses iterative KDD. Tahapan proses KDD dapat dilihat pada gambar 2.2
Gambar 2.2 Tahapan dalam KDD (Han dan Kamber, 2006) Tahapan proses KDD terdiri dari : 1. Data Selection Pada proses ini dilakukan pemilihah himpunan data, menciptakan himpunan data target, atau memfokuskan pada subset variabel (sampel data) dimana penemuan (discovery) akan dilakukan. Hasil seleksi disimpan dalam suatu berkas yang terpisah dari basis data operasional. 2. Pre-Processing dan Cleaning Data Pre-Processing dan Cleaning Data dilakukan membuang data yang tidak konsisten dan noise, duplikasi data, memperbaiki kesalahan data, dan bisa diperkaya dengan data eksternal yang relevan.
7
3. Transformation Proses ini mentransformasikan atau menggabungkan data ke dalam yang lebih tepat untuk melakukan proses mining dengan cara melakukan peringkasan (agregasi). 4. Data Mining Proses data mining yaitu proses mencari pola atau informasi menarik dalam data terpilih dengan menggunakan teknik, metode atau algoritma tertentu sesuai dengan tujuan dari proses KDD secara keseluruhan. 5. Interpretation / Evaluasi Proses untuk menerjamahkan pola-pola yang dihasilkan dari data mining. Mengevaluasi (menguji) apakah pola atau informasi yang ditemukan bersesuaian atau bertentangan dengan fakta atau hipotesa sebelumnya. Pengetahuan yang diperoleh dari pola-pola yang terbentuk dipresentasikan dalam bentuk visualisasi.
b. Teknik Data Mining Ada beberapa teknik yang dimiliki data mining berdasarkan tugas yang bisa dilakukan (Kusrini dkk, 2006), yaitu : 1. Deskripsi Para
peneliti/analis
biasanya
mencoba
menemukan
cara
untuk
mendeskripsikan pola dan trend yang tersembunyi dalam data. Deskripsi dari pola dan kecenderungan sering memberikan kemungkinan penjelasan untuk suatu pola atau kecenderungan.
8
2. Estimasi Estimasi mirip dengan klasifikasi, kecuali variabel tujuan yang lebih ke arah numerik daripada kategori. Misalnya, akan dilakukan estimasi tekanan systolic dari pasien rumah sakit berdasarkan umur pasien, jenis kelamin, indeks berat badan, dan level sodium darah. 3. Prediksi Prediksi memiliki kemiripan dengan estimasi dan klasifikasi. Hanya saja, prediksi hasilnya menunjukkan sesuatu yang belum terjadi (mungkin terjadi dimasa depan). Misalnya, ingin diketahui prediksi harga beras tiga bulan yang akan datang. 4. Klasifikasi Dalam klasifikasi variable, tujuan bersifat kategorik. Misalnya, kita akan mengklasifikasikan pendapatan dalam tiga kelas, yaitu pendapatan tinggi, pendapatan sedang, dan pendapatan rendah. 5. Clustering Custering lebih kearah pengelompokan record, pengamatan, atau kasus dalam kelas yang memiliki kemiripan. Sebuah cluster adalah kumpulan record yang memiliki kemiripan satu dengan yang lain dan memiliki ketidak miripan dengan record-record dalam cluster yang lain.misalnya untuk tujuan audit akuntasi akan dilakukan segmentasi perilaku financial dalam kategori dan mencurigakan.
9
6. Asosiasi Mengidentifikasi hubungan antara berbagai peristiwa yang terjadi pada satu waktu. Pendekatan asosiasi tersebut menekankan sebuah kelas masalah yang dicirikan dengan analisis keranjang pasar. 2.1.3 Klasifikasi 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 (Han dan Kember, 2006). Klasifikasi memprediksi data dalam bentuk kategori, sedangkan prediksi memodelkan fungsifungsi 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 digunakan untuk memprediksi nilai-nilai diskrit atau nominal, sedangkan regresi digunakan untuk memprediksi nilainilai yang kontinyu. Pendekatan umum yang digunakan dalam masalah klasifikasi adalah training set yang berisi record yang mempunyai label kelas yang diketahui haruslah tersedia. Training set digunakan untuk membangun model klasifikasi, yang
10
kemudian diaplikasikan ke test set, yang berisi record-record dengan label kelas yang tidak diketahui
2.1.4 Decision Tree Decision tree merupakan salah satu teknik yang dapat digunakan untuk melakukan klasifikasi terhadap sekumpulan objek atau record. Teknik ini terdiri dari kumpulan decision node, dihubungkan oleh cabang, bergerak ke bawah dari root node sampai berakhir di leaf node. Pengembangan decision tree dimulai dari root node, berdasarkan konvensi ditempatkan di bagian atas diagram decision tree, semua atribut dievaluasi pada decision node, dengan tiap outcome yang mungkin menghasilkan cabang. Tiap cabang dapat masuk baik ke decision node yang lain ataupun ke leaf node (Han dan Kember, 2006). Persyaratan yang harus dipenuhi dalam penerapan algoritma decision tree: 1. Algoritma decision tree merepresentasikan supervised learning, dan oleh karena itu membutuhkan variabel target preclassified. Training data set harus menyediakan nilai-nilai variabel target. 2. Training data set harus kaya dan bervariasi, menyediakan algoritma dengan cross section yang sehat dari tipe record dimana klasifikasinya yang mungkin dibutuhkan dimasa datang. Decision tree belajar melalui contoh, dan jika contoh yang tersedia secara sistematis kurang memiliki subset record yang definable, klasifikasi dan prediksi untuk subset tersebut akan sulit atau tidak mungkin.
11
3. Kelas atribut target harus diskrit. Variabel target harus mempunyai nilai yang jelas batasnya apakah termasuk ke dalam kelas tertentu atau bukan.
2.1.5 Algoritma C5.0 Algoritma C5.0 adalah salah satu algoritma yang terdapat dalam klasifikasi data mining disamping algoritma CART, yang khususnya diterapkan pada teknik decision tree. C5.0 merupakan penyempurnaan algoritma terdahulu yang dibentuk oleh Ross Quinlan pada tahun 1987, yaitu ID3 dan C4.5. Ernawati (2008) menjelaskan bahwa dalam algoritma C5.0, pemilihan atribut yang akan diproses menggunakan information gain. Secara heuristik akan dipilih atribut yang menghasilkan simpul yang paling bersih (purest). Jika dalam cabang suatu decision tree anggotanya berasal dari satu kelas maka cabang ini disebut pure. Kriteria yang digunakan adalah information gain. Jadi dalam memilih atribut untuk memecah obyek dalam beberapa kelas harus kita pilih atribut yang menghasilkan information gain paling besar. Ukuran information gain digunakan untuk memilih atribut uji pada setiap node di dalam tree. Ukuran ini digunakan untuk memilih atribut atau node pada pohon. Atribut dengan nilai information gain tertinggi akan terpilih sebagai parent bagi node selanjutnya. Formula untuk information gain adalah (Kantardzic M, 2003): s ,s ,, , , , s
,
=−
p log (p )
(2.1)
12
S adalah sebuah himpunan yang terdiri dari s data sampel. Diketahui atribut class adalah m dimana mendefinisikan kelas-kelas di dalamnya, Ci (for i= 1, …, m), si adalah jumlah sampel pada S dalam class Ci. untuk mengklasifikasikan sampel yang digunakan maka diperlukan informasi dengan menggunakan aturan seperti di atas (2.1). Dimana pi adalah proporsi kelas dalam output seperti pada kelas Ci dan diestimasikan dengan si /s. Atribut A memiliki nilai tertentu {a1, a2,…, av}. Atribut A dapat digunakan pada partisi S ke dalam v subset, {S1, S2, …, Sv}, dimana Sj berisi sample pada S yang bernilai aj pada A. Jika A dipilih sebagai atribut tes (sebagai contoh atribut terbaik untuk split), maka subset ini akan berhubungan pada cabang dari node himpunan S. Sij adalah jumlah sample pada class Ci dalam sebuah subset Sj. Untuk mendapatkan informasi nilai subset dari atribut A tersebut maka digunakan formula (Ernawati,2006) ( )∑ ⋯
⋯
(
,…,
)
(2.2)
adalah jumlah subset j yang dibagi dengan jumlah sampel pada S,
maka untuk mendapatkan nilai gain, selanjutnya digunakan formula (Ernawati,2006) Gain (A) = I (S1, S2, … Sm) = E (A)
(2.3)
2.1.6 Cross Validation Cross Validation adalah metode umum digunakan untuk mengevaluasi kinerja classifier. Dalam pendekatan cross validation, setiap record digunakan beberapa kali dalam jumlah yang sama untuk training dan tepat sekali untuk testing. Metode ini mempartisi data ke dalam dua sub set data yang berukuran 13
sama. Pilih salah satu sebagai data training dan satu lagi untuk testing, kemudian dilakukan pertukaran fungsi dari subset sedemikian sehingga subset yang sebelumnya sebagai training set menjadi test set demikian sebelumnya. Pendekatan ini dinamakan two-fold- cross-validation. Total error diperoleh dengan menjumlahkan error-error untuk kedua proses tersebut. Metode k-fold cross-validation menggeneralisasi pendekatan ini dengan mensegmentasi data ke dalam k partisi berukuran sama. Selama proses, salah satu dari partisi dipilih untuk training, sedangkan sisanya untuk testing. Prosedur ini diulangi k kali sedemikian sehingga setiap partisi digunakan untuk testing tepat satu kali. Total error ditentukan dengan menjumlahkan error untuk semua k proses tersebut (Tan, et al. 2005).
2.1.7 Pengukuran Kinerja Klasifikasi Evaluasi model klasifikasi didasarkan pada pengujian untuk memprediksi obyek yang benar dan salah, urutan pengujian ditabulasikan dalam Confusion Matrix, dimana kelas yang diprediksi ditampilkan di bagian atas matriks dan kelas yang diamati disisi kiri matriks. Setiap sel berisi angka yang menunjukkan berapa banyak kasus yang sebenarnya dari kelas yang diamati untuk diprediksi (Han dan Kamber, 2006). Tabel 2.2 Confusion Matrix untuk 2 Kelas Classification Class = Yes Class = No
Predicted Class Class = Yes Class = No A b TP (True Positive) FN (False Negative) C d FP (False Positive) TN (True Negative) 14
TP adalah jumlah record positif yang diklasifikasikan sebagai positif, FP adalah jumlah record negative yang diklasifikasikan sebagai positif, FN adalah jumlah record positif yang diklasifikasikan sebagai negative, TN adalah jumlah record negative yang diklasifikasikan sebagai negative. Evaluasi dengan confusion matrix menghasilkan akurasi dan laju error. Akurasi adalah persentase dari total d ata yang diprediksi secara benar. Laju error adalah persentase dari total data yang diprediksi secara salah. =
=
=
=
100%
(2.4)
100% (2.5)
Semua algoritma klasifikasi berusaha membentuk model yang memiliki akurasi tinggi (laju error yang rendah), tetapi umumnya model yang dibangun dapat memprediksi dengan benar pada semua data latih, ketika model berhadapan dengan data uji, barulah kinerja model dari sebuah algoritma klasifikasi ditentukan.
2.2 Penelitian Terkait Beberapa penelitian yang menjadi penelitian terkait antara lain adalah penelitian Hadjaratie (2012) yang membandingkan beberapa algoritma klasifikasi (decision tree, neural network, dan k-neirest neighbor) dalam memprediksi kategori IPK dan lama studi. Hasil penelitiannya menyatakan bahwa metode decision tree dengan agoritma CART memiliki akurasi yang lebih tinggi (rata-rata 15
akurasi 78%) dibandingkan dengan metode klasifikasi lainnya. Dalam penelitian Galathiya,
dkk
(2012)
dijelaskan
bahwa
algoritma
C4.5
merupakan
pengembangan dari algoritma ID3 dan algoritma C5.0 merupakan pengembangan dari algoritma C4.5, sementara hasil penelitian Patil, Lathi, dan Chitre (2012) yang membandingkan algoritma C5.0 dengan algoritma CART
dalam
memprediksi konsumen dalam merekomendasikan kartu keanggotaan dan menyatakan bahwa algoritma C5.0 memiliki kinerja yang lebih baik dari algoritma CART, hingga mencapai 99,6%. Hal ini menjadi dasar penulis untuk menggunakan algoritma C5.0 dalam memprediksi kategori IPK dan lama studi mahasiswa Fakultas Teknik dan Fakultas Ilmu Pendidikan UNG.
16
