Associate Rule / Analisa Asosiasi

Association Rule / Analisa Asosiasi adalah suatu proses untuk mencari hubungan antar data dalam suatu kumpulan data yang terjadi pada sebuah kejadian. Contoh yang dibahas kali ini adalah mengenai penentuan aturan pada barang-barang yang laris terjual.

Diasumsikan ada 15 data barang yang dijual, dengan data sebagai berikut

Contoh data barang adalah sebagai berikut:

Const jumlahBarang As Integer = 15
Dim barang(4)() As String
barang(0) = New String() {"Pensil 2B", "Pensil 3B", "Pensil 4B"}
barang(1) = New String() {"Penghapus L3", "Penghapus S1", "Penghapus Dex"}
barang(2) = New String() {"Pena Merah", "Pena Biru", "Pena Hitam"}
barang(3) = New String() {"Penggaris 15cm", "Penggaris 20cm", "Penggaris 30cm"}
barang(4) = New String() {"Buku Tulis", "Buku Gambar", "Komik"}

Kemudian diketahui terdapat 10 transaksi penjualan dalam 1 hari
Maka tentukan aturan untuk setiap pasang barang yang laris terjual
Diasumsikan 10 data transaksi penjualan tersebut adalah sebagai berikut:

Contoh data transaksi adalah sebagai berikut:
Sebagai catatan, masing-masing transaksi diperbolehkan memiliki data barang yang sama persis
Hanya saja dalam kasus ini, tidak terdapat transaksi yang kembar

Dim transaksi(9)() As String
transaksi(0) = New String() {"Pensil 4B", "Penghapus L3", "Penggaris 20cm", "Penggaris 30cm", "Buku Gambar", "Komik"}
transaksi(1) = New String() {"Pensil 2B", "Penghapus S1", "Pena Merah", "Pena Hitam", "Penggaris 30cm", "Komik"}
transaksi(2) = New String() {"Pensil 3B", "Pena Hitam", "Penggaris 15cm", "Buku Tulis", "Buku Gambar"}
transaksi(3) = New String() {"Pensil 2B", "Pensil 4B", "Penggaris 15cm", "Penggaris 20cm"}
transaksi(4) = New String() {"Pensil 3B", "Penghapus L3", "Pena Biru", "Penggaris 20cm", "Penggaris 30cm", "Buku Tulis", "Buku Gambar"}
transaksi(5) = New String() {"Penghapus Dex", "Pena Biru", "Penggaris 30cm"}
transaksi(6) = New String() {"Penghapus L3", "Penghapus S1", "Pena Merah", "Pena Hitam", "Penggaris 15cm", "Penggaris 20cm", "Buku Tulis", "Komik"}
transaksi(7) = New String() {"Pensil 2B", "Penghapus S1", "Penghapus Dex", "Pena Biru", "Pena Hitam", "Buku Gambar"}
transaksi(8) = New String() {"Pensil 2B", "Penghapus L3", "Penggaris 20cm", "Buku Tulis"}
transaksi(9) = New String() {"Pensil 3B", "Pensil 4B", "Penghapus S1", "Pena Biru", "Pena Hitam"}

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan konversi data transaksi ke dalam bentuk angka
Diasumsikan 15 data barang yang ada memiliki indeks yang urut dari angka 1 sampai dengan 15

Dim dataTransaksi As New List(Of Integer())()
For iTransaksi As Integer = 0 To 9
	Dim input(transaksi(iTransaksi).Length - 1) As Integer
	Dim iInput As Integer = 0

	For iTransaksiBarang As Integer = 0 To transaksi(iTransaksi).Length - 1
		Dim bSt As Boolean = True

		For iDataBarangX = 0 To 4
			For iDataBarangY As Integer = 0 To barang(iDataBarangX).Length - 1
				If transaksi(iTransaksi)(iTransaksiBarang) = barang(iDataBarangX)(iDataBarangY) Then
					input(iInput) = iDataBarangX * (barang(iDataBarangX).Length) + iDataBarangY
					iInput += 1
					bSt = False
					Exit For
				End If
			Next
			If Not bSt Then Exit For
		Next
	Next

	dataTransaksi.Add(input)
Next

* Lakukan pencarian itemSet untuk barang terjual yang banyak terjadi (poin 2 – 4)
2. Tentukan nilai persentase support sebagai faktor penentu sebuah barang dapat dikatakan ‘laris terjual’
Dalam kasus ini nilai persentase support bernilai 0.3
Nantinya nilai support ini akan dikalikan dengan jumlah transaksi yang terjadi, dalam kasus ini bernilai 10
sehingga 0.3 * 10 = 3, artinya sebuah barang dikatakan laris terjual apabila terjual sebanyak 3 kali dalam seluruh transaksi

Const MinPersentaseSupport As Double = 0.3

3. Tentukan batas minimal dan batas maksimal kumpulan barang yang akan dihitung
Dalam kasus ini nilai minimal dan maksimal adalah 2 dan 4
Artinya kumpulan barang yang dihitung adalah kumpulan barang dengan jumlah 2 barang, 3 barang, dan 4 barang

Const minJumlahItemSet As Integer = 2
Const maxJumlahItemSet As Integer = 4

4. Lakukan proses pencarian itemSet untuk barang terjual yang terjadi sesuai kriteria tersebut
Hasil perhitungan adalah kumpulan itemSet yang memenuhi kriteria (poin 4a – 4d)

Dim itemSet As List(Of ItemSet) = HitungItemSet(jumlahBarang, dataTransaksi, MinPersentaseSupport, minJumlahItemSet, maxJumlahItemSet)

Memasuki perhitungan pada fungsi HitungItemSet

4a. Hitung jumlah masing-masing barang pada semua transaksi

Dim jumlahDataBarang(jumlahBarang - 1) As Integer
For i As Integer = 0 To dataTransaksi.Count - 1
	For j As Integer = 0 To dataTransaksi(i).Length - 1
		Dim v As Integer = dataTransaksi(i)(j)
		jumlahDataBarang(v) += 1
	Next j
Next i

4b. Untuk setiap data barang yang memenuhi syarat minimum,
tambahkan data barang ke variabel dictItemSetLaris, daftarItemSetLaris, dataBarangValid

For i As Integer = 0 To jumlahDataBarang.Length - 1
	If jumlahDataBarang(i) >= minSupport Then
		dataBarangValid.Add(i)
		Dim d(0) As Integer
		d(0) = i
		Dim ci As New ItemSet(jumlahBarang, d, 1)
		daftarItemSetLaris.Add(ci)
		dictItemSetLaris.Add(ci.nilaiHash, True)
	End If
Next i

4c. Cari semua itemSet dengan ukuran 2, 3, 4 barang (poin 4c1 – 4c3)

Do While ukuranItemSet <= maxJumlahItemSet AndAlso selesai = False
. . .

4c1. Gunakan itemSet terpilih untuk membuat itemSet baru dengan ukuran itemSet lama + 1 (poin 4c1a dan 4c1b)

For i As Integer = 0 To jumlahItemSet - 1
. . . 

4c1a. Hanya Gunakan itemSet yang ukurannya adalah ukuran itemSet lama dikurangi 1

If daftarItemSetLaris(i).ukuranItemSet <> ukuranItemSet - 1 Then Continue For

4c1b. Lakukan perhitungan sebanyak jumlah data valid (poin 4c1b1 – 4c1b6)

Dim j As Integer = 0
Do While j < dataBarangValid.Count
. . .

4c1b1. Simpan itemSet lama

For p As Integer = 0 To ukuranItemSet - 2
	dataBaru(p) = daftarItemSetLaris(i).data(p)
Next p

4c1b2. Karena data transaksi sudah terurut, maka tidak semua data barang perlu dihitung

If dataBarangValid(j) <= dataBaru(ukuranItemSet - 2) Then
	j += 1
	Continue Do
End If

