K-najbližší susedia

Algoritmus k-najbližších susedov (KNN) je neparametrický, supervidovaný algoritmus učenia používaný na klasifikáciu a regresiu v strojovom učení. Je založený na koncepte blízkosti a predpokladá, že podobné dátové body sa nachádzajú blízko seba. KNN je tzv. “lenivý” algoritmus učenia, čo znamená, že nevyžaduje fázu trénovania a predpovede vytvára uložením celého trénovacieho datasetu, ktorý slúži na určenie triedy alebo hodnoty nových dátových bodov. Algoritmus predikuje výsledok pre testovací dátový bod identifikovaním ‘k’ trénovacích bodov, ktoré sú k nemu najbližšie, a odvodením výstupu na základe týchto susedov. Táto metóda je veľmi intuitívna a napodobňuje ľudské stratégie vnímania, ktoré sa zakladajú na porovnávaní nových údajov s už známymi príkladmi.

Ako KNN funguje

KNN pracuje na princípe identifikácie ‘k’ najbližších dátových bodov k zadanému dopytovanému bodu a tieto susedia slúžia na vytvorenie predikcie.

• Pri klasifikačných úlohách algoritmus priraďuje dopytovaný bod k triede, ktorá je najčastejšia medzi jeho ‘k’ najbližšími susedmi, čo sa nazýva väčšinové hlasovanie. Väčšinové hlasovanie v KNN možno chápať ako “pluralitné hlasovanie” v prípade viacerých tried, kde sa dopytovaný bod priradí k triede s najväčším počtom výskytov medzi najbližšími susedmi, aj keď to nepredstavuje absolútnu väčšinu.
• Pri regresii predpovedá hodnotu spriemerovaním hodnôt ‘k’ najbližších susedov.

Princípy blízkosti a podobnosti, ktoré sú jadrom ľudského vnímania, sú tiež základom fungovania KNN, pretože sa predpokladá, že dátové body, ktoré sú blízko v priestore príznakov, sú si podobné a majú podobné výsledky.

Metriky vzdialenosti

Na určenie najbližších susedov využíva KNN rôzne metriky vzdialenosti, ktoré sú kľúčové pre jeho výkon:

• Euklidovská vzdialenosť: Priama vzdialenosť medzi dvoma bodmi v multidimenzionálnom priestore, často používaná pre spojité premenné. Je to najbežnejšia metrika vzdialenosti pre KNN a je obzvlášť užitočná pri hustých a spojitých dátach.
• Manhattanská vzdialenosť: Nazývaná aj taxikárska vzdialenosť, vypočítava sa súčtom absolútnych rozdielov medzi súradnicami dvoch bodov. Je vhodná v scenároch s pohybom po mriežke, kde je pohyb obmedzený na ortogonálne smery.
• Minkowskiho vzdialenosť: Všeobecná forma euklidovskej a manhattanskej vzdialenosti, parametrizovaná ‘p’. Ak p=1, ide o manhattanskú vzdialenosť, ak p=2, ide o euklidovskú vzdialenosť. Táto metrika poskytuje flexibilitu v závislosti od zvolenej hodnoty ‘p’.
• Hammingova vzdialenosť: Používaná pre kategorizované údaje, počíta počet rozdielnych bitov medzi dvoma binárnymi vektormi. Je výhodná najmä pri binárnych klasifikačných úlohách, kde atribúty nadobúdajú binárne hodnoty.

Voľba správnej hodnoty ‘k’

Parameter ‘k’ v KNN predstavuje počet susedov, ktorých treba brať do úvahy. Výber správnej hodnoty ‘k’ je zásadný:

• Malé ‘k’ môže viesť k preučeniu, kedy je model príliš citlivý na šum v trénovacích dátach a zachytáva náhodné vzory, ktoré sa nedajú zovšeobecniť.
• Veľké ‘k’ môže viesť k podučeniu, kedy je model príliš všeobecný a prehliada dôležité vzory, čo vedie k slabej predikčnej presnosti.
• ‘k’ sa zvyčajne volí pomocou krížovej validácie a malo by byť nepárne, aby sa pri rozhodovaní v klasifikácii predišlo remíze. Voľba ‘k’ môže výrazne ovplyvniť presnosť modelu a často sa určuje empiricky.

Výhody a nevýhody

Výhody

• Jednoduchosť a intuitívnosť: Ľahké na pochopenie a implementáciu, čo z KNN robí vhodnú voľbu pre začiatočníkov. Jednoduchosť KNN spočíva v priamočiarom porovnávaní testovacích prípadov s uloženými príkladmi.
• Bez tréningovej fázy: KNN nevyžaduje explicitnú tréningovú fázu, pretože predpovede realizuje priamo na základe uloženého datasetu. Model sa dá aktualizovať jednoducho pridaním nových dátových bodov do datasetu.
• Univerzálnosť: Možno ho použiť na klasifikáciu aj regresiu, pričom jeho využitie je široké naprieč rôznymi doménami. Je vhodný aj pre úlohy s viacnásobnou klasifikáciou (multi-label).

Nevýhody

• Výpočtová náročnosť: Keďže je potrebné ukladať a porovnávať každý nový dátový bod s celým datasetom, môže byť pomalý a náročný na zdroje, najmä pri veľkých datasetoch. Časová zložitosť KNN je O(n), kde n je počet trénovacích vzoriek.
• Citlivosť na odľahlé hodnoty: Prítomnosť odľahlých hodnôt môže výrazne ovplyvniť predikcie, pretože takéto anomálne body môžu skresliť výsledky, najmä keď je ‘k’ malé.
• Prekliatie dimenzionality: Vo vysokorozmerných priestoroch môže výkon algoritmu klesať, pretože vzdialenosti medzi bodmi strácajú význam. S rastúcou dimenzionalitou narastá aj objem priestoru, čo spôsobuje, že dáta sú riedke. Táto riedkosť sťažuje KNN efektívne vyhľadávanie najbližších susedov.

Príklady použitia

KNN sa využíva v rôznych oblastiach vďaka svojej jednoduchosti a efektívnosti:

• Odporúčacie systémy: Používa sa na odporúčanie produktov alebo obsahu používateľom na základe preferencií podobných používateľov. KNN vie identifikovať podobných používateľov alebo položky porovnávaním príznakov.
• Rozpoznávanie vzorov: Uplatňuje sa pri rozpoznávaní rukopisu a iných úlohách rozpoznávania vzorov, kde dokáže klasifikovať obrázky na základe podobnosti hodnôt pixelov.
• Imputácia dát: Užitočný pri dopĺňaní chýbajúcich hodnôt v datasetoch ich odhadom na základe podobných dátových bodov, čím sa zachováva integrita datasetu.
• Financie a zdravotníctvo: Uplatňuje sa pri predikciách na burze, hodnotení rizika a lekárskej diagnostike analýzou podobností v historických dátach. V zdravotníctve vie predpovedať diagnózy pacientov porovnávaním symptómov s už známymi prípadmi.

Implementácia v Pythone

KNN možno implementovať pomocou knižníc ako scikit-learn v Pythone. Tu je základný príklad použitia KNN na klasifikáciu:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Načítanie datasetu
iris = load_iris()
X, y = iris.data, iris.target

# Rozdelenie dát na trénovaciu a testovaciu množinu
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inicializácia KNN klasifikátora s k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Natrénovanie modelu
knn.fit(X_train, y_train)

# Vytvorenie predikcií
y_pred = knn.predict(X_test)

# Vyhodnotenie presnosti
accuracy = accuracy_score(y_test, y_pred)
print(f"Presnosť: {accuracy:.2f}")

K-najbližší susedia (KNN) vo vedeckom výskume

K-najbližší susedia (KNN) je základný algoritmus používaný v rôznych oblastiach, ako je vyhľadávanie multimediálnych informácií, data mining a strojové učenie, najmä v kontexte veľkých datasetov.

Významné vedecké práce:

• „Approximate k-NN Graph Construction: a Generic Online Approach“ — Wan-Lei Zhao a kol.:
  Predstavuje efektívnu metódu pre aproximatívne vyhľadávanie k-najbližších susedov a konštrukciu grafov. Práca ukazuje dynamické a uskutočniteľné riešenie pre spracovanie rôznych mierok a dimenzií dát s podporou online aktualizácií, čo nie je možné u mnohých existujúcich metód. Čítajte viac.

• „Parallel Nearest Neighbors in Low Dimensions with Batch Updates“ — Magdalen Dobson a Guy Blelloch:
  Predstavuje paralelné algoritmy kombinujúce kd-strom a Mortonovo radenie do štruktúry zd-stromu, optimalizované pre nízkorozmerné dáta. Autori ukazujú, že ich prístup je rýchlejší ako existujúce algoritmy a dosahuje výrazné zrýchlenie vďaka paralelnému spracovaniu. Zd-strom ako prvý umožňuje paralelné dynamické aktualizácie v štruktúrach k-najbližších susedov. Čítajte viac.

• „Twin Neural Network Improved k-Nearest Neighbor Regression“ — Sebastian J. Wetzel:
  Skúma nový prístup k regresii k-najbližších susedov s využitím párových neurónových sietí. Táto metóda sa zameriava na predikciu rozdielov medzi regresnými cieľmi, čo vedie k lepšiemu výkonu oproti tradičným neurónovým sieťam a regresii k-najbližších susedov pri malých a stredne veľkých datasetoch. Čítajte viac.