El algoritmo Apriori tienen como objeto, la extracción de un conjunto de reglas, inducidas desde un conjunto de prueba, entregado como entrada. Reglas de asociación son:
Tal definición define lo que es la intuición de la ocurrencia de cierto parámetro dado la ocurrencia de otros parámetros en sus alrededores.
Ej.
Defecto_Ocular = Miopía usa_Lentes = SI
La
regla general:
Donde son atributos de una transacción dada.
Se dice que predicen a
Hay varios parámetros asociados al algoritmo Apriori. Estos incluyen
Soporte
Dado
una regla, la confianza es el porcentaje de registros para el cual
se encuentra Y, dentro del total de registros en que se
encuentra
Un ejemplo de lo anterior sería
|
ID |
Items
|
|
|
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
Dada la regla
El soporte es : 3/7
La confianza es : 3/4
¿Cómo se extrae un conjunto de reglas significativas de un conjunto de transacciones?
Dado un conjunto de transacciones, generalmente extraídos desde una Base de Datos, se sigue los siguientes pasos
Se leen todas las transacciones, encontrando todas los ítems que tienen soporte sobre el valor definido como mínimo. Este conjunto se denominará L1.
Se construye pares desde el conjunto L1. Este será el Conjunto C2. Se leen las transacciones otra vez, y se encuentran todos los pares con ocurrencias frecuentes en C2. Este será L2.
El algoritmo sigue de manera idéntica, construyendo vectores de tamaño K desde el conjunto Lk-1, el cual se denominará Ck. Se leen las transacciones otra vez, y se encuentran los vectores de ocurrencias frecuentes, denominando a este Lk.
Se encuentran todos los conjuntos posibles de la misma manera.
El algoritmo se detalla a continuación
Apriori ()
{
F = Æ ;
Lk = {conjuntos unarios frecuentes};
k = 2;
while (Lk-1 != Æ )
{
F = F U Lk ;
Ck = Nuevos candidatos de tamaño k generado desde Lk-1 ;
for todas las transacciones t Î D
incrementar el conteo de todos los candidatos dentro de Ck que estan contenidos en t ;
Lk = Todos los candidatos en Ck con el soporte mínimo;
k++ ;
}
return ( F ) ;
}
Copyright Nelson Flores 2001™.