[MÚSICA] Bienvenidos a un nuevo video de nuestro curso de Minería de datos. Hoy continuaremos con el algoritmo a priori. El objetivo principal de este video es explicar en detalles cómo funciona la generación de itemsets candidatos en todas las iteraciones del algoritmo. [AUDIO_EN_BLANCO] En el video anterior, vimos cómo generar itemsets de tamaño dos, a partir de la combinación de itemsets de tamaño uno. También vimos cómo generar itemsets de tamaño tres a partir de la combinación de itemsets de tamaño dos. ¿Cómo lo hacemos, entonces, para generar itemsets de tamaño K+1 a partir de la combinación de itemsets de tamaño K? Lo primero que debemos hacer es definir un orden entre todos los productos. Este orden es totalmente arbitrario, pero debe ser respetado a lo largo del algoritmo, usualmente se llama orden lexicográfico. Aquí tenemos un ejemplo de un orden lexicográfico arbitrario, definido para la lista de productos que vemos en pantalla. Notar que el orden debe estar definido para todos los productos de nuestra base de datos. Una vez que tenemos definido el orden lexicográfico entre nuestros productos, podemos, entonces, definir el criterio para decidir cuándo dos conjuntos frecuentes pueden combinarse para formar un nuevo itemset de tamaño mayor en un producto. Lo primero que debemos hacer antes de ver si dos itemsets pueden o no combinarse, es ordenar los productos dentro de cada itemset, según el orden previamente definido. Vemos en pantalla, entonces, que el itemset Manzana, Naranja y Pera queda como Manzana, Pera y Naranja, y el itemset Plátano, Manzana y Pera queda como Manzana, Pera y Plátano. Para chequear si dos itemsets pueden combinarse o no, el criterio es, comparamos de izquierda a derecha el primer producto del itemset A con el primer producto del itemset B, y debemos chequear de que sean iguales. Luego, comparamos el segundo producto del itemset A con el segundo producto del itemset B, y también debemos chequear de que sean iguales. Finalmente, comparamos el último producto del itemset A con el último producto del itemset B, y aquí debemos chequear que el último ítem del itemset A debe ser menor en el orden lexicográfico que el último producto en el itemset B. En este caso, vemos que se cumple, you que la Naranja tiene una posición menor que el Plátano en el orden previamente definido. En resumen, dos itemsets son combinables si es que todos sus productos son iguales menos el último y, además, el último producto del itemset A debe ser menor que el último producto del itemset B, según el orden lexicográfico. La combinación de dos itemsets es realizada a través de la operación llamada Join. Esta operación es bastante simple, lo único que se hace es generar un itemset nuevo que contiene la unión de los itemsets A y B. No olvidar que esta operación debe realizarse solamente entre itemsets que cumplen con la condición señalada anteriormente. Recién vimos cómo combinar dos itemsets, ¿cómo lo hacemos si tenemos M itemsets que combinar? Para combinar M itemsets, debemos realizar el Join del conjunto de itemsets consigo mismo. Esto en palabras simples significa que chequearemos todos los pares posibles de itemsets y combinaremos todos los que son combinables. En la siguiente diapositiva veremos un ejemplo. El primer par posible podría ser el itemset I1 repetido dos veces. Tal como lo hicimos antes, procedemos a chequear si estos dos itemsets son combinables o no. Vemos que dos itemsets iguales no son combinables, you que no cumplen con la condición de que el último elemento del itemset A debe ser menor en el orden que el último elemento del itemset B. Aquí son iguales. Podemos intuir, entonces, que un itemset nunca podrá ser combinado consigo mismo. Luego, procedemos a comparar el segundo par posible, debemos ver si son combinables o no. Y así seguimos probando todos los posibles pares de itemset y combinando los que cumplen con la condición. Una vez que combinamos todos los pares de itemset de tamaño K, que se pueden combinar, se termina el proceso de generación de candidatos de tamaño K+1. En este video aprendimos cómo se generan los itemsets candidatos de tamaño K+1 a partir de los itemsets de tamaño K, en el algoritmo a priori.
