Algoritma K-Means Clustering

Daftar Isi “Algoritma K-Means Clustering“

1. Distance Space atau Perhitungan Jarak Antara Data dan Centroid pada K-Means Clustering
2. Beberapa Permasalahan yang Terkait Dengan K-Means Clustering
3. Hard K-Means dan Fuzzy K-Means
4. Objective Function
5. Semi-Supervised Classification?
6. Karakteristik K-Means
7. Contoh Kasus Perhitungan K-Means Clustering

K-Means Clustering adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi.

Terdapat dua jenis data clustering yang sering dipergunakan dalam proses pengelompokan data yaitu Hierarchical dan Non-Hierarchical, dan K-Means merupakan salah satu metode data clustering non-hierarchical atau Partitional Clustering.

Partitional Clustering

Metode K-Means Clustering berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain.

Hierarchical Clustering

Dengan kata lain, metode K-Means Clustering bertujuan untuk meminimalisasikan objective function yang diset dalam proses clustering dengan cara meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya.

Contoh Cluster

Data clustering menggunakan metode K-Means Clustering 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

Ilustrasi Proses K-Means Clustering

1. Distance Space atau Perhitungan Jarak Antara Data dan Centroid pada K-Means Clustering

Beberapa distance space dapat diimplementasikan untuk menghitung jarak (distance) antara data dan centroid termasuk di antaranya Manhattan/City Block Distance, Euclidean Distance dan Minkowski Distance. Untuk pembahasan lengkap mengenai distance space dan contoh perhitungan nya dapat dibaca pada artikel berjudul “Vector Space Model (VSM) dan Pengukuran Jarak pada Information Retrieval (IR)“.

Tetapi secara umum distance space yang sering digunakan adalah Manhattan dan Euclidean. Euclidean sering digunakan karena penghitungan jarak dalam distance space ini merupakan jarak terpendek yang bisa didapatkan antara dua titik yang diperhitungkan, sedangkan Manhattan sering digunakan karena kemampuannya dalam mendeteksi keadaan khusus seperti keberadaaan outliers dengan lebih baik.

2. Beberapa Permasalahan yang Terkait Dengan K-Means Clustering

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. Outliers
5. Bentuk cluster
6. Overlapping

Keenam permasalahan ini adalah beberapa hal yang perlu diperhatikan pada saat menggunakan K-Means dalam mengelompokkan data.

Permasalahan 1 umumnya disebabkan oleh perbedaan proses inisialisasi anggota masing-masing cluster. Proses initialisasi yang sering digunakan adalah proses inisialisasi secara random. Dalam suatu studi perbandingan, proses inisialisasi secara random mempunyai kecenderungan untuk memberikan hasil yang lebih baik dan independent, walaupun dari segi kecepatan untuk convergen lebih lambat.

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.

Permasalahan 3, kegagalan untuk converge, secara teori memungkinkan untuk terjadi dalam metode Hard K-Means maupun Fuzzy K-Means. Kemungkinan ini akan semakin besar 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. Demikian juga dengan keadaan sebaliknya.

Kejadian seperti ini tentu akan mengakibatkan pemodelan tidak akan berhenti dan kegagalan untuk converge akan terjadi. Untuk Fuzzy K-Means, walaupun ada, kemungkinan permasalahan ini untuk terjadi sangatlah kecil, karena setiap data diperlengkapi dengan membership function (Fuzzy K-Means) untuk menjadi anggota cluster yang ditemukan.

Permasalahan 4, merupakan permasalahan umum yang terjadi hampir di setiap metode yang melakukan pemodelan terhadap data. Khusus untuk metode K-Means hal ini memang menjadi permasalahan yang cukup menentukan.

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.

Proses ini memerlukan suatu pendekatan khusus yang berbeda dengan proses pendeteksian outliers di dalam suatu dataset yang hanya terdiri dari satu populasi yang homogen.

