K-means

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Langsung ke: navigasi, cari

Pendahuluan[sunting | sunting sumber]

K-means merupakan salah satu algoritma clustering [1]. Tujuan algoritma ini yaitu untuk membagi data menjadi beberapa kelompok. Algoritma ini menerima masukan berupa data tanpa label kelas. Hal ini berbeda dengan supervised learning yang menerima masukan berupa vektor (­1 , y1) , (­2 , y2) , …, (­i , yi), di mana xi merupakan data dari suatu data pelatihan dan yi merupakan label kelas untuk xi [2].

Pada algoritma pembelajaran ini, komputer mengelompokkan sendiri data-data yang menjadi masukannya tanpa mengetahui terlebih dulu target kelasnya[1]. Pembelajaran ini termasuk dalam unsupervised learning. Masukan yang diterima adalah data atau objek dan k buah kelompok (cluster) yang diinginkan.  Algoritma ini akan mengelompokkan data atau objek ke dalam k buah kelompok tersebut. Pada setiap cluster terdapat titik pusat (centroid) yang merepresentasikan cluster tersebut.

K-means ditemukan oleh beberapa orang yaitu Lloyd (1957, 1982), Forgey (1965) , Friedman and Rubin (1967) , and McQueen (1967) [1]. Ide dari clustering pertama kali ditemukan oleh Lloyd pada tahun 1957, namun hal tersebut baru dipublikasi pada tahun 1982. Pada tahun 1965, Forgey juga mempublikasi teknik yang sama sehingga terkadang dikenal sebagai Lloyd-Forgy pada beberapa sumber.

Algoritma K-Means[sunting | sunting sumber]

Algoritma untuk melakukan K-Means clustering adalah sebagai berikut[3]:

  1. Pilih K buah titik centroid secara acak
  2. Kelompokkan data sehingga terbentuk K buah cluster dengan titik centroid dari setiap cluster merupakan titik centroid yang telah dipilih sebelumnya
  3. Perbaharui nilai titik centroid
  4. Ulangi langkah 2 dan 3 sampai nilai dari titik centroid tidak lagi berubah

Proses pengelompokkan data ke dalam suatu cluster dapat dilakukan dengan cara menghitung jarak terdekat dari suatu data ke sebuah titik centroid. Perhitungan jarak Minkowski dapat digunakan untuk menghitung jarak antar 2 buah data. Rumus untuk menghitung jarak tersebut adalah[4]:

d(x_i,x_j)=(|x_{i1}-x_{j1}|^g+|x_{i2}-x_{j2}|^g+...+|x_{ip}-x_{jp}|^g)^{1/g}

Di mana:

g = 1, untuk menghitung jarak Manhattan
g = 2, untuk menghitung jarak Euclidean
g = ∞, untuk menghitung jarak Chebychev
xi , xj adalah dua buah data yang akan dihitung jaraknya
p = dimensi dari sebuah data


Pembaharuan suatu titik centroid dapat dilakukan dengan rumus berikut[4]:

\mu_k = \frac{1}{N_k} \sum_{q=1}^{N_k} x_q

Di mana:

µk = titik centroid dari cluster ke-K
Nk = banyaknya data pada cluster ke-K
xq = data ke-q pada cluster ke-K

Kelebihan dan Kekurangan[sunting | sunting sumber]

Ada beberapa kelebihan pada algoritma k-means, yaitu [2]:

  1. Mudah untuk diimplementasikan dan dijalankan.
  2. Waktu yang dibutuhkan untuk menjalankan pembelajaran ini relatif cepat.
  3. Mudah untuk diadaptasi.
  4. Umum digunakan.

Algoritma k-means memiliki beberapa kelebihan, namun ada kekurangannya juga. Kekurangan dari algoritma tersebut yaitu :

  1. Sebelum algoritma dijalankan, k buah titik diinisialisasi secara random sehingga pengelompokkan data yang dihasilkan dapat berbeda-beda [1]. Jika nilai random untuk inisialisasi kurang baik, maka pengelompokkan yang dihasilkan pun menjadi kurang optimal.
  2. Dapat terjebak dalam masalah yang disebut curse of dimensionality. Hal ini dapat terjadi jika data pelatihan memiliki dimensi yang sangat tinggi (Contoh jika data pelatihan terdiri dari 2 atribut maka dimensinya adalah 2 dimensi. Namun jika ada 20 atribut, maka akan ada 20 dimensi). Salah satu cara kerja algoritma ini adalah mencari jarak terdekat antara k buah titik dengan titik lainnya. Jika mencari jarak antar titik pada 2 dimensi, masih mudah dilakukan. Namun bagaimana mencari jarak antar titik jika terdapat 20 dimensi. Hal ini akan menjadi sulit.
  3. Jika hanya terdapat beberapa titik sampel data, maka cukup mudah untuk menghitung dan mencari titik terdekat dengan k titik yang diinisialisasi secara random. Namun jika terdapat banyak sekali titik data (misalnya satu milyar buah data), maka perhitungan dan pencarian titik terdekat akan membutuhkan waktu yang lama. Proses tersebut dapat dipercepat, namun dibutuhkan struktur data yang lebih rumit seperti kD-Tree atau hashing.

