Regresi Pokok Keputusan dari Awal: Teori dan Amalan

Utama » Python » Regresi Pokok Keputusan dari Awal: Teori dan Amalan

Regresi pokok keputusan dari awal merupakan salah satu latihan paling membuka mata yang boleh anda lakukan jika anda ingin benar-benar memahami cara model berasaskan pokok berfikir dan mengapa ia begitu popular dalam pembelajaran mesin. Daripada menganggap pokok itu sebagai kotak hitam misteri, anda akan melihat bagaimana setiap perpecahan dipilih, bagaimana bendasing diukur dan bagaimana ramalan berangka dihasilkan pada daun, baik untuk masalah regresi mahupun pengelasan.

Dalam panduan ini, kita akan membincangkan idea teras di sebalik pokok keputusan, fungsi kos yang digunakan, cara mereka mencari pecahan terbaik dan cara mengekod pokok asas yang menyokong regresi dan pengelasan, hanya menggunakan konsep asas seperti gelung, syarat dan statistik mudah. Sepanjang proses ini, kita akan membandingkan regresi vs. pokok pengelasan, menghubungkan teori dengan pelaksanaan praktikal dalam alatan seperti Python dan R (contohnya dengan rpart dan pokok), dan secara ringkas meletakkan pokok keputusan di dalam ensembel yang lebih besar seperti hutan rawak.

Apakah itu pokok keputusan dan mengapa ia begitu intuitif?

Pokok keputusan pada asasnya merupakan aliran soalan ya/tidak (atau peraturan mudah) yang membimbing anda daripada keputusan akar kepada ramalan akhir dalam nod daun. Dalam suasana pembelajaran yang diselia secara tipikal, matlamatnya adalah untuk meramalkan pembolehubah sasaran Y menggunakan berbilang peramal (ciri, kovariat), dan pokok mempelajari urutan soalan seperti “adakah berat ≤ 103?” atau “adakah negara dalam {AS, UK, CA}?” yang secara beransur-ansur membahagikan data kepada kumpulan yang lebih homogen.

Untuk mendapatkan sedikit intuisi, bayangkan anda ingin meramalkan sama ada seseorang itu obes hanya menggunakan ketinggian dan berat badan, dan anda mempunyai set data berlabel yang memberitahu anda siapa yang obes dan siapa yang tidak. Sesebuah pokok mungkin menemui peraturan seperti “jika berat badan > 100 kg, ramalkan obesiti”, tetapi peraturan itu tidak akan sempurna: sesetengah orang yang beratnya melebihi 100 kg tidak akan obes, dan sesetengah orang yang beratnya di bawah ambang itu akan obes. Pokok itu kemudiannya terus menambah lebih banyak soalan (sub-pecahan), contohnya tentang ketinggian atau ambang berat badan yang diperhalusi, untuk “memperhalusi” ramalan kasar awal tersebut.

Setiap nod dalaman dalam pokok sepadan dengan peraturan keputusan, setiap cabang sepadan dengan satu hasil peraturan tersebut, dan setiap nod daun sepadan dengan kawasan ruang ciri yang ramalannya adalah malar. Dalam pengelasan, daun mengembalikan label kelas (atau taburan kebarangkalian ke atas label); dalam regresi, daun biasanya mengembalikan min bagi nilai sasaran yang termasuk dalam rantau tersebut.

Salah satu kekuatan utama pokok keputusan ialah ia mengendalikan regresi dan pengelasan secara semula jadi, ia mudah ditafsirkan, dan ia berfungsi dengan peramal kuantitatif dan kualitatif (kategorikal) tanpa memerlukan prapemprosesan yang berat. Anda tidak perlu menganggap sebarang taburan khusus untuk ciri atau sasaran anda, yang menjadikan pokok sangat menarik dalam senario dunia sebenar di mana andaian linear klasik sering dilanggar.

Pengelasan vs. pokok regresi

Walaupun struktur pokok pengelasan dan regresi adalah sama, sifat pembolehubah tindak balas Y dan fungsi kos yang digunakan untuk pemisahan berbeza antara kedua-dua jenis ini. Apabila Y bersifat kuantitatif (contohnya, jualan, jangka hayat, penggunaan bahan api), kita bercakap tentang pokok regresi; apabila Y bersifat kualitatif atau kategorikal (contohnya, terselamat vs. tidak terselamat, obes vs. tidak obes), kita bercakap tentang pokok pengelasan.

