fuzzy clustering

Fuzzy ClusteringSistem Berbasis FuzzyMateri 5

Eko PrasetyoTeknik Informatika

Universitas Muhammadiyah Gresik2012

2

Konsep Clustering Klasifikasi melakukan pengelompokan data dimana setiap data

sudah ada label kelasnya◦ Shingga pekerjaan berikutnya adalah membuat model untuk dapat

melakukan prediksi pada data baru yang kemudian muncul untuk diketahui kelasnya.

Clustering (pengelompokan) melakukan pemisahan/pemecahan/segmentasi data kedalam sejumlah cluster (kelompok) menurut karakteristik tertentu yang diinginkan. ◦ Dalam pekerjaan clustering label dari setiap data belum diketahui, ◦ Diharapkan nantinya dapat diketahui kelompok data untuk kemudian

diberikan label sesuai keinginan. Bidang penerapan teknik clustering: kedokteran, kesehatan,

psikologi, hukum, statistik, astronomi, klimatologi dan sebagainya. ◦ Kedokteran, teknik clustering dapat digunakan untuk mengelompokkan

jenis-jenis penyakit berbahaya berdasarkan karakteristik / sifat-sifat penyakit pasien.

◦ Kesehatan, dapat digunakan untuk mengelompokkan jenis-jenis makanan berdasarkan kandungan kalori, vitamin, protein.

3

Konsep Clustering Cluster analysis adalah pekerjaan yang

mengelompokkan data (obyek) yang didasarkan hanya pada informasi yang ditemukan dalam data yang menggambarkan obyek tersebut dan hubungan diantaranya (Tan, 2006).

Tujuan: agar obyek-obyek yang bergabung dalam sebuah kelompok (cluster) merupakan obyek-obyek yang mirip (atau berhubungan) satu sama lain dan berbeda (atau tidak berhubungan) dengan obyek dalam kelompok yang lain.

Lebih besar kemiripannya (atau homogenitasnya) dalam kelompok dan lebih besar perbedaannya diantara kelompok yang lain, konsep ini yang dibahas dalam clustering.

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

0 2 4 6 80

2

4

6

8

Data asli

Dua cluster

Tiga cluster

Empat cluster

4

Fuzzy C-Means Clustering dengan metode Fuzzy C-Means (FCM) didasarkan

pada teori logika fuzzy. Dalam teori fuzzy

◦ Keanggotaan sebuah data tidak diberikan nilai secara tegas dengan nilai 1 (menjadi anggota) dan 0 (tidak menjadi anggota) melainkan dengan suatu nilai derajat keanggotaan yang jangkauan nilainya 0 sampai 1.

Nilai keanggotaan suatu data dalam sebuah cluster:◦ Menjadi 0 ketika sama sekali tidak menjadi anggota cluster, ◦ Menjadi 1 ketika menjadi anggota secara penuh dalam suatu cluster. ◦ Nilai keangotaannya antara 0 dan 1. ◦ Semakin tinggi nilai keanggotaannya maka semakin tinggi derajat

keanggotaannya, dan semakin kecil maka semakin rendah derajat keanggotaannya.

Kaitannya dengan K-Means, FCM merupakan versi fuzzy dari K-Means dengan beberapa modifikasi yang membedakannya dengan K-Means.

5

Fuzzy C-Means Asumsikan ada sejumlah data dalam data set (X) yang berisi m

data: x1, x2, ..., xm, dinotasikan X = { x1, x2, ..., xn }, ◦ dimana setiap data mempunyai fitur n dimensi: xi1, xi2, …, xin,

dinotasikan xi = { xi1, xi2, …, xin }. Ada sejumlah cluster C dengan centroid: c1, c2, …, ck, dimana k

adalah jumlah cluster. Setiap data mempunyai derajat keanggotaan pada setiap cluster,

◦ dinyatakan dengan uij, dengan nilai diantara 0 dan 1, ◦ i menyatakan data xi dan j menyatakan cluster cj. ◦ Jumlah nilai derajat keanggotaan setiap data xi selalu sama dengan 1,

diformulasikan:

Untuk setiap cluster cj, berisi paling sedikit satu data dengan nilai keanggotaan tidak nol, tapi tidak berisi derajat satu pada semua data, diformulasikan: mu

