Algorisme de creixement de patrons freqüents (FP) a la mineria de dades

frequent pattern growth algorithm data mining

Tutorial detallat sobre l'algorisme de creixement de patrons freqüents que representa la base de dades a l'arbre FP. Inclou la comparació de FP Growth contra Apriori:

Algorisme Apriori es va explicar amb detall al nostre tutorial anterior. En aquest tutorial, aprendrem sobre el creixement de patrons freqüents: el creixement FP és un mètode per extraure conjunts d’elements freqüents.

on puc trobar la clau de seguretat de la xarxa al meu router

Com tots sabem, Apriori és un algorisme per a la mineria de patrons freqüents que se centra a generar conjunts d’elements i descobrir el conjunt d’elements més freqüents. Redueix considerablement la mida del conjunt d’elements de la base de dades, però, Apriori també té les seves pròpies deficiències.

Llegiu el nostre document Sèrie de formació completa sobre mineria de dades per a un coneixement complet del concepte.

Què aprendreu:

• Mancances de l'algorisme Apriori
• Algorisme de creixement de patrons freqüents
• Arbre FP
• Passos d'algorisme de patrons freqüents
• Exemple d'algorisme de creixement FP
• Avantatges de l'algorisme de creixement FP
• Desavantatges de l'algorisme de creixement FP
• FP Growth vs Apriori
• ECLAT
• Conclusió
• Lectura recomanada

Mancances de l'algorisme Apriori

1. L’ús d’Apriori necessita una generació de conjunts d’elements candidats. Aquests conjunts d’elements poden ser nombrosos si el conjunt d’elements de la base de dades és enorme.
2. Apriori necessita diverses exploracions de la base de dades per comprovar el suport de cada conjunt d’elements generats i això comporta costos elevats.

Aquestes deficiències es poden superar mitjançant l’algorisme de creixement FP.

Algorisme de creixement de patrons freqüents

Aquest algorisme és una millora del mètode Apriori. Es genera un patró freqüent sense necessitat de generar candidats. L’algorisme de creixement FP representa la base de dades en forma d’arbre anomenat arbre de patrons freqüents o arbre FP.

Aquesta estructura d’arbre mantindrà l’associació entre els conjunts d’elements. La base de dades es fragmenta mitjançant un element freqüent. Aquesta part fragmentada s'anomena 'fragment de patró'. S’analitzen els conjunts d’aquests patrons fragmentats. Així, amb aquest mètode, la cerca de conjunts d’elements freqüents es redueix comparativament.

Arbre FP

L'arbre de patrons freqüents és una estructura semblant a l'arbre que es fa amb els conjunts inicials d'elements de la base de dades. L’objectiu de l’arbre FP és aprofitar el patró més freqüent. Cada node de l'arbre FP representa un element del conjunt d'elements.

El node arrel representa nul mentre que els nodes inferiors representen els conjunts d’elements. Es manté l’associació dels nodes amb els nodes inferiors que són els conjunts d’elements amb els altres conjunts d’elements mentre es forma l’arbre.

Passos d'algorisme de patrons freqüents

El mètode de creixement de patrons freqüents ens permet trobar el patró freqüent sense generació de candidats.

Vegem els passos seguits per obtenir el patró freqüent mitjançant un algorisme de creixement de patrons freqüents:

# 1) El primer pas és escanejar la base de dades per trobar les ocurrències dels conjunts d’elements a la base de dades. Aquest pas és el mateix que el primer pas d'Apriori. El recompte de conjunts d’elements 1 a la base de dades s’anomena recompte de suport o freqüència de conjunts d’elements 1.

# 2) El segon pas és construir l’arbre FP. Per a això, creeu l'arrel de l'arbre. L’arrel es representa per nul·la.

