Entropiya va qaror qabul qilish daraxtlari

Entropiya va qaror qabul qilish daraxtlari
Qaror qabul qilish daraxtlari nafaqat ma'lumotlarni tasniflash, balki nima uchun u yoki bu ob'ekt biron bir sinfga tegishli ekanligini tushuntirish zarur bo'lgan hollarda qulay vositadir.
Keling, avval rasmning to'liqligi uchun entropiyaning tabiati va uning ba'zi xususiyatlarini ko'rib chiqaylik. Keyin, oddiy misoldan foydalanib, entropiyadan foydalanish tasniflagichlarni yaratishda qanday yordam berishini ko'rib chiqamiz. Shundan so'ng, umumiy ma'noda biz qaror qabul qilish daraxtini qurish algoritmini va uning xususiyatlarini shakllantiramiz.
Kombinator entropiyasi
Ko'p rangli to'plarni ko'rib chiqing: 2 qizil, 5 yashil va 3 sariq. Ularni aralashtiring va ketma-ket joylashtiring. Keling, ushbu operatsiyani almashtirish deb ataymiz:

Keling, bir xil rangdagi to'plarni ajratib bo'lmasligini hisobga olib, turli xil almashtirishlar sonini hisoblaymiz
Agar har bir to'p o'ziga xos rangga ega bo'lsa, unda almashtirishlar soni 10 ta bo'lar edi!, lekin agar bir xil rangdagi ikkita to'p almashtirilsa, yangi almashtirish ishlamaydi. Shunday qilib, siz 5 ni chiqarib tashlashingiz kerak! yashil to'plarni bir-biriga almashtirish (shuningdek, 3! sariq va 2! qizil). Shuning uchun, bu holda, echim bo'ladi:

Multinomial koeffitsient ushbu muammoning umumiy holatida permutatsiyalar sonini hisoblash imkonini beradi

