Pokok Keputusan: Bagaimana Mengoptimumkan Proses Membuat Keputusan Saya?

Mari kita bayangkan anda bermain permainan Twenty Questions. Lawan anda secara rahsia memilih subjek, dan anda mesti mengetahui apa yang dipilihnya. Pada setiap giliran, anda boleh meminta pertanyaan yang sama atau tidak, dan lawan anda mesti menjawab dengan jujur. Bagaimanakah anda mengetahui rahsia dalam bilangan soalan yang paling sedikit?

Ia harus jelas beberapa soalan lebih baik daripada yang lain. Sebagai contoh, bertanya "Bolehkah ia terbang?" Kerana soalan pertama anda mungkin tidak berbuah, sedangkan bertanya "Adakah hidup?" Sedikit berguna. Secara intuitif, anda ingin setiap soalan untuk mengecilkan ruang yang mungkin rahsia, akhirnya membawa kepada jawapan anda.

Itulah idea asas di sebalik pokok keputusan. Pada setiap titik, anda mempertimbangkan satu set soalan yang boleh memisahkan set data anda. Anda memilih soalan yang memberikan pemisahan yang terbaik dan sekali lagi mencari soalan terbaik untuk sekatan. Anda berhenti sekali semua mata yang anda sedang mempertimbangkan adalah kelas yang sama. Kemudian tugas klasifikasi mudah. Anda hanya dapat meraih satu titik, dan memasukkannya ke bawah pokok itu. Soalan-soalan akan membimbingnya ke kelas yang sesuai.

Syarat Penting

Pokok keputusan adalah sejenis algoritma pembelajaran yang diawasi yang boleh digunakan dalam masalah regresi dan klasifikasi. Ia berfungsi untuk pembolehubah input dan output yang mutlak dan berterusan.

Mari kita kenal pasti terminologi penting pada Pokok Keputusan, melihat imej di atas:

  • Nod Root mewakili keseluruhan populasi atau sampel. Ia selanjutnya dibahagikan kepada 2 atau lebih set homogen.
  • Pemisahan adalah proses membahagikan nod menjadi 2 atau lebih sub-nod.
  • Apabila sub-nod dipecah ke dalam sub-node selanjutnya, ia dipanggil Nod Keputusan.
  • Nod yang tidak berpecah dipanggil Terminal Node atau Daun.
  • Apabila anda mengeluarkan sub-nod dari nod keputusan, proses ini dipanggil pemangkasan. Sebaliknya pemangkasan berpecah.
  • Sub-seksyen seluruh pokok dipanggil cawangan.
  • Satu nod, yang dibahagikan kepada sub-nod dipanggil Node Induk sub-node; sedangkan sub-nod dipanggil Anak nod induk.

Bagaimana ia berfungsi

Di sini saya hanya bercakap tentang pokok klasifikasi, yang digunakan untuk meramalkan tindak balas kualitatif. Pokok regresi adalah yang digunakan untuk meramalkan nilai kuantitatif.

Dalam pokok klasifikasi, kami meramalkan bahawa setiap pemerhatian adalah kepunyaan kelas pemerhatian latihan yang paling sering berlaku di rantau ini. Dalam mentafsirkan hasil pokok klasifikasi, kita sering tertarik bukan sahaja dalam ramalan kelas yang sepadan dengan rantau nod terminal tertentu, tetapi juga dalam bahagian kelas di antara pemerhatian latihan yang jatuh ke rantau itu. Tugas untuk mengembangkan pokok klasifikasi bergantung pada penggunaan salah satu daripada 3 kaedah ini sebagai kriteria untuk membuat pecahan binari:

1 - Kadar Ralat Klasifikasi: Kita boleh menentukan "kadar hit" sebagai pecahan pemerhatian latihan di rantau tertentu yang tidak tergolong dalam kelas yang paling luas. Kesalahan diberikan oleh persamaan ini:

E = 1 - argmax_ {c} (π mc)

di mana π mc mewakili pecahan data latihan di rantau R_m yang tergolong dalam kelas c.

2 - Indeks Gini: Indeks Gini adalah metrik ralat alternatif yang direka untuk menunjukkan bagaimana "tulen" rantau. "Kesucian" dalam kes ini bermaksud berapa banyak data latihan di rantau tertentu kepunyaan kelas tunggal. Sekiranya rantau R_m mengandungi data yang kebanyakannya dari satu kelas c maka nilai Indeks Gini akan kecil:

3 - Cross-Entropy: Alternatif ketiga, yang sama dengan Indeks Gini, dikenali sebagai Cross-Entropy atau Deviance:

Entropi salib akan mengambil nilai berhampiran sifar jika π mc adalah hampir sama dengan 0 atau berhampiran 1. Oleh itu, seperti indeks Gini, entropi salib akan mengambil nilai yang kecil jika nod-m adalah murni. Malah, ternyata bahawa indeks Gini dan entropi salib agak sama secara numerik.

