Pada algoritma clustering, data akan dikelompokkan menjadi cluster-cluster berdasarkan kemiripan satu data dengan yang lain. Prinsip dari clustering adalah memaksimalkan kesamaan antar anggota satu cluster dan meminimumkan kesamaan antar anggota clusteryang berbeda. Kategori algoritma clustering yang banyak dikenal adalah Hierarchical Clustering. Hierarchical Clustering adalah salah satu algoritma clustering yang dapat digunakan untuk meng-cluster dokumen (document clustering). Dari teknik hierarchical clustering, dapat dihasilkan suatu kumpulan partisi yang berurutan, dimana dalam kumpulan tersebut terdapat:
a. Cluster – cluster yang mempunyai poin – poin individu. Cluster – cluster ini berada di level yang paling bawah.
b. Sebuah cluster yang didalamnya terdapat poin – poin yang dipunyai semua clusterdidalamnya. Single cluster ini berada di level yang paling atas.
Hasil keseluruhan dari algoritma hierarchical clustering secara grafik dapat digambarkan sebagai tree, yang disebut dengan dendogram. Tree ini secara grafik menggambarkan proses penggabungan dari cluster – cluster yang ada, sehingga menghasilkan cluster dengan level yang lebih tinggi. Gambar 1 adalah contoh dendogram.
Agglomerative Hierarchical Clustering
Metode ini menggunakan strategi disain Bottom-Up yang dimulai dengan meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkanatomic cluster – atomic cluster tersebut menjadi cluster yang lebih besar dan lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat pula berhenti jika telah mencapai batasan kondisi tertentu (Han, 2001). Metode Agglomerative Hierarchical Clustering yang digunakan pada penelitian ini adalah metode AGglomerative NESting (AGNES). Cara kerja AGNES dapat dilihat pada gambar 2.11. Adapun ukuran jarak yang digunakan untuk menggabungkan dua buah obyek cluster adalah Minimum Distance ,yang dapat dilihat pada persamaan 1.
........................................................................(1)
dimana |p – p’| jarak dua buah obyek p dan p’.
K-Mean
K-Means adalah suatu metode penganalisaan data atau metode Data Mining yang melakukan proses pemodelan tanpa supervisi (unsupervised) dan merupakan salah satu metode yang melakukan pengelompokan data dengan sistem partisi. Metode k-means berusaha mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok yang lain. Dengan kata lain, metode ini berusaha untuk meminimalkan variasi antar data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang ada di cluster lainnya.Objective function yang berusaha diminimalkan oleh k-means adalah:
J (U, V) = SUM (k=1 to N) SUM (i=1 to c) (a_ik * (x_k, v_i)^2)
dimana:
- U : Matriks keanggotaan data ke masing-masing cluster yang berisikan nilai 0 dan 1
- V : Matriks centroid/rata-rata masing-masing cluster
- N : Jumlah data
- c : Jumlah cluster
- a_ik : Keanggotaan data ke-k ke cluster ke-i
- x_k : data ke-k
- v_i : Nilai centroid cluster ke-i
Prosedur yang digunakan dalam melakukan optimasi menggunakan k-means adalah sebagai berikut:
- Step 1. Tentukan jumlah cluster
- Step 2. Alokasikan data ke dalam cluster secara random
- Step 3. Hitung centroid/rata-rata dari data yang ada di masing-masing cluster.
- Step 4. Alokasikan masing-masing data ke centroid/rata-rata terdekat
- Step 5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau apabila perubahan nilai centroid, ada yang di atas nilai threshold yang ditentukan atau apabila perubahan nilai pada objective function yang digunakan, di atas nilai threshold yang ditentukan. Centroid/rata-rata dari data yang ada di masing-masing cluster yang dihitung pada Step 3. didapatkan menggunakan rumus sebagai berikut:
v_ij = SUM (k=0 to N_i) (x_kj) / N_i
dimana:
i,k : indeks dari cluster
j : indeks dari variable
v_ij : centroid/rata-rata cluster ke-i untuk variabel ke-j
x_kj : nilai data ke-k yang ada di dalam cluster tersebut untuk variabel ke-j
N_i : Jumlah data yang menjadi anggota cluster ke-i
Sedangkan pengalokasian data ke masing-masing cluster yang dilakukan pada Step 4. dilakukan secara penuh, dimana nilai yang memungkinkan untuk a_ik adalah 0 atau 1. Nilai 1 untuk data yang dialokasikan ke cluster dan nilai 0 untuk data yang dialokasikan ke cluster yang lain. Dalam menentukan apakah suatu data teralokasikan ke suatu cluster atau tidak, dapat dilakukan dengan menghitung jarak data tersebut ke masing-masing centroid/rata-rata masing-masing cluster. Dalam hal ini, a_ik akan bernilai 1 untuk cluster yang centroidnya terdekat dengan data tersebut, dan bernilai 0 untuk yang lainnya.
Sumber:zero-fisip.web.unair.ac.id/artikel_detail-69819-Sistem%20Data%20(Database)-Hierarchical%20Clustering.html
