Metody odkrywania wiedzy: wykład 5
Indukcja reguł

Paweł Cichosz

Date: 2001/2002

Wykład dotyczy metod generowania reguł klasyfikacji na podstawie przykładów.

Zbiór reguł jako hipoteza

Reguła rozumiana zwykle jako wyrażenie postaci logicznej implikacji (,,jeżeli przesłanki to konkluzja'' lub ,,jeżeli warunki to decyzja'') jest najbardziej naturalną metodą reprezentacji wiedzy. Nas będzie interesować zastosowanie jej do zapisu wiedzy dotyczącej klasyfikacji, a więc do reprezentacji hipotez w indukcyjnym uczeniu się pojęć. Część przesłankowa reguły określa wówczas warunki dotyczące wartości atrybutów klasyfikowanego przykładu, a część decyzyjna określa jego kategorię.

Zapis i interpretacja reguł

W ogólnym przypadku można dopuszczać zapis warunków reguł jako dowolnych złożonych formuł logicznych zbudowanych z formuł atomowych mających postać relacji równości, nierówności lub przynależności dla wartości jednego atrybutu. Taka formuła atomowa (warunek elementarny) odpowiada testowi w drzewie decyzyjnym. W praktyce -- ze względu m.in. na efektywność obliczeniową generowania reguł i łatwość ich interpretacji -- jako warunki reguł dopuszcza się najczęściej wyłącznie formuły będące koniunkcją warunków elementarnych. Ponieważ dowolna formuła może być sprowadzona do dysjunkcyjnej postaci normalnej (alternatywy koniunkcji), wiadomo, że reprezentacja hipotez za pomocą zbiorów reguł z koniunkcyjnymi warunkami jest wystarczająca, jeśli interpretujemy zbiór reguł jako alternatywę. Zagadnienie to będzie rozwinięte dalej.

Wspomniane elementarne warunki dotyczące wartości pojedynczego atrybutu nazywane są zwyczajowo selektorami, a ich koniunkcje -- kompleksami, przy czym przyjmuje się ograniczenie, że kompleks zawiera co najwyżej jeden selektor dla każdego atrybutu. Przy tym założeniu można przyjąć wygodną konwencję, zgodnie z którą kompleks jest wektorem selektorów, zawierającym dokładnie jeden selektor dla każdego atrybutu, jeśli dodatkowo wprowadzimy specjalny rodzaj selektora odpowiadający warunkowi spełnionemu przez każdą wartość atrybutu. Regułę złożoną z kompleksu $k$ i kategorii $d$ zapiszemy jako $k\rightarrow d$. Dla reguły $r$ jej kompleks i kategorię będziemy oznaczać odpowiednio przez $k_r$ i $d_r$.

Selektory

W dalszych rozważaniach założymy, że każdemu atrybutowi $a_i$, $i=1,2,\dots,n$ w kompleksie odpowiada selektor $s_i$ jednego z czterech rodzajów:

selektor pojedynczy:

spełniony dla przykładu $x$, jeśli atrybut $a_i$ dla tego przykładu ma pewną wskazaną wartość z jego przeciwdziedziny $v\in A_i$ (selektor taki będziemy zapisywać jako właśnie tę wartość $v$), a więc warunek równoważny takiemu selektorowi można zapisać jako $a_i(x)=v$;

selektor dysjunkcyjny:

spełniony dla przykładu $x$, jeśli atrybut ma jedną z wymienionych wartości z jego przeciwdziedziny $v_{i1},v_{i2},\dots,v_{im}\in A_i$, przy czym $\{v_{i1},v_{i2},\dots,v_{im}\}\neq A$ (selektor taki będziemy zapisywać jako listę tych wartości oddzielonych symbolem alternatywy $\lor$, $v_{i1}\lor v_{i2}\lor\dots\lor v_{im}$), co oznacza, że warunek równoważny takiemu selektorowi można zapisać jako $a_i(x)=v_{i1}\lor a_i(x)=v_{i2}\lor\dots\lor a_i(x)=v_{im}$;

selektor uniwersalny:

spełniony dla przykładu $x$ przez dowolną wartość atrybutu $a_i$ z jego przeciwdziedziny (selektor taki będziemy zapisywać jako symbol $?$), wobec czego warunek równoważny takiemu selektorowi można zapisać jako $a_i(x)\in A_i$;

