Sabtu, 15 September 2018

Implementasi Manual Clustering dengan Metode Fuzzy C-Means


Hi all, setelah kita membahas tentang cara kerja K-means clustering (dan pseudocodenya). Kali ini kita akan membahas tentang metode clustering yang serupa (tapi tak sama) yaitu metode fuzzy c-means (FCM).

Secara singkat, perbedaan yang utama dari keduanya adalah metode K-means termasuk tipe hard clustering sedangkan fuzzy c-means adalah soft clustering.

Untuk analoginya, ambil contoh kita akan mengcluster 25 perusahaan yang ada di Indonesia (sebut saja perusahaan A,B,C,D…. ) menjadi 3 kelompok  (berprospek, cukup berprospek, kurang berprospek) dengan parameter tertentu meggunakan metode K-means. Setelah metode clustering k-means dilaksanakan misal akan menghasilkan result dibawah ini,

Perusahaan
Cluster ke-
A
1
B
2
C
1
D
3
E
1
….

Dari tabel diatas terlihat jelas bukan? Bahwa perusahaan A termasuk pada cluster ke-1, B pada cluster ke-2 dan seterusnya. Namun, jika kita menggunakan metode FCM, kita akan mempunyai hasil seperti berikut;

Perusahaan
Bobot Cluster 1
Bobot Cluster 2
Bobot Cluster 3
A
0,6345
0,1454
0,2201
B
0,1233
0,4564
0,4203
C
0,7123
0,1111
0,1766
D
0,1232
0,2906
0,5862
E
0,4323
0,2245
0,3432
….

Kenapa hasilnya menjadi seperti ini? Untuk lebih jelasnya kita harus belajar yang namanya konsep fuzzy, kalian bisa mencari definisi fuzzy itu sendiri namun singkatnya seperti ini;

Logika fuzzy pertama kali diperkenalkan oleh Prof. Lotfi A. Zadeh pada tahun 1965 (Zimmerman,1991). Zadeh memberikan definisi tentang himpunan fuzzy sebagai berikut: Jika X adalah koleksi objek yang dinotasikan oleh x, maka suatu himpunan fuzzy A dalam X adalah suatu himpunan pasangan berurutan:




Dengan µA(x) adalah derajat keanggotaan x di A yang memetakan X ke ruang keanggotaan M yang terletak pada rentang [0,1]

Untuk lebih jelasnya. konsep bilangan fuzzy itu bertentangan dengan konsep hitam putih, coba dilihat lagi di table sebelumnya, terlihat bahwa Perusahaan A mempunyai derajat keanggotaan sebesar 0,6345 ke ruang keanggotaan cluster 1 , lebih besar dari derajat keanggotaan sebesar 0,1454 ke ruang keanggotaan 2  dan derajat keanggotaan sebesar 0,2201 ke ruang keanggotaan 3. Maka dari itu Perusahaan A bisa digolongkan sebagai anggota cluster ke-1 karena bobot keanggotaan Perusahaan A terhadap cluster ke-1 lebih besar daripada yang lain. Lain halnya dengan menggunakan metode k-means (hard clustering type) dimana hanya mengenal konsep 0 atau 1 (tidak termasuk atau termasuk)

Perusahaan
Bobot Ke-1
Bobot Ke-2
Bobot Ke-3
Bobot Terbesar
A
0,6345
0,1454
0,2201
1
B
0,1233
0,4564
0,4203
2
C
0,7123
0,1111
0,1766
1
D
0,1232
0,2906
0,5862
3
E
0,4323
0,2245
0,3432
1
….

Proses clustering dengan menggunakan algoritma Fuzzy C-Means memiliki langkah-langkah sebagai berikut :
1.             Input data yang akan dimasukan ke X, yang berupa matriks berukuran n x m (n = jumlah sampel data, m = jumlah atribut setiap data). Xij data sampel ke-i (i=1,2,..n), atribut ke-j (j=1,2,..m).

2.             Tentukan jumlah cluster (c), pangkat (w), maksimum iterasi (MaxIter), error terkecil yang diharapkan (ɛ), fungsi objektif awal (P0 = 0), dan iterasi awal (t=1).

3.             Bangkitkan bilangan random µik, i=1,2,..n: k=1,2,..c sebagai elemen matriks partisi awal U. Dengan j=1,2..n, hitung :                                                                                                                           
                                                                                                                                                
4.             Hitung pusat cluster ke-k, dengan k=1,2,..c dan j=1,2,..m
                                                                                                                                      
