Analisis Cluster dengan Menggunakan metode K-Means dan K-Medoids

Penulis: Siswanto

Data mining merupakan proses pengekstrakan informasi dari jumlah kumpulan data yang besar dengan menggunakan algoritma dan teknik gambar dari statistik, mesin pembelajaran dan sistem manajemen database. Data mining disebut juga Knowledge-Discovery in Database (KDD) adalah sebuah proses secara otomatis atas pencarian data di dalam sebuah memori yang amat besar dari data untuk mengetahui pola dengan menggunakan alat seperti klasifikasi, hubungan (association) atau pengelompokan (clustering).

Clustering adalah pengelompokan sejumlah besar obyek berdasarkan ciri atau atribut tertentu ke dalam sejumlah kelompok atau cluster. Dengan clustering, dan dengan menggunakan algoritma clustering, sejumlah obyek yang memiliki nilai parameter yang mendekati sama akan dikelompokkan. Tujuan dari pengelompokan bisa untuk berbagai keperluan, salah satunya adalah untuk keperluan pengenalan pola dimana setelah data dikelompokkan, akan lebih mudah melakukan analisa selanjutnya untuk mengenali secara lebih rinci pola-pola yang dimiliki oleh suatu kumpulan obyek. Pada tulisan ini akan difokuskan mengenai clustering dengan menggunakan algoritma K-Means dan algoritma K-Medoids.

Algoritma K-Means

Algoritma K-Means merupakan algoritma yang relatif sederhana untuk mengklasifikasikan atau mengelompokkan sejumlah besar obyek dengan atribut tertentu ke dalam kelompok-kelompok sebanyak K. K-Means salah satu metode data clustering non hirarki yang berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster atau kelompok. Algoritma K-Means pertama kali diperkenalkan oleh MacQueen JB pada tahun 1976. Pada algoritma K-Means jumlah cluster K telah ditentukan terlebih dahulu.

Kelebihan Algoritma K-Means diantaranya adalah mampu mengelompokkan objek besar dan pencilan obyek dengan sangat cepat sehingga mempercepat proses pengelompokan. Adapun kekurangan yang dimiliki oleh K-Means sangat sensitif pada pembangkitan titik pusat awal secara random, hasil pengelompokan bersifat tidak unik (selalu berubah-ubah), Algoritma K-Means walaupun proses pengerjaannya cepat tetapi keakuratannya tidak dijamin.

Cara kerja algoritma K-Means:

1. Tentukan K sebagai jumlah cluster yang ingin dibentuk,
2. Bangkitkan K centroid (titik pusat cluster) awal secara random
   Dalam menentukan buah pusat cluster awal dilakukan pembangkitan bilangan random yang merepresentasikan urutan data input. Pusat awal cluster didapatkan dari data sendiri bukan dengan menentukan titik baru, yaitu dengan merandom pusat awal dari data.
3. Hitung jarak setiap data ke masing-masing centroids
   Untuk mengukur jarak antara data dengan pusat cluster digunakan Euclidian Distance.
   Algoritma perhitungan jarak data dengan pusat cluster
   1. Ambil nilai data dan nilai pusat cluster
   2. Hitung Euclidian distance data dengan tiap pusat cluster

Euclidian Distance: merupakan jarak yang didapat dari perhitungan antara semua N data dengan K centroid dimana akan memperoleh tingkat kedekatan dengan kelas yang terdekat dengan populasi data tersebut. Jarak euclidian untuk menandai adanya persamaan antar tiap cluster dengan jarak minimum dan mempunyai persamaan yang lebih tinggi. Euclidian matrik antara titik adalah

dengan

4.  Setiap data memilih centroids yang terdekat,

Jarak hasil perhitungan akan dilakukan perbandingan dan dipilih jarak terdekat antara data dengan pusat cluster, jarak ini menunjukkan bahwa data tersebut berada dalam satu kelompok dengan pusat cluster terdekat.
5. Tentukan posisi centroids yang baru dengan cara menghitung nilai rata-rata dari data-data yang terletak pada centroid yang sama,
Pusat cluster yang baru digunakan untuk melakukan iterasi selanjutnya, jika hasil yang didapatkan belum konvergen. Proses iterasi akan berhenti jika telah memenuhi maksimum iterasi yang dimasukkan oleh User atau hasil yang dicapai sudah konvergen (pusat cluster baru sama dengan pusat cluster lama).
6. Kembali ke langkah 3 jika posisi centroids baru dengan centroids yang lama tidak sama.

Flowchart K-Means

Algoritma K-Medoids

Dalam metode K-medoid setiap cluster dipresentasikan dari sebuah objek di dalam cluster yang disebut dengan medoid. Tujuannya adalah menemukan kelompok K-cluster (jumlah cluster) diantara semua objek data di dalam sebuah kelompok data. Clusternya dibangun dari hasil mencocokkan setiap objek data yang paling dekat dengan cluster yang dianggap sebagai medoid sementara. Langkah-langkah menghitung medoids, yaitu:

1. Pilih point k sebagai inisial centroid/nilai tengah (medoids) sebanyak k cluster.
2. Cari semua point yang paling dekat dengan medoid, dengan cara menghitung jarak vector antar dokumen. (menggunakan Euclidian distance)
3. Secara random, pilih point yang bukan medoid.
4. Hitung total distance
5. If TD baru < TD awal, tukar posisi medoid dengan medoids baru, jadilah medoid yang baru.
6. Ulangi langkah 2 – 5 sampai medoid tidak berubah.

Diberikan himpunan data sejumlah n titik dalam ruang R2, tujuan clustering K-medoid adalah untuk membagi titik-titik data ke dalam k cluster sehingga fungsi objektif berikut minimal.

Dalam  merupakan titik perwakilan (representative point) bagi cluster 

• Jika mi dibatasi harus merupakan anggota dari
  , maka disebut medoid.
• Sebaliknya, jika adalah rataan dari titik-titik cluster dan tidak harus merupakan anggota dari P, maka disebut mean.

Dengan demikian algoritma K-mean dan K-medoid mempunyai hubungan yang sangat erat. K-medoid memberikan karakteristik K cluster, dan setiap titik dalam P menjadi milik medoid terdekat. Karena kita telah membatasi dalam ruang R², maka fungsi jarak d biasanya adalah jarak Euclidean.

Salah satu kekurangan pendekatan K-medoid adalah algoritma tersebut menghasilkan “hard” cluster, yaitu masing-masing titik secara unik diberikan satu dan hanya satu cluster.