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 1 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 395 data sample/training).

TABEL 1 : Learning Dataset*
No.Jenis KelaminUsiaDomisiliIPKBeasiswaWaktu Studi
1 Perempuan < 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
2 Laki-laki < 22th Luar kota 3.51 s.d. 4.00 Mendapat beasiswa <= 8 smtr
3 Laki-laki < 22th Dalam kota 2.00 s.d. 2.75 Tidak mendapat beasiswa > 8 smtr
4 Laki-laki >= 22th Dalam kota 3.51 s.d. 4.00 Tidak mendapat beasiswa > 8 smtr
5 Laki-laki < 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr
6 Perempuan >= 22th Luar kota 2.76 s.d. 3.50 Mendapat beasiswa > 8 smtr
7 Laki-laki >= 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr
8 Perempuan >= 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa > 8 smtr
9 Perempuan < 22th Dalam kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
10 Perempuan < 22th Luar kota 2.76 s.d. 3.50 Tidak 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 Luar kota 2.76 s.d. 3.50 Mendapat beasiswa <= 8 smtr
14 Perempuan < 22th Luar kota 3.51 s.d. 4.00 Tidak mendapat beasiswa <= 8 smtr
15 Perempuan < 22th Luar kota 2.00 s.d. 2.75 Mendapat beasiswa <= 8 smtr
...
393 Laki-laki < 22th Dalam kota 2.76 s.d. 3.50 Tidak mendapat beasiswa <= 8 smtr
394 Perempuan >= 22th Dalam kota 2.00 s.d. 2.75 Tidak mendapat beasiswa <= 8 smtr
395 Perempuan < 22th Luar kota 3.51 s.d. 4.00 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
1TotalTotal395118277
2Jenis KelaminPerempuan17549126
3Jenis KelaminLaki-laki22069151
4Usia< 22 th21763154
5Usia>= 22 th17855123
6DomisiliDalam kota22068152
7DomisiliLuar kota17550125
8IPK2.76 s.d. 3.5026479185
9IPK3.51 s.d. 4.00522131
10IPK2.00 s.d. 2.75791861
11BeasiswaMendapat beasiswa19564131
12BeasiswaTidak mendapat beasiswa20054146

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 395 kasus yang terdiri dari 118 "<= 8 smtr" dan 277 "> 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{118}{395})\ *\ log_2(\frac{118}{395}))+(-(\frac{277}{395})\ *\ log_2(\frac{277}{395}))\\&=(-(0.29873417721519) * (-1.2082011404355))+(-(0.70126582278481) * (-0.35486825871378))\\&=0.36093097359844+0.24885698142713\\ &=0.60978795502557\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
3951182770.60978795502557

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 KelaminPerempuan175491260.592953317447470.0006682421785793
Jenis KelaminLaki-laki220691510.62197934555116
Usia< 22 th217631540.602440263520340.00020565569060693
Usia>= 22 th178551230.61828916322134
DomisiliDalam kota220681520.618371350349590.00032244849562446
DomisiliLuar kota175501250.59826958858526
IPK2.76 s.d. 3.50264791850.61022104259940.0058111523181384
IPK3.51 s.d. 4.005221310.67454036221159
IPK2.00 s.d. 2.757918610.5366630757999
BeasiswaMendapat beasiswa195641310.632900242284930.0020225999084095
BeasiswaTidak mendapat beasiswa200541460.5832588401286

Nilai entropy dari masing-masing nilai atribut yang terdapat pada TABEL 4 diperoleh menggunakan persamaan C45-02, sebagai contoh untuk nilai Tidak mendapat beasiswa dari atribut Beasiswa perhitungan entropy-nya sebagai berikut :

2.2.3. Menentukan Root Node

Karena nilai Gain terbesar adalah Gain(IPK) yaitu sebesar 0.0058111523181384, maka atribut IPK 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.