Katedra

Podstaw

Konstrukcji

Maszyn

Wydział

Mechaniczny

Technologiczny

Politechnika

Śląska

ul. Konarskiego 18a

44-100 Gliwice

tel. [phone]

fax. [phone]

http://kpkm.polsl.pl

Metody Sztucznej
Inteligencji

Rok akademicki 2010/11

Instrukcja do ćwiczeń laboratoryjnych

Laboratorium 5

Temat

Drzewa decyzyjne. Klasyfikacja

Opracował:
dr inż. Krzysztof Ciupke

Gliwice 2011-04-13

- 1/5 -

1. Cel laboratorium

Celem zajęć laboratoryjnych jest zapoznanie się z podstawowymi zagadnieniami dotyczącymi

zagadnień klasyfikacji z zastosowaniem drzew decyzyjnych oraz nabycie umiejętności wykorzy-

stywania ich do zadań klasyfikacji.

2. Wprowadzenie

Aby skutecznie dokonywać klasyfikacji konieczne jest dysponowanie klasyfikatorem, pozwala-

jącym na przyporządkowanie elementów rozpatrywanego zbioru tzw. przykładów uczących do

skończonej liczby klas. Jednym z klasyfikatorów mogą być drzewa decyzyjne.

Drzewo decyzyjne jest strukturą złożoną z węzłów, z których wychodzą gałęzie prowadzące

do innych węzłów lub liści, oraz z liści. Węzły odpowiadają warunkom podziałów dokonywa-

nych na wartościach atrybutów uwzględnianych przykładów, gałęzie odpowiadają wynikom

tych podziałów, a liście — klasom (kategoriom).

Przykładami warunków podziału dokonywanych na podstawie wartości atrybutu a przykła-

du x mogą być:

a(x) =







0 jeżeli a(x) < w

1 jeżeli a(x) ­ w

lub

a(x) =







0 jeżeli a(x) = w

1 jeżeli a(x) 6= w

,

gdzie w jest pewną ustaloną wartością.

Kolejność uwzględniania poszczególnych atrybutów podczas tworzenia drzewa oraz okre-

ślenie poszczególnych kryteriów podziału (np. wspomnianej wyżej wartości w) ustalane są na

podstawie miar opisanych w literaturze np. [1] lub [2].

3. Drzewa decyzyjne zastosowaniem R - przykład

W środowisku R możliwe jest zastosowanie drzew decyzyjnych dzięki wykorzystaniu m.in. pa-

kietu rpart. Prezentowany poniżej przykład dotyczy zadania klasyfikacji popularnych kwiatów

– irysów. Identyfikacja gatunku irysa (klasyfikacja) będzie dokonywana na podstawie znajomo-

ści wymiarów jego płatka i kielicha.

Pierwszym krokiem jest załadowanie pakietu rpart oraz wczytanie danych (dane znajdują

się w odpowiedniej bibliotece środowiska R).

library(rpart)
data(iris)

Gliwice 2011-04-13

- 2/5 -

Tworzenie drzewa decyzyjnego na podstawie danych uczących (przykładów) realizowane

jest przy użyciu funkcji rpart:

drzewo <- rpart(Species ~ ., data=iris,

control=rpart.control(cp=0.0001, minsplit=3, minbucket=1))

gdzie Species ∼ . jest formułą mówiącą, że poszukiwane jest drzewo, którego liście będą

odpowiadały klasom opisanym przez wartości atrybutu Species, a przy klasyfikacji brane

mają być pod uwagę wszystkie pozostałe atrybuty (co oznaczono kropką) ze zbioru danych

trenujących iris; parametry sterujące procedurą tworzenia drzewa zadawane są poprzez opcję

control, gdzie m.in. cp oznacza parametr złożoności modelu (wielkości drzewa), minsplit

— najmniejszą liczbę przykładów jaka może podlegać jeszcze dalszemu podziałowi, minbucket

— minimalną liczbę przykładów w liściu drzewa (domyślnie minsplit/3).

Utworzone drzewo można pokazać w postaci tekstowej za pomocą polecenia:

print(drzewo)

którego wyniki należy interpretować w sposób następujący: node) oznacza numer węzła, split

— nazwę atrybutu, wg którego dokonywany był podział, n — liczbę przykładów w danym