Permasalahan 5 menyangkut bentuk cluster yang ditemukan. Tidak seperti metode data clustering lainnya, 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.

Salah Satu Dataset yang Mempunyai Bentuk Khusus

Permasalahan 6, 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.

3. Hard K-Means dan Fuzzy K-Means

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 dan Fuzzy K-Means.

Perbedaan di antara kedua metode ini terletak pada asumsi yang dipakai sebagai dasar pengalokasian.

a. 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:

Hard K-Means

dimana:
aik : Keanggotaan data ke-k ke cluster ke-i
vi : Nilai centroid cluster ke-i

b. 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 variabel 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, diperkenalkan juga suatu variabel myang merupakan weighting exponent dari membership function. Variabel ini dapat mengubah besaran pengaruh dari membership function, uik, dalam proses clustering menggunakan metode Fuzzy K-Means. Nilai 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 myang umumnya digunakan adalah 2.

Membership function untuk suatu data ke suatu cluster tertentu dihitung menggunakan rumus sebagai berikut:

Membership Function Fuzzy Means

dimana:
uik : Membership function data ke-k ke cluster ke-i
vi : 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.

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

Rumus Fuzzy Means Clustering

dimana:
N : Jumlah data
m : Weighting exponent
uik : Membership function data ke-k ke cluster ke-i

4. Objective Function

Objective Function adalah pernyataan kuantitatif dari kasus optimasi, sebagai contoh: memaksimumkan benefit, dengan menentukan biaya operasi minimum. Objective Function yang digunakan untuk metode Hard K-Means, adalah sebagai berikut:

Objective Function Hard K-Means

dimana:
N : Jumlah data
c : Jumlah cluster
aik : Keanggotaan data ke-k ke cluster ke-i
vi : Nilai centroid cluster ke-i

Nilai 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:

Objective Function Fuzzy Means

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

Di sini uik bisa mengambil nilai mulai dari 0 sampai 1.

5. Semi-Supervised Classification?

K-Means merupakan metode data clustering yang digolongkan sebagai metode pengklasifikasian yang bersifat unsupervised (tanpa arahan). Pengkategorian metode-metode pengklasifikasian data antara supervised dan unsupervised classification didasarkan pada adanya dataset yang data itemnya sudah sejak awal mempunyai label kelas atau tidak. Untuk data yang sudah mempunyai label kelas, metode pengklasifikasian yang digunakan merupakan metode supervised classification dan untuk data yang belum mempunyai label kelas, metode pengklasifikasian yang digunakan adalah metode unsupervised classification.

Selain masalah optimasi pengelompokan data ke masing-masing cluster, data clustering juga diasosiasikan dengan permasalahan penentuan jumlah cluster yang paling tepat untuk data yang dianalisa. Untuk kedua jenis K-Means, baik Hard K-Means dan Fuzzy K-Means, yang, penentuan jumlah cluster untuk dataset yang dianalisa umumnya dilakukan secara supervised atau ditentukan dari awal oleh pengguna, walaupun dalam penerapannya ada beberapa metode yang sering dipasangkan dengan metode K-Means.

Karena secara teori metode penentuan jumlah cluster ini tidak sama dengan metode pengelompokan yang dilakukan oleh K-Means, kevalidan jumlah cluster yang dihasilkan umumnya masih dipertanyakan.

Melihat keadaan dimana pengguna umumnya sering menentukan jumlah cluster sendiri secara terpisah, baik itu dengan menggunakan metode tertentu atau berdasarkan pengalaman, di sini, kedua metode K-Means ini dapat disebut sebagai metode semi-supervised classification, karena metode ini mengalokasikan data items ke masing-masing cluster secara unsupervised dan menentukan jumlah cluster yang paling sesuai dengan data yang dianalisa secara supervised.

6. Karakteristik K-Means

