Mirzo ulugʻbek nomidagi oʻzbekiston milliy universitetining jizzax filiali

CART (Classification and Regression Tree). Algoritm tasniflash va regressiya muammolarini hal qiladi, chunki u diskret va uzluksiz foydalanishga imkon beradi maqsadli o'zgaruvchilar. CART daraxtlarni quradi, ularning har bir tugunida faqat ikkita avlod bor.


Bo'lim atributini tanlash
Ajratish ma'lum bir qoidaga muvofiq amalga oshirilishi kerak, buning uchun atribut tanlanadi. Bundan tashqari, tanlangan atribut tugundagi kuzatuvlar to'plamini buzishi kerak, shunda natijada olingan kichik to'plamlar bir xil sinf belgilariga ega bo'lgan misollarni o'z ichiga oladi yoki iloji boricha unga yaqinlashadi. Boshqacha qilib aytganda, ushbu to'plamlarning har biridagi boshqa sinflardagi ob'ektlar soni iloji boricha kichikroq bo'lishi kerak.

• 
  Ko'p mezonlar mavjud, ammo axborot-nazariy va statistik eng mashhurdir.
  
• 
  Axborot-nazariy mezon
  
• 
  Mezon axborot entropiyasiga asoslangan:
  

bu erda n-asl kichik to'plamdagi sinflar soni, Ni-i-sinf misollari soni, N-kichik to'plamdagi misollarning umumiy soni.
Entropiya unda keltirilgan sinflar bo'yicha kichik to'plamning heterojenligining o'lchovi sifatida qaraladi. Va agar sinflar teng nisbatda taqdim etilsa va tasnifning noaniqligi eng katta bo'lsa ham, entropiya ham maksimal bo'ladi. Agar tugunning barcha misollari bitta sinfga tegishli bo'lsa, bitta logaritma entropiyani nolga aylantiradi.
Agar tanlangan AJ bo'linish atributi ota-onaga nisbatan hosil bo'lgan pastki qismning entropiyasini maksimal darajada kamaytirishni ta'minlasa, uni eng yaxshi deb hisoblash mumkin.
Ammo aslida ular entropiya haqida kamdan-kam gapirishadi. Mutaxassislar teskari qiymatga e'tibor berishadi-ma'lumot. Bunday holda, eng yaxshi atribut natija tugunining asl nusxasiga nisbatan maksimal ma'lumot o'sishini ta'minlaydigan atribut bo'ladi:

bu erda Info(S) — bo'linishdan oldin s kichik to'plami bilan bog'liq ma'lumotlar, Info (Sa) — a atributini ajratish natijasida olingan kichik to'plam bilan bog'liq ma'lumotlar.
Bunday vaziyatda atributni tanlash vazifasi ma'lumotlarning ko'payishi deb ataladigan Gain(a) qiymatini maksimal darajada oshirishdir. Shuning uchun axborot-nazariy yondashuv "axborot o'sishi mezoni" nomi bilan ham tanilgan.