Algoritma C4.5

Contoh implementasi Data Mining dengan Algoritma C4.5 menggunakan PHP dan MySQL untuk analisis prediksi masa studi mahasiswa .

Dalam artikel ini akan ditunjukkan penerapan algoritma C4.5 dengan tehnik klasifikasi yang merupakan salah satu tehnik Data Mining untuk menganalisa prediksi masa studi mahasiswa. Akan ditunjukkan juga langkah-langkah pembuatan aplikasinya dengan bahasa pemrograman PHP dan database MySQL.

[ author : cahya dsn, published on : February 9, 2017 updated on : June 8, 2019 ]

minerva minerva donasi donation

Mau lihat artikel lainya? Dapatkan artikel-artikel lain seputar pemrograman website di sini, dan dapatkan ide-ide baru
This document using Dynamic Content Technology for enrichment sample case and reading experience
  • Data yang digunakan BUKAN merupakan data real, tapi data yang digenerate secara otomatis dari sistem
  • Data dan Nilai Perhitungan yang ditampilkan akan SELALU BERBEDA jika halaman di refresh/reload
  • Jumlah Dataset yang diperhitungkan, digenerate secara acak/random antara 100 s.d 400
  • Nilai dari masing-masing dataset ditampilkan secara acak/random

Seiring dengan berkembangnya teknologi penyimpanan data, semakin berkembang pula kemampuan seseorang dalam mengumpulkan dan mengolah data. Data yang terkumpul dan berukuran besar tersebut merupakan aset yang dapat dimanfaatkan untuk dianalisis yang hasilnya berupa pengetahuan atau informasi berharga untuk masa mendatang. Tidak hanya dunia bisnis, namun instansi seperti perguruan tinggi juga mengalami penumpukan data.

Jurusan Teknik Komputer Universitas Antah Berantah adalah program pendidikan tinggi yang memiliki beban studi sekurang-kurangnya 144 SKS (satuan kredit semester) yang dijadwalkan untuk 8 semester dan dapat ditempuh dalam waktu kurang dari 8 semester dan paling lama 14 semester. Dari data kelulusan yang diperoleh dari sekretariat Jurusan Teknik Komputer Program Sarjana (S1) angkatan 2020 hanya 3 orang mahasiswa yang lulus dalam 8 semester. Hal ini menunjukkan bahwa masih banyak mahasiswa Program Sarjana (S1) reguler di Jurusan Teknik Komputer yang menempuh lama studi lebih dari 8 semester.

Melihat kondisi tersebut diperlukan penelitian untuk menggali data yang dimiliki oleh Jurusan Teknik Komputer. Data yang akan dimanfaatkan disini adalah data nilai akademik mahasiswa baik yang sudah lulus (yang akan digunakan sebagai data training dan data testing) maupun yang belum lulus/yang sedang menempuh studi yang akan digunakan untuk memprediksi masa studi masing-masing mahasiswa. Penelitian ini dirasa perlu karena jika masa studi mahasiswa dapat diketahui lebih dini, maka pihak jurusan dapat melakukan tindakan-tindakan yang dirasa perlu supaya mahasiswa dapat lulus tepat waktu sekaligus meningkatkan kualitas jurusan itu sendiri.

Dibutuhkan suatu teknik klasifikasi yang merupakan salah satu teknik dari data mining untuk menganalisis data Jurusan Teknik Komputer tersebut. Dengan menerapkan teknik ini akan dibangun pohon keputusan (decicion tree) untuk melihat kemungkinan mahasiswa yang lulus lebih dari 8 semester. Pohon keputusan tersebut merupakan keluaran dari sebuah aplikasi yang dibangun dengan menerapkan Algoritma C4.5 untuk memprediksi masa studi mahasiswa yang sedang menempuh perkuliahan.

2.1. Learning Dataset

Berikut ini adalah contoh dataset yang digunakan sebagai bahan pembelajaran (dataset di generate secara random sejumlah 394 data sample/training).

TABEL 1 : Learning Dataset*
No.Jenis KelaminUsiaDomisiliIPKBeasiswaWaktu Studi
1 Laki-laki < 22th Luar kota 2.76 s.d. 3.50 Mendapat beasiswa > 8 smtr
2 Perempuan < 22th Luar kota 2.00 s.d. 2.75 Mendapat beasiswa > 8 smtr
3 Perempuan >= 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa > 8 smtr
4 Laki-laki < 22th Dalam kota 2.00 s.d. 2.75 Tidak mendapat beasiswa > 8 smtr
5 Perempuan >= 22th Luar kota 2.00 s.d. 2.75 Mendapat beasiswa > 8 smtr
6 Perempuan < 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa > 8 smtr
7 Perempuan < 22th Luar kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr
8 Perempuan >= 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
9 Perempuan < 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa <= 8 smtr
10 Laki-laki >= 22th Luar kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
11 Perempuan < 22th Dalam kota 2.00 s.d. 2.75 Tidak mendapat beasiswa <= 8 smtr
12 Laki-laki < 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr
13 Laki-laki < 22th Dalam kota 3.51 s.d. 4.00 Mendapat beasiswa > 8 smtr
14 Perempuan < 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
15 Laki-laki < 22th Dalam kota 3.51 s.d. 4.00 Tidak mendapat beasiswa <= 8 smtr
...
392 Laki-laki >= 22th Luar kota 2.00 s.d. 2.75 Mendapat beasiswa > 8 smtr
393 Perempuan >= 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa > 8 smtr
394 Laki-laki < 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr

)* yang ditampilkan hanya beberapa data saja mengingat banyaknya data yang dipakai dan tidak memungkinkan untuk ditampilkan semuanya. Data selengkapnya dapat diunduh di tautan pada bagian akhir artikel ini (-- on progress--)

Dari Learning Dataset tersebut, dapat dibuat summary sebagai berikut:

TABEL 2 : Summary Learning Dataset
NoAtributNilai Atribut Jumlah Kasus
Total<= 8 smtr > 8 smtr
1TotalTotal394127267
2Jenis KelaminLaki-laki22573152
3Jenis KelaminPerempuan16954115
4Usia< 22 th21779138
5Usia>= 22 th17748129
6DomisiliLuar kota18660126
7DomisiliDalam kota20867141
8IPK2.76 s.d. 3.5025288164
9IPK2.00 s.d. 2.75872166
10IPK3.51 s.d. 4.00551837
11BeasiswaMendapat beasiswa22069151
12BeasiswaTidak mendapat beasiswa17458116

Data Summary Learning Dataset pada TABEL 2 tersebut untuk selanjutnya akan diproses untuk mendapatkan suatu pohon keputusan -- decision tree, yang akan diuraikan dibagian berikut ini.

2.2. Perhitungan Manual

Berikut ini adalah uraian langkah-langkah dalam algoritma C4.5 untuk menyelesaikan kasus seorang mahasiswa akan lulus dalam jangka waktu 8 semester atau tidak, berdasarkan jenis kelamin, usia, domisili, IPK, dan beasiswa. Learning Dataset yang telah ada pada TABEL 1, akan digunakan untuk membentuk pohon keputusan.

Pada TABEL 1, atribut-atributnya adalah Jenis kelamin, Usia, Domisili, IPK, dan Beasiswa. Setiap atribut memiliki nilai. Sedangkan kelasnya ada pada kolom Waktu Studi yaitu kelas "<= 8 smtr" dan kelas "> 8 smtr". Kemudian data tersebut dianalisis; dataset tersebut memiliki 394 kasus yang terdiri dari 127 "<= 8 smtr" dan 267 "> 8 smtr" pada kolom Waktu Studi (Lihat TABEL 2 baris pertama).

2.2.1. Perhitungan Total Entropy

Berdasarkan persamaan C45-02 dapat dihitung nilai Entropy untuk keseluruhan data sample/training/learning dataset (S) sebagai berikut:

$\begin{align}Entropy(S)&= (-(\frac{267}{394})\ *\ log_2(\frac{267}{394}))+(-(\frac{127}{394})\ *\ log_2(\frac{127}{394}))\\&=(-(0.67766497461929) * (-0.38910225089768))+(-(0.32233502538071) * (-1.1321638228393))\\&=0.26368096697889+0.36493605457004\\ &=0.62861702154893\end{align}$

Hasil perhitungan Entropy dari Dataset (S) tersebut dapat disajikan dalam tabel sebagai berikut (TABEL 3) :

TABEL 3 : Hasil Perhitungan pada Dataset (S)
Total KasusJumlah '<= 8 Smtr'Jumlah '> 8 Smtr'Total Entropy
3941272670.62861702154893

2.2.2. Perhitungan Entropy dan Gain tiap Atribut

Setelah mendapatkan entropy dari keseluruhan kasus, kemudian dilakukan analisis pada setiap atribut dan nilai-nilainya dan menghitung entropy-nya seperti yang ditampilkan pada TABEL 4

TABEL 4 : Analisis Atribut, Nilai, Banyaknya Kejadian Nilai, Entropy dan Gain
NodeAtributNilaiJumlahEntropyGain
Total<= 8 smtr> 8 smtr
1Jenis KelaminLaki-laki225731520.630174276104571.3565535521343E-5
Jenis KelaminPerempuan169541150.62651212748967
Usia< 22 th217791380.655715837887980.0049231362671425
Usia>= 22 th177481290.58443533321657
DomisiliLuar kota186601260.628799394093781.2348598310563E-7
DomisiliDalam kota208671410.62845370449691
IPK2.76 s.d. 3.50252881640.646953953236620.0045386226898955
IPK2.00 s.d. 2.758721660.5526646224944
IPK3.51 s.d. 4.005518370.63223037777852
BeasiswaMendapat beasiswa220691510.621979345551160.00021874412620748
BeasiswaTidak mendapat beasiswa174581160.63651416829481

Nilai entropy dari masing-masing nilai atribut yang terdapat pada TABEL 4 diperoleh menggunakan persamaan C45-02, sebagai contoh untuk nilai Perempuan dari atribut Jenis Kelamin perhitungan entropy-nya sebagai berikut :

2.2.3. Menentukan Root Node

Karena nilai Gain terbesar adalah Gain(Usia) yaitu sebesar 0.0049231362671425, maka atribut Usia menjadi node akar (root node)

3.1. Persiapan Data

Sebelum melangkah ke pembuatan aplikasinya, dipersiapkan dulu untuk struktur database dan tabel-tabel yang berkaitan dengan aplikasi yang akan dibuat berikut ini

3.1.1 Pembuatan Database

Sebagai bahan pembelajaran aplikasi Data Mining dengan Algoritma C4.5 ini; dibuat database (dalam hal ini menggunakan MySQL/MariaDB Database server) sebagai berikut:

CREATE DATABASE IF NOT EXISTS db_dm;
USE db_dm;

Awalnya membuat dulu database dengan nama db_dm jika belum ada database dengan nama tersebut, kemudian gunakan database tersebut dengan memakai sintak USE db_dm;

3.1.2. Membuat Data Tabel Attributes

DROP TABLE IF EXISTS c45_attributes;
CREATE TABLE IF NOT EXISTS c45_attributes(
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(50),
    target INT DEFAULT '0'
);

3.1.3. Membuat Data Tabel Instances

DROP TABLE IF EXISTS c45_instances;
CREATE TABLE IF NOT EXISTS c45_instances(
    id INT AUTO_INCREMENT PRIMARY KEY,
    id_attribute INT NOT NULL,
    name VARCHAR(50)
);

3.1.4. Membuat Data Tabel Samples

DROP TABLE IF EXISTS c45_samples;
CREATE TABLE IF NOT EXISTS c45_samples(
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(50)
);

3.1.5. Membuat Data Tabel Sample_details

DROP TABLE IF EXISTS c45_sample_details;
CREATE TABLE IF NOT EXISTS c45_sample_details(
    id INT AUTO_INCREMENT PRIMARY KEY,
    id_sample INT NOT NULL,
    id_instance INT NOT NULL
);

3.1.6. Membuat Tabel Decision Tree

DROP TABLE IF EXISTS c45_decision_tree;
CREATE TABLE IF NOT EXISTS c45_decision_tree(
    id INT AUTO_INCREMENT PRIMARY KEY,
    id_attribute INT NOT NULL,
    id_instance INT NOT NULL,
    id_target INT DEFAULT '0'
);

3.2. Koneksi ke Database Server

Sebelum melalukan operasi dengan data dari database, perlu dibuat script untuk koneksi ke database terlebih dahulu. Dari database yang sudah dibuat, kita bisa membuat script php untuk membuat koneksi ke database server dengan extension mysqli sebagai berikut:

<?php
//-- konfigurasi database
$dbhost 'localhost';
$dbuser 'root';
$dbpass '';
$dbname 'db_dm';
//-- koneksi ke database server dengan extension mysqli
$db = new mysqli($dbhost,$dbuser,$dbpass,$dbname);
//-- hentikan program dan tampilkan pesan kesalahan jika koneksi gagal
if ($db->connect_error) {
  die(
'Connect Error ('.$db->connect_errno.')'.$db->connect_error);
}
?>

Sesuaikan nilai-nilai $dbhost,$dbuser,$dbpass dan $dbname dengan konfigurasi database yg digunakan.

3.3. Langkah-langkah Algoritma C4.5

<?php
//-- fungsi Entropy
function entropy($S){
    
$entropy=0;
    foreach(
$S as $s){
        
$p$s/array_sum($S);
        
$entropy+=(-$p)*log($p);
    }
    return 
$entropy;
}
//-- fungsi Gain
function gain($S,$Si){
    
$gain=entropy($S);
    foreach(
$Si as $si){
        
$gain-=($si/array_sum($Si))*entropy($Si);
    }
    return 
$gain;
}
?>

  • Basuki A dan Syarif I, 2003. Decision Tree. Politeknik Elektronika Negeri Surabaya (PENS) – ITS
  • Berry, Michael J.A & Linoff, Gordon S. 2004. Data Mining Techniques For Marketing, Sales, Customer Relationship Management Second Editon. United States of America: Wiley Publishing, Inc.
  • Craw, S., 2005. Case based reasoning: Lecture 3: CBR Case-Base Indexing.
  • Han, J., & Kamber, M., 2006. Data mining Concepts and Techniques. San Fransisco: Morgan Kaufmann.
  • Kusrini, & Lutfhi, E. T., 2009. Algoritma Data Mining. Yogyakarta: Andi.
  • Larose, T. D, 2005. An Introduction to Data Mining. Wiley~Interscience: New Jersey.
  • Larose D, T., 2006, Data Mining Methods and Models, Jhon Wiley & Sons, Inc. Hoboken New Jersey
  • Quinlan, J. R., 1993 C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers.
  • Santosa, B., 2007. Data mining (Teknik Pemanfaatan Data untuk Keperluan Bisnis). Surabaya: Graha Ilmu.
  • Santosa, B., 2007. Data mining Terapan. Surabaya: Graha Ilmu.
  • Sunjana, 2010. Seminar Nasional Aplikasi Teknologi Informasi 2010. Snati 2010. Aplikasi Mining Data Mahasiswa Dengan Metode Klasifikasi Decision Tree , 24-29.
  • Tan, P. N., Steinbach, M., & Kumar, V., 2005. DATA MINING. New York: Addison Wesley.