Apriori Algorithm


  1. Apriori Algorithm
Algoritma Apriori adalah algoritma paling terkenal untuk menemukan pola frekuensi tinggi.  Pola frekuensi tinggi adalah pola-pola item di dalam suatu database yang memiliki frekuensi atau support di atas ambang batas tertentu yang disebut dengan istilah minimum support.
Pola frekuensi tinggi ini digunakan untuk menyusun aturan assosiatif dan juga beberapa teknik data mining lainnya.
Algoritma Apriori dibagi menjadi beberapa tahap yang disebut iterasi atau pass. Tiap iterasi menghasilkan pola frekuensi tinggi dengan panjang yang sama dimulai dari pass pertama yang menghasilkan pola frekuensi tinggi dengan panjang satu. Di iterasi pertama ini, support dari setiap item dihitung dengan men-scan database. Setelah support dari setiap item didapat, item yang memiliki support diatas minimum support dipilih sebagai pola frekuensi tinggi dengan panjang 1 atau sering disingkat 1-itemset. Singkatan k-itemset berarti satu set yang terdiri dari k item.
Iterasi kedua menghasilkan 2-itemset yang tiap set-nya memiliki dua item. Pertama dibuat kandidat 2-itemset dari kombinasi semua 1-itemset. Lalu untuk tiap kandidat 2-itemset ini dihitung support-nya dengan men-scan database. Support disini artinya jumlah transaksi dalam database yang mengandung kedua item dalam kandidat 2-itemset. Setelah support dari semua kandidat 2-itemset didapatkan, kandidat 2-itemset yang memenuhi syarat minimum support dapat ditetapkan sebagai 2-itemset yang juga merupakan pola frekuensi tinggi dengan panjang 2.
Untuk selanjutnya pada iterasi ke-k dapat dibagi lagi menjadi beberapa bagian :

  1. Pembentukan kandidat itemset, Kandidat k-itemset dibentuk dari kombinasi (k-1)-itemset yang didapat dari iterasi sebelumnya. Satu ciri dari algoritma Apriori adalah adanya pemangkasan kandidat k-itemset yang subset-nya yang berisi k-1 item tidak termasuk dalam pola frekuensi tinggi dengan panjang k-1.
  2. Penghitungan support dari tiap kandidat k-itemset. Support dari tiap kandidat k-itemset didapat dengan men-scan database untuk menghitung jumlah transaksi yang memuat semua item di dalam kandidat k-itemset tsb. Ini adalah juga ciri dari algoritme Apriori dimana diperlukan penghitungan dengan scan seluruh database sebanyak k-itemset terpanjang.
  3. Tetapkan pola frekuensi tinggi. Pola frekuensi tinggi yang memuat k item atau k-itemset ditetapkan dari kandidat k-itemset yang support-nya lebih besar dari minimum support.
  4. Bila tidak didapat pola frekuensi tinggi baru maka seluruh proses dihentikan. Bila tidak, maka k ditambah satu dan kembali ke bagian 1.
  • Dikembangkan oleh Agrawal dan Srikant pada tahun 1994 yang merupakan cara inovatif untuk digunakan pada metode asosiasi pada data dengan skala yang besar dengan memberikan keluaran yang berisi lebih dari 1 item
  • Berbasiskan pada frekuensi atau support di atas ambang batas tertentu atau diistilahkan dengan  minimum support threshold  (siap digunakan untuk algoritma AIS)
Apriori memiliki tiga versi :
  • Apriori (Basic version) lebih cepat pada iterasi pertama
  • AprioriTid lebih cepat pada iterasi berikutnya
  • AprioriHybrid dapat merubah dari Apriori ke AprioriTid sesudah iterasi pertama
Batasan pada Algoritma Apriori
  • Membutuhkan beberapa iterasi (perulangan) data
  • Menggunakan sebuah uniform minimum support threshold
  • Sulit menemukan sebuah peristiwa yang jarang terjadi
  • Metode altermatif dapat digunakan dengan menggunakan sebuah metode non-uniform minimum support thresold
  • Beberapa alternatif pendekatan komputerisasi berfokuskan pada partisi dan sampling
Tahapan untuk mendapatkan pengetahuan baru
  1. Pemilihan data
  2. Pembersihan data
  3. Integrasi data
  4. transformasi data
  5. data mining
  6. reporting dan displaying dari hasil data mining
sumber elamasri dan navavathe, 2000
Algoritma Apriori
algoritma_apriori

Algoritma Apriori

Sedangkan pseudocode dari pembentukan kandidat itemset bersama pemangkasannya diberikan di Gambar berikut :
Satu contoh dari penerapan algoritma Apriori diilustrasikan di Gambar berikut :
Di sini minimum support adalah 50% atau minimal support-nya adalah 2. Pada iterasi pertama, item yang support-nya atau count-nya dibawah 2 dieliminasi dari 1-itemset L1. Kemudian kandidat 2-itemset C2 dari iterasi kedua dibentuk dari cross product item-item yang ada di L1. Setelah kandidat 2-itemset itu dihitung dari database, ditetapkan 2-itemset L2. Proses serupa berulang di iterasi ketiga, tetapi perhatikan bahwa selain {2,3,5} yang menjadi kandidat 3-itemset C3 sebenarnya ada juga itemset {1,2,3} dan {1,3,5} yang dapat diperoleh dari kombinasi item-item di L2, tetapi kedua itemset itu dipangkas karena {2,3} dan {1,5} tidak ada di L2. Proses ini berulang sampai tidak ada lagi kandidat baru yang dapat dihasilkan di iterasi ke 4.Dalam contoh ini bisa dilihat bahwa Apriori dapat mengurangi jumlah kandidat yang harus dihitung support-nya dengan pemangkasan. Misalnya kandidat 3-itemset dapat dikurangi dari 3 menjadi 1 saja. Pengurangan jumlah kandidat ini merupakan sebab utama peningkatan performa Apriori.Tetapi di lain pihak Apriori memiliki kelemahan karena harus melakukan scan database setiap kali iterasi, sehingga waktu yang diperlukan bertambah dengan makin banyak iterasi. Masalah ini yang dipecahkan oleh algoritma-algoritma baru seperti FP-growth.(Sumber : http://datamining.japati.net/cgi-bin/indodm.cgi?bacaarsiplalu&1172210143&arsiptutorial&1172210174)
Kelemahan Apriori Algorithm
  • Terlalu banyak melakukan scanning database untuk melakukan perhitungan frekuensi item
Metode asosiasi digunakan dalam proses data mining dimulai dari menemukan pola frekwensi tinggi. Pola frekwensi tinggi adalah pola-pola item di dalam gudang data yang memiliki frekwensi di atas batas tertentu yang disebut dengan istilah threshold (batasan) atau istilah frekwensi himpunan (frequent item set). Jika jumlah frekwensi data yang dihitung kurang dari frequent item set maka item atau kombinasi item tidak akan diikutkan pada perhitungan selanjutnya.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s