Algoritma C4.5 merupakan kelompok algoritma Decision Tree. Algoritma ini mempunyai input berupa training samples dan samples. Training samples berupa data contoh yang akan digunakan untuk membangun sebuah tree yang telah diuji kebenarannya. Sedangkan samplesmerupakan field-field data yang nantinya akan digunakan sebagai parameter dalam melakukan klasifikasi data (Sunjana, 2010)

Algoritma C 4.5 adalah salah satu metode untuk membuat decision tree berdasarkan training data yang telah disediakan. Algoritma C 4.5 dibuat oleh Ross Quinlan yang merupakan pengembangan dari ID3 yang juga dibuat oleh Quinlan (Quinlan, 1993). Beberapa pengembangan yang dilakukan pada C4.5 adalah sebagai antara lain bisa mengatasi missing value, bisa mengatasi continue data, danpruning.

Klasifikasi

Klasifikasi data merupakan suatu proses yang menemukan properti-properti yang sama pada sebuah himpunan obyek di dalam sebuah basis data dan mengklasifikasikannya ke dalam kelas-kelas yang berbeda menurut model klasifikasi yang ditetapkan. Tujuan dari klasifikasi adalah untuk menemukan model dari training set yang membedakan atribut ke dalam kategori atau kelas yang sesuai, model tersebut kemudian digunakan untuk mengklasifikasikan atribut yang kelasnya belum diketahui sebelumnya. Teknik klasifikasi terbagi menjadi beberapa teknik yang diantaranya adalah Pohon Keputusan.

Pohon Keputusan (Decision Tree)

Pohon keputusan merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Dan mereka juga dapat diekspresikan dalam bentuk bahasa basis data seperti Structured Query Language untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target.

Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain. Sebuah pohon keputusan adalah sebuah struktur yang dapat digunakan untuk membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan. Dengan masing- masing rangkaian pembagian, anggota himpunan hasil menjadi mirip satu dengan yang lain (Berry dan Linoff, 2004).

Sebuah model pohon keputusan terdiri dari sekumpulan aturan untuk membagi sejumlah populasi yang heterogen menjadi lebih kecil, lebih homogen dengan memperhatikan pada variabel tujuannya. Sebuah pohon keputusan mungkin dibangun dengan seksama secara manual atau dapat tumbuh secara otomatis dengan menerapkan salah satu atau beberapa algoritma pohon keputusan untuk memodelkan himpunan data yang belum terklasifikasi.

Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probability dari tiap-tiap record terhadap kategori-kategori tersebut atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel continue meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.

Banyak algoritma yang dapat dipakai dalam pembentukan pohon keputusan,antara lain ID3, CART, dan C4.5 (Larose, 2006).

Data dalam pohon keputusan biasanya dinyatakan dalam bentuk tabel dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan pohon. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin, dan temperatur.

Salah satu atribut merupakan atribut yang menyatakan data solusi per item data yang disebut target atribut. Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan, dan hujan (Basuki dan Syarif, 2003)

Proses pada pohon keputusan adalah mengubah bentuk data (tabel) menjadi model pohon, mengubah model pohon menjadi rule, dan menyederhanakan rule (Basuki dan Syarif, 2003).

Algoritma C4.5

Berikut ini algoritma dasar dari C4.5: Input : sampel training, label training, atribut

Membuat simpul akar untuk pohon yang dibuat
Jika semua sampel positif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (+)
Jika semua sampel negatif, berhenti dengan suatu pohon dengan satu simpul akar, beri tanda (-)
Jika atribut kosong, berhenti dengan suatu pohon dengan suatu simpul akar, dengan label sesuai nilai yang terbanyak yang ada pada label training
Untuk yang lain, Mulai
1. A ------ atribut yang mengklasifikasikan sampel dengan hasil terbaik (berdasarkan Gain rasio)
2. Atribut keputusan untuk simpul akar ----- A
3. Untuk setiap nilai, vi, yang mungkin untuk A
  1. Tambahkan cabang di bawah akar yang berhubungan dengan A= vi
  2. Tentukan sampel Svi sebagai subset dari sampel yang mempunyai nilai vi untuk atrribut A
  3. Jika sampel Svi kosong
    1. Di bawah cabang tambahkan simpul daun dengan label = nilai yang terbanyak yang ada pada label training
    2. Yang lain tambah cabang baru di bawah cabang yang sekarang C4.5 (sampel training, label training, atribut-[A])
4. Berhenti

Mengubah tree yang dihasilkan dalam beberapa rule. Jumlah rule sama dengan jumlah path yang mungkin dapat dibangun dari root sampai leaf node.

Prinsip Kerja

Pada tahap pembelajaran algoritma C4.5 memiliki 2 prinsip kerja yaitu:

Pembuatan pohon keputusan. Tujuan dari algoritma penginduksi pohon keputusan adalah mengkontruksi struktur data pohon yang dapat digunakan untuk memprediksi kelas dari sebuah kasus atau record baru yang belum memiliki kelas. C4.5 melakukan konstruksi pohon keputusan dengan metode divide and conquer. Pada awalnya hanya dibuat node akar dengan menerapkan algoritma divide and conquer. Algoritma ini memilih pemecahan kasus-kasus yang terbaik dengan menghitung dan membandingkangain ratio, kemudian node-node yang terbentuk di level berikutnya, algoritma divide and conquer akan diterapkan lagi sampai terbentuk daun-daun.
Pembuatan aturan-aturan (rule set). Aturan-aturan yang terbentuk dari pohon keputusan akan membentuk suatu kondisi dalam bentuk if-then. Aturan-aturan ini didapat dengan cara menelusuri pohon keputusan dari akar sampai daun. Setiap node dan syarat percabangan akan membentuk suatu kondisi atau suatu if, sedangkan untuk nilai-nilai yang terdapat pada daun akan membentuk suatu hasil atau suatu then.

Information Gain

Information gain adalah salah satu attribute selection measure yang digunakan untuk memilih test attribute tiap node pada tree. Atribut dengan informasi gain tertinggi dipilih sebagai test atribut dari suatu node (Sunjana, 2010). Dalam prosesnya perhitungan gain bisa terjadi atau tidak suatu missing value.

Contoh Kasus

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 1 semester. Dari data kelulusan yang diperoleh dari sekretariat Jurusan Teknik Komputer Program Sarjana (S1) angkatan 2012 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.

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.

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;

Membuat Data Tabel Atributtes

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'
);

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)
);

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)
);

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
);

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.
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.