next_inactive up previous


Drzewo decyzyjne C4.5, czyli jak nauczyć komputer odróżniać dobro od zła

Urszula Herman-Iżycka
Przemysław Strzelczak

19. marca 2004


Spis rzeczy

Wprowadzenie

Idea

Człowiek posiada tę umiejętność, że na podstawie przeszłych doświadczeń potrafi trafnie sklasyfikować nowy przypadek i podjąć wobec niego dobrą decyzję. My więc chcielibyśmy tego samego nauczyć komputer. Dając mu ''bagaż'' doświadczeń, czyli informację o przypadkach określonego typu, chcielibyśmy, aby podejmował racjonalną decyzję. Racjonalną znaczy najbliższą indukowanym regułom, które w jego mniemaniu zostały użyte do podjęcia tych dobrych decyzji i jednocześnie o niskim przewidywalnym poziomie pomyłek.

Do tych właśnie celów wymyślono drzewa decyzyjne, które na stałe wpisały się w poczet elementów uczenia maszynowego. Na podstawie dostarczonego zbioru faktów i reguł maszyna uczy się jak sklasyfikować nowe przypadki. Zbiór faktów na podstawie, których będziemy wnioskować nazywamy Training Set, natomiast nowe przypadki, które będziemy chcieli zaklasyfikować to Test Set. Klasyfikacja polega na stwierdzeniu w jakiej kategorii umieścić nowy przypadek, zwykle jest to podział binarny na true lub false itp. Training Set jest zbiorem rekordów o tej samej strukturze, na którą składają się pary typu atrybut/wartość atrybutu. Ponadto każdy rekord jest przyporządkowany do odpowiedniej kategorii. Na podstawie wartości tych atrybutów i Training Set próbujemy sklasyfikować nowe przypadki, w których mamy dane jedynie atrybuty i ich wartości.

Oto przykład wzięty z giełdy:

	ATTRIBUTE   |	POSSIBLE VALUES
	============+=======================
	age	    | old, midlife, new
	------------+-----------------------
	competition | no, yes
	------------+-----------------------
	type        | software, hardware
	------------+-----------------------


	AGE	| COMPETITION | TYPE	| PROFIT
	=========================================
	old	| yes	      | swr	| down
	--------+-------------+---------+--------
	old	| no	      | swr 	| down
	--------+-------------+---------+--------
	old	| no	      | hwr	| down
	--------+-------------+---------+--------
	mid	| yes	      | swr	| down
	--------+-------------+---------+--------
	mid	| yes	      | hwr	| down
	--------+-------------+---------+--------
	mid	| no	      | hwr	| up
	--------+-------------+---------+--------
	mid	| no	      | swr	| up
	--------+-------------+---------+--------
	new	| yes	      | swr	| up
	--------+-------------+---------+--------
	new	| no	      | hwr	| up
	--------+-------------+---------+--------
	new	| no	      | swr	| up
	--------+-------------+---------+--------

A także przykład golfowy, z którego będziemy często korzystać. Na podstawie warunków atmosferycznych określamy czy będziemy grać w golfa czy nie.

	ATTRIBUTE   |	POSSIBLE VALUES
	============+=======================
	outlook	    | sunny, overcast, rain
	------------+-----------------------
	temperature | continuous
	------------+-----------------------
	humidity    | continuous
	------------+-----------------------
	windy       | true, false
	============+=======================


	OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY
	=====================================================
	sunny   |      85     |    85    | false | Don't Play
	sunny   |      80     |    90    | true  | Don't Play
	overcast|      83     |    78    | false | Play
	rain    |      70     |    96    | false | Play
	rain    |      68     |    80    | false | Play
	rain    |      65     |    70    | true  | Don't Play
	overcast|      64     |    65    | true  | Play
	sunny   |      72     |    95    | false | Don't Play
	sunny   |      69     |    70    | false | Play
	rain    |      75     |    80    | false | Play
	sunny   |      75     |    70    | true  | Play
	overcast|      72     |    90    | true  | Play
	overcast|      81     |    75    | false | Play
	rain    |      71     |    80    | true  | Don't Play

Definicja drzewa decyzyjnego

Drzewo decyzyjne jest odpowiednio zbudowanym drzewem o następujących własnościach:

Ponadto dobrze zbudowane drzewo decyzyjne (tzn. takie, które szybko potrafi zwrócić kategorię) ma odpowiednio rozmieszczone atrybuty w węzłach:

Drzewo decyzyjne w przykładzie giełdowym:

			 Age
		       / |    \
		      /  |     \
		  new/   |mid   \old
		    /    |       \
		  Up  Competition Down
                       /      \
		      /        \
		   no/          \yes
		    /            \
		  Up             Down

Natomiast w przykładzie golfowym drzewo decyzyjne wygląda tak: (wierząc autorowi artykułu :-)

			Outlook
		       / |     \
		      /  |      \
            overcast /   |sunny  \rain
                    /    |        \
	         Play   Humidity   Windy
		       /   |         |  \
                      /    |         |   \
		<=75 /  >75|     true|    \false
		    /      |         |     \
                 Play   Don'tPlay Don'tPlay Play

Pomocnicze definicje

Aby przystąpić do budowy drzewa potrzebujemy jeszcze kilku definicji, a przede wszystkim określić jak wybrać spośród atrybutów ten, który zawiera ,,najwięcej informacji''.

Entropia rozkładu prawdopodobieństwa

Mając zadany rozkład prawdopodobieństwa P=(p1, p2, ..., pn) określamy Informację, jaką przechowuje ten rozkład (Entropię P) jako:

$I(P) = -(p_1* \log(p_1) + p_2* \log(p_2) + \ldots + p_n* \log(p_n))$

Im bardziej jednorodny rozkład prawdopodobieństwa, tym większa jest jego informacja:

Podział na klasy

Podzielmy zbiór rekordów T na rozłączne klasy C1, C2, ..., Ck według wartości ich atrybutu kategorii. Informację potrzebną, by stwierdzić do której klasy należy element ze zbioru oznaczmy przez

$Info(T) = I(P)$

gdzie P jest rozkładem prawdopodobieństwa podziału (C1, C2, ..., Ck) zadanym następująco

$P = (\frac{C_1}{T}, \frac{C_2}{T}, \ldots, \frac{C_k}{T})$

W przykładzie z giełdą mamy:

$Info(T) = I(\frac{5}{10},\frac{5}{10}) = 1.0$

gdyż mamy dwie klasy (Up, Down) i w naszym Training Set dokładnie 5 entek spośród 10 miało kategorię Up i dokładnie 5- Down.

Informacja atrybutu

Podzielmy zbiór T na podstawie wartości atrybutu X na podzbiory T1, T2, .., Tn. Informacja potrzebna, by stwierdzić do jakiej klasy należy element z T jest średnią ważoną informacji potrzebnych, by stwierdzić do jakiej klasy należy element Ti:

$Info(X,T) = \sum_{i = 1}^{n} \frac{\Vert T_i\Vert}{\Vert T\Vert} * Info(T_i)$

W golfowym przykładzie obliczenia są następujące:

$Info(Outlook,T) = \frac{5}{14} * I(\frac{2}{5}, \frac{3}{5}) +
\frac{4}{14} * I(\frac{4}{4},0) +
\frac{5}{14} * I(\frac{3}{5}, \frac{2}{5}) = 0.694$

Gain(X,T)

Różnicę pomiędzy informacją potrzebną, by stwierdzić do jakiej klasy należy element T, a informacją potrzebną, po tym jak poznaliśmy wartość atrybutu X definiujemy jako:

$Gain(X,T) = Info(T) - Info(X,T)$

W przykładzie golfowym:

$Gain(Outlook,T) = Info(T) - Info(Outlook,T) = 0.94 - 0.694 = 0.246$

$Gain(Windy,T) = Info(T) - Info(Windy,T) = 0.94 - 0.892 = 0.048$

Widzimy więc, że Outlook daje większy zysk informacji niż Windy.
Budując drzewo decyzyjne będziemy się opierać na wartościach Gain wyliczonych dla każdego atrybutu i umieszczać w korzeniu poddrzewa ten atrybut spośród tych, które jeszcze nie zostały umieszczone w drzewie a który ma największą wartość Gain. Dzięki temu zbudujemy małe drzewo decyzyjne, które będzie w stanie sklasyfikować odpowiednio nowe rekordy w kilku krokach.

Gain Ratios

Gain daje lepsze wyniki w przypadku, gdy atrybut ma dużą liczbę rożnych wartości. Na przykład dla atrybutu D, który ma rozkład prawdopodobieństwa (0,1) Info(D,T)=0 zaś Gain(D,T) jest maksymalne i równe Info(T). Problem możemy zaobserwować w naszym przykładzie golfowym, Gain(Outlook,T) ma dużo większą wartość niż Gain(Windy,T), gdyż Outlook przyjmuje trzy wartości a Windy tylko dwie. Aby to zrównoważyć wprowadzono Gain Ratio:

$GainRatio(D,T) = \frac{Gain(D,T)}{SplitInfo(D,T)}$