selektor pusty:

warunek nie spełniony dla przykładu $x$ przez żadną wartość atrybutu $a_i$ z jego dziedziny (selektor taki będziemy zapisywać jako symbol $\emptyset$).

Selektor uniwersalny pozwala nie nakładać żadnych ograniczeń na wartości atrybutu. Selektor pusty będzie przydatny przy opisie algorytmów generowania reguł.

Wygodnie jest charakteryzować dowolny selektor $s$ dla atrybutu $a:X\mapsto A$ za pomocą zbioru wartości dozwolonych $V_s\subseteq A$, przy czym

1. $V_s=\{v\}$ dla selektora pojedynczego $s=v$,
2. $V_s=\{v_1,\dots,v_m\}\subset A$ dla selektora dysjunkcyjnego $s=v_1\lor\dots\lor v_m$,
3. $V_s=A$ dla selektora uniwersalnego $s=?$,
4. $V_s=\emptyset$ dla selektora pustego $s=\emptyset$.

Między selektorem $s$ a związanym z nim zbiorem dozwolonych wartości $V_s$ istnieje jednojednoznaczna odpowiedniość, można więc mówić o nich wymiennie. Będziemy w związku z tym przyjmować, że mając dany selektor $s$ mamy także odpowiedni zbiór wartości dozwolonych $V_s$ oraz odwrotnie, że dany zbiór wartości $V\subseteq A$ wyznacza selektor $s_V$ odpowiadający atrybutowi o przeciwdziedzinie $A$. W szczególności, posługując się zbiorami wartości selektorów możemy w prosty sposób zdefiniować relację pokrywania przykładów przez selektory.

Selektor $s$ odpowiadający atrybutowi $a:X\mapsto A$ pokrywa przykład $x\in X$, jeśli $a(x)\in V_s$, przy czym $V_s$ oznacza zbiór wartości dozwolonych dla selektora $s$. Piszemy wówczas $s\rhd x$.

Selektory pojedyncze i dysjunkcyjne mogą być stosowane dla atrybutów nominalnych lub porządkowych, których zbiory wartości są dyskretne. Selektorów odpowiednich dla atrybutów ciągłych nie będziemy rozważać, gdyż stosując indukcję reguł praktycznie zawsze poddaje się je dyskretyzacji.

Kompleksy

Kompleks będziemy zapisywać jako ujętą w trójkątne nawiasy listę selektorów, oddzielonych przecinkami, odpowiadających wszystkim atrybutom określonym na dziedzinie, zakładając, że są one uporządkowane i selektor na pozycji $i$ odpowiada $i$-temu atrybutowi. Relację pokrywania przykładów przez kompleksy określimy w następujący sposób.

Kompleks $k=\langle s_1,s_2,\dots,s_n\rangle$ pokrywa przykład $x\in X$, jeśli każdy selektor $s_i$ dla $i=1,2\dots,n$ pokrywa przykład $x$. Piszemy wówczas $k\rhd x$.

Każdy kompleks zawierający przynajmniej jeden selektor pusty nie pokrywa żadnego przykładu, więc wszystkie taki ekompleksy możemy utożsamić i zapisywać krótko jako $\langle\emptyset\rangle$, co nazwiemy kompleksem pustym. Z kolei Kompleks zawierający wyłącznie selektory uniwersalne $?$ będzie nazywany kompleksem uniwersalnym i oznaczany przez $\langle ?\rangle$. Wyróżnimy też jako szczególny przypadek kompleks zawierający dokładnie jeden selektor niepusty i nieuniwersalny (a więc pojedynczy lub dysjunkcyjny) i prócz niego wyłącznie selektory uniwersalne -- taki kompleks będziemy nazywać kompleksem atomowym. Kompleks atomowy ogranicza dopuszczalne wartości dokładnie jednego atrybutu.

Porównywanie kompleksów

Dla kompleksów można określić relację porównywania ze względu na ogólność i szczegółowość.

Dla dziedziny $X$ i danych dwóch kompleksów $k_1$ i $k_2$ mówimy, że $k_1$ jest bardziej ogólny niż $k_2$ (i równoważnie $k_2$ jest mniej ogólny niż $k_1$, $k_2$ jest bardziej szczegółowy niż $k_1$, $k_1$ jest mniej szczegółowy niż $k_2$) wtedy i tylko wtedy, gdy

