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

Apriori Algoritması

Ortaya koyan
Agrawal, R. & Srikant, R.
Yıl
1994
Tür
Frequent itemset and association rule mining algorithm
Aile
Machine learning

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

Yazı boyutu

Ne işe yarar?

Agrawal ve Srikant tarafından 1994 yılında tanıtılan Apriori algoritması, işlem veritabanlarında sık geçen öğe kümelerini ve birliktelik kurallarını keşfetmek için temel yöntemi oluşturur.

Destek (support) değerinin anti-monoton özelliğinden yararlanarak, kullanıcı tarafından belirlenen minimum eşik değerinin üzerinde birlikte ortaya çıkan tüm öğe kombinasyonlarını verimli bir şekilde listelemek için genişlik-öncelikli, seviyeli bir arama kullanır ve ardından bu örüntülerden yorumlanabilir eğer-o zaman kuralları çıkarır.

Yöntemin mantığı

Bir süpermarket fiş veritabanını ele alalım. Apriori'nin temel içgörüsü anti-monoton özelliktir: eğer iki ürün nadiren birlikte alınıyorsa, o çifti içeren daha büyük hiçbir küme sık geçemez. Bu, algoritmanın olası öğe kombinasyonlarının üstel olarak büyük arama uzayını, adayları seviye seviye oluşturarak – tekil öğelerle başlayıp, sonra çiftler, sonra üçlüler – ve herhangi bir adayın alt kümelerinin zaten seyrek olduğu biliniyorsa, veride saymadan önce bile budayarak daraltmasını sağlar.

Tarih

Rakesh Agrawal ve Ramakrishnan Srikant, Apriori algoritmasını 1994'te VLDB'de tanıttılar ve Agrawal ve arkadaşlarının 1993'teki birliktelik kuralı madenciliği problemi formülasyonuna dayandılar. Adı, temel içgörüsünü yansıtır: seviye k+1'de adayları budamak için sık geçen (k)-öğe kümeleri hakkındaki ön bilgiyi kullanmak. Daha sonraki tüm sık geçen öğe kümesi algoritmaları – FP-Growth (2000) ve Eclat dahil – için ölçüt haline geldi ve veri madenciliği ve makine öğrenmesi ders kitaplarında standart bir bölüm olarak kaldı.

Ne zaman kullanılır?

Amaç, işlem veya ikili öğe-mevcudiyet verilerinde – pazar sepeti analizi, anket öğesi birlikte onaylama, tıbbi teşhis birlikte ortaya çıkma veya metin terimi ilişkisi – birlikte ortaya çıkma örüntülerini veya eğer-o zaman ilişkilerini keşfetmek olduğunda Apriori'yi kullanın. Çıktı kurallarının şeffaflığı ve yorumlanabilirliğinin öncelikli olduğu orta büyüklükteki veri kümeleri için uygundur. İşlem veritabanı çok büyükse (milyonlarca satır ve geniş öğe katalogları), çünkü tekrarlanan tam veritabanı taramaları onu FP-Growth'a kıyasla yavaşlatır; bu durumlarda FP-Growth tercih edilir. Ayrıca, önceden ayrıştırılmamış sürekli sayısal veriler için uygun değildir ve yönlülük veya nedensellik modellemez.

Sınırlar ve dikkat edilmesi gerekenler

  • Tekrarlanan tam veritabanı taramaları, büyük veri kümelerinde yavaş olmasına neden olur – ölçekte genellikle FP-Growth tercih edilir.
  • Destek eşiğini düşürmek, yorumlamayı zorlaştıran üstel sayıda aday öğe kümesi ve kural üretebilir.
  • Öğeler arasındaki zamansal sırayı, yönlülüğü veya nedensel ilişkileri yakalamaz.
  • Sonuçlar, alan bilgisi veya sistematik ayarlama gerektiren destek ve güven eşiklerinin seçimine duyarlıdır.

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

