CLUSTERING

MATERI 1

CLUSTERING

Clustering merupakan proses pembagian (partisi) atau pengelompokan data. Menurut Jyoti Bora dan Kumar Gupta, clustering adalah suatu proses pembagian elemen-elemen data ke dalam kelompok yang berbeda (disebut sebagai cluster) sedemikian rupa sehingga elemen-elemen data dalam suatu kelompok memiliki kesamaan yang tinggi dan elemen-elemen data pada kelompok tersebut berbeda dengan elemen-elemen yang berada dalam kelompok lain.

Istilah “kesamaan” yang dimiliki elemen-elemen data harus dipahami sebagai kesamaan secara matematis, dimana ukurannya dapat didefinisikan dengan baik. Kesamaan dapat juga didefinisikan sebagai ukuran jarak. Jarak dapat diukur dari vektor data itu sendiri atau sebagai sebuah jarak dari sebuah vektor data terhadap pusat cluster (Babuska, 2009: 60). Pusat cluster biasanya tidak diketahui sebelumnya. Pusat cluster akan terlihat ketika algoritma clustering telah disimulasikan untuk pembagian data. Algoritma clustering tidak hanya ditunjukkan bagaimana bentuk dan isi dari tiap cluster, tetapi juga dengan relasi dan jarak antar cluster.

Clustering adalah suatu metode pengelompokan berdasarkan ukuran kedekatan (kemiripan). Clustering berbeda dengan group, group berarti kelompok yang sama. Tetapi, cluster tidak harus sama akan tetapi pengelompokannya berdasarkan pada kedekatan dari suatu karakteristik sample yang ada, salah satunya dengan menggunakan rumus jarak ecluidean. Aplikasinya cluster ini sangat banyak, karena hampir dalam mengidentifikasi permasalahan atau pengambilan keputusan selalu tidak persis akan tetapi cenderung memiliki kemiripan saja.

Metode clustering menurut  strukturnya  dibagi  menjadi  dua  yaitu  : 

Metode pengelompokan hirarki memiliki aturan satu data tunggal  bisa dianggap  sebagai  sebuah kelompok,  dua  atau  lebih  kelompok  kecil  dapat  bergabung menjadi satu kelompok besar dan begitu seterusnya hingga semua data dapat bergabung menjadi satu kelompok. Metode clustering hirarki merupakan satu-satunya metode yang masuk kedalam kategori   pengelompokan hirarki. Metode partitioning membagi  set data  kedalam  sejumlah  kelompok  yang  tidak  tumpang  tindih  (overlap) antara  satu  kelompok  dengan  kelompok  yang  lain  artinya  setiap  data  hanya  menjadi anggota satu kelompok. Metode seperti K-Means dan DBSCAN masuk dalam kategori pengelompokan partitioning. 

Metode clustering menurut keanggotaan dalam kelompok dibagi menjadi dua, yaitu eksklusif dan tumpang-tindih. Metode tersebut termasuk kategori eksklusif  jika  sebuah data  hanya  menjadi  anggota  satu  kelompok  dan  tidak  menjadi  anggota  kelompok yang lain.

Clustering K-Means

Algoritma K-Means merupakan algoritma pengelompokan iterative yang melakukan partisi set data ke dalam sejumlah K cluster yang sudah ditetapkan di awal. Algoritma K-Means sederhana  untuk  diimplemtasikan  dan  dijalankan, relative cepat, mudah  beradaptasi,  umum  penggunaannya  dalam  praktek. Secara historis, K-Means menjadi  salah  satu  algoritma  yang  paling  penting  dalam  bidang data  mining (Wu  dan Kumar, 2009). K-Means merupakan  salah  satu  metode  data clustering non  hirarki  yang  berusaha mempartisi  data yang  ada  ke  dalam  bentuk  satu  atau  lebih cluster atau kelompok.

Tujuan pekerjaan  pengelompokan  (clustering) data  dapat  dibedakan menajadi  dua, yaitu  pengelompokan  untuk  pemahaman  dan  pengelompokan  untuk  penggunaan. Jika tujuannya untuk pemahaman, kelompok yang terbentuk harus menangkap struktur alami data, bisanya proses pengelompokan dalam tujuan ini hanya sebagai proses awal untuk kemudian dilanjutkan dengan pekerjaan inti seperti peringkasan atau summarization (rata–rata, standart deviasi), pelabelan kelas pada  setiap  kelompok  untuk  kemudian digunakan  sebagai  data  latih  klasifikasi,  dan  sebagainya.

Metode-Metode Cluster Hirarki

a. Metode Single-linkage

Input untuk algoritma single linkage bisa berwujud jarak atau similarities antara pasangan-pasangan dari objek-objek. Kelompok-kelompok dibentuk dari entities individu dengan menggabungkan jarak paling pendek atau similarities (kemiripan) yang paling besar. Pada awalnya, kita harus menemukan jarak terpendek dalam D= {dik} dan menggabungkan objek-objek yang bersesuaian misalnya, U dan V, untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara (UV) dan cluster W yang lain dihitung dengan cara

