Wrocław 15.06.2004
Daniel Kanafa 110523

Algorytmu grupowania oparte o koncepcję sekwencyjnego pokrywania
W wielu systemach uczących się hipotezy reprezentowane są za pomocą reguł. Podobnie jak drzewa decyzyjne (które zresztą mogą być przekształcone do zbioru reguł), reprezentacja taka dopuszcza pojęcia wielokrotne, dla pewnego zbioru kategorii . Zazwyczaj dla każdej kategorii  mamy regułę postaci: 
IF pokrycie THEN , 
gdzie pokrycie reprezentuje warunki, jakie muszą spełniać wartości atrybutów przykładu , aby był on pokrywany przez tę regułę. (Dla pojedynczych pojęć można poprzestać na tylko jednej regule dla przykładów pozytywnych.) W celu wyznaczenia , gdzie  jest reprezentowana za pomocą zbioru reguł tej postaci, znajduje się regułę pokrywającą  i zwraca jej kategorię. Jeśli jest takich reguł wiele, to bądź wybiera się pierwszą z nich (zakładając hierarchiczne uporządkowanie zbioru reguł w ciąg IF-THEN-ELSE-IF) bądź odpowiednio (np. probabilistycznie) łączy się kategorie wskazywane przez te reguły. Szczegóły zależą od konkretnego systemu. 
Selektory i kompleksy 
Najczęściej pokrycia reguł mają postać alternatyw kompleksów, które są koniunkcjami selektorów. W najprostszym przypadku selektory mają postać taką, jak wprowadzona na wykładzie 3 przy omawianiu przestrzeni wersji. Obecnie oprócz wprowadzonych tam trzech rodzajów selektorów (postaci , , , które będziemy nazywać odpowiednio selektorem pojedynczym, uniwersalnym i pustym) dopuścimy jeszcze stosowany często czwarty rodzaj tzw. selektorów dysjunkcyjnych:   (czyli atrybut może mieć dowolną z wymienionych wartości). Zauważmy, że jedną regułę, której pokrycie jest alternatywą kompleksów, możemy zastąpić zbiorem reguł, pokrycie każdej z których jest pojedynczym kompleksem. Tak właśnie postąpimy przy prezentacji algorytmów. 
Tak jak poprzednio, kompleksy zapisywać będziemy jako ujęte w nawiasy trójkątne wektory selektorów dla wszystkich atrybutów (interpretowane jako ich koniunkcja), zakładając że selektor na pozycji  odpowiada atrybutowi  i pomijając nazwy atrybutów. Odbiega to nieco od konwencji przyjmowanych w większości prac opisujących algorytmy uczenia się reguł, w których wymienia się tylko selektory różne od  wraz z nazwami atrybutów, których dotyczą, a jeśli takich nie ma, nazywa się kompleks pustym. Jednak notacja przyjęta przez nas jest co najmniej równie dobra. 
Definicja 1  Każdy kompleks zawierający selektor pusty  utożsamiany jest z kompleksem  , i nazywany kompleksem sprzecznym lub pustym.
Definicja 2  Kompleks zawierający wyłącznie selektory uniwersalne  nazywany jest kompleksem uniwersalnym.
Definicja 3  Każdy kompleks zawierający dokładnie jeden selektor różny od  i  (tj. pojedynczy lub dysjunkcyjny) oraz wszystkie pozostałe selektory uniwersalne  nazywać będziemy kompleksem atomowym.
Kompleksy atomowe są w gruncie rzeczy zwykłymi pojedynczymi lub dysjunkcyjnymi selektorami (różnymi od  i od ) i tak się na ogół je nazywa. Wprowadzenie dodatkowego terminu racej nie spotykanego w literaturze jest usprawiedliwione troską o precyzję i spójność nazewnictwa. 
Wprowadzone wcześniej relacje większej/mniejszej ogólności/szczegółowości dla hipotez będziemy stosować dla selektorów i kompleksów definiując je w naturalny sposób w terminach zbiorów przykładów pokrywanych przez te selektory czy kompleksy. 
Przecięcia zbiorów kompleksów 
W celu ułatwienia prezentacji algorytmów indukcji reguł wygodnie jest wprowadzić operację przecięcia zbiorów kompleksów. 
Definicja 4  Przecięciem zbiorów kompleksów  i  jest zbiór wszystkich koniunkcji dwóch kompleksów odpowiednio z tych dwóch zbiorów:  
 