Aplikasi[sunting | sunting sumber]

K-means sebagai algoritma clustering memiliki banyak aplikasi. Aplikasi-aplikasi tersebut dapat dikelompokkan sesuai tujuannya.

Pengelompokan untuk Pemahaman (Understanding)[sunting | sunting sumber]

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

  • Aplikasi di Bidang Biologi

K-means dapat digunakan untuk mengelompokkan gen berdasarkan polanya[5]. Hal ini diperlukan untuk menemukan gen yang memiliki fungsi serupa.

  • Aplikasi di Bidang Bisnis

K-means dapat digunakan untuk melakukan segementasi pasar. Segementasi pasar adalah pengelompokan pelanggan sesuai karakteristik mereka (misalnya: gaya hidup, kebutuhan). K-means juga dapat digunakan dalam sistem pemberi rekomendasi untuk mengelompokkan objek-objek yang saling terkait.

  • Aplikasi di Bidang Temu Kembali Informasi

K-means dapat digunakan untuk mengelompokkan dokumen sehingga memudahkan temu kembali dokumen berdasarkan topiknya.

Pengelompokan untuk Utility[sunting | sunting sumber]

Pengelompokkan bertujuan untuk mengelompokkan himpunan data yang besar untuk memudahkan analisis data atau pemrosesan data lebih lanjut. Untuk tujuan ini, centroid dari cluster memegang peran lebih berarti.

  • Kompresi Data Multimedia

K-means dapat digunakan untuk kompresi data multimedia (citra, audio, video). Setiap objek dalam data (misalnya pixel dari citra) direpresentasikan dengan centroid dari cluster yang memuat objek tersebut. Teknik kompresi ini disebut juga kuantisasi vektor.

  • Rangkuman Data

K-means dapat digunakan untuk mengelompokkan data sebelum menerapkan teknik analisis data lainnya seperti regresi, tetangga terdekat, atau PCA. K-means dapat digunakan untuk terlebih dahulu mengelompokkan data ke dalam cluster-cluster. Kemudian teknik analisis data hanya perlu diterapkan pada centroid dari setiap cluster sehingga lebih efisien dalam hal penggunaan waktu dan ruang.

Variasi[sunting | sunting sumber]

Terdapat beberapa algoritma yang merupakan pengembangan/variasi dari algoritma k-means.

  • K-means++

Algoritma untuk memilih nilai awal untuk algoritma k-means[6]. Algoritma ini digunakan untuk mengurangi dampak buruk algoritma k-means yang sangat tergantung dari nilai awalnya.

  • K-medoids

Algoritma clustering yang berbasiskan prototype/model dari cluster. K-means menggunakan centroid (rata-rata) sebagai model dari cluster, sedangkan K-medoids menggunakan medoid (median).

  • Bisecting K-means

Ide dasarnya adalah menggunakan K-means untuk membagi dua suatu cluster. Awalnya setiap objek tergabung dalam satu cluster. Pada tiap iterasi, pilih satu cluster untuk dibagi dua menggunakan K-means. Hal ini dilakukan hingga terbentuk K cluster. Algoritma bisecting K-means bekerja lebih cepat dari K-means karena mengurangi jumlah objek yang diperbandingkan pada setiap iterasi.

Referensi[sunting | sunting sumber]

  1. ^ a b c d X. Wu and V. Kumar, eds., The Top Ten Algorithms in Data Mining.Chapman and Hall, 2009.
  2. ^ a b S. Russell  and P. Norvig, Artificial Intelligence A Modern Approach. Upper Saddle River, New Jersey 07458: Pearson Education, Inc., 3 ed., 2010.
  3. ^ P.-N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, (First Edition). Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2005.
  4. ^ a b O. Maimon and L. Rokach, Data Mining and Knowledge Discovery Handbo- ok. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2005.
  5. ^ http://www.epibiostat.ucsf.edu/biostat/
  6. ^ https://en.wikipedia.org/wiki/K-means%2B%2B