K-nejbližší sousedé

Algoritmus k-nejbližších sousedů (KNN) je neparametrický, řízený algoritmus strojového učení používaný pro klasifikaci a regresi. Je založen na konceptu blízkosti, předpokládá, že podobné datové body se nacházejí blízko sebe. KNN je “líný” algoritmus, což znamená, že nevyžaduje trénovací fázi a provádí předpovědi uložením celé trénovací sady a jejím využitím k určení třídy nebo hodnoty nových datových bodů. Algoritmus předpovídá výsledek pro testovací bod tak, že identifikuje ‘k’ trénovacích bodů nejbližších k testovacímu bodu a odvozuje výstup na základě těchto sousedů. Tato metoda je velmi intuitivní a napodobuje lidské strategie, které spoléhají na porovnávání nových dat se známými příklady.

Jak KNN funguje

KNN pracuje tak, že identifikuje ‘k’ nejbližších datových bodů k danému dotazovanému bodu a na základě těchto sousedů učiní předpověď.

• U klasifikace algoritmus přiřadí dotazovaný bod do třídy, která je mezi jeho ‘k’ nejbližšími sousedy nejčastější, což je známé jako většinové hlasování. Většinové hlasování v KNN může být v případě více tříd chápáno jako „pluralitní hlasování“, kde dotazovaný bod získá třídu s nejvyšším počtem výskytů mezi sousedy, i když nejde o absolutní většinu.
• U regrese předpovídá hodnotu průměrováním hodnot ‘k’ nejbližších sousedů.

Principy blízkosti a podobnosti, které jsou klíčové pro lidské vnímání, jsou také jádrem fungování KNN, neboť datové body, které jsou si ve vlastnostech blízko, jsou považovány za podobné a pravděpodobně mají i podobné výsledky.

Metriky vzdálenosti

Pro určení nejbližších sousedů využívá KNN různé metriky vzdálenosti, které jsou klíčové pro jeho výkon:

• Eukleidovská vzdálenost: Přímá vzdálenost mezi dvěma body v vícerozměrném prostoru, běžně používaná pro spojitá data. Jde o nejčastější metriku v KNN, zvláště užitečnou u hustých a spojitých dat.
• Manhattanská vzdálenost: Také známá jako taxi vzdálenost, počítá vzdálenost sčítáním absolutních rozdílů souřadnic dvou bodů. Je vhodná v případech, kdy je pohyb omezen na ortogonální směry (například na mřížce).
• Minkowského vzdálenost: Zobecnění eukleidovské a manhattanské vzdálenosti s parametrem ‘p’. Pro p=1 jde o manhattanskou vzdálenost, pro p=2 o eukleidovskou. Tato metrika nabízí flexibilitu v závislosti na zvolené hodnotě ‘p’.
• Hammingova vzdálenost: Používá se u kategoriálních dat, počítá počet rozdílných bitů mezi dvěma binárními vektory. Je užitečná zejména v binárních klasifikačních úlohách.

Volba správné hodnoty ‘k’

Parametr ‘k’ v KNN určuje, kolik sousedů se bere v úvahu. Jeho volba je zásadní:

• Malé ‘k’ může vést k přeučení, kdy model příliš reaguje na šum v trénovacích datech a zachytává vzory, které se obecně neopakují.
• Velké ‘k’ může vést k podučení, kdy je model příliš zobecněný a přehlíží důležité vzory, což se projeví nižší přesností.
• ‘k’ se obvykle vybírá pomocí křížové validace a mělo by být liché, aby se v klasifikaci předešlo remízám. Výběr ‘k’ významně ovlivňuje přesnost modelu a často je stanoven empiricky.

Výhody a nevýhody

Výhody

• Jednoduchý a intuitivní: Snadno pochopitelný a implementovatelný, vhodný pro začátečníky. Jednoduchost KNN tkví v přímém srovnávání testovacích vzorků s uloženými příklady.
• Bez trénovací fáze: KNN nepotřebuje explicitní trénink, předpovídá na základě uložené trénovací sady. Model lze tedy aktualizovat jednoduše přidáním nových datových bodů.
• Univerzální: Lze jej použít jak pro klasifikaci, tak regresi, a má široké uplatnění v různých oborech. Je vhodný i pro úlohy s více štítky.

Nevýhody

• Výpočetně náročný: Vyžaduje ukládání a porovnávání každého nového bodu s celou trénovací sadou, což může být pomalé a náročné na zdroje, zejména u velkých dat. Časová složitost je O(n), kde n je počet trénovacích vzorků.
• Citlivost na odlehlé hodnoty: Přítomnost odlehlých bodů může významně ovlivnit výsledky, protože tyto anomálie mohou zkreslit výstupy, zvlášť při malém ‘k’.
• Prokletí dimenzionality: Ve vysoce dimenzionálních prostorech může výkon algoritmu klesat, protože vzdálenosti mezi body ztrácejí smysl. S rostoucí dimenzionalitou roste objem prostoru a data se stávají řídká, což ztěžuje hledání nejbližších sousedů.

Příklady použití

KNN je díky své jednoduchosti a účinnosti používán v různých oblastech:

• Doporučovací systémy: Doporučování produktů či obsahu na základě preferencí podobných uživatelů. KNN pomáhá identifikovat podobné uživatele nebo položky na základě podobnosti vlastností.
• Rozpoznávání vzorů: Využíván například pro rozpoznávání rukopisu a další úlohy, kde klasifikuje obrázky podle podobnosti hodnot pixelů.
• Doplnění chybějících dat: Užitečný při doplňování chybějících hodnot v datech na základě podobných bodů, čímž se zachovává integrita datové sady.
• Finance a zdravotnictví: Používán při predikci akciových trhů, hodnocení rizik a lékařské diagnostice na základě analýzy podobností v historických datech. Ve zdravotnictví může předpovídat diagnózy srovnáváním příznaků s již známými případy.

Implementace v Pythonu

KNN lze implementovat pomocí knihoven jako scikit-learn v Pythonu. Zde je základní příklad použití KNN pro klasifikaci:

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čtení datové sady
iris = load_iris()
X, y = iris.data, iris.target

# Rozdělení na trénovací a testovací data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Inicializace KNN klasifikátoru s k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Natrénování modelu
knn.fit(X_train, y_train)

# Předpovědi
y_pred = knn.predict(X_test)

# Vyhodnocení přesnosti
accuracy = accuracy_score(y_test, y_pred)
print(f"Přesnost: {accuracy:.2f}")

K-nejbližší sousedé (KNN) ve vědeckém výzkumu

K-nejbližší sousedé (KNN) je základní algoritmus využívaný v různých oblastech, jako je vyhledávání v multimediálních datech, data mining a strojové učení, zejména v kontextu velkých datových souborů.

Významné vědecké publikace:

• „Approximate k-NN Graph Construction: a Generic Online Approach“ od Wan-Lei Zhao a kol.:
  Představuje efektivní metodu pro přibližné hledání k-nejbližších sousedů a konstrukci grafu. Článek ukazuje dynamické a použitelné řešení pro různé velikosti a dimenze dat s podporou online aktualizací, což u mnoha existujících metod není možné. Více zde.

• „Parallel Nearest Neighbors in Low Dimensions with Batch Updates“ od Magdalen Dobson a Guy Blelloch:
  Představuje paralelní algoritmy kombinující kd-strom a Mortonovo řazení do zd-stromové struktury, optimalizované pro data s nízkou dimenzionalitou. Autoři ukazují, že jejich přístup je rychlejší než stávající algoritmy a dosahuje významného zrychlení díky paralelnímu zpracování. Zd-strom jako první podporuje paralelní dávkové-dynamické aktualizace u struktur pro hledání k-nejbližších sousedů. Více zde.

• „Twin Neural Network Improved k-Nearest Neighbor Regression“ od Sebastian J. Wetzel:
  Zkoumá nový přístup k regresi k-nejbližších sousedů pomocí twin neural networks. Tato metoda se zaměřuje na predikci rozdílů mezi cílovými hodnotami regrese, což vede k lepším výsledkům ve srovnání s tradičními neuronovými sítěmi a standardní KNN regresí u malých a středně velkých datových sad. Více zde.