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 2024 hanya 2 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 164 data sample/training).
TABEL 1 : Learning Dataset*
| No. | Jenis Kelamin | Usia | Domisili | IPK | Beasiswa | Waktu Studi |
|---|
| 1 |
Laki-laki |
< 22th |
Dalam kota |
3.51 s.d. 4.00 |
Tidak mendapat beasiswa |
> 8 smtr |
| 2 |
Laki-laki |
< 22th |
Dalam kota |
2.76 s.d. 3.50 |
Mendapat beasiswa |
<= 8 smtr |
| 3 |
Perempuan |
< 22th |
Luar kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
<= 8 smtr |
| 4 |
Laki-laki |
>= 22th |
Luar kota |
2.00 s.d. 2.75 |
Mendapat beasiswa |
<= 8 smtr |
| 5 |
Perempuan |
>= 22th |
Dalam kota |
2.76 s.d. 3.50 |
Mendapat beasiswa |
> 8 smtr |
| 6 |
Laki-laki |
< 22th |
Luar kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
<= 8 smtr |
| 7 |
Laki-laki |
< 22th |
Dalam kota |
3.51 s.d. 4.00 |
Mendapat beasiswa |
<= 8 smtr |
| 8 |
Perempuan |
< 22th |
Dalam kota |
3.51 s.d. 4.00 |
Tidak mendapat beasiswa |
> 8 smtr |
| 9 |
Laki-laki |
>= 22th |
Luar kota |
2.76 s.d. 3.50 |
Mendapat beasiswa |
> 8 smtr |
| 10 |
Laki-laki |
>= 22th |
Dalam kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
<= 8 smtr |
| 11 |
Laki-laki |
>= 22th |
Dalam kota |
2.76 s.d. 3.50 |
Mendapat beasiswa |
<= 8 smtr |
| 12 |
Laki-laki |
>= 22th |
Luar kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
> 8 smtr |
| 13 |
Laki-laki |
>= 22th |
Luar kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
> 8 smtr |
| 14 |
Perempuan |
>= 22th |
Dalam kota |
2.76 s.d. 3.50 |
Mendapat beasiswa |
> 8 smtr |
| 15 |
Perempuan |
< 22th |
Luar kota |
3.51 s.d. 4.00 |
Mendapat beasiswa |
> 8 smtr |
| ... |
| 162 |
Laki-laki |
>= 22th |
Dalam kota |
3.51 s.d. 4.00 |
Tidak mendapat beasiswa |
<= 8 smtr |
| 163 |
Laki-laki |
>= 22th |
Dalam kota |
2.76 s.d. 3.50 |
Tidak mendapat beasiswa |
<= 8 smtr |
| 164 |
Laki-laki |
>= 22th |
Luar 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
| No | Atribut | Nilai Atribut | Jumlah Kasus |
|---|
| Total | <= 8 smtr | > 8 smtr |
|---|
| 1 | Total | Total | 164 | 56 | 108 |
| 2 | Jenis Kelamin | Laki-laki | 87 | 32 | 55 |
| 3 | Jenis Kelamin | Perempuan | 77 | 24 | 53 |
| 4 | Usia | < 22 th | 93 | 30 | 63 |
| 5 | Usia | >= 22 th | 71 | 26 | 45 |
| 6 | Domisili | Dalam kota | 97 | 33 | 64 |
| 7 | Domisili | Luar kota | 67 | 23 | 44 |
| 8 | IPK | 3.51 s.d. 4.00 | 28 | 9 | 19 |
| 9 | IPK | 2.76 s.d. 3.50 | 106 | 37 | 69 |
| 10 | IPK | 2.00 s.d. 2.75 | 30 | 10 | 20 |
| 11 | Beasiswa | Tidak mendapat beasiswa | 66 | 19 | 47 |
| 12 | Beasiswa | Mendapat beasiswa | 98 | 37 | 61 |
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 164 kasus yang terdiri dari 56 "<= 8 smtr" dan 108 "> 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{108}{164})\ *\ log_2(\frac{108}{164}))+(-(\frac{56}{164})\ *\ log_2(\frac{56}{164}))\\&=(-(0.65853658536585) * (-0.41773520069998))+(-(0.34146341463415) * (-1.074514737089))\\&=0.27509391265608+0.36690747120114\\ &=0.64200138385722\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 Kasus | Jumlah '<= 8 Smtr' | Jumlah '> 8 Smtr' | Total Entropy |
|---|
| 164 | 56 | 108 | 0.64200138385722 |
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
| Node | Atribut | Nilai | Jumlah | Entropy | Gain |
|---|
| Total | <= 8 smtr | > 8 smtr |
|---|
| 1 | Jenis Kelamin | Laki-laki | 87 | 32 | 55 | 0.65778312925944 | 0.0017490278712946 |
| Jenis Kelamin | Perempuan | 77 | 24 | 53 | 0.62044485891066 |
| Usia | < 22 th | 93 | 30 | 63 | 0.62879939409378 | 0.0010361832936122 |
| Usia | >= 22 th | 71 | 26 | 45 | 0.65690069354522 |
| Domisili | Dalam kota | 97 | 33 | 64 | 0.64117214485995 | 5.0869557828292E-6 |
| Domisili | Luar kota | 67 | 23 | 44 | 0.64318947224509 |
| IPK | 3.51 s.d. 4.00 | 28 | 9 | 19 | 0.62794158873991 | 0.00026344529384616 |
| IPK | 2.76 s.d. 3.50 | 106 | 37 | 69 | 0.64686068293238 |
| IPK | 2.00 s.d. 2.75 | 30 | 10 | 20 | 0.63651416829481 |
| Beasiswa | Tidak mendapat beasiswa | 66 | 19 | 47 | 0.60024144074559 | 0.0043460209516326 |
| Beasiswa | Mendapat beasiswa | 98 | 37 | 61 | 0.6628524941562 |
Nilai entropy dari masing-masing nilai atribut yang terdapat pada TABEL 4 diperoleh menggunakan persamaan C45-02, sebagai contoh untuk nilai < 22 th dari atribut Usia perhitungan entropy-nya sebagai berikut :
$\begin{align}Entropy_{(Usia,\text{< 22 th})}&=\displaystyle \sum_{i=1}^n (-p_i)* log_2(p_i)\\
&=(\frac{- 30}{93}) * log_2(\frac{30}{93})+(\frac{- 63}{93}) * log_2(\frac{63}{93})\\ &=(-0.32258064516129)*log_2(0.32258064516129)+(-0.67741935483871)*log_2(0.67741935483871)\\ &=(-0.32258064516129)*(-1.1314021114911)+(-0.67741935483871)*(-0.38946476676172)\\ &=0.36496842306165+0.26383097103214\\ &=0.62879939409378 \end{align}$
Setelah menghitung nilai entropy untuk masing-masing nilai dari atribut, berikutnya adalah menghitung nilai Gain dari setiap atribut. Sebagai contoh untuk atribut Usia, nilai gain-nya -- berdasarkan persamaan C45-01 -- bisa di hitung sebagai berikut:
$\begin{align}
Gain_{(total,\text{usia})}&= Entropy(total) - \displaystyle\sum_{i=1}^n \frac{|\text{usia}_i|}{|\text{usia}|}*Entropy(\text{usia}_i)\\
&= 0.64200138385722 - (\frac{93}{164} * 0.62879939409378+\frac{71}{164} * 0.65690069354522) \\
&= 0.64200138385722 - (0.35657526616294+0.28438993440067) \\
&= 0.64200138385722 - 0.64096520056361 \\
&= 0.0010361832936122 \\
\end{align}$
2.2.3. Menentukan Root Node
Dari hasil perhitungan sebelumnya, yang ada di pada TABEL 4 diperoleh nilai Gain terbesar adalah Gain(Beasiswa) yaitu sebesar 0.0043460209516326, maka atribut Beasiswa 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;
}
?>
