miniatura|373x373px|Aquesta imatge representa els passos de l'algoritme a priori. AprioriRakesh Agrawal and Ramakrishnan Srikant.Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994. és un algorisme per a la mineria de conjunts d'elements freqüents i l'aprenentatge de regles d'associació sobre bases de dades relacionals. Procedeix identificant els elements individuals freqüents de la base de dades i estenent-los a conjunts d'elements cada cop més grans, sempre que aquests conjunts d'elements apareguin prou sovint a la base de dades. Els conjunts d'elements freqüents determinats per Apriori es poden utilitzar per determinar regles d'associació que destaquen les tendències generals de la base de dades: això té aplicacions en dominis com l'anàlisi de la cistella de la compra.
Visió general L'algorisme Apriori va ser proposat per Agrawal i Srikant el 1994. Apriori està dissenyat per operar en bases de dades que contenen transaccions (per exemple, col·leccions d'articles comprats per clients o detalls de la freqüentació d'un lloc web o adreces IP Published by deductive.com, September 6, 2018, retrieved September 7, 2018). Altres algorismes estan dissenyats per trobar regles d'associació en dades que no tenen transaccions (Winepi i Minepi) o que no tenen marques de temps (seqüenciació d'ADN). Cada transacció es veu com un conjunt d'elements (un conjunt d'elements ). Donat un llindar , l'algorisme Apriori identifica els conjunts d'elements que són subconjunts d'almenys transaccions a la base de dades.
Apriori utilitza un enfocament "de baix a dalt", on els subconjunts freqüents s'amplien un element a la vegada (un pas conegut com a generació de candidats) i els grups de candidats es proven amb les dades. L'algorisme finalitza quan no es troben més extensions reeixides.
Apriori utilitza la cerca per amplitud i una estructura d'arbre hash per comptar conjunts d'elements candidats de manera eficient. Genera conjunts d'elements candidats de longitud de conjunts d'elements de longitud . A continuació, poda els candidats que tenen un subpatró poc freqüent. Segons el lema de tancament descendent, el conjunt de candidats conté tots els freqüents conjunts d'elements de longitud. Després d'això, escaneja la base de dades de transaccions per determinar els conjunts d'elements freqüents entre els candidats.
A continuació es mostra el pseudocodi de l'algorisme per a una base de dades de transaccions , i un llindar de suport de . S'utilitza la notació teòrica de conjunts habitual, tot i que cal tenir en compte que és un multiset. és el conjunt candidat per al nivelll . A cada pas, se suposa que l'algorisme genera els conjunts candidats a partir dels conjunts d'elements grans del nivell precedent, seguint el lema de tancament descendent. accedeix a un camp de l'estructura de dades que representa el conjunt candidat , que inicialment se suposa que és zero. A continuació s'ometen molts detalls, normalment la part més important de la implementació és l'estructura de dades utilitzada per emmagatzemar els conjunts candidats i comptar les seves freqüències.
Apriori(T, ε)
L1 ← {large singleton itemsets}
k ← 2
while Lk−1 is not empty
Ck ← Generate_candidates(Lk−1, k)
for transactions t in T
Dt ← {c in Ck : c ⊆ t}
for candidates c in Dt
count[c] ← count[c] + 1
Lk ← {c in Ck : count[c] ≥ ε}
k ← k + 1
return Union(Lk) over all k
Generate_candidates(L, k)
result ← empty_set()
for all p ∈ L, q ∈ L
where p and q differ in exactly one element
c ← p ∪ q
if u ∈ L for all u ⊆ c where |u| = k-1
result.add(c) return result
Exemples Exemple 1 Considereu la següent base de dades, on cada fila és una transacció i cada cel·la és un element individual de la transacció: αβεαβθαβεαβθ Les regles d'associació que es poden determinar a partir d'aquesta base de dades són les següents:
El 100% dels conjunts amb α també contenen β El 50% dels conjunts amb α i β també tenen ε El 50% dels conjunts amb α i β també tenen θ
també podem il·lustrar això mitjançant diversos exemples.
Exemple 2 Suposem que un gran supermercat fa un seguiment de les dades de vendes per unitat d'estoc (SKU) per a cada article: cada article, com ara "mantega" o "pa", s'identifica amb una SKU numèrica. El supermercat té una base de dades de transaccions on cada transacció és un conjunt de SKU que es van comprar juntes.
Sigui la base de dades de transaccions consti dels següents conjunts d'elements: Conjunts d'elements{1, 2, 3, 4}{1,2,4}{1,2}{2,3,4}{2,3}{3,4}{2,4} Utilitzarem Apriori per determinar els conjunts d'elements freqüents d'aquesta base de dades. Per fer-ho, direm que un conjunt d'elements és freqüent si apareix en almenys 3 transaccions de la base de dades: el valor 3 és el llindar de suport.
El primer pas d'Apriori és comptar el nombre d'ocurrències, anomenat suport, de cada element membre per separat. En escanejar la base de dades per primera vegada, obtenim el següent resultat ÍtemSuport{1}3{2}6{3}4{4}5 Tots els conjunts d'elements de mida 1 tenen un suport d'almenys 3, per la qual cosa tots són freqüents.
El següent pas és generar una llista de tots els parells d'elements freqüents.
Per exemple, pel que fa al parell {1,2}: la primera taula de l'exemple 2 mostra els elements 1 i 2 que apareixen junts en tres dels conjunts d'elements; per tant, diem que l'element {1,2} en suporta tres. ÍtemSuport{1,2}3{1,3}1{1,4}2{2,3}3{2,4}4{3,4}3 Els parells {1,2}, {2,3}, {2,4} i {3,4} compleixen o superen el suport mínim de 3, de manera que són freqüents. Els parells {1,3} i {1,4} no ho són. Ara, com que {1,3} i {1,4} no són freqüents, qualsevol conjunt més gran que contingui {1,3} o {1,4} no pot ser freqüent. D'aquesta manera, podem podar conjunts: ara buscarem triplets freqüents a la base de dades, però ja podem excloure tots els triplets que contenen un d'aquests dos parells: ÍtemSuport{2,3,4}2 A l'exemple, no hi ha triplets freqüents. {2,3,4} està per sota del llindar mínim, i els altres triplets es van excloure perquè eren superconjunts de parells que ja estaven per sota del llindar.
Així doncs, hem determinat els conjunts freqüents d'elements de la base de dades i hem il·lustrat com alguns elements no es van comptar perquè ja se sabia que un dels seus subconjunts estava per sota del llindar.
Limitacions Apriori, tot i ser històricament significatiu, pateix diverses ineficiències o compromisos, que han generat altres algorismes. La generació de candidats genera un gran nombre de subconjunts (l'algorisme intenta carregar el conjunt candidat amb tants subconjunts com sigui possible abans de cada escaneig de la base de dades). L'exploració de subconjunts de baix a dalt (essencialment un recorregut d'amplitud primer per la xarxa de subconjunts) troba qualsevol subconjunt màxim S només després de tots dels seus subconjunts propis.
L'algorisme escaneja la base de dades massa vegades, cosa que redueix el rendiment general. A causa d'això, l'algorisme assumeix que la base de dades està permanentment a la memòria.
A més, la complexitat temporal i espacial d'aquest algorisme és molt alta: , per tant exponencial, on és l'amplada horitzontal (el nombre total d'elements) presents a la base de dades.
Referències
Categoria:Algorismes Categoria:Bases de dades