K ta yaqin qo‘shni usuli

Ushbu qismda o‘rganmoqchi bo‘lgan algoritmimiz bu k ta yaqin qo‘shni deb nomlanadi. Ushbu usul biz rasmlardagi raqamlarni aniqlashda ishlatilgan usulning umumiyroq ko‘rinishi hisoblanadi. Hamda bu usulni ham biz umumiy holda "Bayes" usuli deyishimiz mumkin. Chunki ushbu usul ham oldingi mavjud to‘plamdan foydalanib obyektga baho beradi. Yaqin qo‘shni usuli asosida rasmidagi raqamni topayotganimizda bitta yaqin qo‘shinisi qaragan edik. Endi shuni kengaytirgan holda bitta emas k ta qo‘shni e’tiborga olamiz. Undan tashqari ushbu bobda biz ushbu usulni umumlashtirib regressiya masalalari uchun ham qo‘llaymiz.

Bundan tashqari masalalarni yozish uchun biz imkon qadar matematik belgilashlardan foydalanib boshlaymiz hamda algoritmlarni esa to‘lig‘icha NumPy kutubxonasida yozamiz. Ushbu darsimizning birinchi qismida NumPy kutubxonasiga mos ravishda ba’zi bosqichlarni Python kutubxonasida ham yozamiz shunda biz NumPy kutubxonasini tushunishimiz osonroq bo‘ladi. Keyinchalik esa faqat NumPydan foydalanishga imkon qadar harakat qilamiz.

Eslatma. Ushbu usulni Ingliz tilida qisqartirib kNN nomlashadi yozishadi, ma’nosi esa k Nearest Neighbors. Bevosita tarjimasi esa k ta yaqin qo‘shni.

Classifikatsiya masalasi

Tassavur qilamiz bizga \(\mathbb{X}=\{\mathbf{x}^{(1)}, ..., \mathbf{x}^{(M)}\}, \mathbf{x}^{(1)}\in \mathbb{R}^N\) to‘plam hamda uning har bir \(i\)-obyekti uchun maqsadli alomat \(y^{(i)}\in\{1, 2, \dots, K\}\) berilgan bo‘lsin. Ushbu maqsadli alomat har bir \(i\)-obyekt nima ekanligini bizga bildiradi. Masalan, birinchi obyekt bo‘ri bo‘lsa, ikkinchi obyekt esa it guruhiga tegishli. Bu yerda \(K\) sinflar soni. Masalan, rasmlardagi raqamlar turining umumiy soni \(K=10\) edi. Bizning vazifamiz: shunday algoritm qurishimiz keraki, u algoritm har bir obyekt uchun \(y^{(i)}\) ni taqribiy hisoblab bersin.

Yuqorida qisqacha k ta yaqin qo‘shni usuli haqida izoh berdik. Keling endi shu usulni batafsil o‘rganib chiqamiz. Ushbu usul eng yaqin qo‘shni usulining umumiy ko‘rinishi hisoblanadi. Agar \(k=1\) bo‘lsa, u holda eng yaqin qo‘shni usulini anglatadi. Eng yaqin qo‘shni usulida yangi kelgan \(\mathbf{x}^{(*)}\) obyektning sinfini juda ham oson topish mumkin, chunki biz birinchi \(\mathbf{x}^{(*)}\) obyekt bilan bizga berilgan \(\mathbb{X}=\{\mathbf{x}^{(1)}, ..., \mathbf{x}^{(M)}\}, \mathbf{x}^{(1)}\in \mathbb{R}^N\) to‘plamdagi har bir obyekt o‘rtasidagi masofani topib chiqamiz: \(\mathbf{d}=\{\rho(\mathbf{x}^{(*)}, \mathbf{x}^{(1)}), \rho(\mathbf{x}^{(*)}, \mathbf{x}^{(2)}), \dots, \rho(\mathbf{x}^{(*)}, \mathbf{x}^{(M)})\}\). Shundan so‘ng, \(\mathbf{x}^{(*)}\) obyekt uchun \(\mathbb{X}\) to‘plamdagi eng yaqin obyektni topamiz va shu topilgan obyektning sinfini \(\mathbf{x}^{(*)}\) yangi obyekt uchun sinf deb qaraymiz.

Ko‘rib turganingizdek bu juda ham sodda. Endi biz shu obyektlar \(\mathbf{d}\) yaqinlik tartibi bo‘yicha k tasini tanlab olsak, u holda bizda k obyektning turli xil sinflari mavjud bo‘lib qoladi. Bu holda biz shu sinflardan qaysi eng ko‘p uchragan bo‘lsa, shu sinfni olamiz yangi obyekt uchun sinf deb olamiz. Sizda savol tug‘ilishi mumkin, ya’ni agar ikkita har xil sinflarning obyektlari bir xil bo‘lib qolsa qanday yo‘l tutamiz. Albatta bunday muammolar ushbu usulning umumiy kamchiligi hisoblanadi. Ba’zi hollarda bunday holdan qochish yo‘llari mavjud, bular haqida qisqacha keyinchalik to‘xtalamiz. Hozir ushbu usulni ikki o‘lchovli fazoda qanday ishlashini tushunishga quyidagi rasm orqali harakat qilamiz.

k ta yaqin qo‘shni usuli

