K-MEANS CLUSTERING


Data Clustering merupakan salah satu metode Data Mining yang bersifat tanpa arahan (unsupervised). Ada dua jenis data clustering yang sering dipergunakan dalam proses pengelompokan data yaitu hierarchical (hirarki) data clustering dan non-hierarchical (non hirarki) data clustering. K-Means merupakan salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster/kelompok. Metode ini mempartisi data ke dalam cluster/kelompok sehingga data yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam kelompok yang lain. Adapun tujuan dari data clustering ini adalah untuk meminimalisasikan objective function yang diset dalam proses clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalisasikan variasi antar cluster.

 

Data clustering menggunakan metode K-Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut:

  1. Tentukan jumlah cluster
  2. Alokasikan data ke dalam cluster secara random
  3. Hitung centroid/rata-rata dari data yang ada di masing-masing cluster
  4. Alokasikan masing-masing data ke centroid/rata-rata terdekat
  5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan di atas nilai threshold yang ditentukan

 

distance space, jarak antara dua titik dihitung menggunakan rumus sebagai berikut

dimana:

p : Dimensi data

 

Metode Pengalokasian Ulang Data ke Dalam Masing-Masing Cluster

Secara mendasar, ada dua cara pengalokasian data kembali ke dalam masing-masing cluster pada saat proses iterasi clustering. Kedua cara tersebut adalah pengalokasian dengan cara tegas (hard), dimana data item secara tegas dinyatakan sebagai anggota cluster yang satu dan tidak menjadi anggota cluster lainnya, dan dengan cara fuzzy, dimana masing-masing data item diberikan nilai kemungkinan untuk bisa bergabung ke setiap cluster yang ada. Kedua cara pengalokasian tersebut diakomodasikan pada dua metode Hard K-Means[6] dan Fuzzy K-Means[3,8,9]. Perbedaan di antara kedua metode ini terletak pada asumsi yang dipakai sebagai dasar pengalokasian.

 

Hard K-Means

Pengalokasian kembali data ke dalam masing-masing cluster dalam metode Hard K-Means

didasarkan pada perbandingan jarak antara data dengan centroid setiap cluster yang ada.

Data dialokasikan ulang secara tegas ke cluster yang mempunyai centroid terdekat dengan

data tersebut. Pengalokasian ini dapat dirumuskan sebagai berikut[6]:

dimana:

aik : Keanggotaan data ke-k ke cluster ke-i

vi : Nilai centroid cluster ke-i

 

Fuzzy K-Means

Metode Fuzzy K-Means (atau lebih sering disebut sebagai Fuzzy C-Means) mengalokasikan kembali data ke dalam masing-masing cluster dengan memanfaatkan teori Fuzzy. Teori ini mengeneralisasikan metode pengalokasian yang bersifat tegas (hard) seperti yang digunakan pada metode Hard K-Means. Dalam metode Fuzzy K-Means dipergunakan variable membership function, uik , yang merujuk pada seberapa besar kemungkinan suatu data bisa menjadi anggota ke dalam suatu cluster. Pada Fuzzy K-Means yang diusulkan oleh Bezdek[3], diperkenalkan juga suatu variabel m yang merupakan weighting exponent dari membership function. Variabel ini dapat mengubah besaran pengaruh dari membership function, uik , dalam proses clustering menggunakan metode Fuzzy K-Means. m mempunyai wilayah nilai m>1. Sampai sekarang ini tidak ada ketentuan yang jelas berapa besar nilai m yang optimal dalam melakukan proses optimasi suatu permasalahan clustering. Nilai m yang umumnya digunakan adalah 2.

 

Membership function untuk suatu data ke suatu cluster tertentu dihitung menggunakan rumus sebagai berikut[3,8,9]:

dimana:

uik : Membership function data ke-k ke cluster ke-i

v I : Nilai centroid cluster ke-i

m : Weighting Exponent

Membership function, uik , mempunyai wilayah nilai 0≤ uik ≤1. Data item yang mempunyai tingkat kemungkinan yang lebih tinggi ke suatu kelompok akan mempunyai nilai membership function ke kelompok tersebut yang mendekati angka 1 dan ke kelompok yang lain mendekati angka 0.

 

Objective Function Yang Digunakan

Untuk metode Hard K-Means, objective function yang digunakan adalah sebagai berikut[6]:

dimana:

N : Jumlah data

c : Jumlah cluster

aik : Keanggotaan data ke-k ke cluster ke-i

vi : Nilai centroid cluster ke-i

 

aik mempunyai nilai 0 atau 1. Apabila suatu data merupakan anggota suatu kelompok maka

nilai aik =1 dan sebaliknya. Untuk metode Fuzzy K-Means, objective function yang

digunakan adalah sebagai berikut :

dimana:

N : Jumlah data

c : Jumlah cluster

m : Weighting exponent

uik : Membership function data ke-k ke cluster ke-i

vi : Nilai centroid cluster ke-i

 

Algoritma K-Means

Hard K-Means

Metode Hard K-Means melakukan proses clustering dengan mengikuti algoritma sebagai berikut[6]:

a. Tentukan jumlah cluster

b. Alokasikan data sesuai dengan jumlah cluster yang ditentukan

c. Hitung nilai centroid masing-masing cluster

d. Alokasikan masing-masing data ke centroid terdekat

e. Kembali ke Step c. apabila masih terdapat perpindahan data dari satu cluster ke cluster yang lain, atau apabila perubahan pada nilai centroid masih di atas nilai threshold yang ditentukan, atau apabila perubahan pada nilai objective function masih di atas nilai threshold yang ditentukan.

 

Untuk menghitung centroid cluster ke-i, vi, digunakan rumus sebagai berikut:

dimana:

Ni : Jumlah data yang menjadi anggota cluster ke-i

 

Fuzzy K-Means

Metode Fuzzy K-Means melakukan proses clustering dengan mengikuti algoritma sebagai berikut :

a. Tentukan jumlah cluster

b. Alokasikan data sesuai dengan jumlah cluster yang ditentukan

c. Hitung nilai centroid dari masing-masing cluster

d. Hitung nilai membership function masing-masing data ke masing-masing cluster

e. Kembali ke Step c. apabila perubahan nilai membership function masih di atas nilai threshold yang ditentukan, atau apabila perubahan pada nilai centroid masih di atas nilai threshold yang ditentukan, atau apabila perubahan pada nilai objective function masih di atas nilai threshold yang ditentukan.

 

Untuk menghitung centroid cluster ke-i, vi , digunakan rumus sebagai berikut:

 

dimana:

N : Jumlah data

m : Weighting exponent

uik : Membership function data ke-k ke cluster ke-i

Sedangkan untuk menghitung membership function data ke-k ke cluster ke-i digunakan

rumus pada persamaan (4).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: