Implementasi Fuzzy C-Means Clustering dengan Python¶
Pengertian Fuzzy C-Means¶
Penentuan pusat cluster dapat dilakukan dengan menggunakan formula: $ c_j = {{{\sum \limits_{j=1}^{C}} \mu_{ij}^m . x_i} \over {{\sum \limits_{j=1}^{C}} \mu_{ij}^m}} $ , dimana $ c $ adalah kumpulan cluster yang ada, yang akan di iterasi sebanyak jumlah cluster pada $ c_j $. setelah mendapatkan nilai pusat cluster (cendroid), dapat dilanjutkan dengan memperbaharui nilai derajat ke anggotaan dari masing-masing cluster dengan menggunakan formula, yaitu : $ \mu_{ij} ={1 \over \sum \limits_{k=1}^{C} \left ( \frac {| | x_i - c_j | | } {{| | x_i - c_k | | } } \right) ^ { \frac { 2 } { m-1 } }} $
Algoritma Fuzzy C-Means¶
Algoritma perhitungan dapat dilakukan seperti berikut :
- Menentukan jumlah cluster (k)
- Menginisialisasi nilai random darajat ke anggotaan dari masing masing cluster, dimana nilai diantara 0 s/d 1, dan ketika di jumlah sama dengan 1.
- Mencari pusat cluster (cendroid) sebanyak cluster, $ c_j = {{{\sum \limits_{j=1}^{C}} \mu_{ij}^m . x_i} \over {{\sum \limits_{j=1}^{C}} \mu_{ij}^m}} $
- Mengubah nilai derajat ke anggotaan setiap element cluster $ \mu^{(k + 1)} - \mu^{k} $, dengan $ \mu_{ij} ={1 \over \sum \limits_{k=1}^{C} \left ( \frac {| | x_i - c_j | | } {{| | x_i - c_k | | } } \right) ^ { \frac { 2 } { m-1 } }} $
- Ketika jarak $ \mu^{(k + 1)} - \mu^{k} $ kurang dari ambang batas atau iterasi telah sampai pada batas yang telah ditentukan, maka iterasi dapat dihentikan. selain itu kita dapat mengulang dari langkah ke-2.
Implementasi pada Python¶
Pertama yang dapat dilakukan adalah dengan masukkan data yang berbentuk .csv menggunakan library pandas.
import pandas as pd import random import math as mt data = pd.read_csv('cmeans.csv', sep=';') df = pd.DataFrame(data) df.style.hide_index()
Data akan tampil seperti berikut yang berisi tiga fitur, dan dua fitur akan digunakan untuk perhitungan yaitu, Rumah dan Mobil.
| Nama | Rumah | Mobil |
|---|---|---|
| A | 1 | 3 |
| B | 3 | 3 |
| C | 4 | 3 |
| D | 5 | 3 |
| E | 1 | 2 |
| F | 4 | 2 |
| G | 1 | 1 |
| H | 2 | 1 |
Kemudian dapat membuat membuat fungsi buat_mu(X, cluster), yang akan digunakan membuat nilai derajat keanggotaan secara random sebanyak data dan jumlah cluster.
def buat_mu(X,cluster): mu = [] for i in range(len(X)): temp_mu = [] for j in range(cluster): inp=random.randrange(1,10); temp_mu.append(inp/10) mu.append(temp_mu) return mu
Fungsi berikut untuk melakukan normalisasi pada nilai $ \mu $ agar ketika dijumlah berniali 1.
def normalisasi_mu(mu): n_mu = [] for i in range(len(mu)): temp_mu = [] for j in range(len(mu[i])): nilai2 = 0 for k in range(len(mu[i])): if k==j: nilai = mu[i][k] else: nilai2 += mu[i][k] temp_mu.append(round(nilai/(nilai+nilai2), 4)) n_mu.append(temp_mu) return n_mu
Fungsi berikut untuk melakukan perhitungan pada $ \mu_{ij}^m $
def mu_kuadrat(n_mu,m): mu_pow = [] for i in range(len(n_mu)): temp = [] for j in range(len(n_mu[i])): temp.append(round(n_mu[i][j] ** m,4)) mu_pow.append(temp) return mu_pow
Fungsi berikut untuk melakukan perhitungan $ \mu_{ij}^m . x_i $
def mu_kuad_X(jumlah_cluster,X,mu_kuad): mu_kuad_X = [] for i in range(jumlah_cluster): mu_x = [] for j in range(len(X)): temp = [] for k in range(len(X[j])): temp.append(round(X[j][k] * mu_kuad[j][i], 4)) mu_x.append(temp) mu_kuad_X.append(mu_x) return mu_kuad_X
Fungsi berikut untuk melakukan sum/jumlah pada kolom setiap vektor yang dimasukkan.
def jumlah(N): jumlah = [] for i in range(len(N)): temp = [] for j in range(len(N[i])): if i==0: ij = N[i][j] else: ij = jumlah[i-1][j] + N[i][j] temp.append(ij) jumlah.append(temp) return jumlah[-1]
Fungsi berikut untuk mendapatkan nilai pusat cluster (cendroid) dari masing-masing cluster. perhitungan yang dilakukan adalah dengan menggabungkan fungsi yang telah di definisikan diatas, yang merupakan implementasi dari formula $ c_j = {{{\sum \limits_{j=1}^{C}} \mu_{ij}^m . x_i} \over {{\sum \limits_{j=1}^{C}} \mu_{ij}^m}} $
def getCentroid(U,mu_kuad_X): SUM_C = jumlah(U) centroid = [] for i in range(jumlah_cluster): temp = [] SUM_U = jumlah(mu_kuad_X[i]) for j in range(len(jumlah(mu_kuad_X[i]))): temp.append(SUM_U[j] / SUM_C[i]) centroid.append(temp) return centroid
Fungsi berikut merupakan metode perhitungan jarak Mahatan Distance yang didefinisikan dengan $d _ { \operatorname { man } } = \sum _ { i = 1 } ^ { n } \left| x _ { i } - y _ { i } \right| $
def manhatan_dist(x=[],y=[]): dist = 0 for i in range(len(x)): dist += round(abs(x[i] - y[i]),4) return dist
dan fungsi berikut juga merupakan metode perhitungan jarak Euclidian Distance yang didefinisikan dengan $ d_(x,y) =\sqrt{ \sum _ { i = 1 } ^ { n } \left( x _ { i } - y _ { i } \right)^2} $
def euclidian_dist(x=[],y=[]): dist = 0 for i in range(len(x)): dist += (x[i] - y[i]) ** 2 return round(mt.sqrt(dist),2)
untuk dapat melakukan perubahan nilai derajat ke anggotaan, maka dibuat fungsi update_U() dengan parameter n_mu adalah derajat ke anggotaan $ \mu $, jumlah cluster, data, dan pusat cluster. fungsi tersebut merupakan implementasi dari formula, $ \mu_{ij} ={1 \over \sum \limits_{k=1}^{C} \left ( \frac {| | x_i - c_j | | } {{| | x_i - c_k | | } } \right) ^ { \frac { 2 } { m-1 } }} $
def update_U(n_mu,jumlah_cluster,X,centroid): U = [] for i in range(len(n_mu)): temp = [] for j in range(len(n_mu[i])): penyebut = 0 for k in range(jumlah_cluster): pembilang = euclidian_dist(X[i],centroid[j]) penyebut += euclidian_dist(X[i],centroid[k]) hasil = pembilang/penyebut hasil = round(1/(hasil ** (2/(m-1))),4) temp.append(hasil) U.append(temp) return U
Kemudian kita dapat membuat fungsi utama yaitu, Fuzzy_CMeans(X, jumlah_cluster, m, max_iter, threshold) yang akan melakukan komputasi berdasarkan algoritma yang telah ditentukan diatas. dan akan berhenti ketika telah nilai fungsi objectif kurang dari nilai ambang batas, atau iterasi telah mencapat batas yang telah ditentukan.
def Fuzzy_CMeans(X, jumlah_cluster, m, max_iter, threshold): mu = buat_mu(X, jumlah_cluster) N_mu = normalisasi_mu(mu) iterasi = 0 stop = True while iterasi < max_iter and stop: N = N_mu print('Iterasi', iterasi) centroid = getCentroid(N_mu, mu_kuad_X(jumlah_cluster, X, mu_kuadrat(N_mu, m))) U = update_U(N_mu, jumlah_cluster, X, centroid) N_mu = normalisasi_mu(U) iterasi +=1 if manhatan_dist(jumlah(N_mu), jumlah(N)) < threshold: print('berhenti') stop = False print(pd.DataFrame(N_mu))
dan terakhir kita dapat memanggil fungsi Fuzzy_CMeans() diatas dengan menentukan jumlah cluster adalah 3, memberikan data yang akan dicluster yang berisi dua fitur yang disimpan pada variable X, memberikan nilai m=2, nilai ambang batas adalah 0.1 dan maksimal iterasi adalah 100 kali.
data2 = data.drop("Nama", axis=1) X = data2.values m = 2 threshold = 0.1 max_iter = 100 jumlah_cluster = 3 Fuzzy_CMeans(X, jumlah_cluster, m, max_iter, threshold)
Maka akan mengembalikan hasil seperti berikut:
Iterasi 0 0 1 2 0 0.3006 0.4336 0.2658 1 0.3419 0.4051 0.2530 2 0.3500 0.3839 0.2661 3 0.3510 0.3711 0.2780 4 0.2595 0.5347 0.2058 5 0.3633 0.3782 0.2585 6 0.3198 0.5441 0.1360 7 0.4481 0.3969 0.1550 Iterasi 1 0 1 2 0 0.3275 0.3870 0.2855 1 0.3390 0.3752 0.2858 2 0.3414 0.3642 0.2944 3 0.3403 0.3571 0.3025 4 0.3185 0.4347 0.2468 5 0.3441 0.3638 0.2921 6 0.0713 0.9094 0.0193 7 0.3667 0.4039 0.2294 Iterasi 2 0 1 2 0 0.3297 0.3686 0.3017 1 0.3342 0.3625 0.3032 2 0.3349 0.3554 0.3097 3 0.3362 0.3498 0.3140 4 0.3241 0.3994 0.2765 5 0.3373 0.3544 0.3083 6 0.1465 0.7976 0.0559 7 0.3444 0.3869 0.2687 Iterasi 3 0 1 2 0 0.3287 0.3569 0.3144 1 0.3314 0.3519 0.3167 2 0.3313 0.3475 0.3211 3 0.3327 0.3444 0.3229 4 0.3239 0.3770 0.2991 5 0.3330 0.3475 0.3194 6 0.2066 0.6590 0.1344 7 0.3314 0.3703 0.2983 Iterasi 4 0 1 2 0 0.3292 0.3474 0.3234 1 0.3310 0.3443 0.3247 2 0.3303 0.3427 0.3269 3 0.3323 0.3396 0.3281 4 0.3255 0.3592 0.3153 5 0.3313 0.3414 0.3273 6 0.2711 0.4940 0.2350 7 0.3268 0.3575 0.3157 Iterasi 5 0 1 2 0 0.3303 0.3423 0.3274 1 0.3311 0.3399 0.3290 2 0.3322 0.3374 0.3304 3 0.3324 0.3367 0.3310 4 0.3296 0.3459 0.3245 5 0.3320 0.3380 0.3300 6 0.3138 0.3936 0.2925 7 0.3313 0.3431 0.3256 Iterasi 6 berhenti 0 1 2 0 0.3314 0.3373 0.3314 1 0.3319 0.3362 0.3319 2 0.3351 0.3333 0.3316 3 0.3333 0.3348 0.3319 4 0.3298 0.3405 0.3298 5 0.3320 0.3320 0.3360 6 0.3234 0.3015 0.3751 7 0.3392 0.3276 0.3333
Claster data tersebut dapat ditentukan dengan nilai derajat ke anggota tertinggi pada masing-masing cluster.