Jumat, 29 Juni 2012

Fuzzy C-Means (FCM)

           Fuzzy  C-Means  (FCM)  merupakan  salah  satu  algoritma  fuzzy  clustering. Fuzzy C-Means (FCM) adalah suatu  teknik pengclusteran data  yang  keberadaan  setiap  titik  data  dalam  suatu  cluster  ditentukan  oleh  derajat  keanggotaan. Teknik ini pertama kali diperkenalkan oleh Jim Bezdek pada tahun 1981.
            Konsep  dasar  FCM  yaitu  menentukan  pusat cluster,  yang  akan  menandai  lokasi  rata-rata  untuk  setiap  cluster. Dengan  cara memperbaiki pusat cluster dan derajat keanggotaan setiap titik data  secara  berulang,  maka  akan  dapat  dilihat bahwa  pusat  cluster  akan  bergerak  menuju lokasi  yang  tepat.  Perulangan  ini  didasarkan pada  pada  minimisasi  fungsi  obyektif  yang menggambarkan  jarak  dari  titik  data  yang diberikan  ke  pusat  cluster  yang  terbobot  oleh derajat  keanggotaan  titik  data  tersebut.
            Output dari FCM bukan merupakan fuzzy inference system, namun merupakan deretan pusat cluster dan beberapa derajat keanggotaan untuk tiap-tiap titik data. Informasi ini dapat digunakan untuk membangun suatu fuzzy inference system.
Algoritma Fuzzy C-means clustering adalah sebagai berikut :
  1. Menentukan:
Matriks X yang merupakan data yang akan dicluster, berukuran k x j, dengan k = jumlah data yang akan di-cluster dan j = jumlah variabel/atribut (kriteria).
 
  1. Menentukan :
a.  Jumlah cluster yang akan dibentuk (n >c ≥ 2).
b.  pembobot (w > 1).
c.  Maksimum iterasi (max n).
d.  Kriteria penghentian/treshold (ɛ = nilai positif yang sangat kecil).
e.  Menentukan fungsi obyektif awal (P0).
  1. Membentuk matriks partisi awal U (derajat keanggotaan dalam cluster) dengan ukuran k x i; matriks partisi biasanya dibuat acak, , dengan k = jumlah data yang akan di-cluster dan i = jumlah cluster
  1. Hitung pusat cluster (V) untuk setiap cluster, menggunakan rumus :
Keterangan :
Vij = pusat cluster pada cluster ke-i dan atribut ke-j.
μik = data partisi (pada matriks U) pada cluster ke-i dan data ke-k.
Xkj = data (pada matriks U) pada atribut ke-j dan data ke-k.
w = pembobot.
  1. Hitung nilai obyektif (Pn) dengan rumus :
Keterangan :
μik = data partisi (pada matriks U) pada cluster ke-i dan data ke-k.
dik = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-i dan data ke-k.
w = pembobot.
Pn = nilai obyektif pada iterasi ke-n.
  1. Perbaiki derajat keanggotaan setiap data pada setiap cluster (perbaiki matriks partisi)
dengan :
Keterangan :
μik = data partisi (pada matriks U) pada pusat cluster ke-i dan data ke-k.
dik = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-i dan data ke-k.
djk = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-j dan data ke-k.
w = pembobot.
Xkj = data (pada matriks U) pada atribut ke-j dan data ke-k.
  1. Menghentikan  iterasi  jika  pusat  cluster  V tidak  berubah.  Alternatif  kriteria penghentian  adalah  jika  perubahan  nilai error kurang dari treshold |Pn - Pn-1| < ɛ. Alternatif adalah ketika perulangan melebihi maksimum iterasi ( n > max n). Jika iterasi belum berhenti, kembali ke langkah 4.
  2. Jika iterasi berhenti, ditentukan cluster dari tiap-tiap data. Cluster dipilih berdasarkan nilai matriks partisi terbesar.

Tidak ada komentar:

Posting Komentar