Lihat sumber Algoritma: Pohon Keputusan (Decision Tree)

'''Pohon keputusan''' atau '''''decision tree''''' adalah salah satu metode dalam [[pembelajaran mesin]] dan [[statistika]] yang digunakan untuk melakukan [[klasifikasi]] atau [[regresi]]. Struktur pohon keputusan menyerupai diagram bercabang, di mana setiap simpul internal merepresentasikan suatu pengujian terhadap atribut, setiap cabang merepresentasikan hasil dari pengujian tersebut, dan setiap simpul daun merepresentasikan label kelas atau nilai output. Metode ini populer karena mudah dipahami secara visual dan relatif sederhana untuk diimplementasikan.  

== Konsep dan Struktur ==  
Secara umum, pohon keputusan terdiri dari '''simpul akar''', simpul internal, dan simpul daun. Simpul akar merupakan titik awal pohon yang memuat keseluruhan dataset. Setiap simpul internal memuat suatu tes terhadap atribut tertentu, sedangkan simpul daun menyajikan hasil akhir berupa prediksi atau keputusan. Pohon keputusan bekerja dengan membagi data ke dalam subset berdasarkan nilai atribut, secara rekursif hingga mencapai kondisi berhenti.  

Struktur pohon keputusan dapat direpresentasikan sebagai himpunan aturan berbentuk ''if-then''. Proses ini memungkinkan model untuk menangkap hubungan non-linear antara variabel input dan output. Dalam [[ilmu komputer]], pohon keputusan juga digunakan dalam desain algoritma pencarian dan dalam sistem berbasis aturan.  

== Proses Pembentukan Pohon ==  
Pembentukan pohon keputusan umumnya dilakukan melalui algoritma seperti [[ID3]], [[C4.5]], atau [[CART]]. Algoritma ini menggunakan ukuran tertentu untuk memilih atribut terbaik pada setiap percabangan. Salah satu ukuran yang paling umum digunakan adalah '''information gain''' yang didasarkan pada konsep [[entropi]].  

Rumus entropi dapat dituliskan sebagai:  
<math>H(S) = - \sum_{i=1}^{n} p_i \log_2 p_i</math>  
di mana <math>p_i</math> adalah probabilitas kemunculan kelas ke-''i'' dalam himpunan data <math>S</math>.  

== Kriteria Pemilihan Atribut ==  
Beberapa kriteria yang digunakan untuk memilih atribut terbaik antara lain:  
# '''Information Gain''' – Mengukur pengurangan entropi setelah pembagian data berdasarkan atribut.  
# '''Gain Ratio''' – Memperbaiki kelemahan information gain yang bias terhadap atribut dengan banyak nilai.  
# '''Gini Index''' – Digunakan dalam algoritma CART untuk mengukur ketidakmurnian data.  

Kriteria ini membantu pohon keputusan untuk memilih atribut yang paling informatif pada setiap percabangan, sehingga struktur pohon menjadi optimal.  

== Pemangkasan Pohon ==  
Proses pemangkasan (''pruning'') dilakukan untuk mengurangi kompleksitas pohon yang terbentuk dan mencegah [[overfitting]]. Pemangkasan dapat dilakukan secara '''pre-pruning''' (menghentikan pertumbuhan pohon lebih awal) atau '''post-pruning''' (menghapus cabang yang tidak signifikan setelah pohon terbentuk).  

Metode pemangkasan mempertahankan generalisasi model sehingga dapat bekerja lebih baik pada data baru. Dalam praktik, pengaturan parameter seperti kedalaman maksimum pohon atau jumlah minimum sampel pada simpul daun digunakan untuk mengendalikan ukuran pohon.  

== Kelebihan dan Kekurangan ==  
Kelebihan pohon keputusan antara lain:  
# Mudah dipahami dan diinterpretasikan.  
# Dapat menangani data numerik maupun kategorikal.  
# Memerlukan sedikit praproses data.  

Kekurangannya meliputi:  
# Rentan terhadap [[overfitting]] jika tidak dipangkas dengan tepat.  
# Dapat menghasilkan pohon yang kompleks jika data memiliki banyak atribut.  
# Sensitif terhadap perubahan kecil pada data yang dapat mengubah struktur pohon secara signifikan.  

== Penerapan dalam Dunia Nyata ==  
Pohon keputusan banyak digunakan dalam berbagai bidang, seperti:  
# [[Analisis kredit]] untuk memutuskan kelayakan pinjaman.  
# [[Kedokteran]] untuk membantu diagnosis penyakit berdasarkan gejala pasien.  
# [[Sistem pakar]] yang memberikan rekomendasi atau keputusan otomatis berdasarkan data masukan.  

Dalam [[data mining]], pohon keputusan menjadi salah satu teknik populer karena kemampuannya dalam menangani dataset besar dan menghasilkan aturan yang mudah dipahami.  

== Pohon Keputusan dalam Regresi ==  
Selain untuk klasifikasi, pohon keputusan juga dapat digunakan untuk [[regresi]], di mana simpul daun berisi nilai numerik. Proses pemilihan atribut pada regresi decision tree menggunakan kriteria seperti minimisasi varians.  

Persamaan varians untuk himpunan data <math>S</math> dapat dituliskan sebagai:  
<math>\sigma^2 = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2</math>  
di mana <math>y_i</math> adalah nilai aktual dan <math>\bar{y}</math> adalah nilai rata-rata.  

== Hubungan dengan Metode Ensembel ==  
Pohon keputusan sering digunakan sebagai komponen dasar dalam metode [[ensembel]] seperti [[Random Forest]] atau [[Gradient Boosting]]. Dalam metode ini, banyak pohon dibangun dan hasilnya digabungkan untuk meningkatkan akurasi prediksi.  

Random Forest misalnya, menggunakan teknik ''bagging'' untuk membuat kumpulan pohon yang dilatih pada subset data acak. Hal ini mengurangi varians dan meningkatkan kemampuan generalisasi.  

== Kompleksitas dan Efisiensi ==  
Kompleksitas pohon keputusan bergantung pada jumlah atribut dan kedalaman pohon. Waktu komputasi untuk membangun pohon umumnya adalah <math>O(n \log n)</math> untuk n sampel jika menggunakan teknik pemilihan atribut yang efisien.  

Optimisasi struktur pohon sering dilakukan untuk menangani dataset besar, seperti menggunakan algoritma pemilihan atribut berbasis heuristik atau [[parallel computing]].  

== Representasi dan Visualisasi ==  
Pohon keputusan dapat direpresentasikan dalam bentuk grafik bercabang yang memudahkan interpretasi. Visualisasi ini sering digunakan dalam analisis data untuk menjelaskan proses pengambilan keputusan kepada pihak non-teknis.  

Beberapa perangkat lunak seperti [[scikit-learn]], [[R (bahasa pemrograman)|R]], dan [[WEKA]] menyediakan fungsi untuk membangun dan memvisualisasikan pohon keputusan secara interaktif.  

== Kesimpulan ==  
Pohon keputusan merupakan alat yang kuat dan fleksibel dalam analisis data, baik untuk klasifikasi maupun regresi. Kemampuannya untuk menghasilkan model yang mudah diinterpretasikan menjadikannya pilihan populer dalam berbagai aplikasi.  

Meski demikian, penggunaannya perlu disertai teknik pemangkasan dan, jika perlu, integrasi dengan metode ensembel untuk mengatasi kelemahan seperti overfitting. Dengan pendekatan yang tepat, pohon keputusan dapat memberikan hasil yang akurat dan bermanfaat bagi berbagai bidang ilmu dan industri.