# 3) El següent pas és tornar a escanejar la base de dades i examinar les transaccions. Examineu la primera transacció i esbrineu-ne el conjunt. El conjunt d’elements amb el recompte màxim es pren a la part superior, el següent conjunt d’elements amb un recompte inferior, etc. Vol dir que la branca de l'arbre es construeix amb conjunts d'elements de transacció en ordre descendent de recompte.

# 4) S'examina la següent transacció a la base de dades. Els conjunts s’ordenen en ordre descendent de recompte. Si algun element d'aquesta transacció ja està present en una altra branca (per exemple, a la primera transacció), aquesta branca de transacció compartiria un prefix comú a l'arrel.

Això significa que el conjunt d'elements comuns està enllaçat amb el nou node d'un altre conjunt d'elements en aquesta transacció.

# 5) A més, el recompte del conjunt d’elements s’incrementa a mesura que es produeix a les transaccions. Tant el recompte de nodes comuns com el nou s'incrementen en 1 a mesura que es creen i s'enllacen segons les transaccions.

# 6) El següent pas és extreure l'arbre FP creat. Per a això, primer s’examina el node més baix juntament amb els enllaços dels nodes més baixos. El node més baix representa la longitud del patró de freqüència 1. A partir d’aquí, recorre el camí de l’arbre FP. Aquest camí o camins s’anomenen una base de patró condicional.

La base de patrons condicionals és una sub-base de dades que consisteix en camins de prefix a l'arbre FP que tenen el node més baix (sufix).

# 7) Construeix un arbre FP condicional, format per un recompte de conjunts d’elements al camí. Els conjunts d’elements que compleixen el suport llindar es consideren a l’arbre FP condicional.

# 8) Els patrons freqüents es generen a partir de l'arbre FP condicional.

Exemple d'algorisme de creixement FP

Llindar de suport = 50%, confiança = 60%

Taula 1

Solució:

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

1. Recompte de cada element

millor descarregador de música mp3 per a Android

Taula 2

2. Ordeneu el conjunt d’elements en ordre descendent.

Taula 3

3. Construeix l'arbre FP

