# K-Means Clustering

Salah satu metode *unsupervised learning* yang digunakan untuk masalah *clustering* adalah **K-means**. Pembelajaran tanpa pengawasan menggunakan kumpulan data dengan label atau kelas yang tidak diketahui. Metode pembelajaran tanpa pengawasan akan menambang kumpulan data yang tidak berlabel untuk pola data tersembunyi. Tujuan pembelajaran tanpa pengawasan adalah untuk menemukan pola data berdasarkan seberapa mirip data tersebut. Gambar berikut menunjukkan ilustrasi Klater menggunakan algoritma K-Means.

 

<figure><img src="https://3041032130-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F5CvtE8Xh9b75jKUaRr5Y%2Fuploads%2F9Tx4XjUlwgbOIgbnVdLH%2Fgambar%207.1%20k-means-clustering.png?alt=media&#x26;token=351ea0a7-533f-42b7-8523-987266b8df55" alt=""><figcaption></figcaption></figure>

Simbol K pada K-means clustering menandakan jumlah kluster yang digunakan. Kluster mengacu pada kumpulan titik data yang dikumpulkan bersama karena kesamaan tertentu. Jika K = 2, maka akan ada 2 kluster, dan jika K = 3 maka terdapat 3 kluster, begitu seterusnya.

Algoritma K-means mengambil dataset yang tidak berlabel sebagai input, kemudian membagi dataset menjadi sejumlah k cluster, dan mengulangi proses tersebut sampai tidak menemukan cluster terbaik. Nilai k harus ditentukan sebelumnya dalam algoritma ini.

Algoritma k-means clustering melakukan dua tugas utama, yakni:

1. Menentukan nilai terbaik untuk titik pusat K atau centroid dengan proses iteratif (perulangan).
2. Menetapkan setiap titik data ke pusat k terdekat. Titik-titik data yang dekat dengan pusat-k tertentu, kemudian dibuatkan sebuah kluster

Oleh karena itu setiap cluster memiliki titik data dengan beberapa kesamaan, dan cukup jauh dari cluster lainnya. Gambar berikut menunjukkan ilustrasi cara kerja Algoritma Clustering K-means

<figure><img src="https://3041032130-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F5CvtE8Xh9b75jKUaRr5Y%2Fuploads%2FHsInSJ8jKZjYZVBY6Bu4%2FGambar%207.2%20k-means-clustering-algorithm-in-machine-learning.png?alt=media&#x26;token=3dc8ed5a-c795-4c4c-a0d8-605f98394122" alt=""><figcaption></figcaption></figure>

*Centroid cluster* digunakan untuk mewakili cluster dalam teknik partisi K-means, yang pertama kali diusulkan oleh MacQueen pada tahun 1967. Karena kecepatan dan skalabilitasnya, algoritma *clustering* K-means adalah algoritma *clustering* yang umum. Saat menggunakan K-means, *centroid* awal dipilih secara acak dari sekumpulan  𝑘𝑘  *centroid*.  *Hyperparameter*  𝑘𝑘,  yang  harus  berupa  bilangan  bulat positif kurang dari jumlah *instance* (atau titik data dalam kumpulan data), mendefinisikan berapa banyak *cluster* yang harus dihasilkan. Terkadang, konteks masalah *clustering* mempengaruhi jumlah *cluster*.

Setelah itu dicari *centroid* dengan cara merata-ratakan titik-titik data yang ditunjuk sebagai anggota *cluster*. Langkah awal adalah memilih jumlah 𝑘 *centroid* berdasarkan cluster yang akan dibuat. Selain itu, akan ditentukan seberapa dekat data tambahan ke *centroid* menyerupai *centroid*. Algoritma K- Means kemudian memilih data dengan kemiripan terbaik antara dokumen *centroid* dan *non-centroid* untuk menentukan anggota *cluster*. Selain itu, *centroid* baru untuk setiap *cluster* ditentukan dengan rata-rata anggota *cluster*. Ketika tidak ada lagi perubahan anggota *cluster*, iterasi berlanjut.

*Euclidean distance* merupakan salah satu cara untuk menghitung jarak pada algoritma K-Means. Perhitungan jarak dapat dimodifikasi agar sesuai dengan situasi. Komputasi kesamaan kosinus dapat digunakan saat melakukan pengelompokan dokumen. Menemukan nilai 𝑘 yang ideal, atau jumlah *cluster* di mana data dapat dikategorikan secara efektif, adalah tahap kunci dalam algoritma K-means.

Metode Siku (*elbow method*) adalah teknik yang populer untuk menentukan nilai 𝑘 yang ideal. Nilai fungsi biaya (*cost function*) diplot menggunakan berbagai nilai 𝑘 pada teknik siku. *Sum of Square Error* dapat dimanfaatkan sebagai salah satu fungsi biaya.

<figure><img src="https://3041032130-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F5CvtE8Xh9b75jKUaRr5Y%2Fuploads%2FaNEUnyH4NilTgCGUyDog%2FHands-On_Machine_Learning_with_Scikit-Learn-Keras-and-TensorFlow-2nd-Edition-Aurelien-Geron%5B1%5D.png?alt=media&#x26;token=7beec591-203f-4cd6-af87-4112dd6e59fa" alt=""><figcaption></figcaption></figure>

Gambar di atas menunjukkan grafik hubungan antara **jumlah klaster (k)** pada sumbu horizontal dan **inertia** pada sumbu vertikal.

* **Inertia** adalah ukuran seberapa jauh data dalam satu klaster dari pusat klasternya (centroid). Semakin kecil inertia, semakin rapat data terkumpul di sekitar centroid.
* Terlihat bahwa ketika nilai **k** meningkat dari 1 ke 4, nilai inertia turun dengan sangat cepat. Artinya, penambahan jumlah klaster pada tahap ini benar-benar membantu memperbaiki kualitas pengelompokan.
* Namun, setelah **k = 4**, penurunan inertia menjadi jauh lebih lambat meskipun jumlah klaster terus ditambah. Grafiknya membentuk kurva menyerupai sebuah lengan, dan pada titik **k = 4** terdapat sebuah “siku” (*elbow*).

Titik siku inilah yang disebut **metode Elbow**. Prinsipnya:

* Jika jumlah klaster terlalu sedikit (<4), maka inertia masih terlalu besar, artinya pengelompokan buruk.
* Jika jumlah klaster terlalu banyak (>4), penurunan inertia tidak lagi signifikan, bahkan bisa saja justru memecah klaster yang sudah baik menjadi beberapa bagian tanpa alasan yang jelas.

Oleh karena itu, **k = 4** dianggap sebagai jumlah klaster yang optimal pada dataset ini. Metode Elbow membantu kita memilih nilai k yang seimbang: cukup banyak untuk memisahkan data dengan baik, tetapi tidak terlalu berlebihan hingga membagi klaster yang sudah solid.

Teknik ini dikenal dengan nama **metode elbow (elbow method)**, dan meskipun sederhana, hasilnya cukup kasar. Untuk pendekatan yang lebih **presisi** (meski lebih mahal secara komputasi), dapat digunakan **silhouette score**.

&#x20;