Algoritma Clustering Data Mining: Metode Partisi

Algoritma Clustering dalam Data Mining: Metode Partisi – Analisis klastering (Clustering) merupakan salah satu aktifitas analisis data yakni klasifikasi atau pengelompokan data ke dalam beberapa kategori/cluster. Obyek-obyek/data yang dikelompokkan ke dalam suatu group memiliki ciri-ciri yang sama berdasarkan kriteria tertentu.

Clustering sering digunakan sebagai alat yang berdiri sendiri untuk mendapatkan wawasan tentang distribusi data dan sebagai langkah preprocessing untuk algoritma lain.

Suatu cluster merupakan sekelompok entitas yang memiliki kesamaan dan memiliki perbedaan dengan entitas dari kelompok lain(Everitt,1980)

Apa itu Algoritma Clustering data mining?

Algoritma Clustering data mining bekerja dengan mengelompokkan obyek-obyek data (pola, entitas, kejadian, unit,hasil observasi) ke dalam sejumlah cluster tertentu (Xu and Wunsch,2009). Dengan kata lain algoritma Clustering melakukan pemisahan/ pemecahan/ segmentasi data ke dalam sejumlah kelompok (cluster) menurut karakteristik tertentu.

Penerapan dari Analisis Clustering

  • Pengurangan data
    • Summarization: Preprocessing untuk regresi, PCA, klasifikasi, dan analisis asosiasi
    • Kompresi: Pemrosesan gambar: kuantisasi vektor
  • Pembuatan dan pengujian hipotesis
  • Prediksi berdasarkan kelompok
    • Klaster & temukan karakteristik / pola untuk setiap kelompok
  • Menemukan K-nearest Neighbors
    • Melokalkan pencarian ke satu atau sejumlah kecil cluster
  • Deteksi Outlier: Pencilan sering dianggap sebagai yang “jauh” dari kelompok mana pun

Contoh Penerapan Analisis Clustering

  • Biologi: taksonomi makhluk hidup: kerajaan, filum, kelas, keteraturan, keluarga, genus dan spesies
  • Pengambilan informasi: pengelompokan dokumen
  • Penggunaan lahan: Identifikasi area penggunaan lahan yang serupa dalam database observasi bumi
  • Pemasaran: Bantu pemasar menemukan kelompok berbeda di basis pelanggan mereka, dan kemudian gunakan pengetahuan ini untuk mengembangkan program pemasaran yang ditargetkan
  • Perencanaan kota: Mengidentifikasi kelompok-kelompok rumah sesuai dengan jenis rumah, nilai, dan lokasi geografis mereka
  • Studi gempa bumi: Episentrum gempa bumi yang diamati harus dikelompokkan di sepanjang patahan benua
  • Iklim: memahami iklim bumi, menemukan pola atmosfer dan lautan
  • Ilmu Ekonomi: riset pasar tentang penerapan pada pengenalan pola pembelian & karakteristik konsumen, pengelompokan perusahaan, analisa trend stok
  • Teknik : Digunakan dalam bidang biometric recognition & speech recognition, analisa sinyal radar, Information Compression,dan noise removal
  • Ilmu Komputer : Web mining,analisa database spatial, information retrieval, textual document collection dan image segmentation
  • Medis : Digunakan dalam mendefinisikan taxonomi dalam bidang biologi, identifikasi fungsi protein dan gen, diagnosa penyakit dan penanganannya
  • Sosial : Digunakan pada analisa pola perilaku,identifikasi hubungan diantara budaya yang berbeda, pembentukan sejarah evolusi bahasa, dan studi psikologi criminal.

Langkah-langkah Dasar untuk Mengembangkan Tugas Clustering

  • Pemilihan fitur
    • Pilih info tentang tugas yang menarik
    • Redundansi informasi minimal
  • Ukuran kedekatan
    • Kesamaan dua vektor fitur
  • Kriteria Clustering
    • Disajikan melalui fungsi biaya atau beberapa aturan
  • Algoritma Clustering
    • Memilih algoritma
  • Validasi hasil
    • Uji validasi (juga, uji kecenderungan Clustering)
  • Interpretasi hasil
    • Integrasi dengan aplikasi

