Apa itu decision tree?

Seperti yang dapat Anda lihat dari diagram di bawah ini, decision trees dimulai dengan node akar, yang tidak memiliki cabang yang masuk. Cabang keluar dari node root kemudian dimasukkan ke dalam node internal, juga dikenal sebagai node keputusan. Berdasarkan fitur-fitur yang tersedia, kedua tipe node melakukan evaluasi untuk membentuk himpunan bagian yang homogen, yang dilambangkan dengan node daun, atau node terminal. Node daun mewakili semua kemungkinan hasil dalam kumpulan data.

Sebagai contoh, bayangkan Anda sedang mencoba menilai apakah Anda harus berselancar atau tidak, Anda dapat menggunakan aturan keputusan berikut ini untuk membuat pilihan:

Jenis struktur diagram alur ini juga menciptakan representasi pengambilan keputusan yang mudah dicerna, sehingga memungkinkan berbagai kelompok di seluruh organisasi untuk lebih memahami mengapa suatu keputusan dibuat.

Pembelajaran decision trees menggunakan strategi memecah belah dan menaklukkan dengan melakukan pencarian yang rakus untuk mengidentifikasi titik-titik perpecahan yang optimal di dalam pohon. Proses pemisahan ini kemudian diulangi secara rekursif dari atas ke bawah hingga semua, atau sebagian besar, catatan telah diklasifikasikan di bawah label kelas tertentu.

Apakah semua titik data diklasifikasikan sebagai himpunan homogen atau tidak sangat tergantung pada kompleksitas decision trees. Pohon yang lebih kecil lebih mudah mencapai node daun murni—yaitu titik data dalam satu kelas. Namun, seiring dengan bertambahnya ukuran pohon, akan semakin sulit untuk mempertahankan kemurnian ini, dan biasanya menghasilkan terlalu sedikit data yang jatuh dalam sub-pohon tertentu. Ketika hal ini terjadi, ini dikenal sebagai fragmentasi data, dan sering kali dapat menyebabkan overfitting.

Hasilnya, decision trees memiliki preferensi untuk pohon-pohon kecil, yang konsisten dengan prinsip kesederhanaan dalam Occam's Razor, yaitu "entitas tidak boleh diperbanyak melebihi kebutuhan". Dengan kata lain, decision trees harus menambah kompleksitas hanya jika perlu, karena penjelasan paling sederhana seringkali yang terbaik. Untuk mengurangi kerumitan dan mencegah overfitting, biasanya dilakukan pemangkasan; ini adalah proses menghilangkan cabang-cabang yang terpecah pada fitur-fitur yang tidak terlalu penting. Kesesuaian model kemudian dapat dievaluasi melalui proses validasi silang.

Cara lain agar decision trees dapat mempertahankan akurasinya adalah dengan membentuk ansambel melalui algoritma hutan acak; pengklasifikasi ini memprediksi hasil yang lebih akurat, terutama ketika pohon individu tidak berkorelasi satu sama lain.

Algoritma Hunt, yang dikembangkan pada tahun 1960-an untuk memodelkan pembelajaran manusia di bidang Psikologi, menjadi dasar dari banyak algoritma decision trees yang populer, seperti yang berikut ini:

- ID3: Ross Quinlan dikreditkan dalam pengembangan ID3, yang merupakan singkatan dari 'Iterative Dichotomiser 3'. Algoritma ini memanfaatkan entropi dan perolehan informasi sebagai metrik untuk mengevaluasi pemisahan kandidat. Beberapa penelitian Quinlan tentang algoritma ini dari tahun 1986 dapat ditemukan di sini.

- C4.5: Algoritma ini dianggap sebagai pengulangan terbaru ID3, yang juga dikembangkan oleh Quinlan. Ini dapat menggunakan perolehan informasi atau rasio perolehan untuk mengevaluasi titik-titik pembagian dalam decision trees.

- CART: Istilah CART merupakan singkatan dari “classification and regression trees (pohon klasifikasi dan regresi)” dan diperkenalkan oleh Leo Breiman. Algoritma ini biasanya memanfaatkan ketidakmurnian Gini untuk mengidentifikasi atribut ideal untuk dipecah. Ketidakmurnian Gini mengukur seberapa sering atribut yang dipilih secara acak salah diklasifikasikan. Saat mengevaluasi menggunakan ketidakmurnian Gini, nilai yang lebih rendah lebih ideal.

Meskipun ada beberapa cara untuk memilih atribut terbaik di setiap node, dua metode, perolehan informasi dan Gini impurity, bertindak sebagai kriteria pemisahan yang populer untuk model decision trees. Mereka membantu untuk mengevaluasi kualitas setiap kondisi pengujian dan seberapa baik ia dapat mengklasifikasikan sampel ke dalam kelas.

Sulit untuk menjelaskan perolehan informasi tanpa terlebih dahulu membahas entropi. Entropi adalah konsep yang berasal dari teori informasi, yang mengukur ketidakmurnian nilai sampel. Hal ini didefinisikan dengan rumus berikut, di mana:

• S mewakili kumpulan data yang dihitung entropi 
• c mewakili kelas dalam set, S
• p(c) mewakili proporsi titik data yang termasuk dalam kelas c terhadap jumlah total titik data dalam himpunan, S

Nilai entropi dapat berada antara 0 dan 1. Jika semua sampel dalam kumpulan data, S, termasuk dalam satu kelas, maka entropi akan sama dengan nol. Jika setengah dari sampel diklasifikasikan sebagai satu kelas dan setengah lainnya berada di kelas lain, entropi akan mencapai nilai tertinggi di 1. Untuk memilih fitur terbaik untuk dibagi dan menemukan pohon keputusan yang optimal, atribut dengan jumlah entropi terkecil harus digunakan.

