05 August 2015

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/index

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


43 comments:

  1. ijin share ilmu pohon keputusan yg pernah saya pelajari di http://nugikkool.blogspot.co.id/2012/08/pohon-keputusan-id3-dan-c45-menggunakan.html
    juga ada implementasi program pohon keputusan di php, perhitungan manual, penjelasan pruning, dll. semoga bermanfaat.

    ReplyDelete
  2. Replies
    1. silahkan hubungi langsung saja ya :)

      Delete
    2. cyberpunk581@gmail.com bang minta programnya boleh g buat referensi

      Delete
    3. Boleh saja, silahkan via email ya

      Delete
    4. This comment has been removed by the author.

      Delete
  3. kak boleh minta programnya ya
    kurnia.ika12@gmail.com

    ReplyDelete
  4. silahkan konsultasikan via contact yang tersedia yaa :)

    ReplyDelete
    Replies
    1. gann boleh minta programnnya gak ?? btuh refrensi nih,,, my email : rizalahmad00@gmail.com ,Terimakasi :)

      Delete
  5. program digunakan untuk pengguna jasa Saya saja yaa :)

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. mas, bisa minta programnya gak? buat referensi aja ^^ lia_blue.girl@yahoo.com

    terimakasih sebelumnya :D

    ReplyDelete
    Replies
    1. maaf mbak, program didedikasikan untuk yang konsultasi dengan Saya. Saya sedang update agar bisa digunakan untuk demo, bersabar yaaaahh...

      Delete
  8. This comment has been removed by the author.

    ReplyDelete
  9. gan minta progam nya dong
    iisfirmansyah459@gmail.com

    ReplyDelete
    Replies
    1. sebentar ya, Saya sedang develop ulang agar bisa di akses secara online untuk coba :)

      Delete
  10. Bang saya sudah add Pin BB tapi belum di accept juga, tolong kasih info ke denishbandung@gmail.com ya :D

    ReplyDelete
  11. BB jarang digunakan, silahkan gunakan alternative lain seperti SMS/WA. Thank you atas kunjungannya :)

    ReplyDelete
  12. gan boleh minta source codenya, saya sedang tugas akhir, cuma lagi minim referensi data mining. disini saya liat punya agan pas banget dengan apa yang saya mau, email : ibnusabda@gmail.com

    ReplyDelete
  13. Demo program bisa diakses disini: http://tongameyerogatman.org/algoritm_c45/index

    ReplyDelete
  14. Mas , saya bisa dapetin source codenya ga , utk dipelajari dan dikembangkan

    ReplyDelete
    Replies
    1. Silahkan langsung demokan saja:
      http://tongameyerogatman.org/algoritm_c45/index

      Delete
    2. untuk tahapan pengerjaan / proses kerja c45

      Delete
  15. Silahkan dilihat di website baru Saya:
    http://tongameyerogatman.org/post/detail/pohon-keputusan-menggunakan-metode-c45-implementasi-dengan-php?id=2

    ReplyDelete
  16. mas demo nya ko ga bisa di acces ya?.. mau minta program nya mas hehehehe

    ReplyDelete
    Replies
    1. Silahkan akses disini: http://tongameyerogatman.org/algoritm_c45/index
      Untuk konsultasi silahkan ikuti layanan kami : http://tongameyerogatman.org/service/tutor

      Delete
  17. This comment has been removed by the author.

    ReplyDelete
  18. kang minta sourcodenya donk ke w4n5d@yahoo.com Terima Kasih

    ReplyDelete
  19. kang bgi programnya pls ,send ke andimubaroqq@gmail.com mksh

    ReplyDelete
  20. kang bgi programnya pls ,send ke andimubaroqq@gmail.com mksh

    ReplyDelete
  21. tolong dong admin sourcode dan penjelasannya... ahmadalhusein.aa@gmail.com

    ReplyDelete
  22. bang blh minta program nya kgak untuk bljr pls send ke email andimubaroqq@gmail.com mksh

    ReplyDelete
  23. Mohon maaf source code tidak diperjual belikan, jika ingin mencoba silahkan langsung saja ke: http://tongameyerogatman.org/algoritm_c45/index

    atau jika mau menggunakan jasa Saya silahkan kontak saja melalui alamat yg tersedia : http://codecrosser.blogspot.co.id/p/hubungi-kami.html

    ReplyDelete
  24. Gan Boleh liat source codenya, buat pembelajaran? kalo boleh kirim ke email yoppysamjaya@gmail.com

    ReplyDelete
  25. boleh minta programnya ga ka buat refrensi? makasih

    ReplyDelete
  26. Bang boleh minta programnya buat refrensi skripsi ? Tlng kirim ke aisyahgemini67@yahoo.co.id

    ReplyDelete
  27. Bang boleh minta programnya buat refrensi skripsi ? Tlng kirim ke aisyahgemini67@yahoo.co.id

    ReplyDelete
  28. bang boleh minta programnya samsiraf7@gmail.com buat referensi

    ReplyDelete
  29. boleh minta programnya buat refrensi mochlutvie@gmail.com

    ReplyDelete
  30. DEMO PROGRAM ADA DI SINI: http://tongameyerogatman.com/algoritm_c45/index

    ReplyDelete