Este artículo proviene de un motor de traducción automática.
Ejecución de pruebas
Aprendizaje de reglas de asociación
Descargar el código de muestra
.jpg)
Asociación regla el aprendizaje es una técnica en el campo de aprendizaje de máquina que extrae las reglas si-entonces de un conjunto de datos. Por ejemplo, si los datos están estudiando están un conjunto de transacciones de supermercado, una regla de asociación podría ser, "Si un cliente compra café y manzanas entonces hay una alta probabilidad que comprará también mantequilla y donuts."
Existen varios tipos de reglas de asociación. Este artículo explica cómo extraer las reglas de alta confianza, que se caracterizan por ser verdadero en un mínimo porcentaje especificado de las transacciones está analizando. Aprendizaje de reglas de asociación puede aplicarse a muchas clases de datos además de adquirir transacciones, incluyendo archivos de registro de sistema, las consultas de búsqueda del usuario y comandos de interfaz de usuario naturales. Este artículo explica la regla de asociación alta confianza cómo aprender obras y presenta un programa de demostración completo.
La mejor manera de ver hacia dónde se dirige este artículo es echar un vistazo al programa de demostración en figura 1. La demo se configura 10 transacciones ficticia, codificadas para que cada elemento es un valor basado en 0. Por ejemplo, es la primera transacción (0 3 4 11), lo que significa que artículos de 0, 3, 4 y 11 se presentan juntas. En la mayoría de los casos, se permiten transacciones duplicadas, como las transacciones 2 y 3.
.png)
Figura 1 encontrar las reglas de Asociación de alta confianza
Aunque puede realizar una búsqueda de reglas de Asociación de alta confianza directamente sobre los datos de transacciones codificadas, en situaciones más sets frecuentes de objetos son primero extraídas de las transacciones. Un artículo-set es un subconjunto de todas las operaciones posibles y frecuentes-sets de objetos son los que reúnen a un número mínimo de ocurrencias (llamado el nivel de soporte) especificado por el usuario en el conjunto de las transacciones. En la demo, utilizando un valor de apoyo de 0.30 (así un artículo-set debe ocurrir en por lo menos 0.30 * 10 = 3 transacciones), hay ocho conjuntos elemento frecuentes. El primero es (2 5). Artículos 2 y 5 se presentan juntas en tres operaciones: 7, 8 y 9. Conjuntos de punto frecuentes eliminan transacciones atípicas que puedan generar una regla muy alta confianza pero son tan raras, que la regla no es particularmente relevante. En la mayoría de los casos sets frecuentes de objetos son distintas, no duplicados permitido. Extraer elemento frecuentes-conjuntos de transacciones es una tarea muy difícil. Ver "Frecuentes Sets de objetos para Asociación regla de aprendizaje" en la MSDN Magazine en enero de 2013 msdn.microsoft.com/magazine/dn519928.
Detrás de las escenas, la demo utiliza la lista de conjuntos de elemento frecuentes para generar reglas de candidato. Cada regla de candidato es evaluado para determinar si la regla cumple un umbral mínimo de probabilidad llamado el valor confianza suministrados por el usuario. Esas reglas de candidatos que cumplan o superen el nivel de probabilidad se identifican como high -reglas de confianza. En la demo, se establece el valor de la confianza en 0.700, que significa que una regla del candidato debe ser verdad por lo menos el 70 por ciento de las transacciones para que la regla es aplicable.
En la demo, se encontraron 16 reglas de alta confianza. La primera regla listada es IF (2) y (5), con un valor calculado de 0.75 confianza. Usted puede pensar esto como, "Si una transacción tiene punto 2, entonces la transacción probablemente también contiene artículo 5". La parte de IF de la regla, que se llama el antecedente, se aplica a cuatro operaciones: 6, 7, 8 y 9. La regla es válida para tres de las cuatro operaciones: 7, 8 y 9, así que la confianza computada es 3/4 = 0.75.
Observe que las reglas de alta confianza no son necesariamente simétricas. No si no hay (5) y (2) la regla porque esa regla es aplicable a las transacciones 1, 4, 5, 7, 8 y 9, pero es verdad sólo para transacciones de 7, 8 y 9, así que el valor de la confianza de 3/6 = 0,50 no conoce el valor mínimo de 0.700.
Este artículo asume que ha avanzado conocimientos de programación pero no asume que sabe algo sobre el aprendizaje de reglas de asociación. El programa de demostración está codificado usando C#, pero usted debe ser capaz de refactorizar el código a otros lenguajes .NET como Visual Basic o IronPython sin demasiada dificultad. Comprobación de errores más normal se ha eliminado para mantener el tamaño del código pequeño y las principales ideas claras. El código fuente completo para el demo se presenta en este artículo y el código también está disponible como una descarga de msdn.microsoft.com/magazine/msdnmag0514.
El algoritmo de detección de regla
El algoritmo utilizado por el programa de demostración para encontrar las reglas de alta confianza se ilustra en la figura 2. El diagrama muestra cómo es frecuente tema-set (3 4 7) genera dos normas de alta confianza y cuatro de alta confianza. El algoritmo comienza por generar todas las combinaciones matemáticas de tamaño k = 1 a tamaño artículo conjunto longitud - 1. Combinaciones matemáticas son la clave para la regla de asociación aprendizaje algoritmo presentado en este artículo. Una combinación matemática es un conjunto de números que representa un subconjunto. Por ejemplo, si hay 5 elementos = (0, 1, 2, 3, 4) y el tamaño de subconjunto k 3, los 10 elementos de las combinaciones posibles son:
(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 2, 3)
(0, 2, 4)
(0, 3, 4)
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)
.png)
Figura 2 algoritmo para encontrar las reglas de alta confianza
Los elementos en una combinación matemática no son objetos de transacción, son sólo números. En figura 2, cada combinación se aplica a las frecuentes artículo conjunto para generar un subconjunto del elemento-set, que se interpreta como el antecedente (if-part) de una regla de candidato. Por ejemplo, la última combinación para k = 2 es (1, 2) de manera que los elementos en el conjunto del artículo frecuente (3 4 7) en los índices 1 y 2 se utilizan como el antecedente de la regla de candidato: "IF (4 7)." La parte entonces de la regla de candidato consta de esos elementos en el conjunto de elemento siendo examinado que no se utilizan en la parte de if. Así para el conjunto de elemento (3 4 7), si el antecedente (4 7), la parte entonces (llamada el consiguiente) es (3), y la regla completa candidato es "IF (4 7) entonces (3)."
Sorprendentemente, la parte entonces de una regla del candidato no es necesario calcular el valor de confianza de la regla. Consideran que la regla del candidato (4 7) entonces (3). Para calcular la confianza, es necesario un recuento de las transacciones a las que la regla es aplicable. Estos serían aquellas transacciones que contienen los artículos 4 y 7, que en el caso de la demo es 3 (operaciones en 2, 3 y 6). La segunda parte de la computación necesitada es el número de transacciones aplicables para que la regla de candidato es cierto, en otras palabras, aquellas transacciones que tienen los artículos 4, 7 y también el punto 3. Pero esto es sólo el número de transacciones que contienen la fuente frecuente tema-set (3 4 7).
En figura 2, se calculan los valores de confianza para cada una de las reglas de seis candidatos, y los cuatro que cumplan el límite de confianza se identifican como normas de alta confianza.
Para resumir, a partir de un conjunto de frecuentes-sets de objetos que cumplan con un nivel de soporte mínimo de frecuencia de ocurrencia, para cada elemento frecuente, se generan todas las combinaciones matemáticas de tamaño 1 a través de uno menos que el número de elementos en el conjunto de elemento. Cada combinación determina una parte de IF y una parte entonces de una regla de candidato. Reglas de candidatos que cumplan con un nivel mínimo de confianza, que es la proporción de aplicables frecuentes-sets de objetos para que la regla es cierto, son etiquetadas como buenas reglas (alta confianza) y salvadas.
Estructura general del programa
Para crear el programa de demostración lancé Visual Studio. El programa de demostración no tiene significativa .NET dependencias y cualquier versión de Visual Studio que soporta Microsoft .NET Framework 2.0 o posterior debería funcionar bien. Creé un programa de aplicación de consola de C# y el nombre AssocRuleLearn. Después de que el código generado plantilla cargado en el editor, en la ventana Explorador de soluciones había renombrado Program.cs a la AssocRuleProgram.cs más descriptiva y Visual Studio retitulado automáticamente clase programa para mí. En la parte superior del código fuente, he borrado todas las referencias a los espacios de nombres innecesarios, sólo las al sistema y Collections.Generic dejando.
La estructura general del programa, con algunas declaraciones WriteLine quitados y algunas ediciones menores para ahorrar espacio, se presenta en figura 3.
Figura 3 Asociación regla Demo estructura del programa
using System;
using System.Collections.Generic;
namespace AssocRuleLearn
{
class AssocRuleProgram
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin demo\n");
List<int[]> transactions = new List<int[]>();
transactions.Add(new int[] { 0, 3, 4, 11 });
transactions.Add(new int[] { 1, 4, 5 });
transactions.Add(new int[] { 3, 4, 6, 7 });
transactions.Add(new int[] { 3, 4, 6, 7 });
transactions.Add(new int[] { 0, 5 });
transactions.Add(new int[] { 3, 5, 9 });
transactions.Add(new int[] { 2, 3, 4, 7 });
transactions.Add(new int[] { 2, 5, 8 });
transactions.Add(new int[] { 0, 1, 2, 5, 10 });
transactions.Add(new int[] { 2, 3, 5, 6, 7, 9 });
ShowList(transactions);
List<int[]> freqItemSets = new List<int[]>();
freqItemSets.Add(new int[] { 2, 5 });
freqItemSets.Add(new int[] { 3, 4 });
freqItemSets.Add(new int[] { 3, 6 });
freqItemSets.Add(new int[] { 3, 7 });
freqItemSets.Add(new int[] { 4, 7 });
freqItemSets.Add(new int[] { 6, 7 });
freqItemSets.Add(new int[] { 3, 4, 7 });
freqItemSets.Add(new int[] { 3, 6, 7 });
ShowList(freqItemSets);
double minConPct = 0.70;
List<Rule> goodRules =
GetHighConfRules(freqItemSets, transactions, minConPct);
Console.WriteLine("\nDone.
Rules are:\n");
for (int i = 0; i < goodRules.Count; ++i)
Console.WriteLine(goodRules[i].ToString());
Console.WriteLine("\nEnd demo\n");
Console.ReadLine();
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
Console.ReadLine();
}
} // Main
static void ShowList(List<int[]> trans)
{
for (int i = 0; i < trans.Count; ++i)
{
Console.Write(i.ToString().PadLeft(2) + ": ( ");
for (int j = 0; j < trans[i].Length; ++j)
Console.Write(trans[i][j] + " ");
Console.WriteLine(")");
}
}
static List<Rule> GetHighConfRules(List<int[]> freqItemSets,
List<int[]> transactions, double minConfidencePct) { .
.
}
static int[] NewCombination(int k) { .
.
}
static int[] NextCombination(int[] comb, int n) { .
.
}
static int[] MakeAntecedent(int[] itemSet, int[]comb) { .
.
}
static int[] MakeConsequent(int[] itemSet, int[]comb) { .
.
}
static int CountInTrans(int[] itemSet,
List<int[]> trans, Dictionary<int[], int> countDict) { .
.
}
static bool IsSubsetOf(int[] itemSet, int[] trans) { .
.
}
static int IndexOf(int[] array, int item, int startIdx) { .
.
}
}
public class Rule
{
public int[] antecedent; // If part
public int[] consequent; // Then part
public double confidence;
public Rule(int[] antecedent, int[] consequent, double confidence)
{
this.antecedent = new int[antecedent.Length];
Array.Copy(antecedent, this.antecedent, antecedent.Length);
this.consequent = new int[consequent.Length];
Array.Copy(consequent, this.consequent, consequent.Length);
this.confidence = confidence;
}
public override string ToString()
{
string s = "IF ( ";
for (int i = 0; i < antecedent.Length; ++i)
s += antecedent[i] + " ";
s += ")";
s = s.PadRight(13);
string t = " THEN ( ";
for (int i = 0; i < consequent.Length; ++i)
t += consequent[i] + " ";
t += ") ";
t = t.PadRight(17);
return s + t + "conf = " + confidence.ToString("F2");
}
}
}
La demo define dos transacciones y sets de objetos como matrices de tipo int y establece una lista de transacciones codificadas. Podrías crear una clase definida por el programa conjunto de ítems. En la mayoría de los casos los datos de transacciones crudo serán en un archivo de texto o base de datos SQL y necesitan ser codificados. La demo se configura hardcoded frecuente-sets de objetos. Excepto en situaciones muy pequeña demostración que usted necesitará extraer frecuentes-sets de objetos mediante programación, que es una tarea muy difícil.
Todo el trabajo de encontrar reglas de alta confianza se realiza por el método GetHighConfRules. Este método requiere un valor de parámetro de porcentaje de confianza mínima especificada por el usuario. Confianza significativos los valores pueden variar de un problema a problema.
El programa de demostración utiliza una clase de regla definida por el programa. Miembros de la clase son el antecedente de la regla (if-part), regla consecuente (entonces parte) y el valor de confianza computada. La clase tiene sólo un constructor y un método ToString, que está hackeado para formatear los datos de demostración bien.
Método GetHighConfRules llama varios métodos auxiliares. Método CountInTrans cuenta el número de veces que un artículo conjunto o antecedente de la regla o consecuente regla ocurre en una lista de transacciones. Este método llama sub ayudante IsSubsetOf, que a su vez llama sub ayudante IndexOf. Método NewCombination crea una combinación matemática. Método NextCombination devuelve el siguiente elemento de la combinación de una combinación determinada. Los métodos MakeAntecedent y MakeConsequent devuelven el if-parte y la parte entonces para una regla de candidato, teniendo en cuenta un conjunto de elemento frecuente y una combinación matemática.
Combinaciones matemáticas
Si te refieres al diagrama en figura 2, usted verá el algoritmo utilizado por el programa de demostración requiere crear combinaciones matemáticas y la capacidad de generar el sucesor de una combinación determinada. Método NewCombination se define como:
static int[] NewCombination(int k)
{
int[] result = new int[k];
for (int i = 0; i < result.Length; ++i)
result[i] = i;
return result;
}
Aquí, una combinación es un arreglo de int. El parámetro de entrada k determina el tamaño de la combinación. Una nueva combinación es valores 0 a través de k-1, en orden. Método NextCombination se define como:
static int[] NextCombination(int[] comb, int n)
{
int[] result = new int[comb.Length];
int k = comb.Length;
if (comb[0] == n - k) return null;
Array.Copy(comb, result, comb.Length);
int i = k - 1;
while (i > 0 && result[i] == n - k + i) --i;
++result[i];
for (int j = i; j < k - 1; ++j)
result[j + 1] = result[j] + 1;
return result;
}
Combinaciones matemáticas son temas fascinantes en la su propia derecho y un poco complicados. Método NextCombination es corto pero no trivial. Acepta una combinación y el número de elementos posibles en la combinación. El método devuelve el sucesor lexicográfico a la combinación de entrada, o null si la combinación de entrada es la última en orden lexicográfico. Por ejemplo, si una combinación con n = 6 y k = 3 es (1, 4, 5) entonces la combinación siguiente es (2, 3, 4).
Generación de regla antecedentes y consecuentes
Método auxiliar MakeAntecedent acepta un conjunto de elemento frecuente y una combinación matemática y devuelve la parte if de una regla de candidato. Por ejemplo, si un conjunto de elemento frecuente (1 3 4 6 8) y una combinación es (0, 2), se extraen los valores del elemento en los índices de 0 y 2 dando un antecedente de (1 de 4):
static int[] MakeAntecedent(int[] itemSet, int[] comb)
{
int[] result = new int[comb.Length];
for (int i = 0; i < comb.Length; ++i) {
int idx = comb[i];
result[i] = itemSet[idx];
}
return result;
}
Aunque corto, el código puede ser un poco confuso porque enteros representan valores de elementos de combinación, artículo artículo-conjunto de valores y los valores del índice artículo conjunto. Si rastrear a través de un ejemplo o dos a mano, deberías ver cómo funciona el método.
Método MakeConsequent genera la parte entonces por una regla de candidato. Por ejemplo, si un conjunto de elemento frecuente (1 3 4 6 8) y una combinación es (0, 2), se extraen los valores del elemento en esos índices no es iguales a 0 y 2 dando un consecuente de (3 6 8), como se muestra aquí:
static int[] MakeConsequent(int[] itemSet, int[] comb)
{
int[] result = new int[itemSet.Length - comb.Length];
int j = 0; // ptr into combination
int p = 0; // ptr into result
for (int i = 0; i < itemSet.Length; ++i) {
if (j < comb.Length && i == comb[j])
++j;
else
result[p++] = itemSet[i];
}
return result;
}
He diseñado MakeConsequent para que acepte la misma paramparámetros como método de MakeAntecedent. Una alternativa algo más simple pero asimétrica es definir MakeConsequent que acepta un conjunto de elemento y un antecedente.
Contando las ocurrencias en las transacciones
Método auxiliar clave CountInTrans acepta una matriz de int que puede representar un conjunto de elemento frecuente o un antecedente de la regla de candidato, una lista de transacciones y una colección de diccionario y devuelve al número de veces que el elemento-set o antecedente se produce. El objeto Diccionario almacena recuentos del artículo y su antecedentes y se utiliza como una búsqueda por los sets de objetos o antecedentes que ya han sido procesados no necesitarán ser relató:
static int CountInTrans(int[] itemSet, List<int[]> trans,
Dictionary<int[], int> countDict)
{
if (countDict.ContainsKey(itemSet) == true)
return countDict[itemSet];
int ct = 0;
for (int i = 0; i < trans.Count; ++i)
if (IsSubsetOf(itemSet, trans[i]) == true)
++ct;
countDict.Add(itemSet, ct);
return ct;
}
La mayor parte del trabajo se realiza por método auxiliar IsSubsetOf. El método aprovecha el hecho de que objetos de transacción se asumen para ser almacenado en orden, lo que significa que después de que se ha encontrado un artículo en particular, la búsqueda para el artículo siguiente puede comenzar en la siguiente posición de índice:
static bool IsSubsetOf(int[] itemSet, int[] trans)
{
int foundIdx = -1;
for (int j = 0; j < itemSet.Length; ++j) {
foundIdx = IndexOf(trans, itemSet[j], foundIdx + 1);
if (foundIdx == -1) return false;
}
return true;
}
Método IndexOf también aprovecha la propiedad ordenada de las transacciones a salida temprana cuando en un índice que está más allá del punto donde podría ser un elemento de destino:
static int IndexOf(int[] array, int item, int startIdx)
{
for (int i = startIdx; i < array.Length; ++i) {
if (i > item) return -1;
if (array[i] == item) return i;
}
return -1;
}
Generación de reglas de alta confianza
Con todos los métodos auxiliares en el lugar, el método GetHighConfRules puede ser definido sin demasiada dificultad. Figura 4 muestra el método en pseudocódigo de alto nivel.
Figura 4 pseudocódigo para el método GetHighConfRules
for each frequent item-set
ctItemSet = count times item-set is in transactions
for subset length 1 to item-set length - 1
create a new math combination
loop over each possible math combination
create candidate rule if-part
create candidate rule then-part
compute confidence of candidate rule
if candidate rule meets min confidence, save
end loop
end for
end for
return saved rules
La implementación del método GetHighConfRules cotiza en figura 5. Aunque se puede utilizar el método GetHighConfRules que se enumeran en figura 5, hay muchas oportunidades para mejorar el rendimiento, generalmente a expensas de la memoria o el código de la claridad. Por ejemplo, si te refieres a figura 2, observará que cada candidato regla antecedente-consecuente par tiene una regla de candidato de espejo con el antecedente y el consecuente cambió. Por ejemplo, si es un artículo-set (2 5 7 9), entonces la regla de un candidato con tamaño de subconjunto k = 2 es IF (2 7) entonces (5 9) y otro candidato regla es IF (5 9) entonces (2 7). Así que en vez de computación antecedentes para todos los valores posibles de tamaño frecuente artículo conjunto subconjunto, sólo puedes calcular antecedentes y consecuentes por mitad los tamaños posibles subconjunto.
Figura 5 método GetHighConfRules
static List<Rule> GetHighConfRules(List<int[]> freqItemSets,
List<int[]> trans, double minConfidencePct)
{
List<Rule> result = new List<Rule>();
Dictionary<int[], int> itemSetCountDict =
new Dictionary<int[], int>();
for (int i = 0; i < freqItemSets.Count; ++i)
{
int[] currItemSet = freqItemSets[i]; // for clarity
int ctItemSet = CountInTrans(currItemSet, trans, itemSetCountDict);
for (int len = 1; len <= currItemSet.Length - 1; ++len)
{
int[] c = NewCombination(len);
while (c != null) // each combination makes a candidate rule
{
int[] ante = MakeAntecedent(currItemSet, c);
int[] cons = MakeConsequent(currItemSet, c); // could defer
int ctAntecendent = CountInTrans(ante, transactions,
itemSetCountDict);
double confidence = (ctItemSet * 1.0) / ctAntecendent;
if (confidence >= minConfidencePct) {
Rule r = new Rule(ante, cons, confidence);
result.Add(r);
}
c = NextCombination(c, currItemSet.Length);
} // while each combination
} // len each possible antecedent for curr item-set
} // i each freq item-set
return result;
}
También, el método CountInTrans utiliza un diccionario de consulta de cuentas guardadas. Esto es útil cuando contar ocurrencias antecedentes porque diferentes conjuntos de elemento frecuentes pueden generar la misma apuestacedentes. Pero si frecuentes-sets de objetos son únicos, entonces el cheque en el diccionario de búsqueda es una pérdida de tiempo. Aviso el parámetro diccionario es tanto usado y se ha actualizado para que querrías lo definen como un parámetro ref a explicitar su doble propósito. Si rastrear mediante el método GetHighConfRules, verás varias otras maneras de modificar el código.
Una posibilidad importante optimización aprovecha el hecho de que, para un determinado conjunto de elemento, si la regla de un candidato no cumple el umbral mínimo de confianza, entonces cualquier otra regla de candidato que contiene consecuente de la primera regla no puede cumplir el umbral de confianza. Por ejemplo, supongamos que una regla si (2 4 8 9) entonces (3 5) no cumple la mínima confianza. Entonces cualquier regla que tiene (3 5) en su consecuente, por ejemplo, si (4 8 9) entonces (2 3 5), no se reunirá la mínima confianza, tampoco.
Resumen
La explicación de las reglas de asociación y código de demostración presentados en este artículo debería llegar arriba y corriendo si quieres experimentar con extracción de reglas de Asociación de alta confianza, crear un programa de utilidad de regla de asociación independiente o agregar funcionalidad de regla de asociación a un programa de aplicación.
A diferencia de varias máquinas técnicas de aprendizaje que se pretenden hacer predicciones, Asociación regla el aprendizaje es una técnica exploratoria prevista revelar relaciones interesantes y posiblemente útiles entre los elementos. Esto significa que tendrás que usar un poco de ensayo y error al encontrar las reglas de asociación.
Hay un gran cuerpo de literatura de la investigación sobre el aprendizaje de reglas de asociación. Si usted está interesado en la teoría, te recomiendo el capítulo 6 del libro "Introducción a la minería de datos" (Addison-Wesley, 2005) p. Bronceado, M. Steinbach y V. Kumar. Capítulo 6 está disponible gratuitamente en formato PDF en bit.ly/1m3dbZ9.
Dr.James McCaffrey trabajos de investigación de Microsoft en Redmond, Washington Ha trabajado en varios productos de Microsoft Internet Explorer y Bing. Dr. McCaffrey puede ser contactado en jammc@microsoft.com.
Gracias al siguiente experto técnico de Microsoft por revisar este artículo: Richard Hughes y Kirk Olynik