Senin, 20 Mei 2013

Association Rule (Algoritma A Priori)


Algoritma  A  Priori  termasuk  jenis  aturan  asosiasi  pada  data  mining.  Selain a  priori, yang  termasuk  pada golongan ini adalah metode  generalized rule induction  dan  algoritma hash based. Aturan yang menyatakan asosiasi antara beberapa atribut sering disebut affinity analysis atau market basket analysis.
Metodologi dasar analisis asosiasi terbagi menjadi dua tahap:

a. Analisa pola frekuensi tinggi
Tahap ini mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database. Nilai support sebuah item diperoleh dengan rumus berikut:

b. Pembentukan aturan assosiatif
Setelah  semua  pola  frekuensi  tinggi  ditemukan,  barulah  dicari  aturan  assosiatif  yang  memenuhi  syarat minimum untuk confidence dengan menghitung confidence aturan assosiatif A ->B
Nilai confidence dari aturan A ->B diperoleh dari rumus berikut:


Contoh, ada transaksi seperti yang dilihat di bawah ini:

Transaksi
Item yang dibeli
1
D, E, C
2
C, A
3
C, B, D
4
A, C, E, D
5
E, D
6
E, C, B
7
B, D, A


1. Pisahkan masing-masing item yang dibeli
Item yang dibeli
A
B
C
D
E

2. Kemudian Buat Tabel seperti di bawah ini dan hitung jumlahnya:
Transaksi
A
B
C
D
E
1
0
0
1
1
1
2
1
0
1
0
0
3
0
1
1
1
0
4
1
0
1
1
1
5
0
0
0
1
1
6
0
1
1
0
1
7
1
1
0
1
0
3
3
5
5
4

3.Tentukan Ф
Misalkan kita tentukan Ф = 3, maka kita dapat menentukan frekuen itemset. Dari tabel di atas diketahui total Ф untuk transaksi k = 1, semuanya lebih besardari Ф. Maka:
F1= {{A}, {B}, {C}, {D}, {E}}
Untuk k = 2 (2 unsur), diperlukan tabel untuk tiap-tiap pasang item. Himpunan yang mungkin terbentuk adalah: {A,B}, {A,C}, {A,D}, {A,E}, {B,C}, {B,D}, {B,E}, {C,D}, {C,E}, {D,E}.

 Tabel-tabel untuk calon 2 item set
T
A
B
f
T
A
C
f
T
A
D
f
T
A
E
f
T
B
C
f
1
0
0
s
1
0
1
s
1
0
1
s
1
0
1
s
1
0
1
S
2
1
0
s
2
1
1
s
2
1
0
s
2
1
0
s
2
0
1
S
3
0
1
s
3
0
1
s
3
0
1
s
3
0
0
s
3
1
1
P
4
1
0
s
4
1
1
p
4
1
1
p
4
1
1
p
4
0
1
S
5
0
0
s
5
0
0
s
5
0
1
s
5
0
1
s
5
0
0
S
6
0
1
s
6
0
1
s
6
0
0
s
6
0
1
s
6
1
1
P
7
1
1
p
7
1
0
s
7
1
1
p
7
1
0
s
7
1
0
S

1

1

2

1

2
T
B
D
f
T
B
E
f
T
C
D
f
T
C
E
f
T
D
E
f
1
0
1
s
1
0
1
s
1
1
1
p
1
1
1
p
1
1
1
p
2
0
0
s
2
0
0
s
2
1
0
s
2
1
0
s
2
0
0
s
3
1
1
p
3
1
0
s
3
1
1
p
3
1
0
s
3
1
0
s
4
0
1
s
4
0
1
s
4
1
1
p
4
1
1
p
4
1
1
p
5
0
1
s
5
0
1
s
5
0
1
s
5
0
1
s
5
1
1
p
6
1
0
s
6
1
1
p
6
1
0
s
6
1
1
p
6
0
1
s
7
1
1
p
7
1
0
s
7
0
1
s
7
0
0
s
7
1
0
s

2

1

3

3

3

Dari tabel-tabel 2 unsur di atas, P artinya item-item yang dijual bersamaan, sedangkan S berarti tidak ada item  yang  dijual  bersamaan  atau  tidak  terjadi  transaksi.  Σ  melambangkan  jumlah  Frekuensi  item  set.
Jumlah frekuensi item set harus lebih besar atau sama dengan jumlah Frekuensi item set (Σ >= Ф). Dari
tabel diatas, maka didapat:
F2 = {{C,D},{C,E},{D,E}}

Kombinasi dari itemset dalam F2, dapat kita gabungkan menjadi calon 3-itemset. Itemset-itemset yang dapat digabungkan adalah itemset-itemset yang memiliki kesamaan dalam k-1 item pertama.
Untuk k = 3 (3 unsur), himpunan yang mungkin terbentuk adalah: {C,D,E}
T
C
D
E
f
1
1
1
1
P
2
1
0
0
S
3
1
1
0
S
4
1
1
1
P
5
0
1
1
S
6
1
0
1
S
7
0
1
0
S



2

Dari tabel-tabel di atas, didapat F3= { }, karena tidak ada Σ >= Ф sehingga F4, F5, F6 dan F7 juga merupakan himpunan kosong.

4.Tentukan (ss-s) sebagai antecedent dan s sebagai consequent dari Fk yang telah didapat
Pada F2 didapat himpunan F2= {{C,D},{C,E},{D,E}}
 Maka dapat disusun:
•  Untuk {C,D}:
-  Jika (ss-s) = C, Jika s = D, Maka →If buy C then buy D
-  Jika (ss-s) = D, Jika s = C, Maka →If buy D then buy C

•  Untuk {C,E}:
-  Jika (ss-s) = C, Jika s = E, Maka →If buy C then buy E
-  Jika (ss-s) = E, Jika s = C, Maka →If buy E then buy C

•  Untuk {D,E}:
-  Jika (ss-s) = D, Jika s = E, Maka →If buy D then buy E
-  Jika (ss-s) = E, Jika s = D, Maka →If buy E then buy D

5. Dari langkah di atas, kita mendapatkan 6 rule yang dapat digunakan, yaitu:

  • If buy C then buy D
  • If buy D then buy C
  • If buy C then buy E
  • If buy E then buy C
  • If buy D then buy E
  • If buy E then buy D

6.       Hitung support dan confidence

Sehingga didapat table sebagai berikut:
If antecedent then consequent
Support
Confidence
If buy C then buy D
(3/7)x100%=42,86%
(3/5)x100%=60%
If buy D then buy C
(3/7)x100%=42,86%
(3/5) x100%=60%
If buy C then buy E
(3/7)x100%=42,86%
(3/5) x100%=60%
If buy E then buy C
(3/7)x100%=42,86%
(3/4) x100%=75%
If buy D then buy E
(3/7)x100%=42,86%
(3/5) x100%=60%
If buy E then buy D
(3/7)x100%=42,86%
(3/4) x100%=75%

7.       Setelah  di  dapat  support  dan  confidence  untuk  masing-masing  kandidat,  lakukan  perkalian  antara support dan confidence, dimana confidence-nya diambil 70% ke atas, sehingga di dapat tabel sbb:
If antecedent then consequent
Support
Confidence
Support x Confidence
If buy E then buy C
42,86%
75%
0.32145
If buy E then buy D
42,86%
75%
0.32145

8.       Setelah  didapat  hasil  perkalian  antara  support  dan  confidence,  pilihlah  yang  hasil  perkaliannya  paling besar.  Hasil  paling  besar  dari  perkalian  perkalian  tersebut  merupakan  rule  yang  dipakai  pada  saat menjual. Karena hasil perkalian dari ke-2 penjualan di atas bernilai sama, maka semuanya bisa dijadikan rule.
-          Jika membeli E maka akan membeli C dengan support 42,86% dan confidence 75%
-          Jika membeli E maka akan membeli D dengan support 42,86% dan confidence 75%

15 komentar:

  1. maaf bung mau tanya data kebeetulan saya dpt tugas yang hampir samaa dengan anda

    data yang cocok untuk algoritma Apriori itu apa ya bung

    tolong referensinya ya bung

    BalasHapus
  2. maaf bung mau tanya data kebeetulan saya dpt tugas yang hampir samaa dengan anda

    data yang cocok untuk algoritma Apriori itu apa ya bung

    tolong referensinya ya bung

    BalasHapus
  3. maaf, itu contoh data skala kecil, jika menggunakan data skala yang cukup besar misalkan dengan data transaksi dan data barang yang mencapai ribuan, saya kewalahan jika membuat matriks data transaksi dan kombinasi itemset secara manual. jika menggunakan ms.excel, apakah ada referensi rumus untuk perhitungan nya? terimakasih.

    BalasHapus
    Balasan
    1. goog question, masalah kita sama mas, sya juga, tolong adminnya beri penjelasan gmana data dengan skala besar ?

      Hapus
    2. https://github.com/contohprogram/market-basket/blob/master/market-basket-analysis.xls

      Hapus
    3. kalau skala besar bisa menggunakan RapidMiner, WeKa atau yang lain nya

      Hapus
    4. Pakai aplikasi rapidminer

      Hapus
  4. https://github.com/contohprogram/market-basket/blob/master/market-basket-analysis.xls

    BalasHapus
  5. bisa juga menggunakan program R. jadi menggukan fungsi yang tersedia pada R

    BalasHapus
  6. Itu (3/7)×100% kok 42,86
    Cara menghitungnya gimana..?

    BalasHapus
    Balasan
    1. dari 3 dibagi 7 kemudian dikali 100. darimana didapatkan 3? dari banyaknya kemunculan transaksi yang sama [teh, roti], [teh, roti] [teh, roti]. darimana nilai 7? dari total transaksi.

      Hapus
    2. 3 itu barang yg dibeli secara bersamaan
      7 itu jmlh transaksi

      Hapus