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

Birliktelik Kuralı Madenciliği (Apriori)

Ortaya koyan
Rakesh Agrawal & Ramakrishnan Srikant
Yıl
1994
Tür
Unsupervised pattern discovery algorithm
Aile
Pattern mining

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

Yazı boyutu

Ne işe yarar?

Birliktelik Kuralı Madenciliği, işlem veritabanlarındaki öğeler arasındaki eş-görülme örüntülerini keşfeden denetimsiz bir veri madenciliği tekniğidir.

Agrawal, Imieliński ve Swami tarafından 1993'te resmi olarak tanıtılan ve Agrawal ile Srikant tarafından 1994'te dönüm noktası niteliğindeki Apriori algoritmasıyla geliştirilen bu yöntem, X ⇒ Y biçimindeki kuralları belirler — bu, X öğe kümesini içeren işlemlerin aynı zamanda Y öğe kümesini de içerme eğiliminde olduğu anlamına gelir — ve bu kurallar destek, güvenilirlik ve kaldırma (lift) ile ölçülür.

Yöntemin mantığı

Bir süpermarket fiş kaydını hayal edin: binlerce müşteri ekmek ve tereyağı alıyorsa ve aynı zamanda süt de alıyorsa, bu örüntü dikkat çekmeyi hak eder. Birliktelik Kuralı Madenciliği, her bir fişi titizlikle inceleyen, öğe kombinasyonlarının ne sıklıkla birlikte göründüğünü sayan ve minimum frekansın üzerine çıkan kombinasyonları ortaya çıkaran titiz bir kütüphaneci gibi çalışır. Sık görülen gruplar bulunduğunda, algoritma şunu sorar: bu öğelere zaten sahip olduğunuz göz önüne alındığında, bu bir sonraki öğeyi ne kadar güvenilir bir şekilde tahmin eder? Bu frekans-sonra-güvenilirlik iki aşamalı mantığı, Apriori'nin özüdür.

Tarih

Agrawal, Imieliński ve Swami'nin (1993) temel makalesi, süpermarket işlem verileri bağlamında birliktelik kuralı problemini tanımladı. Agrawal ve Srikant'ın 1994 tarihli VLDB makalesi, büyük ölçekli madenciliği pratik hale getiren Apriori algoritmasını ve verimli budama stratejisini tanıttı. Sonraki çalışmalar, aday üretimini tamamen ortadan kaldıran FP-Growth'u (Han vd., 2000) ve dikey veri formatında madencilik yapan ECLAT'ı üretti — veri madenciliği müfredatlarının merkezinde yer alan zengin bir algoritmik aile oluşturdu.

Ne zaman kullanılır?

Birliktelik Kuralı Madenciliği, önceden tanımlanmış bir hedef değişken olmaksızın eş-görülme örüntülerini keşfetmenin amaçlandığı büyük işlem veritabanları için uygundur. İşlemler başına öğelerin ikili (mevcut/mevcut değil) olduğunu varsayar. Pazar sepeti analizi, öneri sistemleri, web tıklama akışı analizi ve tıbbi eş-tanı keşfi için uygundur. Sürekli veya sıralı veriler için önceden ayrıştırılmadıkça, çok yüksek boyutluluğa sahip veri kümeleri için (üstel aday uzayı) veya nedensel çıkarım yerine ilişkilendirici çıkarımın gerektiği durumlar için uygun değildir. Alternatifler arasında daha hızlı sık-öğe kümesi numaralandırması için FP-Growth ve zamansal sıra önemli olduğunda dizi madenciliği yer alır.

Sınırlar ve dikkat edilmesi gerekenler

  • Üstel aday uzayı: kural sayısı, farklı öğelerin sayısıyla kombinatoryal olarak artar.
  • Destek-güvenilirlik çerçevesi, öğe taban oranları önemli ölçüde değiştiğinde yanıltıcı kurallara yol açabilir (kaldırma ayarlaması gereklidir).
  • İkili işlem modeli, sürekli değişkenlerin ayrıştırılmasını gerektirir ve bilgi kaybına neden olur.
  • Yüksek minimum destek eşikleri nadir ama değerli kuralları kaçırır; düşük eşikler binlerce önemsiz kural üretir.

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

Güçlü yönleri

  • Tamamen denetimsiz: etiketli veri veya önceden tanımlanmış hedef gerekmez.
  • Yorumlanabilir çıktı: kurallar, nicel destek ve güvenilirliğe sahip insan tarafından okunabilir eğer-o zaman ifadeleridir.
  • Apriori budaması yoluyla ölçeklenebilir; FP-Growth varyantı veritabanı taramalarını tamamen ortadan kaldırır.
  • Alana özgü değil: perakende, sağlık, web analizi ve biyoinformatik alanlarında uygulanır.

Uygulama alanları

  • Perakende: satış noktası işlem günlüklerinden ürün yerleştirme ve çapraz satış önerisi.
  • Sağlık: elektronik sağlık kayıtlarında teşhis, prosedür veya ilaçların eş-görülme analizi.
  • Web analizi: sayfa önerisi ve navigasyon optimizasyonu için tıklama akışı örüntüsü keşfi.
  • Biyoinformatik: eş-ifade edilmiş gen kümelerinin ve protein etkileşim motiflerinin tanımlanması.
  • Siber güvenlik: saldırı örüntülerine işaret eden ilişkili ağ olaylarının tespiti.

