Apa itu K-Means Clustering?

K-Means Clustering adalah algoritma pembelajaran tidak terawasi, dan di antara semua algoritma pembelajaran tidak terawasi, K-Means Clustering mungkin yang paling banyak digunakan, berkat kekuatan dan kesederhanaannya. Bagaimana K-Means Clustering bekerja secara tepat?

Jawaban singkatnya adalah bahwa K-Means Clustering bekerja dengan membuat titik referensi (centroid) untuk jumlah kelas yang diinginkan, dan kemudian mengassign data points ke cluster kelas berdasarkan titik referensi mana yang paling dekat. Sementara itu adalah definisi singkat untuk K-Means Clustering, mari kita menghabiskan waktu untuk memahami K-Means Clustering dan mendapatkan intuisi yang lebih baik tentang bagaimana ia bekerja.

Definisi Clustering

Sebelum kita memeriksa algoritma yang digunakan untuk melaksanakan K-Means Clustering, mari kita menghabiskan waktu untuk mendefinisikan clustering secara umum.

Cluster adalah sekumpulan item, dan clustering adalah memasukkan item ke dalam kelompok-kelompok tersebut. Dalam pengertian ilmu data, algoritma clustering bertujuan untuk melakukan dua hal:

• Meng Pastikan semua data points dalam sebuah cluster semirip mungkin satu sama lain.
• Meng Pastikan semua data points dalam cluster yang berbeda semirip mungkin satu sama lain.

Algoritma clustering mengelompokkan item berdasarkan beberapa metrik kesamaan. Ini sering dilakukan dengan menemukan “centroid” dari kelompok-kelompok yang mungkin dalam dataset, meskipun tidak secara eksklusif. Ada berbagai algoritma clustering yang berbeda, tetapi tujuan dari semua algoritma clustering adalah sama, yaitu menentukan kelompok-kelompok yang intrinsic dalam sebuah dataset.

K-Means Clustering

K-Means Clustering adalah salah satu algoritma clustering yang paling tua dan paling umum digunakan, dan ia bekerja berdasarkan kuantifikasi vektor. Ada sebuah titik dalam ruang yang dipilih sebagai asal, dan kemudian vektor ditarik dari asal ke semua data points dalam dataset.

Secara umum, K-Means Clustering dapat dibagi menjadi lima langkah yang berbeda:

• Letakkan semua instance ke dalam subset, di mana jumlah subset sama dengan K.
• Tentukan titik mean/centroid dari partisi cluster yang baru dibuat.
• Berdasarkan centroid tersebut, assign setiap titik ke cluster tertentu.
• Hitung jarak dari setiap titik ke centroid, dan assign titik ke cluster di mana jarak dari centroid adalah minimum.
• Setelah titik telah diassign ke cluster, tentukan centroid baru dari cluster.

Langkah-langkah di atas diulangi sampai proses pelatihan selesai.

Pada fase awal, centroid ditempatkan di antara data points.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternatif, setelah centroid ditempatkan, kita dapat memandang K-Means Clustering sebagai bergantian antara dua fase yang berbeda: labeling data points dan updating centroid.

Pada langkah kedua, metrik jarak seperti jarak Euclidean digunakan untuk menghitung centroid mana yang paling dekat dengan titik tertentu, dan kemudian titik tersebut diassign ke kelas centroid tersebut. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Pada fase labeling data points, setiap data point diassign label yang meletakkannya dalam cluster yang dimiliki oleh centroid terdekat. Centroid terdekat biasanya ditentukan menggunakan jarak Euclidean yang dikuadratkan, meskipun metrik jarak lain seperti Manhattan distance, Cosine, dan Jaccard distance dapat digunakan tergantung pada jenis data yang dimasukkan ke dalam algoritma clustering.

Pada langkah ketiga, centroid dipindahkan ke rata-rata dari semua data points. Kelas kemudian diassign ulang. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

Pada langkah update centroid, centroid dihitung dengan menemukan jarak rata-rata antara semua data points yang saat ini terkandung dalam sebuah cluster.

Bagaimana Memilih Nilai yang Tepat untuk “K”

