Katedra
Podstaw
Konstrukcji
Maszyn
Wydział
Mechaniczny
Technologiczny
Metody Sztucznej
Politechnika
Inteligencji
ÅšlÄ…ska
Rok akademicki 2010/11
Instrukcja do ćwiczeń laboratoryjnych
Laboratorium 5
Temat
Drzewa decyzyjne. Klasyfikacja
Opracował:
dr inż. Krzysztof Ciupke
ul. Konarskiego 18a
44-100 Gliwice
tel. [phone]
fax. [phone]
http://kpkm.polsl.pl
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ć:
Å„Å‚
òÅ‚
0 jeżeli a(x) < w
a(x) =
ół
1 jeżeli a(x) w
lub
Å„Å‚
òÅ‚
0 jeżeli a(x) = w
a(x) = ,
ół
1 jeżeli a(x) = 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-
kieturpart. 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 pakieturpartoraz 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 funkcjirpart:
drzewo <- rpart(Species ~ ., data=iris,
control=rpart.control(cp=0.0001, minsplit=3, minbucket=1))
gdzieSpecies<".jest formułą mówiącą, że poszukiwane jest drzewo, którego liście będą
odpowiadały klasom opisanym przez wartości atrybutuSpecies, a przy klasyfikacji brane
mają być pod uwagę wszystkie pozostałe atrybuty (co oznaczono kropką) ze zbioru danych
trenujÄ…cychiris; parametry sterujÄ…ce procedurÄ… tworzenia drzewa zadawane sÄ… poprzez opcjÄ™
control, gdzie m.in.cpoznacza 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ślnieminsplit/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ęz
le,loss liczbę błędnie sklasyfikowanych przykładów,yvalodpowiada 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. polecenietable(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ść drzewacpw 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
Pakietrpartz 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 -