4c1b3. Tambahkan data barang valid sebagai data baru pada indeks terakhir ukuran

dataBaru(ukuranItemSet - 1) = dataBarangValid(j)
Dim ci As New ItemSet(jumlahBarang, dataBaru, -1)

4c1b4. Jika ItemSet yang baru ternyata sudah ada pada dictionary, maka cari itemSet baru yang lain

If dictItemSetLaris.ContainsKey(ci.nilaiHash) = True Then
	j += 1
	Continue Do
End If

4c1b5. Hitung berapa banyak itemsSet yang baru ini terjadi pada semua transaksi

Dim ct As Integer = 0
For l As Integer = 0 To dataTransaksi.Count - 1
	Dim isSubSetOf As Boolean = True
	For m As Integer = 0 To ci.data.Length - 1
		Dim foundIdx As Integer = -1
		For n As Integer = foundIdx + 1 To dataTransaksi(l).Length - 1
			If n > ci.data(m) Then
				foundIdx = -1
				Exit For
			End If
			If dataTransaksi(l)(n) = ci.data(m) Then
				foundIdx = n
				Exit For
			End If
		Next n

		If foundIdx = -1 Then
			isSubSetOf = False
			Exit For
		End If
	Next m

	If isSubSetOf Then ct += 1
Next l

4c1b6. Jika itemSet baru ini terjadi minimal sebanyak nilai support, maka tambahkan itemSet ini ke dalam dictionary

If ct >= minSupport Then
	ci.ct = ct
	daftarItemSetLaris.Add(ci)
	dictItemSetLaris.Add(ci.nilaiHash, True)
	selesai = False
End If

4c2. Update data barang valid berdasarkan dictionary yang baru saja diupdate

dataBarangValid.Clear()
Dim dictItemSetValid As New Dictionary(Of Integer, Boolean)()
For idx As Integer = 0 To daftarItemSetLaris.Count - 1
	If daftarItemSetLaris(idx).ukuranItemSet <> ukuranItemSet Then Continue For

	For j As Integer = 0 To daftarItemSetLaris(idx).data.Length - 1
		Dim v As Integer = daftarItemSetLaris(idx).data(j)
		If dictItemSetValid.ContainsKey(v) = False Then
			dataBarangValid.Add(v)
			dictItemSetValid.Add(v, True)
		End If
	Next j
Next idx

4c3. Untuk menjaga agar data barang valid selalu dalam keadaan terurut

dataBarangValid.Sort()

4d. Masukkan semua itemset yang memenuhi kondisi sebagai jawaban

Dim hasil As New List(Of ItemSet)()
For i As Integer = 0 To daftarItemSetLaris.Count - 1
	If daftarItemSetLaris(i).ukuranItemSet >= minJumlahItemSet Then
		hasil.Add(New ItemSet(daftarItemSetLaris(i).jumlahBarang, daftarItemSetLaris(i).data, daftarItemSetLaris(i).ct))
	End If
Next i

* Dari setiap itemSet yang ditemukan, tentukan relasi antar barang dalam itemSet tersebut (poin 5 – 6)

5. Tentukan nilai persentase confidence sebagai faktor penentu tingkat kebenaran relasi antar barang dalam itemSet
Dalam kasus ini nilai persentase confidence bernilai 0.7
Artinya relasi tersebut akan termasuk sebagai jawaban apabila tingkat kebenaran nya pada semua transaksi diatas 70%

Const minPersentaseConfidence As Double = 0.7

6. Lakukan proses perhitungan nilai confidence untuk setiap relasi antar barang yang ditemukan
Hasil perhitungan adalah aturan-aturan relasi antar barang dengan tingkat kebenaran lebih dari 70%
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim daftarAturan As List(Of Aturan) = HitungNilaiConfidence(dataItemSet, dataTransaksi, minPersentaseConfidence, barang)

6a. Lakukan perhitungan pada semua itemset (poin 6a1 dan 6a2)

For i As Integer = 0 To dataItemSet.Count - 1
	Dim itemSetTerpilih() As Integer = dataItemSet(i)