Definicja 5  Koniunkcją kompleksów  i   jest kompleks, którego każdy selektor jest koniunkcją pary odpowiednich selektorów z tych kompleksów. Jeśli   i  , to  
 
Definicja 6  Koniunkcją selektorów  i  dla atrybutu  jest selektor zdefiniowany następująco: 
1.jeśli , to  , w przeciwnym przypadku 
2.jeśli , to  , w przeciwnym przypadku 
3.jeśli   lub  , to  , w przeciwnym przypadku 
4.jeśli  i  mają postać alternatywy pewnej liczby wartości atrybutu  (w szczególności także pojedynczej wartości) to   jest alternatywą tych i tylko tych wartości tego atrybutu (w szczególności być może pojedynczą wartością), które występują jednocześnie w  i , albo   jeśli selektory te nie zawierają wspólnych wartości. 
Sekwencyjne pokrywanie
Algorytmy indukcji reguł przeszukują przestrzeń hipotez w poszukiwaniu takich reguł dla każdej kategorii, które pokrywają możliwie wiele przykładów należących do tej kategorii (w przypadku dokładnych reguł wszystkie) i możliwie mało przykładów należących do innych kategorii (w przypadku dokładnych reguł żadnego). Algorytmy te są na ogół realizacjami ogólnego schematu sekwencyjnego pokrywania, przedstawionego w maksymalnie uproszczonej postaci w tablicy  dla zbioru trenuj±cego . 

Ogólny schemat algorytmu sekwencyjnego pokrywania.
	
	Powtarzaj jak długo w  są przykłady nie pokryte przez pokrycie żadnej reguły 
1.znajdź kompleks , który pokrywa pewną liczbę przykładów z  z dużą dokładnością; 
2.dodaj do zbioru reguł regułę 
IF  THEN , 
gdzie  jest większościową kategorią w zbiorze przykładów pokrywanych przez kompleks . 		

Różnice pomiędzy poszczególnymi realizacjami schematu sekwencyjnego pokrywania polegają przede wszystkim na sposobie znajdowania kompleksu dodawanego do pokrycia reguły i kryteriach, które musi on spełniać. Przedstawimy dwa algorytmy indukcji reguł oparte na tym schemacie: AQ Michalskiego i innych (wykorzystywany w serii systemów AQ, ostatnio chyba AQ18?) i CN2 Clarka i Nibletta. Ściśle rzecz biorąc, nie będzie to dokładna prezentacja oryginalnych algorytmów, lecz raczej pewna rekonstrukcja, pomijająca niektóre szczegóły i drobne różnice w stosunku do ogólnego algorytmu skwencyjnego pokrywania, zaś uwypuklająca to, czym te dwa pokrewne algorytmy się różnią od siebie w sposób istotny. 

Algorytm AQ 
Algorytm AQ dość wiernie realizuje schemat z tablicy , z t± jednak ró¿nic±, ¿e zawsze generuje on kompleksy w pe³ni dok³adne: wszystkie przyk³ady pokrywane przez generowany kompleks maj± tê sam± kategoriê. W oryginalnym algorytmie, który uczy siê jednej regu³y dla ka¿dej kategorii, taki kompleks jest nastêpnie dodawany do pokrycia regu³y dla tej kategorii. My jednak przyjmujemy, ¿e mo¿e byæ wiele regu³ dla tej samej kategorii, pokrycie ka¿dej z których zawiera dok³adnie jeden kompleks. Jest to podej¶cie równowa¿ne, przyjête po to, aby umo¿liwiæ jednolit± prezentacj± algorytmów AQ i CN2. 

Znajdowanie kompleksów 
Sposób znajdowania kompleksów przez AQ przedstawia algorytm w tablicy . 

Generowanie kompleksu w algorytmie AQ.
	
	1.wybierz ziarno  jako pewien przykład ze zbioru  nie pokryty przez żadną regułę; 
2.wygeneruj gwiazdę  jako zbiór  najlepszych maksymalnie ogólnych kompleksów pokrywających  i nie pokrywających żadnego przykładu , dla którego  ; 
1.zainicjalizuj gwiazdę jako zbiór zawierający maksymalnie ogólny kompleks: 
; 
2.powtarzaj jak długo  pokrywa jakiś przykład  dla którego   
1.wybierz przykład  pokrywany przez , dla którego  ; 
2.wygeneruj częściową gwiazdę  jako zbiór wszystkich maksymalnie ogólnych kompleksów atomowych, które pokrywają , ale nie pokrywają ; 
3.; 
4.usuń z  każdy kompleks bardziej szczegółowy niż jakiś inny kompleks z ; 
5.pozostaw w  co najwyżej  najlepszych kompleksów według heurystyki oceniającej; 
3.zwróć najlepszy kompleks z  według heurystyki oceniającej. 		

Algorytm AQ stosuje tzw. przeszukiwanie wiązkowe (beam search) w kierunku od ogólnych do szczegółowych kompleksów. Szerokość wiązki  jest parametrem algorytmu (na ogół kilka-kilkanaście). 
Heurystyki 
Algorytm jest również parametryzowany przez funkcje heurystyczne służące do oceny jakości kompleksów przy przycinaniu gwiazdy do  najlepszych oraz przy wyborze najlepszego z gwiazdy. W najprostszym przypadku jest to ta sama w obu przypadkach funkcja obliczana jako liczba pokrywanych przykładów o tej samej kategorii co kategoria ziarna lub suma liczby pokrywanych przykładów o tej samej kategorii co kategoria ziarna i liczby nie pokrywanych (wykluczanych) przykładów o innej kategorii niż kategoria ziarna. Często również uwzględnia się preferencje dla prostszych kompleksów (np. zawierających mniej wartości atrybutów, czyli więcej maksymalnie ogólnych selektorów ). Jest tu wiele możliwych podejść. 
Przykład: pogoda. 
Działanie algorytmu AQ dla zbioru trenującego dotyczącego klasyfikacji pogody. Będziemy szukać wyłącznie reguł dla kategorii yes (dla przykładów pozytywnych), przyjmując maksymalny rozmiar gwiazdy  oraz heurystykę oceniającą kompleksy zgodnie z liczbą pokrywanych przez nie przykładów pozytywnych. (W przypadku kompleksów o równych wartościach heurystyki oceniającej preferowany będzie pierwszy kompleks na liście.) Dla wygody skracamy nazwy wartości atrybutów w selektorach do pierwszej litery. Nie pokrywane przykłady pozytywne i negatywne wybierane są w kolejności numerów. Poniżej podajemy kolejne ziarna i generowane dla nich gwiazdy, uwzględniając wszystkie etapy ich tworzenia. 
1. (  ); 
1.; 
2. (  ); 
•; 
•; 
3. (  ); 
•; 
•; 
•; 
4. (  ); 
•; 
•; 
•; 
5.reguła: IF   THEN ; 
2. (  ); 
1.; 
2.; (  ); 
•; 
•; 
3. (  ); 
•; 
•; 
4. (  ); 
•; 
•; 
•; 
5.reguła: IF   THEN . 
Problemy z algorytmem AQ 
Uwzględnianie tylko całkowicie dokładnych reguł pociąga za sobą brak mechanizmów pozwalających na uniknięcie nadmiernego dopasowania do danych zaszumionych (ale możliwy preprocessing zbioru trenującego lub postprocessing zbioru reguł). 
Algorytm CN2
W przeciwieństwie do algorytmu AQ, algorytm CN2 generuje kompleksy, które nie muszą być w pełni dokładne. Przy generowaniu każdego kompleksu ignorowane są przykłady trenujące, które zostały pokryte przez kompleksy wygenerowane wcześniej (por. opis heurystyki oceniającej poniżej). Oznacza to, że każdy kolejny kompleks powinien być później stosowany do klasyfikowania tylko przykładów, które nie są pokrywane przez żaden wcześniej wygenerowany kompleks. W związku z tym zbiór reguł tworzonych przez CN2 jest uporządkowany i ma postać tzw. listy decyzyjnej (IF-THEN-ELSE-IF). 

