ALGORITMA APRIORI

Algoritma Apriori yaitu algoritma paling populer untuk temukan pola frekwensi tinggi. Pola frekwensi tinggi yaitu pola-pola item didalam satu database yang mempunyai frekwensi atau dukungan diatas ambang batas spesifik yang dimaksud dengan arti minimal dukungan.

Pola frekwensi tinggi ini dipakai untuk membuat ketentuan assosiatif serta sebagian tehnik data mining yang lain. 

Meskipun belakangan ini di kembangkan banyak algoritma yang lebih efektif dari Apriori seperti FP-growth, LCM dsb, namun Apriori terus jadi algoritma yang paling banyak diimplementasikan dalam product komersial untuk data mining lantaran dikira algoritma yang paling mapan.
Algoritma Apriori dibagi jadi sebagian step yang dimaksud iterasi atau pass. Setiap iterasi membuahkan pola frekwensi tinggi dengan panjang yang sama diawali dari pass pertama yang membuahkan pola frekwensi tinggi dengan panjang satu. Di iterasi pertama ini, support
dari tiap-tiap item dihitung dengan men-scan database. Sesudah dukungan dari tiap-tiap item didapat, item yang mempunyai dukungan di atas minimal dukungan diambil juga sebagai pola frekwensi tinggi dengan panjang 1 atau kerap disingkat 1-itemset. Singkatan k-item set bermakna satu set yang terbagi dalam k item.
Iterasi ke-2 membuahkan 2-itemset yang setiap set-nya mempunyai dua item. Pertama di buat kandidat 2-itemset dari gabungan seluruhnya 1-itemset. Lantas untuk setiap kandidat 2-itemset ini dihitung support-nya dengan men-scan database. Dukungan di sini berarti jumlah transaksi
dalam database yang memiliki kandungan ke-2 item dalam kandidat 2-itemset. Sesudah dukungan dari seluruhnya kandidat 2-itemset diperoleh, kandidat 2-itemset yang penuhi prasyarat minimal dukungan bisa diputuskan juga sebagai 2-itemset yang juga adalah pola frekwensi tinggi dengan panjang 2.
Untuk setelah itu pada iterasi ke-k bisa dibagi lagi jadi bagian-bagian :
1. Pembentukan kandidat item set, Kandidat k-item set dibuat dari gabungan (k-1) –item set yang didapat dari iterasi pada awal mulanya. Satu ciri dari algoritma Apriori yaitu ada pemangkasan kandidat k-itemset yang subset-nya yang diisi k-1 item tak termasuk juga dalam pola frekwensi tinggi dengan panjang k-1.
2. Penghitungan dukungan dari setiap kandidat k-item set. Dukungan dari setiap kandidat k-itemset didapat dengan men-scan database untuk mengkalkulasi jumlah transaksi yang berisi seluruhnya item didalam kandidat k-item set tsb. Ini yaitu juga ciri dari algoritme Apriori di mana dibutuhkan penghitungan dengan scan semua database sejumlah k-item set terpanjang.
3. Tentukan pola frekwensi tinggi. Pola frekwensi tinggi yang berisi k item atau k-item set diputuskan dari kandidat k-item set yang support-nya semakin besar dari minimal dukungan.
4. Apabila tak didapat pola frekwensi tinggi baru jadi semua sistem dihentikan. Apabila tak, jadi k ditambah satu serta kembali ke sisi 1.

Contoh studi kasus dalam algoritma apriori :


Transaksi GRAMEDIA terdiri dari beberapa item yang ada pada tabel 1 dengan asumsi minimum suportnya 50%
No
Transakasi Buku
Kode
1
Kesehatan
A
2
Komputer
B
3
Komik
C
4
Novel
D
5
Agama
E
6
Ekonomi
F
7
Masakan
G
8
Sekolah
H
9
Budaya
I
10
Olahraga
J
Transakasi
Item yang dibeli
1
ABCDHI
2
ABDHI
3
ABEFI
4
ABFGI
5
ABCEI
6
ABGHI
7
ABDEI
8
ABCDHI
9
AEFGI
10
AHIJ
11
ABIJ
12
ABCIJ
13
ADEIJ
14
ACDEFI
15
ABGHI
16
ABEGHI
17
ACDF
18
ACGH
19
ACIJ
20
ACEFH
21
AFGHI
22
AEFGH
23
ADEFH
24
ACDFH
25
ABFH
26
ADEIJ
27
AHIJ
28
ABCDH
29
ABEFH
30
ABDEH
Candidate 1 – itemset(C1)
1 –itemset
Support Count
{A}
1
{B}
16/30
{C}
9/30
{D}
11/30
{E}
10/30
{F}
12/30
{G}
8/30
{H}
18/30
{I}
20/30
{J}
7/30
Large 1-itemset (L1)
1-itemset
Support Count
{A}
1
{B}
16/30
{H}
18/30
{I}
20/30
Candidate 2-itemset (C2)
2-itemset
Support Count
{AB}
16/30
{AH}
17/30
{AI}
20/30
{BH}
10/30
{BI}
12/30
{HI}
9/30
Large 2-itemset (L2)
2-itemset
Support Count
{AB}
16/30
{AH}
17/30
{AI}
20/30
Canditade 3-itemset (C3)
3-itemset
Support Count
{ABH}
10/30
{ABI}
13/30
{AHI}
9/30
Large 3-itemset (L3)
2-itemset
Support Count
{ABH}
10/30
{ABI}
13/30
{AHI}
9/30
Support
Itemset
100%
A
66,6%
I, AI
60%
H
56,67%
AH
53,33%
B, AB




Tabel 1. Daftar Buku


Tabel 2. Data Transakasi

Tabel 3. Frequent 1 –itemset (30 transaksi)




Tabel 4 . Frequent 2 –itemset (30 transaksi)









Tabel 5. Frequent 3-itemset (30 transaksi)




Tabel 6. Tabel Hasil Frequent Itemset (min_sup = 50%)

ALGORITMA APRIORI ALGORITMA APRIORI Reviewed by Fatkhul Anam on 3:19 PM Rating: 5

No comments