Klasifikasi Decision Tree

KLASIFIKASI DECISION TREE

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. Klasifikasi merupakan suatu teknik yang digunakan untuk mengetahui atau memperkirakan kelas dari suatu objek berdasarkan atribut yang ada. Klasifikasi dapat diselesaikan menggunakan metode statistika dan machine learning.

Proses klasifikasi biasanya dibagi menjadi dua fase :

Fase learning : sebagian data yang telah diketahui kelas datanya diumpankan untuk membentuk model perkiraan.
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. Klasifikasi dicirikan dengan data training mempunyai label, berdasarkan label ini proses klasifikasi memperoleh pola attribut dari suatu data.

Ada beberapa jenis teknik klasifikasi yang akan kita bahas di sini, antara lain :

Logistic regression
K-nearest neighbors
Support vector machine (SVM)
Naive Bayes
Decision tree classification
Random forest classification

Mengapa data perlu di-preprocessing?

Karena dalam data mentah masih terdapat data yang : incomplete, yaitu

data yang kekurangan nilai atribut atau hanya mengandung agregat data (contoh : address = " ").
noisy, yaitu data yang masih mengandung error dan outliers (contoh : salary = -10).
inconsistent, yaitu data yang mengandung discrepansi dalam code dan nama atau singkatnya datanya tidak konsisten (contoh : dulu rating = 1,2,3 sekarang a,b,c).

Decision tree

Decision tree merupakan struktur seperti bagan alur dimana setiap simpul internal mewakili kemungkinan yang ada pada atribut, masing-masing cabang mewakili hasil dari kemungkinan itu dan setiap simpul daun mewakili nama kelas (keputusan dibuat setelah semua atribut telah dihitung). Jalur dari root ke leaf mewakili aturan klasifikasi. Dalam analisis keputusan, decision tree dan diagram yang terkait dengan itu digunakan sebagai alat pendukung keputusan visual dan analitis, dimana akan dihitungnya nilai atau utilitas yang diharapkan dari alternatif yang ada.

Decision tree merupakan suatu metode klasifikasi yang menggunakan struktur pohon, dimana setiap node merepresentasikan atribut dan cabangnya merepresentasikan nilai dari atribut, sedangkan daunnya digunakan untuk merepresentasikan kelas. Node teratas dari decision tree ini disebut dengan root.

Breiman et al. (1984) menyatakan bahwa metode ini merupakan metode yang sangat populer untuk digunakan karena hasil dari model yang terbentuk mudah untuk dipahami. Dinamai pohon keputusan karena aturan yang dibentuk mirip dengan bentuk pohon. Pohon dibentuk dari proses penyortiran rekursif biner dalam kelompok data, sehingga nilai variabel respons di setiap kelompok data membuat hasil penyortiran menjadi lebih homogen.

Decision tree juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Decision tree memadukan antara eksplorasi data dan pemodelan, sehingga sangat bagus sebagai langkah awal dalam proses pemodelan. Nama lain dari decision tree adalah CART (Classification and Regression Tree). Dimana metode ini merupakan gabungan dari dua jenis pohon, yaitu classification tree dan juga regression tree.

Jika variabel dependen yang dimiliki bertipe kategorik maka CART menghasilkan pohon klasifikasi (classification trees). Sedangkan jika variabel dependen yang dimiliki bertipe kontinu atau numerik maka CART menghasilkan pohon regresi (regression trees).

Ø Jenis-jenis node decision tree :

Akar : merupakan node teratas, tidak ada input pada simpul ini dan tidak ada output atau bisa memiliki output lebih dari satu.
Internal node : merupakan node percabangan, hanya ada satu input dan setidaknya dua output di node ini.
Daun : merupakan node akhir atau terminal node, hanya ada satu input dan tidak ada output (simpul akhir) pada simpul ini.

Sebagai contoh suatu pohon disusun oleh simpul t₁, t₂, …, t₄ dengan rincian terdapat 3 daun, 1 akar, dan 1 internal node. Setiap pemilah (split) memilah simpul nonterminal menjadi dua simpul yang saling lepas. Hasil prediksi respon suatu amatan terdapat pada simpul terminal (daun).

Gambar 1. Pohon Keputusan

Konsep dari pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan. Pohon keputusan merupakan himpunan aturan if – then, dimana setiap path dalam pohon dihubungkan dengan sebuah aturan dimana premis terdiri atas sekumpulan node yang ditemui dan kesimpulan dari aturan terdiri atas kelas yang dihubungkan dengan daun dari path.

Ø Pembentukan pohon keputusan terdiri dari beberapa tahap :

1. Konstruksi pohon diawali dengan pembentukan akar (terletak paling atas). Kemudian data dibagi berdasarkan atribut-atribut yang cocok untuk dijadikan daun.