Mengingat bahwa K-Means Clustering adalah algoritma tidak terawasi dan jumlah kelas tidak diketahui sebelumnya, bagaimana Anda memutuskan jumlah kelas yang tepat/nilai yang tepat untuk K?

Satu teknik untuk memilih nilai K yang tepat disebut “teknik siku“. Teknik siku ini terdiri dari menjalankan algoritma K-Means Clustering untuk berbagai nilai K yang berbeda dan menggunakan metrik akurasi, biasanya Sum of Squared Error, untuk menentukan nilai K mana yang memberikan hasil terbaik. Sum of Squared Error ditentukan dengan menghitung jarak rata-rata antara centroid dari sebuah cluster dan data points dalam cluster tersebut.

Istilah “teknik siku” berasal dari kenyataan bahwa ketika Anda memplot SSE terhadap nilai K yang berbeda, plot garis yang dihasilkan sering memiliki bentuk “siku”, di mana SSE menurun cepat untuk beberapa nilai K pertama, tetapi kemudian menjadi datar. Dalam kondisi seperti itu, nilai K yang terletak di siku adalah nilai K yang terbaik, karena setelah nilai tersebut, hasilnya menurun dengan cepat.

Mini-Batch K-Means Clustering

Ketika dataset tumbuh lebih besar, waktu komputasi juga tumbuh. K-Means Clustering dasar dapat memakan waktu lama untuk diselesaikan ketika dijalankan pada dataset yang sangat besar, dan sebagai hasilnya, beberapa modifikasi telah dilakukan pada K-Means Clustering untuk mengurangi biaya spasial dan temporal algoritma.

Mini-Batch K-means clustering adalah variasi dari K-means clustering di mana ukuran dataset yang dipertimbangkan dibatasi. K-Means Clustering normal bekerja pada dataset/batch secara keseluruhan, sedangkan Mini-batch K-means clustering memecah dataset menjadi subset. Mini-batch secara acak dipilih dari dataset secara keseluruhan dan untuk setiap iterasi baru, sampel acak baru dipilih dan digunakan untuk memperbarui posisi centroid.

Dalam Mini-Batch K-Means clustering, cluster diperbarui dengan kombinasi nilai mini-batch dan tingkat pembelajaran. Tingkat pembelajaran menurun selama iterasi, dan ini adalah kebalikan dari jumlah data points yang ditempatkan dalam cluster tertentu. Efek dari mengurangi tingkat pembelajaran adalah bahwa dampak data baru berkurang dan konvergensi dicapai ketika, setelah beberapa iterasi, tidak ada perubahan dalam cluster.

Hasil studi tentang efektivitas Mini-batch K-means clustering menunjukkan bahwa ia dapat mengurangi waktu komputasi dengan sedikit kompromi pada kualitas cluster.

Aplikasi K-Means Clustering

K-Means Clustering dapat digunakan dengan aman dalam situasi apa pun di mana data points dapat dibagi menjadi kelompok/kelas yang berbeda. Berikut beberapa contoh kasus penggunaan K-mean clustering yang umum.

K-Means Clustering dapat diterapkan pada klasifikasi dokumen, mengelompokkan dokumen berdasarkan fitur seperti topik, tag, penggunaan kata, metadata, dan fitur dokumen lainnya. Ia juga dapat digunakan untuk mengklasifikasikan pengguna sebagai bot atau bukan bot berdasarkan pola aktivitas seperti posting dan komentar. K-Means Clustering dapat digunakan untuk memasukkan orang ke dalam kelompok berdasarkan tingkat kepedulian ketika memantau kesehatan mereka, berdasarkan fitur seperti komorbiditas, usia, riwayat pasien, dan sebagainya.

K-Means Clustering juga dapat digunakan untuk tugas yang lebih terbuka seperti membuat sistem rekomendasi. Pengguna dari sistem seperti Netflix (NFLX ) dapat dikelompokkan bersama berdasarkan pola tontonan dan direkomendasikan konten yang serupa. K-Means Clustering dapat digunakan untuk tugas deteksi anomali, menyoroti contoh kemungkinan penipuan atau item yang rusak.