Qarorlar daraxti. 9-ma’ruza

1.

9-ma’ruza.
Qarorlar daraxti

2.

Qarorlar daraxti
Qarorlar daraxti (shuningdek, sinflash daraxti yoki
regressiya daraxti deb ham ataladi) – mashinali o‘rgatishda,
berilganlar tahlilida va statistikada qo‘llaniladigan qarorlarni
qabul qilishning qo‘llab-quvvatlash vositasidir.
Daraxt tuzilishi "tugunlar" va "yaproqlar" dan iborat.
Qaror daraxtining qirralarida ("tugunlarida") maqsad
funksiya bog‘liq bo‘lgan atributlar, "yaproqlarda" maqsad
funksiyaning qiymatlari, boshqa tugunlarda turli holatlarni
ajratadigan atributlar yozilgan. Yangi bir holatni sinflash
uchun daraxtning yaprog‘igacha tushib kelib, mos qiymatni
(natijalarni) berish kerak.

3.

Qarorlar daraxtlarining turlari
Qarorlar daraxtlari ikki asosiy turga bo‘linadi:
• Sinflash daraxti, bashorat qilingan natija – bu
berilganlar tegishli bo‘lgan sinf;
• Regressiya daraxti, bashorat qilingan natijani haqiqiy
son sifatida hisoblash mumkin (masalan, uyning narxi
yoki bemorning kasalxonada bo‘lish muddati).

4.

Qarorlar daraxtining amal qilishi
Umuman olganda qarorlar daraxti – tugunlar va yaproqlar
deb nomlanuvchi ikki turdagi elementlardan tashkil topgan ierarxik
tuzilmali xulosa qoidalarining taqdim etish usulidir.
Eng sodda holatlarda tekshirish natijasida tugunga tushgan
namunalar to‘plami ikkita to‘plam ostiga bo‘linadi, biriga qoida
shartini qanoatlantiruvchi, ikkinchisiga – qanoatlantirmaydigan
namunalar tushadi. Keyinchalik, har bir to‘plam ostiga yana
qoidalar qo‘llaniladi va jarayon rekursiv ravishda, toki algoritmni
to‘xtatish sharti bajarilmaguncha davom ettiriladi. Natijada oxirgi
tugunda tekshirish va to‘plam ostilariga bo‘lish bajarilmaydi va u
yaproq deb e’lon qilinadi.
Sinflash daraxti uchun – bu tugunga mos keluvchi sinf,
regressiya daraxti uchun – yaproqqa mos maqsad
o‘zgaruvchisining modal intervali.

5.

Qarorlar daraxtiga misol
Avtomobil sug‘urtasidagi tavakkalchilik bo‘yicha maslahat beruvchi
qarorlar daraxti

6.

Qarorlar daraxtining usuli afzalliklari:
• tushunish va izohlash oson. Qisqacha tushuntirishdan so‘ng,
odamlar qaror daraxti modelining natijalarini izohlashi
mumkin bo‘ladi;
• berilganlarni tayyorlash talab qilinmaydi. Boshqa usullar
berilganlarni normallashtirishni, fiktiv o‘zgaruvchilarni
qo‘shish va qiymatlari to‘ldirilmagan berilganlarni o‘chirib
tashlashni talab qiladi;
• ham kategoriyali va interval o‘zgaruvchilari bilan ishlash
qobiliyati. Boshqa usullar faqat bitta o‘zgaruvchini turi
mavjud bo‘lgan berilganlar bilan ishlaydi. Masalan,
munosabatlar usuli faqat nominal o‘zgaruvchilarga, neyron
tarmoqlari usuli esa faqat interval shkalasida o‘lchanadigan
o‘zgaruvchilarga nisbatan qo‘llanilishi mumkin;

7.

Qarorlar daraxtining usuli afzalliklari:
• oq quti modelidan foydalanadi. Agar modelda ma’lum bir
holat kuzatilsa, u holda Bul mantiqi yordamida tushuntirish
mumkin. "qora quti" ning misoli sun’iy neyron tarmoq
bo‘lishi mumkin, chunki ushbu modelning natijalarini
tushuntirish qiyin;
• statistik testlar yordamida modelni baholashga imkon beradi.
Bu modelning ishonchliligini baholashga imkon beradi;
• bu ishonchli usul. Usul modeldagi dastlabki taxminlar
buzilgan bo‘lsa ham yaxshi ishlaydi;
• maxsus tayyorlangan amallarni qo‘llamagan holda katta
hajmdagi berilganlar bilan ishlashga imkon beradi. Ushbu
usul katta berilganlar bazalari bilan ishlash uchun maxsus
jihozlarni talab qilmaydi.

8.

Qarorlar daraxtining usulining kamchiliklari:
• optimal qarorlar daraxti muammosi, hatto oddiy muammolar
uchun ham optimallikning ba’zi jihatlari nuqtai nazaridan NPto‘liq masaladir. Shunday qilib, qarorlar daraxti algoritmini
amaliy qo‘llash evristik algoritmlarga, masalan, "ochko‘z"
algoritmiga asoslanadi, bu yerda har bir tugun uchun yagona
maqbul yechim tanlanadi. Bunday algoritmlar umuman
daraxtning optimalligini ta’minlay olmaydi;
• qaror daraxti qurishda berilganlarni to‘liq ifoda yetmaydigan
juda murakkab tuzilmalar yaratilishi mumkin. Ushbu
muammo me’yoridan ortiq o‘rganish deb nomlanadi. Bunga
yo‘l qo‘ymaslik uchun "daraxtning chuqurligini tartibga
solish" usulidan foydalanish kerak;

9.

Qarorlar daraxtining usulining kamchiliklari:
• modelda tushunish qiyin bo‘lgan tushunchalar mavjud,
chunki model ularni murakkab tarzda tasvirlaydi. Ushbu
hodisa XOR, «chetnost» yoki multipleksarlik muammolari
tufayli yuzaga kelishi mumkin.
Bunday holda, biz haddan tashqari darajada katta
daraxtlarga duch kelamiz. Ushbu muammoni hal qilishda bir
nechta yondashuvlar mavjud, masalan, modeldagi
tushunchani o‘zgartirishga urinish (yangi xulosalar chiqarish)
yoki konsepsiyani to‘liq tasvirlaydigan va ifodalaydigan
algoritmlardan (masalan, statistik munosabatlar usuli,
dasturlashning induktiv mantig‘i).

10.

Qarorlar daraxtini qurish
Entropiya. Mumkin bo‘lgan holatlari N bo‘lgan tizim
uchun Shennon entropiyasi quyidagicha hisoblanadi: