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.

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.

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.

# 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:

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:

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

2. 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)

3. 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)

4. 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)

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

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

6. 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:

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'lshami x bilan bir xil:  (40, 2)

2. 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:

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

3. Elementlarning tartibining o’rnini olish uchun esa np.argsort() funksiyasidan foydalanamiz:

argsort = np.argsort(d)

4. 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:

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

5. 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:

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

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

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. Keyinchalik tezligini ham ko’rib chiqamiz.

Davomi….

data = np.loadtxt('/home/tqqt1/AI/teachings/online-courses/ai_intro/datasets/Dry_Bean_Dataset.csv',
           skiprows=1,
           delimiter=',')
X = data[:, :-1]
y = data[:, -1].astype(int)

1. Underfitting - kam o’rganish

2. Just (Well) fitting - yaxshi o’rganish

3. Overfitting - Me’yoridan ortiq o’rganish

1. Manhattan

\(p(a,b)=\sum_{i=1}^{n}|a_i-b_i|\)

2. Euclidean

\(p(a,b)=\sqrt{\sum_{i=1}^{n}(a_i-b_i)^2}\)

4. Minkowski

\(p(a,b)=(\sum_{i=1}^{n}(a_i-b_i)^p)^{\frac{1}{p}}\)

Vaznlashgan Knn

D = np.zeros((num_val, num_train))
# val to'plam bo'yicha loop
i = 0
while i < num_val:
    # train to'plam bo'yicha loop
    j = 0
    while j < num_train:
        # Manhattan
        # D[i, j] = np.sum(np.abs(X_va[i] - X_tr[j]))
        # Euclidean
        D[i, j] = np.sqrt(np.sum((X_va[i] - X_tr[j]) ** 2))
        j += 1 # j = j + 1
    i += 1 # i = i + 1
D_argsort = np.argsort(D, axis=1)

k_best = 0
acc_best = 0

k = 2

while k < 100:
    y_pred = np.zeros_like(y_va)
    i = 0
    while i < num_val:
        y_k = y_tr[D_argsort[i, :k]]

        D_k = D[i, :k]
        D_k_sum = np.sum(D_k)
        D_k_1 = D_k / D_k_sum
        D_k_2 = 1 - D_k_1
        w = D_k_2 / (k - 1)

        probs = np.zeros(y_tr.max()+1)
        j = 0
        while j < y_tr.max()+1:
            probs[j] = np.sum(w[y_k == j])
            j += 1

        y_pred[i] = np.argmax(probs)


        i += 1
    A = np.mean(y_pred == y_va)
    # print(f"k={k} da aniqlik: {A:.4f}")
    if A > acc_best:
        acc_best = A
        k_best = k
    k += 1 # k = k + 1

print(f"Eng yaxshi aniqlik {acc_best:.4f} {k_best} ta yaqin qo'shnida...")

Eng yaxshi aniqlik 0.9153 40 ta yaqin qo'shnida...

D = np.zeros((num_test, num_train))
# val to'plam bo'yicha loop
i = 0
while i < num_test:
    # train to'plam bo'yicha loop
    j = 0
    while j < num_train:
        # D[i, j] = np.sum(np.abs(X_te[i] - X_tr[j]))
        D[i, j] = np.sqrt(np.sum((X_te[i] - X_tr[j]) ** 2))
        j += 1 # j = j + 1
    i += 1 # i = i + 1
D_argsort = np.argsort(D, axis=1)

y_pred = np.zeros_like(y_te)
i = 0
while i < num_test:
    y_k = y_tr[D_argsort[i, :k]]

    D_k = D[i, :k]
    D_k_sum = np.sum(D_k)
    D_k_1 = D_k / D_k_sum
    D_k_2 = 1 - D_k_1
    w = D_k_2 / (k - 1)

    probs = np.zeros(y_tr.max()+1)
    j = 0
    while j < y_tr.max()+1:
        probs[j] = np.sum(w[y_k == j])
        j += 1

    y_pred[i] = np.argmax(probs)

    i += 1
A = np.mean(y_pred == y_te)

print(f"Testning aniqlik {A:.4f} {k_best} ta yaqin qo'shnida...")

Testning aniqlik 0.9002 40 ta yaqin qo'shnida...