GWKNN: ulepszony algorytm k-najbliższych sąsiadów z rekonstrukcją metryki G i optymalizatorem Grey Wolf

Bardziej inteligentne rozpoznawanie wzorców na dziś'szą falę danych

Od skanów medycznych po transakcje bankowe — współczesne życie generuje oceany danych. Duża część tych informacji musi być automatycznie przyporządkowana do kategorii: zdrowy lub chory, oszustwo lub normalna transakcja, spam lub wiadomość prawdziwa. Klasycznym narzędziem do takich zadań jest algorytm k-najbliższych sąsiadów (KNN), który oznacza nowy przypadek, patrząc na najbardziej podobne przeszłe przykłady. Jednak w miarę jak zbiory danych stają się większe, bardziej złożone i bardziej niezrównoważone, ta prosta idea zaczyna się chwiać. Artykuł przedstawia GWKNN, przeprojektowaną wersję KNN zaprojektowaną tak, by mądrzej wykorzystywać odległości między punktami i sprawiedliwiej traktować rzadkie, lecz ważne przypadki.

Dlaczego prosta podobieństwo nie wystarcza

Tradycyjny KNN zakłada, że wszystkie cechy punktu danych mają równy wkład i mierzy podobieństwo standardową odległością prostoliniową. To może działać dobrze, gdy dane są niskowymiarowe i wyraźnie rozdzielone, ale dane ze świata rzeczywistego często są wysokowymiarowe, zaszumione i mieszanką różnych typów informacji. W takich sytuacjach zwykła miara odległości może wprowadzać w błąd, powodując, że algorytm wybiera nieprzydatnych sąsiadów. Równocześnie wiele zbiorów jest niezrównoważonych: dominują kategorie powszechne, podczas gdy rzadkie, lecz kluczowe kategorie, jak choroba we wczesnym stadium, są niedostatecznie reprezentowane. Gdy KNN głosuje na bazie pobliskich przykładów, klasa większości ma tendencję do zagłuszania tych mniejszości, co prowadzi do stronniczych, a czasem niebezpiecznych decyzji.

Nauka lepszego poczucia odległości przez algorytm

Pierwszą kluczową innowacją w GWKNN jest nauczona miara odległości. Zamiast trzymać się standardowej reguły prostoliniowej, autorzy pozwalają algorytmowi odkryć, jak daleko od siebie powinny być punkty danych, aby najlepiej rozdzielać kategorie. Kodują to jako elastyczną „metrykę G”, która przekształca przestrzeń tak, by informacyjne cechy miały większe znaczenie, a redundantne — mniejsze. Do strojenia tej metryki metoda czerpie inspirację z zachowań łowieckich wilków szarych. Procedura inteligencji rojowej, zwana Grey Wolf Optimizer, eksploruje wiele możliwych sposobów rozciągania i ściskania przestrzeni danych, zachowując te, które redukują błędy klasyfikacji przy jednoczesnym zachowaniu stabilności matematycznej. W kolejnych iteracjach wirtualne „wilki” zbieżają się ku regule odległości, która sprawia, że podobne punkty tworzą bardziej wiarygodne skupiska, nawet w wysokowymiarowych, splecionych zbiorach danych.

Rozdanie głośniejszego głosu rzadkim przypadkom

Drugie usprawnienie dotyczy uprzedzeń w głosowaniu. Standardowy KNN po prostu zlicza, ilu z k sąsiadów należy do każdej klasy i wybiera większość. GWKNN zamiast tego waży każdy głos w zależności od tego, jak powszechna jest dana klasa w całym zbiorze uczącym. Klasom występującym rzadziej przypisuje się większe wagi; bardzo częste klasy otrzymują wagi słabsze. Mały składnik wygładzający zapobiega temu, by ekstremalnie rzadkie kategorie zdominowały decyzję. W ten sposób, jeśli nowy punkt danych znajduje się blisko kilku przykładów klasy mniejszościowej i wielu przykładów klasy większościowej, sygnały mniejszości nie są automatycznie tłumione. Schemat jest prosty do obliczenia, ale ma silny efekt: skłania klasyfikator do zwracania większej uwagi na rzadkie, lecz znaczące wzorce, poprawiając sprawiedliwość i czułość względem klas mniejszościowych.

Testowanie nowej metody

Aby sprawdzić, czy GWKNN rzeczywiście pomaga w praktyce, autorzy ocenili ją na 12 zbiorach referencyjnych z dobrze znanego repozytorium UCI. Kolekcje te obejmują dane finansowe, pomiary medyczne, pisma ręczne, nasiona roślin oraz kilka wysokowymiarowych zbiorów dotyczących raka i ekspresji genów, z problemami dwuklasowymi i wieloklasowymi. Porównali cztery wersje KNN: zwykły punkt odniesienia, wersję z samą nową metryką odległości, wersję z samymi nowymi wagami głosów oraz pełne GWKNN łączące oba pomysły. Zmierzyli się także z GWKNN siedmiu powszechnie używanych klasyfikatorów, w tym maszynami wektorów nośnych, drzewami decyzyjnymi, lasami losowymi, regresją logistyczną, naiwnym Bayesem i siecią neuronową. W powtarzanych podziałach na zbiory uczące i testowe śledzili nie tylko średnią dokładność, ale też wielkość fluktuacji wyników.

Wyniki: dokładniej i bardziej konsekwentnie

Połączone podejście GWKNN okazało się najlepsze lub dzieliło pierwsze miejsce pod względem wyników na większości zbiorów, zwłaszcza na tych z wieloma cechami i nierównymi rozmiarami klas. W stosunkowo prostych zadaniach wszystkie metody radziły sobie dobrze i zyski były skromne, ale GWKNN nadal miało tendencję do nieznacznej poprawy dokładności i zmniejszenia zmienności. W trudniejszych zbiorach ekspresji genów z tysiącami cech zalety były wyraźniejsze: nauczona metryka odległości pomagała algorytmowi tworzyć bardziej sensowne sąsiedztwa, a ważone głosowanie poprawiało rozpoznawanie klas niedostatecznie reprezentowanych. Testy statystyczne na wszystkich zbiorach potwierdziły, że rankingi GWKNN były istotnie lepsze niż standardowego KNN i niektórych klasycznych modeli, co wskazuje, że jego ulepszenia to nie tylko szczęśliwe fluktuacje, lecz trwała poprawa w różnych warunkach danych.

Co to oznacza dla codziennych decyzji opartych na danych

Dla osób nietechnicznych wniosek jest taki, że GWKNN udoskonala bardzo intuicyjną ideę — „spójrz na podobne przeszłe przypadki” — aby lepiej dopasować ją do nieporządku współczesnych danych. Poprzez uczenie, jak mierzyć podobieństwo w sposób zależny od danych, oraz przez zwiększanie wpływu rzadkich kategorii podczas głosowania, metoda ma na celu być zarówno dokładniejsza, jak i sprawiedliwsza. Choć ta dodatkowa złożoność wiąże się z wyższymi kosztami obliczeniowymi, zwłaszcza dla bardzo dużych i wysokowymiarowych zbiorów, GWKNN wykazuje duży potencjał w zadaniach, gdzie poprawna klasyfikacja przypadków mniejszości ma kluczowe znaczenie, takich jak wczesne wykrywanie chorób czy wykrywanie oszustw. Praca pokazuje, jak klasyczne algorytmy można ulepszyć dzięki wnioskom z optymalizacji i sprawiedliwości, aby nadążyć za skalą i złożonością współczesnych informacji.

Cytowanie: Guo, Z., Liu, G., Liu, W. et al. GWKNN: an enhanced k-nearest neighbor algorithm with G metric reconstruction and Grey Wolf Optimizer. Sci Rep 16, 8857 (2026). https://doi.org/10.1038/s41598-026-41851-2

Słowa kluczowe: k-najbliżsi sąsiedzi, uczenie metryki odległości, Niezrównoważenie klas, inteligencja rojowa, klasyfikacja danych