Kualitas Clustering yang baik

  • Metode pengelompokan yang baik akan menghasilkan cluster berkualitas tinggi
    • kesamaan intra-kelas yang tinggi: kohesif dalam klaster
    • kemiripan antar-kelas yang rendah: berbeda antar klaster
  • Kualitas metode clustering tergantung pada
    • ukuran kesamaan yang digunakan oleh metode
    • implementasinya, dan
    • Kemampuannya untuk menemukan beberapa atau semua pola tersembunyi

Mengukur Kualitas Clustering

  • Metrik Dissimilaritas / Kesamaan
    • Kesamaan dinyatakan dalam fungsi jarak, dengan matrik: d (i, j)
    • Definisi fungsi jarak biasanya agak berbeda untuk skala-skala, boolean, kategorikal, rasio ordinal, dan variabel vektor
    • Bobot harus dikaitkan dengan variabel yang berbeda berdasarkan aplikasi dan semantik data
  • Kualitas clustering:
    • Biasanya ada fungsi “kualitas” terpisah yang mengukur “kebaikan” klaster.
    • Sulit untuk mendefinisikan “cukup mirip” atau “cukup baik”
      • Jawabannya biasanya sangat subyektif

Pertimbangan untuk Analisis Cluster

  • Kriteria partisi
    • Partisi Single level vs. hierarchical (seringnya, partisi hierarkis multi-level diinginkan)
  • Pemisahan klaster
    • Eksklusif (mis., Satu pelanggan hanya memiliki satu wilayah) vs. Non-eksklusif (mis., Satu dokumen mungkin milik lebih dari satu kelas)
  • Ukuran kesamaan
    • Distance-based (mis., Euclidian, jaringan jalan, vektor) vs. connectivity-based (mis., Kepadatan atau kedekatan)
  • Ruang clustering
    • Full space (seringkali ketika dimensi rendah) vs. subspaces (sering dalam pengelompokan dimensi tinggi)

Persyaratan dan Tantangan dalam Analisis Cluster

  • Skalabilitas
    • Mengelompokkan semua data, bukan hanya pada sampel
  • Kemampuan untuk menangani berbagai jenis atribut
    • Angka, biner, kategorikal, ordinal, tertaut, dan campurannya
  • Pengelompokan berbasis kendala
    • Pengguna dapat memberikan masukan tentang kendala
    • Gunakan pengetahuan domain untuk menentukan parameter input
  • Interpretabilitas dan kegunaan
  • Lainnya
    • Penemuan cluster dengan bentuk sewenang-wenang
    • Kemampuan untuk menangani data yang bising
    • Pengelompokan secara bertahap dan ketidakpekaan terhadap urutan input
    • Dimensi tinggi

Pendekatan Clustering Utama

  • Pendekatan Partitioning:
    • Bangun berbagai partisi dan kemudian evaluasi dengan beberapa kriteria, mis., Meminimalkan jumlah kesalahan kuadrat
    • Metode umum: k-means, k-medoid dan CLARANS
  • Pendekatan Hierarchical:
    • Buat dekomposisi hirarkis dari set data (atau objek) menggunakan beberapa kriteria
    • Metode umum: Diana, Agnes, BIRCH dan CAMELEON
  • Pendekatan Density-based:
    • Berdasarkan konektivitas dan fungsi kepadatan
    • Metode umum: DBSACN, OPTICS dan DenClue
  • Pendekatan Grid-based:
    • berdasarkan pada struktur granularitas multi-level
    • Metode umum: STING, WaveCluster dan CLIQUE
  • Berbasis model:
    • Sebuah model dihipotesiskan untuk masing-masing kelompok dan mencoba untuk menemukan yang paling cocok dari model tersebut satu sama lain
    • Metode umum: EM, SOM dan COBWEB
  • Berbasis pola yang sering muncul:
    • Berdasarkan analisis pola yang sering muncul
    • Metode umum: p-Cluster
  • User-guided atau constraint-based:
    • Clustering dengan mempertimbangkan batasan spesifik yang ditentukan pengguna atau aplikasi
    • Metode umum: COD (obstacles) dan constrained clustering
  • Link-based clustering:
    • Objek sering dihubungkan bersama dalam berbagai cara
    • tautan masif dapat digunakan untuk mengelompokkan objek: SimRank dan LinkClus