2. Pemangkasan pohon (tree pruning) yaitu mengidentifikasikan dan membuang cabang yang tidak diperlukan pada pohon yang telah terbentuk. Hal ini dikarenakan pohon keputusan yang dikontruksi dapat berukuran besar, maka dapat disederhanakan dengan melakukan pemangkasan berdasarkan nilai kepercayaan (confident level). Pemangkasan pohon dilakukan selain untuk pengurangan ukuran pohon juga bertujuan untuk mengurangi tingkat kesalahan prediksi pada kasus baru dari hasil pemecahan yang dilakukan dengan divide and conquer.

Pruning ada dua pendekatan yaitu :

a. Pre-pruning yaitu menghentikan pembangunan suatu subtree lebih awal (dengan memutuskan untuk tidak lebih jauh mempartisi data training). Saat seketika berhenti, maka node berubah menjadi leaf (node akhir). Node akhir ini menjadi kelas yang paling sering muncul di antara subset sampel.

b. Post-pruning yaitu menyederhanakan tree dengan cara membuang beberapa cabang subtree setelah tree selesai dibangun. Node yang jarang dipotong akan menjadi leaf (node akhir) dengan kelas yang paling sering muncul.

3. Pembentukan aturan keputusan yaitu membuat aturan keputusan dari pohon yang telah dibentuk. Aturan tersebut dapat dalam bentuk if – then diturunkan dari pohon keputusan dengan melakukan penelusuran dari akar sampai ke daun. Untuk setiap simpul dan percabangannya akan diberikan di if, sedangkan nilai pada daun akan ditulis di then. Setelah semua aturan dibuat maka aturan dapat disederhanakan atau digabung.

Pohon keputusan adalah model klasifikasi paling populer karena dapat dengan mudah ditafsirkan oleh manusia. Banyak algoritma dapat digunakan untuk membangun pohon keputusan seperti ID3, C4.5, CART, dan GUIDE.

Konsep Decision Tree :

Mengubah data menjadi pohon keputusan (decision tree) dan aturan-aturan keputusan (rule)

Data dinyatakan dalam bentuk tabel dengan atribut dan record.
Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan tree. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin dan temperatur. Salah satu atribut merupakan atribut yang menyatakan data solusi peritem data yang disebut dengan target atribut.
Atribut memiliki nilai-nilai yang dinamakan dengan instance. Misalkan atribut cuaca mempunyai instance berupa cerah, berawan dan hujan

Model Decision Tree :

Untuk memilih atribut sebagai akar, didasarkan pada nilai Gain tertinggi dari atribut-atribut yang ada. Untuk menghitung gain digunakan rumus :

Contoh pohon klasifikasi :

Contoh pohon Regresi :

Decision tree ini bisa terjadi overlap, terutama ketika kelas dan kriteria yang digunakan sangat banyak tentu saja dapat meningkatkan waktu pengambilan keputusan sesuai dengan jumlah memori yang dibutuhkan.

Dalam hal akumulasi, decision tree juga seringkali mengalami kendala eror terutama dalam jumlah besar. Selain itu, terdapat pula kesulitan dalam mendesain decision tree yang optimal. Apalagi mengingat kualitas keputusan yang didapatkan dari metode decision tree sangat tergantung pada bagaimana pohon tersebut didesain. Maka dibutuhkan Random Forest untuk mengatasi overlap di atas

Ø Manfaat Decision Tree

Decision tree juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Pohon keputusan menggabungkan eksplorasi data dan pemodelan yang menjadikannya langkah pertama yang sangat baik dalam proses pemodelan bahkan ketika digunakan sebagai model akhir untuk beberapa teknik lainnya.

Dalam beberapa aplikasi, akurasi dari sebuah klasifikasi atau prediksi adalah satu-satunya hal yang ditonjolkan dalam metode ini, Misalnya perusahaan surat langsung membuat model yang akurat untuk memprediksi anggota mana yang berpotensi merespons permintaan terlepas dari bagaimana atau mengapa model itu berfungsi.

Kelebihan lain dari metode ini adalah mampu mengeliminasi perhitungan atau data-data yang kiranya tidak diperlukan. Karena sampel yang ada biasanya hanya diuji berdasarkan kriteria atau kelas tertentu.

Meski memiliki banyak kelebihan, namun bukan berarti metode ini tidak memiliki kekurangan. Pohon keputusan ini mungkin tumpang tindih, terutama jika kelas dan kriteria yang digunakan sangat sering dapat meningkatkan waktu pengambilan keputusan sesuai dengan kapasitas memori yang diperlukan.

Ø Kelebihan Descion Tree:

Integrasi yang mudah ke dalam sistem basis data.
Memiliki akurasi yang baik.
Dapat menemukan kombinasi data yang tidak terduga.
Area keputusan yang sebelumnya kompleks dan sangat global dapat dibuat lebih sederhana dan lebih spesifik.
Dapat menghilangkan perhitungan yang tidak diperlukan. Karena dengan metode ini, sampel hanya diuji berdasarkan kriteria atau kelas tertentu.
Dengan pemilihan fitur yang fleksibel dari node internal yang berbeda, fitur yang dipilih membedakan kriteria dari kriteria lain di node yang sama.

