Algoritma Naive Bayes Inference Clustering 4

Algoritma Naive Bayes Inference Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor.
Algoritma ini merupakan contoh penerapan kasus yang lain dari Algoritma Naive Bayes yang sudah pernah dibahas sebelumnya. Pada contoh sebelumnya, Algoritma Naive Bayes yang standar digunakan sebagai perhitungan untuk pengambilan keputusan. Pada contoh kasus kali ini, algoritma tersebut akan diterapkan sebagai pemecahan kasus dari pengelompokan atau klasifikasi data.

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:

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

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Jumlah Cluster
Jumlah Cluster adalah jumlah dari pengelompokan data yang ingin dilakukan
Jumlah Cluster nilainya harus diantara 2 dan jumlah data
Diasumsikan dalam kasus ini, jumlah pengelompokan data ada 2 kelompok, yaitu kelompok Diterima dan Ditolak

Const jumlahCluster As Integer = 2

* Tentukan Jumlah Iterasi
Diasumsikan dalam kasus ini, jumlah iterasi adalah 100

Const jumlahIterasi As Integer = 100

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Pengelompokan untuk masing-masing kriteria
Jumlah pengelompokan bebas tergantung keinginan
Contoh dalam kasus ini:
Kriteria umur hanya dikelompokan menjadi 3 bagian yaitu untuk umur dibawah 40, 41 sampai dengan 50, diatas 50
Kriteria jenis kelamin dikelompokan menjadi 2 bagian yaitu untuk laki-laki dan perempuan
Kriteria skor kepribadian dikelompokan menjadi 4 bagian yaitu untuk skor dibawah 4, 4 sampai dengan 5, 5 sampai dengan 6, diatas 6

Dim atribut As String()() = New String(2)() {}
atribut(0) = New String() {"Dibawah 40", "41 s/d 50", "Diatas 50"}
atribut(1) = New String() {"Laki-laki", "Perempuan"}
atribut(2) = New String() {"Dibawah 4", "4 s/d 5", "5 s/d 6", "Diatas 6"}

2. Tentukan matriks data awal untuk data yang sudah mengalami pengelompokan data sesuai kriteria diatas

Dim dataAwal As Integer()() = New Integer(data.Length - 1)() {}
For i As Integer = 0 To data.Length - 1
	dataAwal(i) = New Integer(atribut.Length - 1) {}

	For j As Integer = 0 To atribut.Length - 1
		Dim v As String = ""
		If j = 0 Then
			If data(i)(j) <= 40 Then
				v = atribut(j)(0)
			ElseIf data(i)(j) <= 50 Then
				v = atribut(j)(1)
			ElseIf data(i)(j) > 50 Then
				v = atribut(j)(2)
			End If
		ElseIf j = 1 Then
			v = data(i)(j)
		ElseIf j = 2 Then
			If data(i)(j) <= 4 Then
				v = atribut(j)(0)
			ElseIf data(i)(j) <= 5 Then
				v = atribut(j)(1)
			ElseIf data(i)(j) <= 6 Then
				v = atribut(j)(2)
			ElseIf data(i)(j) > 6 Then
				v = atribut(j)(3)
			End If
		End If

		dataAwal(i)(j) = lookup(j)(v)
	Next
Next

3. Inisialisasi matriks jumlah data per atribut per cluster untuk digunakan dalam teknik Laplacian Smoothing,
yaitu dengan memberi nilai awal semua data dengan nilai 1
Teknik ini dimaksudkan agar perhitungan probabilitas dalam masing-masing cluster tidak ada yang bernilai 0

Dim jumlahDataPerAtributPerCluster As Integer()()() = New Integer(atribut.Length - 1)()() {}
For i As Integer = 0 To jumlahDataPerAtributPerCluster.Length - 1
	jumlahDataPerAtributPerCluster(i) = New Integer(atribut(i).Length - 1)() {}

	For j As Integer = 0 To jumlahDataPerAtributPerCluster(i).Length - 1
		jumlahDataPerAtributPerCluster(i)(j) = New Integer(jumlahCluster - 1) {}

		For k As Integer = 0 To jumlahDataPerAtributPerCluster(i)(j).Length - 1
			jumlahDataPerAtributPerCluster(i)(j)(k) = 1
		Next
	Next
Next

4. Lakukan pengelompokan data untuk matriks yang sudah mengalami pengelompokan data
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 4a – 4f)

Dim daftarCluster As Integer() = Cluster(dataAwal, jumlahCluster, jumlahIterasi, jumlahDataPerAtributPerCluster, jumlahDataPerCluster, True)

4a. Inisialisasi matriks kelompok data dengan nilai -1

