Maruza. Klasterlash algoritmlari

K eng yaqin qo’shnilar usuli (k nearest neibour, kNN). Shovqin ob’ektlar tasirini yumshatish uchun ob’ektini shunday sinfga tegishli deb qaror qilamizki, elementlari eng yaqin qo’shnilar orasida uchrab qo’lsa:

da bu algoritm oldingi algoritm bilan mos tushadi, natijada, shovqinga turg’unsiz bo’ladi. da, aksincha, u haddan tashqari turg’un va kontantani paydo etadi.
Shunday qilib, qiymatini juda katta tanlash yaxshi emas. Amaliyotda paramerining optimal qiymatini sirpanuvchi nazorat bilan ob’ektlarni bittadan olib tashlash (leave-one-out, LOO) mezoni bilan aniqlanadi. Har bir ob’ekti uchun tekshiriladi, yan’iy u o’zining ta yaqin qo’shnisi bo’yicha to’g’ri klassifikatsiya qilinadimi.

Takidlash joizki, agar klassifikatsiyalanuvchi ob’ektini o’rgatuvchi tanlamadan olib tashlanmasa, u holda ning eng yaqin qo’shnisi ning o’zi bo’ladi va funksionalining minimal (nol) qiymati da erishadi.
kNN usulining alternativ varianti ham mavjud: ob’ektiga har bir sinfdan ta eng yaqin qo’shni tanlab olinadi, va ob’ekti ta eng yaqin qo’shnigacha o’rtacha masofasi minimal bo’lgan sinfga tegishli deb qaror qilinadi.
K vaznli eng yaqin qo’shnilar usuli. kNN usulining kamchiliigi shundaki, maksimal qiymat birdaniga bir nechta sinflarda erishishi mumkun. Ikkita sinfli masalalarda bunday vaziyatdan chiqish mumkun, agar qiymatini toq son sifatida tanlab olinsa. Yanayam umumiyroq yondashuv, yan’iy ko’p sinfli holatlarga ham to’g’ri keluvchi – klassifikatsiyaga chi hissasini beruvchi qat’iy kamayuvchi haqiqiy ( ) vaznlarni kiritishdir:

ketma-ketligini tanlash evristika hisoblanadi. Agar, chiziqli kamayuvchi vaznlarini tanlab olsak, u holda bunday holatlarda ham bir natijali vaziyatlar vujudga kelishi mumkun. Misol, ikkita sinf; birinchi va to’rtinchi qo’shni 1 sinfga ovoz beradi, ikkinchi va uchunchi qo’shni – 2 sinfga; ovozlar yig’indisi mos keladi. Agar nochiziqli kamayuvchi ketma-ketlik tanlab olinsa, masalan, geometric progressiyasi, bunday holatdan chiqib ketish mumkun. Uni ta qo’shnilar miqdoriga qarab, mezoni bo’yicha tanlab olish mumkun.