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
