1. Análisis de Afinidad y Canasta de Mercado
    1. Análisis de afinidad es el estudio de atributos o características que tienden a 'ir juntos'.
    2. Busca descubrir y cuantificar las relaciones entre uno o más atributos.
    3. Las reglas de asociación son de la forma Si ANTECEDENTE entonces CONSECUENTE
    4. Existen dos criterios asociados a cada reglas
      1. El soporte es la probabilidad de que el antecedente y el consecuente sucedan juntos.
      2. La confianza es la covertura o precisión que tiene el consecuente sobre el antecedente.
    5. Ej: De 1000 clientes de una tienda, 200 compraron pañales y de esos 200, 50 también compraron cerveza. La regla de asociación sería...
      1. Si compra pañales entonces compra cerveza.
      2. con soporte 50 / 1000 = 5%.
      3. y confianza 50 / 200 = 25%.
    6. Algunos ejemplos de aplicación...
      1. Investigar la proporción de subscriptores a una compañia de teléfonos que aceptarán una actualización del servicio.
      2. Predecir la degradación en redes de telecomunicaciones.
      3. Encontrar que productos son y no son comprados juntos en los supermercados.
      4. Determinar la proporción de casos en que un nuevo medicamento pueda presentar efectos secundarios nocivos.
      5. Identificar los patrones de comportamientos de los usuarios de una página web.
      6. Proveer alternativas a los saltos dentro de cadenas de ADN.
    7. El problema de la dimensionalidad.
      1. El gran desafio que afrontan los algoritmos de reglas de asociación es la maldición de la dimensionalidad.
      2. El número de posibles reglas de asociación crece exponencialmente según el número de atributos.
      3. Dado k atributos el número de posibles reglas viene dado por ...
      4. Si una tienda tiene un stock de productos de 100 artículos el número de reglas viene dado por ...
  2. Representación de los datos
    1. DataSet Veggies 4 Sale
      1. 1
        1. Broccoli, green peppers, corn
      2. 2
        1. Asparagus, squash, corn
      3. 3
        1. Corn, tomatoes, beans, squash
      4. 4
        1. Green peppers, corn, tomatoes, beans
      5. 5
        1. Beans, asparagus, broccoli
      6. 6
        1. Squash, asparagus, beans, tomatoes
      7. 7
        1. Tomatoes, corn
      8. 8
        1. Broccoli, tomatoes, green peppers
      9. 9
        1. Squash, asparagus, beans
      10. 10
        1. Beans, corn
      11. 11
        1. Green peppers, broccoli, beans, squash
      12. 12
        1. Asparagus, beans, squash
      13. 13
        1. Squash, corn, asparagus, beans
      14. 14
        1. Corn, green peppers, tomatoes, beans, broccoli
    2. Transaccional
      1. Generalmente utilizados en SGBD relacionales.
      2. Topic
    3. Tabular
      1. Facilitan los cálculos pero no son recomendadas para varios atributos.
      2. Topic
  3. El algoritmo Apriori
    1. Introducido en 1994 por Agrawal y otros en el IBM Almaden Research Center.
    2. Itemsets
      1. Sea Si A entonces B, A y B son dos subconjutos de I mutuamene excluyentes.
        1. A = {beans, squash}
        2. B = {asparagus}
      2. A y B son conocidos como itemsets según el número de items que poseen.
        1. {asparagus} es un itemset tipo 1
        2. {beans, squash} es un itemset tipo 2
        3. {broccoli, green peppers,corn} es un itemset tipo 3
      3. El número de apariciones de cada itemset en el conjunto se conoce como el conteo (o soporte) del itemset.
        1. {beans}.count = 10
        2. {beans, squash}.count = 6
      4. Cuando el conteo del itemset supera el soporte establecido, a este itemset se lo denomina un itemset frecuente.
    3. Soporte y Confianza
      1. El soporte de una regla viene dado por...
      2. La confianza de la regla viene dado por ..
    4. Minar reglas de asociación tiene dos pasos ...
      1. Apartir de todos los itemset frecuentes (large itemset) es posible formular las reglas de asociación.
      2. Aquellas reglas que superan el criterio de confianza son conocidas como reglas fuertes (strong rules) y son desplegadas al usuario final.
      3. Encontrar todos los itemsets frecuentes.
      4. Generar las reglas a partir de los itemsets frecuentes encontrados.
    5. La propiedad Downward Closure.
      1. Todos los subconjuntos de un itemset frecuente tipo k deben ser tambien itemsets frecuetnes tipo k-1
      2. Esto restringe considerablemente el campo de busqueda y reduce el problema de dimensionalidad.
    6. Pseudocodigo
  4. ¿Como funciona Apriori? 1ra Parte: generación de itemsets frecuentes.
    1. Soporte = 4
    2. Empezamos con los itemsets candidatos tipo 1 contando su frecuencia en el conjunto.
      1. asparagus 6
      2. beans 10
      3. broccoli 5
      4. corn 8
      5. green peppers 5
      6. squash 7
      7. tomatoes 6
    3. A partir de los itemsets frecuentes tipo 1 generamos los itemsets candidatos tipo 2 y contamos su frecuencia.
      1. Asparagus, beans 5
      2. Asparagus, broccoli 1
      3. Asparagus, corn 2
      4. Asparagus, green peppers 0
      5. Asparagus, squash 5
      6. Asparagus, tomatoes 1
      7. Beans, broccoli 3
      8. Beans, corn 5
      9. Beans, green peppers 3
      10. Beans, squash 6
      11. Beans, tomatoes 4
      12. Broccoli, corn 2
      13. Broccoli, green peppers 4
      14. Broccoli, squash 1
      15. Broccoli, tomatoes 2
      16. Corn, green peppers 3
      17. Corn, squash 3
      18. Corn, tomatoes 4
      19. Green peppers, squash 1
      20. Green peppers, tomatoes 3
      21. Squash, tomatoes 2
    4. Para generar candidatos tipo 3 (k) a partir de los frecuentes tipo 2 (k -1), emparejamos los itemsets cuyos k-1 items sean iguales ...
      1. {asparagus, beans, squash} se genera a partir de ...
        1. {asparagus, beans}
        2. {asparagus, squash}
      2. {asparagus, beans, squash, tomatoes} a partir de ...
        1. {asparagus, beans, squash}
        2. {asparagus, beans, tomatoes}
    5. En este paso verificamos si los itemsets candidatos cumplen con la propiedad Downward closure. Aquellos que no pasen la propiedad son podados y nos ahorramos el conteo de su frecuencia.
    6. En este caso, este seria el conjunto de itemsets candidatos tipo 3 ...
      1. asparagus, beans, squash 4
      2. beans, corn, squash NA
        1. No es frecuente porque {corn, squash} no es frecuente
      3. beans, corn, tomatoes 3
      4. beans, squash, tomatoes NA
        1. No es frecuente porque {squash, tomatoes} no es frecuente
    7. Lista completa de itemsets frecuentes.
      1. {Asparagus} 6
      2. {Beans} 10
      3. {Broccoli} 5
      4. {Corn} 8
      5. {Green Peppers} 5
      6. {Squash} 7
      7. {Tomatoes} 6
      8. {Asparagus, Beans} 5
      9. {Asparagus, Squash} 5
      10. {Beans, Corn} 5
      11. {Beans, Squash} 6
      12. {Beans, Tomatoes} 4
      13. {Broccoli, Green Peppers} 4
      14. {Corn, Tomatoes} 4
      15. {Asparagus, Beans, Squash} 4
  5. ¿Como funciona Apriori? 2da Parte: generación de reglas.
    1. Algoritmo
      1. Primero generamos todos los subconjuntos no vacios ss de un itemset frecente s
      2. Para cada ss generamos una reglas de la forma Si ss entonces (s - ss)
      3. Solo las reglas que superan la confianza establecia serán desplegadas.
    2. Ejemplo
      1. Dado s = {asparagus, beans, squash} tenemos los siguiente subconjuntos ...
        1. {asparagus}
        2. {beans}
        3. {squash}
        4. {asparagus, beans}
        5. {asparagus, squash}
        6. {beans, squash}
      2. Si ss = {asparagus, beans}, entonce (s – ss) = {squash}
      3. obtenemos la regla... Si compra asparagus y beans entonce compra squash donde ...
        1. Soporte = {asparagus,beans,squash}.count / Total número de transacciones = 4 / 14 = 28.6%
        2. Confianza = {asparagus,beans,squash}.count / {asparagus,beans}.count = 4 / 5 = 80%
      4. Las reglas con un solo consecuente para s serían
      5. Encontrar el soporte y la confianza para la regla Si compra beans entonces compra asparagus y squash
      6. Reglas desplegadas
        1. Lista de reglas de asociación con un solo antecedente y consecuente.
        2. Lista final de reglas de asociación con confianza minima del 80%
  6. Usando Weka para encontrar reglas de asociación.
    1. Conjunto Veggies 4 Sale
      1. Cargar el archivo veggies.csv en Weka.
      2. Eliminar el atributo Transaction.
      3. Aplicar el filtro NumericToBinary y guardar el nuevo conjunto como veggiesNumericToBinary.arff
      4. Usando un editor de texto explorar las características del formato ARFF.
      5. Aplicar el algoritmo Apriori en la pestaña Associate con los parametros por defecto. ¿Qué interpretación se pueda dar a estas reglas?
      6. En la sección @data del archivo .arff cambiar los valores de '0' por el de '?'.
      7. Aplicar de nuevo el algoritmo Apriori con los siguientes parametros.
        1. lowerBoundMinSupport=0.28
        2. metricType=Confidence
        3. minMetric=0.8
        4. outputItemSets=True
    2. Conjunto Churn
      1. Aunque no es común las reglas de asociación también son aplicables a conjuntos multivariables.
      2. Cargar el archivo churn.csv
      3. Eliminar las columnas State, Account Length, Area Code, Phone, Day Charge, Eve Charge, Night Charge, Intl Charge.
      4. Usando el filtro Discretize discretizar los atributos numéricos usandos ...
        1. 3 bins para el atributo VMail Message(3).
        2. 5 bins para los atributos de Day Mins (4) a Intl Calls (11).
      5. Aplicar el filtro NumericToNominal al Atributo CustServ Calls (12).
      6. Aplicar el algoritmo Apriori con los siguientes parametros...
        1. car=True
        2. delta=0.01
        3. lowerBoundMinSupport=0.01
        4. upperBoundMinSupport=0.15
        5. metricType=Confidence
        6. minMetric=0.70
        7. numRules=100
        8. outputItemSets=False