Apriori-algoritm

Apriori är en algoritm för frekvent brytning av objektuppsättningar och inlärning av associationsregel över relationsdatabaser . Den fortsätter genom att identifiera de frekventa enskilda objekten i databasen och utöka dem till större och större objektuppsättningar så länge som dessa objektuppsättningar förekommer tillräckligt ofta i databasen. De frekventa artikeluppsättningarna som bestäms av Apriori kan användas för att fastställa associationsregler som lyfter fram allmänna trender i databasen : denna har applikationer inom domäner som marknadskorganalys .

Översikt

Apriori-algoritmen föreslogs av Agrawal och Srikant 1994. Apriori är utformad för att fungera på databaser som innehåller transaktioner (till exempel samlingar av föremål som köpts av kunder, eller uppgifter om en webbplatsbesök eller IP-adresser ). Andra algoritmer är utformade för att hitta associationsregler i data som inte har några transaktioner ( Winepi och Minepi), eller som saknar tidsstämplar (DNA-sekvensering). Varje transaktion ses som en uppsättning poster (en artikeluppsättning ). Givet ett tröskelvärde $C$ identifierar Apriori-algoritmen objektuppsättningarna som är delmängder av åtminstone $C$ -transaktioner i databasen.

Apriori använder en "bottom up"-metod, där frekventa delmängder utökas med ett objekt i taget (ett steg som kallas kandidatgenerering ), och grupper av kandidater testas mot data. Algoritmen avslutas när inga fler framgångsrika tillägg hittas.

Apriori använder bredd-först-sökning och en Hash-trädstruktur för att effektivt räkna kandidatuppsättningar. Den genererar kandidatuppsättningar av objekt med längden $k$ från objektuppsättningar med längden $k-1$ . Sedan beskär den kandidaterna som har ett sällsynt undermönster. Enligt det nedåtgående stängningslemmat innehåller kandidatmängden alla frekventa $k$ -längd objektuppsättningar. Efter det skannar den transaktionsdatabasen för att fastställa frekventa artikeluppsättningar bland kandidaterna.

Pseudokoden för algoritmen ges nedan för en transaktionsdatabas $T$ och ett stödtröskelvärde på $\varepsilon$ . Vanlig mängdteoretisk notation används, men observera att $T$ är en multiset . $C_{k}$ är kandidatuppsättningen för nivå $k$ . Vid varje steg antas algoritmen generera kandidatuppsättningarna från de stora föremålsuppsättningarna på föregående nivå, med beaktande av det nedåtgående stängningslemmat. $\mathrm {count} [c]$ kommer åt ett fält i datastrukturen som representerar kandidatmängden ${\displaystyle c} ,$ som initialt antas vara noll. Många detaljer utelämnas nedan, vanligtvis är den viktigaste delen av implementeringen datastrukturen som används för att lagra kandidatuppsättningarna och räkna deras frekvenser.

  Apriori  (T, ε) L ₁ ← {stor 1 - objektuppsättningar} k ← 2  medan  L _k−1 inte är  tom C _k ← Apriori_gen(L _k−1 , k)  för  transaktioner t  i  T D _t ← {c i C _k : c ⊆ t}  för  kandidater c  in  D _t count[c] ← count[c] + 1 L _k ← {c in C _k : count[c] ≥ ε} k ← k + 1  retur  Union(L _k )  Apriori_gen  (L, k) resultat ← list()  för alla  p ∈ L, q ∈ L  där  p ₁ = q ₁ , p ₂ = q ₂ , ..., p _k-2 = q _k-2 och p _k-1 < q _k-1 c = p ∪ {q _k-1 }  om  u ∈ L  för alla  u ⊆ c  där  |u| = k-1 resultat.add(c)   returnerar  resultat

Exempel

Exempel 1

Tänk på följande databas, där varje rad är en transaktion och varje cell är en individuell post i transaktionen:

alfa	beta	epsilon
alfa	beta	theta
alfa	beta	epsilon
alfa	beta	theta

Föreningsreglerna som kan fastställas från denna databas är följande:

100 % av seten med alfa innehåller också beta
50% av seten med alfa, beta har också epsilon
50% av seten med alfa, beta har också theta

vi kan också illustrera detta genom en mängd olika exempel.

Exempel 2