Apabila membina pokok klasifikasi, sama ada indeks Gini atau entropi rentas biasanya digunakan untuk menilai kualiti perpecahan tertentu, kerana mereka lebih sensitif terhadap kesucian nod daripada kadar kesilapan klasifikasi. Mana-mana daripada 3 pendekatan ini mungkin digunakan semasa pemangkasan pokok itu, tetapi kadar ralat pengelasan adalah lebih baik jika ketepatan ramalan pokok yang dipangkas akhir adalah matlamat.

Pelaksanaan Dari Scratch

Mari kita jalankan algoritma bangunan bangunan keputusan, dengan semua butirannya yang baik. Untuk membina pokok keputusan, kita perlu membuat keputusan awal pada dataset untuk menentukan ciri yang digunakan untuk memecah data. Untuk menentukan ini, kita mesti mencuba setiap ciri dan ukuran yang berpecah akan memberi kita hasil yang terbaik. Selepas itu, kami akan memisahkan set data kepada subset. Subset kemudian akan melintasi cawangan nod keputusan pertama. Sekiranya data pada cawangan adalah kelas yang sama, maka kita telah mengelaskannya dengan betul dan tidak perlu terus membelahnya. Jika data tidak sama, maka kita perlu mengulangi proses pemisahan pada subset ini. Keputusan untuk membahagikan subset ini dilakukan dengan cara yang sama seperti dataset asal, dan kami mengulangi proses ini sehingga kami telah diklasifikasikan semua data.

Bagaimanakah kita memisahkan dataset kita? Salah satu cara untuk mengatur messiness ini adalah untuk mengukur maklumat. Menggunakan teori maklumat, kita boleh mengukur maklumat sebelum dan selepas perpecahan. Perubahan dalam maklumat sebelum dan selepas pemisahan dikenali sebagai keuntungan maklumat. Apabila kita tahu bagaimana untuk mengira keuntungan maklumat, kita boleh memisahkan data kami di setiap ciri untuk melihat pembahagian yang memberikan kita mendapatkan maklumat tertinggi. Perpecahan dengan keuntungan maklumat tertinggi adalah pilihan terbaik kami.

Untuk mengira keuntungan maklumat, kita boleh menggunakan Shannon Entropy, yang merupakan nilai yang diharapkan dari semua maklumat semua nilai yang mungkin di dalam kelas kami. Mari lihat kod Python untuknya:

Seperti yang dapat anda lihat, pertama kita mengira kiraan jumlah contoh dalam dataset. Kemudian kami membuat kamus yang kekuncinya adalah nilai dalam lajur akhir. Sekiranya kunci tidak ditemui sebelum ini, satu akan dibuat. Untuk setiap kunci, kita menjejaki berapa kali label ini berlaku. Akhir sekali, kami menggunakan kekerapan semua label yang berlainan untuk mengira kebarangkalian label tersebut. Kebarangkalian ini digunakan untuk mengira entropi Shannon, dan kita jumlahnya untuk semua label.

Selepas mencari cara untuk mengukur entropi dataset, kita perlu memisahkan dataset, mengukur entropi pada set berpecah, dan melihat sama ada pemisahan itu adalah perkara yang betul untuk dilakukan. Berikut adalah kod untuk berbuat demikian:

Kod ini mengambil 3 input: data yang akan dipisahkan, ciri yang akan dipisahkan, dan nilai ciri untuk dikembalikan. Kami membuat senarai baru pada permulaan setiap kali kerana kami akan memanggil fungsi ini beberapa kali pada dataset yang sama dan kami tidak mahu set data asal diubah. Dataset kami adalah senarai senarai; seperti yang kita lelapkan ke atas setiap item dalam senarai dan jika ia mengandungi nilai yang kami cari, kami akan menambahkannya ke senarai yang baru kami buat. Di dalam kenyataan jika, kami memotong ciri yang kami berpecah.

Sekarang, kami akan menggabungkan 2 fungsi: ShannonEntropy dan splitDataset untuk menembusi dataset dan memutuskan ciri yang terbaik untuk berpecah.

Mari kita segera mengkaji kod:

  • Kami mengira entropi Shannon keseluruhan dataset sebelum pemisahan apa pun telah berlaku dan memberikan nilai kepada variableEntropy yang berubah-ubah.
  • 1 untuk gelung gelung ke atas semua ciri dalam data kami. Kami menggunakan pemahaman senarai untuk membuat senarai (featList) semua entri i-th dalam data atau semua nilai yang mungkin terdapat dalam data.
  • Seterusnya, kami membuat set baru dari senarai untuk mendapatkan nilai unik (unikVal).
  • Kemudian, kita melangkaui semua nilai unik ciri ini dan memecah data untuk setiap ciri (subData). Entropi baru dikira (newEntropy) dan disimpulkan untuk semua nilai unik ciri tersebut. Keuntungan maklumat (infoGain) adalah pengurangan entropi (baseEntropy - newEntropy).
  • Akhir sekali, kami membandingkan keuntungan maklumat di antara semua ciri dan mengembalikan indeks ciri terbaik untuk berpecah (bestFeature).

Sekarang kita dapat mengukur bagaimana mengorganisasikan dataset dan kita boleh memisahkan data, tiba masanya untuk meletakkan semua ini bersama-sama dan membina pokok keputusan. Dari dataset, kita berpecahnya berdasarkan atribut terbaik untuk berpecah. Sekali berpecah, data akan melintasi cabang-cabang pokok ke nod lain. Nod ini akan memisahkan data sekali lagi. Kami akan menggunakan rekursi untuk mengendalikan ini.

