Este artigo foi traduzido por máquina.

Execução de teste

Conjuntos de itens frequentes para o aprendizado da regra de associação

James McCaffrey

Baixar o código de exemplo

James McCaffrey
Uma tarefa importante nas áreas de aprendizado de máquina e interfaces de usuário natural (NUIs) está extraindo freqüentes conjuntos-item de uma lista de transações. O problema é melhor explicado por exemplo. Suponha que você tenha uma lista de itens comprados por clientes diferentes em um supermercado. Por exemplo, transações de um cliente podem ser (maçãs, pão, aipo) e outro, pode ser (pão, rosquinhas, ovos, alface). Pode haver muitos milhares dessas transações. Um item-conjunto é um subconjunto de todos os itens possíveis, tais como (maçãs, pão). O problema é extrair a lista de todas as transações apenas aqueles item de moda que atendem uma contagem mínima. Suponha que a contagem mínima é 20 e item-conjunto (maçãs, pão) ocorre na lista de transações 25 vezes; Portanto, (maçãs, pão) seria um conjunto de item freqüente.

Identificar conjuntos-item freqüentes pode ser útil em muitas maneiras. No caso de um supermercado, conhecimento dos quais itens são frequentemente comprados juntos poderia ser usado para colocação de produtos, marketing dirigido e assim por diante. Além disso, uma vez que todos os conjuntos de itens frequentes foram identificados, esses conjuntos de item poderiam ser analisados na sequência extrato regras tais como, "se os clientes adquirir tanto maçãs e pão, em seguida, há grande probabilidade vão também adquiri alface e leite." Esse processo geral de extrair primeiro item freqüente-moda e então colhendo as regras se-então chama-se aprendizagem de regra de associação.

Este artigo explica detalhadamente o processo de extração de item-conjunto freqüentes. O problema é surpreendentemente difícil e tem sido objecto de um pouco de pesquisa. A melhor maneira de ver para onde vai este artigo é para dar uma olhada no programa de demonstração em Figura 1.

Extracting Frequent Item-Sets from Transactions
Figura 1 extraindo freqüentes Item-conjuntos de transações

O programa de demonstração configura uma lista falsa de 10 operações. Nos bastidores, há um total de 12 itens em um supermercado hipotético: maçãs, pão, aipo, rosquinhas, ovos, farinha, uvas, mel, glacê, geléia, couve e alface. A primeira transação é (maçãs, pão, aipo, farinha). O demo, em seguida, mostra como bruta transações podem ser codificadas em base 0 inteiros para processamento eficiente. Porque o pão de maçãs mapas para 0, 1, aipo 2, e assim por diante, a primeira transação é codificada como (0, 1, 2, 5).

O algoritmo para extrair conjuntos-item freqüentes requer três parâmetros de entrada. O primeiro parâmetro é um valor de limiar mínimo necessário para um conjunto de item classificam-se como freqüente. Isso geralmente é chamado de valor de suporte. Na demo, o valor de apoio é definido como 0,30, o que significa que 0.30 * 10 = 3 é o número mínimo de vezes que um item-conjunto deve ocorrer na lista de todas as transações para o conjunto de item a ser adicionado à lista de resultado do item freqüente-moda. Domínios de problemas diferentes terão valores diferentes de apoio significativo.

O segundo parâmetro de entrada é o tamanho mínimo de um conjunto de item. Na demo que valor está definido como 2, então um item-conjunto de (maçãs, donuts) é examinado, mas não é um item-conjunto de apenas (maçãs). O terceiro parâmetro de entrada é o tamanho máximo de um conjunto de item. Aqui que o valor é definido como 4, então o único item-conjuntos com até quatro itens, tais como (maçãs, aipo, ovos, uvas), são examinados enquanto maior item-conjuntos tais como (maçãs, pão, donuts, farinha, mel) não são.

O programa de demonstração, chama o método para extrair conjuntos-item frequentes na lista de transações e encontra um total de 12 conjuntos de item freqüentes. O primeiro conjunto de item freqüente é (0, 1), que ocorre cinco vezes na lista de transação. O último item-conjunto freqüente é (0, 1, 2, 5), que ocorre três vezes. O demo conclui exibindo o item freqüente-moda em forma de seqüência de caracteres.

Este artigo pressupõe que você tem habilidades de programação de nível intermediário, pelo menos, mas não assumir que sabe alguma coisa sobre aprendizagem de regra de associação. O código de programa demo completa é apresentado no presente artigo e está também disponível como um download a partir msdn.microsoft.com/magazine/msdnmag0114. O demo está em c#, mas você não deve ter muito problemas de refatoração para outro idioma, como Python. Tudo normal verificação de erro foi removido para manter o tamanho do código de menores.

Por que é freqüente Item-conjunto de extração um problema difícil?

No primeiro pensamento, extrair freqüentes conjuntos-item de uma lista de transações não parece tão difícil. Uma abordagem de força bruta simples seria simplesmente gerar todos os possíveis conjuntos item e iterar por meio de transações para cada candidato, contando o número de vezes que o candidato aparece ver se esse item-conjunto reúne-se a contagem de suporte mínimo. Infelizmente, em tudo mas artificialmente pequenos problemas, o número de conjuntos possíveis de item é inimaginavelmente grande. Por exemplo, um supermercado típico pode ter até agora mais de 10.000 itens diferentes em estoque. O número de item-conjuntos de tamanho 2 é escolhe (10.000, 2) = 49,995,000, onde o Choose (n, k) é o número de maneiras de selecionar itens k de n itens. O número de item-conjuntos possíveis de tamanho 9 é escolhe (10.000, 9) = 2,745,826,321,280,434,929,668,521,390,000, que é... bem, muito.

Existem vários algoritmos inteligentes para extrair eficientemente freqüentes conjuntos-item de uma lista de operações, incluindo os algoritmos Apriori, Eclat e FP-crescimento. Cada algoritmo tem muitas variações. O programa de demonstração usa uma variação do algoritmo Apriori, que é ilustrado no Figura 2.

The Apriori Algorithm in Action
Figura 2 o algoritmo Apriori em ação

Brevemente, o algoritmo Apriori começa com todos os item freqüentes-conjuntos de tamanho k = 1 — itens individuais que atendem o limite de suporte na lista de transações. Em seguida, o processo de construção iterativamente adiciona item-conjuntos frequentes de tamanho k = 2, 3 e assim por diante, até que nenhum novo item-moda freqüente é encontrado.

A imagem em Figura 2 mostra como item-conjuntos de tamanho k = 4 são construídos. É mantida uma lista única de item-conjuntos frequentes de todos os tamanhos. Na figura, existem atualmente três item freqüentes-conjuntos com tamanho k = 3: (0, 2, 3), (0, 2, 8) e (0, 3, 6). O algoritmo também mantém uma lista de itens que são válidos em qualquer ponto no tempo. Aqui são cinco itens válidos: {0, 2, 3, 6, 8}. Itens válidos para construir conjuntos-item freqüentes de tamanho k = 4 são os itens distintos em todos os item freqüentes-conjuntos de tamanho k-1 = 3.

O algoritmo verifica cada item freqüente-conjunto de tamanho k = 3. Para cada item-conjunto existente, um novo candidato freqüente item-conjunto de tamanho k = 4 é gerado. Então, o primeiro candidato é (0, 2, 3,?). O? pode ser preenchido com um item válido. O algoritmo pressupõe que os itens dentro de um conjunto de item são sempre armazenados em ordem, então o? pode ser apenas 6 ou 8 neste caso. Cada novo candidato é examinado para contar quantas vezes ocorre na lista de transações. Se a contagem de transações com a contagem mínima de apoio, o candidato é adicionado à lista de conjuntos de item freqüentes.

O algoritmo reduz bastante a quantidade de cálculo necessário, em comparação com a abordagem de geração de força bruta. Por exemplo, observe que o segundo freqüente item-conjunto existente com tamanho k = 3 é (0, 2, 8). Os potenciais candidatos terão forma (0, 2, 8,?). Mas porque nenhum item válido for maior que 8, não há nenhum possíveis candidatos gerados.

Estrutura geral do programa

A estrutura geral do programa de demonstração, com algumas declarações de WriteLine removidas e algumas pequenas edições, é apresentada em Figura 3. Para criar o demo, lançou o Visual Studio 2012 e criou um novo programa de aplicativo de console chamado FreqItemSets. O demo não tem significativa .NET dependências, e qualquer versão relativamente recente do Visual Studio vai funcionar bem. Depois o código do modelo carregados para o editor, na janela Solution Explorer, renomeei o arquivo Program.cs para FreqItemSetProgram.cs, e Visual Studio automaticamente renomeado classe programa para mim.

Figura 3 Demo programa estrutura

using System;
using System.Collections.Generic;
namespace FreqItemSets
{
  class FreqItemSetProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin frequent item-set extraction demo\n");
        string[] rawItems = new string[] { "apples", "bread ", "celery", "donuts",
          "eggs  ", "flour ", "grapes", "honey ", "icing ", "jelly ",
             "kale  ", "lettuce" };
        int N = rawItems.Length; // total number of items to deal with ( [0..11] )
        string[][] rawTransactions = new string[10][];
        rawTransactions[0] = new string[] { "apples", "bread ", "celery",
           "flour " };
        rawTransactions[1] = new string[] { "bread ", "eggs  ", "flour " };
        rawTransactions[2] = new string[] { "apples", "bread ", "donuts",
           "eggs  " };
        rawTransactions[3] = new string[] { "celery", "donuts", "flour ",
           "grapes" };
        rawTransactions[4] = new string[] { "donuts", "eggs  " };
        rawTransactions[5] = new string[] { "donuts", "eggs  ", "jelly " };
        rawTransactions[6] = new string[] { "apples", "bread ", "donuts",
           "icing " };
        rawTransactions[7] = new string[] { "bread ", "grapes", "honey " }; 
        rawTransactions[8] = new string[] { "apples", "bread ", "celery",
           "flour ", "kale  " };
        rawTransactions[9] = new string[] { "apples", "bread ", "celery",
           "flour " };
        for (int i = 0; i < rawTransactions.Length; ++i) {
          Console.Write("[" + i + "] : ");
          for (int j = 0; j < rawTransactions[i].Length; ++j)
            Console.Write(rawTransactions[i][j] + "   ");
          Console.WriteLine("");
        }
        List<int[]> transactions = new List<int[]>();
        transactions.Add(new int[] { 0, 1, 2, 5 });
        transactions.Add(new int[] { 1, 4, 5 });
        transactions.Add(new int[] { 0, 1, 3, 4 });
        transactions.Add(new int[] { 2, 3, 5, 6 });
        transactions.Add(new int[] { 3, 4 });
        transactions.Add(new int[] { 3, 4, 9 });
        transactions.Add(new int[] { 0, 1, 3, 8 });
        transactions.Add(new int[] { 1, 6, 7 });
        transactions.Add(new int[] { 0, 1, 2, 5, 10 });
        transactions.Add(new int[] { 0, 1, 2, 5 });
        for (int i = 0; i < transactions.Count; ++i) {
          Console.Write("[" + i + "] : ");
          for (int j = 0; j < transactions[i].Length; ++j)
            Console.Write(transactions[i][j].ToString() + " ") ;
          Console.WriteLine("");
        }
        Console.WriteLine("");
        double minSupportPct = 0.30;
        int minItemSetLength = 2;
        int maxItemSetLength = 4;
        List<ItemSet> frequentItemSets =
          GetFrequentItemSets(N, transactions, minSupportPct,
          minItemSetLength, maxItemSetLength);
        Console.WriteLine("\nFrequent item-sets in numeric form are:");
        for (int i = 0; i < frequentItemSets.Count; ++i)
          Console.WriteLine(frequentItemSets[i].ToString());
        Console.WriteLine("\nFrequent item-sets in string form are:");
        for (int i = 0; i < frequentItemSets.Count; ++i) {
          for (int j = 0; j < frequentItemSets[i].data.Length; ++j) {
            int v = frequentItemSets[i].data[j];
            Console.Write(rawItems[v] + "   ");
          }
          Console.WriteLine("");
        }
        Console.WriteLine("\nEnd frequent item-set extraction demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);  Console.ReadLine();
      }
    }
    static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
      double minSupportPct, int minItemSetLength, int maxItemSetLength) { .
.
}
    static int CountTimesInTransactions(ItemSet itemSet,
      List<int[]> transactions) { .
.
}
  }
  public class ItemSet { .
.
}
} // ns