1. Tenint en compte el node arrel nul.
2. El primer escaneig de Transaction T1: I1, I2, I3 conté tres elements {I1: 1}, {I2: 1}, {I3: 1}, on I2 està vinculat com a fill a root, I1 està vinculat a I2 i I3 està vinculat a I1.
3. T2: I2, I3, I4 conté I2, I3 i I4, on I2 està vinculat a l'arrel, I3 està vinculat a I2 i I4 està vinculat a I3. Però aquesta branca compartiria el node I2 tan comú com ja s’utilitza a T1.
4. Incrementeu el recompte d’I2 per 1 i I3 està vinculat com a fill a I2, I4 està vinculat com a fill a I3. El recompte és {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. De la mateixa manera, una nova branca amb I5 està vinculada a I4 quan es crea un fill.
6. T4: I1, I2, I4. La seqüència serà I2, I1 i I4. I2 ja està enllaçat amb el node arrel, de manera que s'incrementarà en 1. De la mateixa manera, I1 s'incrementarà en 1, ja que ja està vinculat amb I2 a T1, per tant {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. La seqüència serà I2, I1, I3 i I5. Per tant, {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. La seqüència serà I2, I1, I3 i I4. Per tant, {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. La mineria de l'arbre FP es resumeix a continuació:

1. No es considera l’element de node I5 més baix ja que no té un recompte de suport mínim, per tant es suprimeix.
2. El següent node inferior és I4. I4 apareix en 2 branques, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Per tant, considerant I4 com a sufix, els camins dels prefixos seran {I2, I1, I3: 1}, {I2, I3: 1}. Això forma la base del patró condicional.
3. La base de patrons condicionals es considera una base de dades de transaccions, es construeix un arbre FP. Això contindrà {I2: 2, I3: 2}, I1 no es considera ja que no compleix el recompte de suport mínim.
4. Aquest camí generarà totes les combinacions de patrons freqüents: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Per a I3, el camí del prefix seria: {I2, I1: 3}, {I2: 1}, això generarà un arbre FP de 2 nodes: {I2: 4, I1: 3} i es generen patrons freqüents: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Per a I1, el camí del prefix seria: {I2: 4} generarà un sol node FP-tree: {I2: 4} i es generaran patrons freqüents: {I2, I1: 4}.

El diagrama que es mostra a continuació representa l’arbre FP condicional associat al node condicional I3.

Avantatges de l'algorisme de creixement FP

1. Aquest algorisme només ha d’escanejar la base de dades dues vegades en comparació amb Apriori, que analitza les transaccions de cada iteració.
2. L’aparellament d’elements no es fa en aquest algorisme i això fa que sigui més ràpid.
3. La base de dades s’emmagatzema en una versió compacta a la memòria.
4. És eficient i escalable per a la mineria de patrons freqüents tant llargs com curts.

Desavantatges de l'algorisme de creixement FP

1. FP Tree és més feixuc i difícil de construir que Apriori.
2. Pot ser car.
3. Quan la base de dades és gran, és possible que l'algorisme no encaixi a la memòria compartida.

FP Growth vs Apriori

ECLAT

El mètode anterior, Apriori i FP de creixement, extreu conjunts d’elements freqüents mitjançant format de dades horitzontals. ECLAT és un mètode per extraure conjunts d’elements freqüents mitjançant el format de dades verticals. Transformarà les dades en format de dades horitzontals en format vertical.

Per exemple,Ús del creixement Apriori i FP:

L'ECLAT tindrà el format de la taula com:

Aquest mètode formarà 2 conjunts d’elements, 3 conjunts d’elements, k conjunts d’elements en format de dades verticals. Aquest procés amb k s’incrementa en 1 fins que no es troben conjunts d’elements candidats. Algunes tècniques d’optimitzacions com diffset s’utilitzen juntament amb Apriori.

Aquest mètode té un avantatge sobre Apriori, ja que no requereix escanejar la base de dades per trobar el suport de k + 1 elementsets. Això es deu al fet que el conjunt de transaccions comportarà el recompte d'ocurrència de cada element de la transacció (suport). El coll d'ampolla es produeix quan hi ha moltes transaccions que requereixen una gran memòria i un temps de càlcul per tallar els conjunts.

Conclusió

L’algorisme Apriori s’utilitza per a les regles d’associació minera. Funciona sobre el principi, “els subconjunts no buits dels conjunts d’elements freqüents també han de ser freqüents”. Forma candidats de k-itemset a partir de (k-1) conjunts d’elements i escaneja la base de dades per trobar els conjunts d’elements freqüents.

L’algorisme de creixement de patrons freqüents és el mètode per trobar patrons freqüents sense generació de candidats. Construeix un arbre FP en lloc d’utilitzar l’estratègia de generació i prova d’Apriori. El focus de l’algorisme FP Growth es basa en fragmentar els camins dels ítems i explotar patrons freqüents.

Esperem que aquests tutorials de la sèrie Data Mining enriqueixin el vostre coneixement sobre Data Mining.

PREV Tutorial | PRIMER Tutorial

preguntes i respostes d’entrevistes de disseny de bases de dades

Lectura recomanada

• Tècniques de mineria de dades: algorisme, mètodes i eines principals de mineria de dades
• Algorisme Apriori en mineria de dades: implementació amb exemples
• Exemples d'algorisme de l'arbre de decisions en mineria de dades
• Exemples de mineria de dades: aplicacions més habituals de mineria de dades 2021
• Mineria de dades: processos, tècniques i grans qüestions en l'anàlisi de dades
• Procés de mineria de dades: models, passos de procés i reptes implicats
• Patró de pregunta de l'examen de certificació de proves de programari CSTE
• Mineria de dades contra aprenentatge automàtic contra intel·ligència artificial contra aprenentatge profund