K-means
K-means merupakan salah satu algoritme "clustering" . Tujuan algoritme ini
yaitu untuk membagi data menjadi beberapa kelompok. Algoritme ini menerima masukan berupa data tanpa label kelas. Hal ini berbeda dengan "supervised learning" yang menerima masukan berupa vektor (­"x­, y") , (­"x­, y") , …, (­"x­, y"), di mana "x "merupakan data dari suatu data pelatihan dan "y" merupakan label kelas untuk "x ".
Pada algoritme pembelajaran ini, komputer mengelompokkan sendiri data-data yang menjadi masukannya tanpa mengetahui terlebih dulu target kelasnya. Pembelajaran ini termasuk dalam "unsupervised learning." Masukan yang diterima adalah data atau objek dan "k "buah kelompok ("cluster") yang diinginkan. Algoritme 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) . 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.
Algoritme untuk melakukan K-Means "clustering" adalah sebagai berikut:
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:
formula_1
Di mana:
Pembaharuan suatu titik centroid dapat dilakukan dengan rumus berikut:
formula_2
Di mana:
Ada beberapa kelebihan pada algoritme k-means, yaitu :
Algoritme k-means memiliki beberapa kelebihan, namun ada kekurangannya juga. Kekurangan dari algoritme tersebut yaitu :
K-means sebagai algoritme "clustering" memiliki banyak aplikasi. Aplikasi-aplikasi tersebut dapat dikelompokkan sesuai tujuannya.
Pengelompokan untuk pemahaman bertujuan menghasilkan kelompok-kelompok yang terdiri dari objek-objek dengan karakteristik yang serupa, seperti halnya manusia mengelompokkan objek-objek.
K-means dapat digunakan untuk mengelompokkan gen berdasarkan polanya. Hal ini diperlukan untuk menemukan gen yang memiliki fungsi serupa.
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.
K-means dapat digunakan untuk mengelompokkan dokumen sehingga memudahkan temu kembali dokumen berdasarkan topiknya.
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.
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.
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.
Terdapat beberapa algoritme yang merupakan pengembangan/variasi dari algoritme k-means.
Algoritme untuk memilih nilai awal untuk algoritme k-means. Algoritme ini digunakan untuk mengurangi dampak buruk algoritme k-means yang sangat tergantung dari nilai awalnya.
Algoritme "clusterin"g yang berbasiskan "prototype"/model dari cluster. K-means menggunakan "centroid" (rata-rata) sebagai model dari "cluster", sedangkan K-medoids menggunakan "medoid "(median).
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". Algoritme bisecting K-means bekerja lebih cepat dari K-means karena mengurangi jumlah objek yang diperbandingkan pada setiap iterasi.