Namun untuk pembahasan algoritma Clustering Data Mining kali ini hanya akan membahas Metode partisi saja, metode lainnya seperti metode Hierarchical, metode Density-Based dan metode Grid-Based akan dibahas di lain waktu.

Baca Juga Metode Clustering: hierarki, Density-Based dan Grid-Based

Metode Partisi

Konsep Dasar Algoritma Pastisi

  • Metode partisi: Mempartisi basis data D dari n objek ke dalam kumpulan cluster k, sehingga jumlah jarak kuadrat diminimalkan (di mana ci adalah centroid atau medoid dari cluster Ci)
    Metode Partisi
  • Masukkan nilai k, cari partisi k cluster yang mengoptimalkan kriteria partisi yang dipilih
    • Global optimal: merinci semua partisi secara mendalam
    • Metode heuristik: algoritma k-means dan k-medoid
    • k-means (MacQueen67, Lloyd’57 / ’82): Setiap cluster diwakili oleh pusat dari cluster
    • k-medoid atau PAM (Partisi di sekitar medoid) (Kaufman & Rousseeuw’87): Setiap cluster diwakili oleh salah satu objek dalam cluster

Metode Clustering K-Means

Masukkan nilai k, algoritma k-means diimplementasikan dalam empat langkah:

  1. Partisi objek ke dalam subset nonempty k
  2. Hitung titik benih sebagai centroid cluster dari partisi saat ini (centroid adalah pusat, mis., titik tengah, dari klaster)
  3. Tetapkan setiap objek ke kluster dengan titik benih terdekat
  4. Kembali ke Langkah 2, berhenti ketika tugas tidak berubah

Contoh dari Clustering K-Means

Contoh dari algoritma Clustering Data Mining K-Means
Contoh dari Clustering K-Means

Tahapan Algoritma k-Means

  1. Pilih jumlah klaster k yang diinginkan
  2. Inisialisasi k pusat klaster (centroid) secara random
  3. Tempatkan setiap data atau objek ke klaster terdekat. Kedekatan dua objek ditentukan berdasar jarak. Jarak yang dipakai pada algoritma k-Means adalah Euclidean distance (d)
    Persamaan Euclidean distance
    x = x1, x2, . . . , xn, dan y = y1, y2, . . . , yn merupakan banyaknya n atribut(kolom) antara 2 record
  4. Hitung kembali pusat klaster dengan keanggotaan klaster yang sekarang. Pusat klaster adalah rata-rata (mean) dari semua data atau objek dalam klaster tertentu
  5. Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Jika pusat klaster sudah tidak berubah lagi, maka proses pengklasteran selesai. Atau, kembali lagi ke langkah nomor 3 sampai pusat klaster tidak berubah lagi (stabil) atau tidak ada penurunan yang signifikan dari nilai SSE (Sum of Squared Errors)

Contoh Kasus Algorimta Clustering Data Mining: Metode Partisi

Iterasi 1

  1. Tentukan jumlah klaster k=2
  2. Tentukan centroid awal secara acak misal dari data disamping m1 =(1,1), m2=(2,1)
  3. Tempatkan tiap objek ke klaster terdekat berdasarkan nilai centroid yang paling dekat selisihnya (jaraknya). Didapatkan hasil, anggota cluster1 = {A,E,G}, cluster2={B,C,D,F,H} Nilai SSE yaitu:
    Persamaan Nilai SSE
    Hasil persamaan Nilai SSE

