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

Indukcja reguł (RIPPER)

Autor metody
William W. Cohen
Rok
1995
Typ
Supervised rule learning algorithm
Rodzina
Rule learning

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

Rozmiar czcionki

Do czego służy?

Indukcja reguł, a w szczególności algorytm RIPPER (Repeated Incremental Pruning to Produce Error Reduction), jest nadzorowaną metodą uczenia maszynowego, która uczy się zwartego zbioru reguł klasyfikacyjnych typu JEŚLI-WTEDY na podstawie oznakowanych danych treningowych.

Wprowadzony przez Williama W. Cohena w 1995 roku, RIPPER stosuje strategię „dziel i zwyciężaj” (separate-and-conquer) w połączeniu z przycinaniem opartym na minimalnej długości opisu (MDL), aby generować reguły, które są zarówno dokładne, jak i interpretowalne, co czyni go algorytmem przełomowym w dziedzinie indukcyjnej nauki reguł.

Intuicja stojąca za metodą

Wyobraź sobie pisanie listy kontrolnej diagnostycznej dla lekarza: każda reguła wychwytuje specyficzną kombinację objawów, która niezawodnie przewiduje diagnozę. RIPPER buduje tę listę kontrolną automatycznie na podstawie danych pacjentów. Tworzy jedną regułę na raz, obejmując jak najwięcej przypadków pozytywnych, a następnie sprawdza każdą regułę na wydzielonym zbiorze, aby usunąć nadmiernie specyficzne warunki. Wynikiem jest krótka, czytelna dla człowieka księga reguł, którą można zastosować do nowych pacjentów bez konieczności analizowania całej historii treningowej.

Historia

Indukcja reguł ma swoje korzenie we wczesnych systemach uczenia maszynowego, takich jak AQ (Michalski, 1969) i CN2 (Clark i Niblett, 1989). W artykule Cohena z 1995 roku o RIPPER rozwiązano problemy nieefektywności obliczeniowej i tendencji do nadmiernego dopasowania jego poprzedników, wprowadzając przycinanie przyrostowe i optymalizację opartą na MDL. Zaprezentowany na konferencji ICML w 1995 roku, RIPPER szybko stał się algorytmem referencyjnym ze względu na swoją konkurencyjną dokładność i przejrzystość, i pozostaje standardowym odniesieniem w literaturze i podręcznikach dotyczących nauki reguł.

Kiedy stosować

Indukcja reguł z RIPPER jest odpowiednia, gdy interpretowalność modelu jest głównym wymogiem, na przykład w systemach wsparcia decyzji klinicznych, wykrywaniu oszustw lub w ustawieniach zgodności z przepisami. Działa z mieszanymi cechami nominalnymi i numerycznymi i skaluje się rozsądnie do dziesiątek tysięcy instancji. RIPPER zakłada, że etykiety treningowe są wystarczająco wiarygodne i że granica decyzyjna może być aproksymowana przez koniunkcje wyrównane do osi. Jest mniej odpowiedni dla przestrzeni cech ciągłych o wysokiej wymiarowości lub zadań wymagających skalibrowanych wyjść probabilistycznych; w takich przypadkach preferowane mogą być drzewa wzmocnione gradientowo lub regresja logistyczna.

Ograniczenia i uwagi

  • Jakość reguł znacząco spada w przestrzeniach cech o bardzo wysokiej wymiarowości lub rzadkich
  • Uporządkowane listy reguł mogą być wrażliwe na kolejność klas; klasy mniejszościowe nauczane na końcu mogą otrzymać słabsze reguły
  • Nie generuje skalibrowanych oszacowań prawdopodobieństwa, ograniczając zastosowanie w zadaniach wrażliwych na koszty lub rankingowych
  • Reguły koniunkcyjne nie mogą wychwycić złożonych interakcji wymagających granic innych niż wyrównane do osi bez inżynierii cech

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

Mocne strony

  • Generuje czytelne dla człowieka reguły JEŚLI-WTEDY, które eksperci dziedzinowi mogą audytować i walidować
  • Efektywna nauka metodą „dziel i zwyciężaj” z przycinaniem kierowanym przez MDL zmniejsza nadmierne dopasowanie
  • Obsługuje atrybuty nominalne i numeryczne bez potrzeby obszernego przetwarzania wstępnego
  • Generalnie szybki czas treningu w porównaniu do metod zespołowych dla umiarkowanych rozmiarów zbiorów danych

Zastosowania

  • Wsparcie decyzji klinicznych i ekstrakcja reguł diagnostycznych w medycynie
  • Wykrywanie oszustw i anomalii w monitorowaniu transakcji finansowych
  • Kategoryzacja tekstu przy użyciu cech leksykalnych i strukturalnych
  • Wykrywanie intruzji sieciowych za pomocą interpretowalnych reguł alertowych
  • Predykcja odejść klientów za pomocą praktycznych reguł biznesowych

Jak to działa

Jak to działa

1

RIPPER przetwarza jedną klasę na raz, traktując wszystkie pozostałe instancje jako zbiór negatywny. Chciwie rozwija regułę koniunkcyjną, wielokrotnie dodając warunek, który maksymalizuje stosunek przypadków pozytywnych do całkowitej liczby objętych instancji. Po rozwinięciu reguła jest zatwierdzana, a wszystkie objęte przez nią instancje są usuwane przed nauką kolejnej reguły, zgodnie z klasycznym paradygmatem „dziel i zwyciężaj” opisanym przez Cohena (1995).

Wzór
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}
2

Każda kandydacka reguła jest przycinana na wydzielonej partycji walidacyjnej przy użyciu metryki (p - n) / (p + n), gdzie p i n oznaczają odpowiednio poprawnie i niepoprawnie objęte instancje. Warunki są usuwane od końca reguły do początku, dopóki przycinanie zwiększa tę wartość, chroniąc przed nadmiernym dopasowaniem spowodowanym przez wysoce specyficzne koniunkcje, które przypadkowo pasują do zbioru treningowego.

Wzór
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}
3

Po nauczeniu wszystkich reguł dla poszczególnych klas, RIPPER przeprowadza opcjonalną fazę optymalizacji kierowaną zasadą Minimalnej Długości Opisu. Dla każdej reguły w ostatecznym zbiorze algorytm rozważa jej zastąpienie lub rewizję i akceptuje zmianę tylko wtedy, gdy zmniejsza ona całkowitą długość opisu zbioru reguł i pozostałych błędnie sklasyfikowanych danych, równoważąc dokładność ze złożonością modelu.

Wzór
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})
4

W czasie predykcji reguły są stosowane w kolejności, w jakiej zostały nauczone. Nienapotkana instancja otrzymuje etykietę klasy pierwszej reguły, której wszystkie warunki są spełnione przez wartości cech tej instancji. Jeśli żadna reguła nie zostanie aktywowana, instancja trafia do domyślnej klasy, zazwyczaj klasy większościowej z danych treningowych, zapewniając pełne pokrycie przestrzeni wejściowej.

Wzór
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}

Częste pułapki

  • Zastosowanie RIPPER do małych zbiorów danych bez wystarczających danych do przycinania prowadzi do nadmiernie przyciętych reguł o niskim pokryciu
  • Ignorowanie niezbalansowania klas powoduje, że klasa domyślna pochłania klasę mniejszościową, maskując słabe przypomnienie klasy mniejszościowej
  • Traktowanie kolejności nauczonych reguł jako przyczynowej, a nie predykcyjnej, prowadzi do błędnej interpretacji w analizach eksploracyjnych
  • Pominięcie fazy optymalizacji MDL (dostępnej w niektórych implementacjach) może pozostawić redundantne lub sprzeczne reguły w ostatecznym zbiorze

Najczęściej zadawane pytania

Czym RIPPER różni się od drzewa decyzyjnego?

Oba uczą się granic wyrównanych do osi, ale drzewa decyzyjne rekursywnie partycjonują całą przestrzeń cech, tworząc strukturę hierarchiczną. RIPPER zamiast tego uczy się uporządkowanej listy reguł metodą „dziel i zwyciężaj”, co może prowadzić do bardziej zwartych reprezentacji, gdy liczy się tylko kilka wzorców specyficznych dla klasy. Reguły są również łatwiejsze do odczytania przez ekspertów dziedzinowych w izolacji niż ścieżki drzewa.

Czy RIPPER może obsługiwać problemy wieloklasowe?

Tak. RIPPER rozszerza się na ustawienia wieloklasowe, ucząc się reguł dla każdej klasy po kolei, uporządkowanych od najrzadszej do najczęstszej klasy. Instancje objęte regułami dla wcześniejszych klas są usuwane przed nauką reguł dla późniejszych klas. Reguła domyślna przypisuje klasę większościową każdej instancji nieobjętej jawnymi regułami.

Jaka jest rola zasady Minimalnej Długości Opisu w RIPPER?

MDL zapewnia formalne kryterium równoważenia złożoności reguł z dopasowaniem do danych. W fazie optymalizacji RIPPER preferuje zbiory reguł, których całkowita długość opisu – kodująca zarówno reguły, jak i błędnie sklasyfikowane instancje – jest krótsza. Zapobiega to zapamiętywaniu przez algorytm nadmiernie specyficznych reguł, które zapamiętują szum, zamiast wychwytywać rzeczywiste wzorce w danych.

Pokrewne metody

Źródła

  1. Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.

    Otwórz odnośnik DOI
    Skopiowano.