Senin, 13 Januari 2020

Clustering K-Means dan contoh kasus





Menurut Vulandari(2017:53) menyatakan bahwa  Clustering disebut juga sebagai segmentation digunakan untuk mengidentifikasi kelompok alami dari sebuah kasus yang didasarkan pada sebuah kelompok atribut, mengelompokkan data yang memiliki kemiripan atribut”.
Analisis pengelompokkan/clustering menurut Sadewo et al.,(2018:312) adalah “proses membagi data dalam suatu himpunan ke dalam beberapa kelompok yang kesamaan datanya dalam suatu kelompok lebih besar daripada kesamaan data tersebut dengan data dalam kelompok lain”.
Menurut Ian H,Eibe dalam Silitonga & Morina (2017:23)  algoritma clustering dikelompokkan kedalam 5 kategori yaitu:

  1. Partitioning methods, merupakan metode dengan pengelompokkan objek dimana tiap objek dimiliki oleh satu cluster. Algoritma partisi dapat meminimalkan mean kuadrat jarak dari setiap titik data ke pusat terdekatnya. Yang termasuk kedalam metode ini adalah algoritma K-Means,K-Medoid, atau PAM, CLARA dan CLARANS.
  2. Hierarchical methods, merupakan metode pengelompokan objek dengan 2 cara yaitu agglomerative dan divisive. Agglomerative dimulai dengan menggabungkan beberapa cluster hingga menjadi satu, divisive dimulai dengan cluster yang sama kemudian dipecah menjadi beberapa cluster yang lebih kecil. Yang termasuk kedalam metode ini adalah algoritma CURE, BIRCH dan Chameleon.
  3. Density-based methods, merupakan pengelompokan objek berdasarkan tingkat kerapatan objek atau densitas. Yang termasuk dalam metode ini yaitu DBSCAN, DENCLUE dan OPTICS.
  4. Grid-based methods, adalah metode pengelompokan objek dengan menggunakan struktur data grid multiresolusi yang mampu menangani data berdimensi tinggi. Yang termasuk dalam metode ini adalah CLIQUE, WaveCluster dan STING.
  5. Model-based methods, adalah pengelompokkan objek dengan memodelkan tiap cluster, dan mencoba mengoptimasikan kesesuaian data dengan model matematika. Yang termasuk dalam model ini adalah COBWEB.
 
  • Algoritma K-Means 
Algoritma K-Means termasuk algoritma clustering berulang untuk menetapkan nilai cluster (K) secara acak  sebagai nilai pusat dari cluster/centroid/mean/means. Dari data yang ada dicari jarak yang paling dekat dengan masing-masing cemtroid menggunakan rumus Euclidian(Vulandari,2017:54). Sedangkan menurut Sadewo et al., (2018:312) menjelaskan bahwa “K-Means merupakan suatu algoritma yang digunakan dalam pengelompokkan secara partisi yang memisahkan data ke dalam kelompok yang berbeda-beda”.
Empat langkah algoritma K-Means, yang pertama memilih sejumlah k objek secara acak dari himpunan data untuk centroid, yang kedua memisahkan objek yang bukan centroid ke cluster terdekat, yang ketiga memperbarui centroid berdasarkan rata-rata dari objek dalam cluster, yang keempat mengulang langkah kedua dan ketiga sampai menemukan kestabilan centroid (Suyanto,2019:308).

Langkah-langkah yang dilakukan dalam menggunakan algoritma K-Means menurut Novianti & Haviluddin(2016:21) sebagai berikut :
  1. Tentukan k  sebagai jumlah cluster yang akan dibentuk.
  2. Tentukan k centroid awal secara acak atau random, digunakan rumus sebagai berikut:
                                                                                 (2.1)
    Keterangan :
     i = 1,2,3,…n
    v = centroid pada cluster xi
    xi = objek ke-i
            n = banyaknya objek/jumlah objek yang menjadi anggota cluster
  3. Hitung jarak setiap objek ke masing-masing centroid dari masing-masing cluster dengan menggunakan metode Euclidian Distance :
                                                       (2.2)
    Keterangan:
    Dx,y = jarak objek antara objek x dan y
    n       = Jumlah attribut
    Xi       = Objek data
           Yi      = Data cluster
  4. Alokasikan masing-masing objek ke dalam centroid yang paling dekat
  5. Lakukan iterasi, kemudian tentukan posisi centroid baru dengan menggunakan persamaan (2.1).
  6. Kembali ke langkah 3 jika posisi centroid baru dengan centroid lama tidak sama.
 
Studi Kasus :

 

Sumber: BPS, url: https://www.bps.go.id

Data Akumulasi Volume Air Bersih Yang Disalurkan

  1. Cluster yang dibuat yaitu sebanyak 3 cluster 
  2. Centroid awal secara acak
     
  3.  Contoh perhitungan Jarak/ Euclidian Distance :
               

  4.  Mencari nilai Centroid paling dekat dari tiap objek.
  5. Hasil Iterasi 1

  6. Membuat centroid baru dari setiap kelompok
     
  7. Kembali ke langkah 3 sampai posisi centroid lama dan centroid baru sama
     
  8. Proses Iterasi berhenti di iterasi ke tiga
     
  9. Proses iterasi berhenti di iterasi ke tiga
  10. Proses K-Means Clustering dengan Rapidminer menghasilkan 3 cluster, C0, C1, C2
  11. Cluster 0 memiliki nilai maksimal jumlah air bersih yang disalurkan sebanyak 486199, cluster 1 sebanyak 2551955, cluster 2 sebanyak 1366336.
  12. Cluster 0 termasuk kategori berkebutuhan rendah dengan anggota 25 provinsi
  13. Cluster 1 termasuk kategori berkebutuhan tinggi dengan anggota 4 provinsi
  14. Cluster 2 termasuk kategori berkebutuhan sedang dengan anggota 5 provinsi
  15. Hasil validasi dari metode Davies Bouldin Index mendapatkan nilai 0,534

--Semoga Bermanfaat--

Tidak ada komentar:

Posting Komentar