Apriori Algoritması 1994 yılında Agrawal ve Srikant tarafından geliştirilmiştir.
Birliktelik kuralı çıkarım algoritmalarından en çok bilinen ve kullanılanıdır.
Algoritmanın ismi yaygın öğeler kümelerinin ön bilgisini kullanıyor olmasından dolayı önceki (prior) anlamındaki “Apriori” dir.
Apriori algoritması, özellikle çok büyük ölçekli veri tabanları (VLDB, very large databases) üzerindeki veri madenciliği (datamining) çalışmalarında geliştirilmiştir.
Algoritmanın amacı, veri tabanında bulunan satırlar arasındaki bağlantıyı ortaya çıkarmaktır.
Eğer bir öğe kümesi sık öğe kümesi ise (minimum destek değerini geçiyorsa), onun bütün alt kümeleri de sık öğe kümeleridir.
Örneğin; {a,b,c} öğe kümesi sık öğe kümesi ise onun alt kümeleri olan {a}, {b}, {c}, {a,b}, {a,c}, {b,c} de sık öğe kümesidir.
Aksine, eğer bir alt küme sık değil ise onun bütün üst kümeleri de sık öğe kümesi değildir. Böylece destek değerini geçemeyen bütün tek elemanlı kümelerin üst kümeleri destek değerini geçemeyeceği için değerlendirme dışı bırakılır. Bu yönteme destek-bazlı budama (support based pruning) denir.
Apriori destek bazlı budamayı (support-based pruning) ilk olarak kullanan algoritmadır.
Daha net olarak anlamak gerekirse örneklere bakabilirz.
Örneği açıklamak gerekirse;
Database D, bizim veritabanımızdaki birlikte alınan öğeleri gösterir. Bu örnek için Minimum Destek Değeri:2'dir.
Öncelikle 1 Elemanlı Aday Öğe Kümelerini oluşturuyoruz. -> C1
C1 tablosundan L1 Yaygın Öğe Kümesi oluştururken tabloyu Minimum destek değerine göre kontrol ediyoruz. Minimum destek değerinden küçük olan elemanları siliyoruz. Ki bu tabloda silinen yani budanan elemanımız {4}tür.
Buna göre L1 Yaygın Öğe Kümesi oluşturulur. Bu adımdan sonra 1 elemanlı öğe kümelerinden 2 elemanlı öğe kümeleri oluşturuyoruz.(L1 U L2) -> C2
C2 Aday öğeleri kümesini oluşturduktan sonra C2 kümesine ait alt elemanların L1 de olup olmadığına bakıyoruz.L1 de yer almayanları siliyoruz. Buna göre C2 kümemizi tekrar oluşturuyoruz.
C2 kümemizde Minimum Destek Değerinden küçük olan elemanlarımızı siliyoruz. Ki bu bölümde budanan elemanlarımız: {1,2} ve {1,5} öğeleridir. L2 kümemizi oluşturuyoruz.
L2 kümemiz oluştuktan sonra döngü C2'nin 3'lü kombinasyonlarını bulur ve C3 Aday Öğe Kümesi oluşturur.
C3 Aday Öğe kümesine bakarsak; {1,2} kümesi aday öğe kümelerine dahil edilmediğinden {1,2,3,5}'te dahil edilemez. Bu kuralı konu anlatımının başında da söylemiştik.
3 elemanlı kümeye dahil edilebilecek olan sadece {2,3,5} kümesi vardır. Min. destek değerine baktığımızda 2'ye eşit olduğunu görüyoruz. Bu değer min. destek değerine eşit olduğu için L3 kümemiz {2,3,5} olur.
4 elemanlı aday öğe kümesi olmadığı için işlemimiz burada sona erer.
Başka bir örneğe bakarsak;
| ID | OYUNLAR |
|---|---|
| 1 | DOTA, FIFA, WarCraft, Tomb Raider |
| 2 | DOTA, FIFA, Tomb Raider |
| 3 | LOL, Tomb Raider |
| 4 | LOL, Need For Speed |
| 5 | DOTA, FIFA |
| 6 | DOTA, FIFA, LOL |
**Veritabanımızda birlikte kullanılan öğelerimiz yukarıda ki tablodadır. Minimum Destek Değerimiz: 2'dir. Bu tabloya göre öğe ve frekans tablosunu oluşturuyoruz. **
| OYUN | FREKANS |
|---|---|
| DOTA | 4 |
| FIFA | 4 |
| WarCraft | 1 |
| Tomb Raider | 3 |
| LOL | 3 |
| Need For Speed | 1 |
Bu tabloyu oluşturduktan sonra minimum destek değerinin altında kalan elemanlarımızı kümemizden çıkarıyoruz.
| OYUN | FREKANS |
|---|---|
| DOTA | 4 |
| FIFA | 4 |
| Tomb Raider | 3 |
| LOL | 3 |
Bu işlemden sonra 1 elemanlı kümemizden 2 elemanlı kombinasyonlar tablomuzu oluşturuyoruz.
| OYUN | FREKANS |
|---|---|
| DOTA, FIFA | 4 |
| DOTA, Tomb Raider | 2 |
| DOTA, LOL | 1 |
| FIFA, Tomb Raider | 2 |
| FIFA, LOL | 1 |
| Tomb Raider, LOL | 1 |
Minumum destek değerinden küçük olan elemanları çıkarıyoruz.
| OYUN | FREKANS |
|---|---|
| DOTA, FIFA | 4 |
| DOTA, Tomb Raider | 2 |
| FIFA, Tomb Raider | 2 |
2 elemanlı aday öğe kümesinden 3 elemanlı yaygın öğe kümesi oluşturuyoruz.
| OYUN | FREKANS |
|---|---|
| DOTA, FIFA, Tomb Raider | 2 |
Bu tablomuzda frekans, minumum destek değerini geçtiği için en geniş nesne kümesi DOTA, FIFA ve Tomb Raider kümesidir