Na parte superior do código-fonte, apaguei todas as referências desnecessárias para namespaces .NET, deixando apenas o sistema e o Collections.Generic. A demo começa pela criação de uma coleção de todos os itens em um supermercado hipotético:

string[] rawItems = new string[] { "apples", "bread ", "celery",
  "donuts", "eggs  ", "flour ", "grapes", "honey ", "icing ",
  "jelly ", "kale  ", "lettuce" };
int N = rawItems.Length; // total items in inventory

Em seguida o programa configura 10 transações de disco rígido-codificado. Na maioria dos cenários, suas transações serão armazenadas em um arquivo de texto ou banco de dados SQL. Observe as transações duplicadas são permitidas e nem todos os itens em estoque são necessariamente em uma transação:

string[][] rawTransactions = new string[10][];
rawTransactions[0] = new string[] { "apples", "bread ", "celery", "flour "};
rawTransactions[1] = new string[] { "bread ", "eggs  ", "flour " };
...
rawTransactions[9] = new string[] { "apples", "bread ", "celery", "flour "};

Depois de exibir as transações crus, o demo define uma lista de transações codificadas base 0. Em vez de embutir, na maioria das situações você programaticamente criaria as transações numéricas das operações crus. Observe que os itens em cada transação distintos e classificados:

List<int[]> transactions = new List<int[]>();
transactions.Add(new int[] { 0, 1, 2, 5 });
transactions.Add(new int[] { 1, 4, 5 });
...
transactions.Add(new int[] { 0, 1, 2, 5 });

Depois de exibir a lista de transações, o valor do parâmetro de entrada três são configurados. Aqui, o tamanho máximo de um conjunto de item freqüente é definido como 4. Você pode querer verificar a lista de transações e defina o valor para o comprimento de transação mais longa:

double minSupportPct = 0.30;
int minItemSetLength = 2;
int maxItemSetLength = 4;

Todo o trabalho é realizado por uma chamada ao método GetFrequentItemSets:

List<ItemSet> frequentItemSets =
  GetFrequentItemSets(N, transactions, minSupportPct,
  minItemSetLength, maxItemSetLength);

Observe que o resultado de retorno usa uma classe de conjunto de itens definidos pelo programa. O demo conclui indicando o item freqüente-moda em forma tanto numéricos e string.

A classe de conjunto de itens

Em essência, um conjunto de item é apenas uma matriz de inteiros, portanto, nenhuma classe definida pelo programa é necessário. Mas, na minha opinião, neste caso usar uma classe simplifica o código. O conjunto de itens classe é definida em Figura 4.

Figura 4 a classe do conjunto de itens