Yuqoridagi rasmda jami 40 ta 4 ta sinfga tegishli obyektlar mavjud hamda bitta "Yangi" obyekt bor. Ushbu masalada biz yangi obyekt qaysi sinfga tegishli ekanligini aniqlashimiz kerak bo‘ladi. Buning uchun yuqoridagi rasmdagidek yaqin qo‘shilari joylashgan doiralarni aniqlab olishimiz kerak. Ushbu rasmdagi eng katta doira o‘z ichiga 16 ta eng yaqin qo‘shnisini oladi, undan keyingisi esa 5 va oxirgisi 2 qo‘shini. Agar biz faqat eng yaqin 16 qo‘shinisini qarasak, u holda quyidagi statistikaga ega bo‘lamiz:

Sinf nomi

Obyektlar soni

1-sinf

6

2-sinf

1

3-sinf

1

4-sinf

8

Jami

16

va ushbu statistikaga asosan biz yangi obyektni 4-sinfga tegishli deb ayta olamiz, chunki 4-sinf obyektlari ushbu doirada eng ko‘pchilikni tashkil qiladi. Endi xuddi shunday eng yaqin 5 ta qo‘shnidan iborat doirani olsak:

Sinf nomi

Obyektlar soni

1-sinf

2

2-sinf

0

3-sinf

0

4-sinf

3

Jami

5

va bu holda ham yana shu bir xil natijaga erishamiz. Lekin eng yaqin 2 ta qo‘shinisini olsak, u holda yuqoridagi natija 1-sinfga o‘zgaradi. Ushbu masala, ya’ni aslida nechta qo‘shni olsak yaxshi ekanligi umuman olgan turli xil yechiladi. Biz hozir bu masalani keyinga qoldirib, birinchi matematik ushbu algoritmni ifodalab, keyin Pythonda va oxirida esa NumPyda kodini yozib chiqsak.

Biz yuqorida berilgan belgilashlarni mavjud deb qaraymiz. Ya’ni, obyektlar to‘plami \(\mathbb{X}=\{\mathbf{x}^{(1)}, ..., \mathbf{x}^{(M)}\}, \mathbf{x}^{(1)}\in \mathbb{R}^N\) to‘plam hamda uning har bir \(i\)-obyekti uchun maqsadli alomat \(y^{(i)}\in\{1, 2, \dots, K\}\) va yangi kelgan obyekt \(\mathbf{x}^{(*)}\) berilgan bo‘lsin. Vazifamiz \(\mathbf{x}^{(*)}\) obyekt uchun \(y^{(*)}\) qiymatni yuqoridagi \(\mathbb{X}\) to‘plam obyektlari va mos \(y^{(i)}\) maqsadli alomatlari asosida topishimiz kerak:

  1. Keling, birinchi yuqoridagidek \(\mathbf{x}^{(*)}\) va \(\mathbb{X}\) to‘plam obyektlari o‘rtasidagi masofani hisoblab olib, uni \(\mathbf{d}\) deb belgilaylik, ya’ni: \(\mathbf{d}=\{\rho(\mathbf{x}^{(*)}, \mathbf{x}^{(1)}), \rho(\mathbf{x}^{(*)}, \mathbf{x}^{(2)}), \dots, \rho(\mathbf{x}^{(*)}, \mathbf{x}^{(M)})\}\);

  2. Bundan keyin esa nechta yaqin qo‘shniga e’tibor berishimiz kerakligini \(k\) o‘zgaruvchisi orqali ifodalaylik;

  3. Ushbu navbatda esa ushbu \(\mathbf{d}\) vektorini qiymatlarining tartibi asosida o‘rinlarini \(\mathbf{d}_{argsort}=argsort(\mathbf{d})\) o‘zlashtirsak olsak;

  4. Undan so‘ng har bir sinfda nechtadan obyekt joylashganini ifodalash uchun \(\mathbf{s}=(0, 0, 0, 0)\) o‘zgaruvchisi olsak. Bu yerda har bir sinf obyektlari boshida 0 tadan mavjud deb qaraymiz;

  5. Shundan so‘ng esa \(\mathbf{d}_{argsort}\) ning birinchi k ta elementidan foydalanib \(\mathbf{s}\) ning qiymatlarini \(\mathbf{y}^{(i)}\) asosida aniqlab olamiz. Ya’ni har bir sinf obyektlarini sanaymiz.

  6. Oxirida esa \(\mathbf{x}^{(*)}\) obyekt sinfini \(y^{(*)}=argmax(\mathbf{s})\) ko‘rinishida topamiz.

Keling endi yuqorida yozgan matematik ifodalarimiz bilan rasmda ko‘rsatilgan obyektlarning qiymatini bog‘laylik. Birinchi \(\mathbb{X}\) to‘plamning har bir obyekti ikkita qiymat asosida shakllantiriladi, bular \(x_1\) va \(x_2\). Quyidagi jadvalda shu to‘rta sinfning obyektlari keltirilgan.

[2]:

# Bu kodlarni tekshirish uchun kerak
%load_ext autoreload
%autoreload 2

[ ]:

# ushbu kod orqali biz obyekt qiymatlarini
# yuklaymiz hamda ularni darslikka
# jadval shaklida qo‘shamiz
# BU KODLARNI KEYINCHALIK o‘RGANAMIZ
from IPython.display import Markdown, display
from utils import knn_illustration_dataset
import numpy as np

# to‘rta sinf obyektlari va
# ularning qayis sinfga tegishliligi
# yangi obyekt x_star
# hamda ular o‘rtasidagi masofa
# va jadval
(x, y, x_star, dists,
 mark_table,
 mark_dist_table,
 mark_dist_sort_table) = knn_illustration_dataset()
display(Markdown(mark_table))

\(x_1\)

\(x_2\)

\(x_1\)

\(x_2\)

\(x_1\)

\(x_2\)

\(x_1\)

\(x_2\)

1.50

-1.14

2.47

0.77

-1.26

2.17

-2.48

-1.19

1.65

0.52

1.07

-0.42

-2.12

1.70

-3.11

-2.20

0.77

-1.23

0.46

1.11

-3.48

1.28

-1.19

0.36

2.58

-0.23

-0.15

1.38

-2.46

3.06

-2.07

0.00

0.53

-0.46

0.40

0.71

-1.66

0.24

-1.64

-1.65

0.54

-1.47

0.40

2.85

-1.68

1.61

-1.64

0.54

1.24

-2.91

0.99

-0.06

-2.68

2.61

-2.04

0.56

-0.72

-1.56

1.82

-0.22

-0.97

2.93

-4.62

-0.18

-0.01

-0.69

1.21

-0.96

-2.84

1.69

-1.91

-1.30

0.09

-2.41

-0.33

1.20

-1.67

2.98

-1.91

-2.99

Yuqoridagi jadvalning birinchi ikki ustuni birinchi, keyingi 3 va 4-ustunlar ikkinchi, undan keyingi 5 va 6-ustunlar uchunchi hamda oxirgi 7 va 8-ustunlar esa to‘rtinchi sinf obyektlarini mos ravishda ifodalaydi. Masofalar esa quyidagicha:

[3]:

display(Markdown(mark_dist_table))

Sinf

1

2

3

4

5

6

7

8

9

10

1-sinf

2.50

3.05

1.78

3.66

1.62

1.61

2.95

0.63

1.04

1.79

2-sinf

3.89

2.15

2.56

2.52

2.21

4.10

2.20

2.93

2.21

2.30

3-sinf

3.18

2.92

3.37

4.31

1.40

2.70

3.98

3.93

3.26

4.03

4-sinf

1.49

2.42

1.37

1.47

0.91

1.67

1.88

3.71

0.96

2.19

Keyingi jadvalda esa ushbu masofalarning tartiblangan ko‘rinishi va joriy obyektning qaysi sinfga tegishli ekanligi keltirilgan:

[4]:

display(Markdown(mark_dist_sort_table))

#

\((x^{(*)}, x^{(i)})\)

Sinfi

1

0.63

1-sinf

2

0.91

4-sinf

3

0.96

4-sinf

4

1.04

1-sinf

5

1.37

4-sinf

6

1.40

3-sinf

7

1.47

4-sinf

8

1.49

4-sinf

9

1.61

1-sinf

10

1.62

1-sinf

11

1.67

4-sinf

12

1.78

1-sinf

13

1.79

1-sinf

14

1.88

4-sinf

15

2.15

2-sinf

16

2.19

4-sinf

17

2.20

2-sinf

18

2.21

2-sinf

19

2.21

2-sinf

20

2.30

2-sinf

21

2.42

4-sinf

22

2.50

1-sinf

23

2.52

2-sinf

24

2.56

2-sinf

25

2.70

3-sinf

26

2.92

3-sinf

27

2.93

2-sinf

28

2.95

1-sinf

29

3.05

1-sinf

30

3.18

3-sinf

31

3.26

3-sinf

32

3.37

3-sinf

33

3.66

1-sinf

34

3.71

4-sinf

35

3.89

2-sinf

36

3.93

3-sinf

37

3.98

3-sinf

38

4.03

3-sinf

39

4.10

2-sinf

40

4.31

3-sinf

Yuqoridagi oxirgi jadvaldan biz har bir sinfning obyektlarini belgilanga k qo‘shnigacha sanasak, oldingi jadvallarga ega bo‘lamiz va shu orqali yangi obyektning qaysi sinfga tegishli ekanligini aniqlaymiz. Yana bir bor aytadigan bo‘lsak, k ning qiymatini o‘zgartirish orqali ba’zi hollarda turli xil javob olishmiz mumkin. Shuning uchun ham ushbu usullar SIga asoslangan deyiladi va ba’zida xatolarga yo‘l qo‘yadi.

Navbatdagi qilishimiz zarur bo‘lgan vazifa bu ushbu yuqoridagi jarayoni Python tilida yozib chiqishimiz kerak. Yuqoridagi x, y va x_start Python ro‘yxatlari emas, ular shunchaki NumPy turida. Lekin biz hozir ularni list ko‘rinishida deb tassavur qilib ish yuritamiz. Buning uchun indekslash jarayonini bitta indeks [] amali ichida vergullar bilan yozishimiz yetarli hisoblanadi. Qolgan qismlar esa oddiy Python listi o‘zgaruvchisi kabi ishlaydi, ya’ni tayyor funksiyalardan foydalanmaymiz.

  1. Ikki obyekt o‘rtasidagi masofani topish funksiyasini yozamiz, bunda \(\rho(\mathbf{x^{(a)}}, \mathbf{x^{(b)}})=\sqrt{\sum_{i=1}^{N}{(\mathbf{x^{(a)}}_i - \mathbf{x^{(b)}_i})^2}}\) Evklid masofasidan foydalanamiz:

[ ]:

# ikki obyekt o‘rtasidagi
# for takrorlashi orqali bajariluvchi funksiya
def distance_naive(xa, xb):
    # bunda umumiy masofani saqlaymiz
    s = 0
    # birinchi farqlar kvadratlarning
    # yig‘indisini topamiz
    for i in range(len(xa)):
        # ** 2 -> kvadratga oshirish amali
        s += (xa[i] - xb[i]) ** 2
    # Ildiz olish uchun ** 0.5
    s = s ** 0.5
    return s

# har doim tekshirib ko‘rish kerak
xa = [2, 3]
xb = [4, 5]
s = distance_naive(xa, xb)
# to‘giri javob:
# (4 - 2)*(4-2)+(5-3)*(5-3)=8
print("Javob:", s)
print("To‘giri javob:", 8 ** 0.5)

Javob: 2.8284271247461903
To'giri javob: 2.8284271247461903

  1. Navbatdagi qadamda x_start yangi obyekt va x o‘rtasidagi masofalarni hisoblab chiqish uchun bitta funksiya yozamiz hamda hisoblaymiz:

[ ]:

def distances_between_objects(x, x_star):
    # masofalarni saqlash uchun
    # bitta bo‘sh ro‘yxat
    d = []
    # x dagi obyektlar bo‘yicha takrorlash
    for x_i in x:
        # i-obyekt va x_start o‘rtasidagi masofa
        distance = distance_naive(x_i, x_star)
        # va masofani d ga qo‘shib qo‘yamiz
        d.append(distance)
    return d
d = distances_between_objects(x, x_star)

  1. Endi biz masofalarni ularning sinflari bilan tartiblab chiqishimiz zarur bo‘ladi. Buning uchun eng kichik element turgan o‘rini topib, shu o‘rini biror ro‘yxarga yozib quyamiz hamda shu ro‘yxatda bo‘lmagan elementlar ichidan eng kichigini qidiramiz. Tartiblash jarayonida biz qiymatlarning o‘rinlarini ham o‘sha tartib bo‘yicha joylashtirib chiqamiz, chunki bizga masofa eng muhimi emas, balki qaysi sinf obyekti yangi obyektga ko‘roq yaqinligini bilish muhim. Buning uchun ikkita for operatorini qo‘llaymiz. Buni ham funksiya ko‘rinishida yozamiz hamda faqat indeks bo‘yicha tartibni qaytaramiz:

[ ]:

def argsort_distances(d):
    # birinchi hamma masofalarni
    # nusxalab olamiz
    copy_d = []
    for i in d:
        copy_d.append(i)
    # endi sorted_dist tartiblaymiz
    # shunda d o‘zgarishsiz qoladi
    # indeks tartibini saqlash uchun
    # yana bitta bo‘sh ro‘yxat e'lon qilamiz
    argsort = []
    for i in range(len(d)):
        # element ichidan
        # eng kichik qiymatni qidirish
        # birinchi element eng kichik
        min_d = copy_d[0]
        min_index = 0
        for j in range(len(d)):
            # argsort ro‘yxatda j yo‘qmi
            if j not in argsort and min_d > copy_d[j]:
                min_d = copy_d[j]
                min_index = j
        # indeksni qo‘shib qo‘yamiz
        argsort.append(min_index)

    return argsort

argsort_d = argsort_distances(d)

  1. Endi esa har bir sinfdan nechtadan obyekt qatnashganligini birinchi eng yaqin k obyekt ichidan aniqlaymiz. Buning uchun biz \(\mathbf{y}\) dan foydalanamiz. Biz Pythonda indekslashni 0 dan boshlaganimiz uchun ham \(\mathbf{y}\) ning qiymatlari 0, 1, 2, 3 bo‘lishi mumkin. Buni ham funksiya sifatida yozamiz:

[ ]:

def count_class_objects(k, argsort_d, y):
    # bu qaysi sinfda
    # nechta obyekt borligini
    # sanab boradi
    # boshida 0 hamma sinf uchun
    stats = [0, 0, 0, 0]
    for i in range(k):
        # eng yaqin obyektning indeksi
        near_obj_index = argsort_d[i]
        # eng yaqin obyektning sinfi
        near_obj_class = y[near_obj_index]
        # bu 0, 1, 2, 3 bo‘lishi mumkin
        # stats da to‘rta element bor
        # mos element qiymatini bittaga
        # oshirib qo‘yamiz
        stats[near_obj_class] += 1
    return stats

stats = count_class_objects(16, argsort_d, y)

  1. Oxirida esa stats obyektidagi qiymatlarni chop qilish orqali qaysi sinf obyektlari eng ko‘p ekanligini ko‘rishimiz mumkin:

[9]:

for i in range(len(stats)):
    print(i+1, "-sinf obyektlari: ", stats[i], "ta")

1 -sinf obyektlari:  6 ta
2 -sinf obyektlari:  1 ta
3 -sinf obyektlari:  1 ta
4 -sinf obyektlari:  8 ta

  1. Demak yuqoridagi so‘ngi natijalar bilan oldingi natijalarmiz bir chiqdi. Lekin ushbu jarayoni Pythonda Numpy kutubxonasiz yozish juda ham qiyin bo‘ldi. Quyida ishbu jarayoni umumlashturuvchi yana bitta funskiya yozib qo‘ysak, keyinchalik boshqa to‘plamda NumPyda yozilgan kodlar bilan ushbu kodni solishtiramiz:

[10]:

def knn_naive(x, y, x_star, k):
    d = distances_between_objects(x, x_star)
    argsort_d = argsort_distances(d)
    stats = count_class_objects(k, argsort_d, y)
    for i in range(len(stats)):
        print(i+1, "-sinf obyektlari: ", stats[i], "ta")
knn_naive(x, y, x_star, 10)

1 -sinf obyektlari:  4 ta
2 -sinf obyektlari:  0 ta
3 -sinf obyektlari:  1 ta
4 -sinf obyektlari:  5 ta

Yuqorida qilingan ishlarni NumPy yordamida juda kam qatorlarda va tushunarli qilib yozish mumkin. Quyida biz bitta funksiya sifatida ushbu narsani amalga oshiramiz:

  1. x obyektlari va x_star o‘rtasidagi masofalarni topamiz. Buning uchun NumPyda shunchaki x - x_start kodini yozsak, biz mos elementlari o‘rtasidagi ayirmaga ega bo‘lamiz:

[ ]:

subs_x_start = x - x_star
print("o‘lchami x bilan bir xil: ", subs_x_start.shape)

O'lchami x bilan bir xil:  (40, 2)

  1. Endi har bir qiymatni kvadratga oshirib, har bir qator bo‘yicha yig‘sak hamda ularni element bo‘yicha kvadrat ildizga olsak, x va x_star orasidagi masofalarga ega bo‘lamiz:

[ ]:

# kvadratga oshirish
sqaures = subs_x_start ** 2
# qator bo‘yicha yig‘ish
row_sums = np.sum(sqaures, axis=1)
# va oxiri ildizga olish
d = row_sums ** 0.5

Yuqoridagi masofalarni topishni bitta qator qilib yozsak ham bo‘ladi, shunda yordamchi o‘zgaruvchilardan foydalanish zarurati tug‘ulmaydi:

[13]:

d = np.sum((x - x_star) ** 2, axis=1) ** 0.5

  1. Elementlarning tartibining o‘rnini olish uchun esa np.argsort() funksiyasidan foydalanamiz:

[14]:

argsort = np.argsort(d)

  1. Oxirgi har bir sinfda qanchadan obyekt borligini aniqlash uchun esa, birinchi argsort ning boshidan k tasini kesib olamiz hamda uni y ga indeks sifatida berish orqali eng yaqin k obyektning sinflarini topib olamiz:

[15]:

k = 16
near_k_class_labels = y[argsort[:k]]

  1. Shundan so‘ng har bir sinfda qanchadan obyekt borligini sanash uchun esa np.unique() funskiyasidan foydalanamiz. Ushbu funksiya ikkita numpy.ndarray turida vektor qaytaradi. Birinchi vektor ushbu uzatilgan vektordagi yagona elementlarning turini bildirsa, ikkinchisi esa har bir yagona elementdan nechtadan borligini bildiradi. Faqat har bir elementdan nechtadan borligini ham funskiya qaytarishi uchun biz funksiyaning return_counts=True agrumentini uzatishimiz zarur, quyidagicha:

[16]:

_, stats = np.unique(near_k_class_labels,
                     return_counts=True)

  1. Bularni birlashtirib bitta funskiya qilib yozsak, quyidagi sodda va qisqa kodga ega bo‘lamiz:

[17]:

def knn_numpy(x, y, x_star, k):
    d = np.sum((x - x_star) ** 2, axis=1) ** 0.5
    argsort_d = np.argsort(d)
    near_k_class_labels = y[argsort_d[:k]]
    _, stats = np.unique(near_k_class_labels,
                     return_counts=True)
    # Faqat chop qilish takrorlashi qoladi
    for i in range(len(stats)):
        print(i+1, "-sinf obyektlari: ", stats[i], "ta")
knn_numpy(x, y, x_star, 16)

1 -sinf obyektlari:  6 ta
2 -sinf obyektlari:  1 ta
3 -sinf obyektlari:  1 ta
4 -sinf obyektlari:  8 ta

NumPy orqali biz bor yo‘g‘i 9 qatordan iborat kod bilan k ta yaqin qo‘shni usulini ishlab chiqdik. Bu esa NumPyning qulayligini bizga namoyon etadi hamda bundan keyingi o‘rinlarda oddiy takrorlash operatorlaridan qayerda zarur bo‘lsa, foydalanib qolgan joylarda esa NumPyning imkoniyatlarini ishga solamiz.

Regressiya masalasi

Biz yuqorida classifikatsiya, ya’ni obyektlarni singlarga ajratish masalasini ko‘rib chiqdik. Boshqa so‘z bilan aytganda bizga \(\mathbb{X}=\{\mathbf{x}^{(1)}, ..., \mathbf{x}^{(M)}\}, \mathbf{x}^{(1)}\in \mathbb{R}^N\) to‘plam hamda uning har bir \(i\)-obyekti uchun maqsadli alomat \(y^{(i)}\in\{1, 2, \dots, K\}\) berilgan bo‘lsin deb ta’savur qilib yangi kelgan \(\mathbf{x}^{(*)}\) obyektning sinfini topish zarur edi. Bu masalaga e’tibor bersak, bizda ma’lum sondagi oldindan aniqlangan guruhlar(sinflar) bor, shuning uchun masalaning asosiy maqsadi yangi obyekt uchun uning sinfini topish. Endilikda aynan shu masalani sal chuquroq holda qarasak, ya’ni oldindan belgilangan guruhlar o‘rniga ixtiyoriy soni aniqlashni qarasak, u holda biz bu masalani sinflash deyishning o‘rniga regressiya muammosi deb ataymiz. Matematik yo‘l bilan aytadigan bo‘lsak, maqsadli alomat qiymati \(y^{(i)}\in\{1, 2, \dots, K\}\) biror to‘plamdan \(y^{(i)}\in\mathbb{R}\) haqiqiy to‘plamga o‘tadi. Albatta bu qiymat sohaga qarab ma’lum bir oraliqda bo‘ladi, masalan, inson yoshini aniqlamoqchi bo‘lsak, maqsadli alomat natural son va 0 dan 120 gacha chegaralangan bo‘ladi, ya’ni \(y^{(i)}\in\{0, 1, 2, \dots, 120\}\).

