K-means Clustering

 

Apa itu K-Means clustering?

K-means clustering adalah salah satu algoritma analisis klaster (cluster analysis) non hirarki. Analisis  klaster  merupakan  salah  satu  alat  untuk  mengelompokkan  data berdasarkan variabel atau feature.

Tujuan dari k-means clustering, seperti metode klaster lainnya, adalah untuk mendapatkan kelompok data dengan memaksimalkan kesamaan karakteristik dalam klaster dan memaksimalkan perbedaan antar klaster.

Algoritma K-means clustering mengelompokkan data berdasarkan jarak antara data terhadap titik centroid klaster yang didapatkan melalui proses berulang. Analisis perlu menentukan jumlah K sebagai input algoritma.

Dalam ranah machine learning, algoritma k-means clustering termasuk ke dalam jenis unsupervised learning.

Contoh aplikasi  K-means

Contoh penggunaan K-means clustering antara lain:

• Segmentasi pasar (market segmentation)
• Segmentasi citra
• Kompresi gambar
• Klasifikasi citra penginderaan jauh

Seperti metode clustering lainnya, K-means digunakan dalam penelitian eksploratori, confirmatori dan eksplanatori.

Untuk tujuan-tujuan eksploratori,  k-means dapat dimanfaatkan untuk  melengkapi proses Exploratory Data Analysis (EDA), selain menggunakan analisis statistik deskriptif dan visualisasi data.

Sedangkan dalam proses confirmatori dan eksplanatori, K-means clustering dapat digunakan untuk melakukan konfirmasi terhadap teori-teori yang sudah ada.

Selain itu, algoritma ini juga digunakan untuk melakukan identifikasi jika tiba-tiba terjadi perubahan cluster setelah data baru masuk.

Pada tahap terakhir, hasil cluster dapat digunakan sebagai dasar melakukan strategi atau kebijakan terhadap suatu masalah tertentu yang dikaji.

Metode algoritma K-means clustering (step by step)

Algoritma K-means clustering dilakukang dengan proses sebagai berikut:

1. LANGKAH 1: TENTUKAN JUMLAH CLUSTER (K). Dalam contoh ini, kita tetapkan bahwa K =3 
2. LANGKAH 2: PILIH TITIK ACAK SEBANYAK K. Titik ini merupakan titik seed dan akan menjadi titik centroid proses pertama. Titik ini tidak harus titik data kita
3. LANGKAH 3: LABEL SEMUA DATA BERDASARKAN TITIK CENTROID TERDEKAT. Semua data diberikan label mengikuti titik centroid dari setiap klaster. Perhitungan jarak ini bisa menggunakan algoritma jarak tertentu, secara default dilakukan dengan Euclidean Distance
4. LANGKAH 4: TENTUKAN TITIK CENTROID BARU BERDASARKAN CLUSTER YANG TERBENTUK. Titik centroid selanjutnya “berpindah” ke lokasi centroid setiap cluster yang telah terbentuk.
5. LANGKAH 5: LABEL ULANG DATA  BERDASARKAN JARAK TERDEKAT TERHADAP CENTROID BARU. Langkah ini merupakan langkah yang sama dengan langkah ketiga. Perhatikan titik data yang diberikan tanda panah, berubah dari cluster merah ke cluster biru.
6. LANGKAH 6: ULANGI LANGKAH 4 DAN LANGKAH 5 SAMPAI TIDAK ADA PERGERAKAN LAGI. Secara berulang, algoritma akan mencari lokasi centroid baru dan melabel data berdasarkan centroid tersebut sampai mendapat hasil final, yaitu tidak ada lagi perpindahan centroid di setiap cluster. 

Untuk lebih jelasnya, lihat penjelasan dan ilustrasi dalam gambar di bawah ini. Klik kanan dan pilih Open image in new tab untuk gambar yang lebih besar.

K-means cluster langkah demi langkah

Selain jumlah klaster (K), parameter yang penting yang harus ditentukan oleh analis adalah bagaimana jarak antara titik ke centroid (lihat lankah 3 dan 5).

Dalam k-means clustering, jarak ini dapat diukur menggunakan jarak:

• Euclidean distance
• Manhattan distance
• A squared euclidean distance measure
• Cosine distance measure 

Pemilihan metode pengukuran jarak ini akan mempengaruhi bagaimana algoritma menghitung kesamaan dalam klaster dan bentuk klaster.

Kita sebagai analis harus dapat menentukan pengukuran jarak mana yang paling sesuai dengan kasus kita. Meskipun demikian, sebagian besar k-means dilakukan dengan pengukuran jarak euclidean (default).

K-means clustering dapat kita gunakan jika kita melakukan pengelompokkan data berdasarkan variabel tertentu, di mana kita belum dapat menentukan kelas outputnya seperti apa (unsupervised learning).

Algoritma ini dapat kita gunakan jika kita dihadapkan pada maslah yang penyelaesaiannya membutuhkan proses segmentasi atau pengelompokkan menjadi subgroup tertentu, seperti analisis pasar dan pelanggan.

Algoritma ini dapat kita gunakan saat melakukan pembacaan intuitif terhadap data yang baru kita dapatkan.

Selain itu, kita juga dapat memanfaatkan algoritma k-means clustering dalam proses Exploratory Data Analysis (EDA) untuk melengkapi proses analisis statistika deskriptif dan visualisasi data.

Syarat-syarat dan asumsi

Untuk dapat menjalankan K-means clustering, ada beberapa asumsi yang harus dipenuhi, di antaranya:

1. Tidak ada outlier dalam data kita
2. Sampel kita mewakili keseluruhan populasi.
3. Tidak ada multikolinieritas antara variabel/ feature

Kelebihan dan keunggulan

Berikut ini adalah kelebihan-kelebihan atau keunggulan algoritma K-means clustering:

• Algoritma yang sederhana dan mudah dipahami
• Cepat pemrosesannya
• Tersedia di berbagai tools atau software
• Mudah dalam penerapannya
• Selalu memberikan hasil, apapun datanya.

Kelemahan dan kekurangan

Sedangkan kelemahan atau kekurangan algoritma K-means clustering:

1. Hasilnya sensitif terhadap jumlah cluster (K). Solusinya, dapat dengan menggunakan Elbow Method, dengan menghitung dan membandingkan nilai WCSS. Lihat penjelasannya di bawah.
2. Sensitif terhadap inisialisasi “seed”. Untuk mengatasi ini, kita bisa menerapkan algoritma K-means ++
3. Sensitif terhadap pencilan atau outlier. Solusi untu masalah ini adalah dengan menghapus outlier dengan hati-hati dan berbagai pertimbangan.
4. Sensitif terhadap data dengan variabel yang memiliki skala berbeda. Maka, sebaiknya kita selalu melakukan scale atau standardisasi data sebelum melakukan k-means clustering. Satu kondisi di mana sebaikany kita tidak melakukan standardisasi data adalah ketika satu variabel memiliki bobot atau nilai penting yang lebih tinggi daripada yang lain.
5. Mengasumsikan setiap klaster berbentuk menyerupai lingkaran (spherical) dan kesulitan jika bentuk cluster yang memiliki bentuk berbeda.

Random Initialization Trap

Random Initialization Trap adalah sebuah kondisi dimana perbedaan lokasi “seed” pada tahap awal K-means dapat memberikan hasil yang berbeda pula.

Dengan demikian, terdapat kemungkinan kesalahan clustering karena randomnya proses inisialisasi.

Untuk mengatasi kondisi ini, kita dapat menggunakan algoritma K-means++.

Menentukan jumlah cluster (K)

Sebenarnya tidak ada cara yang baku untuk menentukan jumlah cluster (K).

Namun, untuk membantu proses ini, kita bisa menggunakan Elbow Method.

Elbow Method diperoleh dengan melakukan penilaian visual terhadap grafik garis di mana sumbu x berupa jumlah K, dan sumbu Y adalah nilai Within Cluster Sum Square (WCSS)

Apa itu WCSS?

WCSS merupakan sebuah nilai yang diperoleh dari proses berikut:

1. Pada setiap klaster, hitung jarak setiap titik data ke centroid klaster.
2. Hitung nilai pangkat dari jarak tersebut.
3. Lalu jumlahkan totalnya (sum)

Selanjutnya, plotkan ke dalam grafis sumbu Y, dan jumlah K sebagai sumbu X.

Untuk menentukan jumlah K, kita pilih nilai WCSS yang seminimal mungkin.

Namun selalu diingat, bahwa selalu ada trade-off antara nilai WCSS dan jumlah optimal.

Sehingga penting untuk kita untuk mencoba melakukan analisis untuk beberapa nilai K dan membandingkan hasilnya.

Hal yang penting untuk dicatat adalah WCSS dan Elbow Method hanyalah sebuah pendekatan untuk memudahkan kita menntukan jumlah K.

Keputusan mengenai berapa jumlah K tetap berada di tangan kita sebagai analis.

Cara melakukan K-MEANS CLUSTERING (tutorial)

Seperti yang telah saya ceritakan di atas, salah satu kelebihan K-means adalah ketersediaannya dalam berbagai software seperti SPSS, Matlab, R dan Python.

Untuk melakukan K-MEANS CLUSTERING di R, silahkan menggunakan tutorial pada tauatan ini: K-Means clustering in r.

Sedangkan untuk melakukan K-MEANS CLUSTERING di Python, silahkan menggunakan tutorial pada tauatan ini: K-MEANS CLUSTERING in python

Kesimpulan

Pada artikel ini kita belajar mengenai K-means clustering, meliputi pengertiannya, aplikasi, metode, serta kelebihan dan kelemahannya.

K-means clustering adalah salah satu algoritma unsupervised learning yang termasuk ke dalam analisis klaster (cluster analysis) non hirarki yang digunakan untuk  mengelompokkan  data berdasarkan variabel atau feature.