Sourcecode K-Means Clustering PHP

k-means clustering adalah algoritme untuk membagi n pengamatan menjadi k kelompok sedemikian hingga tiap pengamatan termasuk ke dalam kelompok dengan rata-rata terdekat (titik tengah kelompok).[1] Hasilnya adalah pembagian pengamatan ke dalam sel-sel Voronoi. Pengklasteran k rata-rata meminimalkan ragam dalam klaster (kuadrat jarak Euklides, bukan jarak Euklides biasa).

Permasalahan ini sulit secara komputasi (NP sulit). Namun, algoritme heuristik yang efisien dapat mencapai optimum lokal dengan cepat.

Algoritme ini memiliki hubungan yang renggang dengan algoritme k tetangga terdekat, algoritme pemelajaran mesin yang cukup terkenal dan sering disalahartikan dengan k rata-rata karena kemiripan namanya. Penerapan pengklasifikasi 1 tetangga terdekat ke titik tengah kelompok yang didapatkan oleh k rata-rata dapat mengelompokkan data baru ke dalam kelompok yang sudah ada. Cara ini disebut sebagai pengklasifikasi sentroid terdekat atau algoritme Rocchio.

Algoritma K-Mean Clustering

Algoritme pengklasteran k rata-rata adalah sebagai berikut.[2]

  1. Pilih k buah titik tengah secara acak.
  2. Kelompokkan data sehingga terbentuk k buah kelompok dengan titik tengah tiap kelompok merupakan titik tengah yang telah dipilih sebelumnya.
  3. Perbarui nilai titik tengah tiap kelompok.
  4. Ulangi langkah 2 dan 3 sampai titik tengah semua kelompok tidak lagi berubah.

Proses pengklasteran data ke dalam suatu kelompok dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik tengah. Perhitungan jarak Minkowski dapat digunakan untuk menghitung jarak antara 2 buah data.

Pembaruan titik tengah dapat dilakukan dengan rumus berikut:[3] {\displaystyle \mu _{k}={\frac {1}{N_{k}}}\sum _{j=1}^{N_{k}}x_{j}}

dengan ยตk adalah titik tengah kelompok ke-k, Nk adalah banyak data dalam kelompok ke-k, dan xj adalah data ke-j dalam kelompok ke-k

Kelebihan dan Kekurangan K-Mean Clustering

Algoritme k rata-rata memiliki kelebihan berikut:

mudah untuk diimplementasikan dan dijalankan;
membutuhkan waktu relatif singkat;
mudah diadaptasi; serta
umum digunakan.

Algoritme k rata-rata memiliki kekurangan berikut:

Sebelum algoritme dijalankan, k buah titik diinisialisasi secara acak sehingga pengklasteran data yang dihasilkan dapat berbeda-beda.[1] Jika nilai acak untuk inisialisasi kurang baik, hasil pengklasteran pun menjadi kurang optimal.
Algoritme ini dapat terjebak dalam masalah yang disebut curse of dimensionality (kutukan dimensi). Hal ini dapat terjadi jika data pelatihan memiliki dimensi yang sangat tinggi (jumlah dimensi adalah jumlah atribut sederhananya).
Jika hanya terdapat beberapa titik sampel data, cukup mudah untuk menghitung dan mencari titik terdekat dengan k titik yang diinisialisasi secara acak. Namun, jika terdapat banyak sekali titik data (misal satu miliar buah data), perhitungan dan pencarian titik terdekat akan membutuhkan waktu yang lama. Proses tersebut dapat dipercepat dengan struktur data yang lebih rumit seperti pohon kD atau hashing.

Batasan k rata-rata adalah model pengklasterannya. Model ini menanggap bahwa tiap kelompok berbentuk bola yang terpisah sehingga rata-ratanya bergerak menuju titik tengah bola (kelompok). Tiap kelompok dianggap memiliki ukuran yang mirip agar pengklasteran bisa benar (berhasil). Seperti algoritme pengklasteran lainnya, hasil k rata-rata menggunakan anggapan tertentu. Algoritme ini bekerja baik untuk set data tertentu, tetapi bisa bekerja buruk untuk set data lain.

Penerapan K-Mean Clustering

Pengklasteran untuk memahami

Pengklasteran untuk pemahaman bertujuan menghasilkan kelompok-kelompok yang terdiri dari objek-objek dengan ciri-ciri yang serupa, seperti halnya manusia mengelompokkan objek-objek.

Penerapan dalam biologi

Algoritme k rata-rata dapat digunakan untuk mengelompokkan gen berdasarkan polanya.[5][tidak ada di rujukan] Hal ini diperlukan untuk menemukan gen yang memiliki fungsi serupa.

Penerapan dalam bisnis

Algoritme k rata-rata dapat digunakan untuk melakukan segmentasi pasar. Segmentasi pasar adalah pengelompokan pelanggan sesuai ciri-ciri mereka (misalnya gaya hidup dan kebutuhan). Algoritme ini juga dapat digunakan dalam sistem pemberi rekomendasi untuk mengelompokkan objek-objek yang saling terkait.

Penerapan dalam temu balik informasi

Algoritme k rata-rata dapat digunakan untuk mengelompokkan dokumen sehingga memudahkan temu balik dokumen berdasarkan topiknya.

Pengklasteran sebagai alat

Pengklasteran bertujuan untuk mengelompokkan himpunan data yang besar untuk memudahkan analisis data atau pengolahan data lebih lanjut. Untuk tujuan ini, titik tengah kelompok memegang peran lebih berarti.

Kompresi data multimedia

Algoritme k rata-rata dapat digunakan untuk kompresi data multimedia (citra, audio, dan video). Setiap objek dalam data (misalnya piksel dari citra) direpresentasikan dengan titik tengah kelompok yang memuat objek tersebut. Teknik kompresi ini disebut juga kuantisasi vektor.

Rangkuman data

Algoritme k rata-rata dapat digunakan untuk mengelompokkan data sebelum menerapkan teknik analisis data lainnya seperti regresi, tetangga terdekat, atau PCA. Algoritme ini dapat digunakan terlebih dahulu untuk mengelompokkan data ke dalam kelompok-kelompok. Kemudian, teknik analisis data hanya perlu diterapkan pada titik tengah tiap kelompok sehingga lebih efisien dalam penggunaan waktu dan ruang.