Algoritma Entropy Minimization Clustering


Algoritma Entropy Minimization Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor.
Algoritma ini memiliki kemiripan dengan Algoritma Category Utility Clustering. Pada algoritma tersebut, cluster terbaik diukur dengan nilai CU (Category Utility), semakin tinggi nilai CU, maka semakin baik pengelompokan data yang dilakukan. Sedangkan pada algoritma ini, cluster terbaik diukur dengan nilai Entropy, semakin rendah nilai Entropy, maka semakin baik pengelompokan data yang dilakukan.



Diasumsikan ada 13 data pelanggan, yaitu Pelanggan A,B,C,D,E,F,G,H,I,J,K,L,M
Masing-masing pelanggan memiliki kriteria, yaitu umur, jenis kelamin, skor kepribadian
Maka tentukan kelompok data pelanggan menjadi 2 bagian, yaitu kelompok data Diterima atau Ditolak
Diasumsikan 13 data tersebut adalah sebagai berikut:

Pelanggan Umur Jenis Kelamin Skor Kepribadian
Pelanggan A 44 Laki-laki 3.55
Pelanggan B 52 Perempuan 4.71
Pelanggan C 47 Perempuan 6.56
Pelanggan D 37 Laki-laki 6.8
Pelanggan E 43 Laki-laki 6.94
Pelanggan F 35 Perempuan 6.52
Pelanggan G 61 Laki-laki 4.25
Pelanggan H 53 Perempuan 5.71
Pelanggan I 60 Perempuan 6.05
Pelanggan J 54 Laki-Laki 5
Pelanggan K 52 Laki-Laki 5.7
Pelanggan L 46 Laki-Laki 3.9
Pelanggan M 56 Perempuan 4.85

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Cluster
Jumlah Cluster adalah jumlah dari pengelompokan data yang ingin dilakukan
Jumlah Cluster nilainya harus diantara 2 dan jumlah data
Diasumsikan dalam kasus ini, jumlah pengelompokan data ada 2 kelompok, yaitu kelompok Diterima dan Ditolak

* Tentukan Jumlah iterasi yang diperlukan untuk mendapatkan data awal pada masing-masing cluster
Diasumsikan dalam kasus ini, jumlah iterasi adalah 10


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Pengelompokan untuk masing-masing kriteria
Jumlah pengelompokan bebas tergantung keinginan
Contoh dalam kasus ini:
Kriteria umur hanya dikelompokan menjadi 3 bagian yaitu untuk umur dibawah 40, 41 sampai dengan 50, diatas 50
Kriteria jenis kelamin dikelompokan menjadi 2 bagian yaitu untuk laki-laki dan perempuan
Kriteria skor kepribadian dikelompokan menjadi 4 bagian yaitu untuk skor dibawah 4, 4 sampai dengan 5, 5 sampai dengan 6, diatas 6

2. Tentukan matriks data awal untuk data yang sudah mengalami pengelompokan data sesuai kriteria diatas

3. Lakukan perhitungan untuk mencari cluster awal
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 3a – 3c)

3a. Pilih data sebanyak jumlah cluster, yang datanya dianggap tidak memiliki kemiripan

* Gunakan fungsi ini untuk mencari indeks yang cukup baik pada masing-masing cluster
indeks yang cukup baik adalah indeks data yang dianggap paling berbeda (tidak memiliki kemiripan)
Indeks data yang paling berbeda adalah indeks data dengan nilai total delta yang paling tinggi
Kemudian lakukan proses tersebut sebanyak parameter jumlah iterasi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

3a1. Pada setiap kali perulangan,
Cari indeks acak sejumlah banyak cluster, dengan indeks acak yang tidak boleh ada yang sama

3a2. Hitung total delta yaitu jumlah delta pada pada setiap indeks acak

3a3. Jika total delta yang telah dihitung ternyata lebih dari delta tertinggi, maka ambil indeks nya sebagai indeks terbaik

3b. Masukkan data ini kedalam masing-masing cluster sebagai data awal

3c. Kemudian untuk masing-masing data yang belum terpilih:

3c1. Hitung nilai Entropy untuk setiap cluster apabila data ini dimasukkan ke cluster tersebut

* Gunakan fungsi ini untuk memasukkan data ke dalam cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

* Gunakan fungsi ini untuk mengeluarkan data dari sebuah cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

3c2. Cari nilai Entropy Terbaik untuk mendapatkan cluster tujuan tempat memasukkan data ini
Cluster yang terpilih adalah cluster yang menghasilkan nilai Entropy terendah (terbaik)

3c3. Masukkan data tersebut ke dalam cluster yang menghasilkan nilai Entropy terendah (terbaik)

4. Tentukan nilai Entropy untuk cluster yang sudah ditentukan
Nilai Entropy disini adalah rata-rata nilai entropy pada setiap cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a – 4f)

Lakukan perhitungan Entropy dengan rumus:
H(x) = -(E P(Ci) * log2(P(Ci)))

4a. Hitung P(Ci), yaitu probabilitas kelompok kriteria j pada cluster k dibagi semua data pada cluster k

4b. Hitung log2(P(Ci))

4c. Hitung P(Ci) * log2(P(Ci))

4d. Hitung E P(Ci) * log2(P(Ci)), yaitu tambahkan nilai tersebut pada cluster k

4e. Hitung -(E P(Ci) * log2(P(Ci))), yaitu nilai entropy cluster k dikali -1

4f. Selanjutnya adalah menghitung nilai total dari nilai entropi cluster yang sudah dinormalisasi
Bobot normalisasi yang digunakan adalah persentase jumlah data tiap cluster terhadap semua data
Proses normalisasi akan menyebabkan data akan tersebar ke dalam cluster secara merata
Setelah menemukan nilai bobot normalisasi, maka hitung nilai total entropi pada semua cluster.

5. Lakukan proses perbaikan cluster untuk menghasilkan cluster yang lebih baik
Untuk setiap cluster baru, hitung nilai Entrooy nya
Apabila nilai Entrooy nya lebih rendah (lebih baik), maka ambil cluster ini sebagai cluster terbaik
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 5a – 5d)

5a. Pada setiap proses perbaikan,
Cari indeks data acak, dimana data tersebut berada pada cluster yang memiliki lebih dari 1 data lainnya

5b. Cari cluster acak yang posisi clusternya berbeda dari indeks data acak yang sudah ditentukan sebelumnya

5c. Hitung nilai entropy untuk posisi awal
Keluarkan data [indeks acak] dari cluster nya
Masukkan data tersebut ke cluster yang baru
Hitung nilai entropy baru untuk posisi yang baru

5d. Jika nilai Entropy yang baru ternyata lebih baik, maka ambil cluster ini sebagai cluster terbaik
Jika tidak maka kembalikan posisi data seperti semula

6. Hitung nilai data pada masing-masing cluster
Nilai pada setiap data dihitung dari penjumlahan nilai kelompok kriteria pada masing-masing kolom
Pada Kriteria umur, semakin rendah kelompok kriteria, maka semakin tinggi nilai kolomnya, dan sebaliknya.
Pada Kriteria jenis kelamin dan skor kepribadian, semakin tinggi kelompok kriteria, maka semakin tinggi nilai kolomnya, dan sebaliknya.

7. Lihat kembali matriks data awal yang sudah terkelompok
Bandingkan nilai total data antara kedua cluster
Nilai total data yang lebih tinggi akan masuk ke dalam kelompok Diterima, sedangkan nilai total data yang lebih rendah akan masuk ke dalam kelompok Ditolak


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd50a


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *