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

ECLAT Sık-Öğe Kümesi Madenciliği

Ortaya koyan
Mohammed J. Zaki
Yıl
2000
Tür
Frequent-itemset mining algorithm (vertical format)
Aile
Pattern mining

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

Yazı boyutu

Ne işe yarar?

ECLAT, Mohammed Zaki tarafından 2000 yılında tanıtılmış olup, sık-öğe kümelerini dikey veri temsili kullanarak madencilik yapar: işlemleri taramak yerine, her öğe için onu içeren işlem kimlikleri kümesini (bir tidset) depolar ve herhangi bir öğe kümesinin desteğini tidset'leri kesiştirerek hesaplar.

Bu derinlemesine, kesişim tabanlı yaklaşım, Apriori'nin yatay taramalarına ve FP-Growth'un ağacına bir alternatif olarak hızlı ve bellek açısından verimlidir.

Yöntemin mantığı

Çoğu öğe kümesi madencisi satır satır düşünür: her işlemde hangi öğeler var? ECLAT masayı yan çevirir. Her öğe için onu içeren işlemlerin bir listesini tutar. Şimdi bir öğe çiftinin desteği, iki listelerinin örtüşmesinin boyutu - basit bir küme kesişimi - ve veritabanını asla yeniden taramazsınız. Daha uzun sık öğe kümeleri bulmak için, daha kısa olanların listelerini kesiştirin. Bunu derinlemesine yürüterek ve bir kesişim çok küçüldüğünde budayarak tüm sık öğe kümelerini verimli bir şekilde numaralandırır.

Tarih

Mohammed Zaki, ECLAT'ı ve dikey madencilik paradigmasını, daha sonra fark kümeleriyle (dECLAT) iyileştirdiği ölçeklenebilir birliktelik madenciliği üzerine 2000 IEEE TKDE makalesinde doruğa ulaşan çalışmasında tanıttı. Apriori (1994, yatay aday üretimi) ve FP-Growth (2000, ağaç tabanlı) ile birlikte, her biri tarama, bellek ve veri yoğunluğunu farklı şekilde dengeleyen üç kanonik sık-öğe kümesi algoritması ailesinden biri olarak yerini aldı. ECLAT, veri madenciliği araç takımlarında standart bir seçenek olmaya devam etmektedir.

Ne zaman kullanılır?

ECLAT'ı, dikey, kesişim tabanlı bir yaklaşımın verilere uygun olduğu durumlarda sık-öğe kümesi madenciliği için kullanın - yoğun veri kümelerinde genellikle çok hızlıdır ve tekrarlanan veritabanı taramalarından kaçınır, bu da onu Apriori'ye güçlü bir alternatif ve FP-Growth'a denk hale getirir. Tidset'lerin orta boyutta olduğu ve belleğe sığdığı durumlarda parlar ve fark kümesi varyantı yoğun verileri iyi işler. Maliyetleri: sık öğeler için tidset'ler büyük ve büyük seyrek veri kümelerinde bellek açısından ağır olabilir, ara kesişimler ek yük getirir ve destek tabanlı tüm madencilik gibi minimum destek eşiğine duyarlıdır. Her zaman olduğu gibi, sık öğe kümeleri yalnızca ilk aşamadır; güvenilirlik/kaldırma ile birliktelik kuralları daha sonra oluşturulur. Veri yoğunluğu ve belleğe göre ECLAT, FP-Growth ve Apriori arasından seçim yapın.

Sınırlar ve dikkat edilmesi gerekenler

  • Sık öğeler için tidset'ler büyük olabilir, büyük veri kümelerinde bellek maliyeti olur.
  • Ara kesişim sonuçları bellek/zaman ek yükü ekler.
  • Yatay (Apriori) temsillerden daha az sezgisel.
  • Tüm öğe kümesi madenciliği gibi minimum destek eşiğine duyarlı.

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

Güçlü yönleri

  • Hızlı tidset kesişimleri ile hesaplanan destek - tekrarlanan veritabanı taraması yok.
  • Önek eşdeğerlik sınıflarıyla derinlemesine arama, işi yeniden kullanır ve belleği yerelleştirir.
  • Yoğun veri kümelerinde genellikle çok verimli, FP-Growth ile rekabetçi.
  • Fark kümesi optimizasyonu bellek ve kesişim maliyetini daha da azaltır.

Uygulama alanları

  • Pazar sepeti ve perakende birliktelik madenciliği.
  • Web ve tıklama akışı eş-görünme analizi.
  • Biyoenformatik sık eş-görünme keşfi.
  • Dikey, kesişim tabanlı bir yaklaşımı tercih eden herhangi bir sık-öğe kümesi görevi.
  • Fark kümesi ECLAT'ın üstün olduğu yoğun işlem veri kümeleri.

Nasıl çalışır?

Nasıl çalışır?

1

Veritabanı bir kez dikey formata dönüştürülür: her öğe, göründüğü işlem kimlikleri kümesi olan tidset'ine eşlenir. Bu anahtar veri yapısıdır - sonraki tüm çalışmalar, orijinal işlemler üzerindeki geçişler değil, tidset'ler üzerindeki küme işlemleridir.

Formül
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

Bir öğe kümesinin desteği, öğelerinin tidset'lerinin kesişiminin kardinalitesidir - hepsini içeren işlem sayısıdır. Sayma, hızlı olan kesişim haline gelir ve sık tek öğeler (tidset'i yeterince büyük olanlar) aramayı başlatır.

Formül
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Öğe kümeleri, tidset'leri kesiştirerek genişletilir: X ∪ {y} öğe kümesinin tidset'i, X ve {y} öğe kümelerinin tidset'lerinin kesişimidir. ECLAT, öğe kümesi kafesini eşdeğerlik sınıfları (bir önek paylaşan öğe kümeleri) içinde derinlemesine keşfeder, böylece kesişimler yeniden kullanılır ve arama yerel kalır.

Formül
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

Bir genişletme yalnızca tidset'i (dolayısıyla destek) minimum destek eşiğini karşılıyorsa tutulur; aksi takdirde o dal budanır (anti-monotonluk: hiçbir üst küme sık olamaz). Fark kümeleri (diffsets) - yalnızca tidset'ler arasındaki farkları depolayan - belleği ve kesişim maliyetini daha da azaltan yaygın bir optimizasyondur.

Formül
\text{keep extensions with } \text{support} \ge \text{minsup}

Sık yapılan hatalar

  • Tidset'lerin belleği şişirdiği çok büyük seyrek verileri madenciliği - fark kümelerini veya FP-Growth'u düşünün.
  • Minimum desteği çok düşük ayarlamak ve yönetilemez sayıda öğe kümesi üretmek.
  • Sık öğe kümelerini birliktelik kurallarıyla karıştırmak (kurallar ayrı bir adımdır).
  • Yoğun verilerde büyük ölçüde yardımcı olduğu fark kümesi varyantını göz ardı etmek.

Sık sorulan sorular

ECLAT, Apriori ve FP-Growth'tan nasıl farklıdır?

Her üçü de sık öğe kümeleri bulur. Apriori, aday üretimi ve birçok tarama ile yatay bir format kullanır; FP-Growth veriyi bir ağaçta sıkıştırır ve özyinelemeli olarak madencilik yapar; ECLAT dikey bir tidset formatı kullanır ve işlem kimliği listelerini derinlemesine kesiştirerek desteği hesaplar. ECLAT ve FP-Growth, Apriori'nin tekrarlanan taramalarından kaçınır.

Tidset nedir?

Bir tidset (işlem kimliği kümesi), verilen bir öğeyi veya öğe kümesini içeren işlemlerin listesidir. ECLAT bunları dikey olarak depolar ve bir öğe kümesinin desteğini, öğelerinin tidset'lerinin kesişiminin boyutu olarak hesaplar, saymayı küme kesişimine dönüştürür.

Fark kümeleri (diffsets) nedir?

Fark kümeleri, tam tidset yerine, bir öğe kümesinin tidset'i ile üst öğesinin tidset'i arasındaki farkı depolar. Yoğun verilerde bu, bellek ve kesişim maliyetini önemli ölçüde azaltır, bu da dECLAT varyantına önemli bir verimlilik avantajı sağlar.

İlgili yöntemler

Kaynaklar

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    DOI kaynağını aç
    Kopyalandı.