ALGORITMA AIS DAN APRIORI

ALGORITMA AIS

Fungsi Association Rules seringkali disebut dengan "market basket analysis", yang digunakan untuk menemukan relasi atau korelasi diantara himpunan item-item. Market Basket Analysis adalah Analisis dari kebiasaan membeli customer dengan mencari asosiasi dan korelasi antara item-item berbeda yang diletakkan customer dalam keranjang belanjaannya. Fungsi ini paling banyak digunakan untuk menganalisa data dalam rangka keperluan strategi pemasaran, desain katalog, dan proses pembuatan keputusan bisnis. Tipe association rule bisa dinyatakan sebagai misal : "70% dari orangorang yang membeli mie, juice dan saus akan membeli juga roti tawar".

Pada Association Rules dikenal Blok Sistem AR Mining, seperti gambar di bawah ini:

Dari bagan di atas terdapat suatu masalah pada bagian Large Itemset yaitu Bagaimana melakukan pencarian semua large itemsets secara efisien? Untuk memecahkan masalah tersebut perlu digunakan suatu Algoritma yang salah satu algoritma dinamakan Algoritma AIS.

Algoritma AIS akan digunakan untuk mencari itemset dari suatu database. Bentuk Algoritma AIS adalah :

Contoh Penerapan Algoritma AIS:

Ø Perhatikan bahwa: jika {modem, laptop} adalah sebuah large itemset, maka masing-masing {madem} dan {laptop} dapat dipastikan anggota large itemsets juga.

Ø Hal ini Berarti: Jika sebuah itemsets tidak large / tidak frequent, (seperti {pulsa}) maka tidaklah mungkin akan terdapat large itemset yang memuat pulsa seperti {pulsa, laptop}.

Ø Asumsikan bahwa itemsets dengan ukuran 1 (itemsets-1) berikut telah diketahui merupakan large itemsets dengan ukuran 1 (large itemsets-1): {Modem},{Laptop},{ Pulsa}

Ø Karena {cooling pad} bukan merupakan large itemsets-1→ {cooling pad, pulsa} tidak mungkin akan menjadi large itemsets-2.

Ø Hanya jika {cooling pad} dan {pulsa} keduanya adalah large itemsets-1, maka {Cooling pad, Pulsa} bisa menjadi large itemsets-2.

Ø Sehingga logika kerjanya secara umum adalah:

1. Dapatkan semua large itemsets-1.

2. Untuk mendapatkan semua large itemsets-2, hitunglah frekuensi (counting) dari itemsets-2 yang mengandung 2 dari item-item berikut: Modem, Laptop, Pulsa

APRIORI

Apriori: diambil dari fakta bahwa dalam proses pembentukan frequent itemset digunakan prior knowledge. Algoritma ini menggunakan pendekatan level—wise search (breadth-first search), dimana kitemset digunakan untuk membentuk (k+1)-itemset.

Dalam menghasilkan sebuah frequent k-itemset Lk dibutuhkan 1 kali scan database transaksi. Trick utama: berupaya mengurangi search space, saat mencari frequent k-itemset Lk (properti) Apriori: “seluruh non empty subset dari suatu frequent itemset juga harus frequent.” Dasarnya: Sifat monotone decreasing nilai support suatu itemset. Bentuk algoritma Apriori adalah:

Algoritma Apriori termasuk jenis aturan asosiasi pada datamining. Algoritma Apriori yang bertujuan untuk menemukan frequent itemsets dijalankan pada sekumpulan data. Pada iterasi ke -k, akan ditemukan semua itemsets yang memiliki k items, disebut dengan k -itemsets. Tiap iterasi berisi dua tahap. Misal Oracle Data Mining Fk merepresentasikan himpunan dari frequent k -itemsets, dan Ck adalah himpunan candidate k-itemsets (yang potensial untuk menjadi frequent itemsets).

Tahap pertama adalah men-generate kandidat, dimana himpunan dari semua frequent (k- 1) itemsets, Fk-1, ditemukan dalam iterasi ke-(k-1), digunakan untuk men-generate candidate itemsets Ck. Prosedur generate candidate memastikan bahwa Ck adalah superset dari himpunan semua frequent k-itemsets. Struktur data hash-tree digunakan untuk menyimpan Ck. Kemudian data di-scan dalam tahap penghitungan support. Untuk setiap transaksi, candidates dalam Ck diisikan ke dalam transaksi, ditentukan dengan menggunakan struktur data hash-tree hashtree dan nilai penghitungan support dinaikkan. Pada akhir dari tahap kedua, nilai Ck diuji untuk menentukan yang mana dari candidates yang merupakan frequent. Kondisi penghitung (terminate condition) dari algoritma ini dicapai pada saat Fk atau Ck+1 kosong.

Secara umum, tahapan ini mencakup :

Gunakan frequent (k – 1)-itemsets untuk membangun kandidat frequent k itemsets.
Gunakan scan database dan pencocokan pola untuk mengumpulkan hitungan untuk kandidat itemset.

Notasi Algoritma Apriori adalah sebagai berikut, tetapi notasi terakhir Ck hanya digunakan pada algoritma AprioriTid.