Qaror qabul qilish daraxti (tasniflash yoki regressiya daraxti deb ham ataladi) — qaror qabul qilishni qo‘llab-quvvatlash vositasi bo‘lib, u mashinali o‘qitish, ma’lumotlarni tahlil qilish va statistika sohalarida qo‘llaniladi. Daraxt tuzilishi «barglar» va «shoxlar»dan iborat. Qarorlar daraxtining qirralarida («shoxlarida») maqsad funksiyasi bog‘liq bo‘lgan belgilar, «barglarida» esa maqsad funksiyasining qiymatlari ko‘rsatiladi; qolgan tugunlarda holatlarni bir-biridan ajratuvchi belgilar joylashadi. Yangi holatni tasniflash uchun daraxt bo‘ylab barggacha tushib, unga mos qiymatni aniqlash kerak.
Bunday qarorlar daraxtlari ma’lumotlarni intellektual tahlil qilishda keng qo‘llaniladi. Maqsad — model yaratish bo‘lib, u bir nechta kirish o‘zgaruvchisi asosida maqsad o‘zgaruvchisining qiymatini bashorat qiladi.

Har bir barg ildizdan daraxt qirralari bo‘ylab barggacha o‘tish natijasida aniqlanadigan maqsad o‘zgaruvchisi qiymatini ifodalaydi. Har bir ichki tugun kirish o‘zgaruvchilaridan biri bilan bog‘langan.
Daraxtni belgilar qiymatlarini tekshirish asosida dastlabki o‘zgaruvchilar to‘plamlarini kichik to‘plamlarga ajratish orqali ham «o‘rgatish» mumkin. Bu amal hosil bo‘lgan har bir kichik to‘plamda takrorlanadi. Tugundagi kichik to‘plamda maqsad o‘zgaruvchisining barcha qiymatlari bir xil bo‘lsa, ya’ni u bashoratga qo‘shimcha foyda bermasa, rekursiya to‘xtaydi. «Yuqoridan pastga» usulida kechadigan qarorlar daraxtini induksiya qilish (TDIDT) ochko‘z algoritmga misol bo‘lib, hozirgi kunda ma’lumotlar uchun eng keng tarqalgan qarorlar daraxtini qurish strategiyasidir. Biroq bu yagona mumkin bo‘lgan strategiya emas.
Ma’lumotlarni intellektual tahlil qilishda qarorlar daraxtlaridan ma’lumotlar to‘plamini tavsiflash, tasniflash va umumlashtirishga yordam beradigan matematik hamda hisoblash usullari sifatida foydalanish mumkin. Bunday to‘plamni quyidagicha ifodalash mumkin:
Bog‘liq X o‘zgaruvchisi tahlil qilinishi, tasniflanishi va umumlashtirilishi kerak bo‘lgan maqsad o‘zgaruvchisidir. vektori kirish o‘zgaruvchilari — , , va hokazolardan iborat bo‘lib, ular ushbu vazifani bajarishda ishlatiladi.
Asosiy ta’riflar
Qarorlarni «qarorlar daraxti» yordamida tahlil qilishda raqobatlashuvchi muqobil variantlarning kutilayotgan qiymatlarini (yoki kutilayotgan foydasini) hisoblash uchun qaror qabul qilishni qo‘llab-quvvatlovchi ko‘rgazmali va tahliliy vositadan foydalaniladi.
Qarorlar daraxti uch turdagi tugundan iborat:
- Qaror tugunlari — odatda kvadrat shaklida tasvirlanadi
- Ehtimollik tugunlari — doira shaklida tasvirlanadi
- Yakunlovchi tugunlar — uchburchak shaklida tasvirlanadi
Yuqoridagi rasmda ko‘rsatilgan qarorlar daraxti chapdan o‘ngga qarab o‘qiladi. Qarorlar daraxtida siklik elementlar bo‘lishi mumkin emas: har bir yangi barg keyinchalik faqat tarmoqlanishi mumkin, bir-biriga qo‘shilib ketadigan yo‘llar bo‘lmaydi. Shu sababli daraxtni qo‘lda tuzishda uning o‘lchami bilan bog‘liq muammoga duch kelishimiz mumkin. Odatda qarorlar daraxti maxsus dasturiy ta’minot yordamida hosil qilinadi. Odatda qarorlar daraxti uni tushunish va tahlil qilishni osonlashtiradigan sxematik chizma shaklida tasvirlanadi.
Daraxtlar tipologiyasi
Ma’lumotlarni qazib olish jarayonida qo‘llanadigan qarorlar daraxtlari ikki asosiy turga bo‘linadi:
- Tasniflash daraxti — bashorat qilinayotgan natija ma’lumotlar tegishli bo‘lgan sinfni bildiradi;
- Regressiya daraxti — bashorat qilinayotgan natija haqiqiy son sifatida qaraladi (masalan, uy narxi yoki bemorning shifoxonada qolish muddati).
Yuqorida keltirilgan atamalarni birinchi bo‘lib Breyman va boshqalar qo‘llagan. Sanab o‘tilgan turlarning o‘xshash jihatlari (daraxtni qurishning rekursiv algoritmlari) ham, ayrim farqlari (masalan, har bir tugunda ajratish mezonini tanlash) ham mavjud.
Ayrim usullar bir nechta qarorlar daraxtini (qarorlar daraxtlari ansamblini) yaratishga imkon beradi:
- Bagging (butstrep agregatsiyasi) — qarorlar daraxtlari uchun eng dastlabki yondashuv. Bu usul ma’lumotlardan qayta-qayta o‘rin bosish bilan tanlanma olib (butstrep (bootstrap)), bir nechta qarorlar daraxtini quradi va umumiy javob sifatida daraxtlarning ovoz berish natijasini (ular bashoratlarining o‘rtacha qiymatini) taqdim etadi;
- «Tasodifiy o‘rmon» tasniflagichi bagging usuliga asoslanadi, lekin daraxtlarni bir-biridan mustaqilroq qilish uchun har bir tugunda belgilar kichik to‘plamini ham tasodifiy tanlaydi;
- Boosting (kuchaytirish) usulini regressiya hamda tasniflash vazifalarida qo‘llash mumkin. Daraxtlar uchun boosting usulining bir ko‘rinishi bo‘lgan XGBoost algoritmi ma’lumotlar tahlili musobaqalari g‘oliblari tomonidan ko‘p bora qo‘llangan.
- «Aylantirilgan o‘rmon» (rotation forest) — har bir qarorlar daraxtini tahlil qilishdan oldin kirish belgilarining tasodifiy kichik to‘plamlariga bosh komponentlar tahlili (PCA) qo‘llanadigan daraxtlar ansamblidir.
Daraxtni qurish algoritmlari
Keyingi belgini tanlashning turli usullari mavjud:
- ID3 algoritmi, bunda belgi tanlash axborot yutug‘iga asoslanadi (ingl. Gain) yoki Jini mezoniga asoslanadi.
- C4.5 algoritmi (ID3 ning takomillashtirilgan versiyasi), bunda belgi tanlash me’yorlashtirilgan axborot yutug‘iga asoslanadi (ingl. Gain Ratio).
- Algoritm CART va uning modifikatsiyalari — IndCART, DB-CART.
- Xi-kvadrat bo‘yicha o‘zaro ta’sirni avtomatik aniqlash (CHAID). Tasniflash daraxtlarini hisoblashda ko‘p yo‘nalishli bo‘linishni bajaradi;
- MARS: sonli ma’lumotlarni yaxshiroq qayta ishlash uchun qarorlar daraxtlari imkoniyatlarini kengaytiradi.
Amalda bu algoritmlar natijasida ko‘pincha haddan tashqari batafsil daraxtlar hosil bo‘ladi va ulardan keyinchalik foydalanilganda ko‘plab xatolar yuzaga keladi. Bu holat ortiqcha moslashish hodisasi bilan bog‘liq. Daraxtlarni ixchamlashtirish uchun shoxlarni kesishinglizcha (ingl. pruning).
Usulning afzalliklari
Ma’lumotlarni qazib olishning boshqa usullaridan farqli ravishda qarorlar daraxti usulining bir nechta afzalligi bor:
- Tushunish va talqin qilish oson.
- Ma’lumotlarni me’yorlashtirish, soxta o‘zgaruvchilarni qo‘shish yoki yetishmayotgan qiymatlarni olib tashlash kabi maxsus dastlabki tayyorgarlikni talab qilmaydi.
- Ham toifali, ham intervalli o‘zgaruvchilar bilan ishlay oladi. (Boshqa usullar faqat bir turdagi o‘zgaruvchilardan iborat ma’lumotlar bilan ishlaydi. Masalan, munosabatlar usuli faqat nominal o‘zgaruvchilarga, neyron tarmoqlar usuli esa faqat intervalli shkala bo‘yicha o‘lchangan o‘zgaruvchilarga qo‘llanishi mumkin.)
- «Oq quti» modelidan foydalanadi: modelda muayyan vaziyat kuzatilsa, uni Bul mantiqi yordamida tushuntirish mumkin. «Qora quti»ga sun’iy neyron tarmoq misol bo‘ladi, chunki u hosil qilgan natijalarni tushuntirish qiyin.
- Modelni statistik testlar yordamida baholash imkonini beradi. Bu uning ishonchliligini aniqlashga yordam beradi.
- Modelga kiritilgan dastlabki farazlar buzilgan taqdirda ham usul yaxshi ishlaydi.
- Maxsus tayyorgarlik bosqichlarisiz katta hajmdagi axborot bilan ishlash imkonini beradi. Katta ma’lumotlar bazalari bilan ishlash uchun bu usul maxsus uskunalarni talab qilmaydi.
Usulning kamchiliklari
- Optimal qarorlar daraxtini topish masalasi oddiy vazifalarda ham ayrim optimallik mezonlari nuqtayi nazaridan NP-to‘liq masala hisoblanadi. Shu sababli qarorlar daraxti algoritmlarini amalda qo‘llash har bir tugunda mahalliy darajada eng yaxshi yechimni tanlaydigan «ochko‘z» algoritm singari evristik algoritmlarga asoslanadi. Bunday algoritmlar butun daraxtning umumiy optimal bo‘lishini kafolatlay olmaydi.
- Qarorlar daraxtini qurishda ma’lumotlarni yetarlicha to‘liq ifodalamaydigan haddan tashqari murakkab tuzilmalar paydo bo‘lishi mumkin. Bu muammo ortiqcha moslashish deb ataladi. Uning oldini olish uchun «daraxt chuqurligini boshqarish» usulidan foydalanish kerak.
- Ayrim tushunchalarni modeldan anglash qiyin bo‘ladi, chunki model ularni murakkab yo‘l bilan ifodalaydi. Bunga XOR, juftlik yoki multiplekslash muammolari sabab bo‘lishi mumkin. Bunday vaziyatda daraxt haddan tashqari kattalashadi. Muammoni bartaraf etishning bir necha yo‘li bor: masalan, modeldagi tushunchaning ifodalanishini o‘zgartirish (yangi mulohazalar tuzish) yoki tushunchani to‘laroq tavsiflaydigan algoritmlardan (masalan, statistik munosabatlar usuli yoki induktiv mantiqiy dasturlashdan) foydalanish.
- Ko‘p darajaga (toifaga) ega toifali o‘zgaruvchilar qatnashgan ma’lumotlarda darajalari soni ko‘proq bo‘lgan belgilarga kattaroq axborot vazni beriladi.
Daraxt chuqurligini boshqarish
Daraxt chuqurligini boshqarish — qarorlar daraxtining ahamiyati kichik bo‘lgan qismlarini olib tashlash orqali uning o‘lchamini kamaytirishga imkon beradigan usul.
Qarorlar daraxti algoritmida yuzaga keladigan savollardan biri — yakuniy daraxtning optimal o‘lchami qanday bo‘lishidir. Kichik daraxt tanlanma fazosi haqidagi ayrim muhim ma’lumotlarni qamrab olmasligi mumkin. Biroq algoritm qachon to‘xtashi kerakligini aniqlash qiyin, chunki qaysi tugunni qo‘shish xatoni sezilarli kamaytirishini oldindan aytib bo‘lmaydi. Bu muammo «ufq effekti» nomi bilan ma’lum. Shunga qaramay, daraxtni cheklashning umumiy strategiyasi saqlanadi: qo‘shimcha axborot bermaydigan tugunlar olib tashlanadi.
Daraxt chuqurligini boshqarish o‘rgatilgan daraxt modelining hajmini bashorat aniqligini pasaytirmasdan, jumladan, o‘zaro tekshirish yordamida kamaytirishi kerak. Samaradorlikni optimallashtirishni baholash usuli bilan farqlanuvchi daraxt chuqurligini boshqarishning ko‘plab usullari mavjud.
Boshqarish usullari
Daraxtni yuqoridan pastga yoki pastdan yuqoriga qarab qisqartirish mumkin. Yuqoridan pastga qisqartirish ildizdan boshlanadi, pastdan yuqoriga qisqartirishda esa barglar soni kamaytiriladi. Eng sodda boshqarish usullaridan biri — daraxtni cheklash orqali xatoni kamaytirishdir. Barglardan boshlab har bir tugun eng ko‘p uchraydigan sinf bilan almashtiriladi. Agar bu o‘zgarish bashorat aniqligiga ta’sir qilmasa, u saqlab qolinadi.
Masalaga misol
Faraz qilaylik, sevimli futbol jamoamiz keyingi o‘yinda g‘alaba qozonadimi, degan savol bizni qiziqtiryapti. Bu bir qancha omillarga bog‘liqligini bilamiz. Ularning barchasini sanashning iloji yo‘q, shuning uchun asosiylari bilan cheklanamiz:
- raqib turnir jadvalida yuqoriroq o‘rindami;
- o‘yin o‘z maydonimizda bo‘ladimi;
- jamoa yetakchilaridan birortasi o‘yinni o‘tkazib yuboradimi;
- yomg‘ir yog‘yaptimi.
Bu masala bo‘yicha ma’lum statistik ma’lumotlarimiz bor:
| Raqib | O‘yin joyi | Yetakchilar | Yomg‘ir | G‘alaba |
|---|---|---|---|---|
| Yuqorida | O‘z maydonimizda | Safda | Ha | Yo‘q |
| Yuqorida | O‘z maydonimizda | Safda | Yo‘q | Ha |
| Yuqorida | O‘z maydonimizda | Qatnashmaydi | Yo‘q | Yo‘q |
| Pastda | O‘z maydonimizda | Qatnashmaydi | Yo‘q | Ha |
| Pastda | Mehmonda | Qatnashmaydi | Yo‘q | Yo‘q |
| Pastda | O‘z maydonimizda | Qatnashmaydi | Ha | Ha |
| Yuqorida | Mehmonda | Safda | Ha | Yo‘q |
| Pastda | Mehmonda | Safda | Yo‘q | Ha |
Jamoamiz navbatdagi o‘yinda g‘alaba qozonadimi, shuni bilmoqchimiz.
Ushbu kod qarorlar daraxti yordamida masalani yechadi va buning uchun Python tilidagi kutubxonalardan foydalanadi: sklearn, pandas, matplotlib
import pandas as pd
from sklearn import tree
import matplotlib.pyplot as plt
data = {'opponent_higher': [1, 1, 1, 0, 0, 0, 1, 0], 'home_game': [1, 1, 1, 1, 0, 1, 0, 0], 'leaders_playing': [1, 1, 0, 0, 0, 0, 1, 1], 'rain': [1, 0, 0, 0, 0, 1, 1, 0], 'victory': [0, 1, 0, 1, 0, 1, 0, 1]}
data = pd.DataFrame(data)
X = data.drop(columns='victory').values
y = data['victory'].values
clf = tree.DecisionTreeClassifier(max_depth=3, random_state=42) #параметры по усмотрению
clf.fit(X, y)
new_match = [[1, 1, 1, 1]]
prediction = clf.predict(new_match)
res = prediction[0]
fig = plt.figure(figsize=(20, 10))
tree.plot_tree(clf, class_names=['Defeat', 'Victory'], feature_names = list(data.drop(columns='victory').columns), filled=True, rounded=True, fontsize=12)
plt.show()
Adabiyotlar
- Levitin A. V. 10-bob. Algoritmlar imkoniyatlarining chegaralari: qaror qabul qilish daraxtlari // Algoritmlar. Ishlab chiqish va tahlilga kirish — M.: Vilyams, 2006. — B. 409—417. — 576 b. — ISBN 978-5-8459-0987-9
- Paklin N. B., Oreshkov V. I. 9-bob. // Biznes tahlili: ma’lumotlardan bilimga (+CD): o‘quv qo‘llanma. 2-nashr. — Sankt-Peterburg: Piter, 2013. — B. 428—472. — ISBN 978-5-459-00717-6.