Perolehan informasi mewakili perbedaan entropi sebelum dan sesudah pemisahan pada atribut tertentu. Atribut dengan perolehan informasi tertinggi akan menghasilkan pemisahan terbaik karena atribut ini melakukan pekerjaan terbaik dalam mengklasifikasikan data pelatihan sesuai dengan klasifikasi target. Perolehan informasi biasanya direpresentasikan dengan rumus berikut,

di mana

• a mewakili atribut tertentu atau label kelas
• Entropy(S) adalah entropi dari kumpulan data, S
• |Sv|/|S| mewakili proporsi nilai dalam S_v dengan jumlah nilai dalam kumpulan data, S.

Mari kita lihat contoh untuk memperkuat konsep ini. Bayangkan kita memiliki kumpulan data acak berikut ini:

Untuk kumpulan data ini, entropinya adalah 0,94. Hal ini dapat dihitung dengan mencari proporsi hari di mana 'Bermain Tenis' adalah 'Ya', yaitu 9/14, dan proporsi hari di mana 'Bermain Tenis' adalah 'Tidak', yaitu 5/14. Kemudian, nilai-nilai ini dapat dicolokkan ke rumus entropi di atas.

Entropi (Tenis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

Kita kemudian dapat menghitung perolehan informasi untuk masing-masing atribut secara individual. Misalnya, perolehan informasi untuk atribut, 'Kelembaban' adalah sebagai berikut:

Perolehan (Tenis, Kelembaban) = (0,94)-(7/14)*(0,985) – (7/14)*(0.592) = 0,151

Sebagai rekap,

- 7/14 merupakan proporsi nilai yang kelembapannya sama dengan 'tinggi' terhadap jumlah total nilai kelembapan. Dalam kasus ini, jumlah nilai di mana kelembapan sama dengan 'tinggi' sama dengan jumlah nilai di mana kelembapan sama dengan 'normal'.

- 0,985 adalah entropi ketika Kelembaban = 'tinggi'

- 0,59 adalah entropi ketika Kelembaban = 'normal'

Kemudian, ulangi perhitungan perolehan informasi untuk setiap atribut pada tabel di atas, dan pilih atribut dengan perolehan informasi tertinggi untuk menjadi titik pemisah pertama dalam decision trees. Dalam hal ini, outlook menghasilkan perolehan informasi tertinggi. Dari sana, proses tersebut dicapai untuk setiap subpohon.

Gini impurity adalah probabilitas kesalahan mengklasifikasikan titik data acak dalam kumpulan data jika dilabeli berdasarkan distribusi kelas kumpulan data. Mirip dengan entropi, jika set, S, adalah murni—yaitu milik satu kelas) maka, ketidakmurnian adalah nol. Ini ditandai dengan rumus berikut:

Meskipun decision trees dapat digunakan dalam berbagai contoh penggunaan, algoritma lain biasanya mengungguli algoritma decision trees. Meski begitu, decision trees sangat berguna untuk tugas penambangan data dan penemuan pengetahuan. Mari kita bahas lebih lanjut manfaat utama dan tantangan dalam memanfaatkan decision trees di bawah ini:

• Mudah dipahami: Logika Boolean dan representasi visual decision trees membuatnya lebih mudah dipahami dan digunakan. Sifat hierarkis dari decision trees juga memudahkan untuk melihat atribut mana yang paling penting, yang tidak selalu jelas dengan algoritma lain, seperti neural networks.
  
  
• Sedikit atau bahkan tidak diperlukan persiapan data: Decision trees memiliki beberapa karakteristik yang membuatnya lebih fleksibel daripada pengklasifikasi lainnya. Ini dapat menangani berbagai jenis data—mis. nilai diskrit atau kontinu, dan nilai kontinu dapat dikonversi menjadi nilai kategorikal melalui penggunaan ambang batas. Selain itu, ia juga dapat menangani nilai dengan missing values (nilai yang hilang), yang dapat menjadi masalah bagi pengklasifikasi lain, seperti Naïve Bayes.
  
  
• Lebih fleksibel: Decision trees dapat dimanfaatkan untuk tugas klasifikasi dan regresi, sehingga membuatnya lebih fleksibel daripada beberapa algoritma lainnya. Algoritma ini juga tidak memperhatikan hubungan yang berada di bawah permukaan antara atribut; hal ini berarti bahwa jika dua variabel memiliki hubungan yang sangat erat, maka algoritma hanya akan memilih satu fitur saja untuk dibagi.

• Cenderung overfitting: Decision trees yang kompleks cenderung overfitting dan tidak dapat digeneralisasi dengan baik untuk data baru. Skenario ini dapat dihindari melalui proses pra-pemangkasan atau pasca-pemangkasan. Pra-pemangkasan menghentikan pertumbuhan pohon jika data yang tersedia tidak mencukupi, sementara pasca-pemangkasan menghilangkan subpohon dengan data yang tidak memadai setelah konstruksi pohon.
  
  
• Estimator varians tinggi: Variasi kecil dalam data dapat menghasilkan decision trees yang sangat berbeda. Bagging, atau rata-rata perkiraan, dapat menjadi metode untuk mengurangi varians decision trees. Namun, pendekatan ini terbatas karena dapat menyebabkan prediktor yang sangat berkorelasi.
  
  
• Lebih mahal: Karena Decision Trees menggunakan pendekatan pencarian agresif (greedy search) selama proses konstruksi, maka Decision Trees dapat menjadi lebih mahal untuk dilatih dibandingkan dengan algoritma lainnya.