Tasodifiy o’rmon (Random Forest) va yakkalovchi o’rmon (Isolation Forest) algoritmlari. 10-ma’ruza

1.

10-ma’ruza: Tasodifiy o’rmon (Random Forest) va
yakkalovchi o’rmon (Isolation Forest) algoritmlari
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
1

2.

Tasodifiy o’rmon algoritmi
Tasodifiy o'rmonlar - bu o’qituvchi bilan o’rganiladigan mashinali
o'rgatish algoritmi bo'lib, u regressiya va klassifikatsiya muammolarida
keng qo'llaniladi va ko'pincha giperparametrlarni sozlashsiz ham ajoyib
natija beradi. Bu, ehtimol, soddaligi tufayli eng ko'p ishlatiladigan
algoritmdir. U turli xil tanlanmalar bo'yicha bir qator qarorlar daraxtlarini
yaratadi va agar u klassifikatsiya muammosi bo'lsa, ko'pchilik ovoz berish
orqali qaror qabil qilinadi
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
2

3.

Ansambl texnikasi
Bagging
Ansambl texnikasi bashorat qilish uchun individual model emas, balki
modellar to'plamidan foydalaniladi va bu umumiy samaradorlikni
oshiradi. Mashinali o’rgatishda ikkita asosiy ansambl usulini keng tarqalgan:
1. Qoplash (Bagging, bootstrapping) - Aytaylik, bizda berilganlar to'plami
bor va biz bir xil berilganlar to'plamida turli modellarni yaratamiz va uni
birlashtiramiz, bu foydali bo'ladimi? Yo'q. Xuddi shunday natijalarga erishish
ehtimoli yuqori, chunki biz bir xil berilganni beramiz.
Buning o'rniga biz bootstrapping deb nomlanuvchi texnologiyadan
foydalanamiz. Bunda biz almashtirish bilan asl berilganlar to'plamining kichik
to'plamlarini yaratamiz. Kichik to'plamlarning o'lchami asl to'plamning o'lchami
bilan bir xil. Biz buni almashtirish bilan qilganimiz sababli, modellarimizga turli xil
berilganlar nuqtalarini taqdim etish imkoniyati yuqori.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
3

4.

Bootstrapping
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2020
4

5.

Bagging
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
5

6.

Boosting
Boosting - Faraz qilaylik, kuzatuvdagi har qanday berilgan nuqtasi
sizning 1 - modelingiz tomonidan noto'g’ri klassifikatsiya qilingan, keyingi
(ehtimol, barcha modellar) prognozlarni birlashtirib, yaxshi natijalar
beradimi? Albatta, YO’Q.
Boosting texnologiyasi ketma-ket jarayon bo'lib, har bir model
oldingi modeldagi xatolarni tuzatishga harakat qiladi. Keyingi modellar
oldingi modelga bog’liq bo’ladi.
Yakuniy model eng yuqori aniqlikka ega bo'lishi uchun ketma-ket
modellarni yaratish orqali zaif o'quvchilarni kuchli o'quvchilarga
birlashtiradi. Masalan, ADA BOOST, XG BOOST.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
6

7.

Boosting
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
7

8.

Tasoddifiy o’rmon amal qilishi
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2020
8

9.

Tasodifiy o'rmon algoritmi nima?
Tasodifiy o'rmon - bu murakkab muammolarni hal qilish
uchun ko'plab zaif klassifikatorlarni birlashtirgan ansambl
o'rganishdan foydalanadigan texnikadir.
Nomidan ko'rinib turibdiki, tasodifiy o'rmon ko'plab qaror
daraxtlaridan iborat. Bitta daraxtga qarab emas, balki har bir
daraxtdan bashorat oladi va bashoratlarning ko'pchilik ovoziga
asoslanib, yakuniy natijani bashorat qiladi.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
9

10.

Gini indeksi
Gini indeksi odatda alomatlar to’plamidan informativ alomatni
aniqlash uchun ishlatiladi.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
10

11.

Gini indeksi
Eng past Gini indeksiga ega bo'lgan asosiy tugun sifatida qabul
qilamiz. Matematik jihatdan Jini indeksini quyidagicha yozish mumkin:
Bu erda P + - ijobiy sinf ehtimoli va P _ - salbiy sinf ehtimoli.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
11

12.

Gini indeksi
Keling, sodda tanlanma yordamida ushbu formulani tadqiq qilaylik. Masalan, kredit
summasini asosiy tugun sifatida qabul qilaylik va uni ajratishga harakat qilaylik
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
12

13.

Gini indeksi
Chap bo'linish Jini indeksi:
O’ng bo'linish uchun Jini indeksi:
Ushbu bo'linishning umumiy Jini indeksi bo'lgan vaznli Jini indeksini hisoblashimiz mumkin:

14.

Tasodifiy o'rmon algoritmini amalga oshirish ketma-ketligi
1-qadam - Biz birinchi navbatda dastlabki tanlanma asosida tanlanma ostilarini xosil qilamiz. Buning uchun obyektlar
va alomatlarni tasodifiy tanlab olinadi;
2-qadam - har bir tanlanma ostisi uchun individual qaror daraxtini quramiz;
3-qadam - Har bir qaror daraxti natija beradi;
4-qadam – Yakuniy natija, agar u klassifikatsiya muammosi bo'lsa, ko'pchilik ovozi asosida, agar bu regressiya
muammosi bo'lsa, o'rtacha qiymat orqali qaror qabul qilinadi.

15.

