algoritma gsp (generalized sequential pattern)

Click here to load reader

Upload: nurul-hidayah-aini

Post on 13-Sep-2015

41 views

Category:

Documents


9 download

DESCRIPTION

Algoritma Apriori

TRANSCRIPT

Slide 1

G S PGeneralized Sequential PatternMenurut Halawani, Shaik, & Prasad, algoritma GSP secara umum dipandang sebagai algoritma luas traversal pertama, yang menemukan semua urutan yang sering munculdengan cara melewati beberapa data. Menurut J. Zaki (1997) dalam (Budhi, Handojo, & Wirawan, 2009) menyebutkan algoritma GSP atau dengan nama lain apriori all adalah suatu algoritma yang dapat memproses dan menemukan semua pola sekuensial dan non sekuensial yang ada.Berdasarkan pada atribut penutupan suatu pola sekuensial, GSP mengadopsi banyak cara pada calon generasi dan pendekatan uji pada mining sequential pattern (Han, Pei, & Yan, 2005). Algoritma GSP digunakan pada mining sequence dan baik untuk memecahkan masalah mining sequence yang banyak didasarkan pada sebuah algoritma Apriori (Halawani, Shaik, & Prasad, 2010). Fungsi utama dari algoritma GSP yaitu menemukan pola sequansial atau urutan.

GSP menemukan pola sekuensial. GSP skala linear dengan jumlah urutan data, dan memiliki sifat skala-up yang sangat baik sehubungan dengan ukuran rata-rata urutan data.Tabel 1.1

Tabel 1.1 Untuk menentukan frequent item menggunakan GSP, dengan nilai min_sup=2.

SIDTIME (EID)ITEMS110, 15,20,25

215,20

310

410,20,25

Setiap transaksi disebut juga subsequence3Tabel 1.2

Item yang memenuhi minsup adalah A, B, D, F. Jadi A, B, D, F adalah Frequent 1- sequence

ItemsJumlah Kejadian ItemA4B4C1D2E1F4G1H1Frequent 1- itemset adalah A, B, D, FDengan properti Apriori, frequent itemset yang diperoleh ditunjukkan pada tabel di bawah ini. C digunakan untuk menandakan Calon set (Barang set). Ck menunjukkan kandidat memiliki k item. Untuk misalnya C1 Menandakan barang set (atau calon set) memiliki 1 item.Tabel 1.3 CI

Item yang memenuhi minsup milik L1. Lk menunjukkan kandidat memiliki k item. Untuk misalnya L1 menunjukkan item set (atau calon set) memiliki 1 item.ItemsJumlah Kejadian ItemA4B4C1D2E1F4G1H1Tabel 1.4 L1

Dari Tabel 1.4 di atas kita dapat melihat bahwa a, b, d, f adalah yang memenuhi minsup. C2 (di mana k = 2) dapat diperoleh dengan bergabung L1 X L1 tapi kondisi ini k-2 item harus umum, jadi di sini saat bergabung untuk mendapatkan item set untuk C2 (2-2 = 0) item harus umum.ItemsJumlah Kejadian ItemA4B4D2F4ItemsJumlah Kejadian ItemAA1AB1AD1AF1AB3AD1AF3BA2BB1BD1BF1BD1BF4DA2DB2DD2DF1DF1FA2FB1FD1F F1Tabel 1.5 C2

Kandidat yang memenuhi minsup milik L2.AB = TEMPORAL JOIN; AB = NON-TEMPORAL JOIN7Tabel 1.6 L2

ItemsJumlah Kejadian ItemAB3AF3BA2BF4DA2DB2DF2FA2Sekarang, pada langkah ini kita harus mencapai 3-urutan item-set, yaitu item-set memiliki 3 item. C3 (di mana k = 3) dapat diperoleh dengan bergabung L2 X L2 tapi kondisi ini k-2 item harus umum, jadi di sini saat bergabung untuk mendapatkan item set untuk C3 (3-2 = 1) item harus menjadi umum.Tabel 1.7 C3

Kandidat yang memenuhi minsup milik L3

ItemsJumlah Kejadian ItemABF3ABA1AFA1 BFA2DB A2DFA2DBF2FAF1DFA1DAB1FAB0BAB1BAF1Tabel 1.8 L3

Pada langkah ini kita harus mencapai 4-urutan item-set, yaitu item-set memiliki 4 item. C4 (di mana k = 4) dapat diperoleh dengan bergabung L3 X L3 tapi kondisi ini k-2 item harus umum, jadi di sini saat bergabung untuk mendapatkan itemset untuk C4 (4-2 = 2) item harus menjadi umum.Tabel 1.9 C4

Kandidat yang memiliki dukungan minimal memenuhi syarat untuk pindah ke L4.ItemsJumlah Kejadian ItemsABF3 BFA2DB A2DFA2DBF2ItemsJumlah Kejadian ItemsDBFA2Tabel 1.10 L4

Di sini, kita telah memperoleh hanya 1, 4-urutan (urutan item set memiliki 4 item) barang ditetapkan.ItemsJumlah Kejadian ItemsDBFA2Contoh Perhitungan 1Tabel 1. Satu set transaksi diurutkan berdasarkan ID pelanggan dan waktu transaksiTabel 1. Database

ID PelangganWaktu TransaksiTransaksi1120 Juli 200525 Juli 200530902229 Juli 200514 Juli 200520 Juli 200510, 203040, 60, 70325 Juli 200530, 50, 7044425 Juli 200529 Juli 20052 Agustus 20053040, 7090512 Juli 200590Contoh Perhitungan 1 (Kondisi)Tabel 2. Urutan data yang dihasilkan dari tabel database transaksi 1

