Jika Anda menumbuhkan pohon lengkap, terbaik-pertama (bijaksana-daun) dan kedalaman-pertama (bijaksana-level) akan menghasilkan pohon yang sama. Perbedaannya adalah dalam urutan di mana pohon itu diperluas. Karena kita biasanya tidak menumbuhkan pohon hingga ke kedalaman penuh, urutan menjadi penting: penerapan kriteria penghentian awal dan metode pemangkasan dapat menghasilkan pohon yang sangat berbeda. Karena daun-bijaksana memilih perpecahan berdasarkan kontribusinya terhadap kerugian global dan bukan hanya kerugian di sepanjang cabang tertentu, sering (tidak selalu) akan belajar pohon kesalahan yang lebih rendah "lebih cepat" dari pada tingkat bijaksana. Yaitu untuk sejumlah kecil node, leaf-wise mungkin akan melebihi kinerja level-bijaksana. Ketika Anda menambahkan lebih banyak node, tanpa berhenti atau dipangkas, mereka akan bertemu dengan kinerja yang sama karena mereka benar-benar akan membangun pohon yang sama pada akhirnya.
Referensi:
Shi, H. (2007). Pembelajaran Decision Tree Terbaik-pertama (Tesis, Master of Science (MSc)). Universitas Waikato, Hamilton, Selandia Baru. Diperoleh dari https://hdl.handle.net/10289/2317
EDIT: Mengenai pertanyaan pertama Anda, baik C4.5 dan CART adalah contoh mendalam-pertama, bukan yang terbaik dulu. Berikut beberapa konten yang relevan dari referensi di atas:
1.2.1 Pohon keputusan standar
Algoritma standar seperti C4.5 (Quinlan, 1993) dan CART (Breiman et al., 1984) untuk induksi top-down pohon keputusan memperluas node dalam urutan pertama dalam setiap langkah menggunakan strategi divide-and-conquer. Biasanya, pada setiap simpul pohon keputusan, pengujian hanya melibatkan atribut tunggal dan nilai atribut dibandingkan dengan konstanta. Ide dasar dari pohon keputusan standar adalah bahwa, pertama, pilih atribut untuk ditempatkan pada simpul akar dan buat beberapa cabang untuk atribut ini berdasarkan beberapa kriteria (misalnya informasi atau indeks Gini). Kemudian, bagi instance pelatihan menjadi himpunan bagian, satu untuk setiap cabang yang memanjang dari simpul akar. Jumlah himpunan bagian sama dengan jumlah cabang. Kemudian, langkah ini diulangi untuk cabang yang dipilih, hanya menggunakan instance yang benar-benar mencapainya. Pesanan tetap digunakan untuk memperluas node (biasanya, kiri ke kanan). Jika suatu saat semua instance pada node memiliki label kelas yang sama, yang dikenal sebagai node murni, splitting stops dan node dibuat menjadi node terminal. Proses konstruksi ini berlanjut sampai semua node murni. Kemudian diikuti oleh proses pemangkasan untuk mengurangi kelengkapan berlebih (lihat Bagian 1.3).
1.2.2 Pohon keputusan terbaik-pertama
Kemungkinan lain, yang sejauh ini tampaknya hanya telah dievaluasi dalam konteks meningkatkan algoritma (Friedman et al., 2000), adalah untuk memperluas node dalam urutan pertama-terbaik alih-alih urutan tetap. Metode ini menambahkan split node "terbaik" ke pohon di setiap langkah. Node "terbaik" adalah node yang secara maksimal mengurangi ketidakmurnian di antara semua node yang tersedia untuk dibelah (yaitu tidak diberi label sebagai terminal node). Meskipun ini menghasilkan pohon yang sepenuhnya tumbuh sama dengan ekspansi kedalaman-pertama standar, ini memungkinkan kami untuk menyelidiki metode pemangkasan pohon baru yang menggunakan validasi silang untuk memilih jumlah ekspansi. Baik pra-pemangkasan dan pasca pemangkasan dapat dilakukan dengan cara ini, yang memungkinkan perbandingan yang adil di antara mereka (lihat Bagian 1.3).
Pohon keputusan terbaik pertama dibangun dengan cara divide-and-conquer mirip dengan pohon keputusan kedalaman-pertama standar. Gagasan dasar tentang bagaimana pohon best-first dibangun adalah sebagai berikut. Pertama, pilih atribut untuk ditempatkan di simpul akar dan buat beberapa cabang untuk atribut ini berdasarkan beberapa kriteria. Kemudian, bagi instance pelatihan menjadi himpunan bagian, satu untuk setiap cabang yang memanjang dari simpul akar. Dalam tesis ini hanya pohon keputusan biner dipertimbangkan dan dengan demikian jumlah cabang tepat dua. Kemudian, langkah ini diulangi untuk cabang yang dipilih, hanya menggunakan instance yang benar-benar mencapainya. Di setiap langkah kami memilih subset "terbaik" di antara semua himpunan bagian yang tersedia untuk ekspansi. Proses pembuatan ini berlanjut sampai semua node murni atau jumlah ekspansi tertentu tercapai. Gambar 1. 1 menunjukkan perbedaan dalam urutan terbagi antara pohon first-first biner hipotetis dan pohon first-first biner hipotetis. Perhatikan bahwa pemesanan lain mungkin dipilih untuk pohon best-first sementara urutan selalu sama dalam kasus kedalaman-pertama.
