π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.
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:
Menentukan nilai terbaik untuk titik pusat K atau centroid dengan proses iteratif (perulangan).
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
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.
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.
Last updated