Dalam pokok regresi, objektif biasa adalah untuk membahagikan ruang ciri kepada kawasan di mana tindak balas boleh dianggarkan dengan pemalar, selalunya min bagi pemerhatian di kawasan tersebut. Peraturan keputusan biasa mempunyai bentuk “ialah x_k ≤ c?”, di mana x_k ialah salah satu kovariat dan c ialah ambang; peraturan ini berulang kali membahagikan ruang kepada hiper-segi empat tepat, dan semua titik dalam hiper-segi empat tepat yang sama berkongsi nilai ramalan yang sama ŷ.

Dalam pokok pengelasan, pecahan masih merupakan “ciri ≤ ambang?” atau “kategori dalam set S?”, tetapi kualiti pecahan diukur dengan sejauh mana ketulenan nod anak yang terhasil dari segi label kelas. Ramalan daun biasanya merupakan kelas majoriti di dalam nod tersebut, dan model cuba mencipta daun yang sedekat mungkin dengan hanya mengandungi satu kelas.

Walaupun terdapat perbezaan dalam jenis sasaran ini, dari perspektif pengekodan, anda boleh melaksanakan struktur pokok generik tunggal dan hanya memasukkan ukuran kekotoran atau kerugian yang berbeza bergantung pada sama ada anda melakukan regresi atau pengelasan. Kemudian, apabila kita mengira Perolehan Maklumat, anda akan melihat bahawa formula untuk pengelasan (berdasarkan entropi) dan regresi (berdasarkan varians) adalah selari dari segi semangat.

Fungsi kekotoran dan kos dalam pokok keputusan

Di tengah-tengah mana-mana algoritma pokok keputusan terletaknya fungsi kos yang menilai sejauh mana pemisahan tertentu dapat memisahkan data kepada kumpulan yang bermakna. Fungsi kos ini dinyatakan dalam bentuk bendasing: nod dianggap tulen jika semua sampelnya tergolong dalam kelas yang sama (untuk pengelasan) atau mempunyai nilai angka yang hampir sama (untuk regresi).

Setiap kali anda memilih calon yang dibahagikan pada sesuatu ciri, algoritma akan melihat nod anak yang dihasilkannya dan bertanya: "sejauh manakah campuran label (atau nilai) dalam setiap anak?" Pemisahan yang baik ialah nod yang menghasilkan nod anak yang kurang tulen berbanding nod induk, yang bermaksud data dalam setiap anak lebih homogen berbanding sasaran.

Dalam pokok pengelasan, bendasing biasanya diukur dengan kriteria seperti indeks Gini atau entropi, yang kedua-duanya menunjukkan kemungkinan pemerhatian yang dipilih secara rawak dalam nod tersebut akan disalahkelaskan jika kita hanya meramalkan kelas majoriti. Dalam pokok regresi, kekotoran biasanya diukur dengan ralat kuasa dua atau varians, yang mencerminkan penyebaran nilai sasaran dalam nod.

Indeks Gini: mengukur bendasing dalam pokok pengelasan

Indeks Gini merupakan salah satu ukuran bendasing yang paling biasa digunakan untuk pokok pengelasan kerana ia mudah dikira dan berfungsi dengan baik dalam amalan. Secara konseptual, ia mengukur kebarangkalian bahawa pemerhatian yang dipilih secara rawak daripada nod akan dikelaskan secara salah jika labelnya diramalkan mengikut taburan label dalam nod tersebut.

Jika nod mengandungi kelas dengan kebarangkalian P₁, P₂, … , P_n, indeks Gini dikira sebagai Gini = 1 − Σ (P_i)². Apabila nod adalah tulen sepenuhnya (semua cerapan tergolong dalam kelas yang sama), salah satu kebarangkalian ialah 1 dan selebihnya ialah 0, jadi jumlah kuasa dua ialah 1 dan indeks Gini ialah 0, menunjukkan ketulenan penuh.

