Laboratorium Matematyka Dyskretna

Zastosowanie relacji równoważności i podziału zbioru - Zbiory przybliżone, algorytmy decyzyjne

1. Część pierwsza programy Rosetta i RSES

Charakterystyka algorytmów wyznaczania reduktów relatywnych:

W każdym z omawianych poniżej algorytmów istnieje możliwość wyznaczenia reduktów relatywnych (i następnie z tych reduktów reguł decyzyjnych) lub od razu reguł decyzyjnych.

• Algorytm - Exhaustive Calculation - wyznacza wszystkie redukty relatywne zgodnie z teorią podaną na wykładzie - Algorytm o tej nazwie występuje zarówno w programie Rosetta jak również w programie RSES

• Algorytm - Johnson reducer - program Rosetta.

Algorytm wyznacza jeden redukt z każdego obiektu (możliwie najkrótszy) lub jeden

redukt dla tablicy decyzyjnej.

Załóżmy że wybrano opcje obliczania reduktu dla każdego obiektu, wiadomo, że funkcja odróżnialności modulo d dla tego obiektu zawiera informację na podstawie, której można wyznaczyć wszystkie redukty relatywne dla obiektu. Wiadomo także, że funkcja ta jest w koniunkcyjnej postaci normalnej. Algorytm działa tak, że atrybut występujący najczęściej w każdej alternatywie wchodzącej w skład funkcji odróżnialności modulo d dla każdego obiektu, wybierany jest jako pierwszy atrybut tworzący redukt. Następnie usuwane są wszystkie alternatywy w których ten atrybut występuje. Potem, dla pozostałych alternatyw powtarza się cały proces dodając kolejny najczęściej występujący atrybut, itd. Proces kończy się z chwilą kiedy usunięto już wszystkie alternatywy (nic nie zostało).

• Algorytm - LEM2 - program RSES.

Algorytm LEM2 zaproponowany przez Jerzego Grzymałę-Busse, jest tzw. algorytmem pokryciowym i generuje tzw. minimalny zbiór reguł. Zbiór reguł uznajemy za minimalny jeśli po usunięciu dowolnej reguły z opisu dowolnej klasy decyzyjnej, w klasie tej znajdą się obiekty nie pokrywane przez żadną z reguł pozostałych w opisie. Algorytm jest uruchamiany iteracyjnie dla kolejnych klas decyzyjnych (lub ich przybliżeń - górnego lub dolnego). Regułę buduje się dodając kolejno do części warunkowej (początkowo jest ona pusta) nowe deskryptory. O kolejności dodania deskryptora decyduje siła odróżnialności tego warunku. Tzn. lepszy jest ten warunek (deskryptor - składnik koniunkcji) który powoduje odróżnienie jak największej liczby obiektów z klasy decyzyjnej znajdującej się w konkluzji reguły od obiektów z innych klas decyzyjnych. Deskryptory dodaje się tak długo aż reguła stosuje się regułą dokładną (lub tak dokładną jak to możliwe w danej klasie decyzyjnej - jeśli jest ona sprzeczna). Po wyznaczeniu reguły, wszystkie obiekty które ją wspierają sa usuwane, a algorytm rozpoczyna indukcję kolejnej reguły, której zadaniem będzie pokrycie tych obiektów z opisywanej klasy decyzyjnych, które sa jeszcze nie pokryte. Dokładny opis algorytmu znajduje się m.in. w książce Uczenie maszynowe i sieci neuronowe J. Krawiec, J. Stefanowski, Wydawnictwo Politechniki Poznańskiej 2003 (do kupienia w Sieci).

Wszystkie z przedstawionych algorytmów wymagają uprzedniej dyskretyzacji atrybutów ciągłych. W przypadku programu RSES mamy do dyspozycji dyskretyzację globalną i lokalną, a w przypadku programu Rosetta wykorzystujemy na laboratorium albo algorytm Boolean reasoning algorithm albo Entropy/MDL algorithm. Idea algorytmów zostanie omówiona w czasie wprowadzenia do laboratorium (do materiałów dołączono też informacje o dyskretyzacji znajdujące się w wykładach prowadzonych przez dr Pawła Cichosza z Politechniki Warszawskiej)