m

iij

10

11

k

jiju

6

Fuzzy C-Means Dalam FCM, setiap data juga menjadi anggota pada setiap cluster dengan

derajat keanggotaan uij. ◦ Nilai keanggotaan data xi pada cluster vj, diformulasikan:

◦ Parameter cj adalah centroid cluster ke-j, D() adalah jarak antara data dengan centroid.

◦ Sedangkan w adalah parameter bobot pangkat (Weighting Exponent) yang diperkenalkan dalam FCM, tidak ada nilai ketetapan, biasanya nilai w > 1, dan umumnya diberi nilai 2.

Untuk menghitung centroid pada cluster ci pada fitur j, digunakan formula:

◦ Parameter M adalah jumlah data, w adalah bobot pangkat, dan uil adalah nilai derajat keanggotaan data xl ke cluster ci.

Fungsi obyektif yang digunakan:

k

l

wli

wji

ij

cxD

cxDu

1

12

12

),(

),(

M

l

wil

M

llj

wil

iju

xuc

1

1

)(

)(

M

i

k

jji

wij cxDuJ

1 1

2,)(

7

Algoritma FCM1. Tentukan inisialisasi:

◦ jumlah cluster, bobot pangkat, iterasi maksimal, threshold perubahan fungsi obyektif.

2. Berikan nilai keanggotaan setiap data pada setiap cluster secara acak.

3. Hitung centroid/rata-rata setiap cluster4. Lakukan langkah 5 dan 6, jika:

◦ perubahan nilai pada fungsi obyektif yang digunakan di atas nilai threshold yang ditentukan, atau

◦ iterasi maksimal belum tercapai, atau◦ perubahan nilai centroid ada yang di atas nilai threshold

yang ditentukan, atau 5. Hitung nilai keanggotaan masing-masing data ke

semua centroid.6. Hitung centroid/rata-rata setiap cluster.

8

Contoh Dataset dengan 2 fitur: X dan Y. Jumlah record data = 6 Di-cluster dengan FCM: C=2. Bobot pangkat (w) = 2. Threshold perubahan nilai fungsi obyektif = 0.01

Data ke-i

Fitur X Fitur Y

1 1 12 4 13 6 14 1 25 2 36 5 3 0 2 4 6 8

0

2

4

6

9

C = 2w = 2MaxIter = 10T = 0.01pangkat = -2/(w-1) = -2

InisialisasiData X Y

1 1 12 4 13 6 14 1 25 2 36 5 3

u1 u2 0.6667 0.3333 0.8750 0.1250 0.3333 0.6667 0.8750 0.1250 0.8000 0.2000 0.1818 0.8182

u1^w u1^w * X u1^w * Y u2^w u2^w * X u2^w * Yu1^w*D^

2u2^w*D^

2 0.4444 0.4444 0.4444 0.1111 0.1111 0.1111 - - 0.7656 3.0625 0.7656 0.0156 0.0625 0.0156 - - 0.1111 0.6667 0.1111 0.4444 2.6667 0.4444 - - 0.7656 0.7656 1.5313 0.0156 0.0156 0.0313 - - 0.6400 1.2800 1.9200 0.0400 0.0800 0.1200 - - 0.0331 0.1653 0.0992 0.6694 3.3471 2.0083 - -

Jumlah 2.7599 6.3845 4.8716 1.2962 6.2830 2.7307 - - X1 Y1 X2 Y2 Obj -

Centroid C1 2.313348 1.765161 Centroid C2 4.847153 2.106649 Selisih 0

0 2 4 6 80

2

4

6

10

Iterasi 1Data X Y

1 1 12 4 13 6 14 1 25 2 36 5 3

D D^pangkatC1 C2 C1 C2 sum u1 u21.5200 4.0032 0.4328 0.0624 0.4952 0.8740 0.1260 1.8521 1.3937 0.2915 0.5148 0.8064 0.3615 0.6385 3.7652 1.5980 0.0705 0.3916 0.4621 0.1526 0.8474 1.3342 3.8486 0.5618 0.0675 0.6293 0.8927 0.1073 1.2740 2.9840 0.6161 0.1123 0.7284 0.8458 0.1542 2.9568 0.9063 0.1144 1.2174 1.3318 0.0859 0.9141

u1^w u1^w * X u1^w * Y u2^w u2^w * X u2^w * Y u1^w*D^2 u2^w*D^2 0.7639 0.7639 0.7639 0.0159 0.0159 0.0159 1.7648 0.2544 0.1307 0.5228 0.1307 0.4076 1.6306 0.4076 0.4483 0.7918 0.0233 0.1398 0.0233 0.7180 4.3081 0.7180 0.3303 1.8336 0.7969 0.7969 1.5939 0.0115 0.0115 0.0230 1.4186 0.1705 0.7154 1.4309 2.1463 0.0238 0.0475 0.0713 1.1611 0.2116 0.0074 0.0369 0.0221 0.8356 4.1780 2.5068 0.0645 0.6864 2.4376 3.6911 4.6802 2.0124 10.1917 3.7427 5.1877 3.9484

X1 Y1 X2 Y2 Obj 9.1361 Centroid C1 1.5142 1.9200 Centroid C2 5.0644 1.8598 Selisih 9.1361

0 2 4 6 80

2

4

6


k

lwli

wjiij

cxD

cxDu

112

12

),(

),(

M

l

wil

M

llj

wil

iju

xuc

1

1

)(

)(

M

i

k

jji

wij cxDuJ

1 1

2,)(

11

Iterasi 2Data X Y

1 1 12 4 13 6 14 1 25 2 36 5 3


u1^w u1^w * X u1^w * Y u2^w u2^w * X u2^w * Y u1^w*D^2 u2^w*D^2 0.8827 0.8827 0.8827 0.0037 0.0037 0.0037 0.9805 0.0631 0.0443 0.1771 0.0443 0.6235 2.4938 0.6235 0.3110 1.1672 0.0051 0.0307 0.0051 0.8621 5.1727 0.8621 0.1072 1.3920 0.9680 0.9680 1.9361 0.0003 0.0003 0.0005 0.2622 0.0043 0.7815 1.5630 2.3445 0.0134 0.0269 0.0403 1.0960 0.1438 0.0080 0.0398 0.0239 0.8296 4.1478 2.4887 0.1060 1.0819

Jumlah 2.6896 3.6613 5.2366 2.3325 11.8451 4.0188 2.8629 3.8523 X1 Y1 X2 Y2 Obj 6.7152

Centroid C1 1.3613 1.9470 Centroid C2 5.0783 1.7229 Selisih 2.420876 0 2 4 6 80

2

4

6


k

lwli

wjiij

cxD

cxDu

112

12

),(

),(

M

l

wil

M

llj

wil

iju

xuc

1

1

)(

)(

M

i

k

jji

wij cxDuJ

1 1

2,)(

12

Iterasi 3Data X Y

1 1 12 4 13 6 14 1 25 2 36 5 3



Jumlah 2.6935 3.6198 5.2470 2.3894 12.1004 4.0297 2.6900 3.8962 X1 Y1 X2 Y2 Obj 6.5863

Centroid C1 1.3439 1.9480 Centroid C2 5.0643 1.6865 Selisih 0.1289040 2 4 6 80

2

4

6


k

lwli

wjiij

cxD

cxDu

112

12

),(

),(

M

l

wil

M

llj

wil

iju

xuc

1

1

)(

)(

M

i

k

jji

wij cxDuJ

1 1

2,)(

13

Iterasi 4Data X Y

1 1 12 4 13 6 14 1 25 2 36 5 3



Jumlah 2.6903 3.6080 5.2422 2.3990 12.1360 4.0245 2.6713 3.9094 X1 Y1 X2 Y2 Obj 6.5807

Centroid C1 1.3411 1.9486 Centroid C2 5.0587 1.6775 Selisih 0.0056 0 2 4 6 80

2

4

6


k

lwli

wjiij

cxD

cxDu

112

12

),(

),(

M

l

wil

M

llj

wil

iju

xuc

1

1

)(

)(

M

i

k

jji

wij cxDuJ

1 1

2,)(

14

ANY QUESTIONS ?

fuzzy clustering

Documents