(Ni-har bir rangdagi bir xil to'plar soni).
Barcha almashtirishlarni 0 dan (W — 1) gacha raqamlar bilan raqamlash mumkin. Shuning uchun, log2(W) bitdan olingan satr har bir almashtirishni noyob tarzda kodlaydi.

Permutatsiya n to'pdan iborat bo'lganligi sababli, bitta almashtirish elementiga to'g'ri keladigan bitlarning o'rtacha soni quyidagicha ifodalanishi mumkin:

Ushbu miqdor kombinatorial entropiya deb ataladi:
To'plam qanchalik bir xil bo'lsa (bir xil rangdagi to'plar ustunlik qiladi)-uning kombinatorial entropiyasi shunchalik kichik bo'ladi va aksincha — to'plamdagi turli xil elementlar qancha ko'p bo'lsa, uning entropiyasi shunchalik yuqori bo'ladi.

Shannon Entropiyasi

Keling, entropiya uchun yuqorida tavsiflangan ifodani batafsil ko'rib chiqaylik:

Logarifmlarning xususiyatlarini hisobga olgan holda biz formulani quyidagicha o'zgartiramiz:

Aytaylik, to'plar soni Stirling formulasidan foydalanish uchun etarlicha katta:
Stirling formulasini qo'llash orqali biz olamiz:


(bu erda k — tabiiy logarifmlarga o'tish koeffitsienti)

Buni hisobga olgan holda

 ifodani o'zgartirish mumkin:


To'plarning umumiy soni N va i-chi rangdagi to'plar soni Ni bo'lganligi sababli, tasodifiy tanlangan to'pning aynan shu rangga ega bo'lish ehtimoli: . Shunga asoslanib, entropiya formulasi quyidagicha bo'ladi:

Ushbu ifoda Shenonne entropiyasidir.
Keyinchalik ehtiyotkorlik bilan xulosa qilish orqali Shenonne entropiyasi kombinatorial entropiya uchun chegara ekanligini ko'rsatish mumkin, shuning uchun uning qiymati har doim kombinatorial entropiya qiymatidan biroz kattaroqdir.

Ikki entropiyani taqqoslash quyidagi rasmda keltirilgan bo'lib, u ikki turdagi ob'ektlarni o'z ichiga olgan to'plamlar uchun hisoblab chiqilgan — A va B (har bir to'plamdagi elementlarning umumiy soni — 100):

Termodinamika

Entropiya uchun shunga o'xshash iboralarni termodinamikada olish mumkin:

Moddalarning mikroskopik xususiyatlaridan kelib chiqqan holda: statistik termodinamikaning postulatlariga tayanib (bu holda ular turli xil energiya holatlarida bo'lgan ajratib bo'lmaydigan zarralar bilan ishlaydi).
Moddalarning makroskopik xususiyatlariga asoslanib: issiqlik mashinalarining ishlashini tahlil qilish orqali.
Entropiya tushunchasi termodinamikada asosiy rol o'ynaydi, termodinamikaning ikkinchi printsipini shakllantirishda paydo bo'ladi: agar izolyatsiya qilingan makroskopik tizim muvozanatsiz holatda bo'lsa, unda uning entropiyaning katta qiymatiga ega bo'lgan holatga o'tish ehtimoli katta:

Maksvell Jinlari

1867 yilda termodinamikaning ikkinchi boshlanishining statistik xususiyatini ta'kidlash uchun Jeyms Maksvell fikr tajribasini taklif qildi: "keling, ma'lum bir haroratdagi gaz bilan to'ldirilgan idishni tasavvur qilaylik, idish Demon ochadigan damperli septum bilan bo'linadi.tez zarralarni bir tomonga, sekin zarralarni esa boshqa tomonga o'tkazish uchun. Shuning uchun, bir muncha vaqt o'tgach, tez zarralar tomirning bir qismida, ikkinchisida esa sekin zarralar to'planadi. Shunday qilib, termodinamikaning ikkinchi printsipidan farqli o'laroq, Maksvell jin yopiq tizimning entropiyasini kamaytirishi mumkin":

Keyinchalik, Leo Szilard paradoksni hal qildi, ammo bu munozara ushbu maqola doirasidan biroz tashqarida.

Maksvell Jin = = Klassifikator

Agar "tez" va "sekin" zarralar o'rniga turli sinflarga tegishli ob'ektlarni ko'rib chiqsak, unda Maksvell jinini o'ziga xos klassifikator sifatida ko'rish mumkin.

Paradoksning o'zi o'qitish algoritmini taklif qiladi: siz qoidalarni (predikatlarni) topishingiz kerak, ular asosida entropiyaning o'rtacha qiymati pasayadigan tarzda o'quv ma'lumotlar to'plamini buzishingiz kerak. Ma'lumotlar to'plamini entropiyaning pasayishiga olib keladigan qismlarga bo'lish jarayonini ma'lumot ishlab chiqarish deb hisoblash mumkin.
Dastlabki ma'lumotlar to'plamini ma'lum bir predikat bo'yicha ikki qismga bo'lish orqali har bir kichik to'plamning entropiyasini hisoblash mumkin, shundan so'ng entropiyaning o'rtacha qiymatini hisoblash mumkin — agar u asl to'plamning entropiyasidan kichikroq bo'lsa, unda predikat ma'lumotlar haqida ba'zi umumlashtiruvchi ma'lumotlarni o'z ichiga oladi.

Masalan, ikki rangli to'plar to'plamini ko'rib chiqing,

Rasmdan ko'rinib turibdiki, agar siz to'plamni ikki qismga ajratsangiz, agar bir qism x ≤ 12 koordinatali barcha elementlarni o'z ichiga olsa, ikkinchi qism x \ u003e 12 bo'lgan barcha elementlarni o'z ichiga olsa, u holda o'rtacha entropiya ∆s da asl nusxadan kam bo'ladi. bu shuni anglatadiki, ushbu predikat ma'lumotlar haqida ba'zi ma'lumotlarni umumlashtiradi (x \ u003e 12 bilan — deyarli barcha to'plar sariq ekanligini payqash oson).

Agar siz nisbatan oddiy predikatlardan foydalansangiz ("ko'proq"," kamroq"," teng " va boshqalar), unda to'liq Klassifikatorni yaratish uchun bitta qoida etarli bo'lmaydi. Ammo predikatlarni topish tartibi har bir kichik to'plam uchun rekursiv ravishda takrorlanishi mumkin. To'xtash mezoni entropiyaning nol (yoki juda kichik) qiymatidir. Natijada qaror qabul qilish daraxti deb ataladigan daraxtga o'xshash shartlar to'plami paydo bo'ladi:

Qaror qabul qilish daraxtining barglari sinflardir. Qaror qabul qilish daraxti yordamida ob'ektni tasniflash uchun siz daraxtga ketma-ket tushishingiz kerak (tasniflangan ob'ektga qo'llaniladigan predikatlar qiymatiga qarab yo'nalishni tanlash). Daraxt ildizidan barggacha bo'lgan yo'lni nima uchun u yoki bu ob'ekt biron bir sinfga tegishli ekanligini tushuntirish sifatida talqin qilish mumkin.

Ko'rib chiqilgan misolda, soddalashtirish uchun barcha ob'ektlar faqat bitta atribut bilan tavsiflanadi — x koordinatasi, ammo bir nechta atributlarga ega ob'ektlarga aynan bir xil yondashuvni qo'llash mumkin.

Shuningdek, ob'ekt atributlari qiymatlariga cheklovlar qo'yilmaydi-ular ham kategorik, ham raqamli yoki mantiqiy tabiatga ega bo'lishi mumkin. Faqat atributlar qiymatlarini to'g'ri qayta ishlashga qodir bo'lgan predikatlarni aniqlash kerak (masalan, mantiqiy qiymatlarga ega atributlar uchun "ko'proq" yoki "kamroq" predikatlardan foydalanish mantiqiy emas).

Qaror daraxtini yaratish algoritmi

Umuman olganda, algoritm

s0 = dastlabki to'plamning entropiyasini hisoblang

Agar s0 == 0 bo'lsa:

Asl to'plamning barcha ob'ektlari bir xil sinfga tegishli
Biz bu sinfni daraxt bargi sifatida saqlaymiz

Agar s0 != 0 bo’lsa:

Biz boshlang'ich to'plamni buzadigan predikatni qidirmoqdamiz shunday qilib entropiyaning o'rtacha qiymati kamayadi
Topilgan predikat qaror qabul qilish daraxtining bir qismidir, biz uni saqlaymiz

Predikatga muvofiq asl to'plamni kichik to'plamlarga ajratamiz

Biz ushbu protsedurani har bir kichik to'plam uchun rekursiv ravishda takrorlaymiz
"Predikat izlash "nimani anglatadi?
Shu bilan bir qatorda, dastlabki to'plamning har bir elementi asosida to'plamni ikki qismga ajratadigan predikat tuzilishi mumkin deb taxmin qilishimiz mumkin. Shuning uchun algoritmni qayta tuzish mumkin:

s0 = asl to'plamning entropiyasini hisoblang

Agar s0 == 0 bo'lsa:

Asl to'plamning barcha ob'ektlari bir xil sinfga tegishli
Biz bu sinfni daraxt bargi sifatida saqlaymiz

Agar s0 != 0 bo’sa:

Biz asl to'plamning barcha elementlarini saralaymiz:
Har bir element asosida biz dastlabki to'plamni ikkita kichik to'plamga ajratadigan predikat hosil qilamiz
Entropiyaning o'rtacha qiymatini hisoblang
∆S Ni Hisoblang
Bizni predikat qiziqtiradi, eng katta qiymat ∆S
Topilgan predikat qaror qabul qilish daraxtining bir qismidir, biz uni saqlaymiz

Predikatga muvofiq asl to'plamni kichik to'plamlarga ajratamiz

Biz ushbu protsedurani har bir kichik to'plam uchun rekursiv ravishda takrorlaymiz.

Qanday qilib "to'plamning har bir elementi asosida predikat yaratish" mumkin?
Eng oddiy holatda, faqat atributning qiymatiga tegishli bo'lgan predikatlardan foydalanish mumkin (masalan," x ≥ 12 "yoki" rang == sariq " va boshqalar). Shuning uchun algoritm quyidagi shaklni oladi:
s0 = asl to'plamning entropiyasini hisoblang

Agar s0 == 0 bo'lsa:

Asl to'plamning barcha ob'ektlari bir xil sinfga tegishli
Biz bu sinfni daraxt bargi sifatida saqlaymiz

Agar s0 != 0 bo’lsa:

Biz asl to'plamning barcha elementlarini saralaymiz:
Har bir element uchun biz uning barcha atributlarini saralaymiz:
Har bir atribut asosida biz dastlabki to'plamni ikkita kichik to'plamga ajratadigan predikat hosil qilamiz
Entropiyaning o'rtacha qiymatini hisoblang
∆S Ni Hisoblang
Bizni predikat qiziqtiradi, eng katta qiymat ∆S
Topilgan predikat qaror qabul qilish daraxtining bir qismidir, biz uni saqlaymiz

Predikatga muvofiq asl to'plamni kichik to'plamlarga ajratamiz

Biz ushbu protsedurani har bir kichik to'plam uchun rekursiv ravishda takrorlaymiz

Aslida, agar biz tasniflanadigan ob'ektlarni ko'p o'lchovli kosmosdagi nuqtalar deb hisoblasak, ma'lumotlar to'plamini kichik to'plamlarga ajratadigan predikatlar giperplanlar ekanligini va Klassifikatorni o'qitish tartibi cheklangan hajmlarni izlash ekanligini ko'rishimiz mumkin (umuman, boshqa har qanday klassifikator uchun bo'lgani kabi).

Asosiy afzallik, natijada olingan predikatlarning daraxtga o'xshash tuzilishi bo'lib, u tasniflash natijalarini sharhlashga imkon beradi (garchi uning "ochko'zligi" tufayli tavsiflangan algoritm har doim ham daraxtning optimalligini ta'minlashga imkon bermaydi).

Ta'riflangan algoritmning asoslaridan biri bu daraxt qurishda to'xtash mezonidir. Yuqorida tavsiflangan psevdokodlarda men barcha elementlar bir xil sinfga tegishli bo'lgan to'plamga erishgandan keyingina daraxt qurishni to'xtatdim (entropiya == 0). Ushbu yondashuv qaror qabul qilish daraxtini o'quv ma'lumotlarini tanlashga to'liq moslashtirishga imkon beradi, ammo bu har doim ham amaliy ma'lumotlar bilan samarali emas.

Olingan daraxtlar ansambli (Random forest-ning soddalashtirilgan versiyasi) tasniflanadigan ob'ektni barcha daraxtlar bo'ylab haydash orqali tasniflash uchun ishlatilishi mumkin. Har bir daraxt ob'ektning ma'lum bir sinfga mansubligi uchun "ovoz beradi". Shunday qilib, daraxtlarning qaysi qismi u yoki bu sinfga ovoz berganiga asoslanib, ob'ekt qaysi sinfga tegishli ekanligi haqida xulosa chiqarish mumkin.

Ushbu usul ma'lumotlarning chegara hududlarini etarli darajada qayta ishlashga imkon beradi:

Yagona qaror qabul qilish daraxti butunlay qizil nuqtalarni o'z ichiga olgan hududni tasvirlashini ko'rish mumkin, daraxtlar ansambli esa aylanaga yaqinroq bo'lgan shaklni tasvirlaydi.

Agar tajriba qilish istagi bo'lsa

Men qaror daraxti va tasodifiy o'rmonni taqqoslash uchun kichik dastur yaratdim. Ilovani har safar ishga tushirganingizda, yashil fonda qizil doiraga mos keladigan tasodifiy ma'lumotlar to'plami yaratiladi va dasturni bajarish natijasida yuqoridagi rasm kabi rasm olinadi.

Sizda Java ish vaqti o'rnatilgan bo'lishi kerak

Bu yerdan dec_tree_demo binarini yuklab oling.jar
Ilovani ishga tushirish uchun buyruq satriga yozing: java-jar dec_tree_demo.jar out.png

Github-da manbalar mavjud.

Xulosa o'rniga

Qabul qilish daraxtlari boshqa tasniflash algoritmlarida mavhum og'irliklar va koeffitsientlarni moslashtirishdan charchagan yoki ma'lumotlarni aralash (kategorik) bilan qayta ishlash kerak bo'lgan hollarda yaxshi alternativ hisoblanadi