K-nearest neighbors

Algoritmus k-nearest neighbors je z hľadiska princípu jeden z najjednoduchších algoritmov strojového učenia. Tento algoritmus sa využíva na klasifikáciu.

Fungovanie

Algoritmus v tréningovej fáze najprv umiestni prvky tréningovej množiny do priestoru tak, aby prvky z rovnakých tried vytvárali zhluky. Nasleduje fáza klasifikácie, kde je prvok, ktorý je potrebné klasifikovať umiestnený do priestoru podľa jeho vlastností. Potom sa v priestore nájde k najbližších prvkov okolo klasifikovaného prvku. Následne je prvok klasifikovaný do triedy, do ktorej patrí väčšina k najbližších prvkov (obr. 1).

Podmienky

Číslo $k$ musí byť prirodzené číslo. Pri klasifikačnom probléme s dvomi triedami musí byť $k$ nepárne číslo, pretože by mohlo dôjsť pri klasifikácii k tomu, že by sa počet prvkov oboch tried vo vyhradenom priestore rovnal, a potom by algoritmus nedokázal určiť, ku ktorej triede klasifikovaný prvok pravdepodobnejšie bude patriť. Pre tento istý dôvod $k$ nesmie byť ani násobok počtu tried.