-

Apriori ve Fp-Growth Algoritmaları’nın Karşılaştırılması

Önceki makalelerimde Pazar Sepeti Analizinde kullanılan algoritmalardan genel olarak bahsedip ayrıntılı olarak bu algoritmalardan Apriori ve Fp-Growth Algoritmalarını anlatmıştım. Bu makalede ise Apriori ve Fp-Growth algoritmaları bir örnek uygulama ile test edilip aynı zamanda karşılaştırma çalışması yapılacaktır. Bu uygulama için hazır Java kütüphaneleri kullanılmıştır, aynı veri kaynağı ile Apriori ve Fp-Growth algoritması test edilmiştir. İş Zekası ile ilgili çalışmalarımın genelinde kullandığım veri kaynağı ile aynı olması açısından AdventureWorksDW veri tabanındaki satış bilgileri kullanılmıştır. Java uygulaması birlikte satılan ürünlerin yer aldığı metin dosyasını girdi olarak kabul eder, bu dosya içeriği AdventureWorksDW veri tabanından doldurularak Java uygulamasında kaynak olarak kullanılmıştır. Bu yüzden öncelikle girdi dosyasının hazırlanması gerekmektedir. Veriyi AdventureWorksDW veri tabanından metin dosyasına ekleyen basit bir C# uygulaması yazılmıştır. Ürünlerin satış bilgilerini getirmek üzere aşağıdaki Sql sorgusu kullanılmıştır;

sqlAdo1

Sorguda internet satışlarını tutan ve ürün bilgilerini tutan tablo birleştirilerek 2008 yılı filtresi verilmiştir. SELECTcümlesinde aynı sipariş numarasına sahip kayıtları aynı satırda tutma işlemini gerçekleştiren GetOrderNumberByProductKeys fonksiyonu kullanılmıştır. Fonksiyonun Sql kodu aşağıdaki gibidir;

sqlAdo2Böylece 2008 yılında bir arada satılan ürünlerin listesi elde edilmiş olur, sonraki aşamada bu değerler metin dosyasına yazılacaktır. Sql sorgusundan alınan bilgilerin metin dosyasına yazılması ile ilgili C# kodu aşağıdaki gibidir:

kod1

Basit C# uygulaması ile Java uygulamasında kullanılacak olan ProductKeys.txt girdi dosyası hazır hale getirilmiştir.

Eclipse, Java dili geliştirme aracı, kullanılarak yazılan uygulama[1] açık kaynak kodlu SPMF ismindeki veri madenciliği Java Kütüphanesi, Philippe Fournier-Viger tarafından lisanslanmıştır ve kullanıma açıktır. Bu uygulamaya iki algoritma için yukarıda anlatılan ProductKeys.text dosyası girdi olarak verilmiştir, her iki algoritma için de minimum destek değeri 0.01 verilir. Buna göre uygulamadan iki algoritma için özet veriler ve çıktı metin dosyası oluşturur.

Apriori Algoritması için çıkan sonuç:

=============  APRIORI =============

Candidates count : 1485

The algorithm stopped at size 3, because there is no candidate

Frequent itemsets count : 58

Maximum memory usage : 12.800544738769531 mb

Total time ~ 692 ms

Fp-Growth Algoritması için çıkan sonuç:

=============  FP-GROWTH =============

Transactions count from database : 21255

Max memory usage: 10.554763793945312 mb

Frequent itemsets count : 94

Total time ~ 390 ms

Bu sonuçların yanı sıra aynı zamanda iki algoritma için yaygın öğeler kümesi, her birine ait destek sayısı ve destek değeri içeren metin dosyası oluşur.

Apriori Algoritması için çıkan sonuç incelenecek olursa; algoritma için 1485 adet yaygın öğe adayı bulunmuştur, en fazla 2 elemanlı yaygın öğe kümesi bulunabilinmiş, 58 adet yaygın öğe kümesi oluşturulmuş, algoritma çalışırken 13 mb alan kullanmış ve toplamda 692 milisaniye zaman harcanmıştır. Oluşturulan çıktı dosyasına bakıldığında oluşan yaygın öğe kümelerinden biri; 477 478  #SUP: 292 Sup:0.01373 dir, bu sonuca göre Water Bottle ve Mountain Bottle Cage ürünleri 292 defa birlikte satın alınmış, bu örnek için toplam 21255 adet veri kümesi olduğundan ve bu yaygın öğe kümesinin destek değeri;

Destek (A=>B)=   = = 0,01373   olur.

0,01373>0.01(minimum destek) şartını sağladığından yaygın öğeler kümesine dahil edilmiştir.

Fp-Growth algoritmasından çıkan sonuç incelenecek olursa; aynı veri kümesi için işlem yapıldığında 94 adet yaygın öğe kümesi oluşturulabilinmiştir, işlem için 10.55 mb alan kullanılmış ve algoritma sonucu 390 milisaniye’de  dönmüştür. Çıktı olarak oluşturulan kümeye bakıldığında sonuçlardan biri; 477 478 485 #SUP: 307      Sup:0.0144 dir, buna göre Water Bottle, Mountain Bottle Cage, Fender Set – Mountain ürünleri birlikte 307 defa satın alınmış ve destek değeri 0.014, minimum destek değerinden büyük olduğundan yaygın öğeler kümesine dahil edilmiştir.