Sebaliknya, indeks Gini mencapai maksimumnya apabila kelas dicampur secara sekata di dalam nod, contohnya dalam masalah binari dengan P₁ = P₂ = 0.5, yang memberikan Gini = 1 − (0.5² + 0.5²) = 0.5. Dalam situasi itu, meramalkan kelas majoriti adalah seteruk yang anda boleh dapatkan untuk taburan itu kerana nod mengandungi separuh daripada setiap kelas.

Apabila anda melaksanakan Gini dalam kod, anda biasanya mengambil vektor label untuk nod, mengira frekuensi setiap kelas, menukar frekuensi kepada kebarangkalian, dan kemudian menggunakan formula 1 − Σ p². Jika anda melakukan ini untuk berbilang pembahagian calon, anda boleh membandingkan pembahagian yang menghasilkan anak dengan purata kekotoran Gini berwajaran yang lebih rendah, iaitu apa yang diperlukan oleh pokok untuk menentukan pembahagian terbaik.

Entropi: pandangan lain tentang pengelasan bendasing

Entropi ialah ukuran bendasing alternatif yang digunakan secara meluas dalam teori maklumat dan dalam algoritma pokok awal seperti ID3 dan C4.5, dan ia menangkap jumlah kerawakan atau ketidakpastian dalam taburan kelas nod. Walaupun Gini memberi tumpuan kepada kebarangkalian salah klasifikasi, entropi mengukur "kejutan" yang berkaitan dengan pemerhatian kelas tertentu apabila taburan bercampur.

Kebarangkalian kelas yang diberi p₁, …, hlm_c untuk nod S, entropinya ditakrifkan sebagai E(S) = − Σ p_i log₂(p_i). Jika nod itu tulen, salah satu kebarangkalian ialah 1 dan semua yang lain ialah 0, yang menjadikan jumlahnya sifar (kerana log₂(1) = 0), jadi entropi ialah 0, menunjukkan tiada ketidakpastian.

Apabila nod mengandungi taburan kelas yang seragam, entropi dimaksimumkan; untuk masalah binari dengan p₁ = hlm₂ = 0.5, entropi ialah 1 bit, iaitu nilai tertinggi yang mungkin untuk dua kelas. Nilai ini sepadan dengan ketidakpastian maksimum, bermakna nod tersebut tidak tulen seperti yang boleh di bawah taburan tersebut.

Walaupun Gini dan entropi menggunakan formula yang berbeza dan mempunyai julat angka yang berbeza (Gini antara 0 dan 0.5 untuk dua kelas, entropi antara 0 dan 1), kedua-duanya mengukur konsep yang sama, jadi ia biasanya membawa kepada pokok yang sangat serupa dalam praktiknya. Apabila anda mengira kedua-duanya pada nod yang sama, anda akan mendapati bahawa Gini yang tinggi sepadan dengan entropi yang tinggi dan sebaliknya, itulah sebabnya banyak perpustakaan membenarkan anda memilih sama ada tanpa mengubah prestasi secara drastik.

Pengumpulan Maklumat dan memilih pembahagian terbaik

Untuk memilih pembahagian terbaik antara ramai calon, algoritma pokok menggunakan metrik yang dipanggil Keuntungan Maklumat, yang mengukur berapa banyak bendasing berkurangan apabila kita membahagikan nod kepada anak-anaknya. Secara intuitif, perpecahan mempunyai Perolehan Maklumat yang tinggi jika anak-anak jauh lebih tulen daripada ibu bapa, bermakna peraturan tersebut berjaya memisahkan data kepada kumpulan yang lebih bermakna.

Bagi pokok pengelasan yang menggunakan entropi, Perolehan Maklumat bagi perpecahan ditakrifkan sebagai IG_klasifikasi = E(induk) − Σ (|S_kanak-kanak| / |S_{ibu bapa}|) · E(S_kanak-kanak). Anda mula-mula mengira entropi nod induk, kemudian tolak purata entropi berwajaran nod anak, yang mana pemberatnya ialah saiz relatifnya.

Bagi pokok regresi, konsep analog menggunakan varians atau ralat min kuasa dua sebagai ukuran bendasing, memberikan IG_regresi = Var(induk) − Σ (|S_kanak-kanak| / |S_{ibu bapa}|) · Var(S_kanak-kanak). Dalam suasana ini, pembahagian yang baik adalah pembahagian yang dapat mengurangkan kebolehubahan nilai sasaran dalam setiap kanak-kanak dengan ketara.

