Algoritma DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 4

Algoritma DBSCAN (Density-Based Spatial Clustering of Applications with Noise) adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor.
Masing-masing data / titik yang ada akan dibagi menjadi 3 bagian, yaitu:

• Titik Pusat / Core

Sebuah titik disebut sebagai titik pusat apabila terdapat sejumlah titik lain yang berada dalam radius titik tersebut

• Titik Terjangkau / Reachable

Sebuah titik disebut sebagai titik terjangkau apabila titik tersebut terhubung secara tidak langsung dengan titik pusat

• Titik Noise

Sebuah titik disebut sebagai titik Noise apabila titik tersebut tidak bisa dijadikan titik pusat, dan tidak dapat dijangkau dengan titik core terdekat

Diasumsikan ada 13 data pelanggan, yaitu Pelanggan A,B,C,D,E,F,G,H,I,J,K,L,M
Masing-masing pelanggan memiliki kriteria, yaitu umur, jenis kelamin, skor kepribadian
Maka tentukan kelompok data pelanggan menjadi 2 bagian, yaitu kelompok data Diterima atau Ditolak
Diasumsikan 13 data tersebut adalah sebagai berikut:

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:
Untuk Kriteria Jenis Kelamin:
Laki-laki dilambangkan dengan angka -1
Perempuan dilambangkan dengan angka +1

Dim data(12)() As Double
data(0) = New Double() {44, -1, 3.55}
data(1) = New Double() {52, +1, 4.71}
data(2) = New Double() {60, +1, 6.56}
data(3) = New Double() {56, -1, 6.8}
data(4) = New Double() {51, -1, 6.94}
data(5) = New Double() {46, +1, 6.52}
data(6) = New Double() {48, -1, 4.25}
data(7) = New Double() {58, +1, 5.71}
data(8) = New Double() {47, +1, 6.05}
data(9) = New Double() {52, -1, 5}
data(10) = New Double() {42, -1, 5.7}
data(11) = New Double() {59, -1, 3.9}
data(12) = New Double() {49, +1, 4.85}

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan eps, yaitu radius sebuah titik untuk membentuk sebuah cluster
Diasumsikan dalam kasus ini, eps bernilai 2.5

Dim eps As Double = 2.5

* Tentukan jumlah titik minimal dalam sebuah cluster
Diasumsikan dalam kasus ini, jumlah titik minimal adalah 3

Const jumlahTitikMinimal As Integer = 3

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan pada data awal (poin 1 – 6)

1. Pangkatkan nilai eps sebanyak jumlah kriteria yang ada

eps = Math.Pow(eps, 3)

2. Lakukan perulangan pada setiap data
Apabila data tersebut masih belum masuk ke dalam cluster,
Maka lakukan perhitungan berikutnya

If t.idxCluster = Titik.UNCLASSIFIED Then
. . .

3. Cari semua titik yang berada pada radius titik terpilih
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim tmpDaftarTitik As List(Of Titik) = CariSemuaTItikDalamRadius(daftarTitik, t, eps)

* Gunakan fungsi ini untuk mencari semua titik yang berada pada radius titik terpilih
Hitung jarak pada masing-masing titik
Apabila jarak tersebut masih dalam batas nilai eps, maka masukkan titik tersebut sebagai titik jawaban

Private Function CariSemuaTItikDalamRadius(daftarTitik As List(Of Titik), p As Titik, eps As Double) As List(Of Titik)
	Dim hasil As New List(Of Titik)()
	For i As Integer = 0 To daftarTitik.Count - 1
		Dim jarak As Integer = Titik.HitungJarak(p, daftarTitik(i))
		If jarak <= eps Then
			hasil.Add(daftarTitik(i))
		End If
	Next
	Return hasil
End Function

* Gunakan fungsi ini untuk menghitung jarak antara 2 titik
Rumus yang digunakan adalah jumlah dari kuadrat selisih pada masing-masing kriteria

Public Shared Function HitungJarak(t1 As Titik, t2 As Titik) As Integer
	Dim selisihX As Integer = t2.X - t1.X
	Dim selisihY As Integer = t2.Y - t1.Y
	Dim selisihZ As Integer = t2.Z - t1.Z
	Return selisihX * selisihX + selisihY * selisihY + selisihZ * selisihZ
End Function

4. Lakukan pencarian perluasan cluster pada masing-masing daftar titik (poin 4a – 4c)

4a. Jika jumlah titik yang ditemukan kurang dari jumlah kepadatan minimal,
Maka titik ini termasuk dalam NOISE

If tmpDaftarTitik.Count < jumlahTitikMinimal Then
	t.idxCluster = Titik.NOISE
	Continue For
. . .
Dim means As Double()() = HitungMeansAwal(jumlahCluster, dataAwal)

4b. Jika jumlah titik yang ditemukan memenuhi batas jumlah kepadatan minimal,
maka masukkan semua titik tersebut ke dalam cluster terpilih
dan keluarkan titik terpilih dari daftar tersebut

For j As Integer = 0 To tmpDaftarTitik.Count - 1
	tmpDaftarTitik(j).idxCluster = idxCluster
Next
tmpDaftarTitik.Remove(t)

4c. Lakukan proses perhitungan pada semua titik yang telah ditemukan (poin 4c1 – 4c3)

While tmpDaftarTitik.Count > 0
	Dim titikTujuan As Titik = tmpDaftarTitik(0)
. . .

4c1. Lakukan perhitungan cluster apabila titik terpilih dipakai sebagai titik tujuan

Dim tmpDaftarTitikTujuan As List(Of Titik) = CariSemuaTItikDalamRadius(daftarTitik, titikTujuan, eps)

4c2. Apabila jumlah titik tujuan yang ditemukan lebih dari jumlah kepadatan minimal,
maka lanjutkan ke perhitungan berikutnya

If tmpDaftarTitikTujuan.Count >= jumlahTitikMinimal Then
. . .

4c3. Lakukan perulangan pada semua titik tujuan yang telah didapatkan
Apabila titik tujuan belum termasuk ke dalam cluster,
maka masukkan titik tujuan tersebut kedalam daftar titik, dan catat clusternya

If titikTujuanTerpilih.idxCluster = Titik.UNCLASSIFIED OrElse titikTujuanTerpilih.idxCluster = Titik.NOISE Then
	If titikTujuanTerpilih.idxCluster = Titik.UNCLASSIFIED Then
		tmpDaftarTitik.Add(titikTujuanTerpilih)
	End If
	titikTujuanTerpilih.idxCluster = idxCluster
End If

5. Urutkan data berdasarkan cluster yang telah dipilih sebelumnya

Dim idxClusterTerakhir As Integer = daftarTitik.OrderBy(Function(p) p.idxCluster).Last().idxCluster

6. Masukkan masing-masing titik ke dalam jawaban cluster akhir

If idxClusterTerakhir >= 1 Then
	For i As Integer = 0 To idxClusterTerakhir - 1
		daftarCluster.Add(New List(Of Titik)())
	Next

	For Each t As Titik In daftarTitik
		If t.idxCluster > 0 Then
			daftarCluster(t.idxCluster - 1).Add(t)
		End If
	Next
End If

7. Hitung nilai cluster pada masing-masing cluster
Nilai pada setiap cluster dihitung dari penjumlahan data pada masing-masing kolom
Pada Kriteria umur, semakin rendah nilainya, maka semakin tinggi nilai kolomnya, dan sebaliknya.
Pada Kriteria jenis kelamin dan skor kepribadian, semakin tinggi nilainya, maka semakin tinggi nilai kolomnya, dan sebaliknya.

nilaiCluster(i) += (10 - t.X / 10) + t.Y + t.Z

8. Lihat kembali matriks data awal yang sudah terkelompok
Bandingkan nilai total data antara kedua cluster
Nilai total data yang lebih tinggi akan masuk ke dalam kelompok Diterima, sedangkan nilai total data yang lebih rendah akan masuk ke dalam kelompok Ditolak

If nilaiCluster(0) > nilaiCluster(1) Then
	Console.WriteLine("Nilai Kelompok pertama (" & nilaiCluster(0) & ") lebih dari Kelompok kedua (" & nilaiCluster(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Diterima")
	Console.WriteLine("Kelompok kedua adalah kelompok Ditolak")
Else
	Console.WriteLine("Nilai Kelompok pertama (" & nilaiCluster(0) & ") kurang dari Kelompok kedua (" & nilaiCluster(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Ditolak")
	Console.WriteLine("Kelompok kedua adalah kelompok Diterima")
End If

9. Lakukan pencatatan data pada setiap data yang termasuk sebagai NOISE
NOISE adalah semua data yang tidak berhubungan dengan cluster apapun dan tidak bisa membentuk cluster sendiri

For Each t As Titik In daftarTitik
	If t.idxCluster = Titik.NOISE Then
		Console.Write("Pelanggan " & t.Nama.ToString.PadRight(3))
		Console.Write(t.X.ToString().PadRight(2) & " ")
		Console.Write(IIf(t.Y = -1, "Laki-Laki", IIf(t.Y = +1, "Perempuan", "")).ToString().PadRight(5) & " ")
		Console.Write(t.Z.ToString().PadRight(5) & " ")
		Console.WriteLine()
	End If
Next

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung data nama, nilai pada masing-masing kriteria, dan indeks cluster dimana titik tersebut berada. Deklarasi Class Titik adalah sebagai berikut:

Class Titik
    Public Const NOISE As Integer = -1
    Public Const UNCLASSIFIED As Integer = 0

    Public Nama As String
    Public X As Double, Y As Double, Z As Double
    Public idxCluster As Integer

    Public Sub New(Nama As String, x As Double, y As Double, z As Double)
        Me.Nama = Nama
        Me.X = x
        Me.Y = y
        Me.Z = z
    End Sub
End Class

Hasil akhir adalah: (klik untuk perbesar gambar)

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.