Bisakah model CART dibuat kuat?

14

Seorang kolega di kantor saya berkata kepada saya hari ini, "Model pohon tidak bagus karena tertangkap oleh pengamatan ekstrim".

Pencarian di sini menghasilkan utas ini yang pada dasarnya mendukung klaim.

Yang mengarahkan saya ke pertanyaan - dalam situasi apa model CART dapat menjadi kuat, dan bagaimana hal itu ditunjukkan?

regression classification robust cart Tal Galili
sumber

Jawaban:

15

Tidak, tidak dalam bentuk mereka saat ini. Masalahnya adalah bahwa fungsi kehilangan cembung tidak dapat dibuat kuat terhadap kontaminasi oleh pencilan (ini adalah fakta yang sudah diketahui sejak tahun 70-an tetapi terus ditemukan kembali secara berkala, lihat misalnya makalah ini untuk satu penemuan baru seperti itu):

http://www.cs.columbia.edu/~rocco/Public/mlj9.pdf

Sekarang, dalam kasus pohon regresi, fakta bahwa CART menggunakan marjinal (atau alternatif univariat proyeksi) dapat digunakan: orang dapat memikirkan versi CART di mana kriteria sd diganti oleh mitra yang lebih kuat (MAD atau lebih baik lagi, Qn estimator).

Edit:

Baru-baru ini saya menemukan makalah yang lebih tua yang mengimplementasikan pendekatan yang disarankan di atas (menggunakan penaksir skala M yang kuat dan bukannya MAD). Ini akan memberikan ketahanan untuk outlier "y" pada CART / RF (tetapi tidak untuk outlier yang terletak pada ruang desain, yang akan mempengaruhi estimasi parameter hiper-model) Lihat:

Galimberti, G., Pillati, M., & Soffritti, G. (2007). Pohon regresi yang kuat berdasarkan pada M-estimators. Statistica, LXVII, 173–190.

pengguna603
sumber
Terima kasih kwak. Artikel ini sepertinya berbicara tentang meningkatkan metode. Apakah hasil yang mereka miliki berlaku untuk case classifier sederhana model CART? (di permukaan kedengarannya seperti itu, tapi saya tidak cukup membaca artikel untuk benar-benar tahu)
Tal Galili
Hasil yang mereka miliki berlaku untuk fungsi kehilangan cembung, dan pada awalnya dibahas oleh Tukey. Singkatnya, ukuran penyebaran (Gini atau entropi) yang digunakan untuk mengukur kualitas sebuah node sensitif terhadap kontaminasi oleh pencilan (yaitu pengamatan yang salah label pada dataset). Masalah ini mempengaruhi bangunan dan tahap prunning. Kontaminasi suatu dataset dengan pengamatan dengan label yang salah dimasukkan biasanya akan menyebabkan pohon yang dihasilkan menjadi terlalu rumit (Anda dapat memeriksanya sendiri dengan mudah).
user603
Kwak terima kasih! Dan apakah tidak ada fungsi kerugian yang kuat?
Tal Galili
1
tidak ada fungsi cembung . Lihat artikel ini "Algoritma cepat untuk penaksir kovariansi penentu minimum" untuk contoh apa yang dapat dilakukan dengan fungsi kehilangan non-cembung (meskipun tidak terkait dengan klasifikasi, artikel ini layak dibaca).
user603
2
@Tal CART adalah setara dengan meningkatkan, dari "pivot classifier" (kriteria yang duduk di setiap simpul pohon, seperti beberapa parutan atribut daripada sesuatu atau nilai atribut dalam set sesuatu).
6

Anda dapat mempertimbangkan untuk menggunakan hutan pengantong atau acak Breiman . Salah satu referensi yang baik adalah Breiman "Bagging Predictors" (1996). Juga diringkas dalam "Klasifikasi dan Regresi Pohon Clifton Sutton , Mengantongi, dan Meningkatkan" dalam Buku Pegangan Statistik.

Anda juga dapat melihat diskusi Andy Liaw dan Matthew Wiener R News tentang paket randomForest.

Shane
sumber
2
Bukan untuk merusak pesta, tetapi bagaimana hutan acak seharusnya memberikan ketahanan terhadap kontaminasi oleh pencilan adalah sebuah misteri.
user603
3
@ Kangwak Tetap saja, ini adalah jawaban yang bagus; pohon di RF tidak melihat seluruh rangkaian, sehingga banyak dari mereka tidak akan terkontaminasi. Bahkan lebih baik - pelacakan di mana daun melakukan OOB kasus tanah dapat digunakan untuk menemukan objek yang salah label dan menghilangkannya. (Seingat saya sekarang, ini disebutkan dalam makalah Breiman tentang RF).
4
Masalahnya adalah outlier akan membuat beberapa pohon 'jahat' (terkontaminasi) terlihat lebih baik daripada yang baik (tidak terkontaminasi). Ini disebut efek masking dan mudah ditiru dengan data yang disimulasikan. Masalah muncul karena kriteria yang Anda gunakan untuk mengevaluasi pohon tidak dengan sendirinya kuat untuk pencilan. Saya tahu saya mulai terdengar seperti mullah fundamentalis, tetapi kecuali setiap alat yang Anda gunakan dibuat kuat, prosedur Anda dapat ditampilkan menjadi sensitif (pada satu tingkat atau lain) untuk pencilan (dan karenanya tidak kuat).
user603
3

Jika Anda memeriksa paket 'gbm' di R (generalized gradient boosting), 'boosting' menggunakan fungsi kerugian yang tidak selalu berarti kesalahan kuadrat. Ini muncul dalam argumen 'distribusi' untuk berfungsi 'gbm ()'. Dengan demikian, elaborasi pohon melalui boosting akan tahan terhadap outlier, mirip dengan cara kerja penduga-M.

Anda mungkin mulai di sini .

Pendekatan lain adalah membangun pohon dengan cara biasa (partisi berdasarkan SSE), tetapi pangkas pohon menggunakan validasi silang dengan ukuran kecocokan yang kuat. Saya pikir xpred di rpart akan memberikan prediktor silang yang divalidasi (untuk berbagai kompleksitas pohon), yang kemudian Anda dapat menerapkan ukuran kesalahan Anda sendiri, seperti nilai absolut rata-rata.

AlaskaRon
sumber