Skracanie reguł decyzyjnych

Skracanie reguł decyzyjnych polega na usuwaniu z części warunkowej reguły pewnej liczby deskryptorów. Po usunięciu deskryptora reguła staje się coraz mniej dokładna, parametrem algorytmu jest minimalna dokładność jaką może posiadać reguła po skróceniu. Algorytm skracania wykorzystuje metodę wspinaczki, w każdym kroku usuwany jest deskryptor, który powoduje najmniejszą utratę dokładności reguły. Po każdym usunięciu deskryptora sprawdzana jest reguła stopu, jeśli reguła jest mniej dokładna od założonej wartości progowej to ostatnio usunięty deskryptor jest od niej powrotem dodawany, a sam proces skracania kończy się.

UWAGA:

Bardziej szczegółowe informacje mogą Państwo znaleźć w materiałach pomocniczych:

• Moje wykłady dotyczące zbiorów przybliżonych

• Rosetta Manual (rozdział 4.7 dotyczy sposobów wyznaczania reduktów).

• RSES Manual

Zadania do wykonania

UWAGA - realizacji tych zdań nie opisujemy w sprawozdaniu

1. Zapoznać się z głównymi funkcjami programów Rosetta i RSES

1. wczytywanie danych

2. wykonywanie testów w trybie kroswalidacji

3. dyskretyzacja danych

4. wyznaczanie reduktów relatywnych (wszystkich, najkrótszego)

5. wyznaczanie reguł (wszystkich, najkrótszej, za pomocą algorytmu LEM2)

6. skracanie reguł

7. klasyfikacja obiektów

2. Zapoznać się ze sposobem prezentowania informacji o: reduktach i regułach (support, accuracy) oraz wynikach klasyfikacji (ogólna dokładność klasyfikacji, macierz pomyłek, procent obiektów nierozpoznawalnych przez reguły).

2. Część druga analiza przykładowych zbiorów danych

Pochodzenie i opis zbiorów danych

Zbiory danych Monks - W roku 1991 na terenie Belgii odbyło się spotkanie w ramach międzynarodowej letniej szkoły uczenia się maszyn. Tam też, w toku dyskusji na temat jakości i efektywności algorytmów uczenia się maszyn, sformułowane zostały trzy zadania tworzenia opisu pojęcia M, znane jako trzy problemy mnicha. Kolejne zbiory opisują coraz bardziej złożone problemy uczenia się docelowego pojęcia. W szczególność w trzecim problemie mnicha wprowadzono 5% przykładów zakłócających (błędnie przyporządkowanych do klas decyzyjnych). Reszta szczegółów w katalogu ze zbiorami.

Zbiory danych treningowych i testowych są już przygotowane.

Poniżej podano dokładny opis zbioru oraz opisy docelowe tzn. takie, które pozwalają na osiągnięcie 100% dokładności. Oczywiście metodologia zbiorów przybliżonych, ze względu na język reprezentacji wiedzy (reguły decyzyjne) nie pozwala na uzyskanie takich opisów.

Informacje na temat zbiorów danych Mnich

Number of Instances: 432

Number of Attributes: 7

Wszystkie atrybuty są symboliczne (to nie są liczby tylko symbole)

Attribute information (liczba różnych watości atrybutów):

a1 1, 2, 3

a2 1, 2, 3

a3: 1, 2

a4: 1, 2, 3

a5: 1, 2, 3, 4

a6: 1, 2

class: 0, 1

Missing Attribute Values: None

Target Concepts associated to the MONK's problem:

MONK-1: (a1 = a2) or (a5 = 1)

MONK-2: EXACTLY TWO of {a1 = 1, a2 = 1, a3 = 1, a4 = 1, a5 = 1, a6 = 1}

MONK-3: (a5 = 3 and a4 = 1) or (a5 /= 4 and a2 /= 3)

(5% class noise added to the training set)

Jedne z najlepszych wyników to: Monks-1 - 100%, Monks-2 - trudny problem - powyżej 80%, Monks-3 - powyżej 95%. W zbiorach Monks są zawsze dwie klasy decyzyjne.

Zbiór danych Iris - również zbiór danych benchmarkowych (chyba najpopularniejszy na świecie) opisujący problem klasyfikacji kwiatów irysa. Cztery atrybuty warunkowe (ciągłe, a więc dyskretyzacja), trzy klasy decyzyjne.. Atrybuty warunkowe opisuja kwiaty Irysa, a klasą decyzyjną jest jeden z trzech rodzajów tego kwiatu. W zbiorze są trzy klasy decyzyjne.

Najlepsze z opisanych wyników to od 96%-100% dokładności klasyfikacji.

Zbiór danych Australian Credit - to również zbiór benchmarkowy. Dane te pochodzą z projektu Statlog, którego zadaniem było porównanie efektywności działania różnych algorytmów klasyfikujących. Projekt finansowany był przez Unię Europejską, a realizowano go w latach 1990-1993.

Informacje zawarte w danych Australian Credit dotyczą reguł, według których bank przyznaje klientom kartę kredytową. Znaczenie poszczególnych atrybutów zostało jednak przez bank utajnione. Utajnione zostały również znaczenia wartości atrybutów.

W tablicy decyzyjnej zawartych jest 690 obiektów, wyróżniono 13 atrybutów warunkowych oraz dwie klasy decyzyjne. Interesującą cechą tego zbioru danych jest to, iż część atrybutów jest typu rzeczywistego, a część symbolicznego. W zbiorze są dwie klasy decyzyjne. Dobre wyniki klasyfikacji zaczynają się od 84%.

Zbiór danych SatImage - analizowano również w ramach projektu Statlog. Celem analizy jest rozpoznawanie zdjęć satelitarnych różnych typów obszarów Australii. Dane pochodzą z NASA. W analizie danych chodzi o to, aby na podstawie 4 zdjęć obszaru Australii o wielkości około 320m (dwa zdjęcia w świetle widzialnym dwa w podczerwieni), sklasyfikować badany obszar do jednej z sześciu klas. Cztery zdjęcia opisane są w sumie za pomocą 36 atrybutów numerycznych. Zbiór danych jest duży ponad 4000 obiektów treningowych i 2000 obiektów testowych.

Zbiór danych SeismicTremors - W polskich kopalniach węgla kamiennego zagrożenie sejsmiczne monitorowane jest za pomocą aparatury sejsmologicznej i sejsmoakustycznej znajdującej się w podziemiach kopalni, dane transmitowane są do systemu Hestia, gdzie są one agregowane i analizowane za pomocą tzw. eksperckich metod oceny zagrożenia. Metody te, pomimo nieustannych badań, charakteryzują się jednak dużą niedokładnością. Wykorzystując informacje zawarte w bazie danych systemu Hestia utworzono zbiór danych SeismicTremors, w którym zawarto m.in. informacje o zagregowanych (zarejestrowanych w czasie kolejnych zmian) wartościach: energii sejsmoakustycznej wydzielonej w wyrobisku, energii sejsmicznej, liczbie wstrząsów w poszczególnych klasach energetycznych (od 1*10²J do 1*10⁷J), ocenie zagrożenia generowanej przez klasyczne metody oceniające. W analizowanym zbiorze danych uwzględniano również informację o tym czy analizowana zmiana była zmianą wydobywczą czy nie. Zebrano dane z zagrożonej ściany SC508 w KWK Wesoła. Zbiór danych liczy 864 obiekty, dane podzielono na dwie klasy decyzyjne odzwierciedlające sumaryczną energię sejsmiczną jaka wydzieli się w wyrobisku w czasie następnej zmiany. Wartością graniczną dla klas decyzyjnych była energia 1*10⁵J. Dane są mocno niezbalansowane, gdyż liczebność klasy E>1*10⁵J wynosiła jedynie 97 obiektów. Przewidywanie klasy decyzyjnej 1 oznacza, że w ciągu najbliższej zmiany w monitorowanym rejonie istnieje ryzyko wystąpienia zagrożenia sejsmicznego (np. wstrząsu wysokoenergetycznego). Dobre wyniki - dokładność klasy 0 (brak zagrożenia) 75%, dokładność klasy 1 (zagrożenie) 70%. W przypadku tego zbioru bardziej niż ogólna dokładność klasyfikacji liczy się równoczesna jak największa dokładność klasyfikacji obu klas decyzyjnych.

