Pohon Keputusan Menggunakan Metode C4.5 (Implementasi dengan PHP)

Beberapa hari ini, Saya sedang tertarik dengan salah satu proses data mining, salah satunya adalah membuat pohon keputusan. Salah satu metode yang Saya gunakan untuk membuat aplikasi pohon keputusan adalah metode C4.5. Yang Saya pahami dari metode ini adalah, dimana dengan metode ini kita akan mencari entropy lalu dilanjutkan dengan mencari gain, split info, gain ratio, dsb.

Entropy merupakan pengukuran ketidakpastian rata-rata sekumpulan data untuk mendapatkan suatu hasil dari data baru. Bingung? Yah, Saya juga bingung, namun kalau kamu seorang statistik pastinya mengerti, Saya hanya seorang developer yang mengimplemntasikan rumus-rumus yang diberikan, jadi untuk penjabaran lebih jelasnya silahkan baca-baca referensi dari buku atau Internet. Oleh karena kita langsung saja melihat rumusan yang digunakan untuk mencari entropy yaitu:

Entropy(X) = - (n1/n x log2(n1/n)) + - (n2/n x log2(n2/n)) + - (n3/n x log2(n3/n)) + ... dan seterusnya

X = nama himpunannya
n1... n3 = Merupakan banyaknya suatu kelompok tertentu dari suatu himpunan
n = total himpunan seluruh kelompok

Misalkan ada data (himpunan) dengan nama Programmer sebagai berikut:

Programmer

VB.NET = 3 Orang
C# = 5 Orang
Java = 7 Orang
C++ = 1 Orang
PHP = 20 Orang

Total = 36 Orang

Maka Entropy(Programmer) adalah

- (3/36 x log2(3/36)) + - (5/36 x log2(5/36)) + - (7/36 x log2(7/36)) + - (1/36 x log2(1/36)) + - (20/36 x log2(20/36)) = 1.7684


Implementasi Code PHP:

private function entropy($values)
 {
  $e = 0;

  $sum = array_sum($values);
  foreach ($values as $value)
  {
   if ($value > 0)
   {
    $e += - ((($value / $sum) * log($value / $sum, 2)));
   }
  }

  return $e;
 }

Dimana $values adalah nilai n1, n2, n3, dst dalam bentuk array, jika dalam contoh di atas, maka cara eksekusinya adalah "echo entropy(array(3, 5, 7, 1, 20));"

Gain merupakan ??? (Ada yang bisa mengartikannya? :D)

Langsung ke contoh saja, hampir mirip dengan data sebelumnya, hanya saja dispesifikasikan lagi:

Programmer

VB.NET = 3 Orang, Dimana Levelnya ada 1 = Senior dan 2 = Junior
 C# = 5 Orang, Dimana Levelnya Ada 2 = Senior dan 3 = Junior
Java = 7 Orang, Dimana Levelnya Ada 5 = Senior dan 2 = Junior
C++ = 1 Orang, Dimana Levelnya Ada 1 = Senior dan 0 = Junior
PHP = 20 Orang, Dimana Levelnya Ada 5 = Senior dan 15 = Junior

Sebelumnya, kita harus mencari entropy semua himpunan, namun kita harus menentukan acuan dari entropy semuanya, apakah kategory  VB.NET, C# dsbnya, atau Levelnya yang dibagi atas Senior atau Junior?

Pada contoh ini, kita memilih Levelnya. Dengan demikian Entropy(Semua) adalah:

Jumlah dengan level senior seluruhnya = 14 Orang
Jumlah dengan level junior seluruhnya = 22 Orang
Total = 36 Orang

Maka Entropy(Semua):

 - (14/36 x log2(14/36)) + - (22/36 x log2(22/36)) = 0.96407


Setelah mendapatkan entropy semua, maka gainnya adalah:

Entropy(Semua) - ((sub n1 / n * entropy(x1)) + (sub n2 / n * entropy(x2)) + (sub n3 / n * entropy(x3)) + .... dst...

Dimana,

sub n1, sub n2, sub n3.... dst = sub total dari suatu kelompok data dalam suatu himpunan
n = total seluruh himpunan data
entropy(x1), entropy(x2), entropy(x3)... dst = nilai sub entropy dari kelompok data

Bingung? mari langsung liat saja implementasi data tersebut.

Misalkan:

X1 = Kelompok VB.NET
entropy(X1) = - (1/3 x log2(1/2)) + - (2/3 x log2(2/3)) = 0.91829
SUB N1 = 1 + 2 = 3

X2 = C#
entropy(X2) = - (2/5 x log2(2/5)) + - (3/5 x log2(3/5)) = 0.97095
SUB N2 = 2 + 3 = 5

X3 = Java
entropy(X3) = - (5/7 x log2(5/7)) + - (2/7 x log2(2/7)) = 0.86312
SUB N1 = 5 + 2 = 7

X4 = C++
entropy(X4) = - (1/1 x log2(5/7)) = 0
SUB N1 = 1 + 0 = 1

X5 = PHP
entropy(X5) = - (5/20 x log2(5/20)) + - (15/20 x log2(15/20)) = 0.81127
SUB N1 = 5 + 15 = 20

 Dengan demikian gain dapat dihitung yaitu:

 0.96407 - ( (3 / 36 * 0.91829) + (5/36 * 0.97095) + (7/36 * 0.86312) + (1/36 * 0) + (20/36 * 0.81127) ) = 0.09593

 Implementasi kode untuk PHP:

private function gain($entropy_all, $values)
 {
  $total_records = 0;
  foreach ($values as $sub_values)
  {
   $total_records += array_sum($sub_values);
  }

  $gain = 0;
  foreach ($values as $sub_values)
  {
   $sub_total_value = array_sum($sub_values);
   $gain += ($sub_total_value / $total_records * $this->entropy($sub_values));
  }
  $gain = $entropy_all - $gain;

  return $gain;
 }

Dimana $entropy_all adalah E(Semua)
Sedangkan $values adalah nilai array untuk setiap kelompok. Jika diimplementasikan adalah sebagai berikut "echo $this->gain(0.96407, array(array(1, 2), array(2, 3), array(5, 7), array(1, 0), array(5, 15) ));"


Hmmm... karena rumusan penting pada metode ini sudah cukup mewakili didalam proses pengerjaan pohon keputusan dengan metode C4.5, maka artikel ini Saya batasi sampai disini dulu. Masih ada beberapa rumusan-rumusan yang belum dijelaskan namun kamu bisa baca jurnal-jurnal skripsi maupun buku-buku panduan lainnya sebagai PR buat kamu ;)

Akhirnya, Saya mau tunjukkan hasil implementasi beberapa kode PHP di atas menjadi aplikasi full, dimana data sampling nya diambil dari buku dengan judul "DATA MINING" karangan Eko Prasetyo (Halaman 68).

Dan hasilnya tampak sebagai berikut.

Gambar Data

Gambar Hasil Pencarian Akar

Gambar Hasil Akhir "Pohon Keputusan"

Gambar Konversi Hasil Pohon Keputusan Kedalam Bentuk PHP (Otomatis)

Saya juga telah membuat aplikasi versi web, agar kawan-kawan dapat menguji data uji kawan-kawan. Silahkan akses pada link di bawah ini:

http://tongameyerogatman.com/algoritm_c45/play

Jika diantara teman-teman ada yang tertarik untuk konsultasi, silahkan menghubungi Saya. Salam manis, dan salam damai ;)

Tongam Meyer R. Tampubolon