public class ItemSet
{
  public int N; // data items are [0..N-1]
  public int k; // number of items
  public int[] data; // ex: [0 2 5]
  public int hashValue; // "0 2 5" -> 520 (for hashing)
  public int ct; // num times this occurs in transactions
  public ItemSet(int N, int[] items, int ct) { .
.
}
  private static int ComputeHashValue(int[] data) { .
.
}
  public override string ToString() { .
.
}
  public bool IsSubsetOf(int[] larger) { .
.
}
  private static int IndexOf(int[] array, int item, int startIdx) { .
.
}
}

Campo de membro N é o número total de itens em estoque. Campo k é o tamanho do conjunto de item. Dados da matriz contém os valores do item. Campo hashValue é um inteiro exclusivo para identificar o conjunto de item para que item-moda duplicado pode ser evitado. Ct de campo é o número de vezes que o item-conjunto aparece na lista de transações. O construtor de conjunto de itens é definido:

public ItemSet(int N, int[] items, int ct)
{
  this.N = N;
  this.k = items.Length;
  this.data = new int[this.k];
  Array.Copy(items, this.data, items.Length);
  this.hashValue = ComputeHashValue(items);
  this.ct = ct;
}

O método auxiliar para calcular o hashValue é:

private static int ComputeHashValue(int[] data)
{
  int value = 0;
  int multiplier = 1;
  for (int i = 0; i < data.Length; ++i) {
    value = value + (data[i] * multiplier);
    multiplier = multiplier * 10;
  }
  return value;
}

O auxiliar converte os valores de item para um único inteiro no sentido inverso. Por exemplo, se os itens são (0, 2, 5), o valor de hash é 520. O método funciona em sentido inverso para lidar com 0-itens principais, porque caso contrário (0, 2, 5) e (2, 5) que ambos de hash para 25.

IsSubsetOf método retorna true se o objeto de conjunto de item é um subconjunto de uma transação:

public bool IsSubsetOf(int[] trans)
{
  int foundIdx = -1;
  for (int j = 0; j < this.data.Length; ++j) {
    foundIdx = IndexOf(trans, this.data[j], foundIdx + 1);
    if (foundIdx == -1) return false;
  }
  return true;
}

O método é curta, mas um pouco sutil. Porque as transações e conjuntos de item são ordenados, após o valor de um item de um item-conjunto foi encontrado dentro de uma transação, a pesquisa para o próximo valor do item não tem que começar no índice 0 — pode começar com o próximo índice seguindo o local onde o valor do item anterior foi encontrado. Auxiliar IndexOf é definida:

private static int IndexOf(int[] array, int item, int startIdx)
{
  for (int i = startIdx; i < array.Length; ++i) {
    if (i > item) return -1; // i is past target loc
    if (array[i] == target) return i;
  }
  return -1;
}

Método IndexOf também tira proveito de ordenação. Se o índice de pesquisa atual é maior do que o valor do item de destino sendo procurado, a busca foi longe demais e nunca irá encontrar o item. Por exemplo, suponha que uma transação é (0, 2, 4, 5, 6, 8) e o item de destino sendo procurado é 3. Porque as transações são ordenadas, pode ocorrer o valor mais recente 3 seria em uma transação que tem forma (0, 1, 2, 3, x, x). O ToString método usa concatenação de seqüência de caracteres para a simplicidade:

public override string ToString()
{
  string s = "{ ";
  for (int i = 0; i < data.Length; ++i)
    s += data[i] + " ";
  return s + "}" + "   ct = " + ct; ;
}

O método GetFrequentItemSets

Começa a definição do método GetFrequentItemSets:

static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
  double minSupportPct, int minItemSetLength, int maxItemSetLength)
{
  int minSupportCount = (int)(transactions.Count * minSupportPct);
...

Em vez de especificar um parâmetro de entrada para que o limite de suporte como uma porcentagem de transações, você pode querer usar uma contagem absoluta. Em seguida, três coleções importantes são instanciadas:

Dictionary<int, bool> frequentDict = new Dictionary<int, bool>();
List<ItemSet> frequentList = new List<ItemSet>();
List<int> validItems = new List<int>();
...

FrequentList coleção contém todos os freqüentes conjuntos de item encontrados. Em vez de armazenar conjuntos de item freqüentes de todos os tamanhos em uma única lista, uma importante alternativa é usar uma matriz de listas onde existem listas separadas para cada tamanho de conjunto de item. FrequentDict coleção contém as identificações daqueles item de moda que foram adicionadas ao frequentList para que duplicatas podem ser evitadas. ValidItems coleção armazena valores de item que, em qualquer ponto no algoritmo, podem ser adicionados a um item existente freqüente-conjunto de tamanho k-1, para gerar um candidato freqüente item-conjunto de tamanho k. Em seguida, os valores de cada item na lista de transação são contados:

int[] counts = new int[N];
for (int i = 0; i < transactions.Count; ++i)
{
  for (int j = 0; j < transactions[i].Length; ++j) {
    int v = transactions[i][j];
    ++counts[v];
  }
}
...

Em seguida, esses valores de item que atendem a contagem mínima de suporte são usados para criar objetos de conjunto de itens frequentes de tamanho k = 1, que são adicionados à lista de itens frequentes:

for (int i = 0; i < counts.Length; ++i)
{
  if (counts[i] >= minSupportCount) {
    validItems.Add(i); // i is the item-value
    int[] d = new int[1]; // ItemSet ctor wants an array
    d[0] = i;
    ItemSet ci = new ItemSet(N, d, 1); // size 1, ct 1
    frequentList.Add(ci); // it's frequent
    frequentDict.Add(ci.hashValue, true); // record
  } // else skip this item
}
...

O loop de processamento principal, em pseudocódigo, é:

loop for size k = 2, 3, until done
  foreach existing freq item-set of size k-1
    foreach valid item
      create a candidate item-set
      count times candidate in transactions
      if candidate meets support threshold
        if candidate not already in frequent list
          add candidate to frequent, rec list
    end each valid item
    update valid items
  end each freq item-set
end main loop

O loop de processamento principal é definido como assim:

bool done = false;
for (int k = 2; k <= maxItemSetLength && done == false; ++k)
{
  done = true;
  int numFreq = frequentList.Count;
...

O loop principal vai sair quando todos os tamanhos especificados foram exame­ined, ou quando não encontram-se nenhum novo item-moda do tamanho atual. Porque todos os conjuntos frequentes item são armazenados em uma única lista (e essa lista é adicionada ao), o tamanho inicial da lista é armazenado para uso pelos loops internos, que são definidos como assim:

for (int i = 0; i < numFreq; ++i)
{
  if (frequentList[i].k != k - 1) continue;
  for (int j = 0; j < validItems.Count; ++j)
  {
    int[] newData = new int[k]; // data for a candidate item-set
...

Duas características importantes do algoritmo são que o algoritmo usa apenas freqüente item-moda da iteração anterior para construir novo candidato item-moda e analisam-se valores de item só é válido para completar os candidatos. Os candidato freqüente item conjuntos são criados:

for (int p = 0; p < k - 1; ++p)
  newData[p] = frequentList[i].data[p];
if (validItems[j] <= newData[k - 2]) continue;
newData[k - 1] = validItems[j];
ItemSet ci = new ItemSet(N, newData, -1);
...

Esse código é um pouco complicado. Primeiro, os dados do atual item freqüente-conjunto são copiados para o candidato. O candidato é completado com o valor atual do item válido e, conforme descrito anteriormente, os candidatos podem ser eliminados baseado na propriedade de item-conjuntos de ordenação. O conjunto de itens construtor aceita um valor fictício de -1 para o campo do ct, porque ainda não é conhecido o número de vezes que o candidato aparece nas transacções.

Os dois loops internos são amarrados com o código mostrado na Figura 5.

Figura 5-amarrando os dois Loops interno

...
if (frequentDict.ContainsKey(ci.hashValue) == true)
      continue;
    int ct = CountTimesInTransactions(ci, transactions);
    if (ct >= minSupportCount)
    {
      ci.ct = ct;
      frequentList.Add(ci);
      frequentDict.Add(ci.hashValue, true);
      done = false;
    }
  } // j
} // i
...

Se o candidato já aparece na lista de item-conjunto freqüente, não há nenhuma necessidade de analisá-lo ainda mais. Se não, e se o candidato atende a contagem mínima de apoio, o candidato é um vencedor... e ele é adicionado à lista de conjuntos de item freqüentes. Boolean feito faixas ou não foram encontrado qualquer novo item-moda. Para qualquer dado valor de k, se nenhum novo item-moda freqüente encontram-se, não há nenhuma possibilidade de que um item freqüente-conjunto nunca será encontrado.

Depois de todos os candidatos para o atual tamanho k foram construídos e examinados, a lista de itens válidos para a próxima iteração é atualizada, como mostrado em Figura 6.

Figura 6-actualização da lista de itens válidos

...
validItems.Clear();
  Dictionary<int, bool> validDict = new Dictionary<int, bool>();
  for (int idx = 0; idx < frequentList.Count; ++idx) {
    if (frequentList[idx].k != k) continue;
    for (int j = 0; j < frequentList[idx].data.Length; ++j) {
      int v = frequentList[idx].data[j]; // item
      if (validDict.ContainsKey(v) == false) {
        validItems.Add(v);
        validDict.Add(v, true);
      }
    }
  }
        validItems.Sort();
} // next k
...

Embora não inteiramente óbvio no início, parece que ao construir o novo candidato freqüente item-conjuntos de tamanho k usando existentes item freqüentes-conjuntos de tamanho k-1, os itens só é válidos para completar os candidatos são valores de item que ocorrem no item-define freqüente de tamanho k-1. Este processo de atualização é demorado e em alguns cenários você terá melhor desempenho por ignorar isso e em vez disso, usando a lista original de itens válidos criado para tamanho k = 1.

O método conclui filtrando os resultados por comprimento mínimo do conjunto de item:

...
List<ItemSet> result = new List<ItemSet>();
  for (int i = 0; i < frequentList.Count; ++i)
  {
    if (frequentList[i].k >= minItemSetLength)
    result.Add(new ItemSet(frequentList[i].N,
      frequentList[i].data, frequentList[i].ct));
  }
  return result;
}