Endi qanday qilib ushbu masalani kNN usuli bilan ishlashni, birinchi matematik yo‘l bilan yozib chiqib keyin esa uni amaliy masalada o‘rganib chiqsak. Biz ushbu usulning o‘zgarishi zarur bo‘lgan qismlarini qaraymiz xolos, qolgan qismlarini esa sinflash masalasidagi bilan bir xil:

  1. yangi kelgan \(\mathbf{x}^{(*)}\) obyekt va to‘plamdagi obyektlar o‘rtasidagi masofani topamiz, ularni tartiblaymiz hamda ulardan eng yaqin k tasining \(y^{(i)}\in\mathbb{R}\) maqsadli almatlarining qiymatlarini tanlaymiz;

  2. eng yaqin k ta tanlangan obyektlarning alomatlarining o‘rtachasini topadigan bo‘lsak, u holda biz \(\mathbf{x}^{(*)}\) obyekt uchun maqsadli alomatni topgan bo‘lamiz.

Yuqoridagi algoritm juda ham sodda bo‘lib, biz k yaqin qo‘shnilar soni qanchaligini oldindan bilamiz deb yoki berilgan deb faraz qilyabmiz. Aslida bu faraz ko‘pincha mavjud bo‘lmaydi, ya’ni k bizga ma’lum bo‘lmaydi. Shuning uchun k ning qiymatini ham shu yerda qanday topish mumkinligi haqida ozroq so‘z yuritib, umumiy kodni yozishda k ni ham berilmagan deb qaraymiz, chunki shunday holat amaliy malasalarda ko‘proq uchraydi:

  1. Bu ishni qilish uchun biz k yaqin qo‘shnilar sonini avval 1, keyin 2, undan so‘ng 3, 4, 5, … deb tanlab ko‘rishimiz mumkin bo‘ladi;

  2. Bunday tanlashdagi eng asosiy muammo bu qaysi k yaxshiroq ekanligini baholovchi mezoni hali biz ishlab chiqmaganimizda. Shuning uchun keling, Mashinali o‘rganishga kirish qismizda o‘rgangan baholarga qaytsakda, ulardan regressiya masalasiga mosi bo‘lgan, masalan, "o‘rtacha absolyut xatolik (OAX)"ni olsak va k ni shu asosida tanlasak, ya’ni yaxshi yoki yomon desak. Namuna uchun, yaqin qo‘shnilar soni \(k=5\) bo‘lganda, OAX esa \(OAX_{k=5}=15\) va \(k=6\) bo‘lganda esa \(OAX_{k=6}=13\) bo‘lsa, u holda biz 6 ta yaqin qo‘shni yaxshiroq deymiz. Chunki qancha xatolik kichik bo‘lsa, model shuncha yaxshi ishlayabdi deyiladi.

  3. Keyingi bosqichda esa bizda qaysi yangi obyekt degan savol paydo bo‘ladi, chunki bizda yangi obyekt ham yo‘q hattoki yangi obyekt bo‘lganda ham u obyektning maqsadli alomatining aniq qiymatini bilmasdan, OAXni topa olmaymiz. Yangi obyketni boshqa joydan qidirishning o‘rniga, bizga berilgan to‘plamni, ya’ni o‘rgatuvchi to‘plamni tasodifan ikkita qismga ajrataylik. Masalan, birinchi qismni umumiy obyektlarning 80 foizini tashkil qilsa, keyingi qism esa 20 foizini. Bu kabi asl berilgan o‘rgatuvchi to‘plamni bo‘lishga, to‘g‘rirog‘i, birinchi qismni endi "o‘rgatuvchi(Training)" va ikkinchisini esa "Tasdiqlash(Validation)" to‘plami deb nomlaymiz. Shunda bizdagi tasdiqlash to‘plam paydo bo‘lib, undagi har bir obyektda \(y^{(i)}\in\mathbb{R}\) maqsadli qiymatlar mavjud bo‘ladi. Shunday ekan biz tasdiqlovchi to‘plamdan foydalanib nechta yaqin qo‘shni yaxshi ekanligini aniqlashimiz mumkin bo‘ladi.

  4. k ning eng mos qiymatini aniqlash uchun Tasdiqlash to‘plamidan olingan har bir obyektning maqsadli alomatini berilgan k ta yaqin qo‘shni bo‘yicha tekshirib ko‘ramiz va eng kichik xatolikni hosil qiluvchi k ni tanlaymiz.

To‘plam. Ushbu masalani yechishimiz uchun oldingi MNIST rasmlar to‘plami o‘rinli emas, chunki undagi masala sinflash masalasidir. Shuning uchun ham uyning bahosini ya’ni narxini hisoblab beruvchi to‘plamni olamiz. Ushbu bahoni hisoblash uchun biz quyidagi uyning sifatlaridan foydalanamiz:

#

Nomi

Ma’nosi

1

maydon(area)

Uyning yuzasi yoki maydonining hajmi.

2

yotoq xonalari(bedrooms)

Yoqot xonalari soni.

3

hammomlari(bathrooms)

hammomlar soni yoki yuvinish xonalari soni.

4

qavatlar(stories)

qavatlar soni.

5

asosiy yo‘l(main road)

Asosiy yo‘lga yaqinligi.

6

mehmonxona(guest room)

Mehmonxona mavjudligi.

7

yer to‘la(basement)

Yer to‘lasi mavjudligi.

8

issiq suv(hot qater heating)

Issiq suv mavjudligi.

9

havo moslagich (air conditioning)

Havo moslagich mavjudligi.

10

avto turargoh (parking)

Avto turargoh mavjudligi.

11

joylashuvi (prefarea)

Joylashgan o‘rnining qulayligi.

12

mebel holati (furnishing status)

Mebel mavjudligi.

13

narx (price)

Maqsadli alomat, uyning narxi.

Ushbu masalani yechish uchun quyidagi bosqichlardan foydalanamiz:

  1. calculate_OAX funksiya berilgan o‘rgatuvchi, tasdiqlash to‘plamini va yaqin qo‘shnilar sonini olib, bizga o‘rtacha absolyut xatolikni qaytaradi:

[ ]:

def calculate_OAX(x_train, y_train, x_val, y_val, k):
    # x_train, y_train mos ravishda o‘rgatuvchi to‘plami va uning maqsadli alomati
    # x_val, y_val mos ravishda tasdiqlash to‘plami va uning maqsadli alomati
    # k joriy yaqin qo‘shnilar soni

    # 1. har bir x_valdagi obyekt uchun k ta yaqin qo‘shniga
    # asoslanib bashorat qilingan maqsadli alomat qiymatini topamiz
    # va uni y_pred_val deb nomlaymiz.
    # o‘lchami y_val bilan bir xil bo‘ladi, shuning uchun
    # hammasi boshida 0 ga teng
    y_pred_val = np.zeros_like(y_val)

    # 2. x_valdagi har bir obyekt bo‘yicha takrorlash amali
    # x_valdagi obyektlar soni x_val.shape[0]
    for i in range(x_val.shape[0]):
        # 2.1 x_val[i] obyekt biz uchun yangi obyekt hisoblanadi
        x_star = x_val[i]
        # 2.2 x_star va x_train o‘rgatuvchi to‘plamdagi har bir obyekt
        # o‘rtasidagi masofani topamiz.
        # Evklid masofasidan foydalanamiz.
        d = np.sum((x_train - x_star) ** 2, axis=1) ** 0.5
        # 2.3 masofalarni tartiblaymiz
        argsort_d = np.argsort(d)
        # 2.4 Yaqin obyektlarning maqsadli qiymatlari
        near_k_class_labels = y_train[argsort_d[:k]]
        # 2.4 maqsadli qiymatlarning o‘rtachasi
        y_pred_val[i] = np.mean(near_k_class_labels)

    # 3. bashorat qilingan y_pred_val bilan y_val haqiqiy
    # qiymatlar o‘rtasidagi OAX topamiz
    oax = np.mean(np.abs(y_pred_val - y_val))
    return oax

  1. Endi to‘plamni NumPy yordamida o‘qib olamiz. Buning uchun loadtxt funksiyasidan foydalanamiz.

[ ]:

# nisbiy yo‘lni ko‘rsatish uchun biz bitta nuqta (.) - shu joriy o‘rin
# ikki nuqta (..) ota (oldingi) o‘rinlardan foydalanamiz
data = np.loadtxt('.././../datasets/housing.csv',
                  skiprows=1, # birinchi qator sarlavha, tashlab ketamiz
                  delimiter=',' # ustunlar orasidagi ajratuvchi vergul ,
)
# Birinchi ustunda oxirigacha yuqoridagi jadvaldagi qiymatlar
X = data[:, 1:]
# nolinchi ustunda esa maqsadli qiymatlar joylashgan
y = data[:, 0]
print("To‘plamdagi obyektlar soni:", y.shape[0])

To'plamdagi obyektlar soni: 545

  1. Keyingi navbatda to‘plamni 3 ta qismga ajratib olamiz: o‘rgatuvchi (300 ta obyekt), tasdiqlash (145 ta obyekt) va test to‘plamlarga (100 ta obyekt). Faqat shunchaki hozirda turgan tartibda obyektlarni olish bir qancha xatoliklarga olib kelishi mumkin, shuning uchun birinchi obyektlarni biror indeks bo‘yicha aralashtirib, keyin qismlarga ajratamiz.

[ ]:

# Har bir to‘plamdagi obyektlar soni
num_train = 300
num_val = 145
num_test = 100

# joriy tartib bo‘yicha indekslar
indices = np.arange(data.shape[0])
# har doim natijani bir xil ekangligini baholash uchun
# bir xil tartib, lekin aralashgan tartib
np.random.seed(42)
np.random.shuffle(indices)

# aralashtirilgan indekslar bo‘yicha
# obyektlarni olish
# buning uchun boshidan birinchi num_train olish yeatrli
X_tr = X[indices[:num_train]]
y_tr = y[indices[:num_train]]

# tasdiqlash to‘plami uchun num_train dan boshlab
X_va = X[indices[num_train:num_train+num_val]]
y_va = y[indices[num_train:num_train+num_val]]

