3.1 AIS SETM... 13


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "3.1 AIS SETM... 13"

Transcripción

1 &DStWXOR 5HJODVGHDVRFLDFLyQ FA":G?HAI*J(A2)'LKM* 3.1 AIS SETM APRIORI, APRIORITID & APRIORIHYBRID Algoritmo Apriori Algoritmo AprioriTID Algoritmo AprioriHybrid OCD DHP MAX-MINER ZA":G?HAI*J(A2)'LKM* 4.1 Algoritmo directo Algoritmo mejorado E7"^_<A`<(J<A%02[O+CQ2;QAH$24*IJ(BUà240O+Cb"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"1"RE76

2 i k "!#%$'&(*)+',.--/10$ W5SDFJHDX ;>DY7 Z?JJ [\[ ;IG;IJH=87?K?;>DFGESRJHTIUVE][^'TFJR;IES_ DFC UV_ 58W5SDFJHDPd Rakesh Agrawal & John C. Shafer: Parallel Mining of Association Rules IEEE Transactions on Knowledge and Data Engineering, December es un término genérico que engloba resultados de investigación, técnicas y herramientas usadas para extraer información útil de grandes bases de datos. Este proceso de extracción de información se conoce como L.3M3 [ 58W5SDFJHD ]. Las investigaciones en este tema incluyen análisis estadístico de datos, razonamiento basado en casos 5SDFJ 5SDFJHK JH5SDFE [hjiak : h ], técnicas de representación del conocimiento, redes neuronales y visualización de datos. L.3M3 se ha definido como la extracción no trivial de información potencialmente útil a partir de un gran volumen de datos en el cual la información está implícita (aunque no se conoce previamente). Se trata de interpretar grandes cantidades de datos y encontrar relaciones o patrones. Para conseguirlo harán falta técnicas de aprendizaje [ 9l5?GHZ?;>=?J m ], estadística y bases de datos. L:3n3 Tareas comunes en son: inducción de reglas, clasificación, clustering, reconocimiento de patrones, modelado predictivo, visualización de grandes cantidades de datos, detección de dependencias, manejo de incertidumbre... Aquí nos centraremos en la obtención de reglas de asociación y en la aplicación de las técnicas existentes al caso particular de las bases de datos relacionales. La obtención de reglas de asociación a partir de grandes bases de datos transaccionales resulta atractiva para los estudios de marketing de las organizaciones comerciales. El uso de códigos de barras facilita la recolección de grandes cantidades de datos [ W5SDb`J7 KS587 5 ]. Sería deseable disponer de técnicas que permitan la extracción de información útil a partir del gran volumen de información almacenada en las bases de datos de transacciones. En estas bases de datos, generalmente, una transacción contiene la fecha en la que se produjo y los items involucrados en ella (ítemes sería lo correcto en castellano). Siendo I el conjunto completo de items, una transacción es un conjunto de items To I al que se le asocia un identificador único TID. Una transacción contiene un conjunto de items X si Xo T. A partir de aquí denominaremos ;\7JHpMDFJ7 a un conjunto de items (para evitar confusiones cuando hablemos de conjuntos de itemsets). Una regla de asociación es una implicación de la forma Xq Y donde X e Y son conjuntos de items de intersección vacía. La fiabilidad [ GE =r[ ;>K?JH=?GJ ] de la regla de asociación Xq Y es la proporción de transacciones con X que contienen también a Y. La relevancia [ DF_s^S^OE Tt7 ] de la regla es la proporción de transacciones de la base de datos que contienen Xu Y (tanto X como Y).