5.             Hitung fungsi obyektif pada iterasi ke-t
                                                                               
                            
6.             Hitung perubahan matriks partisi :
                                                                       
                                   
7.             Jika : (|Pt-Pt-1|< ɛ atau (t > MaxIter) maka berhenti, jika tidak : t = t+1, ulangi langkah 4.

Langkah-langkah Algoritma Fuzzy C-Means dapat digambarkan dengan diagram;


Untuk mempermudah implementasi Fuzzy C-Means secara manual, Untuk mempermudah implementasi Fuzzy C-Means secara manual, kita coba buat contoh kasusnya;



Terdapat 10 perusaahan di Indonesia (A,B,C,D,E,F,G,H,I dan J) yang ingin dikelompokkan dengan metode FCM menjadi 4 kelompok, yaitu kelompok perusahaan cost leader, differentiation, focused cost leader dan focused diffentiation. Penilaian prospek perusahaan akan ditentukan dengan dimensi besar margin profit (bernilai antara 0 sampai 4, dimana 4 menunjukan bahwa perusahaan tersebut mwmpunyai margin profit sangat lebar) dan dimensi variasi produk (bernilai antara 0 sampai 5, dimana 5 menunjukan bahwa perusahaan mempunyai banyak variasi produk). Data kesepuluh perusahaan tersebut tersaji pada tabel berikut ini.

Perusahaan
Gross Profit
Variasi Produk
1
A
3,15
3,9
2
B
2,93
4,1
3
C
3,19
5,1
4
D
3,63
3,9
5
E
2,95
4,1
6
F
3,03
4,1
7
G
2,97
4,1
8
H
2,62
4,9
9
I
3,16
3,9
10
J
3,26
3,9
           
            Pada kasus ini data akan diolah atau dikelompokkan (clustering) menggunakan algoritma fuzzy c-means. Dalam algoritma fuzzy c-means yang dilakukan pertama kali adalah menentukan jumlah cluster (c), pangkat (w), maksimum iterasi (MaxIter), error terkecil yang diharapkan (ɛ), fungsi objektif awal (P0 = 0), dan iterasi awal (t=1). Dan pada penelitian ini penulis menentukan 4 kelompok (cluster) untuk proses pengelompokkan (clustering) agar setiap cluster tidak memiliki centroid yang berdekatan sehingga hasil kelompok dapat memiliki kategori yang berbeda-beda. dengan pangkat (w) sebanyak 2.
Langkah berikutnya adalah membangkitkan bilangan random µik, i=1,2,..n: k=1,2,..c sebagai elemen matriks partisi awal µ, dan menghitung total barisnya (Q). 

Matriks Partisi Acak
µ
c1
c2
c3
c4
Sum(Q)
1
0,5629
0,8024
0,888
0,452
2,7053
2
0,7766
0,4265
0,5821
0,4356
2,2208
3
0,9936
0,1295
0,7236
0,3245
2,1712
4
0,1209
0,7016
0,2526
0,5845
1,6596
5
0,316
0,1174
0,3126
0,1235
0,8695
6
0,0961
0,4798
0,4322
0,2546
1,2627
7
0,4186
0,411
0,1021
0,151
1,0827
8
0,0623
0,8989
0,5768
0,4543
1,9923
9
0,1111
0,4647
0,31
0,1242
1,01
10
0,1604
0,2088
0,8455
0,2368
1,4515

Lalu normalisasi matriks partisi dengan membagi tiap elemen dengan total  barisnya.
Matriks Partisi Acak Yang Dinormalisasi
µ
c1
c2
c3
c4
1
0,208073
0,296603
0,328245
0,167079
2
0,349694
0,192048
0,262113
0,196146
3
0,457627
0,059644
0,333272
0,149457
4
0,072849
0,422752
0,152205
0,352193
5
0,363427
0,13502
0,359517
0,142036
6
0,076107
0,379979
0,342282
0,201631
7
0,386626
0,379607
0,094301
0,139466
8
0,03127
0,451187
0,289515
0,228028
9
0,11
0,460099
0,306931
0,12297
10
0,110506
0,143851
0,582501
0,163142

            Langkah berikutnya adalah menghitung pusat cluster ke-k, dengan k=1,2,..c dan j=1,2,..m :
Pusat Kluster

V
x1
x2
C1
3,050354
4,382303
C2
3,080848
4,163438
C3
3,106412
4,160223
C4
3,188975
4,165143

          Setelah itu, hitung fungsi objektif pada iterasi ke-t, dengan memakai rumus 

Hasil P1 adalah 0,754941. Dan hitung perubahan matriks partisi dengan algortima :

          Hasil perubahan matriks partisi akan terlihat pada Tabel dibawah

Hasil Matriks Partisi Baru
µ
c1
c2
c3
c4
cluster
1
0,089841
0,293744
0,313011
0,303404
3
2
0,116987
0,411428
0,317081
0,154503
2
3
0,355425
0,213716
0,21345
0,217409
1
4
0,157646
0,241635
0,262209
0,33851
4
5
0,100972
0,428638
0,322656
0,147734
2
6
0,041158
0,498809
0,34833
0,111704
2
7
0,084697
0,447333
0,328168
0,139802
2
8
0,369926
0,222089
0,213883
0,194103
1
9
0,089785
0,290291
0,311172
0,308753
3
10
0,095926
0,261394
0,290566
0,352114
4

 Pada tabel 3.10 terlihat bahwa di iterasi pertama, nilai cluster 3 pada perusahaan A (no.1) lebih besar daripada nilai di cluster lainnya, sehingga data tersebut dimasukan ke dalam cluster ketiga. Sedangkan nilai cluster 2 pada perusahaan B (no.2) lebih besar daripada nilai di cluster lainnya, sehingga data tersebut dimasukan ke dalam cluster kedua dan seterusnya. Lakukan iterasi dengan menggunakan matriks partisi baru hingga |Pt-Pt-1|< ɛ atau jumlah iterasi mencapai nilai maksimal yang ditentukan.

-----------------------------------------------------------

Begitulah gaes, artikel tentang metode clustering menggunakan FCM ini, jika ada yang ingin disampaikan don't hestite to comment ya gaes!

Sumber :
-   “Student academic performance analysis using fuzzy C-means clustering”, IOP Conference Series: Materials Science and Engineering, Volume 166, conference 1. doi:10.1088/1757-899X/166/1/012036 (http://iopscience.iop.org/article/10.1088/1757-899X/166/1/012036)
-  Kharismawan, Bagus 2015 (Unpad: University of Padjadjaran) Aplikasi K-Means dan Fuzzy C-Means Clustering untuk Mengelompokkan Data Mahasiswa FMIPA

Tidak ada komentar:

Posting Komentar