Dim daftarCluster As Integer() = New Integer(dataAwal.Length - 1) {}
For i As Integer = 0 To daftarCluster.Length - 1
	daftarCluster(i) = -1
Next

4b. Cari indeks yang cukup baik untuk masing-masing cluster

Dim indeksCukupBaik As Integer() = CariIndeksCukupBaik(dataAwal, jumlahCluster, jumlahIterasi)

* Gunakan fungsi ini untuk mencari indeks yang cukup baik pada masing-masing cluster
Fungsi ini mengembalikan nilai indeks data yang cukup baik,
dimana nilai total delta yang dihasilkan adalah tertinggi, tetapi tidak boleh ada indeks yang sama muncul 2 kali
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Function CariIndeksCukupBaik(dataAwal As Integer()(), n As Integer, jumlahIterasi As Integer) As Integer()

4b1. Cari indeks acak sejumlah banyak cluster, dengan indeks acak yang tidak boleh ada yang sama

Dim d As New Dictionary(Of Integer, Boolean)()
Dim indeksAcak As Integer() = New Integer(n - 1) {}
Dim ct As Integer = 0
Dim batasPerulangan As Integer = 0
While ct < n AndAlso batasPerulangan < 10000
	batasPerulangan += 1
	Dim idx As Integer = random.[Next](0, dataAwal.Length)
	If d.ContainsKey(idx) = False Then
		indeksAcak(ct) = idx
		d(idx) = True

		ct += 1
	End If
End While

4b2. Hitung total delta yaitu jumlah delta pada pada setiap indeks acak

Dim jumlahKolom As Integer = dataAwal(0).Length
Dim totalDelta As Integer = 0
For j As Integer = 0 To indeksAcak.Length - 2
	For k As Integer = j + 1 To indeksAcak.Length - 1
		Dim a As Integer = indeksAcak(j)
		Dim b As Integer = indeksAcak(k)

		'Hitung nilai delta, yaitu seberapa banyak perbedaan kelompok kriteria data antara data pada indeks acak a dan b
		'----------
		Dim delta As Integer = 0
		For l As Integer = 0 To jumlahKolom - 1
			If dataAwal(a)(l) <> dataAwal(b)(l) Then
				delta += 1
			End If
		Next
		'----------

		totalDelta += delta
	Next
Next

4b3. Jika total delta yang telah dihitung ternyata lebih dari delta tertinggi, maka ambil indeks nya sebagai indeks terbaik

If totalDelta > deltaTertinggi Then
	deltaTertinggi = totalDelta
	Array.Copy(indeksAcak, hasil, hasil.Length)
End If

4c. Masukkan data dengan indeks terpilih ke dalam masing-masing cluster terpilih

For i As Integer = 0 To indeksCukupBaik.Length - 1
	Dim idx As Integer = indeksCukupBaik(i)
	daftarCluster(idx) = i
Next

4d. Update matriks jumlah data per attribut per cluster sesuai data masukan sebelumnya

For i As Integer = 0 To indeksCukupBaik.Length - 1
	Dim idx As Integer = indeksCukupBaik(i)
	For j As Integer = 0 To dataAwal(idx).Length - 1
		Dim v As Integer = dataAwal(idx)(j)
		jumlahDataPerAtributPerCluster(j)(v)(i) += 1
	Next
Next

4e. Update matriks jumlah data per cluster sesuai data masukan sebelumnya

For i As Integer = 0 To jumlahDataPerCluster.Length - 1
	jumlahDataPerCluster(i) += 1
Next

4f. Lakukan perulangan pada setiap data awal

4f1. Hitung nilai probabilitas data ini terhadap setiap cluster

Dim ProbabilitasPerCluster As Double() = HitungProbabilitasPerCluster(dataAwal(i), jumlahDataPerAtributPerCluster, jumlahDataPerCluster, isBobotAntarKriteriaSama)

4f2. Cari cluster dengan probabilitas paling tinggi
Masukkan data ini kedalam cluster tersebut

Dim probabilitasTertinggi As Double = 0.0
Dim c As Integer = 0

For j As Integer = 0 To ProbabilitasPerCluster.Length - 1
	If ProbabilitasPerCluster(j) > probabilitasTertinggi Then
		probabilitasTertinggi = ProbabilitasPerCluster(j)
		c = j
	End If
Next
daftarCluster(i) = c

4f3. Update matriks jumlah data per attribut per cluster sesuai data masukan sebelumnya
Update matriks jumlah data per cluster sesuai data masukan sebelumnya

