Introducción a los algoritmos de minería de reglas de asociación

Introducción de vaca anidada El algoritmo de minería de reglas de asociación es un algoritmo comúnmente utilizado en la minería de datos, que se utiliza para descubrir patrones, asociaciones y correlaciones interesantes y frecuentes ocultas en grandes datos. conjuntos. El algoritmo se presentará brevemente aquí y luego se utilizará el algoritmo Apriori como ejemplo para demostrar los resultados de ejecución del algoritmo.

Python de minería de reglas de asociación de minería de datos de nariz de vaca anidada

Cuerpo de vaca anidado

1. Principio del algoritmo

1. Conceptos básicos

p>

Las reglas de asociación se utilizan para descubrir patrones, asociaciones y correlaciones frecuentes e interesantes ocultos en grandes conjuntos de datos. El algoritmo Apriori es un algoritmo de reglas de asociación clásico para extraer conjuntos de elementos frecuentes. Encuentra conjuntos de elementos frecuentes mediante iteración capa por capa y finalmente genera reglas de asociación: primero, escanea el conjunto de datos para obtener 1 conjunto de elementos frecuentes, registrado como L1. , y luego obtenga 2 fusionando L1 con el conjunto de elementos frecuentes L2, y luego encuentre de L3 a L2, e itere capa por capa hasta que no se encuentre ningún conjunto de elementos frecuentes.

En el algoritmo Apriori se definen los siguientes conceptos:

? Elementos y conjuntos de elementos: Sea I={i1,i2,...,im} compuesto por m elementos diferentes. Un conjunto de elementos, donde cada ik (k = 1,2,..., m) se denomina elemento, y el conjunto I de elementos se denomina conjunto de elementos y conjunto de elementos. En el experimento, cada registro de compra puede considerarse como un conjunto de artículos y el producto comprado por el usuario es un artículo.

?Transacciones y conjuntos de transacciones: la transacción T es un subconjunto del conjunto de elementos I, y la transacción completa se denomina conjunto de transacciones.

?Reglas de asociación: expresiones, como A=>B, donde A y B pertenecen al conjunto de elementos I, y A y B no se cruzan.

?Soporte: Se define de la siguiente manera: soporte(A=>B) = P(A B), es decir, la probabilidad de que los términos contenidos en A y B aparezcan juntos en el conjunto de transacciones.

?Confianza: definida de la siguiente manera: confianza(A?B) = soporte(A?B)/soporte(A) = P(A B)/P(A B) = P(B|A), Es decir, si A está incluido en la transacción, la probabilidad de que B aparezca simultáneamente en la transacción.

? Conjunto de elementos frecuentes: si el soporte del conjunto de elementos I satisface el umbral de soporte mínimo predefinido (es decir, la frecuencia de aparición de I es mayor que el umbral de frecuencia mínimo correspondiente), entonces I es un conjunto de elementos frecuentes.

?Reglas de asociación fuertes: reglas de asociación que cumplen con el soporte mínimo y la confianza mínima, es decir, las reglas de asociación que se van a extraer.

De acuerdo con los conceptos anteriores, para implementar la minería de reglas de asociación, primero debemos encontrar todos los conjuntos de elementos frecuentes y luego encontrar reglas de asociación sólidas (es decir, escanear el conjunto de datos varias veces para encontrar conjuntos frecuentes y luego generar regla de asociaciones).

2. Minería de conjuntos de elementos frecuentes

En este paso, hay dos partes importantes: conexión y poda. El paso de conexión utiliza k-1 conjuntos de elementos frecuentes y obtiene k conjuntos de elementos candidatos a través de la conexión. Solo se pueden conectar conjuntos de elementos que difieren en un elemento. Por ejemplo, {A, B} y {B, C} se conectan para convertirse en {. A, B, C}. El paso de poda se basa en la propiedad de que un conjunto de elementos k no puede ser un conjunto de elementos frecuentes si uno de sus conjuntos (subconjuntos) de elementos k-1 no es un conjunto de elementos frecuentes. Por lo tanto, el conjunto candidato se puede podar en función de este atributo determinando el atributo a priori.

3. Generar reglas de asociación

Después de la conexión y la poda, es decir, hemos encontrado todos los conjuntos de elementos frecuentes y luego podemos generar reglas de asociación basadas en esto, el específico Los pasos son los siguientes

(1) Para cada conjunto de elementos frecuentes l, genere todos los subconjuntos no vacíos de l (estos subconjuntos no vacíos deben ser conjuntos de elementos frecuentes);

(2) Para cada subconjunto no vacío de l, calcule la confianza (x), luego la confianza (x) y luego la confianza (x).

Supongamos x, calcule la confianza (x => (l-x)). Si la confianza (x => (l-x)) es mínima, entonces se establece la regla x => (l-x)".

2. Diseño de algoritmos

1. Conjunto de datos

Importe la biblioteca relevante para leer los datos a través de la declaración import xlrd. El contenido de los datos son diez registros de compras. Cada registro de compras tiene un número de producto. que representa el registro de compra de un cliente, como se muestra en la figura

Para la parte de carga de datos, use la función de biblioteca xlrd open_workbook para abrir un archivo de tabla, use la función Sheet_by_index para obtener una hoja de trabajo y los valores de fila. La función lee el contenido de la tabla. La cantidad de elementos no es necesariamente la misma, lo que hace que el contenido leído contenga espacios (''), por lo que estos datos deben eliminarse para obtener datos compactos y los resultados de la lectura. los datos finalmente se devuelven en forma de lista.

2. Conexión

El objetivo principal de la parte de conexión es generar k conjuntos de elementos frecuentes candidatos basados ​​en el k-1 existente. conjuntos de elementos frecuentes Los pasos del algoritmo son: primero, ordenar los elementos en el orden del diccionario, y luego comparar dos elementos del conjunto de elementos k-1. los dos conjuntos de elementos son iguales y se pueden conectar mediante la operación OR (|)

La operación de poda utiliza principalmente la función de juicio Pasando el. conjunto de elementos después de la operación de conexión y los primeros conjuntos de elementos frecuentes k-1, se juzga el complemento de cada elemento en el nuevo conjunto de elementos. Si el complemento no es un subconjunto de conjuntos de elementos frecuentes k-1, se demuestra que es el nuevo. itemset no satisface la propiedad anterior de que todos los subconjuntos no vacíos de conjuntos de elementos frecuentes deben ser conjuntos de elementos frecuentes; de lo contrario, satisface los parámetros booleanos para que los utilice la función que lo llama para su juicio. Pasos de conexión y poda, la base de elementos que se convierte en un conjunto de elementos frecuentes también debe cumplir con las condiciones mínimas de soporte. Diseñé la función generateFrequentItems para hacer esto. Después de la concatenación y la poda, se juzgan los k conjuntos de elementos candidatos y se calcula la tasa de soporte. atravesar el conjunto de datos El conjunto de elementos que cumple con el soporte mínimo es el conjunto de elementos frecuentes y se puede devolver a él.

Después del recorrido continuo, la conexión, la poda y la eliminación, se pueden obtener todos los resultados. devuelto en forma de lista. El autor también diseñó una variable de tipo diccionario support_data para obtener un determinado conjunto de elementos frecuentes y su soporte.

4. Reglas de asociación minera

Las reglas de generación (generateRules). La función se utiliza para generar reglas pasando la confianza mínima, conjuntos de elementos frecuentes y sus soportes, extrayendo así reglas de asociación de acuerdo con el teorema: para conjuntos de elementos frecuentes l Para cada subconjunto x no vacío, calcule la confianza (x => (l-x). )). Si la confianza (x => (l-x)) confmin, entonces la regla x => (l-x) " se cumple, por lo que esta función se centra en escanear con frecuencia el conjunto de elementos para obtener cada subconjunto, calcular la confianza y generar reglas cuando el la confianza cumple la condición (es decir, mayor o igual que la confianza mínima). En esta función, se usa una tupla para representar una regla, la tupla contiene x, l-x y su confianza, y finalmente se devuelve una lista de todas las reglas generadas.

3. Resultados de la ejecución del algoritmo

Establezca el número máximo de conjuntos de elementos frecuentes k en 3, el soporte mínimo en 0,2 y la confianza mínima en 0. 8 Utilice pycharm para ejecutar el programa y obtenga los siguientes resultados:

Se puede ver en los resultados de la figura que para el conjunto frecuente de 1 elemento, hay 5 conjuntos de elementos que cumplen las condiciones, hay 6 conjuntos frecuentes de 2 elementos y hay 2 conjuntos frecuentes de 3 elementos. Todos ellos son Si la tasa de soporte es mayor o igual a l-x, finalmente devuelve la lista de todas las reglas generadas. Todos cumplen con el requisito de que el soporte sea mayor o igual al soporte mínimo de 0,2.

Según el conjunto de elementos frecuentes, el programa obtuvo tres reglas de asociación, a saber, {pan}=>{leche}, {huevos}=>{leche},, {pan, manzana}=>{leche, entre las cuales la confianza de todos estas reglas Ambas son 1.0, lo que cumple la condición de ser mayor o igual al nivel de confianza mínimo de 0.8.

IV.Código fuente del programa