Eksploracja danych - indukcja drzewa decyzyjnego

Drzewo decyzyjne to struktura zawierająca węzeł główny, gałęzie i węzły liści. Każdy węzeł wewnętrzny oznacza test atrybutu, każda gałąź oznacza wynik testu, a każdy węzeł liścia posiada etykietę klasy. Najwyższym węzłem w drzewie jest węzeł główny.

Poniższe drzewo decyzyjne dotyczy koncepcji komputer_kup, które wskazuje, czy klient w firmie prawdopodobnie kupi komputer, czy nie. Każdy węzeł wewnętrzny reprezentuje test atrybutu. Każdy węzeł liścia reprezentuje klasę.

Korzyści z posiadania drzewa decyzyjnego są następujące:

• Nie wymaga znajomości domeny.
• Łatwo to pojąć.
• Etapy uczenia się i klasyfikacji w drzewie decyzyjnym są proste i szybkie.

Algorytm indukcji drzewa decyzyjnego

Badacz maszyn o nazwisku J. Ross Quinlan w 1980 roku opracował algorytm drzewa decyzyjnego znany jako ID3 (Iterative Dichotomiser). Później przedstawił C4.5, który był następcą ID3. ID3 i C4.5 przyjmują chciwe podejście. W tym algorytmie nie ma cofania; drzewa są konstruowane w sposób rekurencyjny z góry na dół, dziel i zwyciężaj.

Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree

Input:
Data partition, D, which is a set of training tuples 
and their associated class labels.
attribute_list, the set of candidate attributes.
Attribute selection method, a procedure to determine the
splitting criterion that best partitions that the data 
tuples into individual classes. This criterion includes a 
splitting_attribute and either a splitting point or splitting subset.

Output:
 A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then
   return N as leaf node labeled with class C;
   
if attribute_list is empty then
   return N as leaf node with labeled 
   with majority class in D;|| majority voting
   
apply attribute_selection_method(D, attribute_list) 
to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and
   multiway splits allowed then  // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute
for each outcome j of splitting criterion

   // partition the tuples and grow subtrees for each partition
   let Dj be the set of data tuples in D satisfying outcome j; // a partition
   
   if Dj is empty then
      attach a leaf labeled with the majority 
      class in D to node N;
   else 
      attach the node returned by Generate 
      decision tree(Dj, attribute list) to node N;
   end for
return N;

Przycinanie drzew

Przycinanie drzew jest wykonywane w celu usunięcia anomalii w danych uczących spowodowanych szumem lub wartościami odstającymi. Przycinane drzewa są mniejsze i mniej złożone.

Podejścia do przycinania drzew

Istnieją dwa sposoby przycinania drzewa -

• Pre-pruning - Drzewo jest przycinane przez wcześniejsze zatrzymanie jego budowy.

• Post-pruning - To podejście usuwa poddrzewo z w pełni rozwiniętego drzewa.

Złożoność kosztów

Złożoność kosztów jest mierzona za pomocą następujących dwóch parametrów -

• Liczba liści na drzewie i
• Wskaźnik błędów drzewa.