gdzie SplitInfo(D,T) definiujemy następująco (zakładając że T1..Tm jest podziałem T indukowanym przez D):

$SplitInfo(D,T) = I(\frac{T1}{T}, \frac{T2}{T}, \ldots, \frac{Tm}{T})$

W przykładzie golfowym mamy:

Otrzymaliśmy więc bardziej zrównoważone wyniki. Możemy zatem zamiast Gain używać GainRatio.

Algorytm ID3

Rekurencyjny algorytm budowy drzewa, który jako danych wejściowych potrzebuje:

   function ID3 (R: a set of non-categorical attributes,
		 C: the categorical attribute,
		 S: a training set) returns a decision tree;
   begin
	If S is empty, return a single node with value Failure;
	If S consists of records all with the same value for 
	   the categorical attribute, 
	   return a single node with that value;
	If R is empty, then return a single node with as value
	   the most frequent of the values of the categorical attribute
	   that are found in records of S; [note that then there
	   will be errors, that is, records that will be improperly
	   classified];
	Let D be the attribute with largest Gain(D,S) 
	   among attributes in R;
	Let {dj| j=1,2, .., m} be the values of attribute D;
	Let {Sj| j=1,2, .., m} be the subsets of S consisting 
	   respectively of records with value dj for attribute D;
	Return a tree with root labeled D and arcs labeled 
	   d1, d2, .., dm going respectively to the trees 

	     ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
   end ID3;

Cechy algorytmu ID3

Zalety

Wady

C4.5, czyli dlaczego ID3 nam nie wystarczy?

Algorytm C4.5 (Quinlan) jest rozszerzeniem algorytmu ID3 wychodzącym naprzeciw problemom napotkanym przez ID3.

Lekarstwo na techniczne ograniczenia ID3

Przycinanie, czyli główny pomysł C4.5

W algorytmie ID3 głownym kłopotem był niepotrzebny rozrost drzewa i brak mechanizmów przeciwdziałających zjawisku overfitting-u, co prowadziło do dość wysokiego poziomu błędów dla rzeczywistych danych. Aby tego uniknąć stosuje się tzw. przycinanie (ang. pruning) , w celu zwiększenia generalizacji oceny. Konkretnie działa ono w następujący sposób:

Dzięki temu zabiegowi otrzymujemy większą generalizację oceny nowych przypadków, a o to przecież nam chodziło.

Implementacja algorytmu C4.5

W sieci ogólnodostępna jest implementacja algorytmu C4.5. Pakiet zawiera zarówno program do tworzenia drzewa decyzyjnego, jak i do tworzenia reguł wnioskowania na podstawie wygenerowanego drzewa oraz prostą aplikację do zastosowania otrzymanych reguł do klasyfikacji nowych przypadków.

Poniżej zaprezentuję efekty testów dla znajomych przykładów.

Nazewnictwo

Programy c4.5 oraz c4.5rules jako domyślne parametry przyjmują pliki problem.names z zakodowanymi dziedzinami oraz problem.data z zakodowanym Training Set. Opcjonalnym parametrem jest zbiór danych testowych problem.test.

Wyniki

Problem gry w golfa

Oto dane i wyniki dla problemu z grą w golfa:

Atrybuty i ich dziedziny

Play, Don't Play.

outlook: sunny, overcast, rain.
temperature: continuous.
humidity: continuous.
windy: true, false.

Training Set

sunny, 85, 85, false, Don't Play
sunny, 80, 90, true, Don't Play
overcast, 83, 78, false, Play
rain, 70, 96, false, Play
rain, 68, 80, false, Play
rain, 65, 70, true, Don't Play
overcast, 64, 65, true, Play
sunny, 72, 95, false, Don't Play
sunny, 69, 70, false, Play
rain, 75, 80, false, Play
sunny, 75, 70, true, Play
overcast, 72, 90, true, Play
overcast, 81, 75, false, Play
rain, 71, 80, true, Don't Play

Wyprodukowane drzewo

C4.5 [release 8] decision tree generator	Wed Mar 17 20:18:34 2004
----------------------------------------

    Options:
	File stem <golf>

Read 14 cases (4 attributes) from golf.data

Decision Tree:

outlook = overcast: Play (4.0)
outlook = sunny:
|   humidity <= 75 : Play (2.0)
|   humidity > 75 : Don't Play (3.0)
outlook = rain:
|   windy = true: Don't Play (2.0)
|   windy = false: Play (3.0)


Tree saved


Evaluation on training data (14 items):

	 Before Pruning           After Pruning
	----------------   ---------------------------
	Size      Errors   Size      Errors   Estimate

	   8    0( 0.0%)      8    0( 0.0%)    (38.5%)   <<