Algoritma latihan pokok menilai Keuntungan Maklumat ini untuk setiap kemungkinan pembahagian calon pada setiap ciri, kemudian memilih pembahagian dengan keuntungan tertinggi, dengan syarat ia melebihi beberapa ambang minimum untuk mengelakkan daripada menghasilkan penambahbaikan kecil yang tidak berguna. Proses ini kemudiannya diulang secara rekursif pada setiap nod anak sehingga beberapa kriteria penghentian dicapai.

Cara mencari pembahagian terbaik pada setiap ciri

Mencari pembahagian terbaik pada satu ciri bergantung pada sama ada ciri tersebut berangka atau kategori, tetapi idea asasnya sentiasa sama: menyenaraikan partition calon dan mengira Perolehan Maklumatnya. Untuk ciri berangka, partition ditakrifkan oleh ambang; untuk ciri kategori, ia ditakrifkan dengan mengelompokkan tahap ke dalam subset.

Untuk peramal berangka, strategi biasa adalah untuk melihat semua nilai unik yang diambil oleh ciri dalam nod semasa, menyusunnya, dan kemudian mempertimbangkan ambang calon antara nilai berturut-turut. Bagi setiap ambang calon c, anda mencipta dua kumpulan (x ≤ c dan x > c), hitung kekotoran setiap kumpulan, dan kemudian hitung Keuntungan Maklumat; ambang yang menghasilkan keuntungan tertinggi ialah pembahagian angka terbaik anda pada ciri tersebut.

Apabila berurusan dengan peramal kategori, ruang carian adalah lebih kompleks kerana, pada prinsipnya, mana-mana subset kategori boleh membentuk satu sisi pemisahan, dengan pelengkap di sisi yang lain. Dalam ciri dengan kategori K, terdapat banyak subset yang mungkin (2^K−1 − 1 partition bukan remeh), jadi dalam praktiknya pelaksanaan sering menyekat carian ini atau menggunakan heuristik, terutamanya apabila K adalah besar.

Sebaik sahaja anda mengira pembahagian terbaik untuk setiap ciri, anda membandingkan Keuntungan Maklumat mereka dan memilih ciri dan ambang (atau subset kategori) yang sepadan dengan keuntungan maksimum. Pemisahan yang dipilih ini menjadi keputusan pada nod semasa, dan proses latihan kemudiannya berulang pada setiap kanak-kanak dengan subset pemerhatian yang sepadan.

Mengawal pertumbuhan pokok dengan hiperparameter

Jika anda membenarkan pokok keputusan tumbuh tanpa sebarang kekangan, ia akan terus berpecah sehingga setiap daun sama ada tulen sepenuhnya atau mengandungi sangat sedikit pemerhatian, yang hampir selalu membawa kepada overfitting yang teruk (overfitting vs underfitting). Untuk mengelakkan ini, anda menetapkan koleksi hiperparameter yang mengawal kedalaman dan kerumitan pokok.

Hiperparameter biasa ialah max_depth, yang mengehadkan bilangan maksimum aras yang boleh tumbuh oleh pokok dari akar ke mana-mana daun. Jika max_depth ditetapkan kepada Tiada (atau nombor yang sangat besar), pokok boleh terus tumbuh selagi kekangan lain dipenuhi; jika ia kecil, pokok kekal cetek dan lebih mudah ditafsirkan tetapi mungkin tidak sesuai.

Satu lagi hiperparameter utama ialah min_samples_split, yang menentukan bilangan minimum pemerhatian yang mesti terkandung dalam nod sebelum ia dibenarkan untuk dipecahkan. Jika nod mempunyai sampel yang lebih sedikit daripada ambang ini, ia akan diubah menjadi daun, menghalang model daripada mengejar hingar dalam subset data yang sangat kecil.

Anda juga boleh menguatkuasakan Perolehan Maklumat minimum (min_information_gain) supaya algoritma hanya melakukan pemisahan jika ia menghasilkan peningkatan yang bermakna dalam pengurangan bendasing. Ini mengelakkan daripada mewujudkan cabang yang tidak perlu yang hampir tidak mengubah ramalan dan hanya merumitkan struktur pokok.

