Pohon keputusan: melintasi pohon dengan bijaksana (terbaik-pertama) dan bijaksana

14

Masalah 1:

Saya bingung dengan deskripsi LightGBM mengenai cara pohon diperluas.

Mereka menyatakan:

Sebagian besar algoritma pembelajaran pohon keputusan menumbuhkan pohon berdasarkan level (kedalaman), seperti gambar berikut:

masukkan deskripsi gambar di sini

Pertanyaan 1 : Algoritma "paling" mana yang diimplementasikan dengan cara ini? Sejauh yang saya tahu C4.5 dan CART menggunakan DFS. XGBoost menggunakan BFS. Algoritme atau paket lain mana yang menggunakan BFS untuk pohon keputusan?

Edisi 2:

Status LightGBM:

LightGBM menanam pohon dengan bijaksana (terbaik-pertama). Ini akan memilih daun dengan max delta loss untuk tumbuh. Saat menanam daun yang sama, algoritme daun-bijaksana dapat mengurangi lebih banyak kerugian daripada algoritma tingkat-bijaksana.

masukkan deskripsi gambar di sini

Pertanyaan 2 : Apakah benar mengatakan bahwa pohon pertumbuhan dengan tingkat bijaksana akan memiliki kedalaman yang sama untuk semua daun?

Pertanyaan 3: Jika Pertanyaan 2 tidak benar, maka pohon-pohon dari tingkat bijaksana dan pertumbuhan daun akan terlihat sama di akhir traversal (tanpa pemangkasan dll). Apakah ini pernyataan yang benar?

Pertanyaan 4: Jika pertanyaan 3 benar, bagaimana bisa "algoritma daun-bijaksana dapat mengurangi lebih banyak kerugian daripada algoritma tingkat-bijaksana"? Apakah itu ada hubungannya dengan algoritma pasca pemangkasan?

Jekaterina Kokatjuhha
sumber

Jawaban:

11

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.

David Marx
sumber
Bisakah Anda menjawab pertanyaan pertama juga?
Jekaterina Kokatjuhha
Memperbarui jawaban saya. Versi singkatnya adalah bahwa C4.5 dan CART adalah contoh kedalaman-pertama, bukan terbaik-pertama.
David Marx
Pertanyaan pertama saya bukan tentang definisi atau penjelasan tentang best-first atau DFS. Dan saya menyatakan pada diri saya sendiri bahwa C4.5 dan CART adalah DFS. Pertanyaan pertama adalah tentang "Yang" paling "algoritma diimplementasikan oleh level-bijaksana? [...] Algoritma atau paket lain yang menggunakan BFS untuk pohon keputusan?"
Jekaterina Kokatjuhha
1
Pertumbuhan pohon "Kedalaman-pertama" adalah tingkat-bijaksana. Itulah yang saya coba sampaikan kepada Anda. Baca kutipan yang saya soroti untuk Anda. Jangan bingung grafik traversal DFS dan BFS di sini dengan pertumbuhan pohon "Kedalaman pertama" dan "terbaik pertama". Mereka tidak sama, dan pertumbuhan pertama mendalam mengacu pada apa yang Anda sebut "BFS", bukan "DFS".
David Marx
Itulah titik kritis yang saya lewatkan sepanjang waktu. Terima kasih.
Jekaterina Kokatjuhha