Güçlü yönleri

  • Destek, güven ve lift değerleri nicelendirilmiş, tamamen yorumlanabilir eğer-o zaman kuralları üretir.
  • Anti-monoton budama özelliği, aksi takdirde üstel olan bir aramayı çözülebilir hale getirir.
  • Verinin önceden etiketlenmesini gerektirmez; tamamen denetimsizdir.
  • Eşik parametreleri (destek, güven), analiste kural granülerliği üzerinde doğrudan kontrol sağlar.
  • Çıktı kuralları eyleme geçirilebilir ve algoritmik geçmişi olmayan teknik olmayan paydaşlara iletilebilir.
  • Temel, yoğun atıf alan ve hemen hemen her büyük veri madenciliği kütüphanesinde uygulanan bir yöntemdir.

Uygulama alanları

  • Pazar sepeti analizi: raf düzenini ve promosyonları yönlendirmek için hangi ürünlerin sıklıkla birlikte satın alındığını keşfetmek.
  • Tıbbi bilişim: hasta kayıtlarında birlikte ortaya çıkan semptomları, teşhisleri veya ilaç reçetelerini belirlemek.
  • Web kullanım madenciliği: kullanıcıların hangi sayfaları veya özellikleri birlikte ziyaret etme veya etkinleştirme eğiliminde olduğunu bulmak.
  • Anket ve soru formu analizi: hangi öğelerin veya ölçek yanıtlarının sistematik olarak birlikte onaylandığını tespit etmek.
  • Öneri sistemi başlatma: işbirlikçi filtrelemeyi dağıtmadan önce aday öğe ilişkileri oluşturmak.
  • Dolandırıcılık tespiti: normal sepetlerden sapan işlem günlüklerindeki sıra dışı birlikte ortaya çıkma örüntülerini ortaya çıkarmak.

Nasıl çalışır?

Nasıl çalışır?

1

Analist, algoritmayı çalıştırmadan önce iki eşik değeri seçer: minimum destek (belirli bir öğe kümesinin sık geçtiği kabul edilmesi için gereken işlem oranı) ve minimum güven (tutulacak bir eğer-o zaman kuralı için gereken koşullu olasılık). Bu iki değer, çıktının hacmini ve özgüllüğünü kontrol eder ve alan bilgisi veya keşifsel çalıştırmalar yoluyla ayarlanmalıdır.

2

Algoritma, her bir tekil öğenin ne sıklıkla göründüğünü saymak için işlem veritabanının tam bir taramasını yapar. Yalnızca desteği minimum destek eşiğini karşılayan veya aşan öğeler tutulur; diğerleri atılır. Bu sık geçen tekil öğeler kümesi, adayların ilk seviyesini oluşturur.

Formül
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

k seviyesinde bulunan sık geçen öğe kümeleri, k+1 boyutunda aday öğe kümeleri oluşturmak üzere ikili olarak birleştirilir. Yalnızca aynı ilk k-1 öğeyi paylaşan çiftler birleştirilir; bu kural aday kümesini kompakt tutar. Yeni bir veritabanı taraması, her adayın desteğini sayar.

4

Sayım yapmadan önce, k+1 boyutundaki her aday, tüm (k)-alt kümeleriyle karşılaştırılır. Herhangi bir alt küme önceki seviyede sık geçmediyse, aday veriyi okumadan hemen budanır ve anti-monoton özellikten yararlanarak hesaplama azaltılır. Bu budama adımından kurtulanlar, bir sonraki seviyedeki sık geçen öğe kümelerini oluşturur.

5

İki veya daha fazla öğe içeren her sık geçen öğe kümesinden, öğelerin bir öncül (antecedent) ve bir sonuç (consequent) olarak ayrılmasıyla olası tüm eğer-o zaman kuralları üretilir. Her kural, güven değerine göre değerlendirilir – öncülü içeren işlemlerin ne kadarının sonucu da içerdiğinin oranıdır. Minimum güvenin altındaki kurallar atılır.

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

