Pohon Keputusan ID3 dan C4.5 menggunakan PHP

Moh Nugroho Wibowo

DATA MINING
Data mining adalah serangkaian proses untuk menggali nilai tambah berupa informasi yang selama ini tidak diketahui secara manual dari suatu basis data. Informasi yang dihasilkan diperoleh dengan cara mengekstraksi dan mengenali pola yang penting atau menarik dari data yang terdapat dalam basis data [4].
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.
Menurut Gartner Group data mining adalah suatu proses menemukan hubungan yang berarti, pola, dan kecenderungan dengan memeriksa dalam sekumpulan besar data yang tersimpan dalam penyimpanan dengan menggunakan teknik pengenalan pola seperti teknik statistik dan matematika [5].
Data mining bukanlah suatu bidang yang sama sekali baru. Salah satu kesulitan untuk mendefinisikan data mining adalah kenyataan bahwa data mining mewarisi banyak aspek dan teknik dari bidang-bidang ilmu yang sudah mapan terlebih dulu. Berawal dari beberapa disiplin ilmu, data mining bertujuan untuk memperbaiki teknik tradisional sehingga bisa menangani [6]:
- Jumlah data yang sangat besar
- Dimensi data yang tinggi
- Data yang heterogen dan berbeda bersifat

Menurut para ahli, data mining merupakan sebuah analisa dari observasi data dalam jumlah besar untuk menemukan hubungan yang tidak diketahui sebelumnya dan metode baru untuk meringkas data agar mudah dipahami serta kegunaannya untuk pemilik data.
Data-data yang ada, tidak dapat langsung diolah dengan menggunakan sistem data mining. Data-data tersebut harus dipersiapkan terlebih dahulu agar hasil yang diperoleh dapat lebih maksimal, dan waktu komputasinya lebih minimal. Proses persiapan data ini sendiri dapat mencapai 60 % dari keseluruhan proses dalam data mining. Adapun tahapan-tahapan yang harus dilalui dalam proses data mining antara lain [7]:
1. Data cleaning, untuk membersihkan data dari noise data dan data yang tidak konsiten.
2. Data integration, mengkombinasikan atau mengintegrasikan beberapa sumber data.
3. Data selection, mengambil data-data yang relevan dari database untuk dianalisis.
4. Data transformation, mentransformasikan data summary ataupun operasi agregasi.
5. Data mining, merupakan proses yang esensial dimana metode digunakan untuk mengekstrak pola data yang tersembunyi.
6. Pattern evaluation, untuk mengidentifikasi pola sehingga mereperesentasikan pengetahuan berdasarkan nilai-nilai yang menarik
7. Knowledge presentation, dimana teknik representasi dan visualisasi data digunakan untuk mempresentasikan pengetahuan yang didadapat kepada user.

Gambar: Tahap-tahap Data Mining [7]

Teknik Data mining
Ada banyak jenis teknik analisa yang dapat digolongkan dalam data mining. Namun ada tiga teknik data mining yang popular, yaitu [7]:
1. Association Rule Mining
Association rule mining adalah teknik mining untuk menemukan aturan asosiatif antara suatu kombinasi atribut. Contoh dari aturan asosiatif dari analisa pembelian di suatu pasar swalayan diketahui berapa besar kemungkinan seorang pelanggan membeli roti bersamaan dengan susu. Dengan pengetahuan tersebut pemilik pasar swalayan dapat mengatur penempatan barangnya atau merancang strategi pemasaran dengan memakai kupon diskon untuk kombinasi barang tertentu.
2. Klasifikasi
Klasifikasi adalah proses untuk menemukan model atau fungsi yang menjelaskan atau membedakan konsep atau kelas data, dengan tujuan untuk dapat memperkirakan kelas dari suatu objek yang labelnya tidak diketahui. Model itu sendiri bisa berupa aturan “jika-maka”, berupa pohon keputusan, formula matematis atau neural network.
Proses klasifikasi biasanya dibagi menjadi dua fase : learning dan test. Pada fase learning, sebagian data yang telah diketahui kelas datanya diumpankan untuk membentuk model perkiraan. Kemudian pada fase test model yang sudah terbentuk diuji dengan sebagian data lainnya untuk mengetahui akurasi dari model tsb. Bila akurasinya mencukupi model ini dapat dipakai untuk prediksi kelas data yang belum diketahui.
3. Clustering
Berbeda dengan association rule mining dan klasifikasi dimana kelas data telah ditentukan sebelumnya, clustering melakukan pengelompokan data tanpa berdasarkan kelas data tertentu. Bahkan clustering dapat dipakai untuk memberikan label pada kelas data yang belum diketahui. Karena itu clustering sering digolongkan sebagai metode unsupervised learning. Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu kelas dan meminimumkan kesamaan antar cluster. Clustering dapat dilakukan pada data yang memiliki beberapa atribut yang dipetakan sebagai ruang multidimensi.

