Clustering adalah salah satu metode yang terkenal dalam data mining, yang digunakan untuk mendapatkan kelompok-kelompok dari data, dimana setiap objek data akan dikelompokkan kedalam satu kelompok berdasarkan kemiripannya, dan yang lainnya akan dikelompokan pada kelompok yang lain.( Han,J. and Kamber,M, 2006)
K-Means Clustering merupakan teknik dalam klaster data yang sangat terkenal karena kecepatannya dalam mengklasterkan data. Akan tetapi K-Means Clustering memiliki kelemahan didalam memproses data yang berdimensi banyak. Khususnya untuk masukan yang bersifat non-linierly separable. K-Means clustering juga tidak mampu mengrupkan data yang bertipe kategorikal dan juga data campuran (numeric dan kategorikal). Kenyataan didunia nyata data yang tersedia atau yang diperoleh memiliki dimensi yang banyak dan juga bersifat campuran. Untuk mengatasi permasalahan ini, telah banyak diusulkan oleh para peneliti metode-metode yang dapat mengatasi kelemahan ini, salah satu diantaranya adalah Kernel K-Means Clustering (L.S Dhillon, et. al, 2005).
Kernel K-Means Clustering, pada prinsipnya mirip dengan K-Means tradisional, letak perbedaan yang mendasar ada pada perubahan masukannya. Dalam Kernel K-Means data point akan dipetakan pada dimensi baru yang lebih tinggi menggunakan fungsi non-linier sebelum dilakukan proses clustering (Cristianini N, Taylor,J.S.2000) Kemudian Kernel K-Means akan mempartisi data menggunakan linier separator pada space yang baru.
Metode kernel pertama dan barangkali yang paling tepat adalah Support Vector Machine (SVM) (Burges, 1998), yang mengoptimalkan kriteria margin maksimum dalam ruang fitur kernel. Algoritma k-means barangkali telah menjadi teknik clustering popular sejak diperkenalkan dalam era 1960an. Ini memaksimalkan jarak Euclidean kuadrat antara pusat-pusat cluster. Meskipun demikian, telah diketahui bahwa ini hanya optimal untuk (yang dapat dipisahkan secara linear) cluster terdistribusi Gaussian. Metode yang berbeda untuk melaksanakan algoritma ini dalam ruang kernel yakni kernel k-means telah diperoleh. Dalam (Zang dan Alexander, 2006) teknik optimasi stochastic dikembangkan dengan menggunakan kernel trick, sedangkan dalam (Girolami, 2002) pemetaan data actual diperkirakan melalui eigenvector dari apa yang disebut matriks kernel.
Secara eksperimental, penelitian-penelitian ini memperlihatkan bahwa keterbatasan k-means bisa telah teratasi, dan hasil yang baik dicapai juga untuk kumpulan-kumpulan data yang memiliki batasan-batasan cluster nonlinear. Motivasi untuk keinginan melaksanakan K-means dalam ruang fitur kernel dinyatakan secara longgar sebagai “masalah kemampuan memisahkan nonlinear yang dapat dielakkan oleh kelas melalui pemetaan data yang diamati pada ruang data berdimensi yang lebih tinggi dengan cara nonlinear sehingga setiap cluster untuk setiap kelas membentang ke dalam bentuk sederhana”. Meskipun demikian, tidak jelas bagaimana kernel K-means berhubungan dengan sebuah operasi pada kumpulan data ruang input. Juga tidak jelas cara menghubungkan lebar kernel dengan sifat-sifat kumpulan data input. Beberapa pemikiran yang disebutkan pada point-point ini telah dibuat dalam (Girolami, 2002; Cristianini & Taylor, 2000).
Biasanya perluasan dari k-means ke kernel k-means direalisasi melalui pernyataan jarak dalam bentuk fungsi kernel (Girolami, 2002; Muller et al 2003). Meskipun demikian, implementasi tersebut mengalami masalah seris seperti biaya clustering tinggi karena kalkulasi yang berulang dari nilai-nilai kernel, atau memori yang tidak cukup untuk menyimpan matriks kernel, yang membuatnya tidak dapat sesuai untuk corpora yang besar.
Anggaplah kumpulan data memiliki N sampel x1, x2,…xN. Algoritma K-means bertujuan untuk membagi sampel N ke dalam cluster K, C1, C2, …, CK, dan kemudian mengembalikan pusat dari setiap cluster, m1, m2,…,mk
sebagai representative dari kumpulan data. Selanjutnya kumpulan data N-point dipadatkan ke dalam “code book” point K.
0 Response to "KERNEL K-MEANS CLUSTERING"
Post a Comment