Ini adalah serangkaian catatan belajar yang cepat dan jelas untuk digunakan sebagai lembar contekan sebelum wawancara atau saat bekerja dengan algoritma baru.

Jika kita tidak mengetahui apa pun tentang data kita kecuali datanya, yaitu tidak ada label yang ditentukan dalam kumpulan data, pengelompokan K-means dapat membantu kita memahaminya.

Pernyataan Masalah: Kami dipekerjakan oleh FishBowl, sebuah aplikasi yang menyediakan forum dan komunitas anonim bagi karyawan terverifikasi untuk mendiskusikan masalah. Mereka ingin tahu cara membantu mengembangkan basis penggunanya.

Kami tidak tahu apa pun tentang basis pengguna mereka saat ini atau bagaimana jadinya. Satu-satunya data yang kami miliki per pengguna adalah cara mereka berinteraksi dengan aplikasi. Kami mendapat informasi ini dengan melacak perilaku pengguna di internet.

Fitur (Interaksi):

  • suka yang diberikan/diterima per hari
  • waktu sesi rata-rata
  • kali memposting konten per bulan
  • waktu pengguliran umpan rata-rata per sesi
  • pesan langsung yang dikirim/diterima per hari

Tujuan K-means adalah mengatur data ke dalam K kelompok berbeda.

Contoh Skenario

Untuk pemahaman visual yang lebih baik, asumsikan kita hanya memiliki 2 fitur dan setelah memetakan vektor, grafiknya akan terlihat seperti ini:

Sekarang, jika K=2, algoritma akan memisahkan data menjadi dua kelompok.

Langkah 1: Algoritme memilih K titik acak dan memberinya label berbeda.

Titik-titik ini disebut centroid.

Langkah 2: Setelah ini, kita mencari jarak antara titik pusat massa ini dan setiap titik lainnya.

Langkah 3:Berdasarkan centroid mana yang paling dekat dengannya, setiap titik akan diberi label centroid tersebut.

Langkah 4:Kemudian, kami memperbarui centroid menjadi rata-rata dari titik-titik tertentu di clusternya masing-masing.

Langkah 5:Proses ini diulangi, dan di setiap iterasi, kami memeriksa jarak centroid baru dari titik-titik lainnya di clusternya. Selanjutnya posisi centroid diubah menjadi nilai rata-rata cluster.

Jika koordinat pusat massa tidak berubah setelah beberapa kali iterasi, maka kita dapat mengatakan bahwa K-means telah konvergen.

Bagaimana cara memeriksa kualitas konvergensi K-means?

Kita akan mendapatkan Jarak Euclidean antara pusat massa dan semua titik di clusternya.

Lalu kita akan menjumlahkannya dan mendapatkan Inersia. Inersia memberitahu kita seberapa jauh setiap titik dari rata-rata clusternya.

Tujuannya adalah untuk meminimalkan Inersia untuk membentuk cluster yang paling seragam.

Salah satu cara untuk mencapai Inersia seminimal mungkin adalah dengan mencoba setiap kombinasi cluster untuk K=2 secara harfiah. Itu mengarah ke pertanyaan kami berikutnya:

Bagaimana cara meminimalkan Inersia?

Metode yang jelas adalah dengan menghitung K-means untuk semua kemungkinan kombinasi cluster. Namun, hal ini mungkin memerlukan banyak sumber daya.

Kompleksitas waktu untuk menghitung K-means setiap kemungkinan kombinasi cluster untuk nilai K adalah:

k= jumlah cluster

d= jumlah dimensi

n= jumlah vektor berdimensi d

Beberapa cara yang lebih efisien untuk meminimalkan Inersia adalah:

(a) Algoritme Lloyd

i= jumlah iterasi yang diperlukan hingga konvergensi.

Algoritme Lloyd membantu menurunkan kompleksitas menjadin*K*d*i. Namun, ada beberapa batasan di sini.

Saat menggunakan algoritma Lloyd, pada dasarnya kita memperkirakan konfigurasi cluster terbaik untuk nilai K tertentu. Mari kita membuat grafik 2D dengan Inersia pada sumbu Y, konfigurasi cluster pada sumbu X (jumlah vektor dalam cluster pertama), dan plot algoritma Lloyd.

Kita dapat melihat bahwa ini bukan grafik cembung, yaitu ada beberapa minimum dalam grafik. Oleh karena itu, pengoptimalan ini dapat memberikan hasil yang kurang optimal jika kita terjebak pada nilai minimum lokal. Ada beberapa metode untuk menyiasatinya (K-means++), tetapi tidak ada yang sempurna.

(b) K-means yang terbagi dua

Algoritma K-Means membagi dua merupakan modifikasi dari algoritma K-Means. Ini dapat menghasilkan pengelompokan partisi/hierarki dan mengenali cluster dalam berbagai bentuk dan ukuran.

Ini mengalahkan K-Means dalam pengukuran entropi.

Proses K-means yang terbagi dua

Langkah 1: Terlepas dari nilai K, kita membagi cluster menjadi dua bagian, seperti K=2.

Langkah 2: Kami membagi klaster dengan Inersia yang lebih tinggi, di antara dua klaster yang diperoleh dari langkah 1, menjadi dua klaster.

Langkah 3: Melalui beberapa iterasi ketika kita mencapai nilai K yang diinginkan. Dalam hal ini kita menganggapnya sebagai K=3.

K-means yang terbagi dua dapat digunakan jika kita ingin menghindari terjebak dalam minimum lokal (sambil mendapatkan konfigurasi cluster terbaik). Masalahnya adalah kita perlu mengetahui nilai K-means yang benar untuk dihentikan. Hal ini dapat dilakukan dengan “Metode Siku” dan “Metode Silhoutte”.

Terima kasih telah membaca!