Método auxiliar CountTimesInTransactions, utilizado anteriormente, é definido:

static int CountTimesInTransactions(ItemSet itemSet,
  List<int[]> transactions)
{
  int ct = 0;
  for (int i = 0; i < transactions.Count; ++i) {
    if (itemSet.IsSubsetOf(transactions[i]) == true)
      ++ct;
  }
  return ct;
}

Resumindo

O código e a explicação apresentada neste artigo devem ficar pronto se você precisar determinar freqüentes conjuntos de item em uma lista de transações usando o algoritmo Apriori. Embora seja improvável que alguma vez irá trabalhar diretamente com as operações de supermercado, existem muitos cenários onde extrair conjuntos-item freqüentes pode ser útil. No caso de NUI, você pode pensar de transações como uma lista de comandos do usuário — por exemplo, o texto digitado em uma caixa de texto de pesquisa — e os itens que as palavras que compõem o comando. Identificar as palavras que freqüentemente ocorrem juntos pode ajudar a gerar melhores resultados de pesquisa.

Dr. James McCaffrey funciona para Microsoft Research em Redmond, Wash. Ele trabalhou em vários produtos Microsoft, incluindo o Internet Explorer e Bing. Ele pode ser contatado em jammc@microsoft.com.

Agradecemos ao seguinte especialista técnico pela revisão deste artigo: Richard Hughes (Microsoft Research)