-

Apriori Algoritması

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.

n elemanlı bir eleman kümesi için  yaygın öğe ve  yaygın öğe adayı oluşturulabilir. Apriori Algoritması yaygın öğeleri azaltma noktasında görev almaktadır. Şekil 1’de görüldüğü gibi 5 elemanlı bir küme için olabilecek bütün yaygın öğeler ağaca eklenmiştir, {A,B} eleman kümesi yaygın öğeye dahil olamıyorsa {A,B} ‘nin geçtiği bütün alt kümeler ağaçtan çıkarılır.

Apriori Algoritması’nın temeli; n-elemanlı yaygın öğe kümesi minimum destek kriterini sağlıyorsa bu kümenin bütün alt kümeleri bu kriteri sağlar. Bu yüzden Apriori Algoritması, (n+1)-elemanlı yaygın öğe kümesini bulmak için n-elemanlı sık geçen öğe kümesine ihtiyaç duymaktadır.

Şekil 1

Şekil 1

 

Algoritma temelinde iteratif (tekrarlayan) niteliğe sahiptir, yaygın öğe kümlerini bulurken birçok kez veri tabanına bağlanarak tarama işlemini gerçekleştirmektedir. Başlangıçta veri tabanını tarayarak öğenin alışverişlerde kaç kere geçtiği tespit edilir, bu destek sayısına karşılık gelmektedir. Minimum destek değerinden küçük olan öğeler kümelere dahil edilmemektedir. Yaygın öğe kümelerini bulmak için ilk olarak minimum destek kriterini sağlayan 1-elemanlı yaygın öğe kümesi bulunur, 2-elemanlı yaygın öğe kümesini bulmak için 1-elemanlı yaygın öğe kümesi, 3-elemanlı yaygın öğe kümesini bulmak için 2-elemanlı yaygın öğe kümesi kullanılır. Her adımında bir önceki adımda bulunan yaygın öğe kümeleri, yaygın öğe aday kümeleri (candidate itemsets) adı verilen yeni potansiyel yaygın öğe kümelerini üretmek için kullanılır. Aday kümelerin destek değeri, adım içerisinde hesaplanır ve minimum destek ölçütünü sağlayanlar yaygın öğe kümelerine dahil edilir. Yaygın öğeler bir sonraki adım için aday küme olur. Bu işlem algoritma yaygın öğe kümesi bulamayıncaya kadar devam etmektedir.

Apriori Algoritması’nın klasik özet kodu (pseudo code) aşağıdaki gibidir.

AprioriAlg

 

Apriori-gen Fonksiyonu aşağıdaki gibidir;

AprioriGen

 

Algoritmadan da anlaşılabileceği üzere L(k-1)  yaygın öğe kümesini kullanarak k-elemalı  Ck yaygın öğe aday kümesi oluşturulur. Apriori-gen fonksiyonu aday öğe kümelerinin oluştulması noktasında görev almaktadır. Bu fonksiyon ile önce  L(k-1) öğe kümesi kendisi ile birleştirme (join) işlemi uygulanmaktadır. Birleştirme işleminde  L(k-1)  yaygın aday kümesinin her satırında yer alan son öğe haricinde diğer öğelerlerin çapraz olarak benzerliği aranır ve son öğe haricinde diğer öğelerle yakalanan benzerliklerden aday öğe kümeleri oluşturulmaktadır . Oluşturulan aday öğe kümeleri budama (prune) işlemine tabi tutulur ve yaygın öğe aday kümesini geriye döndürmektedir.

Budama işleminde Ck  yaygın öğe aday kümesinden eleman silme işlemi uygulanır, aday öğe kümesindeki bir öğenin alt kümelerinden biri  L(k-1) yaygın öğe Ck kümesinde yer almıyorsa bu öğe  aday öğe kümesinden silinir.

Apriori Algoritması döngü yapısını daha iyi kavrayabilmek için Şekil 2’deki örnek üzerinden yaygın öğe kümesi ve aday öğe kümelerinin nasıl güncellendiği anlatılacaktır.

