Proses Kerja Algoritma K-Means

LancangKuning - K- means ialah salah satu algoritma clustering. Tujuan algoritma ini ialah buat membagi informasi jadi sebagian kelompok. Algoritma ini menerima masukan berbentuk informasi tanpa label kelas. Perihal ini berbeda dengan supervised learning yang menerima masukan berbentuk vektor (¬x¬1, y1),(¬x¬2, y2),…,(- x¬i, yi), di mana xi ialah informasi dari sesuatu informasi pelatihan serta yi ialah label kelas buat xi.

Pada algoritma pendidikan ini, pc mengelompokkan sendiri data- data yang jadi masukannya tanpa mengenali terlebih dahulu sasaran kelasnya. Pendidikan ini tercantum dalam unsupervised learning. Masukan yang diterima merupakan informasi ataupun objek serta k buah kelompok (cluster) yang diidamkan. Algoritma ini hendak mengelompokkan informasi ataupun objek ke dalam k buah kelompok tersebut. Pada tiap cluster ada titik pusat (centroid) yang merepresentasikan cluster tersebut.

K- means ditemui oleh sebagian orang ialah Lloyd( 1957, 1982), Forgey (1965), Friedman and Rubin( 1967), and McQueen( 1967)[1]. Ilham dari clustering awal kali ditemui oleh Lloyd pada tahun 1957, tetapi perihal tersebut baru dipublikasi pada tahun 1982. Pada tahun 1965, Forgey pula mempublikasikan metode yang sama sehingga terkadang diketahui selaku Lloyd- Forgey pada sebagian sumber.

Algoritma buat melaksanakan K- Means clustering merupakan selaku berikut:

1. Seleksi K buah titik centroid secara acak
2. Kelompokkan informasi sehingga tercipta K buah cluster dengan titik centroid dari tiap cluster ialah titik centroid yang sudah diseleksi sebelumnya
3. Perbaharui nilai titik centroid
4. Ulangi langkah 2 serta 3 hingga nilai dari titik centroid tidak lagi berubah

Proses pengelompokkan informasi ke dalam sesuatu cluster bisa dicoba dengan metode menghitung jarak terdekat dari sesuatu informasi ke suatu titik centroid. Perhitungan jarak Minkowski bisa digunakan buat menghitung jarak antar 2 buah informasi. Rumus buat menghitung jarak tersebut adalah :

Di mana:

1. g = 1, buat menghitung jarak Manhattan
2. g = 2, buat menghitung jarak Euclidean
3. g =∞, buat menghitung jarak Chebychev
4. xi, xj merupakan 2 buah informasi yang hendak dihitung jaraknya
5. p= dimensi dari suatu data

Update sesuatu titik centroid bisa dicoba dengan rumus berikut :

Dimana :

µk= titik centroid dari cluster ke- K

Nk= banyaknya informasi pada cluster ke- K

xq= informasi ke- q pada cluster ke- K

Sebagian kasus yang kerap timbul pada di kala memakai tata cara K- Means buat melaksanakan pengelompokan informasi merupakan:

• Ditemuinya sebagian model clustering yang berbeda
• Pemilihan jumlah cluster yang sangat tepat
• Kegagalan buat converge
• Outliers
• Wujud cluster

Terdapat sebagian kelebihan pada algoritma k- means, ialah:

• Gampang buat diimplementasikan serta dijalankan.
• Waktu yang diperlukan buat melaksanakan pendidikan ini relatif kilat.
• Gampang buat diadaptasi.
• Universal digunakan.

Algoritma k- means mempunyai sebagian kelebihan, tetapi terdapat kekurangannya pula. Kekurangan dari algoritma tersebut ialah:

Saat sebelum algoritma dijalankan, k buah titik diinisialisasi secara random sehingga pengelompokan informasi yang dihasilkan bisa berbeda-beda. Bila nilai random buat inisialisasi kurang baik, hingga pengelompokan yang dihasilkan juga jadi kurang maksimal.

Bisa terjebak dalam permasalahan yang diucap curse of dimensionality. Perihal ini bisa terjalin bila informasi pelatihan mempunyai ukuran yang sangat besar (Contoh bila informasi pelatihan terdiri dari 2 atribut hingga dimensinya merupakan 2 ukuran. Tetapi bila terdapat 20 atribut, hingga hendak terdapat 20 ukuran). Salah satu metode kerja algoritma ini merupakan mencari jarak terdekat antara k buah titik dengan titik yang lain. Bila mencari jarak antar titik pada 2 ukuran, masih gampang dicoba. Tetapi bagaimana mencari jarak antar titik bila ada 20 ukuran.

Bila cuma ada sebagian titik ilustrasi informasi, hingga lumayan gampang buat menghitung serta mencari titik terdekat dengan k titik yang diinisialisasi secara random. Tetapi bila ada banyak sekali titik informasi(misalnya satu milyar buah informasi), hingga perhitungan serta pencarian titik terdekat hendak memerlukan waktu yang lama. Proses tersebut bisa dipercepat, tetapi diperlukan struktur informasi yang lebih rumit semacam kD- Tree ataupun hashing.(Arif)