. . .

6a1. Hitung berapa kali itemSet ini muncul pada semua transaksi

Dim jumlahDataItemSet As Integer = hitungJumlahDataPadaTransaksi(itemSetTerpilih, dataTransaksi, dictJumlahDataItemSet)

* Gunakan Fungsi ini untuk menghitung berapa kali sebuah itemSet muncul pada semua transaksi
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Private Function hitungJumlahDataPadaTransaksi(ByVal itemSet() As Integer, ByVal dataTransaksi As List(Of Integer()), ByVal dictJumlahDataItemSet As Dictionary(Of Integer(), Integer)) As Integer
	If dictJumlahDataItemSet.ContainsKey(itemSet) = True Then
		Return dictJumlahDataItemSet(itemSet)
	End If

	Dim ct As Integer = 0
	For i As Integer = 0 To dataTransaksi.Count - 1
		Dim isSubsetOf As Boolean = True
		For j As Integer = 0 To itemSet.Length - 1
			Dim foundIdx As Integer = -1
			For k As Integer = foundIdx + 1 To dataTransaksi(i).Length - 1
				If k > itemSet(j) Then
					foundIdx = -1
					Exit For
				End If
				If dataTransaksi(i)(k) = itemSet(j) Then
					foundIdx = k
					Exit For
				End If
			Next k

			If foundIdx = -1 Then
				isSubsetOf = False
				Exit For
			End If
		Next j
		If isSubsetOf Then ct += 1
	Next i

	dictJumlahDataItemSet.Add(itemSet, ct)
	Return ct
End Function

6a2. Cari barang yang akan menjadi klausa sebab dan klausa akibat dari sebuah aturan
Semua barang akan dicari mulai ukuran 1 barang sampai dengan ukuran jumlah barang – 1 (poin 6a2a dan 6a2b)

For len As Integer = 1 To itemSetTerpilih.Length - 1
. . .

6a2a. Cari kombinasi semua barang dengan ukuran 1 barang sampai dengan ukuran sebesar variabel len

Dim c(len - 1) As Integer
For j As Integer = 0 To c.Length - 1
	c(j) = j
Next j

6a2b. Untuk setiap kombinasi barang dengan ukuran x (poin 6a2a1 – 6a2a5)

Do While c IsNot Nothing
. . . 

6a2a1. Tentukan barang yang akan masuk ke dalam klausa sebab dari sebuah aturan
Jika itemSet bernilai (1,3,5,7,9) dan nilai kombinasi (0,2), maka nilai pada klausa sebab adalah (1,5)

Dim sebab(c.Length - 1) As Integer
For n As Integer = 0 To c.Length - 1
	Dim idx As Integer = c(n)
	sebab(n) = itemSetTerpilih(idx)
Next n

6a2a2. Tentukan barang yang akan masuk ke dalam klausa akibat dari sebuah aturan
Jika itemSet bernilai (1,3,5,7,9) dan nilai kombinasi (0,2), maka nilai pada klausa akibat adalah (3,7,9)

Dim akibat(itemSetTerpilih.Length - c.Length - 1) As Integer
Dim iKombinasi As Integer = 0
Dim iAkibat As Integer = 0
For n As Integer = 0 To itemSetTerpilih.Length - 1
	If iKombinasi < c.Length AndAlso n = c(iKombinasi) Then
		iKombinasi += 1
	Else
		akibat(iAkibat) = itemSetTerpilih(n)
		iAkibat += 1
	End If
Next n

6a2a3. Hitung jumlah barang-barang pada klausa sebab muncul pada semua transaksi

Dim jumlahDataSebab As Integer = hitungJumlahDataPadaTransaksi(sebab, dataTransaksi, dictJumlahDataItemSet)

6a2a4. Hitung nilai confidence, yaitu tingkat kebenaran jumlah barang-barang pada klausa sebab terjadi pada semua transaksi
Jika nilai confidence lebih dari parameter minConfidence, maka buat aturan baru dengan data-data ini

