Apriori Algoritması

Yazan : Şadi Evren ŞEKER

Veri madenciliğinde kullanılan ve veri kümeleri veya veriler arasındaki ilişkiyi çıkarmak için geliştirilmiş algoritmanın ismidir. Ayrıca pek çok akademik konuda geçen ve temelini felsefeden (ve daha özel olarak mantıktan) alan a priori konusu için bu bağlantıyı tıklayabilirsiniz.

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. Genel anlamda münasebet kuralı (association rule, birliktelik kuralı) çıkarımında kullanılan bir algoritmadır. Algoritmanın amacı, veri tabanında bulunan satırlar arasındaki bağlantıyı ortaya çıkarmaktır.

Algoritmanın ismi, kendinden önceki çıkarımlara bağlı olduğu için, latince, önce anlamına gelen “prior” kelimesinden gelmektedir.

Algoritma yapı olarak, aşağıdan yukarıya (bottom-up) yaklaşımı kullanmakta olup, her seferinde tek bir elemanı incelemekte ve bu elemanla diğer adaylarla münasebetini ortaya çıkarmaya çalışmaktadır.

Ayrıca algoritmanın her eleman için çalışmasını, bir arama algoritmasına benzetmek mümkündür. Algoritma, bu anlamda sığ öncelikli arama (breadth first search) yapısında olup, sanki adayları birer ağaç (tree) gibi düşünerek bu ağaç üzerinde arıyor kabul edilebilir.

Ağaç yapısında, k elemanlı bir aday listesinden k-1 elemana baktıktan sonra, alt frekans örüntüsü yetersiz olan elemanları budamakta ve kalan elemanların üzerinden arama yapmaya devam etmektedir.

Örnek

Algoritmayı daha iyi anlamak için bir örnek üzeridnen inceleyelim.

Bir firmanın ürünlerink SKU numaraları ile (Stock Keeping Unit, depo numarası), veritabanında tuttuğunu düşünelim. Bu durumda firmanın satılan ürünlerden hangilerinin beraber alındığını bulma şansı olabilir. Örneğin kasada işlem yapıldığında aynı fatura içerisinde yer alan SKU’ların beraber satıldığını kabul edelim.

Örneğin faturaların tutulduğu veri tabanı tablosundaki kayıtlar aşağıdaki şekilde olabilir:

{1,2,3,4},

{1,2},

{2,3,4},

{2,3},

{1,2,4},

{3,4},

{2,4}

Yukarıdaki her faturada, hangi ürünün diğer hangi ürünlerle birlikte satıldığı görülmektedir. Buna göre, örneğin yukarıdaki listedeki ikinci satır, firmanın sattığı ürünlerden 1 ve 2 SKU numarasına sahip ürünleri temsil etmektedir (diyelim ki 1 numaralı ürün kravat ve 2 numaralı ürün gömlek olsun, bu durumda ikinci satır, {1,2} kayıdı ile bize gömlek ve kravatın beraber satıldığını anlatmaktadır)

Apriori algoritmamızın ilk adımı, her ürünün frekansını, yani kaç kere listede geçtiğini saymak olacaktır.

Yukarıdaki tabloda, her ürünün toplam satış sayısı bulunmaktadır. Bu değere frekans veya destek (support) ismi verilmektedir.

Algoritmanın ikinci adımında, asgari destek değerini belirliyoruz. Bu belirleme işlemi, üretilen tabloya göre değişebilmektedir. Yukarıdaki örnek için asgari desteğimiz 3 olsun.

Algoritmanın sıradaki adımı, ürünleri 2’li gruplara ayırmak olacak. Buradaki amaç her elemanın diğer elemanlarla olan münasebetini bulmak. Yukarıdaki tabloda, frekansı düşük olan (daha seyrek olan, sık geçmeyen) elemanları eliyoruz. Bunların sonuç listesinde de yer almayacağını kabul ediyoruz.

Bu defa tablomuzda sadece 2 elamanlı listeleri bulunduruyoruz:

Yukarıdaki tabloda bulunan değerleri listelerdeki çiftlerden çıkmıştır. Örneğin {1,2} değeri, 3 yerde geçmektedir ve bunlar:

{1,2,3,4},

{1,2},

{1,2,4},

Listeleridir ( veya senaryomuz gereği faturalar olarak düşünülebilir). Dolayısıyla {1,2} ikilisi için 3 frekansı hesaplanmış olur.

Yukarıdaki listenin devamında 3 elemanlı listelerin tablosu da çıkarılabilir ancak ne yazık ki 3 veya 4 elamanlı liste örneğimizde çıkarılamamaktadır. Bunun sebebi asgari destek değerimizi 3 kabul etmiş olmamızdır. Örneğin {1,2,4} şeklindeki faturayı ele alalım. Bu değer sadece 2 yerde geçmektedir:

{1,2,3,4},

{1,2,4},

Ve dolayısıyla frekans değeri (destek değeri) 2 olmaktadır. Bu destek değeri, asgari destekten küçük olduğu için kabul edilmemektedir.

Algoritma

Konu üzerindeki ilk yayını yapan Agrawal ve Srikat, tarafınan algoritmanın müsvette kodu (pseudo code) aşağıdaki şekilde verilmiştir.

L₁ = {sık tekrarlanan öğeleri içeren küme}

for(k=2; L _k-1 != 0 ; k++){

C_k = apriori-üret (L _k-1);

forall (işlemler t ÎD){

C_t  ⊂ (C_k,t);

forall adaylar c ∈ C_t{

c.sayaç++;

}

}

L_k={ c ∈C_k | c.sayaç = enküçük }

}

Sonuç = U_k L_k;

Algoritmayı açıklayacak olursak, algoritmadaki L, veri tabanı veya veri kümemizde bulunan öğeleri temsil etmektedir. Apriori üret fonksiyonundan üretilen her bir C_k kümesi için, t bir işlem (transaction) olmak üzere, üretilen bu Ck kümesinin t işlemini tutan sayacı, her münasebette bir arttırıyoruz. Ardından sıradaki L değerini alarak algoritmamız çalışmaya devam ediyor. Sonuç olarak da üretilen bu L değerlerinin birleşim kümesini döndürüyoruz.

Yukarıdaki algoritmada belirsiz olan apriori-üret fonksiyonunu ise aşağıdaki şekilde verebiliriz:

C_k‘ya ekle

select p.eleman₁, p.eleman₂, … p.eleman _k-1, q.eleman _k-1

for(L _k-1 p’den L _k-1 q’ya kadar)

where p.eleman₁, p.eleman₂, … p.eleman _k-2 = q.eleman _{k-2 ,} p.eleman _k-1 < q.eleman _k-1

forall elemanlar c ∈C_k {

forall c’nin (k-1)-alt kümesi s için{

if( s ∉L _k-1 ){

c’yi C_k ‘dan sil

}

}

}

Yukarıdaki algoritma, basitçe bütün adayların üretilerek elemanların aday kümelerine konulmasını hedeflemektedir.