İçeriğe atla
Arama sonuçlarına dön

FP-Growth (Sık Desen Büyümesi)

Ortaya koyan
Jiawei Han, Jian Pei & Yiwen Yin
Yıl
2000
Tür
Frequent-itemset mining algorithm
Aile
Pattern mining

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Jiawei Han, Jian Pei ve Yiwen Yin tarafından 2000 yılında tanıtılan FP-Growth, klasik Apriori algoritmasını yavaşlatan maliyetli adım olan aday kümeler oluşturmadan işlem verilerinden sık öğe kümelerini çıkarır.

Veritabanını iki taramada sık-desen ağacına (FP-tree) sıkıştırır, ardından bu yapıdan özyinelemeli olarak sık desenler büyütür, bu da onu büyük, yoğun veri kümelerinde Apriori'den önemli ölçüde daha hızlı hale getirir.

Yöntemin mantığı

Apriori, sık öğe kümelerini tekrarlı olarak aday kombinasyonlar oluşturup test ederek bulur — bu, yoğun verilerde patlayan pahalı, tarama ağırlıklı bir süreçtir. FP-Growth farklı bir yol izler: tüm işlem veritabanını, paylaşılan ön eklerin bir kez saklandığı, böylece yaygın desenlerin örtüştüğü ve sıkıştığı kompakt bir ağaca sıkıştırır. Ardından, adaylar oluşturmak yerine, her öğeye giden yolları izleyerek ve daha küçük 'koşullu' ağaçları özyinelemeli olarak madencilik yaparak sık desenleri doğrudan ağaçtan okur. Veri üzerinde iki geçiş ve akıllı bir veri yapısı, Apriori'nin birçok geçişini ve birleşimsel aday şişmesini değiştirir.

Tarih

Han, Pei ve Yin, FP-Growth'u 2000 yılında SIGMOD'da Apriori'ye aday üretiminden bağımsız bir alternatif olarak sundular ve 2004 tarihli Veri Madenciliği ve Bilgi Keşfi makalelerinde genişletilmiş bir inceleme yaptılar. Sık-desen ağacı fikri — işlemleri paylaşılan bir ön ek yapısına sıkıştırmak ve özyinelemeli olarak madencilik yapmak — Apriori (aday tabanlı) ve ECLAT (dikey format) ile birlikte desen madenciliğinde temel bir teknik haline geldi. Veri madenciliği kütüphanelerinde standart, yüksek performanslı bir öğe kümesi madencisi olmaya devam ediyor.

Ne zaman kullanılır?

Sık öğe kümelerini (ve dolayısıyla ilişki kurallarını) işlem verilerinden — pazar sepeti analizi, web kullanımı ve tıklama akışı madenciliği, öneri ve biyoinformatik birlikte ortaya çıkma — özellikle Apriori'nin aday üretiminin çok yavaş olduğu büyük veya yoğun veri kümelerinde çıkarmak için FP-Growth kullanın. Yalnızca iki veritabanı taraması gerektirir ve tipik olarak Apriori'den çok daha iyi performans gösterir. Maliyetleri: FP-ağacı bellekte kalmalıdır (çok büyük veya aşırı seyrek veriler için bir sınırlama, ağacın kötü sıkıştığı yerlerde), özyineleme uygulaması karmaşık olabilir ve destek tabanlı madencilikteki tümü gibi minimum destek eşiğine duyarlıdır (çok düşük çıktı patlamasına neden olur, çok yüksek desenleri kaçırır). ECLAT (dikey tidset kesişimi) bir alternatiftir; kuralların kendisi için, ilişki kuralı üretimiyle eşleştirin.

Sınırlar ve dikkat edilmesi gerekenler

  • FP-ağacı bellekte kalmalıdır; çok büyük veri kümeleri kalmayabilir.
  • Seyrek verilerde ağaç kötü sıkışır, avantajı aşındırır.
  • Özyinelemeli koşullu ağaç yapısı uygulaması nispeten karmaşıktır.
  • Tüm sık öğe madenciliği gibi minimum destek eşiğine duyarlıdır.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Aday üretimi yok — büyük/yoğun verilerde Apriori'den çok daha hızlı.
  • Desen uzunluğundan bağımsız olarak yalnızca iki veritabanı taraması.
  • FP-ağacı paylaşılan yapıyı sıkıştırır, yoğun verilerde bellek ve zaman tasarrufu sağlar.
  • Aday tabanlı yöntemleri aşırı yükleyen uzun sık desenlere ölçeklenir.