Qarorlar daraxti va tasodifiy o'rmon o'rtasidagi farq
Qaror daraxtlari
Tasodifiy o'rmonlar
1. Qaror daraxtlari, odatda, agar u
maksimal chuqurlikka qadar o'sishiga
ruxsat berilsa, meyoridan ortiq o’rgatish
(overfitting) muammosidan aziyat
chekadi.
1. Tasodifiy o'rmonlar bagging (qoplash)
usulidan foydalanadi. U dastlabki tanlanma
asosida tanlanma ostilarini yaratadi va yakuniy
natija ko'pchilik ovoziga asoslanadi va shuning
uchun meyoridan ortiq o’rgatish (overfitting)
muammosini hal qilinadi.
2. Yagona qaror daraxti hisoblashda
tezroq.
2. Bu nisbatan sekinroq.
3. Alomatlar fazosi elementlari
kombinatsiyasi asosida bashorat qilish
uchun ba'zi qoidalar to'plamini
shakllantiradi.
3. Tasodifiy o'rmon kuzatishlarni tasodifiy
tanlaydi, qarorlar daraxtini quradi va o'rtacha
natija olinadi. U hech qanday formuladan
foydalanmaydi.

16.

Tasodifiy o'rmon algoritmining afzalliklari
Katta sondagi alomatlar va sinflarga ega berilganlar bilan samarali ishlash
qobiliyati.
Alomatlar qiymatlarini mashtablashga befarqlik (va ixtiyoriy monoton
o’girishlarga).
Uzluksiz va diskret alomatlar bilan bir xil ishlaydi. O’takazib yuborilgan
qiymatlar uchun daraxt qurish usullari ham mavjud.
Modeldagi ayrim alomatlar ahamiyatligini baholash usullari mavjud.
Modelning umumlashtirish qobiliyatini ichki baholash (saralanmagan obrazlar
bo’yicha test asosida).
Yuqori parallelizm va katta hajmdagi berilganlar bilan ishlash.
Moslashuvchanlik va yuqori aniqlik.
Turli qarorlar daraxtlari natijalarini birlashtirish yoki o’rtachasini olish orqali
me’yoridan ortiq o’rganish muammosini yengish.
Tasoddifiy o’rmon alohida qarorlar daraxtiga nisbatan kichik dispersiyag ega.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
16

17.

Tasodifiy o'rmon algoritmining kamchiliklari
•Murakkablik tasoddifiy o’rmonning eng katta kamchiligi hisoblanadi.
•Tasoodifiy o’rmonni qurish qarorlar daraxtini qurishga nisbatan
murakkab va ko’p vaqt egallaydi.
•Tasoddifiy o’rmon algoritmini amalga oshirish uchun ko’proq
hisoblash resurslari kerak bo’ladi.
•Juda ko’p sondagi qarorlar daraxtlari bo’lganda olingan natijani
intuitiv tushunish og’ir.
• Tasoddifiy o’rmonda prognozlash boshqa algoritmlarga nisbatan
ko’p mehnat talab qiladi.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2020
17

18.

Anomal obyekt
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2020
18

19.

Yakkalovchi o’rmon
An’anaviy holda boshqa usullar normal berilganlar profilini
yaratadi va keyinchalik qaysi berilganlar nuqtalari anomal sifatida
ushbu profilga mos kelmasligini aniqlaydi.
Yakkalovchi o’rmonning o’ziga xos tomoni yakkalashdan
foydalangan holda anomallarni to’g’ridan-to’g’ri aniqlay oladi
(berilganlar nuqtalari boshqalardan qanchalik uzoqda joylashganligi
asosida). Bu algoritmni chiziqli murakkablikka ega ekanligidir, xuddi
k-yaqin qo’shni algoritmi kabi masofa bilan bog’liq algoritmlardek.
Algoritm, ajralmalarning eng yaqqol xossalariga tayangan
holda ishlaydi - og’ishlar faqat bir nechta va ularning ajralmalari
turlicha bo’ladi.

20.

Yakkalovchi o’rmonni amalga oshirish
Yakkalovchi o’rmon
orqali amalga oshiradi.
binar daraxtlarni (ansamblini) kiritish
Daraxtlar funksiyalarni tasoddifiy tanlash, keyinchalik
funksiyalar uchun tasoddifiy ravishda qiymatlarni tanlash orqali
bo’limlarni rekursiv ravishda hosil qiladi.
Ajratish jarayoni barcha berilganlar
tanlanmalardan ajratmaguncha davom etadi.
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2020
nuqtalari
boshqa
20

21.

Yakkalivchi o’rmon daraxtlarining biri

22.

Ikki o'lchovli nuqtai nazardan chetdagilarni ajratish

23.

Yakkalovchi o’rmon (Isolation Forest) algoritmi
•Yakkalovchi o'rmon chet/anomal obyektlarni aniqlash uchun ishlatiladi
•Yakkalovchi o'rmoni - bu o’qituvchisiz o’rgatish (unsupervised
learning) usuli (sinflar kerak emas)
•Ikkilik qarorlar daraxtlarini qurishda bagging (qoplash) mexanizmidan
foydalanadi (Tasodifiy o'rmonga o'xshaydi)
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
23

24.

Yakkalovchi o’rmon (Isolation Forest) algoritmi
Gipoteza
Bu usul anomal obyektlarni normal obyektlarda ajratib turadi,
buning uchun anamol obyektlar uchun quyidagi taxminlar qilinadi:
• Ular kamroq misollardan iborat bo’lib, ozchilikni tashkil qilada;
• Ular oddiy normal obyektlardan farq qiladigan atribut-qiymatlarga
(alomatlarga) ega.
Boshqacha qilib aytganda, anomal obyektlar "kam va boshqacha".
ЎЗБЕКИСТОН МИЛЛИЙ УНИВЕРСИТЕТИ, 2022
24