Ø Kekurangan Descion Tree:

Tumpang tindih terjadi terutama ketika sangat banyak kelas dan kriteria digunakan. Ini juga dapat menyebabkan waktu keputusan yang lebih lama dan memori yang dibutuhkan.
Akumulasi jumlah kesalahan dari setiap level dalam pohon keputusan besar.
Kesulitan dalam merancang pohon keputusan yang optimal.
Hasil kualitas keputusan yang diperoleh dengan metode pohon keputusan sangat tergantung pada bagaimana pohon itu dirancang.

Ø Decision Tree Terdiri dari Tiga Jenis Simpul :

Simpul keputusan – biasanya diwakili oleh kotak
Simpul peluang – biasanya diwakili oleh lingkaran
Simpul akhir – biasanya diwakili oleh segitiga

Ø Penerapan Decision Tree :

Decision tree atau pohon keputusan adalah alat pendukung keputusan yang menggunakan model keputusan yang berbentuk seperti pohon. Pohon keputusan menggambarkan berbagai alternatif yang mungkin untuk mengatasi suatu masalah dan ada juga faktor-faktor potensial yang dapat memengaruhi alternatif tersebut bersama dengan perkiraan akhirnya ketika suatu alternatif dipilih. Pohon keputusan adalah metode yang dapat digunakan untuk menampilkan algoritma yang hanya berisi pernyataan kontrol bersyarat.

Penggunaan Decision tree ini umunya dalam riset operasi, khususnya dalam analisis keputusan. Tujuan menggunakan pohon keputusan adalah untuk mengidentifikasi strategi yang paling mungkin untuk mencapai tujuan dan merupakan alat yang populer dalam pembelajaran mesin.

Contoh Soal Klasifikasi Dalam Data Mining :

Di bawah ini adalah tabel yang berisi training data dari database karyawan. Data ini sudah di-geralisasi-kan. Misalnya, “31…35” untuk usia berarti kisaran usia antara 31 hingga 35. Khusus untuk kolom "jumlah", itu menunjukkan jumlah tuples dari masing-masing data pada department, status, usia, dan gaji pada baris yang dimaksud department status usia gaji jumlah

sales               senior   31. . . 35 46K. . . 50K        30
sales               junior   26. . . 30 26K. . . 30K        40
sales               junior   31. . . 35 31K. . . 35K        40
systems   junior   21. . . 25 46K. . . 50K        20
systems   senior   31. . . 35 66K. . . 70K        5
systems   junior   26. . . 30   46K. . . 50K       3
systems   senior   41. . . 45 66K. . . 70K        3
marketing senior   36. . . 40 46K. . . 50K       10
marketing junior 31. . . 35    41K. . . 45K       4
secretary senior   46. . . 50 36K. . . 40K        4
secretary junior   26. . . 30 26K. . . 30K        6

Atribut yang menjadi class label adalah atribut "status".

1. Buatlah decision tree menurut teknik anda !

Jawaban:

Catatan:

Setelah menemukan atribut yang terpilih menjadi node 'root', node atau simpul yang kedua, ketiga, dst (node yang bukan menjadi bukan root), seharusnya dihitung lagi atau dihitung ulang menggunakan Information Gain (atau Gain Ratio atau Gini Index atau teknik yang lainnya) untuk menentukan atribut mana yang akan menjadi node berikutnya. Dalam contoh diatas node 'usia' ditentukan tanpa menghitung dan hanya dengan teknik coba-coba/arbitrary saja karena jumlah tuple data dan atribut yang tersisa hanya sedikit sehingga dengan metode 'coba-coba' tidak terlalu sulit. Meskipun atribut 'department' juga bisa menjadi alternatif untuk dipilih menjadi node tersebut dengan hasil yang sama-sama benar. Karena kasus di atas adalah contoh belaka dengan jumlah atribut dan tuple yang tidak banyak maka metode 'coba-coba' untuk pemilihan node kedua di atas hanya untuk memberikan ilustrasi solusi dari kasus di atas. Tetapi untuk node 'root' adalah tetap berdasarkan hitungan information gain. Tetapi kasus di dunia nyata tidak mungkin menggunakan teknik 'coba-coba' karena jumlah atribut dan/atau data tuple akan sangat banyak (tuple bisa berisi jutaan baris data). Beruntungnya software untuk aplikasi data mining akan menentukan pemilihan node secara otomatis sesuai dengan teknik yang kita pilih.

Berikut di bawah adalah contoh capture decision tree alternatif yang dihasilkan dengan software rapidminer dengan menerapkan 'pre-pruning':