# test to‘plami uchun num_train+num_val dan boshlab
# oxirigacha
X_te = X[indices[num_train+num_val:]]
y_te = y[indices[num_train+num_val:]]

  1. Quyida biz o‘rganayotgan usullar samarali ishlashi uchun qiymatlarni bir xil o‘lchamda bo‘lishi muhim ahamiyat kasb etadi. Shuning uchun ham quyidagi har bir alomat qiymatni shu alomatdagi eng katta qiymatga bo‘lib qo‘yish orqali bir xil o‘lchamga erishish mumkin. Shunda har bir qiymat 0 dan 1 gacha intervalda bo‘ladi. Masalan, eng ko‘p xonali uyda 15 ta yotoqxona bor deb aytaylik, shunda boshqa hamma uydagi yotoqxonalar sonini 15 ga bo‘lsal, qaysi uyda 15 ta yotoqxona bo‘lsa, ularning qiymati 1 ga teng bo‘ladi. Qolganlari esa 1 dan kichik bo‘ladi:

[ ]:

# har bir ustun(alomat) bo‘yicha
# eng katta qiymatlarni topish
x_tr_max = X_tr.max(axis=0)

# va har bir alomatni o‘ziga
# mos eng katta qiymatga bo‘lish
X_tr = X_tr / x_tr_max
X_va = X_va / x_tr_max
X_te = X_te / x_tr_max

  1. Keyingi bosqichda esa, biz nechta yaqin qo‘shni yaxshi ekanligini baholashimiz zarur bo‘ladi. Buning uchun biz oldindan qaysi yaqin qo‘shnilar bo‘yicha hisoblab chiqamiz shuni ko‘rishimiz zarur:

[ ]:

# biz xohlagan yaqin qo‘shnilar soni bo‘yicha takrorlash
# boshqa sonlar bilan ham tekshirib ko‘rishingiz mumkin
for k in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25]:
    # ushbu k ga nisbatan o‘rtacha absolyut xatolik
    oax_k = calculate_OAX(X_tr, y_tr, X_va, y_va, k)
    print("yaqin qo‘shnilar soni", k,
          "ga teng bo‘lganda, o‘rtacha xatolik",
          oax_k)

yaqin qo'shnilar soni 1 ga teng bo'lganda, o'rtacha xatolik 946116.6206896552
yaqin qo'shnilar soni 2 ga teng bo'lganda, o'rtacha xatolik 947447.8275862068
yaqin qo'shnilar soni 3 ga teng bo'lganda, o'rtacha xatolik 899425.8160919541
yaqin qo'shnilar soni 4 ga teng bo'lganda, o'rtacha xatolik 829690.9310344828
yaqin qo'shnilar soni 5 ga teng bo'lganda, o'rtacha xatolik 829319.448275862
yaqin qo'shnilar soni 6 ga teng bo'lganda, o'rtacha xatolik 791071.8505747126
yaqin qo'shnilar soni 7 ga teng bo'lganda, o'rtacha xatolik 759604.0689655172
yaqin qo'shnilar soni 8 ga teng bo'lganda, o'rtacha xatolik 737342.948275862
yaqin qo'shnilar soni 9 ga teng bo'lganda, o'rtacha xatolik 741064.4137931034
yaqin qo'shnilar soni 10 ga teng bo'lganda, o'rtacha xatolik 740535.551724138
yaqin qo'shnilar soni 15 ga teng bo'lganda, o'rtacha xatolik 770770.3218390805
yaqin qo'shnilar soni 20 ga teng bo'lganda, o'rtacha xatolik 798247.2931034482
yaqin qo'shnilar soni 25 ga teng bo'lganda, o'rtacha xatolik 790410.3586206896

Yuqoridagi natijalarni kuzatadigan bo‘lsak, u holda biz yaqin qo‘shnilar soni 8 ta bo‘lganda xatolik eng kichik bo‘lganini anglaymiz, ya’ni 737 343. Agar yaxshilab e’tibor bersak bu xatolik yetarlicha katta. Boshqacha qilib aytganda biz qurgan model katta xatolik bilan ishlayabdi. Albatta bunday xatolik yaxshi emas, shuning uchun boshqa yaxshiroq algorimtlarni ishlatish zarur bo‘ladi yoki yuqoridagi jadvaldagi 12 turdagi qiymat uyning narxini juda ham to‘g‘iri ifodala olmaydi.

  1. Oxirgi qadam sifatida yuqoridagi eng kam xatolik bo‘yicha, test to‘plamda algoritmning xatoligini baholab qo‘yaylik:

[ ]:

oax_k = calculate_OAX(X_tr, y_tr, X_te, y_te, k)
print("yaqin qo‘shnilar soni", k,
        "ga teng bo‘lganda, o‘rtacha xatolik",
        oax_k)

yaqin qo'shnilar soni 25 ga teng bo'lganda, o'rtacha xatolik 890499.96

Odatda test to‘plamdagi xatolik tasqidlash to‘plamigaga qaraganda kattaroq bo‘ladi. Bu yerda ham shuni kuzatdik. Qisqacha xulosa qilib aytsak har bir algoritmda kamchiliklar bor. Shu sababli, ushbu algoritmda ham regressiya masalasida yetarlicha katta xatolik mavjud. Shuning uchun ham juda ko‘p boshqa usullarni o‘rganib chiqishimiz zarur bo‘ladi.