-

Fp-Growth Algoritması

Fp-Growth algoritması büyük veri kümelerinde çalışmaktadır ve sistem kaynaklarını verimli bir şekilde kullanan birliktelik kuralı çıkarım algoritmasıdır. Fp-Growth algoritması kendisi ile aynı işi yapan diğer birçok algoritmaya göre daha performanslı çalışır ve maliyeti azaltır, algoritma böl ve yönet stratejisini kullanmaktadır. En önemli özelliği tüm veri tabanını FP-Ağaç (Fp-Tree, Frequent Pattern Tree) adı verilen sıkıştırılmış bir ağaç veri yapısı şeklinde tutmasıdır. Algoritma veri tabanını toplamda iki kez tarar, ilk taramada bütün öğelerin destek değerini hesaplar, ikinci taramada ağaç veri yapısını oluşturur. Fp-Growth algoritması yaygın öğeler kümesini bulurken aday öğeler kümesi kullanmaz, yaygın öğeler Fp-Ağaç yapısından bulunur.

Genel olarak algoritma üç adımdan oluşur; destek sayılarının hesaplanması, Fp-Ağaç yapısının kurulması ve ağaç yapısından kuralların çıkarılması. Veri tabanı ilk kez tarandığında bulunan destek sayıları içerisinde minimum destek değerinden küçük olanlar hesaplama dışında bırakılır. Aşağıdaki tabloda bir alışveriş sepeti örneği bulunmaktadır, bu tabloda bulunan her harf bir ürünü temsil eder, tabloda farklı alışverişlerde aynı anda alınan ürünler görülebilir. İlk aşamada veri tabanı destek değerlerini bulmak üzere 1 kez taranır ve ürünlerin destek sayıları hesaplanır. Öğelerin ağaçtaki başlangıç noktaları Başlık Tablosu’nda (header table), Şekil 1’deki gibi tutulur, bu tablo ağaçta dolaşmayı ve ağaç içerisinde işaretçiler ile birbirine bağlanan aynı düğümlerin takibini kolaylaştırır. Minimum destek değerinin bu örnek için 2 olduğu varsayılır, buna göre {e} ürünü hesaplamalara dahil edilmeyecektir. Bulunan destek değerlerine göre ürünler en büyük destek değerinden en küçük destek değerine sahip olan ürünler şeklinde sıralanır. Bulunan yaygın öğeler (c:5), (a:4), (b:3), (d:3), (f:2) şeklinde sıralanır. Aynı zamanda her bir alışveriş sepeti içindeki öğeler de sıklıklarına göre sıralanırlar. Daha önce minimum destek eşiğinden dolayı elenen değerler sıralamaya eklenmez, örneğimiz için {e} ürünü sıralı ürünlere dahil edilmez, aşağıdaki tabloda Sıralı Ürünler’i de görmek mümkündür.

 

Alışveriş No Sepetteki Ürünler Sıralı Ürünler
 1 a, b, c c, a, b
2 c, d, a c, a, d
3 e, f, c ,b c, b, f
4 a, b, c, d, e c, a, d, b
5 a, c, d, f c, a, d, f

Hesaplama işlemlerinden sonra Fp-Ağaç yapısının kurulması işlemine geçilir. Ağaç yapısında kök (root) boş küme olarak yazılır. Daha sonra her bir alışveriş sepetinin sıralı şekli 1 numaralı alışverişten başlanarak ağaca yerleştirilir. İşlem yapılacak öğe ağaçta yer almıyorsa onun için yeni bir düğüm eklenir ve destek değeri 1 yapılır. Destek değerleri de ağaçtaki öğeler ile birlikte tutulur. Eğer öğe ağaçta var ise destek değeri 1 arttırılır. Alışveriş sepetindeki sıralı öğeler Şekil 1’deki gibi ağaca yerleştirilmiştir.

Şekil1

Şekil 1

 

Fp-Ağacı’nın özellikleri;

Bütünlük;

  • Yaygın öğeleri bulmak için bütün öğeleri barındırmaktadır.

Sıkıştırılmış;

  • Yaygın olmayan öğeler Fp-Ağacı’nda bulunmaz,
  • Destek sayısı daha büyük olan öğeler ağacın köküne daha yakındır,
  • Asıl veri kümesinden daha büyük değildir.