$$\{x\in X \;\vert\; k_2\rhd x\} \subset \{x\in X \;\vert\; k_1\rhd x\}$$ (1)

Piszemy wówczas $k_1\succ k_2$, $k_2\prec k_1$.

Dla dowolnego zbioru przykładów $P\subseteq X$ i kompleksu $k$ przez $P_k$ będziemy oznaczać podzbiór $P$ złożony z przykładów pokrywanych przez $k$:

$$P_k = \{x\in P \;\vert\; k\rhd x\}$$ (2)

Dopisanie w górnym indeksie kategorii dodatkowo zawęzi zbiór do przykładów tej kategorii, podobnie jak to było przyjmowane wcześniej.

Interpretacja zbioru reguł

Weźmy pod uwagę zbiór reguł postaci $k\rightarrow d$, gdzie $k$ jest kompleksem i $d\in C$ jedną z kategorii. Aby umożliwić reprezentowanie dowolnej hipotezy dającej się określić dla danego zestawu atrybutów, nie możemy przyjąć żadnego ograniczenia na liczbę reguł. Używacie zbioru reguł do klasyfikacji dowolnego przykładu $x\in X$ polega na znalezieniu reguły pokrywającej (tj., której kompleks pokrywa) ten przykład. W przypadku, gdy znajdzie się dokładnie jedna taka reguła, jej kategoria jest wartością przypisywaną temu przykładowi przez hipotezę reprezentowaną przez zbiór reguł. Niestety, może zdarzyć się również tak, że przykład będzie pokryty przez wiele reguł z być może różnymi kategoriami lub nie będzie pokryty przez żadną regułę. Postępowanie w takich przypadkach zależy od tego, czy zbiór reguł traktujemy jako uporządkowany, czy nieuporządkowany.

Nieuporządkowane zbiory reguł

Nieuporządkowany zbiór reguł można rzeczywiście w ścisłym sensie nazywać zbiorem -- wchodzące w jego skład reguły nie są uszeregowane w żadnej ustalonej kolejności i każda z nich jest traktowana tak samo. Do rozstrzygania sytuacji, gdy liczba pokrywających przykład reguł jest równa 0 lub większa od $1$, jest potrzebne przyjęcie specjalnych strategii.

Weźmy pod uwagę hipotezę $h:X\mapsto C$ reprezentowaną przez zbiór reguł $R$ i zajmijmy się sytuacją, gdy pewien przykład jest pokrywany przez większą od $1$ liczbę reguł z tego zbioru. Z każdą regułą $r\in R$ można związać liczbę pokrywanych przez nią przykładów trenujących $T_r$ (wyznaczając odpowiedni licznik w trakcie generowania zbioru reguł). Proces klasyfikacji przykładu pokrywanego przez różne reguły można wówczas potraktować jako głosowanie reguł, z liczbą głosów dla każdej z nich równą liczbie pokrywanych przez nią przykładów trenujących. Przewidywaną kategorię przykładu $x$ wyznaczymy jako:

$$h(x) = \mathrm{arg}\max_{d\in C}\sum_{r\in R^d_x}\vert T_r\vert$$ (3)

przy czym $R^d_x$ oznacza zbiór reguł dla kategorii $d$ pokrywających $x$:

$$R^d_x = \{r\in R \;\vert\; r\rhd x\land d_r=d\}$$ (4)

Inne proste strategie postępowania z przykładami pokrywanymi przez wiele reguł w nieuporządkowanych zbiorach reguł to:

• losowy wybór jednej z reguł pokrywających klasyfikowany przykład,
• wybór najbardziej szczegółowej reguły wśród reguł pokrywających przykład lub reguły o najmniejszej liczbie selektorów uniwersalnych w kompleksie,
• losowy wybór kategorii według rozkładu prawdopodobieństwa wyznaczonego przez rozkład częstości kategorii wśród reguł pokrywających przykład.

Mimo prostoty mogą one osiągać całkiem zadowalającą skuteczność, a prostota ta przekłada się na mniejszy koszt obliczeniowy klasyfikacji przykładów, co niekiedy jest ważne w praktycznych zastosowaniach.

Dla przykładów nie pokrywanych przez żadną regułę można zaproponować przynajmniej dwa podejścia. Pierwsze, najprostsze, polegałoby na przyporządkowywaniu takim nie pokrywanym przykładom kategorii domyślnej, którą najrozsądniej określić jako większościową kategorię w zbiorze trenującym:

$$h(x) = \mathrm{arg}\max_{d\in C}\vert T^d\vert$$ (5)

Drugie i bardziej wyrafinowane podejście, jakie można wziąć pod uwagę, polega na wprowadzeniu pewnej miary częściowego pokrywania przykładów przez reguły. Dla każdej reguły $r\in R$ i przykładu $x\in X$ należy określić pewną wartość $\mu(r,x)\in[0,1]$, równą $1$ w przypadku, gdy reguła $r$ pokrywa $x$, i mniejszą od $1$ w pozostałych przypadkach. Ponieważ pokrywanie przykładów przez reguły jest równoważne z pokrywaniem ich przez kompleksy, przyjmiemy $\mu(r,x)=\mu(k_r,x)$ dla dowolnej reguły $r$ i przykładu $x$. Miarę częściowego pokrywania określimy dla dowolnego kompleksu $k$ i przykładu $x$ następująco:

$$\mu(k,x) = \prod_{i=1}^n\mu(s^k_i,x)$$ (6)

przy czym $s^k_i$ oznacza selektor znajdujący się w kompleksie $k$ na pozycji $i$. Wartość $\mu(s^k_i,x)$ jest miarą pokrywania przez ten selektor przykładu $x$. Jej przykładowa definicja, dla dowolnego selektora $s$ odpowiadającego atrybutowi nominalnemu lub porządkowemu $a:X\mapsto A$ o skończonej przeciwdziedzinie $A$, może mieć postać:

$$\mu(s,x) = \begin{cases}1 & \text{jeśli $a(x)\in V_s$,}\\ \frac{\vert V_s\vert}{\vert A\vert} & \text{jeśli $a(x)\not\in V_s$.} \end{cases}$$ (7)

Uwzględniając częściowe pokrywanie można określić zmodyfikowaną wersję głosowania reguł, w którym również częściowo pokrywające przykład reguł mają (ułamkowy) głos:

$$h(x) = \mathrm{arg}\max_{d\in C}\sum_{r\in R}\mu(r,x)\vert T^d_r\vert$$ (8)

i stosować ją do wyznaczania kategorii przykładów nie pokrywanych przez żadną regułę ze zbioru $R$.

Uporządkowane zbiory reguł

Komplikacji, które były dyskutowane wyżej, można uniknąć, wykorzystując algorytmy uczenia się generujące uporządkowane zbiory reguł. Jest dla nich jednoznacznie ustalona kolejność, w jakiej reguły mają być wykorzystywane do klasyfikowania przykładów. Hipoteza reprezentowana przez taki zbiór reguł przyporządkowuje klasyfikowanemu przykładowi kategorię związaną z pierwszą w kolejności regułą, która ten przykład pokrywa. Taki uporządkowany zbiór reguł nazywany jest niekiedy listą decyzyjną. Jest to lista reguł, po każdej z których następuje domniemana fraza ,,w przeciwnym przypadku'' -- jeśli warunki reguły nie są spełnione, brana jest pod uwagę kolejna reguła na liście. W ten sposób eliminowany jest problem klasyfikowania przykładów pokrywanych przez więcej niż jedną regułę, gdyż zawsze jest stosowana reguła o najmniejszym numerze. Wciąż może się jednak zdarzyć, że przykład nie zostanie pokryty przez żadną regułę. Używanie częściowego pokrywania do wyznaczania kategorii jest wówczas trudne do pogodzenia z uporządkowaniem reguł (czy preferować regułę wcześniejszą mniej ,,pasującą'' do przykładu, czy późniejszą, ale bardziej ,,pasującą''?), więc najczęstsze podejście polega na dodaniu do zbioru reguł jako ostatniej w kolejności reguły postaci $\langle ?\rangle\rightarrow d$, przy czym $d$ jest domyślną kategorią, ustaloną na podstawie zbioru trenującego jako kategoria większościowa.

Sekwencyjne pokrywanie

Większość praktycznie stosowanych algorytmów uczenia się reguł jest oparta na wspólnym, prostym schemacie sekwencyjnego pokrywania. Polega on na generowaniu po jednej kolejnych reguł, dopóki nie zostanie przez nie pokryty cały (najczęściej) lub prawie cały (niekiedy) zbiór trenujący, przy czym generując każdą pojedynczą regułę poszukuje się kompleksu zapewniającego pokrycie możliwie wielu przykładów trenujących i uzyskanie reguły możliwie dokładnej. Takie postępowanie opisuje następujący szkieletowy algorytm.

Po znalezieniu kompleksu jest na jego podstawie tworzona nowa reguła, której kategorię określa się na podstawie zbioru trenującego $T$ i/lub jego podzbioru $P$ niepokrytego przez wcześniej utworzone reguły. Powinna to być oczywiście kategoria większościowa, przy czym

• jeśli ma być generowany nieuporządkowany zbiór reguł, należy wybrać kategorię większościową w zbiorze $T$,
• jeśli ma być generowany uporządkowany zbiór reguł, należy wybrać kategorię większościową w zbiorze $P$.

Rdzeniem każdego algorytmu indukcji reguł opartego na sekwencyjnym pokrywaniu jest znajdowanie kompleksu dla kolejnej reguły. Zazwyczaj proces ten jest zorganizowany jako heurystyczne przeszukiwanie przestrzeni możliwych kompleksów, które rozpoczyna się od kompleksu uniwersalnego $\langle ?\rangle$ i poddaje go specjalizacji (zastępuje kompleksami bardziej szczegółowymi) w sposób ukierunkowany pewną funkcją oceny jakości. Kierunek przeszukiwania od kompleksu maksymalnie ogólnego do bardziej szczegółowych zapewnia, że znaleziony będzie kompleks pokrywający możliwie wiele przykładów trenujących.

Specjalizacja kompleksów

Różne algorytmy realizują proces specjalizacji kompleksów na różne sposoby. Jedno z podejść, występujące w dwóch popularnych algorytmach AQ i CN2, polega na zastosowaniu przeszukiwania wiązkowego. W tej strategii przeszukiwania jest tworzony i aktualizowany zbiór kompleksów-kandydatów, czasem nazywany gwiazdą, początkowo zawierający tylko kompleks uniwersalny $\langle ?\rangle$, a potem w kolejnych iteracjach coraz bardziej szczegółowe kompleksy, których liczbę zawsze ogranicza się do ustalonej liczby $m$ najlepszych według przyjętej funkcji oceny kompleksów (parametr ten jest nazywany szerokością wiązki).

Algorytm AQ

W algorytmie specjalizacji wykorzystuje się wybrane przykłady trenujące. Pierwszy przykład, nazywany ziarnem (pozytywnym), jest wybierany jednokrotnie na początku operacji znajdowania kompleksu, ze zbioru nie pokrytych przykładów $P$. Specjalizację prowadzi się tak, aby ziarno zawsze pozostało pokrywane. Każdy krok specjalizacji jest wykonywany z wykorzystaniem wybranego przykładu trenującego kategorii innej niż kategoria ziarna, pokrywanego przez przynajmniej jeden kompleks gwiazdy. Przykład ten jest nazywany ziarnem negatywnym. Specjalizacja jest prowadzona tak, by zapewnić, że ten przykład (i zapewne wiele innych podobnych) przestanie być pokrywany, zmniejszając liczbę pokrywanych przykładów kategorii innej niż kategoria ziarna. W każdym kroku tworzy się zbiór kompleksów nazywany częściową gwiazdą, zawierający wszystkie maksymalnie ogólne kompleksy pokrywające ziarno i nie pokrywające ziarna negatywnego. Nowymi elementami gwiazdy stają się wyniki wszystkich koniunkcji parami elementów dotychczasowej gwiazdy i częściowej gwiazdy, po czym następuje obcięcie do $m$ najlepszych. Proces specjalizacji w standardowym algorytmie AQ trwa do czasu wyeliminowania pokrywania przez którykolwiek kompleks gwiazdy jakiegokolwiek przykładu trenującego kategorii innej niż kategoria ziarna, aczkolwiek możliwe są modyfikacje łagodzące to -- nie zawsze możliwe do spełnienia -- kryterium. Jeśli ma być tworzony uporządkowany zbiór reguł, ten wymóg należy zastosować wyłącznie do przykładów trenujących nie pokrytych przez wcześniej wygenerowane reguły.

Algorytm CN2

Specjalizacja w CN2 nie jest zogniskowana wokół żadnych przykładów trenujących. W każdym kroku generowane są wszystkie możliwe kompleksy bardziej szczegółowe niż kompleksy w aktualnej gwieździe, z których pozostawia się $m$ najlepszych. Jednocześnie przechowywany jest najlepszy dotychczas znaleziony kompleks (początkowo jest to kompleks uniwersalny), przy czym porównując nowe kompleksy z dotychczas najlepszym bierze się pod uwagę tylko takie, które przejdą test statystycznej istotności.

Ocena kompleksów

Ogólne zasady, którymi należy się kierować przy ocenie kompleksów, są oczywiste: preferowane powinny być kompleksy, które pokrywają możliwie wiele przykładów dotąd nie pokrytych (tak aby powstała reguł pokrywająca znaczącą część zbioru trenującego) oraz dokładne, czyli pokrywające przykłady, wśród których wyraźnie dominuje jedna kategoria. Dokładność można przy tym oceniać albo na całym zbiorze trenującym (jeśli chcemy uzyskać zbiór nieuporządkowany reguł), albo tylko na jego podzbiorze nie pokrytym przez wcześniej powstałe reguły (jeśli chcemy uzyskać uporządkowany zbiór reguł).

Algorytm AQ zapewnia, że będący ostatecznym wynikiem specjalizacji kompleks jest dokładny (wynika to z istoty algorytmu specjalizacji), przy czym to, na jakim zbiorze jest dokładny (całym czy tylko nie pokrytym przez wcześniejsze reguły) zależy od tego, z jakiego zbioru wybierane są ziarna negatywne i od dokładności na jakim zbiorze uzależnione jest kryterium stopu specjalizacji. W związku z tym przy ocenie kompleksów uwzględnia się zazwyczaj liczbę pokrywanych przykładów kategorii zgodnej z kategorią ziarna, nie pokrytych przez wcześniejsze reguły (im większa, tym lepiej), ewentualnie dodatkowo biorąc pod uwagę liczbę pokrywanych przykładów kategorii różnych od kategorii ziarna (im mniej, tym lepiej).

W przypadku algorytmu CN2 nie ma gwarancji dokładności kompleksu wynikającej z samego mechanizmu specjalizacji i musi ją zapewnić funkcja oceny. W podstawowej wersji algorytmu jest w tym celu używana entropia, obliczana dla kompleksu $k$ według wzoru:

$$E_k(P) = \sum_{d\in C} -\frac{\vert P^d_k\vert}{\vert P_k\vert}\log\frac{\vert P^d_k\vert}{\vert P_k\vert}$$ (9)

uznając kompleksy za tym lepsze, im mniejsza wartość ich entropii. Innym możliwym podejściem jest ocenianie jakości kompleksów bezpośrednio według ich dokładności określanego za pomocą $m$-szacowania w następujący sposób:

$$\frac{\vert P^d_k\vert+m\frac{1}{\vert C\vert}}{\vert P_k\vert+m}$$ (10)

gdzie $d$ jest większościowa kategorią w zbiorze $P_k$. Często przyjmuje się przy tym $m=\vert C\vert$.

Dodatkowo w algorytmie CN2 wykorzystuje się test statystycznej istotności: tylko kompleksy, które go przejdą, są porównywane z dotychczas najlepszym kompleksem i mogą go zastąpić. Do testowania istotności można wykorzystać statystykę $\chi^2$ lub $G^2$ (ta druga była stosowana w oryginalnej wersji algorytmu), mierzącą niezależność dwóch cech: kategorii i bycia pokrywanym przez oceniany kompleks. Za istotne uznaje się kompleksy, dla których wartość statystyki przekracza ustalony próg.

Przycinanie zbiorów reguł

Analogicznie jak w przypadku generowania drzew decyzyjnych, zbiory reguł w praktyce poddawane są najcześciej przycinaniu, które ma zapobiec nadmiernemu dopasowaniu. Przycinanie zbiorów reguł może polegać na eliminowaniu całych reguł ze zbioru lub eliminowaniu pewnych warunków reguł (przez zastępowanie wybranego selektora nieuniwersalnego selektorem uniwersalnym). Kryteria, jakie bywają stosowane do podejmowania decyzji o przycięciu, są analogiczne do tych stosowanych przy przycinaniu reguł.

Zagadnienia praktyczne

Reguły probabilistyczne

