Data Mining - Induksi Pohon Keputusan

Pohon keputusan adalah struktur yang mencakup simpul akar, cabang, dan simpul daun. Setiap simpul internal menunjukkan tes pada atribut, setiap cabang menunjukkan hasil tes, dan setiap simpul daun memegang label kelas. Node paling atas pada pohon adalah simpul akar.

Pohon keputusan berikut adalah untuk konsep buy_computer yang menunjukkan apakah pelanggan di sebuah perusahaan kemungkinan besar akan membeli komputer atau tidak. Setiap node internal mewakili tes pada suatu atribut. Setiap simpul daun mewakili sebuah kelas.

Manfaat memiliki pohon keputusan adalah sebagai berikut -

• Itu tidak membutuhkan pengetahuan domain apa pun.
• Mudah dimengerti.
• Langkah-langkah pembelajaran dan klasifikasi pohon keputusan sederhana dan cepat.

Algoritma Induksi Pohon Keputusan

Seorang peneliti mesin bernama J. Ross Quinlan pada tahun 1980 mengembangkan algoritma pohon keputusan yang dikenal sebagai ID3 (Iterative Dichotomiser). Kemudian ia mempresentasikan C4.5 yang merupakan penerus ID3. ID3 dan C4.5 mengadopsi pendekatan serakah. Dalam algoritma ini, tidak ada kemunduran; pepohonan dibangun dengan cara membagi-dan-menaklukkan rekursif atas-bawah.

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;

Pemangkasan Pohon

Pemangkasan pohon dilakukan untuk menghilangkan anomali dalam data pelatihan akibat noise atau outlier. Pohon yang dipangkas lebih kecil dan tidak terlalu rumit.

Pendekatan Pemangkasan Pohon

Ada dua pendekatan untuk memangkas pohon -

• Pre-pruning - Pohon dipangkas dengan menghentikan pembangunannya lebih awal.

• Post-pruning - Pendekatan ini menghilangkan sub-pohon dari pohon yang sudah dewasa.

Kompleksitas Biaya

Kompleksitas biaya diukur dengan dua parameter berikut -

• Jumlah daun di pohon, dan
• Tingkat kesalahan pohon.