Dalam Pengantar Pembelajaran Statistik dengan Aplikasi dalam R , penulis menulis bahwa pemasangan pohon keputusan sangat cepat, tetapi ini tidak masuk akal bagi saya. Algoritma harus melalui setiap fitur dan mempartisi dengan segala cara untuk menemukan pemisahan optimal. Untuk fitur numerik dengan pengamatan, ini dapat menghasilkan partisi untuk setiap fitur.
Apakah saya salah paham bagaimana cara kerja pemisahan biner? Atau adakah alasan mengapa algoritma ini tidak akan lama?
Jawaban:
Algoritma pohon keputusan tidak menghitung semua pohon yang mungkin ketika mereka cocok dengan pohon. Jika mereka melakukannya, mereka akan memecahkan NP-hardmasalah. Algoritma pemasangan pohon keputusan biasanya membuat keputusan serakah dalam proses pemasangan — pada setiap tahap mereka mengoptimalkan sub-masalah untuk menemukan pemisahan optimal dengan data dalam simpul yang diberikan dan terus bergerak maju dalam proses pemasangan. Selain itu, saat Anda bergerak lebih dalam ke pohon keputusan, Anda memiliki set data yang lebih kecil yang telah membuatnya ke node yang diberikan sehingga Anda akan mengoptimalkan aturan pemisahan atas subset data yang lebih kecil. Semua pilihan ini adalah pemindaian linear data dalam node yang diberikan. Ini tidak rumit untuk dilakukan tetapi bisa menjadi agak mahal secara komputasi jika Anda memiliki banyak pengamatan atau sejumlah besar kovariat untuk dibagi. Namun, banyak pekerjaan dapat dipisahkan dan dikirim ke mesin yang berbeda untuk dikerjakan sehingga ada cara untuk membangun arsitektur komputasi Anda untuk ditingkatkan.
sumber
Ada beberapa perbedaan antara algoritma CART dan C4.5 untuk membangun pohon keputusan. Misalnya, CART menggunakan Gini Impurity untuk memilih fitur sementara C.4.5 menggunakan Shannon Entropy. Saya tidak berpikir perbedaannya relevan untuk jawabannya, jadi saya tidak akan membedakannya.
Apa yang membuat pohon keputusan lebih cepat daripada yang Anda pikirkan adalah:
and
akan menghasilkan pohon yang lebih baik. Ini berarti Anda harus sangat berhati-hati / pintar ketika melakukan rekayasa fitur. Misalnya, Anda mencoba memperkirakan berapa banyak orang yang minum, Anda mungkin ingin menonjolkan hal-hal seperti insinyurnew_feature = hour > 22 & hour < 4 & (friday_night | saturday_night)
. Pohon keputusan mungkin kehilangan aturan seperti itu, atau memberi mereka kepentingan kurang dari yang seharusnya.X <= 1
X <= 1.5
X <= 2
X <= 1
X <= 1.5
xgboost
sangat cepat. Peningkatan gradien adalah berurutan dan tidak dapat diparalelkan, tetapi pohon itu sendiri bisa.sumber
Hanya untuk memperkaya jawaban,
Pohon keputusan hierarki paralel-paralel cepat (CART, C4.5) tetapi ada alternatif lain seperti pohon keputusan non-hierarkis atau mereka yang melakukan partisi miring yang tidak, meskipun mereka bisa lebih akurat. Periksa referensi berikut jika Anda tertarik (Itu bukan pilihan yang exahustive).
Non-hierarkis:
Grubinger, T., Zeileis, A. dan Pfeiffer, K.-., 2014. Evtree: Pembelajaran evolusi pohon klasifikasi dan regresi optimal global dalam RJStat. Perangkat Lunak 61 (1), 1-29.
Perpecahan miring:
Murthy, SK, Kasif, S. dan Salzberg, S., 1994. Sebuah sistem untuk induksi pohon keputusan miring. J. Artif. Intell. Res. 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63 . Cantú-Paz, E. dan Kamath, C., 2003. Menginduksi pohon keputusan miring dengan algoritma evolusioner. IEEE Trans. Evol. Komputasi. 7 (1), 54-68. http://dx.doi.org/10.1109/TEVC.2002.806857 . Heath, D., Kasif, S. dan Salzberg, S., 1993. Induksi pohon keputusan miring. J. Artif. Intell. Res. 2 (2), 1002-1007.
Semoga berhasil!
sumber