Niekiedy wskazane jest, aby reguły były interpretowane probabilistycznie i reprezentowana przez nie hipoteza dawała oszacowania prawdopodobieństw różnych kategorii dla klasyfikowanego przykładu. Jest to zasadne zwłaszcza wtedy, gey nie jest możliwe uzyskanie zadowalająco dokładnych reguł do klasyfikacji deterministycznej. Przyjmiemy wówczas, że dla każdej reguły $r\in R$ jest przechowywany rozkład częstości poszczególnych kategorii wśród pokrywanych przez nią przykładów trenujących, reprezentowany przez wartości $\vert T^d_r\vert$ dla poszczególnych $d\in C$ (liczniki wyznaczone przy generowaniu reguł). Na podstawie tych liczników można szacować prawdopodobieństwa poszczególnych kategorii, przy czym dokładny sposób postępowania -- tak jak dla reguł deterministycznych -- zależy od tego, czy klasyfikowany przykład jest pokrywany przez dokładnie jedną regułę, przez wiele reguł, czy przez żadną regułę, i czy zbiór reguł traktujemy jako uporządkowany czy nieuporządkowany.

Zaszumione dane

Podstawowym problemem związanym z niepoprawnością danych trenujących jest ryzyko nadmiernego dopasowania. O jego zmniejszaniu za pomocą przycinania była już mowa wyżej. Dla niektórych rodzajów przekłamań w zbiorze trenującym mogą jednak wystąpić także inne problemy. Nietrudno zauważyć, że jeśli znajdą się w nim dwa przykłady o takich samych wartościach wszystkich atrybutów, lecz o różnych kategoriach (czyli wystąpi sprzeczność), to algorytm AQ w pewnym momencie trafi na ziarno, dla którego nigdy nie zdoła znaleźć kompleksu spełniającego jego wymagania. Najprostsze rozwiązanie, które umożliwia kontynuowanie uczenia się mimo wystąpienia sprzeczności, polega na pominięciu przykładu, który doprowadził do jej ujawnienia się. Oznacza to pominięcie ziarna negatywnego, które jest w sprzeczności z aktualnym ziarnem pozytywnym, i kontynuowanie generowania gwiazdy w zwykły sposób.

Warto zauważyć, że problemu sprzeczności przykładów trenujących nigdy nie może wyeliminować sam podstawowy algorytm uczenia się, a co najwyżej może go zignorować. O ile jednak algorytm CN2 ignoruje takie sprzeczności w sposób ,,rozsądny'', gdyż oceniając kompleksy wymaga od nich dużej, niekoniecznie jednak pełnej dokładności oraz statystycznej istotności, o tyle prosta strategia ignorowania sprzeczności podana wyżej dla algorytmu AQ ma poważne mankamenty. Jeśli jako ziarno pozytywne został pechowo wybrany przykład przekłamany, to będzie pominięte nieprzekłamane ziarno negatywne, a powstały kompleks, zapewne bardzo szczegółowy, nie będzie reprezentował zależności użytecznej z punktu widzenia pojęcia docelowego. Konsekwentne trzymanie się wybranego ziarna pozytywnego i pomijanie sprzecznych z nim przykładów może więc prowadzić do złych efektów i niekiedy rozsądniej byłoby porzucić to ziarno i to właśnie je pominąć. Nie jest jednak jasne, jakie kryteria należałoby tu przyjąć. Jeden ze sposobów postępowania mógłby polegać na tym, aby po tymczasowym pominięciu ziarna negatywnego porównać uzyskany w ten sposób kompleks za pomocą stosowanych funkcji oceny z kompleksem lub kompleksami pokrywającymi to ziarno negatywne. Jeśli dotychczas taki kompleks nie został utworzony, można wygenerować go wybierając pominięty przykład jako nowe ziarno pozytywne. Jeśli kompleksy pokrywające przykład pominięty wypadają w ocenie lepiej, to zapewne decyzja o jego pominięciu nie była słuszna, a pominąć należy raczej będące w nim w sprzeczności poprzednie ziarno pozytywne.

Niekiedy lepszym pomysłem może być wstępne przetworzenie zbioru trenującego mające na celu eliminację występujących w nim sprzeczności. Jednokrotnie ,,przefiltrowany'' w ten sposób zbiór przykładów może być następnie wielokrotnie używany dla różnych algorytmów uczenia się lub różnych wartości ich parametrów. Ten rodzaj przetwarzania możemy określić jako wybór reprezentatywnych przykładów trenujących.

Atrybuty porządkowe i ciągłe

Omawiane algorytmy generowania reguł oparte były na założeniu, że do reprezentacji warunków nakładanych na wartości atrybutów wykorzystywane są wyłącznie selektory pojedyncze lub dysjunkcyjne, co jest do przyjęcia tylko dla atrybutów nominalnych lub porządkowych o skończonej (niezbyt dużej) liczbie wartości. Atrybuty porządkowe o większej liczbie wartości i atrybuty ciągłe wymagałyby raczej selektorów nierównościowych czy przedziałowych. Jest możliwe opracowanie rozszerzeń podstawowych algorytmów, dopuszczających takie selektory. Modyfikacje dotyczyłyby oczywiście wyłącznie mechanizmów specjalizacji kompleksów. Jednak -- ze względu na koszt obliczeniowy i czytelność uzyskiwanych reguł -- za lepsze podejście uznaje się zazwyczaj wstępną dyskretyzację atrybutów ciągłych i agregację atrybutów porządkowych, co umożliwia stosowanie algorytmów indukcji reguł bez zmian.

Inkrementacyjna indukcja reguł

Praktyczne uwarunkowania niektórych zastosowań mogą wymagać inkrementacyjnego uczenia się. Wystarczy pobieżna analiza przedstawionych algorytmów, aby stwierdzić, że o ile aktualizowanie zbioru reguł po uwzględnieniu każdego pojedynczego przykładu trenującego raczej nie wchodzi w rachubę, o tyle można z powodzeniem dokonywać takich aktualizacji na podstawie większych zbiorów przykładów.

Schemat sekwencyjnego pokrywania generuje reguły aż do uzyskania pokrycia przez nie całego zbioru trenującego. Jeśli później pojawiają się nowe przykłady trenujące, to część z nich może być pokrywana przez wcześniej wygenerowane reguły. Jeśli są one przy tym poprawnie przez te reguły klasyfikowane, to nie wymagają żadnej modyfikacji zbioru reguł. Z kolei dla tych nowych przykładów, które nie są pokrywane przez istniejące reguły, można w zwykły sposób wygenerować jedną lub więcej nowych reguł, które je pokryją. Jeśli stosowany jest w tym celu algorytm generujący uporządkowane reguły, to nie jest do tego potrzebne pamiętanie ,,starych'' przykładów, gdyż przy generowaniu każdej kolejnej reguły uwzględnia się tylko przykłady wcześniej nie pokryte. Jest to istotny praktycznie argument na rzecz stosowania takich algorytmów, jeśli zachodzi potrzeba okresowego aktualizowania zbiorów reguł na podstawie nowych przykładów. W przypadku algorytmów generujących nieuporządkowane zbiory reguł wcześniejsze przykłady trenujące trzeba przechowywać, gdyż kompleksy muszą mieć dużą dokładność na zbiorze wszystkich przykładów trenujących dotychczas przedstawionych systemowi uczącemu się.

Do rozwiązania pozostaje problem tych nowych przykładów, które przez istniejące reguły nie są klasyfikowane poprawnie. Jeśli jest ich stosunkowo niewiele, to można je po prostu pominąć, godząc się z faktem, że zbiór reguł nie będzie spójny z pojęciem docelowym na całym zbiorze trenującym, co skądinąd nie jest niczym złym. Jeśli jednak nowe przykłady oznaczają znaczne zwiększenie błędu próbki dla niektórych reguł, to niezbędna jest jakaś interwencja. Prosta strategia postępowania może polegać na usunięciu tych reguł i dla wszystkich przykładów, które w wyniku tego pozostaną nie pokryte, wygenerowaniu odpowiednich reguł na nowo. W tym celu niezbędne jest przechowywanie ,,starych'' przykładów trenujących, gdyż po usunięciu niektórych reguł część z nich również przestanie być pokrywana i należy je uwzględnić przy tworzeniu nowych reguł.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdziały 4.1, 4.2, 4.3, 4.4, 4.5, 4.7.)
2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdziały 3.3, 4.4.)
3. Clark, P. Niblett, T. The CN2 induction algorithm. Machine Learning, 3:261-283, 1989.

About this document ...

Metody odkrywania wiedzy: wykład 5
Indukcja reguł

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w5.tex

The translation was initiated by Pawel Cichosz on 2004-02-12