Kami hanya akan berhenti di bawah syarat-syarat berikut: (1) Hilangkan atribut untuk berpecah atau (2) semua keadaan dalam cawangan adalah kelas yang sama. Jika semua keadaan mempunyai kelas yang sama, maka kami akan membuat simpul daun. Mana-mana data yang mencapai nod daun ini dianggap tergolong dalam kelas nod daun tersebut.

Berikut adalah kod untuk membina pokok keputusan kami:

Kod kami mengambil 2 input: data dan senarai label:

  • Kami mula-mula membuat senarai semua label kelas dalam dataset dan memanggil kelas ini. Keadaan berhenti pertama ialah jika semua label kelas adalah sama, maka kami mengembalikan label ini. Keadaan berhenti kedua adalah kes apabila tidak ada lagi ciri untuk berpecah. Jika kita tidak memenuhi syarat-syarat berhenti, maka kita menggunakan fungsi selectBestFeatureToSplit untuk memilih ciri yang terbaik.
  • Untuk membuat pokok itu, kami akan menyimpannya dalam kamus (myTree). Kemudian kita mendapatkan semua nilai unik dari dataset untuk ciri yang dipilih (bestFeat). Kod nilai unik menggunakan set (unikVal).
  • Akhirnya, kita melelaras ke atas semua nilai unik dari ciri yang dipilih dan membuat panggilan balik createTree () bagi setiap pembahagian dataset. Nilai ini dimasukkan ke dalam kamus myTree, jadi kami mempunyai banyak kamus bersarang yang mewakili pokok kami.

Pelaksanaan Melalui Scikit-Learn

Sekarang kita tahu bagaimana untuk melaksanakan algoritma dari awal, mari kita gunakan scikit-learn. Khususnya, kami akan menggunakan kelas DecisionTreeClassifier. Bekerja dengan dataset iris, kami mula-mula mengimport data dan membahagikannya ke dalam latihan dan bahagian ujian. Kemudian kami membina model menggunakan tetapan lalai sepenuhnya membangunkan pokok (tumbuh pokok sehingga semua daun adalah tulen). Kami membetulkan random_state di dalam pokok itu, yang digunakan untuk memecahkan tali dalaman:

Menjalankan model harus memberi kita ketepatan set ujian sebanyak 95%, yang bermakna model meramalkan kelas dengan betul untuk 95% sampel dalam dataset ujian.

Kekuatan dan kelemahan

Kelebihan utama menggunakan pokok keputusan adalah bahawa mereka secara intuitif sangat mudah dijelaskan. Mereka cerminan pengambilan keputusan manusia berbanding pendekatan regresi dan klasifikasi yang lain. Mereka boleh dipaparkan secara grafik, dan mereka boleh mengendalikan peramal kualitinya dengan mudah tanpa perlu membuat pembolehubah dummy.

Satu lagi kelebihan yang besar ialah algoritma-algoritma yang benar-benar tidak mencolok data. Memandangkan setiap ciri diproses secara berasingan, dan kemungkinan pecahan data tidak bergantung kepada skala, tiada pra-pemprosesan seperti normalisasi atau standardisasi ciri diperlukan untuk algoritma pokok keputusan. Secara khusus, pokok keputusan berfungsi dengan baik apabila kita mempunyai ciri-ciri yang berada pada skala yang sama sekali berbeza, atau campuran ciri binari dan berterusan.

Walau bagaimanapun, pokok keputusan umumnya tidak mempunyai tahap ketepatan ramalan yang sama seperti pendekatan lain, kerana mereka tidak begitu teguh. Perubahan kecil dalam data boleh menyebabkan perubahan besar pada pokok akhir yang dianggarkan. Walaupun dengan menggunakan pra-pemangkasan, mereka cenderung untuk mendapatkan kelebihan dan memberikan prestasi umum yang tidak seimbang. Oleh itu, dalam kebanyakan aplikasi, dengan mengagregatkan banyak pokok keputusan, menggunakan kaedah seperti pembalakan, hutan secara rawak, dan meningkatkan, prestasi ramalan keputusan pokok boleh dipertingkatkan dengan ketara.

Sumber Rujukan:

  • Pengenalan Pembelajaran Statistik oleh Gareth James, Daniela Witten, Trevor Hastie, dan Robert Tibshirani (2014)
  • Pembelajaran Mesin Dalam Tindakan oleh Peter Harrington (2012)
  • Pengenalan kepada Pembelajaran Mesin dengan Python oleh Sarah Guido dan Andreas Muller (2016)

- -

Sekiranya anda menikmati sekeping ini, saya akan menyukainya jika anda menekan butang 'clap' supaya orang lain tersandung. Anda boleh mencari kod saya sendiri di GitHub, dan lebih banyak tulisan dan projek saya di https://jameskle.com/. Anda juga boleh mengikuti saya di Twitter, e-mel saya secara langsung atau cari saya di LinkedIn.