Algoritma Hutan dan Pohon Keputusan Acak

14

Hutan acak adalah kumpulan pohon keputusan yang mengikuti konsep pengemasan. Ketika kita berpindah dari satu pohon keputusan ke pohon keputusan selanjutnya, lalu bagaimana informasi yang dipelajari oleh pohon keputusan terakhir bergerak maju ke yang berikutnya?

Karena, sesuai pemahaman saya, tidak ada yang seperti model terlatih yang dibuat untuk setiap pohon keputusan dan kemudian dimuat sebelum pohon keputusan berikutnya mulai belajar dari kesalahan kesalahan klasifikasi.

Jadi bagaimana cara kerjanya?

Abhay Raj Singh
sumber
+ Msgstr "Ketika kita beralih dari satu pohon keputusan ke pohon keputusan berikutnya". Ini menunjukkan proses linear. Kami telah membangun implementasi paralel di mana kami bekerja pada satu pohon per inti CPU; ini berfungsi dengan baik kecuali Anda menggunakan generator nomor acak terpisah per inti CPU dalam pelatihan, yang semuanya berbagi benih yang sama. Dalam hal ini Anda bisa mendapatkan banyak pohon yang identik.
MSalters

Jawaban:

23

Tidak ada informasi yang dikirimkan antar pohon. Di hutan acak, semua pohon terdistribusi secara identik, karena pohon ditanam menggunakan strategi pengacakan yang sama untuk semua pohon. Pertama, ambil sampel bootstrap data, dan kemudian tumbuhkan pohon menggunakan pemisahan dari subset fitur yang dipilih secara acak. Ini terjadi untuk setiap pohon secara individual tanpa memperhatikan pohon lain dalam ansambel. Namun, pohon-pohon tersebut berkorelasi murni berdasarkan setiap pohon yang dilatih berdasarkan sampel dari kumpulan data pelatihan yang umum; banyak sampel dari kumpulan data yang sama akan cenderung serupa, sehingga pohon akan menyandikan beberapa kesamaan itu.

Anda mungkin terbantu untuk membaca pengantar hutan acak dari teks berkualitas tinggi. Salah satunya adalah "Hutan Acak" oleh Leo Breiman. Ada juga bab dalam Elemen Pembelajaran Statistik oleh Hastie et al.

Mungkin saja Anda telah mengacaukan hutan acak dengan metode peningkatan seperti AdaBoost atau pohon yang didorong oleh gradien. Metode peningkatan tidak sama, karena mereka menggunakan informasi tentang ketidakcocokan dari putaran peningkatan sebelumnya untuk menginformasikan putaran peningkatan berikutnya. Lihat: Apakah hutan acak merupakan algoritma penguat?

Sycorax berkata Reinstate Monica
sumber
10

The hutan acak adalah kumpulan pohon keputusan beberapa yang dilatih secara independen satu sama lain . Jadi tidak ada gagasan pelatihan dependen berurutan (yang merupakan kasus dalam meningkatkan algoritma ). Sebagai akibatnya, seperti yang disebutkan dalam jawaban lain, adalah mungkin untuk melakukan pelatihan paralel pohon-pohon.

Anda mungkin ingin tahu dari mana "acak" di hutan acak itu berasal: ada dua cara dengan mana keacakan disuntikkan ke dalam proses belajar pohon. Pertama adalah pemilihan acak dari titik data yang digunakan untuk melatih masing-masing pohon, dan kedua adalah pemilihan acak fitur yang digunakan dalam membangun setiap pohon. Karena pohon keputusan tunggal biasanya cenderung sesuai dengan data, injeksi keacakan dengan cara ini menghasilkan sekelompok pohon di mana masing-masing dari mereka memiliki akurasi yang baik (dan mungkin overfit) pada subset berbeda dari data pelatihan yang tersedia . Karena itu, ketika kita mengambil rata-rata prediksi yang dibuat oleh semua pohon, kita akan mengamati pengurangan overfitting (dibandingkan dengan kasus pelatihan satu pohon keputusan tunggal pada semua data yang tersedia ).

MN

  1. i=0
  2. MMSi
  3. iTiSi
    • proses pelatihan sama dengan melatih pohon keputusan kecuali dengan perbedaan bahwa pada setiap simpul di pohon hanya pilihan acak fitur yang digunakan untuk pemisahan dalam simpul itu.
  1. i=i+1
  2. i<N

T1T2TN

  • Jika digunakan untuk tugas regresi, ambil rata-rata prediksi sebagai prediksi akhir hutan acak.

  • Jika digunakan untuk tugas klasifikasi, gunakan strategi pemungutan suara lunak : ambil rata-rata probabilitas yang diprediksi oleh pohon untuk setiap kelas, kemudian nyatakan kelas dengan probabilitas rata-rata tertinggi sebagai prediksi akhir hutan acak.

Lebih lanjut, perlu disebutkan bahwa adalah mungkin untuk melatih pohon dengan cara yang tergantung secara berurutan dan itulah yang dilakukan oleh algoritma peningkatan pohon gradien , yang merupakan metode yang sama sekali berbeda dari hutan acak.

hari ini
sumber
8

Hutan acak adalah algoritma pengantongan alih-alih algoritma penguat.

Hutan acak membangun pohon secara mandiri menggunakan sampel data acak. Implementasi paralel dimungkinkan.

Anda mungkin ingin memeriksa peningkatan gradien di mana pohon dibangun secara berurutan di mana pohon baru mencoba untuk memperbaiki kesalahan yang dibuat sebelumnya.

Siong Thye Goh
sumber
6

Jadi bagaimana cara kerjanya?

Hutan Acak adalah kumpulan pohon keputusan. Pohon-pohon dibangun secara mandiri. Setiap pohon dilatih tentang subset fitur dan subset sampel yang dipilih dengan penggantian.

Saat memprediksi, katakan untuk Klasifikasi, parameter input diberikan kepada setiap pohon di hutan dan setiap pohon "suara" pada klasifikasi, label dengan suara terbanyak menang.

Mengapa menggunakan Hutan Acak di atas Pohon Keputusan sederhana? Pengorbanan Bias / Varians. Hutan Acak dibangun dari pohon yang jauh lebih sederhana jika dibandingkan dengan pohon keputusan tunggal. Umumnya Hutan Acak memberikan pengurangan kesalahan yang besar karena varians dan peningkatan kesalahan yang kecil karena bias.

Akavall
sumber
Jika kita memilih fitur yang berbeda untuk setiap Decision Tree, lalu bagaimana pembelajaran dengan serangkaian fitur di Decision Tree sebelumnya meningkat sementara kami mengirim nilai yang salah klasifikasi ke depan, sedangkan untuk Decision Tree berikutnya ada sejumlah fitur baru?
Abhay Raj Singh
3
@AbhayRajSingh - Anda tidak "mengirim nilai yang salah klasifikasi" di Random Forest. Seperti yang dikatakan Akavall, "Pohon-pohon dibangun secara independen"
Henry
1

Ya, seperti yang dikatakan penulis di atas, algoritma Random Forest adalah algoritma bagging, bukan boosting.

Bagging dapat mengurangi varians dari classificator, karena algoritma dasar, yang dipasang pada sampel yang berbeda dan kesalahan mereka saling dikompensasi dalam pemungutan suara. Bagging mengacu pada rata-rata versi yang sedikit berbeda dari model yang sama sebagai sarana untuk meningkatkan daya prediksi. Untuk menerapkan bagging, kita cukup membangun pohon regresi B menggunakan set pelatihan B bootstrap, dan rata-rata prediksi yang dihasilkan

Aplikasi pengantongan yang umum dan cukup sukses adalah Random Forest

Tetapi ketika membangun pohon keputusan ini di hutan acak, setiap kali perpecahan dalam pohon dipertimbangkan, sampel acak dari mprediktor dipilih sebagai calon yang terpecah dari set lengkap p prediktor. Pemisahan ini diizinkan untuk hanya menggunakan salah satu dari mprediksi tersebut.

Daniel Chepenko
sumber