Density Based Methods

Density Based Methods

Merupakan metode yang dikembangkan berdasarkan density (kepadatan) tertentu.  Metode ini menganggap cluster sebagai suatu area yang berisi objek-objek yang padat/sesak, yang dipisahkan oleh area yang memiliki kepadatan rendah (merepresentasikan noise).

1.      DBSCAN : A Density-Based Clustering Method Based on Connected Regions with Sufficiently High Density

DBSCAN (Density-Based Spatial Clustering of Applications with Noise), algoritma menumbuhkan area-area dengan kepadatan yang cukup tinggi ke dalam cluster–cluster and menemukan cluster–cluster dalam bentuk yang sembarang dalam suatu database spatial yang memuat noise. DBSCAN mendefinisikan cluster sebagai himpunan maksimum dari titik-titik kepadatan yang terkoneksi (density-connected). Semua objek yang tidak masuk ke dalam cluster manapun dianggap sebagai noise.

Prinsip-prinsip dasar dari metode density based clustering adalah sebagai berikut :

  • Neighborhood yang terletak di dalam radius Ө disebut –neighorhood dari objek data.
  • Jika –neighborhood dari suatu objek berisi paling sedikit suatu angka yang minimum, MinPts dari suatu objek, objek tersebut disebut core objek.
  • Suatu objek p adalah density reachable dari objek q dengan respek ke dan MinPts dalam suatu set objek D jika terdapat suatu rantai objek p1, p2,…,pn, dimana p1 = q dan pn = p, di mana pi+1 density reachable secara langsung dari pi dengan respek ke dan MinPts, untuk 1 £ i £ n, pi anggota D.
  • Suatu objek p adalah density connected ke objek q dengan respek ke dan MinPts dalam suatu set objek D jika terdapat suatu objek o anggota D di mana ke dua p dan q adalah density reachable dari o dengan respek ke dan MinPts.

DBSCAN menemukan cluster–cluster dengan cara :

  • DBSCAN menelusuri cluster–cluster dengan memeriksa –neighborhood dari tiap-tiap point dalam database. Jika –neighborhood dari point p mengandung lebih dari MinPts, cluster baru dengan p sebagai core object
  • Kemudian DBSCAN secara iteratif mengumpulkan secara langsung objek-objek density reachable dari core object tersebut, di mana mungkin melibatkan penggabungan dari beberapa cluster-cluster density reachable.

 

2.      DENCLUE : Clustering Based on Density Distribution Functions

DENCLUE (Density Based Clustering) adalah merupakan metode clustering yang berdasarkan suatu set fungsi distribusi density. Metode ini dibangun dengan beberapa ide antara lain :

  • Pengaruh tiap-tiap data point dapat secara formal dimodelkan dengan menggunakan fungsi matematika, yang disebut influence function, yang menyatakan pengaruh dari data point terhadap neighborhood-nya.
  • Keseluruhan density dari space data dapat dimodelkan secara analitik sebagai jumlah influence function dari semua data point.
  • Cluster-cluster kemudian dapat ditentukan secara matematik dengan mengidentifikasi density atractor (penarik), yang mana density atractor adalah maksimum lokal dari seluruh density function.

 

Fitur – Fitur Utama Metode DENCLUE :

  • Secara total berdasarkan matematika
  • Baik untuk sekumpulan data yang mmuat banyak noise
  • Selalu mengikuti deskripsi matematik untuk sembarang bentuk cluster dalam data berdimensi tinggi
  • Lebih cepat dibandingkan metode yang lain (DBSCAN)
  • Membutuhkan banyak parameter

 

Referensi:

  • Han, Jiawei & Kamber, Micheline, Data Mining – Consepts and Techniques, Simon Fraser University, USA : Morgan Kaufmann, 2001.
  • jbptunikompp-gdl-selvialore-23379-14-14.perte-s