POHON KEPUTUSAN
Salah satu metode data mining yang umum digunakan adalah pohon keputusan. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan rule. Pohon keputusan adalah salah satu metode klasifikasi yang paling popular karena mudah untuk diinterpretasi oleh manusia. Konsep dari pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan [8].

Gambar: Konsep Pohon Keputusan

Data dalam pohon keputusan biasanya dinyatakan dalam bentuk tabel dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan tree

Gambar: Konsep Data dalam Pohon Keputusan

Proses pada pohon keputusan adalah mengubah bentuk data (tabel) menjadi model pohon, mengubah model pohon menjadi rule, dan menyederhanakan rule. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya untuk membreak down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan. Pohon Keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target.
Pohon keputusan merupakan himpunan aturan IF...THEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, di mana premis terdiri atas sekumpulan node-node yang ditemui, dan kesimpulan dari aturam terdiri atas kelas yang terhubung dengan leaf dari path [9].

Gambar: Konsep Dasar Pohon Keputusan [10]

Bagian awal dari pohon keputusan ini adalah titik akar (root), sedangkan setiap cabang dari pohon keputusan merupakan pembagian berdasarkan hasil uji, dan titik akhir (leaf) merupakan pembagian kelas yang dihasilkan.
Pohon keputusan mempunyai 3 tipe simpul yaitu [11]:
1. Simpul akar, dimana tidak memiliki cabang yang masuk dan memiliki cabang lebih dari satu, terkadang tidak memiliki cabang sama sekali. Simpul ini biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu.
2. Simpul internal, dimana hanya memiliki 1 cabang yang masuk, dan memiliki lebih dari 1 cabang yang keluar.
3. Simpul daun, atau simpul akhir dimana hanya memiliki 1 cabang yang masuk, dan tidak memiliki cabang sama sekali dan menandai bahwa simpul tersebut merupakan label kelas.

Tahap awal dilakukan pengujian simpul akar, jika pada pengujian simpul akar menghasilkan sesuatu maka proses pengujian juga dilakukan pada setiap cabang berdasarkan hasil dari pengujian. Hal ini berlaku juga untuk simpul internal dimana suatu kondisi pengujian baru akan diterapkan pada simpul daun. Pada umumnya proses dari sistem pohon keputusan adalah mengadopsi strategi pencarian top-down untuk solusi ruang pencariannya. Pada proses mengklasifikasikan sampel yang tidak diketahui, nilai atribut akan diuji pada pohon keputusan dengan cara melacak jalur dari titik akar sampai titik akhir, kemudian akan diprediksikan kelas yang ditempati sampel baru tersebut.
Pohon keputusan banyak digunakan dalam proses data mining karena memiliki beberapa kelebihan, yaitu:
1. Tidak memerlukan biaya yang mahal saat membangun algoritma.
2. Mudah untuk diinterpetasikan.
3. Mudah mengintegrasikan dengan sistem basis data.
4. Memiliki nilai ketelitian yang lebih baik.
5. Dapat menemukan hubungan tak terduga dan suatu data.
6. Dapat menggunakan data pasti/mutlak atau data kontinu.
7. Mengakomodasi data yang hilang.

Berikut contoh penerapan pohon keputusan dalam memprediksi kelayakan kredit:

Gambar: Contoh Pohon Keputusan dalam Identifikasi Kelayakan Kredit

Dari pohon tersebut diketahui bahwa pemohon yang layak menerima kredit adalah pemohon yang penghasilannya sama dengan 2- 3x angsuran dan kepemilikan rumahnya milik sendiri.
Pohon keputusan banyak mengalami perkembangan, beberapa algoritma yang populer dan sering dipakai adalah Pohon Keputusan ID3 dan C4.5. Tabel berikut menunjukkan frekuensi pemakaian dari bermacam-macam algoritma pohon keputusan [12]:

Tabel: Frekuensi Penggunaan Algoritma Pohon Keputusan

Pohon Keputusan ID3
Algoritma Pohon Keputusan ID3 atau Iterative Dichotomiser 3 (ID3) merupakan sebuah metode yang digunakan untuk membuat pohon keputusan yang telah dikembangkan oleh J. Ross Quinlan sejak tahun 1986. Algoritma pada metode ini menggunakan konsep dari entropy informasi. Algoritma ini melakukan pencarian secara rakus/menyeluruh (greedy) pada semua kemungkinan pohon keputusan [13].
Secara ringkas, langkah kerja Algoritma ID3 dapat digambarkan sebagai berikut [10]:
1. Hitung Entropy dan Information gain dari setiap atribut dengan menggunakan rumus:

Dimana:
S = ruang (data) sample yang digunakan untuk training.
P+ = jumlah yang bersolusi positif (mendukung) pada data sample untuk kriteria tertentu.
P- = jumlah yang bersolusi negatif (tidak mendukung) pada data sample untuk kriteria tertentu.

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
V = suatu nilai yang mungkin untuk atribut A.
Nilai(A) = himpunan yang mungkin untuk atribut A.
|Sv| = jumlah sample untuk nilai V.
|S| = jumlah seluruh sample data.
Entropy(Sv) = entropy untuk sample-sample yang memiliki nilai V.
Tujuan dari pengukuran nilai information gain adalah untuk memilih atribut yang akan dijadikan cabang pada pembentukan pohon keputusan. Pilih atribut yang memiliki nilai information gain terbesar.
2. Bentuk simpul yang berisi atribut tersebut.
3. Ulangi proses perhitungan information gain yang akan terus dilaksanakan sampai semua data telah termasuk dalam kelas yang sama. Atribut yang telah dipilih tidak diikutkan lagi dalam perhitungan nilai information gain.

ID3 berhenti jika atribut sempurna mengklasifikasikan training sets. Atau secara rekursif mengoperasikan nilai n, dimana n adalah banyaknya nilai kemungkinan dari suatu untuk mendapatkan atribut terbaik [2].
Adapun sample data yang digunakan oleh ID3 memiliki beberapa syarat, yaitu [14]:
- Deskripsi atribut-nilai. Atribut yang sama harus mendeskripsikan tiap contoh dan memiliki jumlah nilai yang sudah ditentukan.
- Kelas yang sudah didefinisikan sebelumnya. Suatu atribut contoh harus sudah didefinisikan, karena mereka tidak dipelajari oleh ID3.
- Kelas-kelas yang diskrit. Kelas harus digambarkan dengan jelas. Kelas yang kontinu dipecah-pecah menjadi kategori-kategori yang relatif, misalnya saja metal dikategorikan menjadi “hard, quite hard, flexible, soft, quite soft”.
- Jumlah contoh (example) yang cukup. Karena pembangkitan induktif digunakan, maka dibutuhkan test case yang cukup untuk membedakan pola yang valid dari peluang suatu kejadian.

Pohon Keputusan C4.5
Algoritma Pohon Keputusan C4.5 atau Classification version 4.5 adalah pengembangan dari algoritma ID3. Oleh karena pengembangan tersebut, algoritma C4.5 mempunyai prinsip dasar kerja yang sama dengan algoritma ID3. Perbedaan utama C4.5 dari ID3 adalah:
- C4.5 dapat menangani atribut kontinyu dan diskrit.
- C4.5 dapat menangani training data dengan missing value.
- Hasil pohon keputusan C4.5 akan dipangkas setelah dibentuk.
- Pemilihan atribut yang dilakukan dengan menggunakan Gain Ratio.
Information gain pada ID3 lebih mengutamakan pengujian yang menghasilkan banyak keluaran. Dengan kata lain, atribut yang memiliki banyak nilailah yang dipilih sebagai splitting atribut. Sebagai contoh, pembagian terhadap atribut yang berfungsi sebagai unique identifier, seperti product_ID¸ akan menghasilkan keluaran dalam jumlah yang banyak, di mana setiap keluaran hanya terdiri dari satu tuple. Partisi semacam ini tentu saja bersifat pure, sehingga informasi yang dibutuhkan untuk mengklasifikasi D berdasarkan partisi seperti ini adalah sebesar Infoproduct_ID(D) = 0. Sebagai akibatnya, information gain yang dimiliki atribut product_ID menjadi maksimal. Padahal, jelas sekali terlihat bahwa partisi semacam ini tidaklah berguna.

Karena itu algoritma C4.5 yang merupakan suksesor dari ID3 menggunakan gain ratio untuk memperbaiki information gain, dengan rumus gain ratio:

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
Gain(S,A) = information gain pada atribut A
SplitInfo(S,A) = split information pada atribut A
Atribut dengan nilai Gain Ratio tertinggi dipilih sebagai atribut test untuk simpul. Dengan gain adalah information gain. Pendekatan ini menerapkan normalisasi pada information gain dengan menggunakan apa yang disebut sebagai split information. SplitInfo menyatakan entropy atau informasi potensial dengan rumus:

Dimana:
S = ruang (data) sample yang digunakan untuk training.
A = atribut.
Si = jumlah sample untuk atribut i

Pada saat pembangunan pohon keputusan, banyaknya cabang mungkin mencerminkan adanya noise atau outlier pada training data. Pemangkasan pohon dapat dilakukan untuk mengenali dan menghapus cabang-cabang tersebut. Pohon yang dipangkas akan menjadi lebih kecil dan lebih mudah dipahami. Pohon semacam itu biasanya juga menjadi lebih cepat dan lebih baik dalam melakukan klasifikasi.
Ada dua metode dalam melakukan pemangkasan dalam pohon keputusan, yaitu [15]:
a. Prepruning yaitu menghentikan pembangunan suatu subtree lebih awal, yaitu dengan memutuskan untuk tidak lebih jauh mempartisi data training. Pada pendekatan prepruning, sebuah pohon dipangkas dengan cara menghentikan pembangunannya jika partisi yang akan dibuat dianggap tidak signifikan.
b. Postpruning yaitu menyederhanakan pohon dengan cara membuang beberapa cabang subtree setelah pohon selesai dibangun. Metode postpruning ini merupakan metode standard untuk algoritma C4.5.

Gambar: Pohon keputusan sebelum dan setelah dipangkas [15]

Pemangkasan pohon juga dapat digunakan untuk mengatasi overfitting. Overfitting terjadi karena ada noise data training, yaitu data yang tidak relevan sehingga mengakibatkan pohon memiliki subtree yang panjang dan tidak seimbang. Misal internal node memiliki kelas YA = 5 dan TIDAK = 1. Data yang berada pada kelas TIDAK merupakan noise, sehingga apabila data tersebut diolah akan menghasilkan pohon dengan subtree yang panjang. Overfitting juga dapat terjadi karena data training yang sedikit.

Post Pruning - Reduced Error Prunning (REP)
Reduced Error Pruning merupakan salah satu algoritma postpruning. Algoritma ini membagi data menjadi dua, yaitu training data dan test data. Training data adalah data yang digunakan untuk membentuk pohon keputusan, sedangkan test data digunakan untuk menghitung nilai error rate pada pohon setelah dipangkas.
Cara kerja REP adalah dengan memangkas internal node yang dimulai dari internal node paling bawah ke atas. Pemangkasan dilakukan dengan cara mengganti atribut dengan leaf node yang memiliki kelas yang dominan muncul. Setelah itu test data diproses menggunakan rule hasil pemangkasan, kemudian dihitung nilai error ratenya. Test data juga diproses dengan rule awal, yaitu rule yang terbentuk sebelum pohon dipangkas, kemudian dihitung nilai error ratenya. Apabila nilai error rate yang dihasilkan dari pemangkasan pohon lebih kecil, maka pemangkasan dilakukan.

Pre Prunning
Prepruning yaitu menghentikan pembangunan suatu subtree lebih awal, yaitu dengan memutuskan untuk tidak lebih jauh mempartisi data training. Rumus prepruning:

Yang saya bingung sampai sekarang adalah rumus untuk mendapatkan nilai z (batas kepercayaan). Dalam aplikasi yang saya buat, saya memberi nilai default pada z, yaitu z = 1.645 dimana batas kepercayaan dengan nilai tersebut adalah 95%.
Contoh perhitungan prepruning dapat didownload di http://id3-c45.xp3.biz/dokumentasi/Decision-Tree.10.11.ppt

Daftar Referensi:
1. Sunjana. Klasifikasi Data Nasabah Sebuah Asuransi menggunakan Algoritma C4.5. Seminar Nasional Aplikasi Teknologi Informasi 2010 (SNATI 2010) ISSN: 1907-5022. 1: 1-2. 2012.
2. Sharma, Aman K., dan Sahni, Suruchi. A Comparative Study of Classification Algorithms for Spam Email Data Analysis. International Journal on Computer Science and Engineering (IJCSE) ISSN : 0975-3397. 1: 2-5. 2011.
3. Kumar, S. Anupama, dan M.N, Vijayalakshmi. Efficiency of Decision Trees in Predicting Student’s Academic Performance. Computer Science & Information Technology (CS & IT) DOI: 10.5121/csit.2011.1230. 1: 5-8. 2011.
4. Fairuzabadi, Muhammad. BAB I Konsep, Pengertian, Manfaat, dan Tujuan Data Mining, 2009. URL:http://fairuzelsaid.wordpress.com/2009/10/27/data-mining-1-konsep-pengertian-manfaat-dan-tujuan-data-mining/, diakses tanggal 20 November 2011.
5. Larose, Daniel T. Discovering Knowledge in Data: An Introduction to Data Mining. New Jersey : John Willey & Sons, Inc. 2005.
6. Shaufiah. Pengenalan Data Mining, 2010. URL:http://imeldas.blog.ittelkom.ac.id/blog/files/2010/03/Dami1_Introduction.pdf, diakses tanggal 20 November 2011.
7. Pramudiono, Iko. Pengantar Data Mining: Menambang Permata Pengetahuan di Gunung Data. 2003. URL:http://ikc.dinus.ac.id/umum/iko/iko-datamining.zip, diakses tanggal 12 November 2011.
8. Basuki, Achmad., dan Syarif, Iwan. Pohon keputusan. 2003. URL:http://lecturer.eepis-its.edu/~basuki/lecture/DecisionTree.pdf, diakses tanggal 20 November 2011.
9. Romansyah, F., Sitanggang I. S., dan Nurdiati, S. Fuzzy Decision Tree dengan Algoritma ID3 pada Data Diabetes. Internetworking Indonesia Journal Vol. 1/No. 2 (2009). 1: 2. 2009.
10. Defianti, Sofi., dan Pardede, D. L. C. Perbandingan Kinerja Algoritma ID3 dan C4.5 dalam Klasifikasi Spam-Mail. 2008. URL:http://openstorage.gunadarma.ac.id/~mwiryana/KOMMIT/per-artikel/03-02-004-Perbandingan%5BSofi%5D.pdf, diakses tanggal 14 Agustus 2011.
11. Nugroho, Fanuel., Kristanto, Harianto., dan Oslan, Yetli. Validitas Suatu Alamat menggunakan Pohon keputusan dengan Algoritma ID3. Jurnal Informatika, Volume 3 Nomor 2 April 2007. 1: 2. 2007.
12. Anyanwu, Matthew N., and Shiva Sajjan G. Comparative Analysis of Serial Decision Tree Classification Algorithms. International Journal of Computer Science and Security, (IJCSS) Volume (3) : Issue (3). 1: 2-4. Tanpa Tahun.
13. Wahyudin. Metode Iterative Dichotomizer 3 (ID3) Untuk Penerimaan Mahasiswa Baru. Tanpa Tahun. URL:http://file.upi.edu/Direktori/FPMIPA/PRODI._ILMU_KOMPUTER/WAHYUDIN/metode_ID3_untuk_mhs_baru.pdf, diakses tanggal 14 Agustus 2011.
14. Setiawan, Bambang. Perancangan Sistem Pendukung Keputusan (SPK) untuk Menentukan Kelaiklautan Kapal. Tanpa Tahun. URL:http://digilib.its.ac.id/public/ITS-Master-10163-Paper.pdf, diakses tanggal 14 Agustus 2011.
15. Khairina, Indah Kuntum. Penggunaan Pohon Keputusan untuk Data Mining. Tanpa Tahun. URL:http://www.informatika.org/~rinaldi/Matdis/2008-2009/Makalah2008/Makalah0809-039.pdf, diakses tanggal 10 November 2011.

IMPLEMENTASI POHON KEPUTUSAN MENGGUNAKAN PHP
Program sederhana yang saya buat ini menggunakan bahasa pemrograman PHP dengan studi kasus untuk identifikasi kelayakan kredit. Contoh yang saya buat menggunakan data survey (data training) sebanyak 14 record dengan atribut: penghasilan, pekerjaan, sikap di lingkungan, dan kepemilikan rumah. Kelas dari data tersebut adalah layak dan tidak layak. Berikut data surveynya:

Program yang saya buat ini sudah saya bandingkan  dengan menggunakan software WEKA dan hasilnya 100% akurat. Agar data training dapat dibaca di WEKA, maka data training harus diubah dalam format ARFF. File ARFF data training dalam aplikasi ini sudah saya sertakan dalam file rar source code.  Berikut screenshot perbandingannya:

Gambar: Pohon Keputusan ID3 dan C4.5 yang digenerate oleh Aplikasi

Gambar: Pohon Keputusan ID3 yang digenerate oleh WEKA

Gambar: Pohon Keputusan C4.5 yang digenerate oleh WEKA