Maszyna, która się uczy — klasyfikacja k-NN

🎯 Po co Ci to?

Wszystkie algorytmy tej książki łączyło jedno: Ty podawałeś regułę, komputer ją wykonywał. Sprawdź parzystość — reguła jasna. Posortuj — reguła jasna. Ale spróbuj podać regułę na „rozpoznaj, czy na zdjęciu jest kot" albo „oceń, czy ta wiadomość to spam"… Nie ma takiej reguły do wypisania. Jest za to góra przykładów — i pomysł, żeby komputer wywnioskował odpowiedź z nich. To jest uczenie maszynowe: trzecia wielka zmiana perspektywy w tej książce (po „stanach zamiast obiektów" z 8.4). Poznasz jego najprostszy, najuczciwszy algorytm — tak prosty, że policzysz go na kartce, i naprawdę używany do dziś.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wyjaśnić, czym klasyfikacja z przykładów różni się od wykonywania podanej reguły;
  • wykonać klasyfikację k najbliższych sąsiadów (k-NN) ręcznie i w kodzie;
  • wskazać założenia i pułapki: dobór $k$, skala cech, jakość przykładów.

🔁 Przypomnij sobie

Z 1.6: heurystyka — dobra odpowiedź bez gwarancji; z 8.3: „zapamiętaj i korzystaj" — notes jako supermoc; z 6.8: głosowanie większością.

📘 Wyjaśnienie

Scena. Szkolny sklepik chce automatycznie oceniać, czy nowy napój przypadnie uczniom do gustu. Ma dane historyczne: dla każdego napoju słodkość (0–10) i cena (zł) oraz werdykt uczniów: hit albo kit. Nowy napój: słodkość 6, cena 4 zł. Hit czy kit?

Pomysł k-NN (k najbliższych sąsiadów, ang. k nearest neighbours) jest tak ludzki, że aż wstyd nazywać go „sztuczną inteligencją": spójrz, jak skończyły najbardziej podobne przypadki. Narysuj wszystkie znane napoje jako punkty (słodkość, cena) na płaszczyźnie, znajdź $k$ punktów najbliższych nowemu i przeprowadź wśród nich głosowanie: większość wygrywa.

słodkośćcena?hitkitotoczka = trzej najbliżsi sąsiedzi; głosy 2 : 1 — werdykt: HIT
Klasyfikacja k-NN: znane przypadki jako punkty dwóch klas na płaszczyźnie cech, nowy punkt ze znakiem zapytania, zaznaczone trzy najbliższe sąsiedztwa — dwa głosy na klasę pomarańczową, jeden na indygo, werdykt: pomarańczowa. · rys. własny

Odległość liczy się jak w geometrii (Pitagoras!): dla punktów $(s_1, c_1)$ i $(s_2, c_2)$ — $\sqrt{(s_1-s_2)^2 + (c_1-c_2)^2}$. Cały „trening" polega na… zapamiętaniu przykładów (notes z 8.3 w roli głównej!), a cała klasyfikacja to:

def knn(przyklady, nowy, k=3):
    # przyklady: lista (cechy, etykieta); nowy: cechy
    odleglosci = []
    for cechy, etykieta in przyklady:
        d = sum((a - b) ** 2 for a, b in zip(cechy, nowy)) ** 0.5
        odleglosci.append((d, etykieta))
    odleglosci.sort()                          # sortowanie! (dział 6 w pracy)
    najblizsi = odleglosci[:k]                 # k pierwszych po odległości
    za = sum(1 for d, e in najblizsi if e == "hit")
    return "hit" if za > k / 2 else "kit"      # głosowanie większością (6.8!)

Popatrz, ile znajomych twarzy: odległość z twierdzenia Pitagorasa, sortowanie z działu 6, głosowanie większością jak u lidera (6.8), zapamiętane przykłady jak notes (8.3). Uczenie maszynowe w wersji podstawowej to kompozycja klocków, które już masz.

Trzy decyzje, które są całą sztuką:

  • Dobór $k$. $k = 1$: werdykt od jednego sąsiada — czuły na pojedyncze błędne przykłady (jeden dziwny wpis „kit" psuje okolicę). $k$ ogromne: głosuje cała populacja — nowy punkt dostaje po prostu najczęstszą etykietę, ślepą na jego położenie. Praktyka: małe nieparzyste $k$ (3, 5 — nieparzyste, żeby nie było remisów) i sprawdzenie na odłożonych przykładach, które $k$ myli się najrzadziej.
  • Skala cech. Cena 2–8 zł, słodkość 0–10 — porównywalne. Ale dodaj cechę „liczba mililitrów" (250–1000): odległości zdominuje pojemność, a słodkość przestanie się liczyć (różnica 500 ml to „500", różnica całej skali słodkości to „10")! Cechy trzeba wyskalować do porównywalnych zakresów, inaczej algorytm słucha tylko najgłośniejszej.
  • Jakość przykładów. k-NN nie ma żadnej wiedzy poza przykładami — śmieci na wejściu, śmieci na wyjściu. Za mało przykładów w jakimś rejonie = wróżenie; błędne etykiety = zaraza przenoszona na sąsiadów.

💭 Pomyśl: k-NN „uczy się" bez żadnego uczenia — po prostu pamięta wszystko. Jaka jest cena tej prostoty przy milionie przykładów i tysiącu klasyfikacji na sekundę?

Sprawdź odpowiedź

Każda klasyfikacja liczy odległość do wszystkich przykładów: milion odległości + sortowanie — na każde z tysiąca zapytań na sekundę. To miliard operacji na sekundę na samo liczenie odległości: na granicy wykonalności. k-NN przenosi cały koszt z uczenia na klasyfikację (odwrotnie niż sortowanie przenosiło koszt na przygotowanie — 6.2!). Dlatego przy dużej skali używa się sprytnych struktur do szukania sąsiadów (drzewa przestrzenne — kuzyni drzew z działu 9) albo modeli, które z przykładów destylują regułę raz, a potem odpowiadają błyskawicznie. Ta wymiana — pamiętać wszystko vs zdestylować raz — to główna oś całego uczenia maszynowego; masz ją teraz w rękach na najprostszym przykładzie.

⚠️ Uwaga, pułapka

Nie myl „algorytm się uczy" z „algorytm rozumie". k-NN sklasyfikuje napój, nie mając pojęcia, czym jest napój — liczy odległości między liczbami, które Ty wybrałeś jako cechy. Wybierzesz cechy bez związku z pytaniem (kolor etykiety, dzień dostawy) — dostaniesz pewnie brzmiące bzdury, bo sąsiedztwo w bezsensownej przestrzeni jest bezsensowne. Dobór cech to miejsce, gdzie do algorytmu wchodzi ludzkie rozumienie problemu — i gdzie wchodzą też ludzkie uprzedzenia (przykłady z przeszłości niosą błędy przeszłości). O konsekwencjach — szerzej w dziale 16; tu zapamiętaj zasadę: model jest wart tyle, co cechy i przykłady, które dostał.

🌍 Powiązania

k-NN w naturalnych rolach: systemy polecające („użytkownicy podobni do Ciebie oglądali…"), diagnostyka wspomagana (podobne przypadki kliniczne), rozpoznawanie odręcznych cyfr (piksele jako cechy — działa zaskakująco dobrze!), wykrywanie anomalii (punkt bez bliskich sąsiadów = podejrzany). A sama idea „podobne przypadki, podobne wyroki" jest starsza niż komputery — tak działa orzecznictwo oparte na precedensach i tak diagnozował lekarz przed erą badań: przez analogię do widzianych przypadków. Uczenie maszynowe sformalizowało bardzo starą ludzką heurystykę.

🛠️ Teraz Ty

Bez komputera: dane sklepiku — hity: (8, 3), (7, 4), (6, 2); kity: (2, 6), (3, 7), (2, 3). Nowy napój (5, 4). Policz sześć odległości (wystarczą kwadraty odległości — bez pierwiastka, porządek ten sam!), wybierz 3 najbliższych i zagłosuj. Z komputerem: zaimplementuj knn, przetestuj na tych danych, a potem dodaj trzecią cechę „mililitry" z wartościami 200–1000 i zobacz na własne oczy, jak psuje werdykty, dopóki jej nie przeskalujesz (np. dziel przez 100).

📐 Definicje tej lekcji

  • Klasyfikacja z przykładów — etykieta nowego przypadku wnioskowana z oznakowanych przykładów, bez podanej reguły.
  • k-NN — znajdź $k$ najbliższych (odległość w przestrzeni cech) i głosuj większością; nieparzyste $k$ unika remisów.
  • Skalowanie cech — sprowadzenie cech do porównywalnych zakresów, by żadna nie zdominowała odległości.

📌 Najważniejsze w pigułce

  • k-NN = pamiętaj przykłady + Pitagoras + sortowanie + głosowanie: uczenie maszynowe z klocków, które znasz.
  • $k$ małe — czułe na błędy; $k$ wielkie — ślepe na położenie; wybór sprawdzaj na odłożonych przykładach.
  • Model jest wart tyle, co cechy i przykłady; „uczy się" nie znaczy „rozumie".

🎒 Zadania

  1. Wykonaj klasyfikację z 🛠️ dla $k = 1$ i $k = 5$. Czy werdykt się zmienia? Co to mówi o wyborze $k$?
Wskazówka i odpowiedź

Kwadraty odległości od (5,4): hity — (8,3): 10; (7,4): 4; (6,2): 5; kity — (2,6): 13; (3,7): 13; (2,3): 10. $k=1$: najbliższy (7,4) hit → hit. $k=3$: sąsiedzi 4, 5, 10 — dwa hity i… remis odległości 10 (hit (8,3) i kit (2,3))! Przyjmując hit (8,3): 3×hit → hit. $k=5$: 4,5,10,10,13 → trzy hity, dwa kity → hit. Werdykt stabilny — dobry znak. Ale zauważ remis odległości przy $k=3$: rozstrzyganie remisów (brać oba? losować? preferować częstszą klasę?) to kolejna decyzja projektowa, którą specyfikacja musi podjąć — nawet „prosty" algorytm ma drobny druk.

  1. Bank klasyfikuje wnioski kredytowe k-NN-em po cechach (dochód w zł, wiek w latach). Dochody: 3000–20000, wiek: 18–80. Co pójdzie nie tak bez skalowania i która cecha „zniknie"?
Wskazówka i odpowiedź

Różnice dochodów liczy się w tysiącach, wieku — w dziesiątkach: odległość zdominuje dochód, wiek stanie się szumem (klient 25-letni i 70-letni z tym samym dochodem będą „identyczni"). Po przeskalowaniu (np. oba zakresy do 0–1) obie cechy głosują. I refleksja głębsza: czy wiek powinien decydować o kredycie? Techniczna decyzja o cechach jest tu decyzją etyczno-prawną — modele dziedziczą uprzedzenia danych, a projektant odpowiada za to, co wpuścił do przestrzeni cech. Do tego wątku wrócimy w dziale 16 na poważnie.

  1. k-NN z $k = 1$ osiąga 100% trafności na przykładach, których się „nauczył" (każdy punkt jest swoim najbliższym sąsiadem). Czemu to nie jest żaden sukces i jak uczciwie zmierzyć jakość klasyfikatora?
Wskazówka i odpowiedź

To egzamin, na którym pytania są identyczne z rozwiązanymi na lekcji — mierzy pamięć, nie umiejętność. Uczciwa miara: odłóż część przykładów (np. 20%), nie pokazuj ich algorytmowi, i sprawdź trafność na nich — na pytaniach, których nie widział. Ten rytuał (podział na dane uczące i testowe) to fundament całego uczenia maszynowego i pierwsza rzecz, o którą pytasz, słysząc „nasz model ma 99% skuteczności": na czym mierzone? Sceptycyzm wobec własnych wyników — ostatnia lekcja tego działu i jedna z ważniejszych w książce.

🔍 Sprawdź, czy umiesz

  • Wykonać k-NN na kartce: odległości, sąsiedzi, głosowanie.
  • Wyjaśnić wpływ $k$ i skalowania cech na werdykt.
  • Powiedzieć, czym różni się trafność na danych uczących od uczciwego testu — i czemu to przepaść.

Ucz się tej jednostki z asystentem