d_{( UV ) W} = min{ d_UW,d_VW }

Disini besaran-besaran dUW dan dVW berturut-turut adalah jarak terpendek antara cluster-cluster U dan W dan juga cluster-cluster V dan W.

b. Metode Complete-linkage

Complete linkage memberikan kepastian bahwa semua item-item dalam satu cluster berada dalam jarak paling jauh ( similaritas terkecil) satu sama lain. Algoritma aglomerative pada umumnya dimulai dengan menentukan entri (elemen matriks) dalam D= {dik} dan menggabungkan objek-objek yang bersesuaian misalnya U dan V untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara cluster (UV) dan cluster Wyang lain dihitung dengan cara

d_{( UV ) W} = maks{ d_UW,d_VW }

Di sini besaran-besaran dUW  dan dVW berturut-turut adalah jarak antara tetangga terdekat cluster-cluster U dan W dan juga cluster-cluster V dan W. 

c. Metode Average-linkage

Average linkage memperlakukan jarak antara dua cluster sebagai jarak rata-rata antara semua pasangan item-item di mana satu anggota dari pasangan tersebut kepunyaan tiap cluster. Mulai dengan mencari matriks jarak D={dik} untuk memperoleh objek-objek paling dekat (paling mirip) misalnya U dan V. Objek-objek ini digabungkan untuk membentuk cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara(UV) dan cluster W yang lain ditentukan oleh

           

di mana d_ik adalah jarak antara objek i dalam cluster (UV) dan objek k dalam cluster W, dan Nuv 

dan Nw berturut-turut adalah banyaknya item-item dalam cluster (UV) dan W.

Labeling

Pengertian Labeling (bahasa Inggris: Tag) adalah penanda.

Dalam sistem online komputer, label (tag) adalah kata kunci non hierarki atau tidak bertingkat yang tugasnya adalah menunjukkan potongan-potongan informasi (seperti petunjuk internet,gambar digital,atau file komputer). Label merupakan jenis metadata yang membantu untuk menjelaskan suatu hal dan memungkinkan hal tersebut ditemukan ketika melakukan pencarian (browsing)

Label umumnya dipilih langsung secara informal oleh pembuat item atau penampil item,tergantung pada sistem. Istilah penandaan (tagging) dipopulerkan oleh situs yang berhubungan dengan Web 2.0 dan menjadi fitur penting di banyak layanan Web 2.0. Tagging sekarang juga menjadi bagian dari software desktop.

Sejarah dan Konteks

Penandaan atau pelabelan berfungsi untuk membantu mengklasifikasi, menandai kepemilikan, mencatat batasan, dan menunjukkan identitas online. Penandaan atau pelabelan dapat menggunakan tanda identifikasi yakni melalui bentuk kata-kata atau gambar.

Contoh penganalogian label dalam bentuk fisik di dunia ini adalah coretan ( grafiti ) dan pemberian tanda pada objek “museum”. Dalam organisasi informasi, fungsi tekstual dari kata kunci (keywords) adalah sebagai bagian dari identifikasi dan klasifikasi yang muncul sebelum komputer ada. Sekarang pencarian berbasis komputer menggunakan fungsi kata kunci sebagai cara cepat dalam mencari data yang tersimpan. Database online dan internet serta situs awal digunakan penerbit untuk membantu penggunanya mencari konten yang diinginkan.

Pada tahun 2003, website social bookmarking Delicious memberikan cara bagi penggunanya untuk menambahkan tag atau label pada bookmarks mereka yang nantinya juga mempermudah penggunanya dalam proses pencarian item. Delicious juga menyediakan tampilan agregat browseable dari bookmark semua pengguna yang menampilkan label tertentu.

Berikut ini contoh dari Labeling :

a. Blog
Banyak dari sistem blog yang mengizinkan pembuatnya untuk menambah free-form tags di dalam postingan sekaligus menempatkan postingan ke dalam kategori. Contohnya,sebuah postingan dapat ditampilkan pada sesuatu yang sudah ditandai (tagging) dengan istilah baseball atau tickets.

Masing-masing dari label ini biasanya adalah sebuah link situs yang mengarah ke sebuah halaman daftar index yang berisi segala sesuatu yang berhubungan dengan label tersebut. Blog biasanya mempunyai sebuah sidebar yang berisi daftar semua label yang sudah digunakan dalam blog tersebut dan setiap label mengarah ke sebuah halaman index.

b. For an event

Official label adalah kata kunci yang diadopsi dari peristiwa dan konferensi bagi para peserta yang melakukan publikasi di situs mereka, seperti catatan blog, foto acara atau peristiwa, dan slide presentasi. Mesin pencari dapat mengindeksi hal-hal tersebut untuk membuat bahan-bahan yang lebih relevan dan berhubungan dengan peristiwa yang dicari.