Kalan kurallar, gözlemlenen güveni sonucun taban çizgi frekansıyla karşılaştıran lift (kaldıraç) değerine göre sıralanır. 1'in üzerindeki bir lift, öncül ve sonucun tesadüfen değil, şans eseri daha fazla birlikte ortaya çıktığını gösterir; 1'e yakın lift bağımsızlığı, 1'in altındaki lift ise negatif bir ilişkiyi gösterir. En yüksek lift değerine sahip kurallar en eyleme geçirilebilir keşiflerdir.

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

Sık yapılan hatalar

  • Minimum desteği çok düşük ayarlayıp lift ile filtreleme yapmadan binlerce düşük kaliteli kural içinde boğulmak.
  • Yüksek güveni nedensellik yerine birlikte ortaya çıkma olarak yorumlamak – yüksek güvene ancak lift değeri 1'e yakın olan bir kural önemsizdir.
  • Apriori'yi sürekli özellikleri önce ayrıştırmadan uygulamak, öğe uzayını şişirir ve sonuçları bozar.
  • Öğe kümesi örneklem boyutlarının destek tahminlerine güvenmek için yeterince büyük olup olmadığını kontrol etmeden kuralları raporlamak.
  • Bilgilendirici olmayan kuralları (örneğin, bir mağaza sadakat kartı gibi evrensel olarak satın alınan öğeleri içeren kurallar) kaldırmayı ihmal etmek.

Sık sorulan sorular

Destek, güven ve lift arasındaki fark nedir?

Destek, öğe kümesini içeren tüm işlemlerin oranıdır – yaygınlığı ölçer. Güven, öncül verildiğinde sonucun ortaya çıkma koşullu olasılığıdır – kural güvenilirliğini ölçer. Lift, gözlemlenen güvenin sonucun taban çizgi frekansına oranıdır; 1'in üzerindeki bir lift, öğe popülerliğinden kaynaklanan bir tesadüf yerine gerçek bir pozitif ilişkiyi gösterir.

Apriori yerine ne zaman FP-Growth seçmeliyim?

FP-Growth, veritabanını bir ağaç yapısına sıkıştırır ve tekrarlanan tam taramalar olmadan madencilik yapar, bu da onu büyük veri kümelerinde veya minimum destek düşük olduğunda önemli ölçüde daha hızlı hale getirir. Apriori'nin anlaşılması ve uygulanması daha kolaydır ve çalışma zamanının darboğaz olmadığı küçük ila orta ölçekli veri kümelerinde iyi çalışır.

Minimum destek ve güveni nasıl seçerim?

Evrensel bir kural yoktur. Yaygın uygulama, algoritmayı birkaç destek seviyesinde çalıştırmak, sık geçen öğe kümelerinin sayısını destekle çizmek ve eğrinin dirsek kısmında bir değer seçmektir. Güven daha sonra iş veya araştırma sorusuna göre ayarlanır – kritik görev kuralları için daha yüksek güven, keşifsel keşif için daha düşük güven. En iyi kuralları her zaman alan uzmanlığına göre doğrulayın.

Apriori sayısal veya sürekli verileri işleyebilir mi?

Apriori, ikili öğe-mevcudiyet verileri gerektirir. Sürekli değişkenler, öğe olarak kodlanmadan önce gruplara ayrılmalıdır (örneğin, yaş düşük/orta/yüksek olarak). Kötü ayrıştırma, keşfedilen kuralları ciddi şekilde bozabilir, bu nedenle gruplama stratejisi dikkatli düşünülmeyi hak eder.

Apriori öğeler arasında nedensellik anlamına mı geliyor?

Hayır. Birliktelik kuralları nedenselliği veya yönlülüğü değil, birlikte ortaya çıkmayı yakalar. 'Ekmek → tereyağı' kuralı, aynı sepette sık sık göründükleri anlamına gelir; bu, ekmek almanın birinin tereyağı almasına neden olduğu anlamına gelmez, ne de ilişkinin herhangi bir nedensel anlamda asimetrik olduğu anlamına gelir.

İlgili yöntemler

Kaynaklar

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Yayın kaynağını aç
    Kopyalandı.
  2. Apriori algorithm. Wikipedia.

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