Fuzzy Subtractive Clustering

            Pengklasteran Subtraktif didasarkan atas ukuran kerapatan  (potensi)  titik-titik  data  dalam  suatu  ruang (variabel). Konsep dasar dari Pengklasteran Subtraktif adalah  menentukan  daerah-daerah  dalam  suatu variabel  yang memiliki  potensi  tinggi  terhadap  titik-titik di  sekitarnya. Titik-titik dengan  jumlah  tetangga terbanyak  akan  dipilih  sebagai  pusat  klaster.  Titik yang sudah terpilih sebagai pusat klaster ini kemudian akan dikurangi potensinya. Kemudian algoritma akan memilih  titik  lain  yang memiliki  tetangga  terbanyak untuk  dijadikan pusat klaster  yang  lain. Hal  ini  akan dilakukan berulang-ulang hingga semua titik diuji.

Algoritma Fuzzy Subtractive clustering adalah sebagai berikut (Kusumadewi, 2010) :

1. Menentukan:

Matriks X yang merupakan data yang akan dicluster, berukuran i x j, dengan i = jumlah data yang akan di-cluster dan j = jumlah variabel/atribut (kriteria).

 

2. Menentukan :

a.  r_j (jari-jari setiap atribut data); j=1,2,..,m.

b.  q (squash factor).

c.  accept ratio .

d.  reject ratio.

e.  Xmin_j (min data yang diperbolehkan dalam setiap atribut data) ; j=1,2,..,m.

f.  Xmax_j (max data yang diperbolehkan dalam setiap atribut data) ; j=1,2,..,m.

3. Normalisasi :

 

i = 1,2,…,n ; j=1,2,..,m

Dimana :

X_ij = data ke-i atribut ke-j.

Xmin_j = minimum data pada atribut ke-j.

Xmax_j = maximum data pada atribut ke-j.

4. Tentukan potensi awal tiap-tiap titik data
1. i = 1; i adalah data ke.
2. Kerjakan hingga i=n,

                                                              i.      T_j = X_ij(T_j merupakan data ke-i atribut ke-j); j=1,2,…,m

                                                            ii.      Hitung :

                                                          iii.      Hitung potensi awal :

Dimana :

D_i merupakan potensi data ke-i

5. Cari titik dengan potensi tertinggi 

           

           

            Dimana :

M adalah titik dengan potensi tertinggi

h adalah posisi titik yang memiliki potensi tertinggi

6. Tentukan pusat cluster dan kurangi potensinya terhadap titik-titik di sekitarnya :
1. Center = []

Center merupakan pusat cluster

2. Vj = Xhj; j=1,2,..,m.

            Vj merupakan nilai normalisasi pada data dengan potensi tertinggi.

3. C = 0

            C merupakan jumlah cluster.

4. Kondisi = 1
5. Z = M

            Z merupakan potensi titik yang diacu sebagai pusat cluster.

6. Kerjakan selama (Kondisi ≠ 0)&(Z ≠ 0)

                                                              i.      Kondisi = 0

                                                            ii.      Rasio = Z/M

                                                          iii.      Jika Rasio > accept ratio, maka kondisi = 1

         Hal ini menandakan ada calon pusat baru.

                                                          iv.      Jika tidak

o   Jika rasio > reject ratio, maka kerjakan :

o   Hal ini menandakan calon baru akan diterima sebagai pusat jika keberadaanya akan memberikan keseimbangan terhadap data-data yang letaknya cukup jauh dengan pusat cluster yang telah ada.

·         Md = -1

·         Kerjakan untuk i=1 sampai i=C:

§ , j=1,2,…,m

§

§ Jika (Md < 0) atau (Sd < Md), maka Md = Sd

·         Smd = √Md

·         Jika (Rasio + Smd) >= 1, maka kondisi = 1

Hal ini berarti data diterima sebagai pusat cluster.

·         Jika (Rasio + Smd) < 1, maka kondisi = 2

Hal ini berarti data tidak akan dipertimbangkan kembali sebagai pusat cluster

o   Jika kondisi = 1, maka kerjakan :

·         C = C + 1

·         Center_c = V

·         Kurangi potensi dari titik-titik di dekat pusat cluster :

§ , i=1,2,…,n; j = 1,2,…,m

§ , i=1,2,…,n

§ D_i = D_i - Dc_i

§ Jika D_i <= 0, maka D_i = 0; i=1,2,…,n

§ Z =

§ h = i, sedemikian hingga D_i = Z

o   Jika kondisi = 2, maka :

·         D_h = 0

·         Z =

·         h = i, sedemikian hingga D_i = Z

7. Kembalikan pusat cluster dari bentuk ternormalisasi ke bentuk semula

           

8. Hitung nilai sigma cluster :

σ_j = r_j * (Xmax_j - Xmin_j)/√8

9. Hitung derajat keanggotaan setiap titik data X_i pada cluster ke-k

           

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).

 

2. 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 (P₀).

3. 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

4. Hitung pusat cluster (V) untuk setiap cluster, menggunakan rumus :

Keterangan :

V_ij = pusat cluster pada cluster ke-i dan atribut ke-j.

μ_ik = data partisi (pada matriks U) pada cluster ke-i dan data ke-k.

X_kj = data (pada matriks U) pada atribut ke-j dan data ke-k.

w = pembobot.

5. Hitung nilai obyektif (P_n) dengan rumus :

Keterangan :

μ_ik = data partisi (pada matriks U) pada cluster ke-i dan data ke-k.

d_ik = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-i dan data ke-k.

w = pembobot.

P_n = nilai obyektif pada iterasi ke-n.

6. 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.

d_ik = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-i dan data ke-k.

d_jk = fungsi ukuran  jarak untuk  jarak Euclidean pada pusat cluster ke-j dan data ke-k.

w = pembobot.

X_kj = data (pada matriks U) pada atribut ke-j dan data ke-k.

7. 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.
8. Jika iterasi berhenti, ditentukan cluster dari tiap-tiap data. Cluster dipilih berdasarkan nilai matriks partisi terbesar.