Perhitungan Manual Algoritma K-Means

Misalkan kita memiliki dataset yang terdiri dari 7 titik data sebagai berikut:

(2, 10), (2, 5), (8, 4), (5, 8), (7, 5), (6, 4), (1, 2)
 

Kita akan menggunakan algoritma k-means untuk mengelompokkan data ini menjadi 3 kelompok. Langkah-langkah yang harus dilakukan adalah sebagai berikut:

Langkah 1: Inisialisasi pusat kelompok

Pertama-tama, kita perlu memilih tiga titik acak dari dataset sebagai pusat kelompok awal. Misalnya, kita pilih titik (2, 10), (5, 8), dan (1, 2) sebagai pusat kelompok awal.

Kelompok 1: (2, 10)
Kelompok 2: (5, 8)
Kelompok 3: (1, 2)
 

Langkah 2: Menghitung jarak antara setiap titik dengan pusat kelompok

Kedua, kita perlu menghitung jarak antara setiap titik dalam dataset dengan pusat kelompok. Kita dapat menggunakan rumus jarak Euclidean untuk menghitung jarak antara dua titik dalam ruang dua dimensi:

d(p, q) = sqrt((q1 - p1)^2 + (q2 - p2)^2)

Misalnya, untuk titik (2, 10), jaraknya dengan ketiga pusat kelompok adalah:

Jarak dengan Kelompok 1: sqrt((2 - 2)^2 + (10 - 10)^2) = 0
Jarak dengan Kelompok 2: sqrt((2 - 5)^2 + (10 - 8)^2) = 3.61
Jarak dengan Kelompok 3: sqrt((2 - 1)^2 + (10 - 2)^2) = 8.06

Lakukan perhitungan jarak yang sama untuk semua titik dalam dataset.

Langkah 3: Mengelompokkan setiap titik ke dalam kelompok terdekat

Ketiga, setiap titik akan dikelompokkan ke dalam kelompok dengan pusat terdekat. Misalnya, kita dapat mengelompokkan titik-titik berdasarkan jarak terdekat dengan pusat kelompok sebagai berikut:

Kelompok 1: (2, 10), (7, 5), (6, 4)
Kelompok 2: (2, 5), (5, 8)
Kelompok 3: (8, 4), (1, 2)
 

Langkah 4: Menghitung pusat kelompok baru

Keempat, kita perlu menghitung pusat kelompok baru berdasarkan titik-titik yang telah dikelompokkan pada langkah sebelumnya. Pusat kelompok baru adalah rata-rata dari semua titik dalam kelompok.

Pusat Kelompok 1: ((2 + 7 + 6) / 3, (10 + 5 + 4) / 3) = (5, 6.33)

Pusat Kelompok 2: ((2 + 5) / 2, (5 + 8) / 2) = (3.5, 6.5)

Pusat Kelompok 3: ((8 + 1) / 2, (4 + 2) / 2) = (4.5, 3)

Langkah 5: Ulangi langkah 2-4 hingga konvergen

Kelima, kita perlu mengulangi langkah 2-4 hingga tidak ada lagi perubahan dalam pengelompokkan titik ke dalam kelompok dan pusat kelompok. Jika tidak ada perubahan, maka algoritma dikatakan telah konvergen.

Berikut adalah hasil pengulangan langkah 2-4 hingga konvergen:

Iterasi 1:

Kelompok 1: (2, 10), (7, 5), (6, 4)
Kelompok 2: (2, 5), (5, 8)
Kelompok 3: (8, 4), (1, 2)

Pusat Kelompok 1: (5, 6.33)
Pusat Kelompok 2: (3.5, 6.5)
Pusat Kelompok 3: (4.5, 3)
 

Iterasi 2:

Kelompok 1: (2, 10), (7, 5), (6, 4)
Kelompok 2: (2, 5), (5, 8)
Kelompok 3: (8, 4), (1, 2)

Pusat Kelompok 1: (5, 6.33)
Pusat Kelompok 2: (3.5, 6.5)
Pusat Kelompok 3: (4.5, 3)

Kelompok 2: ((2 + 5) / 2, (5 + 8) / 2) = (3.5, 6.5) Pusat Kelompok 3: ((8 + 1) / 2, (4 + 2) / 2) = (4.5, 3)

Langkah 5: Ulangi langkah 2-4 hingga konvergen

Kelima, kita perlu mengulangi langkah 2-4 hingga tidak ada lagi perubahan dalam pengelompokkan titik ke dalam kelompok dan pusat kelompok. Jika tidak ada perubahan, maka algoritma dikatakan telah konvergen.

Berikut adalah hasil pengulangan langkah 2-4 hingga konvergen:

Iterasi 1:

yamlCopy code

Kelompok 1: (2, 10), (7, 5), (6, 4) Kelompok 2: (2, 5), (5, 8) Kelompok 3: (8, 4), (1, 2) Pusat Kelompok 1: (5, 6.33) Pusat Kelompok 2: (3.5, 6.5) Pusat Kelompok 3: (4.5, 3)

Iterasi 2:

yamlCopy code

Kelompok 1: (2, 10), (7, 5), (6, 4) Kelompok 2: (2, 5), (5, 8) Kelompok 3: (8, 4), (1, 2) Pusat Kelompok 1: (5, 6.33) Pusat Kelompok 2: (3.5, 6.5) Pusat Kelompok 3: (4.5, 3)

Pada iterasi kedua, tidak ada perubahan dalam pengelompokkan titik ke dalam kelompok dan pusat kelompok. Oleh karena itu, algoritma dikatakan telah konvergen.

Langkah 6: Hasil akhir

Hasil akhir dari algoritma k-means adalah pengelompokkan titik dalam kelompok yang berbeda dan pusat kelompoknya. Berikut adalah hasil akhir dari contoh perhitungan di atas:

Kelompok 1: (2, 10), (7, 5), (6, 4)
Kelompok 2: (2, 5), (5, 8)
Kelompok 3: (8, 4), (1, 2)

Pusat Kelompok 1: (5, 6.33)
Pusat Kelompok 2: (3.5, 6.5)
Pusat Kelompok 3: (4.5, 3)
 

Dalam contoh di atas, kita telah berhasil mengelompokkan dataset menjadi tiga kelompok dengan menggunakan algoritma k-means.