Apa itu Decision Tree?

Apa itu Decision Tree?

Decision tree adalah algoritma machine learning yang berguna untuk tugas regresi dan klasifikasi. Nama “decision tree” berasal dari fakta bahwa algoritma ini terus membagi dataset menjadi bagian-bagian yang lebih kecil dan lebih kecil sampai data dibagi menjadi contoh-contoh tunggal, yang kemudian diklasifikasikan. Jika Anda memvisualisasikan hasil algoritma, cara kategori dibagi akan menyerupai pohon dan banyak daun.

Itu adalah definisi singkat tentang decision tree, tetapi mari kita menyelami lebih dalam tentang bagaimana decision tree bekerja. Memahami bagaimana decision tree beroperasi, serta kasus penggunaannya, akan membantu Anda mengetahui kapan harus menggunakannya dalam proyek machine learning Anda.

Format dari Decision Tree

Decision tree mirip dengan flowchart. Untuk menggunakan flowchart, Anda memulai dari titik awal, atau root, dari chart dan kemudian berdasarkan bagaimana Anda menjawab kriteria penyaringan dari node awal, Anda bergerak ke salah satu node berikutnya. Proses ini diulangi sampai akhir dicapai.

Decision tree beroperasi dengan cara yang sama, dengan setiap node internal dalam pohon menjadi beberapa jenis tes atau kriteria penyaringan. Node di luar, yaitu titik akhir dari pohon, adalah label untuk datapoint yang bersangkutan dan mereka disebut “daun”. Cabang yang menghubungkan node internal ke node berikutnya adalah fitur atau konjungsi dari fitur. Aturan yang digunakan untuk mengklasifikasikan datapoint adalah jalur yang berjalan dari root ke daun.

Algoritma untuk Decision Tree

Decision tree beroperasi pada pendekatan algoritma yang membagi dataset menjadi titik data individual berdasarkan kriteria yang berbeda. Pemisahan ini dilakukan dengan variabel yang berbeda, atau fitur yang berbeda dari dataset. Misalnya, jika tujuan adalah menentukan apakah seekor anjing atau kucing yang sedang digambarkan oleh fitur input, variabel yang digunakan untuk membagi data mungkin seperti “cakar” dan “menggonggong”.

Jadi, apa algoritma yang digunakan untuk membagi data menjadi cabang dan daun? Ada beberapa metode yang dapat digunakan untuk membagi pohon, tetapi metode pemisahan yang paling umum adalah teknik yang disebut “recursive binary split“. Ketika melakukan metode pemisahan ini, proses dimulai dari root dan jumlah fitur dalam dataset mewakili jumlah pemisahan yang mungkin. Fungsi digunakan untuk menentukan seberapa besar akurasi setiap pemisahan yang mungkin, dan pemisahan dilakukan menggunakan kriteria yang mengorbankan akurasi yang paling sedikit. Proses ini diulangi secara rekursif dan sub-grup dibentuk menggunakan strategi yang sama.

Untuk menentukan biaya pemisahan, fungsi biaya digunakan. Fungsi biaya yang berbeda digunakan untuk tugas regresi dan klasifikasi. Tujuan dari kedua fungsi biaya adalah menentukan cabang mana yang memiliki nilai respons yang paling seragam, atau cabang yang paling homogen. Pertimbangkan bahwa Anda ingin data tes dari kelas tertentu mengikuti jalur tertentu dan ini memiliki makna intuitif.

Dalam hal fungsi biaya regresi untuk recursive binary split, algoritma yang digunakan untuk menghitung biaya adalah sebagai berikut:

sum(y – prediksi)^2

Prediksi untuk sekelompok datapoint adalah mean dari respon data pelatihan untuk kelompok tersebut. Semua datapoint dijalankan melalui fungsi biaya untuk menentukan biaya untuk semua pemisahan yang mungkin dan pemisahan dengan biaya terendah dipilih.

Mengenai fungsi biaya untuk klasifikasi, fungsi adalah sebagai berikut:

G = sum(pk * (1 – pk))

Ini adalah skor Gini, dan ini adalah pengukuran efektivitas pemisahan, berdasarkan seberapa banyak contoh dari kelas yang berbeda yang ada dalam kelompok yang dihasilkan dari pemisahan. Dengan kata lain, ini mengukur seberapa campur aduk kelompok setelah pemisahan. Pemisahan yang optimal adalah ketika semua kelompok yang dihasilkan dari pemisahan hanya terdiri dari input dari satu kelas. Jika pemisahan yang optimal telah dibuat, nilai “pk” akan menjadi 0 atau 1 dan G akan sama dengan 0. Anda mungkin dapat menebak bahwa pemisahan yang terburuk adalah ketika ada representasi 50-50 dari kelas dalam pemisahan, dalam kasus klasifikasi biner. Dalam hal ini, nilai “pk” akan menjadi 0,5 dan G juga akan menjadi 0,5.

Proses pemisahan dihentikan ketika semua datapoint telah diubah menjadi daun dan diklasifikasikan. Namun, Anda mungkin ingin menghentikan pertumbuhan pohon lebih awal. Pohon yang besar dan kompleks rentan terhadap overfitting, tetapi beberapa metode yang berbeda dapat digunakan untuk mengatasi ini. Salah satu metode untuk mengurangi overfitting adalah dengan menentukan jumlah minimum datapoint yang akan digunakan untuk membuat daun. Metode lain untuk mengontrol overfitting adalah membatasi pohon ke kedalaman maksimum tertentu, yang mengontrol seberapa panjang jalur dapat membentang dari root ke daun.

Proses lain yang terlibat dalam pembuatan decision tree adalah pruning. Pruning dapat membantu meningkatkan kinerja decision tree dengan menghilangkan cabang yang mengandung fitur yang memiliki sedikit kekuatan prediktif/sedikit penting untuk model. Dengan cara ini, kompleksitas pohon berkurang, menjadi kurang rentan terhadap overfitting, dan utilitas prediktif model meningkat.

Ketika melakukan pruning, proses dapat dimulai dari atas pohon atau bawah pohon. Namun, metode pruning yang paling mudah adalah dengan memulai dari daun dan mencoba menghilangkan node yang mengandung kelas yang paling umum dalam daun tersebut. Jika akurasi model tidak memburuk ketika ini dilakukan, maka perubahan tersebut dipertahankan. Ada teknik lain yang digunakan untuk melakukan pruning, tetapi metode yang dijelaskan di atas – reduced error pruning – adalah metode pruning decision tree yang paling umum.

Pertimbangan untuk Menggunakan Decision Tree

Decision tree sering berguna ketika klasifikasi perlu dilakukan tetapi waktu komputasi adalah kendala utama. Decision tree dapat membuatnya jelas mana fitur dalam dataset yang dipilih memiliki kekuatan prediktif yang paling besar. Selain itu, tidak seperti banyak algoritma machine learning di mana aturan yang digunakan untuk mengklasifikasikan data mungkin sulit diinterpretasikan, decision tree dapat menghasilkan aturan yang dapat diinterpretasikan. Decision tree juga dapat menggunakan variabel kategorik dan kontinu, yang berarti bahwa praproses yang lebih sedikit diperlukan, dibandingkan dengan algoritma yang hanya dapat menangani salah satu jenis variabel ini.

Decision tree cenderung tidak berkinerja baik ketika digunakan untuk menentukan nilai atribut kontinu. Keterbatasan lain dari decision tree adalah bahwa, ketika melakukan klasifikasi, jika ada sedikit contoh pelatihan tetapi banyak kelas, decision tree cenderung tidak akurat.