Eng yaqin qo’shni algoritmi

Eng sodda va tushunarli bo’lgan algoritmlardan biri bu ‘Eng yaqin qo’shni’ algoritmidir. Biz bundan oldingi bo’limda MNIST raqmlari yozilgan to’plam bilan ishlab rasmlardagi raqamlarni aniqlovchi dastur tuzdik va undan natijalar oldik. Ushbu dasturda foydalangan algoritmimiz bu ‘Eng yaqin qo’shni’ algoritmidir. Ushbu qismda biz shu algoritmni chuqoroq tahlil qilib, matematik usulda ifodalashga harakat qilamiz.

Buning uchun keling birinchi navbatda uning geometrik ma’nozini tushinishga harakat qilib ko’raylik. Yuqoridagi dasturda biz har bir rasmni 28 ga 28 piksellarda ifodaladik, bu esa 784 o’lchamli vektor degani va bu o’lchamni biz geometrik tarzda tasvirlay olmaymiz. Shuning uchun yuqoridagi masalani boshqa juda sodda masalaga almashtiramiz. Tasavur qilaylik, it va bo’rilar faqat bo’yi va uzunligi (boshidan dumigacha bo’lgan uzunlik) bilan vektor ko’rinishida berilgan. Masalan, quyidagi 2 o’lchovli koordinatalar sistemasida ulardan bir nechtasi berilgan.

Ushbu rasmda uch xil turdagi shakllar joylashgan: aylana itlarni ifodalaydi, uchburchak bo’rilarni va oxirgi ‘X’ belgisi esa yangi bizga berilgan hayvoni ifodalaydi. Bu shu yangi hayvon itmi yoki bo’rimi shuni aytishimiz kerak. Buni esa shu rasmga qarab bu hayvon itlarga yaqin bo’lsa, uni it deymiz, aks holda uni bo’ri deymiz. Hozirgi holda bu albatta bo’ri. Buning uchun biz ushbu yangi hayvonga eng yaqin bo’lgan hayvonni topshimiz kerak bu hayvon bo’ri bo’lgani uchun ham biz yangi hayvoni bo’ri turiga masub deymiz. Ushbu sodda masalani geometrik usulda tushunish qiyin emas. Lekin birinchi rasmlardagi raqam masalasini esa bu kabi chimza yordamida tasvirlab bo’lmaydi. Uning o’rniga biz u shunchaki tasavur qilib ishlaymiz.

Oldingi misolni yechishda biz hozirgidek sodda chizmadan emas balki ularning orasidagi masofani topish uchun maxsus masofa \(\rho (\mathbf{x},\mathbf{y})\) funksiyasidan foydalandik. Hamda ixtiyoriy rasm berilsa unni bizda oldindan mavjud bo’lgan rasmlar bilan solishtirib unga eng yaqinini topdik va shu orqali yangi kelgan rasmda qanday raqam bor ekanligini aniqladik.