Tabel 3. Hasil akhir pola sekuensialID PelangganUrutan Data1

2 3

4

5

Pola sekuensial dengan support 25%1-urutan, , , ,2-urutan, , , 3-urutan

Data yang sering munculdari tabel 2Data yang sering munculdari 1-urutanData yang sering muncul dari 2-urutan dan merupakan hasil akhirContoh Perhitungan 2Berikut ini tabel 1 yang merupakan data transaksi dengan minsup = 2Tabel 1. Database

Dibawah ini adalah tabel 2 untuk menentukan jumlah data urutan yang sesuai dengan minsup.Tabel 2. Jumlah urutan data

Sequence IDTransaction TimeItemsC10001AC10002BC10015CDC20001ABC20020BEC20050CA2B2C2D1E1Kurang dari MinsupBerdasarkan tabel 2, maka data yang lolos (lebih dari minsup) adalah A, B dan C. Berikut tabel 3 yang merupakan 2-urutanTabel 3. 1-urutan

Dari hasil tabel 3 dapat diketahui bahwa hasil akhir pola sekuensial hanya sampai pada tahap 1-urutan yaitu tabel 2.

AA0AB1AC0AB1AC0BA0BB1BC1BC0CA0CB0CC0Contoh Perhitungan 3Tabel 1. Data transaksi, minsup=2

Tabel 2. Jumlah data 1-urutanSIDEIDItems110AB115CD220BD210AD315BC310ACItemJumlahA3B3C2D2Berdasarkan tabel 2, maka data yang lolos (lebih dari minsup) adl A, B, C dan D. Berikut tabel 3 yang merupakan 2-urutan.Tabel 3. 2-urutan

ITEMJUMLAHA A0A B0A C1A D1AB1AC1AD2B A0B B2B C2B D1ITEMJUMLAHBC1BD1C A0C B0C C0C D1CD1D A0D B0D C0D D1Berdasarkan tabel 2, maka data yang lolos (lebih dari minsup) adl AD, BB dan B C.

Untuk membuat 3-urutan kita membutuhkan k=3, tetapi karena AD yang merupakan untemporal join hanya terdiri dari 2 elemen huruf (k=2) dan karena BB dan B C yang merupakan temporal join hanya terdiri dari 2 elemen huruf (k=2), maka kita tidak dapat membuat 3-urutan, itu berarti kita berhenti sampai di 2-urutan.

Contoh Perhitungan 4SIDTIME (EID)ITEMS110, 20,25, 30, 40

201,02,03,04

3003,004,005,006

450,60,70

Tabel 1 Untuk menentukan frequent item menggunakan GSP, dengan nilai min_sup=4.Tabel 1. Satu set transaksi diurutkan berdasarkan ID pelanggan dan waktu transaksi

Tabel 1. DatabaseItemsJumlah Kejadian ItemA4B4C4D3E3F3G1Contoh Perhitungan 4 (Kondisi)Tentukan jumlah data urutan sesuai dengan minsup, dibawah ini tabel 2 yang merupakan jumlah data urutan. Tabel 2. Jumlah data urutanItem yang memenuhi minsup adalah A, B, C. Jadi A, B, C adalah jumlah 1-urutanBerdasarkan tabel 2, data yang lolos adalah A, B dan C. Berikut tabel 3 yang merupakan data 2-urutan.Tabel 3. 2-urutan

Dari tabel 3 dapat diketahui bahwa tidak ada item yang lolos dari minsup, jadi Dari hasil tabel 3 dapat diketahui bahwa hasil akhir pola sekuensial hanya sampai pada tahap 1-urutan yaitu tabel 2. AA1AB2AC3AB2AC1BA2BB0BC1BC2CA3CB1CC2Contoh Perhitungan 5Tabel 1. Satu set transaksi diurutkan berdasarkan ID pelanggan dan waktu transaksi, minsup=3Tabel 1. Database

SIDEIDITEMS120BC110AC115B215A210ABC215AD220C330EF310DB415ACD425AF420BCItemsJumlah Kejadian ItemA3B4C3D3E1F2Contoh Perhitungan 5 (Kondisi)Tentukan jumlah data urutan sesuai dengan minsup, dibawah ini tabel 2 yang merupakan jumlah data urutan.

Tabel 2. Jumlah data urutanItem yang memenuhi minsup adalah A, B, C dan D. Jadi A, B, C dan D adalah jumlah 1-urutanBerdasarkan tabel 2, data yang lolos adalah A, B dan C. Berikut tabel 3 yang merupakan data 2-urutan.Tabel 3. 2-urutan

Dari tabel 3 dapat diketahui bahwa tidak ada item yang lolos dari minsup, jadi dari hasil tabel 3 dapat diketahui bahwa hasil akhir pola sekuensial hanya sampai pada tahap 1-urutan yaitu tabel 2.

AA2AB3AC2AC1AB1AC3AD2BA2BB0BC1BD1BC3BD0CA3CB1CC1CD1CD1DA1DB1DC1DD0Dari tabel 3 dapat diketahui bahwa yang lolos dari minsup adalah AB, AC dan BC. Berikut ini adalah tabel 4 yang merupakan 3-urutan. Tabel 4. 3-urutan

Pada tabel 4 kita dapat mengetahui bahwa tidak ada yang lolos dari minsup, jadi langkah kita berhenti hanya sampai pada tabel 4 yaitu 3-urutanItemsJumlah Kejadian ItemsABC1

DAFTAR PUSTAKAhttp://www.ijedr.org/papers/IJEDR1403022.pdfdiakses tgl 20-06-2015 pukul 16.21https://ellymunig.wordpress.com/2014/04/10/algoritma-generalized-sequential-pattern-gsp/ diakses tgl 20-06-2015 pukul 16.30