Apa itu Pohon Keputusan?

Apa itu Pohon Keputusan?

A pohon keputusan adalah algoritma pembelajaran mesin yang berguna yang digunakan untuk tugas regresi dan klasifikasi. Nama “pohon keputusan” berasal dari fakta bahwa algoritme terus membagi kumpulan data menjadi bagian-bagian yang lebih kecil hingga data tersebut dibagi menjadi beberapa contoh, yang kemudian diklasifikasikan. Jika Anda memvisualisasikan hasil algoritme, cara pembagian kategori akan menyerupai pohon dan banyak daun.

Itu definisi singkat dari pohon keputusan, tapi mari selami lebih dalam bagaimana pohon keputusan bekerja. Memiliki pemahaman yang lebih baik tentang bagaimana pohon keputusan beroperasi, serta kasus penggunaannya, akan membantu Anda mengetahui kapan menggunakannya selama proyek pembelajaran mesin Anda.

Format Pohon Keputusan

Pohon keputusan adalah sangat mirip dengan diagram alur. Untuk menggunakan bagan alur, Anda mulai dari titik awal, atau akar, bagan, lalu berdasarkan cara Anda menjawab kriteria pemfilteran dari simpul awal tersebut, Anda berpindah ke salah satu simpul berikutnya yang memungkinkan. Proses ini diulang sampai akhir tercapai.

Pohon keputusan pada dasarnya beroperasi dengan cara yang sama, dengan setiap simpul internal di pohon menjadi semacam kriteria pengujian/penyaringan. Node di bagian luar, titik akhir pohon, adalah label untuk titik data yang dimaksud dan dijuluki "daun". Cabang-cabang yang mengarah dari node internal ke node berikutnya adalah fitur atau konjungsi fitur. Aturan yang digunakan untuk mengklasifikasikan titik data adalah jalur yang berjalan dari akar ke daun.

Algoritma untuk Pohon Keputusan

Pohon keputusan beroperasi pada pendekatan algoritmik yang membagi kumpulan data menjadi titik data individual berdasarkan kriteria yang berbeda. Pemisahan ini dilakukan dengan variabel yang berbeda, atau fitur yang berbeda dari kumpulan data. Misalnya, jika tujuannya adalah untuk menentukan apakah seekor anjing atau kucing dideskripsikan oleh fitur masukan atau tidak, variabel yang membagi data mungkin seperti "cakar" dan "gonggongan".

Jadi algoritma apa yang digunakan untuk membagi data menjadi cabang dan daun? Ada berbagai metode yang dapat digunakan untuk membelah pohon, tetapi metode pemisahan yang paling umum mungkin adalah teknik yang disebut sebagai “pemisahan biner rekursif”. Saat melakukan metode pemisahan ini, proses dimulai dari akar dan jumlah fitur dalam kumpulan data mewakili kemungkinan jumlah kemungkinan pemisahan. Sebuah fungsi digunakan untuk menentukan berapa banyak akurasi yang akan dikenakan biaya setiap kemungkinan pemisahan, dan pemisahan dibuat menggunakan kriteria yang mengorbankan akurasi paling rendah. Proses ini dilakukan secara rekursif dan sub-kelompok dibentuk dengan menggunakan strategi umum yang sama.

Agar menentukan biaya pemisahan, digunakan fungsi biaya. Fungsi biaya yang berbeda digunakan untuk tugas regresi dan tugas klasifikasi. Tujuan dari kedua fungsi biaya tersebut adalah untuk menentukan cabang mana yang memiliki nilai respon yang paling mirip, atau cabang yang paling homogen. Pertimbangkan bahwa Anda ingin data uji dari kelas tertentu mengikuti jalur tertentu dan ini masuk akal secara intuitif.

Dalam hal fungsi biaya regresi untuk pemisahan biner rekursif, algoritma yang digunakan untuk menghitung biaya adalah sebagai berikut:

jumlah(y – prediksi)^2

Prediksi untuk kelompok titik data tertentu adalah rata-rata dari respons data pelatihan untuk kelompok tersebut. Semua titik data dijalankan melalui fungsi biaya untuk menentukan biaya untuk semua kemungkinan pemisahan dan pemisahan dengan biaya terendah dipilih.

Mengenai fungsi biaya untuk klasifikasi, fungsinya adalah sebagai berikut:

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

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

Proses pemisahan diakhiri ketika semua titik data telah berubah menjadi daun dan diklasifikasikan. Namun, Anda mungkin ingin menghentikan pertumbuhan pohon lebih awal. Pohon besar yang kompleks rentan terhadap overfitting, tetapi beberapa metode berbeda dapat digunakan untuk mengatasi hal ini. Salah satu metode untuk mengurangi overfitting adalah dengan menentukan jumlah minimal titik data yang akan digunakan untuk membuat sebuah daun. Metode lain untuk mengontrol overfitting adalah membatasi pohon ke kedalaman maksimum tertentu, yang mengontrol berapa lama jalur dapat direntangkan dari akar ke daun.

Proses lain yang terlibat dalam pembuatan pohon keputusan sedang memangkas. Pemangkasan dapat membantu meningkatkan kinerja pohon keputusan dengan menghapus cabang yang berisi fitur yang memiliki sedikit kekuatan prediktif/kurang penting untuk model. Dengan cara ini, kompleksitas pohon berkurang, kemungkinan overfit menjadi lebih kecil, dan utilitas prediktif model meningkat.

Saat melakukan pemangkasan, prosesnya bisa dimulai dari bagian atas pohon atau bagian bawah pohon. Namun, metode pruning yang paling mudah adalah memulai dengan daun dan mencoba membuang simpul yang berisi kelas paling umum di dalam daun itu. Jika keakuratan model tidak menurun saat ini dilakukan, maka perubahan tersebut dipertahankan. Ada teknik lain yang digunakan untuk melakukan pemangkasan, tetapi metode yang dijelaskan di atas – pengurangan kesalahan pemangkasan – mungkin merupakan metode pemangkasan pohon keputusan yang paling umum.

Pertimbangan Untuk Menggunakan Pohon Keputusan

Pohon keputusan sering berguna ketika klasifikasi perlu dilakukan tetapi waktu perhitungan merupakan kendala utama. Pohon keputusan dapat memperjelas fitur mana dalam kumpulan data yang dipilih yang memiliki kekuatan paling prediktif. Selain itu, tidak seperti kebanyakan algoritme pembelajaran mesin di mana aturan yang digunakan untuk mengklasifikasikan data mungkin sulit untuk ditafsirkan, pohon keputusan dapat membuat aturan yang dapat ditafsirkan. Pohon keputusan juga dapat menggunakan variabel kategorikal dan kontinyu yang berarti lebih sedikit prapemrosesan yang diperlukan, dibandingkan dengan algoritme yang hanya dapat menangani salah satu dari jenis variabel ini.

Pohon keputusan cenderung tidak bekerja dengan baik bila digunakan untuk menentukan nilai atribut kontinu. Keterbatasan lain dari pohon keputusan adalah ketika melakukan klasifikasi, jika contoh pelatihan sedikit tetapi banyak kelas, pohon keputusan cenderung tidak akurat.