Streszczenie AI
Klasyfikacja w uczeniu maszynowym polega na analizie przestrzennego rozmieszczenia punktów w wielowymiarowej przestrzeni cech.
K‑Nearest Neighbors (KNN) to nieparametryczny, leniwy algorytm oparty na metryce odległości, którego granica decyzyjna zależy od liczby sąsiadów k i wybranej metryki (Manhattan czy euklidesowa), natomiast Support Vector Machines (SVM) są parametrycznym modelem, który znajduje hiperpłaszczyznę maksymalizującą margines; dzięki kernel‑trickowi potrafi obsługiwać nieliniowe granice, a regulowany przez C wybór winien balansować między over‑ a under‑fittingiem.
KNN sprawdza się w rekomendacjach i detekcji anomalii, podczas gdy SVM dominuję w klasyfikacji tekstu, bioinformatyce i innych zadaniach wymagających wyraźnych, globalnych granic decyzyjnych.
Klasyfikacja w uczeniu maszynowym często opiera się na analizie przestrzennego rozmieszczenia punktów danych w wielowymiarowej przestrzeni cech. Zrozumienie geometrycznej intuicji stojącej za algorytmami takimi jak K-Nearest Neighbors (KNN) oraz Support Vector Machines (SVM) pozwala na świadomy dobór metod do charakterystyki rozwiązywanego problemu. Oba te podejścia, choć diametralnie różne w swoich matematycznych założeniach, oferują potężne mechanizmy do wyznaczania zarówno liniowych, jak i wysoce nieliniowych granic decyzyjnych w danych.
K-Nearest Neighbors: Nieparametryczny klasyfikator oparty na odległości
Algorytm K-Nearest Neighbors (KNN) jest jednym z najbardziej intuicyjnych klasyfikatorów w uczeniu maszynowym. Należy do grupy algorytmów nieparametrycznych, co oznacza, że nie zakłada z góry żadnego konkretnego rozkładu statystycznego danych. Jest to również tzw. algorytm leniwy (lazy learner) – proces budowania modelu jest tu właściwie pomijany, a cała złożoność obliczeniowa przenoszona jest na fazę wnioskowania (predykcji). Decyzja o przypisaniu nowej próbki do konkretnej klasy opiera się bezpośrednio na większościowym głosowaniu jej najbliższych sąsiadów.
Kluczowym elementem determinującym kształt przestrzeni decyzyjnej jest wybór metryki odległości. Najbardziej uniwersalną miarą jest odległość Minkowskiego, wyrażona wzorem:
Poprzez manipulację parametrem 
, możemy uzyskać dwie najczęściej stosowane w praktyce metryki:
- Odległość Manhattan (
): Oblicza sumę wartości bezwzględnych różnic wzdłuż poszczególnych osi. Sprawdza się szczególnie dobrze w przestrzeniach o bardzo dużej liczbie wymiarów, gdzie tradycyjne miary tracą na użyteczności. - Odległość Euklidesowa (
): Standardowa miara odległości w linii prostej w przestrzeni 
. Jest to najczęstszy wybór dla danych ciągłych o znormalizowanych skalach.
Wybór hiperparametru 
(np. 
) prowadzą do powstawania bardzo skomplikowanych i ostrych granic decyzyjnych, które idealnie dopasowują się do szumu w danych treningowych (overfitting). Z kolei zbyt duże wartości uśredniają przestrzeń, wygładzając granice do tego stopnia, że algorytm może ignorować ważne, lokalne struktury wieloklasowe (underfitting).
Złożoność obliczeniowa klasycznego wyszukiwania najbliższych sąsiadów metodą siłową (brute-force) wynosi 
, gdzie 
to liczba próbek, a 
to liczba wymiarów. W celu optymalizacji wnioskowania stosuje się struktury przyspieszające:
- KD-tree (K-Dimensional Tree): Drzewo binarne, które rekurencyjnie dzieli przestrzeń za pomocą płaszczyzn prostopadłych do osi układu współrzędnych. Redukuje czas wyszukiwania do
, jednak jego skuteczność gwałtownie spada w przestrzeniach wysokowymiarowych (zjawisko tzw. klątwy wymiarowości). - Ball tree: Zamiast dzielić przestrzeń ortogonalnie, ta struktura hierarchicznie grupuje punkty w zagnieżdżone hiperkule. Rozwiązuje to problem podziałów na brzegach osi i czyni Ball tree znacznie wydajniejszą strukturą dla danych o dużej liczbie wymiarów (zazwyczaj powyżej 20).
Support Vector Machines: Hiperplany i maksymalizacja marginesu
W przeciwieństwie do KNN, algorytm Support Vector Machines (SVM) jest modelem parametrycznym, który podczas fazy treningu stara się znaleźć optymalną hiperpłaszczyznę separującą klasy. W wielowymiarowej przestrzeni o wymiarze , hiperpłaszczyzna jest obiektem płaskim o wymiarze 
. SVM opiera się na twardym założeniu geometrycznym: najlepsza granica decyzyjna to taka, która znajduje się maksymalnie daleko od najbliższych punktów treningowych każdej z klas. Te graniczne próbki, decydujące o ostatecznym ułożeniu płaszczyzny, nazywamy wektorami nośnymi (support vectors).
Główną filozofią SVM nie jest samo oddzielenie klas od siebie, ale uczynienie tego z możliwie największym „marginesem bezpieczeństwa”, co statystycznie gwarantuje najlepszą zdolność modelu do generalizacji na nowych, niewidzianych wcześniej danych.
W rzeczywistych zbiorach danych idealna separacja liniowa rzadko jest możliwa ze względu na szum i nakładające się na siebie próbki. Dlatego wprowadzono koncepcję „miękkiego marginesu” kontrolowanego przez hiperparametr 
. Tolerancja na błędy jest optymalizowana przy użyciu funkcji straty typu hinge loss, zdefiniowanej dla próbki 
i prawdziwej etykiety 
jako:
Parametr regularyzacji bezpośrednio wpływa na geometrię rozwiązania:
- Wysoka wartość
: Model rygorystycznie karze za błędy klasyfikacji. Margines staje się wąski, a granica decyzyjna zawiła, próbując poprawnie sklasyfikować każdą próbkę (ryzyko overfittingu). - Niska wartość : Model pozwala na naruszenia marginesu, co skutkuje szerszym korytarzem decyzyjnym i gładszą granicą, poprawiając generalizację, ale ryzykując underfitting.
Prawdziwa moc SVM ujawnia się dzięki zastosowaniu tzw. tricku jądrowego (kernel trick). Algorytm operuje wyłącznie na iloczynach skalarnych wektorów cech. Zamiast fizycznie transformować dane do wyżej wymiarowej przestrzeni w celu znalezienia liniowej separacji dla danych nieliniowych, SVM używa funkcji jądra (np. RBF – Radial Basis Function, czy jądro wielomianowe). Pozwala to na obliczenie relacji między wektorami w przestrzeni wielowymiarowej bez konieczności jawnego wykonywania niezwykle kosztownych obliczeniowo transformacji na samych wektorach.
Przykłady geometryczne: Granice w przestrzeni 2D
Aby w pełni zrozumieć różnicę między tymi klasyfikatorami, najlepiej wyobrazić sobie ich działanie na płaszczyźnie 2D.
Dla algorytmu KNN przy , przestrzeń decyzyjna przyjmuje formę przypominającą diagram Woronoja (Voronoi tessellation). Każdy pojedynczy punkt treningowy generuje wokół siebie ostrokątną komórkę. Jeśli w terytorium przypisanym do klasy A znajdzie się pojedynczy, błędny punkt (szum) klasy B, algorytm stworzy wokół niego drobną, odizolowaną „wyspę” decyzyjną. Zwiększenie wartości uśrednia głosowanie lokalne, co geometrycznie przekłada się na wygładzenie poszarpanych brzegów i zanikanie takich wysp, prowadząc do tworzenia jednolitych stref.
SVM podchodzi do podziału przestrzeni zupełnie inaczej. Klasyczny SVM (jądro liniowe) przecina przestrzeń 2D jedną, idealnie prostą linią, otoczoną z obu stron strefą buforową (marginesem). Wektory nośne leżą dokładnie na krawędziach tego bufora. Gdy włączymy trick jądrowy (np. jądro RBF z parametrem 
), granica zyskuje elastyczność. Małe wartości tworzą płynne, owalne granice obejmujące całe zgrupowania punktów. Z kolei ogromne wartości sprawiają, że granica „owija się” bardzo ciasno i nieliniowo wokół pojedynczych wektorów nośnych w przestrzeni, co jest podręcznikowym przykładem geometrycznego przeuczenia.
Porównanie właściwości algorytmów
| Cecha | K-Nearest Neighbors (KNN) | Support Vector Machines (SVM) |
|---|---|---|
| Typ algorytmu | Nieparametryczny (Instance-based) | Parametryczny (po wyuczeniu wag) |
| Złożoność treningu |  (brak klasycznego treningu, tylko zapis) | Od  do  w zależności od optymalizatora |
| Złożoność wnioskowania | Bardzo wysoka w przestrzeniach o dużej liczbie wymiarów | Wysoko zoptymalizowana, zależy wyłącznie od wektorów nośnych |
| Wrażliwość na skalowanie | Ekstremalnie wysoka (wymaga standaryzacji cech) | Wysoka (wymaga ujednolicenia rzędu wielkości) |
Praktyczne zastosowania w analizie danych
Mimo teoretycznych i konstrukcyjnych różnic, oba klasyfikatory odgrywają ogromną rolę w systemach analitycznych.
Zastosowania KNN obejmują:
- Systemy rekomendacyjne: Używane do filtrowania kolaboratywnego, gdzie algorytm odnajduje użytkowników o najmniejszej odległości w przestrzeni zakupów (najbardziej zbliżonym guście), aby proponować nowe produkty.
- Detekcja anomalii: Próbki testowe, których średnia odległość do najbliższych sąsiadów drastycznie przekracza normę rynkową lub systemową, są oznaczane jako odchylenia (np. w logach serwerowych).
Zastosowania SVM obejmują:
- Kategoryzacja tekstu: Przy wykorzystaniu metody TF-IDF przestrzenie cech stają się rzadkie i potężnie wielowymiarowe. Liniowy SVM jest jednym z najskuteczniejszych algorytmów do klasyfikacji spamu, analizy sentymentu i tagowania dokumentów w takich warunkach.
- Zastosowania bioinformatyczne: SVM z wyspecjalizowanymi jądrami jest używany do rozpoznawania i klasyfikacji wzorców w sekwencjach DNA oraz identyfikacji markerów chorobowych.
Źródła
- Dokumentacja scikit-learn: Nearest Neighbors i struktury przestrzenne
- Dokumentacja scikit-learn: Support Vector Machines i funkcje jądra
- Trevor Hastie, Robert Tibshirani, Jerome Friedman – The Elements of Statistical Learning
