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

| 20 January 2017 04:20:50 (less than a year ago) | Algoritm Programming 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
Dimana:
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
Programmer C# = 5 Orang
Programmer Java = 7 Orang
Programmer C++ = 1 Orang
Programmer PHP = 20 Orang

Total = 36 Orang Programmer.

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
Programmer C# = 5 Orang, Dimana Levelnya Ada 2 = Senior dan 3 = Junior
Programmer Java = 7 Orang, Dimana Levelnya Ada 5 = Senior dan 2 = Junior
Programmer C++ = 1 Orang, Dimana Levelnya Ada 1 = Senior dan 0 = Junior
Programmer 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 Programmer VB.NET
SUB N1 = 1 + 2 = 3
entropy(X1) = - (1/3 x log2(1/3)) + - (2/3 x log2(2/3)) = 0.91829

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

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

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

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

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 Code 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).


Gambar Cover Buku Referensi

Dan hasil implementasi terlihat seperti berikut:


Gambar Data Sample


Gambar Hasil Perhitungan


Gambar Hasil Dalam Bentuk Pohon Keputusan


Gambar Hasil Konversi Dalam Bentuk Logika Pemrograman

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