Przejdź do treści
Wróć do wyników wyszukiwania

Półnadzorowany algorytm K-najbliższych sąsiadów

Autor metody
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
Rok
2002 (semi-supervised extension); 1967 (KNN base)
Typ
Semi-supervised classifier / label propagation
Rodzina
Machine learning

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Półnadzorowany algorytm KNN rozszerza klasyczny algorytm K-najbliższych sąsiadów, wykorzystując duże zbiory danych nieetykietowanych obok niewielkiego zbioru danych etykietowanych.

Budując graf KNN dla wszystkich obserwacji i propagując znane etykiety poprzez krawędzie grafu, metoda wnioskuje etykiety dla punktów nieetykietowanych bez konieczności kosztownej ręcznej adnotacji każdej próbki.

Intuicja stojąca za metodą

Wyobraźmy sobie salę lekcyjną, w której tylko garstka uczniów ma identyfikatory z imionami, a reszta jest anonimowa. Standardowy KNN może sklasyfikować anonimowego ucznia, patrząc tylko na pobliskich, oznakowanych sąsiadów. Półnadzorowany KNN zamiast tego modeluje całą salę jako sieć — każdy uczeń połączony ze swoimi najbliższymi sąsiadami — i rozsyła etykiety od oznakowanych uczniów, niczym atrament rozlewający się po mokrym papierze. Ponieważ sieć oddaje ogólną strukturę danych, etykiety docierają do nieetykietowanych punktów w sposób zasadniczy, szanujący podstawową geometrię, zamiast ignorować nieetykietowaną większość.

Historia

Propagacja etykiet na grafach KNN została usystematyzowana przez Zhu i Ghahramani w 2002 roku, bazując na transdukcyjnych SVM Vapnika i wcześniejszych ideach dyfuzji opartej na grafach. Ramy te zostały skonsolidowane w tomie Semi-Supervised Learning (Chapelle et al., 2006) wydanym przez MIT Press, który pozostaje standardowym odniesieniem. Skalowalne biblioteki przybliżonego KNN (FAISS, Annoy) później uczyniły to podejście praktycznym dla milionów punktów i nadal jest ono używane jako silna metoda bazowa do półnadzorowanej klasyfikacji obrazów i tekstu.

Kiedy stosować

Używaj półnadzorowanego KNN, gdy masz mały zbiór etykietowany i dużą pulę danych nieetykietowanych z tego samego rozkładu, dane znajdują się w stosunkowo niskowymiarowej przestrzeni (mniej niż około 50 cech) i wierzysz, że sąsiednie punkty należą do tej samej klasy. Jest dobrze przystosowany do klasyfikacji fragmentów obrazów, kategoryzacji tekstu z rzadkimi adnotacjami i zadań przesiewowych w medycynie, gdzie kosztowna jest ręczna etykietacja przez ekspertów. Unikaj go, gdy dane etykietowane i nieetykietowane pochodzą z różnych rozkładów (przesunięcie kowariancji), przestrzeń cech jest bardzo wysokowymiarowa (graf KNN staje się zawodny), zbiór danych jest wystarczająco mały, aby w pełni nadzorowany KNN już wystarczał, lub granice klas nie pokrywają się ze strukturą lokalnej gęstości danych.

Ograniczenia i uwagi

  • Konstrukcja grafu skaluje się kwadratowo wraz z rozmiarem zbioru danych, chyba że używane są metody przybliżonego wyszukiwania najbliższych sąsiadów.
  • Wydajność gwałtownie spada w przestrzeniach wysokowymiarowych, gdzie metryki odległości tracą moc rozróżniania.
  • Zakłada, że dane etykietowane i nieetykietowane pochodzą z tego samego rozkładu; przesunięcie kowariancji zakłóca działanie metody.
  • Wymaga starannego dostrojenia parametru k, szerokości pasma wag krawędzi i parametru mieszania propagacji.
  • Propagacja etykiet może wzmacniać początkowe błędy etykietowania na dużych częściach grafu.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Wykorzystuje tanie dane nieetykietowane do poprawy dokładności ponad to, co jest możliwe przy użyciu samego zbioru danych etykietowanych.
  • Brak założeń dotyczących modelu parametrycznego: opiera się wyłącznie na lokalnej geometrii sąsiedztwa.
  • Naturalnie obsługuje problemy wieloklasowe bez modyfikacji.
  • Konstrukcja grafu KNN jest przejrzysta i łatwa do inspekcji.
  • Dobrze działa, gdy klasy tworzą zwarte, dobrze rozdzielone klastry w przestrzeni cech.

Zastosowania

  • Klasyfikacja obrazów z małym zbiorem etykietowanych obrazów i dużym korpusem danych nieetykietowanych.
  • Kategoryzacja tekstu i dokumentów, gdzie ręczna etykietacja jest kosztowna.
  • Klasyfikacja dokumentacji medycznej lub preparatów patologicznych z ograniczonymi adnotacjami ekspertów.
  • Wykrywanie oszustw, gdy dostępna jest tylko niewielka liczba potwierdzonych przypadków oszustw.
  • Etykietowanie danych z czujników w środowiskach IoT przemysłowego z rzadkimi zdarzeniami potwierdzonymi.

Jak to działa

Jak to działa

1

Graf jest budowany na wszystkich obserwacjach — zarówno etykietowanych, jak i nieetykietowanych. Każdy węzeł odpowiada jednemu punktowi danych, a skierowane lub nieskierowane krawędzie łączą każdy węzeł z jego k najbliższymi sąsiadami w przestrzeni cech. Wybór k kontroluje, jak lokalnie lub globalnie będą propagowane etykiety: małe k utrzymuje propagację w ścisłym zakresie; duże k pozwala etykietom przeskakiwać przez większe luki.

2

Wagi krawędzi odzwierciedlają siłę podobieństwa między połączonymi węzłami, zazwyczaj za pomocą jądra Gaussa (RBF) zastosowanego do odległości euklidesowej między wektorami cech. Parametr szerokości pasma sigma kontroluje, jak szybko podobieństwo maleje wraz z odległością. Silniejsze krawędzie łatwiej przenoszą etykiety podczas propagacji.

Wzór
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

Etykiety są rozsyłane iteracyjnie od węzłów etykietowanych do nieetykietowanych sąsiadów. W każdej iteracji każdy węzeł aktualizuje swój rozkład miękkich etykiet jako ważoną kombinację bieżących rozkładów swoich sąsiadów i własnej początkowej etykiety (jeśli jest etykietowany). Parametr mieszania alpha równoważy wpływ struktury grafu w stosunku do twardych etykiet, a iteracje trwają do momentu zbieżności rozkładów.

Wzór
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

Po zbiegnięciu propagacji, każdy nieetykietowany węzeł otrzymuje klasę z najwyższym wynikiem miękkiej etykiety w swoim zbieżnym rozkładzie. Węzły etykietowane są utrwalane na swoich prawdziwych etykietach przez cały czas, więc znane etykiety nigdy nie są nadpisywane.

Wzór
\hat{y}_i = \arg\max_c F_{ic}

Częste pułapki

  • Konstrukcja grafu KNN bez normalizacji cech, powodująca dominację cech o dużej wariancji w obliczeniach odległości.
  • Ustawienie zbyt dużego k, co wygładza rzeczywiste granice klas i prowadzi do nadmiernie wygładzonych rozkładów etykiet.
  • Ignorowanie możliwości, że dane nieetykietowane są spoza rozkładu w stosunku do zbioru etykietowanego.
  • Raportowanie dokładności na węzłach nieetykietowanych, tak jakby była to nieobciążona estymata zbioru testowego — nieetykietowane węzły przeniknęły do grafu podczas treningu.
  • Pomijanie kontroli zbieżności i używanie ustalonej, arbitralnej liczby iteracji propagacji.

Najczęściej zadawane pytania

Jak wybrać k?

Zacznij od k w zakresie 5-15 i dostosuj na podstawie dokładności walidacji na odłożonym zbiorze etykietowanym. Mniejsze k daje ostrzejsze, bardziej lokalne granice; większe k pozwala etykietom propagować się dalej, ale ryzykuje przekroczenie prawdziwych granic klas.

Czy mogę uczciwie ocenić metodę, gdy większość danych jest nieetykietowana?

Odłóż dedykowany zbiór testowy etykietowany, który nigdy nie jest dodawany do grafu. Węzły w grafie — nawet nieetykietowane — są częścią treningu, więc każdy etykietowany węzeł, który uczestniczy w konstrukcji grafu, nie może jednocześnie służyć jako punkt testowy.

Co jeśli mój zbiór danych jest zbyt duży, aby zbudować pełny graf KNN?

Użyj bibliotek przybliżonego wyszukiwania najbliższych sąsiadów, takich jak FAISS lub Annoy, aby zbudować graf w czasie O(n log n) zamiast O(n^2), a następnie zastosuj propagację etykiet na rzadkim grafie przybliżonym.

Czy półnadzorowany KNN zawsze przewyższa nadzorowany KNN?

Niekoniecznie. Jeśli dane nieetykietowane są spoza rozkładu lub przestrzeń cech jest bardzo wysokowymiarowa, graf jest zaszumiony, a propagacja może pogorszyć wydajność. Zawsze porównuj z nadzorowaną metodą bazową KNN, zanim przypiszesz korzyść z danych nieetykietowanych.

Czy to to samo co rozprzestrzenianie etykiet lub propagacja etykiet w scikit-learn?

Ściśle powiązane. LabelPropagation i LabelSpreading w scikit-learn implementują ramy Zhu i Ghahramani, używając grafu z jądrem KNN lub RBF, więc są to bezpośrednie implementacje opisanej tutaj metody.

Pokrewne metody

Źródła

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Skopiowano.