Veri Madenciliği - Karar Ağacı Oluşturma

Karar ağacı, bir kök düğüm, dallar ve yaprak düğümleri içeren bir yapıdır. Her dahili düğüm, bir öznitelik üzerindeki bir testi ifade eder, her dal bir testin sonucunu belirtir ve her yaprak düğüm bir sınıf etiketi taşır. Ağaçtaki en üst düğüm, kök düğümdür.

Aşağıdaki karar ağacı, bir şirketteki bir müşterinin bilgisayar satın alma olasılığının yüksek olup olmadığını gösteren buy_computer kavramı içindir. Her dahili düğüm, bir öznitelik üzerindeki bir testi temsil eder. Her yaprak düğüm bir sınıfı temsil eder.

Karar ağacına sahip olmanın faydaları aşağıdaki gibidir:

Herhangi bir alan bilgisi gerektirmez.
Anlaşılması kolaydır.
Bir karar ağacının öğrenme ve sınıflandırma adımları basit ve hızlıdır.

Karar Ağacı İndüksiyon Algoritması

1980'de J. Ross Quinlan adlı bir makine araştırmacısı, ID3 (Yinelemeli Dichotomiser) olarak bilinen bir karar ağacı algoritması geliştirdi. Daha sonra ID3'ün halefi olan C4.5'i sundu. ID3 ve C4.5 açgözlü bir yaklaşım benimsiyor. Bu algoritmada geriye dönük izleme yoktur; ağaçlar yukarıdan aşağıya yinelemeli böl ve yönet tarzında inşa edilmiştir.

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;

Ağaç Budaması

Eğitim verilerinde gürültü veya aykırı değerler nedeniyle oluşan anormallikleri gidermek için ağaç budama yapılır. Budanmış ağaçlar daha küçük ve daha az karmaşıktır.