węźle, loss — liczbę błędnie sklasyfikowanych przykładów, yval odpowiada klasie (wg reguły

większościowej), a (yprob) jest wektorem prawdopodobieństw przynależności do danej klasy.

Nazwy klas są uporządkowane leksykograficznie (por. polecenie table(iris["Species"])).

W opisie drzewa symbol „*” oznacza liść drzewa.

Graficznie, drzewo może być przedstawione np. za pomocą poleceń:

plot(drzewo, uniform=TRUE, main="Klasyfikacja irysow")
text(drzewo, use.n=TRUE, all=TRUE, cex=.8)

Informację o parametrze określającym złożoność drzewa cp w zależności od wielkości drze-

wa możemy uzyskać stosując polecenia:

printcp(drzewo)
plotcp(drzewo)

Przyjmuje się, że optymalnym drzewem jest najmniejsze drzewo, dla którego błąd klasyfika-

cji jest niższy od wartości wskazywanej przez poziomą linię na uzyskanym wykresie. Optymalne

drzewo uzyskuje się przez przycięcie pełnego drzewa do wielkości wskazywanej przez optymal-

ny błąd klasyfikacji. W przypadku rozpatrywanego zadania przycięcie to będzie realizowane za

pomocą polecenia:

drzewo.p <- prune(drzewo, cp=drzewo$cptable[4])

Skuteczność klasyfikacji uzyskanego drzewa można ocenić określając poprawność klasyfi-

kacji przykładów, które nie były stosowane w procesie tworzenia drzewa. Dysponując zbiorem

Gliwice 2011-04-13

- 3/5 -

przykładów uczących, możemy dokonać jego podziału na dwa rozłączne zbiory — zbiór przy-

kładów trenujących (stosowanych w procesie tworzenia drzewa) oraz zbiór przykładów testo-

wych. Klasyfikując przykłady testowe i porównując uzyskane wyniki z klasyfikacją prawidłową

(zapisaną jako wartości atrybutu przykładach testowych) możemy ocenić jakość otrzymanego

klasyfikatora. Przykład realizujący ww. działania przedstawiono poniżej:

# podzial zbioru na dane trenujące i testowe
set.seed(123)
l.d <- nrow(iris) #liczba danych
test <- sample(1:l.d, round(l.d/3), replace=FALSE)
iris.tr <- iris[-test,]
iris.test <- iris[test,]

drzewo <- rpart(Species~., data=iris.tr,

control=rpart.control(cp=0.0001, minsplit=3, minbucket=1))

plotcp(drzewo)
printcp(drzewo)
drzewo.p <- prune(drzewo, cp=drzewo$cptable[3])

# błąd klasyfikacji
y.pred <- predict(drzewo.p, newdata=iris.test, type="class")
(blad <- 1-sum(y.pred==iris.test$Species)/nrow(iris.test))

4. Zadanie

Dla danych wskazanych przez prowadzącego, opracować optymalne drzewo klasyfikacyjne i

określić błąd klasyfikacji.

W tym celu należy m.in.:

1. wczytać i przeanalizować dane,

2. dokonać podziału danych na dane trenujące i testowe wg proporcji określonej przez

prowadzącego,

3. zbudować pełne drzewo klasyfikacyjne,

4. przyciąć uzyskane drzewo w taki sposób, aby uzyskać drzewo optymalne,

5. przetestować uzyskany klasyfikator i określić błąd klasyfikacji uzyskany dla danych te-

stowych,

6. opracować sprawozdanie, zawierające uzyskane wyniki oraz wnioski z nich płynące.

5. Przydatne funkcje i elementy języka R

Pakiet rpart z funkcjami stosowanymi powyżej, path.rpart, which.min.

Gliwice 2011-04-13

- 4/5 -

Literatura

[1] Walesiak M, Gatnar E.: Statystyczna analiza danych z wykorzystaniem programu R.

PWN, Warszawa, 2009.

[2] Sztuczna inteligencja. SI Moduł 10 - Zadanie i metody klasyfikacji.

http://wazniak.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja/SI_

Modu%C5%82_10_-_Zadanie_i_metody_klasyfikacji

Gliwice 2011-04-13

- 5/5 -