Aprenentatge de regles d'associació

Un diagrama de Venn per mostrar les associacions entre els conjunts d'ítems X i Y d'un conjunt de dades. Totes les transaccions que contenen l'element X es troben a la part esquerra blanca del cercle, mentre que les que contenen Y es troben de color vermell i a la dreta. Totes les transaccions que continguin X i Y es troben al mig i estan de color rosa. Es poden utilitzar diversos conceptes per representar la informació d'aquest gràfic. Per exemple, si hom pren totes les transaccions de la secció rosa i les divideix per la quantitat total de transaccions (transaccions que contenen X (blanc) + transaccions que contenen Y (vermell), la sortida es coneixeria com a suport. Una instància d'obtenir el resultat d'un mètode conegut com a confiança, es pot prendre totes les transaccions del mig (rosa) i dividir-les per totes les transaccions que contenen Y (vermell i rosa). En aquest cas, Y és l'antecedent i X el conseqüent.

L'aprenentatge de regles d'associació és un mètode d'aprenentatge automàtic basat en regles per descobrir relacions interessants entre variables en grans bases de dades. Es pretén identificar regles fortes descobertes en bases de dades utilitzant algunes mesures d'interès. En qualsevol transacció determinada amb una varietat d'elements, les regles d'associació estan destinades a descobrir les regles que determinen com o per què es connecten determinats elements.

Basant-se en el concepte de regles fortes, Rakesh Agrawal, Tomasz Imieliński i Arun Swami van introduir regles d'associació per descobrir regularitats entre productes en dades de transaccions a gran escala registrades per sistemes de punts de venda (POS) als supermercats. Per exemple, la regla $\{\mathrm {cebes,patates} \}\Rightarrow \{\mathrm {botifarra} \}$ trobat a les dades de vendes d'un supermercat indicaria que si un client compra ceba i patates junts, és probable que també compri botifarres. Aquesta informació es pot utilitzar com a base per prendre decisions sobre activitats de màrqueting com, per exemple, preus promocionals o ubicacions de productes.

A més de l'exemple anterior de l'anàlisi de cistella de mercat, les regles d'associació s'utilitzen avui en dia en moltes àrees d'aplicació, com ara la mineria d'ús web, la detecció d'intrusions, la producció contínua i la bioinformàtica. En contrast amb la mineria de seqüències, l'aprenentatge de regles d'associació normalment no té en compte l'ordre dels elements ni dins d'una transacció ni entre transaccions.

El propi algorisme de regles d'associació consta de diversos paràmetres que poden dificultar l'execució per a aquells que no tenen experiència en mineria de dades, amb moltes regles difícils d'entendre.

Definició

Seguint la definició original d'Agrawal, Imieliński, Swami el problema de la mineria de regles d'associació es defineix com:

SIgui $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ un conjunt de $n$ atributs binaris anomenats elements.

Sigui $D=\{t_{1},t_{2},\ldots ,t_{m}\}$un conjunt de transaccions anomenat base de dades .

Cada transacció en $D$ té un identificador de transacció únic i conté un subconjunt d'elements $I$ .

Una regla es defineix com una implicació de la forma:

$X\Rightarrow Y$, on $X,Y\subseteq I$ .

A Agrawal, Imieliński, Swami només es defineix una regla entre un conjunt i un únic element, $X\Rightarrow i_{j}$ per $i_{j}\in I$

Cada regla està composta per dos conjunts diferents d'elements, també coneguts com a conjunts d'elements, $X$ i $Y$, on $X$ s'anomena antecedent o costat esquerre (LHS) i $Y$ consegüent o a mà dreta (RHS). L'antecedent és aquell element que es pot trobar a les dades mentre que el conseqüent és l'element trobat quan es combina amb l'antecedent. La declaració $X\Rightarrow Y$ sovint es llegeix com si $X$ aleshores $Y$, on l'antecedent ($X$ ) és el si i el conseqüent ($Y$ ) és el llavors . Això simplement implica que, en teoria, sempre $X$ es produeix en un conjunt de dades, doncs $Y$ també ho farà.