Decision tree learning atau Pembelajaran Pohon Keputusan adalah metode pembelajaran yang sering digunakan dalam data mining. Metode ini digunakan untuk membangun model yang mengpredict nilai variabel target berasal dari beberapa variabel input. Decision tree adalah representasi sederhana untuk mengelompokkan contoh. Setiap node dalam tree yang tidak adalah node akhir (leaf) ditandai dengan sebuah input feature. Arcs yang berasal dari node yang ditandai dengan input feature ditandai dengan setiap nilai variabel target atau arc berpindah ke node pembagian terhadap input feature lain. Setiap leaf tree ditandai dengan class atau distribusi kelas, yang menandakan bahwa data set telah dikelompokkan oleh tree ke dalam class tertentu atau distribusi kelas (yang, jika decision tree terbuat dengan baik, berpandangan kepada subkumpulan kelas tertentu).
Tree dibangun dengan cara membagi sumber data, yang merupakan node akar tree, menjadi subkumpulan yang merupakan anak node berikutnya. Pembagian dilakukan berdasarkan setiap set dari aturan pembagian berdasarkan feature pengelompokan. Proses ini dilakukan secara recursive, yang disebut recursive partitioning. Proses ini dilakukan sampai subset pada node memiliki semua sama nilai variabel target atau pembagian tidak menambah nilai pada prediksi. Proses ini disebut top-down induction of decision trees (TDIDT) dan ialah contoh algoritma greedy, yang merupakan strategi yang paling sering digunakan untuk belajar decision trees dari data.
Decision trees dapat juga diterangkan sebagai kombinasi teknologi matematis dan komputer untuk membantu penjelasan, kategorisasi, dan generalisasi data yang diberikan.
Data datang dalam bentuk catatan:
Variabel terikat, , adalah variabel target yang coba kita pahami, klasifikasikan, atau generalisasikan. Vektor
terdiri dari fitur-fiturnya,
dll., yang digunakan untuk tugas itu.
Metrik Pohon Keputusan (Decision Tree)
Perkiraan Kebenaran Positif: Menyeimbangkan Positif Sejati dan Positif Palsu
Saat menyusun pohon keputusan, penting untuk mengukur keakuratan prediksi positif versus positif palsu. Metrik "Perkiraan Kebenaran Positif" memberikan wawasan tentang seberapa efektif suatu fitur dapat mengidentifikasi contoh positif dalam kumpulan data. Dengan mengurangkan positif palsu dari positif sebenarnya, metrik ini menawarkan perkiraan kemampuan fitur untuk mengklasifikasikan sampel positif dengan benar. Namun, penting untuk diingat bahwa perkiraan ini dapat bervariasi tergantung pada distribusi sampel positif antar fitur.
- Ketidakmurnian Gini
Pengotor Gini adalah ukuran yang digunakan dalam pohon klasifikasi untuk mengevaluasi homogenitas variabel target dalam subset. Ini mengukur kemungkinan kesalahan klasifikasi elemen yang dipilih secara acak dalam suatu kumpulan berdasarkan distribusi label. Dengan meminimalkan pengotor Gini, algoritma pohon keputusan bertujuan untuk menciptakan node di mana semua kasus masuk dalam satu kategori target, sehingga meningkatkan akurasi prediksi.
- Perolehan Informasi
Perolehan informasi berfungsi sebagai kriteria penting untuk memilih pemisahan optimal dalam pohon keputusan. Berdasarkan konsep entropi dari teori informasi, perolehan informasi mengukur pengurangan ketidakpastian tentang variabel target yang dicapai dengan pemisahan sebuah node. Dengan memilih pemisahan yang memaksimalkan perolehan informasi, algoritme pohon keputusan memprioritaskan fitur yang menghasilkan node turunan yang lebih konsisten, sehingga pada akhirnya meningkatkan kekuatan prediktif model.
- Pengurangan Varians
Jika variabel target bersifat kontinu, pengurangan varians menjadi metrik utama untuk mengevaluasi pemisahan. Diperkenalkan dalam algoritma seperti CART, pengurangan varians mengkuantifikasi pengurangan total varians variabel target karena pemisahan pada node tertentu. Dengan meminimalkan varians, algoritme pohon keputusan secara efektif menangani variabel kontinu, sehingga meningkatkan akurasi model dalam tugas regresi.
- Ukuran "Kebaikan"
Ukuran “kebaikan” mewakili fungsi yang bertujuan untuk mengoptimalkan keseimbangan antara kapasitas calon perpecahan untuk menciptakan anak-anak murni dan kemampuannya untuk menciptakan anak-anak yang berukuran sama. Metrik ini, yang digunakan dalam CART, memprioritaskan penciptaan struktur pohon yang seimbang, sehingga meningkatkan konsistensi waktu pengambilan keputusan. Namun, hal ini dapat menyebabkan perpecahan tambahan dibandingkan dengan metrik lain seperti perolehan informasi.
Jenis-Jenis Pohon Keputusan dalam Analisis Data Mining (Decision Tree Learning)
Dalam analisis data mining, pohon keputusan digunakan untuk dua jenis utama pemodelan:
1. Pohon Klasifikasi (Classification Tree Analysis): Ini adalah ketika hasil yang diprediksi adalah kelas (discrete) ke mana data tersebut termasuk.
2. Pohon Regresi (Regression Tree Analysis): Ini adalah ketika hasil yang diprediksi dapat dianggap sebagai angka riil (misalnya, harga rumah atau lama tinggal pasien di rumah sakit).
Penggunaan istilah "classification and regression tree" (CART) merujuk pada salah satu prosedur di atas, yang pertama kali diperkenalkan oleh Breiman dkk. pada tahun 1984. Meskipun pohon yang digunakan untuk regresi dan klasifikasi memiliki beberapa kesamaan, namun juga beberapa perbedaan, seperti prosedur yang digunakan untuk menentukan di mana untuk membagi.
Contoh pohon yang memperkirakan kemungkinan kifosis setelah operasi tulang belakang, berdasarkan usia pasien dan tulang belakang tempat operasi dimulai. Pohon yang sama ditampilkan dalam tiga cara berbeda. Kiri Daun berwarna menunjukkan kemungkinan kifosis setelah operasi tulang belakang, dan persentase pasien pada daun. Tengah Pohon sebagai plot perspektif. Pemandangan udara kanan dari plot tengah. Kemungkinan kifosis setelah operasi lebih tinggi di area yang lebih gelap. (Catatan: Pengobatan kifosis telah mengalami kemajuan pesat sejak kumpulan data yang cukup kecil ini dikumpulkan.
Beberapa teknik, sering disebut sebagai metode ensemble, membangun lebih dari satu pohon keputusan:
- Pohon yang Ditingkatkan (Boosted Trees): Membangun secara bertahap sebuah ensemble dengan melatih setiap contoh baru untuk menekankan pada contoh-contoh pelatihan sebelumnya yang salah dimodelkan. Contoh umumnya adalah AdaBoost. Ini dapat digunakan untuk masalah tipe regresi dan klasifikasi.
- Bootstrap Aggregated (Bagged) Decision Trees: Metode ensemble awal ini membangun beberapa pohon keputusan dengan secara berulang memilih sampel ulang data pelatihan dengan penggantian, dan melakukan voting pada pohon-pohon untuk prediksi konsensus.
- Random Forest Classifier: Merupakan jenis khusus dari bootstrap aggregating.
- Rotation Forest: Di mana setiap pohon keputusan dilatih dengan menerapkan analisis komponen utama (PCA) pada subset acak fitur input.
Salah satu kasus khusus dari pohon keputusan adalah daftar keputusan, yang merupakan pohon keputusan satu sisi, sehingga setiap simpul internal memiliki tepat 1 simpul daun dan tepat 1 simpul internal sebagai anak (kecuali simpul terbawah, yang hanya memiliki satu simpul daun tunggal). Meskipun kurang ekspresif, daftar keputusan lebih mudah dipahami daripada pohon keputusan umum karena kekompakan yang ditambahkan, memungkinkan metode pembelajaran non-greedy dan penggunaan batasan monotonic.
Algoritme Pohon Keputusan Meliputi
Algoritma pohon keputusan yang terkenal meliputi ID3, C4.5, CART, CHAID, MARS, dan Conditional Inference Trees. ID3 dan CART ditemukan secara independen pada waktu yang hampir bersamaan, tetapi mengikuti pendekatan serupa untuk mempelajari pohon keputusan dari tupel pelatihan.
Selain itu, telah diusulkan untuk memanfaatkan konsep teori himpunan fuzzy untuk definisi versi khusus dari pohon keputusan, yang dikenal sebagai Fuzzy Decision Tree (FDT). Dalam klasifikasi fuzzy ini, biasanya, vektor input dikaitkan dengan beberapa kelas, masing-masing dengan nilai kepercayaan yang berbeda.
Dengan demikian, pemahaman tentang berbagai jenis pohon keputusan ini menjadi penting dalam konteks analisis data mining untuk mengoptimalkan prediksi dan pemodelan.
Keuntungan Penggunaan Decision Trees
Salah satu keuntungan utama dari decision trees adalah kemampuannya untuk dipahami dengan mudah. Model-model ini dapat dijelaskan secara singkat kepada orang awam dan bahkan dapat disajikan secara grafis, membuatnya mudah diinterpretasikan.
Selain itu, decision trees juga dapat menangani data numerik maupun kategorikal. Hal ini membedakannya dari beberapa metode lain yang hanya bisa digunakan untuk satu jenis variabel saja.
Decision trees juga memerlukan sedikit persiapan data dibandingkan dengan metode lainnya. Karena dapat menangani prediktor kualitatif, tidak diperlukan pembuatan variabel dummy.
Model decision trees merupakan model "white box" atau "open-box", yang artinya penjelasan mengenai kondisi suatu situasi dapat dijelaskan dengan logika Boolean. Hal ini berbeda dengan model "black box" seperti neural networks, di mana penjelasan untuk hasilnya sulit dipahami. Decision trees juga mampu mengatasi co-linearity dengan baik, terutama dalam metode boosting. Selain itu, feature selection juga sudah terintegrasi di dalamnya, membuatnya efisien dalam penggunaan fitur.
Keterbatasan Penggunaan Decision Trees
Meskipun memiliki banyak keuntungan, decision trees juga memiliki beberapa keterbatasan. Salah satunya adalah kecenderungan untuk menjadi sangat tidak stabil. Perubahan kecil dalam data latih dapat menghasilkan perubahan besar dalam pohon keputusan dan prediksi akhirnya.
Selain itu, pencarian untuk membangun decision tree optimal dapat menjadi masalah yang sulit. Algoritma pembelajaran decision-tree didasarkan pada heuristik seperti algoritma greedy, yang tidak dapat menjamin untuk menghasilkan pohon keputusan yang optimal secara global. Decision trees juga rentan terhadap overfitting, di mana model menjadi terlalu kompleks dan tidak dapat menggeneralisasi dengan baik dari data latih. Oleh karena itu, mekanisme pruning diperlukan untuk menghindari masalah ini.
Implementasi dan Ekstensi
Terdapat banyak perangkat lunak data mining yang menyediakan implementasi dari algoritma decision tree, baik yang open-source maupun berbayar. Contohnya adalah KNIME, Orange, dan scikit-learn untuk yang open-source, serta MATLAB, Microsoft SQL Server, dan RapidMiner untuk yang berbayar. Selain itu, terdapat juga ekstensi dari decision trees seperti decision graphs dan metode pencarian alternatif menggunakan algoritma evolusioner.
Disadur dari: en.wikipedia.org