Iterasi 2

  1. Menghitung nilai centroid yang baru
    m1 = [(1 + 1 + 1)/ 3,(3 + 2 + 1)/ 3]= (1,2)
    m2 = [(3 + 4 + 5 + 4 + 2)/ 5,(3 + 3 + 3 + 2 + 1)/ 5] (3,6;2,4)
  2. Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru. Nilai SSE yang baru:
    Persamaan Nilai SSE
    = 12+0.852+0.722+1.522+02+0.572+12+1.412 = 7.88

Iterasi 3

  1. Terdapat perubahan anggota cluster yaitu cluster1={A,E,G,H}, cluster2={B,C,D,F}, maka cari lagi nilai centroid yang baru yaitu: m1=(1,25;1,75) dan m2=(4;2,75)
  2. Tugaskan lagi setiap objek dengan memakai pusat klaster yang baru Nilai SSE yang baru:
    Persamaan Nilai SSE
    = 1.272+1.032+0.252+1.032+0.352+0.752+0.792+1.062 = 6.25

Hasil Akhir

Contoh Kasus Algorimta Clustering dalam Data Mining: Metode Partisi - Hasil Akhir
Contoh Kasus Algorimta Clustering dalam Data Mining: Metode Partisi – Hasil Akhir
  • Dapat dilihat pada tabel. Tidak ada perubahan anggota lagi pada masing-masing cluster
  • Hasil akhir yaitu: cluster1={A,E,G,H}, dan cluster2={B,C,D,F} Dengan nilai SSE = 6,25 dan jumlah iterasi 3

Kelebihan dan Kekurangan pada Metode K-Means

  • Kelebihan :
    • Efisien: O (tkn), di mana n adalah #objek, k adalah #cluster, dan t adalah #iterations. Biasanya, k, t << n.
    • Membandingkan: PAM: O (k (n-k)2), CLARA: O (ks2 + k (n-k))
  • Komentar: Sering berakhir pada optimal lokal
  • Kekurangan :
    • Hanya berlaku untuk objek dalam ruang n-dimensi kontinu
    • Menggunakan metode k-modes untuk data kategorikal
    • Sebagai perbandingan, k-medoids dapat diterapkan pada berbagai data
    • Perlu menentukan k, jumlah cluster, terlebih dahulu (ada cara untuk secara otomatis menentukan k terbaik (lihat Hastie et al., 2009)
    • Peka terhadap data noise dan outliers
    • Tidak cocok untuk menemukan kluster dengan bentuk non-cembung

Variasi dari Metode K-Means

  • Sebagian besar varian k-means yang berbeda
    • Pemilihan sarana awal K-means
    • Perhitungan Dissimilaritas
    • Strategi untuk menghitung sarana klaster
  • Menangani data kategoris: k-mode
    • Mengganti cara cluster dengan mode
    • Menggunakan langkah-langkah ketidaksamaan baru untuk menangani objek kategorikal
    • Menggunakan metode berbasis frekuensi untuk memperbarui mode kluster
    • Campuran data kategorikal dan numerik: metode k-prototype

Metode Clustering K-Medoid

  • K-Medoids Clustering: Temukan objek yang representatif (medoids) dalam klaster
  • PAM (Partisi Sekitar Medoids, Kaufmann & Rousseeuw 1987)
    • Mulai dari seperangkat medoids awal dan secara iteratif mengganti salah satu medoid dengan salah satu non-medoid jika meningkatkan jarak total dari pengelompokan yang dihasilkan.
    • PAM bekerja secara efektif untuk set data kecil, tetapi tidak skala dengan baik untuk set data besar (karena kompleksitas komputasi)
  • Peningkatan efisiensi pada PAM
    • CLARA (Kaufmann & Rousseeuw, 1990): PAM pada sampel
    • CLARANS (Ng & Han, 1994): Pengambilan sampel ulang secara acak

Baiklah sampai di sini saja pembahasan tentang Algorimta Clustering Data Mining: Metode Partisi. Terima kasih telah membaca artikel ini.

Baca Juga :
Memahami Konsep Data Mining Beserta Prosesnya
Metodologi CRISP-DM Beserta Contoh Kasusnya

Tinggalkan komentar

error: Content is protected !!