Otrzymane reguły

C4.5 [release 8] rule generator	Wed Mar 17 20:18:44 2004
-------------------------------

    Options:
	File stem <golf>

Read 14 cases (4 attributes) from golf

------------------
Processing tree 0

Final rules from tree 0:

Rule 2:
    	outlook = overcast
	->  class Play  [70.7%]<br>

Rule 4:
    	outlook = rain
    	windy = false
	->  class Play  [63.0%]

Rule 1:
    	outlook = sunny
    	humidity > 75
	->  class Don't Play  [63.0%]

Rule 3:
    	outlook = rain
    	windy = true
	->  class Don't Play  [50.0%]

Default class: Play


Evaluation on training data (14 items):

Rule  Size  Error  Used  Wrong	          Advantage
----  ----  -----  ----  -----	          ---------
   2     1  29.3%     4      0 (0.0%)	     0 (0|0) 	Play
   4     2  37.0%     3      0 (0.0%)	     0 (0|0) 	Play
   1     2  37.0%     3      0 (0.0%)	     3 (3|0) 	Don't Play
   3     2  50.0%     2      0 (0.0%)	     2 (2|0) 	Don't Play

Tested 14, errors 0 (0.0%)   <<


	  (a)  (b)	<-classified as
	 ---- ----
	    9     	(a): class Play
	         5	(b): class Don't Play

Zabawa z interpreterem drzewa

C4.5 [release 8] decision tree interpreter      Thu Mar 18 20:59:20 2004
------------------------------------------

outlook: sunny
humidity: 23

Decision:
        Play  CF = 1.00  [ 0.50 - 1.00 ]

Problem rozpoznawania języka mówionego

Komputer ma rozpoznać, jaką pisownię ma człowiek na myśli wymawiając identycznie brzmiące słowa. W naszym przypadku rozważamy słowa bare i bear. Ma do dyspozycji informację o częściach mowy pięciu wyrazów poprzedzających słowo, którego pisownie klasyfikujemy.

Atrybuty i ich dziedziny

bare, bear.

pos1: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.
pos2: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.
pos3: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.
pos4: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.
pos5: none, verb, noun, adjective, adverb, article, connective, number, possessive, pronoun, interjection, modal, preposition.

Training Set

none, article, noun, verb, adverb, bare
none, none, none, none, article, bare
none, none, possessive, noun, verb, bare
none, article, noun, noun, verb, bare
verb, adverb, adverb, preposition, article, bare
none, none, none, verb, adverb, bare
none, none, none ,none, none, bare
none, none, none, none, article, bear
pronoun, verb, verb, preposition, article, bear
none, none, pronoun, verb, article, bear
none, none, adverb, noun, modal, bear
none, none, adverb, noun, modal, bear
none, pronoun, modal, pronoun, preposition, bear
pronoun, verb, verb, pronoun, modal, bear
none, none, none, verb, preposition, bear
none, none, none, pronoun, modal, bear

Wyprodukowane drzewo

C4.5 [release 8] decision tree generator	Wed Mar 17 20:25:26 2004
----------------------------------------

    Options:
	File stem <bare>

Read 16 cases (5 attributes) from bare.data

Decision Tree:

pos5 = none: bare (1.0)
pos5 = verb: bare (2.0)
pos5 = noun: bear (0.0)
pos5 = adjective: bear (0.0)
pos5 = adverb: bare (2.0)
pos5 = article: bear (5.0/2.0)
pos5 = connective: bear (0.0)
pos5 = number: bear (0.0)
pos5 = possessive: bear (0.0)
pos5 = pronoun: bear (0.0)
pos5 = interjection: bear (0.0)
pos5 = modal: bear (4.0)
pos5 = preposition: bear (2.0)


Tree saved


Evaluation on training data (16 items):

	 Before Pruning           After Pruning
	----------------   ---------------------------
	Size      Errors   Size      Errors   Estimate

	  14    2(12.5%)     14    2(12.5%)    (51.0%)   <<

Jak widać program po czasowniku zawsze będzie mówił, że chodziło o misia, zaś po czasowniku modalnym stwierdzi, że mieliśmy na myśli tolerowanie czegoś.

About this document ...

Drzewo decyzyjne C4.5, czyli jak nauczyć komputer odróżniać dobro od zła

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -local_icons -html_version 3.2,latin2,unicode c4_5Main.tex

The translation was initiated by Przemyslaw Strzelczak on 2004-03-19


next_inactive up previous
Przemyslaw Strzelczak 2004-03-19