Information Retrieval : Metode Clustering K-Means

Sunday, January 16, 2011

1.      Pendahuluan
K-Means merupakan salah satu metode data clustering 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. Tujuan dari data clustering ini adalah untuk meminimalisasikan objective function yang diset dalam peroses clustering, yang pada umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan memaksimalkan variasi antar cluster.
Dasar Algoritma K-Means:
1. Tentukan jumlah cluster yang akan dibentuk.
2. Bangkitkan titik pusat klaster(centroid) awal secara random.
3. Hitung jarak setiap data ke masing-masing centroid(menggunakan euclidean distance space)
4. Kelompokkan setiap data berdasarkan jarak terdekat antara data dengan centroid.
5. Tentukan posisi centroid  baru.
6. Kembali ke langkah 3 jika posisi centroid baru tidak sama dengan centroid lama. 



2.      Penerapan K-Means
Beberapa alternatif penerapan K-Means dengan beberapa pengembangan teori-teori penghitungan terkait telah diusulkan. Hal ini termasuk pemilihan:
1. Distance space untuk menghitung jarak di antara suatu data dan centroid
2. Metode pengalokasian data kembali ke dalam setiap cluster
3. Objective function yang digunakan.
2.1.     Distance Space Untuk Menghitung Jarak Antara Data dan Centroid
Beberapa distance space telah diimplementasikan dalam menghitung jarak (distance) antara data dan centroid termasuk di antaranya L1 (Manhattan/City Block) distance space, L2 (Euclidean) distance space, dan Lp (Minkowski) distance space. Jarak antara dua titik x1 dan x2 pada Manhattan/City Block distance space dihitung dengan menggunakan rumus sebagai berikut :
dimana :
p : Dimensi data
| . | : Nilai absolute

Sedangkan untuk L2 (Euclidean) distance space, jarak antara dua titik dihitung menggunakan rumus sebagai berikut :
dimana :
p : Dimensi data

Lp (Minkowski) distance space yang merupakan generalisasi dari beberapa distance space yang ada seperti L1 (Manhattan/City Block) dan L2 (Euclidean), juga telah diimplementasikan. Tetapi secara umum distance space yang sering digunakan adalah Manhattan dan Euclidean.
2.2.     Metode Pengalokasian Ulang Data ke Dalam Masing-Masing Cluster
Ada dua cara pengalokasian data kembali ke dalam masing-masing cluster pada saat proses iterasi clustering, yaitu :
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:
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, 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 :
dimana:
u ik : Membership function data ke-k ke cluster ke-i
v i : Nilai centroid cluster ke-i
m : Weighting Exponent


2.3.         Objective Function Yang Digunakan
Objective function yang digunakan khususnya untuk Hard K-Means dan Fuzzy K-Means ditentukan berdasarkan pada pendekatan yang digunakan dalam poin 2.1. dan poin 2.2. Untuk metode Hard K-Means, objective function yang digunakan adalah sebagai berikut :
         dimana:
   N : Jumlah data
   c : Jumlah cluster
   a ik : Keanggotaan data ke-k ke cluster ke-i
   v i : Nilai centroid cluster ke-i
 a ik  mempunyai nilai 0 atau 1. Apabila suatu data merupakan anggota suatu       kelompok maka nilai a ik =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
u ik : Membership function data ke-k ke cluster ke-i
v i : Nilai centroid cluster ke-i
Di sini u ik bisa mengambil nilai mulai dari 0 sampai 1.

3.      Beberapa Permasalahan yang Terkait Dengan K-Means
Beberapa permasalahan yang sering muncul pada saat menggunakan metode K-Means untuk melakukan pengelompokan data adalah:
1. Ditemukannya beberapa model clustering yang berbeda
2. Pemilihan jumlah cluster yang paling tepat
3. Kegagalan untuk converge
4. Pendeteksian outliers
5. Bentuk masing-masing cluster
6. Masalah overlapping.

Permasalahan 1 umumnya disebabkan oleh perbedaan proses inisialisasi anggota masing-masing cluster. Permasalahan 2 merupakan masalah laten dalam metode K-Means. Beberapa pendekatan telah digunakan dalam menentukan jumlah cluster yang paling tepat untuk suatu dataset yang dianalisa termasuk di antaranya Partition Entropy (PE) dan GAP Statistics. Satu hal yang patut diperhatikan mengenai metode-metode ini adalah pendekatan yang digunakan dalam mengembangkan metode-metode tersebut tidak sama dengan pendekatan yang digunakan oleh K-Means dalam mempartisi data items ke masing-masing cluster.
Permasalahan kegagalan untuk converge, kemungkinan besar akan terjadi untuk metode Hard K-Means, karena setiap data di dalam dataset dialokasikan secara tegas (hard) untuk menjadi bagian dari suatu cluster tertentu. Perpindahan suatu data ke suatu cluster tertentu dapat mengubah karakteristik model clustering yang dapat menyebabkan data yang telah dipindahkan tersebut lebih sesuai untuk berada di cluster semula sebelum data tersebut dipindahkan.
Permasalahan keempat, beberapa hal yang perlu diperhatikan dalam melakukan pendeteksian outliers dalam proses pengelompokan data termasuk bagaimana menentukan apakah suatu data item merupakan outliers dari suatu cluster tertentu dan apakah data dalam jumlah kecil yang membentuk suatu cluster tersendiri dapat dianggap sebagai outliers.
Permasalahan kelima, K-Means umumnya tidak mengindahkan bentuk dari masing-masing cluster yang mendasari model yang terbentuk, walaupun secara natural masing-masing cluster umumnya berbentuk bundar. Untuk dataset yang diperkirakan mempunyai bentuk yang tidak biasa, beberapa pendekatan perlu untuk diterapkan.
Masalah overlapping sebagai permasalahan terakhir sering sekali diabaikan karena umumnya masalah ini sulit terdeteksi. Hal ini terjadi untuk metode Hard K-Means dan Fuzzy K-Means, karena secara teori, metode ini tidak diperlengkapi feature untuk mendeteksi apakah di dalam suatu cluster ada cluster lain yang kemungkinan tersembunyi.


Pesan Sponsor:
  •  +1 jika artikel ini bermanfaat
  • Reactions jika tidak sempat tulis comment
  • Budayakan menulis Comment :D
 
Copyright © 2016. syamsularies.
Design by Herdiansyah Hamzah. & Distributed by Free Blogger Templates
Creative Commons License