Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 1998/99

Metody i Techniki Sztucznej Inteligencji

Laboratorium nr 4

INDUKCJA DRZEW DECYZYJNYCH

1. Cel ćwiczenia

Celem ćwiczenia jest nabycie umiejętności opisywania danej przestrzeni zainteresowania za pomocą drzew decyzyjnych.

2. Wprowadzenie

2.1 Opis teoretyczny

Jednym z przykładów pozyskiwania wiedzy w sposób indukcyjny jest generowanie reguł za pomocą drzew decyzyjnych. W metodzie tej stosuje się tzw. atrybutowy model opisu przestrzeni zainteresowania. W szczególności: aby móc w ten sposób przystąpić do reprezentowania wiedzy, należy najpierw określić n - wymiarową przestrzeń, gdzie „n” odpowiada liczbie uwzględnianych cech. Dla każdej cechy określamy - zwykle nieliczny - zbiór wartości o charakterze ilościowym lub jakościowym. Wartości cech dla pewnej grupy obiektów tworzą tzw. zestaw uczący, na podstawie którego zostanie zidentyfikowane drzewo decyzyjne.

Zestaw uczący dotyczy obiektów, które zostały odpowiednio zaklasyfikowane, tzn. każdemu obiektowi zastała przypisana znana klasa. Zakłada się, że klasyfikacja jest tu jednoznaczna i ostra. Jednoznaczność polega na tym, że dany obiekt może należeć tylko do jednej klasy. Natomiast ostrość polega na tym, że dany obiekt albo należy do danej klasy w pełni - albo wcale do niej nie należy. Wyklucza się też możliwość braku jakiejś wartości cechy dla obiektu występujący w zbiorze przykładów.

Elementami struktury drzewa decyzyjnego są:

• korzeń,

• gałęzie,

• węzły,

• liście.

Korzeń jest początkiem drzewa decyzyjnego. Zawiera on nazwę jednego z atrybutów. Z korzenia rozchodzą się gałęzie, które są opisane wartościami atrybutu wybranego na korzeń. Ich liczba zależna jest od liczby wartości danego atrybutu. Każda gałąź jest zakończona węzłem, w którym znajduje się nazwa kolejnego atrybutu. Od każdego węzła rozchodzą się gałęzie w sposób opisany wyżej. Zakończeniami każdego drzewa są liście, a więc liść jest również zakończeniem gałęzi. W liściu znajduje się nazwa klasy. Przykład struktury drzewa decyzyjnego przedstawiono na rys. 1.

W ramach zajęć laboratoryjnych do identyfikacji drzew decyzyjnych będzie stosowany program IDD [3]. Jest on jedną z możliwych implementacji metody indukcyjnych drzew decyzyjnych. Program ten służy do indukcji, jak i stosowania drzew decyzyjnych.

2.2 Obsługa programu

Obsługa programu składa się z następujących etapów:

1. Uruchomienie programu.

2. Wczytanie plików wsadowych.

3. Stosowanie programu.

4. Zakończenie pracy z programem.

IDD jest programem działającym w systemie DOS, co wymaga uruchamiania go w oknie DOS-owym systemu MS Windows NT 4.0 (system taki jest zainstalowany w Laboratorium Metod Numerycznych Katedry Podstaw Konstrukcji Maszyn).

2.2.1 Przygotowanie plików wejściowych

Pliki wejściowe są plikami tekstowymi. Dlatego też do ich tworzenia zaleca się stosowanie Notatnika systemu MS Windows. Konwencja nazywania plików jest następująca:

1. nazwa pliku zawierającego nazwy klas musi posiadać rozszerzenie „kls”,

2. nazwa pliku zawierającego nazwy atrybutów i ich wartości musi posiadać rozszerzenie „atr”,

3. nazwa pliku zawierającego zestaw uczący musi posiadać rozszerzenie „zsu”.

Uwaga ogólna do tworzenia nazw wszystkich plików: nie należy stosować polskich liter w nazwach plików ani w ich zawartości.

a) Tworzenie pliku *.kls

W pliku tym należy umieścić wszystkie nazwy klas. Plik tworzymy wpisując kolejno - jedna pod drugą - nazwy klas. Na końcu pliku umieszczamy cyfrę 0.

Uwaga 1:

długość pojedynczej nazwy nie może przekraczać 50 znaków.

Uwaga 2:

jeśli stosujemy nazwy wielowyrazowe - to poszczególne wyrazy należy połączyć znakiem podkreślenia "_”.

Na rys. 2 przedstawiono widok przykładowego pliku utworzonego za pomocą Notatnika systemu MS Windows:

b) Tworzenie pliku *.atr

W pliku tym (rys. 3) należy umieścić wszystkie nazwy atrybutów i wszystkie nazwy ich wartości. Zawartość pliku musi posiadać następujący porządek:

1. liczba atrybutów,

2. nazwa atrybutu,

3. kolejne nazwy wartości atrybutu (w jednym wierszu dla danego atrybutu) zakończone cyfrą 0,

4. nazwa atrybutu,

5. kolejne nazwy wartości atrybutu (w jednym wierszu dla danego atrybutu) zakończone cyfrą 0,

6. itd.

Uwaga 1:

długość pojedynczej nazwy atrybutu nie może przekraczać 80 znaków.

Uwaga 2:

długość pojedynczej nazwy wartości atrybutu nie może przekraczać 50 znaków.

Uwaga 3:

jeśli stosujemy nazwy wielowyrazowe - to poszczególne wyrazy należy połączyć znakiem podkreślenia „_”.

Rys. 3 Przykład pliku zawierającego nazwy atrybutów i ich wartości

c) Tworzenie pliku *.zsu

W pliku tym należy umieścić zestaw uczący. Zawartość pliku musi posiadać następujący porządek:

1. liczba przykładów,

2. przykłady (każdy przykład zapisywany w jednym wierszu zakończonym cyfrą 0) składające się z nazw wartości cech oraz nazwy klasy.

Uwaga:

w zestawie uczącym nie mogą znaleźć się dwa lub więcej przykłady, które mają identyczne wartości atrybutów a należą do różnych klas.

Rys. 4 Przykład pliku zawierającego zestaw uczący

2.3 Wyniki otrzymane przez zastosowanie programu

Wynikiem zastosowania programu jest powstałe drzewo decyzyjne (rys. 5), którego struktura jest przechowywana w pamięci operacyjnej komputera. Użytkownik programu może przeglądać otrzymane drzewo, przemieszczając się po jego strukturze i odczytując otrzymane w ten sposób reguły. Przeglądanie to odbywa się w trybie tekstowym. Powstałe drzewo decyzyjne nie jest zapisywane w pliku ani też nie jest prezentowane na ekranie monitora w sposób graficzny.

2.4 Stosowanie programu

Po zbudowaniu drzewa decyzyjnego, na ekranie monitora wyświetlane są następujące informacje:

• numer i nazwa atrybutu,

• numery oraz nazwy wszystkich wartości tego atrybutu.

Oto przykład:

- po zbudowaniu drzewa decyzyjnego, na ekranie monitora pojawia się następujący tekst:

Atrybut nr (0) : >> wzajemne_polozenie_bokow <<

• wartosc nr (0) : „wszystkie_rowne”

• wartosc nr (1) : „parami_rownolegle”

• wartosc nr (2) : „parami_rowne”

Wybierz numer:

chcąc przemieścić się w głąb struktury drzewa, wybieramy np. wartość „1” („parami_rownolegle”). Na ekranie monitora widzimy tekst następujący:

Atrybut nr (1) : >> rodzaj_katow_miedzy_bokami <<

• wartosc nr (0) : „katy_proste”

• wartosc nr (1) : „katy_rozne_od_prostych”

Wybierz numer:

Wybierając wartości poszczególnych atrybutów, przemieszczamy się w głąb drzewa. Czynności te mogą zakończyć się dwojako:

1. po dotarciu do liścia (będącego lokalnym zakończeniem drzewa decyzyjnego), program informuje użytkownika tekstem wyświetlanym na monitorze:

Atrybut nr (1) : >> rodzaj_katow_miedzy_bokami <<

• wartosc nr (0) : „katy_proste”

• wartosc nr (1) : „katy_rozne_od_prostych”

Wybierz numer: 0

Obiekt należy do klasy : prostokat

Czy chcesz dokonać następnej klasyfikacji ? t/n

2. jeśli w wyniku wybranych wartości program nie jest w stanie dokonać poprawnej klasyfikacji, pojawia się następujący komunikat:

->> NIEZNANY OBIEKT <<-

i automatycznie nakazuje dokonać następnej klasyfikacji:

->> DOKONAJ NOWEJ KLASYFIKACJI <<-

3. Sposób przeprowadzenia ćwiczenia

Przed przystąpieniem do wykonania ćwiczenia należy zapoznać się z podstawowymi pojęciami dotyczącymi drzew decyzyjnych.

Na zajęciach laboratoryjnych każda sekcja otrzymuje zestaw zawierający:

1. nazwy atrybutów,

2. wartości, które atrybuty mogą przyjmować,

3. nazwy klas.

Na ich podstawie należy:

1. przygotować trzy pliki wsadowe:

• plik *.kls zawierający nazwy podanych klas,

• plik *.atr zawierający nazwy podanych atrybutów i ich wartości,

• plik *.zsu zawierający indywidualnie ułożony zestaw uczący.

2. uruchomić program IDD (plik drzewo.exe).

Zaliczenie ćwiczenia następuje bezpośrednio po jego przeprowadzeniu. Ocena uzyskana przez studenta jest uzależniona od jego przygotowania się do ćwiczenia a także sprawności jego przeprowadzenia.

4. Literatura

[1] CHOLEWA W. PEDRYCZ W. Systemy doradcze, Skrypt Politechniki Śląskiej nr 1447, Gliwice 1987.

[2] Moczulski W. Metody pozyskiwania wiedzy dla potrzeb diagnostyki maszyn, Mechanika z.130, Gliwice 1997.

[3] MULAWKA J. Systemy ekspertowe, Wydawnictwo N-T, Warszawa 1996.

[4] QUINLAN J.R. Induction of decusion trees, Machine learning 1986, 1, 81-106.

[5] WYLEŻOŁ M. Zastosowanie drzew decyzyjnych do identyfikacji wiedzy konstrukcyjnej. Praca dyplomowa, Gliwice 1996.

Opracował: mgr inż. Marek Wyleżoł

Gliwice, 03.03.1999.

1/7

Rys. 2 Przykład pliku zawierającego nazwy klas

Rys. 1 Graficzna prezentacja struktury drzewa decyzyjnego: a) nazwy poszczególnych elementów, b) przykład praktyczny

Rys. 5 Struktura drzewa decyzyjnego powstałego z danych wejściowych pokazanych na rys. 2-4

---