Menú

Algorisme Apriori en mineria de dades: implementació amb exemples

  • Principal
  • Altres
  • Algorisme Apriori en mineria de dades: implementació amb exemples

apriori algorithm data mining

Proveu El Nostre Instrument Per Eliminar Problemes

Tutorial en profunditat sobre l'algorisme Apriori per esbrinar conjunts d'elements freqüents a la mineria de dades. Aquest tutorial explica els passos d'Apriori i com funciona:

En aquest Sèrie de tutorials sobre mineria de dades , vam fer una ullada al Algorisme de l'arbre de decisions al nostre tutorial anterior.

Hi ha diversos mètodes per a l'explotació de dades, com ara l'associació, la correlació, la classificació i l'agrupació.

tutorial de microsoft Dynamics ax per a principiants

Aquest tutorial se centra principalment en la mineria mitjançant regles d'associació. Per regles d’associació, identifiquem el conjunt d’elements o atributs que es produeixen junts en una taula.

Algorisme Apriori

Què aprendreu:

Què és un conjunt d'articles?

Un conjunt d’elements junts s’anomena conjunt d’elements. Si algun element té k-items, s’anomena k-itemset. Un conjunt d’elements consta de dos o més elements. Un conjunt d’elements que es produeix amb freqüència s’anomena conjunt d’elements freqüents. Per tant, la mineria de conjunts d’elements freqüents és una tècnica de mineria de dades per identificar els elements que sovint es produeixen junts.

Per exemple , Pa i mantega, programari per a portàtils i antivirus, etc.

Què és un conjunt d’articles freqüents?

Un conjunt d’elements s’anomena freqüent si compleix un valor llindar mínim de suport i confiança. El suport mostra les transaccions amb articles comprats conjuntament en una única transacció. La confiança mostra les transaccions on els articles es compren un darrere l’altre.

Per al mètode de mineria d’elements freqüents, considerem només aquelles transaccions que compleixin els requisits mínims de suport i confiança del llindar. Les estadístiques d’aquests algoritmes de mineria ofereixen molts avantatges, una reducció de costos i un avantatge competitiu millorat.

Hi ha un temps de compensació per a les dades de mines i el volum de dades per a mines freqüents. L’algoritme de mineria freqüent és un algorisme eficient per extraure els patrons ocults dels conjunts d’elements en poc temps i amb menys consum de memòria.

Mineria de patrons freqüents (FPM)

L’algorisme freqüent de mineria de patrons és una de les tècniques més importants de mineria de dades per descobrir relacions entre diferents elements d’un conjunt de dades. Aquestes relacions es representen en forma de regles d’associació. Ajuda a trobar les irregularitats en les dades.

FPM té moltes aplicacions en el camp de l’anàlisi de dades, errors de programari, màrqueting creuat, anàlisi de campanyes de venda, anàlisi de cistelles de mercat, etc.

Els conjunts d’elements freqüents descoberts a través d’Apriori tenen moltes aplicacions en tasques de mineria de dades. Tasques com ara trobar patrons interessants a la base de dades, esbrinar la seqüència i la mineria de les regles d'associació són les més importants.

Les regles d’associació s’apliquen a les dades de transaccions dels supermercats, és a dir, per examinar el comportament dels clients en funció dels productes comprats. Les normes d'associació descriuen la freqüència amb què es compren els articles junts.

Normes d'associació

La mineria de regles d'associació es defineix com:

'Sigui I = {...} un conjunt d'atributs binaris' n 'anomenats ítems. Posem D = {….} A la transacció anomenada base de dades. Cada transacció a D té un identificador de transacció únic i conté un subconjunt dels elements de I. Una regla es defineix com una implicació del formulari X-> Y on X, Y? Jo i X? Y = ?. El conjunt d’ítems X i Y s’anomenen antecedents i conseqüents de la regla respectivament. ”

L'aprenentatge de les regles d'associació s'utilitza per trobar relacions entre atributs en grans bases de dades. Una regla d'associació, A => B, serà de la forma 'per a un conjunt de transaccions, un cert valor del conjunt d'elements A determina els valors del conjunt d'elements B sota la condició en què es compleixin el mínim suport i confiança'.

El suport i la confiança es poden representar amb el següent exemple:

Bread=> butter (support=2%, confidence-60%)

L'afirmació anterior és un exemple d'una regla d'associació. Això significa que hi ha una transacció del 2% que va comprar pa i mantega junts i que hi ha un 60% de clients que van comprar pa i mantega.

El suport i la confiança per als elements A i B es representen mitjançant fórmules:

Fórmula de suport i confiança per als articles A i B

La mineria de regles d'associació consta de 2 passos:

  1. Cerqueu tots els conjunts d’elements freqüents.
  2. Genereu regles d'associació a partir dels conjunts d'elements freqüents anteriors.

Per què la mineria d’articles freqüents?

La mineria d’elements o patrons freqüents s’utilitza àmpliament a causa de les seves àmplies aplicacions a les regles d’associació minera, les correlacions i la restricció de patrons de gràfics que es basa en patrons freqüents, patrons seqüencials i moltes altres tasques de mineria de dades.

Algorisme Apriori - Algoritmes de patrons freqüents

L’algorisme Apriori va ser el primer algorisme proposat per a la mineria freqüent d’elements. Més tard va ser millorat per R Agarwal i R Srikant i es va conèixer com Apriori. Aquest algorisme utilitza dos passos 'unir' i 'podar' per reduir l'espai de cerca. És un enfocament iteratiu per descobrir els conjunts d’elements més freqüents.

Apriori diu:

La probabilitat que l’ítem I no sigui freqüent és si:

  • PI)
  • P (I + A)
  • Si un conjunt d'elements té un valor inferior al suport mínim, tots els seus superconjunts també cauran per sota del suport mínim i, per tant, es poden ignorar. Aquesta propietat s’anomena propietat Antimonotona.

Els passos seguits a l'algorisme Apriori de mineria de dades són:

  1. Uneix-te a Step : Aquest pas genera (K + 1) conjunt d’elements a partir de conjunts d’elements K unint cada element amb ell mateix.
  2. Pas de poda : Aquest pas analitza el recompte de cada element a la base de dades. Si l’element candidat no compleix el suport mínim, es considera poc freqüent i, per tant, s’elimina. Aquest pas es realitza per reduir la mida dels conjunts d’elements candidats.

Passos a Apriori

L’algorisme Apriori és una seqüència de passos que cal seguir per trobar el conjunt d’elements més freqüents a la base de dades donada. Aquesta tècnica de mineria de dades segueix la unió i els passos de poda de manera iterativa fins a aconseguir el conjunt d’elements més freqüents. El problema proporciona un llindar mínim de suport o l’assumeix l’usuari.

# 1) A la primera iteració de l'algorisme, cada ítem es pren com a candidat a 1 ítem. L’algorisme comptarà les ocurrències de cada element.

# 2) Deixeu que hi hagi un mínim de suport, min_sup (per exemple, 2). Es determina el conjunt de conjunts d'elements 1 l'ocurrència dels quals compleix el mínim sup. Només els candidats que compten amb més o menys de min_sup, es prenen per endavant per a la següent iteració i es poden els altres.

# 3) A continuació, es descobreixen elements freqüents de 2 elements amb min_sup. Per a això, al pas d'unió, el conjunt de 2 ítems es genera formant un grup de 2 combinant ítems amb ell mateix.

# 4) Els candidats de 2 ítems es poden mitjançant el valor del llindar mínim. Ara la taula tindrà 2 conjunts d'elements només amb min-sup.

# 5) La següent iteració formarà 3 conjunts d'elements mitjançant unió i pas de poda. Aquesta iteració seguirà la propietat antimonotònica on els subconjunts de conjunts de 3 elements, és a dir, els subconjunts de 2 grups de cada grup cauen en min_sup. Si tots els subconjunts de dos elements són freqüents, el superconjunt serà freqüent en cas contrari, es poda.

# 6) El següent pas seguirà fent 4-itemset unint 3-itemset amb ell mateix i podant si el seu subconjunt no compleix els criteris min_sup. L'algoritme s'atura quan s'aconsegueix el conjunt d'elements més freqüents.

Passos Apriori

(imatge font )

Exemple d'Apriori:Llindar de suport = 50%, confiança = 60%

TAULA-1

TransaccióLlista d’elements
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T 6I1, I2, I3, I4

Solució:

Llindar de suport = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Recompte de cada element

TAULA-2

ArticleCompta
I14
I25
I34
I44
I52

2. Pas de poda: TAULA -2 mostra que l'element I5 no compleix min_sup = 3, de manera que s'elimina, només I1, I2, I3, I4 compleixen el recompte min_sup.

TAULA-3

ArticleCompta
I14
I25
I34
I44

3. Uneix-te al pas: Formulari 2 elements. Des de TAULA-1 esbrineu les ocurrències de 2-itemset.

TAULA-4

ArticleCompta
I1, I24
I1, I33
I1, I42
I2, I34
I2, I43
I3, I42