Dim confidence As Double = (jumlahDataItemSet * 1.0) / jumlahDataSebab
If confidence >= minConfidence Then
	Dim r As New Aturan(sebab, akibat, confidence, barang)
	hasil.Add(r)
End If

6a2a5. Cari kombinasi lain dari itemSet ini
Jika ukuran = 5, dan nilai kombinasi = (0 3 4) maka nilai selanjutnya adalah 1 2 3)
Jika ukuran = 5, dan nilai kombinasi = (3 4 5) maka nilai selanjutnya adalah null

Dim kombinasiBerikutnya(c.Length - 1) As Integer
Dim ukuranKombinasi As Integer = c.Length

If c(0) = itemSetTerpilih.Length - ukuranKombinasi Then
	c = Nothing
	Continue Do
End If
Array.Copy(c, kombinasiBerikutnya, c.Length)
Dim l As Integer = ukuranKombinasi - 1
Do While l > 0 AndAlso kombinasiBerikutnya(l) = itemSetTerpilih.Length - ukuranKombinasi + l
	l -= 1
Loop
kombinasiBerikutnya(l) += 1
For m As Integer = l To ukuranKombinasi - 2
	kombinasiBerikutnya(m + 1) = kombinasiBerikutnya(m) + 1
Next m

c = kombinasiBerikutnya

* Agar dapat menjalankan skrip diatas, maka diperlukan 2 buah Class, yaitu Class Itemset untuk menampung data jumlah barang, ukuran itemset, dan data transaksi yang dihitung, dan kemudian Class Aturan untuk menampung data sebab akibat sebuah aturan, data barang, dan nilai confidence. Deklarasi kedua class tersebut adalah sebagai berikut:

Public Class ItemSet
    Public jumlahBarang As Integer
    Public ukuranItemSet As Integer
    Public data() As Integer        'misal: [0 2 5]
    Public nilaiHash As Integer     '"0 2 5" -> 520
    Public ct As Integer            'Jumlah itemSet ini muncul pada semua transaksi

    Public Sub New(ByVal jumlahBarang As Integer, ByVal items() As Integer, ByVal ct As Integer)
        Me.jumlahBarang = jumlahBarang
        Me.ukuranItemSet = items.Length
        Me.data = New Integer(Me.ukuranItemSet - 1) {}
        Array.Copy(items, Me.data, items.Length)

        Dim nilaiHash As Integer = 0
        Dim pengali As Integer = 1
        For i As Integer = 0 To items.Length - 1
            nilaiHash = nilaiHash + (items(i) * pengali)
            pengali = pengali * 10
        Next i
        Me.nilaiHash = nilaiHash
        Me.ct = ct
    End Sub
End Class

Public Class Aturan
    Public sebab() As Integer
    Public akibat() As Integer
    Public confidence As Double
    Public barang()() As String

    Public Sub New(ByVal sebab() As Integer, ByVal akibat() As Integer, ByVal confidence As Double, ByVal barang()() As String)
        Me.sebab = New Integer(sebab.Length - 1) {}
        Array.Copy(sebab, Me.sebab, sebab.Length)
        Me.akibat = New Integer(akibat.Length - 1) {}
        Array.Copy(akibat, Me.akibat, akibat.Length)
        Me.confidence = confidence
        Me.barang = barang
    End Sub

    Public Overrides Function ToString() As String
        Dim s As String = "Jika ("
        For i As Integer = 0 To sebab.Length - 1
            s &= IIf(i = 0, "", ", ") & barang(sebab(i) / 3)(sebab(i) Mod 3).PadRight(15)
        Next i
        s &= ")"

        Dim t As String = " maka ("
        For i As Integer = 0 To akibat.Length - 1
            t &= IIf(i = 0, "", ", ") & barang(akibat(i) / 3)(akibat(i) Mod 3).PadRight(15)
        Next i
        t &= ") "

        Return s & t & "confidence= " & confidence.ToString("F2")
    End Function
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.