Zadania do wykonania

1. Zbiory danych Monks

UWAGA: Dane nie wymagają dyskretyzacji. Zbiory danych treningowy i testowy są już ustalone - nie stosować metody kroswalidacji.

UWAGA: Obiekt nierozpoznawalne przez klasyfikator liczymy jako sklasyfikowane błędnie (RSES tego nie robi, proszę obliczyć to manualnie)

Dotyczy wszystkich zbiorów Monks

1. Porównać trzy algorytmy indukcji reguł. Kryterium porównania dokładność klasyfikacji na zbiorze treningowym i testowym

2. Wyznaczyć redukty relatywne, dokonać redukcji atrybutów (jeśli to możliwe), a następnie na ograniczonych zbiorach atrybutów porównać trzy algorytmy indukcji reguł.

3. Sprawdzić czy (i dla którego zbioru danych) skracanie reguł pozwala na poprawę osiąganych wyników

4. Sprawdzić, która metoda pozwala na wyznaczanie najmniejszej liczby reguł

5. Sprawdzić, która metod pozwala na osiągnięcie największej dokładności klasyfikacji

2. Zbiór danych Iris

UWAGA: Dane wymagają dyskretyzacji. Jeśli wyraźnie nie napisano, że należy postępować inaczej, eksperymenty należy przeprowadzić za pomocą dziesięciokrotnej kroswalidacji. Dla programu RSES stosować globalną metodę dyskretyzacji, dla programu Rosetta metodę Entropy/MDL

1. Porównać trzy algorytmy indukcji reguł. Kryterium porównania dokładność klasyfikacji na zbiorze treningowym i testowym

2. Wyznaczyć redukty relatywne, dokonać redukcji atrybutów (jeśli to możliwe), a następnie na ograniczonych zbiorach atrybutów porównać trzy algorytmy indukcji reguł.

3. Sprawdzić czy (i dla którego zbioru danych) skracanie reguł pozwala na poprawę osiąganych wyników

4. Sprawdzić, która metoda pozwala na wyznaczanie najmniejszej liczby reguł

5. Sprawdzić, która metod pozwala na osiągnięcie największej dokładności klasyfikacji

6. Podać która metoda pozwala na całym zbiorze danych (bez kroswalidacji) uzyskać największą dokładność klasyfikacji. Ile wtedy uzyskujemy reguł i czy niosą one z sobą jakąś wiedzę?

3. Zbiór danych Australian Credit

UWAGA: Dane wymagają dyskretyzacji. Jeśli wyraźnie nie napisano, że należy postępować inaczej, eksperymenty należy przeprowadzić za pomocą dziesięciokrotnej kroswalidacji. Dla programu RSES stosować globalną metodę dyskretyzacji, dla programu Rosetta metodę Entropy/MDL

1. Porównać trzy algorytmy indukcji reguł. Kryterium porównania dokładność klasyfikacji na zbiorze treningowym i testowym

2. Wyznaczyć redukty relatywne, dokonać redukcji atrybutów (jeśli to możliwe), a następnie na ograniczonych zbiorach atrybutów porównać trzy algorytmy indukcji reguł.

3. Sprawdzić czy (i dla którego zbioru danych) skracanie reguł pozwala na poprawę osiąganych wyników

4. Sprawdzić, która metoda pozwala na wyznaczanie najmniejszej liczby reguł

5. Sprawdzić, która metod pozwala na osiągnięcie największej dokładności klasyfikacji