4. Pas de poda: TAULA -4 mostra que el conjunt d'elements {I1, I4} i {I3, I4} no compleix min_sup, de manera que se suprimeix.

TAULA-5

ArticleCompta
I1, I24
I1, I33
I2, I34
I2, I43

5. Uniu-vos i podeu el pas: Formulari de 3 elements. Des del TAULA- 1 esbrineu les ocurrències de 3 elements. Des de TAULA-5 , esbrineu els subconjunts de 2 elements que admeten min_sup.

Podem veure els conjunts d’elements {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} que es produeixen a TAULA-5 per tant, {I1, I2, I3} és freqüent.

Podem veure els conjunts d’elements {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} que no són freqüents, ja que no es produeixen a TAULA-5 per tant, {I1, I2, I4} no és freqüent i, per tant, se suprimeix.

TAULA-6

Article
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Només és freqüent {I1, I2, I3} .

6. Generar regles d'associació: Entre els elements freqüents que es descobreixen a sobre de l'associació podríem:

{I1, I2} => {I3}

Confiança = suport {I1, I2, I3} / suport {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Confiança = suport {I1, I2, I3} / suport {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Confiança = suport {I1, I2, I3} / suport {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Confiança = suport {I1, I2, I3} / suport {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Confiança = suport {I1, I2, I3} / suport {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Confiança = suport {I1, I2, I3} / suport {I3} = (3/4) * 100 = 75%

Això demostra que totes les regles d'associació anteriors són sòlides si el llindar mínim de confiança és del 60%.

L’algorisme Apriori: pseudocodi

C: conjunt d’elements candidats de mida k

L: Conjunt d’elements freqüents de mida k

Psudocode

què fer amb un fitxer bin

(imatge font )

Avantatges

  1. Algorisme fàcil d'entendre
  2. Els passos d'ajuntament i de poda són fàcils d'implementar en conjunts d'elements grans de bases de dades grans

Desavantatges

  1. Requereix un càlcul elevat si els conjunts d’elements són molt grans i el suport mínim es manté molt baix.
  2. Cal escanejar tota la base de dades.

Mètodes per millorar l'eficiència de Apriori

Hi ha molts mètodes disponibles per millorar l'eficiència de l'algorisme.

  1. Tècnica basada en hash: Aquest mètode utilitza una estructura basada en hash anomenada taula hash per generar els k-itemsets i el seu recompte corresponent. Utilitza una funció hash per generar la taula.
  2. Reducció de transaccions: Aquest mètode redueix el nombre d’exploracions de transaccions en iteracions. Es marquen o s'eliminen les transaccions que no contenen articles freqüents.
  3. Particionament: Aquest mètode només requereix dues exploracions de bases de dades per extraure els conjunts d’elements freqüents. Es diu que perquè qualsevol conjunt d’elements sigui potencialment freqüent a la base de dades, hauria de ser freqüent en almenys una de les particions de la base de dades.
  4. Mostreig: Aquest mètode selecciona una mostra aleatòria S de la base de dades D i, a continuació, busca un conjunt d’elements freqüents a S. Pot ser possible perdre un conjunt d’elements freqüents a nivell global. Això es pot reduir baixant el min_sup.
  5. Recompte de jocs dinàmics: Aquesta tècnica pot afegir nous conjunts d’elements candidats a qualsevol punt d’inici marcat de la base de dades durant l’escaneig de la base de dades.

Aplicacions de l'algorisme Apriori

Alguns camps on s'utilitza Apriori:

  1. En l'àmbit educatiu: Extracció de normes d'associació en l'explotació de dades d'estudiants admesos mitjançant característiques i especialitats.
  2. En l’àmbit mèdic: Per exemple, l’anàlisi de la base de dades del pacient.
  3. En silvicultura: Anàlisi de la probabilitat i intensitat dels incendis forestals amb les dades dels incendis forestals.
  4. Apriori és utilitzat per moltes empreses com Amazon a la Sistema de recomanacions i per Google per a la funció de completament automàtic.

Conclusió

L’algorisme Apriori és un algorisme eficient que analitza la base de dades només una vegada.

Redueix considerablement la mida dels conjunts d’elements de la base de dades, proporcionant un bon rendiment. Així, la mineria de dades ajuda els consumidors i les indústries a millorar el procés de presa de decisions.

Consulteu el nostre proper tutorial per obtenir més informació sobre l'algorisme de creixement de patrons freqüents.

PREV Tutorial | NEXT Tutorial

Lectura recomanada

^