Şekil 2’deki örnek için minimum destek değeri 2 olarak verilmiştir. “Database D” ismindeki tabloda birlikte alınan ürünleri görebiliriz. İlk aşamada 1-elemanlı aday öğe kümeleri  C1 ismi ile tanımlanarak yazılmıştır.  C1 öğe kümesinden  L1 yaygın öğe kümesi oluşturulurken minimum destek değeri kontrol edilir, minimum destek değerinden küçük olan öğeler kümeden atılır, dolayısı ile {4} elemanı küme dışında bırakılır ve geriye kalan öğeler ile L1 yaygın öğe kümesi oluşturulur. Sonraki adımda 1-elemanlı öğe kümelerinden 2-elemanlı öğe kümeleri oluşturmak üzere çalışma yapılır.  L1 yaygın öğe kümesinin öğelerinin ikili kombinasyonuna benzer şekilde ( L1 U L1 ) yeni C2  ismindeki aday öğe kümesi oluşturulur. Bu aday küme Apriori-gen fonksiyonundaki budama işlemine tabi tutulur ve  C2 kümesinin elemanlarına ait alt kümelerinin L1 kümesinde olup olmadığına bakılır,  L1 içinde yer almayanlar silinir, budanmış olur . C2  den L2  oluşturulurken yine aynı şekilde minimum destek değeri kontrol edilir, Şekil 2.17’deki örnek için {1,2} ve {1,5} kümeleri silinir ve L2 içerisinde yer almamış olur. Döngü sonraki aşamada  L2 öğe kümesinin 3lü kombinasyonlarını bulur ve  C3 isminde aday öğe kümesini oluşturur. {4} elemanı yaygın öğeler kümesinde olmadığından {2,3,4} aday öğeler kümesine dahil edilmez, aynı şekilde {1,2} kümesi aday öğe kümelerine dahil edilmediğinden {1,2,3,5} de 3-elemanlı aday öğe kümesine dahil edilmez. 3-elemanlı kümeye dahil edilebilecek olarak {2,3,5} kümesi vardır, destek sayısı 2 olduğundan ve minimum destek değerinden büyük olduğundan L3 ={2,3,5} olur. Devamında 4 elemanlı aday öğe kümesi bulunamadığından işlem sona erer. Daha fazla elemanlı kümeler için döngü her seferinde öğe sayısını arttırarak devam eder ve bu süreç yeni yaygın öğe kümesi bulamayıncaya kadar devam eder.

Şekil2

Şekil2

 

 

Kaynaklar:

[1]   Agrawal, R., Imielinski, T. ve Swami, A., 1993, Mining Association Rules Between Sets of Items in Large Databases, In Proceedings of the ACM SIGMOD International Conference on Management of Data, June 1 Washington, USA,  207-216.

[2]   Öğüdücü, Ş.G, Veri Madenciliği İlişkilendirme Kuralları, http://www3.itu.edu.tr/ ~sgunduz/courses/verimaden/, [Ziyaret tarihi:16 Nisan 2015].

[3]   Han, J. ve Kamber, M., 2001, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, San Francisco, ISBN:0123814790 9780123814791.

[4]   Güngör, E., Yalçın,N.,Yurtay, N., 2013, Apriori Algoritması ile Teknik Seçmeli Ders Seçim Analizi, UZEM 2013 Ulusal Uzaktan Eğitim ve Teknolojileri Sempozyumu, 01-03 Kasım 2013 Konya,Türkiye, 122-127.

[5]   Gülce, A.C., 2010, Veri Madenciliğinde Apriori Algoritması ve Apriori Algoritması’nın Farklı Veri Kümelerinde Uygulanması, Yüksek Lisans Tezi, Trakya Üniversitesi Fen Bilimleri Enstitüsü.

[6]   [26].    Özseven, T. ve Düğenci M., 2011, LOG Analiz: Erişim Kayıt Dosyaları Analiz Yazılımı ve GOP Üniversitesi Uygulaması, Bilişim Teknolojileri Dergisi, 4(2), 55-56.

[7]    Özçakır, F.C, Çamurcu, A.C, 2007, Birliktelik Kurali Yöntemi İçin Bir Veri Madenciliği Yazilimi Tasarimi Ve Uygulaması,  İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 6(12), 21-37.

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

*