6. Podać która metoda pozwala na całym zbiorze danych (bez kroswalidacji) uzyskać największą dokładność klasyfikacji. Ile wtedy uzyskujemy reguł i czy niosą one z sobą jakąś wiedzę?

4. Zbiór danych SatImage

UWAGA: Dane wymagają dyskretyzacji. Zbiory treningowy i testowy są ustalone - nie stosować kroswalidacji. Dla programu RSES stosować globalną lub lokalną metodę dyskretyzacji, dla programu Rosetta metodę Entropy/MDL

1. Porównać trzy algorytmy indukcji reguł. Kryterium porównania dokładność klasyfikacji na zbiorze treningowym i testowym

2. Wyznaczyć redukty relatywne, dokonać redukcji atrybutów (jeśli to możliwe), a następnie na ograniczonych zbiorach atrybutów porównać trzy algorytmy indukcji reguł.

3. Sprawdzić czy (i dla którego zbioru danych) skracanie reguł pozwala na poprawę osiąganych wyników

4. Sprawdzić, która metoda pozwala na wyznaczanie najmniejszej liczby reguł

5. Sprawdzić, która metod pozwala na osiągnięcie największej dokładności klasyfikacji

6. Podać która metoda pozwala na zbiorze danych treningowych uzyskać największą dokładność klasyfikacji. Ile wtedy uzyskujemy reguł?

5. Zbiór danych SeismicTremors

UWAGA: Dane wymagają dyskretyzacji. Zbiory treningowy i testowy nie są ustalone (stosować kroswalidacji ALE 5-krotną). Dla programu RSES stosować globalną lub lokalną metodę dyskretyzacji, dla programu Rosetta metodę Entropy/MDL

1. Porównać trzy algorytmy indukcji reguł. Kryterium porównania dokładność klasyfikacji na zbiorze treningowym i testowym

2. Wyznaczyć redukty relatywne, dokonać redukcji atrybutów (jeśli to możliwe), a następnie na ograniczonych zbiorach atrybutów porównać trzy algorytmy indukcji reguł.

3. Sprawdzić czy (i dla którego zbioru danych) skracanie reguł pozwala na poprawę osiąganych wyników

4. Sprawdzić, która metoda pozwala na wyznaczanie najmniejszej liczby reguł

5. Sprawdzić, która metod pozwala na osiągnięcie największej dokładności klasyfikacji

UWAGA: Nie możemy zwiększać ogólnej dokładności klasyfikacji kosztem dokładności klasy 1 (stan zagrożony).

6. Podać która metoda pozwala na całym zbiorze danych uzyskać największą dokładność klasyfikacji. Ile wtedy uzyskujemy reguł i czy można „wyciągnąć” z nich jakąś użyteczną informację?

6. Wnioski ogólne. Na podstawie przeprowadzonej analizy proszę opisać jaka zdaniem Państwa powinna być ścieżka analizy danych za pomocą metod udostępnianych przez teorię zbiorów przybliżonych. Które metody i algorytmy sprawdzają się najlepiej, a które najgorzej? Czy wyniki uzyskiwane przez poszczególne algorytmy zależą od czegoś? Jeśli tak to, od czego??

Sprawozdanie w wersji elektronicznej - wyniki mają być zebrane w tabelkach, każdy wyniki powinien być opatrzony dokładnym komentarzem jaka była droga uzyskania wyniku (dyskretyzacja, redukcja wiedzy, indukcja reguł, skracanie reguł). W tabelkach podajemy średnią dokładność klasyfikacji, dokładność każdej klasy decyzyjnej, liczbę reguł, % obiektów nierozpoznanych przez klasyfikator. W przypadku wyników bez kroswalidacji podajemy po prostu uzyskane wartości (nie średnie).

Na końcu sprawozdania wnioski ogólne. Mile widziane własne komentarze i uwagi pokazujące zaangażowanie sekcji w realizację zadania

Integralną częścią sprawozdania są pliki RSES i Rosetty z zapisanymi wynikami wszystkich eksperymentów. Wyniki najlepsze powinny mieć w tytule słowo „best”

---