Fp-Ağacı’ndan koşullu örüntü çıkarılması

Başlık Tablosu’ndanher öğenin bulunduğu ilk düğüm tespit edilir ve ağaç içerisinde aşağıdan yukarıya olacak şekilde öğenin ulaşabileceği bütün düğümlere ulaşılır, koşullu örüntü temelleri (conditional pattern base) bulunur. Şekil 1’deki örnek için bulunabilecek koşullu örüntü temelleri aşağıdaki tablodaki gibidir. Kök düğümden sonra gelen ilk düğüm c dir, tek başına kural oluşturamayacağı için ondan sonra gelen düğümden başlanarak kök düğüme doğru her bir öğenin koşullu örüntüleri bulunmuştur.

Öğe Koşullu Örüntü
 a c:4
b ac:2, c:3, a:2
d ac:3
f c:2

 

Şekil 2’den Fp-Growth algoritmasının genel yapısı görülebilir. Algoritmada öncelikle veri tabanındaki her bir nesnenin destek değeri hesaplanır, algoritmaya girdi olarak verilen minimum destek değerine eşit ve büyük olanlar öğeler F listesine eklenir ve büyükten küçüğe doğru sıralanır. Her bir alışveriş sepeti için öğelerin destek değerine göre sıralanarak sıkıştırılmış biçimde ağaca yerleştirilir. Eklenecek öğe ağaçta yoksa onun için yeni bir düğüm eklenir ve destek değeri 1 verilir, öğe ağaçta var ise destek değeri 1 arttırılır. Ağaç içerisinde aynı nesneyi içeren öğeler birbirine bağlanır. Bu şekilde öğeler ağacı oluşturulmuş olur.

Şekil 2

Şekil 2

 

Bundan sonraki aşamada ağaçtaki her bir öğe için Şekil 3’deki Growth algoritması çalıştırılır. Öncelikle öğenin içerisinde geçtiği bütün yollar belirlenir, tek bir dal varsa yaygın öğeler kümesi o dalı oluşturulan nesnelerin kombinasyonudur.  Bulunan yollar o öğe için koşullu örüntü temelini oluşturur, her bir koşullu örüntü temelinden koşullu örüntü ağacı oluşturulur. Growth algoritması destek değeri en küçük öğeden başlanarak her bir öğe için ayrı ayrı çalıştırılır. Algoritmanın bu kısmı için Şekil 1’de verdiğimiz Fp-Ağacından {b}  öğesini düşünecek olursak ; {b}’nin geçtiği yollar (c:5,a:4,b:1), (c:5,a:4,d:3,b:1), (cb:1) dir. Algoritmanın {b} için çalıştırıldığını varsaydığımızdan b kümelere dahil edilmez, geriye kalan kümelerin destek sayıları {b}’nin destek değerine eşittir.  (c:1,a:1), (c:1,a:1,d:1), (c:1)  yolları {b}’nin şartlı örüntü temelleridir. Bu yollar için algoritma tekrar çalıştırılır. Öğelerin destek değeri; (c:3), (a:2), (d:1) olur, minimum destek değeri 2 olduğundan {d} elenmiş olur. {c} ve {a} öğeleri için yeni yaygın öğe ağacı kurulur. {c} için {(cab:2),(cb:3)} yaygın öğeleri, {a} için (ab:2) bulunur. Sonuç olarak {b} için {(b:3), (cab:2), (cb:3), (ab:2)} yaygın öğeleri bulunur. Algoritma örüntü ağacı üzerinde özyinelemeli (recursive) olarak çalışır. Her bir eleman için Growth algoritması çalıştırıldığında yaygın öğeler kümeleri oluşturulmuş olur.

Şekil 3

Şekil 3

 

Kaynaklar:

[1]   Birant, D.,Kut, A., Ventura, M., Altınok, H., Altınok, B., Altınok, E., Ihlamur, M., 2010, İş Zekası Çözümleri için Çok Boyutlu Birliktelik Kuralları Analizi, 12. Akademik Bilişim Konferansı Bildirileri, 10-12 Şubat 2010 Muğla, Türkiye, 257-264.

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

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

*