11-Mavzu. O’qituvchisiz (Unsupervised) o’qitish algoritmlari Reja: O’qituvchisiz o’qitish tushunchasi va uning usullari

5.2. K eng yaqin qo'shnilarni izlash algoritmi
K eng yaqin qo’shnilar (K Nearest Neighbours (KNN)) algoritmi - bu sinflash uchun ham, regressiyani bashorat qilish masalalari uchun ham qo'llanilishi mumkin bo'lgan mashinali o’qitish algoritmlarining bir turi hisoblanadi. Biroq, u asosan sanoatdagi bashoratli masalalarni sinflash uchun ishlatiladi.
KEYQ algoritmining ishlashi. KEYQ algoritmi yangi ma'lumotlar nuqta (obyekt, hodisa, jarayon)larining qiymatlarini bashorat qilishda "Xususiyatlar o'xshashligi" dan foydalanadi, ya'ni yangi ma'lumotlar nuqtalariga o'quv tanlanmadagi nuqtalarga mos kelishiga qarab qiymatlar beriladi. Ushbu algoritmning ishlashi quyidagi qadamlardan iborat:
1-qadam. O’quv tanlanma va sinov tanlanma skallantiriladi va kompyuterga yuklanadi.
2-qadam. O’quv tanlanmadan K ta yaqin qo’shnilar (nuqtalar) tanlanadi. K ixtiyoriy butun son bo’ishi mumkin.
3-qadam. Sinov tanlanmadan olingan har bir nuqta(obyekt) uchun quyidagilar bajariladi:
3.1. Sinov tanlanmadan olingan har bir nuqta(obyekt) bilan o’quv tanlanmadagi barcha nuqtalar orasidagi masofalarni Evklid, Manxetten yoki Hemming masofasidan foydalangan holda hisoblang. Masofani hisoblashning eng ko'p ishlatiladigan usuli Evklid masofasi hisoblanadi.
3.2. Hisoblangan masofa qiymatlari o’sish tartibida joylashtiriladi.
3.3. O’sish tartibida joylashtirilgan qiymatlarni yuqori qismidan K ta masofa qiymatlari tanlanadi.
3.4. Sinov tanlanmadagi nuqta o’quv tanlanmaning qaysi sinfdagi nuqtalarga masofa ko’rsatkichlari yig’indisi bo’yicha katta qiymatga ega bo’lsa, ushbu sinfga tegishli deb topiladi.
4-qadam. Tugatish.
Misol. 3 ta sinfdan (1-sinf obyektlari to’q ko’k rangda, 2-sinf obyektlari och ko’k rangda va 3-sinf obyektlari sariq rangda) iborat o’quv tanlanmaning berilishi 11.16 - rasmda keltirilgan.
11.16-rasm.
11.16-rasmda berilgan o’quv tanlanmada 2-sinfdan bitta (qizil rangli to’rtburchak shaklida tasvirlangan) obyekt tanlandi. K=5 bo’lganda, ushbu obyektga yaqin qo’shni bo’lgan 5 ta obyekt, ya’ni 2 - sinfdan 3ta (1, 2 va 4 –obyektlar) va 3 - sinfdan 2ta (3 va 5 – obyektlar) aniqlandi (11.17-rasm).Ta’kidlaymizki, tanlangan qizil rangli to’rtburchak shaklida tasvirlangan obyektga 1-sinfdan birorta obyekt ham yaqin qo’shni bo’lib chiqmadi. Tanlangan obyektni bilan 5 ta yaqin qo’shni obyektlar orasidagi masofalar qiymatlarini hisoblash va ushbu qiymatlarni 2 va 3 - sinflardagi yig’indisini taqqoslah natijasida tanlangan obyektning 2-singa tegishli ekanligining holati 11.17-rasmda keltirilgan
11.17-rasm. Obyektning 2-singfa tegishliligining holati.
Misol. Quyida K tushunchasini va KEYQ algoritmining ishlashini tushunish uchun misol keltirilgan.
Bizda quyidagi tuzilishga ega bo’lgan ma'lumotlar to'plami berilgan bo’lsin (11.18-rasm).
11.18-rasm.
Endi biz yangi qora nuqta ma'lumotlarini (60, 60 o’lchamlarda) ko'k yoki qizil sinfga tegishli ekanligini tajratishimiz kerak. Aytaylik, qora nuqta uchun K = 3 ta qo’shni nuqtalar tanlangan bo’lsin, ya'ni yangi qora nuqtaga yaqin bo’lgan uchta nuqtalar masofalarni hisoblash asosida belgilanadi (11.19-rasm).
11.19-rasmdan ko’rinadiki, yangi qora nuqta o’quv tanlanmaning uchta nuqtasi bilan eng yaqin qo’shni hisoblanadi. Ushbu uchta nuqtadan ikkitasi qizil sinfga tegishli bittasi ko’k sinfga tegishli, shuning uchun qora nuqta ham qizil sinfga tegishli deb belgilanadi.
11.19-rasm.