1. K-Means sangat cepat dalam proses clustering
2. K-Means sangat sensitif pada pembangkitan centroid awal secara random
3. Memungkinkan suatu cluster tidak mempunyai anggota
4. Hasil clustering dengan K-Means bersifat tidak unik (selalu berubah-ubah) – terkadang baik, terkadang jelek
5. K-means sangat sulit untuk mencapai global optimum

Memperhatikan input dalam algoritma K-Means, dapat dikatakan bahwa algoritma ini hanya mengolah data kuantitatif atau numerik.
Sebuah basis data tidak mungkin hanya berisi satu macam tipe data saja, akan tetapi beragam tipe.
Sebuah basis data dapat berisi data-data dengan tipe sebagai berikut: binary, nominal, ordinal, interval dan ratio.
Berbagai macam atribut dalam basis data yang berbeda tipe disebut sebagai data multivariate.
Tipe data seperti nominal dan ordinal harus diolah terlebih dahulu menjadi data numerik (bisa dilakukan dengan cara diskritisasi), sehingga dapat diberlakukan algoritma K-Means dalam pembentukan clusternya.

7. Contoh Kasus Perhitungan K-Means Clustering

Ditentukan banyaknya cluster yang dibentuk dua (k=2). Banyaknya cluster harus lebih kecil dari pada banyaknya data (k<n).

Contoh Dataset K-means

Inisialisasi centroid dataset pada tabel dataset diatas adalah C1 = {1 , 1} dan C2 = {2 , 1}. Inisialiasasi centroid dapat ditentukan secara manual ataupun random.

Untuk pengulangan berikutnya (pengulangan ke-1 sampai selesai), centroid baru dihitung dengan menghitung nilai rata-rata data pada setiap cluster. Jika centroid baru berbeda dengan centroid sebelumnya, maka proses dilanjutkan ke langkah berikutnya. Namun jika centroid yang baru dihitung sama dengan centroid sebelumnya, maka proses clustering selesai.

Rumus yang digunaka untuk menghitung distance space atau jarak data dengan centroid menggunakan Euclidiean Distance.

Persamaan Euclidean Distance

Pengulangan ke-1

Jarak data dengan Centroid C1 adalah:

Pengulangan ke-1 C1 K-means

Jarak data dengan Centroid C2 adalah:

Pengulangan ke-1 C2 K-means

Untuk seterusnya, hitung jarak pada setiap baris data, dan hasilnya seperti pada tabel dibawah.

Hasil Perhitungan Pengulangan ke-1

Kelompokan data sesuai dengan cluster-nya, yaitu data yang memiliki jarak terpendek. Contoh; karena d(x1,c1) < d(x1,c2) maka x1 masuk ke dalam cluster 1. Pada tabel diatas, data n=1 masuk ke dalam cluster 1 karena dc1 < dc2, sedangkan n=2,3,4 masuk ke dalam cluster 2 karena dc2 < dc1.

Pengelompokan Data pada Pengulangan ke-1

Setelah mendapatkan label cluster untuk masing-masing data n=1,2,3,4 maka dicari nilai rata-ratanya dengan menjumlahkan seluruh anggota masing-masing cluster dan dibagi jumlah anggotanya.

Nilai Rata-Rata Centroid pada Pengulangan ke-1

Pengulangan ke-2

Pengelompokan Data pada Pengulangan ke-2

Nilai Rata-Rata Centroid pada Pengulangan ke-2

Pengulangan ke-3

Pengelompokan Data pada Pengulangan ke-3

Nilai Rata-Rata Centroid pada Pengulangan ke-3

Karena centroid tidak mengalami perubahan (sama dengan centroid sebelumnya) maka proses clustering selesai.

Semoga artikel berjudul “Algoritma K-Means Clustering” bisa bermanfaat dan silahkan jika masih ada yang kurang jelas dapat ditanyakan di kolom komentar dibawah ini.

Silahkan Like Fanspage dan Share artikel ini jika menurut kamu bermanfaat untuk kamu dan orang lain.

Artikel Lainnya