Visita Encydia-Wikilingue.com

Regles d'associació

regles d'associació - Wikilingue - Encydia

En mineria de dades i aprenentatge automàtic, les regles d'associació s'utilitzen per descobrir fets que ocorren en comú dins d'un determinat conjunt de dades.[1] S'han investigat àmpliament diversos mètodes per a aprenentatge de regles d'associació que han resultat ser molt interessants per descobrir relacions entre variables en grans conjunts de dades.

Piatetsky-Shapiro[2] descriu l'anàlisi i la presentació de regles 'fortes' descobertes en bases de dades utilitzant diferents mesures d'interès. Basat en el concepte de regla forta, Agrawal et al.[3] van presentar un treball en el qual indicaven les regles d'associació que descobrien les relacions entre les dades recopilades a gran escala en els sistemes de terminals de punt de venda d'uns supermercats. Per exemple, la següent regla:


\{cebollas, vegetales\} \Rightarrow \{carne\}

Oposada en les dades de vendes d'un supermercat, indicaria que un consumidor que compra cebes i vegetals alhora, és probable que compri també carn. Aquesta informació es pot utilitzar com a base per prendre decisions sobre màrqueting com a preus promocionals per a certs productes o on situar aquests dins del supermercat. A més de l'exemple anterior aplicat a l'anàlisi de la cistella de la compra, avui dia, les regles d'associació també són aplicable a moltes altres àrees com el Web mining, la detecció d'intrusos o la bioinformática.

Contingut

L'exemple més popular

Un cas molt famós sobre regles d'associació és el de la" cervesa i els bolquers", basat en el comportament dels compradors en el supermercat. Es va descobrir que molts homes acaben comprant bolquers per encàrrec de les seves esposes. En la cadena de supermercats Wal-Mart, on es va descobrir aquest fet, es va adoptar la mesura de col·locar la cervesa al costat dels bolquers. D'aquesta manera va aconseguir augmentar la venda de cervesa.

Definició del problema

Segons la definició original d'Agrawal et al[ 3] el problema de mineria de regles d'associació es defineix com:

Cada transacció en D\,\! té un ANEU (identificador) únic i conté un subconjunt d'items de I\,\!. Una regla es defineix com una implicació de la forma:

X \Rightarrow Y

On:

X, Y \subseteq I i
X \cap Y = \emptyset

Els conjunts d'items X\,\! i Y\,\! es denominen respectivament "antecedent" (o part esquerra) i "conseqüent" (o part dreta) de la regla.

Exemple pràctic

Exemple:
Base de dades amb 4 items i 5 transaccions
ANEU Llet Pa Mantega Cervesa
1 1 1 0 0
2 0 1 1 0
3 0 0 0 1
4 1 1 1 0
5 0 1 0 0

Per il·lustrar aquests conceptes vegeu el següent exemple sobre vendes en un supermercat. El conjunt d'items és:

I= \{\mathrm{Leche, Pan, Mantequilla, Cerveza}\}\,\!

A la dreta es mostra una petita base de dades que conté els items, on el codi '1' s'interpreta com que el producte (item) corresponent està presenta en la transacció i el codi '0' significa que aquest producte no aquesta present. Un exemple de regla per al supermercat podria ser:

\{\mathrm{Leche, Pan}\} \Rightarrow \{\mathrm{Mantequilla}\}

Significaria que si el client va comprar 'llet' i 'pa' també va comprar 'mantega', és a dir, segons l'especificació formal anterior s'hauria de:

X=\{\mathrm{Leche, Pan}\}\,\!
Y=\{\mathrm{Mantequilla}\}\,\!

Regles significatives, 'suport' i 'confiança'

Noti's que l'exemple anterior és molt petit, en la pràctica, una regla necessita un suport de diversos centenars de registres (transaccions) abans que aquesta pugui considerar-se significativa des d'un punt de vista estadístic. Sovint les bases de dades contenen milers o fins i tot milions de registres.

Per seleccionar regles interessants del conjunt de totes les regles possibles que es poden derivar d'un conjunt de dades es poden utilitzar restriccions sobre diverses mesures de" significancia" i "interès". Les restriccions més conegudes són els llindars mínims de" suport" i "confiança".

El' suport' d'un conjunt d'items X\,\! en una base de dades D\,\! es defineix com la proporció de transaccions en la base de dades que conté dita conjunta d'items:

\mathrm{sop}(X)=\frac{\left |X\right \vert}{\left |D\right \vert} \,\!

En l'exemple anterior el conjunt \{\mathrm{Leche, Pan}\}\,\! té un suport de;

\mathrm{sop}(X)=\frac{2}{5}=0.4\,\!

És a dir, el suport és del 40% (2 de cada 5 transaccions).

La' confiança' d'una regla es defineix com:

\mathrm{conf}(X\Rightarrow Y) = \frac{\mathrm{sop}(X \cup Y)}{\mathrm{sop}(X)} = \frac{\left |X \cup Y\right \vert}{\left |X\right \vert}

Per exemple, per a la regla:

\{\mathrm{Leche, Pan}\} \Rightarrow \{\mathrm{Mantequilla}\}

La confiança seria:

\mathrm{conf}(\{\mathrm{Leche, Pan}\} \Rightarrow \{\mathrm{Mantequilla}\}) = \frac{\mathrm{sop}(\{\mathrm{Leche, Pan}\} \cup \{\mathrm{Mantequilla}\})}{\mathrm{sop}(\{\mathrm{Leche, Pan}\})} = \frac{0.2}{0.4}=0.5

Aquest càlcul significa que el 50% de les regles de la base de dades que contenen 'llet' i 'pa' en l'antecedent la també tenen 'mantega' en el conseqüent; en altres paraules, que la regla:

\{\mathrm{Leche, Pan}\} \Rightarrow \{\mathrm{Mantequilla}\}

És certa en el 50% dels casos.

La confiança pot interpretar-se com un estimador de P(Y|X), la probabilitat de trobar la part dreta d'una regla condicionada al fet que es trobi també la part esquerra[4] .

Les regles d'associació han de satisfer les especificacions de l'usuari quant a llindars mínims de suport i confiança. Per aconseguir això el procés de generació de regles d'associació es realitza en dos passos. Primer s'aplica el suport mínim para trobés els conjunts d'items més freqüents en la base de dades. En segon lloc es formen les regles partint d'aquests conjunts freqüents d'items i de la restricció de confiança mínima.

Trobar tots els subconjunts freqüents de la base de dades és difícil ja que això implica considerar tots els possibles subconjunts d'items (combinacions d'items). El conjunt de possibles conjunts d'items és el conjunt potencia d'i I la seva grandària és 2^n-1 de (excloent el conjunt buit que no és vàlid com a conjunt d'items). Encara que la grandària del conjunt potència creix exponencialment amb el nombre d'items n de I, és possible fer una recerca eficient utilitzant la propietat "downward-closure" del suport[3] (també cridada anti-monòtona[5] ) que garanteix que per a un conjunt d'items freqüent, tots els seus subconjunts també són freqüents, i de la mateixa manera, per a un conjunt d'items infreqüent, tots els seus superconjuntos han de ser infreqüents. Explotant aquesta propietat s'han dissenyat algorismes eficients (per exemple: Apriori[6] i Eclat[7] ) per trobar els items freqüents.

Millora de la confiança: "Lift" (1, 2)

El lift, indica com és la proporcion entre el suport observat d'un conjunt de productes respecte del suport teòric d'aquest conjunt donat el supòsit d'independència. Un valor de lift = 1 indica que aquest conjunt apareix una quantitat de vegades concorde a l'esperat sota condicions d'independència. Un valor de lift > 1 indica que aquest conjunt apareix una quantitat de vegades superior a l'esperat sota condicions d'independència (pel que es pot intuir que existeix una relació que fa que els productes es trobin en el conjunt més vegades del normal). Un valor de lift < 1 indica que aquest conjunt apareix una quantitat de vegades inferior a l'esperat sota condicions d'independència (pel que es pot intuir que existeix una relacion que fa que els productes no esten formant part del mateix conjunt més vegades del normal).

Algorismes

Existeixen diversos algorismes que realitzen recerques de regles d'associació bases de dades.

Referències

  1. ↑ T. Menzies, I. Hu. Data Mining For Busy People. IEEE Computer, Outubro de 2003, pgs. 18-25.
  2. ↑ Piatetsky-Shapiro, G. (1991), Discovery, analysis, and presentation of strong rules, in G. Piatetsky-Shapiro & W. J. Frawley, eds, ‘Knowledge Discovery in Databases’, AAAI/MIT Press, Cambridge, DT..
  3. ↑ a b c R. Agrawal; T. Imielinski; A. Swami: Mining Association Rules Between Sets of Items in Large Databases", SIGMOD Conference 1993: 207-216
  4. ↑ Jochen Hipp, Ulrich Güntzer, and Gholamreza Nakhaeizadeh. Algorithms for association rule mining - A general survey and comparison. SIGKDD Explorations, 2(2):1-58, 2000.
  5. ↑ Jian Pei, Jiawei Han, and Laks V.S. Lakshmanan. Mining frequent itemsets with convertible constraints. In Proceedings of the 17th International Conference on Data Engineering, April 2-6, 2001, Heidelberg, Germany, pages 433-442, 2001.
  6. ↑ Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Xile, September 1994.
  7. ↑ Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, May/June 2000.

Vegeu també

Enllaços externs

Bibliografia

Implementacions

Obtingut de" http://ks312095.kimsufi.com../../../../articles/a/r/t/artes_Visuals_Cl%C3%A1sicas_b9bf.html"