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

Dalam algoritma Clustering, selain metode partisi terdapat metode lain diantaranya: Hierarki, Density-Based dan Grid-Based. Berikut ini penjelasan untuk masing masing metode tersebut.

Metode Clustering Hierarki

Metode Hierarki menggunakan matriks jarak sebagai kriteria pengelompokan. Metode ini tidak memerlukan jumlah cluster k sebagai input, tetapi membutuhkan kondisi terminasi.

AGNES (Agglomerative Nesting)

Diperkenalkan di Kaufmann dan Rousseeuw (1990). AGNES diimplementasikan dalam paket statistik, misalnya: S-PLUS. Metode yang digunakan yakni tautan tunggal dan matriks ketidaksamaan. Menggabungkan simpul yang memiliki sedikit perbedaan. Kemudianb erlanjut dengan cara yang tidak menurun. Terakhir, semua node masuk ke klaster yang sama.

Dendrogram: Menunjukkan bagaimana klaster digabungkan

Mengurai objek data menjadi beberapa level partisi bersarang (pohon cluster), yang disebut dendrogram.
Pengelompokan objek data diperoleh dengan memotong dendrogram pada tingkat yang diinginkan, kemudian masing-masing komponen yang terhubung membentuk sebuah kluster.

DIANA (Divisive Analysis)

Diperkenalkan di Kaufmann dan Rousseeuw (1990). Diterapkan dalam paket analisis statistik, misalnya, S-PLUS. Urutannya terbalik dari AGNES. Terakhir, setiap node membentuk sebuah cluster sendiri.

Jarak Antar Klaster

• Single link: jarak terkecil antara elemen dalam satu cluster dan elemen di yang lain, mis., Dist (K_i, K_j) = min (t_ip, t_jq)
• Complete link: jarak terbesar antara elemen dalam satu cluster dan elemen di yang lain, mis., Dist (K_i, K_j) = maks (t_ip, t_jq)
• Average: rata-rata jarak antara elemen dalam satu kluster dan elemen di yang lain, mis., Dist (K_i, K_j) = rata-rata (t_ip, t_jq)
• Centroid: jarak antara centroid dua klaster, mis. Dist (K_i, K_j) = dist (C_i, C_j)
  • Medoid: jarak antara medoid dua kelompok, yaitu, dist (K_i, K_j) = dist (M_i, M_j)

Centroid, Radius dan Diameter dari sebuah klaster (untuk data set numerik)

• Centroid: “tengah” dari sebuah cluster
• Radius: akar kuadrat dari jarak rata-rata dari titik mana pun dari cluster ke centroid
• Diameter: akar kuadrat dari rata-rata jarak kuadrat antara semua pasangan titik dalam klaster

Metode Clustering Density-Based

Clustering berdasarkan pada kepadatan (kriteria cluster lokal), seperti density-connected point. Fitur utamanya yakni: Menemukan kelompok dengan bentuk acak, Menangani Noise, One Scan dan Perlu parameter density sebagai kondisi terminasi. Beberapa studi yang berkaitan yakni: DBSCAN: Ester, dkk. (KDD’96), OPTIK: Ankerst, dkk (SIGMOD’99), DENCLUE: Hinneburg & D. Keim (KDD’98) dan CLIQUE: Agrawal, dkk. (SIGMOD’98) (lebih ke grid-based).

Konsep Dasar Klastering Density-Based

• Dua Komponen:
  • Eps: Jari-jari maksimum lingkungan
  • MinPts: Jumlah minimum dari poin di Eps-neighbourhood pada titik itu
• N_EPS(q):{p milik D | dist (p, q) ≤ Eps}
• Directly density-reachable: Titik p secara langsung dapat dicapai dari titik q w.r.t. Eps, MinPts jika
  • p milik N_EPS (q)
  • kondisi titik inti:
    | N_EPS (q)| ≥ MinPts

Density-Reachable dan Density-Connected

• Density-Reachable:
  • Titik p dapat dijangkau kerapatan dari titik q w.r.t. Eps, MinPts jika ada rantai poin p₁,…, p_n, p₁ = q, p_n = p sedemikian rupa sehingga p_i+1 secara langsung dapat dijangkau kepadatannya dari p_i

• Density-Connected
  • Suatu titik p terhubung dengan densitas ke titik q w.r.t. Eps, MinPts jika ada titik o sedemikian rupa sehingga keduanya, p dan q dapat dijangkau dengan kepadatan dari o w.r.t. Eps dan MinPts

DBSCAN: Density-Based Spatial Clustering of Applications with Noise

Bergantung pada gagasan density-based dari klaster: sebuah klaster didefinisikan sebagai set maksimal titik yang terhubung dengan kerapatan. Menemukan klaster dengan bentuk acak dalam basis data spasial dengan noise

Algoritma DBSCAN

1. Pilih titik secara sewenang-wenang hal
2. Ambil semua titik kerapatan yang dapat dijangkau dari p w.r.t. Eps dan MinPts
3. Jika p adalah titik inti, sebuah cluster terbentuk
4. Jika p adalah titik perbatasan, tidak ada titik yang dapat dijangkau kepadatan dari p dan DBSCAN mengunjungi titik berikutnya dari basis data
5. Lanjutkan proses sampai semua poin telah diproses

Jika indeks spasial digunakan, kompleksitas komputasi DBSCAN adalah O (nlogn), di mana n adalah jumlah objek database. Kalau tidak, kompleksitasnya adalah O (n2)

DBSCAN: Sensitif terhadap Parameters

OPTICS: Ordering Points To Identify the Clustering Structure

Dikenalkan oleh Ankerst, Breunig, Kriegel, dan Sander (SIGMOD’99. Menghasilkan pesanan khusus dari database dengan struktur pengelompokan berbasis kepadatan. Pemesanan cluster ini berisi info sama dengan clustering berbasis kepadatan yang terkait dengan berbagai pengaturan parameter. Baik untuk analisis klaster otomatis dan interaktif, termasuk menemukan struktur pengelompokan intrinsik. Dapat direpresentasikan secara grafis atau menggunakan teknik visualisasi

OPTICS: Beberapa Perpanjangan dari DBSCAN

• Berbasis indeks: k = # dimensi, N: # poin
  • Kompleksitas: O (N * logN)
• Jarak Inti dari objek p: nilai terkecil ε sedemikian rupa sehingga ε-neighborhood p memiliki setidaknya objek MinPts
  • Misalkan N_ε (p): ε-neighborhood of p, ε adalah nilai jarak
  • Core-distance_ε, _MinPts (p) = Tidak ditentukan jika kartu (N_ε (p)) <MinPts MinPts-distance (p), dan sebaliknya
• Reachability Jarak objek p dari objek inti q adalah nilai radius min yang membuat kerapatan p dapat dijangkau dari q
  • Reachability-distance_ε, _MinPts (p, q) = Tidak terdefinisi jika q bukan max objek inti (jarak-inti (q), jarak (q, p)), dan sebaliknya

Core Distance & Reachability Distance

Density-Based Clustering: OPTICS & Applications

Metode Clustering Grid-Based

Menggunakan struktur data grid multi-resolusi. Beberapa metode terkait Grid-Based yakni:

• STING (a STatistical INformation Grid approach) oleh Wang, Yang dan Muntz (1997)
• WaveCluster oleh Sheikholeslami, Chatterjee, dan Zhang (VLDB’98)
  • Pendekatan multi-resolusi clustering menggunakan metode wavelet
• CLIQUE: Agrawal, dkk. (SIGMOD’98)
  • Baik berbasis grid dan clustering

STING: A Statistical Information Grid Approach

• Wang, Yang dan Muntz (VLDB’97)
• Area spasial dibagi menjadi sel-sel persegi panjang
• Ada beberapa tingkat sel yang terkait dengan berbagai tingkat resolusi

Metode Clustering STING

• Setiap sel di tingkat tinggi dipartisi menjadi sejumlah sel yang lebih kecil di tingkat bawah berikutnya
• Info statistik setiap sel dihitung dan disimpan sebelumnya dan digunakan untuk menjawab pertanyaan
• Parameter sel tingkat yang lebih tinggi dapat dengan mudah dihitung dari parameter sel tingkat yang lebih rendah
  • count, mean, s, min, max
  • jenis distribusi — normal, uniform, dll.
• Gunakan pendekatan top-down untuk menjawab pertanyaan data spasial
• Mulai dari lapisan yang dipilih sebelumnya — biasanya dengan sejumlah kecil sel
• Untuk setiap sel di level saat ini hitung interval kepercayaan diri

Algoritma dan Analisis STING

• Hapus sel-sel yang tidak relevan dari pertimbangan lebih lanjut
• Ketika selesai memeriksa lapisan saat ini, lanjutkan ke level bawah berikutnya
• Ulangi proses ini sampai lapisan bawah tercapai
• Keuntungan:
  • Pemutakhiran yang bebas kueri, mudah diparalelkan, tambahan
  • O (K), di mana K adalah jumlah sel kisi di tingkat terendah
• Kekurangan:
  • Semua batas cluster adalah horisontal atau vertikal, dan tidak ada batas diagonal yang terdeteksi

CLIQUE (Clustering In QUEst)

• Agrawal, Gehrke, Gunopulos, Raghavan (SIGMOD’98)
• Secara otomatis mengidentifikasi subruang dari ruang data dimensi tinggi yang memungkinkan pengelompokan yang lebih baik daripada ruang asli
• CLIQUE dapat dianggap sebagai berbasis kepadatan dan berbasis grid
  • Ini membagi setiap dimensi ke dalam jumlah interval panjang yang sama
  • Ini mem-partisi ruang data m-dimensi menjadi unit persegi panjang yang tidak tumpang tindih
  • Suatu unit padat jika fraksi total titik data yang terkandung dalam unit melebihi parameter model input
  • Cluster adalah set maksimal unit padat yang terhubung dalam subruang

CLIQUE: Langkah Utama

1. Partisi ruang data dan temukan jumlah titik yang ada di dalam setiap sel partisi.
2. Identifikasi subruang yang berisi cluster menggunakan prinsip Apriori
3. Identifikasi kelompok
   ⦁ Tentukan unit padat di semua subruang minat
   ⦁ Tentukan unit padat yang terhubung di semua ruang bagian minat
4. Hasilkan deskripsi minimal untuk kluster
   ⦁ Tentukan daerah maksimal yang mencakup sekelompok unit padat yang terhubung untuk setiap kelompok
   ⦁ Penentuan tutupan minimal untuk setiap kluster

Kelebihan dan Kekurangan CLIQUE

• Kelebihan:
  1. secara otomatis menemukan subruang dengan dimensi tertinggi sehingga terdapat kluster kepadatan tinggi di subruang tersebut
  2. tidak sensitif terhadap urutan catatan dalam input dan tidak menganggap beberapa distribusi data kanonik
  3. skala secara linier dengan ukuran input dan memiliki skalabilitas yang baik karena jumlah dimensi dalam data meningkat
• Kekurangan:
  1. Keakuratan hasil pengelompokan dapat terdegradasi dengan mengorbankan kesederhanaan metode ini

Baca Juga:
Algoritma Clustering dalam Data Mining: Metode Partisi