{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# K ta yaqin qo'shni usuli\n", "\n", "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.\n", "\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Classifikatsiya masalasi\n", "\n", "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.\n", "\n", "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.\n", "\n", "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.\n", "\n", "![k ta yaqin qo'shni usuli](./images/knn_illustration.svg)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:\n", "\n", "|Sinf nomi| Obyektlar soni|\n", "|----|-----|\n", "|1-sinf| 6|\n", "|2-sinf| 1|\n", "|3-sinf| 1|\n", "|4-sinf| 8|\n", "|Jami| 16|\n", "\n", "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:\n", "\n", "|Sinf nomi| Obyektlar soni|\n", "|----|-----|\n", "|1-sinf| 2|\n", "|2-sinf| 0|\n", "|3-sinf| 0|\n", "|4-sinf| 3|\n", "|Jami| 5|\n", "\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:\n", "\n", "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)})\\}$;\n", "\n", "2. Bundan keyin esa nechta yaqin qo'shniga e'tibor berishimiz kerakligini $k$ o'zgaruvchisi orqali ifodalaylik;\n", "\n", "3. Ushbu navbatda esa ushbu $\\mathbf{d}$ vektorini qiymatlarining tartibi asosida o'rinlarini $\\mathbf{d}_{argsort}=argsort(\\mathbf{d})$ o'zlashtirsak olsak;\n", "\n", "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;\n", "\n", "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.\n", "\n", "6. Oxirida esa $\\mathbf{x}^{(*)}$ obyekt sinfini $y^{(*)}=argmax(\\mathbf{s})$ ko'rinishida topamiz.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Bu kodlarni tekshirish uchun kerak\n", "%load_ext autoreload\n", "%autoreload 2" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/markdown": [ "|$x_1$|$x_2$|$x_1$|$x_2$|$x_1$|$x_2$|$x_1$|$x_2$|\n", "|---|---|---|---|---|---|---|---|\n", "|1.50|-1.14|2.47|0.77|-1.26|2.17|-2.48|-1.19|\n", "|1.65|0.52|1.07|-0.42|-2.12|1.70|-3.11|-2.20|\n", "|0.77|-1.23|0.46|1.11|-3.48|1.28|-1.19|0.36|\n", "|2.58|-0.23|-0.15|1.38|-2.46|3.06|-2.07|0.00|\n", "|0.53|-0.46|0.40|0.71|-1.66|0.24|-1.64|-1.65|\n", "|0.54|-1.47|0.40|2.85|-1.68|1.61|-1.64|0.54|\n", "|1.24|-2.91|0.99|-0.06|-2.68|2.61|-2.04|0.56|\n", "|-0.72|-1.56|1.82|-0.22|-0.97|2.93|-4.62|-0.18|\n", "|-0.01|-0.69|1.21|-0.96|-2.84|1.69|-1.91|-1.30|\n", "|0.09|-2.41|-0.33|1.20|-1.67|2.98|-1.91|-2.99|\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# ushbu kod orqali biz obyekt qiymatlarini \n", "# yuklaymiz hamda ularni darslikka \n", "# jadval shaklida qo'shamiz\n", "# BU KODLARNI KEYINCHALIK O'RGANAMIZ\n", "from IPython.display import Markdown, display\n", "from utils import knn_illustration_dataset\n", "import numpy as np\n", "\n", "# to'rta sinf obyektlari va \n", "# ularning qayis sinfga tegishliligi\n", "# yangi obyekt x_star\n", "# hamda ular o'rtasidagi masofa\n", "# va jadval\n", "(x, y, x_star, dists,\n", " mark_table,\n", " mark_dist_table,\n", " mark_dist_sort_table) = knn_illustration_dataset()\n", "display(Markdown(mark_table))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/markdown": [ "|Sinf|1|2|3|4|5|6|7|8|9|10|\n", "|---|---|---|---|---|---|---|---|---|---|---|\n", "|1-sinf|2.50|3.05|1.78|3.66|1.62|1.61|2.95|0.63|1.04|1.79|\n", "|2-sinf|3.89|2.15|2.56|2.52|2.21|4.10|2.20|2.93|2.21|2.30|\n", "|3-sinf|3.18|2.92|3.37|4.31|1.40|2.70|3.98|3.93|3.26|4.03|\n", "|4-sinf|1.49|2.42|1.37|1.47|0.91|1.67|1.88|3.71|0.96|2.19|" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(Markdown(mark_dist_table))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Keyingi jadvalda esa ushbu masofalarning tartiblangan ko'rinishi va joriy obyektning qaysi sinfga tegishli ekanligi keltirilgan:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/markdown": [ "|#|$(x^{(*)}, x^{(i)})$|Sinfi|\n", "|---|----|----|\n", "|1|0.63|1.0-sinf|\n", "|2|0.91|4.0-sinf|\n", "|3|0.96|4.0-sinf|\n", "|4|1.04|1.0-sinf|\n", "|5|1.37|4.0-sinf|\n", "|6|1.40|3.0-sinf|\n", "|7|1.47|4.0-sinf|\n", "|8|1.49|4.0-sinf|\n", "|9|1.61|1.0-sinf|\n", "|10|1.62|1.0-sinf|\n", "|11|1.67|4.0-sinf|\n", "|12|1.78|1.0-sinf|\n", "|13|1.79|1.0-sinf|\n", "|14|1.88|4.0-sinf|\n", "|15|2.15|2.0-sinf|\n", "|16|2.19|4.0-sinf|\n", "|17|2.20|2.0-sinf|\n", "|18|2.21|2.0-sinf|\n", "|19|2.21|2.0-sinf|\n", "|20|2.30|2.0-sinf|\n", "|21|2.42|4.0-sinf|\n", "|22|2.50|1.0-sinf|\n", "|23|2.52|2.0-sinf|\n", "|24|2.56|2.0-sinf|\n", "|25|2.70|3.0-sinf|\n", "|26|2.92|3.0-sinf|\n", "|27|2.93|2.0-sinf|\n", "|28|2.95|1.0-sinf|\n", "|29|3.05|1.0-sinf|\n", "|30|3.18|3.0-sinf|\n", "|31|3.26|3.0-sinf|\n", "|32|3.37|3.0-sinf|\n", "|33|3.66|1.0-sinf|\n", "|34|3.71|4.0-sinf|\n", "|35|3.89|2.0-sinf|\n", "|36|3.93|3.0-sinf|\n", "|37|3.98|3.0-sinf|\n", "|38|4.03|3.0-sinf|\n", "|39|4.10|2.0-sinf|\n", "|40|4.31|3.0-sinf|" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(Markdown(mark_dist_sort_table))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "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 `list`i o'zgaruvchisi kabi ishlaydi, ya'ni tayyor funksiyalardan foydalanmaymiz. \n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Javob: 2.8284271247461903\n", "To'giri javob: 2.8284271247461903\n" ] } ], "source": [ "# ikki obyekt o'rtasidagi\n", "# for takrorlashi orqali bajariluvchi funksiya\n", "def distance_naive(xa, xb):\n", " # bunda umumiy masofani saqlaymiz\n", " s = 0\n", " # birinchi farqlar kvadratlarning\n", " # yig'indisini topamiz\n", " for i in range(len(xa)):\n", " # ** 2 -> kvadratga oshirish amali\n", " s += (xa[i] - xb[i]) ** 2\n", " # Ildiz olish uchun ** 0.5\n", " s = s ** 0.5\n", " return s\n", "\n", "# har doim tekshirib ko'rish kerak\n", "xa = [2, 3]\n", "xb = [4, 5]\n", "s = distance_naive(xa, xb)\n", "# to'giri javob:\n", "# (4 - 2)*(4-2)+(5-3)*(5-3)=8\n", "print(\"Javob:\", s)\n", "print(\"To'giri javob:\", 8 ** 0.5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Navbatdagi qadamda `x_start` yangi obyekt va `x` o'rtasidagi masofalarni hisoblab chiqish uchun bitta funksiya yozamiz hamda hisoblaymiz:" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [], "source": [ "def distances_between_objects(x, x_star):\n", " # masofalarni saqlash uchun\n", " # bitta bo'sh ro'yxat\n", " d = []\n", " # x dagi obyektlar bo'yicha takrorlash\n", " for x_i in x:\n", " # i-obyekt va x_start o'rtasidagi masofa\n", " distance = distance_naive(x_i, x_star)\n", " # va masofani d ga qo'shib qo'yamiz\n", " d.append(distance)\n", " return d\n", "d = distances_between_objects(x, x_star)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [], "source": [ "def argsort_distances(d):\n", " # birinchi hamma masofalarni\n", " # nusxalab olamiz\n", " copy_d = []\n", " for i in d:\n", " copy_d.append(i)\n", " # endi sorted_dist tartiblaymiz\n", " # shunda d o'zgarishsiz qoladi\n", " # indeks tartibini saqlash uchun\n", " # yana bitta bo'sh ro'yxat e'lon qilamiz\n", " argsort = []\n", " for i in range(len(d)):\n", " # element ichidan\n", " # eng kichik qiymatni qidirish\n", " # birinchi element eng kichik\n", " min_d = copy_d[0]\n", " min_index = 0\n", " for j in range(len(d)):\n", " # argsort ro'yxatda j yo'qmi\n", " if j not in argsort and min_d > copy_d[j]:\n", " min_d = copy_d[j]\n", " min_index = j\n", " # indeksni qo'shib qo'yamiz\n", " argsort.append(min_index)\n", "\n", " return argsort\n", "\n", "argsort_d = argsort_distances(d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [], "source": [ "def count_class_objects(k, argsort_d, y):\n", " # bu qaysi sinfda\n", " # nechta obyekt borligini\n", " # sanab boradi\n", " # boshida 0 hamma sinf uchun\n", " stats = [0, 0, 0, 0]\n", " for i in range(k):\n", " # eng yaqin obyektning indeksi\n", " near_obj_index = argsort_d[i]\n", " # eng yaqin obyektning sinfi\n", " near_obj_class = y[near_obj_index]\n", " # bu 0, 1, 2, 3 bo'lishi mumkin\n", " # stats da to'rta element bor\n", " # mos element qiymatini bittaga \n", " # oshirib qo'yamiz\n", " stats[near_obj_class] += 1\n", " return stats\n", "\n", "stats = count_class_objects(16, argsort_d, y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "5. Oxirida esa `stats` obyektidagi qiymatlarni chop qilish orqali qaysi sinf obyektlari eng ko'p ekanligini ko'rishimiz mumkin:" ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 -sinf obyektlari: 6 ta\n", "2 -sinf obyektlari: 1 ta\n", "3 -sinf obyektlari: 1 ta\n", "4 -sinf obyektlari: 8 ta\n" ] } ], "source": [ "for i in range(len(stats)):\n", " print(i+1, \"-sinf obyektlari: \", stats[i], \"ta\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 -sinf obyektlari: 4 ta\n", "2 -sinf obyektlari: 0 ta\n", "3 -sinf obyektlari: 1 ta\n", "4 -sinf obyektlari: 5 ta\n" ] } ], "source": [ "def knn_naive(x, y, x_star, k):\n", " d = distances_between_objects(x, x_star)\n", " argsort_d = argsort_distances(d)\n", " stats = count_class_objects(k, argsort_d, y)\n", " for i in range(len(stats)):\n", " print(i+1, \"-sinf obyektlari: \", stats[i], \"ta\")\n", "knn_naive(x, y, x_star, 10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Yuqorida qilingan ishlarni NumPy yordamida juda kam qatorlarda va tushunarli qilib yozish mumkin. Quyida biz bitta funksiya sifatida ushbu narsani amalga oshiramiz:\n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "O'lshami x bilan bir xil: (40, 2)\n" ] } ], "source": [ "subs_x_start = x - x_star\n", "print(\"O'lchami x bilan bir xil: \", subs_x_start.shape)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [], "source": [ "# kvadratga oshirish\n", "sqaures = subs_x_start ** 2\n", "# qator bo'yicha yig'ish\n", "row_sums = np.sum(sqaures, axis=1)\n", "# va oxiri ildizga olish\n", "d = row_sums ** 0.5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Yuqoridagi masofalarni topishni bitta qator qilib yozsak ham bo'ladi, shunda yordamchi o'zgaruvchilardan foydalanish zarurati tug'ulmaydi:" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [], "source": [ "d = np.sum((x - x_star) ** 2, axis=1) ** 0.5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3. Elementlarning tartibining o'rnini olish uchun esa `np.argsort()` funksiyasidan foydalanamiz:" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [], "source": [ "argsort = np.argsort(d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [], "source": [ "k = 16\n", "near_k_class_labels = y[argsort[:k]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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:" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [], "source": [ "_, stats = np.unique(near_k_class_labels,\n", " return_counts=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "6. Bularni birlashtirib bitta funskiya qilib yozsak, quyidagi sodda va qisqa kodga ega bo'lamiz:" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 -sinf obyektlari: 6 ta\n", "2 -sinf obyektlari: 1 ta\n", "3 -sinf obyektlari: 1 ta\n", "4 -sinf obyektlari: 8 ta\n" ] } ], "source": [ "def knn_numpy(x, y, x_star, k):\n", " d = np.sum((x - x_star) ** 2, axis=1) ** 0.5\n", " argsort_d = np.argsort(d)\n", " near_k_class_labels = y[argsort_d[:k]]\n", " _, stats = np.unique(near_k_class_labels,\n", " return_counts=True)\n", " # Faqat chop qilish takrorlashi qoladi\n", " for i in range(len(stats)):\n", " print(i+1, \"-sinf obyektlari: \", stats[i], \"ta\")\n", "knn_numpy(x, y, x_star, 16)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Davomi...." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "data = np.loadtxt('/home/tqqt1/AI/teachings/online-courses/ai_intro/datasets/Dry_Bean_Dataset.csv',\n", " skiprows=1,\n", " delimiter=',')\n", "X = data[:, :-1]\n", "y = data[:, -1].astype(int)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. Underfitting - kam o'rganish\n", "2. Just (Well) fitting - yaxshi o'rganish\n", "3. Overfitting - Me'yoridan ortiq o'rganish" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "1. Manhattan\n", "\n", "$p(a,b)=\\sum_{i=1}^{n}|a_i-b_i|$\n", "\n", "2. Euclidean\n", "\n", "$p(a,b)=\\sqrt{\\sum_{i=1}^{n}(a_i-b_i)^2}$\n", "\n", "4. Minkowski\n", "\n", "$p(a,b)=(\\sum_{i=1}^{n}(a_i-b_i)^p)^{\\frac{1}{p}}$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Vaznlashgan Knn" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "D = np.zeros((num_val, num_train))\n", "# val to'plam bo'yicha loop\n", "i = 0\n", "while i < num_val:\n", " # train to'plam bo'yicha loop\n", " j = 0\n", " while j < num_train:\n", " # Manhattan\n", " # D[i, j] = np.sum(np.abs(X_va[i] - X_tr[j]))\n", " # Euclidean\n", " D[i, j] = np.sqrt(np.sum((X_va[i] - X_tr[j]) ** 2))\n", " j += 1 # j = j + 1\n", " i += 1 # i = i + 1\n", "D_argsort = np.argsort(D, axis=1)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Eng yaxshi aniqlik 0.9153 40 ta yaqin qo'shnida...\n" ] } ], "source": [ "k_best = 0\n", "acc_best = 0\n", "\n", "k = 2\n", "\n", "while k < 100:\n", " y_pred = np.zeros_like(y_va)\n", " i = 0\n", " while i < num_val:\n", " y_k = y_tr[D_argsort[i, :k]]\n", " \n", " D_k = D[i, :k]\n", " D_k_sum = np.sum(D_k)\n", " D_k_1 = D_k / D_k_sum\n", " D_k_2 = 1 - D_k_1\n", " w = D_k_2 / (k - 1)\n", "\n", " probs = np.zeros(y_tr.max()+1)\n", " j = 0\n", " while j < y_tr.max()+1:\n", " probs[j] = np.sum(w[y_k == j])\n", " j += 1\n", "\n", " y_pred[i] = np.argmax(probs)\n", " \n", " \n", " i += 1\n", " A = np.mean(y_pred == y_va)\n", " # print(f\"k={k} da aniqlik: {A:.4f}\")\n", " if A > acc_best:\n", " acc_best = A\n", " k_best = k\n", " k += 1 # k = k + 1\n", "\n", "print(f\"Eng yaxshi aniqlik {acc_best:.4f} {k_best} ta yaqin qo'shnida...\")" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [], "source": [ "D = np.zeros((num_test, num_train))\n", "# val to'plam bo'yicha loop\n", "i = 0\n", "while i < num_test:\n", " # train to'plam bo'yicha loop\n", " j = 0\n", " while j < num_train:\n", " # D[i, j] = np.sum(np.abs(X_te[i] - X_tr[j]))\n", " D[i, j] = np.sqrt(np.sum((X_te[i] - X_tr[j]) ** 2))\n", " j += 1 # j = j + 1\n", " i += 1 # i = i + 1\n", "D_argsort = np.argsort(D, axis=1)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Testning aniqlik 0.9002 40 ta yaqin qo'shnida...\n" ] } ], "source": [ "y_pred = np.zeros_like(y_te)\n", "i = 0\n", "while i < num_test:\n", " y_k = y_tr[D_argsort[i, :k]]\n", " \n", " D_k = D[i, :k]\n", " D_k_sum = np.sum(D_k)\n", " D_k_1 = D_k / D_k_sum\n", " D_k_2 = 1 - D_k_1\n", " w = D_k_2 / (k - 1)\n", "\n", " probs = np.zeros(y_tr.max()+1)\n", " j = 0\n", " while j < y_tr.max()+1:\n", " probs[j] = np.sum(w[y_k == j])\n", " j += 1\n", "\n", " y_pred[i] = np.argmax(probs)\n", " \n", " i += 1\n", "A = np.mean(y_pred == y_te)\n", "\n", "print(f\"Testning aniqlik {A:.4f} {k_best} ta yaqin qo'shnida...\")" ] } ], "metadata": { "kernelspec": { "display_name": "ai_courses", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.0" } }, "nbformat": 4, "nbformat_minor": 2 }