Nasıl çalışır?

Nasıl çalışır?

1

Algoritma, her bir X öğe kümesinin ne sıklıkla göründüğünü saymak için işlem veritabanı D'yi tarar. Bir öğe kümesi, yalnızca desteği (onu içeren işlemlerin oranı) kullanıcı tanımlı minimum destek eşiği σ_min'e eşit veya daha yüksek olduğunda sık olarak beyan edilir ve L_k'ya yerleştirilir. Süreç, tekil öğelerle (k=1) başlar ve yinelemeli olarak daha büyük aday kümeler oluşturur.

Formül
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

Desteğin anti-monotonik özelliği, sık görülen bir öğe kümesinin herhangi bir alt kümesinin kendisinin de sık olması gerektiğini belirtir. Apriori, doğrulanmış sık görülen küme L_{k-1}'de olmayan tüm alt kümeleri olan her bir aday k-öğe kümesini budayarak bundan yararlanır. Bu, olası olarak sık görülmeyecek öğe kümeleri için pahalı veritabanı taramalarını önleyerek arama alanını önemli ölçüde azaltır.

Formül
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

Her sık görülen X ∪ Y öğe kümesinden, algoritma X ve Y'nin ayrık alt kümeler olduğu X ⇒ Y kuralları üretir. Bir kural, yalnızca güvenilirliği — Y'nin X verildiğindeki koşullu olasılığı, destek(X ∪ Y) / destek(X) olarak hesaplanır — minimum güvenilirlik eşiği γ_min'e eşit veya daha yüksek olduğunda saklanır. Bu adım, ham eş-görülmeleri yönlü tahmin edici ifadelere dönüştürür.

Formül
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

Saklanan kurallar, Y'nin X ile birlikte görünme olasılığının şans eseri beklenenden ne kadar daha fazla olduğunu ölçen kaldırma (lift) ile sıralanır ve filtrelenir. Kaldırma > 1, bağımsızlığın ötesinde pozitif bir korelasyonu gösterir; kaldırma = 1, bağımsızlığı gösterir; kaldırma < 1, negatif bir korelasyonu gösterir. İkna (conviction) ve kaldıraç (leverage) gibi ek ilginçlik ölçütleri, pratik dağıtım için kural kümesini daha da iyileştirebilir.

Formül
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}

Sık yapılan hatalar

  • Minimum desteği çok düşük ayarlamak analisti yanıltıcı kurallarla doldurur; eşik seçimi alan bilgisi veya çapraz doğrulama gerektirir.
  • İstatistiksel ilişkiyi nedensellikle karıştırmak: yüksek kaldırma, X'in Y'ye neden olduğu anlamına gelmez.
  • Öğe frekans dağılımını göz ardı etmek: yaygın öğeler kurallarda baskın olur ve anlamlı nadir-öğe ilişkilerini gölgede bırakır.
  • Yalnızca güvenilirliği bir kalite metriği olarak ele almak; düşük kaldırma ancak yüksek güvenilirliğe sahip bir kural, rastgele şanstan daha iyi performans göstermeyebilir.

Sık sorulan sorular

Destek, güvenilirlik ve kaldırma (lift) arasındaki fark nedir?

Destek, bir öğe kümesinin veri kümesinde bir bütün olarak ne sıklıkla göründüğünü ölçer. Güvenilirlik, ardılın (consequent) öncül (antecedent) verildiğindeki koşullu olasılığını ölçer. Kaldırma, güvenilirliği ardılın marjinal frekansına göre normalleştirerek, eş-görülmenin bağımsızlık altında beklenenden daha fazla olup olmadığını ortaya çıkarır. Sağlam kural değerlendirmesi için üç metrik birlikte gereklidir.

Apriori algoritması hesaplama maliyetini nasıl azaltır?

Apriori, anti-monotonik özelliğinden yararlanır: bir öğe kümesi sık görülmüyorsa, tüm üst kümeleri de sık görülmemelidir. Tüm alt kümeleri sık olarak doğrulanmamış herhangi bir adayı atarak, algoritma sayım yapmadan önce arama alanının büyük bölümlerini budar ve kaba kuvvet numaralandırmasına kıyasla gereken veritabanı geçiş sayısını önemli ölçüde azaltır.

Ne zaman Apriori yerine FP-Growth kullanmalıyım?

FP-Growth, işlem veritabanını kompakt bir FP-ağacı yapısına sıkıştırdığı ve açık adaylar üretmeden örüntüleri doğrudan çıkardığı için, veri kümesi büyük olduğunda ve minimum destek eşiği düşük olduğunda tercih edilir. Bu, tekrarlanan tam veritabanı taramalarını ortadan kaldırarak, yoğun veri kümelerinde ve çok sayıda sık görülen öğe kümesine sahip veri kümelerinde Apriori'den önemli ölçüde daha hızlı olmasını sağlar.

İlgili yöntemler

Kaynaklar

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    DOI kaynağını aç
    Kopyalandı.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    Yayın kaynağını aç
    Kopyalandı.