Fuzzy C-Means Clustering

2.3  Fuzzy C-Means Clustering

Fuzzy C-Means (FCM) adalah sebuah metode untuk mengklaster data, membuat satu data menjadi anggota dua klaster atau lebih. Metode ini dibuat oleh Dunn pada 1973 dan dikembangkan oleh Bezdek pada tahun 1981. FCM dibuat berdasarkan minimisasi dari fungsi objektif dibawah ini:

  Gambar 2.1 Rumus Metode Minimisasi

Dimana:

v  m adalah sembarang bilangan real lebih besar daripada 1,

v  u_ij adalah derajat keanggotaan dari x_i  pada klaster j,

v  x_i adalah data terukur ke i,

v  c_j adalah pusat dari klaster, dan

v  ||*|| adalah sembarang bentuk normal yang menyatakan persamaan antara sembarang data terukur dan pusat klaster.

Partisi Fuzzy dibawah ini melalui sebuah optimisasi iterasi dari sebuah fungsi objektif yang ada diatas. Simbol c_j adalah pusat klaster dan u_ij adalah update dari derajat keanggotaan data.

         2.2

    2.3

Gambar 2.3 Rumus Centroid dan Update Derajat Keanggotaan

Iterasi ini akan berhenti saat   , dimana
 adalah sebuah standar penghentian yang nilainya adalah antara 0 dan 1 dan  k adalah langkah-langkah iterasi yang ditempuh selama keadaan penghentiannya terpenuhi. 

              Data diikat pada masing-masing klaster dengan fungsi keanggotaan. Fungsi keanggotaan yang merepresentasikan karakter dari algoritme fuzzy. Untuk pemahaman yang lebih baik, bisa diasumsikan contoh mono-dimensional di bawah ini. Ada sebuah data set tertentu yang direpresentasikan dalam sebuah sumbu x seperti gambar 2.4 di bawah ini:

     Gambar 2. 4 Sumbu X

Dengan melihat gambar 2.5, bisa diidentifikasikan dua klaster yang berdekatan dari dua data terkonsentrasi. Klaster tersebut diberi nama klaster ‘A’ dan klaster ‘B’. Dalam pendekatan pertama –algoritme K-Means-, masing-masing data terhubung hanya pada sebuah centroid. Fungsi keanggotaannya akan menjadi seperti pada Gambar 2.5 berikut ini:

                                          Gambar 2.5 Grafik Derajat Keanggotaan K-Mean

 Pada pendekatan Fuzzy C-Means, data yang sama tidak menjadi sebuah klaster secara eklusif lagi, tapi datanya bisa ditempatkan di tengah. Pada kasus ini, fungsi keanggotaan mengikuti sebuah jalur khusus untuk mengindikasikan bahwa setiap data bisa terdapat dalam beberapa klaster dengan derajat keanggotaan yang berbeda.

Gambar 2.6 Grafik Derajat Keanggotaan Fuzzy C-Means

 Pada Gambar 2.6 data ditunjukkan dalam tanda merah letaknya lebih ke dalam klaster B daripada ke dalam klaster A. Nilai  0.2 dari  ‘m’ mengindikasikan derajat keanggotaan dari A pada data.

Sekarang, dengan menggunakan representasi grafik, dapat dibangun sebuah matrix U yang faktor-faktornya adalah yang diambil dari fungsi keanggotaan. Matrik U tesebut seperti pada Gambar 2.7 berikut ini.

    Gambar 2.7 Matrik U                

 Jumlah dari baris dan kolom bergantung pada banyaknya data dan klaster. Lebih tepatnya jika ada sebuah kolom C = 2 dan baris N, maka C adalah jumlah dari klaster dan N adalah jumlah data yang diindikasikan dengan u_ij.

 Pada contoh di atas menggunakan kasus K-Means dan FCM. Bisa diperhatikan bahwa pada kasus pertama (K-means), koefisiennya selalu satu (unitary). Hal ini mengindikasikan bahwa masing-masing data hanya pada satu klaster. Sedangkan FCM koefisiennya bisa selalu lebih dari satu. Hal ini berarti data bisa menjadi anggota lebih dari satu klaster dengan derajat keanggotaan yang berbeda pula. Derajat keanggotaan yang paling tinggi nilainya akan diambil sebagai suatu acuan dimanakah suatu data masuk menjadi anggota klaster.

FCM lebih baik daripada K-Means dalam hal. FCM lebih fleksibel karena memiliki toleransi keanggotaan data terhadap tiap klaster. Hal ini tidak terjadi pada algoritme K-Means.

Tabel 2.1 Data Contoh

Data
xi	1	2	3	4	5	6
yi	7	8	9	10	11	12

Tabel 2.2 Derajat Keanggotaan Fuzzy dan Crisp untuk dua klaster

Data		Keanggotaan Crisp		Derajat Keanggotaan Fuzzy
xi	yi
1	7	1	0	0,8737	0.1262
2	8	1	0	0,9292	0,0707
3	9	1	0	0,7047	0,2952
4	10	0	1	0,2952	0,7047
5	11	0	1	0,0707	0,9292
6	12	0	1	0,1262	0,8737

            Contoh fleksibilitas dari FCM adalah sebagai berikut, andaikan ada sebuah data set seperti pada Tabel 2.1.  Data tersebut dikelompokkan menjadi 2 klaster dengan menggunakan 2 metode yakni FCM dan K-Means. Anggap Tabel 2.2 adalah hasil dari proses klasterisasi. Metode crisp (pada K-Mean) memberikan derajat keanggotaan 1 atau 0, artinya, metode ini menempatkan tiap data tepat pada satu klaster. Namun, pada FCM, tiap data menjadi anggota pada kedua klaster dengan derajat keanggotaan masing-masing.

            Pada himpunan tegas (crisp), nilai keanggotaan suatu item x dalam suatu himpunan A, yang sering ditulis dengan μ_A[x], memiliki 2 kemungkinan, yaitu:

o      satu (1), yang berarti bahwa suatu item menjadi anggota dalam suatu himpunan, atau

o      nol (0), yang berarti bahwa suatu item tidak menjadi anggota dalam suatu himpunan.

Contoh: Jika diketahui:          

S = {1,2,3,4,5,6} adalah semesta pembicaraan.

A = {1,2,3}

B = {3,4,5}

bisa dikatakan bahwa:

o   Nilai keanggotaan 2 pada himpunan A, μ_A[2] = 1, karena 2 є A.

o   Nilai keanggotaan 3 pada himpunan A, μ_A[3] = 1, karena 3 є A.

o   Nilai keanggotaan 4 pada himpunan A, μ_A[4] = 0, karena 4 є A.

o   Nilai keanggotaan 2 pada himpunan B, μ_B[2] = 0, karena 2 є B.

o   Nilai keanggotaan 3 pada himpunan B, μ_B[3] = 1, karena 3 є B.

Contoh: Misalkan variabel umur dibagi menjadi 3 kategori, yaitu:

Muda   : umur < 35 tahun  Parobaya   : 35 ≤ umur ≤ 55    Tua  : umur > 55 tahun

Nilai keanggotaan secara grafis, himpunan Muda, Parobaya, dan Tua ini dapat dilihat pada Gambar berikut ini:

Pada Gambar, dapat dijelaskan bahwa:

o   apabila seseorang berusia 34  tahun, maka ia dikatakan Muda (μ_MUDA[34] = 1);

o   apabila seseorang berusia 35 tahun, maka ia dikatakan Tidak Muda (μ_MUDA[35] = 0);

o   apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan Tidak Muda ( μ_MUDA[35 tahun – 1 hari] = 0 );

o   apabila seseorang berusia 35 tahun, maka ia dikatakan Parobaya (μ_PAROBAYA[34] = 0);

o   apabila seseorang berusia 55 tahun, maka ia dikatakan Parobaya (μ_PAROBAYA[55] = 1);

o   apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan Tidak Parobaya μ_PAROBAYA[ 35 tahun – 1 hari ] = 1;

Dari sini bisa dikatakan bahwa pemakaian himpunan crisp untuk menyatakan umur sangat tidak adil, adanya perubahan kecil saja pada suatu nilai mengakibatkan perbedaan kategori yang cukup signifikan.

            Himpunan fuzzy digunakan untuk mengantisipasi hal tersebut. Seseorang dapat masuk dalam 2 himpunan yang berbeda, Muda dan Parobaya, Parobaya dan Tua, dsb. Seberapa besar eksistensinya dalam himpunan tersebut dapat dilihat pada derajat keanggotaannya. Gambar berikut ini menunjukkan himpunan fuzzy utnuk variabel umur.

o   Seseorang yang berumur 40 tahun, termasuk dalam himpunan Muda dengan μ_MUDA[40] = 0,25; namun dia juga termasuk dalam himpunan Parobaya dengan μ_PAROBAYA[40] = 0,5.

o   Seseorang yang berumur 50 tahun, termasuk dalam himpunan Tua dengan μ_TUA[50] = 0,25; namun dia juga termasuk dalam himpunan Parobaya dengan μ_PAROBAYA[50] = 0,5.

Kalau pada himpunan crisp, derajat keanggotaan hanya ada 2 kemungkinan, yaitu 0 atau 1, pada himpunan fuzzy derajat keanggotannnya terletak pada rentang 0 dan 1. Apabila x memiliki derajat keanggotaan fuzzy μ_A[x] = 0 berarti x tidak menjadi anggota himpunan A, demikian pula apabila x memiliki derajat keanggotaan fuzzy μ_A[x] = 1 berarti x menjadi anggota penuh pada himpunan A.