Algoritma Decision Tree C4.5
Pohon Keputusan (Decision Tree) 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. Aturan ini juga
dapat diekspresikan dalam bentuk bahasa basis data seperti SQL 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 ini sangat bagus sebagai langkah awal dalam
proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa
teknik lain(J R Quinlan, 1993).
Dalam situasi lain kemampuan untuk menjelaskan alasan pengambilan keputusan adalah sesuatu yang sangat penting. Misalnya pada perusahaan asuransi ada larangan resmi untuk mendeskriminasi berdasarkan variabel-variabel tertentu. Perusahaan asuransi dapat mencari sendiri keadaan yang mencerminkan bahwa mereka tidak menggunakan deskriminasi yang ilegal dalam memutuskan seseorang diterima atau ditolak. 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. Anggota himpunan hasil menjadi mirip satu dengan yang lain dengan masing-masing rangkaian pembagian. 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 (Tan dkk, 2004).
Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-masing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.
Kelebihan dari metode pohon keputusan adalah:
Dalam situasi lain kemampuan untuk menjelaskan alasan pengambilan keputusan adalah sesuatu yang sangat penting. Misalnya pada perusahaan asuransi ada larangan resmi untuk mendeskriminasi berdasarkan variabel-variabel tertentu. Perusahaan asuransi dapat mencari sendiri keadaan yang mencerminkan bahwa mereka tidak menggunakan deskriminasi yang ilegal dalam memutuskan seseorang diterima atau ditolak. 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. Anggota himpunan hasil menjadi mirip satu dengan yang lain dengan masing-masing rangkaian pembagian. 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 (Tan dkk, 2004).
Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-masing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.
Kelebihan dari metode pohon keputusan adalah:
- Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik
- Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sampel diuji hanya berdasarkan kriteria atau kelas tertentu
- Fleksibel untuk memilih fitur dari node internal yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama. Kefleksibelan metode pohon keputusan ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih konvensional
- Dalam analisis multivarian, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.
Kekurangan pada pohon keputusan adalah:
- Terjadi overlapping terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan
- Pengakumulasian jumlah kesalahan dari setiap tingkat dalam sebuah pohon keputusan yang besar
- Kesulitan dalam mendesain pohon keputusan yang optimal
- Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.
Pohon keputusan adalah model prediksi menggunakan struktur pohon
atau struktur berhirarki. Contoh dari pohon keputusan dapat dilihat pada Gambar
berikut :
Gambar Model Pohon Keputusan (Pramudiono,2008)
Setiap percabangan menyatakan kondisi yang harus dipenuhi dan
tiap ujung pohon menyatakan kelas data. Contoh pada Gambar diatas adalah
identifikasi pembeli komputer. Dari pohon keputusan tersebut diketahui bahwa
salah satu kelompok yang potensial membeli komputer adalah orang yang berusia
di bawah 30 tahun dan juga pelajar. Setelah sebuah pohon keputusan dibangun
maka dapat digunakan untuk mengklasifikasikan record yang belum
ada kelasnya. Dimulai dari node root, menggunakan tes
terhadap atribut dari record yang belum ada kelasnya ini lalu
mengikuti cabang yang sesuai dengan hasil dari tes tersebut, yang akan membawa
kepada internal node (node yang memiliki satu
cabang masuk dan dua atau lebih cabang yang keluar), dengan cara harus
melakukan tes lagi terhadap atribut atau node leaf. Record yang
kelasnya tidak diketahui kemudian diberikan kelas yang sesuai dengan kelas yang
ada pada node leaf. Pada pohon keputusan setiap simpul leaf
menandai label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk data
(tabel) menjadi model pohon (tree) kemudian mengubah model pohon
tersebut menjadi aturan (rule) (J R Quinlan, 1993).
Salah satu algoritma induksi pohon keputusan yaitu ID3 (Iterative
Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Dalam prosedur
algoritma ID3, input berupa sampel training, label training dan atribut.
Algoritma Decision Tree C4.5 merupakan pengembangan dari ID3. Sedangkan
pada perangkat lunak open source WEKA mempunyai versi sendiri
dari C4.5 yang dikenal sebagai J48..
ijin share ilmu pohon keputusan yg pernah saya pelajari di http://nugikkool.blogspot.co.id/2012/08/pohon-keputusan-id3-dan-c45-menggunakan.html
BalasHapusjuga ada implementasi program pohon keputusan di php, perhitungan manual, penjelasan pruning, dll. semoga bermanfaat.