İki algoritmadan çıkan özet sonuçlar aşağıdaki tabloya eklenmiştir. Çıkan sonuçlardan da anlaşılabileceği üzere Fp-Growth algoritmasından daha fazla yaygın öğe kümesi oluşmuştur, Fp-Growth algoritması daha kısa sürede cevap vermiş ve daha az bellek kullanmıştır.

 

Yaygın Öğe Sayısı Bellek Kullanımı Harcanan Zaman
Apriori 58 12.8005 mb 692 ms
Fp-Growth 94 10.5547 mb 390 ms

 

Algoritmalarla ilgili başka bir test, farklı sayıda eleman içeren dosya uygulamaya girdi olarak verilip çıkan sonuçları gözlemlemek olmuştur. Bu test için minimum destek=0,01, iki algoritma için de aynı olacak şekilde verilmiştir. İşlem sayısı 100 ile 27659 arasında değişecek şekilde  8 farklı değer için algoritmalar çalıştırılmıştır, çıkan sonuçlar aşağıdaki tabloda verilmiştir. Bu sonuçlara bakıldığında iki algoritma için de işlem sayısı arttıkça genel olarak harcanan süre artmıştır. Neredeyse bütün denemelerde Fp-Growth algoritmasının çalışma süresi Apriori Algoritması’nın çalışma süresinden kısa sürmüştür. Apriori algoritması genelde az sayıda işlem içeren veri tabanlarında iyi performans gösterir, Fp-Growth ise büyük veri tabanlarında daha performanslı çalışır [2]. Aynı test daha büyük veri tabanı ile yapılacak olursa iki algoritma arasındaki fark daha açık bir şekilde gözlemlenebilecektir. Bulunan yaygın öğe sayısına bakıldığında ise 1000 ve 5000 işlem içeren veri tabanında iki algoritma için aynı sayıda yaygın öğe bulunmuştur, bunun dışındakilerde ise Fp-Growth algoritmasında Apriori Algoritması’ndan daha fazla yaygın öğe bulunmuştur. Yaygın öğe sayısını eleman sayısına göre yorumlamak çok doğru olmayabilir çünkü elemanların arasındaki ilişkiye göre bulunan yaygın öğe sayısı farklılık gösterebilir.

 

Input Dosya Eleman Sayısı Apriori Alg.Çalışma Süresi (ms) Fp-Growth Alg.Çalışma Süresi (ms) Apriori Alg.Yaygın Öğe Sayısı Fp-Growth Alg.Yaygın Öğe Sayısı
100 156 187 131 570
1000 186 106 18 18
5000 274 172 30 30
10000 250 453 41 56
15000 459 394 58 82
20000 564 432 52 77
25000 689 444 55 82
27659 738 438 56 84

 

Apriori ve Fp-Growth algoritmaları için yapılan 3. testte ise sabit sayıda işlem içeren veri tabanı verilip (21255 işlem sayısı) farklı minimum destek değerleri için çıkan sonuçlar gözlemlenmiştir. Minimum destek değeri 0,01 den başlayıp 0,2’ye kadar 5 farklı değer için denenmiştir.  Çıkan sonuçlar aşağıdaki tabloda verilmiştir. Sonuçları incelediğimizde her iki algoritma için %20 olan destek değerinde yaygın öğe bulunamamıştır, ayrıca artan minimum destek değerine karşılık iki algoritma için de çalışma süresi azalmıştır. Minimum destek sayısı arttıkça iki algoritmanın bulmuş olduğu yaygın öğe sayısı azalmıştır. Fp-Growth algoritması artan minimum destek değerinden çok fazla etkilenmezken Apriori Algoritması’nda ise minimum destek değeri arttıkça çalışma süresinde ciddi bir düşüş gözlemlemek mümkündür. %10 ve %15’lik minimum destek değerleri için Apriori Algoritması Fp-Growth algoritmasından çok daha hızlı çalışmıştır.

 

Destek değeri Yüzdeliği(%) Apriori Alg.Çalışma Süresi (ms) Fp-Growth Alg.Çalışma Süresi (ms) Apriori Alg.Yaygın Öğe Sayısı Fp-Growth Alg.Yaygın Öğe Sayısı
1 679 447 56 84
5 354 351 13 15
10 282 394 3 3
15 281 379 1 1
20 - 483 0 0

 

İki tablodaki sonuçlar birlikte düşünülürse; Apriori algoritmanın az işlem içeren ve yüksek minimum destek değeri için daha iyi performans sergilediği sonucuna varılabilir. Bu tsteler daha fazla eleman içeren veri tabanında yapılacak olursa iki algoritma arasındaki fark daha keskin olacaktır. Benzer bir çalışma [2]’de de yapılmıştır. Bulunan sonuçlar birbirini destekler niteliktedir.

Kaynaklar:

[1]  Fournier-Viger, P., Gomariz, A., Gueniche, T., Soltani, A., Wu., C., Tseng, V. S, 2014, SPMF: a Java Open-Source Pattern Mining Library. Journal of Machine Learning Research (JMLR), 15, 3389-3393.

[2]  Győrödi, C., Győrödi, R., Holban, S., 2004, A Comparative Study of Association Rules Mining Algorithms, 1st Romanian-Hungarian Joint Symposium on Applied Computational Intelligence, 213-222.

 

 

Your email address will not be published. Required fields are marked *

*