Antag att en stor stormarknad spårar försäljningsdata efter lagerhållningsenhet (SKU) för varje artikel: varje artikel, som "smör" eller "bröd", identifieras med en numerisk SKU. Stormarknaden har en databas med transaktioner där varje transaktion är en uppsättning SKU:er som köptes tillsammans.

Låt databasen med transaktioner bestå av följande postuppsättningar:

Artikeluppsättningar
{1,2,3,4}
{1,2,4}
{1,2}
{2,3,4
} {2,3}
{3,4}
{2,4}

Vi kommer att använda Apriori för att fastställa de vanliga objektuppsättningarna i denna databas. För att göra detta kommer vi att säga att en artikeluppsättning är frekvent om den förekommer i minst 3 transaktioner i databasen: värdet 3 är stödtröskeln .

Det första steget i Apriori är att räkna upp antalet händelser, som kallas stöd, för varje medlemsobjekt separat. Genom att skanna databasen för första gången får vi följande resultat

Artikel	Stöd
{1}	3
{2}	6
{3}	4
{4}	5

Alla artiklar i storlek 1 har ett stöd på minst 3, så de är alla frekventa.

Nästa steg är att skapa en lista över alla par av de vanliga föremålen.

Till exempel, angående paret {1,2}: den första tabellen i exempel 2 visar objekt 1 och 2 som visas tillsammans i tre av objektuppsättningarna; därför säger vi att artikeln {1,2} har stöd för tre.

Artikel	Stöd
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

Paren {1,2}, {2,3}, {2,4} och {3,4} uppfyller alla eller överskrider minimistödet på 3, så de är frekventa. Det är inte paren {1,3} och {1,4}. Nu, eftersom {1,3} och {1,4} inte är frekventa, kan en större uppsättning som innehåller {1,3} eller {1,4} inte vara frekvent. På detta sätt kan vi beskära set: vi kommer nu att leta efter frekventa trippel i databasen, men vi kan redan exkludera alla trippel som innehåller ett av dessa två par:

Artikel	Stöd
{2,3,4}	2

i exemplet finns det inga frekventa trillingar. {2,3,4} är under det minimala tröskelvärdet, och de andra trillingarna exkluderades eftersom de var superuppsättningar av par som redan låg under tröskeln.

Vi har alltså bestämt de frekventa uppsättningarna av objekt i databasen och illustrerat hur vissa objekt inte räknades eftersom en av deras delmängder redan var känd för att vara under tröskeln.

Begränsningar

Apriori, även om det är historiskt betydelsefullt, lider av ett antal ineffektiviteter eller avvägningar, som har gett upphov till andra algoritmer. Generering av kandidat genererar ett stort antal delmängder (Algorithmen försöker ladda upp kandidatuppsättningen, med så många delmängder som möjligt före varje genomsökning av databasen). Bottom-up delmängdsutforskning (i huvudsak en bredd-första genomgång av delmängdsgittret) hittar någon maximal delmängd S bara trots allt $2^{|S|}-1$ av dess korrekta delmängder.

Algoritmen skannar databasen för många gånger, vilket minskar den totala prestandan. På grund av detta antar algoritmen att databasen finns permanent i minnet.

Dessutom är både tids- och rymdkomplexiteten för denna algoritm mycket hög: ${\displaystyle O\left(2^{|D|}\right)} ,$ alltså exponentiell, där $|D|$ är den horisontella bredden (det totala antalet objekt) som finns i databasen.

Senare algoritmer som Max-Miner försöker identifiera de maximalt frekventa objektuppsättningarna utan att räkna upp deras delmängder, och utför "hopp" i sökutrymmet snarare än en rent nedifrån-och-upp-strategi.

externa länkar

ARtool , GPL Java association rule mining-applikation med GUI, som erbjuder implementeringar av flera algoritmer för upptäckt av frekventa mönster och extrahering av associationsregler (inkluderar Apriori)
SPMF erbjuder Java-implementationer med öppen källkod av Apriori och flera varianter som AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID och andra mer effektiva algoritmer som FPGrowth och LCM.
Christian Borgelt tillhandahåller C-implementationer för Apriori och många andra frekventa mönsterutvinningsalgoritmer (Eclat, FPGrowth, etc.). Koden distribueras som fri programvara under MIT-licensen .
R - paketets arules innehåller Apriori och Eclat och infrastruktur för att representera, manipulera och analysera transaktionsdata och mönster.
Efficient-Apriori är ett Python-paket med en implementering av algoritmen som presenteras i originalartikeln.