Membina pokok keputusan dari awal dalam kod

Melaksanakan pokok keputusan dari awal biasanya berkisar pada satu set kecil fungsi teras yang dipanggil secara rekursif. Walaupun perpustakaan seperti scikit‑learn atau rpart melakukan semua ini secara rahsia, pengekodan langkah-langkah ini sendiri menjadikan logiknya lebih jelas (logik pengaturcaraan) dan memberi anda kawalan penuh ke atas tingkah laku tersebut.

Pertama, anda memerlukan rutin yang, berdasarkan data semasa pada nod, menilai setiap ciri dan setiap calon yang dibahagikan untuk mencari yang mempunyai Keuntungan Maklumat tertinggi. Fungsi ini mengembalikan ciri yang dipilih, peraturan pecahan (ambang atau subset kategori), nilai gandaan dan topeng boolean atau set indeks yang mengenal pasti sampel mana yang pergi ke kiri dan yang pergi ke kanan.

Kedua, anda memerlukan fungsi ramalan untuk nod daun yang menukar set nilai sasaran dalam nod tersebut kepada satu ramalan. Untuk regresi, ini biasanya min bagi y dalam nod tersebut; untuk pengelasan, anda biasanya mengambil mod (kelas paling kerap), mungkin menyimpan kebarangkalian kelas juga jika anda mahukan output kebarangkalian.

Ketiga, anda mencipta fungsi latihan rekursif yang menyemak kriteria penghentian, mencari pemisahan terbaik jika dibenarkan, dan kemudian membina nod anak dengan memanggil dirinya sendiri pada subset kiri dan kanan. Jika saiz sampel minimum, kedalaman maksimum atau syarat perolehan minimum tidak dipenuhi, fungsi tersebut berhenti membelah dan menyimpan ramalan daun dan bukannya cabang selanjutnya.

Cara ramalan berfungsi dalam pokok keputusan terlatih

Sebaik sahaja pokok anda dilatih dan anda telah menyimpan semua peraturan perpecahan dan ramalan daun, membuat ramalan untuk pemerhatian baharu hanyalah soal berjalan menuruni pokok dari akar ke daun. Pada setiap nod dalaman, anda memeriksa ciri yang diperlukan dan menguji sama ada pemerhatian tersebut memenuhi syarat nod.

Jika peraturan pecahan adalah berangka, anda semak sama ada nilai ciri kurang daripada atau sama dengan ambang; jika peraturan pecahan adalah kategori, anda semak sama ada kategori tersebut berada dalam subset tertentu. Bergantung pada hasilnya, anda ikuti cabang yang sesuai (contohnya, "ya" ke kiri, "tidak" ke kanan) dan ulangi proses ini pada nod seterusnya.

Anda terus menuruni pokok sehingga anda mencapai nod tanpa anak, iaitu daun yang menyimpan nilai output malar atau label kelas. Bagi pokok regresi, ramalannya ialah nombor seperti anggaran jangka hayat atau kecekapan bahan api; bagi pokok pengelasan, outputnya ialah kategori yang diramalkan seperti "terselamat" atau "tidak terselamat".

Jika anda menguji pendekatan ini pada data yang sama yang anda gunakan untuk latihan, anda akan sering melihat ketepatan pengelasan yang agak tinggi (contohnya, sekitar 85% dalam beberapa contoh obesiti mudah atau gaya Titanic), tetapi prestasi itu mungkin menurun pada data yang tidak kelihatan jika pokok anda terlalu dalam. Inilah sebabnya mengapa mengawal kedalaman dan saiz pokok sangat penting, dan mengapa ensembel seperti hutan rawak dicipta untuk menstabilkan ramalan pokok.

Bekerja dengan pokok regresi dalam amalan

Pokok regresi amat berguna apabila hubungan antara peramal dan tindak balas adalah sangat tidak linear dan melibatkan interaksi yang sukar dimodelkan dengan regresi linear klasik. Daripada cuba menyesuaikan persamaan global tunggal, pokok membahagikan ruang ciri kepada kawasan dan menyesuaikan model pemalar mudah dalam setiap kawasan.

Dalam R, pakej popular seperti rpart dan tree memudahkan pembinaan pokok regresi dengan panggilan fungsi tunggal, dengan menyatakan formula seperti y ~ x1 + x2 + … + x11. Pakej-pakej ini dipengaruhi oleh metodologi CART asal yang diterangkan oleh Breiman dan rakan sekerja, dan ia melaksanakan banyak standard idea pemisahan dan pemangkasan dalam pemodelan berasaskan pokok moden.

Contohnya, anda boleh menggunakan pakej rpart untuk memodelkan respons y berdasarkan sebelas kovariat x1 hingga x11, membersihkan data daripada nilai yang hilang, dan kemudian menggambarkan pokok yang terhasil dengan fungsi pembantu seperti prp daripada pakej rpart.plot. Nod terminal menunjukkan y yang diramalkan untuk setiap rantau, yang boleh anda gunakan secara langsung untuk pemerhatian baharu.

Dengan pokok regresi terlatih, anda boleh memasukkan nilai kovariat baharu seperti x9 = 70, x2 = 100 atau x9 = 60, x2 = 150 ke dalam fungsi ramalan untuk mendapatkan nilai anggaran ŷ (contohnya sekitar 20 atau 28 dalam contoh penggunaan bahan api). Membandingkan ramalan ini dengan nilai yang diperhatikan, contohnya melalui korelasi antara y dan ŷ, memberikan anda gambaran pantas tentang sejauh mana pokok tersebut menangkap corak yang mendasari, walaupun set data agak kecil.

Daripada pokok tunggal kepada hutan rawak

Satu pokok keputusan adalah berkuasa tetapi juga sangat sensitif terhadap kekhususan data latihan, yang boleh menyebabkan varians yang tinggi (bias dan varians) dan terlalu sesuai. Untuk mengurangkan masalah ini, hutan rawak membina banyak pokok pada sampel data yang dibootstrap dan mengagregatkan ramalan mereka, menghasilkan model yang lebih stabil dan biasanya lebih tepat.

Dalam hutan rawak, setiap pokok dilatih menggunakan sampel bootstrap, yang bermaksud set data baharu dengan saiz yang sama diambil daripada set latihan asal dengan penggantian. Proses persampelan ini membolehkan setiap pokok melihat set data yang sedikit berbeza, jadi ralatnya kurang berkorelasi dan boleh terbatal apabila diagregatkan.

Di samping itu, hutan rawak memperkenalkan kerawakan dalam proses pemilihan ciri dengan hanya mempertimbangkan subset rawak peramal pada setiap perpecahan dan bukannya semua peramal. Ini seterusnya mengurangkan korelasi antara pokok, meningkatkan kepelbagaian dalam hutan, dan cenderung untuk mengurangkan varians tanpa meningkatkan terlalu banyak bias.

Gabungan bootstrap dan pengagregatan ramalan dikenali sebagai bagging, dan dalam hutan rawak anda juga mendapat anggaran dalaman ralat model dengan menilai setiap pokok pada titik data yang tidak termasuk dalam sampel bootstrapnya (yang dipanggil pemerhatian di luar beg). Ralat di luar beg ini menyediakan cara yang mudah untuk mengukur prestasi tanpa memerlukan set pengesahan yang berasingan.

Walaupun artikel ini memberi tumpuan kepada membina satu pokok dari awal, memahami cara komponen asas itu berfungsi menjadikannya lebih mudah untuk memahami bagaimana ensembel seperti hutan rawak, penggalakan kecerunan dan kaedah berasaskan pokok lain dibina berdasarkan prinsip yang sama untuk mencapai hasil yang canggih dalam banyak masalah yang digunakan.

Dengan menggabungkan semuanya, regresi pokok keputusan dari awal menunjukkan kepada anda bagaimana satu set peraturan mudah, fungsi kos dan pecahan rekursif boleh memodelkan hubungan yang kompleks, sama ada anda meramalkan hasil binari seperti kelangsungan hidup, label kategori seperti status obesiti atau sasaran berangka seperti jangka hayat atau penggunaan bahan api, dan pemahaman yang mendalam ini menjadi asas yang kukuh untuk menggunakan teknik berasaskan pokok yang lebih maju dalam amalan.