Pembentukan Cluster Dalam Knowledge Discovery In Database Dengan Algoritma K-Means

by
Pembentukan Cluster Dalam Knowledge Discovery in Database Dengan Algoritma K-Means
Dewasa ini pembuatan data elektronika telah menjadi keperluan yang sungguh utama. Perkembangan pesat dalam teknologi isu yang menimbulkan semua berita mampu disimpan dalam jaringan komputer sudah menciptakan munculnya metode basis data yang sangat besar. Dalam hitungan detik, data-data dalam banyak sekali basis data akan senatiasa terbarukan, baik dikarenakan adanya update maupun penambahan data gres. Permasalahan yang kemudian timbul yakni bagaimana mengetahui gosip yang terdapat dalam basis data yang sangat besar. 
Knowledge discovery in Database (KDD) didefinisikan selaku ekstraksi informasi potensial, implisit dan tidak diketahui dari sekumpulan data. Proses knowledge discovery melibatkan hasil dari proses data mining (proses mengekstrak kecenderungan acuan sebuah data), kemudian mengubah akhirnya secara akurat menjadi info yang gampang dimengerti. 
Ada beberapa jenis pendekatan berlawanan yang diklasifikasikan sebagai teknik pencarian info/wawasan dalam KDD. Ada pendekatan kuantitif, mirip pendekatan probabilistik and statistik. Beberapa pendekatan mempergunakan teknik visualisasi, pendekatan klasifikasi seperti akal induktif, penelusuran contoh, dan analisis pohon keputusan. Pendekatan lainnya meliputi deviasi, analisis kecenderungan, algoritma genetik, jaringan syaraf tiruan dan pendekatan campuran dua atau lebih dari beberapa pendekatan yang ada. 
Pada dasarnya ada enam bagian yang paling esensial dalam teknik penelusuran info/ pengetahuan dalam KDD , yakni: (1) melaksanakan sejumlah besar data, (2) diharapkan efisiensi berhubungan dengan volume data, (3) memprioritaskan ketepatan/keakuratan, (4) memerlukan pemakaian bahasa tingkat tinggi, (5) memakai beberapa bentuk dari pembelajaran otomatis, dan (6) menghasilkan hasil yang menawan.
Clustering
Salah satu tata cara yang diterapkan dalam KDD ialah clustering. Clustering yaitu membagi data ke dalam grup-grup yang mempunyai obyek yang karakteristiknya sama. Garcia-Molina et al. menyatakan clustering yaitu menggolongkan item data ke dalam sejumlah kecil grup sedemikian sehingga masing-masing grup mempunyai sesuatu persamaan yang esensial. 
Clustering memegang peranan penting dalam aplikasi data mining, misalnya eksplorasi data ilmu pengetahuan, pengaksesan gosip dan text mining, aplikasi basis data spasial, dan analisis web. Clustering dipraktekkan dalam mesin penelusuran di Internet. Web mesin telusur akan mencari ratusan dokumen yang cocok dengan keyword yang dimasukkan. Dokumen-dokumen tersebut dikelompokkan dalam cluster-cluster sesuai dengan kata-kata yang dipakai. 
Kategori clustering
Tan, dkk. membagi clustering dalam dua kelompok, yaitu hierarchical and partitional clustering. Partitional Clustering disebutkan sebagai pembagian obyek-obyek data ke dalam kelompok yang tidak saling overlap sehingga setiap data berada sempurna di satu cluster. Hierarchical clustering yaitu sekelopok cluster yang bersarang seperti suatu pohon berjenjang (hirarki). 
William membagi algoritma clustering ke dalam golongan besar mirip berikut:
  • Partitioning algorithms: algoritma dalam kalangan ini membentuk bermacam partisi dan kemudian mengevaluasinya dengan menurut beberapa standar. 
  • Hierarchy algorithms: pembentukan dekomposisi hirarki dari sekumpulan data memakai beberapa tolok ukur. 
  • Density-based: pembentukan cluster menurut pada koneksi dan fungsi densitas. 
  • Grid-based: pembentukan cluster menurut pada struktur multiple-level granularity 
  • Model-based: suatu model dianggap selaku hipotesa untuk masing-masing cluster dan model yang bagus diseleksi diantara versi hipotesa tersebut. 
Algoritma K-Means
Algoritma K-Means yakni algoritma clustering yang paling popular dan banyak digunakan dalam dunia industri. Algoritma ini disusun atas dasar inspirasi yang sederhana. Ada mulanya ditentukan berapa cluster yang mau dibuat. Sebarang obyek atau unsur pertama dalam cluster dapat diseleksi untuk dijadikan selaku titik tengah (centroid point) cluster. Algoritma K-Means selanjutnya akan melaksanakan pengulangan tindakan berikut hingga terjadi kestabilan (tidak ada obyek yang dapat dipindahkan):
  • menentukan koordinat titik tengah setiap cluster, 
  • menentukan jarak setiap obyek terhadap koordinat titik tengah, 
  • mengelompokkan obyek-obyek tersebut menurut pada jarak minimumnya. 
Gambar berikut menawarkan diagram alir dari algoritma K-Means.
Berikut ini adalah gambaran penggunaan algoritma K-means untuk memilih cluster dari 4 buah obyek dengan 2 atribut, mirip ditunjukkan dalam Tabel. Clustering akan dilaksanakan untuk membentuk 2 cluster jenis obat berdasarkan atributnya. 
Langkah-langkah algoritma K-means adalah sebagai berikut :
1. Pengesetan nilai permulaan titik tengah. Misalkan obat A dan obat B masing-masing menjadi titik tengah (centroid) dari cluster yang hendak dibentuk. 
Tentukan koordinat kedua centroid tersebut,adalah
dan 
2. Menghitung jarak obyek ke centroid dengan memakai rumus jarak Euclid. 
Misalnya jarak obyek pupuk C=(4,3) ke centroid pertama 
yakni 
dan jaraknya dengan centroid kedua 
Adalah
Hasil perkiraan jarak ini disimpan dalam bentuk matriks k x n, dengan k banyaknya cluster dan n banyak obyek. Setiap kolom dalam matriks tersebut menawarkan obyek sedangkan baris pertama memperlihatkan jarak ke centroid pertama, baris kedua memperlihatkan jarak ke centroid kedua. Matriks jarak setelah iterasi ke-0 yaitu selaku berikut:
Clustering obyek : Memasukkan setiap obyek ke dalam cluster (grup) menurut jarak minimumnya. Jadi obat A dimasukkan ke grup 1, dan obat B, C dan D dimasukkan ke grup 2. Keanggotaan obyek ke dalam grup dinyatakan dengan matrik, unsur dari matriks bernilai 1 jika sebuah obyek menjadi anggota grup. 
Iterasi-1, menetukan centroid : Berdasarkan anggota masing-masing grup, selanjutnya ditentukan centroid gres. Grup 1 hanya berisi 1 obyek, sehingga centroidnya tetap . Grup 2 mempunyai 3 anggota, sehingga centroidnya diputuskan menurut rata-rata koordinat ketiga anggota tersebut:
5. Iterasi-1, mengkalkulasikan jarak obyek ke centroid: selanjutnya, jarak antara centroid gres dengan seluruh obyek dalam grup dihitung kembali sehingga diperoleh matriks jarak sebagai berikut: 
6. Iterasi-1, clustering obyek: langkah ke-3 diulang kembali, memilih keanggotaan grup berdasarkan jaraknya. Berdasarkan matriks jarak yang gres, maka obat B harus dipindah ke grup 2. 
Iterasi-2, memilih centroid: langkah ke-4 diulang kembali untuk memilih centroid gres berdasarkan keanggotaan grup yang gres. Grup 1 dan grup 2 masing-masing memiliki 2 anggota, sehingga centroidnya menjadi 
dan 
8. Iterasi-2, mengkalkulasikan jarak obyek ke centroid : ulangi langkah ke-2, sehingga diperoleh matriks jarak selaku berikut: 
9. Iterasi-2, clustering obyek: menggolongkan tiap-tiap obyek berdasarkan jarak minimumnya, diperoleh:
Hasil pengelompokkan pada iterasi terakhir daripada hasil sebelumnya, diperoleh
Kelebihan dan Kelemahan algoritma K-means
Algoritma K-means dinilai cukup efisien, yang ditunjukkan dengan kompleksitasnya O(tkn), dengan catatan n ialah banyaknya obyek data, k adalah jumlah cluster yang dibuat, dan t banyaknya iterasi. Biasanya, nilai k dan t jauh lebih kecil dibandingkan dengan nilai n. Selain itu, dalam iterasinya, algoritma ini akan berhenti dalam kondisi optimum lokal. 
Hal yang dianggap sebagai kelemahan algoritma ini yakni adanya keharusan menetukan banyaknya cluster yang akan dibentuk, cuma mampu dipakai dalam data yang mean-nya dapat diputuskan, dan tidak mampu menangani data yang mempunyai penyimpangan-penyimpangan (noisy data dan outlier). Berkhin menyebutkan beberapa kelemahan algoritma K-means yakni: (1) sungguh bergantung pada penyeleksian nilai awal centroid, (2) tidak jelas berapa banyak cluster k yang terbaik, (3) hanya melakukan pekerjaan pada atribut numerik. 
Similarity dan Dissimilarity
Memperhatikan input dalam algoritma K-Means, dapat dikatakan bahwa algoritma ini hanya mengolah data kuantitatif. Hal tersebut juga diungkapkan oleh Berkhin, bahwa algoritma K-means hanya mampu mengolah atribut numerik. 
Sebuah basis data, mustahil cuma berisi satu macam type data saja, akan tetapi bermacam-macam type. William menyatakan suatu basis data mampu berisi data-data dengan type selaku berikut: symmetric binary, asymmetric binary, nominal, ordinal, interval dan ratio. Sedangkan Pal dan Mitra menyebutkan suatu basis data mampu berisi data-data teks, simbol, gambar dan suara.
Berbagai macam atribut dalam basis data yang berlawanan type (dalam disebut selaku data multivariate, seperti nominal, ordinal, and kuantitatif) mesti dimasak apalagi dahulu menjadi data numerik, sehingga mampu diberlakukan algoritma K-means dalam pembentukan clusternya. Pengukuran similarity dan dissimilarity mampu dipakai untuk pengolahan data tersebut. 
Atribut yang berlawanan tipe sama artinya dengan adanya ketidaksamaan (dissimilarity) antar atribut tersebut. Ketidaksamaan (dissimilarity) antara dua obyek mampu diukur dengan menjumlah jarak antar obyek berdasarkan beberapa sifatnya. Hubungan dissimilarity antara 2 buah data obyek a=(a1,a2,……,ap) dan b=(b1,b2, ….,bp) mampu dinyatakan dengan pengukuran jarak antara 2 obyek tersebut. Beberapa sifat jarak (dissimilarity) adalah selaku berikut:
  • d(a, b) ³ 0 , jarak kedua obyek senantiasa aktual atau nol,
  • d(a, a) = 0, jarak kepada diri sendiri adalah nol,
  • d(a, b) = d(b, a) , jarak kedua obyek ialah simetri,
  • d(a, b) £ d(a, c) + d(c, b), jarak memenuhi ketidaksamaan segitiga.