For j As Integer = 0 To dataAwal(i).Length - 1
	Dim v As Integer = dataAwal(i)(j)
	jumlahDataPerAtributPerCluster(j)(v)(c) += 1
Next

jumlahDataPerCluster(c) += 1

* Gunakan fungsi ini untuk menghitung nilai probabilitas data pada semua cluster
Nilai pengembalian fungsi ini adalah nilai probabilitas data terhadap masing-masing cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Function HitungProbabilitasPerCluster(tupleAsInt As Integer(), jumlahDataPerAtributPerCluster As Integer()()(), jumlahDataPerCluster As Integer(), isBobotAntarKriteriaSama As Boolean) As Double()
	'Hitung probabilitas parsial data terhadap semua cluster
	Dim probabilitasParsial As Double() = New Double(jumlahDataPerCluster.Length - 1) {}
	For c As Integer = 0 To probabilitasParsial.Length - 1
		Dim prob As Double = HitungProbabilitasParsial(tupleAsInt, jumlahDataPerAtributPerCluster, jumlahDataPerCluster, c, isBobotAntarKriteriaSama)
		probabilitasParsial(c) = prob
	Next

	'Hitung Probabilitas untuk tiap-tiap cluster dengan rumus
	'p = nilai probabilitas parsial / jumlah semua probabilitas parsial
	Dim sumOfPartials As Double = 0.0
	For i As Integer = 0 To probabilitasParsial.Length - 1
		sumOfPartials += probabilitasParsial(i)
	Next

	Dim hasil As Double() = New Double(jumlahDataPerCluster.Length - 1) {}
	For i As Integer = 0 To hasil.Length - 1
		hasil(i) = probabilitasParsial(i) / sumOfPartials
	Next

	Return hasil
End Function

* Gunakan fungsi ini untuk menghitung nilai probabilitas parsial
Nilai pengembalian fungsi ini adalah nilai probabilitas parsial data pada matriks dataAwal terhadap cluster c
Nilai probabilitas dihitung dengan rumus:
probabilitas pada cluster x = probabilitas kriteria 1 pada cluster x * probabilitas kriteria 2 pada cluster x * … * probabilitas kriteria n pada cluster x
Teknik Laplacian Smoothing digunakan untuk menghindari probabilitas yang menjadi 0 pada awal perhitungan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Function HitungProbabilitasParsial(dataAwal As Integer(), jumlahDataPerAtributPerCluster As Integer()()(), jumlahDataPerCluster As Integer(), c As Integer, isBobotAntarKriteriaSama As Boolean) As Double
	Dim jumlahTotal As Integer = 0
	For i As Integer = 0 To jumlahDataPerCluster.Length - 1
		jumlahTotal += jumlahDataPerCluster(i)
	Next
	Dim jumlahCluster As Integer = jumlahDataPerCluster.Length

	'Jumlah data yang masuk kedalam cluster c ditambah faktor Laplacian
	Dim jumlahClusterLaplacian As Integer = jumlahDataPerCluster(c) + jumlahCluster

	'Probabilitas untuk semua atribut dan probabilitas total
	Dim prob As Double() = New Double(jumlahDataPerAtributPerCluster.Length) {}

	'Hitung Probabilitas untuk masing-masing kriteria
	For i As Integer = 0 To prob.Length - 2
		Dim j As Integer = dataAwal(i)

		Dim p As Double = jumlahDataPerAtributPerCluster(i)(j)(c) / (1.0 * jumlahClusterLaplacian)
		prob(i) = p
	Next

	' Hitung probabilitas total
	Dim clusterP As Double = 0.0
	If isBobotAntarKriteriaSama = True Then
		clusterP = 1.0 / jumlahCluster
	Else
		clusterP = jumlahDataPerCluster(c) / (1.0 * jumlahTotal)
	End If
	prob(prob.Length - 1) = clusterP

	'Hitung nilai akhir dengan cara perkalian antar semua probabilitas
	Dim hasil As Double = 1.0
	For i As Integer = 0 To prob.Length - 1
		hasil *= prob(i)
	Next

	Return hasil
End Function

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

If j = 0 Then
	total(k) += atribut(0).Length - v
Else
	total(k) += v
End If

6. 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 total(0) > total(1) Then
	Console.WriteLine("Nilai Kelompok pertama (" & total(0) & ") lebih dari Kelompok kedua (" & total(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Diterima")
	Console.WriteLine("Kelompok kedua adalah kelompok Ditolak")
Else
	Console.WriteLine("Nilai Kelompok pertama (" & total(0) & ") kurang dari Kelompok kedua (" & total(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Ditolak")
	Console.WriteLine("Kelompok kedua adalah kelompok Diterima")
End If

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.