Get best of the week

Entropi: bagaimana Pohon Keputusan membuat keputusan

Terjemahan artikel disiapkan sebelum dimulainya kursus Pembelajaran Mesin .



Anda adalah Spesialis Ilmu Data yang saat ini mengikuti jalur pembelajaran. Dan Anda telah datang jauh sejak Anda menulis baris kode pertama Anda dengan Python atau R. Anda tahu Scikit-Belajar seperti bagian belakang tangan Anda. Sekarang Anda lebih banyak duduk di Kaggle daripada di Facebook. Anda bukan orang baru dalam menciptakan hutan acak yang memukau dan model ensemble lainnya dari pohon keputusan yang melakukan pekerjaan dengan sangat baik. Namun demikian, Anda tahu bahwa Anda tidak akan mencapai apa pun jika Anda tidak berkembang secara komprehensif. Anda ingin menggali lebih dalam dan memahami seluk-beluk dan konsep yang mendasari model pembelajaran mesin yang populer. Saya juga.

Hari ini saya akan berbicara tentang konsep entropi - salah satu topik paling penting dalam statistik, dan kemudian kita akan berbicara tentang konsep Penguatan Informasi (perolehan informasi) dan mencari tahu mengapa konsep dasar ini membentuk dasar bagaimana pohon keputusan dibangun dari data yang diperoleh.

Baik. Sekarang mari kita melampaui.

Apa itu entropi? Dalam istilah sederhana, entropi tidak lain adalah ukuran kelainan. (Ini juga dapat dianggap sebagai ukuran kemurnian, dan segera Anda akan melihat mengapa. Tapi saya lebih suka kekacauan karena kedengarannya lebih keren.)

Rumus matematika entropi adalah sebagai berikut:


Entropi. Kadang-kadang ditulis sebagai H.

Di sini p i adalah probabilitas frekuensi elemen / kelas i dari data kami. Untuk kesederhanaan, anggaplah kita hanya memiliki dua kelas: positif dan negatif. Maka saya akan mengambil nilai "+" atau "-". Jika kami memiliki total 100 poin dalam dataset kami, 30 di antaranya milik kelas positif dan 70 milik negatif, maka p + akan menjadi 3/10, dan p- akan menjadi 7/10. Semuanya sederhana di sini.

Jika saya menghitung entropi kelas dari contoh ini, maka inilah yang saya dapatkan dengan menggunakan rumus di atas:



Entropi adalah sekitar 0,88. Nilai ini dianggap cukup tinggi, yaitu, kita memiliki tingkat entropi atau gangguan yang tinggi (yaitu nilai kemurnian yang rendah). Entropi diukur dalam rentang dari 0 hingga 1. Bergantung pada jumlah kelas dalam dataset Anda, nilai entropi dapat berubah menjadi lebih dari 1, tetapi itu akan berarti sama dengan tingkat gangguan yang sangat tinggi. Untuk mempermudah penjelasan, dalam artikel hari ini kita akan memiliki entropi mulai dari 0 hingga 1.

Lihatlah tabel di bawah ini.



Pada sumbu X, jumlah titik dari kelas positif di setiap lingkaran tercermin, dan pada sumbu Y, entropi yang sesuai. Anda dapat segera melihat bentuk-U terbalik dari grafik. Entropi akan menjadi yang terkecil pada ekstrema ketika tidak ada elemen positif dalam lingkaran pada prinsipnya, atau ketika hanya ada elemen positif di dalamnya. Yaitu, ketika elemen identik dalam lingkaran, kelainan akan menjadi 0. Entropi akan menjadi tertinggi di tengah grafik, di mana elemen positif dan negatif akan didistribusikan secara merata di dalam lingkaran. Di sini entropi atau gangguan terbesar akan tercapai, karena tidak akan ada unsur dominan.

Apakah ada alasan bahwa entropi diukur menggunakan logaritma basis 2, atau mengapa entropi diukur antara 0 dan 1, dan tidak dalam rentang yang berbeda? Tidak, tidak ada alasan. Ini hanya metrik. Tidak begitu penting untuk memahami mengapa ini terjadi. Penting untuk mengetahui bagaimana apa yang kita dapatkan di atas dihitung dan cara kerjanya. Entropi adalah ukuran kebingungan atau ketidakpastian, dan tujuan model pembelajaran mesin dan spesialis Ilmu Data secara umum adalah untuk mengurangi ketidakpastian ini.

Sekarang kita tahu bagaimana kekacauan diukur. Selanjutnya, kita membutuhkan nilai untuk mengukur pengurangan gangguan ini dalam informasi tambahan (atribut / variabel independen) dari variabel target / kelas. Di sinilah Gain Informasi atau Gain Informasi mulai berlaku. Dari sudut pandang matematika, dapat ditulis sebagai berikut:



Kami cukup mengurangi entropi Y dari X, dari entropi Y, untuk menghitung penurunan ketidakpastian tentang Y, asalkan ada informasi tentang X tentang Y. Semakin kuat ketidakpastian menurun, semakin banyak informasi dapat diperoleh dari Y tentang X.

Mari kita lihat contoh sederhana dari tabel kontingensi sehingga lebih dekat ke pertanyaan tentang bagaimana pohon keputusan menggunakan entropi dan informasi memperoleh untuk memutuskan dasar apa untuk mematahkan simpul dalam proses pembelajaran data.

Contoh: Tabel konjugasi



Di sini, variabel target kami adalah Liability , yang hanya dapat mengambil dua nilai: "Normal" dan "High". Kami juga hanya memiliki satu tanda, yang disebut Peringkat Kredit, itu mendistribusikan nilai-nilai ke dalam tiga kategori: "Sangat Baik" , "Baik" dan "Buruk" . Sebanyak 14 pengamatan dilakukan. 7 dari mereka termasuk kelas Kewajiban Normal , dan 7 lainnya dari kelas Kewajiban Tinggi . Ini adalah divisi itu sendiri.

Jika kita melihat jumlah total nilai di baris pertama, kita akan melihat bahwa kita memiliki 4 pengamatan dengan nilai Excellent berdasarkan Credit Rating . Selain itu, saya bahkan dapat mengatakan bahwa variabel target saya rusak oleh Peringkat Kredit “Sangat Bagus” . Di antara pengamatan dengan nilai "Sangat Baik" berdasarkan atributPeringkat Kredit , ada 3 yang termasuk dalam kelas Kewajiban Normal dan 1 yang termasuk dalam kelas Kewajiban Tinggi . Demikian pula, saya dapat menghitung hasil yang sama untuk nilai-nilai Peringkat Kredit lainnya dari tabel kontingensi.

Misalnya, saya menggunakan tabel kontingensi di atas untuk menghitung secara independen entropi dari variabel target kami, dan kemudian menghitung entropinya, dengan mempertimbangkan informasi tambahan akun dari atribut Credit Rating . Jadi saya bisa menghitung berapa banyak informasi tambahan yang akan diberikan peringkat kredit saya untuk variabel target pertanggungjawaban .

Jadi mari kita mulai.



Entropi dari variabel target kami adalah 1, yang berarti kekacauan maksimum karena pemerataan elemen antara "Normal" dan "Tinggi" . Langkah selanjutnya adalah menghitung entropi dari variabel target Kewajiban , dengan mempertimbangkan informasi tambahan dari Peringkat Kredit . Untuk melakukan ini, kami menghitung entropi Kewajiban untuk setiap nilai Peringkat Kredit dan menambahkannya menggunakan rasio observasi tertimbang rata-rata untuk setiap nilai. Mengapa kita menggunakan rata-rata tertimbang akan menjadi lebih jelas ketika kita berbicara tentang pohon keputusan.



Kami memperoleh entropi dari variabel target kami dengan atribut Peringkat Kredit. Sekarang kita dapat menghitung keuntungan Kewajiban informasi dari Pemeringkatan Kredit untuk memahami seberapa informatif fitur ini.



Mengetahui Peringkat Kredit telah membantu kami mengurangi ketidakpastian variabel target Kewajiban kami.. Bukankah itu pertanda baik yang seharusnya berhasil? Beri kami informasi tentang variabel target? Nah, untuk alasan inilah, pohon keputusan menggunakan entropi dan keuntungan informasi. Mereka menentukan dengan kriteria apa untuk memecah node menjadi cabang, untuk mendekati variabel target dengan setiap partisi berikutnya, dan juga untuk memahami kapan konstruksi pohon perlu diselesaikan! (selain hyperparameter seperti kedalaman maksimum, tentu saja). Mari kita lihat bagaimana ini semua bekerja dalam contoh berikut menggunakan pohon keputusan.

Contoh: Pohon Keputusan

Mari kita lihat contoh membangun pohon keputusan, dengan tujuan untuk memprediksi apakah kredit seseorang akan dihapuskan atau tidak. Populasi akan menjadi 30 salinan. 16 akan menjadi bagian dari kelas penghapusan , dan 14 lainnya akan menjadi miliknya"Non-write-off" . Kami akan memiliki dua tanda, yaitu "Saldo" , yang dapat mengambil dua nilai: "<50K" atau "> 50K", dan "Tempat Tinggal" , yang mengambil tiga nilai: "SENDIRI" , "SEWA" atau "LAIN" . Saya akan mendemonstrasikan bagaimana algoritma pohon keputusan akan memutuskan atribut mana yang harus didobrak lebih dulu dan atribut mana yang akan lebih informatif, yaitu, yang terbaik menghilangkan ketidakpastian variabel target menggunakan konsep entropi dan informasi gain.

Gejala 1: Saldo



Di Sini lingkaran milik kelas "penghapusan" , dan bintang-bintang sesuai dengan kelas "penghapusan" . Mempartisi Root Induk berdasarkan AtributSaldo akan memberi kita 2 titik pewaris. Di simpul kiri akan ada 13 pengamatan, di mana 12/13 (probabilitas 0,92) pengamatan dari kelas "write-off" , dan hanya 1/13 (probabilitas 0,08) pengamatan dari kelas "non-write-off" . Di simpul kanan akan ada 17 dari 30 pengamatan, di mana 13/17 (probabilitas 0,76) pengamatan dari kelas "write-off" dan 4/17 (probabilitas 0,24) pengamatan dari kelas "non-write-off" .

Mari kita hitung entropi root dan lihat seberapa banyak pohon dapat mengurangi ketidakpastian dengan menggunakan partisi berdasarkan Balance .



Perpecahan berdasarkan Balance akan memberikan keuntungan informasi sebesar 0,37. Mari kita hitung sama untuk tanda Residencedan bandingkan hasilnya.

Gejala 2: Residence



Membagi pohon berdasarkan Residence akan memberi Anda 3 node pewaris. Node keturunan kiri akan menerima 8 pengamatan, di mana 7/8 (probabilitas 0,88) pengamatan dari kelas write-off dan hanya 1/8 (probabilitas 0,12) pengamatan dari kelas non-write-off . Node penerus rata-rata akan menerima 10 pengamatan, di mana 4/10 (probabilitas 0,4) pengamatan dari kelas write-off dan 6/10 (probabilitas 0,6) pengamatan dari kelas non-write-off . Ahli waris kanan akan menerima 12 pengamatan, di mana 5/12 (probabilitas 0,42) pengamatan dari kelas menulis dan 7/12 (probabilitas 0,58) pengamatan dari kelas non-menulis-off. Kita sudah mengetahui entropi dari simpul induk, jadi kita cukup menghitung entropi setelah partisi untuk memahami keuntungan informasi dari atribut Residence .



Keuntungan informasi dari atribut Balance hampir 3 kali lebih banyak daripada dari Residence ! Jika Anda melihat grafik lagi, Anda akan melihat bahwa partisi berdasarkan Balance akan memberikan node turunan yang lebih bersih daripada menurut Residence . Namun, simpul paling kiri di Residence juga cukup bersih, tetapi di sinilah rata-rata tertimbang ikut bermain. Terlepas dari kenyataan bahwa node bersih, ia memiliki jumlah pengamatan paling sedikit, dan hasilnya hilang dalam perhitungan ulang umum dan perhitungan total entropi menurut Residence. Ini penting karena kami mencari konten informasi umum atribut dan tidak ingin hasil akhir terdistorsi oleh nilai atribut yang langka.

Atribut Balance itu sendiri memberikan lebih banyak informasi tentang variabel target daripada Residence . Dengan demikian, entropi dari variabel target kami berkurang. Algoritma decision tree menggunakan hasil ini untuk membuat pemisahan pertama menurut Balanceuntuk kemudian memutuskan atas dasar apa untuk memecah node berikut. Di dunia nyata, ketika ada lebih dari dua fitur, gangguan pertama terjadi sesuai dengan fitur paling informatif, dan kemudian, dengan setiap pemecahan berikutnya, perolehan informasi akan dihitung ulang untuk setiap fitur tambahan, karena itu tidak akan sama dengan perolehan informasi dari setiap fitur secara individual. Entropi dan perolehan informasi harus dihitung setelah satu atau beberapa partisi terjadi, yang akan mempengaruhi hasil akhir. Pohon keputusan akan mengulangi proses ini saat tumbuh di kedalaman, hingga mencapai kedalaman tertentu atau semacam pemisahan mengarah ke keuntungan informasi yang lebih tinggi di luar batas tertentu, yang juga dapat ditetapkan sebagai hyperparameter!

Itu saja! Sekarang Anda tahu entropi, perolehan informasi, dan bagaimana mereka dihitung. Sekarang Anda mengerti bagaimana pohon keputusan, dengan sendirinya atau sebagai bagian dari ansambel, membuat keputusan tentang urutan terbaik partisi berdasarkan atribut dan memutuskan kapan harus berhenti ketika mempelajari data yang tersedia. Nah, jika Anda harus menjelaskan kepada seseorang bagaimana pohon keputusan bekerja, saya harap Anda akan cukup mengatasi tugas ini.

Saya harap Anda telah mempelajari sesuatu yang berguna untuk diri Anda sendiri dari artikel ini. Jika saya melewatkan sesuatu atau mengekspresikan diri saya secara tidak akurat, tuliskan kepada saya tentang hal itu. Saya akan sangat berterima kasih kepada Anda! Terima kasih


Pelajari lebih lanjut tentang kursus.

More articles:


All Articles