Uygulama alanları

  • Pazar sepeti analizi ve perakende ilişki madenciliği.
  • Web kullanımı ve tıklama akışı desen madenciliği.
  • Sık sık birlikte ortaya çıkan öğeler aracılığıyla öneri.
  • Biyoinformatik birlikte ortaya çıkma ve motif keşfi.
  • Apriori'nin çok yavaş olduğu herhangi bir büyük ölçekli sık öğe kümesi görevi.

Nasıl çalışır?

Nasıl çalışır?

1

İlk veritabanı taraması her öğenin desteğini sayar ve minimum destek eşiğinin altındakileri atar. Kalan sık öğeler azalan frekansa göre sıralanır — bu sıralama, işlemlerin ağaç ön eklerini paylaşmasını sağlar ve FP-ağacını kompakt tutar.

Formül
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

İkinci tarama, her işlemi (sıralanmış sıradaki sık öğeleri) FP-ağacına ekler, paylaşılan ön ek yolları boyunca sayaçları artırır ve gerektiğinde yeni dallar ekler. Bir başlık tablosu, her öğenin tüm oluşumlarını bağlar, böylece ağaç tüm veri kümesinin sık yapısını kompakt bir şekilde temsil eder.

Formül
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Her sık öğe için (en az sık olandan başlanarak işlenir), algoritma, o öğeyle birlikte ortaya çıkan ağaçtaki ön ek yolları kümesi olan koşullu desen tabanını toplar, her biri sayısıyla ağırlıklandırılır. Bu, öğenin sık göründüğü bağlamı yakalar.

Formül
\text{for each item: collect its conditional pattern base (prefix paths)}
4

Her koşullu desen tabanından daha küçük bir koşullu FP-ağacı oluşturulur ve özyinelemeli olarak madencilik yapılır, sık desenleri koşullu ağacında bulunan desenlere öğeyi ekleyerek uzatır. Özyineleme, öğe kümesi kombinasyonlarının doğrudan sayıldığı tek yollu ağaçlarda sonlanır — aday üretimi olmadan tüm sık öğe kümelerini verir.

Formül
\text{build conditional FP-trees recursively to grow frequent patterns}

Sık yapılan hatalar

  • Minimum desteği çok düşük ayarlamak, bir öğe kümesi patlamasına neden olur.
  • Her zaman Apriori'yi yendiğini varsaymak — küçük veya seyrek verilerde kazanç mütevazıdır.
  • Sık öğe kümelerinin kural olmadığını unutmak; kural üretimi ayrı bir adımdır.
  • FP-ağacının RAM'de tutulamadığı bellek sınırlarını göz ardı etmek.

Sık sorulan sorular

FP-Growth, Apriori'den nasıl daha hızlıdır?

Apriori, aday öğe kümelerini tekrarlı olarak oluşturur ve test eder, veritabanını birçok kez tarar. FP-Growth, aday üretimini tamamen ortadan kaldırır: veriyi iki taramada bir FP-ağacına sıkıştırır ve desenleri özyinelemeli olarak ondan çıkarır. Bu, birleşimsel aday şişmesini ortadan kaldırır ve yoğun verilerde büyük hız artışları sağlar.

FP-ağacı nedir?

Veritabanının sık öğelerinin sıkıştırılmış bir ön ek ağacıdır. Bir ön eki paylaşan işlemler, bir yol paylaşır, düğüm sayaçları desteği kaydeder ve bir başlık tablosu her öğenin oluşumlarını bağlar. Veri kümesinin sık yapısını kompakt bir şekilde saklar, böylece desenler veriyi yeniden taramadan okunabilir.

FP-Growth, ECLAT ve ilişki kurallarıyla nasıl ilişkilidir?

FP-Growth, ECLAT ve Apriori hepsi sık öğe kümelerini bulur; ECLAT, bir ağaç yerine dikey bir tidset kesişimi yaklaşımı kullanır. Sık öğe kümelerini bulmak yalnızca ilk aşamadır — ilişki kuralları (güven/kaldıraç ile) bu öğe kümelerinden ayrı bir adımda oluşturulur.

İlgili yöntemler

Kaynaklar

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    DOI kaynağını aç
    Kopyalandı.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    DOI kaynağını aç
    Kopyalandı.