Apa itu k-means clustering?

Ini adalah salah satu metode pengelompokan paling populer yang digunakan dalam machine learning. Tidak seperti pembelajaran diawasi, data pelatihan yang digunakan algoritma ini tidak berlabel, artinya titik data tidak memiliki struktur klasifikasi yang ditentukan.

Meskipun ada berbagai jenis algoritma pengelompokan, termasuk eksklusif, tumpang tindih, hirarkis, dan probabilistik, algoritma k-means clustering adalah contoh metode pengelompokan eksklusif atau "keras". Bentuk pengelompokan ini menetapkan bahwa titik data dapat ada hanya dalam satu kluster. Jenis analisis kluster ini umumnya digunakan dalam ilmu data untuk segmentasi pasar, pengelompokan dokumen, segmentasi gambar, dan kompresi gambar. Algoritma k-means adalah metode yang banyak digunakan dalam analisis kluster karena efisien, efektif dan sederhana.

K-mean adalah algoritma pengelompokan berbasis centroid berulang yang membagi kumpulan data menjadi kelompok serupa berdasarkan jarak antara centroid mereka. Centroid, atau pusat klaster, adalah rata-rata atau median dari semua titik di dalam klaster, tergantung pada karakteristik data.

K-means clustering adalah proses berulang untuk meminimalkan jumlah jarak antara titik-titik data dan pusat klusternya.

Algoritma k-means clustering beroperasi dengan mengkategorikan titik-titik data ke dalam kluster dengan menggunakan ukuran jarak matematis, biasanya euclidean, dari pusat kluster. Tujuannya adalah untuk meminimalkan jumlah jarak antara titik data dan kluster yang ditugaskan. Titik data yang paling dekat dengan centroid dikelompokkan bersama dalam kategori yang sama. Nilai k yang lebih tinggi, atau jumlah kluster, menandakan kluster yang lebih kecil dengan detail yang lebih besar, sedangkan nilai k yang lebih rendah menghasilkan kluster yang lebih besar dengan detail yang lebih sedikit.

Algoritma k-means clustering konvensional membutuhkan beberapa langkah. Langkah pertama adalah menginisialisasi k centroid di mana k sama dengan jumlah kluster yang dipilih untuk kumpulan data tertentu. Pendekatan ini menggunakan seleksi acak atau metode pengambilan sampel centroid awal.

Langkah selanjutnya mencakup proses berulang dua langkah berdasarkan algoritma machine learning maksimalisasi ekspektasi.¹ Langkah ekspektasi ini menetapkan setiap titik data ke centroid terdekatnya berdasarkan jarak (sekali lagi, biasanya berdasarkan sistem euclide). Langkah maksimisasi menghitung rata-rata dari semua titik untuk setiap klaster dan menetapkan kembali pusat klaster atau centroid. Proses ini berulang hingga posisi centroid mencapai konvergensi atau jumlah iterasi maksimum telah tercapai.

K-means clustering sederhana tetapi sensitif terhadap kondisi awal dan outlier. Penting untuk mengoptimalkan inisialisasi centroid dan jumlah kluster k, untuk mencapai kluster yang paling bermakna. Ada beberapa cara untuk mengevaluasi dan mengoptimalkan komponen pengelompokan algoritma dengan menggunakan metrik evaluasi dan metode pengambilan sampel centroid awal.

Kluster yang berkualitas mengandung setidaknya dua properti: 

1. Semua titik data dalam suatu kluster harus serupa.
   
2. Kluster harus berbeda satu sama lain.

Semua sifat ini dicapai dengan meminimalkan jarak di dalam klaster dan memaksimalkan jarak antara klaster dari semua titik data dalam kumpulan data. Dengan kata lain, makin ringkas dan terisolasi sebuah klaster dari kluster lain, makin baik. Tujuan dari algoritma pengelompokan k-mean adalah untuk meminimalkan jumlah kuadrat kesalahan (SSE).² Menghitung SSE dari jarak euclide kuadrat dari setiap titik ke centroid terdekatnya mengevaluasi kualitas dari penetapan klaster dengan mengukur variasi total dalam setiap klaster.

Metrik evaluasi kluster memeriksa kualitas dan memberikan perspektif yang berbeda untuk menganalisis hasil pengelompokan. Ini membantu dalam memilih jumlah kluster yang optimal dan inisialisasi centroid. Metrik evaluasi berikut adalah cara umum untuk mengukur jarak intrakluster dan interkluster dalam pengelompokan.

Algoritma pengelompokan k-mean bertujuan untuk memilih centroid, atau pusat klaster, yang meminimalkan inersia, sebuah metrik evaluasi yang mengukur seberapa baik sebuah kumpulan data dikelompokkan berdasarkan metrik jarak. Inersia dihitung dengan mengukur jarak antara titik data dan centroidnya, mengkuadratkan jarak tersebut dan menjumlahkan kuadrat tersebut untuk setiap titik data dalam klaster. Jumlah atau nilai inersia adalah jarak di dalam klaster. Makin rendah jumlahnya makin baik karena ini berarti titik data dalam klaster tersebut ringkas atau lebih mirip.³

Properti kedua diukur dengan indeks Dunn. Indeks Dunn merepresentasikan hubungan antara jarak minimum di dalam klaster dan jarak maksimum antara klaster. Klaster dengan jarak di dalam kluster yang tinggi mengindikasikan kualitas yang lebih baik, karena ini berarti klaster tersebut sebisa mungkin berbeda satu sama lain.⁴

Optimasi penting ketika menggunakan k-means untuk mencapai hasil pengelompokan terbaik.

Algoritma k-means bersifat nondeterministik karena langkah inisialisasinya acak. Metode ini menyiratkan bahwa jika algoritma dijalankan dua kali pada data yang identik, penugasan kluster mungkin berbeda. Untuk mencapai hasil pengelompokan yang optimal, pemilihan centroid awal yang tepat dan jumlah kluster yang optimal akan meningkatkan akurasi dan kecepatan algoritma k-means.

Setiap kluster diwakili oleh centroid, titik data yang mewakili pusat kluster. K-means mengelompokkan titik-titik data yang serupa ke dalam kluster dengan meminimalkan jarak antara titik-titik data dalam sebuah kluster dengan centroid atau nilai rata-rata k. Tujuan utama algoritma k-means adalah untuk meminimalkan jarak total antara titik-titik dan pusat kluster yang telah ditetapkan. Algoritma beroperasi secara iteratif, dan pemilihan partisi awal dapat sangat mempengaruhi kluster yang dihasilkan.

Risiko inisialisasi acak memberikan hasil yang tidak konsisten. Metode inisialisasi centroid hadir untuk mengurangi risiko ini. Sebuah studi oleh NUS Computing menjelaskan dan membandingkan berbagai metode seperti k-mean++ yang populer dengan inisialisasi acak.⁵

K-mean++ adalah algoritma k-mean yang mengoptimalkan pemilihan satu atau beberapa centroid kluster awal. Dikembangkan oleh peneliti Arthur dan Vassilvitskii, k-mean++ meningkatkan kualitas penetapan klaster akhir.⁶

Langkah pertama untuk inisialisasi dengan menggunakan metode k-means++ adalah memilih satu centroid dari kumpulan data. Untuk setiap centroid berikutnya, hitung jarak setiap titik data dari pusat kluster terdekatnya. Centroid berikutnya dipilih dengan mempertimbangkan kemungkinan bahwa suatu titik berada pada jarak yang proporsional dari centroid terdekat yang dipilih sebelumnya. Proses mengeksekusi iterasi sampai jumlah pusat kluster yang dipilih telah diinisialisasi.

Berikut adalah tutorial dari Pengembang IBM yang menggunakan metode k-mean++ untuk inisialisasi.

Idealnya, algoritma k-mean berulang sampai jumlah kluster optimal tercapai. Jumlah maksimum iterasi terpenuhi setelah centroid mencapai konvergensi.

Salah satu metode untuk mencapai jumlah klaster yang optimal adalah metode elbow. Metode elbow adalah metode grafis untuk menemukan jumlah klaster optimal dalam algoritma pengelompokan k-mean. Metode ini mengukur jarak euclide antara setiap titik data dengan pusat klasternya dan memilih jumlah klaster berdasarkan di mana perubahan tingkat "within cluster sum of squares" (WCSS) stabil. Nilai ini menunjukkan total varians dalam setiap klaster yang dibuat terhadap jumlah klaster.⁷

Langkah pertama dari metode elbow adalah menghitung WCSS untuk setiap klaster (k). Kemudian, nilai WCSS dibuat di sepanjang sumbu y dan jumlah klaster dibuat pada sumbu x. Seiring peningkatan jumlah klaster, titik plot seharusnya membentuk pola yang konsisten. Pola ini akan menghasilkan rentang untuk jumlah klaster yang optimal.⁸ Saat memutuskan jumlah klaster, pertimbangkan biaya komputasi. Makin besar jumlah klaster, makin banyak daya pemrosesan yang dibutuhkan terutama dengan kumpulan data yang besar.

Metode ini belum tentu yang terbaik, terutama untuk kumpulan data dengan dimensi tinggi atau bentuk tidak beraturan. Metode lain untuk memilih jumlah klaster yang optimal adalah analisis siluet.⁹

Algoritma k-means clustering digunakan di hampir setiap domain dan industri. Ini biasanya diterapkan pada data machine learning yang memiliki sedikit dimensi, bersifat numerik, dan dapat dengan mudah dibagi.

Para peneliti telah mengintegrasikan pengelompokan k-mean dengan metode pembelajaran mendalam seperti CNN dan RNN untuk meningkatkan kinerja berbagai tugas machine learning seperti visi komputer, NLP, dan banyak domain lainnya. Berikut adalah daftar aplikasi pengelompokan k-mean yang umum:

Segmentasi pelanggan: Praktik membagi pelanggan perusahaan ke dalam kelompok-kelompok berdasarkan karakteristik umum yang mencerminkan kesamaan. Strategi ini memungkinkan perusahaan untuk menargetkan kluster atau kelompok pelanggan tertentu untuk kampanye iklan tertentu.

Klasifikasi dokumen: Prosedur untuk mengalokasikan berbagai kelas atau kategori ke dokumen. Metode ini digunakan oleh banyak organisasi untuk memoderasi konten. Lihat dokumentasi Watson Discover ini untuk membuat pengklasifikasi dokumen.

Segmentasi gambar: Teknik visi komputer yang membagi gambar digital menjadi kumpulan piksel yang berbeda. Penelitian ini menyelami bagaimana model k-mean digunakan untuk membantu mengidentifikasi batas dalam citra medis.¹⁰

Mesin rekomendasi: Aplikasi di seluruh web menggunakan mesin rekomendasi. Analisis komponen utama dan teknik pengelompokan k-mean digunakan untuk membangun rekomendasi produk bagi bisnis e-commerce.¹¹

Untuk pengalaman belajar langsung, lihat tutorial yang menjelaskan dasar-dasar untuk melakukan pengelompokan k-mean di Python dengan menggunakan IBM® Watson Studio di watsonx.ai.

Tutorial ini menggunakan modul dari pustaka scikit-learn (sklearn) yang melakukan k-means clustering. Modul ini mencakup teknik pengoptimalan bawaan yang dimanipulasi oleh parameter kelasnya. Kelas untuk modul terlihat seperti ini:

class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')12

Parameter termasuk jumlah kluster yang akan dibentuk dan jumlah centroid yang akan dihasilkan (n_cluster). Ada dua metode inisialisasi yang tersedia k-means++ dan random. Ini juga mencakup atribut untuk mengatur jumlah maksimum iterasi. Setiap iterasi dimulai dengan mempartisi kumpulan data menjadi nilai n_clustersparameter.

Pustaka ini digunakan untuk menghasilkan kumpulan data uji dan melakukan pengelompokan:

import pandas as pd 
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns
import numpy

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

Beberapa manfaat umum k-means clustering dalam aplikasi machine learning meliputi:

Sederhana: K-means clustering mudah dipahami dan dipraktikkan. Ini adalah teknik machine learning tanpa pengawasan yang paling populer.

Cepat: Pengelompokan k-mean dirancang dengan pendekatan iteratif yang sederhana dari segi komputasi. Algoritma pengelompokan k-mean lebih cepat daripada pengelompokan hierarkis yang melibatkan pembangunan struktur klaster seperti pohon dan membutuhkan penghitungan jarak berpasangan antara semua titik data.

Dapat diskalakan: K-mean juga mudah diskalakan ke kumpulan data besar dan menggeneralisasi ke klaster dengan berbagai bentuk dan ukuran, yang ideal untuk analisis klaster. Karena sangat efisien secara komputasi, algoritma ini lebih dapat diskalakan dan cocok untuk kumpulan data besar dibandingkan dengan metode lainnya.

Beberapa tantangan umum yang terkait dengan k-means clustering meliputi:

Ketergantungan pada parameter input: K-means clustering bergantung pada parameter input yang diatur dengan benar. Menginisialisasi centroid dan jumlah kluster yang tepat sangat cocok untuk mendapatkan hasil kluster yang bermakna. Inisialisasi centroid yang buruk dapat menyebabkan peningkatan waktu berjalan dan penugasan kluster berkualitas rendah. Banyak penelitian telah dilakukan untuk meningkatkan prosedur inisialisasi centroid untuk hasil pengelompokan yang lebih baik dan waktu konvergensi yang lebih cepat.

Kemungkinan kinerja kurang baik pada kumpulan data tertentu: K-mean bekerja secara efektif ketika kumpulan data berisi klaster yang ukurannya serupa dan tidak ada outlier atau variasi kepadatan yang menonjol. K-mean berkinerja buruk ketika kumpulan data berisi banyak variasi atau memiliki banyak dimensi. Data yang tidak sesuai dengan asumsi kumpulan data tertentu dapat menyebabkan k-mean menghasilkan klaster berkualitas rendah.¹³ Sebagai contoh, klaster yang berukuran tidak merata dapat membuat centroid condong ke arah klaster yang lebih besar sehingga menyebabkan bias dan kesalahan klasifikasi di antara klaster yang lebih kecil. Untuk mengatasi masalah ini, k-mean dapat digeneralisasi menggunakan model probabilistik seperti node Gaussian Mixture.

Dampak outlier yang signifikan: Outlier memiliki dampak yang signifikan pada hasil k-means clustering. Kluster yang berbeda harus berjauhan, tetapi tidak terlalu jauh untuk membelokkan titik data. Penting untuk mempertimbangkan asumsi data sebelum menerapkan k-means. K-means sangat sensitif terhadap outlier karena bertujuan untuk menentukan centroid dengan rata-rata nilai dengan kluster. Sensitivitas ini membuatnya rentan terhadap overfitting untuk menyertakan outlier ini.