Znajdowanie kompleksów 
Sposób znajdowania kompleksów przez CN2 przedstawia algorytm w tablicy . Symbol    oznacza zbiór wszystkich mo¿liwych kompleksów atomowych. 

Generowanie kompleksu w algorytmie CN2.
	
	1.zainicjalizuj gwiazdę jako zbiór zawierający maksymalnie ogólny kompleks: 
; 
2.; 
3.powtarzaj jak długo   
1.; 
2.usuń z  każdy kompleks, który jest także w  lub jest sprzeczny; 
3.dla każdego kompleksu  wykonaj 
jeśli  jest statystycznie znaczący i lepszy niż  według heurystyki oceniającej to ; 
4.pozostaw w  co najwyżej  najlepszych kompleksów według heurystyki oceniającej; 
5.; 
4.zwróć kompleks . 		

Podobnie jak AQ, także CN2 przeszukuje wiązkowo przestrzeń kompleksów w kierunku od ogólnych do szczegółowych, utrzymując wiązkę o rozmiarze  i przechowując najlepszy dotychczas znaleziony kompleks. 
Heurystyki 
W przypadku algorytmu CN2 funkcje heurystyczne stosowane do oceny jakości kompleksów mają decydujące znaczenie, ponieważ w przeciwieństwie do AQ sam algorytm przeszukiwania nie zapewnia, że znaleziony będzie dokładny kompleks. Kompleks jest uznawany za dobry, jeśli pokrywane przez niego przykłady mają możliwie mało zróżnicowane kategorie. Warto zauważyć, że małe zróżnicowanie kategorii jest tym samym celem, do którego zmierza wybór testu w algorytmie ID3. Nie jest więc zaskoczeniem, że CN2 preferuje kompleksy, dla których zbior pokrywanych przykładów ma najniższą entropię obliczaną dla kompleksu  jako:  
 
gdzie  jest zbiorem przykładów pokrywanych przez kompleks  i nie pokrytych wcześniej przez już istniejące reguły, a  . 
Algorytm stosuje również test sprawdzający, czy oceniane kompleksy są statystyczne znaczące, aby uniknąć nadmiernego dopasowania do przypadkowych danych. Ocenia się to według kryterium  , gdzie  
 
 jest zbiorem przykładów pokrywanych przez kompleks , ale nie pokrytych przez wygenerowane wcześniej reguły,  jest zbiorem wszystkich przykładów nie pokrytych przez wygenerowane wcześniej reguły, a  jest wartością progową. Wartości    reprezentują oczekiwany rozkład częstości pomiędzy poszczególne kategorie uzyskany dla  przykładów wybranych losowo według tego samego rozkładu prawdopodobieństwa, według którego ukształtowany jest cały zbiór  przykładów trenujących nie pokrytych przez dotychczas wygenerowane reguły. Oblicza się je w oczywisty sposób:  
 
Wartość  stanowi miarę odległości między rozkładem    a rozkładem pomiędzy kategorie faktycznie występującym w zbiorze  (dlaczego?), która powinna być dostatecznie duża, aby kompleks  uznać za statystycznie znaczący. Ma ona w przybliżeniu rozkład  o  stopniach swobody. Dla danej liczby stopni swobody i pożądanego poziomu istotności, na ogół z przedziału  , odpowiednią wartość progową  można obliczyć numerycznie lub znaleźć w tablicach statystycznych. 
Problemy z algorytmem CN2 
Podczas specjalizacji kompleksów w gwieździe wykorzystywany jest zbiór wszystkich możliwych kompleksów atomowych   , który może być bardzo duży (jeśli atrybuty mają kilka lub kilkanaście wartości i dopuszczamy selektory dysjunkcyjne).