Misalkan dissimilarity antara obyek i dan obyek j dinyatakan dengan dij dan similarity dinyatakan dengan sij. Hubungan antara relationship dissimilarity dengan similarity dinyatakan dengan sij.=1- dij, dengan similarity terbatas pada 0 dan 1 ([5]). Jika similarity bernilai satu (benar-benar sama), maka dissimilarity nol, dan jika similarity bernilai nol (sungguh berlainan), dissimilarity bernilai satu. Setelah perkiraan jarak atau dissimilarity dari setiap variabel, maka seluruh hasil dikumpulkan menjadi sebuah indeks similarity (atau dissimilarity) antara dua obyek ([5]). Selanjutnya hasil tersebut mampu diolah menjadi obyek-obyek yang mau dikelompokkan dalam cluster-cluster oleh algoritma K-means.

SUMBER-SUMBER ARTIKEL DI ATAS :

[1] Berkhin, Pavel. Survey on clustering data mining techniques, http://www.ee.ucr.edu/ barth/EE242/clustering_survey.pdf
[2] Garcia-Molina, Hector; Ullman, JD., & Widom, Jennifer. 2002. Database systems the complete book, International edition. New Jersey, Prentice Hall.
[3] Pal, Shankar K & Mitra, Pabitra. 2004. Pattern Recognition algorithms for data mining. CRC Press. 
[4] Tan, Pang-Ning,; Steinbach,Michael; Kumar ,Vipin. Data Mining Cluster Analysis: Basic Concepts and Algorithms. www-users.cs.umn.edu/ kumar /dmbook/-16k.
[5] Teknomo, Kardi. Similarity Measurement http://people.revoledu.com/kardi/bimbingan/Similarity/index.html
[6] Teknomo, Kardi. Numerical Example of K-Means Clustering, http://people.revoledu.com/kardi/bimbingan/kMean/NmericalExample.htmNu
[7] Wright, Peggy , Knowledge Discovery In Databases: Tools and Techniques, http://www.acm.org/crossroads/xrds5-2/kdd.html#11
[8] William, Graham, Data Mining Cluster, http://datamining.anu.edu.au/student/math3346_2005/ 050809-maths3346-clusters-2×2.pdf