1-ma’ruza. Berilganlarni intellektual tahliliga kirish

Qarorlar daraxtini qurish
Qarorlar daraxtini qurishda qaysi alomatni birinchi bo‘lib tanlash kerak? Ushbu savolga javob berish uchun alomatlari binar bo‘lgan soddaroq misolni ko‘ramiz.
Entropiya
Mumkin bo‘lgan holatlari N bo‘lgan tizim uchun Shennon entropiyasi quyidagicha hisoblanadi:

bu yerda – tizimning i-holatda bo‘lishining ehtimolligi. Ushbu tushuncha fizikada, axborot nazariyasi va boshqa sohalarda keng qo‘llaniladigan muhim tushunchalardan hisoblanadi. Entropiya tizimdagi xaos darajasini ko‘rsatadi. Entropiya qanchalik yuqori bo‘lsa, tizim shunchalik kam tartiblangan bo‘ladi va aksincha. Ushbu mezon “tanlanmani samarali ajratish” ni shakllantirishga yordam beradi.
Misol.
Entropiyaning daraxt qurishda yaxshi alomatlarni aniqlashga yordam berishini o‘yinchoq misolda – sharcha rangini uning koordinatasi bo‘yicha aniqlashda ko‘ramiz.


3-rasm. Sharcha rangini uning joylashuvi bo‘yicha aniqlash

Tanlanmada 9 ta ko‘k va 11 sariq sharchalar bor. Agar biz tasoddifiy ravishda bitta sharchani olsak у ehtimollik bilan кўк, ehtimollik bilan sariq rangda bo‘ladi. Holat entropiyasi . Lekin, bu qiymat hech nimani bildirmaydi. Endi sharchalarni 12 teng va 12 katta o‘rin bo‘yicha guruhlarga bo‘linganda entropiyaini o‘zgarishini ko‘ramiz.

4-rasm. Sharchalar ketma-ketligini ikkiga bo‘lish.

Birinchi guruhda 13 ta sharcha bo‘lib, uning 8 tasi ko‘k va 5 tasi sariq. Guruh entropiyasi . Ўng tomondagi guruhda 7 ta sharcha bo‘lib, uning 1 tasi ko‘k va 6 tasi sariq. Guruh entropiyasi . Ko‘rinib turibdiki, boshlang‘ich holatga nisbatan guruhlardagi entropiya kamaygan, chap tomondagi guruhda nisbatan ozroq. Entropiya – mazmuni bo‘yicha tizimdagi xaos (yoki noaniqlikning) darajasi bo‘lganligi sababli, entropiyani kamayishi informativlikning oshishini deyiladi. q alomat bo‘yicha (bizning misoldа bu “ ” alomati) tanlanmani bo‘lishda informativlikning oshishi (information gain, IG) ramziy ravishda quyidagicha aniqlanadi

Bu yerda – bo‘lishdan keyingi guruhlar soni, – tanlanmaning alomati – qiymatga ega elementlari soni.



5-rasm. Sharcha rangini aniqlash bo‘yicha qarorlar daraxti.

Bizning holatda bo‘lish natijasida 2 гuruh hosil bo‘ldi ( ) – birida 13 elementlar ( ), ikkinchisida 7 ta ( ). Axborot oshishi

Ko‘rinib turibdiki, sharchalarni “koordinata 12 dan kichik yoki teng” alomati bo‘yicha ikkita guruhga bo‘lish natijasida boshlang‘ichga nisbatan tartiblangan tizimga ega bo‘ldik. Sharchalarni guruhlarga bo‘lishni davom ettiramiz, toki har bir guruhda bir xil rangdagi sharchalar hosil bo‘lmaguncha.
O‘ngdagi guruh uchun qo‘shimcha ravishda “koordinata 18 dan kichik yoki teng” alomat bo‘yicha faqat bitta bo‘lish yetarli bo‘ldi, chap guruhi uchun – yana uchta bo‘lish zarur bo‘ldi. Ko‘rinib turibdiki, bir xil sharchali guruhlar uchun entropiya 0 ga teng ( ).
Xulosa qilib, shuni qayd qilish mumkinki, biz sharchalarni koordinatlari bo‘yicha rangini aniqlab beruvchi qarorlar daraxtini qurdik. Shuni qayd etish kerakki, bunday daraxt yangi obyektlar uchun yomon ishlaydi (sharcha rangini aniqlashda), chunki u boshdan 20 sharchadan tashkil topgan tanlanma uchun ideal ravishda moslashgan (meyoridan ortiq o‘rganish (moslashish) muammosi).