3 Dado un conjunto de transacciones D, se trata de obtener todas las reglas de asociación que tengan una fiabilidad y una relevancia superiores a unos umbrales especificados por el usuario (!#"%$'&)( $+* "%,.-/$.0- y!#"%$ ( 798 ). Como caso particular, los algoritmos de extracción de reglas de asociación se pueden aplicar a bases de datos relacionales. Entonces un ítem será un par :%;'8 A%B/;.CD( 7E y podemos imponer la restricción adicional de que todos los items de un itemset han de corresponder a atributos diferentes (como consecuencia de la Primera Forma Normal). F G9HIKJMLDN Supongamos que disponemos de información acerca de las transacciones que se realizan en un supermercado. Cada transacción estará identificada por un código OPRQ (aquí el nombre del cliente) y contendrá un conjunto de artículos ("D8S-9TU ). Una muestra de la base de datos podría ser: Cliente Juan María Ana Artículos Patatas, Huevos, Bacon Pan, Leche, Huevos Pan, Leche, Patatas, Huevos Pan, Leche Si fijamos la relevancia mínima en un 50% (!#"%$ ( 798RV)WXYMW ) estamos indicando que, para que una regla sea considerada, al menos debe cumplirse en el 50% de las transacciones de la base de datos (2 transacciones en este caso). Al establecer un umbral mínimo para la fiabilidad de las reglas de asociación estamos descartando aquéllas reglas que no se cumplen con la frecuencia necesaria para que sean consideradas interesantes. Dada la base de datos anterior, podemos obtener, entre otras, las siguientes reglas de asociación: Z Z Z Z [ Z Z [ [ Z Z [ [ Z Z [ N Regla Support Confidence 1 Pan Leche 75 % 100 % 2 Leche Pan 75 % 100 % 3 Patatas Huevos 50 % 100 % 4 Huevos Patatas 50 % 66.6 % 5 Pan Huevos Leche 50 % 100 % 6 Leche Huevos Pan 50 % 66.6 % 7 Huevos Leche Pan 50 % 100 % 8 Pan Huevos Leche 50 % 66.6 % 9 Leche Pan Huevos 50 % 66.6 % 10 Huevos Leche Pan 50 % 66.6 %

4 De la simple base de datos de transacciones se puede extraer bastante información útil. Por ejemplo, las dos primeras reglas nos muestran cómo es habitual comprar leche cuando se va a por el pan (algo que mucha gente hace diariamente). Las dos siguientes nos podrían indicar que los clientes del supermercado toman con relativa frecuencia huevos con patatas fritas. Estas reglas ponen de manifiesto que la fiabilidad de la regla de asociación A! B obviamente no tiene por qué coincidir con la fiabilidad de la regla inversa B! A. Las seis reglas que vienen a continuación son resultado de combinar varios items (tres en este caso). Se puede apreciar cómo el número de reglas que se obtienen puede ser inmenso para grandes bases de datos, con lo que se crea un problema de "$#&% #')( * ( *+ de segundo orden. Una vez obtenidas las reglas de asociación deberemos idear métodos que nos permitan acceder con facilidad a la información que nos interese. Como es lógico, el número de reglas que se genera se puede disminuir aumentando los umbrales preestablecidos (',(-*/.&021/143 56% y ',(-*8793 *;: (-<&=>*&?= ), pero esta técnica podría ocasionar la pérdida de información útil. Por lo tanto, habrá que facilitarle al usuario la manipulación de la información obtenida tras la extracción de las reglas.

5 q!#"$%'&)(&+*-,/.0(, 132, A continuación se expondrán distintos algoritmos que se han utilizado para extraer reglas de asociación de grandes bases de datos. En ellos, el problema de la obtención de todas las reglas de asociación se suele descomponer en: EF?A/?K R+WdQTF^FQegfUQ^hfUi Encontrar todos los conjuntos de items [jlkmsnpoumk o ] con relevancia por encima de jhrlsxtvuluxw yhk. La relevancia de un conjunto de items z es el número de transacciones que lo contienen y se denotará outvuluxw yhkl{ z5. Los conjuntos de items cuya relevancia quede por encima del umbral serán los itemsets relevantes [}h~ly+dm jlkmsnpoumk o, wl msyujhrƒjlkmsnpoumk o o yum LtLmSrdkjlkmSnpoUmk o ] mientras que los que queden por debajo no nos interesarán [serán los o>np~x}f} jlkmsnpoumk o ]. <ˆ?Š EFILB- 5?ILB>_LŒ`FILŒ`F LK'Mc f>fuolntfcl^ftfolvžru]5bfqsfui Generar las reglas de asociación utilizando los conjuntos de items relevantes obtenidos en el paso anterior. Si - y - son conjuntos de items relevantes, la regla - g 3 tendrá una fiabilidad igual al cociente outvuluxw yhkl{ - - C outvuluxw yhkl{ -. La regla tendrá con seguridad una relevancia mínima (ya que - es un conjunto relevante de items) y nos quedaremos con ella si su fiabilidad alcanza el umbral establecido [ q jhrj -w r jh XmSrX m ].

6 F F F F F F GIH0JLK MON;PRQ STQVÜ W,XZY\[^]U^[^_a`cbE[edgfSTQVY\[^h Rakesh Agrawal, Tomasz Imielinsky & Arun Swami IBM Almaden Research Center, 1993 J,iOj6klK femonaprq PR[^]_es^]tuv[^_e[^_ENwqyxzQ `c`rqv{[^qvs^[^qv_wpr eu^]}`rh Maurice Houtsma & Arun Swami IBM Almaden Research Center, 1993 Go~e0 ^ V0 ^ Go~e0 ^ V0 ^j6hcƒ Go~e0 ^ V0 ˆ Še0 ^Œ Rakesh Agrawal & Ramakrishnan Skirant IBM Almaden Research Center, 1994 CŽƒ K x(x U^[^_e] "QV_etV[^tVQVs^]T o]s^]}pry\[^_eqvs^[^qv_eh Heikki Mannila, Hannu Toivonen & A. Inkeri Verkamo University of Helsinki, 1994 ƒ C K o[ PR]{s šq `R e[^_enwqv_etiœ6pr e_e_e[^_enah Jong Soo Park, Ming-Syan Chen & Philip S. Yu IBM Thomas J. Watson Research Center, 1995 kž Ÿ (kž ^ e Roberto J. Bayardo Jr. IBM Almaden Research Center, 1998

7 !#"%$'&)(+* U U l - l DE-02GF KSR<;8-0D)I TVU KS9QP0=J132\[<1Y ;]113KS2Q1Ÿ -Z[-02Q132ce 4>16g RHih Ukj]l g8c Km^ 139Q13K>X1C K -0K0-7c13D)13KZY#C_^ -ZŸ K g? pr6o? -qsrt0t#u AIS es el primer algoritmo que se desarrolló para obtener reglas de asociación. De hecho, en el artículo donde aparece descrito aparece por primera vez el concepto de regla de asociación como mecanismo de representación del conocimiento simple y útil para caracterizar las regularidades que se pueden encontrar en grandes bases de datos. En AIS, una regla de asociación es una implicación de la forma vswsx)ygzg{v ~} donde es un itemset, es un ítem (no incluido en ), 2 representa la relevancia [ 2QP 0 ]C 9iY ] de la regla y X su fiabilidad [ XC Km^ ]. En algoritmos posteriores, tanto como pueden ser itemsets. La relevancia y la fiabilidad de las reglas de asociación se suelen representar como fracciones. La fiabilidad de la regla de asociación Xƒ Y es la proporción de transacciones con X que contienen también a Y mientras que la relevancia de la regla es la proporción de transacciones de la base de datos que contienen X Y. Una de las características esenciales de las reglas de asociación es que incorporan medidas estadísticas (relevancia y fiabilidad) en las clásicas reglas de la Lógica Proposicional. De hecho, al representarlas se escogió ƒ para distinguirlas de las implicaciones lógicas ( ). Para evitar la generación de reglas de asociación irrelevantes, se fijan de antemano los umbrales U 0 ]C 9iY y U Km^ Un itemset con k items será denominado 0 Ĵ JŠ ŒzQŠ. Los / bi%y13de2q1ÿ 2 con una relevancia igual o superior al umbral U 0 ]C 9iY pertenecerán al conjunto Ž8yG }, el conjunto de k-itemsets relevantes ( / bi%y13de2q1ÿ 2 ). En el conjunto ByG } se incluirán aquéllos k-itemsets que, en /G principio, podrían pertenecer al conjunto. Los itemsets de g /G se denominan k-itemsets candidatos ( bi%y13de2q1ÿ 2 ). Los itemsets candidatos se generan y su relevancia obtiene conforme se recorre la base de datos utilizando un contador. Hay que destacar que los itemsets se almacenan ordenados lexicográficamente. Tras leer una transacción de la base de datos, se determinan qué itemsets relevantes de los encontrados en la pasada anterior por la base de datos están contenidos en la transacción. Los itemsets candidatos se generan extendiendo los itemsets relevantes encontrados en la transacción con otros items de la transacción.

8 De una transacción de N items que contiene un determinado k-itemset relevante se generan (k+1)-itemsets candidatos, los cuales se incluyen en!"#%$'& ( con su contador igual a 1 (si el itemset candidato no existía anteriormente en!"#%$'& ( ) o ven incrementado su contador (si el itemset ya se había introducido en el conjunto de candidatos al procesar una transacción anterior). A continuación se ofrece el esquema básico del )+*-,/./ : : es el conjunto de itemsets relevantes que contienen k items. es el conjunto de k-itemsets (itemsets de k elementos) candidatos, aquéllos que pueden llegar a ser relevantes si tienen la relevancia mínima. L[1] = {large 1-itemsets} k = 2 Mientras L[k-1] D E C[k] = E ; Para cada transacción t F D L t = Conjunto de (k-1)-itemsets relevantes contenidos en t Para cada itemset l t F L t C t = Extensiones de l t contenidas en t (*) Para cada candidato c F C t Si c F C[k] Incrementar el contador asociado a c en C[k] Si no Añadir c a C[k] (contador=1) L[k] = { c F C[k] contador(c)g MinSupport } k++ Solución: H L[k] (*) A partir de los conjuntos relevantes de items encontrados en una transacción, se generan los candidatos expandiendo éstos con items que se encuentren en la transacción.

9 `!#" $&%(''"*)+"-,.0/'"1.0"32$&%54,&6 2 7 Para mantener y manejar eficientemente los conjuntos de items se utiliza un árbol hash (una tabla hash dinámica multinivel). Un nodo del árbol puede ser una lista de itemsets (hojas) o una tabla hash (nodos internos). La función hash de una tabla hash a una profundidad k se aplica al k-ésimo elemento del conjunto de items. Inicialmente, el árbol consiste en un único nodo hoja. Cuando el número de itemsets en una hoja excede un umbral prefijado, la hoja se convierte en un nodo interno. Con esta estructura de datos se puede comprobar eficientemente qué itemsets están contenidos en una transacción determinada. 8 9:"1.0/'3; : Supongamos disponemos de la base de datos del supermercado y establecemos el umbral G1H en 0.5 (para que un ítem sea relevante ha de estar incluido en, al menos, dos de las cuatro transacciones): Cliente Juan María Ana Artículos Patatas, Huevos, Bacon Pan, Leche, Huevos Pan, Leche, Patatas, Huevos Pan, Leche Inicialmente obtenemos el conjunto IJKEL de items relevantes. Este conjunto está formado por los items {Patatas}[2], {Pan}[3], {Huevos}[3] y {Leche}[3]. El número que aparece entre corchetes indica la relevancia del ítem (es un contador asociado a él). IJ1_1L Comenzamos el recorrido por la base de datos. De la primera transacción obtenemos los itemsets incluidos en L[1]: {Patatas} y {Huevos}. A partir de ellos generamos los candidatos {Patatas,Huevos}[1], {Patatas,Bacon}[1] y {Huevos,Bacon}[1]. Nótese que los items que incluyen a {Bacon} nunca podrán ser relevantes y, a pesar de ello, AIS los procesa (el algoritmo Apriori aprovecha esta información). J1_1L {Patatas,Huevos} [1] {Patatas,Bacon} [1] {Huevos,Bacon} [1]

10 De la segunda transacción, que incluye tres items relevantes de "#$ %, se obtienen los candidatos ({Pan,Leche}, {Pan,Huevos} y {Leche,Huevos}) y se actualiza el estado de &#('(% : &#('(% {Pan,Leche}[1] {Pan,Huevos} [1] {Leche,Huevos} [1] {Patatas,Huevos} [1] {Patatas,Bacon} [1] {Huevos,Bacon} [1] Continuando nuestro recorrido analizamos las transacciones realizadas por y Ana, con lo que obtenemos el conjunto C[2]: &#('(% {Pan,Leche}[3] {Pan,Patatas} [1] {Pan,Huevos} [2] {Leche,Patatas} [1] {Leche,Huevos} [2] {Patatas,Huevos} [2] {Patatas,Bacon} [1] {Huevos,Bacon} [1] Quedándonos únicamente con los itemsets candidatos cuyo contador es igual o superior al valor establecido por )+*-,/.1032/254 6(7 obtenemos "#('(% : "#('(% {Pan,Leche}[3] {Pan,Huevos} [2] {Leche,Huevos} [2] {Patatas,Huevos} [2]!

11 B B B!#"%$'& (*)*+-,/."102+#3,54 ('6798*."1(#3,54 (:)#"<;=1>%? Repitiendo el proceso anterior, esta vez con como entrada, vemos que la transacción realizada por Juan incluye al itemset {Patatas,Huevos} de por lo que el itemset =1>%? {Patatas,Huevos,Bacon} se incluye en el conjunto B. =1>%? {Patatas,Huevos,Bacon}[1] De las compras de María, que incluyen el itemset {Pan,Leche} de incluimos =1>%? {Pan,Leche,Huevos} en B. =1>%? {Pan,Leche,Huevos}[1] {Patatas,Huevos,Bacon}[1] De la transacción realizada por, que incluye varios itemsets de se generan los siguientes itemsets candidatos: {Pan,Leche,Patatas}, {Pan,Leche,Huevos}, {Pan,Patatas,Huevos} y {Leche,Patatas,Huevos}. =1>%? {Pan,Leche,Patatas}[1] {Pan,Leche,Huevos}[2] {Pan,Patatas,Huevos}[1] {Leche,Patatas,Huevos}[1] {Patatas,Huevos,Bacon}[1] Finalmente, de la compra de Ana no se puede generar ningún 3-itemset candidato (la =1>%? transacción sólo incluye dos items). Por lo tanto, el conjunto B queda como estaba. Para obtener ;=1>%? =1>%? simplemente nos quedamos con los itemsets de B que tienen la,d(*!#&fe*e<g 0A. relevancia mínima establecida por C : ;=1>%? {Pan,Leche,Huevos}[2]

12 ?!#"%$'&"%$)(+*-,"%$)(.&*0/ #,"%1.&*0/ 187.":9;%<'= A partir de 9;%>'= se obtiene? transacción realizada por : que contiene un único elemento proveniente de la ;%<'= {Pan,Leche,Patatas,Huevos}[1] Como este 4-itemset no tiene la relevancia mínima prefijada, el conjunto de itemsets 9;%<'= queda vacío, por lo que no se realizan más iteraciones.

13 "$#&%('$)+*-,.0/21 O H28>PQ; GI351=[78R?]\ ^_8R?58R/=356R`B^_8ba:; 3c>^edgf=hjijk ;?58Rq]p/2[74X ; 3AG24U/=q]r6>;$sK8R3otf=f$u El algoritmo SETM [ HvLw=PQ; 35478RGS>8RT.x4UG24UGVL;YXy/=?A?5;=64U/S>47; G+351=[78R? ], al igual que el algoritmo AIS, fue desarrollado en el IBM Almaden Research Center (California). Se deriva del algoritmo AIS y se caracteriza porque fue diseñado pensando utilizar SQL para la generación de itemsets relevantes. Tal como hacía AIS, SETM genera candidatos en cada iteración conforme va realizando un recorrido secuencial de la base de datos. El algoritmo genera exactamente el mismo conjunto de candidatos que generaba AIS. No obstante, para utilizar SQL estándar, SETM separa la generación de itemsets candidatos de la obtención de la relevancia de los mismos. SETM utiliza una tabla auxiliar pw z{} en la que almacena los k-itemsets candidatos generados acompañados del identificador de la transacción a partir de la que se obtuvieron (TID). Al final de cada pasada, se obtiene la relevancia de los candidatos ordenando la tabla pw z{} y agrupando las tuplas correspondientes a un mismo itemset. SETM almacena los identificadores de las transacciones (TID) con los candidatos para evitar tener que comprobar si un itemset está incluido en una transacción dada. De esta forma se acelera el proceso de obtener los itemsets relevantes incluidos en una transacción determinada. w z{} El algoritmo utiliza otra tabla auxiliar, ~, para almacenar los k-itemsets relevantes (acompañados de los TIDs correspondientes). Esta tabla se obtiene a partir de pw z{} eliminando de esta tabla aquellos candidatos cuya relevancia no alcanza el umbral preestablecido.x4ug=h 1aKa;35>. Asumiendo que la base de datos se encuentra ordenada según TID, SETM w2z {} puede encontrar los itemsets relevantes incluidos en una transacción w z{} ordenando la tabla ~ según TID. pw z{2 yt De esta forma sólo tiene que recorrer una vez la tabla ~ para generar los candidatos. El principal inconveniente de SETM reside en el tamaño que puede llegar a tener la tabla de candidatos pw z{} pw z{}. Para cada itemset candidato (que pueden ser muchos de por sí) en la tabla aparecerán tantas tuplas como transacciones haya en la base de datos que incluyan al candidato. Además, cuando queremos obtener la relevancia de los itemsets candidatos, pw z{} debe reordenarse ya que tras el paso anterior se encontraba ordenada según TID. Para calcular la relevancia de los itemsets la tabla debe ordenarse de forma que todas las tuplas en las que aparezca un itemset estén agrupadas.!

14 Por si todo esto fuera poco, tras eliminar los candidatos cuya relevancia no alcanza el umbral mínimo preestablecido, el conjunto obtenido "$# %&(' necesita reordenarse según TID para poder ser utilizado en la generación de candidatos )# %&+*-, ' de la siguiente iteración. es el siguiente: L[k] y C[k]: Itemsets (igual que en el algoritmo AIS). LT[k] y CT[k]: Conjuntos de elementos de la forma <TID,itemset> (itemsets junto con los TIDs de las transacciones en las que aparecen) L[1] = { large 1-itemsets } LT[1] = { large 1-itemsets acompañados de los TIDs correspondientes } k = 2 Mientras L[k-1] C D CT[k] = D Para cada transacción t E D L t = Conjunto de (k-1)-itemsets de LT[k-1] contenidos en t (TID) Para cada itemset l t E L t C t = Extensiones de l t contenidas en t CT[k] + = { <TID,c> c E C t } Ordenar CT[k] por itemsets Eliminar de CT[k] los itemsets con contador < MinSupport F LT[k] L[k] = { < l.itemset, l.contador > l E LT[k] } Ordenar LT[k] según TID k++ Solución: G L[k] HJIKML : SETM se diseñó para utilizar SQL, por lo que las transacciones se representan por conjuntos de tuplas N#OQPSRUTWVXZY\[.!

15 3 3 "$#%'& (*) +-,.)/10 Como se ha comentado, la principal desventaja de SETM reside en el tamaño de los conjuntos ya que cada conjunto candidato de items aparece tantas veces como el número de transacciones en las que está presente. Si no cabe en memoria, las dos reordenaciones necesarias en cada iteración deberán realizarse según algún algoritmo de ordenación externa. 9 0 Supongamos que partimos de la información obtenida de la base de datos del supermercado. La tabla de datos de entrada al algoritmo SETM será la mostrada a la izquierda (utilizando el nombre del cliente como TID). Como en AIS, obtenemos primero BDC E<F, formado por los itemsets {Patatas}[2], {Pan}[3], {Huevos}[3] y {Leche}[3]. Además, tenemos que generar la G8H-IKJLHMB?N.C E<F (columna derecha). +.O1PQ+SRT/MR-+.)& U +.O1PQ+WV 3 5X 7 TID Ana Ítem Leche TID Ana Itemset {Leche} Ana Pan Ana {Pan} Juan Bacon Juan {Huevos} Juan Juan Huevos Patatas Juan {Patatas} {Huevos} Huevos {Leche} Leche {Pan} Pan Patatas María {Patatas} {Huevos} María Huevos María {Leche} María Leche María {Pan} María Pan!

16 A partir de la tabla #%$ &' ( rellenamos la )+*-,/.0* : TID Ana Juan Juan Juan María María María Itemset {Leche,Pan} {Bacon,Huevos} {Bacon,Patatas} {Huevos,Patatas} {Huevos,Leche} {Huevos,Pan} {Huevos,Patatas} {Leche,Pan} {Leche,Patatas} {Pan,Patatas} {Huevos,Leche} {Huevos,Pan} {Leche,Pan} Una vez obtenida esta tabla, se ordena por itemsets y se eliminan aquéllos cuya relevancia no llegue a EGF. Esta operación nos permite obtener la )+*-,/.0*IHJ : TID Juan Juan María María Juan Ana María Itemset {Bacon,Huevos} {Bacon,Patatas} {Huevos,Leche} {Huevos,Leche} {Huevos,Pan} {Huevos,Pan} {Huevos,Patatas} {Huevos,Patatas} {Leche,Pan} {Leche,Pan} {Leche,Pan} {Leche,Patatas} {Pan,Patatas} "!

17 De la tabla LT[2] se obtiene con facilidad L[2]: {Huevos,Leche}[2], {Huevos,Pan}[2], {Huevos,Patatas}[2] y {Leche,Pan}[3]. Para seguir con la siguiente iteración debemos ordenar #%$ &('() según su TID: TID Ana Juan María María María Itemset {Leche,Pan} {Huevos,Patatas} {Huevos,Leche} {Huevos,Pan} {Huevos,Patatas} {Leche,Pan} {Huevos,Leche} {Huevos,Pan} {Leche,Pan} A partir de esta tabla, se genera la *,+.-0/ : TID Juan María Itemset {Bacon,Huevos,Patatas} {Huevos,Leche,Pan} {Huevos,Leche,Patatas} {Huevos,Pan,Patatas} {Leche,Pan,Patatas} {Huevos,Leche,Pan} Reordenando y suprimiendo los itemsets que no llegan a la relevancia mínima (CEDGF.HJILK.KNM O(P ) rellenamos la : TID Juan María Itemset {Bacon,Huevos,Patatas} {Huevos,Leche,Pan} {Huevos,Leche,Pan} {Huevos,Leche,Patatas} {Huevos,Pan,Patatas} {Leche,Pan,Patatas} "!

18 De la tabla "$# %'&)( se obtiene con facilidad el conjunto "%'&)(, que está formado única y exclusivamente por el itemset {Huevos,Leche,Pan}[2]. Para la siguiente iteración, debemos ordenar nuevamente "$# %'&)(, esta vez según TID: TID María Itemset {Huevos,Leche,Pan} {Huevos,Leche,Pan} A partir de esta tabla se crea la *,+.-0/ )9 : TID Itemset {Huevos,Leche,Pan,Patatas} Una vez que tenemos esta tabla, es trivial ver que la *,+.-0/1+;:<476 8)9 quedará vacía, ya que el único elemento de =# %'>)( no alcanza la relevancia mínima: TID Itemset {Huevos,Leche,Pan,Patatas} Por lo tanto, el conjunto de itemsets relevantes "%'>)( estará vacío y el algoritmo no tendrá que realizar más iteraciones. Como se puede apreciar, el algoritmo SETM, aunque de una forma diferente, encuentra exactamente los mismos itemsets candidatos que el algoritmo AIS. A continuación se expondrán otros algoritmos que mejoran el rendimiento tanto de SETM como de AIS.!

19 "$#%"'&'( )+*-,.)+*-/ &'( )+*-,.)+* &'( )+*-,.)+*8:9<; )+*-= []\?.C^XF_L Ga` HSRZẌ E.PQCb ` H cdrtumrtugeffc4cs`.grt?<xr-` UQ>ih.L-BDCaj kmlcn>ibdcsbd?.hsgdeq>ibpoq` H^X>sr t.u$vkt kmlcwf_ltpq?.xmbduq>ibdcsbd?.hsgdezy2bdu<xbdh4{$v.?.uqr ` CSBD{ay?ML-Rb ` H4UMRT?} ~VF {Kr h UMBe t.t$ NOr ` E.Uzy2ƒMV.E.? b BDH []?.H4?ML-L-BLcdRTUMRTUG}` bfffc4cs`.grt?<xr-` UQ>ih.L-BDCaj km s s ˆ H4?.U.C4?MgXR-` U.Cq` UQŠUM`JqL-BDxGaB_?.U.xQ :BgBDP'ŒKBDH_ t.ti h.bdc^x Agrawal y Skirant, trabajando para el proyecto Ž de IBM [ k4u<xbdh4u.?<xr-` U.?ML<lih CSRTUMBDC4C c?mgdemrtumbdc ] en el IBM Almaden Research Center de San José en California, propusieron en 1994 dos algoritmos que superan con creces a los algoritmos anteriormente conocidos, los ya discutidos AIS y SETM. Los dos algoritmos propuestos se denominan s S - M ^ y s 2 ^ Z S m < 4 y son la base de muchos algoritmos posteriores, un punto de referencia para los algoritmos actuales. Difieren notablemente tanto de AIS como de SETM y demuestran ser más eficientes tanto con datos sintéticos como con datos tomados de la realidad. Aparte de exponer los dos algoritmos mencionados, los autores proponen como se podrían combinar las mejores características de cada uno de ellos en un único algoritmo, denominado s S - S Q Iš. S -, que consigue mejores resultados (un tiempo de ejecución proporcional al número de transacciones de la base de datos). Los algoritmos de la familia F$osH R` HSR realizan múltiples pasadas sobre la base de datos para obtener los conjuntos de itemsets relevantes. En la primera pasada, se obtienen los items individuales cuya relevancia alcanza el umbral mínimo preestablecido [ cdrtu.vmhœo.oq` H^X Ÿ ], con lo que se obtiene el AŸ conjunto ž de itemsets relevantes. En las siguientes iteraciones, se utiliza el último conjunto ž de k-itemsets relevantes obtenido para generar un conjunto de (k+1)-itemsets potencialmente relevantes (el conjunto de itemsets candidatos y Ÿ ž ) y se obtiene la relevancia de estos candidatos Ÿ para quedarnos sólo con aquéllos que son relevantes, que incluimos en el conjunto ž. Este proceso se repite hasta que no se encuentran más itemsets relevantes. En los algoritmos AIS y SETM, los candidatos se generaban sobre la marcha, conforme se iban leyendo transacciones de la base de datos. El método utilizado implica que se generan innecesariamente itemsets candidatos que de por sí nunca pueden llegar a ser relevantes.!

20 Por su parte, tanto en Apriori como en AprioriTID, los candidatos se generan a partir del conjunto de itemsets relevantes encontrados en la iteración anterior, única y exclusivamente. La idea subyacente es que, dado un itemset relevante, cualquier subconjunto suyo también es relevante. Por lo tanto, los k-itemsets candidatos del conjunto "#$&% pueden generarse a partir del conjunto de (k-1)-itemsets relevantes '#$(*) %. Además, se pueden eliminar de "#$&% aquellos itemsets que incluyen algún itemset no relevante. Este proceso permite reducir el tamaño de los conjuntos de candidatos "#$&%. En los algoritmos de la familia +,.-0/213-0/ se presupone que los items de cada transacción están ordenados lexicográficamente. El tamaño de un itemset es el número de items que incluye. Un k-itemset es un itemset de tamaño k. Los items dentro de un itemset también se encuentran ordenados ascendentemente. Asociado con cada itemset se haya asociado un contador (para calcular la relevancia del itemset) que inicialmente vale 0.!

21 Q "!#$"!#&%('*) +-,.0/$1$23,('45.0/$,.0/ En la primera pasada del algoritmo por la base de datos simplemente se cuenta el número de ocurrencias de los items individuales para determinar el conjunto Las iteraciones siguientes se dividen en dos fases. En la iteración :, primero se genera el conjunto de candidatos ;7:<9 a partir del conjunto 67:=>8 9 obtenido en la iteración :=>8. A continuación, se recorre la base de datos secuencialmente para obtener la relevancia de los elementos del conjunto ;?7:<9. Finalmente, incluimos en el conjunto 67:<9 sólo con los itemsets candidatos de ;7:<9 que son relevantes NPO ). Q(R S M N0CTÖ U*M KVN0C$M N0C L[k] es el conjunto de itemsets relevantes que contienen k items. C[k] es el conjunto de k-itemsets candidatos. L[1] = { large 1-itemsets } k = 2 Mientras L[k-1] W X C[k] = CandidatosAPRIORI ( L[k-1] ) Para cada transacción t Y D C t = Conjunto de candidatos de C[k] contenidos en t Para cada candidato c Y C t c.contador ++ L[k] = { c Y C[k] c.contador Z MinSupport } k++ Solución: [ L[k]!

22 c A!#"$!#%'&$()+* "-,$!(#&.".,$)/,.&102 34!#"5!61&$6 782 %9):0 %9) La generación del conjunto de candidatos ABCED se realiza directamente a partir del conjunto de itemsets relevantes FBCG'H D. En primer lugar se generan posibles candidatos a partir del producto cartesiano FBCG'H D IJFBCG'H D imponiendo la restricción de que los k-2 primeros items de los elementos de FBCG'H D han de coincidir. Acto seguido se eliminan del conjunto de candidatos aquellos itemsets que contienen algún (k-1)-itemset que no se encuentre en FBCG'H D. insert into Ck select p.item1, p.item2,..., p.item(k-1), q.item(k-1) from L[k-1] p, L[k-1] q where p.item1=q.item1... p.item(k-2)=q.item(k-2), p.item(k-1)<q.item(k-1) Para cada c de C[k], eliminar c de C[k] si tiene algún subconjunto de k-1 items que no pertenece a L[k-1] K 7ML Supongamos FB#N9DPORQQ'HTSUN V.WJQ'HTSUX V.WJQ'HYN-X V.WJQ'HYNYZ9V.WJQ[S-NYX VV. Tras la reunión, AB#X9D será QQ'HTSUN-X V.WJQ'HYN-XYZ9VV. La poda del conjunto de candidatos eliminará el itemset Q'HYN-XYZ9V porque el itemset Q'HYXYZ9V no está en FB#N9D. Por lo tanto, AB#X9D sólo incluirá a Q'HTSUN-X V. Para este ejemplo, si en la base de datos existe una transacción que incluya Q'HYS\NUXYZ9V, los algoritmos y ^_<`ba generarían los itemsets Q'HYS\NUX V y Q'HYS\N-Z9V extendiendo Q'HYS\N V. Aparte de ellos, incluirían en AB#X9D tres candidatos más derivados de otros de los elementos de FB#N9D incluidos en la transacción. y ^_<`ba generan un conjunto de candidatos con 5 elementos mientras que %9) sólo incluye un itemset en A4BXbD porque, a priori [de ahí el nombre del algoritmo], se percata de que los otros candidatos nunca pueden llegar a tener la relevancia mínima requerida para ser elementos de FB#X9D. Independientemente del trabajo de Agrawal y Skirant en IBM, en la Universidad de Helsinki, Mannila, Toivonen y Verkamo propusieron un procedimiento alternativo para la generación de candidatos [véase el apartado correspondiente al algoritmo dtame ]. 2 %'%9!(()+* "-,$!61;<f02,$2-!#;?46+!#&.,$2L El conjunto de candidatos ABCED generado contiene necesariamente al conjunto de itemsets relevantes FBCED, esto es, ABCED1g$FBCED. Obviamente, cualquier subconjunto de un itemset relevante también tendrá relevancia mínima. Por lo tanto, si extendemos cada itemset de FBCG'H D con todos los items posibles y eliminamos aquéllos que incluyan algún (k-1)-itemset no incluido en FBCG'H D, obtendremos un superconjunto de FBCED. Esto es lo que hace el procedimiento expuesto. La comprobación p.item(k-1)<q.item(k-1) asegura que no se generan itemsets duplicados.

23 _ " #%$'&)(*!+, -/ %465 7)1/-893%4:1 3%4 Supongamos que nuevamente disponemos de la conocida base de datos del supermercado y establecemos el umbral ; en 0.5 (para que un ítem sea relevante ha de estar incluido en, al menos, dos de las cuatro transacciones): Cliente Ana Juan María Artículos Leche, Pan Bacon, Huevos, Patatas Huevos, Leche, Pan, Patatas Huevos, Leche, Pan Como siempre, inicialmente obtenemos el conjunto B9C D%E de items relevantes: FGH I {Huevos} [3] {Leche} [3] {Pan} [3] {Patatas} [2] J93%4=7)KL3NMO465KL3NMQP4:R <2,SUT?5KL<QP4:R <WVQKXFG'Y'I A partir de FGH I se genera el conjunto de candidatos Z[C]\E : ^ G'Y'I {Huevos, Leche} {Huevos, Pan} {Huevos, Patatas} {Leche, Pan} {Leche, Patatas} {Pan, Patatas} Nótese que los algoritmos SETM y AIS generaban ocho itemsets candidatos, dos de más.!

24 ^ N U 7 Se obtiene la relevancia de cada candidato y se genera!#"%$& eliminando aquellos itemsets cuya relevancia no alcance el umbral establecido ')(+*-,/ : 78696: {Huevos, Leche} [2] {Huevos, Pan} [2] {Huevos, Patatas} [2] {Leche, Pan} [3] {Leche, Patatas} [1] {Pan, Patatas} [1] 78CM=:,/;=<>. *>HIKJ-5;C*/E(GF *L?/; A partir del conjunto de itemsets relevantes 78696: "%O&. En primer lugar se realiza la operación: se genera el conjunto de candidatos insert into C[3] select p.item1, p.item2, q.item2 from L[2] p, L[2] q where p.item1=q.item1 and p.item2<q.item2 PRQ 5 8CM=: {Huevos, Leche, Pan} {Huevos, Leche, Patatas} {Huevos, Pan, Patatas} QGZ A continuación se eliminan el segundo itemset porque no pertenece a 78696: QGZ y el tercero porque tampoco está en 78696:. Después obtenemos la relevancia del único itemset que nos queda y comprobamos que alcanza ')(+*-,/ , por lo que lo incluimos en!#"%o& : 78CM=:]\ 8CM=: {Huevos, Leche, Pan} [2] Los algoritmos AIS y SETM habrían generado cinco itemsets candidatos, mientras que 0#4=(G2 4=( sólo genera uno (que de hecho es relevante). U Tal como aparece descrito el algoritmo, aún se intentaría generar 8_=:, que, como es evidente, no contendrá ningún elemento.

25 V!#"%$&"('*)'*+,"(-+*. /10()'2"(' 354 $6+87 9:4<;=#$6+*4 /KJML%'*)NH5O Ahora se describirán brevemente tres alternativas propuestas por Agrawal y Shafer ( >, IEEE Transactions on Knowledge and Data Engineering, December 1996) para implementar el algoritmo ;=#$6+*4 $6+ en un multiprocesador sin memoria compartida. Las técnicas expuestas son, por lo tanto, aplicables a un cluster de estaciones de trabajo. COUNT DISTRIBUTION Este algoritmo realiza cálculos redundantes para reducir la comunicación necesaria entre los distintos procesadores. Cada uno de los procesadores dispone de una parte de la base de datos global en su disco local. Inicialmente, cada procesador!qp P ST U genera un conjunto de candidatos R a partir ST U de los datos almacenados en su disco local. La información obtenida se distribuye y se obtiene SWXU V. En cada iteración posterior, SWY&T U cada procesador genera el conjunto completo de candidatos R a partir del conjunto V, del que todos tienen una copia. Cada procesador SWXU recorre su parte de la base de datos y obtiene la relevancia local de cada itemset candidato de R. Las relevancias locales se intercambian entre los procesadores SWXU para obtener SWXU la relevancia real de cada candidato. Finalmente, cada procesador obtiene V a partir de R. DATA DISTRIBUTION Este algoritmo fue ideado 4%L /27 ZA+CH[7 $6+8\]L?7+*4 / para aprovechar la capacidad total de memoria disponible en el sistema multiprocesador (R no supone ninguna mejora en ese sentido respecto al algoritmo serie). En cambio, requiere mayor velocidad de comunicación entre los distintos procesadores: cada procesador debe difundir su información local a todos los demás procesadores en cada iteración. El procesador + SWXU SWY&T U P SWXU genera el conjunto R a partir de V pero esta vez almacena únicamente una parte R del conjunto (se puede usar una estrategia $ 4]L /%0(Y^$64?\]+C/ para asignar itemsets equitativamente a cada procesador sin necesidad de comunicación). El procesador + P SWXU obtiene la relevancia de cada itemset de R con sus transacciones y las que le envían los demás procesadores. P SWXU A continuación, P SWXU cada procesador genera un conjunto local de itemsets relevantes a partir de SWXU R y la información obtenida se distribuye de forma que todos los procesadores dispongan de V completo para la siguiente iteración.

26 CANDIDATE DISTRIBUTION Este algoritmo intenta explotar información propia del dominio del problema distribuyendo tanto las transacciones como los itemsets entre los distintos procesadores. Los itemsets relevantes de "#$%'& ( se distribuyen de forma que cada procesador genere un subconjunto de ) #'$*( tal que ),+ #$-(/.)102#$-(4365 si Además, cada procesador 7 dispone en su disco local de todas las transacciones que necesita para obtener la relevancia de los itemsets ),+ #$-(. Nótese que esto implica que parte de la base de datos estará repetida en varios procesadores. Se reduce de esta forma la comunicación entre procesadores realizada en :<;1= BC7EDGFH=7JI K. Además, cada procesador dispone de información acerca de los procesadores interesados en la relevancia de cada itemset para realizar la poda de )#$-(. OTRAS ALTERNATIVAS Además del estudio realizado por Agrawal y Shafer, otros investigadores también han tratado el problema de la obtención de reglas de asociación en bases de datos distribuidas (totalmente equivalente a la paralelización de los algoritmos secuenciales de obtención de reglas de asociación). Por ejemplo, Cheung, Han, Ng, Fu y Fu proponen un algoritmo denominado LMON [P,;!?A= K_^`F!aJQS? ] que reduce la comunicación necesaria en ),I!F K1= BC7EDGFH=7JIK [)b: ] aprovechando relaciones existentes entre los itemsets relevantes localmente (en la base de datos local) y los itemsets relevantes globalmente (en la base de datos completa). En su artículo BC7EDGFH=QSR,[ea WfI BC7E= g!hiy I K6^`F!aJQS?fj, de PDIS 96, exponen distintas variantes del algoritmo: P:\TV%k"ml [P:\Tonp7E= g" I!]S;/al,BCF ], P:\TV%k"eqbl [P:\Tonp7E= g " I!]S;/a1;!K!Rrq s!spqsbc%kt`i!f K!Ril,BCF ] y P:\TV%k"mll [P:\Tunp7E= gi" I!]S;/a/l,BCF l,bcf ].!

27 !#"$!#"$%&(' )+*,.-$/$01*2&34,.-$*,.-6587:9 El algoritmo =.?6AB6C se caracteriza porque no accede a la base de datos para obtener la relevancia de los candidatos. Para ello utiliza los conjuntos auxiliares DA EFHG. Cada miembro del conjunto auxiliar DA EFHG es de la forma IAB6CKJMLONP+Q, donde cada N es un k-itemset potencialmente relevante (un candidato) presente en la transacción identificada por AB6C. Evidentemente, DA ER G se corresponde a la base de datos original en la cual cada item? es reemplazado por el itemset L6? P. El elemento de DA EFHG correspondiente a la transacción S es el par ITAB6CVU JL>WYXZDEFHG\[#WK]^SP_Q. Si una transacción no contiene ningún k-itemset candidato no tendrá una entrada en DA EFHG. ;2` =.?bs =.?6AB6C L[k] es el conjunto de itemsets relevantes que contienen k items. C[k] es el conjunto de k-itemsets candidatos. CT[k] es el conjunto de k-candidatos con sus TIDs asociados. L[1] = { large 1-itemsets } CT[1] = Base de datos D k = 2 Mientras L[k-1] d e C[k] = candidatosapriori ( L[k-1] ) CT[k] = e Para cada entrada t f CT[k-1] C t = Conjunto de candidatos de C[k] contenidos en t (usando TID) Para cada candidato c f Ct c.contador ++ Si C t d e CT[k] += <t.tid, Ct> L[k] = { c f C[k] c.contador g MinSupport } k++ Solución: h L[k]

28 La característica principal de!"$#&%(' #&%*)+*, es que, en cada iteración, se recorre el conjunto )./021 3 en vez de la base de datos completa para obtener la relevancia de los itemsets de -./43. En la generación de candidatos, el algoritmo!"$#&%(' #&%*)+*, utiliza el método ya comentado para el algoritmo!"$#&%(' #&%. El tamaño de los conjuntos auxiliares - )./43 puede llegar a ser mucho menor que el de la base de datos original tras unas cuantas iteraciones del algoritmo (para valores grandes de k), lo que ahorra esfuerzo consumido realizando operaciones de E/S. Sin embargo, para valores pequeños de k (especialmente cuando k vale 2 ó 3), las entradas correspondientes a cada transacción en - )./43 pueden ocupar más espacio que las propias transacciones en la base de datos original: los conjuntos - )./43 pueden llegar a ser mayores que la base de datos inicial para valores pequeños de k. ' #2#&566%(7 #&%BÄ CD'E Diremos que - )./43 es completo si FGABH )./43 el conjunto de itemsets AI%BA5JCLK&5Ä K incluye todos los k-itemsets incluidos en la transacción AIM)+*,. - )./43 es correcto si FGABH )./43 el conjunto de itemsets AI%BA5JCLK&5Ä K no incluye ningún k-itemset que no esté incluido en la transacción cuyo identificador es AIM)+*,. LEMA: F&/ NO1, si - )./021 3 es completo además de correcto y P./021 3 es el correcto, entonces el conjunto -$Q generado por!"$#&%(' #&%*)+*, en la iteración / es el conjunto de k-itemsets candidatos de -./43 incluidos en la transacción AIM)+*,. LEMA: F&/ NO1, si P./021 3 es el correcto y el conjunto -$Q generado por!"$#&%(' #&%*)+*, en la iteración / es el conjunto de k-itemsets candidatos de -./43 incluidos en la transacción identificada por AIM)+*,, entonces el conjunto - )./43 es correcto y completo. TEOREMA: F&/ NO1, el conjunto -$Q generado por!"$#&%(' #&%*)+*, en la iteración / es el conjunto de k- itemsets candidatos de -./43 incluidos en la transacción identificada por AIM)+*,. Primero se demuestra por inducción que RTS*UBV es correcto y WYXJS*UBV es correcto y completo para todo U[ZT\. Cuando U]\, la demostración es trivial: WYXJS&\^V se corresponde con la base de datos inicial y RTS&\^V es correcto por definición. Del primer lema obtenemos que el conjunto generado en la iteración ` a\ es el conjunto de (n+1)- itemsets candidatos de W>S*` a\^v incluidos en la transacción bdcdx&ebf. Ya que la función de generación de candidatos garantiza que W>S*` a\^vgrts*` a\^v y es el correcto, entonces RSM`ah\iV será el correcto. Del segundo lema concluimos que WYXJS*` a\^v será correcto y completo. Al ser CT[k] correcto y completo además de ser L[k] el correcto para todo kj 1, el teorema se demuestra haciendo uso del primer lema.

29 ! "$#&%(')+*, -/ $465 7(1/-893$4:1 3$4<;=<> Partamos una vez más del ejemplo de la base de datos del supermercado y 3&5 en 0.5: TID Ana Juan María Items Leche, Pan Bacon, Huevos, Patatas Huevos, Leche, Pan, Patatas Huevos, Leche, Pan Primero tendremos que generar el conjunto IKJML N$O : TID Itemsets Ana { {Leche}, {Pan} } Juan { {Bacon}, {Huevos}, {Patatas} } { {Huevos}, {Leche}, {Pan}, {Patatas} } María { {Huevos}, {Leche}, {Pan} } Obtenemos el conjunto de itemsets relevantes P9L N$O : =&5QR7TS$Q5 Support {Huevos} 3 {Leche} 3 {Pan} 3 {Patatas} 2 Generamos los itemsets candidatos de IULWVO como en -893$4:1 3$4 : =&5QR7TS$Q5 {Huevos, Leche} {Huevos, Pan} {Huevos, Patatas} {Leche, Pan} {Leche, Patatas} {Pan, Patatas}

30 En "$#&%(') tenemos: TID Itemsets Ana { {Leche,Pan} } Juan { {Huevos,Patatas} } { {Huevos,Leche}, {Huevos,Pan}, {Huevos,Patatas}, {Leche,Pan}, {Leche,Patatas}, {Pan,Patatas} } María { {Huevos,Leche}, {Huevos,Pan}, {Leche,Pan} } Creamos *+%(') : {Huevos, Leche} 2 {Huevos, Pan} 2 {Huevos, Patatas} 2 {Leche, Pan} 3 Generamos ">%(?) a partir : Obtenemos "$#&%(?) :,.-/10324/ :8<; =.-,.-/10324/- {Huevos, Leche,Pan} TID Itemsets { {Huevos,Leche,Pan} } María { {Huevos,Leche,Pan} } Finalmente conseguimos *+%(?) :,.-/10324/ :8<; =.- {Huevos, Leche,Pan} 2 Cuando se genera ">% D4) a partir obtenemos un conjunto vacío, con lo que el algoritmo termina.!

31 "$#%"$#%"&(' )+*,.-%/%01*2&34,.-%*, :,.-%; FHG2I:JLKM NPÖ Q(GSRTOVUXWYIHZ%Z.[\I:]PÖ N:[\].U^[_U ]PO`%U R:ITOGZ a1n.ubö F:ITO U RHGcSI:R:RHUVOHI:J:JBU ]\N.MVd:Ö ]eihcovu ]_csf:i:rf+ghg_ìö FHU:MVOV`jQ[\IH`j].`jRfkÖ FHG2F:I:]eQ(U RalUXWBÖ FHGhg\FHU:Z%Gm npovqvrrq9setu.tv.wpx>y{zh :}>~> H~P}>e {~P S ƒ zy{~ Px+ƒ{ Px H P}>y{z x+ zy{ ƒ ~ ~ˆ w z S~x>zH Hw ze z P S }LŠzeƒ{ S P}+~\e P { P}+ ƒ Œ~x> _z x>y }>~> Hze P}+ƒ{ \ P}L ~P S { \ zeƒe~p %v.wp Sy{~9Ž r ze~p 4o+ y{y{ x>y{ +t ƒ{ z }>y{ El algoritmo &34,.-%*, :,.-%; consiste en combinar los ].` ].` C una forma adecuada, conservando lo mejor de cada uno de ellos. En las primeras ].` se comporta mejor ].` C, ya que los C conjuntos utilizados por este último pueden ser mayores que la base de datos inicial. No obstante, cuando aumenta el número de itemsets candidatos se reduce y, mientras ].` sigue recorriendo la base de datos ].` C recorre simplemente los conjuntos C C El tamaño de los conjuntos recorridos ].` C es mucho menor que el de la base de datos completa cuando es elevado. Como norma general, se puede ].` C C en cuanto el conjunto auxiliar C quepa en memoria. Cuando cabe en memoria principal es más eficiente ].` C, ya que no tenemos que realizar operaciones de E/S sobre disco. El ].` ašd].`jj suele comportarse mejor ].` en la mayor parte de los casos, aunque la mejora puede no ser significativa (el verdadero cuello de botella de estos algoritmos se encuentra en las primeras iteraciones). de!

32 ž ª!#"$&%(')+*,%&-.-./,0,1 2' , :);2<792=<>?0,1 CEDFHGGFIKJ5L5LMF,NHJ5O8C&J5L5LMP?Q5R5F,SR LMDTLVUXWZY[\L5GDT]^F`_#DT]\GJ5abR c [\ade]^r5sdtf:igdḧ imr f5jk R ]lmfhl5fmfhln;w:j\j^r5ofhjphf,r L4qrP5N,DTjts uedvdej5]wḧ abdtlph#rxkeyer admp#hdt]ezmof,dtlmodto {LMF,SDT]\j^F h }~RxkCEDNHj^FHL5GFHOtye\ 5 # 8\ƒ CEDNHj^FHL5GFHO8uEDoDTa 8DT]Z 5 # CEYTIKJ5L5LMF,NHJ5O8CEYQ5R5F,SR LMDTLVUXWZY[^Y_#DT]\GJ5abR ĉ k k F,oF,DTLphWZN ntr ]^F ḧ i5a4jk R ]uefhj^or5sdt]^fhln;w:j\j^r5ofhjphf,r L4qrP5N,DTjts Ẁ Ẁ We[Š #?Œ;R ]\Gj\iMR džr L4 LMR mn,dtfntdmuefhj^or5sdt],}~fhl4u&jpḧ Jp J5j^DTjZ u4u # zmdtjph,hn,dto ŒbJ5j\iMFHLn hr L5O {zw:o8 P5N } 5 # 8Y En la Universidad de Helsinki, Mannila, Toivonen y Verkamo idearon un algoritmo similar al algoritmo WBde]^F,R ] F. Este algoritmo fue desarrollado independientemente del trabajo de Agrawal y Skirant en IBM y se caracteriza porque también aprovecha el hecho de que cualquier subconjunto de un itemset relevante es a su vez un itemset relevante. yšu We[\z Como se verá a continuación, el algoritmo supone una mejora respecto al algoritmo pero no es superior al algoritmo WBde]^F,R ]^F yšu. difiere del ya expuesto WBde]^F,R ]^F en dos aspectos: la forma de obtener los conjuntos de candidatos y G9š yšu y la estructura de datos empleada ( no utiliza como estructura de datos un árbol hash). DTLMDT]\JMoF,œ L&fMDoTJ5L5fMFHf5JphR jmdtl yšu El conjunto de candidatos y G9š { G} FHLMoN,P^}tDrG:abF,DTa ]^R j`fmd \GT9 š es el conjunto MžŸ že. Esta no es más que una forma alternativa de expresar que cualquier subconjunto de un itemset relevante es también un itemset relevante. De hecho, un elemento del conjunto GM `D š + incluye k-itemsets relevantes de G9š. Como caso particular, un itemset relevante de GM š debe incluir exactamente (k+1) itemsets de G9š + 1 : ª = + 1 ª ª Utilizando la misma propiedad podemos llegar a otro resultado interesante. Podemos afirmar que el conjunto GM `D š de itemsets relevantes estará vacío si \G«š + contiene menos de ª k-itemsets relevantes. yšu Los autores del algoritmo propusieron dos fórmulas alternativas de obtener el conjunto de candidatos y G9š, siendo la segunda opción más restrictiva. En la primera de las alternativas se obtienen los candidatos potenciales y G9š a partir de elementos de \GT9 š y š, mientras que en la segunda se obtienen a partir de pares de itemsets de G\ š que tengan HG«items en común.

33 ! ; "$#&%('*)+#-,.,0/21)+#-34,51%76+, C [k] = { X8 Y X 9 L[k-1] & Y 9 L[1] & Y : X } C[k] = { X X en C [k] & X contiene k miembros de L[k-1] } <0)&=?> C [k] = { X8 Y X,Y 9 L[k-1] & #(XA Y) = k-2 } C[k] = { X X en C [k] & X contiene k miembros de L[k-1] } Las dos alternativas propuestas tienen en común la segunda parte, la generación del conjunto final de candidatos BCDFE eliminando aquéllos k-itemsets que no incluyen k miembros del conjunto de itemsets relevantes GC-D+HFIJE. Esta restricción es equivalente a la poda del conjunto C[k] que se realiza en el algoritmo KML$#&%7N #&% : se eliminan de BCDFE a priori aquellos k-itemsets que incluyen algún (k-1)-itemset no incluido en GCDH-I E ya que el k-itemset nunca puede llegar a ser un itemset relevante. Para el paso inicial de la generación de candidatos, Mannila, Toivonen y Verkamo proponen dos formas de obtener el conjunto BPO CDFE, siendo la segunda opción más restrictiva. El conjunto generado por la primera alternativa es un superconjunto del generado por la segunda. A su vez, el conjunto BPO CDFE generado por la segunda alternativa propuesta es un superconjunto del conjunto creado por KML$#&%7N #&% en la primera fase de la generación de BQCRD-E (antes de la eliminación de aquellos posibles candidatos que incluyen algún S(DH-IUT -itemset no perteneciente a GCDH-I E ). Por lo tanto, el algoritmo VWBYX no es mejor que KML$#&%7N #&%. 6&=YZ Retomemos el ejemplo propuesto al exponer el algoritmo KML$#&%7N #&%. Partiendo del conjunto de itemsets relevantes GC+[&E]\_^^-I.à[ b4cu^-i.àd b4cu^-ie[fd b4cu^-ie[eg&b4cu^hà[fd bb se obtiene, aplicando el método utilizado por el algoritmo KML$#&%7N #&% o cualquiera de las alternativas propuestas para VWBYX, el conjunto de candidatos BC+d&Ei\j^^-IWè[.d bb. La diferencia estriba en el conjunto BPO C+d&E. Si utilizamos la primera opción propuesta para VBYX, BPO C+d&E incluirá ^-Ik`l[Wd b, ^-Ik`l[g&b, ^-Ik`ldg&b, ^-I[Wdg&b y ^h`l[wdg&b. Si utilizamos la segunda técnica descrita deberíamos incluir en el conjunto auxiliar BPO C+d&E los itemsets ^-Ik`l[WdJb, ^-I`.[Wg&b y ^-Il[.dlg&b, los cuales se pueden derivar de las uniones de itemsets relevantes ^-Il`f[ b m ^-IWèd b, ^-I`.[ b m ^-IW[Wg&b y ^-IW[ld b m ^-IW[Wg&b, respectivamente. En KML$#&%7N #&%, el conjunto equivalente a BPO C+d&E contendría únicamente a los itemsets ^-IWè[.d b y ^-Il[.dlg&b.

SitemapDeutschland 83 - Season 2 | Danganronpa 3 The End of Hopes Peak High School Future Arc (12) | 1 12 The Crucible Quotes