Dbscan.docx

1.

Density-Based Density-Based merupakan suatu metode yang dikembangkan berdasarkan kepadatan

(density) tertentu. Metode ini menganggap suatu cluster sebagai suatu area yang penuh dengan objek-objek yang padat dan hanya dipisahkan oleh area yang memiliki kepadatan rendah (noise).

2.

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) DBSCAN merupakan algoritma yang mengelompokkan objek-objek yang memiliki

kepadatan yang tinggi ke dalam cluster-cluster dan mengelompokkan objek-objek yang memiliki kepadatan yang rendah ke dalam suatu noise. DBSCAN dengan kata lain, mengelompokkan objekobjek yang saling berkaitan ke dalam cluster-cluster dan menganggap objek-objek yang tidak masuk ke dalam cluster manapun sebagai noise.

3.

Konsep Kepadatan (Density Concept) Jumlah cluster yang dihasilkan sudah ditentukan sendiri oleh DBSCAN sehingga kita tidak

perlu menentukan jumlah cluster yang diinginkan. Namun, DBSCAN memerlukan dua input-an lain, yaitu sebagai berikut. a.

MinPts, MinPts merupakan jumlah objek minimal dalam suatu cluster.

b.

Eps, Eps merupakan nilai jarak antar objek yang menjadi dasar pembentukan neighborhood dari suatu titik objek. Neighborhood yang terletak di dalam jarak suatu objek data maka disebut -Neighborhood

dari suatu objek data. Jika -Neighborhood dari suatu objek berisi paling sedikit sejumlah MinPts, maka objek tersebut disebut core object. -Neighborhood yang jumlah objek datanya lebih sedikit daripada -Neighborhood dari core object disebut border points. Gambar berikut ini menunjukkan bagian mana yang termasuk core object dan yang termasuk border points dengan menggunakan contoh MinPts=5 dan Eps=1.

DBSCAN menemukan cluster-cluster dengan cara memeriksa -Neighborhood dari tiaptiap point dalam database. Jika -Neighborhood dari point p melebihi atau sama dengan MinPts, maka diciptakan suatu cluster baru dengan p sebagai core object-nya. DBSCAN kemudian secara iteratif mengumpulkan secara langsung objek-objek densityreachable dari core object tersebut, dimana mungkin melibatkan penggabungan dari beberapa cluster-cluster yang density-reachable.

4.

Directly Density-Reachable Sebuah titik objek dikatakan directly density-reachable dari titik lainnya apabila jarak di

antara mereka tidak lebih dari nilai Eps. Titik q dikatakan directly density-reachable dari titik p jika titik q adalah -Neighborhood titik p dan p adalah core object. Titik p dikatakan sebagai core object apabila jarak dari titik p ke titik yang lainnya tidak lebih dari nilai Eps. Gambar berikut ini menunjukkan contoh directly density-reachable.

5.

Density-Reachable Sebuah titik objek dikatakan density-reachable dari titik objek lainnya jika ada suatu rantai

yang menghubungkan keduanya yang berisi hanya titik-titik yang directly density-reachable dari titik-titik sebelumnya. Gambar berikut ini menunjukkan contoh density-reachable.

6.

Density-Connected Sebuah objek p adalah density-connected terhadap objek q dengan memperhatikan Eps dan

MinPts dalam set objek D, jika ada sebuah objek o elemen D sehingga p dan q keduanya densityreachable dari o dengan memperhatikan Eps dan MinPts. Gamber berikut menunjukkan contoh density-connected.

7.

Langkah-langkah Algoritma DBSCAN Algoritma DBSCAN secara umum memiliki 5 langkah yang terurut dalam menentukan

cluster-cluster, yaitu sebagai berikut. a.

Pilih point p awal secara acak

b.

Mengambil semua point yang density-reachable terhadap point p

c.

Cluster terbentuk jika point p adalah core object

d.

Namun jika point p merupakan border point, maka DBSCAN akan mengunjungi point selanjutnya dari database

e.

Mengulang dari proses pertama hingga semua point telah diproses